Khóa luận 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
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
có công sinh thành, nuôi dưỡng, những người luôn kịp thời động viên và giúp đỡ vượt qua
những khó khăn trong cuộc sống.
Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhưng
chắc chắn sẽ không tránh khỏi những thiếu sót. Chúng em kính mong nhận được sự thông
cảm của quý Thầy Cô và các bạn
Hà Nội, ngày 12 tháng 5 năm 2009
Sinh viên
Nguyễn Thị Loan
iii
TÓM TẮT
Nội dung của khóa luận là tìm hiểu mô hình CRF, và ứng dụng của mô hình này
trong trích chọn thông tin trong tiếng Việt. Trước hết khóa luận trình bày những khái
niệm chung về trích chọn thông thông tin. Đồng thời nêu đến hai hướng tiếp cận để xây
dựng một hệ thống trích chọn thông tin cũng như ưu nhược điểm của từng hướng tiếp cận,
Đồng thời cũng nêu ra được ứng dụng của trích chọn thông tin trong tiếng Việt như thế
nào. Cụ thể ở đây là bài toán trích chọn thông tin nhà đất.
Để ứng dụng trích chọn trong tiếng Việt luận văn đã nêu ra được ba mô hình học
máy trong đó tập trung chủ yếu vào mô hình Conditional Random Field –CRF. Bất kỳ mô
hình nào cũng có ưu nhược điểm trong luận văn này trình bày hai vấn đề lớn của mô hình
CRF đó là vấn đề gán nhãn và ước lượng tham số. Đồng thời cũng trình bày về công cụ
hữu ích CRF++.
Luận văn cũng trình bày được việc ứng dụng mô hình CRF làm nền tảng lý thuyết
và cơ sở thực hành là công cụ CRF vào bài toán trích chọn thông tin nhà đất. Một bài toán
nhỏ trong bài toán xử lý ngôn ngữ tự nhiên.
iv
MỤC LỤC
LỜI CẢM ƠN ................................................................................................................... iii
TÓM TẮT ..........................................................................................................................iv
MỤC LỤC ...........................................................................................................................v
DANH MỤC CÁC HÌNH VẼ..........................................................................................vii
BẢNG CÁC KÍ HIỆU VIẾT TẮT................................................................................ viii
LỜI MỞ ĐẦU .....................................................................................................................1
Chương 1.TỔNG QUAN....................................................................................................3
1.1. TRÍCH CHỌN THÔNG TIN ................................................................................................ 3
1.2. CÁC CÁCH TIẾP CẬN TRÍCH CHỌN THÔNG TIN........................................................ 5
1.2.1. 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
1.3. KIẾN TRÚC HỆ THỐNG IE................................................................................................ 7
1.4. BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT..............................................8
1.5. Ý NGHĨA CỦA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT.............................. 9
1.6. TỔNG KẾT CHƯƠNG....................................................................................................... 10
Chương 2. CONDITIONAL RANDOM FIELDS.........................................................11
2.1. MÔ HÌNH MARKOV ẨN- HMM...................................................................................... 11
2.2. MÔ HÌNH CỰC ĐẠI HÓA ENTROPY-MEMM............................................................... 13
2.3. MÔ HÌNH CONDITIONAL RANDOM FIELDS.............................................................. 15
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
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..................................................... 19
2.3.3.3. Nguyên lý cực đại hóa Entropy....................................................................... 20
2.3.4. Hàm tiềm năng của các mô hình CRF.............................................................20
2.3.5. Conditional Random Fields.............................................................................21
2.3.6. So sánh với các mô hình khác .........................................................................22
2.4. TỔNG KẾT CHƯƠNG....................................................................................................... 23
Chương 3. THUẬT TOÁN GÁN NHÃN VÀ ƯỚC LƯỢNG THAM SỐ CỦA MÔ
HÌNH CRF VÀ CÔNG CỤ CRF ++..............................................................................24
3.1. THUẬT TOÁN GÁN NHÃN CHO DỮ LIỆU DẠNG CHUỖI......................................... 24
v
3.2. XÁC SUẤT CRF ĐƯỢC TÍNH NHƯ MỘT MA TRẬN.................................................. 25
3.3. ƯỚC LƯỢNG THAM SỐ CHO MÔ HÌNH CRF............................................................ 26
3.3.1. Thuật toán S..................................................................................................28
3.3.2. Thuật toán T .................................................................................................29
3.4. CÔNG CỤ CRF++ TOOLKIT............................................................................................ 30
3.4.1. Giới thiệu.......................................................................................................30
3.4.2. Tính năng.......................................................................................................31
3.4.3. Cài đặt và cách sử dụng.................................................................................31
3.4.3.1 Cài đặt.......................................................................................................31
3.4.3.2. File định dạng huấn luyện và test ................................................................ 31
3.4.3.3. Template type................................................................................................. 32
3.4.4. Huấn luyện và kiểm tra...................................................................................34
3.5. TỔNG KẾT CHƯƠNG....................................................................................................... 36
Chương 4. ỨNG DỤNG CRF VÀO BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ
ĐẤT....................................................................................................................................37
4.1. MÔ HÌNH HÓA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT ........................... 37
4.1.1. Xử lý dữ liệu đầu vào .....................................................................................38
4.2. MÔI TRƯỜNG THỰC NGHIỆM ...................................................................................... 39
4.2.1. Phần cứng ......................................................................................................39
4.2.2. Phần Mềm......................................................................................................39
4.2.3. Dữ liệu thực nghiệm......................................................................................39
4.2.3.1. Lần thử nghiệm thứ nhất ................................................................................... 40
4.2.3.2. Lần thử nghiệm thứ hai ..................................................................................... 40
4.2.3.3. Kết quả và đánh giá ........................................................................................... 42
4.3. HẠN CHẾ VÀ HƯỚNG ĐI CHO TƯƠNG LAI................................................................ 44
4.4. TỔNG KẾT CHƯƠNG....................................................................................................... 45
KẾT LUẬN .......................................................................................................................46
TÀI LIỆU THAM KHẢO................................................................................................47
vi
DANH MỤC CÁC HÌNH VẼ
Hình 1. Một hệ thống trích chọn thông tin..........................................................................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
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
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
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
Hình 12. Tỷ lệ lỗi của CRF so với các mô hình học máy khác..........................................23
Hình 13. Mô hình hoạt động của CRF++...........................................................................31
Hình 14. Mô hình xử lý dữ liệu của bài toán trích chọn nhà đất........................................38
Hình 15. Biểu đồ thể hiện sự tương quan giữa hai lần kiểm tra.........................................44
vii
BẢNG CÁC KÍ HIỆU VIẾT TẮT
STT
Kí hiệu
IE
Chú giải cho kí hiệu sử dụng
Trích chọn thông tin
1
2
3
4
5
HMM
MEMM
CRF
Mô hình Markov ẩn
Mô hình cực đại hóa Entropy
Trường ngẫu nhiên có điều kiện
Tìm kiếm thông tin
IR
viii
LỜI MỞ ĐẦU
Trong thời đại bùng nổ công nghệ thông tin như hiện nay thì việc ứng dụng công
nghệ thông tin trong các lĩnh vực của đời sống ngày càng đa dạng và phong phú. Toàn
bộ các ứng dụng đều thực hiện trên các thông tin đầu vào từ dạng đơn giản đến phức
tạp. Từ dạng văn bản dạng ký tự thông thường cho đến những thông tin đầu vào phức
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
1
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.
¾
Chương 2: Conditional Random Fields: Chương này giới thiệu một số
mô hình học máy như HMM, MEMM và tập trung vào mô hình
Conditional Random Field – CRF. Đưa ra được khái niệm trường ngẫu
nhiên, trường ngẫu nhiên có điều kiện. Đồng thời cũng chỉ ra được rằng
mô hình CRF hiệu quả hơn so với các mô hình học máy khác.
¾ Chương 3: Thuật toán gán nhãn và ước lượng tham số cho mô hình
CRF và công cụ CRF++: Chương này đưa ra hai vấn đề cơ bản của mô
hình CRF và hướng giải quyết hiệu quả nhất. Ở đây thuật toán gán nhãn sử
dụng thuật toán Viterbi một thuật toán trong quy hoạch động. Và hai thuật
toán T và thuật toán S giải quyết vấn đề ước lượng tham số cho mô hình
CRF. Đồng thời cũng giới thiệu được công cụ CRF++ toolkit, một công cụ
cài đặt mô hình CRF được sử dụng trong bài toán trích chọn thông tin nhà
đất.
¾ Chương 4: Ứng dụng CRF vào bài toán trích chọn thông tin nhà đất:
Chương này nói về việc ứng dụng của mô hình CRF đã nói ở các chương
trước vào bài toán trích chọn thông tin nhà đất. Một hướng đi mới trong
bài toán xử lý ngôn ngữ tự nhiên.
2
Chương 1.
TỔNG QUAN
Chủ đề chính của khóa luận là tìm hiểu mô hình Conditional Random Field và
ứng dụng trong trích chọn thông tin trong tiếng Việt. Chương này sẽ giới thiệu tổng
quan về trích chọn thông tin và các hướng tiếp cận trích chọn thông tin. Đồng thời
cũng nêu được ý nghĩa của việc trích chọn thông tin trong tiếng Việt.
1.1. TRÍCH CHỌN THÔNG TIN
Khi tìm kiếm một thư mục có chứa rất nhiều thư mục con hoặc rất nhiều file với
nhiều định dạng khác nhau. Thực chất là chúng ta đang làm việc với các ký tự [10]
[11]. Do vậy có rất nhiều hướng để xử lý như:
¾ Lọc, đếm từ: Tập tin như một chuỗi các ký tự ASCII. Ví dụ trong Linux có thể
tìm kiếm file hoặc các ký tự bằng lệnh grep với điều kiện là đưa ra một chuỗi
mô ta cho nó.
¾ 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.
3
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.
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.
Microsoft Corporation
CEO
Bill Gates
*
Microsoft
Gates
Microsoft
Bill Veghte
Microsoft
*
*
*
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
Windows operating system--to select
customers.
VP
Richard Stallman
founder
Free Software Foundation
"We can be open source. We love the concept
of shared source," said Bill Veghte, a
Microsoft VP. "That's a super-important shift
for us in terms of code access.“
Richard Stallman, founder of the Free
Software Foundation, countered saying…
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.
4
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ệ
thống luật được xây dựng bằng tay hoàn toàn phụ thuộc vào kinh nghiệm riêng của
từng người trong từng lĩnh vực của IE, các mẫu hay các luật được tạo ra và được kiểm
duyệt một cách kỹ lưỡng có quy mô bởi các “knowlegde engineer” [10]. Những quy
tắc luôn được kiểm định nhiều lần. Có thể mô hình hóa việc xây dựng này theo hình 2
như sau:
Kiểm duyệt
Sửa chữa
Kho tài
liệu
Luật cũ
knowlegde
engineer
Cập nhật
Luật mới
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
Với cách tiếp cận này thì hệ thống hoạt động theo một chu trình. Để xây dựng
một hệ thống hoạt động tốt phải luôn luôn có sự tương tác giữa người viết luật và hệ
thống cùng với kho ngữ liệu huấn luyện (hình 2) và tập luật luôn luôn được cập nhật
để cho hệ thống có thể hoạt động tốt nhất.
1.2.2. Hướng tiếp cận xây dựng các mô hình học máy
Với hệ thống IE được xây dựng theo hướng tiếp cận dựa trên tri thức thì chu
trình kiểm tra và sửa lỗi gặp rất nhiều khó khăn và phụ thuộc vào nhiều yếu tố như:
Loại ngôn ngữ, thời gian và khả năng viết luật. Chỉ một vài thay đổi trong đặc tả cũng
gây khó khăn trong sự điều chỉnh.
Câu trả lời cho các giới hạn này là phải xây dựng một mô hình bằng cách nào đó
có thể “tự học”. Điều này sẽ giúp làm giảm bớt sự tham gia của các chuyên gia ngôn
ngữ và làm tăng tính linh hoạt cho hệ thống. Có rất nhiều phương pháp học máy như
mô hình markov ẩn (Hidden Markov Models-HMM), các mô hình Markov cực đại hóa
Entropy (Maximum Markov Models – MEMM) và mô hình các trường ngẫu nhiên có
5
điều kiện ( Conditional Random Fields – CRF)… Các mô hình này sẽ được đề cập chi
tiết trong chương sau.
Các đặc điểm phải kể đến của việc xây dựng hệ thống IE theo hướng hệ thống có
thể tự đào tạo (automatic training approach) là không cần một người nào đó hiểu biết
về cách hoạt động của hệ thống IE và viết luật cho nó như thế nào [10]. Điều cần thiết
ở đây là một người nào đó biết được miền ứng dụng của nó và hiểu được những thông
tin 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.
Thuật toán học
Dữ liệu
Huấn
luyện
Model
file
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.
6
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:
Phân đoạn từ
Phân tích từ tố
Gán nhãn từ loại
Xử lý hình thái, và
từ vựng
Phân tích cú pháp
hoàn chỉnh
Phân tích cú pháp
Đồng tham chiếu
Trộn các kết quả
Phân tích miền
Hình 4. Modules chính của hệ thống IE
Với mô hình trên thì tùy thuộc vào từng ngôn ngữ mà có các bài toán cụ thể và
có những phương pháp xử lý cho phù hợp. Với rất nhiều ngôn ngữ đa dạng do vậy hệ
thống từ tố của mỗi quốc gia sẽ khác nhau: Ví dụ như ngôn ngữ Trung Quốc và Nhật
Bản khác hẳn so với chuẩn ngôn ngữ European. Nhưng chúng ta quan tâm là đối với
tiếng Việt thì có những khó khăn gì trong quá trình xử lý. Về mặt ngữ pháp và ngữ
nghĩa gặp rất nhiều khó khăn. Vì các công cụ để xử lý trong các bước trên là hầu như
chưa có sẵn, hơn nữa đối với tiếng Việt là một ngôn ngữ đơn âm và đa âm phức tạp do
vậy việc xử lý cũng gặp khó khăn.
7
1.4. BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT
Các bài toán điển hình trong xử lý tiếng Việt đó là: nhận biết các loại thực thể,
phân nhóm các cụm từ tiếng Việt, phân loại văn bản tiếng Việt. Đây là những bài toán
cơ bản nhưng đóng vai trò quan trọng để giúp xử lý các bài toàn phức tạp trong lĩnh
vực này. Trong luận văn này trình bày bài toán trích chọn thông tin nhà đất.
Ở đâ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:
9 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ỉ
9 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
9 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
8
9 DD:Di động trong đó B-DD là từ bắt đầu của số di động và I-DD là các từ
tiếp theo của số di động
9 LN: loại nhà có thể là chung cư hoặc căn hộ, trong đó B-LN là từ bắt đầu
loại nhà, I-LN là từ tiếp theo của loại nhà.
Cũng như các bài toán trích chọn khác như: trích chọn thực thể, nhận dạng tên,
trích chọn thông tin nhà đất cũng có các hướng tiếp cận khác nhau, trong luận văn này
tập trung vào bài toán trích chọn thông tin nhà đất theo phương pháp học máy bằng
cách sử dụng mô hình CRF. Một mô hình được đánh giá là có chất lượng cao đối với
bài toán trích chọn thông tin.
1.5. Ý NGHĨA CỦA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT
Trong bất cứ một ngôn ngữ nào thì việc thì việc tìm ra những thông tin liên quan
là điều rất quan trọng mà không cần phải đọc hiểu toàn bộ văn bản. Chính vì vậy việc
trích chọn thông tin có một nghĩa rất lớn trong việc xử lý ngôn ngữ tự nhiên.
¾ Tiết kiệm thời gian. Như chúng ta đã biết thì mỗi một bản tin đăng trên những
website khác nhau thì có những định dạng rất khác nhau: Có thể là định dạng
văn bản thông thường, cũng có thể là dạng bảng biểu, hoặc các đường liên
kết… Với những cách thể hiện văn bản như vậy thì việc tìm ra những thông tin
như diện tích của ngôi nhà, địa chỉ… Là một việc tương đối khó khăn. Với bài
toán trích chọn thông tin nhà đất thì sẽ tiết kiệm thời gian rất nhiều cho người
bán và người mua.
¾ Có thể tìm kiếm thông tin chính xác hơn rất nhiều. Vấn đề ở đây là trong một
bản tin có sự nhập nhằng giữa thông tin địa chỉ của mảnh đất và địa chỉ của
người chủ. Việc trích chọn có thể giảm bớt sự nhập nhằng trong thông tin này.
Nói rộng hơn nữa bài toán trích chọn thông tin nhà đất chỉ là bài toán nhỏ. Từ bài
toán này ta cũng thấy được ý nghĩa của việc trích chọn thông tin trong tiếng Việt.
¾ Giúp cho việc tóm tắt văn bản chính xác nếu như chủ đề của văn bản được chỉ
rõ
¾ Tự tạo ra các trường liên quan một cách tự động trong cơ sở dữ liệu được lấy
từ văn bản.
¾ Một số ứng dụng điển hình của trích chọn thông tin: sử dụng trích chọn thông
tin trong thư viện số- DL (Digital Libraries) - thư viện số có thể hiểu là các văn
9
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ệ
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.
10
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] [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.
r
¾ Chữ đậm x ví dụ: x = (x1,...,xn), 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.
¾ xi , yi biểu diễn các thành phần trong một vector.
¾ chữ viết thường x, y, z…. là ký hiệu cho một giá trị đơn như một
dữ liệu quan sát hay một trạng thái.
¾ S là tập các hữu hạn trạng thái.
¾ O là tập dữ liệu quan sát được.
2.1. MÔ HÌNH MARKOV ẨN- HMM
Mô hình Markov được giới thiệu vào cuối những năm 1960 [12]. Cho đến hiện
nay nó có một ứng dụng khá rộng như trong nhận dạng giọng nói, tính toán sinh học
(Computational Biology ), và xử lý ngôn ngữ tự nhiên.
HMM là mô hình máy hữu hạn trạng thái với các tham số biểu diễn xác suất
chuyển trạng thái và xác suất sinh dữ liệu quan sát tại mỗi trạng thái.
Mô hình Markov ẩn là mô hình thống kê trong đó hệ thống được mô hình hóa
được cho là một quá trình Markov với các tham số không biết trước, nhiệm vụ là xác
định các tham số ẩn từ các tham số quan sát được. Các tham số của mô hình được rút
ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Trong bài toán trích chọn
thông tin nhà đất thì các tham số quan sát được đó chính là các từ trong câu, còn các
trạng thái chính là các nhãn B-DC, I-DC, B-DT, I-DT..
11
Trong một mô hình Markov điển hình, trạng thái được quan sát trực tiếp bởi
người quan sát [21], và vì vậy các xác suất chuyển tiếp trạng thái là các tham số duy
nhất (hình 5 có thể mô tả rõ cho điều này).
Hình 5. HMM
- xi — Các trạng thái trong mô hình Markov
- aij — Các xác suất chuyển tiếp
- bij — Các xác suất đầu ra
- yi — 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.
P(Y | X ) = P(Y | X )/ P(X )
(2.1)
Y1
X1
Y2
X2
…
…
…
…
…
…
Yn
Xn
Hình 6. Đồ thị vô hướng HMM
Ở đó Yn là trạng thái tại thời điểm thứ t=n trong chuỗi trạng thái Y, Xn 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
P(Y, X ) = P(Y1 )P(X1 | Y1 ) P(Yt | Yt−1 )* P(Xt | Yt )
(2.2)
∏
t−2
12
Một số hạn chế của mô hình Markov để tính được xác suất P(Y,X) thông thường
ta phải liệt kê hết các trường hợp có thể của chuỗi Y và chuỗi X. Thực tế thì chuỗi Y là
hữu hạn có thể liệt kê được, còn X (các dữ liệu quan sát) là rất phong phú. Để giải
quyết các vấn đề này HMM đưa ra giả thiết về sự độc lập giữa các dữ liệu quan sát:
Dữ liệu quan sát được tại thời điểm t chỉ phụ thuộc vào trạng thái tại thời điểm đó.
Hạn chế thứ hai gặp phải là việc sử dụng xác suất đồng thời P(Y, X) đôi khi không
chính xác vì với một số bài toán thì việc sử dụng xác suất điều kiện P(Y | X) cho kết
quả tốt hơn rất nhiều.
2.2. MÔ HÌNH CỰC ĐẠI HÓA ENTROPY-MEMM
Mô hình MEMM [4] thay thế các xác suất chuyển trạng thái và các xác suất
sinh quan sát trong HMM bởi một hàm xác suất duy nhất P(Si | Si-1, Oi) (xác suất dịch
chuyển từ trạng thái hiện tại là Si-1 tới trạng thái trước đó là Si với dữ liệu quan sát
hiện tại là Oi) thay vì sử dụng P(Si | Si-1) và P(Oi | Si). 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.
S1
S2
…
…
…
Sn
S1:n
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
P(S | O) = P(S,O)*
P(St | St−1,Ot )
(2.3)
∏
t=1
MEMM coi dữ liệu quan sát là các điều kiện cho trước thay vì coi chúng là các
thành phần được sinh bởi mô hình như trong HMM vì thế xác suất chuyển trạng thái
có thể phụ thuộc vào các thuộc tính đa dạng của chuỗi dữ liệu quan sát.
13
Với mô hình này ta chia P(St | St−1,Ot ) thành các hàm dịch chuyển được huấn
luyện một cách riêng biệt trong |S| tập hợp trạng thái. Như
-
P (S |O ) =P(S | S ,O )
sau:
St−1
t
t
t
t−1
t
McCallum xác định phân phối cho xác suất chuyển trạng thái có dạng hàm mũ
sau:
1
⎛
⎜
⎞
⎟
PS (St | Ot ) =
exp
λ f (O , S )
(2.4)
∑
a
a
t
t
t −1
Z (Ot , St−1
)
a
⎝
⎠
Ở đây λa là các tham số cần được huấn luyện; Z(Ot, St) là thừa số chuẩn hóa để
tổng xác suất chuyển từ trạng St-1 sang St kề với nó đều bằng 1; fa(Ot, St) là hàm thuộc
tính tại vị trí thứ i trong chuỗi dữ liệu quan sát và trong chuỗi trạng thái. Ở đây ta định
nghĩa mỗi một thuộc tính fa có hai đối số: Dữ liệu quan sát hiện tại và trạng thái hiện
tại. McCallum cũng đinh nghĩa a=<b, St> trong đó b chỉ phụ thuộc vào dữ liệu quan sát
hiện tại.
1 nếu dữ liệu quan sát hiện tại là “1tỷ”
b(Ot)=
0 nếu ngược lại
Hàm thuộc tính fa xác định nếu b(Ot) nhận một giá trị xác định:
1 nếu b(Ot)=1 và St=St-1
f<b,St>(Ot,St)=
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
14
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).
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
đến khi gặp một quan sát xác định ( Discriminating Observation ). Nhưng đối với máy
hữu hạn trạng thái thì điều này không thể vì xảy ra sự bùng nổ tổ hợp. giải pháp thứ
hai là ta có thể luôn thay đổi cấu trúc trạng thái của mô hình điều này có nghĩa xác suất
của toàn bộ chuỗi trạng thái sẽ không được bảo tồn mà có thể bị thay đổi trong một vài
bước chuyển tùy thuộc vào quan sát đó.
Trên đây là những vấn đề hạn chế của HMM và MEMM từ đó cho thấy nhu cầu
cần thiết của mô hình CRF có thể giải quyết những hạn chế trên.
2.3. MÔ HÌNH CONDITIONAL RANDOM FIELDS
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, 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”.
2.3.1. Việc gán nhãn cho dữ liệu tuần tự
Nhiệm vụ của gán nhãn tuần tự [13] để thiết lập chuỗi quan sát được xuất hiện
trong nhiều trường. Một trong những phương thức phổ biến để thực hiện gán nhãn và
15
phân đoạn là sử dụng quy tắc HMM hoặc mô hình máy hữu hạn trạng thái để định
nghĩa chuỗi các nhãn có thể xảy ra nhất cho những từ của bất cứ câu nào.
Theo những nghiên cứu về mô hình Markov ẩn và mô hình cực đại hóa Entropy
ở trên. Thì CRF đã giải quyết được toàn bộ những vấn đề mà hai mô hình trên mắc
phải như “ label alias ”[11].
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 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 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…
Trong bài toán trích chọn thông tin nhà đất của mình thì dữ liệu tuần tự ở đây
chính là các bản tin nhà đất, còn các nhãn cần gán đó là các thông tin về địa chỉ (B-
DC, I-DC) hoặc diện tích (B-DT,I-DT)…
2.3.2. Định nghĩa CRF
Trước khi xem định nghĩa trường ngẫu nhiên điều kiện ta xem định nghĩa thế nào
là một trường ngẫu nhiên [9]
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 | v ,v ≠ v ) = P(v | v ,v ≈ v ) thì V gọi là trường ngẫu nhiên
(2.5)
Υ
Υ
i
j
i
j
i
k
k
i
16
Y1
Y4
Y2
Y3
Y5
Y6
Hình 9. Một trường ngẫu nhiên
P(Y5| Υ Yi)=P(Y5|Y4,Y6) . Vậy Y={Y5, Y4,Y6} là trường ngẫu nhiên.
Tiếp đến chúng ta định nghĩa trường ngẫu nhiên có điều kiện 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 Yi 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 phần của
biến ngẫu nhiên Y sao cho tồn tại ánh xạ một – một giữa các đỉnh và một thành phần Yv
của Y. Ta nói:
CRF được định nghĩa: (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(Yi | Xi) với
Yi ⊂Y và Xi ⊂ X và với mỗi Xi ta chọn được argmaxYiP(Yi | Xi).
Trong bài toán dữ liệu dạng chuỗi, G có thể được biểu diễn như sau:
G = ( V={1,2,3,…m}, E={i,i+1}i=1…m-1).
Kí hiệu X=(X1, X2…Xn), Y=(Y1, Y2,…Yn). Ta có mô hình đồ thị vô hướng của CRF
có dạng sau:
Hình 10. Đồ thị vô hướng mô tả cho CRF
17
Gọi C là tập hợp tất cả các đồ thị con đầy đủ của đồ thị G (đồ thị biểu diễn cấu
trúc của một CRF). Theo kết quả của Hammerly-Clifford cho các trường Markov, ta
thừa số hóa được p(y | x) – xác suất của chuỗi nhãn với điều kiện biết chuỗi dữ liệu
quan sát – thành tích các hàm tiềm năng:
P(y|x)=
ψ
( A | x )
(2.6)
∏
A
A ∈ C
Có thể mô phỏng như hình sau:
Yt+3
Yt+1
Y t
Yt+2
Ψ2
Ψ3
X1:n
Hình 11. Mô tả các hàm tiềm năng
Tính chất của trường ngẫu nhiên có điệu kiện là:
¾ 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)
2.3.3. Nguyên lý cực đại hóa Entropy
Laferty xác định các hàm tiềm năng cho các mô hình CRF dựa trên nguyên lý
cực đại hóa Entropy [7]. Nguyên lý này cho phép đánh giá các phân phối xác suất từ
một tập các dữ liệu huấn luyện.
2.3.3.1. Độ đo Entropy điều kiện
Entropy là độ đo tính đồng đều hay tính không chắc chắn của một phân phối xác
suất [7]. Độ đo Entropy điều kiện của một phân phối mô hình trên “một chuỗi trạng
thái với điều kiện biết chuỗi dữ liệu quan sát ” p(y | x) có dạng sau:
H(y | x) = -
p(x, y)*log p(y | x)
(2.7)
∑
x,y
= -
p^(x)*p(y | x)*log p(y | x)
∑
x,y
18
2.3.3.2. Các ràng buộc đối với phân phối mô hình
Vấn đề chính là phải tìm ra chuỗi p*(y|x) sao cho thỏa mãn hàm mục tiêu sau:
p* (y|x) = argmaxH(y|x)
(2.8)
Các ràng buộc đối với mô hình được thiết lập bằng cách thống kê các thuộc tính
được rút ra từ tập dữ liệu huấn luyện. Ví dụ về một thuộc tính
1 nếu y=name, x=Mister
fi(x,y)=
0 nếu ngược lại
Tập các thuộc tính là tập hợp các thông tin quan trọng trong dữ liệu huấn luyện.
Ký hiệu kì vọng của thuộc tính f theo phân phối xác suất thực nghiệm :
ˆ
ˆ
E[ f ] =
(2.9)
p(x,y) f i(x,y)
∑
x,y
Ở đây p^(x,y) là phân phối thực nghiệm trong dữ liệu huấn luyện. Dữ liệu huấn
luyện gồm N cặp, mỗi cặp gồm một chuỗi dữ liệu quan sát và một chuỗi nhãn
D={(xi,yi)}, khi đó phân phối thực nghiệm trong dữ liệu huấn luyện được tính như sau:
ˆ
p(x, y)= 1/N * số lần xuất hiện đồng thời của x,y trong tập huấn luyện
Kỳ vọng của thuộc tính f theo phân phối xác suất trong mô hình
Ep[f] =
(2.10)
p(x) *p(y|x)*f (x,y)
∑
i
x,y
Phân phối mô hình thống nhất với phân phối thực nghiệm chỉ khi kỳ vọng của
mọi thuộc tính theo phân phối xác suất phải xấp xỉ bằng kì vọng của thuộc tính đó theo
phân phối mô hình :
Epˆ (x,y)[ f ] = Ep [ f ]
(2.11)
Từ công thức (2.11) có thể thấy rõ các ràng buộc của mô hình.
19
2.3.3.3. Nguyên lý cực đại hóa Entropy
Gọi P là không gian của tất cả các phân phối xác suất điều kiện, và n là số các
thuộc tính rút ra từ dữ liệu huấn luyện. P’ là tập con của P, P’ được xác định như sau:
P’={ p∈ P | Epˆ [ f ] = Ep [ f ] ∀i ∈{1,2,3...n}}
(2.12)
Tư tưởng chính của nguyên lý cực đại hóa Entropy là ta phải xác định một phân
phối mô hình sao cho: phân phối mô hình phải thỏa mãn mọi ràng buộc được rút ra từ
thực nghiệm, và phải gần nhất với phân phối đều. Có nghĩa là ta phải tìm phân phối
mô hình p( y | x ) thỏa mãn hai điều kiện thứ nhất phải thuộc tập P’ thứ hai là nó phải
làm cực đại hóa Entropy điều kiện (2.7)
Hay nói cách khác khi E ˆ [ f ] = E [ f ] và p(y | x)≥0 ∀x, y và p(y | x) = 1∀x ta
∑
p
p
y∈Y
sẽ có (2.7)
Với mỗi một thuộc tính fi ta đưa vào một thừa số langrange λi, ta định nghĩa hàm
Lagrange L(p, λ) như sau:
λ * Eˆ [f ] - E [f ]
L(p, λ) = H(p)+
(2.13)
∑
i
p
i
p
i
i
Phân phối p(y | x) làm cực đại hóa độ đo Entropy H(p) và thỏa mãn n ràng buộc
(2.11) cũng sẽ làm cực đại hàm L(p, λ). Từ (2.13) suy ra
1
P(y | x) =
exp( λ f )
(2.14)
∑
i
i
Z
λ(x)
i
Ở đây Zλ(x) là thừa số chuẩn hóa để đảm bảo
p(y | x) =1 với mọi x:
∑
y
⎛
⎞
⎟
Zλ(x)= exp
λ f
(2.15)
⎜
∑ ∑
i
i
y
i
⎝
⎠
2.3.4. Hàm tiềm năng của các mô hình CRF
Bằng cách áp dụng nguyên lý cực đại hóa Entropy, Lafferty xác định hàm tiềm
năng của một CRF có dạng hàm số mũ.
yκ fκ ( A | x )
Ψ (A|x)=exp
A
(2.16)
∑
k
Trong đó:
fk là một thuộc tính của chuỗi dữ liệu quan sát
20
yk là trọng số chỉ mức độ biểu đạt thông tin của thuộc tính fk
A là đồ thị con của đồ thị vô hướng G
2.3.5. Conditional Random Fields
Mô hình CRFs cho phép các quan sát trên toàn bộ X, nhờ đó chúng ta có thể sử
dụng nhiều thuộc tính hơn phương pháp Hidden Markov Model. Một cách hình thức
chúng ta có thể xác định được quan hệ giữa một dãy các nhãn y và một câu đầu vào x
qua công thức sau.
1
⎛
⎜
⎞
⎟
P(y | x) =
exp
λ t (y , y , x) +
μ s (y , x)
(2.17)
∑∑
∑∑
k
k
i−1
i
k
k
i
Z(x)
t
k
t
k
⎝
⎠
Ở đây x,y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; tk(yi-1,yi,x,i): là
thuộc tính của toàn bộ chuỗi quan sát và các trạng thái tại vị trí i-1, i trong chuỗi trạng
thái; sk(yi,x,i): là thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại vị trí i trong
chuỗi trạng thái; λj, μk: là các tham số được thiết lập từ dữ liệu huấn luyện.
Khi định nghĩa các thuộc tính , chúng ta xây dựng 1 chuỗi các thuộc tính b(x,i)
của chuỗi dữ liệu quan sát để diễn tả vài đặc trưng nào đó của phân phối thực nghiệm
của dữ liệu huấn luyện.
Ví dụ :
1 nếu quan sát ở vị trí i và từ là = “Đình”
b(x,i) =
0 nếu khác
Mỗi một hàm mô tả sẽ nhận một giá trị của một trong số các giá trị thực b(x,i)
là trạng thái hiện tại( nếu trong trường hợp hàm trạng thái ) hoặc là trạng thái trước và
trạng thái hiện tại (trong trường hợp là hàm dịch chuyển) nhận giá trị riêng. Do đó toàn
bộ hàm mô tả có giá trị thực.
Hàm trạng thái sk(yi,x,i) dùng để xác định định danh của trạng thái
Trong bài toán trích chọn thông tin nhà đất thì ví dụ một hàm trạng thái như sau:
1 nếu xi= “chuỗi các số” và yi =B-DD
si =
0 nếu ngược lại
Hàm dịch chuyển giúp thêm vào mối quan hệ giữa một nhãn và các nhãn liền kệ
với nó.
21
1 nếu xi-1= “Mỹ”, xi= “ Đình” và yi-1=B_DC, yi=I_DC
0 nếu ngược lại.
ti=
Ở đó Z(x) là thừa số chuẩn hóa. Và được tính theo công thức sau:
⎛
⎞
exp
λ t
(
y , yi, x) +
μ s ( y , x)
⎜
⎟
⎠
Z(x)=
(2.18)
∑ ∑ ∑
∑ ∑
k
k
i−1
k
k
i
y
⎝
t
k
i
k
θ(λ1 ,λ2…..,μ1, μ2) là các véctơ tham số của mô hình . θ sẽ được ước lượng giá trị
trong phần tiếp theo.
Chú ý rằng đối với các công thức (2.17) và (2.18) ta có thể viết một cách đơn
giản như sau:
n
sk(yi,x,i)= sk(yi-1, yi,x,i) và Fj(y,x)=
fi(y , y , x,i) .
i−1
∑
i
i=1
Ở đó fj(yi-1,yi,x,i) là hàm trạng thái sk(yi-1, yi,x,i) hoặc hàm dich chuyển tk(yi-1,
yi,x,i). Điều này cho ta tính được xác suất của nhãn y khi biết chuỗi quan sát x:
1
P(y|x,λ) =
exp( λ F (y, x) )
(2.19)
∑
j
j
Z(x)
j
2.3.6. So sánh với các mô hình khác
Bản chất của phân phối toàn cục của CRF giúp cho các mô hình này tránh được
vấn đề label alias .
Qua quá trình thực nghiệm cho thấy tỉ lệ lỗi của CRF là thấp hơn cả so với
MEMM và HMM
Với 2000 mẫu dữ liệu huấn luyện và 500 mẫu test kết quả là tỷ lệ lỗi của CRF là
4.6%, của MEMM tỷ lệ lỗi là 42% [14].
22
Tải về để xem bản đầy đủ
56 trang
29/04/2025
120
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_tim_hieu_mo_hinh_crf_va_ung_dung_trong_trich_chon.pdf
