Inductive logic Programming 2011論文集より

前回はILP2010について述べた。今回は、2011年7月31日から8月3日まで、英国のCumberland Lodgeにて、Imperial College LondonのDepartment of Computingの後援のもと開催された。ILP2011について述べる。

ILP 2011は、1991年の第1回ILPワークショップから20年の節目を迎え、グレート・ウィンザー・パークのカンバーランド・ロッジで開催された。この間、ILPカンファレンスは、論理ベースの機械学習に関する研究の第一人者として発展してきた。第21回帰納論理プログラミング国際会議（ILP2011）のプロシーディングスの形式は、これまでの会議と同様であり、特にILP2006で用いられた形式に近いものとなる。サブミッションは2段階に分けて依頼されている。第1フェーズでは、6ページのショートペーパーを作成し、カンファレンスで発表するとともに、カンファレンスに先立ち、カンファレンスウェブサイトに掲載されている。第2段階では、査読者がロングペーパー（最大15ページ）を投稿する論文を選択されている。これらの論文は、同じ査読者によって評価され、ジャーナルの特集号とプロシーディングスに掲載する論文を決定した。

第1期では66本の論文が投稿された。各論文は3人の審査員によって審査された。このうち31件が長編論文として招待された。長編論文のうち、5編が機械学習ジャーナル特集号に、24編がプロシーディングスに採用された。また、PCレフリーにより、応用賞（シンジェンタ社主催「Michie ILP Application Prize」）と理論賞（機械学習ジャーナル社主催「Turing ILP Theory Prize」）に1件ずつ推薦された。プロシーディングスの論文は、ILPの理論、実装、確率的ILP、生物学的応用、部分群発見、文法推論、関係カーネル、ペトリネット学習、空間学習、グラフベース学習、行動モデルの学習など、現在のILP研究の多様性と活力を象徴しているものとなった。

ILP 2011は、今年は多くの技術論文の発表に加え、Hector Geffner氏、Richard Sutton氏、Toby Walsh氏という著名な人工知能研究者による招待講演が行われた。

Invited Talks

プランニングとは、次に行うべき行動をモデルから導き出す、モデルベースの自律行動へのアプローチである。プランニングの主な課題は、非決定論やフィードバックを考慮するかどうかに関わらず、すべてのモデルが最悪の場合、計算不可能であることです。しかし、ここ数年の間に、様々な環境下で効率的に計画を作成できるアルゴリズムが開発され、大きな進展があった。これらの開発は、一般的な推論技術や変換を定式化し、利用することに関係するものである。本講演では、個々の計画インスタンスを解くのに有効であることが証明されている推論技術をレビューし、完全な計画領域を解くための学習手法と変換の使用についても議論する。前者は、計画の探索を導くヒューリスティック関数の自動導出や、有用な行動やランドマークの同定を行うものである。後者では、一般化された方針の導出や、初期状況や物体数の変化に対応可能な有限状態制御の導出などの手法がある。また、学習が計画に利用できる別の方法と今後の課題についても述べる。

知能とは、非公式には「多くのことを知り、その知識を柔軟に使って目標を達成できること」と定義できる。この意味で、知識がインテリジェンスの中心であることは明らかである。しかし、知識とは何か、知識に意味を与えるものは何か、知識を効率的に獲得し活用する方法は何か、についてはあまり明らかではありません。本講演では、このような古くからある疑問について、現代の経験に照らして（特に強化学習における最近の研究に照らして）再検討を行う。このような問題は、哲学的、理論的な重要性だけでなく、現代の知識ベースシステムの実用性に直接影響する。知識ベースが大規模かつ多様になると、扱いにくく、変更が困難でもろくなる傾向がある。

知識集約型知的システムにとって重要な問題は、「何が知識を正しく保つのか」ということであり、これまでは基本的に3種類の回答があった。1）人間-人間の専門家が知識を理解し、それが彼らの信念と一致することを保証する、2）内部一貫性-システムがその知識が一致することをチェックし、矛盾を取り除く、3）データへの接地-システムが何らかの方法で知識を外部データと比較し、データに一致するように必要に応じて変更する、です。これらはすべて、正しい知識を維持するための有効な方法であり、しばしば有用である。しかし、実際には、正しい知識を維持するために人に頼るという方法が主流であり、内部一貫性のチェックで補完されてきた。この方法は、既存の人間の専門知識を活用するのに適していますが、人に依存するため、非常に大規模な知識ベースへの拡張性には大きな制限があります。このアプローチの本質は、知識は本質的に公的なものであり、（知的システムとは別の）世界の状態を記述し、少なくとも人々が潜在的にアクセス可能であるということである。これは公共知識アプローチと呼ばれるかもしれません。

本講演では、公的知識アプローチに代わる、知識をデータに基づかせることで正しく保つアプローチについて考察する。データとは、人間が介在しない知的システムの日常的な運用で得られる通常のデータのことである。この場合、システムは自律的に知識を修正・学習することができ、非常に大規模な知識ベースへの拡張が可能になるため、最も関心の高いケースです（Sutton 2009, 2001参照）。もしシステムがロボットであれば、このデータは単にセンサーを通して利用可能なあらゆるデータとその運動動作に関するものである。このようなセンサー運動データに基づく知識は、公的な意味を持たないかもしれません。このような感覚運動的アプローチにおける知識は、本質的に私的であり、個人的なものである。

制約は、制約プログラミング以外のパラダイムでも活用できる。特に、強力なグローバル制約は、しばしば小さなプリミティブに分解することができ、これらの分解は、問題についての高度な推論を実行する複雑な伝播アルゴリズムをシミュレートすることができる。我々は、命題充足性（SAT）、疑似ブール（PB）解法、整数線形計画法（ILP）、アンサーセット計画法（ASP）における制約の利用を例として、このアプローチを説明する。

本論文では、与えられたPRISMプログラムのパラメータに対する事後分布を近似する方法を紹介する。分布は1データポイントずつ更新される逐次的なアプローチがとられる。このため、データが時間経過とともに到着するオンライン学習にも適用可能である。この方法は、事前分布がディリクレ分布の積の混合である場合に適用可能である。この場合、真の事後分布は、非常に多くのそのような積の混合物となる。近似はディリクレ分布の積を結合することにより行われる．この近似の品質に関する解析が行われる．このアプローチは計算負荷が大きいため、この方法は論理型プログラミング言語Mercuryで実装されている。隠れマルコフモデルを用いた初期結果を示す。

関係確率モデルと同様に、関係嗜好モデルの必要性は、複数の、異種 の、そして豊かに相互接続された対象を含む実世界のアプリケーションに おいて自然に生じるものである。一方では、関係嗜好は人間のユーザが表現するのに自然な文に表現される必要がある。一方、関係嗜好モデルは、推論と学習の扱いやすい形式をサポートする構造を備えている必要がある。本論文では、条件付き選好関係ネットワーク(CPR-net)の枠組みを紹介する。これは、一般的なCP-netの精神を維持しつつ、ceteris paribusセマンティクスを用いて自然な方法で関係選好を表現するものである。本論文では、非周期的CPR-netが、最適化および順位付けタスクのための扱いやすい推論をサポートすることを示す。さらに、オンライン学習モデルにおいて、木構造CPR-netは最適化タスクとランキングタスクの両方から効率的に学習可能であることを示す。この結果は、大規模な映画推薦データセットに対する実験により確認された。

ProbLogはPrologの確率論的拡張である。ProbLogの意味論に基づく厳密な推論は複雑であるため、機械学習の多くの応用分野では近似的な推論が必要である。しかし、現在のProbLogの近似推論アルゴリズムでは、大量の証明を扱う必要があるか、低い近似誤差が保証されていない。本論文では、これらの欠点に対処する新しい近似推論アルゴリズムを紹介する。このアルゴリズムは、ユーザが指定したパラメータkが与えられたとき、最大k個の証明に基づいて問い合わせの成功確率を近似し、計算された確率pが(1 – 1/e)p∗ ≤ p ≤ p∗ (p∗ は任意のk個の証明の集合に基づいて計算できる最高の確率)であることを保証するものである。

近年、リンクと属性の両方に関する確率的パターンを表現する生成関係モデルに関心が集まっている。関係データの主要な特徴は、ある述語の値がしばしば関連する実体の同じ述語の値に依存することである。本論文では、再帰的な依存関係に対してよく定義される擬似尤度尺度と、論理プログラミングの層別化という2つの重要な概念を利用した、有向関係モデルの学習に対する新しいアプローチを示す。ベイズネットによる再帰的依存関係のモデル化では、学習の複雑性を増大させる冗長なエッジが問題となる。我々は冗長性を排除した1次ベイズネットの新しい正規形を提案し、層別化を仮定した場合、この正規形の制約がモデル化能力の損失を伴わないことを証明する。これらの制約をKhosraviらの学習・結合アルゴリズムに組み込む。このアルゴリズムは、関係データに対する命題ベイズネット学習者の成績を向上させる、最先端の構造学習アルゴリズムである。Emprical評価では、我々のアプローチと無向モデル（Markov Logic Networks）による再帰的依存関係の学習とを比較した。ベイズネットアプローチは桁違いに高速であり、より多くの再帰的依存関係を学習するため、より正確な予測につながる。

帰納論理プログラミングは、モデル検査によって特定された誤りを修正するための自動的なサポートを提供するために使用され、その結果、関心のある領域内で意味のある仮説を学習するための関連するコンテキストを提供することができる。このように、モデル検査と帰納論理プログラミングは、両者の統合によって 得られるものが多い、2つの補完的なアプローチと見なすことができる。本論文では、このような統合のための一般的なフレームワークを提示し、その主な特徴について議論し、そのアプリケーションの概要を紹介する。

論理プログラミングと確率を統合した言語を用いる確率的帰納論理プログラミングの分野への関心が高まっている。これらの言語の多くは分布意味論に基づいており、近年、これらの言語のパラメータ（PRISM、LeProbLog、LFI-ProbLog、EMBLEM）あるいは構造とパラメータの両方（SEM-CP-log）を学習するシステムが様々な著者によって提案されています。例えば、EMBLEMは期待値最大化法を用いており、期待値は二項決定図上で計算される。本論文では、”Structure LearnIng of ProbabilistiC logic progrAmS with Em over bdds “のためのアルゴリズムSLIPCASEを提案する。SLIPCASEは、データの対数尤度をガイドとして、注釈付き論理和（LPAD）の言語空間においてビーム探索を行う。理論改良の対数尤度を推定するために、EMBLEMの期待値最大化反復を限られた回数だけ実行します。SLIPCASEは3つの実世界のデータセットでテストされ、SEM-CP-logicおよびLearning using Structural Motifs（マルコフ論理回路網のためのアルゴリズム）と比較されました。その結果、SLIPCASEは精度-再現率およびROC曲線の下で、より高い面積を達成し、よりスケーラブルであることが示された。

本論文では、数値属性を含むリレーショナルデータベースにおけるサブグループ発見のためのアプローチを提案する。このアプローチは、入力リレーショナルデータベースに対する一次クエリのマッチングの結果得られる置換集合から構築されるヒストグラムのバンプを検出することに基づくものである。本アプローチは7つのデータセットで評価され、解釈可能なサブグループが発見された。学習分割からテスト分割までのサブグループの生存率は実験データセットによって異なるが、少なくともそのうちの3つでは非常に高い。

この論文では、回答集合プログラミング（ASP）における帰納論理プログラミング（ILP）システムの設計と、より一般的には両者の統合の問題について論じる。我々は、学習問題をASPプログラムとして定式化する方法を示し、好ましい仮説を導き出すために、最新のソルバーの最適化機能をどのように適応させるかについて詳細を提供する。

本論文では、グラフマイニングで一般的に用いられるグラフ同型演算子に対して、AC-projectionと名付けられた新しい投影演算子を提示し、良好な複雑性特性を示す。我々は、探索空間のサイズと構造、および、投影演算子の実用的な特性を研究する。これらの特性により、単純な局所演算を用いた特化アルゴリズムが得られる。そして、発見されたパターンの品質を大きく損なうことなく、あるいは大きく損なわずに、重要な性能向上を達成することができることを実験的に証明する。

我々は、複雑な時空間ナラティブを推論するためのインターリーブ帰納的アブダクティブモデルを提案する。帰納論理プログラミング(Typed-ILP)は、観測データからの一般化により領域理論を学習するための基礎として用いられ、一方、アブダクティブ推論は、シナリオと物語補完によるノイズデータ補正に用いられ、これにより、意味的に意味のあるイベントモデルを得るための帰納的学習を改善するものである。我々はこのモデルを、航空機の到着、ドッキング、出発などの物流プロセスを同時に監視する6台のカメラからの15回のターンアラウンドのビデオデータと、約2500のヴィネットで制定された20の動詞のデータセットからなる空港領域に適用した。また、提案するモデルは、空間、イベント、動的な時空間現象に関する常識的な推論と活動認識における定量的な技術とを結びつけるための青写真を提供する。

本研究では、マルチリレーショナルデータベースの時間的パターンを探索するのに適したILPベースのフレームワークであるXMuSerの最適化版を紹介する。XMuSerの主なアイデアは、シーケンスの形で時間的パターンを学習する効率的な方法である頻出シーケンスマイニングを利用することである。XMuSerフレームワークの効率性は、時間データの新しいコーディング方法と予測的なシーケンスマイニングの使用に基づくものである。このフレームワークは、最も興味深いシーケンスパターンを選択し、新しいテーブルであるシーケンス関係にマッピングする。本フレームワークの最後のステップでは、ILPアルゴリズムを用いて、元のマルチリレーショナルデータベースと新しいシーケンス関係からなる拡大されたリレーショナルデータベースに対する分類理論を学習する。

我々は、3つの分類問題を取り上げ、それぞれを頻出、閉じた、最大という3つの異なるタイプの順序パターンに対応させることにより、我々のフレームワークを評価する。実験の結果、我々のILPベースのフレームワークは、ILPアルゴリズムの記述力とシーケンシャルマイニングの効率性の両方から利益を得ることができることがわかった。

「従来の」クラスタリングは、広義には、オブジェクトを、そのメンバー間で「類似」し、他のグループに属するオブジェクトとは「非類似」であるグループ（クラスタ）に組織化することを目的としている。これに対し、概念的クラスタリングでは、学習者が利用可能な記述言語とデータの基本構造がクラスタ形成を促進し、クラスタの理解しやすい記述を提供することで、解釈を容易にする。

我々は、一般的なk-medoidsアルゴリズムに基づく、多関係データ用の新しい概念的クラスタリングシステムを提案する。クラスタリングは一般的に、評価するのが簡単ではないが、いくつかのアプリケーションの実験結果は、有望な結果を示している。クラスタ情報なしで生成されたクラスタは、クラスタのメンバーの真のクラスラベルと非常によく一致した。さらに、クラスタについて理解しやすく意味のある記述を得ることができた。

本論文では、一階論理の一断片である一階論理決定木（FOLDT）のサブクラスの表現力を特徴付ける。具体的には、安全なFOLDTを用いることで、安全な存在文のブーリアン結合を正確に表現することができる。

本論文では、説明的帰納法における接続法正規形（DNF）での仮説計算の問題を検討する。これは通常のILPの設定である接続法正規形(CNF)、すなわち句の集合で仮説を得るのとは対照的である。我々は、DNF仮説を計算するための2つのアプローチと、いくつかの健全で完全なアルゴ リズムを紹介する。この問題は、自然に節理論からのアブダクションを含み、SATテクニックや素因数分解計算のような命題推論手法が利用できるモデルベース帰納推論と関連づけることができる。

アブダクションは、基本的な論理的推論（演繹、帰納、アブダクション）の一つであり、私たちの観察に対して最適な説明を導き出す。統計的アブダクションは、説明に対する確率分布を定義し、その確率によって説明を評価しようとするものである。確率と論理を組み合わせる方法として論理型確率モデル（LBPM）が開発されており、これによって統計的アブダクションを行うことができる。しかし、嗜好や頻度のような非決定的な知識は論理で表現することが難しいように思われる。ベイズ推論はこのような知識を事前分布に反映させることができ、その近似手法として変分ベイズ(VB)が知られている。本論文では、論理ベースの確率モデルに対する変分ベイズを提案し、提案した手法が論理回路と代謝経路の故障に関する帰納的説明の評価において効率的であることを示す。

空間情報を自動的に抽出することは、多くのアプリケーションを持つ挑戦的な新規タスクである。我々はこれを、自然言語から正式な空間表現へのマッピングに必要な情報抽出ステップとして定式化する。文はランドマーク、軌跡、空間指標を表す単語の間に複数の空間関係を生じさせる可能性がある。我々の貢献は、抽出タスクを関係学習問題として定式化することであり、そのために、最近導入されたkLogフレームワークを用いる。我々は、表現とモデリングの側面、我々のタスクにおけるkLogの柔軟性について議論し、現在の実験結果を示す。

ILPシステムProgolは、一つの例を複数の節に汎化することができない不完全なものである。この制限を本論文では単一節学習(SCL)と呼ぶ。しかし、Blumer boundによれば、Progolのような不完全な学習者は、完全な学習者よりも少ない探索量で高い予測精度を得ることができる。この問題は、未知の目的理論やその近似が不完全学習器の仮説空間に含まれるかどうかが明らかでない実問題に特に関係する。本論文では、システム生物学における2つの実世界アプリケーションを用いて、計算量は多いがシステムレベルの多項目仮説を導出できる完全多項目学習（MCL）法が必要であるかどうかを研究している。実験の結果、いずれの用途においても、MCLがSCLよりも有意に高い予測精度を持つデータセットが存在することがわかった。一方、MCLは、SCLの仮説空間内に目的仮説やその近似値が存在するため、常にSCLを上回るというわけでもない。

ILPでは、仮説発見を完全に行う手法の設計に多くの労力が費やされてきた。しかし、現実の応用において完全性が重要かどうかは明らかではない。本論文では、文法学習を単純化したものを用いて、完全な手法が不完全な手法の学習結果をいかに改善できるかを示す。実世界への応用には完全な手法が必要であると考え、⊤向理論共導という手法を導入し、これが正しい（すなわち健全かつ完全である）ことを示す。提案手法はILPシステムMC-TopLogに実装され、グラムマー学習とゲーム戦略学習でテストされました。MC-TopLogは効率的だが不完全なILPシステムであるProgol5と比較して、特に背景知識が著しく不完全な場合に高い予測精度を得ることができる。

本論文では、関係強化学習とアンサーセットプログラミングおよびイベントカルキュラスを統合するアプローチを紹介する。我々のフレームワークは、表現力豊かな形式言語で定式化された背景と事前知識を許容し、ASP-ソルバーによって生成されるソフトな、そして強制的な（サブ）ポリシーと（サブ）プランによって、学習プロセスの計算効率の良い制約を容易にする。この一環として、関係インスタンスベース学習に対する新しい計画ベースのアプローチを提案する。本アプローチの実証評価により、様々なベンチマーク設定において、学習効率と学習結果の大幅な向上が示される。

特徴項は、宣言型言語のオブジェクト指向機能を形式化するために理論計算機科学で導入された一階項を一般化したものであり、構造化機械学習アプリケーションにおける有用性から最近注目されているものである。素性項（ホーン節や記述論理などの他の形式的表現言語も同様）の主な障害は、包含などの基本的な演算が非常に高い計算量を必要とすることである。本論文では、制約プログラミング（CP）を用いて、包含、反統一、単一化をモデル化し、従来の方法よりも効率的にこれらの演算を解決する。

我々は、自分の行動の効果を予測できるようにするために、関係行動モデルを学習するエージェントを考える。このモデルは、STRIPSのようなルール、すなわち、現在の状態が前提条件のセットを満たす限り、与えられたアクションを適用したときに現在の状態で何が変化したかを予測するルールのセットで構成される。ここでは、与えられたアクションに対して複数のルールを関連付けることができるため、条件付き効果のモデル化が可能である。学習はオンラインで行われ、エージェントが行った行動から例が得られる。また、現在の行動モデルは、エージェントの行動から生じる予期せぬ効果によって矛盾が生じるたびに修正されるので、漸進的である。このモデルの形式は、標準的なプランナーの入力として使用することができる。

この研究では、学習ユニットIRALe 1は、i) 行動モデルの学習 ii) 行動選択 iii) 目標到達のための計画 を行うことができる統合システムに組み込まれている。エージェントは現在の行動モデルを用いて能動学習を行う。すなわち、モデルの修正を強制する状態に到達する目的で行動を選択し、モデルの精度を現実的に評価するために計画能力を使用する。

これまで、ILPによって同定された生体系の動的モデルのうち、最も表現力があり、理解しやすいものは定性的微分方程式（QDE）である。QDE表現は、定量的なODEを直感的かつシンプルに抽象化したものです。しかし、この表現には、シミュレーションにおいて偽の挙動を生成することや、並行処理、定量的情報、確率的性質を扱う方法がないなど、いくつかの限界があります。これらの問題は、古くからあるペトリネットの定性的表現にはほとんど存在しない。現在、生物系のペトリネットモデルが盛んに研究されているが、それはほとんど手作業で作られたモデルに関するものであった。本論文では、純粋および拡張ペトリネットが、論理的制約と線形項に対する制約の組み合わせを用いて遷移が定義されるシステムの特殊なケースとして表現できることを示す。データから純粋ペトリネットを同定するためのよく知られた組み合わせ的アルゴリズムと、含意の転置に関するILPの文献からの結果は、データと背景知識が与えられたときに、そのような遷移制約の最大集合を構築する基礎を形成するものである。そして、制約ソルバーを備えたILPシステムが、データと矛盾しない遷移制約の最小部分集合を決定するために使用される。これは、生体システム同定に特化したペトリネット学習器と比較していくつかの利点があり、そのほとんどは背景知識の使用から生じるものである。その結果 (b)確立されたネットワークモデルの再利用により、大規模システムのペトリモデルの階層的同定を行うことができる。 (c)アブダクションとデータに基づく正当化の組み合わせにより、ペトリネットの欠落部分の仮説を立てることができる。我々はこれらの利点を、よく知られた代謝ネットワークやシグナル伝達ネットワークで実証する。

本論文では、機械学習(Abductive ILP)により、生態学的データからもっともらしく、かつ検証可能な食物網を生成できることを実証する。このアプローチでは、これまでのアブダクティブILPの応用とは異なり、アブダクティブ述語である「食べる」は学習開始前に全く定義されない。また、仮説頻度推定（HFE）と呼ばれる、仮説空間をランダムにサンプリングした際の出現頻度に基づいて仮説的な「食べる」事実の確率を推定する新しいアプローチを模索する。クロスバリデーションの結果、確率を用いたトロフィックネットワークは、確率を用いないネットワークと比較して、高い予測精度を持つことが示唆された。提案したトロフィックネットワークをドメイン専門家が検証し、文献と比較した結果、多くのリンクが文献によって裏付けられていることが示された。特に、頻度の高いリンクは、文献で複数回参照されているリンクとよく対応していることが示された。また、新規の高頻度リンクが示唆される場合もあり、検証の可能性がある。

ヘッジキュー検出は、文にヘッジが含まれているかどうかを判定する自然言語処理（NLP）タスクである。これらの言語的工夫は、著者が自分の意見や発言を事実で裏付けていない、あるいは、裏付けできないことを示すものである。この二項分類問題、すなわち、事実に基づく文と不確実な文とを区別することは、最近になってNLPコミュニティで注目されるようになった。我々はカーネルベース学習のための新しい論理・関係言語であるkLogを用いて、この問題に取り組む。本発表では、不確実性検出が重要視されている分野の一つであるWikipediaの段落からなるCoNLL 2010ベンチマークデータセットでの結果を報告する。本手法は最先端のシステムと比較して、競争力のある結果を示した。

確率的帰納論理プログラミング(PILP)のILPに対する優位性を計算機学習理論的に評価することは行われていない。本論文では、射影に基づくPILPを提案する。射影に基づくPILPでは、射影関数を用いて、ILPデータセットから非可逆圧縮データセットを生成することが可能である。射影に基づくPILPがPACよりも少ない例数で済む条件を含む，複雑さの例を示す．また，確率的論理回路（Probabilistic Logic Automata）を機械学習するシステムCellistを用いて，ブラックジャック領域における射影型PILPの理論的境界を実験的に確認する．その結果，投影型PILPは理論値よりも低い予測誤差を示し，ILPよりも大幅に低い予測誤差を達成することができた．本論文は、ILPに対するPILPの優位性について、コンピュータ学習理論とそれに関連する実証的な結果の両方を記述した最初の論文であると考えられる。

CF-inductionは、完全な節付け理論において仮説を発見するための健全で完全な手順である。これは逆伴侶（IE）の原理に基づいており、ブリッジ理論の構築とその汎化という2つの手続きから構成されている。CF-inductionにおける汎化タスクの実現方法には、2つの可能性がある。一つはγオペレータと呼ばれる単一の演繹的オペレータを用いるもので、もう一つは最近提案された逆包含の形式を用いるものである。両者はCF帰納法の完全性を保持することが知られているが、その論理的関係や経験的特徴はまだ明らかにされていない。本論文では、両者の等価性を示すとともに、両者の探索戦略の違いを明らかにし、その結果、得られる仮説に大きな特徴が生じることが多いことを示す。

コグラフ（complement reducible graph）とは、単一頂点のグラフを出発点として、グラフの離散和集合と補集合の操作によって生成できるグラフのことである。コグラフはコンピュータサイエンスの多くの分野で登場し、盛んに研究されている。

本論文では、グラフ構造データに対する効果的なデータマイニング手法の開発を目的として、構造化された変数を持つ特殊なタイプのコグラフであるコグラフパターンと呼ばれるグラフパターン表現を紹介する。まず、コグラフパターンの多項式時間マッチングアルゴリズムを提示する。次に、与えられた正データを説明する最小限の一般化されたコグラフパターンを得るための多項式時間アルゴリズムを与える。最後に、コグラフパターンの言語クラスは、正のデータから多項式時間帰納的に推論可能であることを示す。

次回はILP2012について述べる。