構造データに対するカーネル関数

machine-learning

構造データ (グラフ) に対するカーネル関数 (類似度関数) についてのめも

ひとつの要素

ラベルが一致していたら 1、違ったら 0。

\begin{aligned}
K_\textrm{Symbol}(\sigma, \sigma') =
\left\{ \begin{array}{cc}
1 & \sigma = \sigma' \\
0 & otherwise
\end{array} \right.
\end{aligned}

長さ N の配列

ラベルがすべて一致していたら 1、ひとつでも不一致だったら 0。

K_\textrm{String}(s, s') = \prod_{i=1}^{N} K_\textrm{Symbol}(s_{i}, s'_{i})

畳み込みカーネル

すべての部分構造を列挙して比較する。

K_\textrm{Conv}(x,x') = \sum_{s \in S(x)} \sum_{s' \in S(x')} K_\textrm{String}(s,s')

一致する部分構造の数を数え上げている。

畳み込みカーネル (重み付き)

畳み込みカーネルに重みをつけた。

K(x, x') = \sum_{s \in S(x)} \sum_{s' \in S(x')} f(s \mid x) f(x' \mid s') K_\textrm{String}(s,s')

グラフ上のランダムウォークによって計算するのが一般的。

重みには、$\lambda$ をパラメータとして

f(s \mid x) = \lambda^{|s|}

を利用する。

K(x, x') = \sum_{s \in S(x)} \sum_{s' \in S(x')} \lambda^{|s|+|s'|} K_\textrm{String}(s,s')

再帰的に定義

頂点 v と頂点 v’ から始まる部分構造の和として定義する。

\begin{aligned}
K(x, x') &= \sum_{v \in x} \sum_{v' \in x'} K_\textrm{Begin}(v,v') \\
K_\textrm{Begin}(v,v') &= \sum_{s \in S_{v}(x)} \sum_{s' \in S_{v'}(x')} \lambda^{|s|+|s'|} K_{String}(s,s')
\end{aligned}

$K_\textrm{Begin}(v,v’)$ は再帰的に定義できる。

\begin{aligned}
K_{Begin}(v,v') = \lambda^2 K_{Symbol}(v,v') \left( 1 + \sum_{\tilde{v} \in A_{v}(x)} \sum_{\tilde{v}' \in A_{v'}(x')} \lambda^{2} K_{Begin}(\tilde{v},\tilde{v}') \right) \\
\Leftrightarrow K_{Begin}(v,v') - \sum_{\tilde{v} \in A_{v}(x)} \sum_{\tilde{v}' \in A_{v'}(x')} \lambda^{4} K_{Symbol}(v,v') K_{Begin}(\tilde{v},\tilde{v}') = \lambda^2 K_{Symbol}(v,v')
\end{aligned}

連立方程式を解いて合算すれば、カーネルを計算できる。

頂点数が大きいときは素直にランダムウォークしてモンテカルロ法で解く。

参考文献

  1. 鹿島久嗣, “カーネル法による構造データの解析,” 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解 104(670), 61-66, 2005-02-18.