Tài liệu Biểu diễn tri thức và lập luận trong logic mô tả

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HỒ VĂN LÂM BIỂU DIỄN TRI THỨC LUẬN VĂN THẠC SỸ Người hướng dẫn: Nguyễn Thanh Thủy Hà nội - 2005 -1- Mục lục Lời cảm ơn ............................................. Error! Bookmark not defined. Những thuật ngữ viết tắt........................................................................... 3 Mở đầu...................................................................................................... 5 Chương 1 Tổng quan về logic mô tả 1. 1 Nguồn gốc của logic mô tả .................................................................. 7 1.2 Biểu diễn tri thức và lập luận .............................................................. 9 1.3 Sơ lược lịch sử nghiên cứu về logic mô tả.......................................... 11 1.4 Các lĩnh vực ứng dụng logic mô tả .................................................... 12 1.4.1 Lĩnh vực công nghệ phần mềm.................................................. 13 1.4.2 Lĩnh vực xử lý ngôn ngữ tự nhiên ............................................. 13 1.4.3 Lĩnh vực thư viện số và web ...................................................... 14 1.4.4 Các lĩnh vực khác ...................................................................... 15 Chương 2 Biểu diễn tri thức và lập luận trong logic mô tả 2.1 Biểu diễn tri thức............................................................................... 16 2.1.1 Cơ sở tri thức ............................................................................. 16 2.1.2.1 Cú pháp và ngữ nghĩa của ngôn ngữ AL ...................................................18 2.1.2.2 Họ ngôn ngữ AL ...........................................................................................20 2.1.2.3 Ngôn ngữ mô tả một bộ phận của logic vị từ ...........................................22 2.1.3 Thuật ngữ (Terminologies) ........................................................ 23 2.1.3.1 Tiên đề trong TBox......................................................................................23 2.1.3.2 Tiên đề bao hàm (inclusion axiom) trong TBox ......................................27 2.1.4. ABox ......................................................................................... 28 2.1.4.1 Cá thể trong ABox .......................................................................................28 2.1.4.2 Tập cá thể trong ngôn ngữ mô tả ...............................................................30 2.2 Lập luận ............................................................................................ 30 2.2.1 Tác vụ lập luận (suy diễn) cho TBox ......................................... 31 -2- 2.2.2 Cơ chế lập luận trong ABox ...................................................... 33 2.2.3 Luật ............................................................................................ 34 2.2.4 Thuật toán lập luận .................................................................... 35 2.2.4.1 Thuật toán bao hàm (subsumption algorithm) .........................................36 2.2.4.2 Thuật toán thoả (satisfiability algorithm) .................................................37 Chương3 Logic mô tả cho web ngữ nghĩa 3.1 Logic mô tả và web ngữ nghĩa ........................................................... 43 3.1.1 Web ngữ nghĩa là gì? .................................................................... 43 3.1.2 Logic mô tả cho Web ngữ nghĩa .................................................... 45 3.2 Nền tảng của web ngữ nghĩa ............................................................. 46 3.2.1 Logic mô tả SHIQ.......................................................................... 46 3.2.2 Cú pháp biểu diễn web ngữ nghĩa RDF ......................................... 50 3.2.3 Ontology ...................................................................................... 51 3.3 Cơ sở logic mô tả trong ngôn ngữ cho web ngữ nghĩa....................... 52 3.3.1 Ontology inference layer - OIL ..................................................... 52 3.3.2 DAML + OIL ............................................................................... 60 3.3.3 Ngôn ngữ mô tả cấu trúc web OWL .............................................. 63 3.4 Ứng dụng lập luận logic mô tả vào phân tích và thiết kế web ........... 70 Chương 4 Cài đặt thử nghiệm thuật toán lập luận 4.1 Cài đặt thuật toán lập luận................................................................ 74 4.2 Một số kết quả thử nghiệm thuật toán .............................................. 79 Kết luận .................................................................................................. 82 Tài Liệu Tham Khảo .............................................................................. 83 -3- Những thuật ngữ viết tắt AL : Attributive Language, ngôn ngữ logic mô tả cung cấp các khái niệm nguyên tử (atomic concept), khái niệm top (T), khái niệm bottom ( ), phép phủ định khái niệm nguyên tử ( A), phép giao ( ), các ràng buộc với mọi ( R.C) và ràng buộc tồn tại đối với khái niệm top ( R.T). ALC : AL mở rộng bằng phép phủ định đầy đủ cho khái niệm bất kỳ ( C). DAML+OIL: DARPA Agent Markup Language và Ontology Inference Language, sự kết hợp giữa hai ngôn ngữ cho web ngữ nghĩa. DL : Description Logic, logic mô tả. GCI : General Concept Inclusion axiom, khái niệm bao hàm tổng quát. HTML : HyperText Markup Language, ngôn ngữ đánh dấu siêu văn bản. OIL : Ontology Inference Language, ngôn ngữ được thiết kế cho web ngữ nghĩa. OWL : Web Ontology Language, ngôn ngữ ontology web dùng cho web ngữ nghĩa. RDF : Resource Description Framework, cú pháp để thể hiện cho các ngôn ngữ web ngữ nghĩa. -4- RDFS : RDF Schema, đồ thị RDF. S : Logic mô tả S, được mở rộng từ ALC bằng các tiên đề của các quan hệ có tính bắc cầu (R+). SH : Logic mô tả SH, được mở rộng từ S bằng các quan hệ có tính kế thừa ( H). SHI : Logic mô tả SHI, được mở rộng từ SH bằng các quan hệ nghịch đảo (I). SHIQ : Logic mô tả SHIQ, được mở rộng từ SHI bằng các lượng từ ràng buộc về số lượng ( Q). SHIQ (D) : Logic mô tả SHIQ(D), được mở rộng từ SHIQ xác định trong một lĩnh vực cụ thể (D). XML : eXtensible Markup Language. W3C : Word Wide Web Consortium. -5- Mở đầu Công việc biểu diễn tri thức và lập luận trên cơ sở tri thức trong các hệ thống xử lý thông tin giữ một vai trò quan trọng cho việc thành công của hệ thống. Xuất phát từ sự quan trọng đó, nhiều tổ chức nghiên cứu khoa học đã bỏ công nghiên cứu, tìm kiếm những công cụ để biểu diễn tri thức một cách thuận lợi nhất và logic mô tả là một trong những công cụ để biểu diễn tri thức được các tổ chức nghiên cứu khoa học sử dụng đến. Logic mô tả (Description logics - DL) là thuật ngữ được sử dụng gần đây để biểu đạt những hình thức biểu diễn tri thức trong một lĩnh vực nào đó. Trước kia, thuật ngữ này được dùng để chỉ ngôn ngữ biểu diễn tri thức, ngôn ngữ khái niệm hay ngôn ngữ biểu diễn cơ sở tri thức KL-ONE. DL cho phép định nghĩa những khái niệm liên quan đến lĩnh vực, sử dụng những khái niệm này để chỉ ra những thuộc tính của những đối tượng, những cá thể trong lĩnh vực đó. Bản thân tên gọi DL đã thể hiện một trong những thuộc tính của ngôn ngữ này là mô tả. Về mặt ngữ nghĩa, có thể xem chúng là ngôn ngữ con của logic vị từ. Một đặc trưng khác là nhấn mạnh vào phần lập luận và xem việc lập luận như một dịch vụ trung tâm. Lập luận là các cơ chế cho phép suy luận được tri thức mới và giúp đưa ra những quyết định từ tri thức đã có trong cơ sở tri thức. DL cung cấp nhiều cách suy luận được dùng rộng rãi trong những hệ thống xử lý thông tin thông minh, ngoài ra còn được sử dụng để xây dựng và hiểu thế giới, phân loại những khái niệm, những cá thể. Hiện nay, logic mô tả đã và đang được ứng dụng trong nhiều lĩnh vực khác nhau như: Xử lý ngôn ngữ tự nhiên, công nghệ phần mềm, cơ sở dữ liệu, y học, Web ngữ nghĩa ... Cộng đồng nghiên cứu về logic mô tả trên thế giới hiện nay có hơn 100 nhóm nghiên cứu đang hoạt động và nhiều tổ chức khoa học khác cũng đang -6- rất quan tâm đến logic mô tả cũng như các ứng dụng của chúng trong công nghiệp. Trong nghiên cứu về logic mô tả, nội dung luận văn gồm 4 chương : Chương 1: Trình bày một cách tổng quan về logic mô tả. Trong phần này cung cấp một cái nhìn tổng quan về logic mô tả: Sự ra đời của logic mô tả, thành tựu và lịch sử nghiên cứu về logic mô tả, cũng như ứng dụng trong những ngành khoa học khác của logic mô tả. Chương 2: Trình bày cách biểu diễn tri thức và lập luận trong logic mô tả. Đây là chương trọng tâm của luận văn nhằm làm sáng tỏ chức năng biểu diễn tri thức, lập luận trên cơ sở tri thức trong những ngôn ngữ logic mô tả điễn hình. Cùng với việc biểu diễn tri thức, ta sẽ sử dụng những dịch vụ lập luận được hỗ trợ cho logic mô tả để đưa ra những tri thức mới hay đưa ra những quyết định. Việc sử dụng hai thuật toán lập luận (thuật toán bao hàm và thuật toán thoả) được giới thiệu trong phần này là đề tài nghiên cứu được quan tâm trong logic mô tả. Chương 3: Trình bày về một lĩnh vực đang được quan tâm của logic mô tả là dùng logic mô tả cho việc phát triển web ngữ nghĩa. Web ngữ nghĩa giúp cho việc thiết kế và tìm kiếm thông tin trên web hiệu quả hơn. Với mục đích như thế, các logic mô tả mở rộng đã trở thành một ngôn ngữ nền tảng trong việc mô tả những trang web, cùng với những thuật toán lập luận của logic mô tả đã giúp việc tìm kiếm các thông tin trên web thuận lợi hơn. Chương này sẽ đề cập đến ý nghĩa của web ngữ nghĩa và các ngôn ngữ mở rộng từ logic mô tả phục vụ cho web ngữ nghĩa. Chương 4: Trình bày việc cài đặt thử nghiệm các thuật toán lập luận trong logic mô tả. Đây là những thuật toán đã được sử dụng để lập luận trong -7- các hệ thống xử lý thông tin. Chương trình thử nghiệm thuật toán lập luận được cài đặt để giải quyết bài toán bao hàm, bài toán thoả trong logic mô tả. Chương 1 Tổng quan về logic mô tả Chương này đề cập đến những động cơ thúc đẩy sự phát triển của logic mô tả như là một hình thức cho việc biểu diễn tri thức cũng như một số ý tưởng cơ bản quan trọng cho nền tảng của những hệ thống đã được tạo ra trong logic mô tả truyền thống. Trong chương này, đầu tiên đề cập đến nguồn gốc của logic mô tả, sau đó sẽ đề cập một cách tổng quát các đặc tính của logic mô tả, các giai đoạn nghiên cứu về logic mô tả và cuối cùng chúng ta điểm qua các lĩnh vực ứng dụng của logic mô tả. 1.1 Nguồn gốc của logic mô tả Logic mô tả bắt nguồn từ mạng ngữ nghĩa (semantic networks) và frame, biểu diễn những khái niệm và lập luận trong chúng có quan hệ với nhau. Cấu trúc của một khái niệm được mô tả bởi một ngôn ngữ (được gọi là ngôn ngữ khái niệm) và những phép toán logic. Với cách tiếp cận của logic kinh điển, việc biểu diễn tri thức thường thông qua các biến vị từ, những phép toán vị từ và lập luận xác định hệ quả logic. Theo cách tiếp cận của phi logic, dựa vào những giao diện đồ hoạ, tri thức được biểu diễn thông qua các cấu trúc dữ liệu đặc biệt và lập luận đựơc hoàn thành bằng những thủ tục có các thao tác giống nhau. Trong số đó có hai ngôn ngữ sử dụng nhiều nhất đó là mạng ngữ nghĩa và Frame. Mặt dù có -8- những khác nhau trong cách ký hiệu giữa mạng ngữ nghĩa và Frame nhưng cả hai thể hiện tri thức bằng hình thức trực quan. Do thuộc tính này, chúng trở thành cơ sở cho sự biểu diễn tri thức trước đây. Đáng tiếc là chúng đã không được chấp nhận lâu dài, vì không biểu diễn đầy đủ những đặc tính ngữ nghĩa và kết quả là các hệ thống có sự khác nhau trong cách sử dụng. Tuy nhiên, về mặt ngữ nghĩa, Frame có thể thay cho logic vị từ, các phần tử cơ sở trong Frame được định nghĩa rõ ràng những tính chất như những vị từ một ngôi mô tả những tập hợp các cá thể và vị từ hai ngôi mô tả mối quan hệ giữa các cá thể. Mặt dù không thể hiện hết tất cả các ràng buộc về ngữ nghĩa như những logic vị từ, nhưng chúng được xem là một thành phần con của logic vị từ. Nghiên cứu về logic mô tả được bắt đầu từ những hệ thống sử dụng thuật ngữ (terminological) để nhấn mạnh đến việc thiết lập những thuật ngữ cơ sở mô tả về một lĩnh vực. Những năm gần đây, logic mô tả trở nên phổ biến. Khi dùng logic mô tả trong các hệ thống biểu diễn tri thức thường dùng từ “khái niệm” (concept) được đề cập đến như là một “biểu thức” của logic mô tả, chúng dùng để mô tả những cá thể và từ “thuật ngữ” (terminology) để diễn tả một cấu trúc được xây dựng, cung cấp một thể hiện biểu diễn cho lĩnh vực quan tâm. Nghiên cứu về logic mô tả đã được nghiên cứu cả phần lý thuyết, cùng với cài đặt những hệ thống biểu diễn tri thức và phát triển ứng dụng trong nhiều lĩnh vực của logic mô tả. Nghiên cứu lý thuyết kết hợp chặt chẽ với thực hành đã trở thành phương pháp luận cho việc nghiên cứu logic mô tả. Bên cạnh đó, nhiều hệ thống được xây dựng trên nền tảng logic mô tả với những chuẩn mô tả và những khả năng biểu diễn tri thức khác nhau. Thêm vào đó, các chuẩn và những thuật toán tính toán trong lập luận cũng được nghiên cứu chi tiết. Những nghiên cứu này xuất phát từ việc sử dụng những -9- cấu trúc được cài đặt trong hệ thống hoặc sự cần thiết của các cấu trúc cho những hệ thống đặc biệt và kết quả đã có những hệ thống mới hiệu quả hơn. 1.2 Biểu diễn tri thức và lập luận Đơn vị cơ bản để xây dựng cú pháp của logic mô tả là các khái niệm nguyên tử “atomic concept” (còn được gọi là concept name) mô tả tập cá thể trong lĩnh vực, các quan hệ nguyên tử “atomic role” mô tả mối quan hệ giữa các cá thể. Sau đó, từ những ký hiệu cơ sở này ta đi xây dựng các loại cấu trúc mới, ví dụ như giao của hai khái niệm C D được dùng để chỉ ra những cá thể mà thuộc cả C và D. Một biểu thức khái niệm trong logic mô tả diễn tả tập hợp tất cả các cá thể thoả những tính chất xác định trong biểu thức. Do đó, khái niệm C D được nhìn nhận dưới góc độ của logic vị từ C(x) D(x), phạm vi của các biến là tất cả những cá thể trong lĩnh vực thể hiện và C(x) đúng với tất cả các cá thể thuộc khái niệm C. Trong logic mô tả còn tập trung vào những cấu trúc để thiết lập mối quan hệ giữa những khái niệm. Ví dụ như giới hạn giá trị được viết R.C yêu cầu tất cả những cá thể trong mối quan hệ R đều thuộc khái niệm C. Về phần ngữ nghĩa, những khái niệm được xác định bởi một tập thể hiện: Một khái niệm được thể hiện như một tập những cá thể và những quan hệ được thể hiện như tập hợp những cặp cá thể. Lĩnh vực của sự thể hiện có thể được chọn tuỳ ý và có thể là vô hạn. Tính vô hạn của lĩnh vực và tính mở của ngữ nghĩa là những đặc tính riêng biệt của logic mô tả. Những khái niệm nguyên tử được thể hiện là một tập con của những thể hiện trong lĩnh vực, trong khi đó ngữ nghĩa của những cấu trúc khác nhau được xác định bởi tập hợp những cá thể được mô tả bởi cấu trúc đó. Ví dụ ta có cấu trúc như C D là tập những cá thể thuộc phần chung của những cá thể được mô tả bởi C và D. Giả sử chúng ta có Person, Male, Woman, Doctor là - 10 - những khái niệm nguyên tử, hasChild là quan hệ nguyên tử. Sử dụng các phép toán giao, hợp và phủ định của những khái niệm chúng ta có thể mô tả khái niệm “những người có giới tính nam” và “trai hoặc gái” như sau: Person Male Male Male Hầu hết những ngôn ngữ cung cấp lượng từ tồn tại đầy đủ và ràng buộc giá trị để chúng có thể mô tả các khái niệm như: 1) “Người phụ nữ có con và tất cả chúng đều là con gái” Woman hasChild. Male 2) “Người có con trai” Person hasChild.Male Lượng từ tồn tại và lượng từ với mọi có ý nghĩa trong việc mô tả mối quan hệ giữa những khái niệm. Một loại quan hệ khác của quan hệ giới hạn là quan hệ ràng buộc về số lượng là ràng buộc lực lượng của những tập hợp cá thể thoả quan hệ. Ví dụ như ( 5hasChild) ( 2hasChild.Doctor). Ràng buộc về số lượng đôi khi cũng được xem là đặc tính riêng biệt của logic mô tả mặc dù chúng ta có thể tìm thấy một vài cấu trúc tương tự trong một số ngôn ngữ cơ sở dữ liệu. Từ những cấu trúc đã giới thiệu, logic mô tả sử dụng chúng để biểu diễn tri thức cho lĩnh vực mà hệ thống đề cập. Việc biểu diễn tri thức thông qua hai thành phần TBox và ABox và được xem là cơ sở tri thức trong các hệ thống. TBox chứa đựng tập hợp những thuật ngữ “Terminology” của lĩnh vực quan tâm và ABox là tập những xác nhận của các cá thể thuộc những khái niệm hay những quan hệ trong TBox. Bên cạnh việc lưu trữ tri thức trong các cơ sở tri thức, việc lập luận trong logic mô tả đóng vai trò quan trọng cho việc - 11 - thành công của các hệ thống sử dụng logic mô tả. Những dịch vụ lập luận cho TBox và ABox cùng với những thuật toán lập luận như thuật toán bao hàm (Subsumption algorithm), thuật toán thoả (Satisfiability algorithm) đã cung cấp cho logic mô tả những công cụ lập luận hữu hiệu để giải quyết các bài toán thực tế. Trong chương tiếp theo sẽ đề cập đến việc biểu diễn tri thức cũng như lập luận trong logic mô tả đầy đủ hơn. Nhiều nghiên cứu về thuật toán lập luận được thực hiện nhằm cải thiện độ phức tạp tính toán trong các thuật toán để được những thuật toán tối ưu và từ đó xây dựng những hệ thống thông tin hữu hiệu hơn. 1.3 Sơ lược lịch sử nghiên cứu về logic mô tả Quá trình nghiên cứu về logic mô tả có thể chia ra làm bốn giai đoạn như sau: Giai đoạn 1: Giai đoạn vào đầu những năm 80, tập trung nghiên cứu về những hệ thống như KL-ONE, LOOM... chủ yếu nghiên cứu cấu trúc những thuật toán. Những hệ thống này đã sử dụng những thuật toán có cấu trúc như thuật toán bao hàm cho việc lập luận. Những nghiên cứu lúc đó tập trung vào các ngôn ngữ mô tả diễn cảm nhưng không có các phép phủ định, lượng từ tồn tại và lượng từ với mọi. Những thuật toán đó được sử dụng rất hiệu quả, nhưng đã gặp một trở ngại lớn trong việc mô tả những logic mô tả không rõ ràng. Giai đoạn 2: Giai đoạn vào giữa những năm 80, trong giai đoạn này tập trung phát triển những thuật toán bảng cho logic mô tả và nghiên cứu về độ phức tạp của kết quả nhận được và cố gắng tìm ra những thuật toán tối ưu cho việc lập luận trong logic mô tả. Giai đoạn 3: Giai đoạn vào những năm cuối của thập niên 80 và những năm đầu của thập niên 90 nghiên cứu về những thuật toán bảng cho logic mô - 12 - tả diễn cảm và tìm ra những thuật toán tối ưu nhất đồng thời nghiên cứu mối liên hệ giữa logic mô tả đến các ngôn ngữ logic khác như modal logic, xác định logic mô tả là một ngôn ngữ con của logic vị từ và những hệ thống đã được tạo ra trong giai đoạn này như FACT, RACE .... Giai đoạn 4: Bắt đầu từ cuối những năm 90 cho đến nay, đây là giai đoạn mà các ứng dụng của logic mô tả được tập trung nghiên cứu và hoàn thiện chúng, tập trung theo hướng tạo ra các ứng dụng và công cụ từ logic mô tả như: - Về cơ sở dữ liệu: Nghiên cứu về tính nhất quán của các lược đồ khái niệm, các truy vấn mang tính bao hàm. - Về ontology và semantic web, Gid và e-science như các kỹ nghệ ontology, lập luận với ontology, những dịch vụ mô tả và khám phá trang web. - Về những cài đặt mang tính thương mại như hệ thống Cerebra của Network Inference Ltd. 1.4 Các lĩnh vực ứng dụng logic mô tả Như đã đề cập trước đây, nghiên cứu về logic mô tả không chỉ là nghiên cứu về lý thuyết hay thực hành mà có sự kết hợp chặt chẽ giữa các kết quả của lý thuyết với sự cài đặt hệ thống. Kết quả làm việc của các thuật toán lập luận và độ phức tạp của chúng có ảnh hưởng rất lớn đến hiệu quả của các hệ thống. Nghiên cứu về các thuật toán lập luận giúp chúng ta phân tích được những khả năng cũng như giới hạn của những hệ thống. Logic mô tả được sử dụng để cài đặt trong nhiều hệ thống và đã chứng minh được tính hiệu quả khi sử dụng logic mô tả. Logic mô tả đã được ứng dụng trong nhiều lĩnh vực và sau đây là một số lĩnh vực ứng dụng điển hình của logic mô tả: - 13 - 1.4.1 Lĩnh vực công nghệ phần mề m Công nghệ phần mềm là một trong những lĩnh vực đầu tiên ứng dụng logic mô tả được thực hiện trong hệ thống AT&T. Ý tưởng chính sử dụng logic mô tả để cài đặt hệ thống thông tin phần mềm “Software Information System” là một hệ thống sẽ cung cấp cho những nhà phát triển phần mềm giúp anh ta tìm thấy những thông tin cần thiết trong hệ thống phần mền lớn. Một trong số những ứng dụng mới nhất của logic mô tả là hệ thống LaSSIE của tác giả Devambu, hệ thống này cho phép người dùng xây dựng thêm quy tắt phân loại cho những khái niệm có quan hệ với nhau trong lĩnh vực để cài đặt các code chương trình. Hệ thống LaSSIE đã có nhiều thành công, nhưng cuối cùng gặp phải những khó khăn trong việc bảo trì cơ sở tri thức. Nhiều ứng dụng logic mô tả cho công nghệ phần mềm được mô tả chi tiết trong tài liệu [2]. 1.4.2 Lĩnh vực xử lý ngôn ngữ tự nhiên Logic mô tả cũng như mạng ngữ nghĩa và Frame, xử lý ngôn ngữ tự nhiên là một lĩnh vực ứng dụng chính. Đặc biệt, khi logic mô tả bắt đầu xuất hiện, phần lớn logic mô tả không chỉ là ứng dụng cho xử lý ngôn ngữ tự nhiên, mà còn nghiên cứu sâu vào những chuẩn khác nhau của các hệ thống sử dụng ngôn ngữ tự nhiên. Sử dụng logic mô tả trong việc xử lý ngôn ngữ tự nhiên tập trung chủ yếu vào việc trình diễn ngữ nghĩa tri thức để có thể truyền đạt được ý nghĩa của câu. Tập trung vào ý nghĩa của từ và ngữ cảnh, trình diễn được những tình huống và lĩnh vực diễn đạt của văn bản. Công việc chính dành cho việc giải quyết những bài toán về sự khác nhau của ngữ nghĩa trong các cú pháp khác nhau được sử dụng trong câu, quá trình xử lý đó được gọi là biểu diễn ngữ nghĩa. Hơn thế nữa, biểu diễn ngữ - 14 - nghĩa tri thức bằng logic mô tả được dùng để hỗ trợ cho những ngôn ngữ tự nhiên. Sự diễn cảm của ngôn ngữ tự nhiên đã dẫn đến những nghiên cứu tập trung vào những mở rộng của logic mô tả. Ngày nay, một số dự án lớn phục vụ việc xử lý ngôn ngữ tự nhiên dựa trên logic mô tả đã và đang được thực hiện[6]. 1.4.3 Lĩnh vực thư viện số và web Mối liên hệ giữa mạng ngữ nghĩa và sự liên kết những cấu trúc được cài đặt trong siêu văn bản (hypertext) đã thúc đẩy sự phát triển của ứng dụng logic mô tả cho việc trình diễn thông tin cho các thư mục, cũng như việc phân lớp và sự phản hồi thông tin trong thư viện số. Những ứng dụng này đã chứng minh hiệu quả của logic mô tả cho việc trình diễn sự phân loại khá phổ biến trong sơ đồ phân loại của thư viện, và chúng đã thể hiện được tính tiện lợi của lập luận bao hàm cho sự phân lớp và phục hồi thông tin. Một số câu hỏi đã được đặt ra cho các kỹ thuật lập luận nhằm để xác định các cá thể trong việc phân lớp đã thúc đẩy việc sử dụng các ngôn ngữ logic mô tả mở rộng. Có thể xem World Wide Web như một mạng ngữ nghĩa, xây dựng những hệ thống đáp ứng những thắc mắc về ngữ nghĩa của web, cho phép người sử dụng đưa ra các câu hỏi về web như việc đặt ra những truy vấn trong cơ sở dữ liệu. Dựa trên mối quan hệ giữa logic mô tả và mạng ngữ nghĩa, một lượng lớn các kế hoạch sử dụng logic mô tả cho việc mô phỏng những cấu trúc web được đề xuất và đã phát triển, cho phép khám phá khả năng lập luận của logic mô tả trong việc thu thập và quản lý thông tin. Gần đây đã có nhiều nỗ lực trong việc sử dụng ngôn ngữ đánh dấu để nắm bắt thông tin chứa đựng trong những trang web, nhờ mối quan hệ giữa logic mô tả và ngôn ngữ đánh dấu như là XML đã mô tả rõ ràng các đặc điểm này, vì thế đã xác định được những đặc tính của logic mô tả cho việc biểu - 15 - diễn tài liệu XML. Hơn thế nữa, việc quan tâm đến những chuẩn cho việc biểu diễn tri thức đã dẫn đến sự phát triển các ngôn ngữ như DAML-ONT, ontology language, OIL được xem là những ngôn ngữ mở rộng của logic mô tả cho ứng dụng web ngữ nghĩa. Những ứng dụng logic mô tả cho web ngữ nghĩa được mô tả chi tiết trong Chương 3. 1.4.4 Các lĩnh vực khác Ngoài các lĩnh vực trên, logic mô tả còn được ứng dụng trong nhiều lĩnh vực khác với những hệ thống khá nổi tiếng được ứng dụng trong thực tế. Logic mô tả ứng dụng trong lĩnh vực y tế với những hệ chuyên gia được xây dựng dựa trên nền tảng logic mô tả. Trong lĩnh vực quản lý dữ liệu, những thuật toán lập luận của logic mô tả đã được ứng dụng để giải quyết một số công việc phổ biến như phân loại dữ liệu, tìm kiếm dữ liệu... và nhiều ứng dụng trong các lĩnh vực khác cũng đang được triển khai trong thực tế. Chương này với mục đích giới thiệu tổng quan về logic mô tả, do đó chỉ tập trung cho việc trình bày những thông tin tổng quan nhất về logic mô tả và một số phần đã được giới thiệu trong chương này sẽ được làm rõ ràng hơn trong các chương tiếp theo. - 16 - Chương 2 Biểu diễn tri thức và lập luận trong logic mô tả Việc biểu diễn tri thức và lập luận từ những tri thức đã có để đưa ra những tri thức mới hay những quyết định trong các hệ thống xử lý thông tin là công việc được nghiên cứu trong suốt quá trình nghiên cứu về logic mô tả. Trong chương này, chúng ta sẽ đề cập đến những chức năng biểu diễn tri thức và lập luận một cách cụ thể. 2.1 Biểu diễn tri thức 2.1.1 Cơ sở tri thức Một hệ thống biểu diễn tri thức (knowledge representation) được xây dựng bằng logic mô tả cung cấp những công cụ hữu hiệu, dễ dàng trong việc cài đặt cơ sở tri thức, lập luận và vận dụng những cơ sở tri thức này. TBox Reasoning Description language ABox KB Applications programs Rules - 17 - Hình 2.1: Mô tả một cơ sở tri thức trong hệ thống DL Một cơ sở tri thức bao gồm hai thành phần TBox và ABox. Trong đó TBox là tập các thuật ngữ (Terminology) là bộ từ vựng của một lĩnh vực ứng dụng còn ABox chứa những xác nhận (assertions) về những cá thể trong bộ từ vựng này. Bộ từ vựng bao gồm những khái niệm (concept) diễn tả những tập các cá thể và những quan hệ (role) diễn tả những mối quan hệ hai ngôi giữa những cá thể. Bên cạnh đó còn có những khái niệm nguyên tử (atomic concept), những quan hệ nguyên tử (atomic role) và những khái niệm mô tả (description concept) mà hệ thống DL cho phép sử dụng để xây dựng những mô tả phức tạp cho những khái niệm và những mối quan hệ. Ngôn ngữ dùng cho việc xây dựng những mô tả là một đặc trưng của những hệ thống được xây dựng bởi logic mô tả. Các hệ thống khác nhau được phân biệt bằng những ngôn ngữ mô tả chúng. Vì thế, TBox và ABox có thể xem như định nghĩa trong logic vị từ, trong một vài trường hợp khác chúng được xem như là mở rộng của logic vị từ. Một hệ thống logic mô tả không chỉ lưu trữ terminology và assertions, chúng còn đưa ra các dịch vụ lập luận. Các dịch vụ này chúng ta sẽ tìm hiểu rõ ở phần sau. Trong bất kỳ một ứng dụng, một hệ thống biểu diễn tri thức luôn đặt trong một môi trường rộng lớn. Những đối tượng khác tương tác với thành phần biểu diễn tri thức được thực hiện bằng việc truy vấn cơ sở tri thức và chỉnh sửa nó bằng cách thêm vào hoặc bớt đi những khái niệm, những quan hệ và những xác nhận. Cơ chế giảm hay tăng những xác nhận được thực - 18 - hiện bởi những luật, đây chính là phần mở rộng của logic chuẩn, là nòng cốt để giải thích về tính logic . 2.1.2 Ngôn ngữ mô tả Cơ sở để mô tả là các khái niệm nguyên tử (atomic concept) và các quan hệ nguyên tử (atomic role). Những mô tả phức tạp thì được quy nạp bằng những khái niệm mô tả. Chúng ta sử dụng ký hiệu A và B cho những khái niệm nguyên tử, R cho quan hệ nguyên tử và C, D cho những khái niệm mô tả. Những ngôn ngữ mô tả được phân biệt nhau bởi cú pháp của chúng. Ta sẽ lần lượt tìm hiểu các ngôn ngữ khác nhau. Ngôn ngữ AL (attributive language) được giới thiệu lần đầu vào năm 1991 của các tác giả Schmidt-SchauB và Smolka. AL là một ngôn ngữ cơ bản nhất được quan tâm đến. Những ngôn ngữ khác thuộc họ ngôn ngữ này là mở rộng của ngôn ngữ AL. 2.1.2.1 Cú pháp và ngữ nghĩa của ngôn ngữ AL Những khái niệm mô tả trong AL được tạo thành theo cú pháp như sau: C, D -> A | (khái niệm nguyên tử) T | (khái niệm đỉnh hay vũ trụ) | (khái niệm đáy) A | (phủ định nguyên tử) C D | (giao) R.C | (hạn chế giá trị) R.T (lượng từ tồn tại) - 19 - Trong ngôn ngữ AL, phép phủ định chỉ được áp dụng cho các khái niệm nguyên tử và lượng từ tồn tại chỉ được phép đi với khái niệm đỉnh T (Top concept). Ví dụ, ta có Person và Female là những khái niệm nguyên tử thì Person Female và Person Female là những khái niệm mô tả trong AL. Giả sử ta có một quan hệ nguyên tử hasChild chúng ta có thể xây dựng các khái niệm Person hasChild.Female diễn tả những người có hasChild.T và Person con và tất cả các con của họ là con trai. Để xác định ngữ nghĩa của những khái niệm trong AL chúng ta xét bộ I thể hiện I bao gồm: Một tập khác rỗng là lĩnh vực thể hiện và một hàm thể hiện xác định một khái niệm nguyên tử A là một tập AI nguyên tử R là quan hệ hai ngôi R I I I và quan hệ I . Hàm thể hiện được mở rộng cho x những khái niệm mô tả bằng những định nghĩa quy nạp sau: I T = I = ( A)I = I \ AI D)I = CI (C ( R.C)I = {a I I ( R. T)I = {a | b (a, b) I DI RI -> b CI} | b (a, b) RI } Hai khái niệm C và D được gọi là tương đương và được viết C CI DI cho tất cả các thể hiện I. Ví dụ hai khái niệm hasChild.Student và hasChild.(Female D nếu hasChild.Female Student) là tương đương.