Introduction to Semi-Supervised Learning #5

Introduction to Semi-Supervised Learning (Synthesis Lectures on Artificial Intelligence and Machine Learning)

1. Introduction to Statistical Machine Learning

2. Overview of Semi-Supervised Learning

3. Mixture Models and EM

4. Co-Training

5. Graph-Based Semi-Supervised Learning

5.1 Unlabeled data as stepping stones

• グラフに基づく半教師あり学習の直感的説明
  • 同じ単語を含む文書を線（エッジ）で結ぶ
  • ラベルあり文書のラベルをエッジに沿って伝搬

5.2 The graph

• 訓練事例に対してグラフを構築
  • ノードが事例（ラベルあり，ラベルなし）
  • エッジの重みw_ijは事例x_iとx_j間の類似度
  • w_ijが大→同じラベル（y_i = y_j）

• エッジの重みの定義が大事
  • 完全連結グラフ（fully connected）
    • すべてのノード間に重みを定義
    • w_ij = exp(- ||x_i - x_j||^2 / 2σ^2)
    • Gausiian kernel，もしくは，Radial Basis Function (RBF) kernelと呼ばれる
  • k近傍グラフ（kNN）
    • 距離が近いk個のノードに対してだけ重みを定義
    • 対称ではない
    • 経験的にはkの値が小さい方がよい
  • ε近傍グラフ（εNN）
    • 距離がε以下のノードに対してだけ重みを定義

5.3 Mincut

• source: positive label instances
• sink: negative label instances
• グラフ上におけるsourceからsinkへの流れをカットするエッジ集合にうち最小のものを見つける。

• カット：グラフを二つの部分に分けること。
• カットサイズ：カットしたエッジの重みの総和

• source側の部分グラフのノードにpositiveラベル，sink側の部分グラフのノードにnegativeラベルを付与。

• 正則化損失最小化問題
  • ∞\sigma(y_i - f(x_i))^2 + \sigma w_ij (f(x_i) - f(x_j))^2
  • 第1項がラベルありデータに対する正則化項
  • 第2項がラベルなしデータに対する正則化項

5.4 Harmonic function

• ラベルありデータに対しては，

f(x_i) = y_i
つまり，与えられたラベルと同じ値をとる。

• ラベルなしデータに対しては，

f(x_j) = \sigma w_jk(f(_k)) / \sigma w_jk
つまり，自分の周りのノードのラベルの重み付き平均をとる。

• 反復手続きによってf(x_j)を計算できる。
• 行列演算で解くこともできる。

5.5 Manifold Regularization

• Mincutとharmonic functionは
  • トランスダクティブな学習アルゴリズム
  • ラベルに誤りがあった場合にうまくいかない

• Manifold regularization
  • harmonic function自体の複雑さを正則化項に加える。
  • ラベルありデータに対してもラベルなしデータと同じように損失関数を計算する。

5.6 The Assumption of graph-based methods

• リンクの強さ（エッジの重み）とラベルがスムースであることが前提
• スムースさはspectral graph theoryで説明できる
• グラフの構造とエッジの重みがとても重要