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

Chapelle et al. (2006)を買ったので読んでみてる．Zhu and Goldberg (2009)の"Introduction to Semi-Supervised Learning"も買った．後者はかなり薄いかつ簡単そうなので，概要を掴むには良さそう．まだ特に半教師ありを何かに適用するつもりではないのだけれど，勉強として1章(pp.1-12)を簡単に読んだのでまとめる．

1. Supervised, Unsupervised, and Semi-Supervised Learning

Supervised and Unsupervised Learning

伝統的に教師あり学習と教師なし学習があるよ
教師なし学習は $X = (x_1,\ldots,x_n)$ を $n$ 個の点の集合として各点は共通の分布 $X$ からi.i.d.にドローされると仮定．
$(n \times d)$ 行列 ${\bf X} = (x_i^T)_{i \in [n] }^T$ を定義．
教師なし学習の目的はデータ $\bf X$ の興味深い構造を見つけること

教師あり学習の目的は訓練集合( $(x_i, y_i)$ のペア)が与えられたときに $x$ から $y$ への写像を見つけること
$y_i$ は $x_i$ のラベルと呼ばれる
一般に $X \times Y$ の分布から $(x_i, y_i)$ はi.i.d.に得られたと考える
たとえば $y$ が実数であれば（スカラーorベクトル，もっと言えば連続量であれば）このタスクは回帰と呼ばれる
この本のほとんどは分類に焦点を当てている(Chapter 23は回帰もあるよ)

教師ありには2つのアプローチがある
生成(generative)モデル的アプローチと識別(discriminative)モデル的アプローチ
生成モデルは教師なし学習によってクラスの条件付き確率密度 $p(x|y)$ をモデル化する．
予測確率はベイズの定理によって得られる

　　　　　　 $p(y|x) = \frac{p(x|y) p(y)}{\int_y p(x|y) p(y) dy}$

識別モデルは $x_i$ がどのように生成されたのかは気にしないで $p(y|x)$ を推定するのに集中
識別モデルの中にはSVMのように $p(y|x)$ が0.5以上かどうかのみモデル化するものもある（ここでは識別関数もこっちに含んでいるようだ）
識別モデルは教師あり学習の目的に対して直接的にアプローチしているので，実用上は効率的な傾向

Semi-Supervised Learning(SSL)

半教師あり学習は教師なし学習と教師あり学習の間の子
unlabeled dataを追加して，教師あり学習の精度を上げるよ
データ $X$ はラベル $Y_l$ がある $X_l$ とラベルのない $X_u$ の2つに分けられる
これは半教師あり学習の設定として標準的で本書も基本はこの流れ

SSLに関連する問題としてVapnikが数十年前に提案したtransductive learningもある
これはlabeled training setとunlabeled test setが与えられて，テストデータに対してのみの予測をする問題

A Brief History of Semi-Supervised Learning

unlabeled dataを使って予測精度を上げようという考えは古く，self trainingとして知られている
かなり古いモノではScudder (1965), Fralick (1967), Agrawala (1970)

transductive inferenceが提案されたのがVapnik and Chervonenkis (1974)やVapnik and Sterin (1977)あたり
他にもHartley and Rao (1968)はモデルの尤度を最大化するためにテストデータのラベルに組合せ最適化を適用

SSLは1970s
labeled dataとunlabeled dataによるモデルの尤度はEMアルゴリズムを使う(Dempster et al., 1977)
混合正規分布の代わりにlabeled dataとunlabeled dataによって推定された混合多項分布(Cooper and Freeman, 1970)
Shahshahani and Landgrebe (1994)やMiller and Uyar (1997)
probably approximtely correct (PAC) framework (Valiant, 1984)が2つの混合正規分布の半教師あり学習として導出(Ratsaby and Venkatesh, 1995)
ここらへんで理論的な解析がなされる

SSLに対する関心は1990sから大きくなる．それはNLPでの適用やテキスト分類のため．
たとえばYarowsky (1995), Nigam et al. (1998), Blum and Mitchell (1998), Collins and Singer (1999), Joachims (1999)
記憶ではKerz et al. (1992)がはじめて"semi-supervised"って用語を使った気がする．たぶん．

2. When Can Semi-Supervised Learning Work?

自然な疑問として「半教師ありって意味あるの？」もっと言えば「教師あり学習と比べてunlabeled dataを加えるとどんだけ良くなるの？」
この本の分厚さを見てくれ．原則的に答えは「Yes」だ

The Semi-Supervised Smoothness Assumption

教師あり学習のsmoothness assumptionは非常にpopularな仮定の一つ
- 2つの点 $x_1, x_2$ が近い場合， $y_1, y_2$ は同様の出力になるべきという仮定
半教師ありにおいてはsmoothness assumptionの一般化が有用
- 高次元にある2つの点 $x_1, x_2$ が近い場合， $y_1, y_2$ は同様の出力になるべきという仮定
このsemi-supervised smoothness assumptionは回帰にも分類にも適用できる

The Cluster Assumption

各クラスの点がクラスターを形成する傾向にあるならば，unlabeled dataは各クラスターの境界をより正確に見つけられるかもしれん
これをcluster assumptionと呼ぶ
- もし各点が同じクラスターにあるならば，それらは同じクラスに属していそうだ
cluster assumptionは各クラスが単一のコンパクトなクラスターをつくっていると言ってるわけではないよ
このcluster assumptionは上述のsemi-supervised smoothness assumptionと考えることもできる
low density separation
- 決定境界は低次元領域にあるべきだ

The Manifold Assumption

関連してManifold assumptionというのもあるよ
- (高次元)データは（大雑把には）低次元多様体(manifold)上にある
これはどのように役に立つのか？
多くの統計的方法や学習アルゴリズムのよく知られた問題はいわゆる次元の呪いだ
この問題は（入力空間内における密度推定をベースにした）生成的アプローチに直接影響がある
しかし，もしデータが低次元多様体上にあるのであれば，学習アルゴリズムは次元の呪いを避けてその次元上で考えることができるので嬉しい

Transduction

Vapnikの原則だけ書いときますね
- ある問題を解こうとする際に，中間的なステップとしてより難しい問題を解くべきではない

3. Classes of Algorithms and Organization of This Book

この本はいくつかのパートに分かれている

Generative Models

Part 1(Ch 2-5)は生成モデル
この設定では $p(x)$ の任意の追加的な情報が役立つ
たとえば $p(x|y)$ がGaussianだと仮定して，各クラスに一致するGaussianのパラメータを求めるのにEMアルゴリズムを使う
通常のEMとの違いは任意のlabeled dataに関連する隠れ変数があること
生成的アプローチの強みは問題やデータの構造に関する知識が自然にモデルに組み込めること

Low-Density Separation

Part 2(Ch 6-10)はunlabeled dataからの決定境界を決めるためのlow-density separation assumptionの適用
transductive SVMとか
（読んでないのでちょっとまだイメージ湧いてない）

Graph-Based Methods

Part 3(Ch 11-14)はGraph-Based Methods
データをグラフのノードとして表し，リンクがpairwiseなノード間の距離を表す
weight matrixを考えて，graph Laplacianをごちゃごちゃするようだ
（面白そう）

Change of Representation

Part 4(Ch 15-17)は本質的にはSSLではないけど，2-step learningに変わるアルゴリズムについて
すべてのデータ(labeled, unlabeled data，でもラベルは使わない)で教師なし学習のステップを実行してみる．これは表現を変えると新しい計量や新しいカーネルを作っていると解釈できる？
unlabeled dataを無視して，新しい距離や表現，カーネルを用いた教師有り学習を実行してみる
このパートはパート3とも関連あるよ

Semi-Supervised Learning in Practice

Part 5(Ch 18-21)は適用例など
labeled dataに比べてunlabeled dataが大量にあるときはSSLは結構役立つ
各データの入手コストは低いがラベル付けのコストが高いことはよくある
いろいろ例がありそう．読んでないからしらんけど．

Outlook

Part 6はまとめとかoverviewとか．
Ch 26では対話形式でのSSLとtransductionの違いに対する議論があって面白そう

感想とか

半教師あり学習は言葉は聞いたことあったのだけど，具体的にどういうイメージでなぜ良くなるのかということが理解できたのは昨年11月末に参加した情報数物研究会だった気がする．渡邉陽太郎さんの発表だったのだけど，話の途中で一瞬半教師あり学習の話も触れられていて，発表後の質問で「半教師ありってなんでうまくいくんですか？」という素人質問を私がしたら，田中先生がわかりやすいイメージで説明してくださってなるほどーと思った．

いや，ま，現実逃避ですけどね．さーて，仕事仕事．（この本の読み会したい）