19章＆20章

エージェントアプローチ
人工知能
B4 片渕聡
1
目次

１９章学習における知識

２０章統計的学習手法
2
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
3
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
4
経験による学習

仮説(規則)Hと例(入力)Dから分類(出力)Cを伴意
－H∧D ╞ C (Hは未知)
例 H：Father(y,z)∧Mother(x,y)⇒GrandMother(x,z)
D:Father(Tom,Bob) , Mother(Mary,Tom)
C:GrandMother(Mary,Bob)

上記の式の関係を伴意制約と呼ぶ
5
事前知識の利用

１８章では新たな経験から規則を導出
－事前知識を用いていない

１９章では事前知識を役立てる手法を紹介
－事前知識の利用で学習能力が大幅に向上
例：原始人Aが串を用いて調理している所を
それまで素手で調理していた原始人Bが目撃
することにより原始人Bは素手を使わない
調理法を学習することができる
6
論理による学習の表現

例を正確に分類するための目標述語Q(x)
－例：レストランで待つかどうか (WillWait(x))

Q(x)と等価な論理表現(仮説)の候補定義C(x)

学習の目的はQ(x)と等価なC(x)の導出
－∀x Q(x) ⇔ C(x)
7
論理による学習の表現
（例：レストラン問題）

１８章で作成した決定木を定式化すると
∀x WillWait(x) ⇔ Patrons(x,some)
∨ ( Patrons(x,full)∧￢Hungry(x) )
仮説

新たな例が加わると例に矛盾する仮説を修正
例：Patrons(X,Full)∧Wait(X,0-20)∧
Hungry(X)∧WillWait(X)
－この例は上記の式に矛盾
仮説Patrons(X,Full)∧Wait(X,0-20)∧Hungry(X)を追加
8
にせの負例・にせの正例

にせの負例
－実際はTrueなのに仮説がFalseを返す例
にせの負例

T
T T
F
F
にせの正例
－実際はFalseなのに仮説がTrueを返す例
にせの正例
F T T
F
F
9
最良仮説探索

新たな例が与えられる度に仮説を改定する方法
－仮説の無矛盾性を維持

汎化
特化

10
汎化・特化

汎化
－仮説がにせの負例を含むようにすること
汎用化

T
T T
F
F
F
F
特化
－仮説がにせの正例を排除すること
特化
F
T T
11
最小選択探索

予め膨大な仮説空間を用意して
新たな例に矛盾する仮説を除去していく

初期仮説空間 H1∨H２∨ …∨Hn
例集合に矛盾した仮説をどんどん排除

後戻り(仮説の追加)の必要が無い
12
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
13
事前知識を用いた学習の概念
背景知識
(事前知識)
蓄積
利用
観測

帰納学習
仮説
予測
EBL・RBL・KBIL
14
説明に基づく学習
（Explanation-Based Learning:EBL）

背景知識Bから一般的な規則Hを伴意
観察Dを背景知識を用いて説明
－H∧D ╞ C (Hは未知)
－B ╞ H
例 D:串で調理している人がいる
B:串で食物を支えることができる
H:細くて硬い物体で食物を支えることができる
15
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
16
関連性に基づく学習
（Relevance-Based Learning:RBL）

観察を説明するような一般規則を
背景知識を用いて導出
－H∧D ╞ C (Hは未知)
－B∧D∧C ╞ H
例 B:特定の国の人は皆同じ言語で話す
D:Fernandoはブラジルの人でポルトガル語を話す
H:ブラジルに住む人はポルトガル語を話す
17
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
18
知識に基づく帰納学習
（Knowledge-Based Inductive Learning:KBIL）

背景知識Bと新たな仮説Hで例を説明
－B∧H∧D ╞ C （含意制約）

帰納論理プログラミング
19
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
20
帰納論理プログラミング
（Inductive Logic Programming:ILP）

含意制約を満たしつつ未知の仮説を導出
－例：家系図
George
Elizabeth
Charles
Mum
Philip
Anne
21
背景知識を用いた例の説明

背景知識なしでGrandparentに対する仮説は
Grandparent(x,y)⇔ [∃z Mother(x,z)∧Mother(z,y)]
∨ [∃z Mother(x,z)∧Father(z,y)]
∨ [∃z Father(x,z)∧Mother(z,y)]
∨ [∃z Father(x,z)∧Father(z,y)]

背景知識 Parent(x,y) ⇔ Mother(x,y)∨Father(x,y)
を用いると簡略化が可能
Grandparent(x,y) ⇔ [∃z Parent(x,z)∧Parent(z,y)]
22
トップダウン帰納学習手法

一般規則から例に合うように特殊化していく
例：Grandfather(x,y)の定義の学習
１．例を正例と負例に分ける
正例：<George,Anne>etc 負例：<Mum,Anne>etc
２．左辺が空の節を構築
[] ⇒ Grandfather(x,y)
３．これでは負例も含むので特化する(繰り返し)
Father(x,z) ⇒ Grandfather(x,y)
Father(x,z) ∧ Parent(z,y) ⇒ Grandfather(x,y)
23
逆演繹による帰納学習(1/2)

逆向き（逆融合）の証明を行う
仮説
￢Parent(Elizabeth,y)∨ Grandparent(George,y)
{y/Anne}
KB
Parent(Elizabeth,Anne)
Grandparent(George,Anne)
KB(否定)
￢Grandparent(George,Anne)
24
逆演繹による帰納学習(2/2)
１．目標例C2を規定 Grandparent(George,Anne)
２．空の節とC2の否定を逆融合して
Grandparent(George,Anne) (C1)を生成
３． C1と知識ベースにある
Parent(Elizabeth,Anne)とを逆融合
４．仮説
￢Parent(Elizabeth,y)∨ Grandparent(George,y)
を生成
５．さらに逆融合していくことで新たな仮説が得られる
25
１９章学習における知識
目次





学習の論理的な定式化
説明に基づく学習(EBL)
関連性に基づく学習(RBL)
知識に基づく学習(KBIL)
－帰納論理プログラミング(ILP)
まとめ
26
まとめ






事前知識の利用により学習能力が向上
汎化・特化を行い例に無矛盾な仮説を構築
説明による学習： B ╞ H
関連性による学習： B∧D∧C ╞ H
知識に基づく学習： B∧H∧D ╞ C
帰納論理プログラミング：KBILの実行手法
－トップダウン帰納学習手法
－逆演繹による帰納学習
27
ここまで１９章

演繹
－前提が真ならば結論も真だと認めざるを得ないこと
前提 ⇒ 結論
28
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
29
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
30
確率モデルの学習

実環境は不確実性に満ち溢れている
経験から実環境の確率法則を学習

統計的学習
－確率推論の学習
31
統計的学習（例）

くじ箱が５つあり、そこから一つ選んでくじ引き
d:くじ引きであたりを引くという事象
h1:100%あたり P(d|h1)=1.0
h2:80%あたり P(d|h2)=0.8
h3:50%あたり P(d|h3)=0.5
h4:20%あたり P(d|h4)=0.2
h5:0%あたり
P(d|h5)=0
※dはデータ、hは仮説と呼ぶことにする
32
ベイズ学習

観測データが与えられた時の仮説の確率を計算
－P(hi|d)=αP(d|hi)P(hi) (ベイズ規則)
例：外れを2回引いたとき
P(h5|d)=α×12×0.2≒0.2127

データを得た時にあたりを引く(事象X)確率分布は
P(X|d)=ΣP(X|hi)P(hi|d) (定義)
と予測できる
33
最大事後確率学習
(Max A Posteriori:MAP)

与えられたデータの元で尤もらしい仮説を採用
－P(X|d)≒P(X|hMAP)の近似

ベイズ学習の単純化
計算量の緩和

34
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
35
完全なデータからの学習

完全なデータ
－モデルの全ての確率変数を含む観測データ

完全なデータからの学習
－観測モデルの未知のパラメータの推定
－ベイジアンネットの条件付確率の学習
36
パラメータの最尤学習
離散モデル

当たる確率θのわからないくじにおけるθの導出
１．N個のくじを引いてc個があたりだったとして
このデータが得られるθの尤もらしさ(尤度)は
P(d|hθ)=θc・(1-θ)N-c (hθ：比率θの仮説)
２．尤度の対数(対数尤度)を取る
L(d|hθ)=log(P(d|hθ))=clogθ+(N-c)log(1-θ)
３．θで微分して得られた式を0にするθを求める
dL(d|hθ) c
l
=θ 1-θ
+
dθ
=0 ⇒ θ=
N
c
37
パラメータの最尤学習
連続モデル

確率変数θが連続値をとる場合の最尤学習
・P(θ)が連続関数になる
－離散モデルと同様の処理で求まる

意思決定にはθが最大になる仮説を採用
－離散モデルも同様
38
パラメータのベイズ学習

ベータ分布（一様分布）の利用
beta[a,b](θ)=αθa-1・(1-θ)b-1
a,b:超パラメータ(分布の形に影響)

あたりを引いた場合
P(θ|d1)=αP(d1|θ)P(θ)=α’beta[a,b](θ)・θ
=beta[a+1,b](θ)
あたりを引くたびにaを1増やし
はずれを引くたびにbを1増やすだけで
事後確率の更新が可能
39
素朴ベイズモデル

予測の対象Cを観測の対象Xiから求める
－P(C|x1,x2)=αP(C)P(x1|C)P(x2|C)
P(c)=0.5
C
t
f
P(x1)
0.1
0.5
C
X1
X2
C
P(x2)
t
0.8
f
0.2
40
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
41
隠れ変数を含む学習
EMアルゴリズム

隠れ変数を用いることで問題を単純化できる
－隠れ変数：学習の際に観測不能な変数
A
B
A
B
隠れ変数
E
C

D
C
D
隠れ変数を用いることでややこしくなることも多い
EMアルゴリズム
42
期待値最大化法
(Expectation Maximization):EM

隠れ変数が存在する時の最尤学習を行う手法
－パラメータの更新
θ(i+1)=argmaxΣP(Z=z|x,θ(i))L(x,Z=z|θ)
θ
Z:全ての隠れ変数 L:対数尤度



教師なしクラスタリング
－対象の集合をカテゴリに分類・識別
ベイジアンネットの学習
隠れマルコフモデルの学習
43
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
44
事例に基づく学習

ノンパラメトリック学習
－確率分布に関する仮定を設けずに行う学習
・パラメータの学習にはベータ分布を用いた


最近傍モデル
カーネルモデル
45
最近傍法

ある点xとその近傍にある点x’は似ているだろう
－点xの近くにある点だけを参照
・k個参照する場合は
k近傍法

距離を測るための尺度D(x,x’)を使用
－ハミング距離・マハラノビス距離etc
46
カーネルモデル

観測データに距離によって重み付けを行う
－重み付けにはよくガウス分布が使われる
1
ω2√(2π)d
K(x,xi)=
e
D(x,xi)2
2ω2
(赤字は全て未知)
カーネル関数

確率密度関数P(x)は
P(x)=1/NΣK(x,xi)
i
47
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
48
ニューラルネットワーク

人工的なニューロン(神経細胞)の働きの構築
－電気的信号の収集・処理・伝達
W0,i
Wj,i
ユニットi
Σ
g
ai
収集処理伝達
49
ニューラルネットワークのユニット

入力：ini=ΣajWj,I （0≦ini≦1）
ｊ
－ユニットjの活性度(出力値)aj
－ユニットjとiの(結合の)重みWj,i
※固定入力a0=-1に対するバイアス重みW0,i


処理：活性度関数g(ini) 人間が設定
出力：ai=g(ini) （0≦ai≦1）
50
ニューラルネットワークの構造

前向き結合ネットワーク
－入力に対して出力をただ返す

回帰結合ネットワーク
－出力値がもう一度入力に用いられる
51
前向き結合ネットワークにおける
単純な計算

下図の例ではa5を計算
入力ユニット
1
3
5
2

4
隠れユニット
出力ユニット
a5=g(W3,5a3+W4,5a4)
=g(W3,5g(W1,3a1+W2,3a2)+W4,5g(W1,4a1+W2,4a2))
52
ニューラルネットワークにおける学習

ネットワーク全体の出力(前スライドa5)が
他のネットワークに対する入力関数となる
ネットワーク全体の関数はhW(a1,a2)

Wを調節することでネットワークの関数が変化
パラメータWの調節による関数の変化の学習
53
多層前向き結合ニューラルネットワーク
（パーセプトロン）


隠れユニットを持たない前向き結合ネットワーク
－出力ユニットが１つのみ
ブール関数を表現可能
I1 超平面
－閾関数パーセプトロン
IFΣWjxj>h (h:閾値)
RETURN 1
I1 xor I2は表現不可
I2
I1 or I2
54
多層前向き結合ニューラルネットワーク

隠れユニット(変数)を含む前向き結合ネットワーク
表現力の向上
1
3
5
2

4
誤差逆伝播アルゴリズム
－出力値の誤差を最小にするアルゴリズム
任意の関数の近似に利用
55
カーネルマシン


単層ネットワークでは表現できる関数が乏しい
多層ネットワークでは局所的最適解が沢山出る
カーネルマシン
－上のジレンマをある程度解消
複雑な関数を表現可能かつ
効率的な学習アルゴリズムを持つ
56
２０章統計的学習手法
目次






統計的学習とは
完全なデータからの学習
隠れ変数を含む学習(EMアルゴリズム)
事例に基づく学習
ニューラルネットワーク
まとめ
57
まとめ




統計的学習：確率分布の学習
隠れ変数による問題の単純化や表現力の向上
仮定を設定しない学習：最近傍法・カーネルモデル
ニューラルネットワーク：収集・処理・伝播
58
応用例：手書き数字認識

3近傍法により下記の手書き数字も認識可能

各々の図形に近似している図形(Best3)を参照
－これだけでは精度に難あり
専用ニューラルネットワーク
Boostedニューラルネットワークetc
59

Download Report