Efficient Label Propagation - todo314 @ ウィキ

2017/04/02

Efficient Label Propagation

• Yasuhiro Fujiwara, Go Irie
• ICML 2014

概要

• 半教師有り学習法であるラベル伝播は大事だよ
• 実質的に逆行列の計算が必要
  • 各点に対して、最大のスコアを持つラベルを割り当てる
  • 点数n、ラベル数c
• 厳密手法: $$ O(n^3 + cn^2) $$時間
• 近似手法: べき情報でまとめて計算、ただし、ラベル割当が異なりうる
• 提案手法: 厳密のまま高速化
  • アイデアは、上界下界の保持によるラベルの枝刈り（いつもの感じ）
  • $$ O(cnt) $$時間（tは反復回数）

ラベル伝播

• 入力: 点$$ (x_i)_i $$、ラベル（一部の点のみ）$$ y(x_i) $$

1. 重み付きk近傍グラフを生成
   • 辺重み$$ W_{ij} $$は例えばGaussianカーネル
   • k近傍だけ辺を残す
2. ラベル割当
   • $$ \mathbf{Y} $$: $$n \times c$$行列の$$Y_{ij}=1 \iff $$ $$y(x_i) = l_j$$（これはgiven）
   • $$ \mathbf{F} $$: $$n \times c$$行列の割当スコア
   • $$ \mathbf{D} $$: 重み付き次数和の対角行列
   • $$ F(\mathbf{F}) = \frac{1}{2}\sum_{i,j} W_{ij}\| \frac{\mathbf{F}_i}{\sqrt{D_{ii}}} - \frac{\mathbf{F}_j}{\sqrt{D_{jj}}} \|^2 + \Bigl( \frac{1}{\alpha}-1 \Bigr)\sum_{i} \| \mathbf{F}_i - \mathbf{Y}_i \|^2 $$
   • 第一項：smoothness…隣り合ってたら近い
   • 第二項：fitness…与えられたのラベルに近い
   • $$ \mathbf{F}^* = (\mathbf{I}-\alpha \mathbf{S})^{-1} \mathbf{Y} $$
     • $$ \mathbf{S} = \mathbf{D}^{-1/2} \mathbf{W} \mathbf{D}^{-1/2} $$
   • 最終的に、$$ y(x_i) $$をFで最もスコアが高いラベルに設定する
   • $$ f^*(x_i \mid l_j) $$←スコアのnotation

LU分解

• $$ O(n^3 + cn^2) $$時間でやばお

power iteration

• $$ \mathbf{F}_{t+1} = \alpha \mathbf{S}\mathbf{F}_i + (1-\alpha)\mathbf{Y} $$
  • 早いけど、精度が(´・ω:;.:...

提案手法

• アイデア
  • $$ f^* $$の上限下限を持っておき、反復で改善していく
  • おもむろに、伝播スコア$$ p_t(x_i \mid l) $$を導入
• 伝播スコアによって、上限と下限をそれぞれ計算できる
• 色々な性質を証明：単調に改善する、極限では厳密解、定数時間で更新可能、…
• 計算時間 $$ O(cnt) $$
  • tは反復回数（実験的には小さい）

実験

• 提案手法がpower iterationより大体2倍速い設定
• power iterationは厳密に比べて精度が悪い
  • これは実際の効果（分類精度？）にも多少影響する

まとめ

• 機械学習に使われる手法の高速化もICMLで評価されるのだなぁ。

2017/04/13