木 \(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|)\)．
-- しましま
関連項目†
リンク集†
関連文献†
- 基本文献
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)
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
