文書要約のLexRankや、Googleページランクのアルゴリズムではなぜ固有ベクトルが登場するの？

本記事では、文書要約アルゴリズム（および、重要文の抽出手法）である**LexRank**の手続き(Googleが初期に採用していた、各サイトの重要度を測るページランク手法を応用した手法）に、なぜ線形代数の固有ベクトルや固有値分解が登場するのかを解説します。


# はじめに

2020年8月1日に
**「Deep Learning Digital Conference」**
が開催されます。

https://dllab.connpass.com/event/178714/


上記イベントの【個人セッション】で、
**【AI・ディープラーニングを駆使して、「G検定合格者アンケートのフリーコメント欄」を分析してみた】**
というLTを、同僚（2月から中途入社してきたメンバの御手洗さん）と発表します。

（概要）
2020年5月に実施した「第2回G検定合格者がおススメするAI・DL本アンケート」のフリーコメント欄、「ディープラーニング協会へのご意見・ご要望」に寄せられた意見を、ディープラーニング協会らしく、機械学習とディープラーニングを駆使して分析した結果を紹介します。本発表ではワードクラウド、説明性XAI、クラスタリング、要約、ALBERTなどの自然言語処理技術の概要を解説し、そして実際にこれらの技術を、G合格者のみなさまの「ディープラーニング協会へのご意見・ご要望」データに適用すると、どのような分析結果が出たのか紹介します。


私（小川）は日本ディープラーニング協会を運営している委員なので、

アンケートのフリーコメントを解析し、
皆さまの意見を運営陣に報告・カイゼンする必要があるのですが、
フリーコメントの解析を手でやるのがしんどいです。

そこで、
**ディープラーニングのエンジニアらしく、機械学習を駆使しようじゃないか！**
という取り組みを実施しました（ちゃんと手作業での整理もしましたが・・・）。

# LexRank

フリーコメントの解析の途中で、文書を自動要約する場面があります。

今回要約手法には、簡単な手法である**LexRank**アルゴリズムを採用することにしました。

LexRankは「初期のGoogleで各サイトの重要度を測るページランク手法」を応用した、文書要約（および、重要文の抽出）のアルゴリズムです。


以下、LexRankの解説例です。

https://ohke.hateblo.jp/entry/2018/11/17/230000

https://www.ai-shift.co.jp/techblog/938


2月に中途入社してきた御手洗さんと、このコロナの最中のため、ずっと各自、自宅から、ペアプロをしてました。

ペアプロといっても、僕が指示して彼が頑張り、その間私は別の仕事をする、
分からなくなったら私に聞く、
なので、
ペアプロというよりは、ずっといつでも私に質問できる状態という感じでしょうか。。。

で、LexRankも実装してくれて、
さて発表スライドを作っているときに、私から彼にした質問が以下の3つです。


**[A] 各サイトの重要度を測るページランクの手法を応用したLexRankでは、アルゴリズムになぜ固有値分解が登場するの？**

**[B] ページランクに相当する、各文章の重要度は、固有ベクトルというけど、固有値いくつの固有ベクトルなの？**

**[C] なんで固有ベクトルがページランクや、LexRankでは各文章での重要度に相当するの？**

です。

そして私からの解説が以下になります。


# 文書要約のLexRankや、Googleページランクのアルゴリズムで固有値分解が登場する理由

これは線形代数の固有値、固有ベクトル、固有値分解のお話になります。

まずは、以下のサイトを読んでみてください。

なぜ線形代数を学ぶ？ Googleのページランクに使われている固有値・固有ベクトルの考え方
https://math-fun.net/20180809/1195/

そして上記のサイトの情報だけでは、私の[A]-[C]の質問には答えられない（と思いますので）
補足すると、以下の通りです。


[1] ページランクとは、ページ間の遷移確率を行列で表した行列Aの、固有値1の固有ベクトルの値です

[2] 固有値1の固有ベクトルなので、そのベクトルをページ間の遷移確率行列Aに再度かけ算しても、また、同じ値のベクトルになります。

つまり、
vec_after = A * eigen_vec

ここで、vec_afterはeigen_vecと同じ（なぜなら、固有値が1なので固有値倍されても同じ値）

[3] つまり、固有値1の固有ベクトルの各行の値は”各サイトのパワー”を示します。
そして全サイトのパワーの割合がどんなパターンだと（すなわち、どんな固有ベクトルだと）、
遷移確率行列Aで遷移しても、変化しないのか？
サイトパワーが遷移行列Aで遷移しても変化することのない状態が、各サイトの静的なパワー（ページランク）を示します。
 
※サイトのパワーと言われて理解しづらい人は、そのサイトを見ている人の数、だと思ってください。
そのサイトを見ている人の数が、遷移行列で変換したあとでも変化しない、
すなわち、そのサイトの静的な集客人数≒サイトの重要度、という考え方です。


[4] この[3]が、固有値1の固有ベクトルがページランクに相当する理由です。


[5] 今回はLexRankなので、
検索におけるページ間の遷移行列（被リンク数の行列）とホームページの強さ（ページランク）は、
それぞれ、各文書と文書の類似度行列と各文書の強さ（重要さ）として扱われます。


以上が、LexRankに固有ベクトルがや固有値分解が登場する理由であり、最初の3つの質問、

[A] 各サイトの重要度を測るページランクの手法を応用したLexRankでは、アルゴリズムになぜ固有値分解が登場するの？
[B] ページランクに相当する、各文章の重要度は、固有ベクトルというけど、固有値いくつの固有ベクトルなの？
[C] なんで固有ベクトルがページランクや、LexRankでは各文章での重要度に相当するの？

の回答になります。


※では、なぜ遷移行列Aは最大固有値が1を持つ保証されるのか？の疑問が湧きますが、そのあたりはあまりに数学的過ぎるので、本記事では省略いたします。
気になる方は、以下の式(4)周り、Gerschgorin の定理（ゲルシュゴリンの定理）を使用するあたりを読んでみてください。
http://www.math.sci.hokudai.ac.jp/~ishikawa/Numazu-Shizuoka/fujii-222.pdf



# まとめ

以上、本記事では、「初期のGoogleで各サイトごとの重要度を測るページランク手法」を応用した、文書要約（および、重要文の抽出）のアルゴリズムであるLexRankのアルゴリズムに、なぜ線形代数の固有ベクトルや固有値分解が登場するのかを解説しました。

最近私は、自分が面白いと思った記事やサイト、読んだ本の感想などのAIやビジネス、経営系の情報をTwitterで発信しています。

小川雄太郎@ISID_AI_team
https://twitter.com/ISID_AI_team


私が見ている情報、面白い、重要だ！と思った内容を共有しています。
是非こちらアカウントもどうぞよろしくお願い致します。





---

【備考】[私がリードする、AIテクノロジー部開発チームではメンバ募集中です。興味がある方はこちらからお願い致します](https://www.isidgroup.com/u/job.phtml?job_code=430)


【免責】本記事の内容そのものは著者の意見/発信であり、著者が属する企業等の公式見解ではございません

---