Semi-Supervised Learning (Chapelle et al., 2006)のChapter 3読んだ

Semi-Supervised Text Classification Using EM
Nigam, K., McCallum, A. and Mitchell, T.
私なんぞでも知っている有名人GoogleのNigamさんによるChapter 3 (pp.33-55)． McCallum, Mitchellも有名人．Tom MitchellはMachine Learningのテキストを1997年に出していますね．この章はテキスト分類にEMアルゴリズムを効率的に適用したもの．生成モデルを用いたテキスト分類には3つの重要なポイントがある．1つはシンプルな表現ではあるが，あるテキストのドメインでは生成モデルの確率と分類精度には正の相関があること，2つ目はあるドメインではこのような相関がないこと，3つ目はEMは局所最適に陥ることである．

1. Introduction

EMアルゴリズムで欠損値推定がうまくいく理論的背景は，labeled dataだけを用いる場合よりも，現在考えているモデルクラスによって生成される非常に大量なunlabeled dataを用いることで，よりもっともらしいモデルが見つかる可能性があるため
このアプローチは生成モデルが正しいという仮定をおいている
特にテキスト分類においてはかなりシンプルなモデル構造（たとえばナイーブベイズ分類器のような）を用いることが多い
このような生成モデルアプローチによる半教師あり学習はテキスト分類において適切 or 役に立つのだろうか？（先に結論を言うとうまくいくし，適切．けど，気をつけるところはいっぱいある）
EMアルゴリズムの危険性の一つに局所最適しか保証されていないことがある

2. A Generative Model for Text

テキスト分類における生成モデルの仮定
- データは混合モデルから生成される
- 混合要素(mixture component)とクラス間の一対一対応がある
- 混合要素は各単語の多項分布である
これらの仮定はナイーブベイズ分類器の仮定であり，よく用いられる(Lewis, 1998; McCallum and Nigam, 1998)

文書が多項分布モデルの混合として生成されると仮定する
$M$ クラス，ボキャブラリサイズを $|X|$
各文書 $x_i$ は $|x_i|$ の単語をもつ
このモデルを用いた文書の生成方法は
- 文書のクラスを決めるために $M$ 面サイコロを転がす(余談だがM-sided dieって最初なに？って思った…)
- 次に選んだクラスに一致する $|X|$ 面サイコロを選ぶ
- $x_i$ 回サイコロ投げ，各単語の頻度をカウントする
- これらの単語頻度が文書を生成する

各文書は $\theta$ による混合モデルのパラメータによって定義される確率分布に応じて生成
文書 $x_i$ は混合重み $P(c_j|\theta)$ に応じて混合要素を選択し，確率分布 $P(x_i|c_j;\ \theta)$ に応じて文書を生成する要素を選ぶ
文書 $x_i$ を目にする尤度は各混合要素の確率の和なので，次式

　　　　　 $P(x_i | \theta) = \sum\limits_{j \in [M]} P(c_j|\theta)P(x_i|c_j;\theta)$

各文書はクラスラベルを持つ
文書 $x_i$ のクラスを $y_i$ とする
もし，文書 $x_i$ が混合要素 $c_j$ によって生成されたならば， $y_i = c_j$ である

文書 $x_i$ は単語頻度vector
$x_{it}$ を文書内の単語 $w_t$ の頻度
文書の長さを $|x_i| = \sum_{t=1}^{|X|}x_{it}$ とし要素とは独立に選ばれる
選ばれた混合要素が特定の長さの文書を生成するのに使われる
上の式の第二項を以下のように拡張

　　　　　 $P(x_i|c_j; \theta) \propto P(|x_i|) \prod_{w_t \in X} P(w_t|c_j; \theta)^{x_{it}}$

これは標準的ナイーブベイズの仮定を含んでいる
あるクラスラベルが与えられたとき，文書内の単語は同じ文書内の他の単語と条件付き独立

完全な生成モデルはさきほどの2つの式をまとめて

　　　　　 $P(x_i|\theta) \propto P(|x_i|) \sum\limits_{j \in [M]} P(c_j; \ \theta) \prod\limits_{w_t \in X} P(w_t|c_j; \ \theta)^{x_{it}}$

Supervised Text Classification with Generative Models

ラベル付き文書集合によるナイーブベイズ分類器の学習は生成モデルのパラメータを推定すること
推定されたパラメータ $\theta$ は $\hat \theta$
ナイーブベイズはMAP推定を使って $\arg \max_\theta P(\theta|X, Y)$
事前分布はディリクレ分布の積
ディリクレ分布はら考分布の共役事前分布によく使われる

　　　　　 $P(\theta_{w_t|c_j}|\alpha) \propto \prod_{w_t \in X} P(w_t|c_j)^{\alpha_t -1}$

$\alpha_t$ は0より大きい定数
ディリクレ分布の良いイントロはStolck and Omohundro (1994)参照
単語選択確率の推定値 $\hat \theta_{w_t|c_j}$ は経験的な頻度のスムージング

　　　　　 $\hat \theta_{w_t|c_j} \equiv P(w_t|c_j; \hat \theta) = \frac{1+\sum_{x_i \in X}\delta_{ij}x_{it}}{|X|+ \sum_{s=1}^{|X|} \delta_{ij}x_{is}}$

ここで $\delta_{ij}$ は $y_i = c_j$ のとき1，そうでなければ0
クラス確率も同様に

　　　　　 $\hat \theta_{cj} \equiv P(c_j| \hat \theta) = \frac{1+\sum_{i=1}^{|X|} \delta_{ij}}{M+|X|}$

ベイズの定理より生成モデルは

　　　　　 $P(y_i = c_j|x_i; \hat \theta) = \frac{P(c_j|\hat \theta)P(x_i|c_j; \hat \theta)}{P(x_i|\hat \theta)}$
　　　　　　　　　　　　　 $=\frac{P(c_j|\hat \theta)\prod_{w_t \in X}P(w_t|c_j; \hat \theta)^{x_{it}}}{\sum_{k=1}^M P(c_k|\hat \theta) \prod_{w_t \in X}P(w_t|c_k; \hat \theta)^{x_{it}}}$

Semi-Supervised Text Classification with EM

半教師あり学習においても，教師ありと同様にパラメータのMAP推定をしたい
unlabeled dataはlabelがないので，EMアルゴリズムを用いることで生成モデルの局所MAP推定を求めたい
- ナイーブベイズ分類器を教師ありデータでつくる
- 次に，ナイーブベイズでunlabeled dataを分類する
- labeled dataとunlabeled dataを使ってともにナイーブベイズ分類器を作り直す
- これを分類器が安定するまで繰り返す

完全データにおける期待対数確率は

　　　　　 $l(\theta|X,Y) = \log (P(\theta ))+\sum_{x_i \in X_u} \log \sum_{j \in [M]}P(c_j|\theta)P(x_i|c_j; \theta)+ \sum_{x_i \in X_l} \log (P(y_i = c_j |\theta)P(x_i|y_i=c_j;\theta))$

EMアルゴリズムのEステップは今回のケースではunlabeled dataを分類することに対応し，Mステップは新しいパラメータ $\hat \theta$ をMAP推定することに対応する

Discussion

このアプローチの正当性はデータが混合モデルから生成されており，混合要素と各クラスが一対一対応しているという仮定に依存
次節で性能チェック

3. Experimental Results with Basic EM

Mitchell (1997)の20 newsgroupsテキスト分類データを使用
タスクは各記事を該当するnewsgroupに分類すること
unlabeled dataは10,000記事
教師データだけだとデータサイズが100で精度が30%，1000で精度が65%程度，5000で75%くらい
教師なしデータを追加で教師データサイズ100で精度が55%，1000で70%，5000で78%くらい

もっと精度を高めるにはどうしたらいいのか？
生成モデルが完璧ならEMで精度が上がるが，生成モデルがシンプルなので文書内に含まれる多くの特徴が捉え切れていない？
モデルの確率(尤度)と正確さは良い相関があった

4. Using a More Expressive Generative Model

生成モデルの次の仮定として，混合モデルにおいてクラスと要素に一対一対応しているというのがあった
あるテキストドメインではこのような仮定は明らかにデンジャラス！

単一の混合要素で負例の海をモデリングする代わりに多くの混合要素でモデリングするのがいいかもしれない
そこで，混合要素とクラス間の一対一対応を緩和する
これは各クラスにサブトピック構造をモデル化できるように緩和している

Multiple Mixture Components per Class

前のモデルではサイコロを転がし，一つのクラスを選び，各クラスはサブトピックを持っているので，再度サイコロを転がしサブトピックを選んでいた．そしてサブトピックが決まってから単語が生成される
unlabeled documentにはその文書のクラスとサブトピックが未観測変数
labeled dataであっても，クラスはわかってもサブトピックは未観測
このlocal MAP推定値を推定するためにEMを使う必要

新しいモデルではj番目の混合要素(サブトピック)を $c_j \in [N]$ とし，a番目のクラスを表すのに $t_a \in [M]$ とする
$c_j$ が $t_a$ に属するとき， $q_{aj} = 1$ ,そうでなければ0
各文書のクラスラベルを $y_i$ ，サブトピックのラベルを $z_i$
文書 $x_i$ が $c_j$ から生成されていれば $z_i = c_j$ ，文書がクラス $t_a$ に属していれば， $y_i = t_a$

生成モデルパラメータのMAP推定値は単語確率パラメータは

　　　　　 $\hat \theta_{w_t|c_j} \equiv P(w_t|c_j; \hat \theta) = \frac{1+\sum\limits_{x_i \in X}\delta_{ij}x_{it}}{|X| + \sum\limits_{s=1}^{|X|} \sum\limits_{x_i \in X} \delta_{ij} x_{is}}$

クラス確率パラメータは

　　　　　 $\hat \theta_{t_a} \equiv P(t_a|\hat \theta) = \frac{1+ \sum\limits_{i=1}^{|X|} \delta_{ia}}{M+|X|}$

サブトピック確率は

　　　　　 $\hat \theta_{c_j|t_a} \equiv P(c_j|t_a;\hat \theta) = \frac{1+\sum\limits_{i=1}^{|X|} \delta_{ij}\delta_{ta}}{\sum\limits_{j=1}^{N} q_{aj} + \sum\limits_{i=1}^{|X|} \delta_{ia}}$

分類時，unlabeled documentに対してクラスメンバーシップ確率を推定する必要がある
これはまず，最初にサブトピックメンバーシップを計算し，次にサブトピック全体で合計してクラス確率を計算することで得られる
サブトピックメンバーシップ確率は

　　　　　 $P(z_i = c_j | x_i ; \hat \theta) = \frac{\sum\limits_{a \in [M]} q_{aj} P(t_a | \hat \theta) P(c_j | t_a ; \hat \theta) \prod\limits_{w_t \in X} P(w_t|c_j ; \hat \theta)^{x_{it}}}{\sum\limits_{r \in [N]} \sum\limits_{b \in [M]} q_{br} P(t_a|\hat \theta) P(c_r|t_b; \hat \theta) \prod\limits_{w_t \in X} P(w_t|c_r; \hat \theta)^{x_{it}}}$

クラスメンバーシップ確率は

　　　　　 $P(y_i = t_a | x_i ; \hat \theta) = \sum\limits_{j \in [N ]} q_{aj} P(z_i = c_j | x_i ; \hat \theta)$

精度はナイーブベイズに比べて良くなるが，最適なEMの場合に比べて，クロスバリデーションするとサブトピックの数が減る傾向にある

5. Overcoming the Challenge of Local Maxima

局所最適の問題に対し，Deterministic Annealingという方法を使うと，精度改善に繋がる
力尽きたので今度読む

まとめ

ナイーブベイズってこういうものなのかということを理解するとともに，サブトピックの導入あたりが面白かった．Deterministic Annealingはちゃんと理解しておきたい．