京都大学 化学研究所 バイオインフォマティクスセンター 生命情報学基礎論 カーネル法 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 ４月１３日（月）: 生命情報学の基盤 ４月２０日（月）： 配列の比較と相同性検索 ４月２７日（月）： 進化系統樹推定 ４月１３日（月）:　生命情報学の基盤 ４月２０日（月）：　配列の比較と相同性検索 ４月２７日（月）：　進化系統樹推定 ５月１日（金）：　　隠れマルコフモデル ５月１１日（月）：　遺伝子ネットワークの解析と制御（田村） ５月１８日（月）：　タンパク質立体構造予測 ５月２５日（月）、６月１日（月）：　カーネル法 ６月８日（月）：　　代謝ネットワークの堅牢性（田村） ６月１５日（月）：　生物情報ネットワークの構造解析 ６月２２日（月）：　木の編集距離（田村） ６月２９日（月）：　タンパク質相互作用予測（林田） ７月６日（月）：　　タンパク質複合体予測（林田） ７月１３日（月）：　生物データの圧縮による比較（林田）

内容 サポートベクターマシンとカーネル法 タンパク質配列分類のためのカーネル 化合物分類のためのグラフカーネル

サポートベクターマシン(1) カーネル法の一つ、データのクラス予測に利用 1990年代に、Cortes と Vapnik が発明 トレーニングデータとして与えられた正例と負例から、それらを分離する超平面を計算 機械学習、統計学、人工知能、パターン認識、バイオインフォマティクスなど様々な分野に応用 配列分類 タンパク質フォールド予測、二次構造予測 遺伝子発現データ解析 タンパク質相互作用予測 化合物の性質推定 c.f. Kernel Methods in Computational Biology, MIT Press, 2004

サポートベクターマシン(2) 正例と負例を与えて、それらを最適（マージンを最大）に分離する超平面を学習 カーネルを適切に定義することにより超平面以外での分離が可能

SVMによるテストデータの分類 学習データより超平面を学習(SVM) テストデータは、対応する点の超平面に対する位置（上下）で判定

カーネル サポートベクターマシン：基本的には超平面で分離 Φ(x) (特徴ベクトル）：「非線形曲面⇒超平面」に写像 カーネル： x と y の類似度が高い ⇔ K(x,y)が大

カーネルの定義 関数 K: X×X→ R がカーネル　　 iff. 　　X から内積空間 F への写像Φが存在し、　　 　　とかける

マーセルの定理 (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 は直交行列。 　　（　　　　　　　　　はλi の固有ベクトル。VVt= Vt V =I ） ここで　　　　　　　　　　　　　　 とすると 一方、　　　　　　　　　　　　　　　　とすると、　　　　　　　　　　　　　　　 となり、半正定値となる。

マーセルの定理 (3):連続値の場合 K(x,y) がカーネル iff. 任意の二乗可積分関数 f　に対して

カーネルの性質(1) 　　　　　　　　　　　　　　のとき、特徴ベクトル間の距離は 証明

カーネルの性質(2) Ki が以下を満たす時、K もカーネル

カーネルの例(1) (x・y+c)d はカーネル 証明（d=2, c=0の場合）

カーネルの例(2) K1, K2 がカーネルの時、以下もカーネル (i)(ii)より、カーネルの正係数の線形和もカーネル (i)(ii)(iii)より、カーネルの正係数の多項式もカーネル

(i) f(x): X →R ⇒ f(x) f(y) はカーネル カーネルの例(3) (i) f(x): X →R ⇒ f(x) f(y) はカーネル 証明 　　　　　　　　（別証：　f(x)を１次元の特徴ベクトルと考える） (ii) exp(K(x,y)) はカーネル 略証： 指数関数は正の係数を持つ多項式により任意の精度で近似でき、また、カーネルの多項式もカーネルとなるため、性質（２）によりカーネルとなる

exp(-||x-ｙ||2/σ2) はカーネル カーネルの例(4) exp(-||x-ｙ||2/σ2)　はカーネル 　　　　　　　　　（Gaussian RBF kernel） 証明 最初の二項の積は例(3-i)によりカーネル、 　　最後の項は例(3-ii)によりカーネル、 　　それらの積は例(2-iii)によりカーネル

カーネルの例(5) 以下は必ずしもカーネルとはならない

サポートベクターマシン: 定式化(1) 学習データ： Rd 上の点とラベルのペアの集合 最適化問題 （凸二次計画問題） yi=1 ⇒ 正例　　　 yi=-1 ⇒ 負例 最適化問題　（凸二次計画問題） (w,b): Rd 上の超平面 h: w・x+b=0 に対応 1/||w||: h から一番近い xi までの距離（=margin)

サポートベクターマシン: 定式化(2)

サポートベクターマシン: 双対化(1) 問題の双対化 もとの問題のラグランジアンは (|S|=l) もとの問題は以下のmin-max型と等価 更に、この最適解は以下の双対問題の最適解と一致

サポートベクターマシン: 双対化(2) 双対問題の最適解 双対問題は この式のw と b について微分をとり 上記をもとのラグランジアンに代入し

サポートベクターマシン: 双対化(3) 双対問題　（凸二次計画問題） マージン

サポートベクターマシン: 双対化(4) KKT相補条件 サポートベクター xi がサポートベクター 　　⇔　αi* > 0 超平面 h

サポートベクターマシン: カーネル化 xi・xj を K(xi, xj) で置換 （← K(xi, xj) =Φ(xi)・ Φ(xj) ） 識別関数　　　　　　　　（SV:サポートベクターの集合） 利点：　特徴ベクトルを陽に扱わずに、カーネル値のみが計算できればＯＫ　⇒　カーネルトリック

ソフトマージン（2-ノルム） xi xj xk h γ 正負例が完全には 分離不可の場合 ξi/||w|| ξj/||w|| 　分離不可の場合 スラック変数 ξi　の導入 ξj/||w|| ξi/||w|| xi xj xk ξk/||w|| h γ

ソフトマージン（2-ノルム）: 双対化＋カーネル化

ソフトマージン（1-ノルム） xi xj xk 1-ノルムの場合、二乗和でなく、線形和をとる h γ ξi/||w|| ξj/||w|| ξk/||w|| h γ

ソフトマージン（1-ノルム）: 双対化＋カーネル化

カーネル法 SVMによる多数のクラスの分類法（一例） 古くから多くの研究 SVM以外にも様々な応用 各クラスごとにＳＶＭを構成 KPCA: カーネル主成分分析 KCCA: カーネル正準相関分析 SVMによる多数のクラスの分類法（一例） 各クラスごとにＳＶＭを構成 そのクラスの例を正例、それ以外の例を負例とする 新たなデータをそれぞれのＳＶＭに入力し、スコアが最も良いクラスを出力

実問題に対するカーネル データから特徴ベクトル(feature vector)を作るのが一般的、かつ、 多くの場合に実用的 　多くの場合に実用的 特徴ベクトル：　実数値の列 例えば、各化合物 x に対し、 Φ(x) = (分子量, 容積, 表面積, logP,…) 　とすれば、化合物 x,y に対するカーネルは 　 Φ(x) と Φ(ｙ) の単なる内積

内容 サポートベクターマシンとカーネル法 タンパク質配列分類のためのカーネル 化合物分類のためのグラフカーネル

タンパク質立体構造予測 アミノ酸配列から、タンパク質の立体構造（３次元構造）をコンピュータにより推定 実験よりは、精度が悪い だいたいの形がわかれば良いのであれば、4～５割の予測率

フォールド予測 (Fold Recognition) 立体構造は1000種類程度の形に分類される、との予測(Chotia, 1992)に基づく

SCOPデータベース タンパク質立体構造を形状を中心に、人手で、 階層的に、分類したデータベース Class.1 Fold.1 　階層的に、分類したデータベース Class.1 Fold.1 Super Family.1 Family.1 Family.2 mkkrltitlsesvlenlekmaremglsksamisvalenykkgq SCOP Root ispqarafleevfrrkqslnskekeevakkcgitplqvrvwfinkrmrs Class.2 Fold.2 Super Family.2 Family.3 ‥‥‥‥‥

Super Family 予測 入力配列が SCOP のどのスーパーファミリーに属するかを予測 Super Family.1 タンパク質配列 madqlteeqiaefkeafslfdkdgdgtittkelgtvmrslgqnpteaelqdminevdadg ngtidfpefltmmark タンパク質配列 Super Family.1 Super Family.2 Super Family.3 ：

Secondary Structure Prediction 既存手法の主なターゲット Class Fold Super Family Family HMM, PSI-BLAST, SVM SW, BLAST, FASTA Threading Secondary Structure Prediction

配列解析のためのカーネル 配列を実数ベクトルに変換 様々なカーネルの提案 　配列解析のためのカーネル 配列を実数ベクトルに変換 様々なカーネルの提案 Marginalized kernel, Fisher kernel, Local alignment kernel, …

タンパク質配列解析のための既存カーネル 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カーネル 部分配列 t の配列 x での出現回数を occ(t,x) とすると この内積をとり、k-spectrumカーネルを得る 例：　∑={A,C}で、x=“CAACA”, y=“AACCCA”とすると、 　となるので、 なお、Spectrumカーネルは接尾辞木というデータ構造を使うと高速に計算可能

All Substring カーネル (1) Spectrumカーネルでは長さ k の文字列のみ考えたが、All substringカーネルではすべての長さの（不連続も含めた）文字列を考える 例：　x=“CAC”, y=“ACA”とすると、φは次のとおり よって、 ε A C AA AC CA CC AAA … ACA CAC …… Φ(x) 1 2 Φ(y)

All Substring カーネル (2) All substringカーネル 例： x=“CAC”, y=“ACA” 無限次元だが、実際には有限次元 動的計画法を用いて効率的に計算できる 例：　x=“CAC”, y=“ACA” ε C CA CAC 1 A 2 AC 3 5 ACA 7

配列アラインメント バイオインフォマティクスの最重要技術の一つ ２個もしくは３個以上の配列の類似性判定に利用 文字間の最適な対応関係を求める（最適化問題） 配列長を同じにするように、ギャップ記号（挿入、欠失に対応）を挿入

ローカルアラインメント (1) (Smith-Watermanアルゴリズム) 配列の一部のみ共通部分があることが多い 　　⇒共通部分のみのアラインメント 配列検索において広く利用されている 例えば、HEAWGEH　と　GAWED　の場合、 　　　　　　　　A W G E 　　　　　　　　A W －E 　　というアラインメントを計算

ローカルアラインメント(2) 動的計画法 の式

SVM-ペアワイズ法 学習に使う配列の集合を S={s1, s2, …, sn } とする 各配列 x に対する特徴ベクトルを次のように定義 カーネルは、この内積をとり x = ACGATTCG SW(x,s3)=115 SW(x,s1)=80 SW(x,s2)=25 s1 = CTGAAGG s2 = TTCGAA s3 = TACGATGCG

LAカーネル SWアルゴリズムをそのままカーネルとして利用したい ⇒ カーネルとならない 最適な１個のパスを考えただけではカーネルとならない 全部のパスの重み付き和を考えればカーネルとなる

LAカーネルの定義(1) 文字（残基）ペアのスコア: Kaβ (x,y) ギャップのスコア： Kgβ (x,y)

LAカーネルの定義(2) カーネルの畳み込み(convolution) アラインされる文字が n 個ある場合のスコア LAカーネル

LAカーネルとSWスコアの関係 π：(ローカル)アラインメント s(x,y,π): x,yの アラインメントπの スコア 　　アラインメントπの 　　スコア Π：可能なアライメントの集合 定理

LAカーネルとSWスコア SWスコア： 1個の最適なアラインメントのみを考慮 LAカーネル： すべての可能なアラインメントを考慮 s(x,y,π1)=30 s(x,y,π2)=15 s(x,y,π3)= -35 s(x,y,π4)= -115 s(x,y,π)=30

SVM-ペアワイズ法とLAカーネル SVM-pairwise LA kernel x y x y 内積 1640 2290 入力配列 SWスコア データベース配列群 特徴ベクトル (25, 40, 30, 50) (10,30,20,5) 内積 1640 カーネル値 2290

対角優位性問題への対処 ２つの配列 x と y について、K(x,x) と K(x,y)のスケールが違う問題 この時サポートベクターマシンは正負の例を記憶するだけでうまく学習できない。 (実際上の)回避法

　正規化カーネル K(x,y)　がカーネルなら以下もカーネル 理由 　　　　　　　　　　とおくと　　　　　　　　　はカーネル 　　よって、Knorm はカーネル

提案手法の評価法

ROCによる性能評価 カーブが上にあるほど良い性能

mRFPによる性能評価 カーブが上にあるほど良い性能

タンパク質相互作用の予測 (1) 相互作用するペア (x1,x2) を正例、 相互作用しないペア (x3,x4) を負例 x1 x2 x3

タンパク質相互作用の予測 (2) 手法１： Φ（x1） と Φ（x2） を並べたものを特徴ベクトルとする 手法２： pairwise kernel

c1 p1 化合物ータンパク質結合予測 (c1,p1) を化合物 c1 とタンパク質 p1 のペア 結合するペアを正例、結合しないペアを負例とする p1 c1

結論（タンパク配列に対するカーネル） 様々なカーネルが提案されている Spectrumカーネルでは単純に長さ k の各文字列の出現頻度を特徴ベクトルとしている All substringカーネルでは動的計画法により効率的にカーネル値を計算可能 ローカルアラインメントカーネルではすべてのローカルアラインメントを考慮することにより正定値性を確保 相互作用するペアを正例、しないペアを負例とすることにより、タンパク質相互作用予測、化合物ータンパク質結合予測に利用可能

内容 サポートベクターマシンとカーネル法 タンパク質配列分類のためのカーネル 化合物分類のためのグラフカーネル

カーネル法による化合物の分類・性質予測

周辺化グラフ・カーネル　(1) Kashimaらが2003年に提案 h: グラフ G1 におけるパス h’: グラフ G2 におけるパス l(h): パス h のラベル（原子名）の列 K’(x,y): ラベル列間のカーネル関数 （例：　 K’(x,y)=1 if x=y, otherwise 0　　）

周辺化グラフ・カーネル　(2)

周辺化グラフ・カーネル　(3)

周辺化グラフ・カーネル　(4)

周辺化グラフ・カーネル　(5)

周辺化グラフ・カーネル　(6)

周辺化グラフ・カーネル　(7) 周辺化グラフ・カーネル⇒逆行列の計算 無限次元の特徴ベクトルの内積⇒有限時間　（カーネルトリック）

パス（の集合）だけを用いて化学構造を表現 周辺化グラフカーネルの問題点 パス（の集合）だけを用いて化学構造を表現 反応中心などの情報を十分に取り入れることが困難？ 行列のサイズが大きく（数千×数千）なるため、逆行列の計算に時間がかかる すべてのトレーニングデータのペア（化合物のペア）について、それぞれ、逆行列を計算することが必要 ⇒　構造情報(Morgan Index)との組み合わせ

Morganインデックス 化学構造の一意名を計算機により計算するために1960年代に考案 CAS(Chemical Abstract Service)で利用 等価な原子に同じ番号（整数値）が与えられるような、各原子への番号づけを計算 簡単な繰り返し計算による番号づけ 等価で無い原子にも同じ番号がつく可能性（でも、低い） ⇒　Marginalized グラフカーネルにおいて、原子名とともに、モーガンインデックスを利用 原子名およびモーガンインデックスの両者が一致するパスのみを考慮 ⇒　部分構造に関する特徴も、ある程度、取り入れられる

Morganインデックスの計算法 すべての原子に番号１を割り当てる すべての原子 x について以下を実行 N O x に結合している原子の番号を総和を、x の番号とする N O 1 3 2 5 4 7 6

計算機実験 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.