Bài 1. PHƯƠNG PHÁP SUY DIỄN TRÊN MÔ HÌNH BDTT

1.1 Biểu diễn tri thức bằng luật dẫn (luật sinh)

1.1.1 Giới thiệu

Phương pháp biểu diễn tri thức bằng luật sinh được phát minh bởi Newell và Simon trong l lần hai ông đang cố gắng xây dựng một hệ giải bài toán tổng quát. Đây là một kiểu biểu diễn tri thức có cấu trúc. Ý tưởng cơ bản là tri thức có thể được cấu trúc bằng một cặp điều kiện & hành động: “NẾU điều kiện xảy ra THÌ hành động sẽ được thi hành”. Chẳng hạn: NẾU đèn giao thông là đỏ THÌ bạn không được đi thẳng, NẾU máy tính đã mở mà không khởi động được THÌ kiểm tra nguồn điện, v.v…

Ngày nay, các luật sinh đã trở nên phổ biến và được áp dụng rộng rãi trong nhiều hệ thống trí tuệ nhân tạo khác nhau. Luật sinh có thể là một công cụ mô tả để giải quyết các vấn đề thực tế thay cho các kiểu phân tích vấn đề truyền thống. Trong trường hợp này, các luật được dùng như là những chỉ dẫn (tuy có thể không hoàn chỉnh) nhưng rất hữu ích để trợ giúp cho các quyết định trong quá trình tìm kiếm, từ đó làm giảm không gian tìm kiếm. Một ví dụ khác là luật sinh có thể được dùng để bắt chước hành vi của những chuyên gia. Theo cách này, luật sinh không chỉ đơn thuần là một kiểu biểu diễn tri thức trong máy tính mà là một kiểu biễu diễn các hành vi của con người.

1.1.2. Khái niệm

Một cách tổng quát luật sinh có dạng như sau:

P1 ^ P2 ^ … ^ Pn -> Q

Tùy vào các vấn đề đang quan tâm mà luật sinh có những ngữ nghĩa hay cấu tạo khác nhau:

• Trong logic vị từ: P1, P2, …, Pn, Q là những biểu thức logic.
• Trong ngôn ngữ lập trình, mỗi một luật sinh là một câu lệnh.

IF (P1 AND P2 AND … AND Pn) THEN Q.

• Trong lý thuyết hiểu ngôn ngữ tự nhiên, mỗi luật sinh là một phép dịch:

ONE -> một.

TWO -> hai.

JANUARY -> Tháng một.

Để biễu diễn một tập luật sinh, người ta thường phải chỉ rõ hai thành phần chính sau:

• Tập các sự kiện F(Facts)

F = {f1, f2, … fn}

(2) Tập các quy tắc R (Rules) áp dụng trên các sự kiện dạng như sau:

 f1 ^ f2 ^ … ^ fi v q

Trong đó, các fi, q đều thuộc F

Ví dụ: Cho 1 cơ sở tri thức được xác định như sau:

• Các sự kiện: A, B, C, D, E, F, G, H, K
• Tập các quy tắc hay luật sinh (rule):

R :={ r1: A -> E

r2: B -> D

r3: H -> A

r4: E ^ G -> C

r5: E ^ K -> B

r6: D ^ E ^ K -> C

r7: G ^ K ^ F -> A}

1.1.2 Cơ chế suy luận trên các luật sinh

• Định nghĩa Suy diễn tiến: (forward chaining, forward reasoning)

Suy diễn tiến nói chung là quá trình suy diễn theo chiều thuận, đi từ giả thiết đến kết luận thông qua việc áp dụng các định luật, định lý, các quan hệ tính toán.

Quá trình suy diễn này xuất phát từ giả thiết với mục đích tạo ra những sự kiện (yếu tố) mới, rồi từ các sự kiện (yếu tố) mới này lại tạo ra sự kiện (yếu tố) mới khác cho đến khi đạt được mục tiêu của bài toán hoặc cho tới khi không còn tìm được luật r thuộc tập Luật của mô hình tri thức K mà có thể áp dụng được để tạo ra các sự kiện (yếu tố) mới (khi quá trình suy diễn bị bế tắc ở bước nào đó).

• Thuật giải suy diễn tiến:

Các ký hiệu:

Hypos: tập các sự kiện giả thiết

Goals: tập các sự kiện mục tiêu

facts: tập các sự kiện đã biết

rules: tập các luật được áp dụng để sinh ra sự kiện mới

R: tập luật trong Cơ sở tri thức

Backward_Chaining:

Bước 1: facts = Hypos;

rules = [];

Bước 2:

while Goals Ë facts do

Bước 2.1: Tìm luật r R có thể áp dụng được trên facts để sinh

ra sự kiện mới.

Bước 2.2: Nếu tìm được r thì:

+ Bổ sung r vào rules

+ Bổ sung sự kiện mới vào facts

Ngược lại: Kết thúc suy luận, không tìm được lời giải

Bước 3: Kết luận tìm được mục tiêu

Giải:

Sự kiện ban đầu:{H, K}

Xét r3: H -> A {A, H, K}

Xét r1: A -> E {A, E, H, K}

Xét r5: E ^ K -> B {A, B, E, H, K}

Xét r2: B -> D {A, B, D, E, H, K}

Xét r6: D ^ E ^ K -> C {A, B, C, D, E, H, K}

• Suy diễn lùi: là quá trình suy luận ngược xuất phát từ một số sự kiện ban đầu, ta tìm kiếm các sự kiện đã “sinh” ra sự kiện này. Một ví dụ thường gặp trong thực tế là xuất phát từ các tình trạng của máy tính, chẩn đoán xem máy tính đã bị hỏng hóc ở đâu.

Chiến lược suy luận được bắt đầu bằng tập sự kiện đã biết, rút ra các sự kiện mới nhờ dùng các luật mà phần giả thiết khớp với sự kiện đã biết, và tiếp tục quá trình này cho đến khi thấy trạng thái đích, hoặc cho đến khi không còn luật nào khớp được các sự kiện đã biết hay được sự kiện suy luận.

Quá trình lập luận lùi: Đối sánh giả thuyết đưa ra với các sự kiện biết trước lưu trong bộ nhớ làm việc:

• Nếu có một sự kiện “khớp” với giả thuyết, thì ta xem như giả thuyết là đúng.
• Nếu không có sự kiện nào khớp với giả thuyết, thì đối sánh giả thuyết với phần kết luận của các luật. Với mỗi luật mà kết luận của luật khớp với giả thuyết, ta đi lùi lại phần điều kiện của luật. Các điều kiện này của luật được xem như các giả thiết mới. Với giả thiết mới, ta lập lại quá trình trên.

Nếu tất cả các giả thuyết được sinh ra trong quá trình phát triển các giả thuyết bởi các luật được chọn thích hợp đều được thoả mãn (đều có trong bộ nhớ làm việc) thì giả thuyết đã đưa ra được xem là đúng. Ngược lại, thì giả thuyết đã đưa ra được xem là sai.

Ví dụ 1: Cơ sở luật về các động vật gồm các luật sau:

r1: IF động vật có lông mao THEN động vật là loài có vú

r2: IF động vật có lông vũ THEN động vật là chim

r3: IF động vật biết bay AND động vật đẻ trứng THEN động vật là chim

r4: IF động vật là loài có vú AND động vật ăn thịt THEN động vật là thú ăn thịt

r5: IF động vật là loài có vú AND động vật có răng nhọn AND động vật có móng vuốt

THEN động vật là thú ăn thịt

r6: IF động vật là thú ăn thịt AND động vật có màu lông vàng hung AND động vật có đốm sẫm THEN động vật là báo Châu Phi

r7: IF động vật là thú ăn thịt AND động vật có màu lông vàng hung AND động vật có vằn đen THEN động vật là hổ

r8: IF động vật là chim AND động vật không biết bay AND động vật có chân dài AND động vật có cổ dài THEN động vật là đà điểu

r9: IF động vật là chim AND động vật không biết bay AND động vật biết bơi AND động vật có lông đen và trắng THEN động vật là chim cánh cụt

Giả sử bộ nhớ làm việc chứa các sự kiện sau:

A có lông vũ

A có chân dài

A có cổ dài

A không biết bay

Chứng minh: A là đà điểu.

1.1.3 Vấn đề tối ưu luật

Tập các luật 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.

1.1.3.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.

1.1.3.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.

1.1.3.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.

1.1.3.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.

1.1.3.5 Thuật toán tối ưu tập luật dẫn

Thuật toán này sẽ tối ưu hóa tập luật đã cho bằng cách 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.

Thuật toán bao gồm các bước chính:

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 THUỘC Vế Phải(r)

Nếu A THUỘC Vế Trái(r) thì Loại A ra khỏi vế phải của R.

Nếu Vế Phải(r) rỗng thì loại bỏ r ra khỏi hệ luật dẫn : R = R \{r}

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) THUỘC BaoĐóng(Vế Trái(r), R-{r}) thì R := R \ {r}

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

S = (R – {r}) È{r1}

Nếu BaoĐóng (X – Ai, S) º BaoĐóng (X, R) thì loại sự kiện A ra khỏi X

1.1.5 Vòng lặp trong suy diễn

Định nghĩa vòng lặp trong suy diễn:

Thuật toá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

Bước 1: 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)

Bước 2: Nếu X (Y)­+R thì luật r gây ra vòng lặp

Ví dụ: Cho tập luật R như sau:

r1: A, M -> N

r2: B, N -> C

r3: A, M -> B

r4: A -> P

r5: D -> M

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 THUỘC (D)+R

1.1.6 Ưu điểm và nhược điểm của biểu diễn tri thức bằng luật

• Ưu điểm:

Biểu diễn tri thức bằng luật đặc biệt hữu hiệu trong những tình huống hệ thống cần đưa ra những hành động dựa vào những sự kiện có thể quan sát được. Nó có những ưu điểm chính yếu sau đây:

• Các luật rất dễ hiểu nên có thể dễ dàng dùng để trao đổi với người dùng (vì nó là một trong những dạng tự nhiên của ngôn ngữ).
• Có thể dễ dàng xây dựng được cơ chế suy luận và giải thích từ các luật.
• Việc hiệu chỉnh và bảo trì hệ thống là tương đối dễ dàng.
• Có thể cải tiến dễ dàng để tích hợp các luật mờ.
• Các luật thường ít phụ thuộc vào nhau.

• Nhược điểm:

• Các tri thức phức tạp đôi lúc đòi hỏi quá nhiều (hàng ngàn) luật sinh. Điều này sẽ làm nảy sinh nhiều vấn đề liên quan đến tốc độ lẫn quản trị hệ thống.
• Thống kê cho thấy, người xây dựng hệ thống trí tuệ nhân tạo thích sử dụng luật sinh hơn tất cả phương pháp khác (dễ hiểu, dễ cài đặt) nên họ thường tìm mọi cách để biểu diễn tri thức bằng luật sinh cho dù có phương pháp khác thích hợp hơn! Đây là nhược điểm mang tính chủ quan của con người.
• Cơ sở tri thức luật sinh lớn sẽ làm giới hạn khả năng tìm kiếm của chương trình điều khiển. Nhiều hệ thống gặp khó khăn trong việc đánh giá các hệ dựa trên luật sinh cũng như gặp khó khăn khi suy luận trên luật sinh.

Áp dụng hệ luật dẫn vào giải bài toán tam giác: Triangle Problem | C++ | Áp dụng Hệ luật dẫn giải bài toán tam giác 

Các bạn có thể xem ở kênh youtube của mình: A* (A-Star) PATHFINDING | C++ | Tìm đường đi ngắn nhất

Và trao đổi với mình theo contact dưới phần description trên Youtube!

Like Loading...

Related