構造データからの機械学習

機械学習の伝統的な問題設定では、多数のベクトル集合が訓練データとして与えられ、それを元に、何らかの関数関係を学習（もしくはフィッティング）します。しかし2000年代になって、機械学習がさまざまな実データで試される中で、このような伝統的な問題設定には乗りにくいデータが、大量に存在していることが認識されるようになってきました。

その典型例は、訓練データが図1のようなグラフ集合として与えられる場合です。図において、丸が頂点、直線がつながった辺を表します。頂点につけられたアルファベットは、頂点につけられた何らかのラベルを表します。

図1 グラフの例

グラフ集合の実例としては、たとえば、化学構造式が大量に格納されたデータベースが挙げられます。あるいは、If-Thenルールの集まりを木として見た場合、ある種の知識ベースもまたグラフ（木）集合を保持しているとみなすことができます。Web技術を支えるXMLやHTMLもやはり、木構造ないしはグラフ構造によって表すことができます。これらグラフや木で表現されるデータは一般に「半構造データ」とも呼ばれます。

グラフはベクトルデータの一般化とみなすことができます。上のG1で言えば、もし個々の頂点が独立で区別可能ならば、5次元のベクトルの各次元がAやBといった値をとるものと考えることができます。すなわち、G1 = （B, C, C, A, B）のような表し方ができます。しかしグラフには辺があります。これは頂点の数の次元を持つベクトルでは表現のしようがありません。

一方、伝統的な相関ルール流のデータマイニングでは、ベクトルよりも大雑把に、ひとつのデータを「アイテム集合」として捉えます。上のG1で言えば、もし個々の頂点が独立なら、G1 = {A, 2B, 2C} のような集合と見ることができます。しかしグラフには辺があります。辺がある場合には、頂点同士の結合・非結合の関係を考慮しなければなりません。したがって、たとえば、「グラフG1はG2とどういう関係にあるか」というような問いに答えるのは、グラフが大きくなるとかなり面倒になります。

グラフが大量に格納されたデータベースに対し、相関ルール流のマイニング技術を拡張すること。それは、今まで、アイテム集合という非常に限られた世界のみで通用した（狭義の）データマイニング技術を、圧倒的に広い世界に導くことを意味します。

それに世界で初めて成功したのは、実はIBM東京基礎研究所の研究者でした（Inokuchi et al., PKDD 2000）。A. Inokuchiは、大阪大学のWashio、Motodaらと共同で、グラフ理論におけるグラフの特徴量を巧妙に使い、かつてIBMのRakesh Agrawalらが考案したアプリオリというアルゴリズムが、グラフにも拡張できることを見出しました（AGMアルゴリズム）。ここにおいてデータマイニングは、グラフマイニングという新しい有力分野を見出すことになったのです。

Inokuchiらが先鞭をつけたグラフマイニングの研究はその後も発展を続け、その後も興味深い展開が得られています。 その1つに、対象を木構造に限定することによる、より高速なマイニングアルゴリズムの開発を目指す、木構造マイニングが挙げられます。 木構造は半構造データ解析や自然言語処理などで扱われる、応用上重要な構造データですが、 木構造のもつ特徴をうまく生かすことでアルゴリズムの高速化が計れます。

Hidoらはアイテム集合マイニングやグラフマイニングで共通して用いられる、サイズk+1のデータを2つのサイズkのデータで一意に表現する手法を、兄弟ノード同士に順序を持つ木構造データについても発見しました。この表現によって、マイニングアルゴリズムを木構造データに対し自然に拡張することに成功しました（AMIOTアルゴリズム、下図）。

図2 木構造データの一意な表現手法 （Hido & Kawano: ICDM 2005, 参照）

狭義のグラフマイニングの主要なゴールは、「頻出部分グラフ」を列挙することでした。これはAgrawal流の古典的なデータマイニングの問題設定としては正統的なものでしたが、冒頭に述べたような機械学習一般の問題設定からすれば、ややスコープが狭いものでした。

分類や回帰といった機械学習の問題を、グラフを対象に拡張したらどうなるのか。この問題を考えたのが Kashimaらでした。多くの機械学習のアルゴリズムは、「カーネル関数」という、データ同士の類似度がうまく定義できれば、ある程度容易に理論を構築できることが知られています。Kashimaらが取り組んだのは、グラフ同士のカーネル関数、すなわち、グラフカーネルを理論的に首尾一貫した形で定義することでした。

ノードの数も構造も異なるグラフ同士の類似度を定義すること。ちょっと想像してみただけで非常に困難であることがわかります。Kashimaらは、グラフ上で仮想的にマルコフ的遷移過程を考えるという、それまで誰も考えもしなかったアイディアでこの難問を解決しました（図3）。Kashimaらのグラフカーネルは、グラフを対象にしたカーネル関数としては実質的に世界最初のもので、その後の構造データの機械学習に大きな影響を及ぼすことになります。

図3 グラフ上の酔歩によるカーネル関数の定義 （Kashima, Tsuda, and Inokuchi: ICML 2003, 参照

さて、Inokuchiのグラフマイニングや、Kashimaのグラフカーネルでは、与えられるデータセットは、静的なグラフ集合とみなされ、個別のグラフ同士は基本的に独立とみなされます。

では、グラフが時々刻々変化すると考えたらどうでしょう。そのような例は実は世の中にたくさんあります。たとえば、コンピュータシステムをグラフとして見た場合、毎日のシステムのトラフィックの変化を並べると、グラフの時系列が得られるでしょう。また、物事とその関係をグラフ表現した社会ネットワークの構造は、その変化を時間を追って観察することで、やはり、グラフの時系列として捉えることができます。

グラフ時系列についてのわれわれの研究成果としては、T. Ideらのオンライン異常検知手法の研究が挙げられます。抽象的に言えば、異常検知は、各時刻において、与えられたグラフが、異常か正常かのどちらに分類されるかを答える問題とみなせます。Ideらはそれを、時々刻々変化するグラフのあり方を学習し、そこから異常の兆候を見出すオンライン教師なし学習として定式化しました（Ide ＆ Kashima, 2004）。

Ideの理論のポイントは、各時刻においてグラフの特徴ベクトルを、グラフ上のマルコフ遷移の定常状態として定義する点です（図4）。また、そうやって得られた特徴ベクトルの系列に対し、von Mises-Fisher（vMF）分布という特殊な分布をオンライン学習し、その外れ値検出問題を解くものです。 これらは、グラフ時系列からの知識発見の研究として先駆的業績であることはもちろん、vMF分布の学習が方向データの異常検知に有効であるということを示した初めて仕事です。

図4 グラフ時系列からのオンライン教師なし学習 （Ide & Kashima: KDD 2004, 参照）

構造データの学習に関する最近の特筆すべき研究成果は、2006年末に発表されたKashimaらのリンク予測の理論です。

Kashimaらは、生体ネットワークや、社会ネットワークネットワーク構造の、観測されて分かっている部分構造から、全体の構造を復元する、ネットワーク構造の予測問題に取り組み、構造情報のみからこれを行う、教師付きリンク予測手法を提案しました。

彼らは、ネットワーク構造のこれまでの変化の履歴が得られないような状況でも学習と予測が行えるようにするために、現在のネットワーク構造が、ネットワーク構造の進化モデルのある種の定常分布を考えることによって、定常分布をネットワーク構造の既知の部分にフィットさせる予測を行うというアイディアを提案しました(図5)。

図5 進化モデルに基づくネットワーク構造予測 （Kashima & Abe: ICDM 2006, 参照）

この研究はまだ緒に就いたばかりであり、最新の生体ネットワークデータを用いた新しい生物学的知見の発見などでの実用化のためには、より一層のモデルの精緻化とともに、さまざまな種類の情報をとりこむことが必要です。 我々は上で紹介したような他の構造データ解析の知見も取り入れながら今後もネットワーク構造の予測技術に取り組んでいく予定です。

以上、構造データからの機械学習の理論において、IBM東京基礎研究所がこれまで先駆的な役割を果たしてきたことを述べてきました。

私たちがこれまでプロジェクトの中で実地に出会ってきたデータを振り返ってみる時、構造データからの学習手法は、今後ますます発展することはあっても、退潮していくことはないだろうとある程度確信を持って感じています。

この点については、自然科学の発展史との比較が興味深いかもしれません。1980年代半ば、IBMの研究部門は、高温超伝導物質の発見によりノーベル賞を得ました。この物質の超伝導では、それまで知られていた超伝導物質と異なり、電子間の相互作用が本質的な役割を演じていると考えられています。ひとつの電子をグラフの頂点、相互作用をグラフの辺で表した時、それはまさに、電子の集団をある種のグラフとして捉えねばならないことを意味します。それはデータマイニングで取り扱うグラフとはもちろんずいぶん異なったものですが、データに内在する構造が、きわめて多彩で意表をついた現象を引き起こしうる、という点においては共通したものがあります。

おそらくわれわれは、構造データが本来持っている多彩な内容の、ほんのわずかな部分にしか肉薄できていないに違いありません。高温超伝導のような、世界を驚愕させるような事実がこれから見出されてゆくことでしょう。われわれは今後も、構造データ学習の分野において、グラフマイニングやグラフカーネルに匹敵する顕著な成果が挙げられるよう、この分野に注力していくつもりです。