Marginalized Kernels Between Labeled Graphs
要約
# Abstract
- グラフのラベル間の新しいカーネル関数を提案
- ランダムウォークによって生成されるラベルパスのカウントを特徴ベクトルとして定義
- 離散時間線形システムの定常状態を求めることで効率的に計算可能
- 無限次元の特徴空間に基づくため、動的計画法に基づく他の文字列/ツリーカーネルとは本質的に異なる
- 化学化合物の分類で有望な実験結果を示す
# 1. Introduction
- 機械学習の多くは実数値ベクトルの分類・回帰を扱うが、現実のデータの多くはグラフとして表現される
- 生物学的配列、自然言語テキスト、XML等の半構造化データ
- 特に製薬分野では、化学化合物をラベル付きグラフとして表現
- カーネル法は高性能だが、グラフ間のカーネル関数の定義は容易ではない
- 既存のグラフカーネルの多くは以下のアイデアに基づく:
- オブジェクトを部分構造(部分配列、部分木、部分グラフ)に分解
- 部分構造のカウントで特徴ベクトルを構成
- 特徴ベクトルの次元が非常に高いため、動的計画法等で効率的に計算
# 2. Marginalized Kernels
- 構造化データのカーネル構築の一般的な方法:
- 隠れ変数を仮定し、可視変数と隠れ変数の確率分布を利用
- K(x,x') = Σh,h' Kz(z,z')p(h|x)p(h'|x') という形式
- z=[x,h]は可視変数と隠れ変数の組
- Kzは結合カーネル
- p(h|x)は情報的な特徴を抽出する特徴抽出器として解釈可能
# 3. Graph Kernel
- ランダムウォークに基づくグラフカーネルの定義:
- 隠れ変数h=(h1,...,hl)はグラフ上のランダムウォークによって生成される頂点インデックス列
- 初期確率ps(h)、遷移確率pt(h|h')、終了確率pq(h)で定義
- 結合カーネルKzは、ラベルカーネルの積として定義
- 効率的な計算:
- 線形同時方程式を解くことに帰着
- 係数行列は疎行列のため、効率的な数値計算アルゴリズムが適用可能
- 収束条件:
- 終了確率が一定の場合、ラベルカーネルが1未満なら収束が保証される
# 4. Experiments
- 化学化合物の性質予測に適用:
- PTCデータセット: 417化合物の発がん性予測
- Mutagデータセット: 188化合物の変異原性予測
- パターン発見(PD)法との比較:
- パフォーマンスは同程度
- 本手法の利点:
- 概念的にシンプル
- 計算手順がシンプル
- すべての可能なラベルパスを考慮
# 5. Conclusion
- 新しいグラフカーネルを提案:
- Marginalized kernelの枠組みで定義
- ランダムウォークを使用
- 線形方程式を解くことで効率的に計算可能
- 一般的な構造に適用可能:
- 配列、木、DAG等
- DNA/RNA配列、文書、タンパク質構造等への応用が期待される
評価
# 新規性
- グラフ間のカーネル関数を、グラフ上のランダムウォークによって生成されるラベルパスの数を特徴量とする新しいアプローチで定義
- 無限次元の特徴空間を扱えるようにした点が大きな新規性
- 従来の動的計画法ベースの手法とは異なり、離散時間線形システムの定常状態を求める問題として定式化
# 言及されている全ての関連研究との相違点
- Haussler (1999)の構造データ向けカーネルの基礎研究を拡張
- Watkins (2000)らの配列カーネルとは異なり、無限次元特徴空間を扱える
- Collins & Duffy (2001)らの木構造カーネルとは異なり、グラフ全般に適用可能
- Gärtner (2002)のグラフカーネルとは異なり、パス全体のラベル情報を利用
- Kramer & De Raedt (2001)のパターン発見手法とは異なり、明示的な特徴抽出が不要
# 有効性
- 化学化合物の性質予測タスクで既存手法と同等以上の性能を実証
- PTCデータセット(417化合物)での発がん性予測で平均60-65%の精度
- Mutagデータセット(188化合物)での変異原性予測で80-85%の高精度
- パラメータ感度も検証されており、γ=0.3-0.7の広い範囲で安定した性能
# 信頼性
- 理論的な収束条件が数学的に証明されている
- 実験設定が詳細に記述され、再現可能性が高い
- 複数のベンチマークデータセットで評価を実施
- パターン発見手法との公平な比較実験を行っている
- 計算効率についても疎行列を利用した実装方法を提示
和訳
![]()
1 / 1
100%
付箋を貼る場所をクリックしてください
