Coda

概要 TextRank: Bringing Order into Texts

July 20, 2019

概要

表題にある論文は、ドキュメントからキーワードとキーセンテンスを抽出するためのグラフベースのアルゴリズムTextRankを提案、評価した。 TextRankは、名前から推測できるようにPageRankを応用した手法であり、頂点の重要度を、頂点の内容のような局所的な情報ではなく、他の頂点との辺の接続関係を含むグラフ全体の大域的な情報から決定する。PageRankとTextRankのアルゴリズムの違いは、TextRankの場合は辺ごとに重みが設定できるところにある。

キーワード抽出

TextRankはグラフベースの手法なので、まずはドキュメントからグラフを構築する。TextRankは点の重要度を計算するアルゴリズムなので、単語を頂点として扱う。 論文では、実験を通して、名詞と形容詞のみを頂点ことをすすめている。 グラフの辺は、共起する単語を結んで作られる。ある単語同士が共起関係にある条件は、ウィンドウの間に単語が共に存在することである。ウィンドウサイズは2から10までの値をとりえる。ウィンドウサイズが2のときに最も良い実験結果がえられた。

グラフが構築できたら、以下の式を\(S^{k+1}(V_i)-S^{k}(V_i)\)が収束するまで繰り返し、\(WS(V_i)\)を更新する。 収束後の\(WS\)の値が高いほど単語が重要でであるとみなすことができる。 論文では、収束判定の閾値を\(0.001\)、\(d=0.85\)、各スコア\(WS\)の初期値を1としている。 \(w_{ji}\)は点\(i,j\)を結ぶ辺の重み、\(In(V_i)\)は頂点\(V_i\)に入る辺の対向にある頂点の集合、\(Out(V_j)\)は頂点\(V_j\)から出ていく辺の対向にある頂点の集合になる。 無向グラフの場合、両者の集合は等しい。有向グラフよりも無向グラフの方が実験結果が良かった。

$$ WS(V_i) = (1-d) + d * \sum_{V_j\in In(V_i)}\frac{w_{ji}}{\sum_{V_k\in Out(V_j)}w_{jk}}WS(V_j) $$

キーセンテンス抽出

キーセンテンスを抽出する場合、文が頂点となる。 辺については、文の類似度を示す以下の式により、似ているとみなされた文の間に定義される。 \(w\)は単語、\(S\)は文に含まれる単語の集合を示す。

$$ Similarity(S_i,S_j)=\frac{\mid\left\{ w_k \mid w_k \in S_i \& w_k \in S_j \right\}\mid }{\log(\mid S_i\mid) + \log (\mid S_j\mid)} $$

感想

評価に使われた文章は、コンピュータ科学や情報技術の論文の概要であるため、短く重要な単語が頻出するので、簡単なデータで評価しているように思えた。

もっと長くて冗長な文が含まれる文章でどのような結果がえられるのか気になる。

論文ではナイーブな有向グラフの作り方をしていたので、工夫すれば有向グラフが無向グラフよりも良い結果を生むこともありえる気がする。


論文はこちらからダウンロードできます。