11月24日資料

2015年11月24日
知能システム論(2015-06)
前回の復習

知能システム科学専攻
新田 克己
述語論理の補足


述語論理の推論
もとの知識に矛盾がないことが前提
演繹推論 → 厳格な推論
現実には
無矛盾な論理式集合を構築するのは
困難である。
述語論理では表現力が不足している。
単純な演繹推論しかない。
論理プログラミング

プログラムの実行＝定理証明
?- grandfather(taro, Y).
論理プログラミング



parent(hanako,Y)
mother(hanako,Y)
mother(hanako,jiro)
論理式でプログラムを書く
grandfather(X,Y) :father(X,Z),parent(Z,Y).
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
father(taro, hanako).
mother(hanako, jiro).
さまざまな推論
father(taro, Z), parent(Z,Y).
father(taro, hanako)
述語論理入門
 構文論： 記号の並べ方
 意味論： 定数，関数，述語の解釈
P |= Q
 証明論： 公理，推論規則，証明原理
A, A→B
B
P |- Q

演繹(deduction)
Ａ， Ａ→Ｂ
（結論）
Ｂ
帰納(induction)
Ａ，
Ｂ
Charles S. Peirce
Ａ→Ｂ
（規則）
仮説生成，アブダクション(abduction)
Ｂ，
Ａ→Ｂ
（説明）
Ａ
1
さまざまな推論(cont.)



類推
Ａ→Ｂ，
Ａ～Ｃ
Ｃ→Ｂ
非単調推論
Ａ，not B →C, A
C
時間推論、空間推論、.....
硬い推論から柔らかい推論へ





様相論理(1/4)

公理系 APL
A1 A→（B→A)
A2 （A→（B→C))→（（A→B)→（A→C))
A3 （￢B→￢A)→（（￢B→A)→B)
R1 MP
A→B
A
B
様相論理(3)

公理系 S4 ＝ T＋α
A6 □A→□□A

公理系 S5 ＝ T＋α
A7 ◇A→□◇A
必然性と偶然性 ===> 様相論理
○P，□P
時間、認識、義務===>様相論理の応用ほか
Past P， Know P，Obl P
矛盾、例外、常識 ===> 非単調推論
Pならば「おそらく」Q
ルール不足 ===>
観測結果からルール生成 ---> 帰納推論
事例から直接，推論 ---> 類推
事実不足 ===> アブダクション(仮説生成）
様相論理(2)

公理系 K ＝ APL＋α
A4 □（A→B)→（□A→□B)
R2
A
□A

公理系 T ＝ K＋α
A5 □A→A
様相論理(4)
クリプケモデル M=<W,R,V>

W={w1,w2,w3,w4}
R={<w1,w2>,<w2,w3>,<w2,w4>}
W1
Q
V(W1,P)=0
V(W1,Q)=1
V(W1,R)=0
W2
P
Q
V(W2,P)=1
V(W2,Q)=1
V(W2,R)=0
W3
W4
P
P
R
V(W3,P)=1
V(W3,Q)=0
V(W3,R)=0
V(W4,P)=1
V(W4,Q)=0
V(W4,R)=1
V(W2,□P)=1, V(W2, ◇Q)=1
2
帰納推論とは
帰納推論(Inductive Reasoning)
と帰納論理プログラミング(ILP)

帰納推論
観測された事実から規則を導く推論
例） 文例からの文法規則の学習
入出力例からのプログラムの学習
データマイニング
顧客の購入記録→動向の検出。
株価の変動記録→株価の予測。
カルテ→治療方針の決定。
帰納推論の方法



観測事例
決定木
基本的なルール決定アルゴリズム
ID3
帰納論理プログラミング
論理プログラミングをベースとした
ルール決定。
背景知識を利用することができる。
(ニューラルネット）
決定木(decision tree)
湿度
＜５０％
参加

曇り
雨
参加
≧５０％
不参加

風
弱
参加
風
強い
弱い
弱い
強い
弱い
強い
強い
弱い
気温
20度
18度
6度
18度
12度
15度
6度
20度
湿度
40%
70%
60%
50%
60%
90%
80%
80%
テニス
参加
不参加
不参加
参加
参加
不参加
不参加
参加
決定木の評価
天候
晴れ
天候
晴れ
晴れ
晴れ
曇り
曇り
雨
雨
雨
強
天候，湿度，風 をどの順番に調べるかで
異なる決定木ができる。
コンパクトな木が望ましい。
Occam’s razor
 識別力の強いテストを先に行う。
ＩＤ３
不参加
3
識別力の判定


天候
識別力の判定(cont.)
テストの識別力の判定にentropyを利用
E= – ∑(Pi×log Pi)
天候
晴
識別力の大きいテストを優先する
８
晴 曇
３
２
風
雨
３
４
４
帰納論理プログラミングとは
通常の論理プログラミング（例：Prolog)

論理式（ホーン節）で知識（ルール，事実）を
書く。
質問文を入力すると，導出原理を使って
解答を出す。
fly(X)∨￢bird(X)
例） fly(X) :- bird(X).
bird(tweety).
?- fly(X).
X=tweety
yes
参加：1
不参加：2
0.92
1.00- 0.92×3/8 - 0.00×2/8 – 0.92×3/8
= 0.31
演習
-P×log P

雨
参加：2
不参加：0
0.00
強
弱
エントロピー

曇
参加：1
不参加：2
0.92
８
1.00
参加： 4， 不参加： 4
bird(tweety)
fly(tweety)

エントロピーの計算とID3
帰納論理プログラミングとは(cont.)

観測データからルールを求める
例） fly(tweety), bird(tweety)
 fly(X) :- bird(X)
観測データ
ルール
￢fly(X)
□
4
帰納論理プログラミングの理論
帰納論理プログラミング(Train問題)
背景知識をB, 正事例をE+, 負事例をE-
B |= E+
B ∧ E- |= □
であるときに
B ∧ H |= E+
B ∧ H |= Eの条件を満たす仮説Hを求める
TRAIN問題
east(t1).
TRAIN問題 (cont.)
has_car(t1,c11). has_car(t1,c12).
has_car(t1,c13).
infront(c11,c12). infront(c12,c13).
has_car(t2,c21). has_car(t2,c22).
has_car(t2,c23).
infront(c21,c22). infront(c22,c23).
east(t2).
学習結果 (仮説)
east(X):- has_car(X,Y), short(Y), closed(Y).
long(car11). open(car11). load(car11,3,square).
wheel(car11,2).
short(car11). closed(car12). load(car12,1,triangle).
wheel(car12,3).
long(car13). open(car13). load(car13, 1, lozenge).
wheel(car13, 3).
帰納論理プログラミングの原理

導出
bird(tweety)

逆導出の例(1)

逆導出
bird(tweety)
fly(X)←bird(X)
（ｆｌｙ（X)∨￢bird(X))
fly(tweety)
Facts
father(charles, william).
mother(elizabeth,
charles).
father(philip, charles).
。。。。。
fly(X)←bird(X)
（ｆｌｙ（X)∨￢bird(X))
fly(tweety)
george
edward
frances
elizabeth
diana
charles
philip
anne
william
fatherとmotherによるイ
ギリス王室の家系図
5
逆導出の例(2)

Rules
逆導出の例(3)
（parent と gf の定義）
以下のように、parentの定義と新しいFactが
与えられたときに、gfの定義を作り出せるか。
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
gf(X,Z) :- father(X,Y), parent(Y,Z).


Facts
gf(philip,william).
逆導出の例(4)
逆導出の例(4)
￢gf (philip,william). gf(X,Y)の定義
Ｅ
￢gf (philip,william). gf(X,Y)∨￢father(X,U)∨￢parent(U,Y).
￢father(philip,U)∨￢parent(U,william).
father(philip, charles).
￢father(philip,U)∨￢parent(U,william).
father(philip, charles).
￢parent(charles, william).
￢parent(charles, william).
￢father(charles, william).
parent(charles, william)
∨￢father(charles, william).
father(charles,william).
￢father(charles, william).
□
￢gf (philip,william).
gf(X,Y) :- father(X,U), parent(U,Y).
￢parent(charles, william).
□
father(charles,william).
仮説の生成と評価
￢father(philip,U)∨￢parent(U,william).
father(philip, charles).
￢father(charles, william).
parent(charles, william)
∨￢father(charles, william).
□
逆導出の例(4)
Ｅ
（parent の定義）
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
これらのルールがあれば、以下の質問にも
回答できる。
?- mother(diana, william)?
Yes
?- gf(X,william)?
X = philip;
Ｅ
Rules
parent(charles, william)
∨￢father(charles, william).
father(charles,william).

帰納推論 =
仮説の生成 + 仮説の評価
(注意）仮説の候補はいくつもある。
gf(X,Y)
gf(X,Y) :- father(X,U),parent(U,Y)
gf(philip,william) :- father(philip,charles),parent(charles,william)
gf(philip, william)
6
概念の強弱

概念の強弱（２）
概念の強弱 (半順序関係)


概念が強い
＝ 多くのものを説明できる (general)
概念が弱い
＝ 少ないものしか説明できない (specific)
強
事例
f(1,1), f(1,2), f(2,1), f(2,2)
h(1,1), h(1,2)
仮説
f(A,B).
f(A,A).
f(A,B):-h(A,B).
f(A,A):-h(A,A)
概念を強くするには，
定数を変数に。 条件を削減。
coverできる事例
f(1,1).f(1,2).f(2,1).f(2,2).
f(1,1).f(2,2).
f(1,1).f(1,2).
f(1,1)
弱
概念の強弱（３）
演習

f(A,B)
f(A,A)
f(2,2)
f(A,A):-h(A,A)
概念の強弱
f(A,B):- h(A,B)
f(A,B):-h(A,B),g(A,B)
f(1,1):-h(1,1)
Progol


S. Muggleton(York Univ.) らによって
開発された帰納論理プログラミング
システム
http://web.comlab.ox.ac.uk/oucl/research/
areas/machlearn/PProgol/ppman_toc.html
より入手可能
7
Progolの入力データ

Progolの入力データ (contd.)
モード宣言 (学習対象概念と
利用する背景知識の定義)



:-modeh (1, grand_parent (+person, -person))?

タイプ情報(各述語の引数のドメインの定義)

学習すべき概念の定義

:-modeb (1, parent(+person, -person))?
正負事例

利用可能な背景知識の定義
+ は入力変数を -は出力変数を意味する



east(t1).
:- east(t5).
is_parent_of(oscar, louis).
:- is_parent_of (louis, oscar).
背景知識

負例と一貫性制約条件
person(stephan).
list([H|T]) :- list(T). ルールでも良い
int などの組み込み述語も利用可能
事例に関連のある知識、任意のPrologプログラム
実行のトレース (train.pl)
CProgol Version 4.4

負例の効用： 仮説の過学習を防止
gf(X,Y):- parent(X,U),parent(U,Y).
:- gf(mary, stephen).
parent(mary,louis).
parent(louis,stephen).

一貫性制約
:- class(X,mammal),class(X,fish).
Progolにおける仮説の生成

1. 一つの事例に着目し、それを一般化

最弱仮説(Most Specific Hypothesis)の生成
B∧H |= E  B∧E |= H
[:- modeh(1,eastbound(+train))? - Time taken 0.00s]
[:- modeb(100,has_car(+train,-car))? - Time taken 0.00s]
………
[Generalising eastbound(east1).]
[Most specific clause is]
eastbound(A) :- has_car(A,B), has_car(A,C), has_car(A,D), has_car(A,
E), not open(C), not long(C), not long(E), open(B), open(D),
… … … … ...
[C:-1,5,5,0 eastbound(A).]
[C:-2,5,5,0 eastbound(A) :- has_car(A,B).]
… … … … ...
[Result of search is]
eastbound(A) :- has_car(A,B), not open(B), not long(B).
Progolにおける仮説の生成

2. MSHを積極的に利用した、最良優先
探索により、最良仮説を発見

発見的評価関数を用いた、最良優先全解
探索
ｍｓｈ： B∧E のすべてのモデルで真である
基底リテラルをAND結合したもの
H |= ｍｓｈ
8
仮説生成

Ｐｒｏｇｏｌにおける候補仮説空間
B={ f(1), g(1) }
E= { h(1) }
B∧E |= ￢h(1)
B∧E |= f(1)
B∧E |= g(1)

最弱仮説の存在



もっとも一般的な仮説

msh
￢h(1)∧f(1)∧g(1)



機械的に仮説を生成
h(1)←f(1)∧g(1)
記述長最小原理（ＭＤＬ基準）
(X,Y,...,Z).
目的述語を述語名
にし、変数に何も
制限のない仮説
伴意を包摂で近似

H
考えるべきもっとも特殊な仮説
すべての仮説H は H |= msh(B,E).<target_pred>
最弱仮説
ＰｒｏｇｏｌにおけるＭＤＬ基準
仮説は，強力で単純な方が良い。（矛
盾）
仮説評価のために、記述長を利用
強力さ ＋ 単純さ

Compression Gainがもっとも大きい（負
事例を説明しない）仮説が最良の仮説
を選択
Compression Gain =
説明される正事例の数
－ 仮説のリテラル長
－ 説明される負事例の数
N
ＭＤＬ＝－Σlog p(X;Θ’） ＋ (m/2)log N
N: データ数、 m:パラメータ数
A*-like探索

Progolの仮説束内探索アルゴリズム

頭部のみの仮説から始める





リテラルの追加 （追加されるリテラルはMSHから選ばれ
る）
変数の逆代入（モードに依存して行われる）
システマティックにMSHを包摂する仮説を生成
評価値の高いところから優先的に探索(リテラル
の追加や逆代入)を行う
発見的評価関数を用いた最良優先探索
まとめ



論理プログラミング
さまざまな推論
帰納推論


決定木
帰納論理プログラミング
逆導出
Progolにおける技法
9