Luận văn thạc sĩ Phạm Đình Hiệu
1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

Phạm Đình Hiệu
HỌC CẤU TRÚC MẠNG LOGIC MARKOV VÀ ỨNG DỤNG
TRONG BÀI TOÁN PHÂN LỚP
LUẬN VĂN THẠC SĨ KHOA HỌC
Hà Nội - 2012
Luận văn thạc sĩ Phạm Đình Hiệu
2

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

1.2.2 Công thức trong logic tân từ cấp một 10
1.2.3 Dạng chuẩn hội 12
1.3 Xác suất – thống kê 13
1.3.1 Các khái niệm 13
1.3.2 Công thức Bayes 15
1.3.3 Cực đại hóa xác suất có điều kiện 16
1.3.4 Xích Markov 17
1.3.5 Xích Markov Monte Carlo 19
1.3.6 Phƣơng pháp lấy mẫu Gibbs 20
CHƢƠNG 2. MẠNG LOGIC MARKOV 21
2.1 Giới thiệu 21
2.2 Mạng Markov 22
2.3 Mạng logic Markov 24
2.4 Suy diễn 29
2.4.1 Suy diễn MAP/MPE 29
2.4.2 Suy diễn điều kiện 32
2.5 Học tham số và học cấu trúc 34
2.5.1 Học tham số 34
2.5.2 Học cấu trúc 39
CHƢƠNG 3. Ứ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 46
3.2 Mô tả dữ liệu sử dụng 46
Luận văn thạc sĩ Phạm Đình Hiệu
4

3.3 Giới thiệu công cụ Thebeast 47
3.4 Các bƣớc thực hiện bài toán 48
3.4.1 Dữ liệu và cấu trúc dữ liệu trong Thebeast 48
3.4.2 Xây dựng dữ liệu huấn luyện 49

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ồ. Một số
ứng dụng thƣờng thấy: Rôbốt, trò chơi, phân tích thị trƣờng chứng khoán, phát hiện
gian lận tài chính, phân tích ảnh thiên văn, phân loại chuỗi gene, quá trnh hnh
thành gene, phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động, tm kiếm,
nhận dạng hay nhiều ứng dụng liên quan tới xử lý ngôn ngữ tự nhiên.
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. Trong
đó các mạng MLN (Markov Logic Network) mang tính tổng quát cao nhất, có thể
chuyển đổi sang các mô hnh khác và ngày càng có nhiều nghiên cứu về các mạng
này. 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ê. Mục đích của MLN là mô tả một minh họa cho trƣớc với một
tập các công thức logic có trọng số. Nó cho phép sử dụng những ƣu điểm của logic
tân từ cấp một là khả năng biểu diễn tri thức và các mối quan hệ phức tạp của tri
thức, cùng với ƣu điểm của mạng Markov có thể xử lý một cách hiệu quả sự không
chắc chắn và giải quyết tri thức một cách đối lập và thiếu thông tin.
Luận văn thạc sĩ Phạm Đình Hiệu
7

Mục tiêu của luận văn là tm hiểu các mạng MLN và phƣơng pháp học cấu
trúc cho mạng MLN. Luận văn cũng triển khai một ứng dụng giải quyết bài toán
phân lớp với mạng MLN sử dụng phần mềm Thebeast. Cụ thể ở đây là bài toán gán
nhãn vai nghĩa trong lĩnh vực xử lý ngôn ngữ. 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ử. Việc xây dựng ngữ liệu mẫu
cho bài toán gán nhãn vai nghĩa tƣơng đối phức tạp, nên bƣớc đầu thực hiện chúng
tôi chỉ dùng giới hạn bài toán ở 2 vai nghĩa “tác thể” và “bị thể” trong câu.

Đị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 nối với nhau[3].
Định nghĩa 1.1.5. Clic (Clique) của đồ thị là một đồ thị con đầy đủ[3].
Hnh 1-1. Đồ thị G
Luận văn thạc sĩ Phạm Đình Hiệu
9 Clic cực đại là một clic với số nút là lớn nhất, không thể thêm bất kỳ nút nào
nữa để cho nó vẫn còn là một clic.
Ví dụ: Cho đồ thị nhƣ hnh vẽ:


Ví dụ trong hnh trên các clique cực đại là {(3; 4; 6); (3; 1); (1; 2); (2; 4); (2; 5); (5;
6)}
1.2 Logic tân từ cấp một
1.2.1 Các khái niệm và ký hiệu
Logic tân từ cấp một là một 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 ta mô tả thế giới với các đối tƣợng, các thuộc tính
của đối tƣợng và các mối quan hệ giữa các đối tƣợng[9].
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. Các lƣợng từ có mức ƣu tiên cao nhất.
2. Phép phủ định có mức ƣu tiên cao hơn các phép toán logic khác.
3. Phép hội có mức ƣu tiên cao hơn phép tuyển.
Ta có thể sử dụng các dấu ngoặc đơn để thực thi các mức ƣu tiên.
Ví dụ:
1. Nga và anh trai cô ấy không có bạn chung:

2. Tất cả con chim đều bay:

Luận văn thạc sĩ Phạm Đình Hiệu
11
Công thức đóng:
Một biến nằm trong phạm vi của lƣợng từ gọi là biến ràng buộc. Ví dụ là
biến ràng buộc trong .
Một biến nằm ngoài phạm vi của bất kỳ lƣợng từ nào gọi là biến tự do. Ví dụ :
là biến tự do trong .
Một công thức đƣợc gọi là công thức đóng nếu nó không chứa biến tự do nào.
Ở đây chúng ta chỉ quan tâm tới các công thức đóng.
Một literal dƣơng (Positive literal) là một công thức nguyên tử, một literal âm
(negative literal) là một công thức nguyên tử ở dạng phủ định. Các công thức trong
cơ sở tri thức KB (knowledge base) kết nối với nhau bởi phép hội, v vậy một KB có
thể đƣợc coi là một công thức đơn lớn.
Một hạng thức nền (hay hạng thức cụ thể) (ground term) là một hạng thức
không chứa biến. Một công thức nguyên tử nền (ground atom) là một công thức
nguyên tử mà tất cả các tham biến của nó đều là các hạng thức nền.
Không gian Herbrand (Herbrand universe) U(C) của tập các mệnh đề C là
tập các hạng thức cụ thể đƣợc xây dựng từ hàm và hằng trong C (hoặc nếu C không
“Hút thuốc dẫn đến ung thƣ”
“Nếu hai ngƣời là bạn th họ cùng hoặc
không cùng hút thuốc”
)

Luận văn thạc sĩ Phạm Đình Hiệu
13

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].

trong đó .
Minh họa bằng hnh vẽ:
Hnh 1-2. Phân phối biên trên biến rời rạc
Luận văn thạc sĩ Phạm Đình Hiệu
15  Trƣờng hợp cho các biến liên tục: Minh họa bằng hnh vẽ:

1.3.2 Công thức Bayes
Cho biến cố và các biến cố sao cho[8]:
- Có tập rời nhau từng đôi một.
-
Th ta có công thức tổng:

Công thức Bayes [1]:

Trong đó:
 A
1
, …, A

tennis. Tính giá trị của hai xác suất có điều kiện và , trong
đó là tập dữ liệu về thông tin về thời tiết nhƣ: trời nắng hay mƣa, nhiệt độ,
độ ẩm, sức gió,…
Giả thiết có thể nhất nếu , ngƣợc lại th
. V là nhƣ nhau đối với cả hai giả
thiết nên có thể bỏ qua đại lƣợng . V vậy chỉ cần tính hai biểu thức
và và đƣa ra kết quả tƣơng ứng.
 Nếu , th kết luận anh ta chơi tennis.
 Ngƣợc lại th kết luận anh ta không chơi tennis.
Giả sử trong phƣơng pháp ƣớc lƣợng hợp lý cực đại (hay đánh giá khả năng
xảy ra cao nhất – maximum likelihood estimation – MLE) tất cả các giá trị đều có
Luận văn thạc sĩ Phạm Đình Hiệu
17

giá trị xác suất tiên nghiệm nhƣ nhau : P( th phƣơng pháp MLE
tm giả thiết cực đại hóa giá trị trong đó gọi là khả năng xảy ra của
dữ liệu đối với .

Vẫn với ví dụ trên, tập bao gồm hai giả thiết : Anh ta chơi tennis, : Anh
ta không chơi tennis. lúc này là tập dữ liệu mà trong đó biết trời nắng, gió mạnh.
Giả sử ta có , vậy
hệ thống sẽ kết luận rằng anh ta sẽ không chơi tennis.
1.3.4 Xích Markov
Xét một hệ nào đó đƣợc quan sát tại những thời điểm rời rạc 0, 1, 2,…Giả sử
các quan sát đó là Khi đó ta có một dãy các đại lƣợng ngẫu nhiên
(ĐLNN) ( trong đó là trạng thái tại thời điểm của hệ. Giả thiết rằng mỗi
là ĐLNN rời rạc. Ký hiệu là tập giá trị của các . Khi đó là
một tập hữu hạn hay đếm đƣợc, các phần tử của nó đƣợc ký hiệu là Ta gọi
là không gian trạng thái của dãy.
Định nghĩa 1.3.7. Ta nói rằng dãy các ĐLNN ( là một xích Markov nếu

Phân phối dừng
Phân phối của hệ tại thời điểm đƣợc cho bởi công thức sau :
Luận văn thạc sĩ Phạm Đình Hiệu
19 Đặt và gọi là phân phối ban đầu của hệ.
Ta có . Và đƣợc gọi là phân phối dừng nếu

1.3.5 Xích Markov Monte Carlo
Tích phân Monte Carlo
Tiếp cận đầu tiên của Monte Carlo là một phƣơng pháp phát triển bởi các nhà
vật lý sử dụng phép sinh số ngẫu nhiên để tính toán. Giả sử rằng ta phải tính toán
tích phân rất phức tạp:

Nếu ta có thể phân tích hàm về dạng tích của một hàm và một hàm
mật độ đƣợc định nghĩa trong khoảng .

Tích phân có thể hiểu nhƣ là một kỳ vọng của hàm qua hàm mật độ
.
V vậy nếu ta sinh một số lƣợng lớn các biến ngẫu nhiên từ hàm
mật độ th:

Công thức này gọi là tích phân Monte Carlo.
Ví dụ:

Luận văn thạc sĩ Phạm Đình Hiệu
20
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.
Luận văn thạc sĩ Phạm Đình Hiệu
22

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

Giả sử ta muốn tính xác suất:

Ta có:

Ta có bảng sau: 1
1
1
1
0.012
1
1
1
0
0.0036
1
1
0
1
0.0024
1
1
0
0
0.0072

0
1
0
1
0.0192
0
1
0
0
0.0144
0
0
1
1
0.0588
0
0
1
0
0.0098
0
0
0
1
0.0432
0
0
0
0
0.0072

đó là công thức trong logic tân từ cấp một và là một số thực. Cùng với tập hữu
hạn các hằng số , nó định nghĩa một mạng Markov nhƣ
sau:
Luận văn thạc sĩ Phạm Đình Hiệu
25

a. 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.
b. 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. Trọng số của đặc trƣng đó là
tƣơng ứng với trong L.
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. 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].
Ví dụ: Để xây dựng minh họa này, giả sử ta xây dựng mạng Markov nền từ tập
gồm hai công thức[17]:
, hay với trọng số
hay
với trọng số .
Áp dụng với tập hằng C= {A, B}, ta thu đƣợc mạng Markov nhƣ hnh 2-2: