本論文は、木構造の近似パタン照合と分類学習に関する理論的な基礎づけと新事実の発見、および、木構造の新たな分類学習アルゴリズムの開発とその情報生物学への応用に関する成果についてまとめたものである。

第1章「Introduction(序論)」では、本論文の研究の背景と動機について述べる。木構造(以後、単に木と呼ぶ)は、情報の階層構造を自然に表現し、効率的に処理するために広く用いられている抽象構造である。インターネット上に蓄積されている膨大なHTML・XML 文書や、自然言語の構文木、生物学分野における系統樹、RNAの二次構造、糖鎖構造、画像処理分野における対象物のグラフモデルなどをはじめとするさまざまな対象が木として表現可能である。これらの対象の効率的な検索や、対象からの知識発見のために、木に関する多くのアルゴリズムが提案されている。なかでも、編集距離の概念に基づく木の近似照合アルゴリズムは、2つの木の間の距離や類似度を計算するだけでなく、共通パタンの発見、構造の統合等の用途に対しても適用可能な一般性をもった手法であり、適用範囲の広さからも重要性が高い。編集距離は、2つの構造を比較する一般的なフレームワークであり、一方の構造から編集操作を用いて、もう一方の構造へ変換するために要する最小の編集コストにより定義される。しかし、木の編集距離の分野では、同じアルゴリズムが気づかれることなく独立に何度も発表されたり、提案者が意図する近似照合の意味と実際に提案されているアルゴリズムとの間にギャップがあったりするなどの混乱が生じている。これは、近似照合アルゴリズムを厳密に記述・比較するための理論的なフレームワークがなかったためである。

一方、近年のサポートベクターマシン(SVM)に代表される学習器を用いたカーネル法による機械学習の爆発的な流行にともない、木の分類学習のためのさまざまな木の類似度(カーネル)が提案されている。しかし、この分野でも、提案者が意図する類似度の意味と実際に提案されている類似度の間にギャップがある場合や、厳密にカーネルとしての要件を満たしていることが証明されていない場合が散見される。また、カーネルとして用いることが出来る計算効率のよい一般的な木の類似度計算のアルゴリズムも提案されていない。

このような背景を踏まえて、本論文では木の近似照合分野における混乱を解消するための基礎理論構築と、その機械学習への応用に関する新たな研究成果を示す。

第1部の「Matching in Trees (木の照合)」は、第2章から第4章までの3つの章から成る。第2章「Approximate Tree Matching(木の近似照合)」では、代表的な既存研究を厳密に定式化しながら紹介する。まず木の近似照合の基礎となる文字列の近似照合について述べる。文字列の近似照合は、編集距離、アラインメント、トレースといった様々な観点から定式化可能であり、数学的に等価であることが知られている。これらの定義は、近似照合の意味を構成的手続きにより示す操作的な定義と、集合論的な概念により示す宣言的な定義に分類できる。次に、同様の観点から、木の編集距離や木のアラインメントなどの既存の多様な木の近似照合手法を概観する。

第3章「Theoretical Foundation of Approximate Tree Matching (木の近似照合の理論的基礎)」では、広い分野で独立に提案されてきた多様な木の近似照合を統一的に記述するための基礎理論を半順序代数を用いて構築する。この基礎付けにより、近似照合の操作的な定義と宣言的な定義を、数学的に厳密に橋渡しすることが可能となる。実際に、編集距離における木の編集操作に、2つの木構造間の写像としての厳密な意味を与える。

第4章「Relationship Analysis among Tree Edit Distance Measures (木の編集距離尺度間の関連性の解析)」では、第3章で構築した基礎理論を用いた解析により、10年来、知られていなかった重要な木の近似照合手法である「木のアラインメント」の宣言的な定義を示す。この結果は、2つの木を1つに結合するための必要十分条件になっており、広い応用が考えられる。さらに、従来別々のアルゴリズムであると考えられていた「木のアラインメント」と「less-constrained 編集距離」が、実は等価なアルゴリズムであることを示す。この解析の過程で、「less-constrained 編集距離」の提案論文の宣言的な定義が、実は「constrained 編集距離」の意味と等価であり、提案者の意図を正しくあらわしていないことを示す。その他にも、厳密に等価性が示されていなかったいくつかの近似照合アルゴリズムに対して、等価性を示した。また、さまざまな木の近似照合アルゴリズムをクラス分けし、これらのクラス間の階層関係を示す。

第2部の「Learning in Trees (木の学習)」は、第5章から第8章までの4つの章から成る。第5章「Kernel-based Learning for Trees (カーネルに基づく木の学習)」では、木の学習問題を、カーネル法におけるカーネル設計の問題として捉え、離散構造のカーネルの重要な設計指針として広く用いられている畳み込みカーネルについて述べる。また、畳み込みカーネルの概念に基づき提案された代表的な木のカーネルについて概観する。また、畳み込みカーネルとして提案されている既存の最も一般的な木カーネルが、実際には畳み込みカーネルのクラスではなく、カーネルとして用いるためには理論的な裏づけが必要であることを示す。

第6章「Mapping Kernel for Trees (木のマッピングカーネル)」では、既存の木カーネルを、第4章で明らかにした木の近似照合のクラス階層の観点から統一的に定式化し、既存の木カーネルの意味づけを行う。また、従来研究では理論的な裏づけなくカーネルとして用いられてきた木の類似度が、実際にカーネル法による学習問題に適用できる数学的条件を満たすことを厳密に証明する。さらに、木の近似照合の各々のクラスに対応する2つの木の類似度(木カーネル)を新たに提案し、最も表現力の高かった既存の木カーネルよりも、さらに高い表現力を持つことを示す。これに対して、木のアラインメントに対応する木カーネルが存在しないことを厳密に示す。

第7章「Spectrum Kernel for Trees (木のスペクトラムカーネル)」では、高速でかつ一般性の高い木カーネルとして木のスペクトラムカーネルを提案する。木のスペクトラムカーネルでは、新たな概念として、文字列のqグラムの概念を木に拡張した木の qグラム を提案し、2つの木に共通して含まれるqグラムを数え上げることにより類似性を測る高速なアルゴリズムを提案する。さらに、木のスペクトラムカーネルを拡張したグラム分布カーネルを提案する。

第8章「Application to Glycan Classification (糖鎖の分類への応用)」では、前章で開発した2つの木カーネルを、バイオインフォマティクスの分野における糖鎖構造の分類学習、および、糖鎖構造からのモチーフ抽出に実際に適用する。その結果、従来の一般的な木カーネルや、糖鎖専用のカーネルと比べて、分類能力と計算効率の両面において、高い性能を示すことを示す。また、モチーフ抽出では、糖鎖専用のカーネルよりも一般的な構造をもつモチーフを抽出できることを示す。

最後に、第9章「Conclusion and Future Work (結論と今後の課題)」で、本論文の成果を要約し、関連する未解決問題や今後の発展について述べる。

本論文は、「Matching and Learning in Trees(木の照合と学習)」と題し、木構造データに対するパターン照合と機械学習に関する数理的な性質について研究した結果をまとめたものである。研究にあたっては、他分野にわたり多数提案されている既存の木構造のパターン照合アルゴリズムを数理的な性質から系統的に整理しなおし、その過程で得られた新たな理論的事実を、機械学習アルゴリズムの開発に利用している。また、開発した機械学習アルゴリズムをバイオインフォマティクスにおける糖鎖構造の分類とモチーフ発見に適用し、その有効性を評価している。これらの結果は、以下の9章にまとめられている。

第1章は「Introduction(序論)」であり、本研究の背景および研究課題と、本論文の構成を述べ、その後、研究成果を要約している。研究の背景として、HTML・XML 文書や、自然言語の構文木、RNAの二次構造、糖鎖構造などの木構造として表現可能なデータに対する効率的なパターン照合アルゴリズムの必要性を説いている。次に、編集距離の概念に基づく木構造の近似パターン照合アルゴリズムが、適用範囲の広い一般的なフレームワークであること、また、従来の編集距離に基づく近似パターン照合の研究に、様々な混乱があることを述べている。同様に、サポートベクターマシン(SVM)に代表される学習器を用いたカーネル法による木構造の分類学習についても、同様の混乱があることを説き、これらの混乱の原因が、近似パターン照合の意味を厳密に記述・比較するための理論的なフレームワークがなかったことに起因するとして、その数理的な解明を研究課題として設定している。

第2章は「Approximate Tree Matching(木の近似照合)」と題し、既存の木構造に対する近似パターン照合アルゴリズムを、文字列の近似パターン照合と類比させながら、網羅的にサーベイし、統一的な表記法により厳密に定式化している。その過程で、具体的に既存研究の問題点を洗い出している。

第3章は「Theoretical Foundation of Approximate Tree Matching (木の近似照合の理論的基礎)」と題し、木構造の近似パターン照合を、2つの半順序集合の間の写像とみなすことにより、半順序代数を用いて、既存の編集距離の概念を統一的に記述するための基礎理論を構築している。この理論を用いて、近似パターン照合アルゴリズムの操作的な意味を、代数的な側面から厳密に記述している。

第4章は「Relationship Analysis among Tree Edit Distance Measures (木の編集距離尺度間の関連性の解析)」と題し、既存の様々な木構造の近似パターン照合アルゴリズム間の関係を明らかにしている。その1つとして、文字列のアラインメントの自然な拡張である「木のアラインメント」と、異なるアルゴリズムであると考えられてきた「less-constrained編集距離」が、実は同じ意味を持つアルゴリズムであることを明らかにしている。その過程で、「木のアラインメント」の代数的な意味づけを行い、これが2つの木を1つに結合するための必要十分条件になっていることを示しており、データ統合などの分野での広い応用が考えられる。その他にも、厳密に等価性が示されていなかったいくつかの木構造の近似パターン照合アルゴリズムに対して、証明を与えている。さらに、多様な木構造の近似パターン照合アルゴリズムを、その数理的な性質に基づいてクラス分けし、これらのクラス間の階層関係を明らかにしている。

第5章では、「Kernel-based Learning for Trees(カーネルに基づく木の学習)」と題して、木構造の分類学習問題を、木構造間の類似度であるカーネル関数(木カーネル)を設計する問題として捉え、既存の木カーネルについて概観している。また、一般的な設計手法である畳み込みカーネルの概念に基づき提案されている最も表現力の高い既存の木カーネルが、実際には畳み込みカーネルのクラスではなく、分類学習に用いるためには理論的な裏づけが必要であることを示している。

第6章は、「Mapping Kernel for Trees(木のマッピングカーネル)」と題し、既存の木カーネルを、第4章で明らかにした木構造の近似パターン照合のクラス階層の観点から統一的に定式化し、既存の木カーネルの意味づけを行っている。また、従来研究では理論的な裏づけなくカーネルとして用いられてきた木の類似度が、実際にカーネル法による学習問題に適用できる数学的条件を満たすことを厳密に証明している。さらに、木構造の近似パターン照合の各々のクラスに対応する2つの木カーネルを新たに提案し、最も表現力の高かった既存の木カーネルよりも、さらに高い表現力を持つことを示している。また、「木のアラインメント」のクラスに対応する木カーネルが存在しないことも厳密に示している。

第7章は、「Spectrum Kernel for Trees (木のスペクトラムカーネル)」と題し、高速でかつ一般性の高い木カーネルとして木のスペクトラムカーネルを提案している。木のスペクトラムカーネルは、文字列のqグラムの概念を木に拡張した木のqグラムを提案し、2つの木構造に共通して含まれるqグラムを数え上げることにより類似性を測る高速なアルゴリズムを提案している。さらに、木のスペクトラムカーネルを拡張したグラム分布カーネルを提案している。

第8章は、「Application to Glycan Classification (糖鎖の分類への応用)」と題し、前章で提案された2つの木カーネルを、バイオインフォマティクスの分野における糖鎖構造の分類学習、および、糖鎖構造からのモチーフ抽出に実際に適用し、分類学習の性能を評価している。その結果、従来の一般的な木カーネルや、糖鎖専用のカーネルと比べて、分類能力と計算効率の両面において、高い性能を示すことを示している。また、モチーフ抽出では、既存の糖鎖専用のカーネルよりも一般的な構造をもつモチーフを抽出できることを示している。

第9章は、「Conclusion and Future Work(結論と今後の課題)」と題し、本論文の成果を要約し、関連する未解決問題や今後の発展について述べている。

このように、本論文は、木構造の近似パターン照合を数理的に記述するフレームワークを与え、木構造の近似パターン照合のクラス階層として統一的に整理したものである。このようなクラス階層の観点が実際に、木構造の分類学習のアルゴリズムの分類にも適用可能であり、この観点から新たなアルゴリズムが開発できることを示している点で、既存研究の数理的な解析にとどまらず、様々な応用の可能性を持った普遍性の高い研究であり、本研究分野の発展に寄与すること大である。

よって、本論文は博士(工学)の学位請求論文として合格と認められる。