Bài Giảng Nhập Môn Trí Tuệ Nhân Tạo (AI)

NHÂN T OẠT OẠ TRÍTRÍ TUỆTUỆ NHÂN Intelligent Artificial Intelligent Artificial

Khoa Công Nghệ Thông Tin Đ iạ H cọ Bách Khoa – Tp. HCM

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aù ch K h oa Tp .H C M B aû n q u yeàn (cid:211) K h oa C oân g N g h eä Th oân g Tin

Th aù n g 6/2001

iớ thi uệ

N iộ dung môn h cọ – Gi

 Ch

ngươ 1: Gi

iớ thi uệ

sử hình thành và hi nệ tr ngạ

– Ngành Trí tuệ nhân t oạ là gì? – M cụ tiêu nghiên c uứ c aủ ngành Trí tuệ nhân t oạ – L chị – Turing Test

 Ch

ngươ 2: Logic vị từ – M nhệ đề & logic vị từ – Logic vị từ d

iướ góc nhìn c aủ AI

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 2

N iộ dung môn h cọ – Các kỹ thu tậ tìm ki mế

 Ch

ngươ 3:Tìm ki mế trên không gian tr ngạ thái

– AI : Bi uể di nễ và tìm ki mế – Các gi iả thu tậ tìm ki mế trên không gian tr ngạ thái – Depth first search (DFS) - Breath first search (BFS)

 Ch

ngươ 4:Tìm ki mế theo Heuristic

iả thu tậ A*

– Heuristic là gì? – Tìm ki mế theo heuristic – Các gi – Chi nế l

iả thu tậ Best first search (BFS), Gi cượ Minimax, Alpha Beta

Baøi giaûng “Trí tueä nhaân taïo” - Slide 3

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

(State Space Search)

N iộ dung môn h cọ – Kỹ thu tậ phát tri nể ngứ d ngụ

 Ch

ngươ 5:Hệ lu tậ sinh

nghĩa và ngứ d ngụ

 Ch

– Tìm ki mế đệ qui – Hệ lu tậ sinh: Đ nhị – Tìm ki mế trên hệ lu tậ sinh ngươ 6:Hệ chuyên gia

iớ thi uệ về hệ chuyên gia

 Ch

– Gi – Mô hình hệ chuyên gia: dự trên lu tậ , d aự trên frame – Phát tri nể m tộ hệ chuyên gia ngươ 7:Bi uể di nể tri th cứ

– Bi uể di nể tri th cứ trong AI: vai trò và ngứ d ngụ – Các kỹ thu tậ bi uể di nể tri th cứ : semantic network, l uư đồ phụ thu cộ khái

ni mệ , frame, script

Baøi giaûng “Trí tueä nhaân taïo” - Slide 4

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Th cự hành &Tài li uệ tham kh oả

 Th cự hành Prolog và CLISP

iả thu tậ tìm ki mế

– Prolog : Các gi – CLISP : Bi uể di nể tri th cứ – Bài t pậ l nớ

 Tài li uệ tham kh oả

– Bài gi ngả “Trí tuệ nhân t o”ạ – ThS Nguy nễ Cao Trí – KS Lê Thành Sách – Artificial Inteligent – George F. Luget & Cilliam A. Stubblefied – Giáo trình “Trí tuệ nhân t o”ạ – KS Nguy nễ Đ cứ C ngườ – Trí tuệ nh nậ t oạ – Nguy nễ Quang Tu nấ – Hà n iộ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 5

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ 1:

1: GI

ngươCh Ch

IỚGI

IỚ THI UỆTHI UỆ

sử hình thành và hi nệ tr ngạ

Ngành Trí tuệ nhân t oạ là gì? M cụ tiêu nghiên c uứ c aủ ngành Trí tuệ nhân t oạ L chị Turing Test

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K h oa C oân g N g h eä Th oân g Tin

Th aù n g 6/2001

Đ iố t

ngượ nghiên c uứ c aủ AI

 Đ iố t

ngượ nghiên c uứ c aủ ngành AI

AI là ngành nghiên c uứ về các hành xử thông minh (intelligent behaviour) bao g mồ : thu th pậ , l uư trữ tri th cứ , suy lu nậ , ho tạ đ ngộ và kỹ năng.

Đ iố t

ngượ nghiên c uứ là các “hành xử thông minh” chứ không ph iả

là “sự thông minh”.

‘Không có’ Sự Thông Minh Chỉ có Bi uể hi nệ thông minh qua hành xử

Baøi giaûng “Trí tueä nhaân taïo” - Slide 7

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Sự Thông Minh

 Thông minh hay Hành xử thông minh là gì?

– Hành xử thông minh: là các ho tạ đ ngộ c aủ m tộ đ iố t

ngườ cho k tế quả t

ngườ ) là bi uể hi nệ cụ thể, c mả nh nậ đ

ngượ như là k tế quả c aủ m tộ quá trình thu th pậ , xử lý và đi uề khi nể theo nh ngữ tri th cứ tố theo mong đ iợ so v iớ đã có hay m iớ phát sinh (th các hành xử thông th cượ c aủ “Sự thông minh”

– Khái ni mệ về tính thông minh c aủ m tộ đ iố t

ngượ th

ngườ bi uể hi nệ qua

các ho tạ đ ngộ :  Sự hi uể bi  Sự lý lu nậ t oạ ra tri th cứ m iớ d aự trên tri th cứ đã có  Hành đ ngộ theo k tế quả c aủ các lý lu nậ  Kỹ năng (Skill)

tế và nh nậ th cứ đ cượ tri th cứ

TRI TH CỨ ???

Baøi giaûng “Trí tueä nhaân taïo” - Slide 8

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Tri th cứ (Knowledge)

 Tri th cứ là nh ngữ thông tin ch aứ đ ngự 2 thành ph nầ

– Các khái ni mệ :

 Các khái ni mệ cơ b nả : là các khái ni mệ mang tính quy  Các khái ni mệ phát tri nể : Đ cượ hình thành từ các khác ni mệ cơ b nả thành

cướ

– Các ph

ngươ pháp nh nậ th cứ :

 Các qui lu tậ , các thủ t cụ  Ph

các khái ni mệ ph cứ h pợ ph cứ t pạ h nơ .

 Tri th cứ là đi uề ki nệ tiên quy tế c aủ các hành xử thông minh hay “Sự

cượ qua sự thu th pậ tri th cứ và s nả sinh tri th cứ

thông minh”  Tri th cứ có đ  Quá trình thu th pậ và s nả sinh tri th cứ là hai quá trình song song và n iố ti pế v iớ nhau – không bao giờ ch mấ d tứ trong m tộ th cự thể “Thông Minh”

Baøi giaûng “Trí tueä nhaân taïo” - Slide 9

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ pháp suy di nễ , lý lu nậ ,..

Tri th cứ – Thu th pậ và s nả sinh

 Thu th pậ tri th cứ : – Tri th cứ đ

cượ thu th pậ từ thông tin, là k tế quả c aủ m tộ quá trình thu nh nậ ngườ quá trình thu th pậ tri th cứ g mồ

dữ li uệ , xử lý và l uư trữ. Thông th các b

cướ sau:

lĩnh v cự /ph mạ vi tri th cứ c nầ quan tâm

 Xác đ nhị  Thu th pậ dữ li uệ liên quan d  Hệ th ngố hóa, rút ra nh ngữ thông tin t ngổ quát, đ iạ di nệ cho các tr

ngườ h pợ cụ thể. iướ d ngạ các tr

ngườ h pợ

 Xem xét và giữ l

đã bi tế – T ngổ quát hóa.

iạ nh ngữ thông tin liên quan đ nế v nấ đề c nầ quan tâm , ta

 S nả sinh tri th cứ :

cượ đ aư vào m ngạ tri th cứ đã có.

cượ thu th pậ sẽ đ

– Tri th cứ sau khi đ – Trên cơ sở đó th cự hi nệ các liên k tế , suy di nễ , ki mể ch ngứ để s nả sinh ra

các tri th cứ m iớ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 10

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

có các tri th cứ về v nấ đề đó.

Tri th cứ – Tri th cứ siêu c pấ

 “Trí th cứ siêu c p”ấ (meta knowledge) hay “Tri th cứ về Tri th c”ứ

Là các tri th cứ dùng để: – Đánh giá tri th cứ khác – Đánh giá k tế quả c aủ quá trình suy di nễ – Ki mể ch ngứ các tri th cứ m iớ

 Ph

ngươ ti nệ truy nề tri th cứ : ngôn ngữ tự nhiên

Baøi giaûng “Trí tueä nhaân taïo” - Slide 11

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Hành xử thông minh – K tế lu nậ

 Hành xử thông minh không đ nơ thu nầ là các hành đ ngộ như là k tế quả

c aủ quá trình thu th pậ tri th cứ và suy lu nậ trên tri th cứ .

 Hành xử thông minh còn bao hàm ngươ tác v iớ môi tr

– Sự t – Sự ti pế nh nậ các ph nả h iồ để đi uề ch nhỉ – Sự ti pế nh nậ các ph nả h iồ để hi uệ ch nhỉ

ngườ để nh nậ các ph nả h iồ

 Tính ch tấ thông minh c aủ m tộ đ iố t

ngượ là sự t ngổ h pợ c aủ cả 3 y uế ngượ trên tri th cứ cượ . Chúng hòa quy nệ vào nhau thành m tộ thể th ngố nh tấ “

tố: thu th pậ tri th cứ , suy lu nậ và hành xử c aủ đ iố t thu th pậ đ Sự Thông Minh”

 Không thể đánh giá riêng lẽ b tấ kỳ m tộ khía c nhạ nào để nói về tính

thông minh.

 THÔNG MINH C NẦ TRI TH CỨ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 12

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

hành đ ngộ - Skill và c pậ nh tậ tri th cứ

M cụ tiêu nghiên c uứ c aủ ngành AI

i”ườ ?

Trí tuệ nhân t oạ nh mằ t oạ ra “Máy ng M cụ tiêu  Xây d ngự lý thuy tế về thông minh để gi

iả thích các ho tạ đ ngộ thông

minh

 Tìm hi uể cơ chế sự thông minh c aủ con ng

iườ

 Cơ chế l uư trữ tri th cứ  Cơ chế khai thác tri th cứ

 Xây d ngự cơ chế hi nệ th cự sự thông minh  Áp d ngụ các hi uể bi

tế này vào các máy móc ph cụ vụ con ng

iườ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 13

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

M cụ tiêu c aủ AI (tt)

 Cụ thể:

– Kỹ thu tậ : xây d ngự các máy móc có tính thông minh nh mằ đáp ngứ t

tố

h nơ nhu c uầ c aủ con ng

iườ .

ngươ pháp

– Khoa h cọ : xây d ngự và phát tri nể các khái ni mệ , thu tậ ngữ, ph cượ các hành xử thông minh c aủ sinh v tậ .

để hi uể đ

– Đ iố t

ngượ th

ngườ đ

cượ chú tr ngọ phát tri nể là máy tính

SựSự c nầc nầ thi LàmLàm saosao bi

tế c aủc aủ ngành tế máymáy cócó thông

????? ngành AIAI ????? thông minhminh??

tếthi tếbi

Baøi giaûng “Trí tueä nhaân taïo” - Slide 14

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Turing Test: Thử tính thông minh

tính thông minh c aủ m tộ đ iố t

ngượ

 Bài toán xác đ nhị  Turing test:

Ai đây??

Máy/ng

iườ ??

iườ th cự hi nệ

test

Đ iố t ngượ đ cượ test Câu h iỏ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 15

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Ng iườ đ iố ch ngứ

Turing Test: uƯ Khuy tế

 uƯ đi mể – Đem l

iạ quan đi mể khách quan về sự thông minh: Thông minh hay không thể

– Lo iạ trừ các thành ki nế : không thích công nh nậ tính thông minh c aủ máy móc. cượ đánh giá qua các câu h iỏ , không bị chi ph iố b iở các y uế

hi nệ qua các trả l iờ c aủ các câu h iỏ

– Tránh tình tr ngạ hi uể l mầ

 Khuy tế đi mể :

– Phép thử t pậ trung vào các công vi cệ bi uể di nể hoàn toàn b ngằ ký hi uệ do đó làm m tấ m tộ đ cặ tính r tấ quan tr ngọ c aủ máy tính là tính toán chính xác và hi uệ quả

Sự thông minh chỉ đ tố khác.

– Không thử nghi mệ đ – Gi

cượ các khả năng tri giác và khéo léo

iớ h nạ khả năng thông minh c aủ máy tính theo khuôn m uẫ con ng iườ . Nh ngư

– Không có m tộ chỉ số rõ ràng đ nhị

con ng iườ ch aư h nẳ là thông minh hoàn h oả .

ngượ cho sự thông minh. Phụ thu cộ vào

Thông MinhMinh? ?  CònCòn tùytùy  Thông l

Baøi giaûng “Trí tueä nhaân taïo” - Slide 16

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

ng iườ tester.

L chị

sử phát tri nể c aủ AI : Giai đo nạ cổ đi nể

 Giai đo nạ cổ đi nể (1950 – 1965)

Đây là giai đo nạ c aủ 2 lĩnh v cự chính:Game Playing (Trò ch iơ ) và

Theorem Proving (Ch ngứ minh đ nhị

ký)

ngườ d nẩ t

Game Playing: d aự trên kỹ thu tậ State Space Search v iớ tr ngạ thái (State) là các tình hu ngố c aủ trò ch iơ . Đáp án c nầ tìm là tr ngạ thái iớ tr ngạ thái th ngắ . áp d ngụ v iớ các trò th ngắ hay con đ ch iơ lo iạ đ iố kháng. Ví dụ: Trò ch iơ đánh cờ vua.

Có 2 kỹ thu tậ tìm ki mế cơ b nả :

 Kỹ thu tậ generate and test : chỉ tìm đ  Kỹ thu tậ Exhaustive search (vét c nạ ): Tìm t

cượ 1 đáp án/ ch aư ch cắ t iố uư .

tấ cả các nghi mệ , ch nọ l aự

ph ngươ án t tố nh tấ .

((BùngBùng nổnổ tổtổ h pợh pợ mnmn v iớv iớ mm>=10) >=10)

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 17

L chị

sử phát tri nể c aủ AI : Giai đo nạ cổ đi nể (tt)

cướ , ch

ngươ trình sẽ iớ bi uể th cứ c nầ ch ngứ

Theorem Proving: d aự trên t pậ tiên đề cho tr th cự hi nệ chu iỗ các suy di nể để đ tạ t minh.

N uế có nghĩa là đã ch ngứ minh đ

cượ . Ng

cượ l

iạ là không ch ngứ

minh đ

cượ .

iả toán,...

lý tự đ ngộ , gi Ví dụ: Ch ngứ minh các đ nhị V nẫ d aự trên kỹ thu tậ state space search nh ngư khó khăn h nơ do m cứ độ và quan hệ c aủ các phép suy lu nậ : song song, đ ngồ th iờ , b cắ c uầ ,..

Có các k tế quả khá t

tố và v nẫ còn phát tri nể đ nế ngày nay

Baøi giaûng “Trí tueä nhaân taïo” - Slide 18

((BùngBùng nổnổ tổtổ h pợh pợ mnmn

, , mm>=10) >=10)

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

L chị

sử phát tri nể c aủ AI- Giai đo nạ vi nễ vông

 Giai đo nạ vi nễ vông (1965 – 1975)

– Đây là giai đo nạ phát tri nể v iớ tham v ngọ làm cho máy hi uể đ

cượ con

iườ qua ngôn ngữ tự nhiên.

– Các công trình nghiên c uứ t pậ trung vào vi cệ bi uể di nể tri th cứ và

ngươ th cứ giao ti pế gi aữ ng

iườ & máy b ngằ ngôn ngữ tự nhiên.

– K tế quả không m yấ khả quan nh ngư cũng tìm ra đ

cượ các ph

cượ dùng đ nế ngày nay tuy ch aư th tậ t

ngươ th cứ tố

bi uể di nễ tri th cứ v nẫ còn đ như:

– Semantic Network (m ngạ ngữ nghĩa) – Conceptial graph (đồ thị khái ni mệ ) – Frame (khung) – Script (k chị

b nả )

V pấV pấ ph iảph iả trởtrở ng iạng iạ vềvề năngnăng l cựl cự c aủc aủ máymáy tínhtính

Baøi giaûng “Trí tueä nhaân taïo” - Slide 19

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

L chị

sử phát tri nể c aủ AI- Giai đo nạ hi nệ đ iạ

– Xác đ nhị

iả t

tố nh tấ trong kho ngả th iờ gian ch pấ nh nậ đ

cượ .

 Giai đo nạ hi nệ đ iạ (từ 1975) l iạ m cụ tiêu mang tính th cự ti nễ h nơ c aủ AI là: iờ gi Tìm ra l Không c uầ toàn tìm ra l

iờ gi

iả t – Tinh th nầ HEURISTIC ra đ iờ và đ

iố uư cượ áp d ngụ m nhạ mẽ để kh cắ ph cụ

bùng nổ tổ h pợ .

– Kh ngẳ đ nhị

vai trò c aủ tri th cứ đ ngồ th iờ xác đ nhị

2 trở ng iạ l nớ là bi uể

di nể tri th cứ và bùng nổ tổ h pợ .

tính khó khăn trong

– Nêu cao vai trò c aủ Heuristic nh ngư cũng kh ngẳ đ nhị

đánh giá heuristic.

nothing Better thanthan nothing Better

Baøi giaûng “Trí tueä nhaân taïo” - Slide 20

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Phát tri nể ngứ d ngụ m nhạ mẽ: Hệ chuyên gia, Hệ chu nẩ đoán,..

Các lĩnh v cự ngứ d ngụ

 Game Playing: Tìm ki mế / Heuristic  Automatic reasoning & Theorem proving: Tìm ki mế / Heuristic  Expert System: là h ngướ phát tri nể m nhạ mẽ nh tấ và có giá trị ngứ

d ngụ cao nh tấ .

iả quy tế v nấ đề

 Planning & Robotic: các hệ th ngố dự báo, tự đ ngộ hóa  Machine learning: Trang bị khả năng h cọ t pậ để gi

cượ . Không tìm ra cái m iớ .

cượ tri th cứ h cọ đ

kho tri th cứ :  Supervised : Ki mể soát đ  UnSupervised:Tự h cọ , không ki mể soát. Có thể t oạ ra tri th cứ m iớ nh ngư cũng nguy hi mể vì có thể h cọ nh ngữ đi uề không mong mu nố .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 21

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Các lĩnh v cự ngứ d ngụ (tt)

 Natural Language Understanding & Semantic modelling: cượ phát tri nể m nhạ do m cứ độ ph cứ t pạ c aủ bài toán cả về

Không đ tri th cứ & khả năng suy lu nậ .

 Modeling Human perfromance: Nghiên c uứ cơ chế tổ ch cứ trí tuệ

c aủ con ng

iườ để áp d ngụ cho máy.

 Language and Environment for AI:Phát tri nể công cụ và môi

ngườ để xây d ngự các ngứ d ngụ AI.

 Neurol network / Parallel Distributed processing: gi

iả quy tế v nấ đề năng l cự tính toán và t cố độ tính toán b ngằ kỹ thu tậ song song và mô ph ngỏ m ngạ th nầ kinh c aủ con ng

iườ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 22

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Mô hình phát tri nể ngứ d ngụ AI

 Mô hình ngứ d ngụ Ai hi nệ t

Tri Th cứ Knowledge Engineering

Tìm ki mế Search Suy lu nậ Heurictic

Baøi giaûng “Trí tueä nhaân taïo” - Slide 23

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

iạ : = Presentation AIAI = Presentation & Search & Search

ngươ 2:

2: PHÉP

PHÉP TOÁN

ngươCh Ch

TOÁN VỊVỊ TỪTỪ

iướ góc nhìn c aủ AI

Phép toán vị từ d M nhệ đề Vị từ

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K h oa C oân g N g h eä Th oân g Tin

Th aù n g 6/2001

AIAI &

& PhépPhép toántoán vịvị từtừ

 T iạ sao Ai ph iả nghiên c uứ phép toán vị từ?

ngươ trình có khả năng suy lu nậ

– AI  Phát tri nể các ch – Suy lu nậ giúp ch

ngươ trình AI bi

tế đ

cượ tính đúng/sai c aủ m tộ v nấ đề

nào đó.

 Phép toán vị từ  cung c pấ m tộ khả năng tri nể khai các quá trình suy

di nễ trên máy tính

ngươ trình AI c nầ phép toán vị từ.

 Phát tri nể ch  Phép toán vị từ đ

cượ hi nệ th cự b ngằ ngôn ngữ l pậ trình trên máy tính

PROLOG

Baøi giaûng “Trí tueä nhaân taïo” - Slide 25

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

AIAI &

& PhépPhép toántoán vịvị từtừ: : MinhMinh h aọh aọ 1 1

 “N uế tr iờ m aư thì b uầ tr iờ có mây”  Tr iờ đang m aư V yậ  B uầ tr iờ có mây

 P=“Tr iờ m a”ư  Q= “B uầ tr iờ có mây” Ta có hai phát bi uể sau đúng:  P Q  P V yậ theo lu tậ suy di nễ  Q là đúng. Nghĩa là: “B uầ tr iờ có mây”

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 26

M nhệ đề th cự tế M nhệ đề logic

AIAI &

& PhépPhép toántoán vịvị từtừ: : MinhMinh h aọh aọ 2 2

M nhệ đề logic

M nhệ đề th cự tế  “N uế NAM có nhi uề ti nề thì NAM đi

 “Nam KHÔNG đi mua s m”ắ V yậ  Nam KHÔNG có nhi uề ti nề

mua s m”ắ

(cid:216) QQ

 P=“Nam có nhi uề ti n”ề  Q= “Nam đi mua s m”ắ Ta có hai phát bi uể sau đúng:  P Q  (cid:216) V yậ theo lu tậ suy di nễ  (cid:216) Nghĩa là: “Nam KHÔNG có nhi uề ti n”ề

Baøi giaûng “Trí tueä nhaân taïo” - Slide 27

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

(cid:216) PP là đúng.

nghĩa

Phép toán m nhệ đề : Đ nhị

M nhệ đề:  M nhệ đề là m tộ phát bi uể khai báo  M nhệ đề chỉ nh nậ m tộ trong hai giá trị: ĐÚNG (True) ho cặ SAI

(False)

tế cổ truy nề

Ví dụ:  Ngày 01tháng giêng là ngày t  Môn b nạ đang h cọ là AI  Hôm nay là qu cố khánh

 Hôm nay tr iờ l nhạ  T iạ sao ph iả h cọ AI ?

Baøi giaûng “Trí tueä nhaân taïo” - Slide 28

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

M nhệ đề : Các phép toán

 Bi uể th cứ m nhệ đề: là sự k tế h pợ c aủ các m nhệ đề b iở các phép

toán m nhệ đề  Các phép toán:

(cid:216)

(cid:217)

Ư u t i ê n

(cid:218)

Phủ đ nhị H iộ Tuy nể Suy ra

= T

ngươ đ

m tộ ngôi hai ngôi hai ngôi hai ngôi hai ngôi ngươ  Cách đánh giá giá trị c aủ phép toán:

(cid:222)

B ngả chân trị

Baøi giaûng “Trí tueä nhaân taïo” - Slide 29

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

M nhệ đề : Các phép toán – víví dụdụ

P=“Nam h cọ gi i”ỏ ; Q=“Nam thông minh” ; R=“Nam đ pẹ trai”

 P (cid:217) Q (cid:217) R

Bi uể th cứ m nhđệ ề M nhệM nhệ đềđề th cựth cự tếtế

 P (cid:218)

iỏ , thông minh, đ pẹ trai” iỏ ho cặ thông minh”

Q iỏ , ho cặ đ pẹ trai”

 “Nam h cọ gi  “Nam h cọ gi  “Nam ho cặ h cọ gi  “Nam thông mình thì h cọ gi 

 (P (cid:217) (cid:216) R)(cid:218) ((cid:216) P (cid:217) R)

 Q (cid:222)

i”ỏ



Baøi giaûng “Trí tueä nhaân taïo” - Slide 30

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

M nhệ đề : Các bi uể th cứ m nhệ đề đúng

 Ký hi uệ bi uể th cứ đúng: wff  Thành ph nầ cơ b nả là P hay (cid:216) P, v iớ P là m tộ m nhệ đề nghĩa theo d ngạ lu tậ sinh sau:  Các bi uể th cứ đúng đ nhị

Wff= “Thành ph nầ cơ b n”ả |

(cid:216) wff | wff^wff | wff v wff | wff (cid:222) wff | wff = wff | (wff)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 31

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

M nhệ đề : Ngữ nghĩa

 Ngữ nghĩa c aủ m tộ bi uể th cứ m nhệ đề là giá trị c aủ bi uể th cứ

m nhệ đề đó.

 Giá trị c aủ bi uể th cứ m nhệ đề là có khả năng tính toán đ

cượ . Trong

cượ gán m tộ giá trị true hay false

cượ đánh giá theo b ngả chân trị và thứ tự uư tiên c aủ toán

đó: – M iỗ m nhệ đề đ – M iỗ toán tử đ

tử.

 Giá trị c aủ bi uể th cứ m nhệ đề tính b ngằ cách:

cượ từ node lá khi bi uể th cứ m nhệ đề đ

cượ bi uể di nễ ở

– Dùng b ngả chân trị – Đánh giá ng d ngạ cây

Baøi giaûng “Trí tueä nhaân taïo” - Slide 32

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ đ

ngươ

M nhệ đề : Các t

 Các t

ngươ đ

cượ sử d ngụ th

ngườ xuyên trong quá trình bi nế đ iổ

m tộ bi uể th cứ từ d ngạ này sang d ngạ khác.

 Khả năng bi nế đ iổ t

ngươ đ

ngươ trên máy tính có thể đ

cượ làm tự

ngươ đ

ngươ :

đ ngộ  Các t Trong các t

ngươ đ

ngươ sau A,B,C là các m nhệ đề b tấ kỳ.

 D ngạ hôäi

kép

(cid:216) (cid:216) A

 D ngạ phủ đ nhị A =  D ngạ tuy nể

A FALSE A FALSE A (cid:217) TRUE = A (cid:217) FALSE = A (cid:217) A = A (cid:217) (cid:216) = A

Baøi giaûng “Trí tueä nhaân taïo” - Slide 33

TRUE A A TRUE A

A (cid:218) TRUE = A (cid:218) FALSE = A (cid:218) A = A (cid:218) (cid:216) = Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ đ

ngươ (tt)

M nhệ đề : Các t

 D ngạ suy ra

 D ngạ khác

A (cid:222) B

(cid:216) TRUE = FALSE = (A (cid:222) B) (cid:216) A (cid:218) B A (cid:217) (cid:216) B

A = A = A (cid:222) = = = A (cid:217) (cid:216) B(cid:222) FALSE

A (cid:222) A (cid:222) TRUE (cid:222) FALSE (cid:222) A (cid:222) A = TRUE (cid:216) A A TRUE TRUE

= =

 Phép (cid:217) và (cid:218) có khả năng k tế h pợ .  Phép (cid:217) và (cid:218) có khả năng hoán vị.  Phép (cid:217) có khả năng phân ph iố trên (cid:218) A (cid:218) (B(cid:217) C) =(A(cid:218) B)(cid:217) (A(cid:218) C)  Phép (cid:218) có khả năng phân ph iố trên (cid:217) A (cid:217) (B(cid:218) C) =(A(cid:217) B)(cid:218) (A(cid:217) C)

A A A(cid:217) B A(cid:218) B

(cid:216)

 D ngạ h pấ thu A (cid:217) (A (cid:218) B) A (cid:218) (A (cid:217) B) A (cid:217) ((cid:216) A (cid:218) B)= A (cid:218) ((cid:216) A (cid:217) B)=  D ngạ De Morgan (A (cid:217) B) (A (cid:218) B)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 34

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

= = (cid:216) A (cid:218) (cid:216) B (cid:216) A (cid:217) (cid:216) B

M nhệ đề : Các d ngạ chu nẩ CNF & DNF

 D ngạ chu nẩ là k tế xu tấ chu nẩ c aủ các gi

iả thu tậ làm vi cệ v iớ phép

toán m nhệ đề.

 Tuy nể cơ b nả : là thành ph nầ cơ b nả hay sự k tế h pợ c aủ các thành

ph nầ cơ b nả b ngằ phép tuy nể (v)

 H iộ cơ b nả : là thành ph nầ cơ b nả hay sự k tế h pợ c aủ các thành

ph nầ cơ b nả b ngằ phép h iộ (^).

 D ngạ chu nẩ h iộ – CNF: là thành ph nầ tuy nể cơ b nả hay các

tuy nể cơ b nả k tế h pợ b iở phép h iộ .

 D ngạ chu nẩ tuy nể – DNF: là thành ph nầ h iộ cơ b nả hay các h iộ

cơ b nả k tế h pợ b iở phép tuy nể .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 35

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

M nhệ đề : Lu tậ suy di nễ & ch ngứ minh

cượ áp d ngụ để phát tri nể các ngứ d ngụ có khả iườ

ngườ xuyên c aủ con ng

Lu tậ suy di nễ đ năng suy lu nậ . Suy lu nậ là ho tạ đ ngộ th để hi uể các lý lẽ, ki mể ch ngứ , phán đoán các v nấ đề.

 Lu tậ Modus Ponens (MP)

 Lu tậ C ngộ

\ \ A, A(cid:222) B B A

 Lu tậ Modus Tollens (MT) (cid:216) A

AvB  Lu tậ tam đo nạ lu nậ tuy nể

B, (cid:216) B \ Av B, (cid:216) A \ B

A(cid:222)  Lu tậ H iộ tế

 Lu tậ tam đo nạ lu nậ giả thi C\

 Lu tậ đ nơ gi nả

\ A,B A^B B,B(cid:222) A(cid:222) A(cid:222) C

Baøi giaûng “Trí tueä nhaân taïo” - Slide 36

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

\ A^B A

M nhệ đề : Lu tậ suy di nễ & ch ngứ minh – Ví dụ 1

 Ta có các bi uể th cứ sau: AvB, AvC,và (cid:216) A là TRUE  Ch ngứ minh B^C có trị TRUE

 Đã ch ngứ minh xong

Baøi giaûng “Trí tueä nhaân taïo” - Slide 37

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

1 2 3 4 5 6 AvB AvC (cid:216) A B C B^C P (tieân ñeà) P (tieân ñeà) P (tieân ñeà) 1,3, tam ñoaïn luaän tuyeån 2,3, tam ñoaïn luaän tuyeån 4,5, Luaät hoäi

M nhệ đề : Lu tậ suy di nễ & ch ngứ minh – Ví dụ 2

 Ta có các bi uể th cứ sau là đúng: C, B(cid:222)

D, (cid:216) D Ch ngứ minh C

AvB, A(cid:222)  TaTa giảgiả thi

tếthi tế (cid:216)(cid:216) CC d nẩd nẩ đ nếđ nế false false

1 2 3 4 5 6 7 8 9 10

P (tieân ñeà) P (tieân ñeà) P (tieân ñeà) P (tieân ñeà) P (giaû thieát phaûn chöùng) 3,4,Modus Tollens 1,6, Tam ñoaïn luaän tuyeån 2,5,Modus Tollens 7,8, Luaät hoäi Maâu thuaãn vôùi Luaät hoäi

Baøi giaûng “Trí tueä nhaân taïo” - Slide 38

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

AvB A(cid:222) C B(cid:222) D (cid:216) D (cid:216) C (cid:216) B A (cid:216) A A ^(cid:216) A False

iả m nhệ đề

M nhệ đề : Lu tậ phân gi

 Clause: là tuy nể c aủ không hay nhi uề thành ph nầ cơ b nả .  D ngạ clause:là h iộ c aủ m tộ hay nhi uề Clause  Lu tậ phân gi

iả m nhệ đề:

PVD1, (cid:216) PvD2 \

(D1-P)v(D2-(cid:216) P)

cượ b ngằ cách xóa bỏ các P trong D1

– D1,D2 là tuy nể c aủ không hay m tộ thành ph nầ cơ b nả . – P là m nhệ đề – D1-P : là m tộ clause thu đ – D2- (cid:216) P : là m tộ clause thu đ

cượ b ngằ cách xóa bỏ các (cid:216) P trong D2

Baøi giaûng “Trí tueä nhaân taïo” - Slide 39

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

iả m nhệ đề (tt)

M nhệ đề : Lu tậ phân gi

iả b oả toàn tính Unsatisfiable

Rn(S)cũng unsatisfiable iả , n số l nầ áp d ngụ R trên S, n>0



iả : dùng để ch ngứ minh: Có S là

 Lu tậ phân gi  S là unsatisfiable (cid:219) R: lu tậ phân gi ngỨ d ngụ c aủ lu tậ phân gi t pậ các clause, dùng S ch ngứ minh bi uể th cứ m nhệ đề W

 Ph

c aủ W

cướ ii vào S thành l pậ S1

ngươ pháp: Thành l pậ phủ đ nhị i. ii. Đ aư (cid:216) W về d ngạ clause iii. Thêm clause trong b iv. Dùng lu tậ phân gi

iả trên S1 để d nẫ ra clause r ngỗ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 40

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

iả m nhệ đề - Ví dụ

M nhệ đề : Lu tậ phân gi



Cho đo nạ sau:

“ Nam đ pẹ trai, giàu có. Do v yậ , Nam ho cặ là phung phí ho cặ là nhân từ và giúp ng iườ . Th cự tế, Nam không phung phí ho cặ cũng không kêu căng.” “Do v yậ , có thể nói Nam là ng

iườ nhân t ”ừ



Ki mể ch ngứ k tế quả suy lu nậ trên, b ngằ lu tậ phân gi

iả .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 41

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

iả m nhệ đề - Ví dụ

M nhệ đề : Lu tậ phân gi

 (i) Chuy nể sang m nhệ đề: – P1 = “Nam đ pẹ trai.” – P2 = “Nam giàu có.” – P3 = “Nam phung phí.” – P4 = “Nam kêu căng.” – P5 = “Nam nhân từ.” – P6 = “Nam giúp ng

iườ .”

Các bi uể th cứ thành l pậ đ

cượ từ đo nạ trên:

– Wff1 = P1 ^ P2 – Wff2 = (P1 ^ P2) => (P3 ^ (cid:216) (P5 ^ P6)) v ((cid:216) P3 ^ (P5 ^ P6)) – Wff3 = (cid:216) P3 ^ (cid:216) P4

WffWff4 = 4 = PP55 Bi uểBi uể th cứth cứ c nầc nầ ch ngứch ngứ minhminh..

Baøi giaûng “Trí tueä nhaân taïo” - Slide 42

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

iả m nhệ đề - Ví dụ

M nhệ đề : Lu tậ phân gi

 (ii) Đ aư về d ngạ clause:  

C2 = P2

………………………………………

Wff1, sinh ra hai clause: C1 = P1 Wff2 = (cid:216) (P1 ^ P2) v ((P3 ^ (cid:216) (P5 ^ P6)) v ((cid:216) P3 ^ (P5 ^ P6)) )

= ((cid:216) P1 v (cid:216) P2 v P3 v (cid:216) P3 v (cid:216) P6) ^ ((cid:216) P1 v (cid:216) P2 v P5 v (cid:216) P3 v (cid:216) P6)^((cid:216) P1 v (cid:216) P2 v P3 v P3 v P5) ^ ((cid:216) P1 v (cid:216) P2 v P5 v P3 v P5) ^ ((cid:216) P1 v (cid:216) P2 v P3 v P5 v (cid:216) P6)^ ((cid:216) P1 v (cid:216) P2 v P5 v P5 v (cid:216) P6) ^((cid:216) P1 v (cid:216) P2 v P3 v P3 v P6) ^ ((cid:216) P1 v (cid:216) P2 v P5 v P3 v P6)

Sinh ra các clause: C3 = ((cid:216) P1 v (cid:216) P2 v (cid:216) P6) C5 = ((cid:216) P1 v (cid:216) P2 v P3 v P5) C7 = ((cid:216) P1 v (cid:216) P2 v P3 v P5 v (cid:216) P6) C9 = ((cid:216) P1 v (cid:216) P2 v P3 v P6) C4 = ((cid:216) P1 v (cid:216) P2 v P5 v (cid:216) P3 v (cid:216) P6) C6 = ((cid:216) P1 v (cid:216) P2 v P3 v P5) C8 = ((cid:216) P1 v (cid:216) P2 v P5 v (cid:216) P6) C10 =((cid:216) P1 v (cid:216) P2 v P5 v P3 v P6)

 Wff3 sinh ra các clause: cướ l yấ phủ đ nhị (g mồ cả b

C11 = (cid:216) P3 C12 = (cid:216) P4 C13 = (cid:216) P5

Baøi giaûng “Trí tueä nhaân taïo” - Slide 43

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

k tế lu nậ )

iả m nhệ đề - Ví dụ

M nhệ đề : Lu tậ phân gi

iả trên các clause:

Lu tậ áp d ngụ

Clauses

Lu tậ áp d ngụ P P

TT 12.(cid:216) P4 13 (cid:216) P5

1,2, R 2, 14, R 10,15,R 1,16,R 2,17, R 13, 18, R

14 (cid:216) P2 v (cid:216) P6 15 (cid:216) P6 16 (cid:216) P1 v (cid:216) P2 v P5 v P3 17 (cid:216) P2 v P5 v P3 18 P5 v P3 19 P3 20 (cid:144)

11, 19, R

(cid:144)

iii) áp d ngụ lu tậ phân gi TT Clauses P 1 P1 P 2 P2 3 (cid:216) P1 v (cid:216) P2 v (cid:216) P6 P 4 (cid:216) P1 v (cid:216) P2 v P5 v (cid:216) P3 v (cid:216) P6 P 5 (cid:216) P1 v (cid:216) P2 v P3 v P5 P 6 (cid:216) P1 v (cid:216) P2 v P3 v P5 P 7 (cid:216) P1 v (cid:216) P2 v P3 v P5 v (cid:216) P6 P 8 (cid:216) P1 v (cid:216) P2 v P5 v (cid:216) P6 P 9 (cid:216) P1 v (cid:216) P2 v P3 v P6 P 10 (cid:216) P1 v (cid:216) P2 v P5 v P3 v P6 P 11.(cid:216) P3 P

ĐÃ CH NGỨ MINH

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 44

Logic Vị từ: T iạ sao?

 Phép toán m nhệ đề  suy di nễ tự đ ngộ nh ngư ch aư đủ khi c nầ ph iả

truy c pậ vào thành ph nầ nhỏ trong câu, dùng bi nế số trong câu.

Ví dụ: “M iọ sinh viên tr

ngườ ĐHBK đ uề có b ngằ tú tài. Lan không có b ngằ tú tài.

“Lan” là m tộ đ iố t

ngượ cụ thể c aủ “SV tr

ngườ ĐHBK” – không thể đ cặ tả

cượ “quan h ”ệ này trong m nhệ đề đ

Do v yậ , Lan không là sinh viên tr ngườ ĐHBK”

cượ mà chỉ có thể là: ngườ ĐHBK thì Lan có b ngằ tú tài. Lan không có b ngằ tú tài.

“LAN là sinh viên tr

Do v yậ , Lan không là sinh viên tr

iả quy tế b ngằ cách li

tấ cả các tr

ngườ h pợ

 M nhệ đề ph iả gi  Không khả thi  Do đó, chúng ta c nầ m tộ Logic khác h nơ là phép toán m nhệ đề:

ngườ ĐHBK” tệ kê t

PHÉP TOÁN PHÉP

TOÁN VỊVỊ TỪTỪ

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 45

nghĩa

Vị từ: Đ nhị

 Vị từ là m tộ phát bi uể nói lên quan hệ gi aữ m tộ đ iố t

ngượ v iớ các thu cộ tính

Vị từ đ

cượ bi uể di nễ b iở m tộ tên đ

cượ g iọ là tên vị từ, theo sau nó là

m tộ danh sách các thông số.

c aủ nó hay quan hệ gi aữ các đ iố t ngượ v iớ nhau.

Ví dụ:

ngườ ĐHBK”

ngượ tên là “Nam” có thu cộ tính là “sinh viên tr ngườ ĐHBK”.

+ Phát bi uể : “Nam là sinh viên tr + Bi uể di nễ : sv_bk(“Nam”) Ý nghĩa: đ iố t

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 46

Vị từ: Bi uể di nễ vị từ – Cú pháp

 Chúng ta có bao nhiêu cách bi uể di nễ đúng cú pháp cho phát bi uể nói trên?  Không bi Ví dụ chúng ta có thể thay đ iổ các tên vị từ thành các tên khác nhau như :

tế bao nhiêu nh ngư ch cắ ch nắ nhi uề h nơ 1 

sinhvien_bk, sinhvien_bachkhoa, … T tấ cả chúng đ uề đúng cú pháp.

– Không mô tả nh ngữ vị từ th aừ , có thể suy ra từ m tộ t pậ các vị từ tế kế

ngươ tự dư (th aừ ) dữ li uệ khi thi

khác. Hình th cứ th aừ cũng t CSDL.

– Tên vị từ ph iả có tính g iợ nhớ. Cụ thể, trong ví dụ trên chúng ta có thể bi uể di nễ b iở q(“Nam”), nh ngư rõ ràng cách này không m yấ thân thi nệ và dễ nhớ.

M tộ số quy cướ / chú ý khi bi uể di nễ :

B nạ có bi

tế q(“Nam”) có nghĩa gì ???

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 47

1

2

Vị từ: Bi uể di nễ vị từ – Cú pháp (tt)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 48

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

, term

, …, termn)

D ngạ vị từ:

tên_vị_từ(term

 Tên vị từ:

B tắ đ uầ b iở m tộ ký tự chữ th

ngườ .

Ví dụ: ban_than, banThan,bAN_THAN,…

 Term có thể là: H ngằ ,Bi nế , Bi uể th cứ hàm.

 H ngằ : có thể h ngằ chu iỗ hay h ngằ số.

[a..z](a..z| A..Z| 0..9|_)*

H ngằ chu iỗ : [“](a..z| A..Z| 0..9|_)*[“] hay [a..z](a..z| A..Z| 0..9|_)*

“Nam”, “nam”, “chuoi”, nam, chuoi, qua,… Ví dụ:

 Bi nế : [A..Z](a..z| A..Z| 0..9|_)*

Ví dụ: Nguoi, NGUOI,..

 Bi uể th cứ hàm có d ngạ : tên_hàm(term1, term2, …, termk)

Trong đó Tên hàm = [a..z ](a..z| A..Z| 0..9|_)*

H ngằ số: (0..9)* Ví dụ: 10, 32,..

Vị từ : Bi uể th cứ vị từ

 Bi uể th cứ Vị từ: là sự k tế h pợ c aủ các vị từ b iở các phép toán vị từ.  Các phép toán:

Phủ đ nhị

- m tộ ngôi.

V iớ m iọ

- m tộ ngôi

iạ

Ư u t i ê n

" X $ X ^ v => =

(cid:216)

T nồ t H iộ Tuy nể Suy ra T

- m tộ ngôi - hai ngôi. - hai ngôi. - hai ngôi. - hai ngôi.

ngươ đ

ngươ

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 49

Vị từ: Các bi uể th cứ vị từ đúng

cượ ký hi uệ wff.

 Bi uể th cứ vị từ đúng đ  Bi uể th cứ cơ b nả : Có thể là m tộ vị từ , m tộ đ iạ di nệ trị TRUE (trị là T

đúng), m tộ đ iạ di nệ trị FALSE (trị là F sai).

cượ đ nhị nghĩa như sau:

 M tộ bi uể th cứ đúng cú pháp đ Wff = “Bi uể th cứ cơ b n”ả |(cid:216) wff |wff ^ wff |wff v wff |wff=>wff |wff

= wff |(wff) |" X wff |$ X wff

V iớ

– X : Là m tộ bi nế .

(cid:19)

" : L $ : L

(cid:19)

ngượ từ v iớ m iọ . iạ . ngượ từ t nồ t

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 50

ngượ từ

Vị từ: L

Lan là h cọ sinh trung bình.

Mai h cọ sinh khá

tế : “X là h cọ sinh khá” ta có các vị từ

p(“Mai”) : trị là T.

p(“Lan”) : trị là F.

ngượ từ t nồ t

iạ :

 Giả sử chúng ta có: Nam là h cọ sinh khá.  Xét t pậ D = [Nam, Lan, Mai]  G iọ p(X) cho bi p(“Nam”) : trị là T.  L Xét m nhệ đề p(“Nam”) v p(“Lan”) v p(“Mai”) có thể bi uể di nễ b ngằ vị

từ

$ X ˛ “T nồ t

D: p(X) iạ X thu cộ t pậ D, mà X là h cọ sinh khá”

ngượ từ v iớ m iọ :

 L Xét m nhệ đề p(“Nam”) ^ p(“Lan”) ^ p(“Mai”) có thể bi uể di nễ b ngằ

vị từ " X ˛

D: p(X)

“M iọ X thu cộ t pậ D đ uề là h cọ sinh khá”

Baøi giaûng “Trí tueä nhaân taïo” - Slide 51

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

iớ th cự

Vị từ: Bi uể di nễ thế gi

 Chuy nể các câu sau sang bi uể th cứ vị từ:

ngườ ĐHBK đ uề có b ngằ tú tài.

“M iọ sinh viên tr Lan không có b ngằ tú tài. Do v yậ , Lan không là sinh viên tr

ngườ ĐHBK”

tế : “X là sinh viên tr

ngườ DHBK”

 V iớ sv_bk(X) cho bi

tu_tai(X) cho bi

tế : “X có b ngằ tú tài”

 Các câu trên đ

cượ chuy nể qua vị từ là:

" X(sv_bk(X) => tu_tai(X)).

tu_tai(“Lan”).

Do v yậ , (cid:216) sv_bk(“Lan”).

Baøi giaûng “Trí tueä nhaân taïo” - Slide 52

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

(cid:216)

iớ th cự (tt)

Vị từ: Bi uể di nễ thế gi

 “Chỉ vài sinh viên máy tính l pậ trình t

tố .”

v iớ

sv_mt(X) laptrinh_tot(X)

: “X là sinh viên máy tính” : “X l pậ trình t

t”ố

Câu trên chuy nể sang vị từ là: $ X(sv_mt(X) ^ laptrinh_tot(X))

 “Không m tộ sinh viên máy tính nào không c nầ cù.”

v iớ :

sv_mt(X) can_cu(X)

: “X là sinh viên máy tính : “X c nầ cù”

Câu trên chuy nể sang là: " X (sv_mt(X) => can_cu(X))

 “Không ph iả t

tấ cả các sinh viên máy tính đ uề thông minh”

thong_minh(X) : “X thông minh”

v iớ Câu trên chuy nể sang là:

$ X(sv_mt(X) ^ (cid:216)

thong_minh(X))

Baøi giaûng “Trí tueä nhaân taïo” - Slide 53

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Vị từ: Ngữ nghĩa

 V nấ đề: N uế chúng ta có bi uể th cứ sau: " X$ Y p(X,Y) Chúng ta hi uể như thế nào ????! -> C nầ sự di nễ d chị .

: là con ng

iườ . tế : “X là cha c aủ Y”

iạ ng

iườ Y để X là cha c aủ Y”

+ Cách hi uể 1: X, Y p(X,Y) cho bi Do v yậ : " X$ Y p(X,Y) có thể hi uể là: “M iọ ng iườ X, t nồ t -> wff = " X$ Y p(X,Y) có trị là F (sai)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 54

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Vị từ: Ngữ nghĩa (tt)

: là con ng

iườ . tế : “Y là cha c aủ X”

iạ ng

iườ Y là cha c aủ X”

+ Cách hi uể 2: X, Y p(X,Y) cho bi Do v yậ : " X$ Y p(X,Y) có thể hi uể là: “M iọ ng iườ X, t nồ t -> wff = " X$ Y p(X,Y) có trị là T (đúng)

: là số nguyên.

+ Cách hi uể 3: X, Y p(X,Y) cho bi

tế : “Y b ngằ bình ph

ngươ c aủ X” -> wff = " X$ Y p(X,Y) có trị là T (đúng)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 55

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Vị từ: Ngữ nghĩa (tt)

 Di nễ d chị

: g mồ

: Quan hệ trên D : Hàm (ánh xạ) trên D : M tộ trị trên D, cùng m tộ trị cho các xu tấ hi nệ : M tộ trị trên D, cùng m tộ trị cho các xu tấ hi nệ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 56

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

- T pậ D, không r ngỗ , mi nề di nễ d chị . - Các phép gán:  Vị từ  Hàm  Bi nế tự do  H ngằ

Vị từ: Ngữ nghĩa (tt)

I trên mi nề D c aủ wff.

 Ngữ nghĩa: Có di nễ d chị  Wff không có l

ngượ từ:

Ngữ nghĩa = trị sự th tậ (T|F) c aủ wff khi áp d ngụ di nễ d chị  wff có l

ngượ từ:

$ XW là T,

iạ :

cượ l

" XW là T,

n uế : W(X/d) là T cho m tộ d thu cộ D $ XW là F ng n uế : W(X/d) là T cho m iọ d thu cộ D " XW là F ng

cượ l

iạ :

Baøi giaûng “Trí tueä nhaân taïo” - Slide 57

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Vị từ: Khái ni mệ

Có I : di nễ d chị

, E là wff

 Model:

I là cho E có trị T iạ : Ng

cượ l

---> I là Model c aủ E ---> I là CounterModel c aủ E

 Valid:

E là valid n uế m iọ di nễ d chị

I đ uề là Model.

cượ l

iạ là : Invalid

Ng  Unsatisfiable:

E là unsatisfiable : m iọ I đêu là CounterModel

cượ l

iạ

:Satisfiable

Baøi giaûng “Trí tueä nhaân taïo” - Slide 58

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ đ

ngươ

Vị từ: T

 Từ t

ngươ đ

ngươ c aủ m nhệ đề:

cượ thay cùng m tộ bi uể th cứ vị từ, thì đ

ngươ c aủ vị từ.

ngươ đ

N uế chúng ta thay thế các m nhệ đề b iở các bi uể th cứ vị từ, các m nhệ đề cùng tên thì đ cượ m tộ t Ví dụ: M nhệ đề:

(P => Q) = ((cid:216) P v Q)

Vị từ:

ngươ :

P b iở : " X$ Yp(X,Y), Q b iờ : q(X) ngươ đ t (" X$ Yp(X,Y) => q(X)) = ((cid:216) (" X$ Yp(X,Y)) v q(X))

Baøi giaûng “Trí tueä nhaân taïo” - Slide 59

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ đ

ngươ

Vị từ: T

 L

ngượ từ:

(cid:216) (" X W) = $ X((cid:216) W) (cid:216) ($ X W) = " X((cid:216) W) V iớ W là m tộ wff

 T

ngươ đ

ngươ có ràng bu cộ :

Sau đây: Y: bi nế , W(X): wff có ch aứ bi nế X, C là wff

không ch aứ X

Y không xu tấ hi nệ trong W(X)

Ràng bu cộ : ngươ đ T

ngươ :

 " X W(X) = " Y W(Y)  $ X W(X) = $ Y W(Y)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 60

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ đ

ngươ

Vị từ: T

T ngươ đ

 C v " XA(X) = " X(C v A(X))  C v $ XA(X) = $ X(C v A(X))

ngươ : D ngạ tuy nể :

 C ^ " XA(X) = " X(C ^ A(X))  C ^ $ XA(X) = $ X(C ^ A(X))

D ngạ h iộ :

 C => " XA(X) = " X(C => A(X))  C => $ XA(X) = $ X(C => A(X))  " XA(X) => C = " X(A(X) => C)  $ XA(X) => C = $ X(A(X) => C)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 61

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

D ngạ suy ra:

Vị từ: D ngạ chu nẩ Prenex

 D ngạ Chu nẩ Prenex: Q1X1Q2X2…QnXnM

, $

: " . : wff không có l

ngượ từ.

Qi M Ví dụ:

- sv_bk(x) - " X(sv_bk(X) ^ hoc_te(X)) - " X$ Ycha(X,Y)

 Gi

iả thu tậ đ aư wff về chu nẩ Prenex:  Đ iổ tên bi nế --> wff không còn l

ngượ từ cùng tên bi nế ,

bi nế l  Đ aư l

ngượ từ không trùng tên bi nế tự do. ngươ . ngượ từ sang trái dùng t

ngươ đ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 62

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Vị từ: D ngạ chu nẩ Prenex

 D ngạ chu nẩ Tuy nể Prenex:

 D ngạ chu nẩ H iộ Prenex:

Q1X1Q2X2…QnXn(C1 v … v Ck) : Thành ph nầ h iộ cơ b nả . Ci

 Gi

kép.

ngươ đ

ngươ .

: Thành ph nầ tuy nể cơ b nả .

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 63

Q1X1Q2X2…QnXn(D1 v … v Dk) Di iả thu tậ :  Đ iổ tên bi nế .  Lo iạ bỏ => b iở : A => B = (cid:216) A v B  Chuy nể (cid:216) sang ph iả dùng De Morgan và phủ đ nhị ngượ từ sang trái dùng t  Chuy nể l  Phân ph iố v trên ^ (CNF), hay ^ trên v (DNF)

KHÔNG GIANGIAN

3: TÌMTÌM KI MẾKI MẾ TRÊNTRÊN KHÔNG

ngươ 3:

ngươCh Ch

THÁI TR NGẠTR NGẠ THÁI Search)) Space Search State Space ((State

AI : Bi uể di nễ và tìm ki mế Không gian tìm ki mế Graph Search Các gi iả thu tậ tìm ki mế trên không gian tr ngạ thái Depth first search (DFS) - Breath first search (BFS)

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K h oa C oân g N g h eä Th oân g Tin

Th aù n g 6/2001

T iạ sao ph iả tìm ki mế ?

 Tìm ki mế cái gì?  Bi uể di nễ và tìm ki mế là kỹ thu tậ phổ bi nế gi

iả các bài toán trong lĩnh

v cự AI

 Các v nấ đề khó khăn trong tìm ki mế v iớ các bài toán AI

ngượ tìm ki mế thay đ iổ

– Đ cặ tả v nấ đề ph cứ t pạ – Không gian tìm ki mế l nớ – Đ cặ tính đ iố tr – Đáp ngứ th iờ gian th cự – Meta knowledge và k tế quả “t

iố u”ư

 Khó khăn về kỹ thu tậ

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 65

Lý thuy tế đồ thị - Review

 Đồ thị: là m tộ c uấ trúc bao g mồ :

– T pậ các nút N1, N2,… Nn,.. Không h nạ chế – T pậ các cung n iố các c pặ nút, có thể có nhi uề cung trên m tộ c pặ nút

B

A

B

C

D

E

D

C

E

Nút: {A,B,C,D,E}

Cung: {(a,d), (a,b), (a,c), (b,c), (c,d), (c,e), (d,e) }

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 66

Đ cặ tính đồ thị

 Đồ thị có h

ngướ : là đồ thị v iớ các cung có đ nhị

ngướ , nghĩa là c pặ cướ sau theo t ngừ cung. Cung (Ni,Nj) có

nút có quan hệ thứ tự tr ngướ từ Ni đ nế Nj, Khi đó Ni là nút cha và Nj là nút con. h

 Nút lá: là nút không có nút con.  Path: là chu iổ có thứ tự các nút mà 2 nút kế ti pế nhau t nồ t

iạ m tộ

cung.

 Đồ thị có g cố : Trên đồ thị t nồ t

iạ nút X sao cho t

tấ cả các path đ uề đi

qua nút đó. X là g cố - Root

 Vòng : là m tộ path đi qua nút nhi uề h nơ m tộ l nầ  Cây: là graph mà không có path vòng  Hai nút n iố nhau :n uế có m tộ path đi qua 2 nút đó

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 67

Không gian tr ngạ thái

 Đ nhị

nghĩa:Không gian tr ngạ

thái là m tộ hệ th ngố

g mồ 4 thành ph nầ

[N,A,S,GD]. Trong đó: – N là t pậ nút c aủ Graph. M iỗ nút là m tộ tr ngạ thái c aủ quá trình gi

iả quy tế

v nấ đề

– A: T pậ các cung n iố gi aữ các nút N. M iỗ cung là m tộ b

cướ trong gi

iả

quy tế v nấ đề. Cung có thể có h

ngướ

– S: T pậ các tr ngạ thái b tắ đ uầ . S khác r ngỗ . – GD: T pậ các tr ngạ thái đích. GD Không r ngỗ .

 Solution path: Là m tộ path đi từ m tộ nút b tắ đ uầ Si đ nế m tộ nút k tế thúc

GDj .

iả thu tậ tìm ki mế là tìm ra m tộ solution path và/hay

solution path t

 M cụ tiêu c aủ các gi tố nh tấ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 68

Bi uể di nễ không gian tr ngạ thái-Ví dụ

Tr ngạ thái

thái là m tộ tình

 Trò ch iơ Tic Tac Toa Tr ngạ hu ngố c aủ bàn cờ

thái bùng nỗ

 Số tr ngạ nhanh.

Bi uể di nễ tr ngạ thái

X X

Bi uể di nễ không gian

iườ có 3 d uấ liên t cụ

Tr ngạ thái k tế thúc: có m tộ ng ngườ chéo, th ngẳ , ngang. theo đ

Số tr ngạ thái k tế thúc=???

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 69

State Space & Database search

 Không gian tìm ki mế th

ngườ là m tộ

 Không gian tìm ki mế là m tộ list

graph

hay tree

 M cụ tiêu tìm ki mế là m tộ path  Ph iả l uư trữ toàn bộ không gian trong

 Tìm ki mế m tộ record/nút  Ph nầ tử đã duy tệ qua là không

còn dùng t

quá trình tìm ki mế

iớ

 Không gian tìm ki mế bi nế đ ngộ liên

 Không gian tìm ki mế là cố đ nhị

t cụ trong quá trình tìm ki mế

trong quá trình tìm ki mế

 Đ cặ tính c aủ tr ngạ thái/nút là ph cứ

 Thu cộ tính c aủ m tộ record/nút là

t pạ & bi nế đ ngộ

cố đ nhị

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 70

State Space Database

Chi nế l

cượ đi uề khi nể trong SSS

 M cụ tiêu c aủ bài toán tìm ki nế trên không gian tr ngạ thái:

PATH vs STATE

 Xu tấ phát từ đâu và k tế thúc như thế nào?  Chi nế l

cượ Data-Driven-Search: Quá trình search sẽ đi từ tr ngạ thái hi nệ th iờ áp d ngụ các lu tậ để đi đ nế tr ngạ thái kế ti pế và cứ thế cho đ nế khi đ tạ đ

cượ m tộ goal.

cượ Goal-Driven-Search: Quá trình search sẽ đi từ tr ngạ iạ (goal t mạ th iờ ) tìm xem lu tậ nào có thể sinh ra tr ngạ thái cượ các lu tậ đó trở thành subgoal. Quá

 Chi nế l thái hi nệ t này. Các đi uề ki nệ để áp d ngụ đ trình l pặ l

iạ cho đ nế khi lui về đ nế các sự ki nệ ban đ uầ . Data-Driven Search hay Goal-Driven Search??

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 71

Data-Driven vs Goal-Driven

 Cả hai chi nế l

cượ cùng làm vi cệ trên không gian tr ngạ thái nh ngư thứ tự và số các sự ki nệ duy tệ qua khác nhau. Do cơ chế sinh ra các state khác nhau.  Quy tế đ nhị

cượ tùy thu cộ vào:

ch nọ l aự chi nế l – Độ ph cứ t pạ c aủ các lu tậ – Độ phân chia c aủ không gian tr ngạ thái – Sự hi nệ h uữ c aủ dữ li uệ

Goal đã có hay ch aư , nhi uề hay ít Goal đ

cượ đ cặ tả như thế nào: state cụ thể hay mô tả mang tính

đ cặ tính

 Cơ sở thông tin để ch nọ l aự chi nế l

cượ h pợ lý là m tộ META

KNOWLEDGE

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 72

Data-Driven vs Goal-Driven – Ví dụ

 Ba và Nam là bà con. Ba h nơ nam 250 tu iổ . Tìm m iố quan hệ gi aữ Ba

và Nam.

 Trong bài toán này:

– Không gian tr ngạ thái là cây phả hệ – M cụ tiêu tìm ki mế là path n iố Ba v iớ Nam

 Giả sử m iỗ thế hệ cách nhau 25 năm, như v yậ Ba cách nam 10 thế hệ  Data-Driven-Search: Tìm từ Ba đ nế Nam.

n uế trung bình m iỗ thế hệ có X con thì số tr ngạ thái c nầ xét là X10

 Goal-Driven search: Tìm từ Nam đ nế Ba

m iỗ ng

iườ chỉ có 1 cha và 1 mẹ. Số tr ngạ thai c nầ xét là 210.

Như v yậ Goal-Driven sẽ t

tố h nơ Data driven n uế số con > 2

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 73

Graph Search

 Gi

iả thu tậ graph search ph iả có khả năng tìm ki mế ra t

tấ cả các path có cượ nghi mệ : PATH từ tr ngạ thái kh iở đ uầ đ nế

thể có để tìm đ goal.

 Graph search th cự hi nệ b ngằ cách “l n”ầ theo các nhánh c aủ graph. Từ m tộ tr ngạ thái, sinh ra các tr ngạ thái con, ch nọ m tộ tr ngạ thái con, xem iạ cho đ nế khi tìm th yấ m tộ tr ngạ đó là tr ngạ thái xét kế ti pế . L pặ l thái đích.

 “L n”ầ theo các tr ngạ thái  Đi vào ngõ c tụ ?  Khi g pặ nhánh không đi ti pế đ

cượ , gi

iạ tr ngạ thái tr

iả thu tậ ph iả có khả năng quay cướ đó để đi sang nhánh khác: BACK TRACKING.

lui l Do đó gi

iả thu tậ còn có tên là BACKTRACK search.

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 74

Gi

iả thu tậ chi ti

tế

Cs:= first element of NSL; end; add CS to SL; End; Else begin add children of CS (Except node in

Procedure backtrack; Begin S:=[start]; NLS:=[start]; De:=[ ]; CS:=start; While (NSL<>[ ]) do Begin if CS = Goal then return(SL); if CS has no children (Except node in

DE, Sl and NSL) then

begin

while ((SL<>[ ]) and CS=First element of SL)) do

DE,SL and NSL) to NSL CS:= first element of NSL; add CS to SL; end; end; End; {end while} Return FAIL; End;

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 75

begin add CS to DE remove first element from SL; remove first element from NSL;

Gi

iả thu tậ chi ti

tế (tt)

 Trong đó:

– SL (State list) : ch aứ danh sách các tr ngạ thái trên path hi nệ đang xét. N uế

tìm ra goal thì SL chính là nghi mệ .

– NSL (New State List): ch aứ danh sách các tr ngạ thái đang đ iợ xét. – DE (Dead End): ch aứ các tr ngạ thái mà con cháu c aủ chúng không ch aứ

đích.

– CS (Current State): ch aứ tr ngạ thái đang xét.

 H ngướ phát tri nể c aủ quá trình search tùy theo cơ c uấ tổ ch cứ c aủ

NSL: FIFO, FILO hay Evaluated.

 Gi

iả thu tậ có thể bị loop vô t nậ . Lý do????

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 76

Gi

iả thu tậ chi ti

tế (tt) – Ví dụ

 Xét graph sau:

S=[A] baét ñaàu

A

B

C

D

GD=[G] laø goal. Keát thuùc

Cung graph

E

F

G

Ñöôøng ñi

H

I

J

Quy trình tìm kieám?

F: ñi qua maáy laàn ??

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 77

Gi

iả thu tậ chi ti

tế (tt) – Ví dụ

 V iớ G là goal ta có k tế quả tìm ki mế theo b ngả sau:

Laàn laëp

NSL

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 78

0 1 2 3 4 5 6 7 8 A B E H I F J C G [A] [B A] [E B A] [H E B A] [I E B A] [F B A] [J F B A] [C A] [G C A] [A] [B C D A] [E F B C D A] [H I E F B C D A] [I E F B C D A] [F B C D A] [J F B C D A] [C D A] [G C D A] [] [] [] [] [H] [E I H] [E I H] [B F J E I H] [B F J E I H]

Breath First Search

các nút

Là graph search v iớ các nút “anh em” c aủ nút cượ xem xét hi nệ th iờ đ tr “con cướ cháu”

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 79

Procedure Breath_frist_search; Begin open :=[start]; close:=[]; While (open <>[]) do begin remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to close; eleminate children of X which is in Open or Close; Put remain children on RIGHT end of open; End; End; Return (FALL); End;

Breath First Search – Ví dụ

 V iớ đồ thị đã có trong ví dụ graph search.V iớ Breath first search ta có

quá trình như sau:

Laàn laëp

Open

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 80

0 1 2 3 4 5 6 7 [A] [B C D ] [C D E F] [D E F G] [E F G] [F G H I] [G H I J] [H I J] A B C D E F G [] [A] [A B] [A B C ] [A B C D] [A B C D E] [A B C D E F] [A B C D E F]

Depth First Search

Là graph search v iớ các nút “con cháu” c aủ nút hi nệ th iờ đ cượ xem xét cướ các nút “anh em”. tr

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 81

Procedure depth_frist_search; Begin open :=[start]; close:=[]; While (open <>[]) do begin remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to close; eleminate children of X which is in Open or Close; Put remain children on LEFT end of open; End; End; Return (FALL); End;

Depth First Search – Ví dụ

 V iớ đồ thị đã có trong ví dụ graph search.V iớ Depth First Search ta có quá trình

Laàn laëp

Open

như sau:

[A] [B C D ] [E F C D] [H I F C D] [I F C D] [F C D] [J C D] [C D] [G D] [] [A] [A B] [A B E ] [A B E H] [A B E H I] [A B E H I F] [A B E H I F J] [A B E H I F J C]

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 82

0 1 2 3 4 5 6 7 8 9 A B E H I F J C G

Breath First vs Depth First

cượ tổ ch cứ d ngạ FIFO cượ tổ ch cứ d ngạ LIFO

 Breath First: open đ  Depth First: open đ  Hi uệ quả

– Breath First luôn tìm ra nghi mệ có số cung nhỏ nh tấ – Depth First “th

ng”

cho k tế quả nhanh h nơ .

ườ

 K tế quả

– Breath First search ch cắ ch nắ tìm ra k tế quả n uế có. – Depth First có thể bị l pặ vô t nậ . T iạ sao??????  Bùng nổ tổ h pợ là khó khăn l nớ nh tấ cho các gi

iả thu tậ này.

Gi

iả Pháp cho bùng nổ tổ h pợ ??

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 83

Depth first search có gi

iớ h nạ

 Depth first search có khả năng l pặ vô t nậ do các tr ngạ thái con sinh ra

liên t cụ . Độ sâu tăng vô t nậ .

 Kh cắ ph cụ b ngằ cách gi

iớ h nạ độ sâu c aủ gi

iả thu tậ .

 Sâu bao nhiêu thì v aừ ? iớ h nạ : cượ gi  Chi nế l

– Cố đ nhị

m tộ độ sâu MAX, như các danh thủ ch iơ cờ tính tr

cướ

cượ số n

cướ nh tấ đ nhị – Theo c uấ hình resource c aủ máy tính – Meta knowledge trong vi cệ đ nhị

iớ h nạ độ sâu.

 Gi

gi iớ h nạ độ sâu => co h pẹ không gian tr ngạ thái => có thể m tấ

nghi mệ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 84

AND/OR Graph

 AND/OR graph là m tộ đồ thị v iớ các nút có thể là OR hay AND c aủ các nút con.

OR node

AND node

 Hypergraph: M tộ cung xác đ nhị

– Ph nầ tử đ uầ là m tộ node thu cộ N. – Ph nầ tử sau là m tộ t pậ con c aủ N. – N uế ph nầ tử sau có k node thì ta nói Hypergraph có K-Connector

 AND/OR Graph đòi h iỏ l uư trữ nhi uề dữ li uệ h nơ – Các node OR ki mể tra như Backtrack Search – Các node AND ph iả ki mể tra đ ngồ th iờ – Ph iả l uư trữ t

b iở m tộ c pặ 2 ph nầ tử:

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 85

tấ cả các v tế đã đi qua để ki mể tra AND/OR

ngươ 4:

4: HEURISTIC

HEURISTIC SEARCH SEARCH

ngươCh Ch

iả thu tậ Best first search (BFS), Gi

iả

Heuristic là gì? Tìm ki mế theo heuristic Các gi thu tậ A* Chi nế l

cượ Minimax, Alpha Beta

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K hoa C oâng N gheä Thoâng Tin

Thaùng 6/2001

Heuristic

 Heuristic là gì?

– Heuristic là nh ngữ tri th cứ đ

cượ rút t aỉ

từ nh ngữ kinh nghi mệ , “tr cự

giác” c aủ con ng

iườ .

– Heuristic có thể là nh ngữ tri th cứ “đúng” hay “sai”. – Heuristic là nh ngữ meta knowledge và “th

ngườ đúng”.

 Heuristic dùng để làm gì?

Trong nh ngữ bài toán tìm ki mế trên không gian tr ngạ thái, có 2

ngườ h pợ c nầ đ nế heuristic:

tr 1. V nấ đề có thể không có nghi mệ chính xác do các m nhệ đề không phát

2. V nấ đề có nghi mệ chính xác nh ngư phí t nổ tính toán để tìm ra nghi mệ là

bi uể ch tặ chẽ hay thi uế dữ li uệ để kh ngẳ đ nhị k tế quả.

quá l nớ (hệ quả c aủ bùng nỗ tổ h pợ )

Heuristic giúp tìm ki mế đ tạ k tế quả v iớ chi phí th pấ h nơ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 87

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Heuristic (tt)

 Heuristic dùng như thế nào trong SSS?

ngướ ngướ quá trình tìm ki mế theo h iớ nghi mệ là cao nh tấ . Không “sâu” cũng

– Tìm ki mế trên không gian tr ngạ thái theo chi uề nào? Sâu hay r ngộ ? – Tìm theo Heuristic : Heuristic đ nhị mà “nó” cho r ngằ khả năng đ tạ t không “r ng”ộ

 K tế quả c aủ tìm ki mế v iớ Heuristic

– Vi cệ tìm ki mế theo đ nhị

ngướ c aủ heuristic có k tế quả t

tố hay x uấ tùy

theo heuristic “đúng” hay “sai”.

– Heuristic có khả năng bỏ xót nghi mệ – Heuristic càng t

cượ Heuristic

tố càng d nẫ đ nế k tế quả nhanh và t Heuristic t cượđ LàmLàm saosao tìmtìm đ

tố . tố ?????? tốt

Baøi giaûng “Trí tueä nhaân taïo” - Slide 88

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Best First Search

Y đã có trong Open: if đ nế đ

cượ Y b ngằ m tộ path ng nắ h nơ then gán path ng nắ h nơ này cho Y trên Open.

Y đã có trên close: if đ nế đ cượ Y b ngằ m tộ path ng nắ h nơ

then begin xóa Y kh iỏ danh sách Close; thêm Y vào danh sách Open; end; end; /*end case*/ Đ aư X vào close; X pế thứ tự các tr ngạ thái trên Open theo giá

trị Heuristic (tăng d nầ )

Procedure Best_First_Search; Begin open:=[start]; close:=[]; While (open<>[]) do begin L yấ ph nầ tử đ uầ tiên X kh iỏ Open. if X là goal then return path từ start đ nế X else begin sinh ra các nút con c aủ X; for m iỗ nút con Y c aủ X do case Y of Y không có trong open hay close: begin gán giá trị heuristic cho Y; đ aư Y vào open; end;

Baøi giaûng “Trí tueä nhaân taïo” - Slide 89

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

end; / while/ return failure; End;

Best First Search (tt)

 Best First search vs Depth First & Breath First

– Best First search t

ngươ tự như Depth First & Breath First nh ngư ph nầ tử

tố nh tấ .

cượ xét ti pế theo là ph nầ tử có giá trị heuristic t – C nầ có m tộ hàm đánh giá các tr ngạ thái để xác đ nhị

giá trị heuristic cho

các tr ngạ thái.

– Không gian tr ngạ thái v nẫ không thay đ iổ về “toàn c c“ụ tuy nhiên th

ngườ Heuristic search có không gian tr ngạ thái làm vi cệ nhỏ h nơ Depth First và Breath First. T iạ sao??

Do sự đ nhị

ngướ các tr ngạ thái kế ti pế theo h

ngướ có khả năng tìm ra nghi mệ nhanh h nơ nên số tr ngạ thái xét dư th aừ sẽ h nạ chế  sinh ít tr ngạ thái con h nơ

Đi uề này cũng là nguyên nhân làøm cho Best First Search có thể d nẫ

đ nế k tế quả là “nghiêäm ph ”ụ thay vì “nghi mệ t

iố u”ư .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 90

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Hàm l

ngượ giá Heuristic

 Hàm l

ngượ giá Heuristic là hàm

cướ l

ngượ phí t nổ để đi từ tr ngạ thái hi nệ

iạ đ nế tr ngạ thái goal. t

hàm l

 Cơ sở để xác đ nhị

ngượ giá là d aự vào tri th cứ /kinh nghi mệ thu th pậ

cượ . đ  Hàm l

ngượ giá cho k tế quả đúng (g nầ th cự thế) hay sai (xa giá trị th cự ) sẽ

d nẫ đ nế k tế quả tìm đ

cượ t

tố hay x uấ .

ngượ giá Heuristic. Lý do:

 Không có chu nẩ m cự cho vi cệ đánh giá m tộ hàm l ngượ giá

– Không có c uấ trúc chung cho hàm l – Tính đúng/sai thay đ iổ liên t cụ theo t ngừ v nấ đề cụ thể – Tính đúng/sai thay đ iổ theo t ngừ tình hu ngố cụ thể trong m tộ v nấ

đề

hàm l

 Có thể dùng nhi uề hàm l ngượ giá về các hàm l

ngượ giá khác nhau theo tình hu ngố  c nầ ngượ giá.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 91

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Hàm l

ngượ giá Heuristic – Ví dụ

 Xét bài toán 8 pussle v iớ

goal là: 5 6 0

3 4 0

Heuristic 1: T ngổ số mi ngế sai vị trí

5 6 0

kho ngả Heuristic 2: T ngổ cách sai vị trí c aủ t ngừ mi ngế .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 92

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Vi cệ ch nọ l aự hàm Heuristic là khó khăn và có ý nghĩa quy tế đ nhị đ iố v iớ t cố độ c aủ gi iả thu tậ Heuristic 3: Số c pặ hoán đ iổ vị trí nhân cho 2

Hàm l

ngượ giá Heuristic – C uấ trúc

 Xét l

iạ ho tạ đ ngộ c aủ gi

iả thu tậ Best First Search: – Khi có 2 nút cùng có giá trị kỳ v ngọ đ tạ đ nế m cụ tiêu b ngằ nhau thì nút có cướ như v yậ

cượ ch nọ tr

path từ nút b tắ đ uầ đ nế nút đó ng nắ h nơ sẽ đ nút này có giá trị Heuristic t

tố h nơ .

– Hay nói cách khác hàm l

ngượ giá Heuristic cho nút g nầ start h nơ là t

tố h nơ

n uế kỳ v ngọ đ nế goal là b ngằ nhau.

– V yậ ch nọ nút nào n uế kỳ v ngọ c aủ 2 nút khác nhau? Nút kỳ v ngọ t

tố h nơ

nh ngư xa start hay nút kỳ v ngọ x uấ h nơ nh ngư g nầ root

 Hàm l

ngượ giá bao g mồ cả 2 và có c uấ trúc:

F(n) := G(n) + H(n)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 93

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

G(n): phí t nổ th cự từ root đ nế n H(n): phí t nổ cướ lu ngợ heuristic từ n đ nế goal.

Ví dụ – Best first search

 Xét ví dụ là bài toán 8 puzzle v iớ :

6 M cụ tiêu

B tắ đ uầ

ngượ giá: F(n) = G(n) + H(n)

 Hàm l V iớ G(n): số l nầ chuy nể vị trí tile đã th cự hi nệ

H(n): Số tile n mằ sai vị trí Nút X có giá trị heuristic t

tố h nơ nút Y n uế F(x) < F(y).

Ta có ho tạ đ ngộ c aủ gi

iả thu tậ Best First search trên như hình sau:

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 94

Ví dụ – Best first search (tt)

8

3

21

State A

1

6

4

7

5

F(a) =0+4=4

8

3

8

3

8

22 2x

State B State C State C

1

4

1

6

4

6

1

7

6

5

7

5

7

F(b) =1+5=6 F(c) =1+3=4 F(c) =1+5=6

3

8

3

8

3

23

24 2x

State E State F State G

1

8

4

1

4

1

7

6

5

6

5

6

5

7

F(e) =2+3=5 F(f) =2+3=5 F(g) =2+4=6

3

8

3 x

2x

State H State I

4

1

2

7

1

4

5

6

7

6

5

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 95

F(h) =3+3=6 F(i) =3+4=7

Ví dụ – Best first search (tt)

3

24

State F

4

1

8

5

7

6

F(f) =2+3=5

2

3

8

3

5 2x

2y

State J State K State Close

8

4

1

8

1

4

1

6

5

7

6

7

5

6

5

7

F(j) =3+2=5 F(k) =3+4=7

2

3

16

2

3 y

State L Close

8

4

8

4

1

6

5

7

F(l) =4+1=5

6

5

7

2

3

2

3

2

3 y

17 1x

State M State Close State N

8

4

1

4

8

7

8

4

6

5

7

6

5

7

6

5

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 96

F(m) =5+0=5 F(n) =5+1=7

Ho tạ đ ngộ theo gi

iả thu tậ Best First Search

[a4] [c4,b6,d6] [e5,f5,g6,b6,d6] [f5,h6,g6,b6,d6,i7] [j5,h6,g6,b6,d6,k7,i7] [l5,h6,g6,b6,d6,k7,i7] [m5,h6,g6,b6,d6,k7,i7,n7]

[] [a4] [a4,c4] [a4,c4,e5] [a4,c4,e5,f5] [a4,c4,e5,f5,j5] [a4,c4,e5,f5,j5,l5]

0 1 2 3 4 5 6 7

Laàn X Open Close

A4 C4 E5 F5 J5 l5 m5m5

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 97

Đánh giá gi

iả thu tậ Heuristic

 Admissibility – Tính ch pấ nh nậ

iả thu tậ Best first search v iớ hàm đánh giá

M tộ gi F(n) = G(n) + H(n) v iớ

N G(n) H(n)

: Tr ngạ thái b tấ kỳ : Phí t nổ đi từ nút b tắ đ uầ đ nế nút n : Phí t nổ

ngượ heuristic đi từ nút n đ nế goal

Đ cượ g iọ là gi

cướ l iả thu tậ A

M tộ gi iả thu tậ tìm ki mế đ cượ xem là admissible n uế đ iố v iớ m tộ đồ thị b tấ kỳ nó luôn

Gi

giá trị

tố nh tấ (n uế có). iả thu tậ A v iớ hàm heuristic H(n)luôn luôn £

d ngừ ở path nghi mệ t iả thu tậ A*: Là gi th cự đi từ n đ nế goal. Gi

iả thu tậ A* là admissible

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 98

Đánh giá gi

iả thu tậ Heuristic

 Monotonicity – Đ nơ đi uệ M tộ hàm heuristic H(n) đ nj 1.

cượ g iọ là monotone (đ nơ đi uệ ) n uế : là

cháu

con

nút

có

c aủ

" ni, H(ni)-H(nj) £

: phí t nổ th tậ đi từ ni đ nế nj

1. Đánh giá heuristic c aủ đích là 0 : H(goal) = 0.

iả thu tậ A có hàm H(n) monotone là gi

iả thu tậ A* và Admissible

H2(n) v iớ m iọ tr ngạ

thái n thì H2(n) đ

Gi  Informedness Xét 2 hàm heuristic H1(n) và H2(n) n uế ta có H1(n)£ cượ cho là informed h nơ H1(n).

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 99

Chi nế l

cượ minimax

 Gi

iả thu tậ tìm ki mế Heuristic v iớ các hàm heuristic chỉ thích h pợ cho các bài toán iố ra iườ ch iơ : Puzzle, tìm l

 Các trò ch iơ có tính đ iố kháng cao, th

không có tính đ iố kháng. Như các trò ch iơ chỉ có m tộ ng mê cung, bài toán n quân h uậ ,…

ngườ là các trò ch iơ 2 ng iả thu tậ trên không có tác d ngụ vì: Đ iố ph iườ ch iơ như: tic tac ngươ không

toa, caro, cờ qu cố tế,… gi bao giờ đi theo con đ  C nầ ph iả có m tộ gi ngườ cho ta có thể đi đ nế goal iả thu tậ khác phù h pợ h nơ .

MINIMAX cượ MINIMAX cượl

Chi nếChi nế l cượ thể hi nệ b ngằ gi

 Chi nế l sau: – Cả 2 đ iố thủ có cùng ki nế th cứ như nhau về không gian tr ngạ

thái c aủ trò ch iơ

– Cả 2 đ iố thủ có cùng m cứ cố g ngắ th ngắ như nhau

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 100

cượ Minimax (đ iả thu tậ minimax) d aự trên 2 giả thi tế

Gi

iả thu tậ minimax

cượ Minimax

 Chi nế l Hai đ iố thủ trong trò ch iơ có tên là MAX và MIN

– Max: bi uể di nễ cho m cụ đích c aủ đ iố thủ này là làm l nớ t

iố đa l

iợ thế

c aủ mình

– Min: bi uể di nễ cho m cụ đích c aủ đ iố thủ này là làm nhỏ t

iố đa l

iợ thế

c aủ đ iố ph

ngươ .

Trên cây tìm ki mế sẽ phân l pớ thành các l pớ Max và Min. V iớ m tộ node n b tấ kỳ,

– N uế nó thu cộ l pớ Max thì gán cho nó giá trị Max c aủ các node con – N uế nó thu cộ l pớ Min thì gán cho nó giá trị nhỏ nh tấ c aủ các node con.

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 101

Gi

iả thu tậ minimax – ví dụ

 Bài toán que diêm

M tộ t pậ que diêm ban đ uầ đ tặ gi aữ 2 ng

iườ ch iơ . L nầ l

tượ đi xen kẽ.

iườ đ nế l

tượ đi ph iả chia nhóm que diêm theo nguyên t cắ :

– Ch nọ nhóm b tấ kỳ có số que >2 – Chia thành 2 nhóm có số que khác nhau

iườ nào đ nế l tượ mà không chia đ cượ là thua.

cượ phát tri nể toàn bộ, các node lá

cượ gán giá trị 1 n uế là MAX th ngắ và 0 n uế là MIN th ngắ .

 V iớ m tộ node b tấ kỳ n uế thu cộ l pớ MAX gán cho nó giá trị l nớ nh tấ c aủ các node con. N uế thu cộ l pớ MIN gán cho nó giá trị nhỏ nh tấ c aủ các node con.

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 102

Goal: ng MINIMAX  Không gian tr ngạ thái c aủ trò ch iơ đ

Minimax – bài toán que diêm

7 1

MIN

6-1 1 5-2 1 4-3 1

MAX

5-1-1 0 4-2-1 1 3-2-2 0 3-3-1 1

MIN

4-1-1-1 0 3-2-1-1 1 2-2-2-1 0

MAX

3-1-1-1-1 0 2-2-1-1-1 1

MIN

2-1-1-1-1-1 0

MAX

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 103

Minimax v iớ độ sâu gi

iớ h nạ

 Minimax như đã xét bu cộ ph iả có toàn bộ không gian tr ngạ thái đã đ

cượ tri nể iạ  Không khả thi v iớ

cượ l

khai để có thể gán trị cho các nút lá và tính ng các bài toán l nớ vì không gian tr ngạ thái là quá l nớ .

 Gi

iạ theo m tộ độ sâu nào đó và gi

iớ h nạ các

iớ h nạ không gian tr ngạ thái l node con theo m tộ qui t cắ nào đó.

cượ thông th

ngườ c aủ các ng

iườ ch iơ cờ: khả năng tính tr

cướ

 Đây là chi nế l bao nhiêu n

cướ .

iớ h nạ .

ngượ giá Heuristic.

cượ minimax cho vi cệ đánh giá các nút c pấ trên.

 Khi đó ta chỉ tri nể khai các nút con đ nế độ sâu gi  Đánh giá cho các nút này như là nút lá b ngằ m tộ hàm l  áp d ngụ chi nế l  Kỹ thu tậ này g iọ là nhìn tr

cướ K b

cướ v iớ K la øđộ sâu gi

iớ h nạ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 104

Ví dụ: Bài toán Tic Tac Toa

 Hàm l

ngượ giá heuristic E(n) = X(n) – O(n) v iớ

– X(n) số khả năng th ngắ c aủ quân X. – O(n) số khả năng th ngắ c aủ quân O

X có 6 khả năng th ngắ

E(n) = 6 5 = 1

O có 5 khả năng th ngắ

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 105

V iớ hàm Heuristic trên X sẽ cố làm cho E(n) l nớ nh tấ (MAX) và O làm cho E(n) nhỏ nh tấ (MIN). Tri nể khai bài toán v iớ 2 b cướ nhìn tr cướ .

Ví dụ: Bài toán Tic Tac Toa

1 MAX

-1

1 -2

MIN

1

2 MAX

0 -1

-1 X

1 X

Baøi giaûng “Trí tueä nhaân taïo” - Slide 106

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Độ ph cứ t pạ c aủ gi

iả thu tậ SSS

 Độ ph cứ t pạ tính theo hệ số rẽ nhánh.  Xét bài toán có hệ số rẽ nhánh trung bình là B, độ sâu trung bình c aủ iớ

cượ xét qua để tìm ra l

solution path là D . V iớ T là số tr ngạ thái đã đ gi

iả thì ta có

T= (B +B2 + B2 +……….+BD)/(B-1) T sẽ r tấ l nớ đ iố v iớ các v nấ đề th cự tế.

Ph iả dùng Heuristic để gi

iớ h nạ độ ph cứ t pạ c aủ gi

iả thu tậ b ngằ cách

gi mả số tr ngạ thái ph iả đi qua.

Tuy nhiên hàm Heuristic t

tố thì l

iạ đòi h iỏ yêu c uầ tính toán nhi uề  Phí

t nổ cho tính toán tăng cao.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 107

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ 5:

ngươCh Ch

5: HỆHỆ LU TẬLU TẬ SINHSINH Production system system Production

nghĩa và ngứ d ngụ

Tìm ki mế đệ qui Hệ lu tậ sinh: Đ nhị Tìm ki mế trên hệ lu tậ sinh

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K h oa C oân g N g h eä Th oân g Tin

Th aù n g 6/2001

Đ cặ tính dữ li uệ và đi uề khi nể c aủ SSS

 Các đ cặ tính c aủ gi

iả thu tậ SSS:

iả là m tộ PATH từ đi mể START đ nế đi mể GOAL

ngườ d nẫ đ nế GOAL

– L iờ gi – Tìm ki mế là sự ki mể tra có hệ th ngố các đ – Backtracking cho phép gi

iả thu tậ “ph cụ h i”ồ khi đi vào m tộ nhánh không

có đáp án.

– Các danh sách sẽ giữ các tr ngạ thái đang xem xét:

 Danh sách Open: cho phép hệ th ngố backtrack về các tr ngạ thái ch aư đ

cượ

 Danh sách Close: cho phép hệ th ngố ki mể tra sự quay vòng tránh l pặ vô t nậ

– Dùng STACK cho DFS, QUEUE cho BFS và dùng PRIORITY QUEUE

cho BFS.

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 109

xét.

Tìm ki mế đệ qui – T iạ sao???

 Tìm ki mế đệ qui là gi

iả thu tậ tìm ki mế trên SSS v iớ các đ cặ tính:

– Ng nắ g nọ xúc tích h nơ – Ti pế c nậ c aủ gi – H pợ nh tấ v iớ ph

iả thu tậ tự nhiên h nơ ngươ th cứ hi nệ th cự c aủ Logic vị từ

 Các gi

iả thu tậ tìm ki mế đệ qui chính: – Tìm ki mế đệ qui – Recursive Search (RS) – Tìm ki mế theo m uẫ – Pattern Directed Search (PDS)

 Các gi

cượ sử d ngụ r ngộ r iả trong các shell

iả thu tậ tìm ki mế đệ qui đ c aủ các Hệ chuyên gia (Expert System).

 Pattern Directed Search là n nề t nả c aủ PROLOG

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 110

Thế nào là đệ qui?

nghĩa m tộ đ iố t

ngượ b ngằ cách sử d ngụ chính đ iố t

ngượ

 Đệ qui là sự đ nhị đó – Toán h cọ

 Đệ qui đ

nghĩa và phân tích các c uấ trúc dữ li uệ cũng như

cượ dùng để đ nhị các thủ t cụ xử lý trong ngành máy tính.

 M tộ thủ t cụ đệ qui bao g mồ :

– Thành ph nầ đệ qui, trong đó thủ t cụ g iọ chính nó để l pặ l

iạ

chu iổ các thao tác.

– Thành ph nầ d ngừ dùng để d ngừ quá trình đệ qui vô t nậ . (l pặ vô

t nậ )

 Hai thành ph nầ này t nồ t

iạ đ ngồ th iờ trong t

tấ cả các đ nhị

nghĩa đệ qui cũng

như gi

iả thu tậ đệ qui.

 Đệ qui là m tộ c uấ trúc đi uề khi nể dữ li uệ tự nhiên cho nh ngữ c uấ trúc không : list, tree, và đồ thị.

số ph nầ tử cố đ nhị

xác đ nhị

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 111

Thủ t cụ đệ qui – ví dụ

 Đệ qui có đ yầ đủ tính năng c aủ các c uấ trúc đi uề khi nể truy nề th ngố như Loop và rẽ nhánhm iọ ch ngươ trình cượ b ngằ c uấ trúc truy nề th ngố vi đ uề có thể vi

tế đ

Function Member(item, list); begin if List r ngỗ then return (Fail) else if Item = ph nầ tử đ uầ c aủ list then

return (succes)

tế đệ qui.  Đệ qui thích h pợ bi uể di nễ các c uấ trúc toán h cọ  thu nậ ti nệ trong vi cệ iả thu tậ ki mể tra tính đúng đ nắ c aủ gi đệ qui.

 Công th cứ đệ qui cũng th

else begin

cượ tra

 Đệ qui là công cụ tự nhiên và m nhạ iả

ngườ đ dùng trong vi cệ sinh và ki mể ch ngươ trình tự đ ngộ . Tail:= List \ ph nầ tử đ uầ ; member (item, Tail);

cượ gi

end end; mẻ cho hi nệ th cự các chi nế l quy tế v nấ đề c aủ AI.

T iạT iạ saosao??

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 112

Gi

iả thu tậ DFS đệ qui - DFS

Function Depth_First_Search; Begin if Open r ngỗ then return (fail); Current_state := ph nầ tử đ uầ tiên c aủ open; If (current_state là m cụ tiêu) then return (Success) else begin open:=ph nầ đuôi c aủ open; Closed := Closed + current_state; for m iỗ ph nầ tử con Y c aủ current_state do if not (Y in close) and not (Y in open) then thêm Y vào đ uầ c aủ Open; End; depth_first_search; End;

cượNh Nh

cượ đi mểđi mể c aủc aủ recursive

recursive ? ?

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 113

Pattern-Directed Search (PDS)

 Các gi

iả thu tậ Search đã tìm hi uể và Recursive Seach không trình bày cách bi uể di nể m tộ tr ngạ thái trong không gian tr ngạ thái cũng như cách sinh các tr ngạ thái m iớ .  Pattern-Directed Search là m tộ gi

iả thu tậ search đệ quy dùng Logic Vị

từ để hi nệ th cự vi cệ sinh các tr ngạ thái m iớ .

 Gi

iả thu tậthu tậ : Xu tấ phát từ goal P, áp d ngụ m tộ gi

 Paterm-Directed Search xu tấ phát từ goal và các modus ponen d ngạ q(x)->p(x) để chuy nể tr ngạ thái. Các modus ponen này g iọ là các lu tậ sinh. iảGi iả thu tậ để tìm các rule v iớ P ở vế ph iả , sau đó xem vế trái Q là subgoal. Đệ quy v iớ Q cho đ nế khi Qx là m tộ sự ki nệ trong kho tri th cứ .

Sự ki nệ (FACT) trong kho tri th cứ ?????

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 114

Gi

iả thu tậ PDS

Function Pattern_search(current_goal); Begin If current_goal có trong closed then retuen fail else thêm current_goal vào trong closed; while còn trong database các rule hay fact ch aư

tấ cả các h iộ đ uề success

xét begin case current_goal trùng v iớ fact:

If t then return success else return fail. end; Current_goal là vế ph iả m tộ rule: begin

return(success);

current_goal là m tộ phép h iộ :

begin for m iỗ thành ph nầ h iộ Pi do pattern_search(Pi);

áp d ngụ các thành ph nầ vào vế trái Q. if pattern_search(Q) then return success else return fail;

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 115

end; end; /* case Return fail; End;

Gi

iả thu tậ PDS

 PDS dùng các rule và thành ph nầ h iộ để sinh các tr ngạ thái con.  Tách b chạ quá trình đi uề khi nể c aủ gi

iả thu tậ và dữ li uệ c aủ gi

iả

thu tậ N  Cùng gi

iả thu tậ chỉ c nầ thay đ iổ database : Fact & Rule ta sẽ áp

d ngụ cho các bài toán khác nhau.

N Xây d ngự các shell và có thể v nậ hành cho các hệ th ngố khác

nhau b ngằ cách thay đ iổ Database. iả thu tậ ch aư gi

 Để đ nơ gi nả hoá gi

iả quy tế ở m cứ độ có các bi nế trong các rule. Ví dụ P(x)^Q(x) chỉ thõa khi P và Q cùng th aỏ v iớ cùng giá trị X.  Các phép (cid:216)

, v,.. cũng ch aư gi

iả quy tế trong gi

iả thu tậ này.

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 116

Ví dụ: Bài toán mã đi tu nầ

Đ cặ tả bài toán: tìm đ ngườ đi cho con mã qua t tấ cả các ô trên bàn cờ. Ví dụ v iớ bàn

move(1,8)

move(1,6)

move(2,9)

move(2,7)

cờ 3x3.

move(3,4)

move(3,8)

move(4,9)

move(4,3)

1 2 3

move(6,1)

move(6,7)

move(7,2)

move(7,6)

move(8,3)

move(8,1)

move(9,2)

move(9,4)

4 5 6

" X path(X,X); " X,Y [path(X,Y)  $ Z[move(X,Z]^path(Z,Y)]]

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 117

7 8 9

Gi

iả thu tậ PDS đ yầ đủ

If t

tấ cả các h iộ đ uề success then return các

thành ph nầ h iộ else return fail.

Function Pattern_search(current_goal); Begin If current_goal có trong Closed then return fail else

end; current_goal là phép tuy nể : begin repeat cho m iọ thành ph nầ tuy nể Vi; until (pattern_search(Vi) or (h tế thành ph nầ

h iộ )

return(success);

if pattern_search (Vi) then return các thay thế

else return fail;

thêm current_goal vào Closed; while còn các rule hay fact ch aư xét begin case current_goal trùng v iớ fact: current_goal là negated((cid:216) p): begin

if pattern_search(p) then return fail

end; Current_goal là vế ph iả m tộ rule: begin

else return{} end; current_goal là m tộ phép h iộ :

áp d ngụ các thành ph nầ vào vế trái Q. if pattern_search(Q) then return k tế h pợ c aủ Current_goal và các thay thế c aủ Q else return fail; end; end; /* case*/ return fail; End;

begin for m iỗ thành ph nầ h iộ Pi do if not (pattern_search(Pi)) the return fail else thay thế t tấ cả các bi nế cho các thành ph nầ h iộ khác.

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 118

Hệ Lu tậ Sinh – Production System

 Khái ni mệ : Hệ lu tậ sinh là m tộ mô hình tính toán quan tr ngọ trong iả quy tế v nấ đề c aủ

các bài toán tìm ki mế cũng như mô ph ngỏ cách gi con ng  Đ nhị

iườ trong lĩnh v cự ngứ d ngụ AI. nghĩa: Hệ lu tậ sinh là m tộ mô hình tính toán cung c pấ cơ chế iả quy tế v nấ đề

đi uề khi nể Pattern_directed trong quá trình gi (Proplem solving process).

 C uấ trúc hệ lu tậ sinh bao g mồ 3 thành ph nầ :

1. Production rules ( T pậ lu tậ s nả sinh) 2. Working memory (Vùng nhớ làm vi cệ ) 3. Recognize-action control (Bộ đi uề khi nể nh nậ d ngạ và hành đ ngộ )

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 119

nghĩa (tt) – Production Rule

Đ nhị

cượ đ cặ tả d ngạ :

Action (đi uề ki nệ – hành đ ngộ )

 Production rules: là m tộ t pậ các lu tậ s nả sinh đ Condition –– Action Condition

iả quy tế v nấ đề. Kho tri

 M tộ lu tậ là m tộ m tắ xích c aủ kho tri th cứ gi th cứ là m tộ database c aủ các production rules.

 Thành ph nầ Condition: là m tộ m uẫ (pattern) dùng xác đ nhị

đi uề ki nệ áp

d ngụ c aủ rule cho m tộ v nấ đề t

ngươ ngứ .

 Thành ph nầ action: mô tả b

iả quy tế v nấ đề t

ngươ ngứ sẽ đ

cướ gi

cượ th cự hi nệ . Đây là ph nầ sẽ tác đ ngộ lên hi nệ tr ngạ c aủ không gian tìm ki mế .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 120

nghĩa (tt) – Working memory

Đ nhị

 Working memory ch aứ nh ngữ đ cặ tả tr ngạ thái hi nệ t

iạ c aủ quá trình

suy lu nậ . Chúng đ

cượ l uư trữ như là t pậ các m uẫ .  Nh ngữ đ cặ tả này là các m uẫ để so trùng v iớ các condition c aủ các

production rules.

 Khi m tộ production rule đ

cượ áp d ngụ , và ph nầ action này đ

cượ so trùng ph nầ condition thì ph nầ action cượ xây d ngự đ cặ

c aủ nó có thể đ thù để tác đ ngộ tr cự ti pế lên working memory.

 Working memory đ

cượ kh iở t oạ b ngằ tr ngạ thái b tắ đ uầ c aủ v nấ đề

c nầ gi

iả quy tế .

 Working memory di nễ tả hi nệ tr ngạ c aủ v nấ đề c nầ suy lu nậ

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 121

nghĩa (tt) – Recognize-action

Đ nhị

 Đây là c uấ trúc đi uề khi nể dùng trong production system. Quy trình

ho tạ đ ngộ c aủ Recognize -Action

Recognize (match pattern)

Ch nọCh nọ thếthế nàonào????

Working Memory (t pậ các m uẫ )

Select rule Ch nọ m tộ rule

Conflict Set T pậ các production rule Matched v iớ working memory

Selected Conflict

Tác đ ngộ làm thay đ iổ Working Memory

Apply Action Th cự hi nệ action cượ ch nọ c aủ rule đ

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 122

Các v nấ đề khác

 Ch nọ l aự Conflict để th cự hi nệ

Có thể ch nọ b ngằ cách đ nơ gi nả hay áp d ngụ các chi nế l

cượ l aự

ch nọ heurictic  ngỨ d ngụ meta knowledge.

ng” N uế g iọ chi nế l cượ heuristic ch nọ conflict là meta knowledge thì knowledge “th ườ

 Các hệ lu tậ sinh đ nơ thu nầ không cung c pấ cơ chế để quay lui khi vi cệ áp d ngụ các action làm cho working memory thay đ iổ d nẫ đ nế lúc cượ  Hệ th ngố sẽ không còn production rule nào có thể áp d ngụ đ d ngừ .

 C nầ cung c pấ cơ chế backtracking (Th

ở đâu trong hệ th ngố ?

chú ý để tránh l pặ vòng.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 123

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngườ dùng UNDO). Tuy nhiên c nầ

Ví dụ: bài toán 8 Puzzle

2

8

3

1

2

3

 Working Memory

Current state

1

6

4

8

4

Goal state

7

5

7

6

5

 Production Rules

Goal state  Halt

Blank is not on top edge  Move the blank up

Blank is not on the right edge  Move the blank right

Blank is not on the bottom edge  Move the blank down

Blank is not on the left edge  Move the left down

 RecognizeAction

1 Try each production rule in order

2 Do not allow loops

Baøi giaûng “Trí tueä nhaân taïo” - Slide 124

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

3 Stop when goal is found

Đi uề khi nể tìm ki mế trong hệ lu tậ sinh

 Chi nế l

–

cượ goal state.

–

Data-Driven: b tắ đ uầ v iớ problem trong working memory, matching các condition trong production rule  conflict  áp d ngụ các action  thay đ iổ working memory. L pặ l iạ cho đ nế khi đ tạ đ Goal-Driven: B tắ đ uầ v iớ mô tả goal trong working memory, matching v iớ các k tế quả c aủ Action  sinh t pậ các condition đ aư các condition vào trong working memory. L pặ l

ngươ đ

ngươ c aủ các bi uể th cứ trong

iạ cho đ nế khi working memory ch aứ FACT.  Đi uề khi nể qua c uấ trúc rule: Dùng các bi nế đ iổ t

rule để đi uề khi nể quá trình tìm ki mế .

cượ ch nọ l aự thông

 Đi uề khi nể b ngằ sự phân tích các Conflict: Các conflict có thể đ

qua các Heuristic. áp d ngụ các meta knowledge trong vi cệ ch nọ conflict. Ví dụ:

cượ Data-Driven / Goal-Driven:

cượ áp d ngụ , nó sẽ không đ

cượ dùng n aữ cho đ nế khi thánh

cượ thay đ iỗ .

cượ đ cặ tả chi ti

cượ uư tiên cao.

tế càng đ

Refraction: Khi m tộ rule đã đ ph nầ trùng l pặ v iớ rule cũ trong working memory đ Recency: Ch nọ rule có ph nầ condition match v iớ ph nầ m iớ thêm vào working memory. Theo đu iổ m tộ h ngướ tri nể khai. Specificity: Rule nào càng đ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 125

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Các uư đi mể c aủ Hệ lu tậ sinh

 Hệ lu tậ sinh là khung làm vi cệ t ngổ quát để th cự thi các gi

iả thu tậ tìm ki mế . V iớ đ cặ tính cượ dùng như m tộ công cụ quan tr ngọ để

đ nơ gi nả , dể s aử đ iổ , và linh đ ngộ , hệ lu tậ sinh đ xây d ngự các hệ chuyên gia và các ngứ d ngụ AI khác

 Các uư đi mể c aủ Hệ lu tậ sinh:

 Tách b chạ gi aữ Tri th cứ & Đi uề khi nể :

cượ ch aứ đ ngự trong b nả thân các lu tậ sinh.

 Đi uề khi nể : n mằ trong chu trình Recognize-Action  Tri th cứ : đ  Cung c pấ khả năng c pậ nh tậ tri th cứ mà không c nầ đi uề ch nhỉ

ngươ trình. Thay

đ iổ mã ch

ngươ trình mà không nhả h

ngưở đ nế t pậ lu tậ sinh.

 Dễ dàng áp d ngụ trong tìm ki mế trên không gian tr ngạ thái. Các state c aủ working memory là các node. Các production rule là các chuy nể đ iổ gi aữ các tr ngạ thái (cơ chế sinh các tr ngạ thái m iớ )

iả thích quá trình ho tạ đ ngộ

 Tính đ cộ l pậ c aủ các lu tậ sinh.  Khả năng áp d ngụ heuristic cho vi cệ đi uề khi nể quá trình ho tạ đ ngộ .  Theo dõi và gi  Đ cộ l pậ v iớ ngôn ngữ & có thể dùng như kỹ thu tậ mô ph ngỏ gi

iả pháp c aủ ng

iườ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 126

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

ngươ 6:

CHUYÊN GIAGIA ( (ESES))

ngươCh Ch

6: HỆHỆ CHUYÊN

iớ thi uệ về hệ chuyên gia

Gi Mô hình hệ chuyên gia: dự trên lu tậ , d aự trên frame Phát tri nể m tộ hệ chuyên gia

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K hoa C oâng N gheä Thoâng Tin

Thaùng 6/2001

N iộ dung.

 Gi

– Đ nhị nghĩa, khả năng ngứ d ngụ . – C uấ trúc, các đ cặ tr ngư cơ b nả c aủ ES. – Bi uể di nễ tri th cứ . – Các kỹ thu tậ suy lu nậ .

 Kh oả sát m tộ vài hệ chuyên gia đã có.

– XCON: ES trợ giúp c uấ hình hệ th ngố máy tính c aủ DEC – MYCIN: ES chu nẩ đoán b nhệ nhi mễ trùng máu.

 Hệ chuyên gia d aự trên lu tậ .

– Ki nế trúc, thi uƯ - nh –

iớ thi uệ về hệ chuyên gia.

 Hệ chuyên gia d aự vào Frame.

– Ki nế trúc, thi uƯ - nh –

tế kế. cượ đi mể .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 128

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

tế kế. cượ đi mể .

Gi

iớ thi uệ về hệ chuyên gia.

nghĩa:

 Đ nhị

tế kế để theo mô hình có khả năng gi iả

 Sơ đồ kh iố cơ b nả :

Cô sôû tri thöùc

Ñoäng cô Suy luaän

H eä chuyeân gia

Baøi giaûng “Trí tueä nhaân taïo” - Slide 129

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Hệ chuyên gia là m tộ ch ngươ trình đ quy tế v nấ đề c aủ chuyên gia con ng cượ thi iườ .

Gi

iớ thi uệ về hệ chuyên gia.

 Cơ sở tri th cứ :

con ng

§ Dùng để ch aứ tri th cứ trong m tộ lĩnh v cự nào đó, tri th cứ này do chuyên gia iườ chuy nể giao. Nó bao g mồ : các khái ni mệ cơ b nả , các sự ki nệ , các lu tậ và quan hệ gi aữ

chúng.

Ví dụ:

cượ đ uầ tư do các nhà cố v nấ đ uầ tư chuy nể giao.

dữ li uệ kh oả sát đ aị v tậ lý do các kỹ sư đ aị ch tấ chuy nể

Baøi giaûng “Trí tueä nhaân taïo” - Slide 130

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

- Tri th cứ về b nhệ nhi mễ trùng máu do các bác sĩ chuyên khoa này chuy nể giao. - Tri th cứ về chi nế l - Tri th cứ về sự di nễ d chị giao. - …?

Gi

iớ thi uệ về hệ chuyên gia.

 Đ ngộ cơ suy lu nậ :

Là bộ xử lý cho tri th cứ , đ

cượ mô hình sao cho gi ngố v iớ vi cệ suy iườ . Bộ xử lý này làm vi cệ d aự trên thông iườ dùng mô tả về v nấ đề, k tế h pợ v iớ CSTT, cho ra k tế

lu nậ c aủ chuyên gia con ng tin mà ng lu nậ hay đề nghị.

 T oạ sao ph iả xây d ngự ES ? Chuyên gia con ng

iườ là tài nguyên quý giá cho nhi uề tổ ch cứ . Họ iả quy tế nh ngữ v nấ đề khó, hi uệ quả,…. V yậ có giá trị không ngươ trình có khả năng như chuyên gia iườ ?M tộ số m tặ nào đó còn có thể h nơ h nẳ . Xem b ngả so sánh

có thể gi khi chúng ta xây d ngự m tộ ch con ng sau:

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 131

Gi

iớ thi uệ về hệ chuyên gia.

§ B ngả so sánh:

M iọ n iơ .

Tiêu chí CG con ng ES.

Có

ngườ nhanh h nơ )

Không. H ngằ số. H ngằ số (th

1. S ngẵ dùng 2. Vị trí 3. An toàn 4. Có thể ch tế 5. Hi uệ su tấ 6. T cố độ 7. Chi phí

Thay đ iổ Thay đ iổ Cao

Có thể cố g ngắ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 132

iườ TG. hành chính M iọ lúc. C cụ bộ không thể thay thế Có thể thay thế.

Gi

iớ thi uệ về hệ chuyên gia.

iườ :

Vài lý do để phát tri nể ES thay cho chuyên gia con ng T oạ cho tính chuyên gia s nẵ dùng ở m iọ n iơ , m iọ lúc. Tự đ ngộ hoá các công vi cệ đòi h iỏ chuyên gia. Các chuyên gia đang nghỉ h uư hay chuy nể đ nế n iơ khác – C nầ

thay thế.

Thuê chuyên gia v iớ chi phí quá l nớ . Tính chuyên gia c nầ thi

tế trong các môi tr

ngườ làm vi cệ không thân thi nệ , ở đó h iỏ m tộ ES sẽ nhanh h nơ m tộ chuyên gia con ng

iườ . Phát tri nể ES để trợ giúp cho chuyên gia con ng

iườ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 133

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Gi

iớ thi uệ về hệ chuyên gia.

 Các ki uể v nấ đề th

đ ngườ cượ gi iả

L aự ch nọ : Mô ph ngỏ :

quy tế b iở ES: § § § § § § § §

Đi uề khi nể : Thi tế kế: Chu nẩ đoán: D yạ h cọ : Di nễ d chị : Giám sát: Ho chạ đ nhị Dự đoán:

Baøi giaûng “Trí tueä nhaân taïo” - Slide 134

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

C uấ trúc c aủ ES.

 C uấ trúc c aủ ES:

ES mô ph ngỏ khả năng gi

iả quy tế v nấ đề c aủ chuyên gia con ng

iườ . Do v yậ , chúng ta

c nầ xem xét cách th cứ gi

iả quy tế c aủ chuyên gia con ng

iườ , để từ đó mô ph ngỏ .

Long- Term Memory ------------------------- Tri thöùc cuûa lónh vöïc

Boä suy luaän

Ngöôøi ñöôïc khuyeân ------------- Söï kieän, Keát luaän

Short- Term Memory ------------------------- Söï kieän, keát luaän

Baøi giaûng “Trí tueä nhaân taïo” - Slide 135

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Chuyeân gia con ngöôøi

C uấ trúc c aủ ES.

CSTT ------------------------- Tri thöùc cuûa lónh vöïc

Ñoäng cô suy luaän

Ngöôøi duøng ------------- Söï kieän, Keát luaän

Boä nhôù laøm vieäc ------------------------- Söï kieän, keát luaän

§ Cách gi iả quy tế v nấ đề ở ES:

Baøi giaûng “Trí tueä nhaân taïo” - Slide 136

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Heä chuyeân gia

C uấ trúc c aủ ES.

 CSTT:

Là m tộ bộ ph nậ c aủ ES nh mằ ch aứ tri th cứ c aủ lĩnh v cự . cượ g iọ là CSTT. iườ trong m tộ bộ ph nậ đ iườ kỹ sư tri th cứ ph iả thu th pậ tri th cứ từ chuyên gia con cượ đề c pậ trong ph nầ kỹ

§ ES ch aứ tri th cứ c aủ chuyên gia con ng

iườ r iồ mã hoá vào CSTT – cách th cứ mã hoá sẽ đ

M tộ trong các cách tiêu bi uể để bi uể di nễ là dùng lu tậ , như sau:

c”ượ

IF “Xe car không thể kh iở đ ngộ đ THEN “V nấ đề trong hệ th ngố đi n”ệ

RULE 2:

IF “V nấ đề trong hệ th ngố đi n”ệ AND “Đi nệ thế AC-quy nhỏ h nơ 10Volt” THEN l

iạ bộ AC-quy”

iỗ t

Baøi giaûng “Trí tueä nhaân taïo” - Slide 137

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Để có tri th cứ này, ng ng thu tậ bi uể di nễ tri th cứ . § RULE 1:

C uấ trúc c aủ ES.

 Bộ nhớ làm vi cệ :

iườ cùng thì bộ nhớ làm vi cệ th iườ dùng. Đó là tr

ngườ phân ngườ h pợ

cượ ch aứ trong các ngu nồ iả thông tin này vào bộ

Là bộ ph nậ c aủ ES dùng để ch aứ các sự ki nệ c aủ v nấ đề. Các sự ki nệ này có thể do ng iườ dùng nh pậ vào lúc đ uầ hay do ES sinh ra trong quá trình làm vi cệ . - V iớ ES dùng cho nhi uề ng nhóm theo phiên làm vi cệ (session) c aủ ng iườ dùng từ xa. m tộ ES chung cho nhi uề ng - Nhi uề ES cũng t nậ d ngụ các thông tin đ ngoài như: CSDL, b ngả tính, sensor,…ES sẽ t tế . nhớ làm vi cệ đ uầ m iỗ session hay khi c nầ thi

Baøi giaûng “Trí tueä nhaân taïo” - Slide 138

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

C uấ trúc c aủ ES.

 Đ ngộ cơ suy lu nậ :

Là bộ xử lý trong hệ chuyên gia, là nhi mệ vụ so trùng các sự ki nệ đ

cượ cượ ch aứ trong CSTT nh mằ d nẫ ra

ch aứ trong bộ nhớ làm vi cệ v iớ tri th cứ đ k tế lu nậ cho v nấ đề.

Tiêu bi uể , n uế CSTT có ch aứ lu tậ , ES sẽ tìm ra lu tậ mà các tiên đề cượ ch aứ trong bộ nhớ làm vi cệ , lúc đó ES c aủ lu tậ so trùng v iớ các sự ki nệ đ sẽ thêm các k tế lu nậ c aủ lu tậ đó vào bộ nhớ làm vi cệ , r iồ ti pế t cụ tìm ra sự so trùng khác – gi ngố như nguyên lý ho tạ đ ngộ c aủ hệ lu tậ sinh. Ví dụ: Giả sử CSTT chỉ v iớ hai lu tậ nêu trên

cượ ?

ES: Ng

Có ph iả xe car không kh iở đ ngộ đ Đúng.

iườ dùng:

Baøi giaûng “Trí tueä nhaân taïo” - Slide 139

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

§ cướ 1:

C uấ trúc c aủ ES.

iườ dùng trả l iờ “Đúng”, nên ES thêm vào bộ nhớ làm vi cệ sự ki nệ để

Chú thích: Ng mô tả:

c”ượ

“Xe car không thể kh iở đ ngộ đ Đ ngộ cơ suy di nễ c aủ ES làm nhi mệ vụ so trùng, nh nậ th yấ RULE 1 có thể so

trùng đ cượ , nên nó thêm vào bộ nhớ làm vi cệ ph nầ k tế lu nậ c aủ RULE 1, đó là:

“V nấ đề trong hệ th ngố đi n”ệ

iướ 10 Volt?

iườ dùng:

Có ph iả đi nệ Ac-quy d Đúng. iườ dùng trả l iờ “Đúng”, nên ES thêm vào bộ nhớ làm vi cệ sự ki nệ

cướ 2: ES: Ng Chú thích: Ng để mô tả:

“Đi nệ thế Ac-quy nhỏ h nơ 10Volt” Đ ngộ cơ suy di nễ c aủ ES làm nhi mệ vụ so trùng, nh nậ th yấ RULE 2 có thể so

Baøi giaûng “Trí tueä nhaân taïo” - Slide 140

trùng đ l cượ , nên nó thêm vào bộ nhớ làm vi cệ ph nầ k tế lu nậ c aủ RULE 2, đó là: iỗ t iạ bộ Ac-quy” – phiên làm vi cệ cũng k tế thúc vì CSTT chỉ g mồ hai lu tậ

trên. Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

C uấ trúc c aủ ES.

 Ti nệ ích gi

iả thích.

M tộ trong các đi mể n iổ b tậ c aủ ES là khả năng gi

iả thích về suy lu nậ c aủ nó. iả thích.

ES còn có m tộ kh iố cơ b nả n aữ trong c uấ trúc c aủ nó đó là: kh iố ti nệ ích gi V iớ kh iố này ES có thể cung c pấ cho ng iườ dùng các khả năng gi iả thích:

iạ h iỏ câu h iỏ nào đó. (WHY) - T iạ sao ES l - B ngằ cách nào ES có thể suy ra k tế lu nậ nào đó. (HOW) Kh iố ti nệ ích gi iả thích thu nậ ti nệ cho cả ng

iườ phát tri nể có thể nhờ đó khám phá các l iườ phát tri nể ES và ng iỗ trong tri th cứ c aủ ES. Ng

iườ dùng. iườ thì có tế ph iả quan tâm v iớ

Ng thể yên tâm h nơ khi nh nậ m tộ k tế lu nậ nào đó, không c nầ thi c uấ trúc tri th cứ c aủ ES.

§ iả thích b ngằ cách nào (HOW) Ngoài ch cứ năng cung c pấ cho ng iườ dùng k tế quả suy lu nậ cu iố cùng, ES

Baøi giaûng “Trí tueä nhaân taïo” - Slide 141

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

càng có thể cung c pấ nó đ tạ đ nế k tế lu nậ b ngằ cách nào.

C uấ trúc c aủ ES.

Khả năng gi

nghĩa t ngươ trình truy nề th ngố . Các ch cượ đ nhị cượ ki mể nghi mệ tr tố , k tế quả c aủ ch ngươ trình đã đ

iả thích b ngằ cách nào r tấ quan tr ngọ v iớ ES, nó làm cho ES khác ngươ trình truy nề th ngố làm vi cệ trên các v iớ các ch bài toán đ cướ khi chuy nể giao. ES làm vi cệ trên các bài toán thi uế nhi uề thông tin, th mậ chí tri th cứ còn có thể c pậ nh tậ khi ES đã đ cượ tri nể khai – chính vì v yậ mà k tế lu nậ c aủ nó ph iả đ iả thích b ngằ cách nào để cho k tế quả cu iố cùng có giá trị h nơ . cượ gi

iạ bộ Ac-quy”.

iườ dùng:

cượ , tôi cho r ngằ đã có v nấ đề tế iướ 10 volt, tôi bi

Ví dụ: trong phiên làm vi cệ c aủ ES nói trên. ES: l iỗ t HOW Ng ES: “B iở vì, khi xe c aủ b nạ không kh iở đ ngộ đ trong hệ th ngố đi nệ . M iỗ l nầ , tôi th yấ đi nệ thế c aủ ac-quy d r ngằ ac-quy đã hư.”

iả thích HOW c aủ ES có thể th cự hi nệ đ cượ b ngằ cách cho phép nó

Baøi giaûng “Trí tueä nhaân taïo” - Slide 142

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

- Khả năng gi theo v tế các lu tậ mà nó đã sử d ngụ vào suy lu nậ .

C uấ trúc c aủ ES.

§ Gi iạ sao (WHY)

iả thích t khả năng c aủ ES cung c pấ cách gi iả thích: “t oạ sao nó l

iườ dùng cũng có thể theo v tế đ iạ h iỏ m tộ câu h iỏ nào cượ lu ngồ suy lu nậ c aủ

đó.” V iớ khả năng này, ng ES và yên tâm h nơ v iớ k tế quả.

Ví dụ: trong phiên làm vi cệ v iớ ES nói trên. Có ph iả xe car không kh iở đ ngộ đ cượ ?

iườ dùng: WHY

tế r ngằ xe car không kh iở đ ngộ đ cượ , thì tôi th ngườ cho r ngằ có

ES: Ng ES: “N uế tôi bi v nấ đề trong hệ th ngố đi nệ .”

Khi chúng ta h iỏ WHY, ES th

iờ . H uầ h tế các ES th ngườ đáp trả b ngằ cách mô tả cái gì mà nó có ngườ đáp trả b ngằ cách hi nệ lu tậ mà

Baøi giaûng “Trí tueä nhaân taïo” - Slide 143

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

thể k tế lu nậ từ câu trả l nó đang quan tâm.

C uấ trúc c aủ ES.

 Giao di nệ ng

iườ dùng:

iườ dùng và nh nậ về câu trả l

Giao di nệ cũng là m tộ thành ph nầ quan tr ngọ c aủ ES, nó giúp cho iờ chính xác. ES có thể đ tặ câu h iỏ v iớ ng Yêu c uầ cao nh tấ cho giao di nệ là có khả năng cung c pấ cách h iỏ đáp ngươ tự như gi aữ ng t

iườ - v iớ - ng

iườ . Khi hi nệ th cự hệ th ngố , vì nh ngữ h nạ chế c aủ kỹ thu tậ hi nệ t

iườ thi

iợ , tuy ch aư th tậ gi ngố v iớ “ng

iườ - ng

iạ tế kế ph iả nghĩ đ nế nh ngữ hình th cứ giao ti pế sao cho nên ng i”ườ . Cụ thể, có thể dùng ti nệ l giao di nệ đồ h aọ , d ngạ menu ch nọ , phát âm câu h iỏ , … cũng c nầ ph iả tính đ nế khả năng dùng web như môi tr

ngươ tác.

ngườ t

Baøi giaûng “Trí tueä nhaân taïo” - Slide 144

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Các đ cặ tr ngư cơ b nả c aủ ES.

 Phân tách tri th cứ và đi uề khi nể .

Đã đề c pậ trong hệ lu tậ sinh. Đây cũng là đ cặ đi mể phân bi tệ gi aữ

ch ngươ trình truy nề th ngố và ES.

Hãy so sánh khả năng thay đ iổ tri th cứ c aủ v nấ đề gi aữ hai lo iạ ch ngươ

 Sỡ h uữ tri th cứ chuyên gia.

trình nói trên.

ES có ch aứ tri th cứ c aủ lĩnh v cự trong CSTT. Nhờ có tri th cứ mà nó có cượ nhân ra thành nhi uề b nả , có thể tệ là tri th cứ này có thể đ

cượ tri nể khai.

giá trị. Đ cặ bi c pậ nh tậ trong khi hệ th ngố đã đ  Tính chuyên gia trong lĩnh v cự h pẹ . Cũng gi ngố như chuyên gia con ng iườ , ES đ

iườ thi

cượ đi uề khi nể trong đ ngộ cơ suy di nễ . Ng

Baøi giaûng “Trí tueä nhaân taïo” - Slide 145

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

cượ phát tri nể nh mằ vào m tộ lĩnh v cự h pẹ . Đi uề này cũng dễ hi uể , vì lý do: trong lĩnh v cự h pẹ đó số tế dễ dàng qu nả lý h nơ , ngượ tri th cứ cũng nhỏ h nơ , và giúp cho ng l dể dàng thử nghi mệ chi nế l iườ thi ngườ chia tri th cứ theo t ngừ m ngả như hình sau để qu nả lý nó. tế th

Các đ cặ tr ngư cơ b nả c aủ ES.

Chuaån ñoaùn xe

Heä thoáng ñieän

Heä thoáng nhieân lieäu

Ac-quy

Boä ñaùnh löûa Boä cheá hoaø khí

OÁng daãn

Baøi giaûng “Trí tueä nhaân taïo” - Slide 146

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Các đ cặ tr ngư cơ b nả c aủ ES.

 Suy lu nậ trên ký hi uệ .

Chúng ta có thể dùng ký hi uệ để thể hi nệ tri th cứ cho ES. Chính vì v yậ mà có iả thu tậ iả thu tậ trên ký hi uệ để tri th cứ th cứ , như các gi cượ các gi

ngươ 2 – ph nầ phép toán vị từ.

thể t nậ d ngụ đ đã đề c pậ trong ch  Suy lu nậ có heuristic Chuyên gia con ng iườ có thể từ kinh nghi mệ c aủ mình để d nẫ ra cách gi iả

quy tế v nấ đề hi uệ quả h nơ , ví dụ:

tế cách làm:

cướ các lu tậ khác.

cướ .

Khi chu nẩ đoán xe, họ có thể giả thi - Luôn luôn ki mể tra lu tậ về hệ th ngố đi nệ tr Hay m tộ bác sĩ chuyên khoa có thể giả thi tế : - N uế nghi ngờ bị ung thư, thì ki mể tra dòng họ tr Để có thể hi nệ th cự trong ES, ng

Baøi giaûng “Trí tueä nhaân taïo” - Slide 147

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

tế kế c nầ ph iả có cách đánh giá thứ iườ thi tự uư tiên c aủ các lu tậ , để từ m tộ ngữ c nhả nào đó có thể ch nọ m tộ lu tậ có lý nh tấ để b tắ đ uầ .

Các đ cặ tr ngư cơ b nả c aủ ES.

 Cho phép suy lu nậ không chính xác.

ES có m tộ khả năng r tấ m nhạ đó là: nó có thể làm vi cệ v iớ các v nấ đề đang thi uế ngườ h pợ : m tộ ekip thông tin, hay có nh ngư h nổ t pạ , không rõ ràng. Cũng gi ngố như tr th iờ gian để làm bác sĩ đang ph iả c uứ m tộ b nhệ nhân h pấ h iố , lúc đó họ không còn k pị t tế . Khi thi uế thông tin như v yậ họ đành ti nế hành nh ngữ tấ cả các xét nghi mệ c nầ thi cách có lý nh tấ theo họ. Chúng ta cũng có thể hi nệ th cự ES có tính ch tấ đó b ngằ cách đ aư vào nh ngữ lu tậ t ngươ ngứ v iớ tình hu ngố thi uế thông tin để đ ngộ cơ suy di nễ v nậ d ngụ .  Bị gi

iả quy tế .

iạ ch aư có, ch aư c nầ m tộ chuyên gia con ng

iả quy tế b iở ES. Cụ thể, n uế lĩnh v cự chúng iườ thì vi cệ xây

mu nố xây d ngự ES hi nệ t d ngự ES khó mà thành công.

 Gi

iớ h nạ vào v nấ đề gi Không ph iả m iọ v nấ đề đ uề có thể gi

N uế v nấ đề quá khó, yêu c uầ chuyên gia con ng

iườ đ nế vài giờ, c nầ thi

tế nghĩ

đ nế khả năng chia thành nhi uề bài toán con t

ngươ ngứ m iỗ ES.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 148

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

iả quy tế các v nấ đề có độ ph cứ t pạ v aừ ph iả .

Các đ cặ tr ngư cơ b nả c aủ ES.

 Có khả năng bị l

iườ ES có khả năng bị l

iỗ . Chính vì v yậ , c nầ thi

iạ l

tế đ aư iỗ cho ES – ES có khả năng l uư v tế quá trình suy lu nậ , n uế nó iườ dùng ki mể nghi mệ v iớ th cự tế có sai và báo cho ES, lúc đó nó

vào khả năng ph cụ h iồ l đ aư ra m tộ k tế lu nậ mà ng ph iả có khả năng ghi nh nậ và theo đu iổ m tộ h

ngướ suy lu nậ khác.

đ cặ đi mể này không xu tấ hi nệ trong các ch

ngươ trình truy nề th ngố , nh ngư đ ngừ v iộ tố h nơ . M iỗ lo iạ có nh ngữ đ cặ đi mể riêng như b ngả so sánh

ngươ trình đó t

iỗ . Gi ngố như chuyên gia con ng

iả thu tậ

iả thích.

k tế lu nậ lo iạ ch sau: CT truy nề th ngố Xử lý số Gi Tích h pợ thông tin+ đi uề khi nể Khó thay đ iổ Thông tin chính xác Giao di nệ l nhệ đi uề khi nể K tế quả cu iố cùng T iố uư

ES Xử lý ký hi uệ . Heuristic Tách b chạ thông tin+ đi uề khi nể dễ thay đ iổ . Thông tin không ch cắ ch nắ . H iộ tho iạ + gi iả thích đề nghị + gi Có thể ch pấ nh nậ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 149

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Công nghệ tri th cứ .

Đ nhị

nghĩa l

iạ

1. Đánh giá

Các yêu c uầ

 Quá trình g mồ các giai đo nạ như hình bên. nghĩa:

 M tộ số đ nhị

Các kh oả sát khác

2. Thu th pậ tri th cứ

Tri th cứ

Các tinh ch nhỉ

3. Thi

tế kế

Ki nế trúc

4. Ki mể tra

§ Công nghệ tri th cứ : Là quá trình xây d ngự ES. § Thu th pậ tri th cứ : Là quá trình thu th pậ , tổ ch cứ và nghiên c uứ tri th cứ .

Sự đánh giá

5. L pậ tài li uệ

S nả ph mẩ

6. B oả trì

Baøi giaûng “Trí tueä nhaân taïo” - Slide 150

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Các nhân tố trong m tộ dự án ES

 Các yêu c uầ cho m iỗ nhân tố:

iả quy tế v nấ đề hi uệ quả

 Các nhân tố chính:  Chuyên gia lĩnh v cự .  Kỹ sư tri th cứ  Ng

iườ dùng s nả ph mẩ

tố .

cượ gi

iả quy tế b iở ph nầ

iườ dùng s nả ph mẩ :

tế kế giao di nệ cho ES.

Chuyên gia lĩnh v cự :  Có tri th cứ chuyên gia  Có kỹ năng gi  Có thể chuy nể giao tri th cứ  Không ch ngố đ iố (thân thi nệ ). Kỹ sư tri th cứ :  Có kỹ năng về công nghệ tri th cứ  Có kỹ năng giao ti pế t  Có thể làm cho v nấ đề đ m mề .  Có kỹ năng l pậ trình hệ chuyên gia. Ng  Có thể trợ giúp thi  Có thể trợ giúp vi cệ thu th pậ tri th cứ .  Có thể trợ giúp trong quá trình phát tri nể ES.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 151

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Các kỹ thu tậ suy lu nậ

 Suy lu nậ : là quá trình làm vi cệ v iớ tri th cứ , sự ki nệ , chi nế l

cượ gi

iả

toán để d nẫ ra k tế lu nậ .  B nạ suy lu nậ như thế nào?

Các kỹ thu tậ cơ b nả :

§ § § .

§ § § Suy lu nậ ti nế (forward-chaing) Suy lu nậ lùi (backward-chaining)

§ §

Các hình th cứ cơ b nả : Suy lu nậ di nễ d chị Suy lu nậ quy n pạ . ngươ tự. Suy lu nậ t Suy lu nậ khả sai. Suy lu nậ common-sense.

§ Suy lu nậ đ nơ đi uệ § Suy lu nậ không đ nơ đi uệ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 152

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

§ §

uƯ – nh

cượ đi mể c aủ m iỗ kỹ thu tậ

Suy lu nậ ti nế – forward chaining

 Nh

 uƯ đi mể :

§ § Làm vi cệ t

c aủ t ngừ

cượ đi mể : Không có cách để nh nậ th yấ tính quan tr ngọ sự ki nệ . H iỏ nhi uề câu h iỏ th aừ , vì đôi lúc chỉ c nầ m tộ vài sự ki nệ là cho ra k tế lu nậ .

tố v iớ bài toán có b nả ch tấ : gôm thông tin và sau đó tìm xem có thể suy ra cái gì từ thông tin đó.

§ Có thể d nẫ ra r tấ nhi uề thông tin §

chỉ từ m tộ ít sự ki nệ ban đ uầ .

§ Có thể h iỏ nh ngữ câu h iỏ không liên quan gì nhau – chu iổ câu h iỏ không ăn nh pậ nhau.

Thích h pợ cho m tộ số v nấ đề như: , giám sát, đi uề khi nể , di nễ

ho chạ đ nhị . d chị VD:

Baøi giaûng “Trí tueä nhaân taïo” - Slide 153

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

tệ cao ? - B nạ có thân nhi - B nạ đ nế VN đã lâu r iồ ? - …

uƯ – nh

cượ đi mể c aủ m iỗ kỹ thu tậ

Suy lu nậ lùi – backward chaining

 Nh

 uƯ đi mể :

cượ đi mể : ngướ Luôn h

§ § Làm vi cệ t

tr theo dòng suy lu nậ cướ th mậ chí có thể d ngừ và rẽ

ch tấ : thành l pậ giả thi xem có thể ch ngứ minh đ tố v iớ bài toán có b nả tế , sau đó tìm cượ không.

§ H ngướ đ nế m tộ goal nào, nên h iỏ iả quy tế : dùng meta-rule để

nh ngữ câu h iỏ có liên quan nhau.

§ Chỉ kh oả sát CSTT trên nhánh v nấ

ngướ không gian cượ kh oả sát sang m tộ vùng

đ nhị sang m tộ goal khác.  Gi kh cắ ph cụ . Meta-rule: dùng để h tri th cứ đ khác. T tố cho các v nấ đề: chu nẩ đoán,

Baøi giaûng “Trí tueä nhaân taïo” - Slide 154

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

đề đang quan tâm. § kê toa, gỡ r iố .

Kh oả sát ES: MYCIN

 Gi

 Các đ cặ đi mể chính:

iớ thi uệ : Là ES về lĩnh v cự chu nẩ đoán b nhệ

nhi mễ trùng nháu. § Sử d ngụ kỹ thu tậ suy lu nậ lùi. Có khả năng phân tách tri th cứ và § năm đi uề khi nể .

§ § 1970, t Là th Đ cượ phát tri nể vào kho ngả iạ đ iạ h cọ Standford cướ đo cho nhi uề ES d aự trên

§ Có tích h pợ Meta-rule. Có thể dùng khi thi uế thông tin hay

§ thông tin không chính xác. vi lu tậ sau này. Đ cượ tế trên ngôn ngữ

§ INTERLISP, m tộ nhánh c aủ LISP. Có khả năng nhớ đ

§ Ng iườ ta từ MYCIN, t cượ các thông tin iườ

trong m tộ phiên làm vi cệ v iớ ng b nhệ cụ thể.

§ Dể sử d ngụ – giao ti pế v iớ bác sĩ cướ bỏ ph nầ CSTT c aủ nó để đ cượ m tộ hệ th ngố EMYCIN (empty MYCIN), dùng để phát tri nể các ES khác. qua ti ngế anh.

§ Cung c pấ các ch cứ năng gi iả thích:

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 155

WHY, HOW.

Kh oả sát ES: MYCIN

 M tộ phiên làm vi cệ cụ thể v iớ

? MYCIN cố g ngắ xác đ nhị b nả ch tấ lây

nhi mễ .

cượ Vi

tệ hóa. ? M tộ vài thông tin về b nhệ nhân:

MYCIN (“Expert System”. Author: John Durkin) --- đã đ

5. MYCIN: Có b tấ kỳ phép c yấ vi khu nẩ cho Jack Durkin liên qua đ nế b nhệ hi nệ t iạ ? USER: Có

6. MYCIN: M uẫ v tậ l yấ từ đâu?

USER: CSF

7. MYCIN: Ngày, giờ th cự hi nệ c yấ ?

USER: 7- July-7:00

iớ tính ? ….

Nam

1. MYCIN: Họ tên ? USER: Jack Durkin. 2. MYCIN: Tu iổ ? 24 USER: 3. MYCIN: Gi USER: 4. MYCIN: Ch ngủ t cộ ? USER: CAUCASIAN MYCIN: G nầ đây Jack Durkin có các tri uệ ch ngứ như: choáng ván, hôn mê không? USER: Có.

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 156

….

Kh oả sát ES: XCON

 Gi

iớ thi uệ : Là ES về lĩnh v cự h

ngướ d nẫ c uấ hình các hệ th ngố máy tính c aủ

ngưở .

cướ khi xu tấ x

iạ đ iạ h cọ CMU

Đ cượ phát tri nể vào kho ngả năm 1980, t Đ cượ công bố gi mả th iờ gian c uấ hình cho m iỗ hệ th ngố xu ngố tế ki mệ vào kho ngả 25 tri uệ $

DEC tr § § còn 2 phút (so v iớ 25 phút b ngằ tay.). Ti cho m iỗ năm.

(Theo “Expert System” – John Durkin)

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 157

Hệ chuyên gia d aự trên lu tậ

 Đ nhị

nghĩa: Là m tộ ch ngươ trình máy tính, xử lý các thông tin cụ thể c aủ bài toán đ

cượ cượ ch aứ trong CSTT, sử d ngụ đ ngộ

ch aứ trong bộ nhớ làm vi cệ và t pậ các lu tậ đ cơ suy lu nậ để suy ra thông tin m iớ .

ngươ tr cướ .

ES d aự trên lu tậ : có n nề t ngả xây d ngự lá hệ lu tậ sinh – ch ES d aự trên lu tậ cũng có nh ngữ đ cặ tr ngư cơ b nả như đã nêu trong ph nầ

tr cướ cho các ES t ngổ quát, m tộ vài đ cặ đi mể :

iườ dùng, ng iườ phát tri nể .

Có CSTT ch aứ các lu tậ . Có bộ nhớ làm vi cệ t mạ th iờ . Có đ ngộ cơ suy lu nậ . Có m tộ giao di nệ để giao ti pế v iớ ng Có ti nệ ích gi iả thích. Có khà năng giao ti pế v iớ ch ngươ trình ngoài như: các DBMS, xừ lý b ngả

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 158

§ § § § § § tính,…

Hệ chuyên gia d aự trên lu tậ

 Ki nế trúc: (như hình sau)  Nguyên lý ho tạ đ ngộ t

Boä nhôù laøm vieäc

Ngöôøi duøng

Ñoäng cô suy luaän

Giao dieän ngöôøi duøng

Boä giao tieáp chöông trình ngoaøi

Cô sôõ tri thöùc

Ngöôøi phaùt trieån

Boä giaûi thích

Giao dieän Ngöôøi phaùt trieån

Baøi giaûng “Trí tueä nhaân taïo” - Slide 159

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ngươ tự hệ lu tậ sinh đã gi iớ thi uệ .

Hệ chuyên gia d aự trên lu tậ

 Nh

 uƯ đi mể

cượ đi mể Các fact mu nố đ ngồ

§ § Bi uể di nễ tri th cứ tự nhiên: IF…

THEN.

§ nh tấ nhau, ph iả kh pớ nhau hoàn toàn  Các facts cùng m tộ ý nghĩa ph iả gi ngố nhau về cú pháp, ngôn ngữ tự nhiên không như v yậ . Phân tách tri th cứ – đi uề khi nể . Tri th cứ là t pậ các lu tậ có tính đ cộ

§ l pậ cao -> dễ thay đ iổ , ch nhỉ s aữ .

§ cượ tri th cứ heuristic. §

§ Dễ mở r ngộ . T nậ d ngụ đ Có thể dùng bi nế trong lu tậ , tri §

xu tấ ch ngươ trình ngoài.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 160

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

khó tìm m iố qua hệ gi aữ các lu tậ trong m tộ chu iổ suy lu nậ , vì chúng có thể n mằ r iả rác trong CSTT. Có thể ho tạ đ ngộ ch mậ . Làm cho nhà phát tri nể ph iả hình chung m iọ cái ở d ngạ lu tậ - không ph iả bài toán nào cũng có thể làm cượ như thế này. đ

ngươ 7:

ngươCh Ch

7: BI UỂBI UỂ DI NỄDI NỄ TRITRI TH CỨTH CỨ

Bi uể di nể tri th cứ trong AI: vai trò và ngứ d ngụ Các kỹ thu tậ bi uể di nể tri th cứ :

ư ồ ụ

ệ

Semantic network L u đ ph thu c khái ni m ộ Frame Script

ThS Nguy n Cao Trí – caotri@dit.hcmut.edu.vn

ễ

KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn

Ñ aïi H oïc B aùch K hoa Tp.H C M B aûn quyeàn (cid:211) K h oa C oân g N g h eä Th oân g Tin

Th aù n g 6/2001

Các l

cượ đồ bi uể di nễ tri th cứ .

 Đ nhị

ngươ pháp để mã hoá tri th cứ , nh mằ thành l pậ cơ sỡ tri th cứ

cho các hệ th ngố d aự trên tri th cứ (knowledge-based system).

B ngằ cách nào ?

Tri th cứ tính toán

Tri th cứ th cự C aủ lĩnh v cự

cượ

ngượ và các

ngượ th cự  đ iố

nghĩa: Bi uể di nễ tri th cứ là ph

G mồ : đ iố t quan hệ gi aữ chúng trong lĩnh v cự .

G mồ : B ngả ánh xạ gi aữ : Đ iố t t ngượ tính toán. Quan hệ th cự  quan hệ tính toán.

B ngằ cách: dùng các l đồ bi uể di nễ (scheme).  Ch nọ dùng l cượ đồ cho lo iạ tri th cứ là v nấ đề quan tr ngọ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 162

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Các l

cượ đồ bi uể di nễ tri th cứ .

cượ đồ bi uể di nễ :

 Chú ý:

 Các lo iạ l L

cượ đồ logic. tệ : L C nầ phân bi

ngườ

ngươ

Dùng các bi uể th cứ trong logic hình th cứ ,như phép toán vị từ, để bi uể di nễ tri th cứ .

lo iạ l sát trong ch

Ngôn ngữ l pậ trình hi nệ th cự t

Các lu tậ suy di nễ áp d ngụ cho cượ đồ này r tấ rõ ràng, đã kh oả ngươ 2 (như: MP, MT,…). tố cượ đồ này là:

nh tấ cho lo iạ l PROLOG. § L cượ đồ thủ t cụ : cượ đồ bi uể di nễ (scheme) và môi tr hi nệ th cự (medium), t tự như vi cệ tệ : c uấ trúc dữ li uệ (CTDL) và phân bi ngôn ngữ l pậ trình. V iớ m tộ lo iạ CTDL, ví dụ như: B nả ghi (record), chúng ta có hi nệ th cự trong nhi uề ngươ tự, ngôn ngữ như: Pascal, C,…T v iớ m tộ lo iạ l cượ đồ nào đó chúng ta có thể ch nọ m tộ trong các NNLT để hi nệ th cự nó.

Bi uể di nễ tri th cứ như t pậ các

Baøi giaûng “Trí tueä nhaân taïo” - Slide 163

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

chỉ thị l nhệ để gi iả quy tế v nấ đề.

Các l

cượ đồ bi uể di nễ tri th cứ .

§ L cượ đồ thủ t cụ : Các ví dụ về lo iạ l

Ng cượ l

cượ đồ d ngạ iạ v iớ các l khai báo, như logic và m ngạ , các chỉ cượ đồ thủ t cụ chỉ ra thị l nhệ trong l iả quy tế v nấ đề. b ngằ cách nào gi cượ đồ này g mồ : m ngạ ngữ nghĩa, phụ thu cộ khái ni mệ , đồ thị khái ni mệ  đ cượ kh oả sát sau đây c aủ ch ngươ này. § L cượ đồ c uấ trúc:

c aủ l Là m tộ mở r ngộ Các lu tậ trong CSTT c aủ ES d aự iả

trên lu tậ là ví dụ về thủ t cụ gi quy tế v nấ đề.

Hệ lu tậ sinh là ví dụ đi nể hình

cượ đồ này.

c aủ lo iạ l § L cượ đồ m ngạ .

b nả (script) , khung (frame), như là các đ iố t ngượ

cượ đồ m ngạ ; b ngằ cách cho phép các node có thể là m tộ CTDL ph cứ t pạ g mồ các khe(slot) có tên và trị hay m tộ thủ t cụ . Chính vì v yậ nó tích h pợ cả d ngạ khai báo và thủ t cụ . K chị ngượ (object) là ví dụ c aủ l cượ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 164

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Bi uể di nễ tri th cứ như là đồ thị; các đ nhỉ ho cặ khái ni mệ , các cung như là quan hệ gi aữ chúng. đ iố t đồ này  kh oả sát sau.

Các chú ý về l

cượ đồ.

 Khi xây d ngự các l

cượ đồ c nầ

chú ý nh ngữ v nấ đề sau:

§ cượ meta-

§ § Các đ iố t

B ngằ cách nào thể hi nệ đ knowledge? B ngằ cách nào thể hi nệ tính phân c pấ c aủ tri th cứ . Lúc bi uể di nễ tính phân c pấ thì các hình th cứ : kế th aừ , ngo iạ lệ, trị m cặ , ngo iạ lệ, đa th aừ kế ph iả đ cặ tả đ nhị như thế nào § Khi mô tả đ iố t

ngượ và các quan hệ có thể bi uể di nễ cho cái gì trong lĩnh v cự ? Ví dụ: để bi uể di nễ cho ý “Nam cao 70”,chúng ta có thể dùng: 1mét chieucao(nam,170). V yậ thì để di nễ tả “An cao h nơ Nam” chúng ta làm như thế nào, vì chi uề cao c aủ An lúc này không là m tộ trị cụ thể n aữ !

§ B ngằ cách nào phân bi

ngượ , b ngằ cách nào có thể tích h pợ m tộ tri th cứ thủ t cụ vào b nả thân mô tả, khi nào thủ t cụ cượ th cự hi nệ ,.. đ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 165

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

tệ gi aữ “n iộ hàm” và “ngo iạ di n”ệ c aủ m tộ khái ni mệ .

M ngạ ngữ nghĩa

 Đ nhị

Là m tộ l

cượ đồ bi uể di nễ ki uể m ngạ , dùng đồ thị để bi uể di nễ tri th cứ . Các đ nhỉ

bi uể

di nễ đ iố t

ngượ ; các cung bi uể di nễ quan hệ gi aữ chúng.

 Ví dụ:

ngượ ,

bi uể di nễ đ iố t

Caùnh

còn l

thu cộ

nghĩa:

coù

IS-A

Chim

Chim yeán

có nhãn “Chim y n”ế n iố v iớ đ nhỉ

Di chuyeån

tệ “IS-A” nói

Bay

ngườ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 166

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Xem m ngạ bên: - Có hai đ nhỉ iạ bi uể di nễ thu cộ tính. và hai đ nhỉ - đ nhỉ có nhãn: “Chim” n iố v iớ hai đ nhỉ tính có nhãn: “Cánh”, “Bay” nên có thể bi uể di nễ : “M tộ con chim thì có cánh và có hình th cứ di chuy nể là bay”. -Đ nhỉ “Chim” thông qua cung đ cặ bi lên: “Chim y nế là m tộ loài chim”.Vì v yậ chim y nế có thể sỡ h uữ các thu cộ tính: có cánh, bay như m tộ con chim thông th

M ngạ ngữ nghĩa

 Mở r ngộ m ngạ ngữ nghĩa:

Caùnh

Khoâng khí

Để mở r ngộ m ngạ th tậ đ nơ gi nả ; và các cung có s nẵ . Các đ nhỉ cượ thêm vào m ngạ ho cặ là bi uể di nễ ngượ ho cặ là bi uể di nễ thu cộ tính cướ . Xét ví dụ sau đây minh

chúng ta chỉ vi cệ thêm các đ nhỉ quan hệ v iớ các đ nhỉ đ đ iố t như ví dụ tr h aọ vi cệ mở r ngộ m ngạ đã có.

co ù

thô û

IS-A

 Tính th aừ kế:

Lilo

Chim

Ñoäng vaät

Chim yeán

Di chuyeån

IS-A

Bay

Caùnh cuït

cượ đồ Là đ cặ đi mể n iổ b tậ c aủ l ra m ngạ ngữ nghĩa. M ngạ ngữ nghĩa đ nhị tệ “IS-A” để chỉ ra sự cung quan hệ đ cặ bi th aừ kế. Ví dụ, nhờ tính th aừ kế mà từ m ngạ bên chúng ta có thể suy ra: “Lilo là m tộ đ ngộ v tậ có thể bay và hít thở không khí.”

Di chuyeån

 Tính ngo iạ lệ:

Đ nhị

nghĩa m tộ cung quan hệ m iớ

đ nế m tộ đ nhỉ

có trị khác.

Ñi

Baøi giaûng “Trí tueä nhaân taïo” - Slide 167

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

M ngạ ngữ nghĩa

 Phép toán trên m ngạ ngữ nghĩa:

Giả sử chúng ta đã mã hoá m ngạ ở hình tr

nào đó. Ví dụ, v iớ đ nhỉ

cướ vào máy tính. Để dùng m ngạ , có thể “Chim” chúng ta đ tặ câu iờ

iờ câu hòi chúng ta có thể hi nệ th cự cách trả l

đ nơ gi nả là chúng ta câu h iỏ v iớ m tộ đ nhỉ h iỏ : “B nạ di chuy nể như thế nào?”. Để trả l sau cho đ nhỉ

: tìm ki mế cung quan hệ có nhãn “di chuy n”ể b tắ đ uầ từ nó, như case 1,2 ở bên.

Chim

Di chuyeån

Bay

Chim

Ngöôøi duøng

Q: Baïn di chuyeån nhö theá naøo ?

Case 1:

A: bay

Q: B nạ di chuy nể như thế nào ?

A: bay

Di chuy nể

Lilo

iườ dùng

Case 2:

Q: B nạ di chuy nể như thế nào ?

Chim y nế

Q: B nạ di chuy nể như thế nào ?

Bay

A: bay

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 168

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

 Trong quá trình nghiên c uứ về cách hi uể ngôn ngữ tự nhiên, Schank và Rieger đã cố tế l pậ m tộ t pậ các ph nầ tử cơ b nả để có thể bi uể di nễ c uấ trúc ngữ nghĩa

g ngắ thi c aủ các bi uể th cứ ở ngôn ngữ tự nhiên theo m tộ cách đ ngồ nh tấ .

Lý thuy tế về phụ thu cộ khái ni mệ có đề ra 4 khái ni mệ cơ b nả để từ đó ngữ

nghĩa đ

§ cượ xây d ngự , chúng là: ACT (Action)

§ PP (Picture Producers) : các đ iố t

§ AA (Action Adder)

§ PA (Picture Adder) ngượ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 169

: các hành đ ngộ . : (các đ ngộ từ trong câu) ngượ . : (các chủ từ, tân ngữ,..) : bổ nghĩa cho hành đ ngộ . : (tr ngạ từ) : bổ nghĩa cho đ iố t : (tính từ)

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

 T tấ cả các hành đ ngộ đ

cượ mô tả b ngằ cách phân rã về m tộ

ho cặ nhi uề hành đ ngộ như li cượ cho là có thể đ tệ kê sau đây:

ngượ – VD: đ yẩ , ch iả ,…

ngượ – VD: đá..

ngượ khác. – VD: c mầ , n mắ , giữ,…

ngượ b iở đt khác – VD: ăn, nu tố ,..

: di chuy nể m tộ ph nầ thân thể b iờ đ iố t : n mắ l yấ đ iố t : ăn vào b ngụ m tộ đ iố t : t ngố ra từ thân thể c aủ m tộ đ iố t ngượ – VD: khóc,..

tế lộ,..

, …

: nghĩ về m tộ ý ki nế – VD: suy nghĩ, hình dung,…

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 170

1. ATRANS : chuy nể đ iổ m tộ quan hệ – VD: đ ngộ từ: cho, bi uế ,… 2. PTRANS : chuy nể đ iổ vị trí v tậ lý – VD: đi, ch yạ , di chuy nể ,.. 3. PROPEL : tác đ ngộ m tộ l cự v tậ lý lên đ iố t 4. MOVE 5. GRASP 6. INGEST 7. EXPEL 8. MTRANS : chuy nể đ iổ thông tin tinh th nầ – VD: nói, ti 9. MBUILD : t oạ ra m tộ thông tin tinh th nầ m iớ – VD: quy tế đ nhị 10. CONC 11. SPEAK : t oạ ra âm thanh – VD: nói, phát bi uể ,… 12. ATTEND: t pậ trng giác quan – VD: l ngắ nghe, nhìn,…

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

ngượ PP

ACT Đ iố t

PP

th cự hi nệ hành đ ngộ ACT

ngượ PP có thu cộ tính PA

PA Đ iố t

PP

O

Hành đ ngộ ACT tác đ ngộ lên PP

PP

ACT

PP

ngượ nh nậ và cho

R

ACT

Đ iố t trong hành đ ngộ ACT R: đ iố t

ngượ nh nậ (recipient)

 Quan hệ phụ thu cộ khái ni mệ bao g mồ m tộ t pậ các lu tậ cú pháp cho khái ni mệ , hình thành nên văn ph mạ về quan hệ ngữ nghĩa. Các quan hệ cượ dùng vào vi cệ này sẽ đ bi uể di nễ bên trong cho câu trong ngôn ngữ tự nhiên. Danh sách các phụ thu cộ khái ni mệ đ

tệ kê như bên.

cượ li

PP PP

ngượ

D

ACT

PP

H ngướ c aủ đ iố t trong hành đ ngộ ACT D: H ngướ (Direction)

I

ACT

tế bị ph cụ vụ cho hành đ ngộ .

Quan hệ gi aữ hành đ ngộ và thi (xem ví dụ ph nầ sau)

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 171

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

X

Bi uể di nễ quan hệ nhân quả. X: nguyên nhân. Y: k tế quả.

Y

PA1

PP

Bi uể di nễ sự chuy nể đ iổ tr ngạ thái c aủ PP từ PA2 sang PA1

PA2

PP1

PP2 Bi uể di nễ quan hệ sỡ h uữ .

PP2 là PART OF ho cặ POSSESSOR OF PP1

§ Từ các phụ thu cộ khái ni mệ cơ b nả nêu trên. Chúng ta có thể k tế

h pợ để có thể bi uể di nễ các câu trong NNTN, như ví dụ sau:

Nam PROPEL

Ý nghĩa: “Nam đã tác d ngụ m tộ l cự vào quả bóng“

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 172

Quả bóng

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

p : quá khứ – ACT đã x yả ra trong quá khứ VD:

Ý nghĩa: Nam đã tác d ngụ m tộ l cự (đ yẩ ) vào

 Các phụ thu cộ khái ni mệ trên cho phép chúng bi uể di nễ quan hệ gi aữ : chủ từ v iớ đ ngộ từ (như phụ thu cộ đ uầ tiên), hay gi aữ chủ từ và thu cộ cượ đồ về quan hệ tính c aủ nó,…. L phụ thu cộ khái ni mệ càng đ aư ra cách th aứ để bi uể di nễ thì, đi uề ki nệ ,…, như bên ph iả .

cái bàn. f : t ngươ lai. t : chuy nể ti pế . ts : b tắ đ uầ chuy nể ti pế . tf : k tế thúc chuy nể ti pế . k : đang di nễ ra. ? : nghi v nấ . / : phủ đ nhị . C : đi uề ki nệ . Nil: hi nệ t

iạ . (không ghi chú gì)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 173

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

p O Cái bàn Nam PROPEL

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

 M tộ số ví dụ về vi cệ k tế h pợ các phụ thu cộ khái ni mệ để bi uể di nễ câu:

VD:

: Nam đã đánh Lan

Nam

PROPEL

Lan

ACT

Bài gi ngả

Nam

ATTEND

: Nam đang t pậ trung vào bài gi ngả .

Height (> average)

: Nam is tall.

PA

Nam

PP

: Nam is a doctor.

Nam

doctor

PP

PA

: A nice boy

boy

nice

Poss-by

PP

dog

John

: John’s dog.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 174

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

: John pushed the car.

John

PROPEL

Car

ACT

PP

John

R

ACT

John

ATRANS

: John took the book from Mary.

PP

Mary

O Book

John

I

John

I

INGEST

ACT

: John ate ice cream (by spoon)

Ice cream

O spoon

field

PP

D

John

D

: John fertilized the field

ACT

bag

PP

PTRANS O fertilizer

Baøi giaûng “Trí tueä nhaân taïo” - Slide 175

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

PA1

Size >X

: The plants grew

Plants

PP

Size =X

PA2

(b)

(a)

Bob

O

R

Bullet

Bill

PROPEL

gun

Health (-10)

Bob

p

Health (10)

: Bill shot Bob

yesterday

: John ran yesterday

John

PTRANS

p

Baøi giaûng “Trí tueä nhaân taïo” - Slide 176

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

§ Từ nh ngữ k tế h pợ gi aữ các H1: p O Lan ATRANS Cu nố t pậ AI

Quang

R

Lan phụ thu cộ khái ni mệ để bi uể di nễ các câu đ nơ gi nả ở trên, chúng ta có thể cũng có thể t oạ ra bi uể di nễ cho các câu ph cứ t pạ h nơ như ví dụ sau: Câu: “Nam đã c mấ Lan g iở cu nố t pậ AI cho Quang”

H2:

*DO* N uế đ tặ C là m nhệ đề: “Lan g iở cu nố t pậ cho Quang”, thì câu trên có thể hi uể là: Nam c mấ cái m nhệ đề v aừ nêu x yả ra. Nam

Mà m nhệ đề C đ cượ bi uể di nễ

như H1, nên toàn bộ câu là như H2:

O *ATRANS* Lan Cu nố t pậ AI

c/ p

Quang

R

Baøi giaûng “Trí tueä nhaân taïo” - Slide 177

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Lan

L uư đồ về quan hệ phụ thu cộ khái ni mệ .

 uƯ đi mể

 Nh

§ §

cượ đi mể : Khó khăn trong vi cệ phát tri nể thu gi mả ch ngươ bi uể di nễ c aủ câu b tấ kỳ về d ngạ quy t cắ chu nẩ .

trình để tự đ ngộ

Cung c pấ cách th cứ bi uể di nễ hình th cứ cho ngữ nghĩa c aủ ngôn ngữ tự nhiên, ngữ nghĩa đ cượ bi uể di nễ theo có quy t cắ  gi mả sự nh pậ d ngạ nh ngằ .

§ Trả giá cho vi cệ phân rã m iọ cái về § Chính b nả thân d ngạ

các thành ph nầ cơ b nả : ACT, PP, …

bi uể di nễ ngữ nghĩa  tính đ ngồ ngươ ngứ là sự đ ngồ nh tấ về cượ đồ bi uể di nễ  nghĩa  so minh tính đ ngồ

Baøi giaûng “Trí tueä nhaân taïo” - Slide 178

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ch aứ đ ngự nghĩa t cú pháp c aủ l ch ngứ trùng hai đồ thị bi uể di nễ . Các thành ph nầ cơ b nả không thích h pợ để miêu tả nh ngữ khái ni mệ tinh tế c aủ ngôn ngữ tự nhiên, như các từ có nghĩa đ nhị tính: cao, đ pẹ ,…

Đồ thị khái ni mệ

 Đ nhị

nghĩa: Đồ thị khái ni mệ là m tộ đồ thị h uữ h nạ , liên thông, các đ nhỉ

đ cượ chia làm hai

quan hệ.

khái ni mệ và đ nhỉ khái ni mệ : dùng để bi uể di nễ các khái ni mệ cụ thể (cái, đi nệ tho iạ , …) cượ bi uể di nễ b iở hình ngượ (tình yêu, đ pẹ , văn hoá,…). Đ nhỉ khái ni mệ đ

lo iạ : đ nhỉ Đ nhỉ hay tr uừ t chữ nh tậ có gán nhãn là khái ni mệ .

quan hệ: dùng để chỉ ra quan hệ gi aữ các khái ni mệ có n iố đ nế nó.

Đ nhỉ Trong đồ thị khái ni mệ : chỉ có khác lo iạ m iớ n iố đ cượ v iớ nhau. Chính vì

dùng đ nhỉ quan hệ nên các cung không c nầ ph iả đ cượ gán nhãn n aữ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 179

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

§ M iỗ đồ thị khái ni mệ bi uể di nễ m tộ m nhệ đề đ nơ . Cơ sỡ tri th cứ : ch aứ nhi uề đồ thị khái ni mệ .

Đồ thị khái ni mệ

 M tộ số ví dụ:

tế Con chim

Bi uể di nễ : “Con chim bi bay”

bay m tộ ngôi

Con chó nâu Bi uể di nễ : ”con chó có màu nâu”. màu hai ngôi

Ng iườ :hoàng

Ng iườ :nam bố mẹ

Bi uể di nễ : ”Nam có bố mẹ là ông Hoàng và bà Nga”. Ng iườ :nga ba ngôi

Baøi giaûng “Trí tueä nhaân taïo” - Slide 180

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

quan hệ có thể là m tộ hay nhi uề ngôi. * M tộ đ nhỉ

Đồ thị khái ni mệ

 M tộ số ví dụ:

agent object person: mary give

person: john book recipient

Represent: “Mary give John the book”

quan hệ

iườ nh nậ thông quan đ nhỉ quan hệ “object”, tân ngữ gián ti pế ngướ mũi tên cho quan hệ “recipient”, h

Baøi giaûng “Trí tueä nhaân taïo” - Slide 181

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Trong ví dụ trên, chú ý: đ ngộ từ “give” có chủ từ thông qua đ nhỉ “agent”, tân ngữ tr cự ti pế thông qua đ nhỉ cũng là ng các lo iạ đ ngộ từ t ngươ tự có d ngạ như đồ thị trên.

Đồ thị khái ni mệ

 Lo iạ , cá thể, tên:

Trong đồ thị khái ni mệ , m iỗ đ nhỉ

quan hệ bi uể di nễ cho m tộ cá thể đ nơ lẽ thu cộ m tộ cượ quy đ nhị

khái ni mệ đ

lo iạ nào đó. Để nói lên quan hệ gi aữ “lo iạ -cá th ”ể , nên m iỗ đ nhỉ cách gán nhãn là:

“lo iạ : tên_cá_th ”ể

tên_ cá_thể có thể là: 1. M tộ tên nào đó, như:

sinhviên: nam

 m tộ sinh viên có tên là Nam.

2. M tộ khoá để phân bi

tệ , đ

cượ vi

sinhviên: #59701234

tế theo cú pháp #khoá, như  m tộ sinh viên có khoá là: 59701234.

3. Có thể dùng d uấ sao (*) để chỉ ra m tộ cá thể ch aư xác đ nhị

, như:

cượ l yấ qua bi nế X.

sinhviên: * , có tác d ngụ như sinhviên  chỉ ra m tộ sinh viên b tấ kỳ sinhviên:*X  sinh viên b tấ kỳ, tên sinh viên đã đ sinhviên:ng*  sinh viên có tên b tắ đ uầ b iở “ng”

ngườ h pợ 1 và 2, khái ni mệ đ

cượ g iọ là khái ni mệ cá thể, tr

ngườ h pợ 3 ta có khái ni mệ

Tr t ngổ quát.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 182

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Đồ thị khái ni mệ

 N uế dùng cách đ tặ tên như nói trên có thể nhín th yấ 3 đồ thị sau có tác d ngụ bi uể di nễ như

nhau n uế con có luu có khoá là #123.

G1:

color

dog:lulu

color:brown

G2:

color

dog:#123

color:brown

G3:

color

dog:#123

color:brown

name

string:”lulu”

Baøi giaûng “Trí tueä nhaân taïo” - Slide 183

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Đồ thị khái ni mệ

 Bi nế có thể đ

cượ dùng khi c nầ chỉ ra nhi uề đ nhỉ khái ni mệ đ ngồ nh tấ nhau trong

object

dog:*X

agent

verb:scratch

part: ear

part

instrument

part: paw

dog:*X

part

Represent: “The dog scratches its ear with its paw”

Baøi giaûng “Trí tueä nhaân taïo” - Slide 184

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

m tộ đồ thị như tr ngườ h pợ sau.

Đồ thị khái ni mệ

 Phân c pấ lo iạ (type)

N uế có s và t là hai lo iạ (type) thì: s £

t :  s: subtype c aủ t

 t : supertype c aủ s

iườ .

iườ là super type c aủ sinhviên.

Ví dụ: - sinhviên là subtype c aủ ng - ng  nên vi

ng

cượ g iọ là common-subtype c aủ r và

cượ g iọ là common-supertype c aủ s

- ^

tế : sinhviên £ iườ Trong sơ đồ phân c pấ bên, s: đ v. v : đ và u. T : supertype c aủ m iọ type : subtype c aủ m iọ type

Baøi giaûng “Trí tueä nhaân taïo” - Slide 185

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Đồ thị khái ni mệ

§ Phép copy (nhân b nả ): nhân b nả m tộ đồ

 Các phép toán trên đồ thị khái ni mệ .

thị.

Xét hai đồ thị sau:

§ Phép Restriction (gi

khái ni mệ b iờ m tộ đ nhỉ

G1:

iớ h nạ ): t oạ ra đồ thị m iớ b ngằ cách: từ m tộ đồ thị đã có, thay thế m tộ đ nhỉ khác cụ thể h nơ , như hai tr

ngườ h pợ :

agent

eat

bone

object

 M tộ bi nế *, đ

cượ thay thế b iở m tộ khoá,

hay m tộ tên c aủ cá thể. VD: dog:*  dog:#123 hay dog:luu

brown

dog: luu

color

 M tộ type đ

cượ thay thế b iở subtype c aủ

nó. VD: ng

iườ : nam  sinhviên:nam

location

porch

G2: animal: luu

brown

color

Baøi giaûng “Trí tueä nhaân taïo” - Slide 186

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Đồ thị khái ni mệ

Aùp d ngụ phép restriction trên đồ thị G2, có thể d nẫ ra G3 như sau:

G3:

location

porch

dog: luu

brown

color

cượ m tộ đồ thị khác.

Phép Join (n iố ): N iố hai đồ thị để đ

khái ni mệ C xu tấ hi nệ trên cả hai đồ thị X và Y, thì chúng ta có thể n iố hai đồ thị trên đ nhỉ

chung là: dog:lulu)

N uế có đ nhỉ chung C nói trên, như từ G1 và G3 có thể t oạ ra G4 như sau: (n iố trên đ nhỉ

G4:

agent

eat

bone

object

brown

dog: luu

color

brown

color

location

porch

Baøi giaûng “Trí tueä nhaân taïo” - Slide 187

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Đồ thị khái ni mệ

G5:

agent

eat

bone

object

brown

dog: luu

color

location

porch

Phép simplify: (rút g nọ ) N uế trên m tộ đồ thị có hai đồ thị con gi ngố nhau hoàn toàn thì chúng ta có thể bỏ đi m tộ để t oạ ra m tộ đồ thị m iớ có khà năng bi uể di nễ không thay đ iổ . Từ G4 có thể sinh ra G5 cùng khả năng bi uể di nễ .

Baøi giaûng “Trí tueä nhaân taïo” - Slide 188

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Nh nậ xét: Phép Restriction và phép Join cho phép chúng ta th cự hi nệ tính th aừ kế trên đồ thị khái ni mệ . Khi thay m tộ bi nế * b iở m tộ cá thể cụ thể, lúc đó chúng ta cho phép cá thể th aừ kế các tính ch tấ từ lo iạ (type) c aủ nó, cũng t ngươ tự khi ta thay thế m tộ type b iở subtype c aủ nó.

Đồ thị khái ni mệ

 Đ nhỉ

cượ khái ni mệ , lúc đó chúng ta g iọ là

mở r ngộ để có thể ch aứ cả m tộ m nhệ đề trong m tộ đ nhỉ đ nhỉ

m nhệ đề là m tộ đ nhỉ

khái ni mệ có ch aứ m tộ đồ thị khái ni mệ khác. Xét đồ

m nhệ đề. V yậ đ nhỉ

m nhệ đề: Để thu nậ ti nệ bi uể di nễ cho các câu g mồ nhi uề m nhệ đề, đồ thị khái ni mệ đã đ

thị khái ni mệ mở r ngộ bi uể di nễ cho câu: “Tom believes that Jane likes pizza”.

experiencer

believe

object

person: tom

proposition

agent

person: jane

pizza

object

Baøi giaûng “Trí tueä nhaân taïo” - Slide 189

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Đồ thị khái ni mệ

 Đồ thị khái ni mệ và logic.

cượ

- Phép h iộ (and) c aủ nhi uề khái ni mệ , m nhệ đề chúng ta có thể th cự hi nệ dễ dàng cách cách n iố nhi uề đồ thị b iở phép toán join. - Phép phủ đ nhị thể hi nệ b ngằ cách đ aư vào đ nhỉ

(not) và phép tuy nể (or) gi aữ các khái ni mệ hay m nhệ đề cũng có thể đ ), or(tuy nể ) như d ngạ sau.

quan hệ có tên: neg(phủ đ nhị

neg

Baøi giaûng “Trí tueä nhaân taïo” - Slide 190

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Đ nhỉ khái ni mệ , m nhệ đề Đ nhỉ khái ni mệ , m nhệ đề

Đồ thị khái ni mệ

Câu: “There are no pink dogs”, đ

cượ bi uể di nễ :

Ví dụ:

proposition

neg

Trong đồ thị khái ni mệ , các khái ni mệ t ngổ quát (đ nhỉ cượ xem như có l

ngượ từ t nồ t

dùng bi nế * - như dog:*, hay chỉ iạ ($ ). Do v yậ , m nhệ đề trong ví dụ

có tên lo iạ - như dog) đ trên có bi uể di nễ vị từ là:

$ X$ Y(dog(X) ^ color(X,Y) ^ pink(Y)).

pink dog:* color

Và toàn bộ đồ thị ( bao g mồ đ nhỉ

quan hệ :neg), có bi uể di nễ

vị từ:

$ X$ Y(dog(X) ^ color(X,Y) ^ pink(Y)). (dog(X) ^ color(X,Y) ^ pink(Y))).

" X" Y((cid:216)

Baøi giaûng “Trí tueä nhaân taïo” - Slide 191

(cid:216)

= Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Đồ thị khái ni mệ

5. H iộ c aủ t

 Gi

cướ 3 và 4. T tấ cả cượ đ uề đính kèm

iả thu tậ để chuy nể m tộ đồ thị khái

tấ cả các câu trong b các bi nế trong bi uể th cứ thu đ iạ . ngượ từ t nồ t l

1. Gán m tộ bi nế riêng bi

tệ (X1, X2,…) cho

m iỗ khái ni mệ t ngổ quát.

Ví dụ: có đồ thị như sau

dog:lulu

color

brown

Đ cượ chuy nể sang là: $ X1(dog(luu) ^ color(X1) ^ brown(X1))

quan hệ b iờ m tộ vị quan hệ, cượ gán

2. Gán m tộ h ngằ cho m iỗ khái ni mệ cá thể trong đồ thị. H ngằ này có thể là tên cá thể hay khoá c aủ nó. Bi uể di nễ m tộ đ nhỉ khái ni mệ b iở m tộ vị từ m tộ ngôi; có tên là tên lo iạ (type), đ iố số là bi nế hay h ngằ v aừ gán trên. Bi uể di nễ m iỗ đ nhỉ từ n ngôi; có tên là tên c aủ đ nhỉ các thông số là bi nế hay h ngằ đ cho các đ nhỉ

khái ni mệ n iố đ nế nó.

Baøi giaûng “Trí tueä nhaân taïo” - Slide 192

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

ni mệ sang bi uể di nễ vị từ:

L

cượ đồ có c uấ trúc - Frame

 Frame – khung.

Object1

Frame name:

Là m tộ c uấ trúc dữ li uệ cho phép bi uể di nễ tri th cứ ở d ngạ khái ni mệ hay đ iố t ngượ .

Object2

Class:

M tộ khung có c uấ trúc như hình

vẽ bên.

Property 1

Value1

Properties:

 C uấ trúc c aủ frame:

Property 2

Value2

Đ cặ tả cho m tộ frame g mồ các

…

thành ph nầ cơ b nả sau: 1. Frame name: tên c aủ frame. - N uế frame bi uể di nễ cho m tộ cá thể nào đó, thì đây là tên c aủ cá thể. Ví dụ: an, nam, lulu,..

…

Ñ aïi H oïc Baùch Khoa Tp.H CM – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 193

L

cượ đồ có c uấ trúc – Frame

 C uấ trúc c aủ frame (tt):

Khi 3. Các thu cộ tính (property): bi uể di nễ m tộ frame chúng ta có thể thi tế l pậ m tộ hay nhi uề thu cộ tính cho nó, như ví dụ sau:

chim

Frame name:

Properties:

m aøu

C höa bieát

aên

C oân truøng

- N uế Frame bi uể di nễ cho m tộ l pớ , thì đây là tên l pớ . Ví dụ: chim, đ ngộ v tậ , … 2. Class: Tên lo iạ . - N uế thành ph nầ này xu tấ hi nệ , nó tế r ngằ frame mà chúng ta đang cho bi bi uể di nễ có lo iạ là giá trị tr ngườ class.  Cho phép thành l pậ quan hệ th aừ kế IS-A.

Soá caùnh

2 bay

true

Như ví dụ trên, chúng ta có: Object1 IS-A Object2

ñoùi

C höa bieât

H oaït ñoäng

C höa bieât

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 194

L

cượ đồ có c uấ trúc – Frame

 C uấ trúc c aủ frame (tt):

tế đ

tấ cả các đ iố t

Các thu cộ tính c aủ frame n mằ ở hai d ngạ cơ b nả :  D ngạ tĩnh(static): giá trị c aủ nó không thay đ iổ trong quá trình hệ th ngố tri th cứ ho tạ đ ngộ .  D ngạ đ ngộ (dynamic): giá trị có thể chuy nể đ iổ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 195

- Khi chúng ta đ tặ tả thu cộ tính cho cượ giá m tộ l pớ ; n uế chúng ta bi trị chung cho t ngượ thu cộ l pớ mà chúng ta đang bi uể di nễ thì đi nề vào trị cho thu cộ tính đó, giá trị đó chúng ta g iọ là giá trị m cặ nhiên, như: ăn, số cánh ở trên ; n uế tế trị cụ thể (nh ngư chúng ta ch aư bi tế là có thu cộ tính đó) thì chúng ta có bi tế ) – như màu, thể bỏ tr ngố (ch aư bi ho tạ đ ngộ ,..:. Khi ph iả tìm ki mế m tộ frame, chúng ta có thể d aự vào frame name , cũng có thể d aự vào các thu cộ tính cượ đ tặ tả cho frame. đ

L

cượ đồ có c uấ trúc – Frame

cượ đính kèm v iớ

 C uấ trúc c aủ frame (tt):

Hai thủ t cụ phổ bi nế đ m tộ thu cộ tính là: IF_NEEDED và IF_CHANGED.  IF_NEEDED:

Thủ t cụ này đ

cượ th cự thi m iỗ khi chúng ta c nầ đ nế giá trị c aủ thu cộ tính (gi ngố thủ t cụ GET trong VB). Ví dụ: thủ t cụ sau (d ngạ if_needed) cho thu cộ tính bay c aủ frame chim nói trên.

self:số_cánh < 2

self:số_cánh = 2

4. Các thủ t cụ : L cượ đồ frame càng cho phép tích h pợ cách th cứ đ tặ như các thu cộ tính như trên và các thủ t cụ vào m tộ frame. Về hình th cứ , m tộ thủ t cụ sẽ chi mế m tộ khe t ngươ tự như khe thu cộ tính nói trên. Thủ t cụ đ

If Then self:bay = false If Then self:bay = true

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa C oâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 196

cượ dùng để: bi uể di nễ m tộ hành đ ngộ nào đó c aủ đ iố t ngượ , đi uề khi nể giá trị c aủ thu cộ tính như: ki mể tra ràng bu cộ về trị, ki uể , c aủ thu cộ tính m iỗ khi c nầ trích, hay thay đ iổ nó.

L

cượ đồ có c uấ trúc – Frame

 C uấ trúc c aủ frame (tt):

 IF_CHANGED:

Thủ t cụ này đ

cượ th cự thi m iỗ khi giá trị c aủ thu cộ tính mà if_changed này cượ g nắ vào thay đ iổ . (gi ngố như SET, đ LET trong VB)

Ví dụ: g nắ thủ t cụ sau cho thu cộ

cượ đồ frame cũng gi ngố như các hệ

Chú ý: các ví dụ trên mô ph ngỏ theo ngôn ngữ Kappa PC, trong đó, “Expert System -DurKin”: - Seft: từ khoá chỉ chính b nả thân frame đang mô tả (như Me c aủ VB, this c aủ VC) - # : d uấ n iố chu iổ (như & c aủ VB, + c aủ VC) - L th ngố h

ngượ . Chúng ta:

ngướ đ iố t

Seft:hànhđ ngộ

 Có thể đ tặ tả frame l pớ hay cá

thể.

tính đói c aủ l pớ chim nói trên. If Seft:đói = true Then eating # seft:ăn 4. Các thông tin khác:

M tộ số khe khác c aủ frame có thể ch aứ frame khác, link đ nế frame, m ngạ ngữ nghĩa, rules, hay các lo iạ thông tin khác.

nghĩa l

 Có thể đ tặ tả tính th aừ kế.  M iỗ khi t oạ ra frame cá thể, có thể copy các thu cộ tính, thủ t cụ c aủ th iờ có thể mở r ngộ frame l pớ ; đ ngồ thêm, hay đ nhị iạ m tộ số thu cộ tính, thủ t cụ .

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 197

L

cượ đồ có c uấ trúc – Script

2. Results:

K tế quả thu đ

cượ từ script khi

 Script – K chị Là m tộ l

nó hoàn thành. 3. Props:

Các đồ v tậ tham gia vào script,

iớ thi uệ tr

ngươ , cán, bình oxy,…

b nả : cượ đồ bi uể di nễ có c uấ trúc, dùng để bi uể di nễ m tộ chu iổ các sự ki nệ trong m tộ ngữ c nhả cụ thể. Nó như ngươ ti nệ để tổ ch cứ các phụ thu cộ m tộ ph cướ ) để mô tả khái ni mệ – (đã gi m tộ tình hu ngố cụ thể.

như: xe c uứ th 4. Roles:

Script đ

Các cá nhân tham gia vào script, iườ

cượ dùng trong các hệ th ngố hi uể NNTN, tổ ch cứ tri th cứ trong thành ph nầ các tình hu ngố mà hệ th ngố ph iả tìm hi uể .

như: b nhệ nhân, bác sĩ, y tá, ng nhà,… 5. Scenes:

chính trong script,

Các c nhả

 C uấ trúc c aủ Script: 1. Entry conditions:

như: di chuy nể , c pấ c uứ , h iồ s cứ ,..

Các đi uề ki nệ ph iả true để script cượ g iọ . Ví dụ: m tộ cá nhân bị b nhệ thì cượ g iọ .

đ script nh pậ vi nệ đ

b nả đi nhà hàng

 M tộ ví dụ về k chị như ví dụ sau:

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 198

L

cượ đồ có c uấ trúc – Script

Scene 1: (Entering)

Script: RESTAURENT Track: Coffe Shop Entry conditions: S is hungry S has money

Results:

S PTRANS S into restaurent. S ATTEND eyes to tables S MBUILD where to sit S PTRANS S to table S MOVE S to sitting position ---

Props:

Scene 2: (Ordering) (Menu on table) S PTRANS menu to S

Roles:

(S ask for menu) S MTRANS signal to W W PTRANS W to table S MTRANS ‘need menu’ to W W PTRANS W to menu

S has less money O has more money S is not hungry S is pleased (optional) Tables Menu Food (F) Check Money Custumer (S) Waiter(W) Cook(C) Cashier(M) Owner(O)

Ñ aïi H oïc Baùch Khoa Tp.H C M – 2001 Baûn quyeàn (cid:211) Khoa Coâng N gheä Thoâng Tin

Baøi giaûng “Trí tueä nhaân taïo” - Slide 199