からっぽのしょこ

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

2.7:ユニグラムモデルのMAP推定の導出:ハイパーパラメータ推定【青トピックモデルのノート】

はじめに

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

 この記事では、カテゴリモデルに対するMAP推定(ハイパーパラメータ推定)の数式の行間を埋めます。

【前節の内容】

www.anarchive-beta.com

【他の節の内容】

www.anarchive-beta.com

【この節の内容】

2.7 ユニグラムモデルのMAP推定の導出:ハイパーパラメータ推定

 ユニグラムモデル(unigram model)に対する不動点反復法(固定点反復法・fixed point iteration)を用いた最大事後確率推定(MAP推定・maximum a posteriori estimation)におけるハイパーパラメータの計算式を導出する。この節では、ハイパーパラメータに事前分布を設定して、ハイパーパラメータを推定する。
 ユニグラムモデルの定義や記号については「2.2:ユニグラムモデルの生成モデルの導出【青トピックモデルのノート】 - からっぽのしょこ」、ハイパーパラメータに事前分布を設定しない(パラメータを推定する)場合については「2.4:ユニグラムモデルのMAP推定の導出:パラメータ推定【青トピックモデルのノート】 - からっぽのしょこ」を参照のこと。

MAP解の設定

 ここでは、単語分布のハイパーパラメータ  \boldsymbol{\beta} = (\beta_1, \cdots, \beta_V) を一様な値  \beta_1 = \cdots = \beta_V = \beta として  \beta で表す(  V 次元ベクトルをスカラで表記する)。
 また、ハイパーパラメータ  \beta の事前確率(事前分布)として、パラメータ  c, d を持つガンマ分布  \mathrm{Gam}(\beta | c, d) を設定する。

 ハイパーパラメータに事前確率を設定したMAP推定では、事後確率  p(\beta | \mathbf{W}, c, d) を最大化するハイパーパラメータ  \beta を求める。

 \displaystyle
\begin{align}
\beta_{\mathrm{MAP}}
   &= \mathop{\mathrm{argmax}}\limits_{\beta}
          p(\beta | \mathbf{W}, c, d)
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta}
          \log p(\beta | \mathbf{W}, c, d)
\tag{1}
\end{align}

  \mathop{\mathrm{argmax}}\limits_{x} f(x) は、関数  f(x) を最大化させる引数(変数)  x を表す。また、単語分布のハイパーパラメータのMAP解を  \beta_{\mathrm{MAP}} とする。
 計算を簡単にするため、対数をとった事後確率  \log p(\beta | \mathbf{W}, c, d) の最大化を考える。

 ハイパーパラメータに事前分布を設定したユニグラムモデルにおける事後確率は、ベイズの定理より、パラメータ  \boldsymbol{\phi} を周辺化した周辺尤度  p(\mathbf{W} | \beta) とハイパーパラメータ  \beta の事前確率  p(\beta | c, d) を用いて、次の式で定義される。

 \displaystyle
p(\beta | \mathbf{W}, c, d)
    = \frac{
          p(\mathbf{W} | \beta)
          p(\beta | c, d)
      }{
          p(\mathbf{W} | c, d)
      }
\tag{2.5'}

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


  • 1: ベイズ定理  p(B | A) = \frac{p(A | B) p(B)}{p(A)} より、確率変数(観測データ)とパラメータの条件関係を入れ替える。

 ベイズの定理に当てはめなくても得られる。

 \displaystyle
\begin{aligned}
p(\beta | \mathbf{W}, c, d)
   &= \frac{
          p(\mathbf{W}, \beta | c, d)
      }{
          p(\mathbf{W} | c, d)
      }
\\
   &= \frac{
          \int
              p(\mathbf{W}, \boldsymbol{\phi}, \beta | c, d)
          \mathrm{d} \boldsymbol{\phi}
      }{
          \iint
              p(\mathbf{W}, \boldsymbol{\phi}, \beta | c, d)
          \mathrm{d} \boldsymbol{\phi} \mathrm{d} \beta
      }
\\
   &= \frac{
          \int
              p(\mathbf{W} | \boldsymbol{\phi})
              p(\boldsymbol{\phi} | \beta)
              p(\beta | c, d)
          \mathrm{d} \boldsymbol{\phi}
      }{
          \iint
              p(\mathbf{W} | \boldsymbol{\phi})
              p(\boldsymbol{\phi} | \beta)
              p(\beta | c, d)
          \mathrm{d} \boldsymbol{\phi} \mathrm{d} \beta
      }
\end{aligned}
  • 1: 条件付き確率  p(A | B) = \frac{p(A, B)}{p(B)} より、項を分割する。
  • 2: 連続型の確率変数の周辺化  p(A) = \int p(A, B) \mathrm{d} B より、周辺化されていたパラメータ  \boldsymbol{\phi} を明示する。
  • 3: 乗法定理  p(A, B) = p(A | B) p(B) より、依存関係に従い項を分割する。

 分母は、 \boldsymbol{\phi}, \beta を周辺化した周辺確率  p(\mathbf{W} | c, d) であり、 \beta に影響しない。

 この式を式(1)に代入して、式を整理する。

 \displaystyle
\begin{align}
\beta_{\mathrm{MAP}}
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \left[
          \log \frac{
              p(\mathbf{W} | \beta)
              p(\beta | c, d)
          }{
              p(\mathbf{W} | c, d)
          }
      \right]
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \Bigl[
          \log p(\mathbf{W} | \beta)
          + \log p(\beta | c, d)
          - \log p(\mathbf{W} | c, d)
      \Bigr]
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \Bigl[
          \log p(\mathbf{W} | \beta)
          + \log p(\beta | c, d)
      \Bigr]
\tag{2}\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \Biggl[
          \log \left(
              \frac{
                  \Gamma(\sum_{v=1}^V \beta_v)
              }{
                  \Gamma(N + \sum_{v=1}^V \beta_v)
              }
              \prod_{v=1}^V
                  \frac{\Gamma(N_v + \beta_v)}{\Gamma(\beta_v)}
          \right)
      \Biggr.
\\
   &\qquad \qquad \qquad
      \Biggl.
          + \log \left(
              \frac{d^c}{\Gamma(c)}
              \beta^{c-1}
              \exp(- d \beta)
          \right)
      \Biggr]
\end{align}

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


  • 1: 式(1)の事後確率の項を事後確率の式(2.5')に置き換える。
  • 2: 対数の性質  \log (x y) = \log x + \log y \log \frac{x}{y} = \log x - \log y より、分数を分解する。
  • 3:  \beta と無関係な周辺確率の項を省く。
  • 4: ユニグラムモデルの定義(2.2節)より、周辺尤度(パラメータを周辺化した文書集合の生成確率)とハイパーパラメータの事前確率(ガンマ分布)を具体的な式に置き換える。

 周辺尤度の式については「2.2:ユニグラムモデルの生成モデルの導出【青トピックモデルのノート】 - からっぽのしょこ」を参照のこと。
  \beta に影響しない項は省ける。
 事後確率を最大化するパラメータは、周辺尤度と事前確率の対数の和を最大化するパラメータを求めればよいことが分かった。
 ただし、周辺尤度を解析的に計算するのは困難である。そこで、不動点反復法により繰り返し値を更新してMAP解を近似することを考える。

不動点反復法の更新式の導出

 周辺尤度(2.8')に関して、2つの項をそれぞれ

 \displaystyle
\begin{aligned}
\frac{\Gamma(V \beta)}{\Gamma(N + V \beta)}
   &\geq
      \frac{\Gamma(V \beta)}{\Gamma(N + V \beta)}
      \exp \Bigl(
          V (\beta - \beta^{\mathrm{new}})
          b
      \Bigr)
\\
\frac{\Gamma(N_v + \beta)}{\Gamma(\beta)}
   &\geq
      \frac{\Gamma(N_v + \beta)}{\Gamma(\beta)}
      \beta^{-a}
      (\beta^{\mathrm{new}})^a
\end{aligned}

に置き換えて、下限  G とおく。

 \displaystyle
\begin{align}
p(\mathbf{W} | \beta)
   &= \frac{\Gamma(V \beta)}{\Gamma(N + V \beta)}
      \prod_{v=1}^V
          \frac{\Gamma(N_v + \beta)}{\Gamma(\beta)}
\tag{2.8'}\\
   &\geq
      \frac{\Gamma(V \beta)}{\Gamma(N + V \beta)}
      \exp \Bigl(
          (V \beta - V \beta^{\mathrm{new}})
          b
      \Bigr)
      \prod_{v=1}^V
          \frac{\Gamma(N_v + \beta)}{\Gamma(\beta)}
          \beta^{-a}
          (\beta^{\mathrm{new}})^a
    \equiv
      G
\end{align}

 また(式が長くなるので)、次のようにおいた。

 \displaystyle
\begin{aligned}
a  &= \Bigl(
          \Psi(N_v + \beta)
          - \Psi(\beta)
      \Bigr)
      \beta
\\
b  &= \Psi(N + V \beta)
      - \Psi(V \beta)
\end{aligned}
\tag{3}

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


  • 1: 対数ガンマとディガンマ関数の不等式を用いて、式を置き換える。

  \hat{x} \geq 0 に対して、 x \gt 0 n \geq 0 のとき、次の関係が成り立つ。

 \displaystyle
\begin{aligned}
\frac{\Gamma(x)}{\Gamma(n + x)}
   &\geq
      \frac{\Gamma(\hat{x})}{\Gamma(n + \hat{x})}
      \exp \Bigl(
          (\hat{x} - x) b
      \Bigr)
\\
b  &= \Psi(n + \hat{x})
      - \Psi(\hat{x})
\end{aligned}

  V \beta \hat{x} V \beta^{\mathrm{new}} x に対応させて項を変形する。
 また、 \hat{x} \geq 0 に対して、 n \geq 1 のとき、次の関係が成り立つ。

 \displaystyle
\begin{aligned}
\frac{\Gamma(n + x)}{\Gamma(x)}
   &\geq
      \frac{\Gamma(n + \hat{x})}{\Gamma(\hat{x})}
      \hat{x}^{-a}
      x^a
\\
a  &= \Bigl(
          \Psi(n + \hat{x})
          - \Psi(\hat{x})
      \Bigr)
      \hat{x}
\end{aligned}

  \beta \hat{x} \beta^{\mathrm{new}} x に対応させて項を変形する。


 現在の値を  \beta、更新後の値を  \beta^{\mathrm{new}} とする。周辺尤度に関して  \beta の周りでテイラー展開(近似)して下限として用いる。
 詳しくは「対数ガンマ関数とディガンマ関数の不等式の導出【青トピックモデルのノート】 - からっぽのしょこを参照のこと。

 周辺尤度の代わりに下限を用いて、近似的な事後確率を最大化するハイパーパラメータを考える。

 \displaystyle
\begin{align}
\beta^{\mathrm{new}}
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \Bigl[
          \log G
          + \log p(\beta | c, d)
      \Bigr]
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \Biggl[
          \log \left(
              \frac{\Gamma(V \beta)}{\Gamma(N + V \beta)}
              \exp \Bigl(
                  (V \beta - V \beta^{\mathrm{new}})
                  b
              \Bigr)
              \prod_{v=1}^V
                  \frac{\Gamma(N_v + \beta)}{\Gamma(\beta)}
                  \beta^{-a}
                  (\beta^{\mathrm{new}})^a
          \right)
      \Biggr.
\\
   &\qquad \qquad \qquad
      \Biggl.
          + \log \left(
              \frac{d^c}{\Gamma(c)}
              (\beta^{\mathrm{new}})^{c-1}
              \exp(- d \beta^{\mathrm{new}})
          \right)
      \Biggr]
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \Biggl[
          \log \Gamma(V \beta)
          - \log \Gamma(N + V \beta)
          + (V \beta - V \beta^{\mathrm{new}})
            b
      \Biggr.
\\
   &\qquad \qquad \qquad
      \Biggl.
          + \sum_{v=1}^V \Bigl\{
              \log \Gamma(N_v + \beta)
              - \log \Gamma(\beta)
              - a \log \beta
              + a \log \beta^{\mathrm{new}}
          \Bigr\}
\\
   &\qquad \qquad \qquad
      \Biggl.
          c \log d
          - \log \Gamma(c)
          + (c - 1) \log \beta^{\mathrm{new}}
          - d \beta^{\mathrm{new}}
      \Biggr]
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \left[
          - V b \beta^{\mathrm{new}}
          + \sum_{v=1}^V
              a \log \beta^{\mathrm{new}}
          + (c - 1) \log \beta^{\mathrm{new}}
          - d \beta^{\mathrm{new}}
      \right]
\\
   &= \mathop{\mathrm{argmax}}\limits_{\beta} \left[
          - (d + V b) \beta^{\mathrm{new}}
          + \left(
              c - 1
              + \sum_{v=1}^V
                  a
            \right)
            \log \beta^{\mathrm{new}}
      \right]
\end{align}

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


  • 1: 周辺尤度と事前確率の対数の和(2)に関して、周辺尤度を下限(近似)  p(\mathbf{W} | \beta) \approx G に置き換える。
  • 2: 周辺尤度の下限とハイパーパラメータの事前確率(ガンマ分布)を具体的な式に置き換える。
  • 3: 対数の性質  \log (x y) = \log x + \log y \log \frac{x}{y} = \log x - \log y \log x^a = a \log x より、積が和、商が差、べき乗が積になる。
  • 4:  \beta^{\mathrm{new}} と無関係な項を省く。
  • 5:  \beta^{\mathrm{new}}, \log \beta^{\mathrm{new}} の項をそれぞれまとめる。

  \beta^{\mathrm{new}} に影響しない項は省ける。または、定数  \mathrm{const.} としてまとめておくと偏微分の際に0になり消える。

 (近似的な)事後確率を最大化するハイパーパラメータは

 \displaystyle
- (d + V b) \beta^{\mathrm{new}}
+ \left(
    c - 1
    + \sum_{v=1}^V
        a
  \right)
  \log \beta^{\mathrm{new}}
\tag{4}

を最大化するハイパーパラメータを求めればよいことが分かった。

 周辺尤度の下限  G と事前確率の対数の和を  F とおく。また、 \beta^{\mathrm{new}} に影響しない(式(4)以外の)項をまとめて  \mathrm{const.} とする。

 \displaystyle
\begin{aligned}
F  &= \log G
      + \log p(\beta | c, d)
\\
   &= - (d + V b) \beta^{\mathrm{new}}
      + \left(
          c - 1
          + \sum_{v=1}^V
              a
        \right)
        \log \beta^{\mathrm{new}}
        + \mathrm{const.}
\end{aligned}

 関数  F \beta^{\mathrm{new}} に関して微分する。

 \displaystyle
\begin{aligned}
\frac{\partial F}{\partial \beta^{\mathrm{new}}}
   &= \frac{\partial}{\partial \beta^{\mathrm{new}}} \left\{
          - (d + V b) \beta^{\mathrm{new}}
          + \left(
              c - 1
              + \sum_{v=1}^V
                  a
            \right)
            \log \beta^{\mathrm{new}}
            + \mathrm{const.}
      \right\}
\\
   &= \frac{\partial}{\partial \beta^{\mathrm{new}}} \Bigl\{
          - (d + V b) \beta^{\mathrm{new}}
      \Bigr\}
      + \frac{\partial}{\partial \beta^{\mathrm{new}}} \left\{
          \left(
              c - 1
              + \sum_{v=1}^V
                  a
            \right)
            \log \beta^{\mathrm{new}}
        \right\}
      + \frac{\partial \mathrm{const.}}{\partial \beta^{\mathrm{new}}}
\\
   &= - (d + V b)
        \frac{\partial \beta^{\mathrm{new}}}{\partial \beta^{\mathrm{new}}}
      + \left(
          c - 1
          + \sum_{v=1}^V
              a
        \right)
        \frac{\partial \log \beta^{\mathrm{new}}}{\partial \beta^{\mathrm{new}}}
      + 0
\\
   &= - (d + V b)
      + \left(
          c - 1
          + \sum_{v=1}^V
              a
        \right)
        \frac{1}{\beta^{\mathrm{new}}}
\end{aligned}

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


  • 1:  F の式全体の微分を考える。ただし、 \beta^{\mathrm{new}} に関する微分なので、 \beta は定数として扱う。
  • 2: 和の微分  \{f(x) + g(x)\}' = f'(x) + g'(x) より、項ごとの微分の和に分割する。
  • 3:  \beta^{\mathrm{new}} の係数は  \frac{\partial}{\partial \beta^{\mathrm{new}}} の外に出せ、定数の微分は(定数  a x で微分すると)  \{a\}' = 0 である。
  • 4: 変数の微分は(変数  x x で微分すると)  \{x\}' = 1、自然対数の微分は  \{\log x\}' = \frac{1}{x} である。

  \frac{\partial G}{\partial \beta^{\mathrm{new}}} = 0 となる  \beta^{\mathrm{new}} を求める。

 \displaystyle
\begin{aligned}
&&
- (d + V b)
+ \left(
    c - 1
    + \sum_{v=1}^V
        a
  \right)
  \frac{1}{\beta^{\mathrm{new}}}
   &= 0
\\
\Rightarrow &&
\beta^{\mathrm{new}}
   &= \frac{
          c - 1
          + \sum_{v=1}^V
              a
      }{
          d
          + V b
      }
\\
&& &= \frac{
          c - 1
          + \sum_{v=1}^V
              \Bigl(
                  \Psi(N_v + \beta)
                  - \Psi(\beta)
              \Bigr)
              \beta
      }{
          d
          + V \Bigl(
              \Psi(N + V \beta)
              - \Psi(V \beta)
          \Bigr)
      }
\\
&& &= \frac{
          c - 1
          + \beta \left(
              \sum_{v=1}^V
                  \Psi(N_v + \beta)
              - V \Psi(\beta)
          \right)
      }{
          d
          + V \Psi(N + V \beta)
          - V \Psi(V \beta)
      }
\end{aligned}

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


  • 1:  \frac{\partial F}{\partial \beta^{\mathrm{new}}} 0 とおく。
  • 2:  \beta^{\mathrm{new}} について式を整理する。
  • 3:  a, b に具体的な式(3)を代入する。
  • 4: 括弧を展開する。

 不動点反復法によるハイパーパラメータの更新式が得られた。

  i 回目の更新において、 \beta を現ステップ(更新前)の値(  i-1 回目の更新値)  \beta^{(i-1)} \beta^{\mathrm{new}} を次ステップ(更新後)の値(  i 回目の更新値)  \beta^{(i)} とする。

 \displaystyle
\beta^{(i)}
    = \frac{
          c - 1
          + \beta^{(i-1)} \left(
              \sum_{v=1}^V
                  \Psi \Bigl(
                      N_v + \beta^{(i-1)}
                  \Bigr)
              - V \Psi \Bigl(
                  \beta^{(i-1)}
              \Bigr)
          \right)
      }{
          d
          + V \Psi \Bigl(
              N + V \beta^{(i-1)}
            \Bigr)
          - V \Psi \Bigl(
              V \beta^{(i-1)}
          \Bigr)
      }

 また、ハイパーパラメータの初期値を  \beta^{(0)} とする。
 この式により更新を繰り返すことで、MAP解  \beta_{\mathrm{MAP}} に近付いていく。

 この記事では、ユニグラムモデルに対する不動点反復法を用いたMAP推定によるハイパーパラメータの計算式を導出した。次の記事では、実装してハイパーパラメータを推定する。

参考書籍

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

おわりに

  • 2024.05.07:加筆修正の際に「一様なハイパーパラメータの場合の経験ベイズ推定の導出」から記事を分割しました。

 本で数行、修正前の記事でも30行ほどだった内容を丁寧に書いたら1記事分になりました。
 順序立てて書くために問題設定から追ってみて分かった(分からなくなった)のですが、これはMAP推定ってことですよね。4週目にしてようやくそれらしいキーワードで書かれていることを認識できました。
 2.7節では2手法を扱ってるから節タイトルが目的である「ハイパーパラメータ推定」になってたんですかね。

 この手法でも多様ハイパラ版を書くつもりで始めたんですが、パラメータ推定のMAP推定では書かなかったですし、書かなくていいですよね。実装はどうしましょうか。
 この記事の更新時点で、2章の数式読解編は全て書き直せました。実装編は2つ組めて解説は未着手な状況です。実装しなければこれが2章最後の記事です。

【次節の内容】

  • スクラッチ実装編

 ユニグラムモデルに対するMAP推定をプログラムで確認します。

www.anarchive-beta.com


  • 数式読解編

 混合ユニグラムモデルを数式で確認します。

www.anarchive-beta.com