機械学習_潜在意味解析_理論編

データ分析

#機械学習

yoshim

2017.12.20

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

概要

　こんにちは、データインテグレーション部のyoshimです。
　この記事は機械学習アドベントカレンダー20日目のものとなります。
　今回は「潜在意味解析(LSA)」という手法を説明してみようと思います。

今回のご説明の流れとして、「潜在意味解析(LSA)」は「トピックモデル」という概念を背景としているものなので、まずは「トピックモデル」についてご説明しようと思います。
その後に「潜在意味解析(LSA)」についてご説明し、「潜在意味解析(LSA)」を発展させたアルゴリズムである「確率的潜在意味解析(pLSA)」、「潜在ディリクレ割り当て（LDA）」、LDAでよく利用されるギブスサンプリングというサンプリング手法、をご紹介しようと思います。

1.トピックモデルとは

　ざっくり言うと、「文書が潜在的なトピック（話題）」から生成される」という考え方をするモデルで、文書のトピック（話題）を推定したり、推定したトピックに応じてクラスタリングするのに利用されます。例えば、14日目のブログで「ニュース文書を野球の記事か宇宙の記事かを分類する」といったことをしているのですが、こんな感じです。
「トピックモデル」では、「各文書、各単語には潜在的なトピック（話題）が存在する」という前提のもと、「トピック単位」で分析を進めていく点が特徴です。

文書のトピック（話題）を推定できると何が嬉しいのかって、商品レビューやアンケート等の結果をクラスタリングしてみると面白い分類ができたり、情報検索時に低ランクな文書は検索しないように効率化する事ができます。また、今回ご紹介するLSAのように、「行と列」の両方でそれぞれクラスタリングできる点も特徴的です。
（文書分類で言うなら、単語をクラスタリング、文書をクラスタリング、をそれぞれできる）

トピックモデルはあくまでも概念の話なので本エントリーではこれ以上説明しませんが、もしこれよりも詳細が知りたい場合はアルベルトさんのHPがわかりやすく解説してくれているので、ご参照ください。

では、「潜在意味解析(LSA)」の背景となる概念である「トピックモデル」の説明が終わったので、続いて「潜在意味解析(LSA)」の説明に移ろうと思います。

2.潜在意味解析(LSA)とは

　潜在意味解析(LSA)はなんなのかと言うと、「トピックを推定する手法における、もっとも基本的なアルゴリズム」と言えるでしょう。
LSAにおけるアルゴリズムの流れは下記の通りで、「トピックモデルの考え方の基本をアルゴリズム的に示したもの」、といった感じです。

1.単語-文書行列を生成
2.特徴量を「文書数、単語数」から「潜在的なトピック数」に削減してモデル作成＆評価
3.できたモデルを使ってクラスタリングや文書分類をする

LSAのアルゴリズムの流れは大まかには上記の通りですが、下記からもう少し詳細についてご説明していきます。

3.アルゴリズムの流れ

LSAにおける処理の流れは上記の通りですが、もう少し詳細についてご説明しようと思います。

1.単語-文書行列を生成

文書データから、「tf-idf」を計算するのが一般的です。「tf-idf」については、手前味噌ですが先日記述したエントリをご参照ください。
tf-idfについてざっくりまとめ_理論編
 tf-idfについて勉強したのでざっくりまとめ_pythonでやってみた

イメージとしては、下記のような計算結果を取得します。(本来ならもっと単語が多くなります)

単語	文書1	文書2	文書3	文書4	文書5
単語A	1.5	-0.4	-0.2	0.1	0.6
単語B	0.5	0.3	-0.6	-1	0.7
単語C	-1.3	0.4	-0.6	0.1	0.3
単語D	0.1	0.1	-0.2	-0.5	-0.5
単語E	-0.6	-0.1	0.2	1.5	0.5
単語F	-1.0	-0.4	1.0	0.4	0.5

2.特徴量を「単語数」から「潜在的なトピック数」に削減してモデル作成＆評価

単語単位で情報を保持していると、「同義語による検索漏れ」といった問題が発生します。
（例えば「自転車」で検索した場合「ママチャリ」という単語を使った文書を検索することができない。）トピックモデルでは、「意味が似ていそうな単語は１つのトピックにまとめる」ことで「同義語による検索漏れ」問題を解消します。

これをちょっと機械学習風に言うと、「単語-文書行列の特徴量をトピック数に削減」というものになります。 X個ある単語をZ個のトピックに集約、Y個ある文書をZ個のトピックに集約、といった具合です。文字だけだとイメージがつきづらいと思いますので、下記に処理内容のイメージを示そうと思います。

５個の文書に６個の単語があった場合の単語-文書行列（tf-idfを計算しただけなので上の表と同じ）

単語	文書1	文書2	文書3	文書4	文書5
単語A	1.5	-0.4	-0.2	0.1	0.6
単語B	0.5	0.3	-0.6	-1	0.7
単語C	-1.3	0.4	-0.6	0.1	0.3
単語D	0.1	0.1	-0.2	-0.5	-0.5
単語E	-0.6	-0.1	0.2	1.5	0.5
単語F	-1.0	-0.4	1.0	0.4	0.5

これを２トピックに削減した場合、下記のような２つの行列が得られる。
(さらに特異値行列も得られるがここでは割愛します。また、数値は適当です。イメージを掴むためのものなのでご容赦ください)

各単語が各トピックに属する割合

単語	トピックα	トピックβ
単語A	0.8	-0.1
単語B	0.5	0.2
単語C	-0.6	0.1
単語D	0.7	0.4
単語E	-0.9	-1.1
単語F	-1.5	0.4

各文書が各トピックに属する割合

単語	文書1	文書2	文書3	文書4	文書5
トピックα	1.2	-0.1	-0.6	0.5	0.2
トピックβ	0.4	0.2	0.1	-1.1	0.8

LSAでは、このような処理を「トピック数」を変更しつつ精度を確認しながら繰り返していくことになります。
　　
　この「トピック数に情報量を削減する」という処理時に「特異値分解」をして、「特異値の高い方からk個選んで元の「単語-文書行列」を近似する」、という計算をしています。
(上記の例だと、特異値を高い方から２つ選んで、元の単語-文書行列を近似している、という計算をしています。)

特異値分解については今回のエントリーではご紹介しませんが、特異値分解で「単語-文書行列」をk個のトピックで近似した計算式は下記のような意味を持つと考えられます。

(k個のトピックで近似した単語-文書行列) = (各単語が各トピックに属する度合いの行列) * (各トピックの重要度の行列) * (各文書が各トピックに属する度合いの行列)　　

(各単語が各トピックに属する度合いの行列)と(各文書が各トピックに属する度合いの行列)を別々に求めることができるので、それぞれ「どの単語が潜在的に似たような意味を持っているか」、「どの文書が潜在的に似たような意味を保有しているか」といったことを確認することができます。
　　
　　

3.できたモデルを使ってクラスタリングや文書分類をする

生成したモデルを実際に利用するフェーズです。新しい文書を投入してどんなトピックの文書かを推定したり、保有している文書データセットをクラスタリングしたりします。

以上が、潜在意味解析(LSA)の概要ですが本手法に更に確率的な概念を拡張した「確率的潜在意味解析（pLSA）」というアルゴリズムがあるので、そちらについてもご紹介します。

4.確率的潜在意味解析（pLSA）

pLSAについてざっくり説明しますと、「確率の概念を追加したLSA」であり、「各文書が複数のトピックに割り当てられていることを確率的に表現する」アルゴリズムです。
「確率の概念ってどういう意味だよ」、という話ですが、これは「文書はある確率モデルに基づいて生成される」という考え方で、pLSAはこの考え方に沿ったアルゴリズムであるということです。
「ある確率モデルってなんだよ」、という点についてですが、これは下記２点の確率モデルを仮定することになります。
（正確には確率モデルではなく「確率密度関数」です）

・各文書における各トピックの重要度割合
(ex.文書1では、トピックα、βの重要度をそれぞれ0.2、0.8とする)

・各トピックにおける各単語の重要度割合
(ex.トピックαでは、単語A、Bの重要度をそれぞれ0.3,0.7とする)

pLSAでは上記の２つの確率モデルのパラメータを更新していき、最も尤度の高い確率モデルを生成します。
（「EMアルゴリズム」と言われる手法でパラメータを更新していくのが一般的です。)

ここまで文だけでの説明だと直感的にわかりづらいと思いますので、「pLSA」を説明する際によく使われる図を参考にして、上記の言葉を説明していこうと思います。

まずこの図に出てくるアルファベットの意味なのですが、下記の通りです。
M: 文書数
N: 各文書の単語数
d: 各文書
c: トピック分布
w: トピックごとの単語分布

また、円の色の意味についてですが、これは「白丸は観測されていないもの（潜在的なもの）」、「灰色の円は観測されたもの」を表しています。
また、四角の箱は「右下の数字だけ処理を繰り返す」という意味です。

この図の前提条件の説明は以上として、続いてこの図の中身についてのご説明です。
この図の意図する処理の流れは下記の通りです。
1.「各文書における各トピックの重要度割合」、「各トピックにおける各単語の重要度割合」を適当に決める
2.「各文書における各トピックの重要度割合」に基づいてトピックの割り当てを実施（d→c）
3.「各トピックにおける各単語の重要度割合」に基づいて単語の割り当てを実施（c→w）
4.3をその文書内の全ての単語（この図だと単語数はN）について繰り返し行う（c→w）
5.「各文書における各トピックの重要度割合」、「各トピックにおける各単語の重要度割合」のパラメータを更新
6.2-5を全文書に対して繰り返す（この図だと文書数がMなので、M回繰り返すことになる）

この図での処理の流れは以上です。

また、pLSAでは値を「確率」として扱うので、LSAの欠点であった「負の値をとる（計算的にはいいかもしれないけど直感的に理解しづらい）」、「各単語が１つのトピックにのみ属するというありえない仮定をしている」という問題をクリアしています。
(確率として扱うゆえに、「値を合計すると１になる」といった制約は若干残りますが...)

このように、pLSAはLSAの欠点を解消しているアルゴリズムなので、LSAよりはpLSAを用いることが一般的でしょう。
しかし、pLSAでは「各パラメータについて１つの値を決定」しており、「汎化性能」といった面から若干の不安が残ります。
そこで、pLSAに対して、「各パラメータの値を１つに決定するのではなく、分布を考える」というベイズ的な手法を用いた「潜在的ディリクレ配分法（LDA）」なる手法も存在します。

5.ギブスサンプリングとは

LDAでは、「ギブスサンプリング」という「サンプリング手法」がよく使われます。
（LDAの誕生当時は変分ベイズ方が使われていましたが、今ではギブスサンプリング、特に崩壊型ギブスサンプリングが主流です）
なので、まず「サンプリングとはなんぞや」についてざっくり説明してから「ギブスサンプリング」、「LDA」の説明へと移行しようと思います。

サンプリング

さて、「サンプリングとはなんぞや」という話ですが、サンプリングとは「ある確率分布に沿ってサンプルを取り出す方法」です。例えばサイコロを6,000回振って出た目をカウントし、下記のような結果を取得したとします。

出目	回数
1	950
2	1,000
3	1,050
4	950
5	950
6	1,100

これも立派なサンプリングです。これは「サイコロの各面がでる確率分布p(θ)に沿って6,000回サンプリングした結果」と言えます。このようなサンプリングですが、「完全にランダムなサンプリングをする方法」、「MCMC（マルコフ連鎖モンテカルロ法）に基づいた方法」等の色々な手法が存在します。

そもそも、なぜサンプリング手法が必要なのかというと、「パラメータ」が解析的に求められない時には「パラメータを近似解で表現する」といった対策を取ることが多いからです。この「近似解」を求めるために、「サンプリング」をして「パラメータの調整（尤度最大化）」を繰り返していくことになります。繰り返しになりますが、これは解析的に求めた解ではなく、「今あるデータが真の母集団だと仮定して計算した近似的な解」になります。

ギブスサンプリング

「ギブスサンプリング」はMCMCを背景としたサンプリング手法です。下記の２点が特徴です。

1.MCMC（マルコフ連鎖モンテカルロ法）に基づく
MCMCとは、「マルコフ連鎖」と「モンテカルロ法」を組み合わせたサンプリング手法です。

「マルコフ連鎖」とは、「１つ前の状態を利用して次のパラメータを推定する」という手法です。　　「モンテカルロ法」とは「ランダム性を取り入れるために、乱数を発生させる」手法です。なのでMCMCを端的に述べてしまえば、「１つ前の情報（パラメータがいくつだった時に尤度がいくつだったか）を利用して、次のパラメータをある程度ランダムに選択して尤度計算をして、その尤度に基づいてパラメータ更新を繰り返していく」ためのサンプリング手法です。

MCMCについてもう少し詳細を知りたい方はこちらをご参照ください。

2.条件付き確率
ギブスサンプリングでは、求めたいパラメータがN個あった場合に「(N-1)個のパラメータを固定し、1個のパラメータだけ値を更新」することを事前に設定した回数だけ繰り返していきます。最終的には尤度がある程度収束したところまで繰り返し計算します。

もう少し具体的に説明しようと思います。例えば、求めたいパラメータが３つ（α、β、γ）あったとします。まずはそれぞれのパラメータの初期値を適当に決めます。今回は（α=0.1,β=0.1,γ=0.1）を初期値として設定して、これらのパラメータの更新回数を10,000回とします。この時の計算の流れは、下記のようになります。

1.β=0.1,γ=0.1の状態で、パラメータαを利用する事後分布での尤度が最大になるようなαに値を更新(今回はα=0.2になったとします)
2.α=0.2,γ=0.1の状態で、パラメータβを利用する事後分布での尤度が最大になるようなβに値を更新(今回はβ=0.3になったとします)
3.α=0.2,β=0.3の状態で、パラメータγを利用する事後分布での尤度が最大になるようなγに値を更新(今回はγ=0.4になったとします)
4.1-3の流れを最初に指定した回数だけ繰り返す

ギブスサンプリングは上記のような流れでパラメータを更新していき、「パラメータの近似解」を求めることを目的としたサンプリング手法なのです。
(解析的に求められないのでサンプリングすることでデータを大量に集めてその結果を使えば、解析的に求められる解に近いだろう、という仮定が背景にあります。)

ここまでごちゃごちゃしてしまったので簡単にまとめると、下記の通りです。
・LDAでは、求めたいパラメータが解析的に求められないので、パラメータの近似解を求めることで対応する。そのために「サンプリング」をする
・LDAでよく使われるサンプリング手法は「ギブスサンプリング」という手法である
・ギブスサンプリングはMCMC手法の１つであり、パラメータを１個ずつある程度ランダムに選択し尤度を確認しながら更新していく手法である

6.潜在的ディリクレ配分法（LDA）

潜在的ディリクレ配分法（LDA）は指定すべきパラメータ（今回の場合、pLSAで検討した２つの確率密度関数）に対して事前分布を仮定し、パラメータの事後分布を推定するというベイズ的手法です。
（「LDA」と略されるアルゴリズムとしてに「線形判別分析(linear discriminant analysis）」というアルゴリズムがあり紛らわしいですが、これらは全く異なるアルゴリズムです）
（正確には「Smoothed LDA」と呼ばれるLDAですが、LDAと言うと一般的にこちらのアルゴリズムがよく使われているので本エントリーでも「Smoothed LDA」をLDAとしてご紹介します。）

LDAのアルゴリズムを説明する際には下記のような図がよく使われますので、私もこれに沿ってご説明しようと思います。
ただ、pLSAとアルゴリズムの大枠は同じですので、あまり身構える必要はありません。

まずこの図に出てくるアルファベットの意味なのですが、下記の通りです。（pLSAと異なる点のみ記述）
α: 各文書ごとのトピック分布の事前分布（ディリクレ分布）のハイパーパラメータ。
β: トピックごとの単語分布の事前分布（ディリクレ分布）のハイパーパラメータ。
θ: 各文書ごとののトピック分布(多項分布)
φ: トピックごとの単語分布(多項分布)
K: トピック数

円の色、四角い箱の意味については、pLSAと同じです。 LDAにおいては、人間が明示的に指定するハイパーパラメータはαとβです。なお、パラメータが色々と出てきましたが、最終的に求めたいパラメータはαとβの２つです。θやφは、αとβを求めるために間接的に利用することとなります。

さて、ここでギブスサンプリングでどのようにパラメータを更新していくのか、ですが大雑把に言うと下記のような流れになります。
1.α、βを適当に決める
2.αからz(各文書ごとのトピック分布)、βからφ(トピックごとの単語分布)を求める
3.zとφの同時分布からw(ある文書におけるトピックごとの単語分布)を求める
4.wからzを更新する
(ここでは、「zの各成分についてギブスサンプリングで１つずつ更新していく」ことになります。この時、wとzの更新するパラメータ以外を固定した同時条件付き確率から予測分布を求めてzを更新します。)
5.4を単語数Nだけ繰り返す
6.zからθとφを更新
7.θとφの周辺同時尤度を最大化させるようにα、βを更新
8.全文書数Mだけ、2-8を繰り返す
9.終了条件(反復回数等)を満たすまで2-8を繰り返す

今回用いる崩壊型ギブスサンプリングの特徴としてθ、φに対して積分消去し推定するパラメータ数を減らすことでサンプリングを効率化することができるので、下記のような図を説明資料として使うこともありますが、やっていることは同じです。

LDAは「ベイズ的手法」なので「事前分布」、「事後分布」を仮定する必要があります。事後分布には多項分布、事前分布には共役事前分布であるディリクレ分布を選択することが一般的です。
（多項分布とディリクレ分布についてもう少し知りたい方はこちらがわかりやすく整理してくれているのでご参照ください。）
以上より、「潜在的ディリクレ配分法」という名前の由来が「潜在的なトピックを、ディリクレ分布に基づいて配分する」という意味だということがなんとなく理解できます。

「多項分布が既に確率密度関数なのに、更に事前分布を仮定する」ってどういう意味なんだろう、と私は最初思ってしまったのですがこれはLatent Dirichlet Allocation (LDA) ゆるふわ入門のブログを読んで腹落ちしました。
例えば、ある文書における各トピックの重要度割合が(トピックα,トピックβ,トピックγ)=(0.2,0.3,0.5)である確率が0.1、(トピックα,トピックβ,トピックγ)=(0.4,0.3,0.3)である確率が0.2といったような「確率密度関数の確率密度関数」と考えることができます。 (ベイズだぞ、そんなんすぐにわかるだろ、という方もいらっしゃる方もいると思いますが...)

LDAはこのディリクレ分布の形を決定するためのハイパーパラメータを求めることで、最終的に求めたい確率密度関数を求める手法です。このLDAでも最終的に求めたいものはpLSAと同じ２つの確率密度関数なのですが、この２つの確率密度関数の事後分布を求める計算手法をベイズ的に行うことによって若干アルゴリズムが変わってくるということです。
また、LDAはpLSAと比較すると「汎化性能が高い」、「階層ベイズモデルになったので、様々な拡張が可能」といった特徴があります。　　

本エントリーではLDAについての説明はここまでとします。
（LDAについての説明はこちらがわかりやすかったです。ありがとうございます。)

7.まとめ

以上でLSAのご説明を終わりとします。
結局LSA、pLSA、LDAと色々出てきましたが「トピックモデルという概念に基づく」という点は同じなので、最終的に求めるものは同じです。
ただ、精度や汎化性能によってアルゴリズムをどれにするかを選択する必要がある、というものです。
(LSAを利用することはほとんどないと思います。pLSA、LDAは利用する目的によって使い分けることになります）
pLSAは尤度最大化をするため「過学習しやすい」のですが、その分「今あるデータに対してアドホック的に一回分析する」といった場合はpLSAが適しています。一方、今後も新しいデータが投入されモデルを更新し続ける必要がある場合はLDAの方が適しています。

短くまとめようとしたのですが長くなってしまいました。(文字ばっかりだし...)
ここまで読んでくださった方、ありがとうございます。ｍ（＿＿）ｍ
明日は、今回ご紹介したLSAをPythonで実装してみようと思います。　　 |ω･`)ﾉﾏﾀﾈｰ