Bài giảng Công nghệ tri thức và ứng dụng - Phần 1: Quản lý tri thức - Chương 2: Tối ưu hóa cơ sở tri thức

Chương 2: Tối ưu hố Cơ sở tri thức Phần I: Quản lý tri thức (Knowledge Management) I. Tại sao phải tối ưu hĩa Cơ sở tri thức ? Tri thức trong một cơ sở tri thức rất có khả năng thừa, trùng lắp hoặc mâu thuẫn. 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. II. Luật thừa II.1. Rút gọn bên phải Luật sau hiển nhiên đúng : A  B  A	(1) Do đó luật 	A  B  A  C Là hoàn toàn tương đương với 	A  B  C Quy tắc rút gọn : Có thể loại bỏ những sự kiện bên vế phải nếu những sự kiện đó đã xuất hiện bên vế trái. Nếu sau khi rút gọn mà vế phải trở thành rỗng thì luật đó là luật hiển nhiên. Ta có thể loại bỏ các luật hiển nhiên ra khỏi tri thức. II. Luật thừa (tt) II.2. Rút gọn bên trái  	Xét các luật : 	(L1) A  B  C	 	(L2) A  X	 	(L3) X  C   Rõ ràng là luật A  B  C có thể được thay thế bằng luật A  C mà không làm ảnh hưởng đến các kết luận trong mọi trường hợp. Ta nói rằng sự kiện B trong luật (1) là dư thừa và có thể được loại bỏ khỏi luật dẫn trên. II. Luật thừa (tt) II.3. Phân rã và kết hợp luật 	Luật A  B  C .Tương đương với hai luật 	A  C; B  C Với quy tắc này, ta có thể loại bỏ hoàn toàn các luật có phép nối HOẶC. Các luật có phép nối này thường làm cho thao tác xử lý trở nên phức tạp. II.4. Luật thừa: Một luật dẫn A  B được gọi là thừa nếu có thể suy ra luật này từ những luật còn lại. Ví dụ : trong tập các luật gồm {A  B, B  C, A  C} thì luật thứ 3 là luật thừa vì nó có thể được suy ra từ 2 luật còn lại. Loại đi các luật có phép nối HOẶC, các luật hiển nhiên hoặc các luật thừa. II.5 Thuật tốn loại bỏ luật thừa: B1 : Rút gọn vế phải Với mỗi luật r trong R 	Với mỗi sự kiện A  VếPhải(r) 	 Nếu A  VếTrái(r) thì Loại A ra khỏi vế phải của R. 	 Nếu VếPhải(r) là rỗng thì loại bỏ r ra khỏi hệ luật dẫn: 	R = R – {r}  II. Loại bỏ luật thừa (tt) II.5 Thuật tốn loại bỏ luật thừa: (tt) B2 : Phân rã các luật: 	Với mỗi luật r : X1  X2  …  Xn  Y trong R 	Với mỗi i từ 1 đến n R := R  { Xi  Y } 	R := R \ {r} B3 : Loại bỏ luật thừa: Với mỗi luật r thuộc R Nếu VếPhải(r)  BaoĐóng(VếTrái(r), R\{r}) thì R := R\{r} II. Loại bỏ luật thừa (tt) II.5 Thuật tốn loại bỏ luật thừa: (tt) B4 : Rút gọn vế trái  Với mỗi luật dẫn r : X : A1  A2, …, An  Y thuộc R 	Với mỗi sự kiện Ai thuộc r 	Gọi luật r1 : X\{Ai}  Y và S = ( R\{r} )  {r1} 	Nếu BaoĐóng(X\{Ai}, S)  BaoĐóng(X, R) thì 	X := X \ {Ai} II. Loại bỏ luật thừa (tt) III. Luật mâu thuẫn III.1 Ví dụ luật mâu thuẫn Cho tập R như sau: 	r1: A, M  N	r5: D  M 	r2: B, N  C	r6: B, N  M 	r3: A, M  B	r7: P, C  A 	r4: A  P	r8: D, O  A Xét luật	r: D, O   N là một luật mâu thuẫn vì 	D, O  A, M, P (do r8, r5, r4) 	D, O  A, M, P, N (do r1)  D, O  N III. Luật mâu thuẫn (tt) III. 2 Định nghĩa luật mâu thuẫn Gọi	R: tập luật của cơ sở tri thức 	r R: X  Y 	(X)R – {r} : tập các mệnh đề suy được từ mệnh đề X bằng các luật 	thuộc R – {r} 	  Y: phủ định của Y Luật r được gọi là mâu thuẫn nếu: Y  (X)R – {r} III. Luật mâu thuẫn (tt) III.3 Thuật tốn loại bỏ luật mâu thuẫn a. Kiểm tra luật mâu thuẫn - Đặt R’ = R – {r} - Xác định (X)R’ = {Aj / Aj các mệnh đề cĩ thể suy diễn từ X dựa trên tập luật R’} (bao đĩng của X trên R’) Kiểm tra nếu  Y (X)R’ khơng? Nếu đúng: thì luật r mâu thuẫn đối với tập luật R’ Ngược lại r khơng mâu thuẫn III. Luật mâu thuẫn (tt) III.3 Thuật tốn loại bỏ luật mâu thuẫn (tt) b. Loại bỏ luật mâu thuẫn trong CSTT 	B1: Xét luật r trong R của CSTT 	Kiểm tra r cĩ mâu thuẫn với tập R – {r} khơng? 	B2: Nếu mâu thuẫn thì R = R – {r} 	B3: Quay lai B1 với luật khác III. Luật mâu thuẫn (tt) III.4 Cơ chế xử lý mâu thuẫn luật Nguyên tắc 1: Dựa theo trọng số luật 	Nếu	Luật r và r’ mâu thuẫn nhau 	Và	Luật r’ cĩ trọng số xuất hiện nhiều hơn r 	Thì	Loại bỏ luật r và giữ lại r’ Nguyên tắc 2: Dựa theo tần số xuất hiện 	Nếu	Luật r và r’ mâu thuẫn nhau 	Và	Luật r’ cĩ tần xuất xuất hiện nhiều hơn r 	Thì	Loại bỏ luật r và giữ lại luật r’ III. Luật mâu thuẫn (tt) Nguyên tắc 3: Dựa theo lĩnh vực đang xét 	Nếu	Luật r và r’ mâu thuẫn nhau 	Và	Luật r’ thuộc lĩnh vực A 	Và	Luật r thuộc lĩnh vực B 	Và	Đang xét lĩnh vực A 	Thì	Loại bỏ luật r và giữ lại luật r’ III. Luật mâu thuẫn (tt) Nguyên tắc 4: Trường hợp chung riêng 	Nếu	Luật r và r’ mâu thuẫn nhau 	Và	Luật r biểu thị trường hợp chung 	Và	Luật r’ biểu thị trường hợp riêng 	Thì	Khơng áp dụng luật r và áp dụng luật r’ Nguyên tắc 5: Dựa vào chuyên gia 	Nếu	Luật r và r’ mâu thuẫn nhau 	Và	Chuyên gia chấp nhận luật r’ 	Thì	Loại bỏ luật r và giữ lại r’ IV. Vịng lặp trong suy diễn IV.1 Thế nào là vịng lặp trong suy diễn ? IV. Vịng lặp trong suy diễn (tt) IV.2 Thuật tốn phát hiện vịng lặp Gọi	R: tập luật sẵn cĩ của cơ sở tri thức 	r: X  Y là luật mới cần thêm vào B1. Xác định (Y)R = {Aj / Aj các mệnh đề cĩ thể suy diễn từ Y dựa trên tập luật R} (bao đĩng của Y trên R) B2. Nếu X  (Y)R thì luật r gây ra vịng lặp IV. Vịng lặp trong suy diễn (tt) Ví dụ: Cho tập luật R như sau: 	r1: A, M  N	r4: A  P 	r2: B, N  C	r5: D  M 	r3: A, M  B	r6: B, N  M 	r7: D  A Giả sử ta muốn thêm luật mới r: N  D, luật này sẽ làm xuất hiện vịng lặp trong CSTT vì N  (D)R