生命情報学基礎論
カーネル法
阿久津 達也
京都大学 化学研究所
バイオインフォマティクスセンター
講義予定
４月１４日（月）: 生命情報学の基盤
４月２１日（月）： 配列の比較と相同性検索
４月２８日（月）： 進化系統樹推定
５月１２日（月）： 隠れマルコフモデル
５月１９日（月）： タンパク質立体構造予測
５月２６日（月）、６月２日（月）： カーネル法
６月９日（月）： 生物情報ネットワークの構造解析
６月１６日（月）: 遺伝子ネットワークの解析と制御（田村）
６月２３日（月）： 代謝ネットワークの堅牢性（田村）
６月３０日（月）： 木の編集距離（田村）
７月７日（月）： タンパク質相互作用予測（林田）
７月１４日（月）： タンパク質複合体予測（林田）
７月１７日（木）： 生物データの圧縮による比較（林田）
内容
サポートベクターマシンとカーネル法
タンパク質配列分類のためのカーネル
化合物分類のためのグラフカーネル
サポートベクターマシン(1)
カーネル法の一つ、データのクラス予測に利用
1990年代に、Cortes と Vapnik が発明
トレーニングデータとして与えられた正例と負例から、
それらを分離する超平面を計算
機械学習、統計学、人工知能、パターン認識、バイオ
インフォマティクスなど様々な分野に応用
配列分類
タンパク質フォールド予測、二次構造予測
遺伝子発現データ解析
タンパク質相互作用予測
化合物の性質推定
c.f. Kernel Methods in Computational Biology, MIT
Press, 2004
サポートベクターマシン(2)
正例と負例を与
えて、それらを最
適（マージンを最
大）に分離する超
平面を学習
カーネルを適切に
定義することによ
り超平面以外で
の分離が可能
margin
SVMによるテストデータの分類
学習データより超平
面を学習(SVM)
テストデータは、対
応する点の超平面
に対する位置（上
下）で判定
テストデータ
カーネル
サポートベクターマシン：基本的には超平面で分離
Φ(x) (特徴ベクトル）：「非線形曲面⇒超平面」に写像
カーネル： K (x, y) (x) (y)
x と y の類似度が高い ⇔ K(x,y)が大
φ(x)
カーネルの定義
関数 K: X×X→ R がカーネル
iff.
X から内積空間 F への写像Φが存在し、
K (x, y) (x) (y)
とかける
マーセルの定理 (1)
X を有限空間とし、K(x,y) を X 上の対称関
数とすると、
K(x,y) がカーネル
iff
行列 K=(K(xi,xj)) (i, j=1,…,n) が半正定値
行列 K が半正定値 iff
K の固有値がすべて非負 iff
(x) (xtKx 0)
マーセルの定理 (2):証明
K は対称なので、K=VΛVt とかける。ただし、Λは固有
値λi を対角要素とする対角行列で、V は直交行列。
n
v
V
i
ji j 1
（
はλi の固有ベクトル。VVt= Vt V =I ）
ここで (x ) V n
とすると
i
k
ik k 1
n
(xi ) (x j ) k Vik V jk (V Λ V t )ij K (xi , x j )
k 1
一方、 K (xi , x j ) (xi ) (x j ) とすると、
w Kw wi ( (xi ) (x j ))wｊ wi (xi ) wi (xi ) 0
i
i
j
i
t
となり、半正定値となる。
マーセルの定理 (3):連続値の場合
K(x,y) がカーネル iff.
任意の二乗可積分関数 f に対して
K
(
x
,
y
)
f
(
x
)
f
(
y
)
d
x
d
y
0
カーネルの性質(1)
K (x, y) (x) (y) のとき、特徴ベクトル間
の距離は
( x) ( y )
K (x, x) K (y, y ) 2 K (x, y )
証明
( x) ( y )
2
(x) (x) (y ) (y ) 2 (x) (y )
カーネルの性質(2)
Ki が以下を満たす時、K もカーネル
x, y X , lim K n (x, y ) K (x, y )
n
カーネルの例(1)
(x・y+c)d はカーネル
証明（d=2, c=0の場合）
(x y ) ( x1 y1 x2 y2 )
2
2
x1 x1 y1 y1 x2 x2 y2 y2 2 x1 x2 y1 y2
x1 x1 , x2 x2 , 2 x1 x2 y1 y1 , y2 y2 , 2 y1 y2
カーネルの例(2)
K1, K2 がカーネルの時、以下もカーネル
(i)
K1 (x, y ) K 2 (x, y )
(ii)
a K1 (x, y )
(a 0)
(iii) K1 (x, y ) K 2 (x, y )
(i)(ii)より、カーネルの正係数の線形和もカーネル
(i)(ii)(iii)より、カーネルの正係数の多項式もカーネル
カーネルの例(3)
(i) f(x): X →R ⇒ f(x) f(y) はカーネル
証明
n
n
v v K (x , x
i 1 j 1
i
j
i
n
j
n
) vi v j f (xi ) f (x j )
i 1 j 1
n
n
vi f (x i ) v j f (x j ) 0
i 1
j 1
（別証： f(x)を１次元の特徴ベクトルと考える）
(ii) exp(K(x,y)) はカーネル
略証： 指数関数は正の係数を持つ多項式により任意の精度
で近似でき、また、カーネルの多項式もカーネルとなるため、
性質（２）によりカーネルとなる
カーネルの例(4)
exp(-||x-ｙ||2/σ2) はカーネル
（Gaussian RBF kernel）
証明
xy
exp
2
2
x2
y2
2x y
exp 2 exp 2 exp 2
最初の二項の積は例(3-i)によりカーネル、
最後の項は例(3-ii)によりカーネル、
それらの積は例(2-iii)によりカーネル
カーネルの例(5)
以下は必ずしもカーネルとはならない
(i)
(ii)
K (x, y )
logK (x, y )
(iii) K (x, y ) tanh(ax y )
(シグモイドカーネル )
サポートベクターマシン: 定式化(1)
学習データ： Rd 上の点とラベルのペアの集合
S (xi , yi ) | xi R , yi {1,1}
yi=1 ⇒ 正例
d
yi=-1 ⇒ 負例
最適化問題 （凸二次計画問題）
minimizew w
w ,b
subject to yi (w xi b) 1
(w,b): Rd 上の超平面 h: w・x+b=0 に対応
1/||w||: h から一番近い xi までの距離（=margin)
サポートベクターマシン: 定式化(2)
1/ w
サポート
ベクター
γ
minimizew w
(w xi b) 1
w ,b
subject to
yi (w xi b) 1
(w xi b)
h
(w xi b) 1
1
( w x b)
(w xi b)
1
0
サポートベクターマシン: 双対化(1)
問題の双対化
(|S|=l)
もとの問題のラグランジアンは
L(w, b, α) w w i 1 i yi (w xi b) 1
l
1
2
もとの問題は以下のmin-max型と等価
min max L(w, b, α )
( w ,b ) 0
更に、この最適解は以下の双対問題の最適解と一致
max min L(w, b, α )
0 ( w ,b )
サポートベクターマシン: 双対化(2)
双対問題の最適解
双対問題は
max min L(w, b, α )
0 ( w ,b )
この式のw と b について微分をとり
L(w, b, α )
l
w i 1 yi i x i 0
w
L(w, b, α )
l
i 1 yi i 0
b
上記をもとのラグランジアンに代入し
L(w, b, α) i 1 i
l
1
2
l
l
i 1
j 1
yi y j i j xi x j
サポートベクターマシン: 双対化(3)
双対問題 （凸二次計画問題）
maximize i 1 i
l
α
subject to
l
i 1
1
2
l
l
i 1
j 1
yi y j i j x i x j
yi i 0
i 0
マージン
1
l
*
*
* , where w i 1 yii xi
w
サポートベクターマシン: 双対化(4)
KKT相補条件
サポート
ベクター
i yi (w* xi b* ) 1 0
*
サポートベクター
xi がサポートベクター
⇔ α i* > 0
h
超平面 h
w x b
*
*
y
x
x
b
i
i
i
i 1
l
0
*
*
γ
サポートベクターマシン: カーネル化
xi・xj を K(xi, xj) で置換 （← K(xi, xj) =Φ(xi)・ Φ(xj) ）
maximize i 1 i
l
α
subject to
l
i 1
i 0
（SV:サポートベクターの集合）
w x b
*
y
xi SV
i
*
i
K ( x i , x) b
b*
y
y
K
(
x
,
x
)
i
j
i
j
i
j
j 1
l
i 1
yi i 0,
識別関数
*
l
1
2
*
maxyi 1 w* xi min yi 1 w* xi
2
利点： 特徴ベクトルを陽に扱わずに、カーネル値のみ
が計算できればＯＫ ⇒ カーネルトリック
ソフトマージン（2-ノルム）
正負例が完全には
分離不可の場合
スラック変数 ξi の導入
min w w C
l
w ,b
2
i 1 i
subject to
yi (w x i b) 1 i
i 0
h
xi
ξj/||w||
ξi/||w||
xj
xk
ξk/||w|| γ
ソフトマージン（2-ノルム）: 双対化＋カーネル化
maximize
α
y y K (x , x
y 0
l
i 1
1
2
subject to
i
l
l
i 1
j 1
l
i 1
i
i 0
i
i
j
i
j
i
1
)
j
C ij
ソフトマージン（1-ノルム）
1-ノルムの場合、二
乗和でなく、線形和
をとる
min w w C i 1 i
l
w ,b
subject to
yi (w x i b) 1 i
i 0
h
xi
ξj/||w||
ξi/||w||
xj
xk
ξk/||w|| γ
ソフトマージン（1-ノルム）: 双対化＋カーネル化
i
i 1
l
maximize
α
1
2
subject to
l
l
i 1
j 1
y
0
i
i
i 1
l
0 i C
yi y j i j K (x i , x j )
カーネル法
古くから多くの研究
SVM以外にも様々な応用
KPCA: カーネル主成分分析
KCCA: カーネル正準相関分析
SVMによる多数のクラスの分類法（一例）
各クラスごとにＳＶＭを構成
そのクラスの例を正例、それ以外の例を負例とする
新たなデータをそれぞれのＳＶＭに入力し、スコ
アが最も良いクラスを出力
実問題に対するカーネル
データから特徴ベクトル(feature vector)を
作るのが一般的、かつ、
多くの場合に実用的
特徴ベクトル： 実数値の列
例えば、各化合物 x に対し、
Φ(x) = (分子量, 容積, 表面積, logP,…)
とすれば、化合物 x,y に対するカーネルは
Φ(x) と Φ(ｙ) の単なる内積
内容
サポートベクターマシンとカーネル法
タンパク質配列分類のためのカーネル
化合物分類のためのグラフカーネル
タンパク質立体構造予測
アミノ酸配列から、
タンパク質の立体
構造（３次元構造）
をコンピュータによ
り推定
実験よりは、精度が
悪い
だいたいの形がわ
かれば良いのであ
れば、4～５割の予
測率
アミノ酸配列
T C A V F G L G G V R L S D
V
コンピュータ
タンパク質
立体構造
フォールド予測 (Fold Recognition)
アミノ酸配列
精密な３次元構造
ではなく、だいたい
の形（fold)を予測
立体構造は1000
種類程度の形に分
類される、との予
測(Chotia, 1992)
に基づく
T C A V F G L G G V R L S D
V
1000個のテンプレート構造
SCOPデータベース
タンパク質立体構造を形状を中心に、人手で、
階層的に、分類したデータベース
SCOP
Root
‥‥‥‥‥
Class.1 Class.2
‥‥‥‥‥
Fold.1 Fold.2
Super
Super
Family.1 Family.2
Family.1
‥‥‥‥‥
Family.2
mkkrltitlsesvlenlekmaremglsksam
ispqarafleevfrrkqslnskekeevakkcg
isvalenykkgq
itplqvrvwfinkrmrs
Family.3
Super Family 予測
入力配列が SCOP のどのスーパーファミリー
に属するかを予測
Super Family.1
タンパク質配列
madqlteeqiaefkeafslfdkdgdgtittkel
gtvmrslgqnpteaelqdminevdadg
Super Family.2
ngtidfpefltmmark
：
：
Super Family.3
既存手法の主なターゲット
Class
Secondary Structure Prediction
Fold
Threading
Super
Family
HMM, PSI-BLAST, SVM
Family
SW, BLAST, FASTA
配列解析のためのカーネル
配列を実数ベクトルに変換
様々なカーネルの提案
Marginalized kernel, Fisher kernel, Local alignment kernel, …
ACCGTA
φ(x)
CACGTA
TCCGTCC
CCACCG
CCACCGA
TCCGTTC
CTACCA CTACCGG
GACCGTA
GACCTC
AGCGTG
AGCGTAA
TACCGTA
タンパク質配列解析のための既存カーネル
HMMから特徴ベクトルを抽出
配列から直接特徴ベクトルを抽出
Fisher カーネル (Jaakkola et al., 2000)
Marginalized カーネル (Tsuda et al., 2002)
Spectrum カーネル (Leslie et al., 2002)
Mismatch カーネル (Leslie et al., 2003)
他の配列とのスコアを特徴ベクトルとして利用
SVM pairwise (Liao & Noble, 2002)
Spectrumカーネル
AA AC AG
A CCT A C
( 0
φ(x)
2
0
CC CG CT
1
0
1
TA
1
)
Spectrumカーネル
部分配列 t の配列 x での出現回数を occ(t,x) とすると
k ( x) (occ(t, x))t
k
この内積をとり、k-spectrumカーネルを得る
K ( x, y) k ( x) k ( y)
例： ∑={A,C}で、x=“CAACA”, y=“AACCCA”とすると、
2 ( x) (1,1,2,0), 2 ( y) (1,1,1,2)
となるので、
K ( x, y) 4
なお、Spectrumカーネルは接尾辞木というデータ構造を使うと高速に計算可能
All Substring カーネル (1)
Spectrumカーネルでは長さ k の文字列のみ考えたが、
All substringカーネルではすべての長さの（不連続も
含めた）文字列を考える ( x) (occ' (t , x))
t*
K ( x, y) ( x) ( y) occ' (t , x)occ' (t , y)
t
例： x=“CAC”, y=“ACA”とすると、φは次のとおり
ε
A
C
AA
AC
CA
CC
AAA … ACA
… CAC ……
Φ(x)
1
1
2
0
1
1
1
0
… 0
… 1
……
Φ(y)
1
2
1
1
1
1
0
0
… 1
… 0
……
よって、
K ( x, y) 1 2 2 1 1 7
All Substring カーネル (2)
All substringカーネル
無限次元だが、実際には有限次元
動的計画法を用いて効率的に計算できる
K ( x, ) 1
K ( xa, y) K ( x, y)
K ( x, y[1... j 1])
j: y[ j ] a
ε
C
CA
CAC
ε
1
1
1
1
A
1
1
2
2
AC
1
2
3
5
ACA
1
2
5
7
例： x=“CAC”, y=“ACA”
K (CA, ACA) K (C, ACA)
K (C, ) K (C, AC)
2 1 2 5
K (CAC, ACA) K (CA, ACA) K (CA, A)
5 2 7
配列アラインメント
バイオインフォマティクス
の最重要技術の一つ
２個もしくは３個以上の配
列の類似性判定に利用
文字間の最適な対応関
係を求める（最適化問題）
配列長を同じにするよう
に、ギャップ記号（挿入、
欠失に対応）を挿入
A L G F G S L Y G
A L G G V S V G
A L G F G
A L G
S L Y G
G V S V
G
ローカルアラインメント (1)
(Smith-Watermanアルゴリズム)
配列の一部のみ共通部分があることが多い
⇒共通部分のみのアラインメント
配列検索において広く利用されている
例えば、HEAWGEH と GAWED の場合、
AWGE
A W －E
というアラインメントを計算
ローカルアラインメント(2)
動的計画法
の式
0
F ( i 1, j 1) s ( x y )
,
F ( i , j ) max
F ( i 1, j ) d
F ( i , j 1) d
SVM-ペアワイズ法
学習に使う配列の集合を S={s1, s2, …, sn } とする
各配列 x に対する特徴ベクトルを次のように定義
SW ( x) (SW( x, si ))s S
i
カーネルは、この内積をとり
K ( x, y) SW ( x) SW ( y)
x = ACGATTCG
SW(x,s1)=80
s1 = CTGAAGG
SW(x,s3)=115
SW(x,s2)=25
s2 = TTCGAA
s3 = TACGATGCG
SW ( x) (80, 25, 115)
LAカーネル
SWアルゴリズムをそのままカーネルとして利用
したい ⇒ カーネルとならない
最適な１個のパスを考えただけではカーネルと
ならない
全部のパスの重み付き和を考えればカーネルと
なる
LAカーネルの定義(1)
文字（残基）ペアのスコア: Kaβ (x,y)
if | x | 1 or | y | 1
0
K a ( x, y)
exp(s( x, y)) otherwise
ギャップのスコア： Kgβ (x,y)
K g ( x, y ) exp ( g (| x |) g (| y |) )
ただし、 g (0) 0, g (n) d e(n 1)
LAカーネルの定義(2)
カーネルの畳み込み(convolution)
K1 K2 ( x, y)
x x x, y y y
アラインされる文字が n 個ある場合のスコア
n 1
K ( n ) ( x, y ) K 0 K a K g
K1 ( x , y ) K2 ( x , y )
K a K 0
ただし、 K 0 1
LAカーネル
K LA
( x, y) K (i ) ( x, y)
i 0
F V- - EKL GAV- - T
F L L DDRL - - VL L T
Kaβ Kｇβ Kaβ Kｇβ Kaβ Kｇβ Kaβ
n=7
LAカーネルとSWスコアの関係
π：(ローカル)アラ
インメント
s(x,y,π): x,yの
アラインメントπの
スコア
Π：可能なアライメ
ントの集合
定理
SW ( x, y) max s( x, y, )
( x , y )
1 ln max exp( s( x, y, ))
( x , y )
K LA
( x, y)
exp( s( x, y, ))
( x , y )
lim ln(K LA ( x, y)) SW ( x, y)
1
LAカーネルとSWスコア
SWスコア： 1個の最適なアラインメントのみを考慮
LAカーネル： すべての可能なアラインメントを考慮
配列 x
HAWGEG
配列 y
AGEHV
SWスコア
AWGE
A - GE
s(x,y,π)=30
LAカーネル
π1
AWGE
A - GE
p(x,y,
π)=0.003
s(x,y,π
1)=30
π2
AWGE
AG - E
p(x,y,
π)=0.001
s(x,y,π
)=15
2
π3 HAWGE
p(x,y,
π)=0.0006
s(x,y,π
)= -35
π4 HAWGE - G
p(x,y,
π4)=0.0001
s(x,y,π
)= -115
A -G -E
A -G EHV -
3
SVM-ペアワイズ法とLAカーネル
SVM-pairwise
入力配列
データ
ベース配
列群
特徴ベク
トル
カーネル値
x
LA kernel
y
x
y
SWスコア
exp( s( x, y, ))
( x , y )
(25, 40, 30, 50)
(10,30,20,5)
内積
2290
1640
対角優位性問題への対処
２つの配列 x と y について、K(x,x) と K(x,y)
のスケールが違う問題
この時サポートベクターマシンは正負の例を
記憶するだけでうまく学習できない。
(実際上の)回避法
~
K LA ( x, y ) ln K LA ( x, y )
~
K LA ( x, y )
K norm ~
1
~
K LA ( x, x) K LA ( y, y )
正規化カーネル
K(x,y) がカーネルなら以下もカーネル
K norm ( x, y)
K ( x, y)
K ( x, x) K ( y, y)
理由
f ( x)
1
K ( x, x)
とおくと
1
K ( x, x) K ( y, y)
よって、Knorm はカーネル
はカーネル
提案手法の評価法
ROCによる性能評価
カーブが
上にある
ほど良い
性能
mRFPによる性能評価
カーブが
上にある
ほど良い
性能
タンパク質相互作用の予測 (1)
相互作用するペア (x1,x2) を正例、
相互作用しないペア (x3,x4) を負例
x1
x3
(x1, x2)
x4
(x3, x4)
x2
タンパク質相互作用の予測 (2)
手法１： Φ（x1） と Φ（x2） を並べたものを特徴
ベクトルとする
( x1 , x2 ) ( ( x1 ), ( x2 ))
K ((x1 , x2 ), ( x3 , x4 )) ( ( x1 ), ( x2 )) ( ( x3 ), ( x4 ))
K ( x1 , x3 ) K ( x2 , x4 )
手法２： pairwise kernel
K ((x1 , x2 ), ( x3 , x4 )) K ( x1 , x3 ) K ( x2 , x4 )
K ( x1 , x4 ) K ( x2 , x3 )
化合物ータンパク質結合予測
(c1,p1) を化合物 c1 とタンパク質 p1 のペア
結合するペアを正例、結合しないペアを負例とする
K ((c1, p1 ), (c2 , p2 )) Kmol (c1, c2 )K protein ( p1, p2 )
c1
p1
結論（タンパク配列に対するカーネル）
様々なカーネルが提案されている
Spectrumカーネルでは単純に長さ k の各文字列の
出現頻度を特徴ベクトルとしている
All substringカーネルでは動的計画法により効率的に
カーネル値を計算可能
ローカルアラインメントカーネルではすべてのローカル
アラインメントを考慮することにより正定値性を確保
相互作用するペアを正例、しないペアを負例とするこ
とにより、タンパク質相互作用予測、化合物ータンパク
質結合予測に利用可能
内容
サポートベクターマシンとカーネル法
タンパク質配列分類のためのカーネル
化合物分類のためのグラフカーネル
カーネル法による化合物の分類・性質予測
周辺化グラフ・カーネル (1)
Kashimaらが2003年に提案
K (G1,G2 ) p(h) p(h')K '(l (h), l (h'))
hV1* h'V2*
h: グラフ G1 におけるパス
h’: グラフ G2 におけるパス
l(h): パス h のラベル（原子名）の列
K’(x,y): ラベル列間のカーネル関数
（例： K’(x,y)=1 if x=y, otherwise 0
）
周辺化グラフ・カーネル (2)
G1
u3
u1
H
u2
C
O
u4
Cl
G2
H
v1 v2
H
h (u1 , u2 , u3 ), h' (v1 , v2 , v5 )
l (h) (H, C, O), l (h' ) (H, C, O)
K ' (l (h), l (h' )) 1
v4
C
v3
v5
O
v6
H
H
h' ' (u1 , u 2 , u3 , u 2 , u 4 )
l ( h' ' ) ( H, C, O, C, Cl)
h' ' ' (v1 , v2 , v5 , v2 , v1 )
l ( h' ' ' ) ( H, C, O, C, H )
K ' (l ( h' ' ), l ( h' ' ' )) 0
周辺化グラフ・カーネル (3)
x
H
O
C
φ(x)
Cl
H
C
N
( 0.03 0.03 0.0
H
C
H
O
C
H
H
C
H
0.02
0.0
0.01
0.002
)
周辺化グラフ・カーネル (4)
p(v1 , v2 , v3 )
0.25 0.9 0.3 0.1
p(v2 , v4 , v2 , v3 )
0.25 0.3 0.9 0.3 0.1
p0 (vi ) 0.25 pq (vi ) 0.1
pa (v2 | v1 ) 1.0
(1 pq ) pa (v2 | v1 ) 0.9
pa (v3 | v2 ) 1 / 3
(1 pq ) pa (v3 | v2 ) 0.3
G1
START
0.25
0.25
0.25
0.25
O
0.3
v1
H
0.3
v2
0.9
C
0.3
0.9
0.9
0.1
v3
0.1
v4
Cl
0.1
END
0.1
周辺化グラフ・カーネル (5)
p s ( v ) p0 ( v ) p q ( v )
pt (u | v)
1 pq (v )
pq ( v )
pa (u | v) pq (u )
n
p(v1 ,, vn ) ps (v1 ) pt (vi | vi 1 )
i 2
周辺化グラフ・カーネル (6)
s (u1 , v1 ) ps(1) (u1 ) ps( 2) (v1 )
t ((ui , vi ) | (ui 1 , vi 1 )) pt(1) (ui | ui 1 ) pt( 2) (vi | vi 1 )
n
((u1 , v1 )(u2 , v2 ) (un , vn )) s (u1 , v1 ) t ((ui , vi ) | (ui 1 , vi 1 ))
i 2
G1 u 1
H
G2
Cl
K
O
v1
u2 G1×G2 ( u1 , v1 ) ( u1 , v2 ) ( u1 , v3 )
v2
v3
H
H,K
H,O
H,H
Cl,K
Cl,O
Cl,H
( u2 , v1 ) ( u2 , v2 ) ( u2 , v3 )
周辺化グラフ・カーネル (7)
K (G1,G2 ) p(h) p(h')K '(l (h), l (h'))
hV1* h'V2*
(h)
h(V1V2 )*
s ( s (v))vV (V V1 V2 )
n 1
(
h
)
(
)
1
s
t
t ( t (u' | u))u 'V ,uV hV , |h| n
*
n 1
K (G1,G2 )
(h) s ( t ) 1
n1
n 1 hV *, |h| n
1 x x 2 1 /(1 x)
s (I t )1 1
周辺化グラフ・カーネル⇒逆行列の計算
無限次元の特徴ベクトルの内積⇒有限時間 （カーネルトリック）
周辺化グラフカーネルの問題点
パス（の集合）だけを用いて化学構造を表現
反応中心などの情報を十分に取り入れることが困
難？
行列のサイズが大きく（数千×数千）なるため、
逆行列の計算に時間がかかる
すべてのトレーニングデータのペア（化合物のペア）
について、それぞれ、逆行列を計算することが必要
⇒ 構造情報(Morgan Index)との組み合わせ
Morganインデックス
化学構造の一意名を計算機により計算するために
1960年代に考案
CAS(Chemical Abstract Service)で利用
等価な原子に同じ番号（整数値）が与えられるような、
各原子への番号づけを計算
簡単な繰り返し計算による番号づけ
等価で無い原子にも同じ番号がつく可能性（でも、低い）
⇒ Marginalized グラフカーネルにおいて、原子名ととも
に、モーガンインデックスを利用
原子名およびモーガンインデックスの両者が一致するパス
のみを考慮
⇒ 部分構造に関する特徴も、ある程度、取り入れられる
Morganインデックスの計算法
すべての原子に番号１を割り当てる
すべての原子 x について以下を実行
x に結合している原子の番号を総和を、x の番号とする
1
2
1
1
1
1
1
1
1
1
N
O
1
2
2
1
4
3
2
2
3
2
2
1
5
4
3
7
5
5
7
5
6
7
1
1
N
1
3
N
3
O
O
3
O
O
5
O
計算機実験
MUTAG データを利用
標準的ベンチマークテストの一つ
化合物のサルモネラ菌の変異性への影響データ
125個の正例、６３個の負例を利用
各例1個のみをテストデータとし、他を学習データと
したテストを繰り返した
ソフトウェア
SVMソフトとして、GIST
(http://microarray.cpmc.columbia.edu/gist)
を利用
他は C++ で記述
結論（化合物に関するカーネル法）
周辺化グラフカーネル
パスの出現頻度を特徴ベクトルとする
逆行列計算により、無限次元ベクトルの内積を有
限時間で計算可能（カーネルトリック）
モーガンインデックスの利用により精度を保ちつつ
高速化可能
他のカーネル
パスでなく部分木、もしくは、部分グラフを使う
従来のケモインフォマティクス分野で開発された特徴
ベクトル（descriptor）を利用
グラフ構造だけでなく、３次元構造データを利用
参考文献
SVMおよびカーネル一般
N. Cristianini & J. Shawe-Taylor: An Introduction to Support Vector
Machines and Other Kernel-based Learning Methods, Cambridge Univ.
Press, 2000.
（日本語訳： 大北（訳）、サポートベクターマシン入門、共立出版, 2005）
J. Shawe-Taylor & N. Cristianini : Kernel Methods for Pattern Analysis,
Cambridge Univ. Press, 2004.
赤穂： カーネル多変量解析, 岩波書店, 2008.
バイオインフォマティクスにおけるカーネル
Kernel Methods in Computational Biology, MIT Press, 2004.
丸山、阿久津： バイオインフォマティクス –配列データ解析と構
造予測, 朝倉書店, 2007.
© Copyright 2024 ExpyDoc
