機械学習・知識発見の対象となるデータとして構造化データを扱うことをテーマとしています． 構造データの特徴の一つは，複雑なデータは単純なデータから帰納的な手続きによって生成されることです． この生成過程は導出とよばれます．機械学習では精密化とよぶこともあります． 本研究室では構造データから導出を利用して知識を導き出す学習方式の開発を行っています． 実問題への応用としてRNAの分類問題を取り上げ，研究を進めています．

木構造データから正データ学習

クラスタリングなどの正データからの機械学習の困難さを計算論的に解析することは， 機械学習の基本的な問題であり，後述するように数学基礎論や代数学とも密接に関連します． 木構造データを対象として，導出を用いることにより，学習可能なクラスとして新たなものを提示することに成功しました．

属性としての導出

文脈自由文法などの生成文法では，文法から文字列を生成する過程が導出(精密化)です． 文法を一つ固定し，データはその文法が生成する形式言語の要素である文字列としますと， 各データに対して少なくとも一つそのデータを生成した導出が存在します． このことは，導出がデータの属性であることを示し，導出を用いて機械学習手法を適用することが可能となります． RNAの分類問題に対しては，各データを生成する導出(の同値類)を列挙するアルゴリズムを構築した上で， 機械学習手法としてクラスタリング手法を利用しています．

内包カーネル [1-1]

属性として導出を用いることにより，構造データにサポートベクトルマシンを適用するための新たなカーネル関数の 一族を「内包カーネル」として定式化しました． 一階述語論理の原子論理式や文脈自由文法を利用した内包カーネルを計算の効率化を含めて設計しています． 構造データを扱うカーネル関数の一族としては合成積 カーネルが有名であるが， 内包カーネルはそれとは対照的な発想に基づいています．RNAの分類問題用の内包カーネルは， 合成積カーネルと比肩して遜色ない性能を出しています．

文字列パターンと精密化 [1-5]

計算論的学習理論における極限同定の枠組みにおいて，広く研究されているモデルの1つに文字列パターンがあります． 文字列パターンは定数文字と変数から構成される1つの文字列で，文字列パターン中の変数は代入によって 別のパターンへと置き換えられます．ある文字列パターンの変数を全て文字列に置き換えて構成される集合をパターン言語と呼びます． 過去の研究においては，文字列に置き換えるために代入の全ての可能性を考えていましたが，新しい枠組みとして代入を制限し， それを精密化と見なすことで，文字列パターンと精密化によるパターン言語の改装を作り， それを文字列データのデータ生成モデルと見なすことができます．このデータ生成モデルから文字列上の確率モデルを作り， それを推定する問題を解いたのが[1-5]の論文です．その後，より精密化自体に着目した研究へと進んでいます．

最近の論文

[1-1]	Sankoh, H., Doi, K., Yamamoto, A. : An Intentional Kernel Function for RNA Classification, Proceedings of the 10th International Conference on Discovery Science, (Lecture Notes in Artificial Intelligence 4755), 281-285, 2007.
[1-2]	Doi, K., Yamamoto, A. : Kernel Functions Based on Derivation, New Frontiers in Applied Data Mining, (Lecture Notes in Artificial Intelligence 5433), 111-122, 2009.
[1-3]	Ouchi, S., Yamamoto, A. : Learning from Positive Data based on the MINL Strategy with Refinement Operators, Revised Selected Papers of LLLL 2009 (Lecture Notes in Artificial Intelligence 6284), 345-357, 2010.
[1-4]	Yudai Kawai, Mahito Sugiyama, Akihiro Yamamoto : Mining RNA Families with Structure Histograms, The 5th International Workshop on Data-Mining and Statistical Science (DMSS2011), 2011.
[1-5]	Otaki, K., Yamamoto, A.:Estimation of Generating Processes of Strings Represented with Patterns and Refinements, The 11th International Conference on Grammatical Inference (ICGI2012), 2012.

木構造データからなるデータベースに対しては，導出以外の性質を利用した機械学習手法を開発しています.

木構造データの文法圧縮と知識発見 [2-1]

文法圧縮は，生成文法を利用したデータ圧縮手法であり，データ内の重複している部分を生成文法に 置き替えながら圧縮を行います．木構造データに対する文法圧縮は，オーバラップの処理が必要ない上に， 重複している部分を見つけることはデータマイニングの一種とみなすことができます． そこで，木構造データに対して文法圧縮を積極的に利用したデータマイニング・アルゴリズムを開発しました[2-1]．

木構造データからの知識発見 [2-2, 2-3, 2-4, 2-5]

ある制約を満たすパターンだけをデータマイニングの結果として出力するアルゴリズムを研究しています． 木構造に対する制約として自然な部分木構造を用いて，ユーザの意図を制約の形で課すことができるアルゴリズムを開発しました[2-2],[2-4]． またデータが徐々に変化する状況において，既存の計算結果を再利用することで， できるだけ再計算のコストが少ないマイニングアルゴリズムを開発しました[2-3]． また本研究室で広く利用されている形式概念分析を無向グラフを対象とした機械学習アルゴリズムへと応用し， 無向グラフによって構成される概念束を定義し，概念束を用いたマイニングアルゴリズムを開発しました[2-5]．

最近の論文

[2-1]	Murakami, S., Doi, K., Yamamoto, A. : Finding Frequent Patterns from Compressed Tree-Structured Data, Proceedings of the 11th International Conference on Discovery Science, (Lecture Notes in Artificial Intelligence 5255), 284-295, 2008.
[2-2]	Viet Anh Nguyen, Akihiro Yamamoto : Incremental Mining of Closed Frequent Subtrees, Proceedings of the 12th International Conference on Discovery Science, (Lecture Notes in Artificial Intelligence 6332), 356-370, 2010.
[2-3]	Anh, N. V., Yamamoto, A.: Mining of Closed Frequent Subtrees From Frequently Updated Databases, Intelligent Data Analysis, 16(6), 2012.
[2-4]	Anh, N. V., Yamamoto, A.: Efficient Mining of Closed Tree Patterns From Large Tree Databases With Subtree Constraint, International Journal on Artificial Intelligence Tools, 2012.
[2-5]	Anh, N. V., Yamamoto, A.: Learning From Graph Data by Putting Graphs on The Lattice, Expert Systems With Applications, 2012.

実数のコード化を利用した学習方式 [3-1, 3-2]

学習アルゴリズムに実数のコード化を取り込むことで，効果的な学習手法を提案しました． コード化という帰納的な手続きに基づいて数値データを離散化することで， 連続的な数値データを位相や距離といった「構造」が与えられた離散データとして扱います． これによって，データ間の類似度計算や，それに基づく分類，クラスタリングなどが高速かつ頑健に実行できます． 具体的には，コード化の過程に潜むフラクタル性に着目することで機械学習における2値クラス分類問題をユークリッド空間上の 閉集合の学習として定式化し（図3-1）， クラス分類問題の限界を計算論的な側面から明らかにしました [3-1]． また，データ集合間の類似度を「符号化ダイバージェンス」として定式化し（図3-2）， 最近傍法に基づく分類によってその有効性を確認しました [3-2]．

(研究プロジェクト: 学術振興会基盤研究(A))

図3-1.クラス分類の計算論的な学習方式．学習機械は訓練データを受け取り，そこから仮説を出力する．各仮説は分類器に対応しており，自己相似集合を表している．このプロセスを繰り返して，仮説の精度を良くしていく．

図3-2.符号化ダイバージェンスの計算．左の例では，青いデータ集合と赤いデータ集合の間の符号化ダイバージェンスは2/10 + 2/10 = 0.4（2はコードのビット数，10はデータ数）となり，右の例では26/10 + 26/10 = 5.2となる．

木構造を利用した高速な類似度計算手法 [3-5]

符号化ダイバージェンスの性質を利用して，データを逐次的に読みながら木構造として管理し，類似度の計算を高速に行うための手法を開発しました [3-5]．

クラスタリングへの応用 [3-3, 3-4, 3-6]

符号化ダイバージェンスを計算するために実数データを符号化するときの計算手法に着目し， 新規のクラスタリング手法などを開発しており [3-3]， 準備実験では任意形状を発見するクラスタリング手法として世界最速を記録しました． より詳細に新規のクラスタリング手法を検証・実験した結果は国際会議において発表しました [3-4], [3-6]． 著者たちの知る限りにおいて，世界最速の手法となっています．

ガウス関数の高速化に基づいたクラス分類手法 [3-8, 3-9]

ガウス関数を別の関数に畳み込む演算は，信号処理・画像処理においてフィルタなどとして広く利用されています． 本研究ではガウス関数を離散化し，畳み込み積分を累積和によって実現する際に高速に計算する手法を構築しました [3-8]． またその手法を基にして，畳み込みを行った値に基づく高速な二値分類手法を構築し， SVMと比べて遜色のない精度を得られることを確認しました [3-9]．

最近の論文

[3-1]	Sugiyama, M., Hirowatari, E., Tsuiki, H., Yamamoto, A.: Learning Figures with the Hausdorff Metric by Fractals, Proceedings of the 21th International Conference on Algorithmic Learning Theory (ALT 2010), Lecture Notes in Artificial Intelligence 6331, 315-329, 2010.
[3-2]	Sugiyama, M., Yamamoto, A.: The Coding Divergence for Measuring the Complexity of Separating Two Sets, Proceedings of the 2nd Asian Conference on Machine Learning (ACML2010), JMLR: Workshop and Conference Proceedings 13, 127-143, 2010.
[3-3]	Sugiyama, M., Yamamoto, A. : Fast Clustering Based on the Gray-Code (extended abstract), In Proceedings of 7th Workshop on Learning with Logics and Logics for Learning (LLLL2011), p. 42, 2011.
[3-4]	Sugiyama, M., Yamamoto, A. : The Minimum Code Length for Clustering Using the Gray Code, ECML PKDD 2011 (LNCS 6913), 2011.
[3-5]	Sugiyama, M., Yoshioka, T., Yamamoto, A. : High-throughput Data Stream Classification on Trees, Proceedings of The Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP 2011), 2011.
[3-6]	Sugiyama, M., Yamamoto, A. : A Fast and Flexible Clustering Algorithm Using Binary Discretization, IEEE ICDM 2011, 2011.
[3-7]	Sugiyama, M., Hirowatari, E., Tsuiki, H., Yamamoto, A. : Learning Figures with the Hausdorff Metric by Fractals―Towards Computable Binary Classification, Machine Learning, 90(1), 91-126, 2013.
[3-8]	Imajo, K.: Fast Gaussian Filtering Algorithm Using Splines. Proceedings of the 21st International Conference on Pattern Recognition (ICPR 2012), 2012.
[3-9]	Imajo, K., Otaki, K., Yamamoto, A.: Binary Classification Using Fast Gaussian Filtering Algorithm, Proceedings of The Third Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP 2012), 2012.

データを，対象の集合と属性の集合の二項関係と見なした上で，代数的構造を用いて分析する「形式概念解析」という手法は，仮説の学習，頻出アイテム集合の発見といった機械学習，データマイニングの基本的問題に用いられてきました． 我々の研究室では，近年の多様化の進んだデータから学習やマイニングを行なう際の代数的なアプローチとして，形式概念解析を応用する研究を行っています．

離散値・連続値混在データからの半教師あり学習 [4-1, 4-2]

機械学習に用いられているデータはますます多様化しており，その中でも例えばネットワークの不正侵入検知のためのデータのように， 離散値と連続値が混在しているデータが多く出現しています． しかし，このような離散値・連続値混在データに対する機械学習手法としては，C4.5のような古典的手法しか提案されていません．一方，関係データベースからの機械学習において，データのもつ代数的な性質が鍵となることが明らかとなってきています．そこで，形式概念解析を活用した離散値・連続値混在データのための機械学習手法を開発しました [4-2]． 特に，半教師あり学習と呼ばれている，正解のわかっているデータ，わからないデータを共に用いて未知データの分類規則を学習するという課題に取り組みました． 代数的に「閉じている」性質に着目することで，訓練データから束構造を導出し（図 4-1）， その上での極大性を利用することで正解付きデータを有効に使った学習を実現しました．実データを用いた実験により， C4.5のような他の機械学習手法より良い性能が出ることを確認しました．

(研究プロジェクト: 学術振興会基盤研究(A))

図4-1.形式概念解析による束の構成．ここから分類規則を学習する．

頻繁に更新されるデータからの局所的な特徴選択を用いた怠惰学習 [4-3]

実際のデータベースの多くは，次々と新たなデータが加えられることにより増大していきます．気象データや株価データはもちろん，Webページのコンテンツも時間とともに増加していくデータ集合です．そのようなデータベースからの学習を考える場合，データベースが更新される度に一から学習を行うのではなく，更新された部分についてのみ逐次的に学習を行う怠惰学習という考え方があります．k近傍法に代表されるこのタイプの学習は，未知のデータをクラス分類する際，分類ルールを学習する代わりに，特徴空間上で近傍(クラスの分かっているデータのうち未知データに類似するもの)を探してそれを参考に未知データをクラス分類します．学習に適した特徴空間を獲得することを目的として，特徴選択という前処理がデータに対して行われます．一般に，特徴選択は全てのデータを対象として，それらを分類するために適した特徴空間の獲得を目的としています．しかし，未知データそれぞれについて分類に適した特徴空間が存在すると予想されます．本研究は，形式概念を各未知データに対する特徴選択の結果とそれにより決定される近傍の集合であると見なすことで，怠惰で局所的な特徴選択を行う手法を提案し，実験によりk近傍法より高い精度でクラス分類可能であることを確認しました．

最近の論文

[4-1]	Nguyen, D. A., Doi, K., Yamamoto, A. : Discovering the Structures of Open Source Programs from Their Developer Mailing Lists, Proceedings of the 12th International Conference on Discovery Science, (Lecture Notes in Artificial Intelligence 5808), 227-241, 2009.
[4-2]	Sugiyama, M., Yamamoto, A. : Semi-Supervised Learning for Mixed-Type Data via Formal Concept Analysis, The 19th International Conference on Conceptual Structures (ICCS2011), 2011 (採択済，ProceedingsはLecture Notes in Artificial Intelligenceに掲載).
[4-3]	Ikeda, M., Yamamoto, A.: Classification by Selecting Plausible Formal Concepts in a Concept Lattice, Proceedings of Workshop on Formal Concept Analysis meets Information Retrieval (FCAIR2013), 22-35, 2013.

大量のデータを扱う場合の一つの方法として，データマイニングを分散処理によって行う方法があります．しかし大量のデータを分散して処理する場合や，分散して各地に保存されているデータを対象とした分散処理は，その処理を達成するためにデータベース間での通信や情報の共有が書かせません．そのため，データマイニングを達成する代わりに，各サイト所持している外部へ流出させられない機密性の高い情報が漏洩する可能性が指摘されており，その対策としてプライバシー保護データマイニングという分野の研究が進んでいます． そこで本研究室では頻出パターンマイニングなどの基本的なデータマイニング手法を対象として，分散処理を行う際のデータ構造に注目した研究を行っています．例えば頻出パターンマイニングでは，各サイトが所有するデータをパターンの集合として表現しますが，集合を秘匿するための暗号学的な処理（準同型性暗号）に注目したり ([5-1])，集合をBDDやZDDに代表される木構造として表現する場合において，木構造に注目した上でデータの秘匿性を確保するような偽の情報を追加する処理に注目したりして ([5-2], [5-3])，プライバシー保護データマイニングを研究しています．

最近の論文

[5-1]	Shin-ya Kuno, Koichiro Doi, Akihiro Yamamoto : Frequent Closed Itemset Mining with Privacy Preserving for Distributed Databases, Proceedings of the 10th ICDM Workshop on Privacy Aspects of Data Mining (PADM 2010), 483-490, 2010.
[5-2]	Keisuke Otaki, Akihiro Yamamoto : Preserving Privacy with Dummy Data in Set Operations on Itemsets, Proceedings of The Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP 2011), 2011.
[5-3]	Keisuke Otaki, Mahito Sugiyama, Akihiro Yamamoto : Privacy Preserving using Dummy Data for Set Operations in Itemset Mining Implemented with ZDDs, IEICE Transactions on Information and System, Vol. E95-D, No. 12, 3017-3025, 2012.

数理論理学においては，論理式に対して真偽による解釈を与えることで，意味の世界を記号として扱います． これにより，推論を記号の操作として扱う論理体系が構築されました． しかし，そうした論理体系は現実世界の推論を表現するには十分でないことが知られています． 例えば，推論は現実には不確実性を持つことがあるため，その正しさを真と偽の2値で表現することは十分ではありません． そこで，対象とする現実的な問題に即した形で不確実性と既存の論理体系を統合する研究を行っています．

不確実推論に基づく仮説の意味論と仮説管理の支援手法 [6-1]

歴史学における仮説は，不確実な推論の積み重ねにより導出され，統計的に正しさを計測できないことが多いとされています． このような仮説は矛盾を起こすことがあり，矛盾は取り除かれる必要があります．そこで，仮説を導出した不確実推論の積み重ねを， 有向非巡回グラフを用いて表現するための意味論 (Reasoning Webモデル) を構築し， その意味論に基づいて，仮説から矛盾を取り除く手続きなど，人間が行う仮説管理を計算機によって支援する手法を構築しました．

不確実性を伴う人間の推論の論理と確率推論の統合 [6-2]

不確実推論を計算機上で行うものとしてよく知られているBayesian Networkでは，条件付き確率表が必要です．しかし，訓練データが不十分な場合には条件付き確率表の獲得が困難です．そこで，条件付き確率表の代わりに確実性スコア(Certainty Score)を付加した確定節からなる論理プログラムを用いて人間の行う不確実推論を表現する手法を提案しました．また，確定節に与えた確実性スコアの計算によってBayesian Networkにおける確率伝播アルゴリズム(Belief Propagation Algorithm)と同等の振る舞いを表現可能であることを示しました．

節論理のグラフィカルモデル

節論理とは論理積標準形で表現された論理式を扱う論理体系であり，古くから研究されています．一方，グラフィカルモデルは離散構造を表現する一つの手段であり，ベイジアンネットワークやマルコフネットワークなどに代表されます．近年，論理における性質をグラフィカルモデルと対応づける研究が注目されていますが，既存の研究では論理の推論プロセスを十分に把握できているとは言えません．本研究では，節に現れる各原子式の，節に対する寄与率の違いに注目し，論理とグラフィカルモデルに関する研究に一つのフレームワークを提供します．

最近の論文

[6-1]	Ikeda, M., Nishino, M., Doi, K., Yamamoto, A., Hayashi, S. : Semantics of a graphical model for representing hypotheses and a system supporting management of hypotheses, Proceedings of the Fifth International Conference on Knowledge, Information and Creativity Support Systems (KICSS2010), 159-166, 2010.
[6-2]	Masaaki Nishino, Madori Ikeda, Akihiro Yamamoto : Integrating Probabilistic Reasoning and Logic for Expressing Human Inference with Uncertainty, 1st International Workshop on Advanced Methodologies for Bayesian Networks (AMBN 2010), 2010.

代数学においては，多項式環イデアルが有限基底性を持つことはよく知られていますが，この事実は正データからの極限同定による形式言語の学習可能性の特別な場合であることが明らかになっています．そこで，学習可能性の方が有限基底性よりも詳細な条件分析が行われていることから，学習可能性の条件を基準にして，抽象代数の備えるべき性質を分類しました．その発展として，極限同定における学習の複雑さの理論を用いて，従来よりも大きな超限順序数に意味を与えることに成功しました．さらに，代数学ではあまり考察の対象とはなっていませんが，形式言語の学習ではよく考察の対象となっている「有界集合和」を，多項式環イデアルに適用し，その性質を明らかにする研究も行なっています．

(研究プロジェクト: 学術振興会基盤研究(A))

最近の論文

[7-1]	de Brecht, M., Kobayashi, M., Tokunaga, H., Yamamoto, A. : Inferability of Closed Set Systems From Positive Data, New Frontiers in Artificial Intelligence (Lecture Notes in Artificial Intelligence 4384), Springer, 265-275, 2007.
[7-2]	de Brecht, M, Yamamoto, A : Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data, Theoretical Computer Science, 411(7-9), 976-985 , 2010.
[7-3]	de Brecht, M, Yamamoto, A : Topological properties of concept spaces (full version), Information and Computation, 208(4), 327-340, 2010.
[7-4]	Kameda, Y., Tokunaga, H. , Yamamoto, A. : Learning Bounded Unions of Noetherian Closed Set Systems Via Characteristic Sets, Proc. ICGI 2008, LNAI 5278, 98-110, 2008.
[7-5]	Kameda, Y., Yamamoto, A.: Mining Closed Weighted Itemsets for Numerical Transaction Databases, Proc. of JSAI-isAI 2011 Workshop ALSIP, 197-210, 2011.

(可算な)集合、順列、グラフなどの離散的な対象の上の最適化問題は、その多くがNP困難やさらに難しい問題クラスに属すことが過去の研究で明らかにされています。 大学の一般的な講義における「計算量理論」では、Cook-Levinの定理を代表とするNP完全性の理論に基づいて問題の難しさを議論します。この文脈では、「入力サイズ」に対して多項式時間で動作するチューリング機械の存在を持てば「容易な問題」と定義され、NP完全問題はP = NPでない限り「容易ではない問題」と分類されます。 そのような問題へのアプローチとして、パラメータ化アルゴリズム、指数時間厳密アルゴリズム、近似アルゴリズムなどの代表的な手法が知られています。

当研究室では、伝統的な問題だけに限らず、機械学習やデータマイニングなどの研究中に生じる困難な問題に対し、これらの理論的なアプローチに加え、SATや整数計画法などの高速なソルバを用いた解法の研究も行なっています。

パラメータ化アルゴリズム・パラメータ化計算量理論

パラメータ化計算量理論では、問題に対して「入力サイズ」を2次元的に捉え、「入力サイズ」と「パラメータ」のふたつの値を考えます。 前述の通り、P = NPでない限りNP困難問題を解く「入力サイズ」に関する多項式時間アルゴリズムは存在しないが、ふたつの値をを考慮するとこで新たな計算量理論(パラメータ化計算量理論)が構築されます。 例えば、入力サイズnとパラメータkに対し、O(2^kn) 時間で動作するアルゴリズムは、「入力サイズ + パラメータ」に関する多項式時間アルゴリズムではないが、パラメータkが小さい時に、高速に動作することが期待できます。 このような計算時間のアルゴリズムをもつ問題を固定パラメータ容易と呼び、古典的な計算量理論ではあまり扱って来なかったNP困難な問題に対する「容易さ」の研究を行なわれています。

指数時間厳密アルゴリズム

「この問題は指数時間かかるから解けない」という言説を見かけることがありますが、本当にそうでしょうか？ 伝統的な計算量理論における「容易な」問題は多項式時間で動作する問題であり、入力サイズnに関してO(n¹⁰) 時間で動作するアルゴリズムしか知られていない場合でも容易な問題です。 一方で、O(1.01ⁿ) 時間で動作するアルゴリズムが知られていない問題は「解けない」問題なわけですが、現実的に動作する入力サイズの範囲で考えれば、後者の方が高速なアルゴリズムです。 指数時間厳密アルゴリズムの研究は、指数時間で動作するものの、問題の構造がどれだけ小さい指数関数のアルゴリズムを可能にするかを探索します。

近似アルゴリズム

上ふたつのアプローチが「厳密解法」、つまり最適解を求める解法であるのに対し、近似アルゴリズムの研究ではある程度解の質を妥協することで高速なアルゴリズムの設計を目指します。 ただし、ここでいう「妥協」とは理論的に保証された範囲内でなければなりません。そのため、様々なメタヒューリスティックスなどの手法とは異なります。

最近の論文

[8-1]	久保田稜，小島健介，小林靖明，山本章博：可換マッチング問題の固定パラメーター容易性に関する研究 ．人工知能学会，第112回人工知能基本問題研究会, 2020.
[8-2]	Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone, Akihiro Yamamoto: Algorithms and hardness results for the maximum balanced connected subgraph problem. COCOA 2019.
[8-3]	Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, Ryuhei Uehara: On the complexity of lattice puzzles. ISAAC 2019.
[8-4]	Eto Hiroshi, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi: Parameterized Algorithmis for Maximum Cut with Connectivity Constraints. IPEC 2019.
[8-5]	Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki: An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number. IWOCA 2019.
[8-6]	小林靖明，曽根大雅，土中哲秀：グラフの2等分割問題に対するアルゴリズムと計算複雑性．情報処理学会 第175回アルゴリズム研究会, 2019.
[8-7]	Eunpyeong Hong, Yasuaki Kobayashi, Akihiro Yamamoto: Improved Methods for Computing Distances between Unordered Trees Using Integer Programming. COCOA 2017.
[8-8]	Masaaki Nishino, Kei Amii, Akihiro Yamamoto: On the Sizes of Decision Diagrams Representing the Set of All Parse Trees of a Context-free Grammar. AMBN 2017.

本研究では、関係データを表現する二値行列からのコミュニティ抽出を目的とした 新たな双クラスタリング手法を提案しました。 コミュニティ抽出とは,膨大なデータから同 じ特徴を共有するグループを抽出することであり、 二値の関係データは二部グラフや二値行列として表現することができます。

これまでにグラフや行列からのコミュニティ抽出のためのクラスタリング手法が様々に研究されていますが、 クラスタリング手法の有効性は対象としているデータやクラスタの目的に依存するため、 それらは本研究で対象とする「公共事業入札」における関係データに適さないという欠点がありました。 そこで本研究では二部グラフの密度と非負値行列因子分解による特徴抽出に着目して、 あらたに双クラスタリング手法を提案しました。

これは入札データの特徴として 「参加業者にコミュニティを含まない案件が入札データに含まれている」 「コミュニティを参加業者に含む案件において、コミュニティ外の入札参加業者数が非常に少ない」 という二点があり、この仮定を利用した手法です。 提案手法は、明示的なクラスタ構造を持つランダムグラフを用いて、 正規相互情報量 (NMI) と二部グラフ Modularity を測定し、 実験の結果クラスタ構造を持たない部分グラフが多く含まれているグラフに対して、 提案手法は既存手法よりも高い NMI を示しました。 また、現実の入札データからのコミュニティ抽出性能を評価するために 談合の可能性を直感的にとらえやすくするような指標として落札率を用いて実験を行い、 既存手法は非常に密度の低いコミュニティを多く抽出したのに対し、 提案手法は密度が高くかつ平均落札率の高いコミュニティをより多く抽出することに成功しました。

本研究では，正例からのGold型学習における言語の非有界和のクラスが 学習可能なための十分条件に関した研究を行いました。 正例からのGold型学習は計算論的学習の分野で提示された抽象的な学習モデルであり、 形式言語族を中心に多くの学習可能なクラスについて研究されております。

本研究の中心的概念は精密化演算子と呼ばれるものです。 精密化演算子とは，元々はShapiroが提唱した論理プログラムを合成して 新たな論理プログラムを作成するための手続きであり、 学習者は，例に無矛盾な論理プログラムを枚挙ではなく論理プログラムの合成によって探索する ことを行います。 過去に大内らは精密化演算子を正例からのGold型学習に導入し， 正例からのGold型学習において言語族の学習可能性を保証するための精密化演算子を用いた十分条件を与えました。 本研究ではそれをさらに発展させ、精密化演算子を用いた正例からのGold型学習モデルを用いて， 言語の非有界和が学習可能であるための十分条件を与えることに成功しました．

Web上のニュースや，SNS上での個人の発言など，自然言語によって書かれているデータが広く見られるようになりました．自然言語文書は数値データとは異なった特徴をもつため，特別に自然言語を対象とした機械学習・データマイニング技術の開発が行われています．そこで本研究では，自然言語処理において通常用いられるN-グラムではなく，近年広く使われているLDAにより (図1)，文章からトピックヒストグラムを取得します．LDAとは，自然言語文書から，その文書がどのようなトピックで書かれているのかを学習する手法です．こうして計算したヒストグラムを文章間で比較することにより (図2)，テキストのクラス分類を行います．本研究では特に，距離学習 (metric learning) の分野において近年開発されたGround metric learningと，ヒストグラム間の距離としてTransportation distanceを利用することで，様々なクラス分類手法とくらべて遜色のないクラス分類精度を達成しました．

日本語において，文の述語項構造に注目することは自然言語処理， とりわけ意味解析にとって有効であるとされています． 述語項構造とは，文中の述語と項からなる構造で，項とは格助詞と名詞の組のことをいいます． 例えば文1からは以下の2つの述語項構造が得られます．

• 文1: 中臣鎌足らが蘇我入鹿を暗殺し蘇我氏を滅ぼした
• 述語項構造1: 暗殺する (ガ格: 中臣鎌足, ヲ格: 蘇我入鹿)
• 述語項構造2: 滅ぼす (ガ格: 中臣鎌足, ヲ格: 蘇我氏)

本研究では，述語項構造を利用して文書の内容が正確であるかを評価する手法を提案しました． 具体的には，述語項構造を用いて文を述語，主語，目的語，時間，理由，その他の6属性によって解析し，対象とする文が正解の文に対して正確であるがどうかを判定します． 提案手法を用いて，Wikipedia内の日本史上の事件57項目について，歴史事典を正解例とした評価を行った結果，本手法は人手による文書評価に対して再現率約49.1%，精度約93.4%の性能であることを確認しました．

物語など大規模な文書の解析では，大域的な特徴量である文書構成を利用することが考えられます． 民話学者Proppは，物語の構成を登場人物の行為として捉えるために，「戦い」，「勝利」など，合計で32種類の「機能」と呼ばれる概念を考案しました． 物語を「機能」の列と見なすことで，物語の情報学的な解析が可能になることが予想されます． そこで本研究では，物語から機能列を抽出する手法を提案しました． 具体的には，物語を文の列とし，構文解析を用いて，文を登場人物，動詞，文構造からなる特徴ベクトルに変換します． そして物語を変換して得られる特徴ベクトルの列を機能の列に変換することで，目的である機能列を抽出します． この際，物語上の前後のつながりを考慮する為に，特徴ベクトルの列から機能列への変換を系列分類問題と捉え，Conditional Random Fieldを用いた学習を行いました．

これまで画像に対するデータマイニングでは，信号処理に基づく手法が一般的でした．そこで，画像の部分領域を木構造で表現することで，離散的な観点から画像データマイニングへアプローチしました．具体的には，画像の部分領域検索の高速化手法を提案し，フラクタル圧縮とデータマイニングに応用しました．まず，検索の性能評価のためにフラクタル圧縮を用いて，高速化を確認しました．さらに，画像間の類似度を，頻出な部分領域によって測ることを提案しました．この問題を，木構造上の頻出パス発見問題に還元することで，類似度測定を実現しました．

文字を計算機で扱う研究は，OCR (Optical Character Recognition) を代表とする文字認識技術がよく知られている．文書画像に対する文字列の検索という目的において，OCRは字種・字体が既知である場合には有効であるが，劣化文書や手書き文字，未知の言語の文字には不適である．この問題に対して，OCRのように文字認識は行わず，直接，画像として扱う文字列画像検索がある．また，機械学習の分野において，学習者が効率的に解を学習するための手法である質問学習や，過学習を軽減するメタアルゴリズムであるAdaBoostが知られている．そこで我々は文字列画像検索のアルゴリズムに質問学習とAdaBoostを組み合わせることで検索効率の向上が見込めることを示した．