TR NG Đ I H C BÁCH KHOA HÀ N IƯỜ Ạ Ọ Ộ
VI N CÔNG NGH THÔNG TIN VÀ TRUY N THÔNGỆ Ệ Ề
BÀI T P L N TRÍ TU NHÂNẬ Ớ Ệ
T O Ạ
Đ TÀI: XÂY D NG H CHUYÊN GIA T V N MUA ĐI N THO I DI Đ NGỀ Ự Ệ Ư Ấ Ệ Ạ Ộ
SVTH :Nguy n Th Thúy 20082599ễ ị
Ph m Kh ng Duy 20080459ạ ươ
L pớ: HTTT – K53
GVHD : TS. Nguy n Nh t Quang ễ ậ
Hà N i, tháng 11 năm 2012ộ
Trí tu nhân t oệ ạ
K HO CH TH C HI N Ế Ạ Ự Ệ
Th i gian th c hi nờ ự ệ N i dung công vi cộ ệ Ng i th c hi nườ ự ệ
01/09/2012- 05/09/2012 Tìm hi u đ xu t đ tàiể ề ấ ề
môn h c.ọ Thúy
08/09/2012-20/09/2012 Thu th p tri th c xây d ngậ ứ ự
t p lu t, d li u.ậ ậ ữ ệ Duy
20/09/2012-31/10/2012 Vi t ch ng trìnhế ươ Thúy
01/11/2012-08/11/2012 Vi t báo cáo l n1ế ầ Duy
09/11-13/11/2012 Hoàn thi n báo cáo, vi tệ ế
slide
Duy+ Thúy
Trí tu nhân t oệ ạ
I- Gi i thi u bài toán ớ ệ
- Hi n nay, khoa h c công ngh phát tri n r t nhanh chóng làm thay đ i r tệ ọ ệ ể ấ ổ ấ
nhi u trong đ i s ng hàng ngày c a chúng ta.Ngày nay, ta th y r ng chi c đi nề ờ ố ủ ấ ằ ế ệ
tho i di đ ng d ng nh là v t b t ly thân đ i v i m i ng i m i t ng l p.B iạ ộ ườ ư ậ ấ ố ớ ỗ ườ ở ọ ầ ớ ở
nó đáp ng r t nhi u nhu c u c a con ng i trong cu c s ng hi n đ i ngày nay tứ ấ ề ầ ủ ườ ộ ố ệ ạ ừ
nhu c u thi t y u trao đ i thông tin t i nhu c u gi i trí, t i ph c v cho các m cầ ế ế ổ ớ ầ ả ớ ụ ụ ụ
đích chuyên môn khác.
- Nh ng chi c đi n tho i ngày nay không nh ng ch giúp con ng i trao đ iữ ế ệ ạ ữ ỉ ườ ổ
thông tin mà nó còn cung c p r t nhi u các ti n ích khác: nghe nh c, ch p hình, truyấ ấ ề ệ ạ ụ
c p internet…..ậ
- Nh ng hi n t i có r t nhi u hãng và s n ph m đi n tho i di đ ng ra đ i v iư ệ ạ ấ ề ả ẩ ệ ạ ộ ờ ớ
r t nhi u các ki u dáng màu s c tính năng, giá c …… khi n cho vi c vi c l aấ ề ể ắ ả ế ệ ệ ự
ch n m t chi c đi n tho i phù h p v i m c đích s d ng, công vi c, kh năng tàiọ ộ ế ệ ạ ợ ớ ụ ử ụ ệ ả
chính, … tr nên khó khăn h n.ở ơ
- H t v n mua đi n tho i di đ ng s h tr cho ng i s d ng ch n đ cệ ư ấ ệ ạ ộ ẽ ỗ ợ ườ ử ụ ọ ượ
chi c đi n tho i phù h p v i cá nhân ng i s d ng.ế ệ ạ ợ ớ ườ ử ụ
II- C s lý thuy tơ ở ế
1. Bi u di n tri th cể ễ ứ
- Bi u di n tri th c (knowledge representation) là m t lĩnh v c nghiên c uể ễ ứ ộ ự ứ
quan tr ng c a Trí tu nhân t o. Nh m phát tri n các ph ng pháp, cách th cọ ủ ệ ạ ằ ể ươ ứ
bi u di n tri th c và các công c h tr vi c bi u di n tri th c.ể ễ ứ ụ ỗ ợ ệ ể ễ ứ
- Có r t nhi u ph ng pháp bi u di n tri th c, và ph i ph thu c vào tri th cấ ề ươ ể ễ ứ ả ụ ộ ứ
c th c a t ng bài toán ta m i ch n đ c m t ph ng pháp bi u di n h p lýụ ể ủ ừ ớ ọ ượ ộ ươ ể ễ ợ
nh t.ấ
•Bi u di n tri th c b ng lu t s n xu t (Production rules)ể ễ ứ ằ ậ ả ấ
•Bi u di n tri th c b ng khung (Frames)ể ễ ứ ằ
•Bi u di n tri th c s d ng m ng ng nghĩa(Semantic networks )ể ễ ứ ử ụ ạ ữ
•Bi u di n tri th c b ng ontologyể ễ ứ ằ
•Các mô hình xác su tấ
……………..
- Khi bi u di n tri th c cho m t bài toán, vi c bi u di n này đ c coi là t tể ễ ứ ộ ệ ể ễ ượ ố
khi chúng th a mãn đ c 4 y u t sau ỏ ượ ế ố
•Tính hoàn ch nh (Completeness)ỉ
•Tính ng n g n (Conciseness)ắ ọ
•Tính hi u qu v tính toán( Computational efficiency)ệ ả ề
•Tính rõ ràng, d hi u(Transparency)ễ ể
- V i bài toán c th đang xét- bài toán t v n mua đi n tho i di đ ng, vi c bi uớ ụ ể ư ấ ệ ạ ộ ệ ể
di n tri th c s d ng lu t là m t ph ng pháp bi u di n h p lý.ễ ứ ử ụ ậ ộ ươ ể ễ ợ
1.1 Bi u di n tri th c d a trên lu tể ễ ứ ự ậ
- Ph ng pháp bi u di n tri th c b ng lu t sinh đ c phát minh b i Newellươ ể ễ ứ ằ ậ ượ ở
và Simon trong lúc hai ông đang c g ng xây d ng m t h gi i bài toán t ng quát.ố ắ ự ộ ệ ả ổ
Trí tu nhân t oệ ạ
Đây là m t ki u bi u di n tri th c có c u trúc, và đ c s d ng ph bi n nh tộ ể ể ễ ứ ấ ượ ử ụ ổ ế ấ
trong các h c s tri th c.ệ ơ ở ứ
- Ý t ng c b n là tri th c có th đ c c u trúc b ng m t c p đi u ki n –ưở ơ ả ứ ể ượ ấ ằ ộ ặ ề ệ
hành đ ng : "N U đi u ki n x y ra THÌ hành đ ng s đ c thi hành".ộ Ế ề ệ ả ộ ẽ ượ
- Trong bi u di n tri th c s d ng lu t, ta c n xác đ nh:ể ễ ứ ử ụ ậ ầ ị
•T p các s ki n F(Facts)ậ ự ệ
{A1,A2, A3, …… An, B1,B2, B3, …… Bm }
•T p các lu t R(rules) áp d ng trên các s ki n có d ng sau:ậ ậ ụ ự ệ ạ
IF A1 AND A2 AND … AND An THEN B
(trong đó A1,A2, …… An, B) là các s ki n trong F.ự ệ
A1,A2, A3, …… An – đ c g i là đi u ki n (Conditions)ượ ọ ề ệ
B: là k t luân(conclusion).ế
-Trong bi u di n tri th c d a trên lu t, c ch suy lu n trên các lu t s n xu t baoễ ễ ứ ự ậ ơ ế ậ ậ ả ấ
g m hai c ch : suy di n ti n, và suy di n lùi.ồ ơ ế ễ ế ễ
•Suy di n ti n: là quá trình suy lu n xu t phát t m t s s ki n ban đ u, xácễ ế ậ ấ ừ ộ ố ự ệ ầ
đ nh các s ki n có th sinh ra t s ki n này.ị ự ệ ể ừ ự ệ
•Suy di n lùi:ễ là quá trình suy lu n ng c xu t phát t m t s s ki n ban đ u,ậ ượ ấ ừ ộ ố ự ệ ầ
ta tìm ki m các s ki n đã "sinh" ra s ki n này.ế ự ệ ự ệ
-V n đ t i u lu t: T p các lu t trong m t c s tri th c r t có kh năng th a,ấ ề ố ư ậ ậ ậ ộ ơ ở ứ ấ ả ừ
trùng l p ho c nguy hi m h n là mâu thu n nhau. Dĩ nhiên là h th ng có th đặ ặ ể ơ ẫ ệ ố ể ổ
l i cho ng i dùng v vi c đ a vào h th ng nh ng tri th c nh v y. Tuy vi c t iỗ ườ ề ệ ư ệ ố ữ ứ ư ậ ệ ố
u m t c s tri th c v m t t ng quát là m t thao tác khó (vì gi a các tri th cư ộ ơ ở ứ ề ặ ổ ộ ữ ứ
th ng có quan h không t ng minh), nh ng trong gi i h n c s tri th c d iườ ệ ườ ư ớ ạ ơ ở ứ ướ
d ng lu t, ta v n có m t s thu t toán đ n gi n đ lo i b các v n đ này.ạ ậ ẫ ộ ố ậ ơ ả ể ạ ỏ ấ ề
-u đi m c a ph ng pháp bi u di n tri th c d a trên lu tƯ ể ủ ươ ể ễ ứ ự ậ :
Bi u di n tri th c b ng lu t đ c bi t h u hi u trong nh ng tình hu ng h th ngể ễ ứ ằ ậ ặ ệ ữ ệ ữ ố ệ ố
c n đ a ra nh ng hành đ ng d a vào nh ng s ki n có th quan sát đ c. Nó cóầ ư ữ ộ ự ữ ự ệ ể ượ
nh ng u đi m chính y u sau đây : ữ ư ể ế
• Các lu t r t d hi u nên có th d dàng dùng đ trao đ i v i ng iậ ấ ễ ể ể ễ ể ổ ớ ườ
dùng (vì nó là m t trong nh ng d ng t nhiên c a ngôn ng ). ộ ữ ạ ự ủ ữ
• Có th d dàng xây d ng đ c c ch suy lu n và gi i thích t cácể ễ ự ượ ơ ế ậ ả ừ
lu t. ậ
• Vi c hi u ch nh và b o trì h th ng là t ng đ i d dàng. ệ ệ ỉ ả ệ ố ươ ố ễ
• Có th c i ti n d dàng đ tích h p các lu t m .ể ả ế ễ ể ợ ậ ờ
-Nh c đi m c a ph ng pháp bi u di n tri th c d a trên lu t.ượ ể ủ ươ ể ễ ứ ự ậ
•Các tri th c ph c t p đôi lúc đòi h i quá nhi u (hàng ngàn) lu t sinh.ứ ứ ạ ỏ ề ậ
Đi u này s làm n y sinh nhi u v n đ liên quan đ n t c đ l n qu n tr hề ẽ ả ề ấ ề ế ố ộ ẫ ả ị ệ
th ng. ố
• Th ng kê cho th y, ng i xây d ng h th ng trí tu nhân t o thíchố ấ ườ ự ệ ố ệ ạ
s d ng lu t sinh h n t t c ph ng pháp khác (d hi u, d cài đ t) nên hử ụ ậ ơ ấ ả ươ ễ ể ễ ặ ọ
th ng tìm m i cách đ bi u di n tri th c b ng lu t sinh cho dù có ph ngườ ọ ể ể ễ ứ ằ ậ ươ
pháp khác thích h p h n! Đây là nh c đi m mang tính ch quan c a conợ ơ ượ ể ủ ủ
ng i. ườ
• C s tri th c lu t sinh l n s làm gi i h n kh năng tìm ki m c aơ ở ứ ậ ớ ẽ ớ ạ ả ế ủ
ch ng trình đi u khi n. Nhi u h th ng g p khó khăn trong vi c đánh giáươ ề ể ề ệ ố ặ ệ
các h d a trên lu t sinh cũng nh g p khó khăn khi suy lu n trên lu t sinh.ệ ự ậ ư ặ ậ ậ
Trí tu nhân t oệ ạ
2. Suy di n ti nễ ế
- Là m t trong hai c ch c ch suy lu n trên các lu t s n xu t trong bi u di nộ ơ ế ơ ế ậ ậ ả ấ ể ễ
tri th c d a trên lu t.ứ ự ậ
- Bài toán c n ch ng minh:V i m t t p các m nh đ gi thi t (c s tri th c)ầ ứ ớ ộ ậ ệ ề ả ế ơ ở ứ
KB, c n suy ra m nh đ k t lu n Q. Suy di n ti n là suy di n d a trên d li uầ ệ ề ế ậ ễ ế ễ ự ữ ệ
nên r t phù h p v i các bài toán đ a ra quy t đinh, nh n d ng đ i t ng…..ấ ợ ớ ư ế ậ ạ ố ượ
-Ý t ng c a suy di n ti nưở ủ ễ ế : L p l i 2 b c sau cho đ n khi suy ra đ c k tặ ạ ướ ế ượ ế
lu n:ậ
•Áp d ng các lu t có m nh đ gi thi t đ c th a mãn trong KBụ ậ ệ ề ả ế ượ ỏ
•B sung k t lu n c a các lu t đó vào trong KB.ổ ế ậ ủ ậ
-S đ thu t toán.ơ ồ ậ
-Nh ng đi m c n chú ý khi cài đ t gi i thu t suy di n ti n.ữ ể ầ ặ ả ậ ễ ế
•Tránh các vòng l p b ng cách ki m tra xem các m nh đ m i đã có trongặ ằ ể ệ ề ớ
danh sách các m nh đ c n ch ng minh ch a? N u r i thì không b sungệ ề ầ ứ ư ế ồ ổ
l i n a!ạ ữ
•Tránh vi c ch ng minh l p l i đ i v i m t m nh đ . M nh đ này cóệ ứ ặ ạ ố ớ ộ ệ ề ệ ề
th đã đ c ch ng minh là đúng tr c đó ho c đã đ c ch ng minh ể ượ ứ ở ướ ặ ượ ứ ở
tr c đó là không th th a mãn đ c trong KB.ướ ể ỏ ượ
-u đi m c a suy di n ti n Ư ể ủ ễ ế
•u đi m chính c a suy di n ti n là làm vi c t t khi bài toán v b n ch tƯ ể ủ ễ ế ệ ố ề ả ấ
đi thu th p thông tin r i th y đi u c n suy di n.ậ ồ ấ ề ầ ễ
• Suy di n ti n cho ra kh i l ng l n các thông tin t m t s thông tin banễ ế ố ượ ớ ừ ộ ố
đ u. Nó sinh ra nhi u thông tin m i.ầ ề ớ
• Suy di n ti n là ti p c n lý t ng đ i v i lo i bài toán c n gi i quy tễ ế ế ậ ưở ố ớ ạ ầ ả ế
các nhi m v nh l p k ho ch, đi u hành đi u khi n và di n d ch.ệ ụ ư ậ ế ạ ề ề ể ễ ị
-Nh c đi m c a suy di n ti nượ ể ủ ễ ế