木カーネルの変更点

追加された行はこの色です。
削除された行はこの色です。
木カーネルへ行く。
* 木カーネル (tree kernel) [#rf67875e]

//ここには %項目の説明を書いてください．よろしければ署名しておいてください．

木 \(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|)\)．

> -- しましま

**関連項目 [#b5df2bc1]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．

-[[tree kernel]]
#br
-[[カーネル]]
-[[畳み込みカーネル]]
#br
-[[検索:木カーネル]]

**リンク集 [#tc1e5a66]

//関連するWWW資源があればリンクしてください．
-[[Tree Kernels in SVM-light>http://dit.unitn.it/~moschitt/Tree-Kernel.htm]]

**関連文献 [#pf100dbe]

//この%項目%に関連する書籍や論文を紹介してください．

-基本文献~
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)>http://joi.jlc.jst.go.jp/JST.JSTAGE/tjsai/24.459?lang=ja]]
-松本裕治 "自然言語処理におけるカーネル法の利用" IBIS2002, pp.19-24 (2002)
-構造化データのためのカーネルのサーベイ [[KDD Explorations, vol.5, issue 1>http://www.acm.org/sigs/sigkdd/explorations/issue.php?volume=5&issue=1&year=2003&month=07]]
(タイトルがなぜか"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)
木カーネル の変更点
