SGT の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• SGT へ行く。

* spectral graph transducer (SGT) [#oa89175d]

//ここには %項目の説明を書いてください．よろしければ署名しておいてください．

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

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

> -- しましま

** 関連項目 [#bd85c149]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．

*** Freeware [#c3c1359d]

-[[spectral graph transducer]]
#br
-[[半教師あり学習]]
-[[トランスダクティブ学習]]
-[[グラフスペクトル]]
#br
-[[検索:SGT]]

** リンク集 [#a9dfa9c8]

//関連するWWW資源があればリンクしてください．

*** Freeware [#m37a362a]

-[[Spectral Graph Transducer>http://sgt.joachims.org/]]：プログラムの配布先

** 関連文献 [#q7ee9974]

//この%項目%に関連する書籍や論文を紹介してください．

-基本文献~
T.Joachims, "Transductive Learning via Spectral Graph Partitioning", ICML, pp.290-297 (2003)~
[[GoogleScholarAll:Transductive Learning via Spectral Graph Partitioning]]