ACLid:syou6162が常時ベイジアンだと思うなよ、ということでsubmodularな論文。去年のACLにもsubmodularを使って要約のdecodeをやるという論文が出ていたが、同一著者によるこれの発展研究。していていい論文だと思う。alignmentに使ったらしい(あとで読みたい)。去年の内容をざっと復習すると要約のdecoding部分は制約付き最適化問題として定式化されることが多いよく線形計画問題(ILP)として落とし込まれていたが、最適化にめっちゃ時間がかかる*1この論文では目的関数がmonotoneかつsubmodularという形式をしていればgreedyなアルゴリズム(実装がめっちゃ簡単!!)で最悪ケースの保証ができるということを証明した実験的には最悪ケースよりずっといいところに行くことが多いことも示したという感じの内容だったが、肝心の目的関数がsubmodularだけどmonotoneではないということから最悪ケースの保証がきちんとはできていなかった(実験ではいいところにいってたんだけどね)。いうわけでこの論文のcontributionとしては「submodularかつmonotone」な目的関数を設計、最悪時の性能保証をきちんとできるこの目的関数をgreedyなアルゴリズムに食わせて実験。去年のものよりもさらにいいパフォーマンスを出すことを示した最悪ケースが保証できるだけじゃないよ、ってことこれまでの要約タスクに使われていた目的関数をsubmodularを使って定式化。submodularが要約タスクに自然にfitするものであることを示した。ROUGEとか「submodularで定式化したはいいけど、それって要約に合ってるの?」っていう問にある程度の答えを与えてくれる、と考えることができるという感じ。SubmodularityVをオブジェクトの集合(要約ではsentenceの集合),FをVの部分集合を入力として実数を返すような集合関数とする。要約タスクは部分集合の数がk以下でFを最大にするような最適化問題と捉えることができる(あるいは文中の単語数の和がk以下)。でかい集合Bにvを足したときの増加分よりも、ちっちゃい集合Aにvを足したときの増加分のほうが大きいよ、ということを言っている。returns(収穫逓減の法則)のことである。nondecreasingであるという。Objectivesよい要約はrelevance(正解の要約に対して類似度が高い)とnon-redundancy(正解の要約がいくつかあったりしたらなるべく多くのトピックを包含してて欲しい。MMRなんかまさにそれ)。MMRのようなアプローチ、つまり冗長性に対してペナルティを付けていくようなものでは目的関数のmonotonicityが壊れてしまうということが知られている。diversityというものを考えることにした。algorithmが適用できかつ最悪ケースも保証できる。以下はそれを満たすようにどうL(S)とR(S)を設計していくか、という話。functionのL(S)の項。要約されるべきものとの類似度的なものと解釈できるような集合関数。functionが満たすべき性質を考えていくと自然とsubmodularの性質が出てくるという話が少し書いてある(エントロピーの例などを出しながら)。この論文ではL(S)をとしている。submodularな関数。submodular。submodularとなる。なるのは文iが要約Sによって十分カバーされた場合を意味している(もう増えない、さちっている)。diminishes)。submodularはC_iをどのように設計していくかについて考えよう。iとjの間の類似度(実際の実験のところではtf-idfを使ってコサイン類似度を使っている)。FunctionのR(S)の項。diversity)という形で以下を目的関数に足してやるという風に設計してやる。分からないので、要素毎に見ていくことにする。それぞれはdisjoint。vectorを特徴ベクトルとしてK個にただK-meansでクラスタリングするだけっぽい)。文iの要約にとっての重要性を表わしている。文iと文jの類似度で、自分以外の文への類似度を平均しているようなものを考えている。Summarization関連記事2017-12-04マージン最大化近傍法の読書メモ社内で異常検知本の輪講を進めています。今回は近傍法による異...2016-01-01研究発表これまで行なってきた研究内容です。(1)スターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。