spectral graph transducer (SGT)

半教師あり学習の手法の提案.グラフを使った多様体仮定に基づく手法.

  • 各事例を頂点とする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^-\) とへの分割をハードではなく,実数の所属度に緩和してグラフスペクトルで近似解を求める.

-- しましま

関連項目

Freeware

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:23 (2492d)