1
TÊN ĐỀ TÀI:
TÌM HIỂU CONDITIONAL RANDOM FIELDS
VÀ GIỚI THIỆU CÔNG CỤ CRF+ + TRONG BÀI TOÁN TRÍCH
CHỌN THÔNG TIN
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

BÀI TIỂU LUẬN MÔN
MÁY HỌC VÀ ỨNG DỤNG
Giảng viên hướng dẫn: PGS. TS. Vũ Thanh Nguyên
Họ tên học viên: Đặng Thị Mỹ Hạnh
Mã số học viên: CH1301012
CHƯƠNG 1
TÌM HIỂU CONDITIONAL RANDOM FIELDS (CRF)
1. Nguồn gốc
CRF được giới thiệu vào những năm 2001 bởi Lafferty và các đồng nghiệp
[14] [11]. CRF là mô hình dựa trên xác xuất điều kiện, thường được sử dụng trong
gán nhãn và phân tích dữ liệu tuần tự ví dụ ký tự, ngôn ngữ tự nhiên. Khác với mô
hình MEMM (Mô hình Markov cực đại hóa Entropy – Maximum Entropy Markov
Model), CRF là mô hình đồ thị vô hướng. Điều này cho phép CRF có thể định
nghĩa phân phối xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan
sát cho trước thay vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái
trước đó và quan sát hiện tại như trong mô hình MEMM. Chính những tính chất
này của CRF mà mô hình này giải quyết được vấn đề “label bias” - gán nhãn.
2. Định nghĩa
2.1. Định nghĩa trường ngẫu nhiên
Cho một đồ thị vô hướng không có chu trình G(V,E), ở đây V là tập các đỉnh
của đồ thị và E là tập các cạnh vô hướng nối các đỉnh của đồ thị nếu thỏa mãn:
P(v
i

, Y
6
} là trường ngẫu nhiên.
2.2. Trường ngẫu nhiên có điều kiện - CRF
- Trường ngẫu nhiên có điều kiện được phát biểu như sau: X là biến ngẫu
nhiên nhận giá trị là chuỗi dữ liệu cần phải gán nhãn. Y là biến ngẫu nhiên nhận
giá trị là chuỗi nhãn tương ứng. Mỗi thành phần Y
i
của Y là một biến ngẫu nhiên
nhận giá trị trong tập hữu hạn các trạng thái S. Các đỉnh V biểu diễn các thành
2
phần của biến ngẫu nhiên Ysao cho tồn tại ánh xạ một - một giữa các đỉnh và một
thành phần Y
v
của Y.
- Hay CRFs là mô hình trạng thái tuyến tính vô hướng (máy trạng thái hữu
hạn được huấn luyện có điều kiện) và tuân theo tính chất Markov thứ nhất.
+ Gọi o = (o
1
, o
2
, …, o
T
) là một chuỗi dữ liệu quan sát cần được gán nhãn.
Gọi S là tập trạng thái, mỗi trạng thái liên kết với một nhãn. Đặt s = (s
1
, s
2
,…, s
T

- Ngoài ra có thể hiểu Conditional random fields là một probabilistic
framework (theo xác suất) cho việc gán nhãn và phân đoạn dữ liệu tuần tự. Thay vì
sử dụng xác suất độc lập trên chuỗi nhãn và chuỗi quan sát, ta sử dụng xác suất có
điều kiện P(Y|X) trên toàn bộ chuỗi nhãn được đưa bởi chuỗi mỗi chuỗi quan sát
X. CRF là một mô hình đồ thị vô hướng định nghĩa một phân bố tuyến tính đơn
3
trên các chuỗi nhãn (trình tự nhãn) được đưa ra bởi các chuỗi quan sát được. CRFs
thuận lợi hơn các mô hình Markov và MEMM. Nó làm tốt hơn cả của MEMM và
HMM (Mô hình Markov ẩn – Hiden Markov Model) trên sốlượng chuỗi gán nhãn
lớn. Ví dụ: xét ngôn ngữ tự nhiên, việc gán nhãn cho các từ trong câu sẽ tương ứng
với loại từ vựng. Ở đây các câu sẽ là dữ liệu tuần tự còn nhãn cần gán chính là các
từ loại:
[NP He] [VP reckons] [NP the current account deficit] [VP will narrow] [PP
to] [NP only # 1.8 billion ] [PP in ] [NP September ]
Trong đó ý nghĩa của các nhãn là: NP: nounse phrase, VP: verb phrase…
4
Punctuation Tags
#
$
''
(
)
,
.
:
``
- Một phát biểu khác về CRF: (Y|X) là một trường ngẫu nhiên điều kiện
(Conditional Random Field) với điều kiện X khi ta chỉ tính được xác xuất có điều
kiện P(Y
i

Hình: Đồ thị vô hướng mô tả cho CRF
3. Tính chất của trường ngẫu nhiên có điều kiện
- Mô hình phân biệt (discriminative models)
- Mô hình chuỗi (sequential models)
- Mô hình đồ thị vô hướng (Undirected graphical models)
4. Mục đích
- CRFs đã được chứng minh rất thành công cho các bài toán gán nhãn cho
chuỗi như tách từ, gán nhãn cụm từ, xác định thực thể, gán nhãn cụm danh từ ⇒
sử dụng phương pháp CRF kết hợp với một vài phương pháp xử lý khác (như xử lý
ngôn ngữ tự nhiên) giúp nâng cao hiệu quả của trích xuất thông tin web.
- Người ta thường huấn luyện CRFs bằng cách làm cực đại hóa hàm
likelihood theo dữ liệu huấn luyện sử dụng các kĩ thuật tối ưu. Việc lập luận (dựa
trên mô hình đã học) là tìm ra chuỗi nhãn tương ứng của một chuỗi quan sát đầu
vào. Đối với CRFs, người ta thường sử dụng thuật toán qui hoạch động điển hình
(Viterbi) để thực hiện lập luận với dữ liệu mới.
- Cách giải quyết vấn đề: Giả sử cần rút trích thông tin từ trang web cho
trước, khi đó cần xác định mục tiêu.
+ Xác định trang web có chứa tin tức hay không?
+ Xác định vùng thông tin chứa tin tức?
+ Xác định tin tức thuộc loại tin tức nào?
 Có thể xem mục tiêu đặt ra được diễn giải như sau:
Cho một trang web x và tập DOM (document object model), nút lá cây x
1
,
…,x
k
trong x. Đặt = y
1
,…,y
k

+ Xử lý tiếng việt chỉ xảy ra ở bước xác định từ loại điều này giúp vấn đề trở
nên đơn giản hơn.
+ Xác định ngữ pháp của câu.
+ Sự giúp đỡ của bộ từ điển tiếng Việt.
5. Thuật toán gán nhãn cho dữ liệu dạng chuỗi
- Hai vấn đề quan trọng cần phải được đề cập đến khi nghiên cứu về mô hình
CRF đó là: thứ nhất khi đưa chuỗi nhãn y và một chuỗi quan sát x làm thế nào tìm
ra một tham số λ của CRF để làm cực đại hóa xác suất p(y|x, λ) vấn đề này tạm gọi
là huấn luyện (training). Thứ hai khi đưa ra một chuỗi quan xát x và một tham số λ
làm thế nào để tìm được chuỗi các nhãn y phù hợp nhất tạm gọi vấn đề này quy
nạp (inference).
- Mục đích của việc gán nhãn là làm sao tìm được chuỗi y* sao cho cực đại
hóa xác suất p(y|x, λ). Hay nói cách khác mục đích của thuật toán là làm sao tìm ra
chuỗi nhãn phù hợp nhất với chuỗi dữ liệu quan sát.
7
- Thay việc tính xác suất tổng các xác suất ta chỉ cần tính giá trị lớn nhất của
xác suất dịch chuyển. Khi đó chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu
quan sát x là nghiệm của phương trình.
(**)
- Vì Z(x) không phụ thuộc vào nhãn riêng biệt x và số mũ là một hàm đơn
điệu. Nên ta bỏ qua Z(x) trong công thức (**). Để tìm được y*, thỏa mãn (**) thì
gặp phải một khó khăn trong thời gian tính toán, vì thời gian tính toán là hàm mũ.
- Chuỗi y* được xác định bằng thuật toán Virterbi. Định nghĩa ∂
i
(y) là xác
suất của chuỗi trạng thái độ dài i kết thúc bởi trạng thái y và có xác suất lớn nhất
biết chuỗi quan sát là x. Trong đó ∂
1
(y
k

t
k
(y
’
, y, x) + ∑
k
s
k
(y, x)), ∀y∈ Y
Ψ
i(y)
= arg max(∂
i
(y
’
) + ∑λ
k
t
k
(y
’
, y, x) + ∑
k
s
k
(y, x)), ∀y∈ Y
Bước 3: Dừng
Đệ quy dừng khi i=n bằng chiều dài của chuỗi
6. Ứng dụng
- Một trong các ứng dụng nổi trội của CRFs là rút trích thông tin (Information

1. Giới thiệu
- CRF ++ là một công cụ cài đặt mô hình CRF và được phân phối dưới dạng
mã nguồn mở có thể dùng để phân đoạn và gán nhãn dữ liệu tuần tự.
- CRF++ được thiết kế cho cùng một mục đích phổ dụng có thể ứng dụng
trong những bài toán xử lý ngôn ngữ tự nhiên như nhận dạng thực thể tên, trích
chọn thông tin và đóng khung văn bản.
- Hệ thống được hoạt động theo phương pháp học nửa giám sát được thực
hiện gồm các bước sau:
10
Bước 1: Tạo bộ dữ liệu huấn luyện bé. Bước này được thực hiện bằng tay.
Bước 2: Sử dụng mô hình CRFs để huấn luyện trên tập dữ liệu này.
Bước 3: Tạo tập test và sử dụng CRFs để gán nhãn.
Bước 4: Bộ dữ liệu mới được sinh ra bằng cách bổ sung các nhãn cho tập dữ
liệu test.
- CRF++ được chia làm 2 modulo chính có thể mô tả như hình như sau:
Hình: Mô hình hoạt động của CRF++
2. Tính năng
- Có thể định nghĩa lại các tính năng đã có, ta có thể tùy biến để thêm các đặc
trưng mới phù hợp với bài toán cụ thể.
- Viết bằng C++, là phần mềm mã nguồn mở.
- Bộ nhớ nhỏ sử dụng trong cả kiểm tra và phân tích.
- Có thể đưa ra xác suất lề cho tất cả những đầu vào.
3. Cài đặt và cách sử dụng
Cài đặt
- Chuyển vào thư mục chứa công cụ CRF++
- Dùng chmod 777 ./configure
- make clean && make
11
4. File định dạng huấn luyện và test
Để sử dụng được CRF++ ta cần phải có 2 file dữ liệu, 1 file dùng cho quá

reckons VBZ B-VP
Ví dụ 2:
Ke NN B-NP
hoach NN I-NP
bien VB B-VP
soan VB I-VB
giao NN B-NN
trinh NN I-NN
nam NN B-NN
hoc NN I-NN
2011 CD B-CD
2012 CD I-VP
Template type
File này mô tả những đặc trưng sẽ sử dụng khi huấn luyện và kiểm tra. Mỗi
một dòng trong trong file template chỉ ra một template, mỗi một template có dạng
như sau %x[row,col] dùng để định nghĩa một từ trong dữ liệu đầu vào.
File template được xây dựng tùy vào từng bài toán cụ thể và tùy vào file huấn
luyện và file kiểm tra. Ví dụ với dữ liệu đầu vào như sau thì file template sẽ được
xây dựng như sau:
Dữ liệu đầu vào
He PRP B-NP
reckons VBZ B-VP
the DT B-NP << CURRENT TOKEN
current JJ I-NP
account NN I-NP
Template Từ tố tương ứng
%x[0,0] The
%x[0,1] DT
13
%x[-1,0] Reckons

obj: Giá trị của đối tượng hiện tại. Khi giá trị này hội tụ tại một điểm cố định.
CRF ++ dừng lặp
5.2. Kiểm tra (testing)
Để kiểm tra dữ liệu sau khi huấn luyện sử dụng lệnh crf_test với cú pháp như
sau:
% crf_test -m model_file test_files
Model_file là file do crf_learn tạo ra. Trong khi test không cần tạo ra
template_file bởi vì model file có thông tin giống như file template .
Test_file là kiểm tra dữ liệu bạn muốn gán thẻ theo trình tự. File này có định
dạng giống như file traning được xây dựng ở trên.
Hình: Công cụ CRF++-0.58
15