id:syou6162が常時ベイジアンだと思うなよ、ということでsubmodularな論文。去年のACLにもsubmodularを使って要約のdecodeをやるという論文が出ていたが、同一著者によるこれの発展研究。しっかりしていていい論文だと思う。スライドもある。この著者らのページを見に行ってみると、今年のACLでもう一本submodularを使った論文を通していて、こっちはword alignmentに使ったらしい(あとで読みたい)。 さて、去年の内容をざっと復習すると 要約のdecoding部分は制約付き最適化問題として定式化されることが多い よく線形計画問題(ILP)として落とし込まれていたが、最適化にめっちゃ時間がかかる*1 この論文では目的関数がmonotoneかつsubmodularという形式をしていればgreedyなアルゴリズム(実装がめっちゃ簡単!!)で最悪ケースの保証がで