木カーネル (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|)\).
関連項目 †リンク集 †関連文献 †
|