HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Hoàng Quỳnh
SO SÁNH MỘT SỐ PHƯƠNG PHÁP HỌC MÁY
CHO BÀI TOÁN GÁN NHÃN TỪ LOẠI
TIẾNG VIỆT
bồi d
ưỡng kiến thức cho tôi trong bốn năm qua, tôi xin gửi lời cảm ơn chân thành đến
các thầy cô, những kiến thức mà tôi nhận được không chỉ giúp tôi hoàn thành khóa
luận này mà còn là hành trang quan trọng giúp tôi vững bước trong tương lai.
Tôi cũng xin gửi lời cảm ơn tới các thầy cô, các anh chị và các bạn sinh viên
trong nhóm seminar “Khai phá dữ liệu”, phòng thí nghiệm Các hệ thống tích hợp
thông minh (SISLAB) – trường Đại học Công nghệ đã tạo một môi trường nghiên cứu
khoa học hi
ệu quả cũng như cho tôi những lời khuyên bổ ích về chuyên môn trong quá
trình nghiên cứu.
Bên cạnh đó, tập thể sinh viên lớp K50CA cũng đóng một vai trò không nhỏ giúp
tôi xây dựng, củng cố kiến thức và cùng với tôi vượt qua những khó khăn trong học
tập.
Và cuối cùng, nhưng vô cùng quan trọng, tôi xin bày tỏ lòng chân thành và biết
ơn vô hạn tới cha mẹ, anh chị cũng như các bạn bè thân thiết đã luôn ở bên cạnh, quan
tâm, động viên tôi trong suố
t quá trình học tập và thực hiện khóa luận tốt nghiệp này.
Sinh viên
Lê Hoàng Quỳnh
ii
TÓM TẮT
Gán nhãn từ loại (Part-of-Speech Tagging) là một trong hai bài toán nền tảng,
đóng vai trò quan trọng trong các hệ thống xử lý ngôn ngữ tự nhiên. Ở Việt Nam đã có
một số nghiên cứu về bài toán này, tuy nhiên kết quả đạt được vẫn còn ở mức khiêm
tốn so với nhiều ngôn ngữ khác. Việc tìm hiểu các phương pháp gán nhãn từ loại trong
tiếng Anh cho thấy hướng tiếp cận dựa theo phương pháp học máy cho kết quả tốt hơn
cả trong các ph
ương pháp đã được công bố.
Nội dung khóa luận tập trung so sánh ba phương pháp học máy cho bài toán gán
Chương 2. CÁC HƯỚNG TIẾP CẬN BÀI TOÁN GÁN NHÃN TỪ LOẠI 13
2.1. Gán nhãn bằng phương pháp dựa trên hệ luật 13
2.2. Các phương pháp dựa vào học máy 15
2.3. Phương pháp lai 19
2.4. Các nghiên cứu liên quan tại Việt Nam 21
2.4.1. Các nghiên cứu dựa trên phương pháp hệ luật 21
2.4.2. Các nghiên cứu dựa trên phương pháp học máy 22
2.4.3. Các nghiên cứu dựa trên phương pháp lai 22
Chương 3. BA MÔ HÌNH HỌC MÁY ÁP DỤNG CHO BÀI TOÁN GÁN NHÃN
TỪ LOẠI TIẾNG VIỆ
T 25
3.1. Mô hình cực đại hóa Entropy 25
3.1.1. Khái niệm MEM 25
3.1.2. Nguyên lý cực đại hóa Entropy 26
3.1.3. Mô hình xác suất 26
3.1.4. Hạn chế của mô hình MEM 27
3.2. Mô hình trường ngẫu nhiên điều kiện 28
3.2.1. Khái niệm CRF 28
iv
3.2.2. Hàm tiềm năng của các mô hình CRF 30
3.2.3. Thuật toán gán nhãn cho dữ liệu dạng chuỗi 31
3.2.4. Ước lượng tham số cho các mô hình CRF 33
3.3. Mô hình máy véc tơ hỗ trợ 33
3.3.1. Khái niệm và cơ sở của phương pháp SVM 33
3.3.2. Áp dụng phương pháp SVM cho bài toán gán nhãn từ loại 36
3.3.3. Huấn luyện SVM 37
Chương 4. THỰC NGHIỆM ÁP DỤNG BA MÔ HÌNH HỌC MÁY CHO BÀI
TOÁN GÁN NHÃN TỪ LOẠI TIẾNG VIỆT VÀ ĐÁNH GIÁ KẾT QUẢ 39
4.1. Mô tả thực nghiệm 39
Hình 9. Hai cách chia không gian véc tơ thành hai nửa riêng biệt 33
Hình 10. Mặt siêu phẳng tách các mẫu dương khỏi các mẫu âm. 34
Hình 11. Trường hợ
p không thể phân chia các mẫu âm và các mẫu dương bằng
một siêu phẳng tuyến tính 35
Hình 12. Biến đổi siêu phẳng không tuyến tính thành siêu phẳng tuyến tính sử
dụng hàm nhân 35
Hình 13. Hàm nhân Basis Radial 37
Hình 14. Cửa sổ trượt với kích cỡ size=5 chuyển động dọc theo dữ liệu 44
Hình 15. Một mô hình gán nhãn từ loại tiếng Việt 46
Hình 16. Độ chính xác trung bình trong thực nghiệm với bộ dữ liệu thứ nhất 52
Hình 17. Độ chính xác trung bình trong thực nghiệm với bộ dữ liệ
u thứ hai 52 vi
Danh mục bảng biểu
Bảng 1. Một số thuật ngữ Anh – Việt được sử dụng trong khóa luận viii
Bảng 2. Tổng kêt số nhãn có thể có của các từ trong tập từ vựng Brown 7
Bảng 3. Tập nhãn từ loại Penn Treebank 8
Bảng 4. Ví dụ về một số luật chuyển của TBL cho tiếng Anh 20
Bảng 6. Tập nhãn từ loại VnPOS cho tiếng Việt 42
Bảng 7. Thông tin từ vựng và thông tin từ loại sử dụng cho việc lự
a chọn đặc
trưng 44
Bảng 8. Một số mẫu ngữ cảnh BTCQ xác định dữ liệu dạng số 45
Bảng 9. Độ chính xác khi áp dụng mô hình MEM ở mức từ 49
Bảng 10. Độ chính xác khi áp dụng mô hình MEM ở mức hình vị 49
Bảng 11. Độ chính xác khi áp dụng mô hình CRF ở mức từ 50
Bảng 12. Độ chính xác khi áp dụng mô hình CRF ở mức hình vị 50
các nghiên cứu về bài toán này ở Việt Nam vẫn còn ở giai đoạn ban đầu nên nhu cầu
về cả lý thuyết và ứng dụng đều còn r
ất lớn. Đối với các văn bản tiếng Việt, việc gán
nhãn từ loại gặp phải nhiều khó khăn, đặc biệt là bản thân việc phân loại từ tiếng Việt
cho đến nay vẫn là một vấn đề còn nhiều tranh cãi, chưa có một chuẩn mực thống
nhất. Ý thức được tầm quan trọng và nhu cầu thực tiễn cũng như những khó khăn của
bài toán gán nhãn từ loạ
i, nghiên cứu trong khóa luận phục vụ đồng thời hai mục đích:
Thứ nhất, lựa chọn một tập đặc trưng phù hợp với tính chất của tiếng Việt và có thể sử
dụng cho các phương pháp học máy khác nhau. Thứ hai, áp dụng ba phương pháp học
máy cho kết quả khá tốt ở các ngôn ngữ khác vào bài toán gán nhãn từ loại tiếng Việt,
từ đó đưa ra nhận xét về kết quả, độ phù h
ợp của từng phương pháp với các ứng dụng
thực tế cũng như góp phần đánh giá chất lượng của tập đặc trưng đã xây dựng.
Thực nghiệm trên các văn bản tiếng Việt áp dụng ba mô hình học máy đều cho
kết quả khá khả quan, tùy vào các đặc trưng riêng của mỗi mô hình mà thời gian xử lý
cũng như độ chính xác có những chênh lệch nhất định. Các vấn đề đượ
c giải quyết
trong khóa luận sẽ đóng góp một phần hữu ích trong việc lựa chọn phương pháp thích
hợp giải quyết bài toán, để từ đó phục vụ cho việc tiến hành các nghiên cứu ở mức cao
hơn như phân tích cú pháp, dịch máy, tóm tắt văn bản …
Khóa luận được tổ chức thành bốn chương chính với nội dung cơ bản như
sau:
Chương 1: Khái quát về bài toán gán nhãn từ loại. Chươ
ng 1 đưa ra khái
niệm, vị trí và ứng dụng của bài toán gán nhãn từ loại trong xử lý ngôn ngữ tự nhiên.
Cùng với đó, việc phân tích các vấn đề cơ bản của bài toán và việc xây dựng tập nhãn
từ loại cũng là nội dung quan trọng mà chương này đề cập tới.
Chương 2: Các hướng tiếp cận bài toán gán nhãn từ loại. Trình bày một số
hướng tiếp cận nhằm giải quyết bài toán gán nhãn từ loại nh
tích những khó khăn mà bài toán gán nhãn từ loại cần phải giải quyết và vấn đề xây
dựng tập nhãn từ loại.
1.1. Khái niệm và vị trí của bài toán gán nhãn từ loại trong xử lý
ngôn ngữ tự nhiên
1.1.1. Khái niệm về bài toán gán nhãn từ loại
Mỗi từ trong một ngôn ngữ nói chung đôi khi có thể gắn với nhiều từ loại và việc
giải thích đúng nghĩa một từ phụ thuộc vào việc nó có được xác định đúng từ loại hay
không dựa trên ngữ cảnh cho trước. Công việc gán nhãn từ loại cho một văn bản là
xác định từ loại của mỗi từ trong phạm vi văn bản đó, tức là phân loại các từ
thành các lớp từ loại dựa trên thực tiễn hoạt động ngôn ngữ [2, 7]. Việc gán nhãn
từ loại thường được thể hiện bằng cách gán cho mỗi từ một “nhãn” có sẵn theo tập
nhãn cho trước.
Bài toán có thể được mô tả như sau:
Input: Một chuỗi các từ và tập nhãn từ loại (Ví dụ như chuỗi các từ “Book that
flight.” và tập nhãn từ loại Penn Treebank của tiếng Anh.)
Output: Một nhãn tố
t nhất cho từng từ trong chuỗi từ đã được đưa ra (Ví dụ:,
đối với chuỗi từ “Book that flight.”, thì nhãn thích hợp tương ứng cho từng từ
sẽ là Book/VB that/DT flight/NN./.)
Quá trình gán nhãn từ loại thường được chia làm 3 bước [2, 3, 4]:
Giai đoạn tiền xử lý: Phân tách xâu ký tự thành chuỗi các từ. Giai đoạn này có
thể đơn giản hay phức tạp tuỳ theo ngôn ngữ và quan niệm về đơn vị từ vựng.
Chẳng hạn đối với tiếng Anh hay tiếng Pháp, việc phân tách từ phần lớn là dựa
vào các ký hiệu trắng. Tuy nhiên vẫn có những từ ghép hay những cụm từ gây
tranh cãi về cách xử lý. Trong khi đó với tiếng Việt thì dấu trắng càng không
phải là dấu hiệu để xác định ranh giới các đơn vị từ vựng do tần số xuất hiện từ
ghép rất cao.
4
Khởi tạo gán nhãn, tức là tìm cho mỗi từ tập tất cả các nhãn từ loại mà nó có Hình 1. Các bước xử lý ngôn ngữ tự nhiên
Morphology Syntax Semantics Discourse Pragmatics Knowledge
Bill was about to be impeached, and he called his lawyer
ADDITIVE or RESULT?
Could you pass me the salt? Yes or pass it?
Five man lif a piano / a chair?
Untieable Knot (un)tieable or untie(able)?
walks Noun or Verb?
rice flies (NP (NN rice) (NNS files)) or
(S (NP (NN rice) (VP (VBZ files)))
bank river or financial?
cottog bag PART-WHOLE or PURPOSE?
5
Gán nhãn từ loại là một công việc quan trọng và bắt buộc phải có đối với hầu hết
các ứng dụng xử lý ngôn ngữ tự nhiên. Nếu coi quá trình xử lý ngôn ngữ tự nhiên gồm
các bước: Tiền xử lý văn bản, phân tích hình thái, phân tích cú pháp và phân tích ngữ
nghĩa thì gán nhãn từ loại thuộc vào bước phân tích hình thái. Bước này có nhiệm vụ
phân tích câu thành một bảng các từ (hay cụm từ) riêng biệt, đồng thời kèm theo tất cả
các thông tin v
ề từ đó, như là: Từ loại (part-of-speech), phạm trù ngữ pháp (category),
các biến cách của từ, tiền tố, hậu tố của từ (nếu có) [5, 9]. Hình 1 ở trên cho ta mô tả
trực quan về vị trí của bài toán gán nhãn từ loại trong xử lý ngôn ngữ tự nhiên.
Như vậy, gán nhãn từ loại là bước tiền xử lý quan trọng cho các phần tiếp theo
trong quá trình xử lý ngôn ngữ tự nhiên như phân tích cú pháp, phân tích ngữ nghĩa.
Có thể điể
tiếng Việt là “Phản lực các phi cơ bay khoảng chín dặm cao”
Jet planes fly about nine miles high
Phản lực các phi cơ bay khoảng chín dặm cao
Trong khi đó, nếu các từ đã được gán nhãn từ loại một cách chính xác, ta sẽ có
khả năng cao nhận được một câu tiếng Việt hợp lý hơn rất nhiề
u: “Các phi cơ
phản lực bay cao khoảng chín dặm”
Jet planes fly about nine miles high Các phi cơ phản lực bay cao khoảng chín dặm
…
1.2. Các khó khăn của bài toán gán nhãn từ loại
Nếu mỗi từ chỉ có một nhãn từ loại và ta có thể xây dựng được một từ điển hữu
hạn các từ và nhãn tương ứng của nó thì chắc chắn có thể giải quyết được bài toán gán
nhãn từ loại với kết quả tối ưu. Tuy nhiên, trong thực tế một từ đôi khi có thể có nhiều
hơn một nhãn từ loại thích hợp, và ta cũng không thể kiểm soát đượ
c toàn bộ các từ có
thể xuất hiện trong văn bản, điều này dẫn đến hai vấn đề mà bài toán gán nhãn từ loại
phải đối mặt: Nhập nhằng từ loại và từ mới.
Vấn đề chủ yếu của bài toán gán nhãn từ loại thực chất là việc loại bỏ nhập
nhằng về từ loại, tức là khi một từ có nhiều từ loại, nhưng trong m
ột ngữ cảnh cụ thể,
nó chỉ có thể có một từ loại đúng mà thôi [5, 18].
Ví dụ:
Trong câu “I can can a can”, bộ gán nhãn từ loại sẽ phải đánh dấu từ loại
khái quát, theo khả năng kết hợp với các từ ngữ khác trong ngữ lưu và thực hiện
những chức năng ngữ pháp nhất định ở trong câu [1]. Trong thực tế, các tập nhãn sử
dụng cho việc gán nhãn từ loại thường được xây dựng và phát triển từ các lớp cơ bản
là các lớp từ đóng (Closed word class, function word class, còn được g
ọi là các từ
chức năng, là một tập cố định và không thể mở rộng, các lớp này thường chỉ chứa một
số lượng ít các từ có liên quan. Ví dụ: Giới từ, mạo từ, đại từ, số đếm, ) và các lớp từ
mở (Open class, là các lớp từ có khả năng mở rộng bằng cách tạo thêm từ mới hoặc
“mượn” từ các ngôn ngữ khác. Có 4 lớp từ mở chính là danh từ
- nouns, động từ -
verb, tính từ - adjective và một phần của phó từ - [adverb]). Thường thì một lớp từ sẽ
được chia thành nhiều từ loại theo các đặc tính riêng nào đó [21].
8
Chỉ xét riêng đối với Tiếng Anh, cho đến hiện nay đã có rất nhiều tập nhãn từ
loại khác nhau được xây dựng và sử dụng, hình 2 điểm qua một số tập nhãn từ loại đã
được xây dựng theo các mốc thời gian [7].
Hình 2. Một số tập nhãn từ loại cho Tiếng Anh
Có thể kể đến một số tập nhãn từ loại điển hình như:
Brown corpus: 87 nhãn.
Penn Treebank: 45 nhãn. Các nhãn của tập nhãn từ loại Penn Treebank được
cho trong bảng 3 dưới đây.
Lancaster UCREL C5 (Dùng để gán nhãn BNC – British National Corpus): 61
nhãn.
Lancaster C7: 145 nhãn.
Bảng 3. Tập nhãn từ loại Penn Treebank
Nhãn Ý nghĩa Nhãn Ý nghĩa
CC
CD
LOB Corplus
Created(EN-US)
1 Millions Words
Brown
Cor
p
lus
POS Tagging
separated from
other NLP
LOB Corplus
Ta
gg
ed
Penn Treebank
Corpus
(WSJ, 4.5M)
British National
Corpus
(tagged by CLAWS)
9
Nhãn Ý nghĩa Nhãn Ý nghĩa
JJR
JJS
LS
MD
NN
NNS
WP$
WRB
$
#
“
”
(
)
,
.
:
Verb, non-3rd person singular
present
Verb, 3rd person singular present
Wh-determiner
Wh-pronoun
Possessive wh-pronoun
Wh-adverb
Dollar sign
Pound sign
Left quote
Right quote
Left parenthesis
Right parenthesis
Comma
Sentence-final punc
Mid-sentence punc
Đối với các ngôn ngữ khác trên thế giới, để phục vụ cho việc giải quyết bài toán
gán nhãn từ loại, nhiều tập nhãn từ loại với độ mịn khác nhau cũng đã được xây dựng
Tiêu chuẩn 2 - Khả năng kết hợp với các từ ngữ khác trong ngữ lưu. V
ới ý
nghĩa khái quát, các từ có thể có khả năng tham gia vào một kết hợp có nghĩa.
Ở mỗi vị trí của kết hợp có thể xuất hiện những từ có khả năng lần lượt thay thế
nhau, trong khi đó, ở các vị trí khác nhau trong kết hợp, các từ còn lại tạo ra
bối cảnh cho sự xuất hiện khả năng thay thế của những từ nói trên. Những từ
cùng xuất hiệ
n trong cùng một bối cảnh, có khả năng thay thế nhau ở cùng một
vị trí, có tình chất thường xuyên, được tập hơn vào một lớp từ. Vận dụng vào
tiếng Việt, những từ; nhà, bàn, cát, đá … có thể xuất hiện và thay thế nhau
trong kết hợp kiểu: nhàn ày, bàn này, cát này, đá này … và được xếp vào lớp
danh từ. Chúng không thể xuất hiện và thay thế cho nhau trong kết hợp kiểu:
hãy ăn, hãy mua, ăn xong, mua xong … vốn là kiểu kế
t hợp của động từ.
Tiêu chuẩn 3 - Chức năng ngữ pháp. Tham gia vào cấu tạo câu, các từ có thể
đứng ở một hay một số vị trí nhất định trong câu, hoặc có thể thay thế nhau ở vị
trí đó, và cùng biểu thị một mối quan hệ về chức năng cú pháp với các thành
phần khác trong cấu tạo câu, có thể phân vào một từ loại. Ví dụ, các từ; nhà,
bàn, cát, đá … có thể đứng
ở nhiều vị trí trong câu. Chúng có thể thay thế nhau
ở những vị trí đó, và có quan hệ về chức năng giống nhau với các thành phần
khác trong câu ở mỗi vị trí, nhưng thường ở vị trí chủ ngữ trong quan hệ với vị
ngữ. Chủ ngữ và vị ngữ là hai chức năng cú pháp cơ bản, chức năng chủ ngữ là
chức năng cú pháp chủ yếu để phân loại các từ nói trên vào lớp danh t
ừ; còn
11
chức năng vị ngữ lại là chức năng cú pháp chủ yếu của các động từ và tính từ
…
Qua khảo sát các nghiên cứu gần đây của tiếng Việt cho bài toán gán nhãn từ loại
tập nhãn này được xây dựng bằng cách quy chiếu từ tập nhãn tiếng Anh là Brown
Corpus.
Hiện nay, bài toán gán nhãn từ loại cho tiếng Anh đã được giải quyết khá tốt, đạt
độ chính xác cao (Khoảng hơn 97% ), bên cạnh việc hoàn thiện hơn nữ
a các phương
12
pháp gán nhãn, việc xây dựng bộ nhãn mịn hơn và có khả năng ứng dụng thực tế cao
cũng đang rất được quan tâm. Có thể nói rằng kết quả đạt được của bài toán gán nhãn
từ loại cho tiếng Anh đã ngày càng tiến gần tới mức tối ưu. Tuy nhiên, đối với các
ngôn ngữ khác, đặc biệt là các ngôn ngữ tượng hình (như tiếng Trung Quốc, Nhật, Hàn
Quốc …), các ngôn ngữ của Nga, Ấn
Độ, A Rập, Thái Lan … cũng như đối với tiếng
Việt thì bài toán gán nhãn từ loại vẫn là một thách thức lớn. Các phương pháp và công
cụ đã được xây dựng gần như hoàn thiện cho Tiếng Anh khi đem áp dụng cho các
ngôn ngữ khác loại trên thường đưa lại kết quả thấp hoặc chưa đáp ứng được nhu cầu
ứng dụng. Như vậy, yêu cầu đặt ra với từng ngôn ngữ là phải k
ế thừa, tận dụng được
các phương pháp sẵn có, tiến hành hiệu chỉnh hoặc đề xuất ra các hướng tiếp cận mới
sao cho phù hợp với đặc điểm riêng của từng ngôn ngữ. 13
Chương 2. CÁC HƯỚNG TIẾP CẬN BÀI TOÁN GÁN
NHÃN TỪ LOẠI
Như đã giới thiệu, bài toán gán nhãn từ loại là một trong những bài toán cơ bản
trong xử lý ngôn ngữ tự nhiên và được quan tâm từ rất sớm, cùng với đó là sự xuất
hiện của rất nhiều phương pháp giải quyết bài toán này. Cho đến nay, việc hoàn thiện
các phương pháp đã có và xây dựng các phương pháp mới nhằm đạt được kết quả tốt
hơn vẫn là mục tiêu của nhiều nghiên cứu.
(CLAWS)
93% - 95%
Transformation
Based Tagging
(Eric Bill)
Rule Based
–
95
%
+
Tree-Based Statistics
(Helmut Shmid)
Rule Based – 96%+
Neural Network
96% +
14
cảnh chứa từ đang xét nhằm loại bỏ nhập nhằng nếu từ đó có thể có nhiều nhãn từ loại
thích hợp, ví dụ, nếu một từ nhập nhằng đang xét đi sau một từ chỉ định thì nó có xu
hướng là một danh từ hơn là một động từ.
Đại diện tiêu biểu cho nhóm các phương pháp thủ công dựa trên hệ luật này là
ENGTWOL (Voutilainen, 1995) [21].
Về thực chấ
t, phương pháp này dựa trên kỹ thuật hai bước dưới đây:
Bước 1: Xác định cho mỗi từ một danh sách các từ loại có khả năng của nó.
Đối với ENGTWOL, việc này được thực hiện mởi một bộ phân tích hình thái hai
mức độ (Máy chuyển hữu hạn trạng thái).
Ví dụ: Để gán nhãn từ loại cho câu “Pavlov had shown that salivation”, ở bước
này, bộ gán nhãn tạo một danh sách tất cả các nhãn có thể cho từng từ nh
ư sau:
ạn này là phải xây dựng một hệ thống bằng cách nào đó có thể “tự
học”, điều này sẽ giúp giảm bớt sự tham gia của các chuyên gia ngôn ngữ và làm tăng
tính khả chuyển cho hệ thống, các phương pháp như vậy được gọi là các phương pháp
dựa vào học máy.
Như đã nói ở trên, các phương pháp dựa vào học máy là các phương pháp xây
dựng hệ thống mà bằng cách nào đó có thể “tự học” (để
ngắn gọn ở các phần dưới đây
ta sẽ gọi là các phương pháp học máy). Phần này sẽ xem xét một đại diện tiêu biểu của
phương pháp học máy, giải quyết nhập nhằng bằng cách sử dụng một bộ dữ liệu huấn
luyện để tính toán xác suất của một từ cho sẵn sẽ được gán với một nhãn nào đó trong
ngữ cảnh cho trước, vì bản chất
đó, họ các phương pháp này còn được gọi là các
phương pháp xác suất.
Xác suất cho một từ, tức là xác suất mà một nhãn cho trước t là thích hợp với
một từ cho trước w được tính bằng công thức:
(2.0)
Để minh họa cho phương pháp xác suất, phần này sẽ giới thiệu một bộ gán nhãn
điển hình sử dụng mô hình Markov ẩn (HMM) [16]. Mô hình Markov ẩn được giới
thiệu và nghiên cứu vào cuối những năm 1960 và đầu nh
ững năm 1970, cho đến nay
nó được ứng dụng nhiều trong nhận dạng tiếng nói, tin sinh học và xử lý ngôn ngữ tự
nhiên. HMM lựa chọn một chuỗi nhãn tốt nhất cho toàn bộ câu, thông thường người ta
sử dụng thuật toán Viterbi để tìm chuỗi nhãn tốt nhất đó.
Mô hình HMM có thể được xây dựng bởi các ô-tô-mát hữu hạn trạng thái
(probabilistic finite state automata) 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. Các trạng thái trong mô hình
HMM được xem là bị ẩn đi bên dưới dữ liệu quan sát sinh ra do mô hình. Quá trình
(, )
t
n
). Bộ gán nhãn sử dụng mô hình HMM sẽ tìm chuỗi các nhãn sao cho giá trị của tích
P(Từ |nhãn) * P (nhãn | n nhãn trước đó) là cực đại, tức là thỏa mãn công thức (2.1)
(2.1)
Sử dụng luật Bayes, P(T|W) được viết theo công thức (2.2)
(2.2)
Ta đang quan tâm tới việc tìm chuỗi nhãn phù hợp nhất làm cực đại công thức
(2.2) nên mẫu số trong tất cả các trường hợp là giống nhau, vì vậy ta có thể loại bỏ nó.
Do đó, bài toán trở thành tìm chuỗi các nhãn thỏa mãn công thứ
c (2.3)
(2.3)
Áp dụng luật chuỗi xác suất, ta có công thức (2.4)
(2.4)
Vẫn không có phương pháp hiệu quả để tính xác suất của chuỗi này một cách
chính xác, vì nó yêu cầu quá nhiều dữ liệu. Ở đây ta phải áp dụng các giả thiết độc lập
điều kiện để có một xác suất đơn giản hơn (giả thiết rằng mỗi từ đều là độc lập với các
từ khác và đặc tính của m
ột từ chỉ phụ thuộc vào nhãn của nó). Sử dụng giả thiết N-
gram để mô hình hóa xác suất chuỗi từ:
(2.5a)
Cụ thể ta dùng mô hình phổ biến nhất là mô hình tri-gram.
(2.5b)
Đầu tiên, ta đơn giản hóa rằng xác suất của một từ thì chỉ phụ thuộc vào nhãn của
nó:
ˆ
(| )
T
TargmaxPTW
P
(t , ,t )= P(t |t )
123 2 1 3 2
P
t,t,t = Pt|t Pt| t
Copyright: Tài liệu đại học ©