EMアルゴリズムを使ったPLSAを数式から理解する!

こんにちは!
IT企業に勤めて、約2年間でデータサイエンティストになったごぼちゃん(@XB37q)です!

このコラムでは、PLSAという手法を深く紹介します。
複雑な数式でモデルを構築しているため、理解が難しい方に理解してもらうために、このコラムを作成しました。

PLSAの理論

PLSAの流れ
PLSAの流れ

PLSAでは、3種類の確率変数P(x|z), P(y|z), P(z)を計算することが最終アウトプットです。
3種類の確率変数は式(1)~式(6)のように最尤法を用いて、計算します。

PLSAの式(1)~式(6)は大きく2つの段階に区別されます。

式(1)、式(2)
共起確率P(x,y)を潜在クラスタzを使って表現し、対数尤度関数Lを求める

xとyが同時に出現する共起確率P(x,y)は、潜在クラスタzを使って式(1)のようにモデル化できます。
また、xとyの同時出現頻度をN(x,y)とすると、対数尤度関数Lは式(2)のようになります。
この対数尤度関数Lを最大にする確率変数P(x|z), P(y|z), P(z)をEMアルゴリズムを用いて推定します。

式(3)~式(6)
EMアルゴリズムで、確率変数P(x|z), P(y|z), P(z)を求める

zの確率分布P(z|x,y)を計算する式(3)のEステップと、Eステップで計算したP(z|x,y)を用いて対数尤度関数Lを最大化するようなP(x|z), P(y|z), P(z)を計算する式(4)~(6)のMステップを繰り返します。

なお、EMアルゴリズムをスタートするには、P(x|z), P(y|z), P(z)の初期値が必要です。
PLSAはこの初期値によって最終的な解が微妙に影響を受ける初期値依存性があります。
他のクラスター分析の手法であるk-meansも同様に初期値依存性があり、クラスター分析には初期値依存性がつきものです。

PLSAを理解するために必要な公式の復習

PLSAで使用する公式
PLSAで使用する公式

PLSAに使われる基礎的な公式です。
この公式を簡単に使いこなすことで、PLSAの理解に1歩近づくことができます!
1つ1つの公式は非常に簡単なため、必ず理解してください!!

乗法定理は、条件付き確率の公式から、導出される公式です。
条件付確率の公式とは別の定理になっていますが、ただ右辺と左辺を移行しただけの公式です。

ベイズの定理は、条件付確率の公式に乗法定理を導入することで、導出されます。

式(1)の導出

PLSAの理論 式(1)-モデル化
PLSAの理論 式(1)-モデル化

式(1)では、共起確率P(x,y)を潜在クラスタzを使って表現します。
このように共起確率P(x,y)を表現することによって、式(1)はクラスタzからxとyが生成されると考えることができます。

補足ですが、加法定理と乗法定理を組み合わせた展開方法を周辺化と呼びます。
そのため、一度に②を導くことも可能です。

PLSAでは、P(x)とP(y)を独立と考えているため、②から③を導くことができます。

式(2)の導出

PLSAの理論 式(2)-対数尤度関数1
PLSAの理論 式(2)-対数尤度関数1

PLSAでは、3種類の確率変数P(x|z), P(y|z), P(z)を計算することが最終アウトプットになります。
その最終アウトプットに向けて、最尤法を用いるために式(2)では対数尤度関数を求めます。

N(x,y)は文書xで単語yが出現する回数を表しています。
つまり、N(x,y)が大きいデータの場合、この対数尤度関数も大きくなります。

このように、EMアルゴリズムのE-Stepで求める潜在クラスタzの事後分布を、④のように変形します。
しかし、logの中にΣがある場合、解析的に求めることが難しいことが立証されています。
そのため、もう1つ工夫してあげる必要があります。

式(2)からEMアルゴリズムまで

PLSAの理論 式(2)-対数尤度関数 続き
PLSAの理論 式(2)-対数尤度関数 続き

式(2)の対数尤度に対して、イェンセンの方程式を用いて下限を求めます。
※イェンセンの方程式 参考:https://www.ccn.yamanashi.ac.jp/~tmiyamoto/img/variational_bayes1.pdf
対数尤度の下限を最大化するパラメータを求めることにより、間接的に対数尤度を最大化するのです。

そして、③の式になった後、ついにEMアルゴリズムを使用します。

クラスタzの事後分布からなる2項目を固定し(E-step)、その他の事後分布を求めます(M-step)。
対数尤度が収束するまで、E-stepとM-stepを繰り返すのがEMアルゴリズムです。

式(3)の導出

PLSAの理論 式(3)-Eステップ
PLSAの理論 式(3)-Eステップ

クラスタzの事後分布を求めます。
P(x|z), P(y|z), P(z)に対して、ランダムな値を初期値として設定し、P(z|x,y)を固定します。

PLSAの理論 EMアルゴリズム(M-Step)

PLSAの理論 Mステップ
PLSAの理論 Mステップ

クラスタzの事後分布を固定した状態で、その他の事後分布を求めます。
対数尤度Lに対してラグランジュの未定乗数法を使用します。

そして、ラグランジュの未定乗数法を用いて、事後分布を求めます。
※ラグランジュの未定乗数法 参考:https://mathtrain.jp/mlm

PLSAの理論 式(4)の導出

PLSAの理論 式(4)-Mステップ
PLSAの理論 式(4)-Mステップ

先ほどのFを微分することで、P(x|z)を求めます。
P(x|z)はクラスタzの中でデータxが出現する確率です。
クラスターがどのような構成で作られているかを確認することができます

PLSAの理論 式(5)の導出

PLSAの理論 式(5)-Mステップ
PLSAの理論 式(5)-Mステップ

先ほどのFを微分することで、P(y|z)を求めます。
P(y|z)はクラスタzの中でデータyが出現する確率です。
クラスターがどのような構成で作られているかを確認することができます。

PLSAの理論 式(6)の導出

PLSAの理論 式(6)-Mステップ
PLSAの理論 式(6)-Mステップ

先ほどのFを微分することで、P(z)を求めます。
P(z)はクラスタzの存在確率を表しています。

PLSAの自由パラメータ(参考)

PLSAの自由度
PLSAの自由度

PLSAの自由度は上記の式で求められるそうです。

まとめ

  • PLSA
    • 3種類の確率変数P(x|z), P(y|z), P(z)を計算することが最終アウトプット
    • 初期値によって最終的な解が微妙に影響を受ける初期値依存性があります。
  • 共起確率P(x,y)を潜在クラスタzを使って表現し、対数尤度関数Lを求める
    • 共起確率P(x,y)は、潜在クラスタzを使ってモデル化
    • 対数尤度関数Lを求める
    • 対数尤度関数Lを最大にする確率変数P(x|z), P(y|z), P(z)をEMアルゴリズムを用いて推定
  • EMアルゴリズム
    • EステップとMステップを対数尤度が収束するまで交互に繰り返す
    • zの確率分布P(z|x,y)を計算するEステップ
    • 対数尤度関数Lを最大化するようなP(x|z), P(y|z), P(z)を計算するMステップ

参考書籍

EMアルゴリズムを使ったPLSAを数式から理解する!” に対して1件のコメントがあります。

コメントは受け付けていません。