木の編集距離による近似パタン発見と半構造データからの情報抽出

点击翻译按钮获取中文摘要

前年度までに、木の編集距離の様々な既存アルゴリズムを対象に、その近似の度合いを代数的に定式化した。これにより、既存の木の編集距離のアルゴリズムを、統一的に記述し俯瞰することができるようになり、その近似の度合いや計算量に応じた自然なクラス階層が存在することもわかった。この成果は、カーネル法に基づく機械学習においても、2つの木構造間の写像の数え上げをベースにした類似度関数を設計することにより、木の編集距離の様々なアルゴリズムをカーネル関数として利用できることがわかった。本年度は、当初の計画では、木の構造照合に関する理論的な枠組みが出来次第、Webのページの木構造を対象にした情報抽出という応用へ研究を進める予定であったが、理論的により興味深く、かつ一般的な成果が得られたため、理論面の研究を進めた。具体的には、前年度までの研究成果を踏まえて、木構造のみでなく、文字列をはじめとする他の離散構造を対象とした既存の畳み込みカーネルの性質を調べた。その結果、畳み込みカーネルの厳密な定義ではなく「共通部分構造の重みつき数え上げ」という概念的な理解により設計されたカーネルで、畳み込みカーネルの定義を逸脱したものが散見されることが判明した。そのようなカーネル関数では、半正定値性が保証されず、その妥当性を確認する必要が発生する。このようなカーネル関数に対しても、本研究で、2つの木構造間のカーネル関数の設計として構築したマッピングの数え上げに基づくカーネル関数の設計手法が有効であることを示した。また、多項式カーネルを一般化したPolynomial Summaryカーネルを提案し、既存の様々なフレームワークを包括する手法であることを示した。すなわち、多項式カーネルは、限定された形式の多項式で定義されているが、これを、より一般の多項式について定義し、カーネル関数となる条件を与えた。