からっぽのしょこ

読んだら書く!書いたら読む!同じ事は二度調べ(たく)ない

3.3:混合ユニグラムモデルの最尤推定(EMアルゴリズム)の導出【青トピックモデルのノート】

はじめに

 『トピックモデル』(MLPシリーズ)の勉強会資料のまとめです。各種モデルやアルゴリズムを「数式」と「プログラム」を用いて解説します。
 本の補助として読んでください。

 この記事では、混合カテゴリモデルにおけるEMアルゴリズムを用いた最尤推定の数式の行間を埋めます。

【前節の内容】

www.anarchive-beta.com

【他の節の内容】

www.anarchive-beta.com

【この節の内容】

3.3 混合ユニグラムモデルの最尤推定(EMアルゴリズム)の導出

 混合ユニグラムモデル(mixture of unigram model)に対するEMアルゴリズム(EM algorithm)を用いた最尤推定(maximum likelihood estimation)におけるパラメータの計算式を導出する。
 混合ユニグラムモデルの定義や記号については「3.1-2:混合ユニグラムモデル【『トピックモデル』の勉強ノート】 - からっぽのしょこ」を参照のこと。

最尤解の設定

 最尤推定では、尤度  p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi}) を最大化するパラメータ  \boldsymbol{\theta}, \boldsymbol{\Phi} を求める。

 \displaystyle
\begin{aligned}
\boldsymbol{\theta}_{\mathrm{ML}}
   &= \mathop{\mathrm{argmax}}\limits_{\boldsymbol{\theta}}
          p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi})
\\
   &= \mathop{\mathrm{argmax}}\limits_{\boldsymbol{\theta}}
          \log p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi})
\\
\boldsymbol{\Phi}_{\mathrm{ML}}
   &= \mathop{\mathrm{argmax}}\limits_{\boldsymbol{\Phi}}
          p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi})
\\
   &= \mathop{\mathrm{argmax}}\limits_{\boldsymbol{\Phi}}
          \log p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi})
\end{aligned}

  \mathop{\mathrm{argmax}}\limits_{x} f(x) は、関数  f(x) を最大化させる引数(変数)  x を表す。また、トピック分布と単語分布のパラメータの最尤解を  \boldsymbol{\theta}_{\mathrm{ML}}, \boldsymbol{\Phi}_{\mathrm{ML}} とする。
 計算を簡単にするため、対数尤度  \log p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi}) の最大化を考える。

 混合ユニグラムモデルの尤度は、次の式で定義される。

 \displaystyle
\begin{aligned}
p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi})
   &= \prod_{d=1}^D
          p(\mathbf{w}_d | \boldsymbol{\theta}, \boldsymbol{\Phi})
\\
   &= \prod_{d=1}^D
          \sum_{k=1}^K
              p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_{z_d})
\\
   &= \prod_{d=1}^D 
          \sum_{k=1}^K \Bigl\{
              p(z_d = k | \boldsymbol{\theta})
              p(\mathbf{w}_d | z_d = k, \boldsymbol{\phi}_{z_d})
          \Bigr\}
\\
   &= \prod_{d=1}^D
          \sum_{k=1}^K \left\{
              p(z_d = k | \boldsymbol{\theta})
              \prod_{n=1}^{N_d}
                  p(w_{dn} | \boldsymbol{\phi}_k)
          \right\}
\\
   &= \prod_{d=1}^D
          \sum_{k=1}^K \left\{
              \theta_k
              \prod_{n=1}^{N_d}
                  \phi_{kw_{dn}}
          \right\}
\\
   &= \prod_{d=1}^D
          \sum_{k=1}^K \left\{
              \theta_k
              \prod_{v=1}^V
                  \phi_{kv}^{N_{dv}}
          \right\}
\end{aligned}

途中式の途中式(クリックで展開)


  • 1-4: 混合ユニグラムモデルの定義(3.1節)より、尤度(文書集合の生成確率)を各文書のトピックの生成確率と各単語の生成確率の積に分解する。
  • 5: 尤度を具体的な式(各トピックと各単語の生成確率をカテゴリ分布のパラメータ)に置き換える。
  • 6: 文書番号  d と単語番号  n を用いた式から、語彙番号  v を用いた式に変換する。

 尤度の式については「3.1-2:混合ユニグラムモデル【『トピックモデル』の勉強ノート】 - からっぽのしょこ」を参照のこと。
 混合ユニグラムモデルの対数尤度は、解析的に計算できない。そこで、EMアルゴリズムにより繰り返し値を更新して最尤解を近似することを考える。

 EMアルゴリズムを行うために、文書  d がトピック  k である確率を  q_{dk} として、負担率  \mathbf{q} = \{\mathbf{q}_1, \cdots, \mathbf{q}_D\} \mathbf{q}_d = (q_{d1}, \dots, q_{dK}) を導入する。 \mathbf{q}_d の各要素は確率なので、それぞれ非負の値であり、総和(全てのトピックに関する和)が1になる条件を満たす必要がある。

 \displaystyle
0 \leq q_{dk} \leq 1
,\ 
\sum_{k=1}^K q_{dk}
    = 1

 イェンゼンの不等式を用いて、対数尤度の下限を求める。

 \displaystyle
\begin{align}
\log p(\mathbf{W} | \boldsymbol{\theta}, \boldsymbol{\Phi})
   &= \sum_{d=1}^D
          \log \sum_{k=1}^K \Bigl\{
              p(z_d = k | \boldsymbol{\theta})
              p(\mathbf{w}_d | \boldsymbol{\phi}_k)
          \Bigr\}
    \equiv
      L
\tag{3.1}\\
   &= \sum_{d=1}^D
          \log \sum_{k=1}^K \left\{
              q_{dk}
              \frac{
                  p(z_d = k | \boldsymbol{\theta})
                  p(\mathbf{w}_d | \boldsymbol{\phi}_k)
              }{
                  q_{dk}
              }
          \right\}
\\
   &\geq
      \sum_{d=1}^D \sum_{k=1}^K \left\{
          q_{dk}
          \log \left(
              \frac{
                  p(z_d = k | \boldsymbol{\theta})
                  p(\mathbf{w}_d | \boldsymbol{\phi}_k)
              }{
                  q_{dk}
              }
          \right)
      \right\}
\\
   &= \sum_{d=1}^D \sum_{k=1}^K \left\{
          q_{dk}
          \log \left(
              \frac{
                  \theta_k
                  \prod_{v=1}^V \phi_{kv}^{N_{dv}}
              }{
                  q_{dk}
              }
          \right)
      \right\}
\\
   &= \sum_{d=1}^D \sum_{k=1}^K \left\{
          q_{dk} \left(
              \log \theta_k
              + \sum_{v=1}^V N_{dv} \log \phi_{kv}
              - \log q_{dk}
          \right)
      \right\}
    \equiv F
\tag{3.2}
\end{align}

途中式の途中式(クリックで展開)


  • 1: 対数をとった尤度を考える。
  • 2:  \frac{q_{dk}}{q_{dk}} = 1 を分割して掛けて、負担率を導入する。
  • 3: イェンゼンの不等式(1.1.10項)を用いて、下限の式に変形する。
  • 4: 混合ユニグラムモデルの定義(3.1節)より、尤度を具体的な式に置き換える
  • 5: 対数の性質  \log (x y) = \log x + \log y \log \frac{x}{y} = \log x - \log y \log x^a = a \log x より、分数を分解する。

 対数尤度を  L、対数尤度の下限を  F とおく。
 イェンゼンの不等式については「1.1.8-10:カルバック・ライブラー・ダイバージェンスとイェンゼンの不等式【『トピックモデル』の勉強ノート】 - からっぽのしょこ」を参照のこと。

 対数尤度の代わりに、下限を最大化するパラメータを考える。

 \displaystyle
\begin{align}
\mathbf{q}^{\mathrm{new}}
   &= \mathop{\mathrm{argmax}}\limits_{\mathbf{q}}
          F
\\
\boldsymbol{\theta}^{\mathrm{new}}
   &= \mathop{\mathrm{argmax}}\limits_{\boldsymbol{\theta}}
          F
\\
\boldsymbol{\Phi}^{\mathrm{new}}
   &= \mathop{\mathrm{argmax}}\limits_{\boldsymbol{\Phi}}
          F
\end{align}

 EMアルゴリズムでは、対数尤度の下限を最大化する負担率とパラメータを求める。負担率の更新とパラメータの更新の2つのステップを交互に繰り返すことで、対数尤度の下限を最大化していき、(解析的に計算できない)最大化された対数尤度に近付けていく。

Eステップ

 Eステップでは、パラメータが与えられた下で(更新したパラメータで固定して)、対数尤度の下限が最大化するように負担率を更新する。

負担率の更新式の導出

 ラグランジュの未定乗数法を用いて、 \sum_{k=1}^K q_{dk} = 1 の制約の下で下限  F が最大となる負担率  q_{dk} を求める。

 \displaystyle
F(q_{dk})
    = q_{dk} \left(
          \log \theta_k
          + \sum_{v=1}^V
              N_{dv} \log \phi_{kv}
          - \log q_{dk}
      \right)
      + \lambda \left(
          \sum_{k=1}^K
              q_{dk}
          - 1
      \right)
\tag{3.4}

途中式の途中式(クリックで展開)


  • 1: ラグランジュ乗数  \lambda を用いて、最大化問題の対象である対数尤度の下限(3.2)と制約条件(総和が1である)を含めて、 q_{dk} の関数  F(q_{dk}) を立てる。

 ラグランジュの未定乗数法については「1.1.11:ラグランジュの未定乗数法【『トピックモデル』の勉強ノート】 - からっぽのしょこ」を参照のこと。
 ここでは  q_{dk} に注目するため、 F(q_{dk}) とおく。
 対数尤度の下限の項に関して、文書  d 以外の文書  1, \dots, d-1, d+1, \dots, D、またトピック  k 以外のトピック  1, \dots, k-1, k+1, \dots, K の項は  q_{dk} に影響しないため省ける。または、定数  \mathrm{const.} としてまとめておくと偏微分の際に0になり消える。

 関数  F(q_{dk}) q_{dk} に関して微分する。

 \displaystyle
\begin{aligned}
\frac{\partial F(q_{dk})}{\partial q_{dk}}
   &= \frac{\partial}{\partial q_{dk}} \left\{
          q_{dk} \left(
              \log \theta_k
              + \sum_{v=1}^V
                  N_{dv} \log \phi_{kv}
              - \log q_{dk}
          \right)
        + \lambda \left(
            \sum_{k=1}^K
                q_{dk}
            - 1
          \right)
      \right\}
\\
   &= \frac{\partial}{\partial q_{dk}} \Bigl\{
          q_{dk} \log \theta_k
        \Bigr\}
      + \frac{\partial}{\partial q_{dk}} \left\{
          q_{dk}
          \sum_{v=1}^V
              N_{dv} \log \phi_{kv}
        \right\}
      - \frac{\partial}{\partial q_{dk}} \Bigl\{
          q_{dk} \log q_{dk}
      \Bigr\}
\\
   &\qquad
      + \frac{\partial}{\partial q_{dk}} \left\{
          \lambda \left(
              \sum_{k=1}^K
                  q_{dk}
              - 1
          \right)
      \right\}
\\
   &= \log \theta_k
      \frac{\partial q_{dk}}{\partial q_{dk}}
      + \left(
          \sum_{v=1}^V
              N_{dv} \log \phi_{kv}
      \right)
      \frac{\partial q_{dk}}{\partial q_{dk}}
      - \left(
          \log q_{dk}
          \frac{\partial q_{dk}}{\partial q_{dk}}
          + q_{dk}
          \frac{\partial \log q_{dk}}{\partial q_{dk}}
      \right)
\\
   &\qquad
      + \lambda
        \frac{\partial q_{dk}}{\partial q_{dk}}
\\
   &= \log \theta_k
      + \sum_{v=1}^V
              N_{dv} \log \phi_{kv}
      - \log q_{dk}
      - \frac{q_{dk}}{q_{dk}}
      + \lambda
\end{aligned}

途中式の途中式(クリックで展開)


  • 1:  F(q_{dk}) の式全体の微分を考える。
  • 2: 和の微分  \{f(x) + g(x)\}' = f'(x) + g'(x) より、項ごとの微分の和に分割する。
  • 3-4:  q_{dk} に関する微分なので、それ以外の項  q_{dk'}\ (k' \neq k) \theta_k, \phi_{kv} は定数として扱う。これを偏微分と言う。

  q_{dk} の係数は  \frac{\partial}{\partial q_{dk}} の外に出せ、変数の微分は  \{x\}' = 1 なので、1つ目と2つ目の項は、係数のみが残る。
 3つ目の項は、積の微分  \{f(x)g(x)\}' = f'(x)g(x) + f(x)g'(x) と自然対数の微分  \{\log x\}' = \frac{1}{x} より、次のようになる。

 \displaystyle
\begin{aligned}
\frac{\partial q_{dk} \log q_{dk}}{\partial q_{dk}}
   &= (\log q_{dk})
      \frac{\partial q_{dk}}{\partial q_{dk}}
      + q_{dk}
        \frac{\partial \log q_{dk}}{\partial q_{dk}}
\\
   &= \log q_{dk}
      + q_{dk} \frac{1}{q_{dk}}
\\
   &= \log q_{dk} + 1
\end{aligned}

 最後の項は、 k に関する項の係数のみが残る。

 \displaystyle
\begin{aligned}
\frac{\partial}{\partial q_{dk}} \left\{
    \lambda \left(
        \sum_{k=1}^K
            q_{dk}
        - 1
    \right)
\right\}
   &= \lambda
      \frac{\partial}{\partial q_{dk}} \left\{
          \sum_{k=1}^K
              q_{dk}
          - 1
      \right\}
\\
   &= \lambda
      \frac{\partial}{\partial q_{dk}} \Bigl\{
          q_{d1}
          + \cdots
          + q_{dk}
          + \cdots
          + q_{dK}
          - 1
      \Bigr\}
\\
   &= \lambda \left(
          \frac{\partial q_{d1}}{\partial q_{dk}}
          + \cdots
          + \frac{\partial q_{dk}}{\partial q_{dk}}
          + \cdots
          + \frac{\partial q_{dK}}{\partial q_{dk}}
          - \frac{\partial 1}{\partial q_{dk}}
      \right)
\\
   &= \lambda \left(
          0
          + \cdots
          + 1
          + \cdots
          + 0
          - 0
      \right)
\\
   &= \lambda
\end{aligned}

 定数の微分は  \{a\}' = 0 である。


  \frac{\partial F(q_{dk})}{\partial q_{dk}} = 0 となる  q_{dk} を求める。

 \displaystyle
\begin{align}
&&
\log \theta_k
+ \sum_{v=1}^V
    N_{dv} \log \phi_{kv}
- \log q_{dk}
+ \lambda - 1
   &= 0
\\
\Rightarrow &&
\log q_{dk}
   &= \lambda - 1
      + \log \theta_k
      + \sum_{v=1}^V
          N_{dv} \log \phi_{kv}
\\
\Rightarrow &&
\exp(\log q_{dk})
   &= \exp \left(
          \lambda - 1
          + \log \theta_k
          + \sum_{v=1}^V
              N_{dv} \log \phi_{kv}
      \right)
\\
&&
   &= \exp(\lambda - 1)
      \exp(\log \theta_k)
      \exp \left(
          \log \prod_{v=1}^V
              \phi_{kv}^{N_{dv}}
      \right)
\\
\Rightarrow &&
q_{dk}
   &= \exp(\lambda - 1)
      \theta_k
      \prod_{v=1}^V \phi_{kv}^{N_{dv}}
\tag{3.5}
\end{align}

途中式の途中式(クリックで展開)


  • 1:  \frac{\partial F(q_{dk})}{\partial q_{dk}} 0 とおく。
  • 2:  \log q_{dk} について式を整理する。
  • 3: 両辺それぞれで全体をネイピア数  e の指数  e^x = \exp(x) にする。
  • 4: 指数の性質  e^{n+m} = e^n e^m より、和が積になる。
  • 5: 指数と対数の関係  x = \exp(\log x) より、 \log を外す。

 この式の両辺で  k に関して和をとる。

 \displaystyle
\begin{align}
&&
\sum_{k=1}^K
    q_{dk}
   &= \sum_{k=1}^K \left\{
          \exp(\lambda - 1) \theta_k
          \prod_{v=1}^V
              \phi_{kv}^{N_{dv}}
      \right\}
\\
\Rightarrow &&
1  &= \exp(\lambda - 1)
      \sum_{k=1}^K \left\{
          \theta_k
          \prod_{v=1}^V
              \phi_{kv}^{N_{dv}}
      \right\}
\\
\Rightarrow &&
\exp(\lambda - 1)
   &= \frac{
          1
      }{
          \sum_{k=1}^K \left\{
              \theta_k
              \prod_{v=1}^V
                  \phi_{kv}^{N_{dv}}
          \right\}
      }
\tag{3.6}
\end{align}

途中式の途中式(クリックで展開)


  • 1:  k に関して  1 から  K まで和をとる。
  • 2: 負担率  \mathbf{q}_d の定義より、 \sum_{k=1}^K q_{dk} = 1 である。
  • 2: 係数を  \sum の外に出す。
  • 3:  \exp(\lambda - 1) について式を整理する。

 この式を式(3.5)に代入する。

 \displaystyle
q_{dk}
    = \frac{
          \theta_k
          \prod_{v=1}^V
              \phi_{kv}^{N_{dv}}
      }{
          \sum_{k'=1}^K \left\{
              \theta_{k'}
              \prod_{v=1}^V
                  \phi_{k'v}^{N_{dv}}
          \right\}
      }
\tag{3.3}

 文書  d におけるトピック  k に関する負担率  q_{dk} の更新式が得られた。他の文書やトピックについても同様に求められる。

Mステップ

 Mステップでは、負担率が与えられた下で(更新した負担率で固定して)、対数尤度の下限が最大化するようにパラメータを更新する。

トピック分布のパラメータの更新式の導出

 Eステップと同様に、 \sum_{k=1}^K \theta_k = 1 の制約の下で下限  F が最大となるパラメータ  \theta_k を求める。

 \displaystyle
\begin{aligned}
F(\theta_k)
    = \sum_{d=1}^D
          q_{dk} \left(
              \log \theta_k
              + \sum_{v=1}^V
                  N_{dv} \log \phi_{kv}
              - \log q_{dk}
          \right)
      + \lambda \left(
          \sum_{k=1}^K
              \theta_k
          - 1
      \right)
\end{aligned}

 ここでは  \theta_k に注目するため、関数  F(\theta_k) とおく。
 対数尤度の下限の項に関して、 k' = 1, \dots, k-1, k+1, \dots, K の項は  \theta_k に影響しないため省ける。

 関数  F(\theta_k) \theta_k に関して微分する。

 \displaystyle
\begin{align}
\frac{\partial F(\theta_k)}{\partial \theta_k}
   &= \frac{\partial}{\partial \theta_k} \left\{
          \sum_{d=1}^D
              q_{dk} \left(
                  \log \theta_k
                  + \sum_{v=1}^V
                      N_{dv} \log \phi_{kv}
                  - \log q_{dk}
              \right)
          + \lambda \left(
              \sum_{k=1}^K
                  \theta_k
              - 1
          \right)
      \right\}
\\
   &= \frac{\partial}{\partial \theta_k} \left\{
          \left(
              \sum_{d=1}^D
                  q_{dk}
          \right)
          \log \theta_k
      \right\}
      + \frac{\partial}{\partial \theta_k} \left\{
          \sum_{d=1}^D \left(
              q_{dk}
              \sum_{v=1}^V
                  N_{dv} \log \phi_{kv}
          \right)
        \right\}
      - \frac{\partial}{\partial \theta_k} \left\{
          \sum_{d=1}^D
              q_{dk} \log q_{dk}
        \right\}
\\
   &\qquad
      + \frac{\partial}{\partial \theta_k} \left\{
          \lambda \left(
              \sum_{k=1}^K
                  \theta_k
              - 1
          \right)
      \right\}
\\
   &= \left(
          \sum_{d=1}^D
              q_{dk}
      \right)
      \frac{\partial \log \theta_k}{\partial \theta_k}
      + 0
      - 0
      + \lambda \frac{\partial \theta_k}{\partial \theta_k}
\\
   &= \frac{
          \sum_{d=1}^D
              q_{dk}
      }{
          \theta_k
      }
      + \lambda
\end{align}

途中式の途中式(クリックで展開)


  • 1-4:  \theta_k に関する微分なので、それ以外の項  \theta_{k'}\ (k' \neq k) \phi_{kv}, q_{dk} は定数として扱う。

  \frac{\partial F(\theta_k)}{\partial \theta_k} = 0 となる  \theta_k を求める。

 \displaystyle
\begin{align}
&&
\frac{
    \sum_{d=1}^D
        q_{dk}
}{
    \theta_k
}
+ \lambda
   &= 0
\\
\Rightarrow &&
\theta_k
   &= \frac{
          \sum_{d=1}^D
              q_{dk}
      }{
          - \lambda
      }
\tag{1}
\end{align}

途中式の途中式(クリックで展開)


  • 1:  \frac{\partial F(\theta_k)}{\partial \theta_k} 0 とおく。
  • 2:  \theta_k について式を整理する。

 この式の両辺で  k に関して和をとる。

 \displaystyle
\begin{aligned}
&&
\sum_{k=1}^K
    \theta_k
   &= \sum_{k=1}^K
          \frac{
              \sum_{d=1}^D
                  q_{dk}
          }{
              - \lambda
          }
\\
\Rightarrow &&
1  &= - \frac{1}{\lambda}
        \sum_{k=1}^K \sum_{d=1}^D
          q_{dk}
\\
\Rightarrow &&
\lambda
   &= - \sum_{k=1}^K \sum_{d=1}^D
          q_{dk}
\end{aligned}

途中式の途中式(クリックで展開)


  • 1:  k に関して  1 から  K まで和をとる。
  • 2: カテゴリ分布のパラメータ  \boldsymbol{\theta} の定義より、 \sum_{k=1}^K \theta_k = 1 である。
  • 2: 係数を  \sum の外に出す。
  • 3:  \lambda について式を整理する。

 この式を(1)に代入する。

 \displaystyle
\theta_k
    = \frac{
          \sum_{d=1}^D
              q_{dk}
      }{
          \sum_{k'=1}^K \sum_{d=1}^D
              q_{dk'}
      }
\tag{3.7}

 トピック  k に関するトピック分布のパラメータ  \theta_k の更新式が得られた。他のトピックについても同様に求められる。

単語分布のパラメータの更新式の導出

 これまでと同様に、 \sum_{v=1}^V \phi_{kv} = 1 の制約の下で下限  F が最大となるパラメータ  \phi_{kv} を求める。

 \displaystyle
\begin{aligned}
F(\phi_{kv})
    = \sum_{d=1}^D
          q_{dk} \left(
              \log \theta_k
              + \sum_{v=1}^V
                  N_{dv} \log \phi_{kv}
              - \log q_{dk}
          \right)
      + \lambda \left(
          \sum_{k=1}^K
              \phi_{kv}
          - 1
      \right)
\end{aligned}

 ここでは  \phi_{kv} に注目するため、関数  F(\phi_{kv}) とおく。
 対数尤度の下限の項に関して、 k' = 1, \dots, k-1, k+1, \dots, K (と  v 以外の  1 から  V も) の項は  \phi_{kv} に影響しないため省ける。

 関数  F(\phi_{kv}) \phi_{kv} に関して微分する。

 \displaystyle
\begin{aligned}
\frac{\partial F(\phi_{kv})}{\partial \phi_{kv}}
   &= \frac{\partial}{\partial \phi_{kv}} \left\{
          \sum_{d=1}^D
              q_{dk} \left(
                  \log \theta_k
                  + \sum_{v=1}^V
                      N_{dv} \log \phi_{kv}
                  - \log q_{dk}
              \right)
          + \lambda \left(
              \sum_{k=1}^K
                  \phi_{kv}
              - 1
          \right)
      \right\}
\\
   &= \frac{\partial}{\partial \phi_{kv}} \left\{
          \left(
              \sum_{d=1}^D
                  q_{dk}
          \right)
          \log \theta_k
      \right\}
      + \frac{\partial}{\partial \phi_{kv}} \left\{
          \sum_{d=1}^D \left(
              q_{dk}
              \sum_{v=1}^V
                  N_{dv} \log \phi_{kv}
          \right)
        \right\}
      - \frac{\partial}{\partial \phi_{kv}} \left\{
          \sum_{d=1}^D
              q_{dk} \log q_{dk}
        \right\}
\\
   &\qquad
      + \frac{\partial}{\partial \phi_{kv}} \left\{
          \lambda \left(
              \sum_{k=1}^K
                  \phi_{kv}
              - 1
          \right)
      \right\}
\\
   &= 0
      + \left(
          \sum_{d=1}^D
              q_{dk} N_{dv}
        \right)
        \frac{\partial \log \phi_{kv}}{\partial \phi_{kv}}
      - 0
      + \lambda
        \frac{\partial \phi_{kv}}{\partial \phi_{kv}}
\\
   &= \frac{
          \sum_{d=1}^D
              q_{dk} N_{dv}
      }{
          \phi_{kv}
      }
      + \lambda
\end{aligned}

途中式の途中式(クリックで展開)


  • 1-4:  \phi_{kv} に関する微分なので、それ以外の項  \phi_{k'v'}\ (k' \neq k, v' \neq v) \theta_k, q_{dk} は定数として扱う。

 全ての文書で  v 番目の項のみが残る。

 \displaystyle
\begin{aligned}
\frac{\partial}{\partial \phi_{kv}} \left\{
    \sum_{d=1}^D \left(
        q_{dk}
        \sum_{v=1}^V
            N_{dv} \log \phi_{kv}
    \right)
\right\}
   &= \sum_{d=1}^D
          q_{dk}
          \frac{\partial}{\partial \phi_{kv}} \left\{
              \sum_{v=1}^V
                  N_{dv} \log \phi_{kv}
          \right\}
\\
   &= \sum_{d=1}^D
          q_{dk}
          \frac{\partial}{\partial \phi_{kv}} \Bigl\{
              N_{d1} \log \phi_{k1}
              + \cdots
              + N_{dv} \log \phi_{kv}
              + \cdots
              + N_{dV} \log \phi_{kV}
          \Bigr\}
\\
   &= \sum_{d=1}^D
          q_{dk} \left(
              \frac{\partial N_{d1} \log \phi_{k1}}{\partial \phi_{kv}}
              + \cdots
              + \frac{\partial N_{dv} \log \phi_{kv}}{\partial \phi_{kv}}
              + \cdots
              + \frac{\partial N_{dV} \log \phi_{kV}}{\partial \phi_{kv}}
          \right)
\\
   &= \sum_{d=1}^D
          q_{dk} \left(
              0
              + \cdots
              + N_{dv}
                \frac{\partial \log \phi_{kv}}{\partial \phi_{kv}}
              + \cdots
              + 0
          \right)
\\
   &= \sum_{d=1}^D
          q_{dk}
          N_{dv}
          \frac{1}{\phi_{kv}}
\end{aligned}

  \frac{\partial F(\phi_{kv})}{\partial \theta_k} = 0 となる  \theta_k を求める。

 \displaystyle
\begin{align}
&&
\frac{
    \sum_{d=1}^D
        q_{dk} N_{dv}
}{
    \phi_{kv}
}
+ \lambda
   &= 0
\\
\Rightarrow &&
\phi_{kv}
   &= \frac{
          \sum_{d=1}^D
              q_{dk} N_{dv}
      }{
          - \lambda
      }
\tag{2}
\end{align}

途中式の途中式(クリックで展開)


  • 1:  \frac{\partial F(\phi_{kv})}{\partial \phi_{kv}} 0 とおく。
  • 2:  \phi_{kv} について式を整理する。

 両辺で  v に関して和をとる。

 \displaystyle
\begin{aligned}
&&
\sum_{v=1}^V
    \phi_{kv}
   &= \sum_{v=1}^V
          \frac{
              \sum_{d=1}^D q_{dk} N_{dv}
          }{
              - \lambda
          }
\\
\Rightarrow &&
1  &= - \frac{1}{\lambda}
        \sum_{v=1}^V \sum_{d=1}^D
          q_{dk} N_{dv}
\\
\Rightarrow &&
\lambda
   &= - \sum_{v=1}^V \sum_{d=1}^D
          q_{dk} N_{dv}
\end{aligned}

途中式の途中式(クリックで展開)


  • 1:  v に関して  1 から  V まで和をとる。
  • 2: カテゴリ分布のパラメータ  \boldsymbol{\phi}_k の定義より、 \sum_{v=1}^V \phi_{kv} = 1 である。
  • 2: 係数を  \sum の外に出す。
  • 3:  \lambda について式を整理する。

 この式を式(2)に代入する。

 \displaystyle
\phi_{kv}
    = \frac{
          \sum_{d=1}^D
              q_{dk} N_{dv}
      }{
          \sum_{v=1}^V \sum_{d=1}^D
              q_{dk} N_{dv}
      }
\tag{3.8}

 トピック  k における語彙  v に関する単語分布のパラメータ  \phi_{kv} の更新式が得られた。他のトピックや語彙についても同様に求められる。

対数尤度と下限の関係の導出

 最後に、対数尤度と対数尤度の下限の差から関係をみる。

 対数尤度  L と下限  F の差を求める。

 \displaystyle
\begin{align}
L - F
   &= \sum_{d=1}^D
          \log \sum_{k=1}^K
              p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
      - \sum_{d=1}^D \sum_{k=1}^K \left\{
          q_{dk}
          \log \frac{
              p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
          }{
              q_{dk}
          }
      \right\}
\\
   &= \sum_{d=1}^D
          \left\{
              \sum_{k=1}^K
                  q_{dk}
          \right\}
          \log p(\mathbf{w}_d | \boldsymbol{\theta}, \boldsymbol{\Phi})
      - \sum_{d=1}^D \sum_{k=1}^K \left\{
          q_{dk}
          \log \frac{
              p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
          }{
              q_{dk}
          }
      \right\}
\\
   &= \sum_{d=1}^D \sum_{k=1}^K
          q_{dk} \left(
              \log p(\mathbf{w}_d | \boldsymbol{\theta}, \boldsymbol{\Phi})
              - \log \frac{
                   p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
              }{
                  q_{dk}
              }
          \right)
\\
   &= \sum_{d=1}^D \sum_{k=1}^K
          q_{dk}
          \log \left(
              p(\mathbf{w}_d | \boldsymbol{\theta}, \boldsymbol{\Phi})
              \frac{
                  q_{dk}
              }{
                  p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
              }
          \right)
\\
   &= \sum_{d=1}^D \sum_{k=1}^K
          q_{dk}
          \log \frac{
              q_{dk}
          }{
              p(z_d = k |\mathbf{w}_d, \boldsymbol{\theta}, \boldsymbol{\phi}_k)
          }
\\
   &= \sum_{d=1}^D
          \mathrm{KL} \Bigl(
              \boldsymbol{q}_d, 
              p(z_d |\mathbf{w}_d, \boldsymbol{\theta}, \boldsymbol{\Phi})
          \Bigr)
\tag{3.9}
\end{align}

途中式の途中式(クリックで展開)


  • 1: 対数尤度と対数尤度の下限の差を考える。
  • 2: 対数尤度に関して、トピックを周辺化する。
  • 2: 対数尤度の項と下限の項の式の形を揃えるために、対数尤度の項に  \sum_{k=1}^K q_{dk} = 1 を掛ける。
  • 3:  q_{dk} で括る。
  • 4: 対数の性質  - \log (\frac{x}{y}) = - \log x + \log y = \log \frac{y}{x} より、 \log の項をまとめる。
  • 5: 条件付き確率  \frac{p(A, B)}{p(B)} = p(A | B) より、 \mathbf{w}_d を条件に入れる。

 文書  d の単語集合  \mathbf{w}_d とトピック  z_d の同時分布は、依存関係より

 \displaystyle
p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
    = p(\mathbf{w}_d | z_d = k, \boldsymbol{\phi}_k)
      p(z_d = k | \boldsymbol{\theta})

と分割できるので、ベイズ定理  p(B | A) = \frac{p(A | B) p(B)}{p(A)} としても捉えられる。

 \displaystyle
\begin{aligned}
p(z_d = k | \mathbf{w}_d, \boldsymbol{\theta}, \boldsymbol{\phi}_k)
   &= \frac{
          p(\mathbf{w}_d, z_d = k | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
      }{
          p(\mathbf{w}_d | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
      }
\\
   &= \frac{
          p(\mathbf{w}_d | z_d = k, \boldsymbol{\phi}_k)
          p(z_d = k | \boldsymbol{\theta})
      }{
          p(\mathbf{w}_d | \boldsymbol{\theta}, \boldsymbol{\phi}_k)
      }
\end{aligned}

 ただし、逆数として変形している。

  • 6: 式の形が(離散型確率分布の)KLダイバージェンス  \mathrm{KL}(p, q) = \sum_x p(x) \log \frac{p(x)}{q(x)} なので、式を置き替える。

 対数尤度  L と下限  L の差が、各文書の負担率  \mathbf{q}_d とトピックの事後分布  p(z_d | \mathbf{w}_d, \boldsymbol{\theta}, \boldsymbol{\Phi}) のKLダイバージェンスを全ての文書で和をとった値であることが分かった。
 対数尤度と下限が一致する(差が0になる)のとき、(全ての文書で)負担率と事後分布が一致する(KLダイバージェンスが0になる)ことを表す。
 KLダイバージェンスについては「1.1.8-10:カルバック・ライブラー・ダイバージェンスとイェンゼンの不等式【『トピックモデル』の勉強ノート】 - からっぽのしょこ」を参照のこと。

 この記事では、混合ユニグラムモデルにおける最尤推定を数式で確認した。次の記事では、プログラムで確認する。
 またこの節では、最尤推定によりパラメータを点推定した。次節では、変分ベイズ推定によりパラメータを分布推定する。

参考書籍

  • 岩田具治(2015)『トピックモデル』(機械学習プロフェッショナルシリーズ)講談社

おわりに

2019/07/26:加筆修正しました。

2020/07/24:加筆修正の際に記事から「混合ユニグラムモデル」を分割しました。


  • 2024.05.15:加筆修正しました。

 どうして投稿時にあとがきを書いてないんだろう。全く記憶がない。

【次節の内容】

  • スクラッチ実装編

 アルゴリズム3.1を参考にして、ループ処理を使って実装します。

www.anarchive-beta.com

 行列計算を使ってシンプルに実装します。

www.anarchive-beta.com


  • 数式読解編

 混合ユニグラムモデルに対する変分ベイズ推定を数式で確認します。

www.anarchive-beta.com

 トピックモデルに対する最尤推定を数式で確認します。

www.anarchive-beta.com