抄訳 TextRank: Bringing Order into Texts(2004)

#キーワード抽出

July 20, 2019

概要

TextRankは、ドキュメントからキーワードとキーセンテンスを抽出するためのグラフベースのアルゴリズムである。 TextRankは、単語を頂点、文書をグラフとみなすことで、PageRankを応用する。頂点の重要度を、頂点の内容のような局所的な情報ではなく、他の頂点との辺の接続関係を含むグラフ全体の大域的な情報から決定する。 TextRankは、PageRankと違い、辺ごとに重みを設定できる。

キーワード抽出

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

グラフを構築したら、以下の式を$\textit{WS}^{k+1}(V_i)-\textit{WS}^{k}(V_i)$が収束するまで繰り返し、$WS(V_i)$を更新する。収束後の$\textit{WS}$の値が高いほど単語が重要でであるとみなす。論文では、収束判定の閾値を$0.001$、$d=0.85$、各スコア$\textit{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)} $$

感想

評価に使われた文書は、コンピュータ科学や情報技術の論文の概要であり、短く重要な単語が頻出するので、簡単なデータで評価しているように思えた。もっと長く冗長な文書でどのような結果がえられるのか気になる。

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