Bài giảng Trí tuệ Nhân tạo - ĐH KTCN TP.HCM

t hoặc đạt trạng thái cân bằng. Ví dụ sau minh họa trường hợp đầu. Ví dụ 10.1 Cho mạng neuron với 6 neuron x1, x2, a, b, c và y, trong đó x1, x2 là các neuron input còn y là neuron output. Ngưỡng θ và trọng w được cho trong các bảng neuron a b c y θ 0.3 -0.6 0.5 -0.1 a b c y x1 -0.5 0.4 0.4 x2 0.4 0.3 0.5 a 0.2 0.3 b 0.2 c -0.4 Dùng hàm chuyển ⎩⎨ ⎧ <− ≥= θ θ x x xS 1 1 )( Hãy xác định tín hiệu ra khỏi các neuron a, b, c và y, biết tín hiệu ra khỏi x1, x2 là -1 và 1 Giải: Vẽ cây y b a c x0 x1 x2 -0.1 -0.6 0.3 0.5 -0.5 0.4 0.4 0.4 0.3 0.5 0.2 0.3 0.2 -0.4 Tính toán a = S(-0.3 + 0.5 +0.4) = 1 b = S(0.6 – 0.4 + 0.2) = 1 c = S(-0.5 – 0.4 + 0.3) = -1 y = S(0.2 +0.1 +0.3 + 0.5 + 0.4) = 1 Vậy y = 1. (c) Học Coi mạng là mô hình f Â(W, θ, x) của hàm f(x). Bài toán học là xác định W và θ từ tập mẫu. Có hai kiểu học: 1. Học giám sát (có thầy): tập mẫu dạng {(xk, yk)} 2. Học không giám sát (không có thầy): tập mẫu dạng {xk} 1.2. Giới thiệu một số luật học (a) Luật học Hebb Hebb (1949), dựa trên những thí nghiệm của mình, đã giả thiết là khi neuron x liên tục truyền tín hiệu đến neuron y thì sẽ làm tăng trọng synapse giữa chúng. Ta có Δwxy = α ax ay trong đó α là hằng số học, ax là giá trị của neuron x, Association Memory (bộ nhớ kết hợp) Mô hình y = S(Wx) ⎩⎨ ⎧ <− ≥= 01 01 )( x x xS Luật học ΔW = yxT Hoạt động (là quá trình lặp) y0 = S(Wx0) xn = S(WTyn-1), yn = S(Wxn) y = y* = f Â(x) = S(Wx*) Ví dụ 10.2 Xét ánh xạ f: {0, 1, , 7} → {0, 1, 3}, biết xi 1 3 yi = f(xi) 0 1 Ta xây dựng mạng như sau: gồm 3 nút a, b, c nối đầy đủ với 2 nút u, v. a u b v c Bộ ba (a, b, c) sẽ mã hoá các giá trị từ 0 đến 7, chẳng hạn 5, có biểu diễn nhị phân là 101, sẽ được mã hoá với a = c = 1 và b = -1; cũng vậy cặp (u, v) sẽ mã hoá các số nguyên từ 0 đến 4. Quá trình học, bắt đầu với W = 0, ta cập nhật ΔW cho mỗi lần học cặp tín hiệu mẫu. Với (1, 0), ta có W: -1 a (1, 1, -1) u -1 -1 b (1, 1, -1) v -1 1 c Tiếp theo, với cặp (3, 1), W lúc này là -1 a (2, 0,-2) u -1 1 b (0, 2, 0) v 1 1 c ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −= 020 202 W Cho mạng hoạt động, trước hết kiểm tra kết quả học: Với x = 1, ta có (-1, -1, 1)T → (-1, -1)T→ (-1, -1, 1)T suy ra y = 0, khớp; Với x = 3, ta có (-1, 1, 1)T → (-1, 1)T→ (-1, 1, 1)T suy ra y = 1, khớp. Tìm f(x) Với x = 7, ta có (1, 1, 1)T → (1, 1)T→ (1, 1, -1)T → (1, 1)T, mạng ổn định ở trạng thái (6, 3) (nói theo thuật ngữ phân loại, mạng xếp 6 và 7 cùng nhóm) Với x = 4, ta có (1, -1, -1)T → (1, -1)T→ (1, -1, -1)T, mạng ổn định ở (4, 2) (b) Học bằng cách sửa lỗi Rosenblatt (1958), dựa trên các tính toán của mình, đã đưa ra luật học Δwxy = α ax ey trong đó α là hằng số học, ey = dy – ay là sai số giữa giá trị chờ đợi d và giá trị của neuron y. Trong một chu kỳ học, chúng ta hy vọng tổng lỗi sẽ giảm để có thể đạt đến giá trị bé nhất. Luật học này được Rosenblatt sử dụng trong mạng perceptron sau đây. Mạng Perceptron Mô hình y = S(Wx – θ) ⎩⎨ ⎧ <− ≥= 01 01 )( x x xS Luật học (là quá trình lặp cho đến khi cực tiểu sai số). Δwxy = α ax ey Δθx = -α ex Hoạt động y = f Â(x) = S(Wx – θ)) Ví dụ 10.3 Cho mạng với 3 neuron a, b, c. Giả sử a nối c trọng wac = 1 và b nối c trọng wbc = -3. tại c ngưỡng θc = 2. Với α= 0.5, hãy xác định trọng và ngưỡng của mạng sau khi học mẫu (a, b, c) = (1, -1, -1) và kiểm tra kết quả học. Giải: Mạng trước khi học c 1 1 -3 a b Tính y: (1, -1) → 1 = y và e = d – y = (-1) – 1 = -2; Cập nhật: wac = 1 + 0.5 × 1 × (-2) = 0; wbc = -3 + 0.5 × (-1) × (-2) = -2; θc = 2 – 0.5*(-2) = 3. Mạng sau khi học c 3 0 -2 a b Kiểm tra kết quả học, (1, -1) → -1 và sai số ec = 0. Mạng Back propagation Mô hình y = S(Wx, θ) ae aS −+= θθ 1 1),( Luật học (là quá trình lặp cho đến khi sai số cực tiểu). Δwxy = α ay (1 – ay) ax ey Δθx = -α ax (1 – ax) ex Trong đó α là hằng số học, ax là tín hiệu từ neuron x, Hoạt động y = f Â(x) = S(Wx, θ)) (c) Competitive Tích wTx khi x và w được chuẩn hoá cho ta biết sự gần nhau giữa chúng, cụ thể wTx càng lớn thì x và w càng gần nhau. Điều chỉnh w = w + α(x – w) làm w gần x hơn. Tiếp cận này chỉ có một neuron chiến thắng được xem xét. Kohonen (1982) đưa ra luật học competitive như sau Mô hình yk = max i (wiTx) Luật học (là quá trình lặp cho đến khi sai số cực tiểu). Δwxk = α (x – wk ) Hoạt động yk = max i (wiTx) 2. Thuật toán di truyền 2.1. Khái niệm Trong tự nhiên, những cá thể yếu sẽ bị đào thải. Tự nhiên có khuynh hướng giữ lại các thể có khả năng thích nghi cao. Công việc này được thực hiện qua lai tạo, đột biến và chọn lọc. Với tiếp cận này, thay vì đi tìm phương án tối ưu, chúng ta tìm một tập các phương án có chứa phương án tối ưu. Mỗi phương án được gọi là cá thể, tập các phương án đang xét được gọi là quần thể. Mỗi cá thể có một độ thích nghi riêng; những cá thể có độ thích nghi cao sẽ có xác suất tồn tại lớn. Mỗi cá thể được biểu diễn bằng một chuỗi các nhiễm sắc thể. Sau mỗi bước thuật toán ta có một thế hệ quần thể mới. Thế hệ mới được tạo ra từ các cá thể của thế hệ cũ nhờ lai tạo, đột biến và chọn lọc. 1 Phép chọn lọc được thực hiện qua hàm thích nghi, qua đó tính được khả năng tồn tại của cá thể. 2 Phép đột biến dựa trên việc thay đổi một số nhiễm sắc thể được chọn một cách ngẫu nhiên. 3 Phép lai tạo giữa hai cá thể là sự trộn lẫn nhau giữa các nhiễm sắc thể của chúng. Ví dụ 10.4 Giả sử một cá thể gồm có 6 nhiễm sắc thể và chỉ có hai loại nhiễm sắc thể là 0 và 1, ta có: Đột biến (100100) → (101100) Lai tạo (1001⏐10) → (1001⏐01) (1011⏐01) (1011⏐10) 2.2. Mô hình và Thuật toán (a) Mô hình Trong mô hình này, nhiễm sắc thể gồm có 2 loại là 0 và 1; cá thể là một xâu bit; hàm thích nghi là một hàm dương và được ký hiệu là f (fitness). Chúng ta có một phân bố xác suất chọn cho quần thể; xác suất lai pc, cho biết tỉ lệ các cá thể tham gia lai tạo; và xác suất đột biến pm, của nhiễm sắc thể bất kỳ. Công thức tính xác suất chọn: Giả sử quần thể gồm n cá thể được liệt kê từ x1 đến xn, ta có xác suất chọn cá thể thứ k cho bởi: ∑==== ki i k kk xf xfxxpp 1 )( )()( Thủ tục chọn lọc: Coi ∑== ki kpkF 1)( , F(0) = 0. Tạo một số ngẫu nhiên q giữa 0 và 1, nếu q nằm giữa F(k-1) và F(k) thì cá thể xk được chọn. Thủ tục lai tạo: Xét cá thể x, tạo một số ngẫu nhiên giữa 0 và 1, nếu số này bé hơn pc, đưa cá thể này vào nhóm lai tạo. Xét 2 cá thể trong nhóm lai tạo, chọn ngẫu nhiên một vị trí, thực hiện thao tác lai tại vị trí này. Thủ tục đột biến: Xét cá thể x, với mỗi nhiễm sắc thể của x, tạo một số ngẫu nhiên giữa 0 và 1, nếu số này bé hơn pm, đột biến nhiễm sắc thể này. (b) Thuật toán 1. Khởi tạo quần thể ban đầu 2. Tính phân bố xác suất chọn cho quần thể 3. Lặp 3.1. Chọn lọc 3.2. Lai tạo 3.3. Đột biến 3.4. Tính phân bố xác suất chọn cho quần thể (c) Minh họa Ví dụ 10.5 Giả sử cá thể gồm 4 nhiễm sắc thể 0, 1. Độ thích nghi f bằng 5 cộng cho hiệu của số nhiễm sắc thể 1 trừ cho số nhiễm sắc thể 0. Xét quần thể ban đầu x 1101 1100 0111 0001 f 7 5 6 3 p 7/21 5/21 6/21 3/21 F 7/21 12/21 18/21 1 Tạo 4 số ngẫu nhiên (giả sử 0.2, 0.4, 0.3 và 0.6) ta có kết quả sau chọn lọc: x 1101 1100 1101 0111 Với xác suất lai pc = 0.5, ta sẽ chọn ra 1 cặp. Tạo 4 số ngẫu nhiên (giả sử 0.6, 0.4, 0.3 và 0.7), chọn được 1101 và 0111. Tiếp, chọn ngẫu nhiên 1 vị trí lai (giả sử 1), ta được 2 cá thể mới 0101 và 1111. Kết quả sau lai tạo: x 0101 1100 1101 1111 Với xác suất đột biến pm = 0.1, ta hy vọng có 1.6 ~ 2 nhiễm sắc thể sẽ được đột biến. Tạo 16 số ngẫu nhiên (giả sử chỉ có các số thứ 3 và thứ 8 bé hơn 0.1). Ta đột biến bit 3 của cá thể 1 và bit 4 của cá thể 2. Kết quả ta được quần thể mới: x 0111 1101 1101 1111 f 7 7 7 9 p 7/30 7/30 7/30 9/30 F 7/30 14/30 21/30 1 Có thể nhận thấy khả năng thích nghi của quần thể mới cao hơn quần thể cũ. 3. Xử lý ràng buộc 3.1. Khái niệm Nhiều bài toán mà lời giải là một tập hợp các biến sẽ nhận giá trị trong một miền nào đó và thoả mãn một số ràng buộc (Constraint Satisfaction Problem -CSP). Thường thì lời giải cần đạt đến phải tối ưu một hàm mục tiêu nào đó. f(x1, , xn) → min/max sao cho xj ∈ Dj và thoả tập ràng buộc C Ví dụ 10.6 Xét bài toán đoán chữ S E N D + M O R E = M O N E Y. Các ký tự nhận các giá trị đôi một khác nhau. Gọi c0, c1, c2, c3 là các cờ nhớ (nhận trị là 0 hoặc 1) tương ứng từ hàng đơn vị trở đi, ta viết bài toán dưới dạng quen thuộc: S E N D c3 c2 c1 c0 + M O R E M O N E Y Các ràng buộc gồm: }1,0{ }9,...,2,1,0{,,,,, }9,...,2,1{, )( )(O10 )(10 )(10 )(10 53 432 321 210 10 ∈ ∈ ∈ = +=++ +=++ +=++ +=+ jc YRODNE MS rMc rcMcS rNcOcE rEcRcN rYcED Ví dụ 10.7 Bài toán tô màu bản đồ { }⎪⎩ ⎪⎨ ⎧ ∈ =∑ ∑ ∑ ∈ 1,0 1 min ),( ij j ij j Eli ljij x x xx Trong đó xij nhận trị 1 khi và chỉ khi đỉnh i và đỉnh j là kề nhau và có màu giống nhau. Trong tiếp cận này các ràng buộc được xem xét để thu hẹp miền giá trị của các biến. Ta minh họa cách xử lý ràng buộc qua hai ví dụ sau. Ví dụ 10.8 Tô màu bản đồ sau, tập các số tại mỗi đỉnh là các màu hợp lệ của đỉnh. Các ràng buộc là các cung, theo đó 2 đỉnh kề nhau phải có màu khác nhau. Xử lý các ràng buộc (e, a), (e, b), (e, c) và (e, d). Thu hẹp miền giá trị. Xử lý các ràng buộc (b, a), (b, c), và (b, d). Thu hẹp miền giá trị. Và bài toán là không giải được Ví dụ 10.9 Một biến thể của trò chơi Sudoku nổi tiếng có xuất xứ từ Nhật. Đặt các số từ 1 đến 4 vào bảng kích thước 4×4 (gồm 4 ô lớn kích thước 2×2, xem hình) sao cho mỗi dòng, mỗi cột và mỗi ô lớn đều có đủ 4 số này. Chúng ta có tất cả 12 ràng buộc: 4 cho dòng d1, d2, d3, d4; 4 cho cột c1, c2, c3, c4; và 4 cho ô o1, o2, o3, o4. Xét trò chơi với tập giá trị của mỗi ô như sau: 1 1, 2, 3, 4 1, 2, 3, 4 1, 2, 3, 4 1, 2, 3, 4 3 1, 2, 3, 4 1, 2, 3, 4 1, 2, 3, 4 2 1 1, 2, 3, 4 1, 2, 3, 4 1, 2, 3, 4 1, 2, 3, 4 1, 2, 3, 4 Xử lý các ràng buộc d1, d2, d3, c1, c2, c3, o1, o3, o4. Thu hẹp miền giá trị. 1 4 2, 3, 4 2, 3, 4 2, 4 3 2, 4 1, 2, 4 3, 4 2 1 3, 4 3, 4 1, 4 2, 3, 4 2, 3, 4 Xử lý các ràng buộc d1, c2, o1. Thu hẹp miền giá trị. 1 4 2, 3 2, 3 2 3 2, 4 1, 2, 4 3, 4 2 1 3, 4 3, 4 1 2, 3, 4 2, 3, 4 Xử lý các ràng buộc d2, d4, c1, c2, o1, o4. Thu hẹp miền giá trị. 1 4 2, 3 2, 3 2 3 4 1, 4 3, 4 2 1 3, 4 3, 4 1 2, 3, 4 2, 3, 4 Xử lý các ràng buộc d2, c3, o2. Thu hẹp miền giá trị. 1 4 2, 3 2, 3 2 3 4 1 3, 4 2 1 3, 4 3, 4 1 2, 3 2, 3, 4 Giờ đây áp dụng phương pháp giải quyết vấn đề (chẳng hạn tìm kiếm) ta dễ dàng tìm thấy một lời giải. 3.2. Thuật giải (a) Những nét chính Một số heuristic được sử dụng 1 Bậc của đỉnh (ràng buộc nhiều nhất) 2 Giá trị chọn ít nhất Bổ sung một số tính toán đặc thù của bài toán giúp cây tìm kiếm gọn nhất. Định nghĩa 10.1 Cung (a, b) được gọi là vững chắc nếu mọi giá trị khả dĩ của a đều có một giá trị khả dĩ của b. Thuật toán: Thủ tục xử lý cung không vững chắc Vào: cung (a, b) Ra: có thu hẹp miền giá trị của a 1 Gán removed = false 2 Với mỗi x thuộc miền giá trị của a, nếu không có giá trị y nào thuộc miền giá trị của b thoả mãn ràng buộc giữa a và b thì 2.1 Loại x khỏi miền giá trị của a 2.2 Gán removed = true 3 Return removed (b) Thuật giải cung chắc chắn Giống như alpha-beta, thuật giải này tiả nhánh để giảm sai lầm khi gán trị cho biến. Nhờ đó mà quá trình gán trị không phải truy ngược nhiều. Thuật giải 7: thuật giải cung chắc chắn 1 Chọn một ràng buộc và lưu lại trong S 2 Nếu S khác rỗng, lấy khỏi S một ràng buộc đã lưu 2.1 Thực hiện thủ tục xử lý cung không vững chắc 2.2 Nếu có sự thay đổi thì với mỗi biến bị thay đổi miền giá trị, lưu tất cả các ràng buộc liên quan 3 Nếu không chọn được biến để gán trị thì return false 4 Gán trị cho biến, nếu còn biến vẫn chưa được gán trị thì quay về bước 1 5 Return true Ví dụ 10.10 Xét bài toán tô màu bản đồ ở ví dụ trên, tập giá trị ban đầu của các đỉnh là a b c d e 1,2,3 2,3 1,2,3 1,2 3 giả sử xét cạnh (b, e) (b, e) b = 2 (a, b) a = 1, 3 (c, b) c = 1, 3 (d, b) d = 1 (e, a) a = 1 (c, a) c = 3 (a, c) (b, c) (e, c) xung đột! Ví dụ 10.11 Xét bài toán đoán số trong ví dụ trên, tập giá trị ban đầu là S E N D M O R Y c3 c2 c1 c0 1..9 0..9 0..9 0..9 1..9 0..9 0..9 0..9 0,1 0,1 0,1 0,1 1 Xét ràng buộc r5 (r5 : M=c3) M=c3=1 (r4 : S+c2+1=O+10) S=8,9; O=0 (r3 : E+c1=N+10c2) c1=1; c2=0 (r4 : S+1=10) S=9 (r2 : N+c0+R=E+10) N=3..8; E=2..7 (r3 : E+1=N) (r1 : D+E=Y+10c0) S E N D M O R Y c3 c2 c1 c0 9 2..7 3..8 2..8 1 0 2..8 2..8 1 0 1 0,1 Vì đặc trưng của bài toán, bổ sung ràng buộc r6 (nếu không có ràng buộc này cũng không sao, khi ấy cây tìm kiếm sẽ có nhiều nhánh hơn thôi) c0 + 1 + R = 10 2 Xét ràng buộc r6 (r6 : c0+1+R=10) c0=1; R=8 (r2 : N+9=E+10) (r1 : D+E=Y+10) D=6,7; E=5,6; Y=2,3 (r3 : E+1=N) N=6,7 (r2 : N+9=E+10) (r2 : N+9=E+10) S E N D M O R Y c3 c2 c1 c0 9 5,6 6,7 6,7 1 0 8 2,3 1 0 1 1 3 Xét ràng buộc r3 với 2 khả năng cho E. Xét khả năng E=5, và để khả năng còn lại cho cây tìm kiếm, ta có: (r3 : E+1=N) E=5; N=6 (r2 : N+9=E+10) (r1 : D+5=Y+10) D=7; Y=2 Và tất cả các ràng buộc đều thỏa S E N D M O R Y c3 c2 c1 c0 9 5 6 7 1 0 8 2 1 0 1 1 Minh họa cây tìm kiếm M=1; S=9; O=0; c3=1; c2=0; c1=1 R=8; c0=1 E=5; N=6; D=7; Y=2 E=6; Như vậy với sự trợ giúp của thuật giải cung chắc chắn, cây tìm kiếm của chúng ta hết sức gọn nhẹ 4. Máy vector hỗ trợ (Supported Vector Machine - SVM) 4.1. Khái niệm Xét bài toán tách tuyến tính hai nhóm đối tượng sau: + + – – + – Ta có thể giải dễ dàng bằng cách dùng mạng perceptron. Tuy nhiên, vấn đề nằm ở chỗ có rất nhiều lời giải và ta muốn tìm lời giải tốt nhất theo nghĩa sau: + + – – + – Siêu phẳng lời giải nằm ở tâm của hành lang có độ rộng cực đại. Ta cũng quan sát thấy các vector hỗ trợ nằm ở hai lề của hành lang. Bài toán ( ){ 1 min 2 1 ≥+ → bxwy ww iT i T Trong đó wTx + b = 0 là phương trình của siêu phẳng và yi là dấu của nhóm mà xi thuộc vào. 4.2. Thuật toán 1. Giải bài toán đối ngẫu ⎩⎨ ⎧ ≥ = →− 0 0 min 2 1 α α ααα T TT y eM Trong đó M = XTX, X = (y1x1, y2x2, , ymxm), eT = (1, 1, , 1) 2. Tính w = Xα 3. Tính b = 1/yi – wTxi tại một αi > 0. Ví dụ 10.12 Tách tuyến tính bằng SVM với nhóm (+) gồm duy nhất x1= (0, 0)T và nhóm (–) cũng gồm duy nhất x2 = (1, 0)T. Giải: Tính ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −= 00 10 X suy ra ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛== 10 00 XXM T bài toán đối ngẫu ⎩⎨ ⎧ ≥ =− →−− 0, 0 min 2 1 21 21 21 2 2 αα αα ααα có nghiệm tối ưu là α = (2, 2)T Suy ra w = Xα = (-2, 0)T và b = 1 – wTx1 = 1 Vậy siêu phẳng tách là -2x1 + 1 = 0, tức x1 = 1/2. 4.3. Tách phi tuyến (a) Ý tưởng Ta sẽ tìm phương trình đường cong tách dạng bxxybxw k k kk T +=+ ∑ )()()( φφαφ Trong đó φ là phép biến đổi chuyển sang không gian mới và zk = φ(xk) trong tổng trên là các vector hỗ trợ trong không gian mới. Phương trình cũng chính là siêu phẳng tách trong không gian mới. và dấu của bxxKybxxy k k kk k k kk +=+ ∑∑ ),()()( αφφα sẽ quyết định nhóm của x Ví dụ 10.13 Đường liền nét d(x) là đường cong tách, đường đứt nét là kết quả phân nhóm. (b) Thuật toán Bài toán ( ){ 1)( min 2 1 ≥+ → bxwy ww iT i T φ Thuật toán tính α và b 1. Giải bài toán đối ngẫu ⎩⎨ ⎧ ≥ = →− 0 0 min 2 1 α α ααα T TT y eM Trong đó M = (mij) với mij = yiyjφ(xi)Tφ(xj) 2. Tính b = 1/yi – ΣykαkK(xk,xi) tại một αi > 0. (c) Minh họa Chúng ta không đưa ra các tính toán mà chỉ cho thấy hiệu quả của tiếp cận. Ví dụ 10.14 Chọn φ(x) là có các thành phần đa thức bậc từ 2, ta có K(x, y) = (xy + 1)2 Ta có thể thấy các vector hỗ trợ. Ví dụ 10.15 Chọn φ(x) có 2 2 2)()(),( σφφ yx T eyxyxK −−== Minh họa trường hợp σ lớn Minh họa trường hợp σ nhỏ BÀI TẬP Mạng neuron Bài tập 10.1 c a b -1 x2x1 Cho mạng (hình) với : θa = -0.4 w1a = 0.2 w2a = -0.2 θb = 0.3 w1b = -0.5 w2b = 0.2 θc = 0.1 wac = -0.3 wbc = 0.5 Giả sử tín hiệu của neuron là ±1 và luật học kiểu perceptron với α = 0.2, hãy xác định 1. Tín hiệu ra của a, b, c khi x1 =1, x2 = -1 2. Sai số truyền về a, b khi sai số ở c là –2 3. Các giá trị trọng và ngưỡng của neuron a nếu sai số mà nó nhận được là 0.2 Bài tập 10.2 Cho mạng ca b -1 x2x1 trong đó θa = -0.4, w1a = 0.2, w2a = -0.2; θb = 0.3, w1b = -0.5, w2b = 0.2; θc = 0.1, wac = -0.3, wbc = 0.5. Dùng luật học perceptron với α = 0.2, hãy xác định: 1. Tín hiệu ra của các neuron a, b, c khi x1 =1, x2 = -1 2. Sai số truyền về a, b khi sai số ở c là –2 Bài tập 10.3 Cho mạng neuron loại bộ nhớ kết hợp với 3 neuron vào và 2 neuron ra. Biết ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − − = 01 23 12 W Xét cặp mẫu x(1, 1, -1), y(-1 1) 1. Tính W sau khi mạng học xong cặp mẫu trên 2. Kiểm tra kết quả học Bài tập 10.4 Phép AND cho bởi x1 x2 y 0 0 0 0 1 1 1 0 1 0 0 1 Xây dựng mạng perceptron: 1. Tạo mạng: cấu trúc, các giá trị trọng và ngưỡng ban đầu sao cho sai số chỉ xảy ra ở dòng 2; 2. Chọn hệ số học thích hợp sao cho không quá 2 chu kỳ học, mạng không còn sai số nữa. Bài tập 10.5 Biểu diễn các chữ cái L, T và I bằng ma trận 3×3 các số –1 và 1. Xây dựng hệ nhận dạng dùng bộ nhớ kết hợp: 1. Chọn số neuron output, xác định luật kết hợp, tính ma trận W; 2. Kiểm tra kết quả học (nếu không khớp, làm lại câu 1); 3. Làm nhiễu chữ T, kiểm tra xem mạng nhận dạng chữ này thành chữ gì? Thuật toán di truyền Bài tập 10.6 Làm lại ví dụ 5, vẫn dùng lại các tham số, kể cả các số ngẫu nhiên; chỉ thay đổi độ thích nghi: f bằng 5 cộng cho 2 lần số nhiễm sắc thể 0 trừ cho số nhiễm sắc thể 1 Bài tập 10.7 Xét bài toán tối ưu g = x2 → min trên đoạn [–1, 1]. 1. Chia đoạn [–1, 1] thành 15 khoảng đều nhau bởi phép chia x0 = -1 < x2 < < x15 = 1. a. Biểu diễn xk bằng biểu diễn nhị phân của k, ví dụ x3 = 0011; b. Coi độ thích nghi bằng f = 1 + g, ví dụ f(0011) = 1 + g(x3) = 1 + g(- 4/5) = 41/25. Tính f cho tất cả 16 cá thể. 2. Biết quần thể gồm 6 cá thể, xác suất lai pc = 0.33, xác suất đột biến pm = 0.1. Hãy c. Chọn ngẫu nhiên một quần thể; d. Tính phân bố xác suất chọn; e. Tự đưa ra các số ngẫu nhiên, và xác định quần thể mới theo cách thức của thuật toán di truyền. Xử lý ràng buộc Bài tập 10.8 Giải bài toán đoán chữ, dùng biểu diễn đồ thị như sau: Bài tập 10.9 Giải bài toán điền chữ sau T A B + T O M = M A I T Bài tập 10.10 Dùng 3 màu 1, 2, 3 hãy tô màu bản đồ có 5 thành phố a, b, c, d, e. Biết biểu diễn đồ thị phẳng của nó gồm các cạnh (a,b), (a,c), (b,c), (b,d), (c,d), (c,e), (d,e) và màu hợp lệ cho a là 1, cho e là 1 hoặc 2, cho các đỉnh còn lại là 1, 2, 3. Bài tập 10.11 Cúp Tiger 98 có 4 đội lọt đến bán kết: Việt Nam, Singapor, Thái Lan và Indonesia. Trước khi thi đấu ba bạn Quang, Dũng và Tuấn dự đoán như sau: 1 Quang: Việt Nam hạng nhì, Thái Lan hạng tư 2 Dũng: Singapor hạng nhì, Thái Lan hạng ba 3 Tuấn: Singapor hạng nhất, Indonesia hạng nhì Kết quả mỗi bạn đoán đúng một đội và sai một đội Dùng một trong những phương pháp đã học cho biết kết quả đúng của mỗi đội Máy vector hỗ trợ Bài tập 10.12 Tìm siêu phẳng tối ưu, với tập ví dụ thuận (+) chỉ gồm 1 phần tử x1 = (1, 1)T, và tập ví dụ nghịch (-) cũng chỉ gồm 1 phần tử x2 = (-1, 0)T. Bài tập 10.13 Tìm siêu phẳng tối ưu, với tập mẫu huấn luyện sau: Ví dụ Biểu diễn Lớp x1 (0, 1)T + x2 (0, 0)T – x3 (-1, 0)T – x4 (2, 0)T + x5 (2, -1)T – Yêu cầu: 1. Huấn luyện đủ 5 ví dụ; 2. Vẽ hình, chọn 2 vector hỗ trợ, giải và thử lại. Phụ lục 2 Ngôn ngữ Prolog 1. Giới thiệu prolog 1.1. Các thành phần của chương trình • Miền giá trị domains • Vị từ predicates • Cơ sở dữ liệu quan hệ database • Mệnh đề clauses • Đích goal • Chú thích % hoặc /**/ 1.2. Sự kiện và luật Tất cả đều được mô tả thông qua vị từ, chẳng hạn với vị từ p(integer) thì • Các sự kiện có thể là p(1), p(3), • Các luật có thể là p(X) if Ví dụ 2.1 Bài toán tìm đường đi: predicates road(symbol, symbol) %để định nghĩa cung route(symbol, symbol) %để định nghĩa đường đi clauses /*các sự kiện*/ road(n,c). road(c,d). road(n,t). road(n,d). road(t,g). road(t,l). road(t,c). road(d,u). road(d,h). road(h,l). road(d,l). /*luật*/ route (X,Y) if road(X,Y); road(X,Z), route(Z,Y), goal route(n,l) 1.3. Quan hệ (a) Định nghĩa Cho quan hệ, chẳng hạn r( A B) a 1 b 2 a 3 là tập con của tập tích nên r ở đây có thể mô tả tường minh bằng cách liệt kê các phần tử của nó hoặc mô tả ẩn thông qua một vị từ nào đó. Ví dụ 2.2 Xét quan hệ đơn giản sau r(A) 1 2 3 4 • Liệt kê predicates r(integer) clauses r(1). r(2). r(3). r(4). • Dùng vị từ (chỉ để kiểm tra xem số n có thuộc r không) predicates r(integer) clauses r(1). r(X):-Z=X-1, Z=0, r(Z). (b) Thao tác Ví dụ 2.3 Cho các quan hệ r, s, r1, r2 như sau predicates r(integer) s(integer, integer) r1(integer) r2(integer) clauses r(1). r(2). r(3). r(4). s(1, a). s(1, b). s(2, a). r1(X):-r(X), X<4. r2(X):-r(X), X>1. Thực hiện các phép toán đại số quan hệ Hội: r1(X); r2(X), not(r1(X)). Giao: r1(X), r2(X). Hiệu: r1(X), not(r2(X)). Bù: r(X), not(r1(X)). Tích: r1(X), r2(Y). Chọn: s(1,X). Chiếu: s(_,X). Kết tự nhiên: r(X), s(X,Y). Kết theta: r(X), s(Z,Y), X<Z. 1.4. Các kiểu đối tượng (a) Chuẩn Kiểu ví dụ char ‘a’ integer (2byte) 258 real (6 byte) 2.56 string “Hello” symbol hello hoặc “hello” (b) Danh sách Ký hiệu [H|T] là một danh sách gồm hai phần H: Head và T: Tail. Dùng con trỏ khai báo kiểu danh sách. Ví dụ 2.4 Sắp xếp một danh sách các số nguyên domains intlist = integer* predicates sort(intlist, intlist) insert(integer, intlist, intlist) clauses insert(X,[],[X]). insert(X,[H|T],L):- X<=H, L = [X|[H|T]]. insert(X,[H|T],L):- X>H, insert(X,T,L1), L = [H|L1]. sort([H],[H]). sort([H|T],X):- sort(T,Y), insert(H,Y,Z), X = Z. Minh họa sort([1,3,2],X false sort([3,2],Y) insert(1,Y,Z) X=Z false sort([2],Y1) insert(3,Y1,Z) Y=Z sort([2],[2]) (c) Kiểu dữ liệu phức hợp Ví dụ 2.5 Minh họa cây nhị phân • Định nghĩa cây nhị phân và vị từ prints domains treetype = tree(string, treetype, treetype) ; empty() predicates prints(treetype) clauses prints(empty). prints(tree(X, Y, Z)) :- write(X), nl, prints(Y), prints(Z). • Tạo và in một đối tượng kiểu cây nhị phân như sau goal prints(tree("Cathy", tree("Michael", tree("Charles", empty, empty), tree("Hazel", empty, empty) ), tree("Melody", tree("Jim", empty, empty), tree("Eleanor", empty, empty) ) ) ). • Một số thao tác mới rất cần được định nghĩa thêm: chẳng hạn bổ sung vị từ search để tìm cây con dựa vào thông tin của đỉnh. predicates search(string, treetype, treetype) clauses search(_, empty(), empty()):-fail. search(S, tree(S,L,R), tree(S,L,R)). search(S, tree(_,L,_), X):-search(S,L,X). search(S, tree(_,_,R), X):-search(S,R,X). • Bây giờ nếu đích cũ được đưa vào vị từ init(treetype) thì một ví dụ áp dụng có thể là goal init(X), search(“Hazel”, X, Y), prints(Y). 1.5. Cơ chế tìm kiếm Là cơ chế hợp nhất, truy ngược và quay lui • Hợp nhất: thay giá trị cụ thể cho các biến của vị từ để đuợc mệnh đề có chân trị đúng (true). • Truy ngược: đến đích gần nhất khi gặp mệnh đề có chân trị sai (false) • Quay lui: khi gặp mệnh đề có chân trị đúng (true) Ta sẽ minh họa cơ chế này qua hai ví dụ sau Ví dụ 2.6 Cho các sự kiện và luật predicates p(symbol, symbol) q(symbol, symbol) clauses p(n,c). p(c,t). p(c,d). p(n,d). q (X,Y):- p(X,Y); p(X,Z), q(Z,Y), goal q(n,t). • Mô tả bằng cấu trúc cây • Cơ chế tìm kiếm Đích 1: q(n, t), hợp nhất X = n và Y = t Đích 2: p(n, t), không tìm thấy trong quan hệ p. Thất bại cho nên truy ngược đến đích 3: p(n, Z) Đích 3: p(n, Z), hợp nhất Z = c. Thành công nên quay lui Đích 4: q(c, t), hợp nhất X = c, Y=t Đích 5: p(n, c), hợp nhất n = n, c = t không thành công, truy ngược đến đích 6 p(c, t) Đích 6: p(n, t), hợp nhất n = n, t = t thành công, quay lui và kết thúc quá trình tìm kiếm. Ví dụ 2.7 Tuỳ theo đích trong hay đích ngoài mà sự truy ngược là mặc định cho dù đã tìm thấy lời giải. Một nhát cắt, !, sẽ ngăn cản sự truy ngược này. Ngoài ra nếu muốn prolog truy ngược để tìm mọi lời giải thì vị từ fail trả về false sẽ ép quá trình truy ngược. Minh họa • Cho quan hệ predicates r(integer) clauses r(1). r(3). r(2). • Đích trong goal r(X), write(“X=”,X,”\n”). % một lời giải goal r(X), write(“X=”,X,”\n”), fail. % truy ngược và vét cạn các lời giải • Đích ngoài goal r(X). % prolog tự động truy ngược goal r(X), !. % nhát cắt ngăn chận truy ngược 1.6. Vài ví dụ lập trình prolog (a) Tìm đường đi domains city = symbol predicates road(city,city) route(city,city) clauses road(n,c). road(c,d). road(n,t). road(n,d). road(t,g). road(t,l). road(t,c). road(d,u). road(d,h). road(h,l). road(d,l). route (X,Y):-road(X,Y); road(X,Z), route(Z,Y), goal route(n,l). (b) Đối tượng phức domains person = person(name,address) name = name(first,last) address = addr(street,city,state) street = street(number,street_name) city, state, street_name = string first, last = string number = integer goal P1= person(name(jim,mos),addr(street(5,"1st st"),igo,"CA")), P1= person(name(_,mos),Address), P2= person(name(jane,mos),Address), write(P2). (c) Xử lý danh sách domains llist = l(list); s(symbol); i(integer); c(char); t(string) list = llist* predicates append(list, list, list) clauses append([], L, L). append([X|L1], L2, [X|L3]) :- append(L1, L2, L3) goal makewindow(1, 7, 7, "answer", 15, 0, 8, 80), append([s(likes), l([s(bill), s(mary)])], [s(bill), s(sue)],Ans), write("FIRST LIST: ", Ans), nl, nl, append([l([s("This"),s("is"),s("a"),s("list")]),s(bee)],[c('c')], Ans2), write("SECOND LIST: ", Ans2), nl. (d) database domains thing = string conds = cond* cond = string database is_a(thing, thing, conds) type_of(thing, thing, conds) false(cond) predicates run(thing) ask(conds) clauses run(Item):- is_a(X, Item, List), ask(List), type_of(ANS, X, List2), ask(List2), write("The ", Item," you need is a/an ", Ans),nl. run(_):- write("This program does not have enough "), write("data to draw any conclusions."), nl. ask([]). ask([H|T]):- not(false(H)), write("Does this thing help you to "), write(H," (enter y/n)"), readchar(Ans), nl, Ans='y', ask(T). ask([H|_]):- assertz(false(H)), fail. is_a(language, tool, ["communicate"]). is_a(hammer, tool, ["build a house", "fix a fender", "crack a nut"]). is_a(sewing_machine, tool, ["make clothing","repair sails"]). is_a(plow, tool, ["prepare fields", "farm"]). type_of(english, language, ["communicate with people"]). type_of(prolog, language, ["communicate with a computer"]). 2. Thảo luận 2.1. Biểu diễn cây Qua kinh nghiệm bản thân, với các chương trình nhỏ hoặc đơn giản, để viết vị từ mới, ta nên thực hiện qua 3 bước: • Biểu diễn vị từ dưới dạng cây AND/OR. • Để ý đến cơ chế tìm kiếm của PROLOG mà sắp xếp các đỉnh (goal) cho thích hợp. • Viết vị từ Ngoài ra ta cũng có thể hiểu được hoạt động của các vị từ qua việc biểu diễn bằng cấu trúc cây như vậy. Ví dụ 2.8 • Cấu trúc lặp Sơ đồ trên rất giống cấu trúc repeat until của ngôn ngữ pascal. Chẳng hạn nếu vòng lặp thực hiện 2 lần, ta có Minh hoạ vị từ repeat predicates repeat clauses repeat. repeat:-repeat. goal repeat, readint(X), X=0. Minh hoạ vị từ for predicates for(integer, integer) clauses for(I,I). for(I,K):- L=K+1, for(I,L). goal for(I,1), write(X), I=2. • Xét chuơng trình minh họa vị từ dowhile sau predicates dowhile p clauses while. while:- while, p. p :- readint(X), X=2. goal dowhile, fail. Biểu diễn qua 2 vòng lặp Ta không những hiểu hoạt động của các vị từ mà còn thấy nó làm việc không giống lập trình cấu trúc. Khác với repeat, ở đây dowhile không là vị từ làm việc độc lập nên khó dùng hơn repeat. Cái mà chúng ta học được ở ví dụ này là qua đó ta có thể viết một số vị từ tương tự. Ví dụ 2.9 Để viết vị từ max, ta có thể dùng biểu diễn domains intlist = integer* predicates max(intlist, integer) max(integer, integer, integer) clauses max([H|[]],H). max([H|T],X):- max(T,Y), max(H,Y,X). max(X,Y,X):-X>=Y. max(_,Y,Y). goal max([1,3,2],X) 2.2. Dùng đại số quan hệ Ví dụ 2.10 Để tìm giá trị max trên quan hệ r, từ mệnh đề (∃x∈r)(∀y∈r)(x ≥ y), ta có phép toán là r(x) – (σx<yr×r)[x]. Do đó predicates max(integer) p(integer) database r(integer) clauses r(1). r(3). r(2). p(X):- r(X), r(Y), X<Y. max(X):- r(X), not(p(X)). BÀI TẬP Bài tập 2.1 Trong 10 ví dụ nói trên, hãy 1. Cài đặt chúng 2. Viết một số đích (goal). Bài tập 2.2 Viết các vị từ thích hợp chuyển các thể hiện của quan hệ thành danh sách. Bài tập 2.3 Viết các vị từ sau và xây dựng chương trình áp dụng 1. min(X, Y, Z) theo nghĩa Z = min(X, Y) 2. min(L, M) theo nghĩa M = min(danh sách L) 3. ptb1(A, B, X, N) theo nghĩa phương trình bậc 1: AX + B = 0, X là nghiệm nếu có còn N là số nghiệm : 0, 1 hoặc 2 (tức vô số nghiệm) 4. ptb2(A, B, C, X, Y, N) theo nghĩa phương trình bậc 2: AX2 + BX + C = 0, X và Y là 2 nghiệm nếu có còn N là số nghiệm: 0, 1, 2 hoặc 3 (vô số nghiệm) Bài tập 2.4 Viết các vị từ làm việc với danh sách như tìm phần tử M trong danh sách L: search(M, L), nối hai danh sách L1 và L2 thành L: join(L1, L2, L), xoá phần tử M trong danh sách L0 thành danh sách L: del(M, L0, L). Bài tập 2.5 Định nghĩa cây nhị phân và viết các vị từ như: tìm phần tử M trong cây T search(M, T), thêm phần tử X vào cây T0 add(X, T0, T), xoá phần tử M khỏi cây T0 del(M, T0, T). Bài tập 2.6 Tìm hiểu và làm việc với các vị từ chuẩn Findall Phụ lục 3 Nghiên cứu tình huống 1. Thiết kế hướng đối tượng dùng C++ 1.1. Một thiết kế đơn giản (a) Cơ sở tri thức Sự kiện là thành phố; con đường (nối trực tiếp) là luật. class City { public: int AddRoad(City* c, int d); int AddRoad(int i, int d); static int AddRoad(int i, int j, int d); City(char c); struct Road { City* c; int d;}; CArray RoadList; static CArray CityList; char name; }; CArray City::CityList; City::City(char c){ name = c; CityList.Add(this); } int City::AddRoad(City* c, int d){ Road *r = new Road; r->c = c; r->d = d; RoadList.Add(r); return 1; } int City::AddRoad(int i, int d){ return AddRoad(City::CityList[i],d); } int City::AddRoad(int i, int j, int d){ return City::CityList[i]->AddRoad(j,d); } (b) Mô tơ suy diễn Giải quyết vấn đề bằng tìm kiếm. Cài đặt thuật toán tìm kiếm int Solve(City& s, City& g) { //open & close priority_queue,myless> open; queue close; //open <- s open.push(new Node(&s,0)); while (!open.empty()){ //n <-open Node *n = open.top(); open.pop(); //close <- n close.push(n); //n==g if (n->c->name==g.name) { Node *m = close.back(); while (m!=0){ coutc->nameg<<endl; m = m->father; } return 1; } //for m in bn(n) int k = n->c->RoadList.GetSize(); for (int i=0; i<k-1; i++) { City::Road *r = n->c->RoadList[i]; open.push(new Node(r->c,n,n->g+r->d)); } } return 0; }; Tổ chức cây tìm kiếm class Node{ public: City *c; Node *father; int g; Node(City*,Node*,int d=0); }; Node::Node(City*ic,Node*f,int d){ c = ic; father = f; g = d; } int operator<(const Node& a, const Node& b){ return a.g<b.g; } struct myless: less{ bool operator()(const Node*& x, const Node*& y) const { return x->g>y->g; } }; (c) Minh họa void main(){ City v[8]={'n','c','t','d','u','h','l','g'}; City::AddRoad(0,3,19); City::AddRoad(0,2,8); City::AddRoad(0,1,10); City::AddRoad(1,3,10); City::AddRoad(3,6,10); City::AddRoad(3,5,15); City::AddRoad(3,4,10); City::AddRoad(5,6,15); City::AddRoad(2,7,15); City::AddRoad(2,6,18); City::AddRoad(2,1,5); //tìm đường đi từ n đến l if (Solve(v[0],v[6])) cout<<"success\n"; else cout<<"fail\n"; } 1.2. Một thiết kế tổng quát (a) Cơ sở tri thức //Cơ sở tri thức class KB{ public: virtual void *Start()=0; virtual void *Goal()=0; virtual void Bn(void*,Container &)=0; virtual void Show(void*)=0; }; //Bản đồ là một cơ sở tri thức class Map: public KB{ int n, m; struct Road {int f; int t;}; typedef char City; char *Cities; Road *Roads; Road Set(int, int); public: Map(); ~Map(); virtual void *Start(); virtual void *Goal(); virtual void Bn(void*,Container &); virtual void Show(void*); }; //Tháp Hà Nội cũng là một cơ sở tri thức class HNTower: public KB{ int n; struct State {int a, b, c;}; WorkList sl; void *MakeState(int, int, int); public: HNTower(int d = 2){n=d;} ~HNTower(); virtual void *Start(); virtual void *Goal(); virtual void Bn(void*,Container &); virtual void Show(void*);}; (b) Mô tơ suy diễn class Engine{ public: virtual int Reasone(KB &)=0; virtual void Report(KB *)=0; }; //Suy diễn tiến bằng cơ chế tìm kiếm. class Search: public Engine{ struct Snote {void *State; Snote *Father;}; void MakeNote(void*,Snote*); WorkList open, close; public: ~Search(); virtual int Reasone(KB &); virtual void Report(KB*); }; (c) Hệ cơ sở tri thức //Hệ giải bài toán gồm một cơ sở tri thức và một mô tơ suy diễn. class GPSystem{ protected: KB *kb; Engine *e; public: GPSystem(); GPSystem(KB*,Engine*); virtual Solve(); }; (d) Cài đặt Cơ sở tri thức bản đồ Map::Map() { n = 8; m = 11; Cities = new char[n+1]; strcpy(Cities,"nctduhlg"); Roads = new Road[m]; Roads[0].f = 0; Roads[0].t = 3; Roads[1].f = 0; Roads[1].t = 2; Roads[2].f = 0; Roads[2].t = 1; Roads[3].f = 1; Roads[3].t = 3; Roads[4].f = 3; Roads[4].t = 6; Roads[5].f = 3; Roads[5].t = 5; Roads[6].f = 3; Roads[6].t = 4; Roads[7].f = 5; Roads[7].t = 6; Roads[8].f = 2; Roads[8].t = 7; Roads[9].f = 2; Roads[9].t = 6; Roads[10].f = 2; Roads[10].t = 1; } Map::~Map() { delete Cities; delete Roads; } void *Map::Start(){ return &Cities[0]; } void *Map::Goal(){ return &Cities[6]; } void Map::Bn(void *s, Container &c){ for (int i=0; i<m; i++) if (*((City*)(s))==Cities[Roads[i].f]) c.Store(&Cities[Roads[i].t]); } void Map::Show(void*s){ cout<<*(char*)(s); } Cơ sở tri thức tháp Hà Nội HNTower::~HNTower() { State *n; sl.GoToHead(); while (0!=(n=(State*)(sl.Retrieve()))) { delete n; sl.GoNext();} } void *HNTower::MakeState(int a, int b, int c) { State *n; sl.GoToHead(); while (0!=(n=(State*)(sl.Examine()))) { if ((n->a==a)&&(n->b==b)&&(n->c==c)) return n; sl.GoNext(); } n = new State; n->a = a; n->b = b; n->c = c; sl.Store(n); return n; } void *HNTower::Start() { return (MakeState(3,0,0)); } void *HNTower::Goal() { return (MakeState(0,0,3)); } void HNTower::Bn(void *s, Container &c) { State t = *(State*)(s); if (t.a == 3) {c.Store(MakeState(2,1,0)); c.Store(MakeState(2,0,1)); return;} if (t.b == 3) {c.Store(MakeState(1,2,0)); c.Store(MakeState(0,2,1)); return;} if (t.c == 3) {c.Store(MakeState(1,0,2)); c.Store(MakeState(0,1,2)); return;} if ((t.a == 2) && (t.b==1)) {c.Store(MakeState(3,0,0)); c.Store(MakeState(2,0,1)); c.Store(MakeState(0,1,2)); return;} if ((t.a == 2) && (t.c==1)) {c.Store(MakeState(3,0,0)); c.Store(MakeState(2,1,0)); c.Store(MakeState(0,2,1)); return;} if ((t.b == 2) && (t.a==1)) {c.Store(MakeState(0,3,0)); c.Store(MakeState(0,2,1)); c.Store(MakeState(1,0,2)); return;} if ((t.b == 2) && (t.c==1)) {c.Store(MakeState(0,3,0)); c.Store(MakeState(1,2,0)); c.Store(MakeState(2,0,1)); return;} if ((t.c == 2) && (t.a==1)) {c.Store(MakeState(0,0,3)); c.Store(MakeState(0,1,2)); c.Store(MakeState(1,2,0)); return;} if ((t.c == 2) && (t.b==1)) {c.Store(MakeState(0,0,3)); c.Store(MakeState(1,0,2)); c.Store(MakeState(2,1,0)); return;} } void HNTower::Show(void*s) { State t = *(State*)(s); cout<<'('<<t.a<<','<<t.b<<','<<t.c<<")\n"; } Mô tơ suy diễn void Search::MakeNote(void*s,Snote*f){ Snote *n; open.GoToHead(); while (0!=(n=(Snote*)(open.Examine()))) { if (n->State==s) return; open.GoNext(); } close.GoToHead(); while (0!=(n=(Snote*)(close.Examine()))) { if (n->State==s) return; close.GoNext(); } Snote *tmp = new Snote; tmp->State = s; tmp->Father = f; open.Store(tmp); open.GoToHead(); } Search::~Search(){ Snote *n; open.GoToHead(); close.GoToHead(); while (0!=(n=(Snote*)(open.Retrieve()))){ delete n; open.GoNext();} while (0!=(n=(Snote*)(close.Retrieve()))){ delete n; close.GoNext();} } void Search::Report(KB *kb){ close.GoToHead(); Snote *n=(Snote*)(close.Examine()), *t; kb->Show(n->State); t = n->Father; close.GoNext(); while (0!=(n=(Snote*)(close.Examine()))) { if (t==n) { kb->Show(n->State); t = n->Father; } delete n; close.GoNext(); } } int Search::Reasone(KB &kb){ void *s = kb.Start(), *g = kb.Goal(), *m; Snote *n; Queue q; MakeNote(s,0); while (0!=(n=(Snote*)(open.Retrieve()))) { close.Store(n); if (n->State==g) return 1; kb.Bn(n->State,q); while (0!=(m = q.Retrieve())) MakeNote(m,n); open.GoToHead(); } return 0; }; Hệ cơ sở tri thức GPSystem::GPSystem(){ kb = 0; e = 0; } GPSystem::GPSystem(KB*k,Engine*E){ kb = k; e = E; } int GPSystem::Solve(){ return (e->Reasone(*kb)); } (e) Minh họa void main(){ KB *kb = new HNTower; Engine *e = new Search; GPSystem s(kb,e); if (s.Solve()) e->Report(kb); else cout<<"\nfail"; delete kb; delete e; } 2. Cài đặt thuật toán A* bằng prolog domains city = symbol dist = integer database open(city, city, dist) close(city, city, dist) done predicates road(city, city, dist) heuristic(city, dist) init repeat check(city, dist) bn(city, dist) run report report(city) min(city, city, dist) p(dist) clauses road(n,c,10). road(d,l,10). heuristic(n,26). heuristic(c,20). heuristic(t,18). heuristic(d,10). heuristic(g,30). heuristic(l,0). heuristic(u,30). heuristic(h,15). min(F,T,X):-open(F,T,X), not(p(X)). p(X):- open(_,T1,X), heuristic(T1, D1), open(_,T2,Y), heuristic(T2, D2), X+D1>Y+D2. run:- repeat, min(X,Y,D), retract(open(X,Y,D)), asserta(close(X,Y,D)), check(Y,D), done. check(X,_):-X=l, assert(done). check(X,D):-bn(X,D). report:-retract(close(X,Y,D)), write(D),nl,write(Y), report(X). report(z). report(X):-close(Z,X,_), write("<-",X), report(Z). bn(X,D):- road(X,Y,D1), D2 = D + D1, asserta(open(X,Y,D2)), fail. bn(_,_). goal init, assertz(open(z,n,0)), run, report. 3. Xây dựng hệ chuyên gia đơn giản bằng prolog Hệ có thể nhận biết trái cây đang xét là loại trái nào. 3.1. Cơ sở tri thức (a) Mô tả Dùng mạng ngữ nghĩa vàng đỏ màu mọc trên cây Trái táo cực bắc không có ở hình tròn nhỏ kích thước dùng làm rượu Trái nho thân mềm mọc trên cây không có gai (b) Thủ tục Dùng luật sản xuất 1. Nếu X là đối tượng và tất cả các thuộc tính của nó đều đúng → X là loại trái cây đang xét; 2. Nếu A là thuộc tính của X và A chưa biết → hỏi trái cây đang xét có thuộc tính A không 3.2. Cài đặt bằng prolog domains object = symbol attribute = symbol val = integer vlist = val* predicates rule(object, attribute, val) min(vlist, val) isa(object) obj(object) value(object, val) database /*lưu các chứng cứ*/ term(attribute, val) clauses /*tri thức mô tả các loại trái cây*/ obj(apple). obj(grape). rule(apple, on_tree, 1). rule(apple, round, 1). rule(apple, yellow_red, 1). rule(apple, north_hole, 0). rule(grape, small, 1). rule(grape, soft_tree, 1). rule(grape, wine, 1). rule(grape, gai, 0). /*tri thức thủ tục cho mô tơ suy diễn*/ value(X, 1) if rule(X, Y, V), term(Y, V). value(X, 0) if rule(X, Y, U), term(Y, V), U = 1 - V. isa(X) if obj(X), findall(Y, value(X, Y), L), write(L), nl, min(L,1). value(X, V) if rule(X, Y, W), write("does it have : ",Y," 0/1? "), readint(U), assert(term(Y, U)), V=U*W + (1-W)*(1-U). /*các tiện ích*/ min([X], X) if !. min([0|_], 0) if !. min([1|T], V) if min(T, V). goal isa(X), writeline(X). 4. Xây dựng một cơ chế thu nhận tri thức Xét bài toán hệ thức lượng trong tam giác. Để giải bài toán này chúng ta có hàng loạt các công thức. Giả sử chúng ta cung cấp cho hệ các công thức như: Ach CBA haS b a sin 2 1 ×= =++ ×= π thì hệ sẽ thu hoạch được gì? Thay vì hệ chỉ biết những gì ta dạy, ta muốn hệ có khả năng tổng quát hoá. Muốn vậy, chúng ta phải cung cấp cho hệ những tri thức khác cho phép hệ có thể suy luận để tổng quát hoá các công thức mà chúng ta vừa dạy cho nó. Cơ chế học được đưa ra ở đây dựa vào phương pháp học bằng cách xây dựng một giải thích. 4.1. Cơ sở tri thức Dùng luật sản xuất 1. Nếu X là một cạnh → X là một đại lượng; 2. Nếu X là một góc → X là một đại lượng; 3. Nếu X là một đường cao → X là một đại lượng; 4. Nếu X là diện tích → X là một đại lượng; 5. Nếu X, Y, Z là các đại lượng → (X, Y, Z) là một bộ 3 các đại lượng; 6. Nếu S là diện tích và Y, Z là các đại lượng cùng đỉnh → (X, Y, Z) có một ràng buộc; 7. Nếu X, Y, Z là các đại lượng có các đỉnh đôi một khác nhau → (X, Y, Z) có một ràng buộc; 8. Nếu (X, Y, Z) là một bộ 3 các đại lượng và (X, Y, Z) có một ràng buộc → (S, Y, Z) là một công thức 4.2. Minh họa cơ chế học Ký hiệu c(X) : X là một cạnh; g(X): X là một góc; d(X): X là diện tích; v(X): X là đường cao; dl(X): X là một đại lượng; b3(X, Y, Z): (X, Y, Z) là một bộ 3 các đại lượng; rb(X, Y, Z): (X, Y, Z) có một ràng buộc; ct(X, Y, Z): (X, Y, Z) là một công thức; cd(X, Y): X, Y là các đại lượng cùng đỉnh; kd(X, Y, Z): X, Y, Z là các đại lượng có các đỉnh đôi một khác nhau. Cây giải thích khi học công thức ahaS ×= 2 1 như sau ct(X,Y,Z) b3(X,Y,Z) rb(X,Y,Z) dl(X) dl(Y) dl(Z) d(X) cd(Y,Z) kd(X,Y,Z) d(X) c(Y) v(Z) d(S) cd(a,a) d(S) c(a) v(a) và kết quả hệ học được luật mới cụ thể hơn 9. Nếu X là diện tích và Y là một cạnh và Z là một đường cao và Y, Z cùng đỉnh → (X, Y, Z) là một công thức Tương tự, cây giải thích khi học công thức π=++ CBA như sau ct(X,Y,Z) b3(X,Y,Z) rb(X,Y,Z) dl(X) dl(Y) dl(Z) d(X) cd(Y,Z) kd(X,Y,Z) g(X) g(Y) g(Z) kd(a,b,c) g(a) g(b) g(c) kết quả hệ học được luật mới 10. Nếu X, Y, Z là 3 góc có đỉnh khác nhau đôi một → (X, Y, Z) là một công thức Cuối cùng, cây giải thích khi học công thức Achb sin×= như sau ct(X,Y,Z) b3(X,Y,Z) rb(X,Y,Z) dl(X) dl(Y) dl(Z) d(X) cd(Y,Z) kd(X,Y,Z) g(X) g(Y) g(Z) kd(b,c,a) v(b) c(c) g(a) kết quả hệ học được luật mới 11. Nếu X là đường cao và Y là cạnh và Z là góc và X, Y, Z có đỉnh khác nhau đôi một → (X, Y, Z) là một công thức 5. Đối sánh 5.1. Khái niệm Định nghĩa 3.1 Đối sánh là quá trình so sánh hai hoặc nhiều cấu trúc để phát hiện ra chúng là giống hay khác nhau. Các trường hợp 1. Đơn giản nhất là so sánh bằng nhau Chẳng hạn kết quả đối sánh hai xâu acdebfba và acdebeba là khác nhau sau khi so sánh từng ký tự một 2. Phức tạp hơn là trường hợp phải biến đổi trước khi so sánh bằng nhau Chẳng hạnï kết quả đối sánh hai xâu (ab(cd)e) và (ab?xe) là giống nhau sau khi thay ?x bởi (cd) 3. Trường hợp phức tạp nhất đòi hỏi biến đổi dạng biểu diễn trước khi đối sánh. Chẳng hạn một đối tượng ảnh biểu diễn dưới dạng đa mức xám đối sánh với các mô tả theo logic vị từ, rõ ràng một so sánh trực tiếp là không thể trừ phi một dạng được biến đổi về dạng còn lại. 4. Ngoài ra còn một số kiểu đối sánh khác Chẳng hạn yêu cầu đối sánh chỉ các phần tử khoá. 5.2. Đối sánh biểu thức Ta có thể viết luật, sự kiện dưới dạng biểu thức. Với biểu thức ta có thể • Dùng cấu trúc cây nhị phân để biểu diễn • Phép thay thế các biến tự do trên cấu trúc cây cho phép sinh ra các sự kiện mới một cách dễ dàng, trực quan và có thể cài đặt được. Xét ví dụ sau Ví dụ 3.1 Aùp dụng luật x + y = y + x trên biểu thức (a + 2*b) + c*d • Biểu diễn biểu thức • Biểu diễn luật • Áp dụng luật cho đỉnh cộng (+) đầu tiên tìm thấy Bài tập Xét bài toán biến đổi biểu thức mệnh đề, hãy 1. Mô tả cấu trúc dữ liệu cho mệnh đề 2. Mô tả cấu trúc dữ liệu cho luật 3. Mô tả quá trình áp dụng luật đưa biểu thức về dạng chuẩn Tài liệu tham khảo 1 Trí tuệ nhân tạo - Đỗ Trung Tuấn, 1998 2 Trí tuệ nhân tạo, các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri thức - Nguyễn Thanh Thủy 3 Trí tuệ nhân tạo, các phương pháp và ứng dụng - Bạch Hưng Khang - Hoàng Kiếm 4 Giải một bài toán trên máy tính như thế nào (tập 1&2) - Hoàng Kiếm 5 Lập trình C cho trí tuệ nhân tạo - Herbert Schildt 6 Introduction Artificial Intellegent & Expert System - Dan W Patterson 7 Problem Solving & Artificial Intellegent - Jean - Louis Laurière 8 Artificial Intellegence – Elaine Rich – Kevin Knight, 1991 9 Artificial Intellegence A Modern Approach – Stuart Russell – Peter Norvig, 1995 10 Turbo prolog