HỆ THỐNG LUẬT SINH (HỆ SINH – PRODUCTION SYSTEM)

Định nghĩa hệ sinh

Hệ sinh là một mô hình tính toán quan trọng trong trí tuệ nhân tạo về cả hai mặt: thực hiện các thuật toán tìm kiếm và mô hình hóa việc giải các bài toán của con người.

Một hệ sinh được định nghĩa bởi:

• Tập luật sinh(Production rules): Mỗi luật sinh có dạng condition → action (điều kiện → hành động). Phần điều kiện của luật là một mẫu cho biết khi nào thì có thể áp dụng luật. Phần hành động quy định các bước giải toán tương ứng điều kiện.
• Bộ nhớ làm việc (Working memory): Chứa một mô tả về trạng thái hiện thời của bài toán trong quá trình suy luận. Mô tả này là một mẫu sẽ được đối sánh với phần điều kiện của một luật sinh để chọn ra bước giải thích hợp. Khi phần điều kiện của luật phù hợp với nội dung trong bộ nhớ làm việc, hành động phát sinh từ điều kiện đó sẽ được thực hiện làm thay đổi nội dung bộ nhớ làm việc.
• Chu trình nhận dạng - hành động (Recognize – act cycle) : Là cấu trúc điều khiển của hệ sinh.

Cấu trúc điều khiển của một hệ sinh khá đơn giản: Bộ nhớ làm việc được khởi đầu với mô tả của bài toán. Trạng thái hiện hành của việc giải bài toán được duy trì dưới dạng một tập các mẫu trong bộ nhớ làm việc. Các mẫu này được đối sánh với phần điều kiện của các luật sinh, các luật có điều kiện phù hợp với mẫu trong bộ nhớ làm việc được gọi là tập luật tranh chấp (conflict set). Sau đó một trong các luật sinh này sẽ được chọn và được kích hoạt. Để kích hoạt một luật, phần hành động của nó được thục hiện và làm thay đổi nội dung bộ nhớ làm việc. Chu trình điều khiển sẽ lặp lại với nội dung đã được thay đổi trong bộ nhớ làm việc. Quá trình này kết thúc khi nội dung của bộ nhớ làm việc không còn phù hợp với điều kiện của luật nào nữa.

Một quá trình giải quyết tranh chấp (conflict resolution) sẽ chọn một luật từ tập luật tranh chấp để kích hoạt. Chiến lược giải quyết tranh chấp có thể rất đơn giản như chọn luật đầu tiên có điều kiện phù hợp hoặc có thể dựa vào các heuristic chọn luật phức tạp. Đây là một khâu quan trọng để các hệ sinh có thể đưa khả năng điều khiển heuristic vào một thuật toán tìm kiếm.

Một sơ đồ của hệ sinh được mô tả như hình sau:

Hình 5.1 – Cấu trúc hệ sinh

Thí dụ 5.1: Một chương trình hệ sinh đơn giản dùng để sắp xếp một dãy các chữ cái a,b,c theo thứ tự từ điển. Trong ví dụ này, một luật sinh sẽ được áp dụng nếu điều kiện của nó phù hợp với một phần của dãy chữ cái trong bộ nhớ làm việc. Khi một luật được kích hoạt, phần dãy phù hợp với điều kiện luật này được thay thế bởi dãy ở phần hành động của luật đó.

Hình 5.2 – Các bước thực hiện của một hệ sinh đơn giản

Một số ví dụ về hệ sinh

Thí dụ 5.2: Bài toán trò đố 8 ô

Không gian tìm kiếm do trò đố 8 ô sinh ra vừa đủ phức tạp để khảo sát và cũng vừa đủ nhỏ để có thể theo dõi, cho nên ta thường hay sử dụng nó để minh họa cho các chiến lược tìm kiếm khác nhau như tìm kiếm sâu, tìm kiếm rộng, cũng như các chiến lược tìm kiếm heuristic. Nó cũng thích hợp với việc giải bằng hệ sinh. Các nước đi hợp lệ được trình bày như các luật trong hình. Trong trường hợp trạng thái bắt đầu và trạng thái đích của trò chơi được xác định, chúng ta có khả năng áp dụng một hệ sinh cho không gian tìm kiếm của bài toán.

Hình 5.3 – Trò đố 8 ô dưới dạng một hệ sinh

Thí dụ 5.3: Bài toán đường đi quân mã (Knight’s tour problem)

Bài toán đường đi quân mã trên bàn cờ vua cũng có thể được giải bằng cách sử dụng hệ sinh. Mỗi nước đi sẽ được biểu diễn bằng một luật mà phần điều kiện của nó là vị trí của quân cờ tại một ô và phần hành động của nó là vị trí hợp lệ sau khi di chuyển quân cờ. Mười sáu luật sinh sẽ biểu diễn cho tất cả các nước đi hợp lệ của quân cờ. Khởi đầu, bộ nhớ làm việc chứa trạng thái bàn cờ hiện tại và trạng thái đích. Vòng lặp điều khiển sẽ áp dụng các luật cho đến khi trạng thái hiện tại giống trạng thái đích rồi dừng lại. Một chiến lược giải quyết tranh chấp sẽ kích hoạt luật đầu tiên và không tạo vòng lặp. Vì quá trình tìm kiếm có thể dẫn đến những kết thúc chết nên chu trình điều khiển cho phép lần ngược.

Hình 5.4 – Giải pháp hệ sinh cho bài toán đ ư ờng đi quân mã

Điều khiển chọn chiến lược tìm kiếm hướng dữ liệu (suy diễn tiến) hay tìm kiếm hướng mục tiêu (suy diễn lùi)

Tìm kiếm hướng dữ liệu bắt đầu với một mô tả bài toán (như một tập các tiền đề logic, các triệu chứng của người bệnh, hay một khối dữ liệu cần suy diễn ...) rồi suy ra các kiến thức mới từ dữ liệu đó. Quá trình này được thực hiện bằng cách áp dụng các luật suy diễn, các nước đi hợp lệ trong một trò chơi hoặc các thao tác sinh ra trạng thái khác vào mô tả hiện hành của bài toán, đồng thời đưa thêm các kết quả vào mô tả bài toán. Quá trình này tiếp tục cho đến khi tiếp cận một mục tiêu.

Hình 5.5 – Tìm kiếm hướng dữ liệu trong một hệ sinh

Mô tả của quá trình suy luận hướng mục tiêu này nhấn mạnh sự gần giống của nó với mô hình hệ sinh của việc tính toán. Trạng thái hiện tại của bài toán được đưa vào bộ nhớ làm việc. Chu trình nhận dạng – hành động sẽ đối sánh trạng thái hiện tại với tập luật sinh (theo thứ tự). Khi các dữ liệu này phù hợp với phần điều kiện của một trong các luật sinh đó, phần hành động của luật sinh sẽ bổ sung thêm (bằng cách thay đổi bộ nhớ làm việc) một thông tin mới vào trạng thái hiện tại của bài toán.

Vì tất cả các luật sinh đều có dạng CODITION→ ACTION. Khi CONDITION phù hợp với một số phần nào đó trong bộ nhớ làm việc, ACTION sẽ được thực hiện.

Hình trên trình bày quá trình tìm kiếm hướng dữ liệu đơn giản dựa vào một tập các luật sinh được biểu diễn dưới dạng phép kéo theo của phép tính mệnh đề. Chiến lược giải quyết tranh chấp đơn giản là chọn luật vừa mới được kích hoạt. Theo ràng buộc này, luật đầu tiên sẽ được chọn. Quá trình thực hiện sẽ dừng lại khi tiếp cận một mục tiêu. Hình này cũng giới thiệu trình tự các luật kích hoạt và trạng thái bộ nhớ làm việc trong quá trình thực hiện cùng với đồ thị của không gian tìm kiếm.

Ta cũng có thể áp dụng tìm kiếm hướng mục tiêu trong các hệ sinh. Để thực hiện điều này, mục tiêu được đưa vào bộ nhớ làm việc và được đối sánh với phần ACTION của các luật sinh (bằng phép hợp nhất chẳng hạn) và phần CODITION cuả luật sẽ được bổ sung vào bộ nhớ làm việc và trở thành các mục tiêu mới của quá trình tìm kiếm. Quá trình này cứ tiếp tục cho đến khi một sự kiện được tìm thấy, thường là trong mô tả ban đầu của bài toán. Quá trình tìm kiếm sẽ dừng lại khi các CODITION của tất cả các luật sinh được kích hoạt đều là đúng. Hình sau là một ví dụ về suy luận hướng mục tiêu. Cần chú ý rằng ta sẽ dừng lại khi các CODITION của tất cả các luật sinh được kích hoạt đều là đúng. Tìm kiếm hướng mục tiêu sẽ kích hoạt loạt luật sinh khác và tiến hành quá trình tìm kiếm trên không gian khác so với kiểu hướng dữ liệu.

Hình 5.6. – Tìm kiếm hướng mục tiêu trong một hệ sinh

Câu hỏi :

Một hệ sinh sử dụng động cơ suy diễn là một chu trình nhận dạng hành động (đối sánh → giải quyết tranh chấp → thi hành luật). Hãy cho biết điểm khác biệt cơ bản tại bước đối sánh (match) khi hệ thống tiến hành suy diễn tiến và suy diễn lùi ?

Điều khiển tìm kiếm thông qua cấu trúc luật

Cấu trúc của các luật trong một hệ sinh bao gồm sự phân biệt giữa phần điều kiện (CONDITION) với phần hành động (ACTION) và thứ tự mà các điều kiện được thử, sẽ quyết định cách tìm kiếm trong không gian.

Trong biểu diễn của phép tính vị từ, các biểu thức chỉ định nghĩa các quan hệ thực trong một lĩnh vực bài toán chứ không khẳng định về thứ tự diễn dịch các thành phần của chúng do đó có thể có một vài cách biểu diễn khác nhau cho cùng một luật nhưng chúng vẫn tương đương về mặt chân trị. Những cách viết này có thể không dẫn đến cùng một kết quả khi được diễn dịch dưới dạng các luật sinh vì việc cài đặt của hệ sinh phải theo một thứ tự trong việc đối sánh và kích hoạt các luật. Hệ sinh thử các luật theo một thứ tự xác định nên người lập trình có thể điều khiển quá trình tìm kiếm thông qua cấu trúc và thứ tự của các luật trong tập luật sinh. Mặc dù tương đương về mặt logic nhưng hai cách thực hiện không như nhau trong một quá trình tìm kiếm.

Các chuyên gia mã hóa các heuristic quan trọng theo những quy luật chuyên môn của họ. Thứ tự của các tiền đề sẽ mã hóa những thông tin quan trọng về trình tự để giải bài toán. Chẳng hạn khi một kỹ sư cơ khí nói rằng “Nếu động cơ không khởi động được và đèn không sáng thì kiểm tra acquy”, tức là anh ta đã đề nghị một trình tự đặc trưng cho các hành động. Thông tin này sẽ không thể hiểu bởi phát biểu logic tương đương “Động cơ khởi động được hoặc đèn sáng hoặc kiểm tra acquy”. Dạng này của các luật rất quan trong trong việc điều khiển tìm kiếm, nó làm cho hệ thống thực hiện một cách logic, làm cho quá trình theo dõi việc kích hoạt các luật dễ hiểu hơn, ...

Điều khiển chọn chiến lược giải quyết tranh chấp

Mặc dù các hệ sinh (giống như tất cả các cấu trúc dùng cho những hệ thống dựa vào kiến thức) cho phép các heuristic được mã hóa vào trong nội dung kiến thức của bản thân các luật, nhưng chúng cũng có nhiều cơ hội khác để điều khiển heuristic thông qua các giải pháp giải quyết tranh chấp. Ví dụ các chiến lược giải quyết tranh chấp được hỗ trợ bởi OPS5 (Brownston và cộng sự -1985) gồm có:

• Chiến lược khúc xạ (refraction): Chiến lược này quy định rằng khi một luật đã được kích hoạt, nó không thể được kích hoạt lại trước khi các phần tử trong bộ nhớ làm việc phù hợp với phần điều kiện của nó thay đổi. Chiến lược này giúp ngăn ngừa vòng lặp.
• Chiến lược vừa mới xảy ra (recency): Chiến lược này chọn những luật có phần điều kiện phù hợp với các mẫu vừa mới được bổ sung vào bộ nhớ làm việc. Chiến lược này giúp tập trung việc tìm kiếm vào một dòng suy luận duy nhất.
• Chiến lược tính chi tiết (specificity): Chiến lược này quy định rằng một luật giải toán chi tiết hơn sẽ được ưa thích hơn luật tổng quát. Một luật có tính chi tiết hơn luật khác nếu nó có nhiều điều kiện hơn. Điều này có nghĩa nó sẽ đối sánh với số mẫu ít hơn trong bộ nhớ làm việc.

Những ưu điểm của hệ sinh dùng cho trí tuệ nhân tạo

Theo các minh họa trên, hệ sinh cho chúng ta một quy tắc chung để thực hiện tìm kiếm. Nhờ tính đơn giản, khả năng cải biến và sự linh hoạt trong việc áp dụng các kiến thức giải toán, hệ sinh đã tỏ ra là một công cụ quan trọng để xây dựng các hệ chuyên gia và các ứng dụng trí tuệ nhân tạo khác. Những ưu điểm chính của các hệ sinh đối với trí tuệ nhân tạo là:

• Tách riêng tri thức và điều khiển: Trong hệ sinh sự điều khiển được cho bởi chu trình nhận dạng – hành động của vòng lặp hệ sinh, còn các kiến thức giải toán được mã hóa vào trong các luật. Ưu điểm của sự tách biệt này là dễ thay đổi loại cơ sở tri thức mà không thay đổi việc điều khiển chương trình và ngược lại.
• Đưa một sắp xếp tự nhiên vào tìm kiếm trong không gian trạng thái: Các phần tử của một hệ sinh sẽ được sắp xếp một cách tự nhiên vào cấu trúc tìm kiếm không gian trạng thái. Các trạng thái kế tiếp của bộ nhớ làm việc sẽ tạo nên các nút của đồ thị. Các luật sinh là các bước chuyển đổi có thể xảy ra giữa các trạng thái cùng với các chiến lược giải quyết tranh chấp sẽ cài đặt việc chọn một nhánh trong không gian trạng thái đó.
• Tính module của luật sinh: Một yếu tố quan trọng của hệ sinh là không có bất kỳ sự tương tác lẫn nhau nào về cú pháp giữa các luật sinh. Các luật chỉ có thể tác động đến việc kích họat các luật khác bằng cách thay đổi mẫu trong bộ nhớ làm việc, chúng không thể “gọi” trực tiếp các luật khác như là một thủ tục con (subroutine), cũng không thể thiết lập giá trị của các biến cho các luật sinh khác. Tính độc lập về cú pháp này đã hỗ trợ cho sự phát triển của các hệ chuyên gia bằng cách liên tục bổ sung, loại bỏ hoặc thay đổi các tri thức (luật) của hệ thống.
• Điều khiển theo mẫu: Các bài toán được chương trình trí tuệ nhân tạo nhằm vào đều yêu cầu phải linh hoạt trong quá trình thực thi chương trình. Mục tiêu này được đáp ứng bởi thực tế là các luật trong hệ sinh có thể kích hoạt theo mọi trình tự. Trong một bài toán, các mô tả tạo nên trạng thái hiện hành sẽ xác định tập luật tranh chấp và do đó cũng sẽ xác định con đường tìm kiếm và lời giải riêng.
• Có cơ hội cho điều khiển heuristic của quá trình tìm kiếm.
• Theo dõi và giải thích: Tính module của các luật và bản chất lặp lại trong quá trình thực thi làm cho nó dễ dàng theo dõi hơn trong một hệ sinh. Ở mỗi giai đoạn của chu trình nhận dạng – hành động, luật được chọn có thể được hiện ra. Vì mỗi luật ứng với một đoạn của quá trình giải toán nên nội dung luật sẽ giải thích đầy đủ ý nghĩa về trạng thái và hành động hiện hành của hệ thống đó.
• Tính độc lập ngôn ngữ: Mô hình điều khiển hệ sinh không phụ thuộc vào cách thể hiện đã được chọn cho các luật và cho bộ nhớ làm việc miễn là cách thể hiện đó hỗ trợ cho việc đối sánh mẫu.

Mô hình hóa việc giải các bài toán của con người: Đây là một trong những ứng dụng đầu tiên của hệ sinh, chúng vẫn còn được dùng làm mô hình cho họat động của con người trong nhiều nghiên cứu khoa học về nhận thức.