Advanced Data Mining 高度データマイニング

人工知能特論2011
平成２４年１月１３日（金）
東京工科大学大学院
亀田弘之
全体のまとめ
• なぜ論理学の話をしたのか？
• 今までの話がどのように人工知能に関わって
いるのか？
• 最近はやりのData Mining ( Text Mining,
Web Mining  Knowledge Discovery)の
側面から話をしましょう！
（DMは今やAIの一分野とも考えられる）
2
知識の発見
• 知識=普遍の真理
• 真理の探究
こんなことが自動的にできると凄いよね！
3
真実
Web
4
“高度データマイニング2005”より
Advanced Data Mining
高度データマイニング
東京工科大学大学院
バイオニクス・情報メディア学専攻科
Version 2
ＤＭ Methodology
6
ＤＭ Methodology
1. Exploratory data analysis
（探索的データ解析）
2. Computational data mining
（計算論的データマイニング）
3. Statistical data mining
（統計的データマイニング）
7
ＤＭ Methodology
1. Exploratory data analysis
（探索的データ解析）
2. Computational data mining
（計算論的データマイニング）
3. Statistical data mining
（統計的データマイニング）
8
１．Exploratory data analysis
a. 統計的データ解析(SDA)
b. 探索的データ解析(EDA)
9
統計的データ解析(SDAの基礎)
1. 視覚的分析
•
•
表：度数分布表(frequency table)
図：ヒストグラム(histogram)
2. 数値的分析
•
•
•
代表値：
平均 (mean)
中央値 (median)
モード (mode,最頻値）
ばらつき度：分散(variance)
平均偏差(mean deviation; MD)
標準偏差(standard deviation)
範囲(range = 最大値ー最小値)
その他
四分位数(quartile,第一・二・三）
外れ値
10
統計的データ解析(EDAの基礎)
1. 視覚的分析
•
•
表：度数分布表(frequency table)
図：ヒストグラム(histogram)
2. 数値的分析
•
•
•
代表値：
平均 (mean)
中央値 (median)
モード (mode,最頻値）
ばらつき度：分散(variance)
平均偏差(mean deviation; MD)
標準偏差(standard deviation)
範囲(range = 最大値ー最小値)
その他
四分位数(quartile,第一・二・三）
外れ値
11
探索的データ解析(EDA)
1.
2.
3.
4.
5.
6.
7.
幹葉表示(stem-and-leaf display)
要約値(letter value display)
箱ヒゲ図(box-whisker plots)
Ｘ－Ｙ表示(X-Y plotting)
抵抗性のある直線回帰(registant line)
中央値分散分析(median polish)
時系列データのならし(smoothing)
12
探索的データ解析(EDA)
1. 幹葉表示(stem-and-leaf display)
ヒストグラムに代わる手法
2. 要約値(letter value display)
平均値・標準偏差に代わるもの
3. 箱ヒゲ図(box-whisker plots)
分布の形と外れ値の図的表示
13
ＤＭ Methodology
1. Exploratory data analysis
（探索的データ解析）
2. Computational data mining
（計算論的データマイニング）
3. Statistical data mining
（統計的データマイニング）
14
３．Statistical data mining
a.
b.
c.
d.
e.
f.
Statistic models（統計モデル）
Statistic inference（統計的推論）
Non-parametric model
General linear model
Log-linear model
Graphical model
etc.
15
ＤＭ Methodology
1. Exploratory data analysis
（探索的データ解析）
2. Computational data mining
（計算論的データマイニング）
3. Statistical data mining
（統計的データマイニング）
16
２．Computational data mining
1.
2.
3.
4.
5.
6.
Cluster analysis（クラスター分析）
Tree models（木モデル）
Linear regression（線形回帰）
Logistic regression（ロジスティック回帰）
Neural networks（ニューラルネットワーク）
ILP(Inductive Logic Programming;
帰納論理プログラミング）
7. SVM(support vector machines)
etc.
17
２．Computational data mining
a.
b.
c.
d.
e.
f.
Tree models（木モデル）
Cluster analysis（クラスター分析）
Linear regression（線形回帰）
Logistic regression（ロジスティック回帰）
Neural networks（ニューラルネットワーク）
ILP(Inductive Logic Programming;
帰納論理プログラミング）
etc.
18
a．クラスター分析
i. Hierarchical methods（階層型法）
ii. Non-hierarchical methods（非階層型法）
19
a．クラスター分析（２）
•
基本的考え方：
1. 近いデータをかき集めてグループを作る。
2. 近いグループ同士をかき集めて新たなグルー
プを作る。
3. これの繰り返し。
20
クラスター分析（例）
21
クラスター分析（例）
22
クラスター分析（例）
23
クラスター分析（例）
24
クラスター分析（例）
25
クラスター分析（２）
•
基本的考え方：
1. 近いデータをかき集めてグループを作る。
2. 近いグループ同士をかき集めて新たなグルー
プを作る。
近い＝＞距離(distance)が主要な役割を果たす
26
距離って何だっけ？
27
距離(distance)
•
空間Ｓの任意の２点x,yの間に、１つの実数d(x,y)
が定義されていて、これが次の4つの条件を満た
しているとき、d(x,y)を２点x,y間の距離という。
(1)d ( x, y )  0　(2)d ( x, x)  0
(3)d ( x, y )  d ( y, x)
(4)d ( x, y )  d ( x, z )  d ( z, y )
28
29
２点間の距離
空間Ｓ
x
２点間の距離d(x,y)
y
30
２グループ間の距離は？
31
２グループ間の距離は？
グループA
グループＢ
32
２グループ間の距離
グループA
グループＢ
距離d(A,B)
33
２グループ間の距離
グループA
平均値・中央値
グループＢ
距離d(A,B)
34
２グループ間の距離
グループA
平均値・中央値
グループＢ
距離d(A,B)
代表値間の距離
35
いろいろな距離（関数）
 
2
2
1.d ( x , y )  ( x1  x2 )  ( y1  y2 )
 
2.d ( x , y )  | x1  x2 |  | y1  y2 |
 
3.d ( x , y )  max{| x1  x2 |, | y1  y2 |}
 
 
 
4.d ( x , x )  0, d ( x , y )  1　if　x  y.
etc.
36
いろいろな距離（関数）（２）
• Euclidean distance（ユークリッド距離）
• Mahalanobis disntance（マハラノビス距離）
• Edit distance（エディト距離）
etc.
37
b．木モデル
• 決定木(decision tree)
38
決定木の用途
•
•
•
•
•
分類問題
診断問題
予測問題
制御問題
パターン認識問題 etc.
39
その前に、ちょっと復習
40
木とは？
41
42
43
44
• これらをひっくり返すると…
45
46
• これらを抽象化すると…
47
木とは
48
木とは（２）
枝(branch)
49
木とは
根(root)
節(node)
50
木とは
根(root)
葉(leaf)
節(node)
51
決定木の例(その１)
クレジット利用者
1000人
利用状況
適切利用者
700人
不適切利用者
300人
負債状況
負債あり
500人
負債なし
200人
履歴状況
ブラックリスト者
10人
非ブラックリスト者
290人
52
決定木の例(その２)
サイレン
あり
なし
車体の色
車体の大きさ
白
赤
大
中
白黒
消防車
パトカー
小
救急車
大型トラック
普通自動車
軽自動車
53
決定木の作成（学習）
大
量
の
例
決定木の作成
決
定
木
54
決定木の作成（学習）
大
量
の
例
決定木の作成
決
定
木
分類問題の解
55
56
人工知能特論2009
東京工科大学大学院
バイオニクス・情報メディア学専攻科
Decision Tree for PlayTennis
Outlook
Sunny
Rain
Overcast
Humidity
High
Yes
Wind
Yes
Normal
Yes
Strong
No
Weak
Yes
58
Training Examples
Day
Outlook
天候
Temperature
温度
Humidity
湿度
Wind
風
Play
Tennis
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
Sunny
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Sunny
Overcast
Overcast
Rain
Hot
Hot
Hot
Mild
Cool
Cool
Cool
Mild
Cool
Mild
Mild
Mild
Hot
Mild
High
High
High
High
Normal
Normal
Normal
High
Normal
Normal
Normal
High
Normal
High
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Strong
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
59
Top-down Induction of
Decision Tree
Main loop:
1. A ← the best decision attribute for next node
2. Assign A as decision attribute for node
3. For each value of A, create new descendant
of node
4. Sort training examples to leaf nodes
5. If training examples perfectly classified, then
HALT, else iterate over new leaf nodes.
60
Which attribute is the best?
[29+, 35-]
T
[21+, 5-]
A1=?
F
[8+, 30-]
[29+, 35-]
T
[18+, 33-]
A2=?
F
[11+, 2-]
61
Entropy
•
•
•
•
S is a sample of training examples
p+ is the proportion of positive examples in S
p- is the proportion of negative examples in S
Entropy measures the impurity of S
Entropy(S )   p log2 p  p log2 p
(0  p , p  1, p  p  1)
62
Entropy（エントロピー）
1
0.9
0.8
0.7
0.6
0.5
Entropy
0.4
0.3
0.2
0.1
0
0
0.5
1
63
Interpretation of Entropy
• Entropy(S)とは…２つのグループ（各生起確
率がp+とp-）を符号化するのに必要なビット
数（情報量）
• その理由は…
P+
P-
64
Information Theory（情報理論）
• 生起確率pのメッセージに対する最適符号長符号
(optimal length code)は、  log2 p で与えられる。
• したがって、それぞれ確率p+とp-で生起する２つの組
に対する平均符号長は、
p ( log2 p )  p ( log2 p )
で与えられる。これはEntropyの公式そのものである。
65
Entropyの本当の定義
• 無記憶情報源Sから、シンボルs1, s2, s3, …, snがそ
れぞれp1, p2, p3, … ,pn の生起確率で出現するとき、
この無記憶情報源Sのエントロピーは以下の式で定
義される。
n
Entropy( S )   pk log2 pk
k 1
0  pk　 1　（ k  1,2,3,...,n）
p1  p2  p3  ...  pn  1
66
Information Gain(情報利得)
• Gain(S,A)：「もともと（S)のエントロピー」と「Aに着目
する分類後のエントロピー」の差。
これを情報利得と呼ぶ。
| Si |
Gain( S , A)  Entropy( S )  
Entropy( Si )
iValues( A) | S |
67
Which attribute is the best?
[29+, 35-]
T
[21+, 5-]
A1=?
F
[8+, 30-]
[29+, 35-]
A2=?
T
[18+, 33-]
| Si |
Gain( S , A)  Entropy( S )  
Entropy( Si )
iValues( A) | S |
F
[11+, 2-]
68
Which is the best?
- Selecting the next attribute -
high
[3+, 4-],
E=0.985
[3+, 4-],
E=0.985
[3+, 4-],
E=0.985
Humidity
Wind
normal
[3+, 4-],
E=0.985
Gain(S,Humidity)=0.151
weak
[3+, 4-],
E=0.985
strong
[3+, 4-],
E=0.985
Gain(S,Wind)=0.048
69
Training Examples
Day
Outlook
天候
Temperature
温度
Humidity
湿度
Wind
風
Play
Tennis
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
Sunny
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Sunny
Overcast
Overcast
Rain
Hot
Hot
Hot
Mild
Cool
Cool
Cool
Mild
Cool
Mild
Mild
Mild
Hot
Mild
High
High
High
High
Normal
Normal
Normal
High
Normal
Normal
Normal
High
Normal
High
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Strong
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
70
分類前のエントロピー
・Yes
・No
9
5
[9+, 5-]
9
9
5
5
E (S )   log2 ( )  log2 ( )
14
14 14
14
 0.94
71
Outlookに着目する場合
• Sunny
• Overcast
• Rain
[2+, 3-]
[4+, 0-]
[3+, 2-]
5
4
5
E (Outlook)  E ( Sunny)  E (Overcast)  E ( Rain)  0.767
14
14
14
2
2 3
3
E ( Sunny)   log2 ( )  log2 ( )  0.97
5
5 5
5
4
4 0
0
E (Overcast)   log2 ( )  log2 ( )  0.26
4
4 5
5
3
3 2
2
E ( Rain)   log2 ( )  log2 ( )  0.97
5
5 5
5
72
Temperatureに着目する場合
• Hot
• Mild
• Cool
[2+, 2-]
[4+, 2-]
[3+, 1-]
4
6
4
E (Tem p)  E ( Sunny)  E (Overcast)  E ( Rain)  0.911
14
14
14
2
2 2
2
E ( Hot)   log2 ( )  log2 ( )  1.00
4
4 4
4
4
4 2
2
E ( Mild )   log2 ( )  log2 ( )  0.918
6
6 6
6
1
1 3
3
E (Cool)   log2 ( )  log2 ( )  0.811
4
4 4
4
73
Humidityに着目する場合
• High
• Normal
[3+, 4-]
[6+, 1-]
7
7
E ( Hum idity)  E ( High)  E ( Norm al)  0.789
14
14
3
3 4
4
E ( High)   log2 ( )  log2 ( )  0.985
7
7 7
7
6
6 1
1
E ( Norm al)   log2 ( )  log2 ( )  0.592
7
7 7
7
74
Windに着目する場合
• Weak
• Strong
[6+, 2-]
[3+, 3-]
8
6
E (Wind )  E (Weak )  E ( Strong)  0.892
14
14
6
6 2
2
E (Weak )   log2 ( )  log2 ( )  0.811
8
8 8
8
3
3 3
3
E ( Strong)   log2 ( )  log2 ( )  1.00
6
6 6
6
75
情報利得を計算すると…
Gain( S , Outlook)  E ( S )  E (Outlook) 
Gain( S , Hum idity)  E ( S )  E ( Hum idity) 
Gain( S ,Wind )  E ( S )  E (Wind ) 
Gain( S , Tem perature)  E ( S )  E (Tem perature) 
76
Decision Tree for PlayTennis
Outlook
Sunny
Rain
Overcast
Humidity
High
Yes
Wind
Yes
Normal
Yes
Strong
Yes
Weak
Yes
77
決定木まとめ
• 決定木は分類器
• 決定木が例から学習出来る
• 過学習(overfiting)回避の工夫が必要
＝＞枝刈り(pruning)
• 決定木学習は命題論理の命題学習に相当
＝＞述語論理への拡張が必要
＝＞帰納的論理プログラミング
(ILP; Inductive Logic Programming)
78
79
高度データマイニング
ーILP概説ー
東京工科大学大学院
亀田弘之
Version 2
ILP What?
• 述語論理上で帰納推論を展開するアプロー
チであり、分類問題を解決することが出来る
枠組み
81
ILP What?
• 述語論理上で帰納推論を展開するアプロー
チであり、分類問題を解決することが出来る
枠組み
82
述語論理
• 対象間の関係を記述する知識表現
例：太郎は花子を愛している。
＝＞愛する（太郎,花子）
＝＞ love（taro,hanako）
83
述語論理
• 対象間の関係を記述する知識表現
記述のための言語が必要
＝＞ love（taro,hanako）
＝＞ P（x1,x2）
84
述語論理記述のための言語
•
•
•
•
•
•
変数
関数
述語
論理結合子
限量子
コンマ等
85
述語論理記述のための言語
•
•
•
•
•
•
変数：
関数：
述語：
論理結合子：
限量子：
コンマ等：
xi (i  1,2,3,...)
f
P
k
i
k
(i  1,2,3,...;k  0,1,2,...)
(i  1,2,3,...;k  0,1,2,...)
　
i

,
86
項(Term)
• 変数は項である。
• 関数F(t1, t2, …, tn) は項である。
ただし、 t1, t2, …, tn は項。
• 以上のものだけが項である。
87
基礎項
• 変数を含まない項のこと。
88
アトム(atom)
• P(t1, t2, …, tn )はアトムである。
ただし、 t1, t2, …, tn は項。
• t1, t2, …, tnすべてが基礎項のとき、
p(t1, t2, …, tn )を基礎アトム(ground atom)と
呼ぶ。
89
論理式
1. 述語P(t1, t2, …, tn )は論理式。
2. Fが論理式ならば、￢Fも論理式。
3. FとGが論理式ならば、(F∧G) と(F∨G)も論
理式。
4. Fが論理式、xが変数のとき、
∃x F と ∀x F も論理式。
5. これらにより作られるものだけが論理式。
90
論理式の例
F  (x1P52 ( x1, f 21 ( x2 ))  x2 P42 ( x2 , f72 ( f 40 , f51 ( x3 ))))
Problem１: この論理式の構造は
どうなっているか？
Problem２: この論理式の意味は
どうなっているか？
91
確認問題
次のうちどれが論理式？
2
3
Q ( x100 , x4 )
2
3
P ( x100 , x4 )
2
4 3 100
, )x P x (
3
2
P ( x100 , x4 )
love(taro, hanako)
92
確認問題
次のうちどれが論理式？
2
3
Q ( x100 , x4 )
2
3
P ( x100 , x4 )
2
4 3 100
, )x P x (
3
2
P ( x100 , x4 )
x4x P ( x100 , x4 )
3
100 2
love(taro, hanako)
93
love(taro, hanako)
2
3
P ( x100 , x4 )
論理式のシンタッ
クスはこちら。
扱いたいのは
こちら！
94
「解釈」の導入（形式 → 内容）
• 解釈(Interpretation)
• なぜ「解釈」が必要なの？
• これって真(true)なの偽(false)なの？
2
3
P ( x100 , x4 )
各記号の解
釈が必要！
Pやxが何を意味しているのかわからなければ
決まらない。
95
述語論理式の意味論
• 構造A=（UA,IA）
ただし、UA≠Φ（領域）
IA は論理式の各記号の意味割り当てをする
写像。
この辺は抽象的なので、具体例で理解しよう
。
96
とある世界を考える。
97
抽象化しよう！
98
とある世界
99
とある世界
100
とある世界
101
太郎
花子
愛
102
言語化
論理式
解釈
103
言語化
2
3
P ( x100 , x4 )
解釈
104
もう一息整理しよう！
105
言語化
love(taro, hanako)
2
3
P ( x100 , x4 )
太郎は花子を愛する
解釈
106
解釈の構築(意味の割当て)
• UA={ taro, hanako }
• IA:
x100 ↔ taro
x4 ↔ hanako
P32 （＊, ＊＊） ↔ love(＊,＊＊)
これに意味を持たせる
ことができた！！
P32 ( x100 , x4 )
以下、省略…
107
述語論理あれこれ
• Prenex Conjunctive Normal Form (PCNF)
• Skolem Standatd Form (SSF)
– Skolem 定数
– Skolem関数
– φが充足不可能SSF(φ)が充足不可能
• Herbrand Model (HM)
– φがモデルを持つ  φがHMを持つなど
108
その他
•
•
•
•
•
Resolution
代入
包摂
束構造
lgg(least general generalization)や
rlgg(reletively lgg)
• 高階論理
• Paraconsistent Logic など
109
• 知識記述言語（知識表現）としての論理式
• 推論のために論理学を導入
推論体系完全性・妥当性・推論アルゴリズム
の存在等の理由により、現在は通常“１階の
述語論理”が採用されている。
この殻を破ればさらに発展がある筈！
110
こんな準備しつつ、いよいよILPへ
111
以下、Webより拝借した資料です
• 取り扱いに注意してください！
112
Inverse Entailment and Progol
Stephen Muggleton
有川研究室修士1年
坂東恭子
一部亀田により改変2010.01.08
発表の流れ
・はじめに
・帰納論理プログラミング（ILP）とは
・Progolの説明
・まとめ
114
はじめに
機械学習：決定木
一階述語論理式を学習しよう
背景知識を使おう
帰納論理プログラミング（ILP）
115
帰納論理プログラミングとは？
帰納論理
プログラミング
論理プログラミング
logic programming
機械学習
machine learning
背景知識、正例、負例
負例を説明せず、正例を説明する仮説をみつける
116
ILP システムの例
・GOLEM ：1992年Muggletonらにより開発
rlgg (Relative Least General Generalization)
・Progol :1995年Muggletonらにより開発
逆伴意（inverse entailment）に基づく
・FOIL :1990年Quinlanにより開発
・GKS ：1995年溝口により開発など
117
Progol とは？
・1995年Muggletonにより開発されたILP
システム
・C (Prolog)で記述されている。
・逆伴意（inverse entailment）の考えを採用
118
伴意(entailment)とは？
・伴意＝論理的帰結
・記号 ⊨ を使う
A ⊨ B
・BはAの伴意である
・BはAの論理的帰結である
・背景知識＋仮説 ⇒ 例
記号を使って表すと
B(背景知識) ∧ H（仮説）
⊨ E（例）
119
逆伴意(inverse entailment)とは？
伴意：B(背景知識) ∧ H（仮説）
⊨
E（例）
演繹定理より
H（仮説）
⊨
B(背景知識) → E（例）
逆伴意：伴意を逆向きに読む
背景知識と例から仮説を得る
120
Progolの仮説生成プロセス
逆伴意に基づき最も特殊な節（最弱仮説）を構成
最弱仮説を包摂する空間（最弱仮説空間）
において、最良優先探索
最良な仮説の発見
121
仮説と最弱仮説の関係
仮説
一般的
探索空間が
縮小される！
正例
仮説
特殊化
最弱仮説
仮説
特殊化
正例
最弱仮説
特殊化
特殊
正例
ここが歳弱化節とすると．．．
122
最弱仮説の生成
・B  ￢ Eから最弱仮説を演繹的に計算可能
H（仮説）
⊨

￢（B → E）
B(背景知識) → E（例）
対偶をとって
⊨
￢H

B￢E
⊨
￢ Hは￢ bot(B,E)
の部分連言（）
￢H
すべてのモデルで真な基底
リテラルの連言（）：bot(B,E)
B￢E
⊨

￢ bot(B,E)
123
証明：￢ Hは￢bot(B,E)の部分連言（）
￢ Hが￢ bot(B,E)以外の基底リテラルを含む
￢ bot(B,E) = l1 ・・・  ln
￢ H = l1 ・・・  ln  lk  lk+1
B  ￢ E にはlk , lk+1を
含まないモデルが存在
B￢E
⊭
￢H
124
￢ Hは￢ bot(B,E)の部分連言（）
B  ￢ E ⊨ ￢ bot(B,E)
⊨
￢H
対偶をとって
H
⊨
bot(B,E)
最弱仮説MSH
B  ￢ Eから最弱仮説を演繹的に計算可能
125
正例：
gf（波平，タラオ）
gf（洋平，カツオ）
gf（洋平，サザエ）
gf（洋平，ワカメ）
負例：
gf（波平，カツオ）
gf（舟，タラオ）
gf（洋平，タラオ）
背景知識：f（波平，サザエ）， m（舟，ワカメ），
f（波平，カツオ），f（波平，ワカメ），
m（サザエ，タラオ），f（洋平，波平）
p（A，B）:- f（A，B），p（A，B）:- m（A，B）
126
母
洋平
海平
妹
波平
舟
ワカメカツオサザエ
マスオ
タラオ
127
正例E+： gf（波平，タラオ）について
B
 ￢E
⊨
￢MSH
￢MSHはB  ￢Eのすべてのモデルで真
B  ￢E
= ￢ gf（波平，タラオ）
 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）
 f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平）
 p（A，B）:- f（A，B）  p（A，B）:- m（A，B）
￢MSH
は基底リテラルの連言
= ￢ gf（波平，タラオ）
 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）
 f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平）
 p（波平，サザエ） p（舟，サザエ） p（波平，カツオ）
 p（波平，ワカメ） p（サザエ，タラオ）  p（洋平，波） 128
MSH
＝￢ (￢ gf（波平，タラオ）
 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）
 f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平）
 p（波平，サザエ） p（舟，サザエ） p（波平，カツオ）
 p（波平，ワカメ） p（サザエ，タラオ）  p（洋平，波平）)
と同じ意味
＝gf（波平，タラオ）:- f（波平，サザエ）, m（舟，サザエ）,
f（波平，カツオ）, f（波平，ワカメ）,
m（サザエ，タラオ）,f（洋平，波平）,
p（波平，サザエ）, p（舟，サザエ）,
p（波平，カツオ）, p（波平，ワカメ）,
p（サザエ，タラオ）,p（洋平，波平）
129
最弱仮説から仮説を求める
仮説
一般的
H（仮説） ⊨ MSH（最弱仮説）
最弱仮説を伴意する
最良な仮説を求める
伴意を機械的
に行うのは困難
伴意を包摂で近似し、
仮説空間を探索しよう
特殊
最弱仮説
130
Progolの仮説生成プロセス
逆伴意に基づき最も特殊な節（最弱仮説）を構成
最弱仮説を包摂する空間（最弱仮説空間）
において、最良優先探索
最良な仮説をみつける
131
A*-like 探索
・Progolにおける探索方法
＜＝改善の余地あり！
・最弱仮説空間（最弱仮説を包摂する空間）を
探索し、最良仮説を得る
・A*探索が元になっている
132
A* 探索
・グラフにおける最良優先探索
・評価関数 f(n) を最小にするパスをみつける。
f(n)＝g(n)＋h(n) : n経由の最短解の見積りコスト
g(n):出発接点から接点nまでの経路のコスト
h(n):ヒューリスティック関数
nからゴールまでの見積りコスト
133
S
14
B
I
10
10
8
18
A
5
E
H
9
10
C
14
7
G
6
D
7
F
134
ヒューリスティック関数（ゴールとの直線距離）
S:
A:
B:
C:
D:
E:
F:
H:
I :
G:
42
35
28
30
23
19
16
10
18
0
S
B
A
f=14+28=42
f=10+35=45
S
f=24+36=60
f=36
E
f=22+19=41
I
f=24+18=42
135
f=22+19=41
E
B
F
f=30+25=55
f=38+16=54
f=31+10=41
F
G
E
f=40+19=59
H
f=44+16=60
f=41+0=41
よって、最良経路は、S  B  E  H  G
136
S
14
B
I
10
10
8
21
A
18
E
H
9
10
C
14
7
G
13
D
12
F
137
A*-like 探索グラフの生成
・探索空間・・・最弱仮説（MSH）を包摂する空間
・（empty set）からはじまるグラフを作り、そのグラフ
について最良優先探索を行う。
138
MSH(最弱仮説)
＝gf（波平，タラオ）:- f（波平，サザエ）, m（舟，サザエ）,
f（波平，カツオ）, f（波平，ワカメ）,
m（サザエ，タラオ）,f（洋平，波平）,
p（波平，サザエ）, p（舟，サザエ）,
p（波平，カツオ）, p（波平，ワカメ）,
p（サザエ，タラオ）,p（洋平，波平）
139

gf（A，B）
gf（A,B）： gf（A,B）： gf（A,B）：
-f(A,C) -m(C,D) -m(C,B)
gf（A,B）： gf（A,B）：
-f(C,A)
-p(A,C)
gf（A,B）：
-p(C,D)
gf（A,B）：
-p(C,B)
gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）：
-f(A,C),
-f(A,C),
-f(A,C),
-f(A,C),
-f(A,C), -f(A,C), -f(A,C),
m(C,B) f(D,A)
p(A,C)
p(D,C)
p(C,B)
p(D,A)
m(D,C)
・
・
・
・
・
・
・
・
・
・
・
・
最も特殊な節
・
・
・
・
・
・
gf(A,B):-f(A,C),m(D,C),f(A,E),m(C,B),f(F,A),
p(A,C),p(D,C),p(A,E),p(C,B),p(F,A)
140
グラフ内A*-like探索
・評価関数として記述長最小原理を使う。
・compression gainが最も大きいものが最良
compression gain＝
{説明される正事例の数}
－(｛仮説のリテラル長｝＋｛説明される負事例の数｝)
｛仮説のリテラル長｝＝
｛その時点の仮説のリテラル長｝＋｛追加されるリテラル長｝
g(n) ＝｛仮説のリテラル長｝＋｛説明される負事例｝
141
・｛追加されるリテラルの最小値｝を
ヒューリスティック関数で与える
h(n)＝ head部の出力変数がすべて、body部の入力変数
として存在しない時に追加するリテラルの最小値
gf（A,B）： -f(A,C)
Bについてのリテラルを追加
p(A,B,C): -q(A,D)
B, Cについてのリテラルを追加
・ f(n)＝説明される正事例の数－｛ g(n) ＋ h(n)｝
が最大になる仮説を見つける
・全解探索（仮説空間すべて考慮）
142

例
4 － (1+2+1)
ｰ2
=0
gf（A，B） 4 － (0+3+2)= －1
0
gf（A,B）： gf（A,B）： gf（A,B）：
-f(A,C) -m(C,D) -m(C,B)
－2
－1
gf（A,B）： gf（A,B）：
-f(C,A)
-p(A,C)
－2
gf（A,B）：
-p(C,D)
0
gf（A,B）：
-p(C,B)
gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）： gf（A,B）：
-f(A,C),
-f(A,C),
-f(A,C),
-f(A,C),
-f(A,C), -f(A,C), -f(A,C),
m(C,B) f(D,A)
p(A,C)
p(D,C)
p(C,B)
p(D,A)
m(D,C)
ｰ3
・
・
・
・
・
・
ｰ1
ｰ3
・
・
・
・
・
・
ｰ1
・
・
・
・
・
・
ｰ3
2
・
・
・
・
最良な仮説
・
・
ｰ3
gf(A,B):-f(A,C),m(D,C),f(A,E),
m(C,B),f(F,A), p(A,C),
p(D,C),p(A,E),p(C,B),p(F,A)
4 － (10+0)= ｰ6
143
実世界での応用
・突然変異性物質の判別問題（King）
事例：突然変異を有する化合物
背景知識：化合物の原子と結合情報

仮説：化合物の突然変異性に関するルール
・データベースからの知識発見（嶋津，古川）
電子メール分類システム
・暗黙知の獲得（古川）
理想的な弓の動かし方
144
まとめ
・Progolにおける仮説生成
逆伴意に基づき，背景知識と正例から最弱仮説
を生成
最弱仮説を包摂する木においてA*-like探索
・Progolの利点
探索空間が縮小される
145
146
背景知識
・既に持っている知識
・背景知識があるとより正確な理論が
得られる
・背景知識として、事実とルールが利用
可能
147
背景知識なし
正例：D1 = CuddlyPet(x)  Small(x) , Fluffy(x) , Dog(x)
D2 = CuddlyPet(x)  Fluffy(x) , Cat(x)
C = CuddlyPet(x)  Fluffy(x)
Cuddly：やわらかい
Fluffy：ふわふわした
背景知識あり
背景知識： Pet(x)  Cat(x) , Pet(x)  Dog(x)
Small(x) Cat(x)
D = CuddlyPet(x)  Small(x) , Fluffy(x) , Pet(x)
148
特殊な節とは？
・節には半順序関係がある
一般的
一般的：多くの例を説明する
特殊：少ない例しか説明しない
p(A,B) ＞ p(A,A).
一般的
特殊
p(A,B) ＞ p(A,B):-q(A,B)
p(A,B) ＞ p(桂子,B)
特殊
149
記述長最小原理
・学習の記述量・・・機械学習にとって重要な問題
・記述量の多い仮説が多くの例を説明できるのは
当然
できるだけ少ない記述量で多くの例を説明はできないか？
記述長最小原理
150
包摂（subsumption）とは？
定義： H1,H2:節
H1θ ⊆ H2 となるような代入θが存在
H1はH2をθ-subsume（θ-包摂）する。
例: parent（花子, 太郎）:- mother(花子, 太郎)を考える
包摂する節
parent(花子, 太郎)
parent (A, 太郎)： - mother(花子, 太郎)
parent (A, B) :- mother (A, B)
包摂しない節 parent(花子，次郎)
parent (A, B) :- mother (B, A)
包摂＝部分集合＋逆代入
151
伴意と包摂の関係
A subsume(包摂する) B
 A ⊨ B
これがなり立つ！
積極的に利用しよう
伴意を包摂で近似する
152
部分連言だと伴意される
A=l1･･･ln
B=l1･･･lnln+1
Bの解釈はAの解釈でもある
B ⊨ A ：BはAを伴意する
153
正例：
gf（波平，タラオ）
gf（洋平，カツオ）
gf（洋平，サザエ）
gf（洋平，ワカメ）
負例：
gf（波平，カツオ）
gf（舟，タラオ）
gf（洋平，タラオ）
背景知識：f（波平，サザエ）， m（舟，ワカメ），
f（波平，カツオ），f（波平，ワカメ），
m（サザエ，タラオ），f（洋平，波平）
p（A，B）:- f（A，B），p（A，B）:- m（A，B）
154
引用はここまで。
155
ILPは機械学習の主要な手法
• 人工知能の分野にも多くのインパクトを与え
ている。
• ILPも年々進化している。
• Logicも進化している！
• 感性科学や脳科学もAIに関わって来ている。
新しいAIの手法を自分の力で考え出そう！
156
レポート課題
• 課題：
論文“Inverse entailment and Progol
(Muggleton)”のAppendixes A.Definitions
from logic (A1～A3)を和訳せよ。
• 提出方法
– 提出期限：平成２４年２月８日（水）１７：００
– 提出先：研A６階レポート提出ボックス
– 書式：A4レポート用紙（表紙を付けること）
157

Download Report