木カーネル

木カーネル (tree kernel) †

木 \(T\) の全ての可能な部分木の列挙を考え，\(h_i(T)\) を \(i\)番目の部分木が木 \(T\) 中で生じる回数とする．二つの木 \(T_1\) と \(T_2\) についてカーネルは次式で定義： \[k(T_1,T_2)=\sum_i h_i(T_1)h_i(T_2)\] さらに， \(T_1\) と \(T_2\) の頂点集合 \(\mathcal{V}_1\) と \(\mathcal{V}_2\) について， \(S(v_1,v_2)\;v_1\in\mathcal{V}_1, v_2\in\mathcal{V}_2\) は頂点 \(v_1\) と \(v_2\) を根とする同型の部分木の数とすれば次式でも計算可能： \[k(T_1,T_2)=\sum_i h_i(T_1)h_i(T_2)=\ \sum_{v_1\in\mathcal{V}_1, v_2\in\mathcal{V}_2}\ S(v_1,v_2)\] 計算量は \(O(|\mathcal{V}_1||\mathcal{V}_2|)\)．

-- しましま

関連項目 †

• tree kernel
   
• カーネル
• 畳み込みカーネル
   
• 検索:木カーネル

リンク集 †

• Tree Kernels in SVM-light

関連文献 †

• 基本文献
  M.Collins and N.Duffy "Convolution kernels for natural language" NIPS14 (2002)
  GoogleScholarAll:Convolution kernels for natural language
• 申 吉浩 "木の半正定値カーネル ー フレームワークとサーベイ" 人工知能学会論文誌, vol.17, no.6, pp.459-468 (2009)
• 松本裕治 "自然言語処理におけるカーネル法の利用" IBIS2002, pp.19-24 (2002)
• 構造化データのためのカーネルのサーベイ KDD Explorations, vol.5, issue 1 (タイトルがなぜか"Kernel-based Learning in Multi-Relational Data Mining"になっている)
  T.Gärtner", "A Survey of Kernels for Structured Data", SIGKDD Explorations, vol.5, issue 1, pp.49-58 (2003)