Bài giảng Trí Tuệ Nhân Tạo - Chương 4: Biểu thức tri thức - Nguyễn Văn Hòa

pdf

33 trang huongle 2190

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí Tuệ Nhân Tạo - Chương 4: Biểu thức tri thức - Nguyễn Văn Hòa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_tri_tue_nhan_tao_chuong_4_bieu_thuc_tri_thuc_nguye.pdf

Nội dung text: Bài giảng Trí Tuệ Nhân Tạo - Chương 4: Biểu thức tri thức - Nguyễn Văn Hòa

Ch ươ ng 4: Bi u di n tri th c 1
Ni dung Gi ới thi ệu v ề tri th ức Bi ểu di ễn và ánh x ạ Các cách ti ếp c ận Các v ấn đề trong bi ểu di ễn tri th ức Vấn đề khung 2
Tri th c là gì? Dữ li ệu là các con s ố, ký hi ệu mà máy tính có th ể lưu tr ữ, bi ểu di ễn, x ử lý. B ản thân d ữ li ệu không có ý ngh ĩa. Ch ỉ khi con ng ườ i c ảm nh ận, t ư duy thì d ữ li ệu mới có m ột ý ngh ĩa nh ất đị nh, đó chính là thông tin. Tri th ức là k ết tinh, cô đọ ng, ch ắt l ọc c ủa thông tin. Tri th ức hình thành do quá trình x ử lý thông tin mang l ại. 3
Phân lo i tri th c Các đị nh lý tóan h ọc, đị nh lu ật v ật lý là các tri th ức mang tính kh ẳng đị nh s ự ki ện. Các ph ươ ng pháp điều ch ế hóa h ọc, thu ật toán là tri th ức mang tính th ủ t ục. Các nh ận đị nh, k ết lu ận v ề s ự ki ện, hi ện t ượ ng là tri th ức mô t ả. Các ướ c l ượ ng, suy đoán hình thành qua kinh nghi ệm là tri th ức heuristic 4
Nhu c u x lý tri th c? Trí tu ệ, s ự thông minh ph ải d ựa trên n ền t ảng c ủa tri th ức. Tuy nhiên, nó còn ph ụ thu ộc vào vi ệc vận d ụng, x ử lý tri th ức. Bi ểu di ễn tri th ức là vi ệc đư a tri th ức vào máy tính. Và ch ỉ có ý ngh ĩa n ếu công vi ệc ti ếp theo: “x ử lý tri th ức đượ c th ực hi ện”. 5
Ví d v m t h tri th c Cho 2 bình r ỗng X, Y có th ể tích l ần l ượ t là Vx, Vy. Dùng 2 bình này để đong ra z lít n ướ c. Cụ th ể v ới Vx=5, Vy=7 và z=4, ta làm nh ư sau: Múc đầ y bình 7 Đổ qua cho đầ y bình 5. Đổ h ết n ướ c trong bình 5 Đổ ph ần còn l ại trong bình 7 qua bình 5 Múc đầ y bình 7 Đổ t ừ bình 7 qua cho đầ y bình 5 Ph ần còn l ại trong bình 7 là 4 lít 6
Bi u di n tri th c Là ph ươ 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 Tri th ức th ực Tri th ức Bằng cách nào ? Của lĩnh vực tính toán ồ Gồm: đố i tượ ng và các quan Bằng cách : dùng các lượ c G m: Bảng ánh xạ gi ữa: hệ gi ữa chúng trong lĩnh vực đồ bi ểu di ễn (scheme ). Đố i tượ ng th ực đố i tượ ng Ch ọn dùng lượ c đồ cho tính toán lo ại tri th ức là vấn đề quan Quan hệ th ực quan hệ tr ọng tính toán 7
Lư c đ bi u di n tri th c Lượ c đồ logic 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. Các lu ật suy di ễn áp d ụng cho lo ại l ượ c đồ này Ngôn ng ữ l ập trình hi ện th ực t ốt nh ất cho lo ại l ượ c đồ này là: PROLOG Lượ c đồ th ủ t ục Bi ểu di ễn tri th ức nh ư t ập các ch ỉ th ị l ệnh để gi ải quy ết vấn đề Các ch ỉ th ị l ệnh trong l ượ c đồ th ủ t ục ch ỉ ra b ằng cách nào gi ải quy ết v ấn đề 8
Lư c đ bi u di n tri th c Lượ c đồ m ạng Bi ểu di ễn tri th ức nh ư là đồ th ị; các đỉ nh nh ư là các đố i tượ ng ho ặc khái ni ệm, các cung nh ư là quan h ệ gi ữa chúng Các ví d ụ v ề lo ại l ượ c đồ này g ồm: mạng ng ữ ngh ĩa Lượ c đồ c ấu trúc Là m ột m ở r ộng c ủa l ượ c đồ m ạng; b ằng cách cho phép các nút 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 Kịch b ản (script), khung (frame), đố i t ượ ng (object) là ví d ụ c ủa l ượ c đồ này 9
Bi u di n và ánh x Tri th ức c ủa l ĩnh v ực: Là toàn b ộ nh ững hi ểu bi ết v ề l ĩnh v ực đó Gồm: khái ni ệm, đố i t ượ ng, quan h ệ gi ữa chúng, lu ật tồn t ại gi ữa chúng, Hi ện t ồn t ại 1 s ố l ượ c đồ ghi nh ận tri th ức Để gi ải bài toán AI c ần: Tri th ức v ề bài toán (có th ể nhi ều) Ph ươ ng ti ện để x ử lý tri th ức nh ư: retrieve, update, infer, 10
Bi u di n và ánh x Hình th ức hóa tri th ức 11
Bi u di n và ánh x Hai m ức c ấu trúc cho facts/representations Mức tri th ức: Mức mà các s ự ki ện, g ồm cách hành x ử c ủa agent (tác tử) và m ục tiêu hi ện t ại, đượ c mô t ả. Mức ký hi ệu: Mức mà s ự bi ểu di ễn c ủa các đố i t ượ ng đã đượ c ch ọn trong m ức tri th ức đượ c vi ết ra ở d ạng ký hi ệu để có th ể xử lý đượ c b ằng ch ươ ng trình 12
Bi u di n và ánh x Ví d ụ: Câu ti ếng Anh: “Spot is a dog” “Every dog has a tail” Có th ể đượ c bi ểu di ễn ở nhi ều l ượ c đồ Dạng logic (ch ươ ng sau): 1. dog(Spot). 2. ∀X(dog(X) → hastail(X)). Từ đó câu: “Spot has a tail”, có th ể thu đượ c qua các b ướ c: 3. T ừ 2, X=“Spot”: dog(Spot) → hastail(Spot). 4. T ừ 1, 3: hastail(Spot). Ánh x ạ ng ượ c → “Spot has a tail”. 13
Bi u di n và ánh x Dạng m ạng ng ữ ngh ĩa (ch ươ ng sau): 14
Bi u di n và ánh x Mô hình gi ải quy ết v ấn đề c ủa con ng ườ i và máy 15
Các cách ti p c n Bốn thu ộc tính c ủa h ệ th ống bi ểu di ễn tri th ức: Kh ả n ăng bi ểu di ễn t ất c ả các tri th ức c ần thi ết cho l ĩnh vực đó. Kh ả n ăng x ử lý các c ấu trúc s ẵn có để sinh ra các c ấu trúc m ới t ươ ng ứng v ới tri th ức m ới đượ c sinh ra t ừ tri th ức c ũ. Kh ả n ăng thêm vào c ấu trúc nh ững tri th ức thông tin b ổ sung mà nó có th ể đượ c dùng để h ướ ng d ẫn c ơ ch ế suy lu ận theo h ướ ng có nhi ều tri ển v ọng nh ất. Kh ả n ăng thu đượ c thông tin m ới d ễ dàng. Tr ườ ng h ợp đơ n gi ản nh ất là chèn tr ực ti ếp tri th ức m ới (do con ng ườ i) vào c ơ s ở tri th ức. Lý t ưở ng nh ất là ch ươ ng trình có th ể ki ểm soát vi ệc thu đượ c tri th ức. 16
Các cách ti p c n Năng l ực hi ện nay: Không m ột h ệ th ống nào có th ể t ối ưu t ất c ả các kh ả năng trên cho m ọi ki ểu tri th ức. Nhi ều k ỹ thu ật dùng cho bi ểu di ễn tri th ức cùng t ồn t ại. Ch ươ ng trình th ườ ng dùng nhi ều h ơn 1 k ỹ thu ật bi ểu di ễn. 17
Các cách ti p c n Tri th ức quan h ệ đơ n gi ản: Bi ểu di ễn các s ự ki ện (facts) d ạng khai báo nh ư t ập quan hệ đã dùng trong CSDL quan h ệ - xem ví d ụ sau 18
Các cách ti p c n Tri th ức có kh ả n ăng th ừa k ế: Một d ạng b ổ sung c ơ ch ế suy di ễn vào c ơ s ở tri th ức quan h ệ nói trên, đó là: th ừa k ế thu ộc tính. Th ừa k ế thu ộc tính: Tổ ch ức các đố i t ượ ng thành các l ớp (class). Các l ớp đượ c s ắp x ếp vào h ệ th ống phân c ấp (hierachy) – có l ớp cha (t ổng quát) và l ớp con (c ụ th ể). → Các l ớp con th ừa k ế các thu ộc tính t ừ l ớp cha. 19
Các cách ti p c n Tri th ức có kh ả n ăng th ừa k ế (tt.): Line: Thu ộc tính Box: Đố i t ượ ng, Tr ị (Value) c ủa thu ộc tính c ủa đố i t ượ ng. Arrow: Từ đố i t ượ ng sang tr ị c ủa thu ộc tính. 20
Các cách ti p c n Tri th ức suy di ễn: Th ừa k ế thu ộc tính ở trên là 1 d ạng suy di ễn Logic truy ền th ống: cung c ấp d ạng suy di ễn m ạnh h ơn Tri th ức suy di ễn: c ần th ủ t ục suy di ễn Th ủ t ục suy di ễn: nhi ều d ạng Forward (ti ến): Đi t ừ s ự ki ện đế n k ết lu ận Backward (lùi): Đi t ừ k ết lu ận đế n s ự ki ện đã cho Th ủ t ục th ườ ng dùng: resolution – xem ch ươ ng 5. 21
Các cách ti p c n Tri th ức th ủ t ục: Tri th ức trong các ví d ụ tr ướ c: T ĩnh, d ạng khai báo Một d ạng tri th ức khác: ch ỉ ra hành độ ng đượ c thi hành khi điều ki ện nào đó tho ả → tri th ức th ủ t ục Cách bi ểu di ễn trong ch ươ ng trình Vi ết b ằng các NNLT (LISP ch ẳng h ạn) ⇒ Máy s ẽ th ực thi mã để th ực hi ện công vi ệc Tr ở ng ại Khó vi ết CT suy di ễn v ề hành vi c ủa CT khác Cập nh ật/debug s ố l ượ ng l ớn mã → khó kh ăn 22
Các cách ti p c n Tri th ức th ủ t ục (tt): (defun fun1 (lis) (cond ((null lis) 0) ((not (listp (car lis))) (cond ((eq (car lis) nil) (fun1 (car lis))) (T (+ 1 (fun1 (cdr lis)))) ) ) (T (+ (fun1 (car lis)) (fun1 (cdr lis)))) ) ) 23
Các cách ti p c n Tri th ức th ủ t ục (tt): dùng lu ật sinh (production rule) Lu ật sinh và cách s ử d ụng chúng: là đị nh h ướ ng ho ạt độ ng h ơn các d ạng bi ểu di ễn nói tr ướ c đây. Tuy phân bi ệt đâu là tri th ức khai báo hay th ủ t ục là một công vi ệc khó kh ăn. 24
Các v n đ trong bi u di n tri th c Có nh ững thu ộc tính c ơ b ản nào c ủa đố i t ượ ng mà chúng xu ất hi ện trong m ọi l ĩnh v ực không? Nếu có: đó là nh ững thu ộc tính nào? Có ch ắc ch ắn là chúng s ẽ đượ c x ử lý thích h ợp trong t ừng c ơ ch ế đượ c đề ngh ị không? Có quan h ệ quan tr ọng nào t ồn t ại cùng v ới thu ộc tính không? 25
Các v n đ trong bi u di n tri th c Tri th ức đượ c bi ểu di ễn đế n m ức chi ti ết nào? Có t ồn t ại nh ững primitive cơ b ản mà qua đó t ất cả tri th ức đượ c bi ểu di ễn? Sử d ụng primitives có ích không? Tập các đố i t ượ ng đượ c bi ểu di ễn nh ư th ế nào? Với s ố l ượ ng l ớn tri th ức đượ c ch ứa trong CSDL, Bằng cách nào truy xu ất nh ững thành ph ần c ần thi ết? 26
Các v n đ trong bi u di n tri th c Các thu ộc tính quan tr ọng: 1. Instance: Cho bi ết quan h ệ thành viên gi ữa đố i t ượ ng và l ớp nó thu ộc vào 2. Isa Cho bi ết m ột l ớp là con c ủa l ớp khác Cặp thu ộc tính trên cho phép kh ả n ăng th ừa k ế thu ộc tính Chúng có th ể đượ c g ọi và bi ểu di ễn khác nhau trong nhi ều h ệ th ống tri th ức 27
Các v n đ trong bi u di n tri th c Các quan h ệ cùng v ới các thu ộc tính: Thu ộc tính: entity | relationship Có tính ch ất quan tr ọng: Đả o Tồn t ại trong m ột h ệ th ống Isa Các k ỹ thu ật để suy di ễn gi ữa các giá tr ị Các thu ộc tính đơ n tr ị 28
Các v n đ trong bi u di n tri th c Các quan h ệ cùng v ới các thu ộc tính: 29
Vn đ khung Khung Mỗi frame mô t ả m ột đố i t ượ ng (object) . Một frame bao g ồm 2 thành ph ần c ơ b ản là slot và facet. Một slot là m ột thu ộc tính đặ c t ả đố i t ượ ng đượ c bi ểu di ễn b ởi frame. Ví d ụ : trong frame mô t ả xe h ơi, có hai slot là tr ọng l ượ ng và lo ại máy . Mỗi slot có th ể ch ứa m ột ho ặc nhi ều facet. Các facet ( đôi lúc đượ c g ọi là slot "con") đặ c t ả m ột s ố thông tin ho ặc th ủ t ục liên quan đế n thu ộc tính đượ c mô t ả b ởi slot. Facet có nhi ều lo ại khác nhau, sau đây là m ột s ố facet th ườ ng g ặp: value, default value, range, 30
Vn đ khung Bằng cách nào bi ểu di ễn hi ệu qu ả chu ỗi tr ạng thái cho bài toán tìm ki ếm? Bài toán robot: on(Plant12, Table34). under(Table34, Window13). in(Table34, Room15). → 1 tr ạng thái = danh sách các facts trên. → bất ti ện: danh sách dài. từ tr ạng thái A → B: nhi ều facts không thay đổ i. Vấn đề khung: bài toán v ề bi ểu di ễn facts thay đổ i cùng v ới nh ững facts không đượ c bi ết. 31
Vn đ khung Sử d ụng các ti ền đề khung: Mô t ả t ất c ả nh ững cái s ẽ không thay đổ i khi áp d ụng 1 toán t ử c ụ th ể nào đó để chuy ển t ừ tr ạng thái n → n+1 Ví d ụ: “V ật X có màu Y t ại tr ạng thái S1 thì c ũng có màu Y t ại tr ạng thái S2 khi di chuy ển X t ừ S1 → S2’ color(X,Y, S1) ^ move(X,S1,S2) → color(X,Y,S2). Bất ti ện: → Số ti ền đề nhi ều. 32
Vn đ khung Sử d ụng gi ả đị nh: Nh ững cái thay đổ i: ghi t ườ ng minh ho ặc đượ c d ẫn ra 1 cách logic t ừ nh ững cái thay đổ i. Hai cách ti ếp c ận dùng cho backtrack trên chu ổi tr ạng thái: Không thay đổ i mô t ả đầ u. Ghi nh ận s ự thay đổ i c ụ th ể tại node c ần thay đổ i. Thay đổ i mô t ả đầ u. Ghi nh ận nh ững gì c ần làm khi undo t ại tr ạng thái đó. 33