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

A Taxonomy for Semi-Supervised Learning Methods
Seeger, M.

Ch 2(pp.15-31)もどちらかというとoverviewっぽい．半教師あり学習の分類について書かれている．相変わらず簡単なまとめメモ＋適当な意訳あり．あとはてダの数式が綺麗ではないので，少しがんばってみた．はてなブログの方が数式綺麗らしいので乗り換えようかなぁ…．

1. The Semi-Supervised Learning Problem

半教師あり学習には2つの基本的手法がある
unlabeled data $D_u$ を無視した教師あり分類問題

2. Paradigms for Semi-Supervised learning

半教師あり学習は教師あり学習のテクニックなので，当然生成モデル的アプローチと識別モデル的アプローチに分類できる
この節では統計学や機械学習でよく用いられるグラフィカルノーテーションを用いる．これはグラフィカルモデル(またはindependence diagrams)とも呼ばれる．
グラフィカルモデルは変数の確率分布からサンプリングされるメカニズムをシンプルに表現できる
- ノードは確率変数を表す
- ノード $i$ の親は有向リンク $j \rightarrow i$ をもつノード $j$
- ノードの集合をグルーピングする箱をplates（良い訳が浮かばないのでプレートとする）を利用する
- これは任意のプレートの親ノードからi.i.d.に繰り返しサンプリングされたグループであることを表す

The Generative Paradigm

クラス分布 $P({\bf x}|y)$ を $\{P({\bf x}|y, {\bf \theta }) \}$ を用いてモデル化
$P(y)$ は $\pi_y = P(y| {\bf \pi})$ , ${\bf \pi} = (\pi_y)_y$
この構造のモデルは完全な同時確率 $P({\bf x}, y)$ を $\pi_y P({\bf x} | y, {\bf \theta})$ によってモデリングするのでjoint density modelと呼ばれる
ベイズの定理より

　　　　　 $P(y|{\bf x, \hat \theta, \hat \pi}) = \frac{\hat \pi_y P({\bf x}|y,\hat \theta)}{\sum_{u$

生成モデルアプローチでは周辺確率 $P({\bf x})$ は次のように書ける．

　　　　　 $P({\bf x|\theta, \pi}) = \sum_{y=1}^M \pi_y P({\bf x}|y,{\bf \theta})$

もしlabeled dataとunlabeled dataが両方利用可能であれば， $D_l$ と $D_u$ の同時対数尤度は次のように書ける．

　　　　　 $\sum\limits_{i=1}^n \log \pi_{y_i} P({\bf x}_i | y_i, {\bf \theta}) + \sum\limits_{i=n+1}^{n+m} \log \sum\limits_{y=1}^{M} \pi_y P({\bf x}_i | y, {\bf \theta})$

- これは( $y$ を潜在変数として扱うと)欠損データがある場合の尤度最大化問題である
- で，これはEMアルゴリズムによって原理的にできる
これで半教師あり学習の良い解が得られそうな雰囲気があるが，生成モデルでは分類問題の良い解をなかなか得られない
生成アプローチでは $P({\bf x})$ を得るが，これは分類問題には不要で，限られたデータでは無駄になることがある
ここらへんの議論は後ほどやる

The Diagnostic Paradigm

識別モデル的アプローチでは $\{P(y|{\bf x, \theta }) \}$ を用いて条件付き確率分布 $P(y|\bf x)$ をモデル化
データに対する完全なサンプリングモデルのためにによってもモデル化する必要あり
- でも， $\bf \theta$ の更新や未知の点に対する $y$ の予測にのみ関心がある場合は必要ない
このモデルの下では $\bf \theta,\ \ \mu$ は事前独立，つまり $P({\bf \theta, \mu}) = P({\bf \theta})P({\bf \mu})$ である

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

　　　　　 $P(D_l, D_u| {\bf \theta, \mu}) = P(Y_l| {\bf X_l, \theta}) P({\bf X_l} , D_u | {\bf \mu})$

さらに $P({\bf \theta}|D_l, {\bf \mu}) = P({\bf \theta}|D_l)$ とする．これはunlabeled data $D_u$ に対する知識も ${\bf \mu}$ に対する知識もlabeled sampleの事後信念 $P({\bf \theta}|D_l)$ を変えないことを意味する
そのため，識別モデルの標準的なデータ生成モデルにおいては，unlabeled data $D_u$ はベイズ推論のために使うことができず，inputの確率分布 $P(\bf x)$ をモデル化する必要はない
識別モデルの中でunlabeled dataをうまく利用するためには上記のデータ生成モデルを後の節で議論するように改善する必要がある

Regularization Depending on the Input Distribution

一般に限られたlabeld dataを使うと過学習するので正則化する
識別モデルアプローチだと単純にやるとunlabeled data $D_u$ はうまく利用できない．なんでかというと， $\bf \theta$ と $\bf \mu$ が事前独立を仮定してたからで，これも入力分布の独立性によるある種の正則化である

$\bf \theta$ と $\bf \mu$ の事前独立を緩和してみよう．つまり，

　　　　　 $P({\bf \theta, \mu}) = P({\bf \theta}|{\bf \mu})P({\bf \mu}),\ \ \ P({\bf \theta}) = \int P({\bf \theta}|{\bf \mu})P({\bf \mu})d{\bf \mu}$

この場合， $\bf \mu$ についての情報が $\bf \theta$ に影響を与えるので，unlabeled dataは $\bf \theta$ の事後信念を変化させる
識別モデル的アプローチでunlabeled dataを有効活用するには条件付き確率を表す潜在関数と入力確率分布の間に従属関係があることを仮定するしかない
この関係の下では， $P({\bf \theta}) = \int P({\bf \theta}|{\bf \mu})P({\bf \mu})d{\bf \mu}$ は

　　　　　 $P({\bf \theta}|D_u) = \int P({\bf \theta}|{\bf \mu})P({\bf \mu}|D_u)d{\bf \mu}$

に変わる．こうすることでエントロピーが小さくなる

しかし，謎がある．ここまでしたら，これって識別モデルなのか？
識別モデルは $P(\bf x)$ を推定する必要がないから節約的なモデルであったはずなのに．なんかこれって生成モデルっぽくない？
なんかこのへんの違いが曖昧なので次節でちゃんと説明する．

The Borderline between the Paradigms

教師あり学習と教師なし学習の境界はかなりはっきりしているのに対し，生成モデルと識別モデルの間の違いはかなり曖昧だ．半教師あり学習の文脈では特に曖昧
いま，やりたいことは $P(y|\bf x)$ を推定すること
生成モデルアプローチでは同時確率をモデル化し，真の同時確率分布の性質を捉えることによってこのモデルをデータにフィットさせ，目的を達成する
- $P(\bf x)$ の推定値は常に同時確率の周辺化によって得られる
識別モデルアプローチでは条件付き確率のみをモデル化したい
- $P(\bf x)$ は必要ない．んだけど，半教師あり学習においては $D_u$ から何か情報を得るために $P(\bf x)$ をモデル化しなきゃいけない
では，すべての半教師あり学習は生成モデル？
我々はそうではないと考えている． $P(\bf x)$ が行う役割が違う

半教師あり学習ではたしかにをモデル化する
- だけど，生成モデルアプローチでは各クラスの条件付き分布 $P({\bf x}|y)$ を明示的にモデル化し， $P(\bf x)$ はそれらのmixtureに過ぎない
- これらの推定値と $P(y)$ からベイズの定理より $P(y|{\bf x})$ を得る
- 予測値の性質は完全にクラス条件付きモデルに依存する．たとえば同じ共分散行列をもった正規分布でモデル化すると推定値は線形関数になる
- つまり，生成モデルアプローチでは $P({\bf x}|y)$ を特定化し，それによって， $P(y|{\bf x})$ や $P({\bf x})$ の形の情報を与えている
- $P(y|{\bf x})$ や $P({\bf x})$ に固有の性質を与えるには $P({\bf x}|y)$ の候補を見つけるしかない
識別モデルアプローチではを直接モデル化し，一般的にのモデリングはかなり自由度がある
- 半教師あり学習においては $P({\bf x})$ からの情報を用いて $P(y|{\bf x})$ を正則化するが，明示的にクラス条件付き確率を特定化しなくてよい
- この定義は半教師あり学習としては役立つけど，生成モデルというには制約が強すぎる

半教師あり学習が実用上成功したのはunlabeled data，つまりに関する知識が教師あり学習にとって有用だったからであるが，必ずしも良いの推定に繋がる同じ情報が必要なわけではない
- たとえば，SVMやロジスティック回帰のような純粋な識別モデル的アプローチに対して半教師あり学習を導入するならば，cluster assumptionのような $P({\bf x})$ のある性質を破るような $P(y|{\bf x})$ の正則化を用いることで最終的な $P(y|{\bf x})$ への $P({\bf x})$ の影響は必要最低限なレベルであるように制約する

3.Examples

以下は途中まで書いていたのが消えて心が折れたので簡潔に．

Generative Techniques

EMアルゴリズムを使う方法
Nigam et al. (2000)はテキスト分類にEMアルゴリズムを使った
との対数尤度巻数の重み付けは上の方の式にもあるが，現実にはunlabeled dataの方がべらぼーに多いので，別の重み付けを考えた
- 再重み付けパラメータはクロスバリデーションで決める
Zhang and Oles (2000)
- フィッシャー情報量を使う

Diagnostic Techniques

Tong and Koller (2000)
- restricted Bayes optimal classification (RBOC)
Anderson (1979)
- unlabeled dataを用いたロジスティック回帰

Input-Dependent Regularization

識別モデル的アプローチにunlabeled dataを使うときはパラメータの依存関係に正則化をする

The Cluster Assumption
- ラベル伝搬法
The Fisher Kernel
- kernel based SVMにunlabeled dataを追加するためにフィッシャーカーネルが提案(Jaakkola and Haussler, 1999)
- 尤度を最大化するように生成モデル $P({\bf x}|{\bf \mu})$ をフィットさせる
- hidden Markov modelを用いたりガウス過程を用いたり
Co-Training
- Blum and Mitchell (1998)に提案された
- アイデアは分類のためにオブジェクトの別の面を利用する
- 例として，web pageはpage上のテキストによって表現できるが，pageを参照しているハイパーリンクによって表現することもできる
- それぞれの観点で分類器を学習させるとき， $D_u$ は真のラベルがないが，これはどの観点からみても同じなので，Co-Trainingは条件付き事前確率を用いたベイズ推定の特別なケースと考えることができる

まとめ

生成モデル的アプローチの半教師あり学習は理屈として理解できていたが，識別モデル的アプローチにおける半教師あり学習のイメージができたのは良かった．細かな話は以降のChapterを読むか，個別論文に当たる必要があると思うけど．しかし，なぜローカルに保存していなかったのかという点が悔やまれる…．