#30 A class of Submodular Functions for Document Summarization

id:syou6162が常時ベイジアンだと思うなよ、ということでsubmodularな論文。去年のACLにもsubmodularを使って要約のdecodeをやるという論文が出ていたが、同一著者によるこれの発展研究。しっかりしていていい論文だと思う。スライドもある。この著者らのページを見に行ってみると、今年のACLでもう一本submodularを使った論文を通していて、こっちはword alignmentに使ったらしい(あとで読みたい)。

さて、去年の内容をざっと復習すると

要約のdecoding部分は制約付き最適化問題として定式化されることが多い
- よく線形計画問題(ILP)として落とし込まれていたが、最適化にめっちゃ時間がかかる*1
この論文では目的関数がmonotoneかつsubmodularという形式をしていればgreedyなアルゴリズム(実装がめっちゃ簡単!!)で最悪ケースの保証ができるということを証明した
- 実験的には最悪ケースよりずっといいところに行くことが多いことも示した

という感じの内容だったが、肝心の目的関数がsubmodularだけどmonotoneではないということから最悪ケースの保証がきちんとはできていなかった(実験ではいいところにいってたんだけどね)。で、それを誰かがやるだろうとメモにも書いているわけだけど、その人らがやってしまったというわけだ(論文中だとSection 4がそれに相当)。

そういうわけでこの論文のcontributionとしては

「submodularかつmonotone」な目的関数を設計、最悪時の性能保証をきちんとできる
この目的関数をgreedyなアルゴリズムに食わせて実験。去年のものよりもさらにいいパフォーマンスを出すことを示した
- 最悪ケースが保証できるだけじゃないよ、ってこと
これまでの要約タスクに使われていた目的関数をsubmodularを使って定式化。submodularが要約タスクに自然にfitするものであることを示した。例えばROUGEとか
- 「submodularで定式化したはいいけど、それって要約に合ってるの?」っていう問にある程度の答えを与えてくれる、と考えることができる

という感じ。

Background on Submodularity

Vをオブジェクトの集合(要約ではsentenceの集合),FをVの部分集合を入力として実数を返すような集合関数とする。要約タスクは部分集合の数がk以下でFを最大にするような最適化問題と捉えることができる(あるいは文中の単語数の和がk以下)。

submodular functionとは

任意の $A \subset B \subset V \setminus v$ に対して、Fがsubmodular functionであるとは $F(A + v) - F(A) \geq F(B + v) - F(B)$ ということ。でかい集合Bにvを足したときの増加分よりも、ちっちゃい集合Aにvを足したときの増加分のほうが大きいよ、ということを言っている。これは経済の分野とかではよく知られているdiminishing returns(収穫逓減の法則)のことである。

monotone nondecreasingとは

任意の $A \subset B$ に対して $F(A) \leq F(B)$ であるとき、Fはmonotone nondecreasingであるという。

諸性質

$\{F_i\}_i$ がsubmodular関数で $\alpha_i$ を非負の重みとしたときに $F = \sum_i \alpha_i F_i$ もまたsubmodular関数
Fをnondecreasing submodular関数、fをnondecreasing concaveな関数とするとき、fとFの合成(例えば $F^\prime(s) = f(F(S))$ )もnondecreasing submodular関数(Theorem 1)

Monotone Submodular Objectives

よい要約はrelevance(正解の要約に対して類似度が高い)とnon-redundancy(正解の要約がいくつかあったりしたらなるべく多くのトピックを包含してて欲しい。いくら正解のものに含まれているからって似たようなものがいっぱいあってもうれしくないので冗長性は減らしたい)の2つを満たしている必要がある(maximum marginal relevance: MMRなんかまさにそれ)。しかし、MMRのようなアプローチ、つまり冗長性に対してペナルティを付けていくようなものでは目的関数のmonotonicityが壊れてしまうということが知られている。そこで、これの代わりに著者らは正のreward diversityというものを考えることにした。具体的には
$F(S) = L(S) + \lambda R(S)$
というもので、L(S)は要約されるべきものとの類似度的なもの、R(S)はSの多様性の度合い(どんだけカバーできてるか)、 $\lambda$ を0以上としておく。あとはL(S)とR(S)のそれぞれがnondecreasing submodularなように設計すればF(S)もnondecreasing submodularになる(see also: 諸性質)のでgreedy algorithmが適用できかつ最悪ケースも保証できる。以下はそれを満たすようにどうL(S)とR(S)を設計していくか、という話。

Coverage function

$F(S) = L(S) + \lambda R(S)$ のL(S)の項。要約されるべきものとの類似度的なものと解釈できるような集合関数。論文中ではcoverage functionが満たすべき性質を考えていくと自然とsubmodularの性質が出てくるという話が少し書いてある(エントロピーの例などを出しながら)。この論文ではL(S)を
$L(S) = \sum_{i \in V} \mbox{min}(C_i(S), \alpha C_i(V))$
としている。ここで、 $C_i(\cdot)$ はnondecreasing submodularな関数。また

$f(x) = \mbox{min}(x, a), \mbox{where} a \geq 0$

はconcaveでnondecreasingな関数であり、各C_iはnondecreasing submodularであるから和の各項はnondecreasing submodular。nondecreasing submodularの和もnondecreasing submodularなのでL(S)もnondecreasing submodularとなる。

$\mbox{min}(C_i(S), \alpha C_i(V)) = \alpha C_i(V)$ となるのは文iが要約Sによって十分カバーされた場合を意味している(もう増えない、さちっている)。さちった後は $C_i(S)$ の項は関係なくなるので目的関数には寄与しない(return diminishes)。

(minとかの解釈についてあとで書く...)

さて、ここからはnondecreasing submodularはC_iをどのように設計していくかについて考えよう。ここでは単純に $C_i(S) = \sum_{i \in S} w_{i, j}$ とする。ここで、 $w_{i, j} \geq 0$ はiとjの間の類似度(実際の実験のところではtf-idfを使ってコサイン類似度を使っている)。

Diversity Reward Function

$F(S) = L(S) + \lambda R(S)$ のR(S)の項。冗長性という形で目的関数からさっぴく代わりに多様性(reward diversity)という形で以下を目的関数に足してやるという風に設計してやる。
$R(s) = \sum_{i=1}^K \sqrt{\sum_{j \in P_i \cap S} r_j}$
一見よく分からないので、要素毎に見ていくことにする。Kは候補文Vの分割の数で、それぞれの分割は $P_i$ で書き表わす。それぞれはdisjoint。「分割をどう作るんだ?」というのは外部で勝手に作るらしく、CLUTOというツールを使うらしい(IDFで重み付けたterm vectorを特徴ベクトルとしてK個にただK-meansでクラスタリングするだけっぽい)。 $r_i$ は文iの要約にとっての重要性を表わしている。 $r_i$ はどうやって作るかというと $r_i = \frac{1}{N} \sum_j w_{i, j}$ としている。 $w_{i, j}$ は文iと文jの類似度で、自分以外の文への類似度を平均しているようなものを考えている。

で、R(S)が何をやっているかという話なのだが、クラスタ毎にr_jの合計のルートを取っていくのだが、

*1:それにあまり愛も感じない