SSNB

"Text Classification from Labeled and Unlabeled Documents using EM", JMLR, 2000

ナイーブベイズを半教師ありに拡張した手法。半教師あり学習について知らない人は別の所の説明を見てね。

ナイーブベイズがナイーブかつベイズと言われるゆえんがこの式変形。文書 $d$ がクラス（ラベル） $c$ に属する確率は以下のように書ける。

$P(c|d) \propto P(d|c)P(c) \\ = \prod_i P(w_i|c)P(c)$

一つ目の変形でベイズの定理を使い、二つ目の変形で文書 $d$ に含まれる単語 $w_i$ は全て（cについて条件付き）独立に生成されるというナイーブな仮定を置いている。

ここでナイーブベイズで求めたいパラメータは $P(w_i|c)$ と $P(c)$ となる。普通の教師ありのナイーブベイズだと簡単に求まるんだけど半教師ありだとそうはいかない。

対数尤度

いま、手元に文書データ集合 $D$ があるとし、それはラベル付き文書集合 $D^L$ とラベル無し文書集合 $D^U$ に分けられるとする（ $D = D^L \cup D^U$ ）。

普通の教師ありナイーブベイズでは、学習に $D^L$ のみを使うが、半教師ありのナイーブベイズでは $D^L$ と $D^U$ の両方を学習に使う。

対数尤度は以下のように書ける

$\log P(D) = \log P(D^L) + \log P(D^U) \\ = \sum_{d_i \in D^L} \log P(d_i,y_i) + \sum_{d_i \in D^U} \log \sum_k P(d_i,z_i=c_k) \\ = \sum_{d_i \in D^L} \log P(d_i|y_i)P(y_i) + \sum_{d_i \in D^U} \log \sum_k P(d_i|z_i=c_k)P(z_i=c_k)$

ただし、観測変数 $y_i$ は文書 $d_i$ のラベルを表し、潜在変数 $z_i$ は文書 $d_i$ の（観測されていない）ラベルを表す。第二項目はラベルが観測されていないため、全ての $z$ についての和をとっている。

ここで、 $D^U$ に関する対数尤度（第二項）は、対数の中に和があるので最大化は難しいように見える。

一方、 $D^L$ に関する対数尤度（第一項）は、対数の中に和がないため、最大化が簡単に見える。

つまり、不完全データを含む対数尤度をそのまま最大化するのは難しそうだが、完全データ対数尤度の最大化は簡単そうということになる。

ということでEMアルゴリズムが登場する。

E-step

Eステップでは潜在変数 $z_i$ の事後分布を計算する。

$P(z_i=c_k|d_i) = \frac{P(d_i|z_i=c_k)P(z_i=c_k)}{\sum_k P(d_i|z_i=c_k)P(z_i=c_k)}$

これはベイズの定理により簡単に求まった。

ここで、超重要ポイントが１点。ラベルが観測されている文書 $d \in D^L$ に対しては $P(z_i=c_k|d_i) = \delta(y_i=c_k)$ と固定する。ただし $\delta(y_i=c_k)$ は $y_i = c_k$ の時 $1$ 、それ以外で $0$ を取る関数である。

こうすることで、ラベルが観測されている文書 $d \in D^L$ も観測されていない文書 $d \in D^U$ も同様に扱えるようになる。

M-step

Mステップでは $q(z_i=c_k) = P(z_i=c_k|d_i)$ と固定し、Q関数を最大にするパラメータ $P(w_i|c)$ と $P(c)$ を求める。

ある文書 $d_i$ に注目すると、Q関数は以下のように書ける

$Q = \sum_k P(z_i=c_k|d_i) \log P(d_i,z_i=c_k) \\ = \sum_k P(z_i=c_k|d_i) \log P(d_i|z_i=c_k)P(z_i=c_k) \\ = \sum_k P(z_i=c_k|d_i) \log \prod_{w_j \in d_i}P(w_j|z_i=c_k)P(z_i=c_k) \\ = \sum_k P(z_i=c_k|d_i) [\log P(z_i=c_k) + \sum_{w} n(d_i,w)\log P(w|z_i=c_k)]$

ただし、 $n(d,w)$ は文書 $d$ に単語 $w$ が含まれる回数を示す。文書データ集合全体に注目すると、Q関数は

$Q= \sum_i\sum_k P(z_i=c_k|d_i) [\log P(z_i=c_k) + \sum_{w} n(d_i,w) \log P(w|z_i=c_k)]$

となり、これを最大化するパラメータを求めることになる。

$P(c)$ についてQ関数を最大化

$\sum_k P(c_k)=1$ という制約があるため、ラグランジュ定数 $\lambda$ を用いて

$H = Q + \lambda(\sum_k P(c_k) - 1)$

を最大化する。

$H$ を $P(c_k)$ で微分して $0$ とおくと

$\frac{\partial H}{\partial P(c_k)} = \sum_i P(z_i=c_k|d_i) \cdot \frac{1}{P(c_k)} + \lambda = 0$

となる。 $P(c_k)$ について整理すると、

$P(c_k) = - \frac{\sum_i P(z_i=c_k|d_i)}{\lambda}$

となる。 $k$ についての和を取ると

$\sum_k P(c_k) = 1 = \sum_k - \frac{\sum_i P(z_i=c_k|d_i)}{\lambda} \\ = - \frac{1}{\lambda} \sum_i\sum_kP(z_i=c_k|d_i) \\ = - \frac{1}{\lambda} \sum_i 1 \\ = - \frac{1}{\lambda} |D|$

となる。ただし、 $|D|$ は文書の数を表す。 $\lambda$ について整理すると $\lambda = -|D|$ となるため

$P(c_k) = \frac{\sum_i P(z_i=c_k|d_i)}{|D|}$

と求まる。

$P(w|c)$ についてQ関数を最大化

$\sum_w P(w|c) = 1$ という制約があるため、ラグランジュ定数 $\lambda_k$ を用いて

$H = Q + \sum_k \lambda_k(\sum_w P(w|c_k) - 1)$

を最大化する。

$H$ を $P(w|c_k)$ で微分して $0$ と置くと

$\frac{\partial H}{\partial P(w|c_k)} = \sum_i P(z_i=c_k|d_i) \cdot \frac{n(d_i,w)}{P(w|c_k)} + \lambda_k = 0$

となる。 $P(w|c_k)$ について整理すると

$P(w|c_k) = - \frac{\sum_i P(z_i=c_k|d_i)n(d_i,w)}{\lambda_k}$

となる。 $w$ について和を取ると

$\sum_w P(w|c_k) = 1 = \sum_w - \frac{\sum_i P(z_i=c_k|d_i)n(d_i,w)}{\lambda_k}$

となる。 $\lambda_k$ について整理すると

$\lambda_k = - \sum_w \sum_i P(z_i=c_k|d_i)n(d_i,w)$

となるため

$P(w|c_k) = \frac{\sum_i P(z_i=c_k|d_i)n(d_i,w)}{\sum_w \sum_i P(z_i=c_k|d_i)n(d_i,w)}$

と求まる。

まとめ

以上より、EMアルゴリズムを用いたSSNBのパラメータ推定の手続きは

適当な値で $P(w|c_k)$ 、 $P(c_k)$ を初期化する
ラベル観測されていない文書 $d_i \in D^U$ について、 $P(z_i=c_k|d_i) = \frac{P(d_i|z_i=c_k)P(z_i=c_k)}{\sum_k P(d_i|z_i=c_k)P(z_i=c_k)}$ を計算する
ラベル観測されている文書 $d_i \in D^L$ について、 $P(z_i=c_k|d_i) = \delta(y_i=c_k)$ と固定する
$P(c_k) = \frac{\sum_i P(z_i=c_k|d_i)}{|D|}$ を計算する
$P(w|c_k) = \frac{\sum_i P(z_i=c_k|d_i)n(d_i,w)}{\sum_w \sum_i P(z_i=c_k|d_i)n(d_i,w)}$ を計算する
収束するまで2-4を繰り返す

となる。