Inductive logic Programming 2010論文集より

前回はILP2019について述べた。今回は、2010年6月27日から30日にかけてイタリアのフィレンツェで開催された第20回帰納論理プログラミング国際会議（ILP2010）の論文について述べる。

ILPカンファレンスシリーズは1991年に始まり、論理ベースの機械学習へのアプローチに関する国際的な一大イベントとなる。近年では、統計的学習や他の確率的アプローチとの融合が模索され、研究の幅が大きく広がっている。

第20回大会は、招待講演、一般講演、ポスターセッション、パネルセッションで構成され、今回初めてチュートリアルデイが設けらた。招待講演は、Michael Kifer氏、Avi Pfeffer氏、David Poole氏の3名です。講演の要旨は本誌に掲載されている。Gianluigi GrecoとFrancesco Scarcelloは “Structural Decomposition Methods “というテーマでチュートリアルを発表した。Volker Trespは “Multivari-ate Models for Relational Learning “についてのチュートリアルを発表した。Ivan Bratko, Luc De Raedt, Peter Flach, Katsumi Inoue, Stephen Muggleton, David Poole, and Ashwin Srinivasanは、最初の会議から20年後のILPの成功と将来の傾向を強調したパネルセッションに参加した。

プログラム全体では、16件の口頭発表と15件のポスター発表が行われた。口頭発表は16件、ポスター発表は15件で、いずれも拡張アブストラクトに基づいて選出されたものとなる。また、ILP2010で採択された論文の一部は、Lecture Notes in Artificial Intelligenceの本編およびMachine Learning誌の特集号として出版された。最初に提出された44の拡張アブストラクト（LNCS形式で8ページ）の中から、31の論文が会議で発表されることが決まった。各投稿は少なくとも3人のプログラム委員によって査読され、Easy-Chairのサポートによる公開査読モデルによって、プログラム委員全員（利害関係のある場合を除く）が追加コメントを読むことができた。採択された投稿のうち、5件は特集号に選ばれ、11件はロングペーパー（16ページ）、15件はショートペーパー（8ページ）としてプロシーディングスに掲載された。これらの論文は、会議終了後に作成されたものとなる。また、一部の採択論文の補足資料は、大会ウェブサイト（http://ilp2010.dsi.unifi.it/）から取得することができる。

以下に詳細を示す。

Abstracts of Invited Talks

近年、ルールシステム技術に対する関心は、それ自体として、あるいは既存のWeb標準との組み合わせとして、非常に高まっています。特に、セマンティックWebは、産業界だけでなく、学術的にもルールのための広大な競技場と見なされています。この新たな関心が、異なるシステム間でルールを交換するための最近のW3C Web標準であるRule Interchange Format (RIF) の開発の動機となりました[1-5]。RIFはその名前とは裏腹に、単なるフォーマットではなく、RIF方言と呼ばれる具体的なルール言語の集合体であり、互いに調和した新しいルールを定義するためのフレームワークでもある。これには、構文、意味論、XMLシリアライゼーションに関する正式な仕様が含まれます。

本講演では、RIFが知識表現と情報処理の主流にルールベース技術を再導入し、論理型プログラミングへの関心を再び呼び起こす大きなチャンスであることを主張する。まず、RIFの背後にある主要な原理を紹介し、この標準が関連するコミュニティに受け入れられた場合に出現する可能性のあるアプリケーションの風景について議論する。論理プログラミング、セマンティックウェブ、知識表現。また、論理プログラミングの過去を振り返り、将来どのようにRIFから恩恵を受け、RIFに貢献できるかを推測する。

確率的プログラミングは、プログラミング言語の力を使ってモデルを作成することを可能にし、モデルについての推論に汎用アルゴリズムを適用することで、確率的モデリングを容易にすることを約束するものである。我々は、実用性と使いやすさを考慮して設計された新しい確率的プログラミング言語Figaroを発表する。Figaroは、確率的関係モデルや、任意の制約を持つ無向性関係を持つモデルなど、他の言語では表現が困難であったモデルを自然に表現することができる。重要な特徴は、Figaro言語と推論アルゴリズムがScalaのライブラリとして組み込まれていることです。ケーススタディを通してFigaroの使い方を説明します。

本講演では、統計的関係解析AIやセマンティックウェブの進展を踏まえ、知識を創造する方法、発表された知識を評価する方法、そして人間の知識の総和を超える方法について概説した。真実の主張がある場合、その主張にはどのような証拠があるのかを問い、証拠のない主張は信じないのが合理的である。そのため、私たちは証拠を示すことができるデータを公開する必要があるのです。また、そのようなデータがあれば、そこから学ぶこともできる。本講演では、オントロジー、データ、確率的仮説・理論などを公開することで、いかに証拠に基づく信念を持つことができるか、また、その結果として、人間の知識の集積を超えた世界規模の心を持つことができるか、について概説する。世界のデータの多くは関係性であり、合理的な意思決定を行うためには確率的な予測を行いたい。したがって、確率的関係学習と帰納論理プログラミングは、セマンティックウェブの基礎となる必要がある。本講演では、このビジョンの背後にある技術と、残された相当な技術的・社会的問題について概説した。

本稿では、マルチインスタンス学習に基づく数値絞り込み演算子を紹介する。このアプローチでは、文節中の数値変数を扱うタスクは統計的なマルチインスタンス学習スキームに委ねられる。各節には、その節の数値変数を入力とするマルチインスタンス分類モデルが関連付けられている。節は貪欲に構築され、各改良は新しい数値変数を追加し、それらはマルチインスタンスモデルが既に知っている数値変数に追加して使用される。実験では、Wekaワークベンチで利用可能なマルチインスタンスラーナー（MI- SVMなど）を用いてこのアプローチをテストしました。これらの節は、SLIPPERのような標準的な被覆処理やルールの離散ブーストを越えて、マージン情報を利用できるブーストアプローチで使用される。本アプローチは、ヘキソース結合部位予測、薬理学的応用、変異原性予測の問題で評価された。3つのアプリケーションのうち2つでは、結合部位または薬物活性を特徴付ける3次元空間内の特定の特性を持つ点の配置を見つけることが課題である。節の論理部分は点とその特性を構成し、一方、マルチインスタンスモデルは点間の距離を制約している。このように、論理的学習と統計的学習を融合させた新しい数値的絞り込み演算子は、理論的にも、生化学的応用における結合部位やファーマコフォアの特性評価のための新しい手法としても興味深いものである。

視覚システムを高次の知識と推論で補強することにより、より豊かで構造化されたインフォーメーションを用いて、低次の視覚処理を改善することができる。本論文では、低レベルの構成要素間の空間的関係に基づいて、ストリートビューの概念的要素を区切るという問題に取り組んでいる。我々は構造化データを用いる。各概念は、構成要素間の空間的関係を表すグラフとして見ることができ、例えば、右、上、近くといった観点から見ることができる。我々は、画像の一部を既知の例と照合するために、論理的解釈間の距離に基づくアプローチを採用し、実画像を用いた実験的評価を提供する。

LPAD（Logic Programs with Annotated Disjunctions）は確率的帰納論理プログラミングのための有望な言語である。LPADの効率的な学習システムを開発するためには、高性能な推論アルゴリズムが不可欠である。既存のアプローチは、時間がかかりすぎたり、大きな問題では失敗したりする。本論文では、ProbLogのために開発された近似推論手法、すなわちk-bestとモンテカルロをLPADに適応させる。

k-bestは最も確率の高いk個の説明を特定することで問い合わせの確率の下限を求め、Monte Carloはプログラムの空間をスマートにサンプリングすることで確率を推定する。この二つの手法はcplint suiteに実装され、グラフを表す実データと人工データでテストされた。その結果、両手法は厳密なアルゴリズムよりも短時間で大きな問題を解くことができることがわかった。

確率論的論理型言語の形式では、非常に複雑な確率分布を定義することができる。この複雑さは、構造が固定され、学習がパラメータ推定に還元される場合でも、しばしば学習を困難にすることがある。本論文では、PRISMのパラメータに対する事後分布の近似を計算する近似ベイズ計算(ABC)手法を示す。ABCアプローチの鍵は、尤度関数を計算する必要がなく、観測データと候補パラメータ値によって生成された合成データとの「距離」が学習を駆動するために用いられることである。このため、ABCは、尤度関数が難解であるが合成データを容易に生成できるPRISMプログラムに非常に適している。このアルゴリズムは、簡単な問題ではうまく機能することが実験的に示されているが、より難しい問題で許容できる結果を得るためには、さらなる研究が必要である。

従来、ルール学習者は決定論的なデータから決定論的なルールを学習してきた。つまり、ルールは論理的な文として表現され、例とその分類も純粋に論理的なものであった。我々は、ルール学習を確率的な設定に改良し、例そのものとその分類を確率的なものにする。この設定は、関係ルール学習器FOILの原理と確率的PrologであるProbLogを組み合わせた確率的ルール学習器ProbFOILに取り入れられている。また、本アプローチの有用性を示すいくつかの実験についても報告する。

構造活性予測は、ケモインフォマティクスにおける最も重要なタスクの一つです。その目的は、一連の低分子化合物や薬剤の構造データが与えられたときに、関心のある特性を予測することです。理想的には、このタスクに取り組むシステムは、単に正確であるだけでなく、あるターゲットに関して最も差別的な構造要素を記述する、解釈可能な識別構造を特定できる必要がある。

本論文では、化学フラグメントの識別マイニングのための対話型ソフトウェアにおけるILPの適用を紹介する。特に、化学者が化学フラグメント中の興味深いパターンの探索をグラフィカルに制御することを可能にする分子可視化ソフトウェアとILPシステムの結合について説明する。さらに、環、カルボキシル、アミン、メチル、エステルなどの官能基などの構造情報が、どのように検索に統合され利用されるかを示す。

すべての遺伝子やタンパク質が関与している生物学的プロセスは、病気の治療法を設計するために不可欠な知識です。しかし、現在でも多くの遺伝子やタンパク質について、このようなアノテーションが知られていない。そのため、代謝経路、相互作用ネットワーク、タンパク質ファミリー、組織、疾患など、様々な種類のアノテーションを計算機で予測することが求められている。生物学的データは、遺伝子やタンパク質など、多くの基準でグループ化された固有の関係構造を持っています。このため、属性値表現を用いた場合、良い仮説を発見する可能性を妨げている。そこで、我々は関係データマイニング(RDM)を用いて、様々な種類の遺伝子やタンパク質のan-表記を予測するための汎用的なモジュール型マルチ関係フレームワーク(MMRF)を提案する。MMRFをヒトのタンパク質に適用し、疾患に関するアノテーションを行った結果、グループ知識（主にタンパク質-タンパク質相互作用ペア）が事前予測を改善し、特に精度-再現曲線下の面積を2倍にすることが確認された。

ProbLogは最近導入されたPrologの確率論的拡張である。本論文では、ProbLogに連続分布を指定する機能を追加し、ProbLogの厳密推論機構がそのような分布に対処するためにどのように修正されるかを示すことが重要な貢献である。この結果得られた推論エンジンは、区間計算と動的離散化アルゴリズムを組み合わせた効果的なソルバーとなる。

セマンティックウェブ（SW）データの主な特徴の1つは、不完全であることで知られていることです。よく知られている例として、友人の友人関係データセットがあります。あるメンバーはプライベートな情報や社会的な情報を網羅的に記録していますが、他のメンバーはプライバシーに関する懸念やその他の理由から、ほとんど何も知られていません。演繹的推論は存在論的背景に基づく事実的知識を補完するために用いることができるが、それでもなお、膨大な数の潜在的に正しい記述が発見されずに残っている。本論文では、統計的関係学習アルゴリズムを用いて、データの規則性を利用し、潜在的な関係や属性を予測することに焦点を当てる。結果として生じる高次元の疎なデータ行列を扱うには、多変量予測アプローチが最も適していることを主張する。統計的なフレームワークの中で、このアプローチは大規模なドメインにスケールアップし、高度にスパースな関係データを扱うことが可能である。本発表の主要な目標は、機械学習のバックグラウンドをあまり持たない人でも利用できる帰納的学習アプローチを定式化することである。本論文では、友人関係データセットを用いた実験結果を示す。

メタレベルアブダクションは、不完全なネットワークからミッシングリンクや未知のノードを発見し、観測のためのパスを完成させるものである。本研究では、メタレベルアブダクションの適用性を拡張し、正負両方の因果関係を持つネットワークを扱う。このようなネットワークは、シグナル伝達や代謝経路において抑制効果が重要である生物学など多くの領域で見られる。抑制効果を持つネットワークでの推論は必然的に非単調となり、アブダクションにおけるデフォルトの仮定を含む。我々は、メタレベルアブダクションにより、正負両方の因果関係や発明されたノードが一貫して生成されることを示す。メタレベルアブダクションの事例として、p53シグナルネットワークにおいて、新しいタンパク質で腫瘍を抑制し、損傷が発生したらDNA合成を停止するという因果関係のルールがアブダクションされた例を紹介する。

既存のILP（Inductive Logic Programming）システムは、C言語、Progolなど、さまざまな言語で実装されている。また、入力データの形式もシステムごとにカスタマイズされている。そのため、実験目的で利用する場合、システムおよび入力仕様の理解が必要となり、非常に面倒で時間がかかる。Weka [1]の精神に則り、我々はJavaで実装されたBET(Background + Examples = Theories)と呼ばれる関係学習ワークベンチを発表する。BETの目的は、ユーザ（初心者を含む）の学習曲線を短縮し、新しい関係学習システムの迅速な開発、および、既存のILPシステムの迅速な統合を促進することである。標準化された入力フォーマットにより、共通のデータセット上で様々な関係学習アルゴリズム の実験が容易に行える。

典型的な帰納論理プログラミングのベンチマークにおける例題の削減可能性について研究する．還元性の概念は、帰納論理プログラミングで仮説の還元によく用いられるθ-reductionに関連している。通常、例題はそれ自体では漸化式ではないのですが、仮説を構成する言語が固定されると、暗黙のうちに漸化式になることがよくあります。我々は、いくつかの実世界の分子データセットにおいて、データセット中の基底事実の数がほぼ半分になることを示す。さらに、このことがILPシステムAlephに与える影響についても研究している。

最近のいくつかの論文では、ILPがシステムバイオロジー問題に適用され、生物学的ネットワークの記述のギャップを埋めるために使用されている。本論文では、植物生物学の分野におけるこのタイプの2つの新しいアプリケーションを説明する。これらのアプリケーションは、植物系統の改良が作物開発のモデリングに有益である農薬業界にとって特に興味深いものである。これらのアプリケーションの背景知識は広範囲に及び、Ondexと呼ばれる新しいシステム（開発者BBSRC Rothamsted）を用いて、Prologフォーマットで公開データベースからデリベイトされます。この論文では、精度の向上と学習時間の増加を考慮し、この背景知識をどの程度含めることが有益であるかという問題を検討する。その結果、最大限の精度を得るためには、比較的浅い背景知識が必要であることがわかった。

多くのSRLモデルは、論理推論を重み付き充足可能性解として提起している。このため、LazySAT[8]のようなアプローチは、領域のスパース性を利用して、この問題に対処している。ここでは、知識ベース(Σ)を一次ホーン節の集合に限定した場合の効率性を調査する。ホーン節における充足可能性の探索空間を刈り込むアルゴリズムを提案し、刈り込まれた空間に最適解が存在することが保証されることを証明する。このアプローチは、モデルが存在する場合は多項式時間で、そうでない場合は重みが与えられた場合に最も可能性の高い解釈を見つける。我々のアプローチが探索空間のサイズを大幅に減少させるという実験的証拠を提供する。

WARMRで確立された問題を通じて、多関係パターンマイニングのアルゴリズムを提案する。パターン空間が大きいという組み合わせの問題を克服するために、もう一つのアルゴリズムMAPIXは、パターンをプロパティと呼ばれる基本パターンの組み合わせに制限している。プロパティは、例題に現れるリテラルの集合として定義され、拡張された属性-値形式である。MAPIXの利点は、例題に出現するパターンの断片からパターンを作ることである。例題に登場しない多くのパターンはテストされない。MAPIXはパターンの範囲が明確であり、効率的にパターンを列挙できるが、多くのパターンが範囲外である。提案アルゴリズムでは、この利点を生かしつつ、特性の組み合わせ方法を拡張している。このアルゴリズムは、例題に登場する性質をそのまま組み合わせるもので、構造保存型組み合わせと呼んでいる。

本論文では、非可逆的帰納論理プログラミングプログラムHYPER/Nについて、主にノイズ処理と学習向上のための他のメカニズムに焦点を当てて説明する。HYPER/Nを用い、人工的にノイズを加えた合成気象データ、および、レーダー雨画像とシナプスデータから雨の動きを予測する学習のための実天候データを用いた実験を行う。

通常の帰納論理プログラミング(ILP)では、一階再帰理論の学習は困難であるが、多くのアプローチがなされている。高階論理(HOL)を用いることにより、このような課題に対して再帰節の学習を必要としない。HOLの表現力を利用した高階論理学習(HOLL)は、一階論理学習(FOLL)に比べて問題の学習能力の向上が期待できる分野の一つである。本発表では、昨年のポスター発表[15]で紹介したILPシステムProgolとHOL形式λPrologを適応したHOLLシステムλProgolの最初の実用的な実装を紹介します。特に、学習例がデータサイズに対して小さい場合、λProgolは一階再帰理論の学習において、標準的なProgolより優れた予測精度を持つことを実証する。

関係強化学習の枠組みにおいて、与えられた状況下での行動の結果を予測するために、行動モデル（または遷移関数の近似値）を学習するアルゴリズムを提案する。このアルゴリズムは、ノイズの多い環境において、データ駆動型ループに従って一次規則を漸進的に学習する。現在の行動モデルに矛盾する新しい例が提示されるたびに、モデルは（汎化や特殊化によって）修正される。ノイズのない環境で動作する我々のアルゴリズムの前バージョンとは対照的に、我々は各ルールに付随する多くの指標を導入し、改訂を直ちに行うべきか、遅らせるべきかを評価できるようにする。また、通常のRRLベンチマークを用いた実証的な評価も行う。

エンタイルメントは計算論理学の重要な問題であり、特に帰納論理プログラミング(ILP)のコミュニティにとって重要な問題です。解決ヒューリスティックや、最近ではサブサンプション・エンジンが開発されましたが、 ほとんどのILPシステムでは、PrologのSLD解決のための左から右への深さ優先探索選択関数を使って、 仮説網羅性テストが実行されているだけです。

我々は、SLD解決のために、最小述語領域(SPD)と最小変数領域(SVD)の2つの選択関数を実装し、サブサンプションエンジンSubsumerを開発しました。これらの包含関係エンジンはILPシステムProGolemに完全に統合された。

これらの4つの包含エンジンの性能を、代表的なILPデータセットで比較した。予想されたように、確定的なデータセットでは、Prologの内蔵された解決法 は、他の追随を許さないものでした。しかし、わずかな非決定性が存在する場合、その性能はすぐに低下し、洗練された含意項エンジンが必要とされます。

この論文で紹介する研究は、次のような疑問が動機となっている。節の汎化順序とrefinementなどの関連概念をどのように確率的探索に適応させることができるか？この問題を解決するために、我々は確率的絞り込み演算子の概念を導入し、確率的絞り込み検索と呼ばれるフレームワークを適応する。本論文では、ある節の確率的精密化を、節の集合に対する確率分布として導入する。この確率分布は確率的ILP探索における事前分布と見なすことができる．我々は，確率的絞り込み探索の特性を，よく知られた2つのマルコフ的アプローチとして研究する．1) ギブスサンプリング法、2) ランダムヒューリスティック探索。確率的絞り込み探索は，Gibbsサンプリングアルゴリズムとして，仮説空間から事後分布に従ったランダムな標本を繰り返し生成する．我々は、最小のサンプルサイズを設定することで、各反復において高い確率で矛盾のない節が生成されることを示す。我々は、確率的精密化演算子をランダムヒューリスティック探索の枠組みで研究し、この枠組みを用いていくつかのILPシステムにおける確率的探索法を特徴付ける。また、確率的絞り込み検索の特殊なケースとして、絞り込み演算子が最下位節に対する包含順に関して定義されている場合についても研究する。また、ILPシステムGolemやProGolemのように、確率的lgglike演算子を使用することの相対的な利点を説明するためのいくつかの洞察を提供した。

山火事は、世界の広い地域の生態系と経済に重要な影響を与える可能性があります。その影響を軽減するためには、効果的な予防技術が基本となる。そのような先制的な方法を設計するためには、火災のリスクを高める要因、特にその要因に介入できる場合について、深く理解する必要がある。これは、山火事の発生を最小限に抑える景観の生態的バランスの維持のためのものである。1つは景観のモザイクを記述し、その用途の観点から特徴付けるもの、もう1つは数年間に山火事が発生した多角形領域を記述するものである。我々の帰納法は、ベクトル地理データの論理項表現上で動作し、空間述語を使用して検索空間を探索するもので、Spatial-Yapのフレームワークとその多次元インデックス化およびタブリング拡張を活用する。論理ベースの空間データベースと帰納論理プログラミングエンジンの結合は、空間データマイニングへのエレガントで強力なアプローチを提供することを示す。

帰納論理プログラミング(ILP)は、正例、負例、背景知識、探索空間の指定(モード定義など)があれば、論理理論を効率的に学習することができる方法である。正例と負例の指定は比較的簡単ですが、効果的な背景知識の構成と探索空間の定義はILPのプロセスの多くの側面を詳細に理解する必要があり、ILPの使い勝手を制限しています。本発表では、ILPの専門家でない人がILPを自動利用するための2つの手法を紹介します。この技術では、ユーザから提供された情報から、特定の学習例の重要な側面を記述するための簡単な関連性言語の形で背景知識を自動生成し、反復深化型の探索プロセスを実現します。

我々は、既存の計画の一般化された共通の核を見つけることによって、新しい類似の計画タスクを解決するために既存の計画を利用することができる新しい戦略を提示する。この目的のために、我々は、2つの部分順序付きプランの最小結合汎化をもたらす演算子を開発した。3つの計画領域において、プランナがゼロからではなく、学習された共通の一般化されたコアから探索空間の探索を開始した場合に、計画の大幅なスピードアップが達成されることを示す。

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