Progolを用いた帰納論理プログラミング（ILP）

初めに

大学でProgolを用いる課題が与えられたときに、少しでも参考になってくれればいいなと思って記述しました。

Progolによって、正負事例から概念を定義するルールを学習する

Progolとは

帰納論理プログラミングをしてくれるシステムである。機械学習の一環である。

帰納論理プログラミング（ILP:Inductive Logical Programming）とは？

述語理論上で帰納的推論を展開するアプローチの一種で、様々な分類問題を解決することである。

• 述語理論
  コンピュータが読み解ける、形式的な知識表現言語。
  C言語とか、Javaとか。

• 帰納的推論
  様々な事実や例から、一般的なルールを定義する推論。
  「チワワは足が4つ、耳が2つで...」,「トイプードルは足が4つ、耳が2つで...」という例から「犬とは足が4本、耳が2つである」というルールを定義できる。

• 分類問題
  分類するための基準を考えること。
  犬と猫の分類基準は？　足の数？鳴き声？目？

ILPは5過程からなる

• 目標概念
  何についての帰納推論を行うのか。

• 事例
  目標概念に関する、例や事実。
  その中で目標概念に対して正しい事例を正例、間違っているものが負例

• 背景知識
  事例に対する関連知識。

• 仮説
  帰納的推論によって提示されるルール。
  ただし、目標概念に関するすべてに正しいと限らないから、あくまで仮説。

• 被覆
  仮説が正例に対して、正しい場合被覆しているという。

我々が入力するのは目標概念、事例、背景知識
Progolが行うのは、仮説、被覆

例）二郎系ラーメンとは何か

目標概念を「二郎系ラーメンとは何か？」とする。
事例を「二郎系ラーメン」に対する正例として「ラーメン二郎」「ちばから」、負例として「ラーメン凪」とする。
背景知識を「ラーメン二郎とはモヤシとキャベツが入っていて、麺が多く、トッピングが4種類ある二郎系ラーメンである」,「ちばからとはモヤシとキャベツが入っていて、麺が多く、トッピングが5種類ある二郎系ラーメンである」,「ラーメン凪とは煮干しベースの、普通の量のラーメンである」とする。
すると、「二郎系ラーメンとはモヤシとキャベツが入っていて、麺が多いラーメンである」という仮説が定義される。この仮説は「ラーメン二郎」「ちばから」に対して被覆していて、「ラーメン凪」に対して被覆していない。よって、この仮説は正しいと定義される。

Progol使い方

Progol（Ver4.4）ダウンロードはこちら

Progolはコマンドプロンプト上で実行する。
[スタート画面]→[cmd]→[コマンドプロンプトを起動]→[progol.exeのあるディレクトリへcd C:\Users...\progolで移動]→[progol (ファイル名)で実行]

Progol書き方

• バイアスの記述

ramen.pl

:- modeh(1,class(+ramen,#class))?
:- modeb(1,noodle_amount(+ramen,#nat))?
:- modeb(1,soup(+ramen,#base))?
:- modeb(1,man_rate(+ramen,#nat))?
:- modeb(1,has_moi(+ramen))?
:- modeb(1,has_cabbage(+ramen))?
:- modeb(1,has_spinach(+ramen))?
:- modeb(1,num_pork(+ramen,#nat))?

簡潔にいうとmodehで目標概念を宣言、modebで背景知識を宣言する。+は入力,-は出力,#は定数。
1行目:入力されたラーメンは、何系ラーメンであるか？
2行目:入力されたラーメンの麺の量は何ｇか？
3行目:入力されたラーメンのスープのベースは何か？
・・・

• クラスの記述

ramen.pl

ramen(kabuji). ramen(butayama). ramen(ayumu). ramen(chibakara). ramen(menderu).
ramen(yamatoya). ramen(machida_syouten). ramen(konshinya). ramen(yoshimuraya).
ramen(kaigaraya). ramen(jinbei). ramen(sinka). ramen(dead_or_alive).

class(jiro). class(ie). class(normal).

base(soy_source). base(soy_pork_source). base(pork_soy_source).
base(emulsification). base(oister).
base(oil). base(solt). base(sardines).

ラーメンのクラス：カブジ、豚山、歩夢...
系列のクラス：二郎系、家系、普通
味のベース:醤油、豚骨醤油...

• 正例の記述、負例の記述(一部表示)

正例

ramen.pl

class(kabuji,jiro).
class(butayama,jiro).
class(ayumu,jiro).
class(chibakara,jiro).
class(menderu,jiro).
class(yamatoya,ie).

カブジは二郎系
大和家は家系

負例

ramen.pl

:-class(kabuji,ie).
:-class(ayumu,normal).
:-class(kaigaraya,jiro).
:-class(yamatoya,jiro).

カブジは家系

• 背景知識の記述(一部表示)

ramen.pl

noodle_amount(kabuji,250).
noodle_amount(butayama,250).
noodle_amount(ayumu,300).

soup(kabuji,soy_source).
soup(butayama,soy_pork_source).

has_cabbage(kabuji).
has_cabbage(butayama).

カブジの面の量は250g

ソースコード（全部）

ramen.pl

:-set(c,3). %仮説の長さの制限．仮説本体部に含まれるリテラルの最大数．
:-set(noise,1). %ノイズ許容率．仮説が充足してしまう負事例の最大数．
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% class learns the class (Jiro/Ie/other) of various ramen.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Mode declarations
:- modeh(1,class(+ramen,#class))?
:- modeb(1,noodle_amount(+ramen,#nat))?
:- modeb(1,soup(+ramen,#base))?
:- modeb(1,man_rate(+ramen,#nat))?
:- modeb(1,has_moi(+ramen))?
:- modeb(1,has_cabbage(+ramen))?
:- modeb(1,has_spinach(+ramen))?
:- modeb(1,num_pork(+ramen,#nat))?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Types
ramen(kabuji). ramen(butayama). ramen(ayumu). ramen(chibakara). ramen(menderu).
ramen(yamatoya). ramen(machida_syouten). ramen(konshinya). ramen(yoshimuraya).
ramen(kaigaraya). ramen(jinbei). ramen(sinka). ramen(dead_or_alive).

class(jiro). class(ie). class(normal).

base(soy_source). base(soy_pork_source). base(pork_soy_source).
base(emulsification). base(oister).
base(oil). base(solt). base(sardines).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Positive examples
class(kabuji,jiro).
class(butayama,jiro).
class(ayumu,jiro).
class(chibakara,jiro).
class(menderu,jiro).
class(yamatoya,ie).
class(machida_syouten,ie).
class(konshinya,ie).
class(yoshimuraya,ie).
class(kaigaraya,normal).
class(jinbei,normal).
class(sinka,normal).
class(dead_or_alive,normal).

% Negative examples
%正しいルールが出ないときは適切に負事例をいれる
:-class(kabuji,ie).
:-class(ayumu,normal).
:-class(kaigaraya,jiro).
:-class(yamatoya,jiro).
:-class(machida_syouten,normal).
:-class(sinka,jiro).
:-class(chibakara,normal).
:-class(konshinya,normal).
:-class(dead_or_alive,jiro).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Background knowledge
noodle_amount(kabuji,250).
noodle_amount(butayama,250).
noodle_amount(ayumu,300).
noodle_amount(chibakara,300).
noodle_amount(menderu,250).
noodle_amount(yamatoya,160).
noodle_amount(machida_syouten,150).
noodle_amount(konshinya,170).
noodle_amount(yoshimuraya,180).
noodle_amount(kaigaraya,170).
noodle_amount(jinbei,170).
noodle_amount(sinka,140).
noodle_amount(dead_or_alive,150).

soup(kabuji,soy_source).
soup(butayama,soy_pork_source).
soup(ayumu,soy_pork_source).
soup(chibakara,emulsification).
soup(menderu,soy_source).
soup(yamatoya,pork_soy_source).
soup(machida_syouten,pork_soy_source).
soup(konshinya,pork_soy_source).
soup(yoshimuraya,pork_soy_source).
soup(kaigaraya,oister).
soup(jinbei,oil).
soup(sinka,solt).
soup(dead_or_alive,sardines).

man_rate(kabuji,79).
man_rate(butayama,85).
man_rate(ayumu,100).
man_rate(chibakara,95).
man_rate(menderu,90).
man_rate(yamatoya,73).
man_rate(machida_syouten,78).
man_rate(konshinya,75).
man_rate(yoshimuraya,85).
man_rate(kaigaraya,70).
man_rate(jinbei,70).
man_rate(sinka,80).
man_rate(dead_or_alive,60).

has_moi(kabuji).
has_moi(butayama).
has_moi(ayumu).
has_moi(chibakara).
has_moi(menderu).
has_moi(dead_or_alive).

has_cabbage(kabuji).
has_cabbage(butayama).
has_cabbage(ayumu).
has_cabbage(chibakara).
has_cabbage(menderu).

has_spinach(yamatoya).
has_spinach(konshinya).
has_spinach(yoshimuraya).
has_spinach(machida_syouten).

num_pork(kabuji,1).
num_pork(butayama,2).
num_pork(ayumu,2).
num_pork(chibakara,1).
num_pork(menderu,1).
num_pork(yamatoya,1).
num_pork(yoshimuraya,1).
num_pork(konshinya,1).
num_pork(machida_syouten,1).
num_pork(kaigaraya,1).
num_pork(jinbei,1).
num_pork(dead_or_alive,1).
num_pork(sinka,1).

実行結果

実行結果（一部）

[Generalising class(kabuji,jiro).]
[Most specific clause is]

class(A,jiro) :- noodle_amount(A,250), soup(A,soy_source), man_rate(A,
        79), has_moi(A), has_cabbage(A), num_pork(A,1).

[C:3,5,4,0 class(A,jiro).]
[C:9,3,0,0 class(A,jiro) :- noodle_amount(A,250).]
[C:7,2,0,0 class(A,jiro) :- soup(A,soy_source).]
[C:8,5,1,0 class(A,jiro) :- has_moi(A).]
[C:8,5,0,0 class(A,jiro) :- has_moi(A), has_cabbage(A).]
[C:0,3,1,0 class(A,jiro) :- has_moi(A), num_pork(A,1).]
[C:10,5,0,0 class(A,jiro) :- has_cabbage(A).]
[C:-9,3,4,0 class(A,jiro) :- num_pork(A,1).]
[8 explored search nodes]
f=10,p=5,n=0,h=0
[Result of search is]

class(A,jiro) :- has_cabbage(A).

[5 redundant clauses retracted]

1. カブジとその背景知識の学習
2. そこから最弱仮説の生成
3. 二郎系はラーメンの量が250ｇであるという仮説は、正例被覆数p=3、負例被覆数n=0となり、評価値f=9
4. 最終的にf=10が最大の評価値として現れたので、その仮説を採用し、「二郎系ラーメンとはキャベツを含んでいる」というルールが定義された。

※評価値$$f=P(p-(n+c+h))p$$

P:正例の総数,p:正例被覆数,n:負例被覆数,c:仮説のリテラル数,h:入出力関係を完全なら0、不完全なら完全までに必要なリテラル数

参考

帰納論理プログラミング 古川康一