機械学習技術 人工知能技術 自然言語処理技術 セマンティックウェブ技術 オントロジー技術 デジタルトランスフォーメーション技術 AI学会論文 知識情報処理技術 AI学会論文を集めて 推論技術
Inductive logic Programming 2008より。
2008年9月10日から12日にかけて、プラハで第18回帰納論理プログラミング国際会議が開催されました。11年ぶりにプラハに戻ってきたILPですが、その間に興味のあるトピックがどのように進化してきたかを見てみたい気がします。ILPコミュニティは明らかに、愛着のある一階論理表現のフレームワークを大切にし続けています。ILP2008で発表された研究は、逆包含関係などの確立されたILPアプローチの拡張と、ブレイブ誘導などの新しい論理誘導フレームワークの探求の両方にまだ余地があることを示したので、これは正当なことだと思います。また、統計的関係学習、グラフマイニング、セマンティックウェブなど、ILPの研究分野に貢献する論文も多数発表されました。また、ILPをより主流の研究分野に開放するために、セマンティックウェブ（Frank van Harmelen）、バイオインフォマティクス（Mark Craven）、認知科学（Josh Tenenbaum）の3つの領域から素晴らしい招待講演が行われました。また、ILPの研究に直接関与していない講演者を意図的に探しました。さらに、ILPの観点から発表してほしいという強い要望に応えて、統計的関係学習（Kristian Kersting）のチュートリアルを招待しました。最後に、欧州委員会からStefano Bertolo氏をお招きし、現在EUが支援している知的コンテンツと意味論に関する研究において、ILPが理想とするニッチについて講演していただきました。
メインのテクニカルトラックでは、46のアブストラクトと36のフルペーパーの投稿がありました。そのうち8件は受理され、16件は再確認の後、却下されました。残りの12本は条件付採録とし、著者にさらに3週間の修正期間を設けました。修正された論文は、プログラム委員長によって再査読され、出版に問題がないことが確認されました。このように、今年も著者の方々に負担をかけたことは、大会の質を確保する上で有効な手段であったと考えています。また、ILP2008では、Late-breaking papers トラックに22本の短報が投稿され、別途審査が行われました。採択された論文は、別冊の論文集に掲載されます。また、両トラックから選ばれた論文の拡張版は、Machine Learning Journalの特別号に掲載される予定です。
ILP2008の開催は、さまざまな方面からの素晴らしい協力のおかげで、素晴らしい経験となりました。招待講演者の旅費（米国空軍欧州宇宙研究開発局、PASCAL2 Network of Excellence、Czech Society for Cybernetics and Informatics、Euro-pean Commissionがスポンサー）、学生論文賞（Machine Learning Journalがスポンサー）を実現してくれた寛大なスポンサーに感謝している。また、この論文集とMachine Learning Journalの特集号の準備に柔軟かつ積極的に協力してくれたSpringer社にも感謝します。また、投稿された論文を熱心に審査してくださったプログラム委員会の皆様にも感謝いたします。この査読活動は、強力で使いやすい会議管理ソフトウェアであることが証明されたMyReviewシステムによって支えられています。
ILPは、論文の著者がいなければ、たった3文字になっていたことでしょう。彼らに最大の感謝を捧げます。これからも頑張ってILP2009に投稿してください。
Invited Talks
世界に関する人間の知識は、直感的な理論として表現されることが多い。これは、世界を観察する際に組織化し、予測し、説明する抽象的な概念の体系である。このような強力な知識構造は、どのように表現され、獲得されるのだろうか。私は、人々の直観的理論と理論構築過程をモデル化するための計算フレームワークと、これらのモデルを人間の学習者を用いて実験的に検証するいくつかの方法について説明する。人間の学習と推論に関する我々のモデルは、ベイズ人工知能、統計的関係学習、帰納論理プログラミングの中核となるアプローチに基づいているが、これらの機械学習と推論アプローチをより人間に近い能力に拡張する新しい方法も提案している。
統計的関係学習は、人工知能の中心的な問題の一つである、確率的推論と一階論理表現および機械学習の統合に取り組むものである。これまで、様々な形式や学習手法が開発されてきた。このチュートリアルでは、統計的関係性学習についてやさしく紹介し、最先端の技術を概観する。帰納論理プログラミングの古典的な設定から始まり、それらがどのように確率的手法で拡張できるかを示す。また、統計的関係学習に対するノンパラメトリックなアプローチにおける、持ち上げられた推論と最近の開発について触れる。その一方で、最新の統計的関係性学習のアプローチについてもレビューする。
一見したところ、ILPとセマンティックウェブには多くの共通点がある。どちらも大量のデータを扱うこと、背景知識を利用すること、計算可能な論理形式を用いること、などです。しかしながら、この2つの研究領域が実際に交わることは非常に少ない。本講演では、まずセマンティックウェブプログラムの概要（その目標、方法、これまでの成果、重要な未解決課題）を鳥瞰的に説明します。ILPはセマンティックウェブにとって非常に重要な要素であるオントロジーを学習するのに使えるだろうか。しかし、機械学習の結果と同様に、そのようなオントロジーは完全に正しく、完全なものではないだろう。そのため、セマンティックウェブコミュニティは、部分的に不完全で不正確なオントロジーを扱う方法を、その側から学ぶ必要がある。私は、この方向性で最も新しい仕事、つまり、無限に拡張可能な分散型不完全セマンティックWeb推論のためのプラットフォームであるLarKC（Large Knowledge）を構築する努力を紹介する。ラージナレッジコライダーは、ILPとセマンティックウェブが最終的に出会う場所となりうるのでしょうか？
計算生物学の中心的な課題は、細胞の環境に応じて様々な遺伝子の発現を制御する仕組みや細胞回路を明らかにすることである。この課題は、機械学習手法、特に表現力豊かな表現を用いた手法に多くの興味深い機会を与えてくれる。本講演では、機械学習を用いて、（1）ゲノム配列中の制御因子の認識、（2）遺伝子間の相互作用ネットワークの解明、（3）様々な刺激による細胞応答の特徴付けを行う最近の研究について紹介する。本講演では、表現力豊かなモデルを必要とする課題に焦点を当て、どのような表現属性がこれらの課題にとって重要であるかについて、得られた教訓を述べる。
レバーや織機のような物理的な道具は、人間の力と器用さを増幅させ、農業収穫機のように、ある興味ある量（小麦畑）が突然豊富になると、他の関連する量（収穫に必要な人間の労働力）の希少性をもたらすため、しばしば導入されます。デジタル情報が（組織と個人の両方にとって）利用可能になるにつれ、それを解釈して私たちに利益をもたらす意思決定を行う能力にも、同様の希少性が生じているのです。この講演では、EUがフレームワーク・プログラム7を通じて提供する、この不足に対処するための資金提供の機会について説明します。ILPのコミュニティがこのような取り組みに理想的に貢献できるようないくつかの傾向について、また、最近成功した提案のエンジニアリングにおいて非常に効果的であることが証明されたいくつかの一般的なパターンについて説明します。
Research Papers
記号学習の可能性は、仮説空間におけるヒューリスティック探索の有効性に強く依存する。しかし、最近の関係学習では、探索中の包含テストにおいて起こりうる相転移現象が、ヒューリスティック探索のプラトーとして働き、その効率を強く阻害すると主張されている。我々は、この点をさらに発展させ、トップダウンおよびボトムアップの学習戦略が、探索中に解に到達する前にプラトーに直面することを示す学習問題生成器を提案する。この性質は、サブサンプションテストの相転移を示すために用いるCSP生成器の基本モデルであるRBモデルによって保証される。このモデルでは、学習者が保持する現在の仮説の大きさが相転移のオーダーパラメータであり、ヒューリスティック探索の制御パラメータでもあるため、学習者は問題解決中にプラトーに直面する必要があります。このモデルの利点として、興味深い性質を持つ小さな関係学習問題を構成できるため、学習に用いられる完全探索アルゴリズムのベンチマークモデルとして利用できることがあげられる。我々はこの生成器を用いて、関係学習における完全探索アルゴリズムと非完全探索アルゴリズムを研究し、包含テストの相転移に直面したときの振る舞いを比較する。このジェネレータは、インフォームド・ラーニングが非インフォームド・ラーニングに堕落する病的なケースを示すことを示す。
(多）関係回帰は、参照オブジェクトと呼ばれる対象オブジェクトの連続的な応答を、課題関連オブジェクトと呼ばれる他のオブジェクトとの相互作用を考慮して予測するものである。リレーショナル・データベースでは、参照オブジェクトと課題関連オブジェクトはそれぞれ別のデータ関係に格納される。オブジェクト間の相互作用は、（多対一の）外部キー制約によって表現され、タスク関連オブジェクトの説明変数を応答変数にいくつかの方法でリンクさせることができる。複数のas-signmentsを異なる属性値ベクトルで具体化することにより、参照オブジェクトは複数のインスタンスのバッグとして表現されるが、バッグ全体に対する応答値は1つしか存在しない。このことは、多インスタンス学習の前提である、ある参照対象の応答値を観測するのは主要なインスタンスであることを示唆している。本論文では、分割統治戦略に従って外部キー制約をナビゲートし、参照オブジェクトを属性値ベクトルのバッグとして表現し、各バッグに対して、応答値の主要な責任者である主インスタンスを構築するトップダウン誘導型多関係モデルツリーシステムを提案する。局所超平面の係数は、ステップワイズ最小二乗回帰のEM実装で推定される。実験により、従来の属性値学習器や関係モデル木学習器と比較して、本提案の精度が向上していることが確認された。
あるコードの最悪の場合の実行時間（WCET）を決定する問題は、リアルタイムシステムのコミュニティでは基本的な問題である。既存の方法は、プログラムコードを解析するか、大規模なタイミング解析を実行することによって、この情報を得ようとするものである。本論文では、ILPの形で機械学習を用いて、コードのサンプル実行に基づいてプログラムの特性を推測する、この問題に対する新しいアプローチを提示する。さらに、より高度なILPの手法を適用することで、学習可能な関数の範囲と学習に要する時間を大幅に改善することが可能である。
Markov Logic Networks (MLN) はマルコフネットワークと一階論理を組み合わせたもので、一階論理式に重みをつけ、これをマルコフネットワークの特徴のテンプレートとして捉える。MLNの構造学習は、リレーショナルデータベースの尤度を最大化することで行うのが最新の方法である。このため、予測課題では最適な結果が得られないことがある。一方、ある構造を持つMLNの重みを識別的に学習することで、予測問題においてより良い結果が得られることが分かっている。本論文では、述語の結合尤度ではなく、クエリ述語の条件付き尤度を最大化することにより、MLNの構造を識別的に学習するアルゴリズムを提案する。このアルゴリズムでは、条件付き尤度の最大化によって構造を選択し、最尤法によってパラメータを設定する。2つの実世界ドメインでの実験により、提案アルゴリズムはMLNに対する最新の識別重み学習アルゴリズムよりも条件付き尤度の点で改善されることが示される。また，提案アルゴリズムとMLNにおける最新の生成的構造学習アルゴリズムを比較し，データセットが小さい場合は生成的アルゴリズムが，データセットが大きい場合は識別的アルゴリズムが生成的アルゴリズムより優れていることを示す[22]の結果を確認する．
ロボット領域における自律的発見へのILPの適用実験について述べる。自律的なロボットはその世界において実験を行い、データを収集し、その世界に関する事前予測的な理論を形成している。特に、我々はロボットが述語の発明を通じて「洞察を得る」ことに関心がある。ブロック押し領域での最初の実験シナリオでは、ロボットは物体の移動可能性という概念を発見する。第二のシナリオは、障害物という概念を発見するものである。模擬ロボットを用いた実験と、ロボットの観測にノイズが含まれる場合の実ロボットによる実験について説明する。
理論修正システムは、初期理論の正確さを向上させ、純粋な帰納的手法よりも正確で理解しやすい理論を生み出すために設計されたものである。このシステムは、例文が誤って分類されている箇所を検索し、修正オペレー タを用いて修正する。この際、通常は知識ベースの全てのリテラルを考慮したトップダウンアプローチで生成される文節に先行詞を追加しようとする。このため、膨大な探索空間が必要となり、リビジョンプロセスのコストを支配している。ILPのMode Directed Inverse Entailmentシステムでは、先行詞の検索を最下部の節のリテラルに制限する。本論文では、底部節とモード宣言を導入することにより、理論修正先行詞付加の効率を向上させた。FORTE修正システムとの比較実験の結果、修正処理の実行時間が平均で3桁速くなり、精度を低下させることなく、より理解しやすい理論を生成できることが示された。さらに、提案する理論修正手法は、Alephシステムで生成された理論よりも予測精度を大幅に向上させることができる。
本論文では、記述論理で表現された概念記述の学習に焦点を当てる。この文脈における学習問題を述べた後、一般的な記述言語へ適用可能なFOILライクなアルゴリズムを提示し、この表現の意味論の根底にある固有の不完全性に関連した学習の理論的側面について議論する。その後、このアルゴリズムの性能を経験的に評価するために、いくつかの実際のオントロジーに対して行われたこのアルゴリズムの実装の実験的評価を提示する。
-
Feature Discovery with Type Extension Trees
我々は、リレーショナルなデータから複雑な組み合わせの特徴を学習することに興味がある。我々は、表現力豊かで一般的な表現言語を用いており、その意味論により、様々な統計的関係学習で用いられてきた多くの特徴を表現することができる。関係性特徴の空間に対する高価な網羅的探索を避けるため、情報利得の一般化された関係性概念と判別関数によって導かれる発見的探索アルゴリズムを導入する。このアルゴリズムは、人工的な関係学習問題や実世界の関係学習問題において、興味深く解釈可能な特徴を見出すことに成功する。
- Feature Construction Using Theory-Guided Sampling and Randomised Search
誘導論理プログラミング（ILP）システムによって構築されたブール素性を、関連する関係情報にアクセスすることで、非常に優れた予測モデルが得られることが繰り返し発見されている。ILPシステムによる特徴構築プロセスは、「命題化」と呼ばれることもあるが、主に前処理段階として行われるか（最初に有用と思われる大規模な特徴セットを構築し、その後予測モデルを構築する）、特徴構築とモデル構築を密結合する（新しい特徴ごとに予測モデルを構築し、性能が大幅に向上する特徴のみを保持）かのいずれかであった。これらは両極端であり、特徴選択に対するフィルターやラッパーベースのアプローチと同様の考え方である。この問題に対する第3の視点として、探索に基づく特徴構築の考え方がある。これは、ILPシステムで構築可能な全ての特徴の部分集合を検索する、という概念的なものである。このような空間を網羅的に探索することは、通常、困難であることは明らかである。そこで、ランダムに（ただし一様ではない）特徴の部分集合を構成し、この部分集合から始まる貪欲な局所探索を繰り返すランダム化局所探索に再分類する。可能な特徴の数は、通常、すべての局所的な動きを列挙することを禁止している。その結果、探索空間における次の動きは、現在の特徴量セット を用いて構築されたモデルによる誤差によって導かれる。これは、性能を向上させることができるものだけを選択するという観点から、すべての可能な局所的な手の集合から非一様にサンプリングしていると見なすことができる。その結果、前処理として特徴量の部分集合が生成されるが、それ以上の変更は実際のモデル予測によって積極的に導かれる。我々はこの方法を、語義曖昧性解消という言語処理タスクで検証した。この課題では、SVMと前処理で作成したILP素性を組み合わせて用いることで、良好なモデルが得られている。我々の結果は、これらの以前の結果を改善するものである。すなわち、予測精度は通常より高く、必要な素性は大幅に少なくなる。
ILPは概念学習における過去の成果を利用した関係学習の主要なアプローチであり、事前の概念知識を利用することが特徴である。概念知識は記述論理(DL)を中心としたオントロジーの形で提供されることが多くなってきている。本論文では、関係データとオントロジーを組み合わせた観測からルールを学習する問題を考察し、それに対するILPソリューションの構成要素を明らかにする。本提案は、KRフレームワークDL+logの表現力と演繹力に依存し、否定を含むDLと分離型Datalogの緊密な統合を可能にする。より正確には、DL SHIQと肯定的なデータログを統合するこのフレームワークのインスタンス化を採用する。この提案により、オントロジーを考慮した関係学習（Onto-Relational Learning）の拡張の基礎が構築されると主張する。
我々は、生物学的文法の学習という文脈の中で、標準的な肯定的な節のみの評価関数の欠点を明らかにした。この欠点を克服するために、我々はL-modificationを提案する。L-modificationとは、この評価関数を修正し、個々の用例の長さを考慮するようにしたものである。我々はニューロペプタイドプレカーソルミドル（NPP-middles）と呼ばれる一連の生物学的配列を用いる。このNPP-middlesから学習するL-modificationを用いることで、標準的な正節のみの評価関数を用いた場合よりも優れた性能を持つ誘導文法が得られる。また、L-modificationを用いることで、短・中・長のNPP-middleで学習した場合、誘導文法の性能が向上することが示された。L-modificationの潜在的な欠点について議論する。最後に、探索空間の大きさの制限が大きくなればなるほど、L- modificationによる予測性能の向上が大きくなることを示す。
隠れマルコフモデル（HMM）は、音声認識、行動認識、バイオインフォマティクスなどのアプリケーションで成功裏に使用されています。これまでにも、階層型HMMや抽象型HMMなど、HMMを複数の時間抽象度でエレガントに拡張する試みがなされてきた（例えば、ユーザーの活動を表現する場合など）。同様に、HMMを関係構造を持つドメインに拡張するロジカルHMMのような研究も過去に行われている。本研究では、論理的階層隠れマルコフモデル（LoHiHMMs）という形で、関係モデルと階層モデルの両方の力を自然に結合する表現を開発する。LoHiHMMは論理HMMのコンパクトな表現と階層HMMの推論容易性を受け継いでいる。1つは命題型HMMに基づくもので、もう1つはこの設定に適応した粒子フィルタリングに基づくものである。また、このモデルを用いた2つのシミュレーション領域での実験結果を示す。
我々は、記述論理で表現されるセマンティックWebの標準的な知識ベース表現における統計的学習の問題に取り組む。具体的には、ALCN論理のカーネル関数とサポートベクターマシンを統合し、参照表現を用いた統計的学習の利用を可能にする。実験では、カーネル分類をOWLオントロジー上の資源検索と問合せ応答タスクに適用した。
ウェブページ、デジタルライブラリー、知識ベース、セマンティックウェブ、データベースなど、さまざまなソースからの異種データの統合は、オープンな問題である。本研究の最終的な目的は、このような異種データソースに対して、あたかも単一のリレーショナルデータベースにデータが格納されているかのように問い合わせることができるようにすることである。この目的に従い、我々はリレーショナルデータベースモデルからの結合の一般化を提案し、高次表現で任意に複雑な構造化データへの結合を可能にする。構造化データのカーネルと距離を取り入れることで、このモデルをさらに拡張し、異種データの近似的な結合をサポートする。CORAデータセットに対する近似クエリの例を評価し、共著者セットから出版物全体までのタイプについて結合することで、出版物領域における我々のアプローチの柔軟性を実証している。
統計的関係学習は、この10年間で大きな注目を集めている。ILPのコミュニティでは、一階論理のサブセットで表現される不確実な知識をモデル化し、学習するためのモデルがいくつか出現している。しかし、これらのモデルを深く比較した例はなく、アプリケーションによってどのモデルを選択すべきかを決定するのは困難である。本論文では、マルコフ論理回路網とベイジアンプログラムの2つを、特にその表現能力と推論方法に関して比較する。比較の結果、この2つのモデルはユーザの視点から見て大きく異なっており、どちらかを選択することは、問題を見るための異なる哲学を選択することを意味することがわかった。比較をより具体的にするために、我々は実行例を用いた。この実行例は、両アプローチの興味深い点のほとんどを示し、しかも正確に扱いやすいものである。
Brave Induction
本論文では、次のような帰納問題を考える。背景知識 B と観測 O が与えられたとき、整合的な理論 B∧H が O を満たす最小限のモデルを持つような仮説 H を見つける。この種の帰納法を勇敢な帰納法と呼ぶ。ブレイブ帰納法は、ILPにおける説明的帰納法（B∧Hの全てのモデルでOを満たすことが必要）とは異なる。ブレイブ帰納法は、観測から離接規則を学習したり、不定あるいは不完全な情報を含む背景知識から学習する場合に有効である。我々は、勇敢な帰納法を計算するアルゴリズムを開発し、それを答集合プログラミングにおける帰納法に拡張する。
知識ベースは、人工知能研究の多くの分野で重要な役割を担っています。このような知識ベースを作成するための簡単なアプローチは、基底リテラルのデータベースである。しかし、この方法は、学習システムやパフォーマンスシステムにとって、コンパクトでもなく、計算量的に扱いやすいものでもない。本論文では、階層構造化された一階知識ベースを漸進的に学習するための統計的手法を提案する。本手法では、ルールと基底事実の両方を用いて、基底リテラルを一般化する簡潔なルールを構築する。我々は、本アプローチが計算効率に優れ、多くの関係性を持つドメインにうまく対応できることを実証する。
逆伴侶(IE)を用いるILPシステムでは、最も具体的な節で囲まれた仮説空間を通じて節を絞り込むことが基本となっている。本論文では、このような設定における絞り込み演算子の新しい分析を行う。特に、Progolのrefinementオペレータを再確認し、議論する。Progolのrefinementオペレータは一般的な包摂順序に対して非完了的であることが知られている。我々は、最も具体的な（底辺の）節に対するサブサンプションオーダーを導入する。このサブサンプションオーダーは、従来提案されていたオーダーとは異なり、Progolの絞り込み空間を特徴づけるものである。我々はこのサブサンプションオーダーの特性を研究し、このオーダーに対して理想的な絞り込み演算子が存在することを示す。また、最下位節に対する部分集合の最小汎化および最大特殊化のための効率的な演算子が実装できることを示す。また、最下位節に対するより限定的な部分集合順序を研究し、Progolの不完全性にどのように対処できるかを示す。
様々な応用領域において、データはベクトルの袋として表現されることがある。このようなバッグに対する関数の学習は困難な問題である。本論文では、このようなデータを扱うために、カスケード相関ネットワークに基づくニューラルネットワークアプローチを提案する。ネットワークに統合された特殊なアグリゲーションユニットを定義することで、bag上の関数を学習する一般的なフレームワークを得ることができる。人工的に作成したデータセットと実世界のデータセットの両方についての結果を報告する。
outerplanar graphとは、すべての頂点が外側の境界線上にあるように、平面上に置くことができる平面グラフのことである。多くの化合物がアウタープラナー・グラフで表現されることが知られている。我々は、化合物のデータセットのような外平面グラフの集合に共通するグラフパターンとして、ブロック保存外平面グラフパターン（略してbpo-graphパターン）を提案した。本論文では、まず、与えられた外平面グラフの集合を説明する最小生成bpo-graphパターンを求める多項式時間アルゴリズムを与える。次に、外平面グラフの集合に含まれる最大頻度のbpo-graphパターンをすべて列挙するパターンマイニング・アルゴリズムを与える。最後に、本パターンマイニングの性能を示すために、化学物質データセットに対する実験結果を報告する。
次回はILP2009について述べる。
コメント
[…] Inductive logic Programming 2008論文集より […]
[…] Inductive logic Programming 2008論文集より […]
[…] 前回のILP2008に続き、今回はILP2009について述べる。 […]