Tài liệu Xử lý các câu truy vấn và tìm kiếm trên kho tài liệu có chú thích ngữ nghĩa bằng tiếng anh

Cũng d Đại Học Quốc Gia TP. Hồ Chí Minh TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------o0o---------- LUẬN VĂN ĐẠI HỌC XỬ LÝ CÁC CÂU TRUY VẤN VÀ TÌM KIẾM TRÊN KHO TÀI LIỆU CÓ CHÚ THÍCH NGỮ NGHĨA BẰNG TIẾNG ANH Chuyên ngành: Khoa Học Máy Tính GVHD : Pgs.Ts. Cao Hoàng Trụ Sinh viên : Nguyễn Trần Đăng Khoa (50601130) Tạ Tất Tài (50602084) TP. Hồ Chí Minh, tháng 12 – 2010 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : PGS.TS. CAO HOÀNG TRỤ Cán bộ chấm nhận xét 1 : ......................................................................................... Cán bộ chấm nhận xét 2 : ......................................................................................... Luận văn đại học được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN ĐẠI HỌC TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . . tháng . . . . năm . . . . . LỜI CAM ĐOAN Tôi cam đoan rằng ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường đại học nào khác. Ngày................ Tháng ............ Năm .......... Ký tên LỜI CẢM ƠN Trước hết, chúng tôi xin gởi lời cảm ơn chân thành và sâu sắc đến Pgs.Ts. Cao Hoàng Trụ, và kỹ sư Châu Kim Cường, những người đã trực tiếp hướng dẫn tôi trong quá trình làm luận văn này. Sự hướng dẫn chu đáo, tận tình, cùng với những tài liệu và lời khuyên quý giá của thầy và anh trong hơn 3 tháng qua là nhân tố không thể thiếu để chúng tôi có thể hoàn thành nhiệm vụ. Chúng tôi xin gửi lời cảm ơn đến gia đình và bạn bè, những người luôn sát cánh, động viên, và tạo mọi điều kiện tốt nhất để chúng tôi có thể học tập và hoàn tất được luận văn tốt nghiệp này. Chúng tôi chân thành biết ơn sự tận tình dạy dỗ và sự giúp đỡ của tất cả quý thầy cô khoa Khoa học và Kỹ thuật Máy tính trường Đại học Bách khoa. Luận văn này khó tránh khỏi còn thiếu sót do tầm nhìn của chúng tôi còn hạn hẹp, rất mong nhận được sự góp ý của quý thầy cô cùng các bạn. TÓM TẮT Từ khi ra đời đến nay, World Wide Web đã trở thành một công cụ quan trọng để lưu trữ và chia sẻ nguồn tri thức khổng lồ. Tuy nhiên, các công cụ phần mềm hiện nay chưa hỗ trợ thật hiểu quả cho con người trong quá trình khai thác kho tri thức ấy. Với mong muốn làm hiệu quả hơn quá trình đó, luận văn này xây dựng một công cụ tìm kiếm có thể “hiểu” được nội dung của câu truy vấn bằng tiếng Anh và trả về kết quả. Để biên dịch câu truy vấn ngôn ngữ tự nhiên, luận văn này dựa trên nền tảng web ngữ nghĩa, kết hợp với phương pháp dịch ít phụ thuộc vào cú pháp của nhóm VN-KIM. Để thể hiện nội dung biên dịch được, luận văn biểu diễn bằng đồ thị ý niệm. Cuối cùng, câu truy vấn SeRQL được dùng để tìm kiếm kết quả. Hiệu quả của hệ thống được đánh giá trên tập câu truy vấn mẫu “TREC 2002”. MỤC LỤC CHƯƠNG 1 TỔNG QUAN ............................................................ Error! Bookmark not defined. 1.1 Giới thiệu....................................................................................................................... 1 1.2 Mục tiêu và phạm vi ...................................................................................................... 3 1.3 Cấu trúc luận văn ........................................................................................................... 5 CHƯƠNG 2 6 CÁC NGHIÊN CỨU VÀ HỆ THỐNG LIÊN QUAN ....................... Error! Bookmark not defined. 2.1 Rút trích quan hệ............................................................................................................ 6 2.2 Sơ lược về đồ thị ý niệm ................................................................................................ 7 2.2.1 Đồ thị ý niệm mở rộng ............................................................................................. 9 2.2.2 Các phương pháp chuyển đổi câu truy vấn sang đồ thị ý niệm . Error! Bookmark not defined. CHƯƠNG 3 12 PHƯƠNG PHÁP TIẾP CẬN .........................................................................................................12 3.1 Chuyển đổi câu truy vấn với từ để hỏi “How many” .................................................... 12 3.2 Chuyển đổi câu truy vấn có tính từ ............................................................................... 14 3.3 Chuyển đổi câu truy vấn có tính từ so sánh nhất ........................................................... 16 3.4 Chuyển đổi câu truy vấn có liên từ luận lý ................................................................... 17 CHƯƠNG 4 21 PHƯƠNG PHÁP BIÊN DỊCH ......................................................... Error! Bookmark not defined. 4.1 Các bước của giải thuật ................................................................................................ 21 4.1.1 Phân tách câu truy vấn ............................................................................................23 4.1.2 Nhận biết thực thể có tên.........................................................................................23 4.1.3 Nhận biết thực thể không tên...................................................................................23 4.1.4 Nhận biết tính từ .....................................................................................................24 4.1.5 Nhận biết từ quan hệ ...............................................................................................24 4.1.6 Xác định lớp của thực thể ........................................................................................24 4.1.7 Gom các thực thể ....................................................................................................25 4.1.8 Xác định quan hệ ẩn ................................................................................................26 4.1.9 Xác định loại quan hệ giữa các thực thể ..................................................................26 4.1.10 Xoá bỏ quan hệ không phù hợp ...............................................................................29 4.1.11 Xác định quan hệ giữa tính từ và thực thể................................................................30 4.1.12 Xây dựng đồ thị ý niệm ...........................................................................................33 4.2 Tập luật ....................................................................................................................... 33 4.2.1 Cấu trúc của hệ thống luật .......................................................................................34 4.2.2 Cấu trúc thành phần điều kiện của luật ....................................................................35 4.2.3 Cấu trúc thành phần hành động của luật ..................................................................35 4.2.4 Xây dựng một số luật đặc biệt .................................................................................36 4.2.5 Xây dựng từ điển luật ..............................................................................................37 4.3 Kết quả thí nghiệm....................................................................................................... 39 CHƯƠNG 5 47 ĐỒ THỊ Ý NIỆM ............................................................................. Error! Bookmark not defined. 5.1 Lưu trữ đồ thị............................................................................................................... 55 5.2 Hiển thị đồ thị ................................................................ Error! Bookmark not defined. CHƯƠNG 6 62 KẾT LUẬN 62 TÀI LIỆU THAM KHẢO ..............................................................................................................64 PHỤ LỤC A: TẬP CÂU MẪU TREC 2002.............................................................................................68 PHỤ LỤC C: ĐỒ THỊ Ý NIỆM SINH ĐÚNG TỪ TREC 2002 TRƯỚC KHI LÀM GIÀU ONTOLOGY.............73 PHỤ LỤC D: ĐỒ THỊ Ý NIỆM SINH ĐÚNG TỪ TREC 2002 SAU KHI LÀM GIÀU ONTOLOGY..................74 DANH MỤC HÌNH Hình 2.1: Ví dụ về đồ thị ý niệm. ............................................... Error! Bookmark not defined. Hình 2.2: Ví dụ về biểu diễn câu truy vấn sử dụng HA (Hypostatic abstraction). ...............Error! Bookmark not defined. Hình 2.3: Ví dụ về biểu diễn câu truy vấn lồng nhau sử dụng đỉnh truy vấn con. ...............Error! Bookmark not defined. Hình 3.1: Ví dụ về biểu diễn câu truy vấn "How many". ..........................................................13 Hình 3.2: Ví dụ về biểu diễn câu truy vấn "How many" ở dạng rút gọn. ...................................13 Hình 3.3: Ví dụ về biểu diễn tổng quát cho câu truy vấn "How many". ....................................13 Hình 4.1: Mô tả các bước dùng để xây dựng đồ thị ý niệm cho câu truy vấn. ............................22 Hình 4.2: Xác định loại quan hệ giữa hai thực thể ei và ej. ........................................................27 Hình 4.3: Lược đồ ánh xạ kiểu quan hệ của bộ ba truy vấn. ......................................................28 Hình 4.4: Xác định loại quan hệ giữa tính từ adj và thực thể. ....................................................31 Hình 4.5: Lược đồ ánh xạ kiểu quan hệ giữa tính từ và thực thể. ..............................................32 Hình 4.6: Cấu trúc tập thành phần TransformRules và rule. ......................................................34 Hình 4.7: Cấu trúc của thành phần điều kiện luật......................................................................36 Hình 4.8: Ví dụ về thành phần premise.....................................................................................36 Hình 4.9: Cấu trúc của thành phần hành động. .........................................................................37 Hình 4.10: Cấu trúc từ điển quan hệ. ..........................................................................................38 Hình 4.11: Ví dụ một luật hoàn chỉnh. ........................................................................................38 Hình 4.12: Ví dụ một số thành phần trong từ điển. .....................................................................38 Hình 4.13: Ví dụ về biểu diễn câu truy vấn “Queried relation”. ..................................................42 Hình 4.14: Ví dụ về biểu diễn câu truy vấn “Advert / Temporal”. ..............................................42 Hình 5.1: defined. Cấu trúc dữ liệu sử dụng để lưu trữ đồ thị ý niệm kết quả. ........ Error! Bookmark not Hình 5.2: defined. Cấu trúc dữ liệu sử dụng để hiển thị đồ thị ý niệm kết quả. ....... Error! Bookmark not Hình 5.3: defined. Ví dụ về kết quả phương pháp lưu trữ và hiển thị đồ thị ý niệm.Error! Bookmark not DANH MỤC BẢNG Bảng 4.1: Bảng thuộc tính thành phần premise. ........................................................................35 Bảng 4.2: Mô tả các thuộc tính của thành phần entry. ...............................................................38 Bảng 4.3: Kết quả thực nghiệm trên TREC 2002 khi chưa áp dụng phương pháp đề nghị. ........40 Bảng 4.4: Kết quả thực nghiệm trên TREC 2002 sau khi áp dụng phương pháp đề nghị. ..........40 Bảng 4.5: Kết quả thực nghiệm trên TREC 2002 sau khi làm giàu Ontology. ...........................41 Bảng 4.6: Bảng tổng kết kết quả cuối cùng đạt được trên tập TREC 2002. ................................43 Bảng 4.7: Kết quả thực nghiệm trên TREC 2007 khi chưa áp dụng phương pháp đề nghị. ........44 Bảng 4.8: Kết quả thực nghiệm trên TREC 2007 sau khi áp dụng phương pháp đề nghị. ..........44 Bảng 4.9: Kết quả thực nghiệm trên TREC 2007 sau khi làm giàu Ontology. ...........................45 Bảng 4.10: Bảng tổng kết kết quả cuối cùng đạt được trên tập TREC 2007. ................................46 CHƯƠNG 1 TỔNG QUAN 1.1 Giới thiệu Kể từ khi ra đời đến nay, World Wide Web (WWW) đã làm thay đổi rất nhiều cách con người trao đổi và tiếp cận với thông tin, tri thức. Và đối với nền kinh tế tri thức hiện nay, tầm quan trọng của WWW càng lớn hơn. Điều đó đặt ra yêu cầu là: phải làm sao để quá trình khai thác tri thức từ WWW đạt được hiệu suất tối ưu. Muốn vậy, một giải pháp là phải tự động hóa được quá trình đó; nói cách khác, máy móc phải có khả năng khai thác thông tin trên WWW với một độ chính xác cao. Hiện nay, đã có những công cụ phần mềm nhắm đến mục tiêu đó. Nổi bật nhất có lẽ là các động cơ tìm kiếm dựa trên từ khóa (keyword – based search engine), như động cơ tìm kiếm của Google, Yahoo,... Tuy đã đạt được những thành công nhất định, nhưng các hệ thống này còn có những khuyết điểm làm cho người sử dụng chưa được hài lòng. Có thể nêu ra như:  Kết quả trả về cho một truy vấn là nhiều, nhưng độ chính xác lại thấp. Người dùng phải tốn nhiều thời gian với những kết quả không thích hợp.  Kết quả trả về hoàn toàn phụ thuộc vào từ khóa được cung cấp. Trong khi, theo mong muốn của con người, thì các truy vấn tương tự nhau về mặt ngữ nghĩa phải dẫn đến những kết quả như nhau. Do công cụ tìm kiếm chủ yếu chỉ so trùng, mà chưa “hiểu” được nội dung của thông tin chứa trên WWW và nội dung của câu truy vấn, nên dẫn đến những hạn chế trên. Như vậy, để làm tăng hiệu quả của quá trình tìm kiếm tự động, một hướng tiếp cận là làm cho máy tính “hiểu” được nội dung của thông tin: thông tin được lưu trữ trên WWW và thông tin trong câu truy vấn của người dùng. 1 Đề tài này quan tâm đến khía cạnh giúp cho máy tính hiểu được nội dung của câu truy vấn dùng ngôn ngữ tự nhiên là tiếng Anh. Nhìn chung, việc hướng dẫn cho máy tính xử lý 1 câu truy vấn bằng ngôn ngữ tự nhiên (bất kỳ) nhằm hiểu được ý nghĩa là khá phức tạp, có thể liệt kê ra một số khó khăn:  Ngữ pháp của ngôn ngữ tự nhiên rất đa dạng, cách sử dụng rất linh hoạt. Và một câu có thể có nhiều ngữ pháp phù hợp (mặc dù đối với con người sẽ không có nghĩa). Dẫn đến không thể chỉ dựa vào cấu trúc của câu để xác định ngữ nghĩa.  Cùng một từ nhưng có thể ứng với nhiều từ loại (danh từ, động từ, ...). Muốn hiểu đúng phải xác định đúng loại từ. Lấy ví dụ: “Time flies like an arrow”. “Time” và “flies” có ít nhất 2 cách hiểu có ý nghĩa: “Time” làm danh từ và “flies” làm động từ, hay “Time” làm động từ và “flies” làm danh từ.  Phải giải quyết sự đa hình của từ (morphology) nếu muốn nhận biết đầy đủ các thành phần của câu. Ví dụ như động từ “fly” có thể có dạng “flies”, “flying”, “flew”.  Việc xác định quan hệ ngữ nghĩa giữa các đối tượng trong câu đòi hỏi phải có tri thức về các mối quan hệ phù hợp giữa các đối tượng. Và phải xem xét ngữ cảnh của câu để chọn ra quan hệ phù hợp nhất.  Câu có thể hàm chứa những mối quan hệ ngầm giữa các đối tượng, mà không được biểu hiện ra bằng các từ ngữ biểu diễn quan hệ, vì các mối liên hệ này được con người ngầm thỏa thuận trên một nền tảng kiến thức chung.  Một cách thường xuyên, câu truy vấn bằng ngôn ngữ tự nhiên không chặt về ngữ pháp, mà thường được dùng ở dạng thông dụng không “chuẩn” ngữ pháp. Tuy có nhiều khó khăn như đã kể trên, nhưng hiện nay các nhóm nghiên cứu về lĩnh vực web ngữ nghĩa đã đạt được những tiến bộ đáng kể. Và việc xây dựng một động cơ tìm kiếm theo ngữ nghĩa là khả thi, có thể thành công với những câu truy vấn không quá phức tạp. Vì vậy, đề tài này sẽ ứng dụng các thành tựu đó để xây dựng một động cơ tìm kiếm cho phép người dùng truy vấn bằng ngôn ngữ tự nhiên, và trả về tài liệu chứa nội dung cần tìm. 2 1.2 Mục tiêu và phạm vi Đề tài này sẽ xây dựng một hệ thống tìm kiếm dựa trên ngữ nghĩa. Dữ liệu đầu vào sẽ là một câu truy vấn bằng tiếng Anh. Hệ thống, sau khi xử lý, sẽ trả về tài liệu chứa thông tin được tìm kiếm hoặc trả về số liệu được yêu cầu (lúc này không sử dụng chức năng tìm kiếm mà chỉ đưa ra số liệu trả lời). Đồng thời, để giúp người dùng kiểm tra liệu cách “hiểu” câu truy vấn của hệ thống có đúng hay không, hệ thống cũng vẽ ra đồ thị ý niệm tương ứng với câu truy vấn đã nhận vào. Một hệ thống như vậy nếu xây dựng mới hoàn toàn sẽ đòi hỏi rất nhiều thời gian và công sức. Vì vậy, đề tài sẽ dựa trên hệ thống tìm kiếm ngữ nghĩa cho tiếng Việt (VN-KIM Search) có sẵn [tham khảo anh Dũng], tái sử dụng nhiều mô-đun không phụ thuộc vào ngôn ngữ, như mô-dun chú giả, đánh chỉ mục, gom cụm, truy xuất tài liệu, chỉ tập trung làm mới mô-dun xử lý câu truy vấn. Hệ thống sẽ bảo đảm được khả năng xử lý những câu truy vấn tiếng Anh đơn giản, chỉ bao gồm danh từ, động từ, từ để hỏi và giới từ. Ví dụ như câu truy vấn: “What actress starred in “The Lion in Winter” ?”. Đây là khả năng mà hiện nay VN-KIM Search đã làm được cho tiếng Việt. Luận văn không chỉ dừng lại ở những câu truy vấn đơn giản như ví dụ trên, mà còn nhắm đến mục tiêu trả lời được những câu truy vấn phức tạp hơn. Đó là câu truy vấn có liên từ luận lý, tính từ định tính, tính từ định lượng, tính từ so sánh nhất, và lượng từ. Lấy ví dụ như các câu truy vấn sau: “Who was biographer and Samuel Johnsons's friend?” chứa liên từ luận lý. “What famous model was married to Billy Joel?” chứa tính từ định tính. “What is the oldest university in the US?” chứa tính từ định lượng. “What is the highest dam in the U.S.?” và “What is the most common kind of skin cancer in the U.S.?” chứa tính từ so sánh nhất. “How many films did Ingmar Bergman make?” chứa lượng từ. Hiện đã có nghiên cứu của nhóm VN-KIM để biên dịch những câu truy vấn dạng này từ ngôn ngữ tự nhiên sang đồ thị ý niệm. Luận văn này sẽ ứng dụng thành quả nghiên cứu đó, đồng thời mở 3 rộng thêm một số khả năng khi xử lý những câu truy vấn dạng này. Đầu tiên là khả năng đề xuất đồ thị ý niệm khả áp dụng ngay cả khi quan hệ với tính từ trong câu truy vấn không có trong cơ sơ tri thức. Mục đích là làm ta có thể đánh giá tính chính xác của quá trình “hiểu” câu truy vấn của hệ thống mà không bị quá lệ thuộc vào cơ sơ tri thức. Ví dụ như sau: “What is the longest dam in the U.S.?” Mặc dù quan hệ giữ “dam” và “long” không có trong cơ sơ tri thức, nhưng ta vẫn có thể cung cấp đồ thị ý niệm cho người dùng (với quan hệ “ảo” được vẽ màu xanh lá). Hình 1.1 Đồ thị có đề xuất quan hệ không tồn tại trong cơ sở tri thức Ngoài ra, để truy xuất được tài liệu, thì chỉ ngừng lại ở đồ thị là chưa đủ, cần phải chuyển đồ thị đó sang ngôn ngữ SeRQL, là ngôn ngữ dùng để truy xuất cơ sở tri thức ngữ nghĩa. Luận văn này sẽ đề xuất cách thức chuyển từ đồ thị của những câu truy vấn dạng này sang truy vấn SeRQL để lấy về thực thể (entity) cần tìm. Luận văn cũng đề xuất cách xử lý câu truy vấn có chứa so sánh hơn của tính từ định lượng. Các câu truy vấn có so sánh hơn với một hằng số, hoặc so sánh hơn với một thực thể, như “What dam in the U.S. is higher than 1200 meters?”, “What dam is higher than Dworshak in the U.S.?” cũng sẽ được chuyển sang đồ thị ý niệm, rồi chuyển sang câu truy vấn SeRQL tương ứng. 4 1.3 Cấu trúc luận văn Chương 1 đã trình bày khái quát động cơ, mục đích, ý tưởng thực hiện đề tài. Tiếp theo sau Chương 1 là phần trình bày chi tiết về ý tưởng và phương pháp của chúng tôi để đạt được mục đích đã đề ra. Chương 2 trình bày những nghiêu cứu và hệ thống liên quan đến việc chuyển đổi câu truy vấn tiếng Anh sang đồ thị ý niệm. Mục 2.1 trình bày phương pháp rút trích quan hệ trong câu truy vấn. Sơ lược giới thiệu về đồ thị ý niệm được trình bày ở Mục 2.2. Chương 3 trình bày cách tiếp cận vấn đề với việc giải quyết câu truy vấn hỏi về số lượng được trình bày tại Mục 3.1, giải quyết cho câu truy vấn có chứa tính từ được trình bày tại Mục 3.2, giải quyết cho câu truy vấn có chứa tính từ so sánh nhất được trình bày tại Mục 3.3 và giải quyết cho câu truy vấn có chứa liên từ luận lý sẽ được trình bày tại Mục 3.4. Chương 4 trình bày phương pháp biên dịch câu truy vấn tiếng Anh sang đồ thị ý niệm. Mục 4.1 sẽ mô tả các bước trong giải thuật xây dựng đồ thị ý niệm cho câu truy vấn. Mục 4.2 trình bày chi tiết về tập luật ánh xạ. Những kết quả đạt được của đề tài sẽ được tổng kết tại Mục 4.3. Chương 5 trình bày chi tiết phương pháp lưu trữ và hiển thị đồ thị ý niệm. Chương 6 đưa ra kết luận và đề nghị hướng phát triển cho tương lai. Phần phụ lục giới thiệu tập câu hỏi mẫu TREC 2002, TREC 2007 cùng các đồ thị ý niệm đã được sinh đúng cho những câu truy vấn rút ra từ hai tập câu hỏi mẫu này. 5 CHƯƠNG 2 KIẾN THỨC NỀN TẢNG 2.1 Rút trích quan hệ Rút trích quan hệ là xác định mối quan hệ ngữ nghĩa giữa cặp các thành phần không có cấu trúc hay bán cấu trúc trong văn bản ngôn ngữ tự nhiên. Rút trích quan hệ dựa vào Ontology liên quan tới hai công việc chính: xác định mối quan hệ giữa hai thành phần đã biết chủ yếu dựa trên miền Ontology và khám phá các mối quan hệ mới giữa hai ý niệm không có trên miền Ontology. Ví dụ trong câu “Bill Gates is chairman and chief software architect of Microsoft Corporation”, tồn tại quan hệ theo kiểu của ACE (Automatic Content Extraction) là EMPLOYMENT.exec giữa hai thực thể có tên là “Bill Gates” thuộc lớp PERSON.Name và “Mircrosoft Corporation” thuộc lớp ORGANIZATION.Commercial. Có nhiều kỹ thuật rút trích quan hệ, dựa trên luật (rule-based), dựa trên đặc điểm (feature-based) và phương pháp kernel (kernel-based) dưới đây trình bày một số nghiên cứu về rút trích quan hệ:  Các phương pháp dựa trên luật sử dụng các luật của ngôn ngữ để nắm bắt các mẫu quan hệ khác nhau. Hệ thống [8] rút trích quan hệ từ một quá trình phân tích cú pháp, do đó kết quả của nó phụ thuộc hoàn toàn vào cây cú pháp.  Các phương pháp rút trích dựa trên đặc điểm [21] sử dụng các đặc điểm của ngôn ngữ như đặc điểm từ vựng, đặc điểm cú pháp và đặc điểm ngữ nghĩa. Những phương pháp này rất hiệu quả cho việc rút trích quan hệ. Tuy nhiên, vấn đề gặp phải là các đặc điểm phải được mô tả thủ công và cấu trúc thông tin trong cây cú pháp không được bảo toàn trong cây đặc điểm (Là cây biểu diễn các đường nối không kết thúc giữa hai thực thể trong cây cú pháp).  Các phương pháp dựa trên kernel chú trọng vào việc sử dụng các cây kernel riêng lẻ để khai thác đặc điểm cấu trúc. Hệ thống [19] xây dựng một quan hệ kernel trên cây cú pháp cho việc rút trích quan hệ. Kernel so trùng các node từ gốc cho tới lá một cách đệ quy theo từng lớp từ trên xuống. 6 Tuy nhiên các nghiên cứu trên chỉ chú trọng vào rút trích quan hệ giữa các thực thể có tên đã biết. Để xây dựng được đồ thị ý niệm, ngoài việc rút trích quan hệ giữa các thực thể có tên còn phải rút trích quan hệ giữa các thực thể không tên với nhau, hay các quan hệ giữa các thực thể có tên với thực thể không tên. 2.2 Đồ thị ý niệm (Conceptual Graph) 2.2.1 Sơ lược về đồ thị ý niệm Đồ thị ý niệm là một hình thức biểu diễn logic (logical formalism) vừa có tính trực quan, vừa có sự chính xác. Về hình thức, đây là một đồ thị tạo ra bởi các đỉnh và các cạnh (có thể có hướng hoặc không có hướng). Nhờ sử dụng cách biểu diễn đồ họa trực quan đó, đồ thị cho phép con người nhanh chóng có được một cái nhìn tổng quan, dễ nắm bắt ý nghĩa. Về nội dung, đồ thị ý niệm có thể được ánh xạ trực tiếp sang logic vị từ (predicate logic). Nhờ đó, có thể biểu diễn ngữ nghĩa một cách chính xác, giữ được tính chính xác về mặt logic. Với những đặc điểm đó, đồ thị ý niệm vừa dễ tiếp cận đối với con người, vừa khả xử lý đối với máy tính. Và đồ thị ý niệm đã được dùng như là một hình thức biểu diễn tri thức, là một ngôn ngữ trung gian cho việc chuyển đổi qua lại giữa hình thức biểu diễn hướng máy tính và ngôn ngữ tự nhiên. “Tim Berners Lee, người phát minh của WWW, kết luận rằng các CG có thể dễ dàng tích hợp với Semantic Web. Nó cũng được chỉ ra trong là có một ánh xạ chặt giữa CG và ngôn ngữ RDF (ko hiểu đoạn này >.<).” [tham khao HA]. “Trong bài báo đầu tiên công bố liên quan tới đồ thị ý niệm, Sowa đã định nghĩa đồ thị ý niệm như sau: Chỗ này ta nghĩ chỉ cần nói: Sowa đã định nghĩa dtyn trong 1 bài báo của mình:… rồi trích dẫn đoạn định nghĩa thôi Đồ thị ý niệm là một đồ thị hữu hạn, liên thông, không có hướng, lưỡng phân với những nút thuộc một loại được gọi là ý niệm (hoặc khái niệm – concepts) và những nút thuộc loại còn lại được gọi là quan hệ khái niệm (conceptual relations).” [tham khao HA] 7 Như vậy, đồ thị ý niệm thuộc loại đồ thị phân đôi, và bao gồm 2 loại đỉnh: các đỉnh khái niệm và các đỉnh quan hệ. Trong đó, các đỉnh khái niệm chỉ liên kết với các đỉnh quan hệ bởi các cạnh và ngược lại. Đỉnh khái niệm được biểu diễn bằng hình chữ nhật có nhãn là kiểu khái niệm kết hợp với tham chiếu. Đỉnh quan hệ có hình oval với nhãn chính là kiểu quan hệ của nó. Mỗi đỉnh quan hệ có thể liên kết với nhiều đỉnh khái niệm bằng các cạnh có hướng. Để ngắn gọn, chúng ta sẽ gọi đỉnh quan hệ, đỉnh khái niệm lần lượt là quan hệ, khái niệm. STUDENT: John STUDY SUBJECT: * IN FIELD: CS [hình tham khảo CDT] Hình trên là đồ thị ý niệm cho câu “John is a student. There is a subject. CS is a field of study. The subject is in CS. John studies the subject”. Hoặc ngắn gọn hơn là “John studies a subject in CS”. (Đoạn này nếu có thể ta nghĩ mình nên tìm một ví dụ khác tương tự, vì ngay cả ví dụ mà cũng phải tham khảo có thể tạo cho người đọc cảm giác mình chưa hiểu kỹ về nó) Trong định dạng văn bản, các khái niệm và các quan hệ có thể được biết trong dấu ngoặc vuông và ngoặc tròn như sau: [STUDENT: John]→(STUDY)→[SUBJECT: *]→(IN)→[FIELD: CS] Trong ví dụ này, [STUDENT: John], [SUBJECT:*], [FIELD: CS] là các khái niệm với STUDENT, SUBJECT và FIELD trở thành kiểu khái niệm, trong khi đó (STUDY) và (IN) là các quan hệ với STUDY và IN là các kiểu quan hệ. Các tham khảo John và CS là các tham chiếu xác định. Tham chiếu “*” là tham chiếu tổng quát ám chỉ tới một thực thể không xác định. Đồ thị ý niệm được sử dụng để kiểm tra tính chính xác của quá trình dịch câu truy vấn trong đề tài, bên cạnh các tham chiếu xác định và tham chiếu tổng quát, được bổ sung thêm tham chiếu nghi vấn. Tham chiếu nghi vấn biểu diễn cho thực thể được truy vấn trong câu. Một đồ thị ý niệm truy 8 vấn là một đồ thị ý niệm mà các tham chiếu có thể là tham chiếu xác định, tham chiếu tổng quát hoặc là tham chiếu nghi vấn được biểu diễn bằng dấu “?”. 2.2.2 Đồ thị ý niệm mở rộng Đồ thị ý niệm mở rộng [tham khảo HA] là đồ thị ý niệm có sử dụng thêm một khái niệm đặc biệt, gọi là đỉnh truy vấn con. Đó là một đỉnh khái niệm, nhưng có kiểu khái niệm riêng, và tham chiếu đến thực thể của nó là một đồ thị ý niệm khác. Tức là, bên trong đỉnh truy vấn con là nội dung một đồ thị ý niệm truy vấn tri thức. Đỉnh truy vấn con được biểu diễn bằng hình chữ nhật tròn góc (Ta nghĩ chỗ này mình nên nói: trong tài liệu (hay luận văn) này, đỉnh truy vấn con được biểu diễn bằng hình chữ nhật vát góc, vì các ví dụ sau này đâu phải tròn góc). Ta xét một ví dụ minh họa: ta có câu truy vấn lồng nhau như sau: “Tìm tên của những giảng viên có tên trùng với tên của những giảng viên tại trường Đại học Bách Khoa”. Câu truy vấn này sẽ được biểu diễn như sau: [hình tham khảo HA] Trong đề tài [tham khảo HA], đỉnh truy vấn con này được sử dụng phần lớn trong các phương pháp đề xuất sẽ được bàn đến ở những phần tiếp theo. 9 2.3 Câu truy vấn SeRQL [tham khảo http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html #section-numerical-comparisons] SeRQL (Sesame RDF Query Language) là một ngôn ngữ truy vấn cơ sở tri thức. Tương tự như SQL được sử dụng làm ngôn ngữ truy vấn trên các cơ sở dữ liệu quan hệ, SeRQL được sử dụng trên các cơ sở dữ liệu viết bằng ngôn ngữ RDF. Trong SeRQL, có 2 loại câu truy vấn: một loại sẽ trả về một bảng các giá trị (một tập các ràng buộc (binding) giữa biến với giá trị, tương tự như khi truy vấn với SQL), loại còn lại sẽ trả về một đồ thị RDF (RDF graph). Trong đề tài này chỉ sử dụng loại thứ nhất, gọi là select queries (phiên bản 2.3.2), sẽ được trình bày sau đây. Đối với 1 câu truy vấn thuộc loại select queries , sẽ có 8 mệnh đề có thể được sử dụng, đó là: SELECT, FROM, FROM CONTEXT, WHERE, ORDER BY, LIMIT, OFFSET và USING NAMESPACE. Chỉ có mệnh đề SELECT là bắt buộc, các mệnh đề còn lại có thể không có mặt trong câu truy vấn. Các mệnh đề SELECT, FROM, WHERE và ORDER BY là những mệnh đề sẽ được sử dụng để truy vấn trong đề tài này. Mệnh đề SELECT ở SeRQL cũng tương tự như trong SQL, sẽ chỉ ra các biến mà ta cần trả về giá trị. Nếu truy vấn thành công, tập kết quả trả về sẽ là các giá trị được ràng buộc với các biến liệt kê trong mệnh đề SELECT. Ví dụ [tham khảo http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#section-numerical-comparisons]: SELECT O, S FROM {S} rdfs:label {O} Mệnh đề FROM ở SeRQL cũng tương tự như trong SQL, nhưng, thay vì chỉ ra các bảng (table) có chứa dữ liệu, người sẽ phải chỉ ra các biểu thức đường đi (path expression) có chứa dữ liệu trong cơ sở tri thức RDF. Trong ví dụ trên, biểu thức đường đi là “{S} rdfs:label {O}” . Mệnh đề WHERE, cũng tương tư như SQL, là nơi để người dùng đặc tả các ràng buộc mà các biến phải thỏa mãn. Nếu có nhiều ràng buộc, chúng có thể được liên kết bằng các từ khóa AND, OR, NOT, là các toán tử của đại số Bool.Trong mệnh đề WHERE, ta cũng có thể sử dụng câu truy 10