内包カーネルとその応用

内包カーネルとその応用

Intentional Kernel and Its Applications

土井晃一郎

1∗

山本章博

1

Koichiro Doi

1

_{, and Akihiro Yamamoto}

1

1

_{京都大学 大学院情報学研究科}

1

_{Graduate School of Informatics, Kyoto University}

Abstract: We present the intentional kernel as a new class of kernel functions for structured

data. The convolution kernel, that is a typical class of kernel functions is based on sub-structures. On the other hand, the intentional kernel is based on derivations. We also show applications of the intentional kernel, such as boolean functions, first-order terms, RNA sequences. We show properties of the intentional kernel, and discuss the difference between intentional kernel and convolution kernel.

1

はじめに

サポートベクトルマシン (Support Vector Machine, SVM)は近年，パターン認識や機械学習，データマイニ ングの分野で大きく注目されている手法である．SVM は，特徴空間をマージン最大化という基準により分割 する超平面を学習することによって認識を行う．また 非線形関数を用いて原データを高次の特徴空間に写像 することにより，非線形の判別関数を求める手法も開 発されている．SVM において，この写像関数を計算す るのではなく，カーネル関数という特徴空間における 内積を与える関数を使用することにより，学習を行う ことが可能である． SVMはもともと数値データの分類問題に適用するも のであったが，文字列，木などの構造を持ったデータ (以下，構造データとよぶ) の分類問題にも，構造デー タを特徴空間に写像する関数を定義することにより適 用され始めている．構造データを扱ったカーネル関数 のクラスとして，畳込みカーネル (convolution kernel) が Hausler[Haussler 99] によって提案されて，多くの構 造データに対するカーネル関数がこの考え方に基づい て設計されている．畳込みカーネルでは部分構造が構 造データの特徴であるという考え方に基づいてカーネ ルを設計する． それに対して本研究では，構造データの導出過程に 注目したカーネル関数のクラスとして内包カーネル (in-tentional kernel)を提案する．2 章では準備として SVM とカーネルについて説明を行い，3 章では内包カーネ ルの定義を与える．4 章では内包カーネルの具体例を ∗_{連絡先：京都大学 大学院情報学研究科 知能情報学専攻}       〒 606-8501 京都府京都市左京区吉田本町        E-mail: [email protected] いくつか与え，5 章で内包カーネルの性質，6 章で畳込 みカーネルとの違いを議論し，7 章でまとめと今後の 課題を述べる．

2

準備

2.1

SVM

とカーネル

サポートベクトルマシン (SVM)[高須 00, 津田 00] は 訓練データとして有限集合 X∈ Rn _{の要素 x} iと yi ∈ {−1, +1} の組 (xi, yi)が与えられたとき， yi= +1 ⇒ fd(xi)≥ 0, yi=−1 ⇒ fd(xi) < 0. すなわち yi· fd(xi)≥ 0 となる線形判別関数 fd(x) = (w· x) + b を見つける．ここで w は重みベクトル，b はバイアス 項とよばれる．重みベクトル w に対し，訓練データを 重みベクトル上に射影したとき，2 つのクラスの訓練 データの中で重みベクトル上もっとも短い訓練データ の距離が最大になるように判別関数を計算する．この 距離をマージン (margin) とよぶ．すなわち訓練データ xi ∈ X, yi ∈ {+1, −1}(i = 1, 2, ..., n) に対して, 最大 マージンを持つ超平面 f (x) = (w· x) + b = 0 を計算す る．ここで (w· x) は w と x の内積を表す．この超平 面は，以下の最適化問題を解くことによって得られる．

SIG-DMSM-A701-14 (7/26)

人工知能学会研究会資料

:positive example :negative example

margin

linear discriminant function

図 1: サポートベクトルマシン 最大化 : n ∑ i=1 λi− 1 2 n ∑ i=1 n ∑ j=1 λiλjyiyjxi· xj, 制約条件 : n ∑ i=1 λiyi= 0, λi≥ 0 (1 ≤ i ≤ n). 任意の非線形関数 ϕi(x)(i = 1, 2, ..., d)に対して， ϕ(x) = (ϕ1(x), ϕ2(x), ..., ϕd(x))とする．このとき訓 練データ xi∈ X を ϕ によって別の特徴空間内の ϕ(xi) に写像し，そこで SVM を適用することを考える．こ のときの最適化問題は， K(xi, xj) = ϕ(xi)· ϕ(xj) とすると以下のようになる． 最大化 : n ∑ i=1 λi− 1 2 n ∑ i=1 n ∑ j=1 λiλjyiyjK(xi, xj), 制約条件 : n ∑ i=1 λiyi= 0, λi≥ 0 (1 ≤ i ≤ n). このとき判別関数は，fd(x) = ∑n i=1λiyiK(xi, x) + b で求めることができる． 一般に新たな特徴空間はもとの空間よりも高次元で ある．しかし，判別のための最適化問題を計算する際は ϕ(x)を用いなくても K(xi, xj)だけを用いて計算でき るので，高次元の計算を避けることができる．すなわ ち，ϕ によって写像した特徴空間のベクトルを実際に求 めなくても最適化問題を解くことができる．このとき 関数 K(xi, xj) = ϕ(xi)· ϕ(xj)をカーネル関数 (kernel function)と呼ぶ． 䉺 䊷 䊂 䋱 䉺 䊷 䊂 ₂ ዉ಴ general concrete 䊂䊷䉺䋱䇮䊂䊷䉺䋲䈮 ౒ㅢ䈜䉎ዉ಴ㆊ⒟ 図 2: 内包カーネル

3

内包カーネルの定義

構造データの特徴の一つに，データを導出する過程 の存在がある．導出過程とは文字列に対する文脈自由 文法による導出や，木構造が根から成長していく過程 である．これらの具体例については次章で述べる．デー タ d の導出過程を N0 → N1→ · · · → Nk = dとする と各 Niはある構造データの集合を表す概念である．導 出が進むにつれて概念が詳細に，つまり導出が表す構 造データの集合が小さくなっていき，最後には一つの 構造データを表すような導出に注目する (図 2) と，導 出過程の中に出現する節点にはそれが表す構造データ の集合の包含関係により半順序関係を定義できる．こ の半順序関係を利用して次のように定義されるカーネ ルを一般に内包カーネルとよぶことにする. 定義 1 構造データとその構造データの導出過程の節点 の集合とその間に成り立つ半順序関係≽ を考える．構 造データ x, y を入力とするとき，x, y の両方を包摂す る概念の集合 E(x, y) ={z|z ≽ x, z ≽ y} を用いて定義されるカーネルを内包カーネル(intentional kernel)とよぶ. 導出過程はデータの集合を表す概念と考えることが できるので，このカーネル関数のクラスを内包カーネ ルとよんでいる．図 2 の太い枠で囲まれた節点は内包 カーネルを定義するための E(x, y) のイメージである．

例えば，♯(E(x, y)) が E(x, y) の要素数を表すとする と，K(x, y) = ♯(E(x, y)) は内包カーネルの一種であ る．特に K(x, y) = ♯(E(x, y)) という形で定義された 内包カーネル関数を数え上げ内包カーネルとよぶ．

完備束では半順序集合の任意の部分集合に対して最 小上界 (least upper bound, lub) が存在する. 半順序集 合の要素 x, y の最小上界を lub(x, y) と記述するとき， ♯(E(x, y))は lub(x, y) を包摂する要素全体の数のこと

を表す．一般の半順序関係には最小上界が存在すると は限らない．

4

具体例

この章では，前章で定義をした内包カーネルの具体 的な例を挙げる．

4.1

ブール関数

Sadohara [Sadohara 01, Sadohara 02] と Khardon et al. [Khardon 05]は SVM を用いたブール関数の学 習を独立に考案した．データは集合 X⊆ Bn_の要素で あり，高次元の特徴空間に射影して SVM を用いて線 形判別関数を求める．このようなブール関数の学習の ためのカーネル関数として DNF カーネル，単調 DNF カーネル，k-DNF カーネルなどが考案されている． 特徴空間の座標としてリテラルの連言を選ぶ．ただ し命題変数の xiの否定を 1− xiで表すことにする． 定義 2 idx を idx(D, ..., D) = 0 となるような{D, 1, 0}n から{0, 1, ..., 3n_{− 1} への全単射とする．任意の命題変} 数 x と任意の p∈ {D, 1, 0} に対して，L を以下のよう に定義する． L(x, p) =      x (p = 1), 1− x (p = 0), 1 (p = D). さらに ϕi(x)を ϕi(x) = n ∏ j=1 L(xj, pj), idx−1(i) = (p1, p2, ..., pn) として，ϕ(x) = (ϕ1(x), ϕ2(x), ..., ϕl(x))とする．この とき特徴空間の次元は l = 3n_{− 1 である．} 例 1 2 変数 x1, x2のブール関数 g(x1, x2)は以下の 32− 1個のブール式を基底とする特徴空間に射影できる． x1, x2, 1− x1, 1− x2, x1, x2, x1(1− x2), (1− x1)x2, (1− x1)(1− x2). 定理 1 ([Sadohara 01]) n 変数のブール関数 g : Bn → B に対し，以下の条件を満たす超平面 fd(z) = ∑3n₋₁ i=1 wizi= 0が存在する． g(x) = 1 ⇒ fd(ϕ(x)) = 1, g(x) = 0 ⇒ fd(ϕ(x)) =−1. ただし x∈ Bn ϕi(x)はリテラルの連言であるから，判別関数の重 みベクトル w がブール値であるときにおいては x = (x1, x2, ..., xn)∈ Bnに対する ϕ(x) = (ϕ1(x), ϕ2(x), ..., ϕl(x))は DNF を表しているとみなすことができる． このとき特徴空間における内積を考える．ϕi(x)に対 して，idx(i) = (p1, p2, ..., pn)とするとき，x = (x1, x2, ..., xn)において ϕi(x) = 1となるのは j = 1, 2, ..., n に 対して “pj = D”または “pj ̸= D かつ xj = pj” が成 立するときである．そのため ϕi(x)· ϕi(y) = 1となる ときを考えると， ϕi(x) = 1かつ ϕi(y) = 1 であり，ϕi(x)と ϕi(y)で pj = Dとなる j は等しい ので，pj ̸= D ならば xj = yj = pjのときに ϕi(x)· ϕi(y) = 1となる．これはブール値ベクトル x で ϕi(x) に含まれるリテラルの値がすべて等しいことを意味し ている．そこでブール値ベクトル x, y∈ Bdに対して， d(x, y) = x, yにおいて xi= yiとなる i の個数 とすると，長さ i のリテラルの連言でともに値が等し くなるものがただ ( d(x, y) k ) 個存在する．したがっ て内積 ϕ(x)· ϕ(y) は ϕ(x)· ϕ(y) = s(x,y)_∑ i=1 ( d(x, y) i ) となる．これよりカーネルは K(x, y) =−1 + 2d(x,y) となる．このカーネルを DNFカーネル (DNF Kernel) とよぶ． 同様に特徴空間の座標として否定を含まないリテラ ルの連言だけをとることも考えられる．この特徴空間 への射影 ϕ′(x)のカーネルは Km(x, y) =−1 + 2d ′_(x,y) である．ここで d′(x, y) = x, yにおいて xi= yi= 1となる i の個数 とする．このカーネルを単調 DNF カーネル (mono-tone DNF Kernel)とよぶ．また，長さが高々k である リテラルの連言で張られた特徴空間を考えることにより k-DNFカーネル (k-DNF Kernel)Kk_{(x, y)と単調} k-DNFカーネル (monotone k-DNF Kernel) Kk m(x, y) を以下のように定義できる． Kk(x, y) = k ∑ i=1 ( d(x, y) i ) ,

x

1

¬x

1

x

2

¬x

2

x

3

¬x

3

...

x

1

∧ x

2

¬x

1

∧ x

2

x

1

∧ ¬x

2

¬x

1

∧ ¬x

2

x

1

∧ ¬x

2

∧ ¬x

3

x

1

∧ ¬x

2

∧ x

3

x

1

∧ ¬x

2

∧ ¬x

3

∧ x

4

x

1

∧ ¬x

2

∧ x

3

∧¬ x

4

ϕ ϕ

(1

0 0 1)

(1

0 1 0)

K

DNF

: 2

2

– 1 = 3

図 3: ブール関数における包摂関係 Kmk(x, y) = k ∑ i=1 ( d′(x, y) i ) . 例 2 x = (1, 0, 0, 1), y = (1, 0, 1, 0) とする．このとき d(x, y) = 2, d′(x, y) = 1より K(x, y) =−1 + 2d(x,y)_{= 3,} Km(x, y) =−1 + 2d ′_(x,y) = 1. DNFカーネルにおいては連言をブール関数の特徴と しているが，連言の間に “連言 X, Y の中に含まれるリ テラルの集合 S(X), S(Y ) が S(X) ⊇ S(Y ) であると き X ≽ Y である” という半順序関係を考えると，図 3 のような包摂関係の図を考えることができる．図 3 は (1, 0, 0, 1)と (1, 0, 1, 0) に対する包摂関係を示している． したがって DNF カーネルは内包カーネルの一種であ るといえる．

4.2

一階述語論理における一般項

一階述語論理における一般項に対して SVM が適用 できるような特徴空間として,

ϕ_{T ERM}(t) = (ϕ1_{T ERM}(t), ϕ2_{T ERM}(t), ...)

を定める．(Doi et al. [Doi 07]) ここで，σ = s1, s2, . . .

は変種を含まないすべての項からなる列とし， ϕi_{T ERM}(t) = { 1 (ある代入 θ に対して t = siθ), 0 (それ以外のとき) とする．項 t を構成する記号列は有限なので ϕT ERM(t) の成分のうち 1 であるものの個数は有限である. KT ERM f(g(X,Y),h(a)) f(g(X,a),h(Z)) f(g(X,Y),W) f(g(X,a),W) f(g(b,a),h(a)) f(g(X,a),h(a)) f(g(X,Y),h(Y)) f(V,h(Z)) f(V,h(a)) f(g(X,Y),h(Z)) f(g(c,a),h(a)) Anti-unification f(g(b,X),h(a)) f(g(b,X),h(Y)) f(g(c,X),h(a)) f(g(c,X),h(X)) f(V,W)

KTERM(f(g(b,a),h(a), f(g(c,a),h(a))

Non linear tem

図 4: 項データにおける包摂関係

は ϕT ERM(t)を用いて次のように定義される.

KT ERM(s, t) = ϕT ERM(s)· ϕT ERM(t).

いま，項 v を包摂し，かつ変種を含まないすべての項 の総数を size(v) とすると，KT ERM に対して KT ERM(s, t) = size(lub(s, t)) が成立する. カーネル関数 KT ERMの値を求めるためには, lub(s, t) を包摂するような項の変種を除いた個数を求める必要 がある. このカーネル関数の値を求めるアルゴリズム は Doi et al. [Doi 07] において提案されている．図 4 は，f (g(b, a), h(a)) と f (g(c, a), h(a)) に対する導出を 図示している． 内包カーネルの定義における x, y を項とすると，♯(E(x, y)) は KT ERMに一致し，KTERMは内包カーネルの一種 であることがわかる．Muggleton et al.[Muggleton 05] が提案した論理プログラムを利用したカーネルは，節 の最小汎化を利用しているような内包カーネルの一種 となる．Muggleton et al. はこのカーネルを用いて実 験を行ったが, カーネルの値をどのように計算するのか は示していない.

4.3

RNA

配列

RNAに対する内包カーネルは Sankoh et al. [Sankoh 07] によって提案されている．本稿では，いかにして RNA 配 列に対して導出を考えて内包カーネルを設計するかを説 明するにとどめる．さらにこの考え方を拡張したカーネ ル関数の設計方法については Sankoh et al. [Sankoh 07] を参照して欲しい．

RNA配列のうち，最近注目されているタンパク質に 翻訳されずに機能する非コード RNA を考える．RNA 配列のまま機能するため RNA の二次構造が機能に密接

S L P P R RNA㈩೉ ੑᰴ᭴ㅧ CFG䈮䉋䉎ዉ಴ AUGCCG U ACAGU 図 5: RNA 配列における導出と二次構造の関係 に係わっていると考えられる．我々は，RNA の二次構造 を単純な文脈自由文法 (Context Free Grammar, CFG) で表現する．この CFG は，非終端記号 P, L, R, S, E を 用いて構成される．P は塩基の相補対を表し，L と R はそれぞれ左と右に一つの塩基を排出するという操作 を表すために用いる．S と E はそれぞれ開始記号，終 了記号を表す．この CFG は以下の生成規則から成る． S→ P | L | R | E, P → xP y | xLy | xRy | xEy,

L→ xP | xL | xR | xE, R→ P x | Lx | Rx | Ex.

ここで，x∈ {a, u, c, g} であり，x は塩基を表す．また， (x, y)∈ {(a, u), (u, a), (c, g), (g, c)} であり，(x, y) は塩 基の相補対を表す．図 5 に CFG による導出と RNA 配 列，二次構造の関係を示している． 本稿では，KRN Aとして，開始記号 S から 2 つの引 数の配列に向かうまでの全ての導出の中で，共通でか つ重複を除いたものの個数に注目する．以下に簡単な 例を用いて，この考え方を説明していく． 例 3 配列 σ1= aauuと配列 σ2 = auauに対して，開 始記号 S から各配列への導出の例として以下のものが ある． S→ P → aP u → aaEuu → aauu, S→ P → aP u → auEau → auau. ここで，導出における終端記号の違いを無視すると，導 出 S，S → P ，S → P → P の 3 つが共通な導出で ある． a a a u u a u u a a a u u a u u a a a u u a u u ) 2 ( ) 1 ( (4) (3) a a a u u a u u 図 6: 配列 σ1= aauuと配列 σ2= auauの共通二次構 造候補 S L _P R L R L R P P L R P P L R

aauu aauu_auau

P L R auau 図 7: 配列 σ1= aauuと配列 σ2= auauの共通二次構 造候補 次に，共通の導出過程のうち二次構造として同じも のを表している重複を除いた代表元を以下に示す． (1) S→ P → P, (2) S→ P, (3) S→ L → R → P, (4) S. これらの代表元は，2 つの配列が取り得る二次構造の 4 個の候補 (図 6) に対応しており，任意の導出は 4 個の 二次構造候補のいずれかを表現している．例えば，代 表元ではない導出 S → P → R → R → E は，(2) の 二次構造候補を表現する． 以上より，2 つの配列が共通に取り得る導出の個数 を数え上げることと，2 つの入力配列が共通に取り得 る二次構造候補の数を数え上げることは等価であるこ とがわかる．

5

内包カーネルの性質

前章で述べた内包カーネルは代表元をとっている RNA の場合もあるが，二つのデータに共通する導出をすべ て数え上げることによって，カーネル関数の値として いる．まず，このような内包カーネルがカーネルであ ることを示し，さらにその健全性と完全性についても 示す．

定理 2 数え上げ内包カーネルはカーネル関数である． 証明の概略 E(x, y)の定義は x, y をともに導出する節 点であるので x, y に対して対称性を満たす．また，各 導出過程における節点を次元とする特徴空間を考えて， その節点から導出されるなら 1，されないなら 0 とな る特徴空間に写像されると考える．すると，この特徴 空間上の内積と，数え上げ内包カーネルの値が一致す る．このような空間を与えることができるので数え上 げ内包カーネルはカーネル関数であるといえる． 2 G¨artner[G¨artner 03]はカーネルとしての “良さ ”を 完全性 (completeness) と健全性 (correctness) によって 定義した. 完全性は, すべての x, x′, y ∈ X に対して K(x, y)の値によって x ∈ X が一意に決まることを いう. 定義 3 カーネル K が完全(complete) であるとは, K がすべての x, x′, y∈ X に対して K(x, y) = K(x′, y)⇒ x = x′ を満たすことをいう. 定理 3 (内包カーネルの完全性) 数え上げ内包カーネ ルは完全である． 証明の概略 データの間に半順序関係がなければ明ら か．一階述語論理の項データのように，データ間に半 順序関係が成り立つ (導出過程の節点も項である) とき 背理法を用いて証明する. x ̸= x′を仮定して, すべて の y に対して K(x, y) = K(x′, y)が成立しないことを 示す. つまり, K(x, y)̸= K(x′, y)が成立するような y が存在することを示す. このとき, x と x′に包摂関係 が成立するかしないかで場合分けを行う. x ≽ x′かつ x ̸= x′のとき, x を導出するすべての 節点は x′ も導出する．また，x′から x は導出されな いので E(x, x′) ( E(x′, x′)となり，y = x′ のとき, K(x, x′) < K(x′, x′)が成り立つ. x x′かつ x̸= x′のとき, x は x′を導出しないので E(x, x′)( E(x, x) となり, y = x のとき, K(x, x′) < K(x, x)が成り立つ. よって, K(x, y)̸= K(x′, y)が成立するような y が存 在することを示すことができたので, 数え上げ内包カー ネルの完全性が示された. 2 次にある概念クラスに関する健全性を定義する. 概 念クラスC と SVM に関する健全性とは任意の x ∈ X に対して線形識別関数がある閾値を超えるか, 超えな いかによってカーネルの入力である任意の x∈ X は概 念 c∈ C に含まれるかどうか判別を正しく行えること をいう. 定義 4 カーネル K が概念クラスC と SVM に関して 健全(correct) であるとは概念クラスC に含まれるすべ ての概念 c∈ C と x ∈ X に対して ∑ i αiK(xi, x)≥ θ ⇔ c(x) を満たすような αi ∈ R, xi ∈ X, θ ∈ R が存在するこ とである. 定理 4 (内包カーネルの健全性) 数え上げ内包カーネ ルを使用した SVM により任意の概念が学習可能可能 である． 証明の概略 データが与えられたときに，導出過程の 節点を次元とする特徴空間上でデータの任意の分割が 線形分離可能なことを示す．データの間に半順序関係 がなければ，データを全部導出した節点に対する次元 においてはそのデータに対してのみ 1 となるので明ら かである．一階述語論理の項データのように，データ 間に半順序関係が成り立つ (導出過程の節点も項であ る) ときも，データを一般的なものから順にトポロジカ ルソートし，データを一つずつ順に加えていくことを 考えて数学的帰納法で証明する．1 点だけのときは 0 次 元の単体である．i 個の節点が i− 1 次元の単体をなす と仮定し，そこに一点 d を加えることを考える．する とデータ d が加わったときには，データ d 自身を表す 次元が 1 となるデータは d のみである．よって，デー タ集合がなす図形に対して新たな次元を加えていくこ とになる．よって，データ集合は単体となる．これに より，特徴空間上でデータを頂点とする単体をなすこ とを示すことができた． 2

6

畳込みカーネルとの違い

畳込みカーネルとは構造データを部分構造に分け，そ の部分構造間のカーネル関数を足し合わせることによっ て定義されたカーネル関数である．つまり，“部分構造 が類似していれば構造データ全体も類似している” と いう考え方に基づいて設計されている．具体的には K(T, T′) = ∑ s∈s(T ) ∑ s′∈s(T′) Ks(s, s′). と定義される．ここで，s(T ), s(T′)はそれぞれ T, T′の それら自身を含まない部分構造全体の集合を表す． これに対して内包カーネルでは構造データの導出過 程に注目して，“共通の導出が多いということは構造 データが類似している” という考え方に基づいている． 部分構造の間にも包摂関係を考えることが出来るので， その包摂関係に基づいてカーネル関数を設計すれば内 包カーネルも畳込みカーネルの一種と考えられなくも

ないが，畳込みカーネルとは違う設計になる場合もあ る．例えば，一階述語論理の項データの導出において は同じ変数が複数回出てくる項 (非線型項) も導出にお いて出てくる場合があり，このような項はデータの部 分構造とは考えにくく，構造データ全体の導出として とらえる必要がある．

7

まとめ

本稿では内包カーネルという新しいカーネル関数の クラスを提案し，その具体例について述べた．さらに 内包カーネルの考え方でカーネル関数を設計し，内包 カーネルの有用性を示していくことを考えている．

謝辞

この研究の一部は科学研究費補助金基盤研究 (B) 課 題番号 19300046 の助成を受けたものである．

参考文献

[Doi 07] Doi, K., Yamashita, T., and Yamamoto, A.: An Efficient Algorithm for Computing Kernel Function De-fined with Anti-unification, in Proceedings of the 16th International Conference on Inductive Logic Program-ming (ILP2006), Revised Selected Papers (LNAI 4455), pp. 139–153 (2007)

[G¨artner 03] G¨artner, T.: A Survey of Kernel for Struc-tured Data, SIGKDD Explorations, Vol. 5, No. 1, pp. 268–275 (2003)

[Haussler 99] Haussler, D.: Convolution Kernels on Dis-crete Structures, Technical report, University of Cali-fornia - Santa Cruz (1999)

[Khardon 05] Khardon, R., Roth, D., and Servedio, R.: Efficincy versus Convergence of Boolean Kernels for On-Line Learning Algorithms, Journal of Artificial Intelli-gence Research, Vol. 24, pp. 341–356 (2005)

[Muggleton 05] Muggleton, S., Lodhi, H., Amini, A., and Sternberg, M. J. E.: Support Vector Inductive Logic Programming, Proceedings of the 8th Interna-tional Conference on Discovery Science (DS2005), pp. 163–175 (2005)

[Sadohara 01] Sadohara, K.: Learning of Boolean Func-tions Using Support Vector Machine, in Proceedings of the 12th International Conference on Algorithmic Learning Theory (ALT2001), pp. 106–118 (2001) [Sadohara 02] Sadohara, K.: On a Capacity Control

Us-ing Boolean Kernels for the LearnUs-ing of Boolean Func-tions, in Proceedings of the IEEE International Confer-ence on Data Mining, pp. 410–417 (2002)

[Sankoh 07] Sankoh, H., Doi, K., and Yamamoto, A.: An Intentional Kernel Function for RNA Classification, in Proceedings of the 10th International Conference on Discovery Science (DS2007), to appear (2007)

[高須00] 高須 淳宏：Support Vector Machineによる分類,発 見科学とデータマイニング, pp. 118–127,共立出版(2000)

[津田00] 津田 宏治：サポートベクターマシンとは何か,電