木カーネル (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|)\).

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-07-30 (土) 09:29:38