- Học cấu trúc mạng logic Markov và ứng dụng trong bài toán phân lớp. - Trình bày về một số kiến thức cơ bản được sử dụng trong cấu trúc mạng logic markov và ứng dụng trong bài toán phân lớp liên quan tới lý thuyết đồ thị, logic và xác suất thống kê. - Tìm hiểu các kiến thức về mạng Markov, mạng logic Markov và một số vấn đề về học máy với mạng logic Markov như suy diễn, học tham số và đặc biệt là học cấu trúc. - Nghiên cứu ứng dụng mạng logic Markov trong bài toán gán nhãn vai nghĩa: trình bày về bài toán gán nhãn vai nghĩa, vấn đề xây dựng dữ liệu huấn luyện trong công cụ Thebeast cho bài toán gán nhãn vai nghĩa và đánh giá kết quả.. - Trong sự phát triển về Công nghệ thông tin hiện nay vấn đề xử lý, tính toán không còn thuần túy là tính toán trên các dữ liệu kiểu số biểu diễn dưới dạng cấu trúc, bảng biểu hay véc tơ, vv. - Nó đã được phát triển mở rộng xử lý trên dữ liệu kiểu hình ảnh, âm thanh, văn bản, đồ thị và nhiều kiểu khác nữa. - Đến nay học máy có ứng dụng rộng khắp trong các ngành khoa học, sản xuất, đặc biệt những ngành cần phân tích khối lượng dữ liệu khổng lồ. - Học quan hệ thống kê cũng là một trong các lĩnh vực của học máy, nó hướng tới sự kết hợp giữa học theo quan hệ và học theo thống kê nhằm xử lý các dữ liệu không chắc chắn với cấu trúc quan hệ phức tạp. - Có nhiều mô hình được phát triển gần đây cho học quan hệ thống kê như mô hình quan hệ xác suất (Probabilistic Relational Model) sử dụng logic kết hợp với các mạng Bayes hay Markov. - Mạng logic Markov có thể được xem như là một sự kết hợp hữu cơ giữa học logic và học thống kê. - tập các công thức logic có trọng số. - Xử lý ngôn ngữ chính là xử lý thông tin khi đầu vào là dữ liệu ngôn ngữ, tức là dữ liệu kiểu văn bản hay tiếng nói. - Các dữ liệu liên quan đến ngôn ngữ viết (văn bản) và tiếng nói đang dần trở nên kiểu dữ liệu chính con người có và lưu trữ dưới dạng điện tử.. - Trong chương này sẽ trình bày về một số kiến thức cơ bản được sử dụng trong luận văn liên quan tới lý thuyết đồ thị, logic và xác suất thống kê.. - Chƣơng II: Mạng logic Markov. - Chương này sẽ trình bày các kiến thức về mạng Markov, mạng logic Markov và một số vấn đề về học máy với mạng logic Markov như suy diễn, học tham số và đặc biệt là học cấu trúc.. - Chƣơng III: Ứng dụng mạng logic Markov trong bài toán gán nhãn vai nghĩa Chương này sẽ trình bày về bài toán gán nhãn vai nghĩa, vấn đề xây dựng dữ liệu huấn luyện trong công cụ Thebeast cho bài toán gán nhãn vai nghĩa và đánh giá kết quả.. - Định nghĩa 1.1.1. - Ta cũng có thể định nghĩa đồ thị là cặp. - Cho đồ thị . - Định nghĩa 1.1.2. - Định nghĩa 1.1.3. - Định nghĩa 1.1.4. - Định nghĩa 1.1.5. - Một cơ sở tri thức xây dựng trên logic tân từ cấp một (KB) là một tập các câu hay các công thức trong logic tân từ cấp một. - Công thức được xây dựng bằng cách sử dụng 4 loại ký hiệu: hằng, biến, hàm và vị từ[9], [12].. - 1.2.2 Công thức trong logic tân từ cấp một. - Một công thức nguyên tử được định nghĩa là:. - Nếu P là vị từ n biến và là các hạng thức thì là công thức nguyên tử.. - Các công thức được xây dựng một cách đệ quy từ các công thức nguyên tử bằng cách sử dụng các phép toán logic và các lượng từ. - Nếu và là các công thức thì những ký hiệu sau đây cũng là công thức. - Mọi công thức trong logic tân từ cấp một có thể chuyển thành một công thức tương đương trong dạng chuẩn hội (CNF. - 1.3 Xác suất – thống kê 1.3.1 Các khái niệm. - Định nghĩa 1.3.1. - Định nghĩa 1.3.2. - Xác suất có điều kiện của biến cố với điều kiện biến cố đã xảy ra là một con số không âm, được ký hiệu là , nó biểu thị khả năng xảy ra của biến cố. - Định nghĩa 1.3.3. - Biến ngẫu nhiên: Một biến nhận các giá trị của nó ứng với một xác suất nào đấy gọi là biến ngẫu nhiên[1].. - Định nghĩa 1.3.4. - Định nghĩa 1.3.5. - Phân phối đồng thời (joint distribution): Cho hai biến ngẫu nhiên và được định nghĩa trên cùng một không gian xác suất, phân phối đồng thời của và là xác suất của các biến cố được định nghĩa trong véc tơ ngẫu nhiên của và. - Định nghĩa 1.3.6. - 1.3.2 Công thức Bayes. - Thì ta có công thức tổng:. - Công thức Bayes [1]:. - là xác suất xảy ra biến cố A k. - Xác suất để biến cố B xảy ra. - P(B| A i ) là xác suất để B xảy ra biết rằng A i đã xảy ra rồi ( tỉ lệ xảy ra B trong A i. - MẠNG LOGIC MARKOV 2.1 Giới thiệu. - Xác suất là một cách thức thông thường để biểu diễn những sự kiện hoặc kiến thức không chắc chắn.. - Kết hợp logic tân từ cấp một và xác suất sẽ cho phép xây dựng các mối quan hệ dựa trên xác suất phức tạp của dữ liệu nằm trong miền được quan tâm. - Vấn đề này được quan tâm và phát triển trong một số năm gần đây trong các nghiên cứu về học quan hệ thống kê, khai phá dữ liệu nhiều quan hệ, vv.. - Mô hình đồ họa: Là mô hình biểu diễn sự kết hợp giữa lý thuyết xác suất và lý thuyết đồ thị. - Về phía lý thuyết đồ thị cung cấp cả giao diện trực quan mà con người có thể mô hình các tập hợp của các biến cũng như cấu trúc dữ liệu để thiết kế các thuật toán mục đích chung hiệu quả.. - Chương này sẽ giới thiệu một mô hình kết hợp xác suất với logic tân từ cấp một, mới được đưa ra năm 2004[16]. - Đó là mạng logic Markov, mô hình biểu diễn cơ sở tri thức dựa trên logic tân từ cấp một với một trọng số kèm theo cho mỗi công thức và nó có thể được coi như là một mẫu cho việc xây dựng các mạng Markov. - Nội dung trình bày bao gồm: Mạng Markov, mạng logic Markov, suy diễn trên mạng logic Markov, học tham số và đặc biệt là học cấu trúc cho mạng logic Markov.. - Phân phối đồng thời được biểu diễn bởi mạng Markov cho bởi công thức sau:. - Z được gọi là hàm phân hoạch (partition function), cho bởi công thức. - 2.3 Mạng logic Markov. - Cơ sở tri thức (KB- knowledge base) dựa trên logic tân từ cấp một được xem như là tập các ràng buộc chặt trên tập các minh họa có thể: Nếu một minh họa chỉ vi phạm một công thức thì nó có xác suất bằng không. - Ý tưởng đơn giản trong mạng logic Markov là để nới lỏng ràng buộc này: Khi một minh họa vi phạm một công thức trong cơ sở tri thức thì nó có xác suất thấp, nhưng không phải là không thể có. - Càng ít công thức mà minh họa đó vi phạm thì xác suất xảy ra của minh họa đó càng lớn. - Mỗi công thức có một trọng số kèm theo phản ánh hạn chế đó mạnh như thế nào: trọng số càng cao thì sự khác biệt trong xác suất giữa một minh họa thỏa mãn công thức và một minh họa không thỏa mãn càng lớn.. - Định nghĩa 2.2.1. - Một mạng logic Markov là một tập các cặp , trong đó là công thức trong logic tân từ cấp một và là một số thực. - chứa một nút nhị phân cho mỗi công thức nguyên tử nền có thể của mỗi vị từ xuất hiện trong . - Giá trị của nút đó bằng 1 nếu công thức nguyên tử nền là đúng và bằng 0 nếu ngược lại.. - chứa một đặc trưng cho mỗi công thức nguyên tử nền có thể của mỗi công thức xuất hiện trong L. - Giá trị của đặc trưng này là 1 nếu như công thức nguyên tử đúng và sai nếu ngược lại. - Một mạng logic Markov được xem như là một mẫu cho việc xây dựng các mạng Markov. - Cho các tập hằng khác nhau thì sẽ cho ra các mạng khác nhau và các mạng này có thể có kích thước rất lớn, nhưng tất cả chúng đều có những quy tắc nào đó trong cấu trúc và các tham biến cho bởi mạng logic Markov (ví dụ tất cả các công thức nền sẽ có cùng một trọng số). - Chúng ta gọi mỗi một mạng Markov này là mạng Markov nền để phân biệt nó với mạng logic Markov. - Luận văn này sẽ tập trung vào mạng logic Markov mà các công thức của nó là các mệnh đề không có hàm (function free clause) và nó cũng được giả thiết trên miền đóng đảm bảo rằng các mạng Markov được sinh ra là hữu hạn. - công thức nền được xác định bằng cách thay thế các biến của nó bằng tất cả các hằng có thể . - 2.4 Suy diễn. - Trạng thái MAP (Maximum a posteriori) là trạng thái mà tổng các trọng số của các công thức nền thỏa được đạt cực đại.. - trong đó là số các mệnh đề nền có giá trị chân lý đúng thứ bao gồm các công thức nguyên tử của tập chưa biết. - Nhìn vào phương trình 2.4 thì ta nhận thấy suy diễn MAP/MPE sẽ phải tìm những giá trị chân lý cho các công thức nguyên tử nền (hay các nút) (không tính những công thức nguyên tử nằm trong giả thiết, nghĩa là ) bằng việc làm cực đại tổng trọng số của các mệnh đề thỏa được (hay các đặc trưng). - Thuật toán sau có tên là MaxWalkSAT được sử dụng cho suy diễn MAP/MPE để tìm ra các trạng thái MAP trong mạng logic Markov.. - Suy diễn điều kiện trong các mô hình đồ thị bao gồm việc tính toán xác suất của các biến truy vấn cho bởi các biến giả thiết.. - Mạng logic Markov là một mô hình quan trọng giúp chúng ta giải quyết nhiều vấn đề phức tạp và không chắc chắn. - Cụ thể thì các mạng logic Markov có thể trả lời bất kỳ câu hỏi nào có dạng sau: “Tính xác suất mà công thức đúng khi biết đúng?”.. - Việc học mô hình từ cơ sở dữ liệu là vấn đề quan trọng và phức tạp nhưng đây cũng là yếu tố quyết định để áp dụng mô hình vào thực tế thông qua các bộ dữ liệu thực. - Học tham số của mạng logic Markov bao gồm tìm các trọng số mà tối ưu một hàm khả năng (likehood) cho bởi dữ liệu huấn luyện. - Một cách tối ưu được sử dụng thay thế là phương pháp pseudo-likelihood (dùng hàm tựa hàm khả năng) tính toán xác suất chỉ bao gồm các biến trong phủ Markov (được định nghĩa phía dưới) trong dữ liệu. - Ngược lại, cách tiếp cận tách biệt sẽ tối đa hóa hàm hợp lý điều kiện của một tập các dữ liệu đầu ra cho bởi tập dữ liệu đầu vào[17].. - 2.5.2 Học cấu trúc. - Học cấu trúc mạng logic Markov có thể từ một mạng rỗng hoặc từ một cơ sở tri thức đã tồn tại. - Chúng ta xây dựng bắt đầu bằng việc thêm tất cả các mệnh đề đơn vị (các vị từ đơn) vào mạng logic Markov. - ỨNG DỤNG MẠNG LOGIC MARKOV TRONG BÀI TOÁN GÁN NHÃN VAI NGHĨA 3.1 Bài toán gán nhãn vai nghĩa. - 3.2 Mô tả dữ liệu sử dụng. - Dữ liệu được sử dụng ở đây là kho ngữ liệu 10.000 cây cú pháp của vnTreebank. - Dữ liệu văn bản được thu thập từ chuyên mục Chính trị - Xã hội của báo Tuổi trẻ Online. - Nó là một phần mềm học quan hệ thống kê trên logic Markov. - Nó cho phép chúng ta thực hiện học quan hệ và dự đoán cấu trúc các vấn đề như thực thể, dự đoán liên kết, phân tích cú pháp phụ thuộc, nhãn ngữ nghĩa, nén câu, vv bằng định nghĩa một mô hình đơn giản và cung cấp dữ liệu huấn luyện cho nó. - Thebeast sử dụng logic Markov như là ngôn ngữ để mô tả mạng Markov phức tạp. - 3.4.1 Dữ liệu và cấu trúc dữ liệu trong Thebeast 3.4.2 Xây dựng dữ liệu huấn luyện. - [1] Đào Hữu Hồ (2006), Xác suất thống kê, Nhà xuất bản Đại học Quốc gia Hà Nội.. - “Sử dụng bộ gán nhãn từ loại xác suất QTAG cho văn bản tiếng Việt”, Báo cáo hội thảo ICT.rda.