#7 Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions

Zhu, X., Ghahramani, Z., & Lafferty, J. (2003a).
ICML-03, 20th International Conference on Machine Learning.

The bulk of the harmonic functions section of the tutorial is devoted to this paper. It directly addresses many aspects of the harmonic function approach to learning. Given a graph on labeled and unlabeled instances, Zhu et al. introduce the Gaussian field formulation for labeling functions on the graph. They also demonstrate connections to random walks, normalized cuts, and graph kernels. Finally they suggest algorithms for discovering the energy-minimizing (harmonic) function f, including the closed form solution suggested by the connection to random walks and electric networks. At the end of the work, they also suggest methods for learning similarity parameters from data.

Graph-based SSL - SSL Tutorial: ACL 2008

またもやグラフベースのSSLです。Harmonic Functionsが大体の主役になってくる。main contributionは色々あるんだけど

  • ランダムウォーク、electric networks、spectal graph theoryなどとの関連性を見い出した
  • クラスのpriorを取り入れられるようにした*1
  • 教師あり学習も中で使って、半教師あり学習をしている(あとで説明)
  • hyper parameterをエントロピー最小化によって求める手法をproposeした

などなどがあるみたい。最初の、他の手法との関連性のところは他の手法の論文を読んでないのでかなり割愛気味な感じで。

Basic Framework

ここでもまず損失関数について考えられてます。edgeの重みを付けた二乗和誤差最小化を考える。あんまり誤差が大きすぎるところは小さくしようということで負の指数を取って、正規化定数で割る(これがGaussian fieldというものだそうだ)。で、このGaussian fieldの条件付き期待値を取る。この条件付き期待値を最小にする関数のことをharmonic関数と呼ぶ。この関数には重要な性質があって、ラベルなしデータのfの値はそのデータの周りのデータの値の平均になる、というものがある(これは自明...なのか?)。ラベルなしデータについてのfを得るためのmatrixのnotationでharmonic関数を計算してあげるとclosed form solutionが出てくる((5)式)。

Interporating Class Prior Knowledge

ベイズの流れを期待したけど、まだそこまでは至ってないっぽい感じ。重み行列Wの問題点を指摘していて、どういう重み(というか距離尺度)を採用するかによってえらく精度が違ってきてしまうことを上げている。だから、その重みWを「そのまま」使ってしまうのはまずいんでないかい?と問題提起している。「そのまま使うのがまずいなら事前の知識を入れてあげるのはどうしょう?」というのがここでの提案。まず、(ラベル付きデータとかを使って)、ラベル1の割合qとラベル0の割合1 - qというのを仮定する(事前知識的)。この事前知識と基準化したf_u(i)をかけたものを考えるんだが、この値がラベル1とラベル0のどちらが大きいかでf_u(i)の割り当てを変えよう、ということである(class mass normalization、CMNと書いてある)。

つまり、前は1/2と「閾値」で決めてた(実験ではこれでやって比較している)が、事前知識も取り込んでやってあげようという発想である。

Interporating External Classifiers

ここではノードiに対して"dongle"なノードを付け加えてやることを考える。加えられたノードは(ラベル付きデータのみから学習した)学習器によってノードiへのラベルが値として付けられる。で、(ここでは説明を飛ばした)ランダムウォークのモデルについて考える。ノードiと"dongle"なノードの遷移確率を\eta、iから他に行く確率からその分の確率を割り引いておく。こうしてまたランダムウォークのようにしてあげると、(10)式のようにfを出すことができる。

Learning the Weight Matrix W

ウエイトの付け方のパラメータをどうやって決めようか、という話。最尤法的な感じでパラメータを推定できればいいんだけど、ここでは生成モデルのようなものを考えているわけではないので、最尤法は使えない。この論文では代わりに平均エントロピーを最小にするようなパラメータはどうだろうか、と提案している。エントロピーが小さいってことはf(i)が1か0にかなり近いってことを表わしていて、これはconfidentなラベルになるようなパラメータになっている、ということで平均エントロピー最小化について考えるのは妥当じゃないか、という説明がしてある。

ただ、(今パラメータはスケーリングを表わすようなものについて考えているが)パラメータを0に近づけていくと平均エントロピーが0に行ってしまうので、これでは意味がなくなってしまうという問題がある。

これを避けるために推移確率のスムージングを考えたいということでPage Rankの話が出てくるが、この辺はよく分かっていないorz。あとで勉強しよう。

*1:ベイズ、とまではいってない