TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Loan
TÌM HIỂU MÔ HÌNH CRF
VÀ ỨNG DỤNG TRONG TRÍCH CHỌN THÔNG TIN
TRONG TIẾNG VIỆT
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI -2009
i
TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Loan
TÌM HIỂU MÔ HÌNH CRF
VÀ ỨNG DỤNG TRONG TRÍCH CHỌN THÔNG TIN
TRONG TIẾNG VIỆT
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn : Tiến Sĩ Nguyễn Trí Thành
HÀ NỘI – 2009
ii
LỜI CẢM ƠN
Trước tiên, em muốn gửi lời cảm ơn sâu sắc đến Tiến Sĩ Nguyễn Trí Thành, người
đã tận tình hướng dẫn em trong suốt quá trình thực hiện khóa luận.
Em xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy, cô tại trường Đại học
Công Nghệ đã dạy dỗ và tận tình chỉ bảo cho tôi trong suốt quá trình học tập tại trường.
Những kiến thức mà thầy cô truyền đạt sẽ là vốn quý báu cho chúng em bước vào tương
lai.
Mình xin cảm ơn tập thể sinh viên K50C Trường Đại học Công Nghệ đã ủng hộ và
khuyến khích tôi trong quá trình nghiên cứu và thực hiện khóa luận này.
Cuối cùng, con xin cảm ơn chân thành và biết ơn vô hạn tới gia đình, những người

BẢNG CÁC KÍ HIỆU VIẾT TẮT...................................................................................ix
LỜI MỞ ĐẦU...................................................................................................................1
Hình 1. Một hệ thống trích chọn thông tin........................................................................4
1.2.1. Hướng tiếp cận dựa trên tri thức.............................................................................4
Hình 2. Mô hình xây dựng IE theo hướng tiếp cận dựa trên tri thức............................5
1.2.2. Hướng tiếp cận xây dựng các mô hình học máy.......................................................5
Hình 3. Mô hình xây dựng IE theo mô hình học máy........................................................6
Hình 4. Modules chính của hệ thống IE ...........................................................................7
1.4. BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT................................................7
Hình 5. HMM..................................................................................................................12
Hình 6. Đồ thị vô hướng HMM.......................................................................................12
Hình 7. Đồ thị có hướng mô tả cho mô hinh MEMM.......................................................13
Hình 8. label alias...........................................................................................................14
2.3.1. Việc gán nhãn cho dữ liệu tuần tự ........................................................................15
2.3.2. Định nghĩa CRF.....................................................................................................16
Hình 9. Một trường ngẫu nhiên........................................................................................17
Hình 10. Đồ thị vô hướng mô tả cho CRF.......................................................................17
Hình 11. Mô tả các hàm tiềm năng.................................................................................18
2.3.3. Nguyên lý cực đại hóa Entropy..............................................................................18
2.3.3.1. Độ đo Entropy điều kiện..........................................................................................18
2.3.3.2. Các ràng buộc đối với phân phối mô hình...............................................................18
2.3.3.3. Nguyên lý cực đại hóa Entropy................................................................................19
2.3.4. Hàm tiềm năng của các mô hình CRF....................................................................20
2.3.5. Conditional Random Fields....................................................................................20
2.3.6. So sánh với các mô hình khác................................................................................22
Hình 12. Tỷ lệ lỗi của CRF so với các mô hình học máy khác........................................22
3.3.1. Thuật toán S...........................................................................................................27
3.3.2. Thuật toán T..........................................................................................................29
v
3.4.1. Giới thiệu...............................................................................................................29

BẢNG CÁC KÍ HIỆU VIẾT TẮT...................................................................................ix
LỜI MỞ ĐẦU...................................................................................................................1
Hình 1. Một hệ thống trích chọn thông tin........................................................................4
1.2.1. Hướng tiếp cận dựa trên tri thức.............................................................................4
Hình 2. Mô hình xây dựng IE theo hướng tiếp cận dựa trên tri thức............................5
1.2.2. Hướng tiếp cận xây dựng các mô hình học máy.......................................................5
Hình 3. Mô hình xây dựng IE theo mô hình học máy........................................................6
Hình 4. Modules chính của hệ thống IE ...........................................................................7
1.4. BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT................................................7
Hình 5. HMM..................................................................................................................12
Hình 6. Đồ thị vô hướng HMM.......................................................................................12
Hình 7. Đồ thị có hướng mô tả cho mô hinh MEMM.......................................................13
Hình 8. label alias...........................................................................................................14
2.3.1. Việc gán nhãn cho dữ liệu tuần tự ........................................................................15
2.3.2. Định nghĩa CRF.....................................................................................................16
Hình 9. Một trường ngẫu nhiên........................................................................................17
Hình 10. Đồ thị vô hướng mô tả cho CRF.......................................................................17
Hình 11. Mô tả các hàm tiềm năng.................................................................................18
2.3.3. Nguyên lý cực đại hóa Entropy..............................................................................18
2.3.4. Hàm tiềm năng của các mô hình CRF....................................................................20
2.3.5. Conditional Random Fields....................................................................................20
2.3.6. So sánh với các mô hình khác................................................................................22
Hình 12. Tỷ lệ lỗi của CRF so với các mô hình học máy khác........................................22
3.3.1. Thuật toán S...........................................................................................................27
3.3.2. Thuật toán T..........................................................................................................29
3.4.1. Giới thiệu...............................................................................................................29
vii
Hình 13. Mô hình hoạt động của CRF++.........................................................................31
3.4.2. Tính năng...............................................................................................................31
3.4.3. Cài đặt và cách sử dụng.........................................................................................31

tạp như hình ảnh, âm thanh.
Việc ứng dụng công nghệ xử lý ngôn ngữ cũng hết sức phong phú. Có thể kể tới
trong những năm gần đây có một số công nghệ rất nổi tiếng như [1]: Hãng SAMSUNG
đưa ra thị trường điện thoại di động P207 có thể nhận biết được các câu nói đơn giản ví
dụ “tôi sẽ gọi lại” rồi chuyển chúng về dạng tin nhắn. Bên cạnh đó có rất nhiều những
công nghệ dịch tự động trên web như Language Tool dịch nhiều thứ tiếng trong google.
Có thể phân loại các bài toán như xử lý tiếng nói hay xử lý hình ảnh (speech and image
processing), xử lý văn bản (text processing), khai phá văn bản hoặc web (text and web
mining). Tất cả các bài toán đều được thực hiện bằng máy, tuy nhiên vấn đề đặt ra là
làm thế là để máy có thể xử lý một cách tự động lại là một bài toán khó. Cái khó ở chỗ
làm sao cho máy hiểu được ngôn ngữ đa dạng của con người.
Đối với tiếng Việt đã có một số các sản phẩm liên quan đến tiếng Việt như: Bộ gõ
chữ tiếng Việt, chương trình nhận dạng chữ tiếng Việt như VnDOCR của viện Công
Nghệ Thông Tin, các phần mềm như EVTRAN, gần đây tiêu biểu là kết quả của việc
Việt hóa Windows và Office.
Là người đi sau trong lĩnh vực xử lí ngôn ngữ tự nhiên, việc hiểu các công nghệ
ngôn ngữ là rất cần thiết. Trong luận văn này đề cập tới ứng dụng của CNTT trong việc
trích chọn thông tin trong tiếng Việt. Có rất nhiều phương pháp, trong luận văn này giới
thiệu mô hình Conditional Random Field là cơ sở lý thuyết để thực hiện công việc và
công cụ CRF++ để thực hành trích chọn thông tin trong tiếng Việt và cụ thể là bài toán
trích chọn thông tin nhà đất.
Trong khuôn khổ của khóa luận tốt nghiệp với đề tài “Tìm hiểu mô hình CRF và
ứng dụng trong trích chọn thông tin trong tiếng Việt” em xin trình bày một công nghệ
ứng dụng trong việc xử lý ngôn ngữ tiếng Việt. Nội dung khóa luận gồm 4 chương:
 Chương 1: Tổng quan: Giới thiệu tổng quan về trích chọn thông tin, và các
cách tiếp cận để xây dựng hệ thống trích chọn thông tin những ứng dụng của
trích chọn thông tin, và ứng dụng trong xử lý tiếng Việt, đồng thời cũng mô
hình hóa và nêu được ý nghĩa của bài toán trích chọn thông tin nhà đất.
1
 Chương 2: Conditional Random Fields: Chương này giới thiệu một số mô

 Tìm kiếm thông tin hoặc tài liệu: Tệp tin là những từ có thể là một chuỗi các đơn
vị từ mang một ý nghĩa nào đó.
 Trích chọn thông tin: Cũng như “tìm thông tin tài liệu” nhưng nó có thể là một từ
hoặc một cụm từ có nghĩa và liên quan đến một chủ đề cụ thể nào đó.
 Hiểu toàn văn bản (text understanding). Tệp tin như câu truyện, tiểu thuyết. Với
dữ liệu đầu vào rất lớn. Và nhiệm vụ của mình phải “hiểu toàn văn bản” mới đưa
ra được nội dung cần quan tâm.
Không giống như việc hiểu toàn văn bản (tất cả các câu chữ đều liên quan đến
nhau), các hệ thống trích chọn thông tin chỉ cố gắng nhận biết một số nội dung thông tin
đáng quan tâm. Có thể kể tới các mức độ trích chọn thông tin từ văn bản sau: Trích chọn
các thực thể (Entity Extraction), trích chọn quan hệ giữa các thực thể (Relation
Extraction), xác định đồng tham chiếu (Co-reference Resolution). Cũng phải lưu ý rằng
trích chọn không đơn thuần là trích chọn trong một văn bản với các ký tự ASCII hoặc
Unicode. Trích chọn ở đây có thể là trích chọn âm thanh, trích chọn hình ảnh. Tuy nhiên
trong luận văn này chỉ tập chung giới thiệu trích chọn thông tin liên quan tới văn bản.
Các kỹ thuật sử dụng trong trích chọn thông tin gồm: Phân đoạn, phân lớp, kết hợp
và phân cụm.
3
October 14, 2002, 4:00 a.m. PT
For years, Microsoft Corporation CEO Bill
Gates railed against the economic philosophy
of open-source software with Orwellian fervor,
denouncing its communal licensing as a
"cancer" that stifled technological innovation.
Today, Microsoft claims to "love" the open-
source concept, by which software code is
made public to encourage improvement and
development by outside programmers. Gates
himself says Microsoft will gladly disclose its
crown jewels--the coveted code behind the

Stallman
founder
Free Soft..
NAME
TITLE ORGANIZATION
Bill Gates
CEO
Microsoft
Bill
Veghte
VP
Microsoft
Richard
Stallman
founder
Free Soft..
*
*
*
*
Hình 1. Một hệ thống trích chọn thông tin
Trích chọn thông tin như một nhiệm vụ lấp đầy các trường (slots) trong cơ sở dữ
liệu bằng những đoạn text nhỏ hơn (hay nói cách khác kết quả của một hệ thống trích
chọn thông tin thường là các mẫu chứa một số lượng xác định các trường đã được điền
thông tin). Ví dụ như ở hình 1 ta có một hệ thống trích chọn những tên riêng xuất hiện
trong văn bản, trích chọn các tổ chức liên quan, tìm các sự liên kết giữa các tổ chức và
tên người, vị trí của người đó trong tổ chức và cuối cùng là đưa vào trong cơ sở dữ liệu.
1.2. CÁC CÁCH TIẾP CẬN TRÍCH CHỌN THÔNG TIN
1.2.1. Hướng tiếp cận dựa trên tri thức
Đặc điểm của việc xây dựng hệ thống trích chọn thông tin theo hướng này là hệ

Luật cũ
Kiểm duyệt
Sửa chữa
Luật mới
Cập nhật
knowlegde
engineer
cần rút trích. Một khi dữ liệu huấn luyện được chú thích, thuật toán huấn luyện chạy và
sinh ra những thông tin học được hay còn gọi là model để phục vụ cho quá trình trích
chọn tự động sau này. Mô hình với hướng tiếp cận này được mô tả qua hình 3 như sau:
Các thuật học sẽ dựa trên dữ liệu để tự học và thu được một model, dựa trên model này
nó sẽ trích chọn các thông tin trên dữ liệu mới.

Hình 3. Mô hình xây dựng IE theo mô hình học máy
Khi xây dựng hệ thống IE theo hướng này phải tập trung vào việc tạo ra dữ liệu
huấn luyện. Hệ thống có thể tự học mà không cần sự can thiệp của bất kỳ các chuyên
viên nào. Tuy vậy việc xây dựng và lưu trữ tập dữ liệu huấn luyện rất khó và đắt vì để
hệ thống có thể thực hiện tốt thì yêu cầu dữ liệu phải nhiều đó cũng là hệ quả dẫn đến
việc khó sửa đổi. Vì chỉ cần thêm hoặc xóa các thuộc tính thì cần phải thay đổi trên toàn
tập huấn luyện của nó.
Tùy vào công việc và những điều kiện đã có mà ta có thể xây dựng hệ thống IE
theo hướng các mô hình học máy hoặc theo hướng tiếp cận dựa tri thức. Ví dụ như khi
nguồn văn bản và người viết luật đáp ứng được yêu cầu thì nên xây dựng hệ thống IE
theo hướng tiếp cận dựa tri thức, hoặc khi các mô tả về thông tin trích chọn luôn có sự
thay đổi thì cũng lên làm theo hướng thứ nhất. Còn với dữ liệu lớn thì nên xây dựng hệ
thống IE theo mô hình học máy.
1.3. KIẾN TRÚC HỆ THỐNG IE
Mặc dù hệ thống IE được xây dựng theo các ứng dụng và công việc khác nhau,
theo những cách khác nhau. Nhưng về cơ bản thì một hệ thống IE nói chung có những
phần tử chính được mô tả trong hình sau:

vựng
Phân tích cú pháp
Phân tích miền
Ở đây chúng ta phải phân biệt rõ giữa tìm kiếm thông tin (Information Retrival
-IR) và trích chọn thông tin (Information Extraction -IE). IR có thể hiểu đơn giản là từ
một nguồn rất nhiều tệp văn bản hay tiếng nói tìm ra những tệp có nội dung liên quan
đến một câu hỏi hay một điều cần biết. Điển hình của công nghệ này là Google, một hệ
tìm kiếm trên web. Cần nói thêm rằng mặc dù rất hữu hiệu, nhưng google chỉ cho chúng
ta tìm theo những từ khóa và đôi khi tìm những kết quả không hề liên quan, hoặc tìm ra
những văn bản vốn đã tồn tại trên Web.
Với Information Extraction từ một nguồn rất nhiều tệp văn bản hay lời nói tìm ra
những đoạn bên trong một số tệp liên quan đến một vấn đề cần quan tâm. Ví dụ xét một
bản tin nhà đất sau:
“Cần bán chung cư TT9 Văn Phú mặt đường Lê Trọng Tốn, diện tích 90m2, mặt
tiền 4,5m. Giá bán: 1 tỷ Liên hệ: 0988830999”
Với bản tin nhà đất trên ta chỉ cần quan tâm đến địa chỉ, diện tích, giá bán, loại nhà
và điện thoại liên hệ. Do vậy không nhất thiết phải hiểu toàn văn bản, mục đích của bài
toán trích chọn thông tin nhà đất là làm sao đưa ra được các thông tin liên quan đến địa
chỉ, diện tích, giá bán, loại nhà… từ một khối dữ liệu rất lớn. Với mục đích đó văn bản
trên có thể được mô phỏng bằng cách gán nhãn như sau:
Cần bán chung<B-LN> cư<I-LN> TT9<B-DC> Văn <I-DC> Phú<I-DC> mặt
đường Lê <B-DC> Trọng <I-DC>Tốn <I-DC>, diện tích 90m2<I-DT>, mặt tiền 4,5m.
Giá bán: 1<B-GB> tỷ <I-GB>. Liên hệ: 0988830999 <B-DD>.
Với các quy ước các nhãn cho các từ tố trong đoạn tin trên như sau:
 DC: Địa chỉ trong đó B-DC là từ bắt đầu của địa chỉ và I-DC là các từ tiếp
theo của địa chỉ
 GB: Giá bán trong đó B-GB là từ bắt đầu của giá bán và I-GB là các từ tiếp
theo của giá bán
 DT: Diện tích trong đó B-DT là từ bắt đầu của diện tích và I-DT từ tiếp
theo của diện tích

trong thư viện số- DL (Digital Libraries) - thư viện số có thể hiểu là các văn bản
hoặc hình ảnh…. Rút trích thông tin từ thư điện tử. Trích chọn tiểu sử người (có
thể là chân dung, vị trí, email, địa chỉ, số điện thoại, số fax…)
1.6. TỔNG KẾT CHƯƠNG
Chương này giới thiệu tổng quan về trích chọn thông tin. Với hai hướng tiếp cận
của xây dựng hệ thống trích chọn thông tin theo hướng máy tri thức và theo hướng hệ
9
thống tự đào tạo giúp mọi người có thể hình dung ra được các cách tiếp cận với trích
chọn thông tin. Đồng thời cũng nêu ra được nhiệm vụ của khóa luận.
Chương 2.
CONDITIONAL RANDOM FIELDS
Như giới thiệu trong chương trước, chương này giới thiệu vào một số mô hình học
máy, trong đó tập trung vào mô hình Conditional Random Fields (CRF) [11] [13] [8]
10
[17], phần đầu nêu lên hai mô hình học máy HMM, và MEMM và những vấn đề gặp
phải từ đó nêu lên mô hình học máy CRF có thể giải quyết được các vấn đề đó như thế
nào. Đồng thời cũng giới thiệu được chi tiết về mô hình CRF như: Đưa ra được định
nghĩa CRF, xác định các hàm tiềm năng của CRF thông qua nguyên lý cực đại hóa
Entropy, xác định được các ràng buộc của mô hình.
Một số qui ước ký hiệu:
 Chữ viết hoa X, Y, Z.. kí hiệu cho các biến ngẫu nhiên.
 Chữ đậm
x
r
ví dụ: x = (x
1
,...,x
n
), y, t .. ký hiệu các vector vector
biểu diễn chuỗi dữ liệu quan sát , vector biểu diễn chuỗi các nhãn.

ij
— Các xác suất chuyển tiếp
- b
ij
— Các xác suất đầu ra
- y
i
— Các dữ liệu quan sát
Mô hình Markov ẩn thêm vào các đầu ra: mỗi trạng thái có xác suất phân bố trên
các biểu hiện đầu ra có thể. Vì vậy, nhìn vào dãy của các biểu hiện được sinh ra bởi
HMM không trực tiếp chỉ ra dãy các trạng thái. Ta có tìm ra được chuỗi các trạng thái
mô tả tốt nhất cho chuỗi dữ liệu quan sát được bằng cách tính.

)(/)|()|( XPXYPXYP =
(2.1)

Hình 6. Đồ thị vô hướng HMM
Ở đó Y
n
là trạng thái tại thời điểm thứ t=n trong chuỗi trạng thái Y, X
n
là dữ liệu
quan sát được tại thời điểm thứ t=n trong chuỗi X. Do trạng thái hiện tại chỉ phụ thuộc
vào trạng thái ngay trước đó với giả thiết rằng dữ liệu quan sát được tại thời điểm t chỉ
phụ thuộc và trạng thái t. Ta có thể tính P(Y, X).
∏
−
−
=
n

i
) thay vì sử dụng P(S
i
| S
i-1
) và P(O
i
| S
i
). Mô hình MEMM quan niệm rằng các quan sát
đã được cho trước và chúng ta không cần quan tâm đến xác suất sinh ra chúng mà chỉ
quan tâm vào xác suất chuyển trạng thái.
Dưới đây là đồ thị có hướng mô tả cho mô hình MEMM.Hình 7. Đồ thị có hướng mô tả cho mô hinh MEMM
Qua đồ thị ta nhận thấy rằng quan sát hiện tại không chỉ phụ thuộc vào trạng thái
hiện tại mà còn có thể phụ thuộc vào trạng thái trước đó.
Xác suất P(S | O) có thể tính như sau:
∏
=
−
=
n
t
ttt
OSSPOSPOSP
1
1
),|(*),()|(


=
∑
−
−
),(exp
),(
1
)|(
1
1
tta
a
a
tt
ttS
SOf
SOZ
OSP
t
λ
(2.4)
Ở đây
a
λ
là các tham số cần được huấn luyện; Z(O
t
, S
t
) là thừa số chuẩn hóa để

t
)=1 và S
t
=S
t-1
f<b,S
t
>(O
t
,S
t
)=
0 nếu ngược lại
Vấn đề “label alias” gặp phải trong mô hình MEMM
Vấn đề gặp phải ở mô hình MEMM [14] “lable alias”. Xét một ví dụ đơn giản
sau:
Hình 8. label alias
Giả sử ta cần xác định chuỗi trạng thái khi xuất hiện chuỗi quan sát là “rob” do
vậy chuỗi trạng thái đúng là 0345 vì vậy ta mong đợi xác suất.
P( 0345|rob ) > P( 0125|rob)
Lại có P(0125|rob) = P(0)*P(1|0, r)*P(2|1,o )*P(5|2, b).
14
Do xác suất chuyển trạng thái của 2 trạng thái kề nhau là l. Do vậy:
P(0125 | rob)=P(0)*P(1 | 0, r).
Tương tự ta cũng có P(0345 | rob)=P(0)*P(3 | 0, r). Nếu trong tập huấn luyện
“rib”xuất hiện nhiều hơn “rob” thì chuỗi trạng thái S=0125 luôn được chọn dù chuỗi
quan sát là rib hay rob. Đây là hạn chế gặp phải trong mô hình MEMM, hạn chế này ảnh
hưởng rất lớn đến quá trình gán nhãn của MEMM.
Để giải quyết vấn đề alias Léon Bottou (1991) [4] đưa ra một số cách sau: Thứ
nhất như mô hình ở trên ta có thể gộp trạng thái 1 và 4 và trì hoãn việc phân nhánh cho