Bài giảng Trí tuệ nhân tạo - Nguyễn Đình Cường

ình "Sẻ là Chim" thể hiện trên mạng ngữ nghĩa
 Artificial Intelligence Nguyễn Đình Cường 85
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Hình Phát triển mạng ngữ nghĩa
Artificial Intelligence Nguyễn Đình Cường 86
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Giải bài toán tam giác tổng quát
 3
• Có 22 yếu tố của tam giác. Như vậy có C 22 -1 cách để xây dựng hay xác định một tam giác.
• Theo thống kê, có khoảng 200 công thức liên quan đến cạnh và góc 1 tam giác.
• Để giải bài toán này bằng công cụ mạng ngữ nghĩa, sử dụng khoảng 200 đỉnh để chứa công
thức và khoảng 22 đỉnh để chứa các yếu tố của tam giác. Mạng ngữ nghĩa cho bài toán này có
cấu trúc như sau :
 • Đỉnh của đồ thị bao gồm hai loại :
 Đỉnh chứa công thức (ký hiệu bằng hình chữ nhật)
 Đỉnh chứa yếu tố của tam giác (ký hiệu bằng hình tròn)
 • Cung : chỉ nối từ đỉnh hình tròn đến đỉnh hình chữ nhật cho biết yếu tố tam giác xuất
 hiện trong công thức nào
• Lưu ý : trong một công thức liên hệ giữa n yếu tố của tam giác, ta giả định rằng nếu đã biết
giá trị của n-1 yếu tố thì sẽ tính được giá trị của yếu tố còn lại. Chẳng hạn như trong công thức
tổng 3 góc của tam giác bằng 1800 thì khi biết được hai góc, ta sẽ tính được góc còn lại.
 Artificial Intelligence Nguyễn Đình Cường 87
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Giải bài toán tam giác tổng quát
• B1 : Kích hoạt những đỉnh hình tròn đã cho ban đầu (những yếu tố đã có
giá trị)
• B2 : Lặp lại bước sau cho đến khi kích hoạt được tất cả những đỉnh ứng
với những yếu tố cần tính hoặc không thể kích hoạt được bất kỳ đỉnh nào
nữa.
• Nếu một đỉnh hình chữ nhật có cung nối với n đỉnh hình tròn mà n-1 đỉnh
hình tròn đã được kích hoạt thì kích hoạt đỉnh hình tròn còn lại (và tính giá
trị đỉnh còn lại này thông qua công thức ở đỉnh hình chữ nhật).
 Artificial Intelligence Nguyễn Đình Cường 88
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Ví dụ : "Cho hai góc a, b và chiều dài cạnh a của tam giác. Tính chiều dài đường 
cao hC".
 p=(a+b+c)/2
 p
Artificial Intelligence Nguyễn Đình Cường 89
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Frame
 Hình Cấu trúc frame
 Hình Nhiều mức của frame mô tả quan hệ phức tạp hơn 
Artificial Intelligence Nguyễn Đình Cường 90
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 LOGIC MỆNH ĐỀ VÀ LOGIC VỊ TỪ
Logic mệnh đề
Khái niệm: 
Mệnh đề: một phát biểu có giá trị là đúng hoặc sai.
Các luật cơ bản:
1. Luật phủ định: (P) = P
2. Luật kéo theo: (P Q) = (P  Q)
3. Luật tương phản: (P Q) = (Q P)
4. Luật De Morgan: (P  Q) = (P  Q) và (P  Q) = (P  Q)
5. Luật giao hoán: (P  Q) = (Q  P) và (PQ) = (QP)
6. Luật kết hợp: ((P  Q)  R) = (P  (Q  R)) và ((P  Q)  R) = (P  (Q  R))
7. Luật phân phối: P  (Q  R) = (P  Q)  (P  R) và
 P  (Q  R) = (P  Q)  (P  R)
 Artificial Intelligence Nguyễn Đình Cường 91
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Các cơ chế suy diễn
Modus Ponens: Nếu mệnh đề A đúng và A B đúng thì
 giá trị của B sẽ là đúng.
Modus Tollens: Nếu mệnh đề A B đúng và B sai thì
 giá trị của A sẽ là sai.
Artificial Intelligence Nguyễn Đình Cường 92
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Chứng minh tính đúng đắn của phép suy diễn (a → b).
Thao tác biến đối hình thức: khó đối với con người và cài đặt được trên máy tính.
Lập bảng chân trị: độ phức tạp O(2n)
Hai phương pháp chứng minh mệnh đề có độ phức tạp chỉ O(n):
 ▪ Thuật giải Vương Hạo.
 ▪ Thuật giải Robinson.
Artificial Intelligence Nguyễn Đình Cường 93
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Thuật giải Vương Hạo
B1: Phát biểu lại giả thiết và kết luận theo dạng chuẩn:
 GT1, GT2, ..., GTn → KL1, KL2, ..., KLm
B2: Chuyển vế các GTi và KLi có dạng phủ định.
B3: Nếu GTi có phép  thì thay thế phép  bằng dấu ","
 Nếu KLi có phép  thì thay thế phép  bằng dấu ",“
B4: Nếu GTi có phép  thì tách thành hai dòng con.
 Nếu ở KLi có phép  thì tách thành hai dòng con.
B5: Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở cả hai phía.
B6: a) Nếu một dòng không còn phép  và  ở cả hai vế và ở 2 vế không có chung một 
 mệnh đề thì dòng đó không được chứng minh.
 b) Một vấn đề được chứng minh nếu tất cả dòng dẫn xuất từ dạng chuẩn ban đầu 
 đều được chứng minh.
 Artificial Intelligence Nguyễn Đình Cường 94
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Một số ví dụ:
 B2: Ví dụ: p  q, (r  s), g, p  r → s, p
 p  q, p  r , p → (r  s), g, s
 B3: Ví dụ: p  q , r  (p  s) → q, s
 p, q, r, p  s → q, s
 B4: Ví dụ: p, p  q → q
 p, p → q và p, q → q
 B5: Ví dụ: p, q → q được chứng minh
 p, p → q p → p, q
Artificial Intelligence Nguyễn Đình Cường 95
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Artificial Intelligence Nguyễn Đình Cường 96
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
➢ Hoạt động dựa trên:
 + Phương pháp chứng minh phản chứng.
 + Phép hợp giải Robinson.
─ Phương pháp chứng minh phản chứng:
 ▪ Chứng minh (a → b) là đúng.
 ▪ Phản chứng: giả sử b sai, suy ra b là đúng.
─ Phép hợp giải Robinson:
 i) p  (p  q) → q
 ii) (p  q)  (p  r) → q  r
• Bài toán được chứng minh nếu a đúng và b đúng.
Artificial Intelligence Nguyễn Đình Cường 97
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Thuật giải Robinson
B1: Phát biểu lại giả thiết và kết luận dưới dạng chuẩn:
 GT1, GT2,..., GTn → KL1, KL2,..., KLm
B2: Nếu GTi có phép  thì thay bằng dấu ","
 Nếu KLi có phép  thì thay bằng dấu ",“
B3: Biến đổi dòng chuẩn ở B1 thành danh sách mệnh đề:
 {GT1, GT2,..., GTn , KL1, KL2,..., KLm}
B4: Nếu danh sách mệnh đề có 2 mệnh đề đối ngẫu nhau thì bài toán được chứng minh. Ngược lại thì 
 chuyển sang B5.
B6: Áp dụng phép hợp giải: i) p  (p  q) → q
 ii) (p  q)  (p  r) → q  r
B7: Nếu không xây dựng được thêm mệnh đề mới và danh sách mệnh
 đề không có 2 mệnh đề đối ngẫu thì vấn đề không được chứng minh. 
Ví dụ : Chứng minh rằng
 ( p  q)  ( q  r)  ( r  s)  ( u  s) →  p  u
Artificial Intelligence Nguyễn Đình Cường 98
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 LOGIC VỊ TỪ
Khái niệm
Vị từ và lượng từ (" - với mọi, $ - tồn tại) tăng cường tính cấu trúc của mệnh đề.
Mệnh đề được biểu diễn dưới dạng : 
 Vị từ (, , , )
(Vị từ: mối liên hệ giữa các đối tượng tri thức.)
Artificial Intelligence Nguyễn Đình Cường 99
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Artificial Intelligence Nguyễn Đình Cường100
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Giải quyết vấn đề bằng logic vị từ
 Sử dụng phép thay thế và phép hợp giải Robinson.
 Ví dụ: Cho vị từ P(x,y) và các mệnh đề sau:
 1. P(x,y)  P(y,z)  P(x,z)
 2. P(a,b)
 3. P(b,c)
 4. P(c,d)
 5. P(a,d)
Artificial Intelligence Nguyễn Đình Cường101
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Quá trình hợp giải:
 6. P(a,z)  P(b,z) thế x=a, y=b hợp giải 1 và 2
 7. P(a,c) thế z=c hợp giải 3 và 6
 8. P(b,d) thế z=d hợp giải 5 và 6
 9. P(x,b)  P(x,a) thế y=a, z=b hợp giải 1 và 2
 10. P(b,z)  P(c,z) thế x=b, y=c hợp giải 1 và 3
 11. P(b,d) thế z=d hợp giải 4 và 10
 12. Mâu thuẫn hợp giải 8 và 11 
Artificial Intelligence Nguyễn Đình Cường102
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Bài toán 1: Giải bài toán tìm đường đi
 Định nghĩa 2 vị từ:
 1. P(x,y) : có đường đi trực tiếp (road) từ x đến y
 2. Q(x,y) : có đường đi (route) từ x đến y
 Các mệnh đề:
 1. ($x)($y) (P(x,y))
 2. ("x) ("y) (P(x,y) → Q(x,y))
 3. ("x) ("y) ($z) (Q(x,z)  P(z,y) → Q(x,y))
Artificial Intelligence Nguyễn Đình Cường103
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Giải bài toán tìm đường đi
Artificial Intelligence Nguyễn Đình Cường104
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
 Giải bài toán tìm đường đi
 Ví dụ: Cho đồ thị, tìm đường đi từ N đến L. (tt)
 Quá trình hợp giải:
 15. Q(N,C) thế x=N, y=C hợp giải 1 và 12
 16. Q(N,D) thế x=N, f(x,y)=C, y=D hợp giải 2,13 và 15
 17. Q(N,L) thế x=N, f(x,y)=D, y=L hợp giải 11,13 và 16
 18. Có điều phải chứng minh hợp giải 14 và 17
Artificial Intelligence Nguyễn Đình Cường105
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Bài toán 2: Bài toán con khỉ và nải chuối
Trong phòng có con khỉ, chiếc ghế và nải chuối
Có thể giải bài toán nhờ vào các vị từ:
1. in_room(X) : có X trong phòng
2. dexterous(X) : X là loài khéo léo
3. tall(X) : X thì cao
4. can_climb(X,Y) : X có thể leo lên Y
5. can_move(X,Y,Z) : X có thể di chuyển Y đền gần Z
6. get_on(X,Y) : X đứng trên Y
7. under(X,Y) : X ở dưới Y
8. close(X,Y) : X ở gần Y
9. can_reach(X,Y) : X có thể cầm lấy Y
Artificial Intelligence Nguyễn Đình Cường106
 BIỂU DIỄN VÀ SUY LUẬN TRÍ THỨC
Các mệnh đề giúp giải bài toán:
1. in_room(bananas)
2. in_room(chair) 
3. in_room(monkey)
4. dexterous(monkey)
5. tall(chair)
6. can_move(mokey,chair,bananas)
7. can_climb(monkey,chair)
8. can_climb(X,Y) → get_on(X,Y)
9. in_room(X)in_room(Y)in_room(Z)can_move(X,Y,Z)→ under(Y,Z)
10. get_on(X,Y)  under(Y,Z)  tall(Y) → close(X,Z) 
11. dexterous(X)  close(X,Y) → can_reach(X,Y)
Artificial Intelligence Nguyễn Đình Cường107
 TRƯỜNG ĐẠI HỌC NHA TRANG
 Bài giảng 
 TRÍ TUỆ NHÂN TẠO
 NGUYỄN ĐÌNH CƯỜNG
 Bộ môn Công Nghệ Phần Mềm
 Khoa Công Nghệ Thông Tin
 Nha trang - 2012
Artificial Intelligence Nguyễn Đình Cường108
 MÁY HỌC
 MỞ ĐẦU
Các chương trước đã thảo luận về biểu diễn và suy luận tri thức. Trong trường 
hợp này giả định đã có sẵn tri thức và có thể biểu diễn tường minh tri thức. 
Tuy vậy trong nhiều tinh huống, sẽ không có sẵn tri thức như:
 • Kỹ sư tri thức cần thu nhận tri thức từ chuyên gia lĩnh vực.
 • Cần biết các luật mô tả lĩnh vực cụ thể.
 • Bài toán không được biểu diễn tường minh theo luật, sự kiện hay các quan hệ.
Có hai tiếp cận cho hệ thống học:
 • Học từ ký hiệu: bao gồm việc hình thức hóa, sửa chữa các luật tường minh, sự kiện 
 và các quan hệ.
 • Học từ dữ liệu số: được áp dụng cho những hệ thống được mô hình dưới dạng số liên 
 quan đến các kỹ thuật nhằm tối ưu các tham số. Học theo dạng số bao gồm mạng 
 Neural nhân tạo, thuật giải di truyền, bài toán tối ưu truyền thống. Các kỹ thuật học 
 theo số không tạo ra CSTT tường minh.
 Artificial Intelligence Nguyễn Đình Cường109
 MÁY HỌC
 CÁC HÌNH THỨC HỌC
 1. Học vẹt: Hệ tiếp nhận các khẳng định của các quyết định đúng. Khi hệ tạo ra 
 một quyết định không đúng, hệ sẽ đưa ra các luật hay quan hệ đúng mà hệ 
 đã sử dụng. Hình thức học vẹt nhằm cho phép chuyên gia cung cấp tri thức 
 theo kiểu tương tác. 
 2. Học bằng cách chỉ dẫn: Thay vì đưa ra một luật cụ thể cần áp dụng vào tình 
 huống cho trước, hệ thống sẽ được cung cấp bằng các chỉ dẫn tổng quát. Ví 
 dụ: "gas hầu như bị thoát ra từ van thay vì thoát ra từ ống dẫn". Hệ thống 
 phải tự mình đề ra cách biến đổi từ trừu tượng đến các luật khả dụng. 
 3. Học bằng qui nạp: Hệ thống được cung cấp một tập các ví dụ và kết luận được 
 rút ra từ từng ví dụ. Hệ liên tục lọc các luật và quan hệ nhằm xử lý từng ví dụ 
 mới. 
Artificial Intelligence Nguyễn Đình Cường110
 MÁY HỌC
 CÁC HÌNH THỨC HỌC
4. Học bằng tương tự: Hệ thống được cung cấp đáp ứng đúng cho các tác vụ tương
 tự nhưng không giống nhau. Hệ thống cần làm thích ứng đáp ứng trước đó nhằm
 tạo ra một luật mới có khả năng áp dụng cho tình huống mới.
5. Học dựa trên giải thích: Hệ thống phân tích tập các lời giải ví dụ (và kết quả)
 nhằm ấn định khả năng đúng hoặc sai và tạo ra các giải thích dùng để hướng dẫn
 cách giải bài toán trong tương lai.
6. Học dựa trên tình huống: Bất kỳ tính huống nào được hệ thống lập luận đều được
 lưu trữ cùng với kết quả cho dù đúng hay sai. Khi gằp tình hướng mới, hệ thống
 sẽ làm thích nghi hành vi đã lưu trữ với tình huống mới.
7. Khám phá hay học không giám sát: Thay vì có mục tiêu tường minh, hệ khám phá
 liên tục tìm kiếm các mẫu và quan hệ trong dữ liệu nhập. Các ví dụ về học không
 giám sát bao gồm gom cụm dữ liệu, học để nhận dạng các đặc tính cơ bản như
 cạnh từ các điểm ảnh.
 Artificial Intelligence Nguyễn Đình Cường111
 MÁY HỌC
Ví dụ
• Hệ MYCIN
• Mạng Neural nhân tạo
• Thuật toán học Quinland
• Bài toán nhận dạng
• Máy chơi cờ carô, cờ tướng
Artificial Intelligence Nguyễn Đình Cường112
 MÁY HỌC
 THUẬT GIẢI Quinlan
• Là thuật toán học theo quy nạp dùng luật, đa mục tiêu.
• Do Quinlan đưa ra năm 1979.
• Ý tưởng: Chọn thuộc tính quan trọng nhất để tạo cây quyết định.
• Thuộc tính quan trọng nhất là thuộc tính phân loại Bảng quan sát thành các
 bảng con sao cho từ mỗi bảng con này dễ phân tích để tìm quy luật chung.
 Artificial Intelligence Nguyễn Đình Cường113
 MÁY HỌC
 THUẬT GIẢI A. Quinlan
 STT Size Nationality Family Conclusion
 1 Small German Single A
 2 Large French Single A
 3 Large German Single A
 4 Small Italian Single B
 5 Large German Married B
 6 Large Italian Single B
 7 Large Italian Married B
 8 Small German Married B
Artificial Intelligence Nguyễn Đình Cường114
 MÁY HỌC
Xét vector V: có số chiều bằng số phân loại
 • V(Size=Small) = (ASmall, BSmall)
 • ASmall=Số quan sát A có Size là Small / Tổng số quan sát có Size=Small
 • BSmall= Số quan sát B có Size là Small / Tổng số quan sát có Size=Small
 • V(Size=Small) = (1/3 , 2/3)
 • V(Size=Large) = (2/5 , 3/5)
Với thuộc tính Nationality Chọn thuộc tính có nhiều 
 • V(Nat = German)= (2/4 , 2/4) vecto đơn vị
 • V(Nat = French) = (1 , 0)
 • V(Nat = Italian) = (0 , 1)
Thuộc tính Family:
 • V(Family=Single) = (3/5 ,2/5)
 • V(Family = Married) = (0, 1)
Artificial Intelligence Nguyễn Đình Cường115
 MÁY HỌC
 VỚI MỖI THUỘC TÍNH CỦA BẢNG QUAN SÁT
Chỉ còn xét German
•Thuộc tính Size: 
 V(Size=Small) = (1/2 , 1/2)
 V(Size=Large) = (1/2 , 1/2)
•Thuộc tính Family:
 V(Family=Single) = (1, 0)
 V(Family=Married) = (0,1) 
 Artificial Intelligence Nguyễn Đình Cường116
 MÁY HỌC
Artificial Intelligence Nguyễn Đình Cường117
 MÁY HỌC
 Thuật giải Học theo độ bất định
Artificial Intelligence Nguyễn Đình Cường118
 MÁY HỌC
Artificial Intelligence Nguyễn Đình Cường119
 MÁY HỌC
Artificial Intelligence Nguyễn Đình Cường120
 MÁY HỌC
 Đừng tưởng xuân tàn hoa rụng hết
 Đêm qua sân trước một nhành mai
Artificial Intelligence Nguyễn Đình Cường121
 TRƯỜNG ĐẠI HỌC NHA TRANG
 Bài giảng 
 TRÍ TUỆ NHÂN TẠO
 NGUYỄN ĐÌNH CƯỜNG
 Bộ môn Công Nghệ Phần Mềm
 Khoa Công Nghệ Thông Tin
 Nha trang - 2012
Artificial Intelligence Nguyễn Đình Cường122
Artificial Intelligence Nguyễn Đình Cường123
Artificial Intelligence Nguyễn Đình Cường124
Artificial Intelligence Nguyễn Đình Cường125
Artificial Intelligence Nguyễn Đình Cường126
Artificial Intelligence Nguyễn Đình Cường127
Artificial Intelligence Nguyễn Đình Cường128
Artificial Intelligence Nguyễn Đình Cường129
Artificial Intelligence Nguyễn Đình Cường130
Artificial Intelligence Nguyễn Đình Cường131
Artificial Intelligence Nguyễn Đình Cường132
Artificial Intelligence Nguyễn Đình Cường133
Cách biên dịch:
C:\opencv\sources\samples\cpp>cl /I C:\opencv\build\include neural_network.cpp /link 
opencv_world341d.lib opencv_world341.lib
Artificial Intelligence Nguyễn Đình Cường134
Artificial Intelligence Nguyễn Đình Cường135
[1] Neural network, Raul Rojas, 1996.
[2] Neural network, David Kriesel, 2005
[3] Bài Giảng Trí Tuệ Nhân Tạo, Nguyễn Đình Thuân-Đại học Nha Trang.
[3] Opencv Lib
Artificial Intelligence Nguyễn Đình Cường136
 View publication stats