Taste of Tech Topics

Acroquest Technology株式会社のエンジニアが書く技術ブログ

キーフレーズを自動推定するPositionRankの収束性について解説

機械学習 数学

こんにちは。
学生時代に信号処理で使っていた数学の知識を生かして、機械学習関連の仕事をしている３年目の@maron8676です。

本記事はAdvent Calendar 機械学習の数理の21日目の記事となります。

0. はじめに

本記事では、文書からキーフレーズを抽出するアルゴリズムであるPositionRankの収束性について解説します。
原論文[1]には収束について書かれていませんが、アルゴリズムを使うにあたり収束性があるかどうかは気になるところだと思います。
※機械学習では初期点によって結果が変わるなんてことはよくある話ですよね
そこで、今回はPositionRankの収束性について関数解析の視点から検証してみます。
結果として、PositionRankのアルゴリズムが作る点列は、任意の初期点に対し唯一つの点に収束するという、とてもよい性質を持っていることが分かります。

1. PositionRankについて

1.1. 目的

PositionRankは文書からキーフレーズ（文書のトピックを表すフレーズ）を抽出するためのアルゴリズムです。
キーフレーズが文書から自動で得られれば、文書を読まなくてもトピックが分かるため便利です。
また、自動で得られたキーフレーズをクラスタリングや、レコメンデーションへ応用することも考えられます。

1.2. 特徴

PositionRankはPageRankから影響を受けているアルゴリズムです。PageRankのページリンクに相当するものが、単語の共起情報となっています。
つまり、重要な単語と共起する単語は重要な単語であるという考えでキーフレーズの抽出を行っていると言えます。
PositionRankでは、単語の共起情報に加え、単語の出現位置を重要度に反映させることによって、共起情報だけを使った場合より精度を高めています。
それでは、PositionRankではどのようにしてキーフレーズを求めているのか見ていきましょう。

1.3. アルゴリズム

PositionRankでは、図1のような流れで各単語の重要度を算出し、高い重要度の単語を使ってキーフレーズを構築します。
単語の重要度が出てしまえば、高い重要度の単語を使ってキーフレーズを構成できます。
そのため以下では、各単語の重要度を導出するアルゴリズムについて注目していきましょう。

f:id:acro-engineer:20181217200127p:plain
図1. PositionRankで単語の重要度を導出するアルゴリズムの流れ

1.3.1. 文書から単語の共起情報を表すグラフを作る

ある単語とある単語が同じ場所で使われることを共起と言います。この共起情報を使って文書からグラフを作ることができます。
例えば、２つ隣までの単語は共起していることにすると、「PositionRankは文書からキーフレーズを抽出するためのアルゴリズムです」という文から
以下のグラフを作れます。

f:id:acro-engineer:20181217194955p:plain
図2. 例文から構成されるグラフ

図2では辺の重みが全て1のため省略しますが、辺の重みは共起回数となります。
実際にはいくつかの文があるため、さらに大きなグラフとなります。

1.3.2. グラフから各単語の重要度を計算する

作ったグラフの隣接行列M \in \mathbb{R}^{|V| \times |V|}と、単語の出現位置から構成したベクトルp \in \mathbb{R}^{|V|}を使い、初期点x_0 \in \mathbb{R}^{|V|}（|V|はグラフの頂点数=単語の種類）から以下の計算を繰り返し行うことで各単語の重要度を求めます。
x_{n+1} = \alpha \widetilde{M} x_n + (1-\alpha)p \qquad (0 < \alpha <1)
\widetilde{M}はグラフの隣接行列Mの各行を和が1になるようにl_1ノルムで正規化した行列であり、
p=\Bigl [ \frac{p_1}{p_1+p_2+ \ldots +p_{|V|}},\frac{p_2}{p_1+p_2+ \ldots +p_{|V|}}, \ldots ,\frac{p_{|V|}}{p_1+p_2+ \ldots +p_{|V|}} \Bigr ]^T.
ここで、p_iは単語の出現位置から計算される値です。例えば、i番目の単語が文書の5番目と7番目に出現した場合はp_i=\frac{1}{5}+\frac{1}{7}=\frac{12}{35}となります。

2. アルゴリズムの収束性

それでは、1.3.のアルゴリズムによって作られる点列が唯一つの点に収束することを確認していきましょう。
図3の流れで確認を進めていきます。

f:id:acro-engineer:20181218073153p:plain
図3. 収束を証明する流れ

2.1. 行列\widetilde{M}による線形写像は非拡大写像である

行列\widetilde{M}の各行がl_1ノルムで正規化されていることを使って、非拡大写像であることを示します。
ここでの非拡大写像とは、完備なノルム空間における任意の x, y \in \mathbb{R}^{|V|} に対し、以下が成り立つ写像A : \mathbb{R}^{|V|} \rightarrow \mathbb{R}^{|V|}のことです。
\|x-y\| \geq \|Ax-Ay\|
\|\cdot\|はノルムです。これ以降はノルムをl_{\infty}ノルム*1として進めていきます。最終的な収束の結果については、ノルムの等価性*2を使うと\mathbb{R}^{|V|}上の全てのノルムについて成り立つことが確認できます。
\widetilde{M}が線形写像であることに注意すると、
\begin{align}\|\widetilde{M}x-\widetilde{M}y\|_{\infty}&=\|\widetilde{M}(x-y)\|_{\infty}\\ &\leq\|\widetilde{M}\|_T\|x-y\|_{\infty}\end{align}
となります。\|\cdot\|_Tは作用素ノルム
\|A\|_T:=\max_{\|x\|_{\infty}=1}\|Ax\|_{\infty}
です。行列\widetilde{M}の各行はl_1ノルムで正規化されているため、\|\widetilde{M}\|_T = 1となります*3。したがって、行列\widetilde{M}による線形写像は非拡大写像です。

2.2. 実数 0 < \alpha < 1 によるpとの凸結合は縮小写像である

単語の出現位置から構成したベクトルpとの凸結合が縮小写像であることを示します。
ここでの凸結合とは、実ベクトル空間の任意の点x,y \in \mathbb{R}^{|V|}と実数0 < \alpha < 1から得られる
\alpha x + (1-\alpha)y
のことを言います。また、写像fが縮小写像であるとは、完備なノルム空間における任意の点x,y \in \mathbb{R}^{|V|}に対しあるk \in [0,1)が存在して、
\|f(x)-f(y)\|\leq k\|x-y\|
が成り立つことです。
fをpとの凸結合
f(x)= \alpha x+(1-\alpha)p \quad (0 < \alpha < 1)
とすると、
\begin{align}\|f(x)-f(y)\|_{\infty}&=\|\alpha x+(1-a)p-\alpha y-(1-\alpha)p\|_{\infty}\\ &=\|\alpha x-\alpha y\|_{\infty}\\ &\leq|\alpha|\|x-y\|_{\infty}\end{align}
となるため縮小写像となります。

2.3. バナッハの不動点定理[2]を適用する

バナッハの不動点定理[2]は以下が成り立つことを示しています。
Tを完備距離空間における縮小写像とすると、Tは唯一つの不動点を持つ
点列x_n=T(x_{n-1})は唯一つの不動点に収束する。
2.1.と2.2.より、PositionRankの1イテレーション
g(x_{n}) = \alpha \widetilde{M} x_n + (1-\alpha)p \qquad (0 < \alpha <1)
は縮小写像であるため、バナッハの不動点定理[2]より唯一つの不動点が存在し、イテレーションを繰り返すことでその不動点に収束します。
　　　

3. アルゴリズムの収束速度

バナッハの不動点定理[2]により、収束速度も以下のように得ることができます。
\|x^* - x_k\| \leq \frac{\alpha^k}{1-\alpha}\|x_1 - x_0\|
ここで、x^*は不動点、k \in \mathbb{N}はイテレーション回数であり、\alphaは2.2.の凸結合に登場する\alphaです。
実際の例として、距離がl_{\infty}ノルムで\alpha = 0.85*4とした場合を見てみましょう。
ランダムに決める初期値としては、原論文[1]で使われている、全ての成分が\frac{1}{|V|}のベクトルを使うことにしましょう。すると、 \|x_1 - x_0\|_{\infty} < 1となるため、100回イテレーションを回して得られるベクトルx_{100}は
\begin{align}\|x^* - x_{100}\|_{\infty} &\leq \frac{\alpha^{100}}{1-\alpha}\|x_1 - x_0\|_{\infty}\\ &=\frac{0.85^{100}}{0.15}\|x_1 - x_0\|_{\infty}\\ &< 5.8 \times 10^{-7}\end{align}
を満たします。100回のイテレーションで十分収束していると言えますね。

4. まとめ

キーフレーズを抽出するアルゴリズムであるPositionRankの1イテレーションが縮小写像であることを示して、唯一つの点に収束することと収束の速度を確認しました。任意の初期点から始めて収束する＋指数オーダで収束速度もいいという結果で、安心して使えます。実用上いい結果が出ることも大事なのですが、今回のように収束を検証できることも重要なことなので、何となく使っていたアルゴリズムを見直してみるのもよいのではないでしょうか。

5. 参考文献

[1] Corina Florescu and Cornelia Caragea, PositionRank: An Unsupervised Approach to Keyphrase Extraction from Scholarly Documents
[2] S. Banach, Sur les operations dans les ensembles abstraits et leur application aux equations integrales, Fund. Math. 3(1922), 133–181
[3] 山田 功, 工学のための関数解析, 数理工学社
[4] Sergey Brin and Lawrence Page, The anatomy of a large-scale hypertextual Web search engine

*1 ベクトルx \in \mathbb{R}^{|V|}のl_{\infty}ノルムは\|x\|_{\infty} := \max_{1 \leq i \leq |V|}|x_i|です。

*2 ベクトル空間Xに定義されたノルム\|\cdot\|_Aとノルム\|\cdot\|_Bが等価であるとは、ある実数M_2 \geq M_1 > 0が存在して、すべてのx \in Xに対し、M_1 \|x\|_A \leq \|x\|_B \leq M_2 \|x\|_A
が成り立つことを言います。有限次元ベクトル空間に定義可能なノルムはすべて等価であることが知られています([3]を参照されたい)。

*3 証明は省略しますが([3]を参照されたい)、行列とベクトルの積を成分で展開し、
1. （積の絶対値）\leq（絶対値の積）から上界
2. 単位ベクトルとの積から下界
を作って挟み込むことで、l_{\infty}ノルムに対応する行列A \in \mathbb{R}^{|V|}の作用素ノルムは
\|A\|_T:=\max_{1 \leq j \leq |V|} \Sigma_{k=1}^{|V|}|a_{jk}|
となることを示せます。

*4 PageRankのdamping factor[4]にならって0.85を設定することが多いようです。

Acroquest Technologyでは、キャリア採用を行っています。


  • ディープラーニング等を使った自然言語／画像／音声／動画解析の研究開発
  • Elasticsearch等を使ったデータ収集／分析／可視化
  • マイクロサービス、DevOps、最新のOSSを利用する開発プロジェクト
  • 書籍・雑誌等の執筆や、社内外での技術の発信・共有によるエンジニアとしての成長

　
少しでも上記に興味を持たれた方は、是非以下のページをご覧ください。

Kaggle Masterと働きたい尖ったエンジニアWanted！ - Acroquest Technology株式会社のエンジニア中途・インターンシップ・契約・委託の求人 - Wantedlywww.wantedly.com