しまてく

学んだ技術を書きためるブログ

ITエンジニアのための機械学習理論入門 7

第7章 EMアルゴリズム: 最尤推定法による教師なし学習

この章では2つのことを学ぶ。

  1. 特定の文字だけからなる手書き文字サンプル群から、それらを代表する「代表文字」を生成する方法。
    • ベルヌーイ分布と呼ばれる確率分布を用い、最尤推定法を実施する。
  2. 複数の文字が混在した手書き文字サンプル群を分類する方法。

7.1 ベルヌーイ分布を用いた最尤推定

  • 代表文字 = 複数の顔写真を合成した「平均的な顔」のイメージ
  • 複数の画像データを合成する方法
    • 平均を取る。
      1. 画像に含まれるピクセルを横一列に並べる
      2. ピクセルの色(黒or白)を1or0として表したベクトルにする。
      3. n番目の画像に対応するベクトルを${\bf x}_n$とする。
      4. その第i成分$[{\bf x}_n]_i$を見ると、i番目のピクセルの色がわかる。
      5. 画像データがN個あるとして、これらの平均をとったベクトル$\mu$を用意する。 $$ \mu = \dfrac{1}{N} \sum_{n=1}^{N} {\bf x}_n \tag{7.1} $$
      6. $\mu$の各成分は0から1の範囲の実数値となる。これがピクセルの色の濃淡。
    • ただし、これは直感的すぎるので、以下で理論的な根拠を見る。

「画像生成器」による最尤推定法の適用

  • 最尤推定法を適用するには、何らかの方法で「トレーニングセットが得られる確率」を計算する必要がある。
  • そこで、ランダムに手書き文字を生成する「画像生成器」を用意する。
  • (7.1)の$\mu$の各成分の値を「対応するピクセルが黒になる確率」と考える。
  • これにより、「確率$\mu_i$でi番目のピクセルを黒にする」というルールで画像を生成できる。
  • いま、トレーニングセットにN個のデータがあり、画像生成器からもN個のデータを生成するとする。
  • これらのデータ群が全て同一になる確率を考える。
  • この確率が最大になるような画像生成器を見つけ出せば、トレーニングセットを代表する画像になっているものと期待できる。

ベクトル$\mu$で表される画像生成器からトレーニングセットのデータと同じものが生成される確率を計算する。

  • トレーニングセットに含まれる特定の画像データを$\bf x$とする。
  • $\bf x$は、第$i$成分の値${\bf x}_i$が$i$番目のピクセルの色(1=黒、0=白)を表すベクトル。
  • ピクセル数は全部で$D$個あるとする。
  • この中で、特に$i$番目のピクセルに注目した場合、そのピクセルの色が得られる確率$p_i$は以下になる。

$$ x_i = 1の場合 : p_i = \mu_i \tag{7.2} $$

$$ x_i = 0の場合 : p_i = 1 - \mu_i \tag{7.3} $$

  • これらをまとめて記述すると以下になる。

$$ p_i = \mu_i^{x_i}(1 - \mu_i)^{1-x_i} \tag{7.4} $$

したがって、ある特定の画像のすべてのピクセルが同じ色になる確率は次の式で表せる。 ($D$個すべてのピクセルが同じなので掛け算する)

$$ p(x) = \prod_{i=1}^{D}p_i = \prod_{i=1}^{D}{\mu_i^{x_i}(1 - \mu_i)^{1-x_i}} \tag{7.5} $$

さらに、トレーニングセットに含まれるすべての画像のすべてのピクセルが一致する確率は次のようになる。 ($N$個の画像の$D$個のピクセルすべてが同じなので二重の掛け算する)

$$ \begin{eqnarray} P &=& \prod_{n=1}^{N}p({\bf x}_n) \nonumber \\ &=& \prod_{n=1}^{N}\prod_{i=1}^{D}[p_n]_i \nonumber \\ &=& \prod_{n=1}^{N}\prod_{i=1}^{D}{\mu_i^{[x_n]_i}(1 - \mu_i)^{1-[x_n]_i}} \tag{7.6} \end{eqnarray} $$

  • これが、このモデルにおける尤度関数となる。
  • これを最大にする$\mu$を計算すると、(7.1)が得られる。
  • つまり、(7.1)は尤度関数(7.6)を最大化する画像生成器といえる。

(7.6)を最大化する$\mu$を求めてみる。

  • まず計算を簡単にするため対数尤度関数$lnP$を計算し、これを最大化する$\mu$を求める。

$$ \begin{eqnarray} P &=& \prod_{n=1}^{N}\prod_{i=1}^{D}{\mu_i^{[x_n]_i}(1 - \mu_i)^{1-[x_n]_i}} \nonumber \\ lnP &=& \sum_{n=1}^N\sum_{i=1}^D{ln\mu_i^{[x_n]_i}(1 - \mu_i)^{1-[x_n]_i}} \nonumber \\ lnP &=& \sum_{n=1}^N\sum_{i=1}^D{ln\mu_i^{[x_n]_i} + ln(1 - \mu_i)^{1-[x_n]_i}} \nonumber \\ lnP &=& \sum_{n=1}^N\sum_{i=1}^D\{[{\bf x}_n]_i ln\mu_i + (1 - [{\bf x}_n]_i)ln(1-\mu_i)\} \tag{7.7} \end{eqnarray} $$

  • これを$\mu_i$で偏微分すると以下のようになる。

$$ \begin{eqnarray} \dfrac{\partial(lnP)}{\partial \mu_i} &=& \sum_{n=1}^N\left(\dfrac{[{\bf x}_n]_i}{\mu_i} - \dfrac{1 - [{\bf x}_n]_i}{1-\mu_i}\right) \tag{7.8} \end{eqnarray} $$

$$ \begin{eqnarray} x &=& lnA \nonumber \\ x' &=& \dfrac{A'}{A} \end{eqnarray} $$

  • これが0になるという条件から、以下のように変形できる。

$$ \begin{eqnarray} \sum_{n=1}^N\left(\dfrac{[{\bf x}_n]_i}{\mu_i} - \dfrac{1 - [{\bf x}_n]_i}{1-\mu_i}\right) &=& 0 \nonumber \\ \sum_{n=1}^N\dfrac{[{\bf x}_n]_i}{\mu_i} - \sum_{n=1}^N\dfrac{1 - [{\bf x}_n]_i}{1-\mu_i} &=& 0 \nonumber \\ (1-\mu_i)\sum_{n=1}^N[{\bf x}_n]_i - \mu_i\sum_{n=1}^N(1 - [{\bf x}_n]_i) &=& 0 \nonumber \\ \sum_{n=1}^N[{\bf x}_n]_i - \mu_i\sum_{n=1}^N[{\bf x}_n]_i - \mu_i\sum_{n=1}^N + \mu_i\sum_{n=1}^N[{\bf x}_n]_i &=& 0 \nonumber \\ \sum_{n=1}^N[{\bf x}_n]_i - \mu_iN &=& 0 \nonumber \\ \mu_iN &=& \sum_{n=1}^N[{\bf x}_n]_i \nonumber \\ \mu_i &=& \dfrac{1}{N}\sum_{n=1}^N[{\bf x}_n]_i \nonumber \tag{7.9} \end{eqnarray} $$

  • これは、(7.1)を成分表記したものである。

$$ \mu = \dfrac{1}{N}\sum_{n=1}{N}{\bf x}_n \tag{7.1} $$

  • (7.4)や(5.6)はベルヌーイ分布と呼ばれる確率分布。
  • 上記のモデルは「ベルヌーイ分布を用いた最尤推定法」と呼ぶ。

7.2 混合分布を用いた最尤推定

  • 7.1ではある一種類の数字からなる、手書き文字画像のトレーニングセットを利用した。
  • ここでは、全部で$K$種類の数字を含む、手書き文字画像のトレーニングセットを利用する。
  • 全部で$K$種類なので、画像生成器は $\{\mu_k\}_{k=1}^{K}$ とする。
  • この時、特定の画像生成器$\mu_k$から画像$\bf x$が得られる確率は(7.5)同様に以下式になる。

$$ p_{\mu_k}({\bf x}) = \prod_{i=1}^{D}{[\mu_k]_i^{x_i}(1 - [\mu_k]_i)^{1-x_i}} \tag{7.10} $$

  • どの画像生成器を使うか、ということも確率に入れて考える。
  • どれか1つの画像生成器をランダムに選択し、新しい画像を生成する。
  • ここで、$k$番目の画像生成器を選ぶ確率を$\pi_k$とする。
  • $\{\pi_k\}_{k=1}^K$は、以下の条件を満たす。

$$ \sum_{k=1}^K\pi_k = 1 \tag{7.11} $$

このような操作で、特定の画像$\bf x$が得られる確率は以下になる。

  1. ある画像生成器が選択される確率( = $\pi_k$)
  2. 特定の画像生成器からある画像$\bf x$が得られる確率( = $p_{\mu_k}({\bf x})$)
  3. 数字は全部で$K$種類あるので、すべての場合を足し合わせる。

$$ p({\bf x}) = \sum_{k=1}^K\pi_kp_{\mu_k}({\bf x}) \tag{7.12} $$

  • さらに、トレーニングセット内のデータ数が$N$個とすると、トレーニングセットのデータ群と一致する確率は以下になる。

$$ P = \prod_{n=1}^{N}p({\bf x}_n) = \prod_{n=1}^{N}\sum_{k=1}^K\pi_kp_{\mu_k}({\bf x}_n) \tag{7.13} $$

  • (7.13)が、このモデルの尤度関数になる。
  • このように、複数のベルヌーイ分布を混ぜたものを混合ベルヌーイ分布と呼ぶ。

EMアルゴリズムの手続き

  • ここで、尤度関数(7.13)を最大化するパラメーターを決定するのだが、簡単にはできない。
  • 積の計算$\Pi$と和の計算$Σ$が混在しているので、対数尤度関数にしてもうまく進められない。
  • このような場合に、EMアルゴリズムを適用することができる。
  • EMアルゴリズムは、k平均法に類似した方になる。

手順

  1. $K$個の画像生成器 $\{\mu_k\}_{k=1}^{K}$ を用意する。
  2. それぞれの画像生成器を選択する確率($\{\pi_k\}_{k=1}^K$)は条件(7.11)を満たす。
  3. どれが一つの画像生成器を選択して、画像${\bf x}_n$が得られる確率は、 $$ p({\bf x}_n) = \sum_{k=1}^K\pi_kp_{\mu_k}({\bf x}_n) \tag{7.14} $$
  4. 特定の$k$番目の画像生成器から、画像${\bf x}_n$が得られる可能性について、その割合を以下で取り出す。 $$ \gamma_{nk} = \dfrac{\pi_kp_{\mu_k}({\bf x}_n)}{\sum_{k'=1}^K\pi_{k'}p_{\mu_{k'}}({\bf x}_n)} \tag{7.15} $$
  5. これはk平均法において、トレーニングセットに含まれるデータ${\bf x}_n$が所属する代表点を決める操作に相当する。
  6. k平均法の場合は最も距離が近い代表点に所属するという条件で設定した。
  7. 上記の$\gamma_{nk}$はこれに相当する。
  8. 今の場合、${\bf x}_n$はどれか一つの画像生成器に所属するのではなく、それぞれの画像生成器に対して、$\gamma_{nk}$の割合で所属する。
  9. 各画像生成器に所属する割合が決まったら、この割合に基づいて、新たに画像生成器$\{\mu_k\}_{k=1}^{K}$を作りなおす。 $$ \mu_k = \dfrac{\sum_{n=1}^N\gamma_{nk}{\bf x}_n}{\sum_{n=1}^N\gamma_{nk}} \tag{7.16} $$
  10. これはk平均法において、各クラスターの重心として新たな代表点をとる操作にあたる。
  11. 特に、(7.16)は(6.3)と同じ形の計算式になっていることがわかる。
  12. あるいは、(7.16)は1種類の文字についての代表文字を作成する(7.1)を$K$種類の文字の混合版に拡張したと考えることができる。
  13. さらに、それぞれの画像生成器を選択する確率 $\{\pi_k\}_{k=1}^K$も作りなおす。 $$ \pi_k = \dfrac{\sum_{n=1}^N\gamma_{nk}}{N} \tag{7.17} $$
  14. (7.17)は、それぞれの画像生成器を使用する割合を「それぞれの画像生成器に所属する画像の量」に比例するようにしている。

以上でEMアルゴリズムの手続きは完成で、(7.16)・(7.17)で決まった値を用いて再度(7.15)を計算、 そしてまた(7.16)・(7.17)というように繰り返す。

繰り返すごとに(7.13)の尤度関数の値が大きくなり、最終的に極大値に達する。

とりあえずここまで。