1
Chương
4
Chương
4
Tri thức và suy diễn
Lê Thanh Hương
Khoa CNTT
-
ĐHBK HN
1
Khoa
CNTT
ĐHBK
HN
4.1. Tri thức là gì?
•Dữ liệu và Tri thức: là những dạng khác nhau
của thông tin nên khó phân biệt rạch ròi
Tri thức
- ký hiệu tượng trưng
-tản mạn
-cấu trúc phức hợp
Dữ liệu
-số
-có cấu trúc
-cấu trúc đơn giản
2
-VD: Đông y:
- hâm hấp sốt
-mạch nhanh/chậm
- VD: Tây y:
-t
0390
-mạch 75
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phân loại tri thức
aTrithứcmôtả: what?
a
.
Tri
thức
mô
tả:
what?
–về tình huống (GT + KL): sự kiện
–về lĩnh vực: luật nếu … thì
3
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phân loại tri thức
b. Tri thức thủ tục: how?
–
Modus Ponens
–
Modus
Ponens
– Modus Tollens
Tri thức cũ về tình huống --------→Tri thức mới về t/huống
Hiểu biết về lĩnh vực
Modus Ponens Modus Tollens
4
A, A →B A →B, ¬B
B ¬A
•Ví dụ: Trán rộng →Thông minh
Bình: trán rộng ⇒Bình thông minh
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
2
Phân loại tri thức
cTrithứcđiềukhiển: heuristic
c
.
Tri
thức
điều
khiển:
heuristic
–Chọn hướng suy diễn: tiến, lùi, hỗn hợp
–Chọn luật áp dụng: đảm bảo đủ, không
thừa, có cấu trúc, ngắn gọn
–Vẽ hình phụ
5
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 1: Chứng minh bài toán hình học
•Mô tả?
•Thủ tục?
•
GT, KL, hình vẽ+ Định lý, tính chất
Áp dụng định lý đường trung bình vào tam giác ABC ta có
Nghĩ
→
SD tiến, lùi; Viết
→
SD tiến
Cho X = 600, Y = 600. CM XY = XZ, XY = YZ
Mô tả:
•Sự kiện: Bnhau(XY,UV) Bang(X,Y) Banggoc(X,a)
•Luật:
– Bnhau(XY,UV) ⇒bnhau(UV,XY)
–
Bnhau(XY,UV)
⇒
bnhau(XY,VU)
Nghĩ
→
SD
tiến,
lùi;
Viết
→
SD
tiến
X
YZ
60
60
6
Bnhau(XY,UV)
⇒
bnhau(XY,VU)
– Bang(Y,Z) ⇒bnhau(XY,XZ)
– Bnhau(XY,UV) ∧bnhau(UV,ST) ⇒bnhau(XY,ST)
– ???
• Ban đầu: banggoc(X,60), banggoc(Y,60)
•Đích: bnhau(XY,XZ), bnhau(XY,YZ)
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 2
Hlà1 thỏ
H(H )
•
H
arry
là
1
con
thỏ
H
are
(H
arry
)
• Tom là 1 con rùa Tortoise(Tom)
•Thỏ chạy nhanh hơn rùa
),()()(, yxOutrunsyTortoisexyHarex →∧∀
7
• Harry chạy nhanh hơn Tom?
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tom và Harry
Tri thức mô tả:
•
Giảthiếtdướidạng phép And
Giả
thiết
dưới
dạng
phép
And
•Luật
•Kết luận
)()( TomTortoiseHareHarry
∧
),()()( TomHarryOutrunsTomTortoiseHarryHare →
∧
)
(
T
H
Ot
8
Tri thức thủ tục?
Tri thức điều khiển?
)
,
(
T
om
H
arry
O
u
t
runs
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3
Bản chất tri thức chuyên gia
Làm sao để chuyển tri thức từ chuyên gia con
ờià á
Æ
kỹ ử lý t i thứ
lĩnh vực
chuyên môn
tin học
ch/gia đầu ngành giỏiε1∼0
ngư
ời
v
à
o m
á
y
Æ
kỹ
sư x
ử
lý
t
r
i
thứ
c
9
lập trình viên ε2
∼
0giỏi
ksư xử lý tri thức khá khá
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Biểu diễn tri thức
Có
nhi
ều
các
h
b
i
ểu
d
i
ễ
n
t
ri
t
h
ức
.
Có
nhiều
cách
biểu
diễn
tri
thức.
GT, KL →sự kiện →mệnh đề, vị từ →đỉnh
R →luật →mệnh đề, vị từ, sản xuất →cung ngữ nghĩa
1. BDTT = logic
2. BDTT = luật sản xuất
3
BDTT = mạng ngữnghĩa
10
3
.
BDTT
=
mạng
ngữ
nghĩa
4. BDTT = frame
5. BDTT = bộ 3 Object – Attribute - Value
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = logic
•
BDTT = logic mệnh đề
BDTT
=
logic
mệnh
đề
–Tri thức mô tả:
•Các mệnh đề p, q, r, …
•Các luật suy diễn (đưa về dạng chuẩn Horn)
p1 ∧p2 ∧… ∧pn ⇒q
–
Tri thức thủ t
ụ
c:
11
ụ
• modus ponens: {A, A →B} →{A,B}
• modus tollens: {A →B, ¬B} →{¬A, ¬B}
–Tri thức điều khiển: tiến, lùi
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ
• Nếu trời đ
ẹp
thì đi chơi.
ẹp
p q
• Nếu đi chơi và có tiền và có thời gian thì đi Hồ Tây.
q s t u
• Nếu đi Hồ Tây và có tiền và có thời gian thì đi Nhật Tân.
u s t v
•
Nếu đi Nhật Tân thì mời Lâm
12
•
Nếu
đi
Nhật
Tân
thì
mời
Lâm
.
v w
• Nếu mời Lâm thì mời bạn Lâm.
w x
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
4
BDTT = luật sản xuất
Các luật sản xuất có dạng:
•Nếuđiều kiện 1
. . . . .
và điều kiện m
•thì kết luận 1 và … và kết luận n
• Trong logic mệnh đề hay vị từ, đk1…đkm, kl1…klnlà
những biểu thức logic, còn cặp nếu…thì thì ⇔dấu →
13
• Trong nguyên tắc dịch
– one →một
– one →người ta
– one →cái
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = mạng ngữ nghĩa
•
Mạng ngữnghĩalàmộtđồ thịđịnh hướng
Mạng
ngữ
nghĩa
là
một
đồ
thị
định
hướng
G=(N,A), trong đó
–N -tập các đối tượng, các sự kiện hay các khái
niệm cụ thể (đỉnh)
–A -tập các mối liên hệ giữa các cặp đối tượng, sự
kiện hay khái niệm (cung)
–
A
=
{(x,y) | x,y
∈
N}
=
∪
{(x,y) | x R
i
y}
14
A
{(x,y)
|
x,y
∈
N}
∪
{(x,y)
|
x
R
i
y}
Rilà 1 quan hệ nào đó trên tập N
•VD: Giải bài toán lượng giác: cho biết a,b,ma.
Tìm hc
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = frame
• Là 1 dẫn xuất của BDTT = mạng ngữ nghĩa, là cơ sở
của phương pháp xử lý thông tin kiểu hướng đối tượng
•
Phương pháp BDTT = logic và mạng ngữnghĩa mang
mạng
ngữnghĩa
frame (tri thức
hướng đốitượng)
•
Phương
pháp
BDTT
=
logic
và
mạng
ngữ
nghĩa
mang
đặc trưng mô tả
•Phương pháp BDTT = luật sản xuất : thủ tục
•Phương pháp BDTT = frame kết hợp mô tả và thủ tục
15
ngữ
nghĩa
hướng
đối
tượng)
thực thểđỉnh đối tượng (object)
quan hệcung phân cấp (hierachy)
VD: …
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = bộ 3
Object – Attribute - Value
•
VD:
•
VD:
–(bồ câu, là, chim)
–(bồ câu, biết, ăn) ⇔mạng ngữ nghĩa
–(bồ câu, biết, bay)
16
•Hạn chế: chỉ thể hiện được những quan
hệ “=“, khó khăn khi biểu diễn ≥, ≤, …
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
5
Các phương pháp chứng minh
•
Chứng minh sửdụng phương pháp tìm kiếm
Chứng
minh
sử
dụng
phương
pháp
tìm
kiếm
•Hợp giải (kỹ thuật chứng minh)
• Suy diễn
– Sinh các câu mới từ các câu cũ
–Chứng minh = áp dụng các luật suy diễn. Có thể
ửd l ậtdiễhátátửt
17
s
ử
d
ụng
l
u
ật
suy
diễ
n n
h
ư c
á
c
t
o
á
n
tử
t
rong
phương pháp tìm kiếm chuẩn
–Thường đòi hỏi chuyển các câu sang dạng chuẩn
Horn
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Kỹ thuật CM Suy diễn
BT = GT + KL
GT →KL
CM
BT = GT + KL
GT →KL
R
18
CM
GT + ¬KL →><
R
GT + R →KL
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn
•Dạng chuẩn Horn
CSTT = tập các câu ở dạng chuẩn Horn
Câ H
–
Câ
u
H
orn =
• các ký hiệu mệnh đề
•biểu thức kết hợp các ký hiệu ⇒ký hiệu
–Ví dụ
C ∧(B ⇒A) ∧(C ∧D ⇒B)
•Modus Ponens (cho dạng chuẩn Horn):
β
19
α1, … ,αn,α1∧…
∧
αn⇒
β
β
•Có thể dùng cho suy diễn tiến và suy diễn lùi
•Các thuật toán này có độ phức tạp tuyến tính.
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn đối với logic mệnh đề
Bài toán: Cho 1 CSTT R
=
{r
1
r
}
Bài
toán:
Cho
1
CSTT
R{r
1
, …,
r
n
}
,
rilà luật, ricó dạng p1∧…∧pm→q
Ngữ nghĩa:
–Nếu p1đúng và … và pmđúng
– thì q đúng
• Cho biết GT=
{
f
1
,
…
,
f
u
}
20
{
1
,,
u
}
•Cần CM KL={q1,…,qv} đúng
• Ta nói KLGT
R
*
a
Lê Thanh Hương – Khoa CNTT - ĐHBKHN