矛盾した知識

デフォルト推論



仮説を用いた推論



デフォルト規則
デフォルト理論の拡張 → デフォルト証明
シナリオ
アブダクション
準無矛盾推論
©2008 Ikuo Tahara
1
デフォルト推論

 M  
デフォルト規則
 :

「前提  が成り立ち
理由付け  が無矛盾ならば,
結論  が成り立つ」
 :

 と が同一(
)

正規デフォルト規則

閉正規デフォルト規則
と  が閉式
©2008 Ikuo Tahara
2
デフォルト理論

デフォルト理論   ( D,W )

D :デフォルト規則の集合

W :閉式の集合
penguin( Hanako)
が明示されるとこの結
論は成り立たない
例外の処理
bird ( x) : fly ( x)
fly ( x)
x.[ penguin( x)  fly ( x)]
bird ( Hanako)
fly( Hanako)
©2008 Ikuo Tahara
3
デフォルト理論
閉世界仮説
: student ( x)
student ( x)
student (Taro) ?
YES
student ( Jiro) ?
NO
student (Taro)
フレーム公理
holds( f , s) : holds( f , after ( g , s))
holds( f , after ( g , s))
©2008 Ikuo Tahara
4
デフォルト理論の拡張

デフォルト理論のもとで何が成り立つか?
E
  ( D,W )
拡張 E (Reiterの定義)
(1) E0  W
  :

(2) Ei 1  Th( Ei )  
 D,   Ei ,   E 




(3) E  Ei
i 0
©2008 Ikuo Tahara
5
デフォルト証明

閉正規デフォルト理論の性質



拡張は少なくとも一つ存在する.
デフォルト規則については単調である.
閉式  が閉正規デフォルト理論   ( D,W )
から導き出される.
  E なる拡張 E が存在する.
©2008 Ikuo Tahara
6
デフォルト証明

  ( D,W ) に関する  のデフォルト証明
Dの部分集合の系列: D0 , D1 ,
無矛盾

CONS (D0 )
PRE( D0 )
CONS ( D1 )
PRE(D1 )
, Dk 1 , Dk
(Di  D, Dk  )
  :

CONS ( Di )  
 Di 



 :
PRE ( Di )   (for 
 Di )

CONS ( Dk 2 )
PRE( Dk 2 ) CONS (Dk 1 )
W
PRE( Dk 1 )
©2008 Ikuo Tahara
7
線形導出によるデフォルト証明
 ( x) 
bird ( x) : fly( x)
fly ( x)
x[ penguin( x)  fly( x)]
bird ( Hanako)
fly( Hanako) ?
線形導出L0
線形導出L1
( fly( Hanako),{}) の証明
(bird ( Hanako),{ ( Hanako)}) の証明
(fly( Hanako),{})
( fly( x),{ ( x)})
(bird ( Hanako),{ ( Hanako)})
(bird ( Hanako),{})
( ,{ ( Hanako)})
( ,{ ( Hanako)})
©2008 Ikuo Tahara
8
仮説を用いた推論

知識=事実集合+仮説集合
仮説集合 H
仮説集合の要素はすべて原子式
で表現できる
, H 
事実集合 
演繹
知識
, H 
H   h   H 
    h     H 
無矛盾
©2008 Ikuo Tahara
9
仮説を用いた推論

デフォルト推論は仮説推論として定式化できる
bird ( x) : fly( x)
 ( x) 
fly ( x)
x.[ penguin( x)  fly ( x)]
bird ( Hanako)
デフォルト理論
H
 ( x)

 ( x)  (bird ( x)  fly( x))
x.[ penguin( x)  fly ( x)]
bird ( Hanako)
©2008 Ikuo Tahara
10
仮説推論の方法(1)

シナリオ
(1) S  H
(2)   S は無矛盾
という条件を満たす極
大な   S を , H 
のシナリオという.
仮説集合 H
事実集合 
シナリオ
知識
©2008 Ikuo Tahara
11
仮説推論の方法(1)

軽信的方針と懐疑的方針
H
p

p
pq
p  q
r
, H  から何が得られるか?
q
r
q
©2008 Ikuo Tahara
r
12
仮説推論の方法(2)

説明(アブダクション)
閉式 G が与えられたとき
(1)   E G
(2)   E は無矛盾
を満たす論理式の集合
E  H を, H  からの
G?
G の説明という.
仮説集合 H
事実集合 
知識
©2008 Ikuo Tahara
13
説明の計算
 とGから前向き推論によっ
てEを求めることができる

結論発見問題
  E G
  G  E
E が説明で E  E  ならば
E  も説明である.

極小説明
説明 E のいかなる真部分集合も説明でないとき,
E を極小説明という.
©2008 Ikuo Tahara
14
説明の計算(命題論理の場合)

極小支持節

 :命題論理節集合
極小支持節の否定形
が極小説明である!
C :質問節
( S  C )
(1)   {S} C
(2)  {S} は無矛盾 ( – S )
を満たす節 S を に関する C の支持節といい,S を
包摂するいかなる S 以外の節も支持節でないとき
S を極小支持節という.

Sからいくつかのリテ
ラルを除去した節
©2008 Ikuo Tahara
15
説明の計算(命題論理の場合)

極小支持節の計算法

MS (, C ) :  に関するCの極小支持節の集合

PI ()
:  のprime implicateの集合
MS (, C)  {P  C | P  PI (), P  C  }
PからCのリテラルを除去
  {S} C
 S  C
Sが極小ならば  の
prime implicateである
©2008 Ikuo Tahara
PとCは共通の
リテラルを持つ
16
例(ライトが点灯するのは?)
S1
on
S2
on
off
off
S3
on
off
S1 :スイッチS1がon
S2 :スイッチS2がon
S3 :スイッチS3がon
L
L :ライトLがon
S1 S1
S2
S 2
S3
S3
S1  S2  S3  L
S1  S2  L
S1  S3  L
©2008 Ikuo Tahara
L?
17
例(ライトが点灯するのは?)

事実集合のprime implicateを求める
S1  S2  S3  L
S1  S2  L
S1  S2  S3  L
S1  S2  L
S1  S3  L
S1  S3  L
S1  S3  L
S3  L
©2008 Ikuo Tahara
18
例(ライトが点灯するのは?)

Lの極小説明を求める
S1
S1  S2  L
S3  L
on
S2
on
off
S3
on
off
off
L  L (自明なprime implicate)
L
Lの極小支持節: {S1  S2 , S3 , L}
Lの極小説明:
{S1  S2 , S3 , L}
©2008 Ikuo Tahara
19
準無矛盾推論
矛盾した知識



合理的な結論
極大無矛盾集合に基づく方法
議論に基づく方法
多値論理による方法
合理性の判断基準
結論の成立条件
©2008 Ikuo Tahara
20
極大無矛盾集合に基づく方法
矛盾した知識 極大無矛盾集合
p q p  r
p q q  r
p q p  r
p q q  r
p q p  r
p q q  r
p q p  r
p q q  r
©2008 Ikuo Tahara
21
極大無矛盾集合に基づく方法
r を導く極大無矛盾集合は?
p q p  r
p q q  r
p q p  r
p q q  r
p q p  r
p q q  r
p q p  r
p q q  r
極大無矛盾集合を
区別したい!
©2008 Ikuo Tahara
22
文脈

 の極大無矛盾集合を S1 ,
, Si ,
, Sn と
したとき
(1) C  Si は無矛盾
(2) C  S j ( j  i ) は矛盾
となるような論理式C を S i の文脈という.
 \ Si の要素の否定の連言は S i の文脈
である
©2008 Ikuo Tahara
23
文脈の例
pq
矛盾
p q p  r
p q q  r
p q p  r
p q q  r
p q p  r
p q q  r
p q p  r
p q q  r
©2008 Ikuo Tahara
24
文脈

複数の極大無矛盾集合を指定する文脈
極大無矛盾集合 S1 , S 2 , , S k の文脈をそ
れぞれ C1 , C2 , , Ck とすれば
C1  C2 
は S1 , S 2 ,
 Ck
, S k を指定する文脈である.
©2008 Ikuo Tahara
25
r を導く文脈
pq
p q p  r
p q q  r
p  q
p q p  r
p q q  r
p  q
p q p  r
p q q  r
p q p  r
p q q  r
©2008 Ikuo Tahara
26
r を導く文脈
p  q
 ( p  q)
p q p  r
p q p  r
p q( p qq)
 ( pr q)  (p 
q)p q q  r
 pq
p q p  r
p q q  r
矛盾
p q p  r
p q q  r
©2008 Ikuo Tahara
27
議論
無矛盾な極小集合
知識

S
S 

 S ,  :  からの議論
S の要素がすべて成り
支持
結論
©2008 Ikuo Tahara
立つとき議論は健全で
あるという
28
議論間の関係

対立関係

S1
S2


反駁(rebut)
  
無効化(undercut)
  1 (1  S1 )
弱無効化(weakly-undercut)
不同意(disagreement)
©2008 Ikuo Tahara
29
議論の有効性

議論 A  S ,  について
無効化する議論が存在しない
・反駁する議論が存在しない
・不同意な議論が存在しない
・弱無効化する議論が存在しない
A を無効化する議論が存在しないか,存在して
もすべて健全でないとき,A は有効であるという
©2008 Ikuo Tahara
30
結論の正当化条件

結論  を導く議論 A を有効にするには
A を無効化する議論を健全でなくすれ
ばよい
論理式 s のもとで,結論  を導く議論の少なく
とも一つが有効であるとき,s を  の正当化条
件という
©2008 Ikuo Tahara
31
r を導く議論の正当化条件
p q p  r
p q q  r
pq
 {p}, p 
 {q}, q 
 { p, p  r}, r 
 {q, q  r}, r 
©2008 Ikuo Tahara
32
ダウンロード

矛盾した知識