* 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]]

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS