Marginalized Kernels Between Labeled Graphs - todo314 @ ウィキ

Marginalized Kernels Between Labeled Graphs

• Hisashi Kashima, Koji Tsuda, Akihiro Inokuchi
• ICML 2003

概要

• 新しくグラフカーネルを作りました
• ランダムウォークで生成されるラベル列のカウントが特徴ベクトル
• 無限次元だけど、効率的に計算できます

Marginalized Kernel

• 本当に欲しいもの: $$ K({\bf x}, {\bf x}') = \sum_{{\bf h}}p({\bf x}|{\bf h}) p({\bf x}'|{\bf h}) p({\bf h}) $$
  • hという隠れ変数からx、x'が生成される過程
• 実際に取れるもの: $$ K({\bf x}, {\bf x}') = \sum_{{\bf h}}\sum_{{\bf h}'} K_z({\bf z}, {\bf z}') p({\bf h}|{\bf x}) p({\bf h}'|{\bf x}') $$
• 意味としては、xからhが出て来る事後確率、みたいな奴

Graph Kernel

• PageRank的なランダムウォークを考える
• 初期確率: $$ p_s(h) $$
• 遷移確率: $$ p_t(h_i | h_{i-1}) $$
• 停止確率: $$ p_q(h_{i-1}) $$
• 頂点・辺のラベル毎にカーネルがあるとした時、
• 同じ長さの2パス$$ z=(G,h), z'=(G',h') $$間のカーネル$$ K_z(z,z') $$は、
• 点-辺-点-…-点-辺-点 のカーネルの掛け算をとる
• 要は: $$ K(G,G') = \sum_{\ell \geq 1}\sum_{{\bf h}}\sum_{{\bf h}'} $$
• 計算は頑張ると出来る
  • 収束の条件とかもかなり調べている

実験

• データセット: 生物学っぽい奴
• 特徴が似ている既存の手法と比較
• 主張: 分類精度で圧勝ではないが、シンプルさ計算の効率さでこちらは良い

ICML グラフカーネル

2016/12/31