共訓練

共訓練 (co-training)†

半教師あり学習を実現する手法の一つ

事例の定義域は \(X\) は \(X_1\times X_2\) に分割できる．すなわち，一つの事例を二種類の属性ベクトルで表現できる．例えば，一つのWebページがテキストに基づく特徴\(X_1\)と，リンクに基づく特徴 \(X_2\) で記述されているなど．
\(X_1\) と \(X_2\) のどちらか一方だけでも分類には十分とする．
\(\mathcal{D}\) は \(X\) 上の分布．
\(\Pr{}_{\mathcal{D}}(x)\ne0\)なる事例 \(x\in X\) について，ラベル付け関数は無矛盾，すなわち，\(f(x\in X)=f_1(x_1\in X_1)=f_2(x_2\in X_2)\)．これが成立する仮定をcompatibleという．
ここで，\(x_1\in X_1\) と \(x_2\in X_2\) をそれぞれノード集合とし，\(\Pr{}_{\mathcal{D}}(x_1\times x_2)\ne0\) なら \(x_1\) と \(x_2\) の間に辺がある二部グラフを考える．
compatibleの仮定は，この二部グラフの連結成分中のラベルが同じであることになる．
少数のラベルあり事例と，多数のラベルなし事例が存在する状況を想定
ラベルなし事例が存在すると，その事例について \(\Pr{}_{\mathcal{D}}(x_1\times x_2)\ne0\) であることがわかり，二部グラフの辺を作れる．
二部グラフの連結成分中に一つでもラベルあり事例があれば，その連結成分のラベルはcompatible仮定から同じになるので，少数のラベルでも多数の事例がラベル付けできる．