プレゼンの資料がここに置いてあった。
SSL(Semi-Supervised Learning)でグラフ理論を使ったものには
- Mincut
- Discrete Markov Random Fields and Harmonic Functions
- Mainfold Regularization
- Graph Kernels from the Spectum of Laplacian
などなどがある(そして、どれもまだよく知らない!!)が、そのMincutの最初のやつっぽい。MincutでSSLをやろうという動機付けとしては
- お互い似ていれば高い重み付けがされてるだろうし、お互い似ていなければその重みは小さいだろう
- 似ている2つのexamplesは最小カットを構築すれば、同じ部分集合の枝に配置されるだろう
というようなもの。その場合の重み、いわゆる距離尺度としてどのようなものを使うかは問題になるので、auxiliary learning algorithmのようなものを使ってどういうのがよさそうか選択するとよいんじゃないんでしょうか、とある(auxiliary learning algorithmは知らないので、あとで調べよう)。最小カットをなんで使うかの直感的な説明はこんな感じだが、この論文は最小カットを使った場合に言える理論的な性質をいくつか証明している。
Motivation #1: minimizing LOOCV error
LOOCVはleave-one-out cross-validationのこと。ここでは2つ最小カットを使う理論的根拠*1を書いていて
- ある学習アルゴリズムAがあって、最小カットのアルゴリズムによりedgeの重みを定義することができる。そして、Aを使うとラベルあり&ラベルなしデータ全体に対してleave-one-out cross-validation誤差最小のものを達成できる
- 同じような感じで、ラベルなしデータをheld-outした場合のデータに対してleave-one-out cross-validation誤差を0にできる
というもの。学習アルゴリズムAがどういうものかは行ってないけど、そういうのを満たすようなものがあると言っている。
Motivation #2 a Generative Model
最小カットやその拡張はMarkov Random Field(これもまたよく知らないorz)にmotivateされたおのが多い、ということだが、このモデルは物理システムやピクセルイメージ(?)に対しては意味を成す*2が、例からの学習にはそういうのは向かない、らしい。Markov Random Fieldが分からないので、なんとも言えない。
なので、やりたいことに向いてるような生成モデルを考えようぜ、ということでそういうモデルが提案されている(ここの終わり3枚くらいのところ)。Rを領域として、-interiorと
-tendrilsというものに分ける。これはRの境界から
遠いか近いかでRを分けたようなもの。で、Rは以下の条件を満たすときに(
,
)であるという(
-tendrilsのほうは
fraction of its volumeというのの意味がよく取れない)。その条件は
-interiorで(グラフが)連結されていて、空でないということである。
で、そんな(,
)なk個の領域の和集合を考える。データがこの領域から一様に生成されるとすると、分類の精度というのは1 - O(
)で書けるというのが証明されている(ラベルありデータとラベルなしデータはこれくらい必要だよ、というのも書いてある)。
Section 5以降の実験はこのgenerative modelを使ってやってある。うーん、グラフがそもそもちゃんと連結にならない例があったりするように思うんだけど、どうなんだろうか。どっか読み落としてる?
参考
Blum, A., & Chawla, S. (2001).
Proc. 18th International Conf. on Machine Learning.
The original "semi-supervised learning with mincuts" paper. Blum and Chawla describe an algorithm analogous to "transductive nearest neighbor". Given annotated positive and negative instances with a graph whose edges represent similarity, the algorithm suggests computing the minimum cut between positive and negative instances. Blum and Chawla motivate this algorithm under a particular generative assumption, where instances are generated in particular well-behaved regions, and all the instances in a particular region have the same label. They demonstrate results on several of the UCI datasets.
Graph-based SSL - SSL Tutorial: ACL 2008
