射にもとづく類似性理論
申吉浩
兵庫県立大学応用情報科学研究科
Graduate School of Applied Informatics, University of Hyogo
Abstract: We propose a generic framework to evaluate similarity of data.
1
はじめに
データの類似性は機械学習において最も基本的な概 念である。例えば、クラスタリングは互いに類似した データを集めることが目的であり、類別はデータの類 似性に基づいて新しいデータのクラスを予測する。パ ターン抽出・認証は、複数のデータに共通に現れる類 似領域を特定する。いずれにおいても、データの類似 性の定量的評価が、機械学習における鍵となる。実際、 文献中では、データの類似性を測る多くの手法が提案 されてきた。例えば、カーネルは SVM を含む多変量 解析の手法に用いられるが、本質は類似性関数である。 編集距離は、構造化データの反類似性を測る反類似性 関数である。 本論文のテーマは、文字列、木、グラフといった、構 造をもつデータについて、その類似性を評価する手法 を統一的に考えることにある。本論文はこのテーマに 関する研究の端緒であって、代表的な類似性評価の手 法である、編集距離、パターン抽出、カーネルの関係 を部分的にでも明らかにすることを目的とする。例え ば、編集距離問題とパターン抽出問題の間の双対性を 示す。即ち、編集距離を求めることは、実は、二つの データの間で最も類似性の高い共通パターンを見つけ ることと同じであることを示す。また、編集距離を計 算したり、共通パターンを特定することは、類似性の 分布においてそのピークを探索することであり、対照 的に、カーネルを計算することは分布そのものの評価 であることを見る。 類似性の評価指標を統一的な基盤の受けで考えるこ とは、新しい手法を体系的に開発することにもつなが る。例えば、文献中では、編集距離とパターン抽出は独 立に研究されてきた。しかしながら、前述の双対性を 理解できれば、それぞれの手法を交換することができ る。例えば、本論文では、編集距離に関連して多重ア ラインメントを近似計算するアルゴリズムであるセン タースター法を、複数のデータの共通（類似）パター ンを近似的に求める目的で利用できることを示す。 本論文中では、δx,yは Kronecker のデルタ関数を表す ものとし、即ち、x = y であればδx,y= 1、それ以外で はδx,y= 0 が成り立つ。2
射
2.1
オブジェクトと要素
本論文では、一つかそれ以上のコンポーネントによっ て構成されるデータについて考える。簡便のため、そ のようなデータをオブジェクトと呼び、オブジェクト を構成するコンポーネントを要素と呼ぶ。定式化のた めに、要素の空間をZ 、オブジェクトの空間を W と する。X ∈ W は有限個の要素から構成されるので、X をZ の有限部分集合とみなすことができる。 データのもつ個別の性質によって、オブジェクトの 要素は特定の方法で構造化されている。例えば、一方向 に並べられた文字は文字列を構成する。木は頂点の集 合であるが、頂点の構造は少なくとも、グラフの観点、 順序集合の観点、台数構造の観点の三つの異なる観点 から理解することができる。即ち、Z 及び W は、オブ ジェクトの構造を正しく表現できるように定義されなけ ればならない。以下では、例として、文字列を表現する (ZS,WS)、順序集合として木を表現する (ZTp,WTp)、 半群として木を表現する (ZTs,WTs)、及び、一般的な グラフを表現する (ZG,WG) を導入する。 例 1 (文字列). ZS=Σ×N とし、WSの元 X は、X⊂ ZS で、X ={(ℓ1, 1), (ℓ2, 2), . . . , (ℓn, n)} と表されるものとと する。容易に、X をアルファベットΣ 上の文字列と考 えることができる。 例 2 (順序集合としての木). X を木の頂点集合を表すも のとする。v > w により、v は w の祖先であることを表 す。この時、(X, >) は半順序集合 (partially ordered set, poset) となる。更に、(X , >) は、以下の条件を満足す る。(p1) v > u かつ w > u ならば、v > w か v≤ w かのい ずれかが成り立つ。(p2) 頂点 r∈ X が存在し、r ≥ v が 全ての v∈ X に対して成り立つ。反対に、もし半順序集 合 (X, >) が上記の条件を満足するならば、X は木とな 人工知能学会研究会資料 SGI-FPAI-B503-12る。(ZTp, >) を半順序数号とし、WTpは、X⊆ ZTpで あり、かつ、(X, >) が条件 (p1) 及び (p2) を満足するも のからなるとする。明らかに、WTpは木の集合となる。 例 3 (半群としての木). 木 X を半群として見ることも 可能である。v•w が、v と w の直近共通祖先を表す時、 (X ,•) は可換半群となる。即ち、(u•v)•w = u•(v•w)、 及び、u• w = w • v が任意の u,v,w ∈ X に対して成り立
つ。更に、(X,•) は、(s1) u•u = u、及び、(s2) |{u•v,v•
w, w• u}| ≤ 2 の二つの性質をもつ。反対に、可換半群 (X ,•) が (s1) 及び (s2) を満足すれば、X は木となるこ とを示すことができる。(ZTs,•) を可換半群、WTsは、 部分半群 (ZTs,•) で、(s1) 及び (s2) を満足するものか らなるとする。この時、WTsは木の集合である。 例 4 (グラフ). ZGを V∪ E、E = V ×V とする。WG は、X⊂ ZGで、かつ、(v, w)∈ X ∩E ならば、v ∈ X ∩V かつ w∈ X ∩V となるものからなるとする。X はグラフ であり、X∩V は頂点集合を、X ∩E は辺集合を与える。 要素 (ℓi, i)∈ ZS=Σ×N の ℓiはラベルと考えること ができる。同様に、木及びグラフの頂点にはラベルが 付与されることが多い。本論文では、ℓ :Z → Σ はラベ ルを与える写像であるとする。Σ はラベルのアフファ ベットである。
2.2
射
射µは有限集合 X から有限集合Y への一対一部分写像 である。即ち、部分集合 X′⊆ X をとると、µ: X′→ Y は 一対一写像（単射）となる。この X′を Dom(µ) で表し、 µ(X′)⊆ Y を Ran(µ) で表す。さらに、|µ| は |Dom(µ)| を表すものとする。 X と Y の間の類似性を測るために、射の集合MX ,Y を定める。MX ,Yを定める標準的な方法は、データの構 造を保存する部分写像を集めることである。例えば、半 群構造を例にとると、準同型射は f (x• y) = f (x) • f (y) を満足する。 例 5 (Hamming 射). WSと n∈ N において、WS n をWS 中で|X| = n を満足する文字列の集合とする。X,Y ∈ WS n について、Hamming 射ιX ,Y は、(ℓi, i)∈ X を (ℓ′i, i)∈ Y に対応づける。MH X ,Y ={ιX ,Y} とする。 例 6 (Levenshtein 射). Levenshten 射µは順序を保存す る。即ち、X∈ WS、Y∈ WSとする時、(ℓ i, i), (ℓj, j)∈ X、 (ℓ′i′, i′) =µ((ℓi, i))、(ℓj′, j′) =µ((ℓj, j))∈ Y 及び i < j が 成り立てば、i′< j′が成り立つ。MX ,YL は X から Y へ の Levenshtein 射の全体を表すものとする。例 7 (Ta¨ı射). X,Y∈ WTpに対して、Ta¨ı射µは頂点間の
世代順序を保存する。即ち、v, w∈ Dom(µ) について、 v > w はµ(v) >µ(w) と必要かつ十分である。MT X ,Yは X から Y への Ta¨ı射の全体とする。 例 8 (合意部分木射). 直近共通祖先演算子• に関して、 木 X の部分半群 X′合意部分木と呼ぶ。合意部分木 X′ は• に関して閉じているので根をもつ。X,Y ∈ WTsを 木とする時合意部分木射µは X の合意部分木 X′から Y への一対一準同型である。MX ,YA を合意部分木射の全 体とする。
例 9 (Bunke 射). グラフ X,Y∈ WGに対して、Bunke 射
µは部分グラフ X′⊆ X から Y への一対一グラフ準同型 である。MB S,Y を Bunke 射の全体とする。 Dom(µ) と Ran(µ) の形からMX ,Y を定める方法も有 効である。次の例では、よく知られた MAST (Maximum Agreement SubTree) 問題と関連して、射の集合を定め る。 例 10 (合同合意部分木射). MAST 問題 [5] は二つ以上 の木の最大共通合意部分木を求める問題である。合意 部分木 X′⊆ X と Y′⊆ Y が共通であるとは、互いに同相 であり、かつ、同相写像において対応する頂点が同じラ ベルをもつことをいう。したがって、 X,Y∈ WTsに対 して、MC X ,Y ⊆ MX ,YA を以下のように定める：µ∈ MX ,YA であり、任意の v∈ Dom(µ) がµ(v) と同じラベルを持 つ時、かつ、その時に限り、µ∈ MC X ,Y とする。二つの
木の間の MAST 問題は、arg max{|µ| |µ∈ MC
X ,Y} に属 する合同部分木射を見つけることに他ならない。
2.3
推移的射
射系とは{MX ,Y | X,Y ∈ W } であって、(1) idX∈ MX ,X; (2)µ∈ MX ,Y ならば、µ−1∈ MY,X. idX: X→ X は X の 恒等写像である。 以下に定める推移性は射系の重要な性質であり、編集 距離の三角不等式やカーネルの正定値性の条件である。 定義 1. 射系{MX ,Y| X,Y ∈ W } が弱推移的であるとは、 すべての X,Y, Z∈ W 、µ∈ MX ,Y、ν∈ MY,Zに対して、 Ran(µ) = Dom(ν) が成り立つならば、ν◦µ∈ MX ,Z成 り立つことをいう。 定義 2. 射系{MX ,Y | X,Y ∈ W } が推移的であるとは、 すべての X,Y, Z∈ W 、µ∈ MX ,Y、ν∈ MY,Zに対して、 ν◦µ∈ MX ,Zが成り立つことをいう。2.4
類似性指標
類似性指標ΦX ,Y:MX ,Y → R は、(X,Y) ∈ W ×W に 対して、射µ∈ MX ,Yの Dom(µ) と Ran(µ) との間の類 似性を定める。本論文で導入する方法論において、ΦX ,Yは X と Y との間の類似性評価の基礎となる。3 節で見 るように、max{ΦX ,Y(µ)|µ∈ MX ,Y} により類似性を 評価することは、ΦX ,Y の利用法としては、最も直接的 である。以下では、ΦX ,Y を単純にΦ と表記する。 Φ を定義するために、要素間の原始類似性指標φ: Z × Z → R を利用する。特に、原始類似性指標から、 Φ+とΦ×の二つの類似性指標が導かれる。 Φ+(µ) =
∑
(x,y)∈µφ (x, y) Φ×(µ) =∏
(x,y)∈µφ (x, y) φが正定値であると仮定することで、多くの利点を得 ることができる。正定値カーネルの最も重要な性質は、再生核ヒルベルト空間 reproducing kernel Hilbert spaces
(RKHS) が存在することである [1]: ヒルベルト空間H への埋め込み写像Z ∋ x 7→φx∈ H が存在して、すべ ての x, y∈ Z に対して、φ(x, y) =⟨φx,φy⟩H が成り立 つ。⟨·,·⟩H はH における内積を表す。
3
最大類似性問題
二つのデータオブジェクトの類似性を決定する問題 は、以下の最大類似性問題として、最適化問題として 定式化される。Maximum Similarity Measurement (MSM) 問題: X ,Y∈ W に対して、max{Φ(µ)|µ∈ MX ,Y} を求めよ。
4
編集距離と
MSM
問題の双対性
まず、コスト関数ψ+:Z × Z → R を原始的類似性 指標φ:Z ×Z → R から定義する。このために、ギャッ プ要素⊥ を Z に追加し、φをφ(x,⊥) =φ(⊥,y) =φ(⊥ ,⊥) = 0 により拡張する。簡単のため、拡張後も、同じ 記号Z 、φを用いる。コスト関数ψ+は以下のように 定義される。 ψ+(x, y) = 1 2φ(x, x) + 1 2φ(y, y)−φ(x, y). (1) φ(x, y) をヒルベルト空間内の内積⟨x,y⟩ と見なした場 合、ψ+(x, y) =12∥x−y∥2は余弦定理より導かれる。従っ て、ψ+(·,·) はある距離の二乗の半分に相当する。 ψ+(x,⊥) とψ+(⊥,y) は編集操作の削除と挿入に相当 し、ψ+(x, y) は置換操作を意味する。Eq. (1) は次の式 と同値である。 φ(x, y) =ψ+(x,⊥) +ψ+(y,⊥) −ψ+(x, y). (2) M 定義 編集距離 データ構造 MH X ,Y 例 5 Hamming 文字列 ML X ,Y 例 6 Levenshtein 文字列 MT X ,Y 例 7 Ta¨ı 木 MA X ,Y 例 8 Accordant 木 MB X ,Y 例 9 Graph グラフ 表 1: 文献中で知られている (M ,Φ+)-距離 命題 1. 1. 任意の x, y∈ Z について、ψ+(x, y) =ψ+(y, x) が成り立つ。 2. 任意の x∈ Z について、ψ+(x, x) = 0 が成り立つ。 3. 任意の x∈ Z について、ψ+(x,⊥) =ψ+(⊥,x) = 1 2φ(x, x) が成り立つ。 4. ψ+が負定値であることと、φが正定値であるこ ととは同値である。 系 1. φが正定値であるならば、Z はψ+(·,·)12 に関し て擬距離空間となる。. 例 11. 編集距離の計算では、同じラベルの置換操作の コストを 0 とし、その他のすべての編集操作のコストを 1 とすることが通常である。即ち,ψ+はψ+(x, y) = 1− δℓ(x),ℓ(y),ψ+(⊥,⊥) = 0、及び、ψ+(x,⊥) =ψ+(⊥,y) = 1 により定義される。このψ+は、Eq. (1) により、φ(x, y) = δℓ(x),ℓ(y)+ 1 から導出される。勿論、ψ+は負定値であ り、φ は正定値である。ただし、異なる要素が同じラ ベルを有することが許されるので、√ψ+(·,·) は必ずし も距離空間を与えない。 次いで、X,Y∈ W に対して、µ∈ MX ,Y の編集コス トΨ+(µ) を以下のように定義する。 Ψ+(µ) =∑
x∈X\Dom(µ)ψ +(x,⊥) +∑
y∈Y\Ran(µ)ψ +(⊥,y) +∑
(x,y)∈µψ +(x, y). 定義 3. dM ,Φ+(X ,Y ) = min{Ψ+(µ)|µ∈ MX ,Y}. 例 5、6、7、8、9 で述べたM と例 11 のφℓから導 出されるΦ+に対して、得られる (M ,Φ+)-距離はすべ て文献でよく知られている編集距離と一致する (表 1)。 定理 1 は編集距離問題と MSM 問題との関係を明ら かにする。 定理 1 (双対性). 以下の等式が成り立つ。 dM ,Φ+(X ,Y ) = 1 2 (∑
x∈Xφ (x, x) +∑
y∈Yφ (y, y) ) − max µ∈MX ,Y Φ+(µ)[11] は、文献中で双対性を最初に指摘した論文であ り、木の編集距離 (TED) 問題とパターン抽出問題との 間の双対性を指摘した。具体的には、accordant 距離を 求める TED 問題の双対問題として、MAAST (Mostly Adjusted Agreement-Subtree) 問題を定義した。定理 1 は、上記の結果を著しく一般化したものである。
5
パターン抽出
射系M = {MX ,Y | X,Y ∈ W } の別の見方として、パ ターン抽出問題において抽出したい構造のクラスを指 定する手段と見ることができる。 MAST 問題は以下のように定式化できる。 MAST 問題: {X1, . . . , Xn} ⊆ WTsとする。すべての i̸= j ̸= k ̸= i に対 して (1)µji=µi j−1及び (2) Dom(µi j) = Dom(µik) が成 り立つ条件のもとで、|µ12| を最大にする {µi j∈ MC Xi,Xj| i, j = 1, . . . , n; i̸= j} を求めよ。 ここで、φℓを原始類似性指標ととれば、Φ+(µ) =|µ| が成り立ち、|µ| は類似性指標となる。これを一般化し て、次のようにパターン抽出問題を定式化することが できる。 (M ,Φ)-パターン抽出 (PE) 問題: {X1, . . . , Xn} ⊆ W とする。すべての i ̸= j ̸= k ̸= i に対 して (1)µi j=µ−1ji 及び (2) µi j=µik◦µk jが成り立 つという条件のもとで、∑n i=1∑nj=i+1Φ(µi j) を最大に する{µi j∈ MX i,Xj| i, j = 1,...,n;i ̸= j} を求めよ。 Proposition 2 により、φℓが原始類似性指標であると き、MAST 問題は (MC,Φ+)-パターン抽出問題である。 命題 2. {µi j∈ MXi,Xj| i ̸= j} を (M ,Φ)-パターン抽出 問題の最適解とする。この時、Dom(µji) = Dom(µki) = Ran(µi j) = Ran(µik) がすべての i̸= j ̸= k ̸= i に対して なりたつ。 定理 1 は、(M ,Φ)-パターン抽出問題を n = 2 の場合 に解くことが、(M ,Φ)-距離問題をとくことと同値であ ることを示す。一方、多くの場合、(M ,Φ)-距離問題は 編集距離問題として効率的に解けることが知られてい る。対照的に、(M ,Φ)-パターン抽出問題を n ≥ 3 の場 合に解くことは一般に NP 困難である。 この問題を避けるために、定理 1 はセンタースター 法の利用が可能であることを示唆している。センター スター法は文字列の最適多重アラインメントの近似を 計算するためのアルゴリズムであり [3]、ペアワイズの 編集距離が効率的に計算可能であれば、高速に多重ア ラインメントを計算する。近似アルゴリズムとしては、 近似保証が定数 2 で抑えられるという、非常によい性 質を持つ。 以下では、センタースター法を (M ,Φ)-パターン抽出 問題に適用する方法を示す。多重アラインメントを求め る際のセンタースター法の場合と同じく、ピボットの計 算は効率的であることを仮定する。{X,X1, . . . , Xn} ⊆ W に対して、X のまわりのピボットとは、Dom(µ1) =··· = Dom(µn) という条件のもとで、S =∑ni=1Φ(µi) を最大に する ( ¯µ1, . . . , ¯µn)∈ MX ,X1× ··· × MX ,Xn のことである。 S をピボットのシグニチャと呼ぶ。 (M ,Φ)-パターン抽出問題の近似解を計算するための 「センタースター法」は、以下のように、記述される。 センタースター法: X1, . . . , Xn∈ W が与えられているとする。 1. Xiのまわりのピボット ¯µi1. . . , ¯µi,i−1, ¯µi,i+1, . . . ¯µin を計算し、Siをそのシグネチャとする。 2. k∈ argmax{Si| i = 1,...,n} をとる。 3. i̸= k 及び j ̸= k に対して、µki= ¯µki、µik= ¯µki−1 及びµi j= ¯µk j◦ ¯µki−1を計算する。 センタースター法で (M ,Φ)-パターン抽出問題を解 く最大のメリットは、近似保証が定数で与えられると いう点にある。 定義 4. 原始的類似性指標φ:Z × Z → R が正有界であるとは、inf{φ(x, y)| x,y ∈ Z } > 0 かつ sup{φ(x, y)| x, y∈ Z } < ∞ が成り立つことである。また、supφ/ infφ を c(φ) で表す。 定理 2. X1, . . . , Xn∈ W と (M ,Φ)-パターン抽出問題に 対して、{µi j∈ MX i,Xj| i, j = 1,...,n,i ̸= j} はセンター スター方で求めた近似解であるとし、{bµi j∈ MX i,Xj | i, j = 1, . . . , n, i̸= j} を最適解であるとする。φが正有界 であり、かつ、M が推移的ならば、以下が成り立つ。 n
∑
i=1 n∑
j=i+1 Φ+(µi j)≥ 1 c(φ) n∑
i=1 n∑
j=i+1 Φ+(bµi j)6
モーメントカーネル
実確率変数 X と X 上の確率分布 P が与えられた時、 この確率分布の n 次モーメントは以下のように定義さ れる。 mn= ∫ ∞ −∞x nP(x)dx. 特に、X の定義域が有限集合{x1, . . . , xn} である時は、 n 次モーメントは mn= n∑
i=1 xnip(xi) となる。モーメントは分布を記述する統計量である。実 際、1 次モーメント m1は分布の平均に他ならず、m2− m21は分散を与える。定義 5. X,Y をW に属するオブジェクトとする。射系 MX ,Y と類似性指標Φ に対して、n 次モーメントカー ネルを Kn(X ,Y ) =
∑
µ∈MX ,Y Φ(µ)nによって定義する。 K0(X ,Y ) =|MX ,Y| が成り立つ。K1(X ,Y )/K0(X ,Y ) は、 µ∈ MX ,Y にわたるΦ(µ) の分布の平均値であり、 K2(X ,Y )/K0(X ,Y )− (K1(X ,Y )/K0(X ,Y ))2 はその分散を与える。 モーメントカーネルを利用する重要な利点は、SVM を含む強力なた変数関数理論による分析手法を使える 点にある。そのために、定理 3 は重要な役割を果たす。 定理 3 ([9]). Φ を Φ+又はΦ×とし、原始類似性指標φ から導かれるとする。M が推移的で、かつ、φが正定 値ならば、Kn(X ,Y ) も正定値である。 Kn(X ,Y ) が正定値であるためには、M の推移性が根 拠になっていることに注意されたい。 文献中でも、構造化データの分析にカーネルを用い る手法は精力的に研究 s れてきた。最初の重要な貢献 は畳み込みカーネル [4] であり、集合 S と T とに対し て、K(S, T ) =∑(x,y)∈S×Tk(x, y) と定義される。この時、 k(x, y) が正定値ならば、K(S, T ) も正定値である。申・ 久保山 [8] は畳み込みカーネルを一般化して、マッピ ングカーネルを導入した。マッピングカーネルにより、 構造を持つデータに対する正定値カーネルの設計が著 しく容易になった。これらの貢献に基づき、文献中で 多くのカーネルが提案されている。 例えば、全文字列カーネル [7] は、文字列に対する カーネルとして非常によく知られているが、実は、ML に対する 0 次モーメントカーネルであることがわかる。 木に対しては、[2] が解析木カーネルを導入し、[6] が弾 性カーネルを導入している。これらも 0 次モーメント カーネルの例であり、特に、弾性カーネルはMAに対 する 0 次モーメントカーネルである。文字列と木に対 しては、他にも多くのカーネルが知られているが、筆 者が知る限り、ほとんど全てがなんらかの射系M に 対する 0 次モーメントカーネルとなる。[10] では、高 次モーメントカーネルを含む多様なカーネルの計算可 能性について論じている。 また、定理 4 は、オブジェクトの類似性とモーメン トカーネルの間の非常に興味深い関係を与える。 定理 4. Φ(µ) > 0 がすべてのµ∈ MX ,Y に対して成り 立てば、以下の関係が成り立つ。 max{Φ(µ)|µ∈ MX ,Y} = lim n→∞Kn(X ,Y ) 1/n.7
結論
構造化データの間の類似性を統一的な方法で評価す る共通のフレームワークを提案した。このフレームワー クにより、編集距離、パターン抽出、カーネルの関連性 を明確に説明することができる。特に、類似性の分布を 評価する手法としてモーメントカーネルを提案し、か つ、文献中で知られている構造化データに対するカー ネルのほとんどが 0 次モーメントカーネルの例となる ことを示した。参考文献
[1] C. Berg, J. P. R. Christensen, and R. Ressel. Har-monic Analysis on semigroups. Theory of positive definite and related functions. Springer, 1984. [2] M. Collins and N. Duffy. Convolution kernels for
natural language. In Advances in Neural Informa-tion Processing Systems 14 [Neural InformaInforma-tion Pro-cessing Systems: Natural and Synthetic, NIPS 2001], pages 625–632. MIT Press, 2001.
[3] D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Mathematical Biology, 55:141–154, 1993.
[4] D. Haussler. Convolution kernels on discrete struc-tures. UCSC-CRL 99-10, Dept. of Computer Sci-ence, University of California at Santa Cruz, 1999. [5] Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung,
and Hing-Fung Ting. An even faster and more uni-fying algorithm for comparing trees via unbalanced bipartite matchings. July 2007.
[6] H. Kashima and T. Koyanagi. Kernels for semi-structured data. In the 9th International Conference on Machine Learning (ICML 2002), pages 291–298, 2002.
[7] J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.
[8] K. Shin and T. Kuboyama. A generalization of Haus-sler’s convolution kernel - mapping kernel. In ICML 2008, 2008.
[9] K. Shin and T. Kuboyama. Generalization of haus-sler’s convolution kernel - mapping kernel and its ap-plication to tree kernels. J. Comput. Sci. Technol, 25(5):1040–1054, 2010.
[10] Kilho Shin. Partitionable kernels for mapping ker-nels. In ICDM 2011, pages 645–654, 2011.
[11] Kilho Shin. Tree edit distance and maximum agree-ment subtree. Inf. Process. Lett., 115(1):69–73, 2015.
