An Application of Boosting to Graph Classification - todo314 @ ウィキ

An Application of Boosting to Graph Classification

• Taku Kudo, Eisaku Maeda, Yuji Matsumoto
• NIPS 2004

概要

• グラフ分類にBoostingを応用する（最初期の論文？）

提案手法

概要

• ラベル付きグラフがL個あります
• 決定株$$ h_{\langle t,y \rangle}(\mathbf{x}) $$
  • xについてある部分グラフyを含んでいたらyを返す
• ものすごく弱いので、Boosting(特にAdaBoost)を適用
  • 決定株をK個用意する
  • $$ \mathrm{gain}(\langle t,y \rangle) = \sum_{1 \leq i \leq L} y_i d_i h_{\langle t,y \rangle}(\mathbf{x}) $$
  • gainを上げる<t,y>を選んでいきながらdを更新
  • $$\mathbf{d}$$はどの程度破ったかに応じて決める感じ（MWアルゴリズムで説明できる）

効率的計算

• 今やりたい事：<x_i,y_i,d_i>が与えられた元でgainを最大化する<t,y>が欲しい

1. 部分グラフの列挙
   • branch-and-bound
2. gainの上限
   • 探索空間の枝刈りに使う

SVMとの関係

• AdaBoost: 大体線形計画、marginも$$\ell_1$$-norm
• SVM: 二次計画、marginも$$\ell_2$$-norm
• 他にも色々書いているけど省略

実験

• F値を比較
• 実際にどういう特徴が良かったかを出してる

まとめ

• 普通にこういうので良いのかな？
• 既存の機械学習の枠組みを適用するときの挑戦的部分がわかってきた気がする：
  • どうやって特徴をとってくるか、を何らかの基準で測りたい
  • 部分グラフ全列挙は大変なので、マイニング技法＋枝刈り（上限とか）を入れる
  • ナイスなのがとってこれました！

Boosting NIPS グラフ分類 特徴選択

2017/06/19