Báo cáo nghiên cứu khoa học " LẬP LUẬN XẤP XỈ VỚI MODUS PONENS TRÊN CƠ SỞ ĐẠI SỐ GIA TỬ "

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

43
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Xét cơ sở tri thức bao gồm các câu gồm hai phần cơ bản: phần rõ ràng và phần mơ hồ được biểu diễn dưới dạng các luật If . . . then . . . khi đó cơ sở tri thức của ta bao gồm các luật có dạng như sau: If "The student is more young" and "He is a very good student" then "The student is quite a good candidate". 53 Ở đây các sự kiện "X is hA" (với h là các từ nhấn như more, very...) có thể viết lại là: "X (is h) A" hay h...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học " LẬP LUẬN XẤP XỈ VỚI MODUS PONENS TRÊN CƠ SỞ ĐẠI SỐ GIA TỬ "

LẬP LUẬN XẤP XỈ VỚI MODUS PONENS TRÊN CƠ SỞ ĐẠI SỐ GIA TỬ Nguyễn Thế Dũng Trường Đại học Sư phạm, Đại học Huế I. MỞ ĐẦU Xét cơ sở tri thức bao gồm các câu gồm hai phần cơ bản: phần rõ ràng và phần mơ hồ được biểu diễn dưới dạng các luật If . . . then . . . khi đó cơ sở tri thức của ta bao gồm các luật có dạng như sau: If "The student is more young" and "He is a very good student" then "The student is quite a good candidate". 53
Ở đây các sự kiện "X is hA" (với h là các từ nhấn như more, very...) có thể viết lại là: "X (is h) A" hay h là cấp độ đúng (true degree) của câu "X is A". Nói cách khác, câu "X is hA" is true  "X is A" is h true. Ở đây h true thể hiện cấp độ đúng của câu "X is A". Chẳng hạn "He is a very good student" có thể viết lại là: "(He is a good student) is very true", hay “Robert is old” được viết lại "(Robert is old) is true". Các câu phức tạp hơn như: "It is quite likely that the snow is almost white" có thể biểu diễn ở dạng "(The snow is white) is almost true) is quite true". Trong bài này, một câu S chứa thông tin mơ hồ được tách biệt ra bởi một trạng từ (adverb)  và một mệnh đề P, ở đây  diễn tả cấp độ câu S thỏa mãn tính chất P là , chúng ta sẽ gọi  là cấp độ đúng (true degree) của câu S. Bên cạnh đó với một câu S, chúng ta quan tâm đến mức độ tin cậy hay còn gọi là độ chắc chắn của ta về câu S đó. Trong bài này sẽ ký hiệu  là cấp độ thể hiện sự tin cậy - chắc chắn (certain degree) của câu S. Ví dụ: Trong câu "(The snow is white) is almost true) is quite true" trên thì P="The snow is white", ="almost" còn ="quite". Việc quan tâm đến mức độ tin cậy của một câu S vẫn thường thấy khi thu thập tri thức trong các hệ chuyên gia. Khi thu nhận một tri thức từ các chuyên gia, chúng ta vẫn thường đặt vấn đề mức độ tin cậy - chắc chắn về tri thức ấy. 54
Trong [2][4][12] đã biểu diễn các câu trên ở dạng S(x,u) với x là biến còn u là khái niệm mơ hồ và một khẳng định A=(S(x,u),t) với t thể hiện cấp độ đúng của câu S. Như thế cách biểu diễn trong bài này là tương tự cách biểu diễn câu khẳng định trong [2][4] [12], ở đây câu S hiểu theo nghĩa trên sẽ là một khẳng định S=(S(x,u), true) với x là biến còn u là khái niệm mơ hồ, còn  true chính là t trong cách biểu diễn trong [2][4] [12]. Lưu ý, trong bài này chúng ta tách biệt khái niệm mơ hồ u trong câu thông qua trạng từ  và mệnh đề P. Ví dụ: Với câu S="Lan học rất chăm chỉ là có thể đúng" với cách biểu diễn trong [4][12] sẽ là S(học(Lan, rất chăm chỉ), có thể đúng). Còn với cách biểu diễn trong bài này sẽ là S(học(Lan, chăm chỉ), rất đúng, có thể đúng). ở đây ="rất đúng" còn  ="có thể đúng". Như vậy cấp độ ngữ nghĩa t theo cách biểu diễn trong [4][12] tương ứng chính là true degree " true" trong cách biểu diễn của bài này. Cách biểu diễn của chúng ta tách biệt được phần rõ ràng và phần mơ hồ của câu, bên cạnh đó thể hiện được độ tin cậy (certain degree) của một câu. Ví dụ với câu "Lan học rất chăm chỉ là có thể đúng" nói trên thì phần rõ ràng là: "Lan học chăm chỉ" và phần mơ hồ là: "rất chăm chỉ" nói cách khác là "Lan học chăm chỉ là rất đúng" thì phần rất đúng là mơ hồ, còn câu phát biểu "(Lan học chăm chỉ là rất đúng) là có thể đúng” thì “có thể đúng” thể hiện độ chắc chắn của phát biểu này. Trong bài này các cấp độ đúng true và cấp độ tin cậy true nói trên được xét trên đại số gia tử của biến chân lý true AX=(X,,G,LH) với G={True, 55
False}, LH là dàn phân phối sinh bởi các gia tử. Như đã biết AX là một dàn đầy đủ, nên có thể định nghĩa các phép và ( -cận trên) , hoặc ( -cận dưới) giữa hai phần tử bất kỳ của AX, hơn nữa như trong [1] cũng đã bổ sung các phần tử kí hiệu bởi I, O, W được định nghĩa như sau: I > x > W > y > O với mọi x  LH(True), yLH(False) và hI =I, hO=O, hW=W với mọi hLH. Các phần tử I, O, W có thể được hiểu như các giá trị ngôn ngữ tương ứng là: completely true, completely false và unknown. Từ đó không mất tính tổng quát có thể giả thiết rằng AX được sinh bởi tập các phần tử sinh G={I, true, W,false,O}. Trong [1] cũng đã xây dựng các toán tử joint (), toán tử meet () trong dàn AX, bên cạnh đó toán tử concept-implication x=>y cũng được định nghĩa: x=>y = xy với mọi x, y AX. Ở đây, x= x- (phần tử đối nghịch của x trong AX). Khi đó AX cùng với các toán tử hai ngôi , , =>; tập các toán tử một ngôi LH và {} cùng 5 toán tử 0 ngôi true, false, O, W, I trở thành một đại số De-Morgan. AX bao hàm đại số Lukasiewicz ba phần tử {O,W, I } như một đại số con, hơn nữa AX cũng là một đại số Kleen. Lúc này toán tử concept implication là một mở rộng của toán tử kéo theo kinh điển trong đại số Bool hai phần tử {O, I }. Bên cạnh đó trong [1] cũng đã xây dựng toán tử giả bù ~ và giả bù tương đối  cũng như đưa ra các kết quả tính toán cho toán tử giả bù tương đối. Lúc đó X'= là đại số Heyting và  là một mở rộng của toán tử kéo theo, theo nghĩa kinh điển. Do đó có thể nói rằng AX là một cơ sở logic tốt cho việc lập luận xấp xỉ. 56
Để lập luận trên các luật If ... then ... một qui tắc suy diễn thường được sử dụng đó là modus ponens. Với cơ sở tri thức có dạng trên qui tắc này sẽ là: If A then B is true; If A is true B is true Trong bài này, phần II chúng ta sẽ mở rộng qui tắc trên trong một số trường hợp mà các mệnh đề A, B trong các luật được hiểu là có các cấp độ đúng và cấp độ tin cậy khác nhau trên đại số gia tử AX vừa nói trên. Đồng thời chúng ta cũng sẽ mở rộng các luật trong lập luận xấp xỉ trên các biến ngôn ngữ trong [12], tập trung thảo luận các trường hợp liên quan đến modus ponens. Các qui tắc lập luận của chúng ta trong bài này được phân chia ra các trường hợp (9 trường hợp) có thể có khi vận dụng modus ponens. Qua các trường hợp được phân chia trong phần sau, chúng ta sẽ thấy rằng các qui tắc lập luận sử dụng trong bài này tuân theo bản chất lập luận dựa trên khoảng cách và tính sắp thứ tự của đại số gia tử như trong [4][12]. Vì một số qui tắc RT1, RT2... trong [12] về qui tắc modus ponens là một trong các trường hợp của bài này. Trong các trường hợp 3 và 4, chúng ta sử dụng hàm modus ponens tổng quát như trong logic mờ, nhưng cách tính toán của chúng ta bỏ qua được các bước xây dựng hàm thuộc, khử mờ... của logic mờ, nhưng cho kết quả hợp lý. 57
Bên cạnh đó một heuristic để lựa chọn luật cháy (fire rule) khi lập luận trên cơ sở tri thức có dạng nói trên cũng được đưa ra trong bài, ở cuối phần II. II. LẬP LUẬN XẤP XỈ TRÊN CƠ SỞ ĐẠI SỐ GIA TỬ Một câu hỏi thường được đặt ra trong lập luận xấp xỉ là: Giả sử đã biết {A is  true and (A  B) is  true} lúc đó có kết luận gì về B? Hoặc đã biết {(A  B)is  true and B is  true}, có kết luận về A? Trường hợp đầu là modus ponens, còn trường hợp sau chính là modus tollens mở rộng cho lập luận xấp xỉ. Trong bài này chúng ta tập trung quan tâm đến modus ponens. Để cho tiện ký hiệu chúng ta sẽ viết A thay cho "A is  True", còn nếu viết A được hiểu là "A is true" và (A) được hiểu "A is True" với cấp độ chắc chắn (certain degree) là True. Như vậy khi viết A thì hiểu true degree và certain degree của câu A đều là True. Ví dụ: Với câu "The student is more intelligent is very true" có thể viết thành "(((The student is intelligent) is more true) is very true)", lúc này A="The sudent is intelligent", ="more" và ="very". Trước hết ta thấy rằng giữa true degree và certain degree có thể chuyển đổi như sau: 58
(A)  (A)  A V í d ụ: Câu "(Lan rất chăm chỉ) là có thể đúng" được viết lại là: "((Lan chăm chỉ) rất đúng) là có thể đúng"  "((Lan chăm chỉ) đúng) là rất có thể đúng"  "((Lan chăm chỉ) rất có thể đúng) là đúng". Câu "(Quả cà chua đỏ) rất đúng) là ít đúng"  "((Quả cà chua đỏ), đúng) là rất đúng"  "((Quả cà chua đỏ), rất ít đúng) là đúng). Với quan niệm trên thì cơ sở tri thức của chúng ta sẽ bao gồm các luật If then có dạng như sau: [If [[X is A] is  true] then [[Y is 'B] is 'true]] is true. Ở đây  là certain degree của luật, còn ' chính là true degree của luật. Dưới đây chúng ta sẽ xem xét các trường hợp mở rộng của modus ponens cho lập luận xấp xỉ trên cơ sở tri thức có dạng trên. Chúng ta sẽ ký hiệu modus ponens ở dạng: AB 59
A' B' Vấn đề đặt ra là với các trường hợp khác nhau của A, B, A' hãy tính true degree và certain degree của B'. Ta có các trường hợp sau: TH 1: AB A B Đây chính là trường hợp modus ponens thông thường. TH 2: AB A B. 60
Khi giả thiết A và kết luận B của luật là True và nếu ta có đầu vào là A thì đầu ra là B, tức ta gán cấp độ đúng của đầu vào cho đầu ra. TH 3: A  B A B Với  được tính như sau: True = True  (True, True). Ở đây ,  tương ứng là toán tử meet và toán tử giả bù tương đối trên đại số gia tử AX đã nói ở mục trên [1]. Các tính toán liên quan đến toán tử  xin xem thêm trong [1]. Cách tính  ở trên dựa trên ý tưởng của modus ponens tổng quát (generalized modus ponens - GMP) trong logic mờ. Với cơ sở RH đại số gia tử AX nói trên, chúng ta có đầy đủ công cụ để tính toán GMP, nhưng ở đây chúng ta không phải tính toán thông qua hàm thuộc (membership function). Hơn nữa lập luận của chúng ta cũng rất tự nhiên trên ngôn ngữ như cách lập luận thông thường của con người. 61
Như vậy, khi giả thiết A của luật là không mờ và kết luận B của luật là  true, còn đầu vào là A is  true, khi đó cấp độ đúng của đầu ra được tính toán theo công thức trên và ta thấy chúng là hoàn toàn hợp lý trong thực tiễn. Để làm rõ hơn cách tính kết luận B, ta chứng minh mệnh đề dưới đây. Mệnh đề 1 Toán tử M(x, y)=xy với x,y AX thỏa mãn các tính chất của một hà m modus ponens tổng quát (modus ponens generating function). Tức là: a) M(0, I ) = M(I ,O) = M(O,O) =O và M(I, I)= I. b) M(x,y) không tăng theo x và theo y. c) M(x,(x,y)y; M(I,y)=y và (I,y)=y. Chứng minh: a) và b) là hiển nhiên theo định nghĩa toán tử meet  trong AX. Hơn nữa, theo định lý 3.5 trong [1] trang 78, ta có (x  (x,y))  y và (I,y)=y với mọi x, yAX. Còn Iy=y là dễ thấy, nên c) được chứng minh. Mệnh đề chứng minh xong. 62
Các vấn đề liên quan đến hàm modus ponens tổng quát (modus ponens generating function) xin xem thêm trong [12]. TH 4: A  B ( A) (B) Với  được tính theo công thức sau: True = True(True,True). Tóm lại, khi giả thiết A của luật là true và kết luận B là  true, còn đầu vào là (A is  true) is  true. Khi đó ta gán certain degree True cho đầu ra, còn true degree True của đầu ra được tính theo công thức tương tự trường hợp 3. TH 5: A  B (A) (B) 63
V í d ụ: Nếu cà chua khá đỏ thì rất ngon Nếu cà chua khá đỏ là có thể đúng. Khi đó theo qui tắc trên dễ thấy rằng kết luận thu được sẽ là: Cà chua rất ngon là có thể đúng. Khi giả thiết A của luật là  true và kết luận B là  true, còn đầu vào là (A is  true) is  true - cấp độ đúng của giả thiết và đầu vào là như nhau. Khi đó ta gán certain degree True cho đầu ra và gán true degree True của kết luận B cho đầu ra. Lưu ý rằng, khi cấp độ đúng của giả thiết và đầu vào là khác nhau ta không thể suy luận được gì trong trường hợp này. TH 6: A  B (A) với    Không thể suy diễn được gì thêm. 64
V í d ụ: Nếu cà chua khá đỏ thì rất ngon Nếu cà chua rất đỏ là đúng. ="Khá"; ="Rất", trong thực tiễn ta thấy ở đây không thể suy diễn được gì thêm. Từ trường hợp 2 và trường hợp 4 ta có: TH 7: AB (A) (B) Kết hợp với qui tắc RMP và qui tắc RT1 trong [12] ta có: TH 8: (A B) 65
A (B) Đây chính là qui tắc liên quan đến modus ponens RMP trong [12]. TH 9: ((A B)) A (B). Đây chính là sự kết hợp giữa qui tắc chuyển đổi gia tử RT1 trong [12] và trường hợp TH7 ở trên và cũng chính là qui tắc RPI1 trong [12]. Tóm lại ta có: Nếu kết luận B của luật là true thì gán true degree và certain degree của đầu vào cho đầu ra. Ngược lại, 66
Nếu giả thiết A của luật là true thì tính toán các cấp độ true degree và certain degree cho đầu ra theo các công thức trong các trường hợp 2, 3, 4. Ngược lại, Nếu true degree của giả thiết A bằng true degree của đầu vào thì gán certain degree  của đầu vào cho đầu ra và gán true degree  của kết luận B cho đầu ra. Ngược lại, không thể suy diễn gì thêm. Hơn nữa cũng lưu ý rằng khi lập luận xấp xỉ trên cơ sở tri thức bao gồm các câu như đã xét ở các phần trên nếu xảy ra trường hợp đụng độ khi lựa chọn luật để suy diễn - luật cháy (fire rule), trong trường hợp này một heuristic để lựa chọn luật là: lựa chọn luật cháy là luật có certain degree lớn nhất, khi có nhiều luật như thế ta chọn luật có true degree lớn nhất. Ví dụ 1: Giả sử ta có các luật sau: R1: If A then C R2: If B then C 67
Cùng các sự kiện sau: A và  B với ="Khá" và  ="Rất". Áp dụng heuristic ta thấy luật R2 sẽ được chọn để lập luận và thu được kết luận là:  C. Ví dụ 2: Giả sử ta có các luật sau: R1: (If A then B is very true) is very true R2: (If A then C is more true) is very true Cùng sự kiện A, khi đó cả 2 luật R1, R2 đều có thể chọn để cháy, tuy vậy áp dụng heuristic trên, ta thấy luật R1 được chọn và ta thu được kết luận là: B. III. KẾT LUẬN Trong các phần trên chúng ta đã mở rộng và tính toán cho các trường hợp của modus ponens. Các mở rộng trên cùng với các qui tắc RT1,RT2, RMP, RE... trong [12] tạo cơ sở vững chắc cho việc lập luận xấp xỉ trên biến ngôn ngữ. Hơn nữa cách biểu diễn câu của chúng ta làm tách biệt được hai phần cơ bản của tri thức con người là: phần rõ ràng và phần mơ hồ. Đồng thời thể hiện 68
được độ tin cậy của câu, điều này thường gặp khi lập luận trên cơ sở tri thức thu thập từ các chuyên gia trong các hệ chuyên gia. Bên cạnh đó cách kí hiệu (A) tạo điều kiện dễ dàng khi cài đặt một mô tơ suy diễn trên cơ sở tri thức có dạng nói ở phần I. Cũng cần nói thêm với cơ sở là đại số gia tử chúng ta có thể định nghĩa các toán tử giả bù tương đối, qua đó xét toán tử M trong mệnh đề 1 thỏa mãn các tính chất của hàm modus ponens tổng quát, nhưng việc lập luận xấp xỉ ở trên của chúng ta không phải thông qua việc tính toán dựa vào hàm thuộc trong logic mờ mà lập luận trên biến ngôn ngữ như cách suy nghĩ thông thường của con người. TÀI LIỆU THAM KHẢO 1. Huỳnh Văn Nam, Một cơ sở đại số cho logic mờ Zadeh và tính toán trên các từ, Luận án Tiến sĩ Toán học, Hà nội (1999). 2. Lê Xuân Việt, Thuật toán suy diễn trên thông tin không chắc chắn, Luận văn thạc sĩ khoa học, Đảm bảo toán học cho máy tính và hệ thống tính toán, Trường ĐHKHTN, Hà Nội ( 2001). 3. N.C Ho, T.D Khang, H.V Nam, N.H Chau, Hedge Algebras, Linguistic-Valued and Their Application to Fuzzy Reasoning, Inter. 69
J. of Uncertainty, Fuzziness and Knowledge-Based System 7 (4) (1999) 347 - 361. 4. Nguyen Cat Ho, Tran Thai Son, Tran Đinh Khang and Le Xuan Viet, Fuzziness Measure, Quantified Semantic Mapping and Interpolative Method of Approximate Reasoning in Medical Expert Systems, Tạp chí Tin học và Điều khiển học, T.18, S.3 (2002) 237 - 252. 5. Trần Thái Sơn, Nguyễn Thế Dũng, Một số vấn đề về lập luận xấp xỉ trên cơ sở Đại số gia tử, Báo cáo Hội nghị Tin học Toàn quốc, Đà Nẵng (2004). 6. Nguyễn Thanh Thuỷ. Trí tuệ nhân tạo, NXBGD (1997). 7. Phan Xuân Minh, Nguyễn Doãn Phước, Lý thuyết điều khiển mờ, NXBKH và KT (1999) 8. Trần Đình Khang, Ứng dụng đại số gia tử đối sánh các giá trị ngôn ngữ, Tạp chí Tin học và điều khiển học, T.14, S.3 (1998) 35 - 41. 9. Trần Đình Khang. So sánh suy diễn mờ và suy luận ngôn ngữ, Tạp chí Tin học và điều khiển học, T.12, S.1, (1996) 29 - 40. 10. Trần Đình Khang. Tích hợp các đại số gia tử cho suy luận ngôn ngữ, Tạp chí Tin học và điều khiển học, T.1, S.3, (1997) 63 - 80. 70
11. Trần Đình Khang, Xây dựng hàm đo trên đại số gia tử và ứng dụng trong lập luận ngôn ngữ, Tạp chí Tin học và điều khiển học, T.13, S.1 (1997)16 - 30. 12. Trần Thái Sơn. Lập luận xấp xỉ với các giá trị của biến ngôn ngữ, Tạp chí Tin học và Điều khiển học, Tập 15, S.2 (1999) 6 - 10. 13. E. Trillas, L. Valverde. On modus ponens in fuzzy logic, Proceeding of the fifteenth international symposium of moltiple valued logics, 0915 -623X/85/0000/0294$01.00 IEEE (1985). 14. Akdag H, Khoukhi F, Sercoun C. Approimative Reasoning using Linguistic Valuations, The eigth International Symposium on Computer and Information Sciences, Istanbul (1993). TÓM TẮT Trong bài báo này chúng tôi trình bày việc mở rộng modus ponens trên cơ sở tri thức được biểu diễn dưới dạng luật If ... then ... với cấp độ đúng (true - degree) và cấp độ tin cậy (certain-degree) trên cơ sở đại số gia tử. APPROXIMATE REASONING WITH MODUS PONENS 71
BASED ON HEDGE ALGEBRA Nguyen The Dung College of Pedagogy, Hue University SUMMARY In this paper, we introduce about expending modus ponens on knowledge base which present by If ... then rules with true -degree and certain-degree based on hedge algebra. 72