IBM Research

カーネル法による 構造データの解析

鹿島 久嗣
IBM 東京基礎研究所© 2005 IBM Corporation

IBM Research

はじめに : 構造データ解析のモチベーション 従来の機械学習の対象はベクトル形式で表現されていることが前提– その上での、学習アルゴリズムを議論

 これらの枠では捉えきれない「（グラフ）構造をもつデータ」が増加している– テキスト、HTML、XML、購買履歴、DNA配列、蛋白質立体構造、Web、遺伝子ネットワーク、社会ネットワーク、…

© 2005 IBM Corporation

1

IBM Research

本講演の内容 : カーネル法による構造データの解析手法
１） カーネル法とは
２） 構造カーネル法 – 畳み込みカーネルを中心に
３） 分類問題から、構造マッピング問題へ

DB
AACAB

EAC

DCC

© 2005 IBM Corporation

IBM Research１） カーネル法とは？
 カーネル法の例– ２クラスの分類学習問題を題材に紹介– パーセプトロンを使った説明

 カーネル法の一般的な概念© 2005 IBM Corporation2

IBM Research

題材: ２クラスの分類学習問題 目的: 写像 h: X → Y を求める
– X :全ての解析対象の集合• 例： 人間全体の集合– Y = {+1, -1}: 解析対象が属するクラスの集合• 例: 男／女

 手がかり– N 個の訓練データ :• ただし、h男性

男性

女性？？

女性

© 2005 IBM Corporation

IBM Research

２クラスの分類学習問題への一般的アプローチ
 解析対象して表現を、特徴空間中の点（=特徴ベクトル）と それぞれのクラスに属する点集合を分類する面を求める– 超平面 :
: 重みベクトル•– 予測 :
年収

女性

・・

男性

髪の長さ・・
男性

身長<W,Φ(x)> + b = 0女性© 2005 IBM Corporation3

IBM Research

パーセプトロン ２クラス分類の逐次学習アルゴリズム– 訓練データをひとつづつ処理しながら学習– １）訓練データに対する予測を行う– ２）予測が外れたとき（）のみ、重みベクトルを更新•

重みベクトルに特徴ベクトルを足す／引く（）© 2005 IBM Corporation

IBM Research

パーセプトロンからカーネル法へ 学習 = 重みベクトル w に特徴ベクトルを足す／引く つまり、w は訓練データの特徴ベクトルの線形和で表せる–は新たな重みパラメータ カーネル法としての、パーセプトロン– 代入による分類器の書き換え内積による– カーネル関数: 内積の置き換えデータアクセス© 2005 IBM Corporation4

IBM Research

カーネル法とは カーネル関数（＝内積）によってのみデータアクセスを行う学習器（カーネル関数）（カーネル分類器）

カーネル関数

データ２つのデータのインデックス
カーネル学習器
内積© 2005 IBM Corporation

IBM Research

カーネル法のポイント
 特徴ベクトルが陽に現れない– （カーネル関数はさておき）データアクセス部分が次元に依存しないや が何であれ、適当に類似度それがカーネル関数として使えるを定義すれば– 特徴ベクトルを陽に設計しなくてもよい

データのインデックス

データ

通常の学習器特徴ベクトル© 2005 IBM Corporation5

IBM Research

カーネル法のポイント
 特徴ベクトルが陽に現れない– （カーネル関数はさておき）データアクセス部分が次元に依存しないや が何であれ、適当に類似度それがカーネル関数として使えるを定義すれば– 特徴ベクトルを陽に設計しなくてもよい

カーネル関数データ

２つのデータのインデックス
カーネル学習器
内積© 2005 IBM Corporation

IBM Research２） 構造カーネル法
 構造をもったデータ– 内部構造と外部構造

 構造データに対するカーネル– 畳み込みカーネルの概念– グラフカーネルの設計– 様々な構造に対する畳み込みカーネル© 2005 IBM Corporation

6

IBM Research

構造をもったデータ

データ間の関係

 外部構造: データ間にグラフ構造がある– Web– 社会ネットワーク– 遺伝子／蛋白質ネットワーク
データ

本日のお話

 内部構造: データ内にグラフ構造がある– HTML、XML
データの構成要素– DNA– 化合物要素間の関係© 2005 IBM Corporation

IBM Research

当面の目標: グラフとグラフの間のカーネル関数をつくる
 仕様– グラフとグラフの類似度をうまく表している– それなりの時間で計算できる

ADCCADC B B

ACACB

B

D

© 2005 IBM Corporation

7

IBM Research

簡単なケース１： 単一ノード同士のカーネル関数
 ラベルを比較して、同じなら1、 異なるなら 0 あるいは、何らかの類似度を定義– 原子の性質、大文字／小文字、…

σσ’© 2005 IBM Corporation

IBM Research

簡単なケース2： 長さ n の配列同士のカーネル関数
 ノード同士のカーネル関数の積

A

B

ACD

B

AA

この調子で拡張していっても少しでも形が異なった時点でアウト© 2005 IBM Corporation

8

IBM Research

畳み込みカーネル:構造カーネル設計の一般的な枠組み
 構造データの特徴は、その部分構造が担っている– 例: 自動車の特徴は、部品の特徴が担っている

 ２つの構造の間のカーネル関数は、部分構造間のカーネル関数によって再帰的に定義される– 例: 自転車と自動車のカーネル関数は、それぞれの部品同士のカーネル関数によって定義される© 2005 IBM Corporation

IBM Research

畳み込みカーネルの定義
 定義 :の部分構造の集合–:–: 部分構造間のカーネル関数© 2005 IBM Corporation

9

IBM Research（重み付き）畳み込みカーネルの定義
 定義 :の部分構造の集合–:–: 部分構造間のカーネル関数–:の部分構造の重み

これらを定義（再帰）計算© 2005 IBM Corporation

IBM Research

グラフ・カーネルの定義
 部分構造の集合として何を使うか？

– 部分グラフ？ ⇒ ダメ （計算がNP-hard）– グラフ上のランダム・ウォークによって生成されるパスを使う！
••

は同じ長さの配列同士のカーネル
はパスs の長さによって減衰 (0<λ<1)

BC

A
A

C

DC

A

C
B

A

CC

B

D

A

C

D

C…

…

グラフ

AC

B A
A A C
AA

パス間のカーネル関数

パスの集合

パスの集合グラフ© 2005 IBM Corporation

10

IBM Research

グラフ・カーネルの計算
 グラフ上のランダム・ウォークによって生成されるパスは無限個ありうるため、ナイーブな計算はできない 再帰計算
: ノード v で終わるパスの集合 （–）– ノード対 (v, v’) で終わるパスのみに注目したときのカーネルKV の和に分解

A(v’)– KV が再帰的に書ける！
vv’• 連立方程式を解けばカーネルが計算できる（多項式時間）© 2005 IBM Corporation

A(v)IBM Research

特殊な場合 非循環有向グラフ（DAG）– 再帰式がループしないので、動的計画法で、より速く解ける

A

 木

B

C
AC

BCA

B

ACC

 配列

AB

ACCC

© 2005 IBM Corporation

11

IBM Research

様々な畳み込みカーネル
対象部分
構造

パス

配列

順序木

木

DAGグラフ

○（※２）

○（※２）

○（※２）

○△（※１）○×××部分グラフ※ 1 : 部分構造が同じノードを何度も使える※2:のときには接尾辞木による線形時間解法© 2005 IBM Corporation

IBM Research構造カーネルのまとめ
 データのもつ構造は外部構造と内部構造にわけられる
 内部構造をもつデータのカーネル関数は、部分構造間のカーネル関数によって再帰的に定義される （畳み込みカーネル） 部分構造の数は通常、非常に多くなるので畳み込みカーネルのナイーブな計算は困難
 畳み込みカーネルは、通常、再帰計算によって効率よく計算することができる© 2005 IBM Corporation

12

IBM Research

補足: 外部構造に対するカーネル関数
 隣り合うデータ間のカーネル関数が与えられたとき、離れたデータ間のカーネル関数を定義する– 例: 拡散カーネル• 隣の隣は隣データ間の関係

データ© 2005 IBM Corporation

IBM Research３） 構造マッピング問題
 構造マッピング問題の定義
 ２つのアプローチ
 隠れマルコフ・パーセプトロン
 構造カーネルの適用と問題点
 ２段階学習による解決© 2005 IBM Corporation

13

IBM Research構造マッピング問題
 構造分類問題の、より一般的なケース

XY２クラス分類構造データ構造マッピング

構造データ{+1, -1}構造データ© 2005 IBM Corporation

IBM Research

構造マッピング問題の例
 長さTの配列⇒長さTの配列

DFDEABA

C– 品詞付け– 固有表現抽出– 蛋白質２次構造予測– 遺伝子発見

 配列⇒木構造– 構文解析

G– RNA２次構造予測

AB

A

C

DE

F

G E D
© 2005 IBM Corporation

14

IBM Research

品詞付け
 長さTの配列⇒長さTの配列のマッピング問題– 構造は固定、ラベルだけ当てる

yDT

NN

VBD

NN

xthemansaw.... glasses© 2005 IBM Corporation

IBM Research

構造マッピング問題への２つのアプローチ
 直接マッピング方式: x の特徴空間からy の特徴空間へのマッピングを直接求めるを求め、

–

本日のお話
 ランキング方式: x と y を合わせた構造に対する良し悪しを評価する– x と y を合わせた構造の特徴ベクトルのランキング問題

R&xy

直接マッピング方式

xyランキング方式© 2005 IBM Corporation

15

IBM Research

ランキング方式
 x と y を合わせた構造に対する特徴ベクトルy配列⇒配列を評価

y配列⇒木xx 重み w による評価値が最大になる y を出力する

&？

最大化

yx

© 2005 IBM Corporation

IBM Research

隠れマルコフ・パーセプトロン
 ランキング方式の構造マッピング学習アルゴリズム– 逐次学習アルゴリズム• 訓練データをひとつづつ処理しながら学習– １）訓練データに対する予測を行う– ２）予測が外れたとき（）のみ、重みベクトルを更新•– 全ての誤ったマッピングに対し、やはり、重みベクトルに特徴ベクトルを足す＆引く© 2005 IBM Corporation

16

IBM Research

隠れマルコフ・カーネル・パーセプトロン
 パーセプトロンと同様、カーネル化できるマッピング同士のカーネル関数（組み合わせた構造）

A B C DA B A CとD B C Aのカーネル関数

A B A C© 2005 IBM Corporation

IBM Research

マッピング（組み合わせた構造）同士のカーネル関数
 畳み込みカーネルが使える

 組み合わせた構造の部分構造 S(x, y)
y配列⇒配列EDFxC…

– 注意: y の要素は、任意個は使えない• argmax 操作が、部分構造の含むy要素の数に対して指数的な計算量• Viterbiアルゴリズム（動的計画法）と同じ理由© 2005 IBM Corporation

17

IBM Research

２段階学習: 再ランキングによる方法
 小さい部分構造にもとづく隠れマルコフ・パーセプトロンによって、トップk 候補を出力・ 但し、この中に正解が含まれるかは保証されない そのなかで一番よいものを、大きい部分構造を用いた隠れマルコフ・パーセプトロンで予測– あらかじめ候補がk 個に絞られているので、Viterbiの必要なし
トップ k 候補

？ ？ ？ ？

小さい畳み込み
カーネルA B A CB A A BA B A CA B C DA B A C

トップ k
候補

任意の畳み込み
カーネルD B C AA B A CD B C AA B A C© 2005 IBM Corporation

IBM Research

構造マッピングのまとめ 構造マッピング問題には、直接マッピング方式と、ランキング方式がある
 ランキング方式の一手法が隠れマルコフパーセプトロンであり、パーセプトロンと同様、カーネル化できる
 構造マッピング問題においては、畳み込みカーネルで用いることのできる部分構造に制限がある
 そのため、あくまで任意サイズの部分構造を用いたい場合には、学習を２段階にするなどの工夫が必要© 2005 IBM Corporation

18

IBM Research

構造カーネルの課題
 高速化– 動的計画法などによって、効率的に計算できるといっても、遅い• より高速なアルゴリズム （線形時間、確率、近似）– カーネル法の計算量は、訓練例の数に依存• 例の効率的な管理 （変換、データ構造）

 特徴選択（属性選択）による精度向上– カーネル関数によって特徴空間表現が隠蔽されているため、特徴選択が陽に行えない• 部分構造の重みの学習が特徴選択に相当© 2005 IBM Corporation

IBM Research

おわり１） カーネル法とは
２） 構造カーネル法 – 畳み込みカーネルを中心に
３） 分類問題から、構造マッピング問題へ

DB
AA

CA

B

E

AC

DCC

© 2005 IBM Corporation

19

IBM Research

ありがとうございました© 2005 IBM Corporation

20