Học cấu trúc mạng logic Markov và ứng dụng
trong bài toán phân lớp Phạm Đình Hiệu Trường Đại học Khoa học Tự nhiên
Luận văn ThS. ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán
Mã số: 60 46 35
Người hướng dẫn: TS. Nguyễn Thị Minh Huyền
Năm bảo vệ: 2012 Abstract. 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ả.

Keywords. Toán học; Bài toán phân lớp; Mô hình Markov Content
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. Trong sự phát triển đó của Công nghệ, học máy được xem là một

Chƣơng I: Cơ sở toán học
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ả. CHƢƠNG 1. CƠ SỞ TOÁN HỌC
1.1 Lý thuyết đồ thị
Định nghĩa 1.1.1. Đồ thị là cặp , trong đó A là tập đỉnh, F là ánh xạ từ
[3].
Ta cũng có thể định nghĩa đồ thị là cặp: , trong đó là tập đỉnh và
là tập cung. Về thực chất đồ thị là một tập hợp các đối tượng được biểu
diễn bằng các đỉnh và giữa các đối tượng có quan hệ (nhị nguyên) biểu diễn bằng các
cung[3].
Cho đồ thị . Nếu có thì ta nói rằng là một cung và gọi là
đỉnh đầu, gọi là đỉnh cuối của cung đó.
Hai đỉnh kề nhau là hai đỉnh của cùng một cung. Đỉnh nút là đỉnh kề với chính nó.
Định nghĩa 1.1.2. Đồ thị với được gọi là đồ thị con của đồ thị
nếu [3].
Định nghĩa 1.1.3. Hai đỉnh gọi là liên thông với nhau nếu chúng trùng nhau hoặc có
xích nối với nhau[3].
Đồ thị đối xứng gọi là đồ thị vô hướng tức là ta luôn có
.
Định nghĩa 1.1.4. Đồ thị vô hướng được gọi là đầy đủ nếu hai đỉnh bất kỳ đều có cung

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: : F1, F1^F2, F1 F2, F1 F2, F1 F2, F1 và
F1[9].
1.2.3 Dạng chuẩn hội
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) , trong đó Q là lượng từ, là biến
và là hội của các mệnh đề.
1.3 Xác suất – thống kê
1.3.1 Các khái niệm
Định nghĩa 1.3.1. Xác xuất của biến cố A là một số không âm bằn trong khoảng [0;1],
ký hiệu là P(A), biểu thị khả năng xảy ra biến cố A và được xác định như sau:

Trong đó là số trường hợp thuận lợi cho , là số trường hợp có thể có khi phép thử
thực hiện .
Đị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ố
trong tình huống biến cố đã xảy ra khi đó:

Đị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. Hai biến ngẫu nhiên và là độc lập nếu và
.
Đị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. Phân phối biên (marginal distribution): Cho hai biến ngẫu nhiên
và , và là phân phối đồng thời của chúng. Phân phối biên của là phân phối của
mà được bỏ qua.
1.3.2 Công thức Bayes
Cho biến cố và các biến cố sao cho[8]:

2.1 Giới thiệu
Logic tân từ cấp một là ngôn ngữ rất mạnh để biểu diễn những thông tin có quan hệ
phức tạp, cho phép chúng ta mô tả một cách đầy đủ rộng lớn của tri thức.
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ị. Nó cung cấp một công cụ tự nhiên để giải quyết hai vấn đề xảy ra trong toán học ứng
dụng và trong kỹ thuật: Không chắc chắn và phức tạp. Đặc biệt nó đóng vai trò quan trọng
trong việc phân tích và thiết kế các thuật toán học máy. Về mặt cơ bản thì ý tưởng của mô
hình đồ họa là dựa vào khái niệm của mô đun: Một hệ thống phức tạp được xây dựng bằng
việc kết nối các phần đơn giản hơn. 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.
2.2 Mạng Markov
Mạng Markov[12] (hay còn gọi là trường ngẫu nhiên Markov) là mô hình cho phân
phối đồng thời (joint distribution) của một tập hợp các biến . Nó bao gồm
một đồ thị vô hướng và một tập các hàm tiềm năng . Đồ thị có một nút cho mỗi biến, và
có một hàm tiềm năng cho mỗi clique trong đồ thị. Hàm tiềm năng là hàm giá trị thực không
âm xác định cho từng trạng thái của các clique. 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:

đóng đảm bảo rằng các mạng Markov được sinh ra là hữu hạn. Trong trường hợp này các
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ể[12], [16], [17].
2.4 Suy diễn
Trong phần này sẽ trình bày về suy diễn trên mô hình qua 2 bài toán suy diễn, suy diễn
MAP/MPE và suy diễn điều kiện.
2.4.1 Suy diễn MAP/MPE
Suy diễn MAP/MPE (MPE – the most probable explaination) [12], [13], [14] là: Tìm
trạng thái (giá trị chân lý) có khả năng xảy ra lớn nhất của tập các biến đầu ra (output) cho bởi
trạng thái của các biến đầu vào (input).
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.
2.4.2 Suy diễn điều kiện
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?”.
2.5 Học tham số và học cấu trúc
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. Việc học mô
hình bao gồm 2 vấn đề là: học tham số và học cấu trúc.

- Vai chủ sở hữu (Possessor, viết tắt là Poss): Biểu thị chủ sở hữu của sự vật. Ví dụ:
Tôi
Poss
còn tiền.
- Vai bị thể (Patient, viết tắt là Pa): Biểu thị người hoặc vật chịu sự tác động. Ví dụ: Tôi
đánh nó
Pa
.
- Vai tiếp thể (Recipient, viết tắt là Rec): Biểu thị người tiếp nhận trong hành động trao
tặng. Ví dụ: Tôi tặng mẹ
Rec

- v.v…
Trong luận văn này mới chỉ dừng lại ở quá trình gán nhãn cho vai tác thể gán “A0” và
vai bị thể gán “A1” trong câu tiếng Việt.
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. Kho
văn bản được chia làm ba tập tương ứng với ba mức gán nhãn là tách từ, gán nhãn từ loại và
gán nhãn cú pháp. Tập được gán nhãn cú pháp là tập con của tập được gán nhãn từ loại; tập
được gán nhãn từ loại là tập con của tập được tách từ.
3.3 Giới thiệu công cụ Thebeast
“Markov Thebeast” là một công cụ phần mềm phiên bản 0.0.2 được đưa ra bởi
Sebastian Riedel – June 14, 2008. 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ó. Học tập và suy diễn
đều được xử lý bởi Thebeast. Thebeast sử dụng logic Markov như là ngôn ngữ để mô tả
mạng Markov phức tạp. So với công cụ khác, thebeast sử dụng một kỹ thuật suy diễn MAP.
3.4 Các bƣớc thực hiện bài toán

Bina (2010), “Structure Learning for Markov Logic Networks with Many
Descriptive Attributes”, in Proceedings of the Twenty-Fourth AAAI Conference on
Artificial Intelligence (AAAI-10), pages. 487-493.
[12] Stanley Kok and Pedro Domingos (2005), “Learning the Structure of Markov
Logic Networks”, in Proceedings of the 22
nd
internatrional conference on Machine
learning, pages 441 – 448.
[13] Pedro Domingos and Daniel Lowd, “Markov logic: An interface layer for
artificial intelligence”. Synthesis Lectures on Artificial Intelligence and Machine
Learning, Morgan & Claypool Publishers, 2009, vol 3, No.1, pages 1-155.
[14] Stanley Kok and Pedro Domingos (2009), “Hypergraph Lifting for Structure
Learning in Markov Logic Networks”, Proceedings of the 26
th
Annual
International Conference on Machine Learning, pages 505 - 512.
[15] Stanley Kok and Pedro Domingos (2010), Learning Markov Logic Networks Using
Structural Motifs, in Proceedings of the 27th International Conference on
Machine Learning, Haifa, Israel.
[16] Matthew Richardson and Pedro Domingos (2006), Markov Logic Networds,
Machine Learning, vol 62, no 1-2, pages 107-136.
[17] Đinh Quang Thắng (2011), Apprentissage Statistique Relationnel: Apprentissage
de Structures de Réseaux de Markov Logiques, The University of Orléans.
[18] Marenglen Biba, Integrating Logic and Probability: Algorithmic Improvements in
Markov Logic Networks, Department of Computer Science University or Bari,
Italy (2009).