4.帰納論理プログラミングによるデータマイニングエンジン Datagolの研究開発

［目次］

1. 研究テーマ
2. 研究体制／研究方法
3. 想定されるソフトウェア成果

［研究テーマ］

1) 研究テーマ名：

帰納論理プログラミングによるデータマイニングエンジン Datagolの研究開発

2) 研究の背景

現在、インターネットを中心として、情報化が加速されており、企業においてもデータウエアハウスによる統合情報システムの確立が望まれている。そこで期待される機能は、氾濫する膨大な情報の中から如何にして有益な情報を抽出するかである。これらの要求に答えるための技術として、データベースからの知識発見、あるいはデータマイニングの技術が近年注目を浴び、多くの研究が行われている。

実際、データマイニングへの期待は、より大きな広がりを見せている。それは流通業における、売上増大のための効果的な棚配置の決定、金融業における株価や為替レートの予測、医療分野における発症機構の解明と予防に関する知識の獲得、製造業における生産計画・在庫管理、さらにはWWWに代表されるインターネットを介して得られる膨大なデータの意思決定への利用など、様々な目的で、多種多様な分野を巻き込んだ形で展開されている。

このように、データマイニングへの関心が高まれば高まるほど、現在開発されているデータマイニングツールとの要求される機能面でのギャップが大きくなってきている。すなわち、現在データマイニングのための帰納推論エンジンとしては、ID3やC4.5などの命題論理学習器がニューラルネットワークとならんで、主要なツールとして一般に利用されてきたが、これらのエンジンは、より現実的な複雑な問題を扱うことが出来ない。それは、仮説を表現する言語の表現力の不足に起因する。

一方、帰納論理プログラミングは、一階述語論理に基づく機械学習の新しい方法論として、現在注目を浴びている。それは、ID3やC4.5などの決定木を生成する命題論理学習器に対して、データ間に潜んでいる共通の論理的、関係的パターンを抽出することが出来る。そのため、背景知識の利用が可能となり、命題論理学習器に比べて、応用分野が格段に広がった。データベースの用語で言えば、命題論理学習器は単一の表からの学習しか出来ないが、一階述語論理学習器は、複数の表に跨るデータの中から、論理的な関連性を抽出してくれる。このため、例えば関係データベースからの知識の発見が帰納論理プログラミングの枠組の中で、自然に達成することが出来る。

3) 研究の目的

本研究の目的は、背景で述べた、データマイニングの機能の高度化である。データマイニングの研究においては知識を抽出するエンジン部が重要となる。しかし、通常データマイニングが対象とするデータベースのサイズは、1万件、あるいはそれを越えてしまうので、一階述語論理学習器では、これまでは性能面で手に負えなかった。本研究においては、この問題を解決し、従来のデータマイニング技術では扱うことが困難であった「関係知識」を対象とした、表現力に富み、かつ効率の良い、データマイニングエンジンの開発を目指す。すなわち、現在、様々な分野から出されているデータマイニングシステムへの要求に応じることのできる、帰納論理プログラミングに基づくデータマイニングエンジンの開発を目的とする。より具体的には、現在の帰納論理プログラミングシステムの高機能化及び高速化を目的とする。

本研究目的は、主として知識処理の高度化を狙っているが、同時に、並列記号処理も念頭に置いている。

4) 研究の内容

本研究の目的は、表現力に富みかつ効率の良い帰納論理プログラミングに基づくデータマイニングエンジンを開発することである。この目的達成のために、以下の研究を行う。

第一に、問題を記述する表現言語をDatalogに制限する。Datalogは、データベースの表現言語であり、ID3やC4.5などの表現言語である命題論理と、Progolなどの表現言語であるホーン論理の中間に位置する表現力を持つ。また、実行効率に関しても、命題論理とホーン論理の中間に位置する。本研究では、仮説および背景知識の表現言語として、Progolに見られる任意のPrologプログラムに代えて、Datalogプログラムのみを許すようにする。すなわち、一般ホーン論理エンジンに変わって、Datalogのための専用エンジンを用いることにより、扱えるデータの量を大幅に拡大できるばかりではなく、効率の向上も期待できる。さらにDatalogを採用することは、外部データベースの扱いを可能にし、機能的にもデータマイニングのエンジンとしての機能が大幅に向上することが期待される。

自然言語処理などのいくつかの応用問題においては、リスト表現が不可欠となるが、Datalogは、リストなどの関数表現を許さない。この問題を解決するために、我々はDatalogに対し、制約条件付でのリストの使用を許すように、その表現力を拡張する。具体的には、‘ある要素がリストに含まれているか’などのチェック(テスト)の対象としてのみ、リストの利用を許すようにする。このことにより、実行効率を保ったまま、システムの適用できる問題範囲を拡張することが可能となる。

また、この表現言語の選択により、本プロジェクトによって開発する帰納論理プログラミングに基づくデータマイニングエンジンをDatagolと名付ける。

研究の第２として、帰納推論アルゴリズムの改良を行う。我々は、既にMGTPによるボトムアップ型の帰納推論アルゴリズムを開発し、それが最弱仮説の計算のみならず、帰納推論の処理の大部分を占める被覆集合アルゴリズムについても、実行効率を上げる上で大きな効果があることを示してきた。被覆集合アルゴリズムは仮説束上のA*-like探索を行なうが、アルゴリズムの工夫によって、探索すべきノードの数、および各ノードでの被覆計算の両方を効率化することを示してきた。具体的には、Progolが最終的に生成する仮説の引数間の入出力の関連性を調べ、それらが連鎖として閉じていることをヒューリスティック探索の手がかりとして優先探索を行ない、これによって無駄な探索の発生を抑制する（探索すべきノードの抑制）。さらに、各被覆計算において、直接の先祖で計算された事例の被覆集合をメモしておき、それによってそれ以下のノードでの被覆計算の対象事例の数を減少させる（各ノードでの被覆計算の効率化）。また昨年度の研究においては、これらのアルゴリズムの精密化を行い、更なる効率的帰納推論アルゴリズムの開発を行った。今回の研究では、これらの成果を基に、特に表現言語をDatalogに限定した場合での、効率的な帰納推論アルゴリズムの開発を行う。

研究の第３として、帰納推論エンジンとデータベースとの連結を行う。具体的には、仮説の評価に外部データベースを利用する。これにより、帰納推論のうち最も時間のかかる仮説処理をデータベースに任せることが可能となり、推論エンジンの大規模な問題へ適用が可能となる。また、単に連結するだけではなく、帰納論理プログラミングにおけるメタ情報と、データベースにおける概念モデルとの関係について考察する。これにより、実際にデータベースに格納されているデータから、帰納推論に必要なメタ情報をある程度自動的に抽出することが可能となり、利用者の負担の軽減につながると考えられる。また、データベースと推論エンジン間の通信コストの軽減に関しても研究を行う予定である。

［研究体制／研究方法］

1) 研究体制

	氏名	所属
研究代表者	古川 康一	慶応義塾大学 大学院 政策・メディア研究科
研究協力者	向井 国昭	慶応義塾大学 環境情報学部
同上	清木 康	慶応義塾大学 環境情報学部
同上	嶋津 恵子	慶応義塾大学 大学院 政策・メディア研究科
同上	尾崎 知伸	慶応義塾大学 大学院 政策・メディア研究科
同上	植野 研	慶応義塾大学 大学院 政策・メディア研究科

2) 研究の方法

研究は、古川、向井が全体のとりまとめを行ない、尾崎、植野は帰納推論部を開発する。清木、嶋津はデータベースとのインタフェース部の設計、開発を担当する。システムインテグレーションは、尾崎、植野が主に担当する。

［想定されるソフトウェア成果］

1) ソフトウェア名称:

帰納論理プログラミングに基づくデータマイニングエンジン -- Datagol --

2) そのソフトウェアの機能／役割／特徴

Datagolは、Progolと同様、与えられた正事例集合、負事例集合、および背景知識から、背景知識とともに正事例を説明するコンパクトな仮説を生成するプログラムである。正事例は、Prologの基底アトムとして与えられる。負事例は基底アトムの否定の他にも、ゴールの形の一貫性制約条件を与えることが出来る。背景知識は、任意のDatalogプログラムとして与えることが出来る（ただし、今学習しようとしている述語の呼び出しを含まない）。

本システムの役割は、Datalogによって与えられた演繹データベースからの知識発見のエンジンとして働くことである。これによって、データマイニングエンジンとして、表現力が命題論理よりも格段に豊かで、しかも効率的にも実用的な帰納推論エンジンの雛型が開発されるものと期待される。そのため、従来は不可能であった複雑な論理的パターンを演繹データベースから抽出することが可能になると予想される。

本システムの特徴は、帰納推論エンジンとして見た場合、Progolに匹敵する汎用性を持ち合わせ、しかもデータベースと結合している点である。そのため、外部データベースのスキーマさえ定義すれば、それらを容易に本システムに結合して使うことが可能である。また、本システムは、大量データに対する処理を効率的に行なうことが期待される。

3) ソフトウェアの構成／構造

本ソフトウエアは、帰納論理プログラミングに基づく、データマイニングエンジンである。大まかなシステム構成を以下の図に示す。

                +------------+              +----------------------+
                |データベース|←----------→|ユーザインターフェース|
                +------------+              +----------------------+
                     ↑｜                          ↑
                     ｜↓                          ｜
                推論エンジン/データベース          ｜
                   インターフェース (SQL)          ｜
                     ↑｜                          ｜
                     ｜↓                          ｜
                +----------------+                 ｜
                |帰納推論エンジン| ←--------------＋
                +----------------+

本ソフトウエアは、帰納推論エンジン、データベース、ユーザインターフェース、から構成される。推論エンジン部は、Progolと同様、最弱仮説(仮説束)生成部、及び仮説束内探索部からなる。また仮説束内探索部では、その探索中に必要とされる事例の被覆計算において、データベースが利用される。

4)ブラッシュアップ項目

• プログラムや用いられたアルゴリズムの解説

  まず帰納論理プログラミングに関して概要を示し、次に本システムのベースである、Progolシステムに関して、その詳細なアルゴリズムの解説を行う。Progolは、最弱仮説生成部と仮説束内探索部からなる。そのそれぞれについて、理論的な枠組みの解説、および実際の実現方式について解説を行う。また、仮説の評価基準に関しても説明を行う。これらProgolの解説の後、今回導入する改良アルゴリズムの詳細な解説を行う。Datalog言語の表現力と、その拡張についての理論的考察、効率化のために導入されたアルゴリズムの理論的な考察と実際の実現方式などについて解説を行う。

5) もし、ＩＦＳとの関連があれば、どのソフトウェアと関連があるのか

IFSのMGTP、およびボトムアップ型帰納論理プログラミングシステムMG-Progolが、本システムと深く関連している。

6) 使用予定言語および動作環境／必要とされるソフトウェア・パッケージ／ポータビリティなど

帰納推論エンジン、データベースインターフェースはともに、Prologを用いて実装する。ポータビリティに関しては、基本的に、PrologおよびOracleなどのSQLをサポートする関係データベースシステムがあれば利用できる。

7) ソフトウェアの予想サイズ（新規作成分の行数）

推論エンジン	:Prolog で5000行程度
DBとのインターフェース	:Prolog 1000行程度

8)ソフトウェアの利用形態

本ソフトウエアは、演繹データベースからの知識発見を行なうことが目的であるから、その利用は、データベースの存在を仮定する。また、帰納論理プログラミング自身は、教師付き学習のための枠組であるので、それが扱うことの出来る問題は、与えられた例からの分類ルールの同定である。その際、データベースの中の一つの表が分類クラスの正事例集合となるのが一般的である。その時、他の表はDatagolへ与えられる背景知識となる。一般に、帰納論理プログラミングシステムを利用する場合に最も労力を要する部分が、負事例の用意である。ただし、明確に定義された排反クラスへの分類問題なら、ある一つのクラスに対する正事例は他のクラスに対する負事例となる。そのようにして、通常は負事例を準備することが可能である。また、帰納論理プログラミングシステムの利用を困難にするもう一つの原因は、モード情報などの付随的な情報の与え方に対する指針の欠如である。我々はこの点を考慮して、ユーザインターフェースを改善することにより、一般ユーザでも利用が可能なシステムの開発を目指す。

また、本システムは、実用レベルの大きな問題を扱うことの出来る帰納論理プログラミングに基づいたデータマイニングエンジンであるので、従来のツールでは発見できなかった知識をデータベースから抽出することが可能である。さらに、本システムは演繹データベースの上に構築されるので、そのようにして得られたルールは、直ちに同じ演繹データベースの内包データベースとすることが出来る。これによって、演繹データベースから漸増的に知識を発見することが可能となる。

9) 添付予定資料

• ユーザマニュアル
• アルゴリズムの解説書