Bài giảng Mạng suy diễn - Tính toán

ính khác. Khái niệm tập hợp sinh và phương pháp tìm một tập hợp sinh trên một mạng suy diễn là cơ sở cho việc phát triển các thuật toán giải quyết vấn đề kiểm định giả thiết của bài toán suy diễn. Đại Học Quốc Gia TP.HCM, 2001 5.1 Khái niệm tập hợp sinh Định nghĩa: Cho (A, D) là một mạng suy diễn. Một tập thuộc tính S  A được gọi là một tập hợp sinh của mạng suy diễn khi ta có bao đóng của S trên mạng là A, nghĩa là = A. Ví dụ: Xét mạng suy diễn (A, D) với A = a, b, c, A, B, C, R, p, S gồm các biến số thực dương. Đại Học Quốc Gia TP.HCM, 2001 D là tập hợp các luật suy diễn tương ứng của các quan hệ suy diễn thể hiện bởi các công thức sau đây: f1: A + B + C =  ;	 f2: a/sin(A) = 2*R ; f3: b/sin(B) = 2*R ; f4: c/sin(C) = 2*R ; f5: a + b + c = 2*p ; f6: a2 = b2 + c2 – 2*b*c*cos(A) ; f7: b2 = a2 + c2 – 2*a*c*cos(B) ; f8: c2 = b2 + a2 – 2*b*a*cos(C) ; f9: S = sqrt(p*(p-a)*(p-b)*(p-c)) Đại Học Quốc Gia TP.HCM, 2001 Mạng suy diễn nầy có một tập hợp sinh là T = a, A, B và từ T ta suy ra được D nhờ các luật suy diễn sau: A, a  R; A, B  C; R, C  c; R, B  b; a, b, c  p; a, b, c, p  S Đại Học Quốc Gia TP.HCM, 2001 5.2 Tìm tập hợp sinh Ta có thể tìm một tập hợp sinh bằng phương pháp thử dần. Tuy nhiên ở đây sẽ trình bày cách tìm một tập hợp sinh không tầm thường với số phần tử càng ít càng tốt. Phương pháp: thiết lập một “biểu đồ (hay đồ thị) phân cấp” của một mạng suy diễn. Không làm mất tính tổng quát ta có thể giả sử các luật suy diễn có phần kết luận gồm 1 phần tử. Đại Học Quốc Gia TP.HCM, 2001 Định nghĩa: Cho một mạng suy diễn (A, D) mà mỗi luật suy diễn có phần kết luận gồm 1 phần tử. Ta xây dựng một đồ thị định hướng Graph(A, D) như sau: Tập hợp đỉnh gồm tất cả các thuộc tính và tất cả các luật suy diễn, tức là A  D. Ứng với mỗi luật r : hypothesis(r)  goal(r), thiết lập một tập hợp edges(r) gồm tất cả các cung định hướng (x, r) và (r, y) thỏa x  hypothesis(r) và y  goal(r). Tập hợp các cạnh của đồ thị Graph(A, D) là hợp của tất cả các tập hợp edges(r) với r chạy trong tập D. Đại Học Quốc Gia TP.HCM, 2001 Trong trường hợp trên đồ thị Graph(A, D) ta có degin(x)  1 với mọi x  A, thì ta có thể hiểu ngầm các đỉnh thuộc D và xét một đồ thị thu gọn GraphD (A) gồm: Tập hợp đỉnh là tập hợp các thuộc tính A. Tập hợp cạnh gồm tất cả các cung (x,y) thỏa mãn điều kiện: Có (duy nhất) một luật r sao cho goal(r) = y và x  hypotheis(r). Đại Học Quốc Gia TP.HCM, 2001 Định nghĩa: Ta gọi một đồ thị định hướng đơn giản không có chu trình là một biểu đồ phân cấp (hay một đồ thị phân cấp). Đỉnh x của đồ thị mà không có cung hướng tới sẽ được gọi là đỉnh mức 0, và ta viết level(x) = 0. Đối với các đỉnh x khác, ta định nghĩa một cách qui nạp mức của nó và mức của đỉnh nầy có thể được cho bởi: level(x) = max level(a) | có cung nối a với x + 1  tập hợp đỉnh được sắp xếp thành các mức:  mức 0 của là tập hợp tất cả các đỉnh mức 0,  mức 1 là tập hợp tất cả các đỉnh mức 1, v.v… Đại Học Quốc Gia TP.HCM, 2001 Ví dụ: Một biểu đồ phân cấp gồm 5 mức Đại Học Quốc Gia TP.HCM, 2001 Mệnh đề: Cho mạng suy diễn (A, D). Giả sử đồ thị Graph(A, D) có đồ thị thu gọn GraphD(A). Khi ấy, nếu GraphD(A) là một đồ thị phân cấp thì tập hợp S = Level0 gồm tất cả các đỉnh mức 0 sẽ cho ta một tập hợp sinh của mạng suy diễn. Hơn nữa trong trường hợp nầy ta còn có: (1) S là tập hợp sinh nhỏ nhất trên mạng suy diễn.  (2) Tập D là tập hợp luật tối thiểu để Level0 sinh ra A. Đại Học Quốc Gia TP.HCM, 2001 Định lý: Cho mạng suy diễn (A, D). ta có: S  A là một tập hợp sinh trên mạng suy diễn khi và chỉ khi có một tập luật D’  D sao cho Graph(A, D’) là một đồ thị phân cấp và S chứa tập hợp các đỉnh mức 0 của đồ thị nầy. Tồn tại một tập luật D’  D sao cho Graph(A, D’) là một đồ thị phân cấp. Đại Học Quốc Gia TP.HCM, 2001 Thuật toán: Tìm một tập hợp sinh S trong mạng suy diễn (A, D) bằng cách xây dựng một mạng con (A’, D’) với A’ = A và có Graph(A’, D’) là một biểu đồ phân cấp. Bước 1: A’  ; D’  ; S  ; Bước 2:  For r  D do If not (attr(r)  A’) then A’  A’  attr(r); D’  D’  r; và Thực hiện việc cập nhật A’, D’ và S theo  2 trường hợp như sau: - Trường hợp 1: goal(r)  A’ S  S  (hypothesis(r) - A’);  Đại Học Quốc Gia TP.HCM, 2001 - Trường hợp 2: goal(r)  A’ Loại r’ (nếu có) trong D’ mà goal(r’) = goal(r); Loại một số luật suy ra các x  hypothesis(r) để  bảo đảm tính phân cấp của biểu đồ và cập nhật S. Bước 3: S  S  (A - A’); A’  A Đại Học Quốc Gia TP.HCM, 2001 5.3 Bổ sung giả thiết xét việc bổ sung giả thiết cho bài toánH  G trên một mạng suy diễn (A, D) trong trường hợp bài toán không giải được. Ý tưởng chính ở đây là tiến hành một quá trình xây dựng một biểu đồ phân cấp với tập hợp đỉnh chứa G và ưu tiên cho việc đặt các phần tử của H ở mức 0. Đại Học Quốc Gia TP.HCM, 2001 Thuật toán: Cho mạng suy diễn (A, D) và bài toán H  G không giải được (không có lời giải). Tìm H’ sao cho H  H’ =  và bài toán (H  H’)  G là giải được. Bước 1: A’  H; D’  ; G  G \ A’; Bước 2: while (G   and D  ) do 2.1: Lấy ra một r từ D và cập nhật D. 2.2: if hypothesis(r)  G   or attr(r)  A’ then  Bỏ qua r 2.3: else Thêm r vào D’ và bổ sung attr(r) vào A’và trong trường hợp goal(r)  A’ thì loại ra r’ từ D’ (nếu có) thỏa goal(r’) = goal(r) và loại một số luật suy ra các x  hypothesis(r) để bảo đảm tính phân cấp. Đại Học Quốc Gia TP.HCM, 2001 2.4: G  G - A’ Bước 3: if G   then  Kết thúc với kết luận:Vấn đề bổ sung  giả thiết là không giải quyết được Bước 4: else (Trong trường hợp nầy Graph(A’,D’) có biểu đồ phân cấp tương ứng là GraphD’A’) Gọi L0  là mức 0 của biểu đồ GraphD’A’. Đặt: H’  L0 - H Thuật toán tìm sự bổ sung giả thiết cho bài suy diễn được nêu trên là đúng và có độ phức tạp là O(|A|.|D|). Đại Học Quốc Gia TP.HCM, 2001 VI. Mạng Suy diễn - Tính toán 6.1 Mô hình 6.2 Giải bài toán trên mạng suy diễn-tính toán Đại Học Quốc Gia TP.HCM, 2001 6.1 Mô hình Định nghĩa: Một mạng suy diễn-tính toán gồm bốn thành phần: Tập hợp A gồm các thuộc tính. Tập hợp D gồm các luật suy diễn (hay các quan hệ suy diễn) trên các thuộc tính. Tập hợp F gồm các công thức tính toán hay các thủ tục tính toán tương ứng với các luật suy diễn. Sự tương ứng nầy thể hiện bởi một ánh xạ f : D  F. Tập hợp R một số qui tắc hay điều kiện ràng buộc trên các thuộc tính. Đại Học Quốc Gia TP.HCM, 2001 Nhận xét: Mạng suy diễn tính toán gồm 4 tập hợp A, D, F và R như thế sẽ được ký hiệu bởi bộ bốn (A, D, F, R). Theo định nghĩa, ta có (A, D) là một mạng suy diễn và lời giải cho bài toán H  G trên mạng suy diễn nầy sẽ xác định các công thức hay các thủ tục tính toán các phần tử thuộc G từ các phần tử thuộc H. Ví dụ: Kiến thức về một tam giác có thể được biểu diễn bởi một mạng suy diễn tính toán (A, D, F, R) như sau: Đại Học Quốc Gia TP.HCM, 2001 A = A, B, C, a, b, c, R, S, p, ... là tập hợp các yếu tố  của một tam giác gồm 3 góc, 3 cạnh, bán kính vòng tròn ngoại tiếp, diện tích, nửa chu vi, v.v… D = r1: A, B  C; r2: A, C  B; r3: B, C  A;  r4: A, a  R; r5: A, R  a; r6: R, a  A;  r7: A, b, c  a; ... F = f1: C = -A-B; f2: B = -A-C; f3: A = -B-C; f4: R = a/(2.sin(A)); f5: a = 2.R.sin(A);  f6: A = arcsin(a/(2.R));  f7: a= b2+c2-2.b.c.cos(A); ... R =  a+b > c; a+c > b; b+c > a; a > b  A > B;  a = b  A = B; ... Đại Học Quốc Gia TP.HCM, 2001 6.1 Giải toán trên Mạng Suy diễn - Tính toán Trên một mạng suy diễn-tính toán ta có thể giải quyết các bài toán suy diễn tính toán chẳng hạn bài toán giải tam giác hay bài toán giải tứ giác dựa trên việc giải bài toán suy diễn trên mạng suy diễn.  Hơn nữa, các công thức hay thủ tục tính toán có thể được gán cho các trọng số thể hiện độ phức tạp tính toán của chúng. Từ đó ta có thể tìm ra được những lời giải cho bài toán suy diễn tính toán với chi phí tính toán thấp nhất dựa trên việc tìm lời giải tối ưu trên mạng suy diễn có trọng số. Đại Học Quốc Gia TP.HCM, 2001 Ngoài ra, chúng ta có thể tìm ra được các công thức tường minh qua các bước giải bài toán và rút gọn các công thức dưới dạng ký hiệu. Kết hợp điều nầy với việc dò tìm những sự liên hệ suy diễn giữa các yếu tố nào đó mà ta quan tâm sẽ cho ta một phương pháp để tự động tìm ra thêm những luật suy diễn và những công thức tính toán liên quan đến các yếu tố. Điều nầy có ý nghĩa như một kỹ thuật khám phá tri thức. Đại Học Quốc Gia TP.HCM, 2001 Sự Mở rộng & Phát triển Mô hình Một sự mở rộng của mạng suy diễn tính toán là cho phép xét thêm các quan hệ khác với các quan hệ suy diễn – tính toán ở đây, chẳng hạn các quan hệ hình học giữa các đối tượng hình học điểm, đoạn, tia, góc. Sự mở rộng nầy sẽ được tích hợp trong một cấu trúc trừu tượng theo phương pháp lập trình hướng đối tượng mà ta gọi là một đối tượng tính toán. Khái niệm về đối tượng tính toán sẽ được xây dựng và được xem xét trong một mô hình tri thức được gọi là mô hình tri thức các đối tượng tính toán. Đại Học Quốc Gia TP.HCM, 2001