半教師あり学習の手法の提案.グラフを使った多様体仮定に基づく手法.
- 各事例を頂点とするk近傍グラフを作る.\(x_i\) からのそのk近傍中の点 \(x_j\) への類似度 \(w_{ij}\) が辺の重み.ただし,k近傍内で総和が 1 になるように正規化.
\[A_{ij}=w_{ij}/\sum_{m\in kNN(x_i)}w_{im}\]
- ここで,このグラフを正例を含む \(G^+\) と,負例を含む \(G^-\) に分割する.
- ラベルなし事例の分け方は任意なので,いろいろな分割がある.
そこで,グラフの辺のcut (切断される辺の重みの総和) を最小化することを考える.
さらに,\(G^+\) と \(G^-\) の大きさが揃うようにする.
\[\min_{G^+,G^-} \mathrm{cut}(G^+,G^-) / |G^+||G^-|\]
- ラベルあり事例の影響を反映させるために,ラベルあり事例の誤分類の罰則項を加える
- あとは,\(G^+\) と \(G^-\) とへの分割をハードではなく,実数の所属度に緩和してグラフスペクトルで近似解を求める.
-- しましま
関連項目†
リンク集†
関連文献†