#9 Multi-document summarization via budgeted maximization of submodular functions

NIPSが機械学習の最前線だとするなら、その中でもhotなsubmodularは機械学習の中でもhotなトピックなはず。NLPは離散最適化とかなり密接に関係している分野なので、submodularが進展すればNLPもちょっとづつ進展、ということで今回はsubmodularを使った要約のお話。submodularについてはICMLやIJCAIといった機械学習、人工知能系学会のトップカンファレンスでチュートリアルが開かれているので、そちらを見ていただきたい。

ざっくりと説明すると、離散最適化を考えるときにとある性質(submodularity)を見たすようなものについてはgreedyに攻めていくようなアルゴリズムでも最悪ケースのboundが理論的に保証できるし、実験でもそのboundよりももっといいところに行けると色々なケースで示されているよ、greedyにやっていけばいいのでILPより高速に簡単に(ものによっては違うかもしれないが、この論文のアルゴリズムはめちゃくちゃ簡単)実行できるよ、というもの。

アルゴリズム

基本的にはAlgorithm 1のline 4のような関数についてgreedyにいいやつを選んでいくだけ。boundを保証するためにline 8と9でちょっと変則的にはなっているけど、ここも実装するのは簡単。line 4の分子は「今持ってる集合にlを追加したら評価値はよくなるかな?」というもので分母はそれのコストを勘定したようなtermとなっている。r乗というのがいかにも怪しげで「これなかったらどうなるねん」とつっこみたくなるが、(Khuller et al., 1999)でそういう場合は最悪ケースの関数の評価値が保証できなくなってしまうということが示されている。「greedyにやって高速に実行できるのはうれしいんだが、ある程度うまくいく理論的な保証が欲しい」と思ってしまうのが人の常なので、この論文ではそのような性質を得られるように2つの修正をほどこしている。一つ目はline 8と9で二つ目はr乗(この論文ではscaling factorと呼ばれている)。こやつらを導入することで、さっき言ったようなうれしい効果を得ることができる。

解析

肝の証明のところはAppendixに書いてあるが、ちゃんと追ってみるとそんなに難しくない(が、自分はLemma 2が数学的帰納法の初期ステップになっていることに気づかずあれこれやろうとしていたので無駄に時間を食ってしまったorz)。scaling factor r = 1のときはinstanceによらずlower boundを導くことができて、それ以外のときもきちんとboundを求めることができる。で、ここまではかっこよかったんだが、Theorem 3付近はあんまりかっこよくない。さっき言った性質はmonotoneである仮定の元で得られるのであるが、この実験で使うMMR(情報量のカバレッジと冗長性の両方を考えたような指標、らしい。要約ではよく使われる関数)はそれを満たしていない(ので、確率的にnear-optimallyであると一応書いてはある)。が、きっとmonotoneでかつ要約によさそうなsubmodular functionは誰かがもう考えてる気が(ry。

実験

同じ最適化問題をILP*1でも定式化することができるので、それを実行した結果とsubmodularを使ってgreedyにやったときの結果をまず比較している。ILPのほうは最適解が出るので、ILPに勝つことはないんだが、どこまで迫れるか。結果は結構いい線いってて、rをうまいこと調整してやればoptimal solutionにexactにいっている(この場合は。論文だからあえてそういう例を持ってきたんだろうけど)。

あと注目しておかないといけないのは計算時間。ILPを使った場合には17時間かかるらしいが、このアルゴリズムだと0.001秒もかからず終わる。この差は圧倒的...。パラメータチューニングするときとかに大分(というか相当)楽になりそうな感じだ。

目的関数だけでなく、もちろんROUGEの評価のほうも見ないといけないのだが、rを調整してあげるとbest system in DUC04のものやグラフベースの教師なしの要約システムよりもよいROUGEの評価値を得ることに成功している。greedyなくせにこれは。

まとめ

使う側としては

  • simple、高速
  • 理論的なboundが保証できる
  • 実験でもいい性能を残している

ということで使い勝手がよさそうなアルゴリズムである(プログラミングある程度できる人ならNLP詳しくなくても半日程度でstate of art並みの性能を出すものが作れる、という意味で脅威的)。今度これと争っていく側としてはmonotonisityを満たしつつ、要約により適切なsubmodular functionをどのように定義していくか、が鍵になっていくのかなと勝手に思っている。

@inproceedings{Lin:2010:MSV:1857999.1858133,
 author = {Lin, Hui and Bilmes, Jeff},
 title = {Multi-document summarization via budgeted maximization of submodular functions},
 booktitle = {Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
 series = {HLT '10},
 year = {2010},
 isbn = {1-932432-65-5},
 location = {Los Angeles, California},
 pages = {912--920},
 numpages = {9},
 url = {http://portal.acm.org/citation.cfm?id=1857999.1858133},
 acmid = {1858133},
 publisher = {Association for Computational Linguistics},
 address = {Stroudsburg, PA, USA},
} 

*1:MOSEKというsolverが使われていたのだが、有名なsolverなんだろうか?