i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ HƢƠNG THẢO
PHÂN TÁCH CỤM DANH TỪ CƠ SỞ TIẾNG VIỆT
SỬ DỤNG MÔ HÌNH CRFs
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS.Nguyễn Phƣơng Thái
Hà Nội – 2010
i
MỤC LỤC
Lời cảm ơn .....................................................................Error! Bookmark not defined.
Tóm tắt nội dung ...........................................................Error! Bookmark not defined.
Lời cam đoan .................................................................Error! Bookmark not defined.
Danh mục bảng số liệu..............................................................................................iii
Danh mục hình vẽ ..................................................................................................... iv
Lời mở đầu ................................................................................................................. 1
Chương 1: Khái quát về bài toán phân tách cụm danh từ cơ sở ............................. 3
1.1. Giới thiệu bài toán ......................................................................................... 3
1.2. Một số nghiên cứu về bài toán phân tách cụm danh từ cơ sở ......................... 5
1.3. Một số phương pháp biểu diễn dữ liệu........................................................... 7
1.4. Một số phương pháp giải quyết bài toán ........................................................ 8
1.4.1. Thuật toán học dựa vào biến đổi ............................................................. 9
1.4.2. Thuật toán máy vector hỗ trợ ................................................................ 10
1.4.3. Phương pháp tiếp cận của luận văn ....................................................... 12
Chương 2: Mô hình trường ngẫu nhiên có điều kiện ............................................. 13
2.1. Mô hình đồ thị............................................................................................. 14
Mô hình đồ thị vô hướng ................................................................................ 14
2.2. Mô hình trường ngẫu nhiên có điều kiện ..................................................... 15
2.3. Ước lượng tham số và suy diễn CRFs ......................................................... 17
2.3.1. Ước lượng tham số cho CRFs ............................................................... 17
2.3.2. Suy diễn CRFs...................................................................................... 19
Chương 3: Đặc điểm cụm danh từ tiêng Việt và phương pháp xây dựng tập dữ
liệu ............................................................................................................................ 21
3.1. Đặc điểm cụm danh từ tiếng Việt ................................................................ 21
3.2. Phương pháp xây dựng tập dữ liệu .............................................................. 26
3.2.1. Phương pháp xây dựng tập dữ liệu tiếng Anh ....................................... 26
3.2.2 Phương pháp xây dựng tập dữ liệu Tiếng Việt ....................................... 26
Chương 4: Bài toán phân tách cụm danh từ tiếng Việt sử dụng mô hình CRFs .. 33
4.1. Phân tách cụm từ tiếng Việt sử dụng mô hình CRFs .................................... 33
4.2. Thực nghiệm ............................................................................................... 34
ii
4.2.1. Dữ liệu và chương trình ............................................................................ 34
4.2.2. Kết quả thử nghiệm .................................................................................. 36
4.2.2.1 Thực nghiệm 1: Đánh giá sự phục thuộc tập thuộc tính ...................... 36
4.2.2.2. Đánh giá sự phụ thuộc của kích thước tập dữ liệu huấn luyện ............ 40
4.2.2.3. Đánh giá và phân tích lỗi ................................................................... 41
Kết luận .................................................................................................................... 43
Tài liệu tham khảo ................................................................................................... 45
Phụ lục: Tập nhãn từ loại và nhãn cú pháp trong Viet Treebank ........................ 49
Tập nhãn từ loại: ................................................................................................ 49
Tập nhãn cú pháp ............................................................................................... 49
Tập nhãn mệnh đề: ............................................................................................. 50
Tập nhãn chức năng cú pháp: ............................................................................. 50
iii
Danh mục bảng số liệu
Bảng 1: Một số kết quả bài toán phân tách cụm danh từ cơ sở tiếng Anh ..................... 6
Bảng 2: Một số kết quả bài toán phân tách cụm danh từ cơ sở ngôn ngữ khác ............. 6
Bảng 3: Ví dụ về các phương pháp biểu diễn dữ liệu ................................................... 8
Bảng 4: Cấu trúc phần đầu của cụm danh từ tiếng Việt .............................................. 23
Bảng 5: Cấu trúc phần đầu của cụm danh từ tiếng Việt .............................................. 24
Bảng 6: Ví dụ về tệp dữ liệu được sử dụng trong thực nghiệm ................................... 34
Bảng 7: Một vài thống kê về tập dữ liệu..................................................................... 36
Bảng 8: Một số ví dụ về mẫu thuộc tính ..................................................................... 37
Bảng 9: Chi tiết tập thuộc tính của thí nghiệm 7......................................................... 39
Bảng 10: Kết quả của bộ phân tách cụm danh từ tiếng Việt ....................................... 40
iv
Danh mục hình vẽ
Hình 1: Quá trình huấn luyện của thuật toán TBL ........................................................ 9
Hình 2: Siêu phẳng có lề hẹp ..................................................................................... 11
Hình 3: Siêu phẳng có lề rộng .................................................................................... 11
Hình 4: Dữ liệu có nhiễu ............................................................................................ 11
Hình 5: Dữ liệu không thể phân tách tuyến tính ......................................................... 11
Hình 6: Mô hình đồ thị CRFs..................................................................................... 16
Hình 7: Ví dụ về biểu diễn dạng cây của một câu đã phân tích cú pháp...................... 27
Hình 8: Ví dụ về nhánh NP có độ sâu bằng 1 hoặc 2 .................................................. 28
Hình 9: Ví dụ về nhánh NP có độ sâu lớn hơn 2......................................................... 29
Hình 10: Nhánh NP có độ sâu lớn hơn 3 .................................................................... 30
Hình 11: Nhánh QP có độ sâu bằng 1 ........................................................................ 30
Hình 12: Nhánh QP có độ sâu bằng 2 ........................................................................ 30
Hình 13: Nhánh QP có độ sâu bằng 3 và chứa NP ..................................................... 30
Hình 14: Nhánh QP có độ sâu lớn hơn 3 và chứa NP có độ sâu bằng 1 ...................... 31
Hình 15: Ví dụ về cụm danh từ chứa liên từ “và” ....................................................... 31
Hình 16: Mô hình hoạt động của bộ tách cụm danh từ tiếng Việt ............................... 33
Hình 17: Sự tác động của tập thuộc tính đến độ chính xác của mô hình phân cụm ..... 38
Hình 18: Kết quả bộ phân tách cụm danh từ theo kích thước tập dữ liệu huấn luyện .. 40
1
Lời mở đầu
Thế giới bước vào thế kỷ 21 với sự phát triển nhanh và đạt được nhiều thành
tựu trong tất cả các lĩnh vực kinh tế, kỹ thuật, văn hóa, xã hội… Cùng với sự phát triển
này, nhân loại đã tạo ra một lượng thông tin khổng lồ và phần lớn những thông tin đó
chúng ta có thể tìm thấy thông qua hệ thống mạng Internet. World Wide Web (gọi tắt
là Web) đã trở thành một môi trường chuyển tải thông tin không thể thiếu trong thời
đại Công nghệ thông tin ngày nay. Sự phổ biến và bùng nổ thông tin trên Web cũng
đặt ra một thách thức mới là làm thế nào để khai thác được thông tin trên Web một
cách hiệu quả, mà cụ thể là làm sao để máy tính có thể trợ giúp xử lý tự động được
chúng. Có thể nói xử lý ngôn ngữ tự động trên máy tính là một trong những vấn đề
khó nhất của Công nghệ thông tin. Cái khó nằm ở chỗ làm sao cho máy được hiểu
ngôn ngữ con người, từ việc hiểu nghĩa từng từ trong mỗi hoàn cảnh cụ thể, đến việc
hiểu nghĩa một câu, rồi hiểu cả văn bản.
Trong nỗ lực xây dựng một cơ sở tri thức tiếng Việt thì các bài toán cơ bản như
tách từ, gán nhãn từ loại, xác định cụm từ, phân tích cú pháp, … là những công việc
không thể thiếu. Tùy từng ứng dụng sẽ cần phân tích thông tin ở các mức độ khác
nhau. Nhiều ứng dụng của xử lý ngôn ngữ tự nhiên (như dịch máy) yêu cầu thông tin
về cú pháp và các công cụ để phân tích cú pháp. Tuy nhiên với tiếng Việt, hầu hết các
nhà nghiên cứu hiện tại mới chỉ tập trung vào bài toán tách từ và gán nhãn từ loại (theo
[21]).
Quá trình xây dựng bộ công cụ và dữ liệu đã gán nhãn cho các bài toán nền tảng
như phân tách cụm từ và phân tích cú pháp hiện đang được nghiên cứu, phát triển. Đây
là một bước quan trọng cho các ứng dụng phát triển ngôn ngữ tự nhiên yêu cầu hiểu
sâu hơn về ngôn ngữ. Nhu cầu cần phải phát triển những công cụ như này là động lực
thúc đẩy tôi nghiên cứu và tìm hiểu về bài toán phân tách cụm từ danh từ tiếng Việt,
với mục tiêu phát triển được một công cụ cho bài toán này.
Luận văn với đề tài “Phân tách cụm danh từ cơ sở tiếng Việt sử dụng mô hình
CRFs” được tổ chức thành bốn chương mà nội dung chính của các chương được giới
thiệu như dưới đây.
Chương 1: Khái quát về bài toán phân tách cụm danh từ giới thiệu bài toán và
các nghiên cứu trước đó cũng như kết quả đã đạt được về bài toán này. Chương này
cũng trình bày một số thuật toán điển hình phân tách cụm danh từ, từ đó chọn ra
2
hướng tiếp cận với ngôn ngữ tiếng Việt. Một số phương pháp biểu diễn dữ liệu cũng
được giới thiệu trong chương này.
Chương 2: Mô hình trường ngẫu nhiên có điều kiện trình bày cơ bản về CRFs mô hình học máy được đánh giá là môt trong những phương pháp tốt nhất cho bài toán
gán nhãn dữ liệu dạng chuỗi.
Chương 3. Đặc điểm cụm danh từ tiếng Việt và phương pháp xây dựng tập dữ
liệu trình bày cấu trúc của cụm danh từ tiếng Việt, từ đó đề xuất phương pháp thích
hợp xây dựng tập dữ liệu tiếng Việt.
Chương 4. Bài toán phân tách cụm danh từ tiếng Việt sử dụng mô hình CRFs
trình bày các kết quả thực nghiệm khi áp dụng mô hình CRFs để phân tách cụm danh
từ tiếng Việt với bộ dữ liệu do luận văn xây dựng. Một số nhận xét, đánh giá cũng
được trình bày.
3
Chương 1: Khái quát về bài toán phân tách cụm danh từ cơ sở
1.1. Giới thiệu bài toán
Trong những năm gần đây, nhiều ứng dụng xử lý ngôn ngữ tự nhiên như trích
chọn thông tin, tóm tắt văn bản, hỏi đáp và dịch máy phát triển mạnh mẽ đem lại nhiều
lợi ích thiết thực. Trong các ứng dụng này, cụm danh từ cơ sở đóng một vai trò quan
trọng. Chính vì vậy, ngay từ những năm 1990, đã có nhiều nghiên cứu liên quan đến
lĩnh vực này trên tiếng Anh và cho đến nay các nghiên cứu đó vẫn liên tục được cải
tiến và đã đạt được một số kết quả khả quan nhất định. Các ngôn ngữ khác như tiếng
Trung, tiếng Hàn Quốc, tiếng Ấn Độ … cũng rất được quan tâm và nghiên cứu khá
nhiều. Nhiều công trình nghiên cứu và bài báo khoa học liên quan đến vấn đề này đã
được công bố, điển hình phải kể đến hai hội nghị: Hội nghị về xử lý ngôn ngữ tự nhiên
CoNLL1 năm 2000 với chủ đề chính là phân tách cụm từ và phân tách cụm danh từ;
Hội nghị về phân tích sơ bộ các ngôn ngữ Nam Á SPSAL 2007 2. Đối với tiếng Việt,
hiện nay hầu hết các nhà nghiên cứu mới chỉ tập trung vào bài toán tách từ và gán
nhãn từ loại. Phân tách cum danh từ cơ sở tiếng Việt vẫn còn là bài toán mở. Các
nghiên cứu về bài toán này rất ít và mới chỉ dừng ở mức thử nghiệm quy mô nhỏ, chưa
được công bố rộng rãi.
Phân tách các cụm từ là bài toán chia một câu thành các cụm sao cho các từ
trong cùng một cụm có liên quan với nhau về mặt cú pháp. Các cụm này không chồng
lên nhau (non-overlapping) theo nghĩa một từ chỉ được phép thuộc một cụm duy nhất.
Ví dụ câu tiếng Anh dưới đây sẽ được tách thành các cụm như sau:
[NP He] [VP reckons] [NP the current account deficit] [VP will narrow] [PP to]
[NP only £ 1.8 billion]
Hoặc một câu tiếng Việt sẽ được tách thành các cụm như sau:
[NP Cô ấy] [VP học] [PP ở] [NP trường Đại học Công nghệ]
Ở đây, các cụm được biểu diễn như một nhóm các từ liền kề nhau nằm giữa hai
dấu ngoặc vuông: Dấu ngoặc vuông mở biểu thị bắt đầu một cụm; Dấu ngoặc vuông
đóng biểu thị kết thúc một cụm. Các chữ viết hoa liền sau dấu ngoặc vuông mở là kí
hiệu viết tắt biểu thị loại của các cụm, ví dụ NP là cụm danh từ, VP là cụm động từ, PP
là cụm giới từ. Trong các loại cụm thì cụm danh từ chiếm tỷ lệ lớn nhất, tập dữ liệu
1
2
http://www.cnts.ua.ac.be/conll2000/
http://shiva.iiit.ac.in/SPSAL2007/
4
tiếng Anh WSJ 15-18 có tới 51% là cụm danh từ [12]. Hơn nữa, trong nhiều ứng dụng
xử lý ngôn ngữ tự nhiên, việc tách các cụm danh từ là bước trung gian quan trọng để
xử lý các bước tiếp theo. Vì vậy, phân tách cụm danh từ cũng đóng vai trò quan trọng
trong xử lý ngôn ngữ tự nhiên.
Phân tách cụm danh từ là một phần của bài toán phân tách cụm từ, giải quyết
việc nhận biết các cụm danh từ không đệ quy (non-recursive noun phrase) hay cụm
danh từ không chồng nhau (non-overlappling noun phrase) trong câu. Các cụm danh từ
được phân tách ở đây là các cụm danh từ đơn giản, hay cụm danh từ cơ sở. Đó là các
cụm danh từ không đệ quy, tức là không chứa một cụm danh từ khác bên trong nó và
không chứa thành phần bổ nghĩa là một cụm danh từ.
Trong khuôn khổ luận văn này, tôi chỉ tập trung giải quyết bài toán tách cụm
danh từ cơ sở tiếng Việt. Tuy nhiên, do các đặc trưng ngôn ngữ của tiếng Việt nên cấu
trúc của cụm danh từ cơ sở tiếng Việt sẽ khác cấu trúc cụm danh từ đơn giản trong các
xử lý trích cụm danh từ tiếng Anh. Đặc trưng và cấu trúc cụm danh từ cơ sở tiếng Việt
sẽ được trình bày kỹ ở Chương 3.
Một hệ thống phân tách cụm danh từ cơ sở tốt có thể được áp dụng trong nhiều
bài toán như:
Trong hệ thống tìm kiếm thông tin, thay vì tìm kiếm tài liệu chứa các từ riêng
lẻ, hệ thống sẽ tìm kiếm dựa vào các cụm từ. Khi đó một số cụm từ và danh từ
riêng sẽ rất hữu ích cho mục đích tìm kiếm tài liệu. Phân tách các cụm từ cũng
rất hữu ích cho các bài toán trích chọn thông tin, máy hỏi-đáp.
Hệ thống dịch máy dựa vào thống kê có thể gồm các hệ con có nhiệm vụ dịch
các cụm như cụm danh từ, cụm động từ, cụm giới từ,… như một tác vụ nhỏ
trong quá trình dịch. Hệ dịch con có thể được huấn luyện trên tập dữ liệu học là
các cụm danh từ, cụm động từ, cụm giới từ,… Với hệ dịch máy sử dụng tập dữ
liệu huấn luyện song song, các cụm danh từ cũng được sử dụng để gióng hàng
văn bản. Các câu trong tập dữ liệu song song được gióng hàng bằng cách sử
dụng các thông tin cụm từ và liên kết cụm ở ngôn ngữ nguồn với cụm ở ngôn
ngữ đích.
Phân tách cụm danh từ có thể được sử dụng như một bước tiền xử lý trước khi
phân tích cả câu. Vì ngôn ngữ tự nhiên có tính nhập nhằng cao nên việc phân
tích một câu có thể trở nên rất phức tạp. Trong những trường hợp này, phân
tách cụm từ có thể được sử dụng như một bước tiền xử lý giải quyết những
nhập nhằng này.
5
Xác định đồng tham chiếu là bài toán xác định các cụm danh từ cùng tham
chiếu tới một thực thể nào đó. Xác định đồng tham chiếu là một trong những
nghiên cứu cốt lõi trong xử lý ngôn ngữ tự nhiên, đóng vai trò quan trọng trong
các lĩnh vực như máy hỏi-đáp, dịch tự động, tóm tắt văn bản. Để giải quyết bài
toán phải qua nhiều bước, nhưng bước quan trọng đầu tiên là phải xác định
được các cụm danh từ trong từng câu. Vì vậy, phân tách cụm danh từ là bài toán
cơ sở để xác định tham chiếu trong văn bản.
Trong hệ thống tự động sinh chỉ mục các thuật ngữ cho một cuốn sách, bước
đầu tiên là phải xác định được các thuật ngữ để đánh chỉ mục. Các thuật ngữ
này thường là danh từ hoặc cụm danh từ. Do đó, bài toán phát hiện và phân tách
cụm danh từ sẽ là một bước quan trọng trong quá trình sinh chỉ mục tự động.
1.2. Một số nghiên cứu về bài toán phân tách cụm danh từ cơ sở
Năm 1991, Stenven Abney đã đề xuất bài toán phân tích một câu đầu vào thành
các cụm từ trong đó các từ trong cùng một cụm tương liên với nhau [7]. Nghiên cứu
của tác giả dựa vào kết quả nghiên cứu của hai nhà tâm lý học Gee và Grojean (1983),
theo đó các cụm là những quãng ngắt khi đọc một câu. Giả sử khi đọc một câu, ta
không đọc liền mạch cả câu đó mà sẽ ngắt ra thành các cụm như sau:
[I begin] [with an intuition] : [when I read] [a sentence], [I read it] [a chunk] [at
a time]
Những cụm này được gọi là cụm . Cụm điển hình gồm một từ nội dung,
xung quanh là các từ chức năng. Từ chức năng (function word) là những từ chứa ít
nghĩa từ vựng hoặc nhập nhằng về ngữ nghĩa nhưng nó diễn tả quan hệ ngữ pháp với
các từ khác trong một câu như giới từ, đại từ, …); Những từ không phải là từ chức
năng được gọi là từ nội dung (content word).
Sau Abney, một số nghiên cứu khác tập trung chủ yếu vào phát hiện các cụm
danh từ ở mức thấp, thường là trích chọn các thuật ngữ (Bourigault 1992, Voutilainen
1993) (theo [19]) bằng cách sử dụng văn phạm. Phải đến năm 1995 khi Lance
Ramshaw và Mitch Marcus đề xuất phương pháp phân tách cụm từ bằng phương pháp
học máy thì bài toán này mới được biết đến rộng rãi và được nhiều nhà khoa học quan
tâm. Phương pháp học máy dựa vào biến đổi (Transformation-Based Learning - TBL)
được Ramshaw và Marcus sử dụng và đem lại kết quả khả quan với F1 bằng 92.03%
[19]. Hai tác giả cũng xây dựng bộ dữ liệu chuẩn tiếng Anh mà hầu hết các nghiên cứu
sau này thường sử dụng để so sánh, đánh giá kết quả. Ba nhà nghiên cứu Abney,
Ramshaw, Marcus được coi là những người đi tiên phong trong vấn đề này.
6
Sau nghiên cứu của Ramshaw và Marcus, nhiều nhà nghiên cứu khác đã đi sâu
tìm hiểu, giải quyết bài toán, trong đó phải kể tới hội nghị CONLL-2000 tập trung về
phân tách cụm danh từ và các loại cụm từ khác. Nhiều phương pháp học máy khác
nhau đã được sử dụng để thử nghiệm và thu được kết quả khá tốt. Có thể được chia
thành bốn nhóm phương pháp: phương pháp học dựa vào luật, học dựa vào bộ nhớ,
học thống kê và các hệ thống kết hợp. Một số kỹ thuật mới được phát triển gần đây
như mô hình trường ngẫu nhiên có điều kiện (Conditional Random Fields, CRFs),
phương pháp học cấu trúc, học bán giám sát,… cũng đã được áp dụng, phát triển. Mặc
dù đã được nghiên cứu trong gần hai mươi năm qua nhưng đến nay nhiều nhà nghiên
cứu vẫn quan tâm và tìm cách cải tiến. Điều này chứng tỏ sự cần thiết và tầm quan
trọng của một hệ thống phân tách cụm từ danh từ nói riêng và các cụm từ nói chung.
Một số kết quả tốt nhất cho bài toán phân tách cụm danh từ cơ sở tiếng Anh
được biểu diễn trong bảng 1.
Bảng 1: Một số kết quả bài toán phân tách cụm danh từ cơ sở tiếng Anh
Tác giả
Phương pháp
F1
Hieu, Minh 2006 [25]
Trường ngẫu nhiên có điều kiện
96.74
Kudo, Matsumoto 2001 [34]
Máy vector hỗ trợ
95.77
Sang 2000 [13]
Kết hợp các phương pháp
94.90
Sha, Pereira 2003 [31]
Trường ngẫu nhiên có điều kiện
94.38
Với các ngôn ngữ khác, hầu hết kết quả tách cụm danh từ thấp hơn khá nhiều so
với tiếng Anh, do mỗi ngôn ngữ có những đặc trưng và khó khăn riêng. Ngôn ngữ
Trung Quốc đạt kết quả cao khi sử dụng phương pháp máy vector hỗ trợ và mô hình
trường ngẫu nhiên có điều kiện [15]. Ba ngôn ngữ của Ấn Độ là Bengali, Hindi và
Telugu đạt kết quả phân tách cụm từ cao nhất khi sử dụng phương pháp CRFs [10].
Ngôn ngữ Hàn Quốc cũng đạt kết quả rất cao với CRFs khi phân tách cụm danh từ cơ
sở. Một số kết quả phân tách cụm danh từ của các ngôn ngữ khác được biểu diễn trong
bảng 2.
Bảng 2: Một số kết quả bài toán phân tách cụm danh từ cơ sở ngôn ngữ khác
Tác giả
Phương pháp
Chen, Zang, Isahara 2006 CRFs
[36]
Xu, Zong, Zhao 2006 [15]
Kết hợp SVMs và CRFs
Ngôn ngữ
F1
Trung Quốc
89.79
Trung Quốc
89.27
7
Avinesh, Karthik 2007 [10]
Lee, Kim, Lee [38]
CRFs
Bengali (Ấn Độ) 82.74
(phân tách cụm từ)
Hindi (Ấn Độ)
80.97
Telugu (Ấn Độ)
79.15
Hàn Quốc
94.27
CRFs
Các nhà nghiên cứu xử lý ngôn ngữ tiếng Việt hiện vẫn đang nỗ lực trong quá
trình xây dựng bộ công cụ và tập dữ liệu cho các bài toán nền tảng như phân tích cú
pháp, phân tách cụm từ. Tuy nhiên hiện nay vẫn chưa có một bộ dữ liệu chuẩn nào cho
việc đánh giá và so sánh hệ thống tách cụm danh từ tiếng Việt, do việc xây dựng bộ dữ
liệu này rất tốn kém về mặt thời gian cũng như công sức. Hi vọng rằng trong thời gian
gần sắp tới, chúng ta sẽ có được bộ dữ liệu chuẩn hỗ trợ trong việc nghiên cứu bài toán
này.
1.3. Một số phương pháp biểu diễn dữ liệu
Bài toán phân tách cụm danh từ tiếng Việt có thể được xem là bài toán gán nhãn
hoặc phân lớp cho các từ trong câu. Ví dụ, đối với bài toán xác định từ loại của các từ
trong câu là gán nhãn các lớp từ loại cố định có sẵn (danh từ, động từ, tính từ, đại từ,
số từ, …) cho các từ trong câu. Hay như bài toán xác định trọng âm của từ là xác định
loại trọng âm nào tại mỗi ký tự trong từ, trong câu. Như vậy, tùy theo tác vụ xử lý
ngôn ngữ tự nhiên mà có thể gán nhãn giá trị của lớp trên mỗi ký tự hoặc trên mỗi từ
trong câu. Riêng đối với xác định cụm danh từ trong câu thì dữ liệu cần gán nhãn là
nhóm các từ liên tục nhau và cần xác định xem mỗi từ có thuộc cụm danh từ hay
không. Tùy vào phương pháp biểu diễn, ta sẽ có tập các nhãn để gán cho các từ trong
câu.
Bộ dữ liệu do Ramshaw và Marcus xây dựng năm 1995 được biểu diễn theo
phương pháp IOB, sử dụng tập nhãn là {I, O, B}. Sau này khi Sang và Veenstra giới
thiệu ba biến thể khác là IOB2, IOE1, IOE2 năm 1999 [35] thì phương pháp biểu diễn
của Ramshaw và Marcus được gọi là IOB1. Bốn phương pháp biểu diễn dữ liệu này
giống nhau ở cách gán nhãn cho từ không thuộc cụm – nhãn O; và khác nhau ở cách
gán nhãn cho từ đầu tiên và từ cuối cùng của một cụm danh từ. Cụ thể như sau:
IOB1: Từ đầu tiên của một cụm danh từ cơ sở theo sau một cụm danh từ cơ sở
khác được gán nhãn B.
8
IOB2: Từ đầu tiên của cụm danh từ cơ sở được gán nhãn B, những từ tiếp theo
của cụm danh từ cơ sở được gán nhãn I, từ không thuộc cụm danh từ nào được
gán nhãn là O.
IOE1: Từ cuối cùng của một cụm danh từ cơ sở đứng liền trước cụm danh từ
khác được gán nhãn E.
IOE2: Từ cuối cùng của tất cả cụm danh từ cơ sở được gán nhãn E.
Đây là một số phương pháp thường được sử dụng trong các hệ thống phân tách
cụm danh từ cơ sở. Ngoài ra còn một số phương pháp khác như [+], [+IO, IO+].
Ví dụ, câu “Tốc độ tăng trưởng GDP trên địa bàn TP đạt 12% năm 2005” sẽ
được gán nhãn như sau:
Bảng 3: Ví dụ về các phương pháp biểu diễn dữ liệu
Từ
Nhãn từ loại
IOB1
IOB2
IOE1
IOE2
Tốc_độ
N-H
I
B
I
I
tăng_trưởng
V-H
I
I
I
I
GDP
Ny
I
I
I
E
trên
E-H
O
O
O
O
địa_bàn
N-H
I
B
I
I
TP
Ny
I
I
I
E
đạt
V-H
O
O
O
O
12%
M
I
B
E
E
năm
N-H
B
B
I
I
2005
M
I
I
I
E
1.4. Một số phương pháp giải quyết bài toán
Phân tách cụm danh từ là một trong các bài toán xử lý ngôn ngữ tự nhiên có
ứng dụng khá rộng rãi trong nhiều lĩnh vực khác nhau. Chính vì vậy, ngay từ những
năm 1990, đã có nhiều nghiên cứu liên quan đến bài toán này và cho đến nay các
nghiên cứu đó vẫn tiếp tục được cải tiến, đạt được những kết quả khả quan và ngày
càng được áp dụng trên nhiều ngôn ngữ khác nhau.
9
Hiện nay tồn tại nhiều phương pháp giải quyết bài toán phân tách cụm danh từ
cơ sở, nhưng nhìn chung có thể chia thành bốn nhóm chính sau: học dựa trên luật
(rule-based methods), học mẫu (memory-based methods), các phương pháp dựa vào
thống kê (statistical methods) và các phương pháp kết hợp (combined methods).
Phần này sẽ trình bày hai thuật toán học máy là học dựa vào biến đổi và máy
vector hỗ trợ. Thuật toán học dựa vào biến đổi là phương pháp học máy đầu tiên được
áp dụng để xác định cụm danh từ tiếng Anh và đã thu được kết quả khá tốt. Máy
vector hỗ trợ hiện là một trong những phương pháp đem lại kết quả tốt nhất cho bài
toán này.
1.4.1. Thuật toán học dựa vào biến đổi
Học dựa vào biến đổi (Transformation-based learning hay Transformationbased error-driven learning, TBL) là phương pháp học máy dựa trên luật hiệu quả,
được Brill giới thiệu năm 1993 [11]. TBL là thuật toán linh hoạt, có thể dễ dàng mở
rộng với nhiều bài toán và miền ứng dụng khác nhau. TBL đã được áp dụng cho nhiều
bài toán và đem lại kết quả khả quan như gán nhãn từ loại, phân tách cụm danh từ,
phân đoạn và hiểu văn bản.
Ý tưởng cơ bản của TBL là học một tập các luật từ dữ liệu huấn luyện. Tập luật
này được sắp thứ tự và phát triển tăng dần dựa vào trạng thái hiện tại của tập dữ liệu
học. Tập luật đầu tiên được lựa chọn dựa vào thống kê đơn giản, sau đó các luật được
học tăng dần để hiệu chỉnh những lỗi sai cho đến khi độ chính xác không thể tăng lên
được nữa.
Dữ liệu huấn luyện
Hệ dự đoán cơ sở
Tập mẫu luật
Đánh giá các luật
ứng cử
Tập dữ liệu hiện tại
Tập nhãn đúng
Lựa chọn luật
Áp dụng luật
Tập luật kết quả
Hình 1: Quá trình huấn luyện của thuật toán TBL
10
Quá trình học được thực hiện như sau (hình 1): Đầu tiên, một hệ thống cơ sở
(baseline system) được sử dụng để gán nhãn cho tập ví dụ học. Hệ thống cơ sở thường
dựa vào kinh nghiệm, có thể là nhãn phổ biến nhất trong tập dữ liệu huấn luyện, hoặc
có thể là kết quả của một bộ phân lớp khác. Sau đó, với các ví dụ bị hệ thống cơ sở dự
đoán sai, các mẫu luật sẽ được sử dụng để lựa chọn danh sách các luật ứng cử
(candidate). Các luật ứng cử này được kiểm tra với các ví dụ còn lại, xác định số ví dụ
bị được gán đúng và số ví dụ bị gán sai khi áp dụng luật. Luật nào có tỉ số (số ví dụ
gán đúng trừ số ví dụ gán sai) lớn nhất sẽ được lựa chọn. Luật này sẽ là luật đầu tiên
trong danh sách luật được học. Quá trình học này được lặp lại trên tập dữ liệu đã bị
biến đổi: tìm tập luật ứng cử, đánh giá chúng và lựa chọn luật tốt nhất. Quá trình này
được lặp đi lặp lại, cho đến khi độ chính xác không thể tăng lên được nữa. Kết quả của
quá trình này ta sẽ được một tập các mẫu được sắp xếp theo thứ tự, luật nào được lựa
chọn trước sẽ đứng trước, luật nào được lựa chọn sau sẽ đứng sau. Để dự đoán một tài
liệu, đầu tiên ta áp dụng hệ dự đoán cơ sở và sau đó áp dụng lần lượt từng luật trong
tập luật trả về từ quá trình học.
1.4.2. Thuật toán máy vector hỗ trợ
Máy vector hỗ trợ (Support Vector Machines – SVMs) được Vapnik giới thiệu
lần đầu tiên năm 1995, là một hướng tiếp cận học máy mới dựa trên lý thuyết thống kê
để giải quyết các bài toán nhận dạng hai lớp. SVMs được biết tới rộng rãi bởi độ chính
xác cao khi áp dụng cho nhiều bài toán nhận dạng. Gần đây, SVMs được ứng dụng
trong nhiều bài toán xử lý ngôn ngữ tự nhiên như phân lớp văn bản, phân tách cụm
danh từ [15,33,34]. Đã có những kết quả lý thuyết cũng như thực nghiệm chỉ ra rằng
SVM có thể đem lại kết quả tốt với không gian thuộc tính nhiều chiều mà không gặp
phải hiện tượng quá khớp (over-fitting) dữ liệu huấn luyện.
Về cơ bản, SVM là một bộ phân lớp tuyến tính giải quyết bài toán phân lớp nhị
phân. Bài toán được định nghĩa như sau:
Cho tập dữ liệu học D ( xi , y i ), i 1,..., n với xi R m và yi 1,1 là một số
nguyên xác định xi là dữ liệu dương hay âm. Một tài liệu xi được gọi là dữ liệu dương
nếu nó thuộc lớp ci ; xi được gọi là dữ liệu âm nếu nó không thuộc lớp ci . Các ví dụ
huấn luyện sẽ được phân tách thành hai miền âm và dương bởi siêu phẳng có dạng:
x : f ( x) w
T
w0 0
Trong đó w R m và w0 R đóng vai trò là tham số của mô hình. Hàm phân lớp
nhị phân h : Rm 0,1 có thể thu được bằng cách xác định dấu của f(x) :
11
1 nếu f ( x) 0
h( x) ngược lại
0
Hình 2: Siêu phẳng có lề hẹp
Hình 3: Siêu phẳng có lề rộng
Nếu dữ liệu được phân tách tuyến tính thì sẽ tồn tại nhiều siêu phẳng có khả
năng phân tách dữ liệu thành hai miền. Hai trong số những siêu phẳng được minh họa
như trên hình 2 và hình 3. Câu hỏi đặt ra là trong hai siêu phẳng này thì siêu phẳng nào
tốt hơn, và làm thế nào để xác định được siêu phẳng tối ưu?
Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các
dữ liệu học gần nhất. Vapnik chứng minh rằng, siêu phẳng tối ưu nhất là siêu phẳng có
biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ
siêu phẳng đến những điểm gần nhất là lớn nhất. Vapnik cũng chứng minh rằng khả
năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác.
Hình 4: Dữ liệu có nhiễu
Hình 5: Dữ liệu không thể phân tách tuyến
tính
Vì khoảng cách nhỏ nhất giữa f và dữ liệu huấn luyện là 1/||w||, SVM sẽ tìm w
và wo sao cho:
12
Cực đại hóa
1
w
2
2
với ràng buộc: yi wT xi w 0 1 , i = 1, 2, … n
Nếu dữ liệu có thể phân tách tuyến tính như trên thì SVM có thể tìm được siêu
phẳng phân tách dữ liệu huấn luyện với độ chính xác lý tưởng. Tuy nhiên, trong thực
tế rất hiếm khi dữ liệu có thể phân tách tuyến tính mà thường bị nhiễu (hình .. ) hoặc
không tồn tại siêu phẳng phân tách (hình). Khi đó, thêm vào tham số độ sai lệch C, bài
toán tối ưu trở thành:
Cực tiểu hóa
n
1 2
w C i với ràng buộc yi wT xi w 0 1 i in1 : i 0
2
i 1
Trong đó, i là độ sai lệch của mỗi ví dụ huấn luyện, được đo bằng khoảng
cách giữa ví dụ đó và biên của lớp chứa ví dụ.
Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support
Vector Machine.
1.4.3. Phương pháp tiếp cận của luận văn
Các kết quả nghiên cứu về phân tách cụm danh từ đối với tiếng Anh và một số
ngôn ngữ khác như tiếng Trung, tiếng Hàn Quốc, và một số ngôn ngữ của Ấn Độ cho
thấy, trường ngẫu nhiên có điều kiện (CRFs) là một trong những phương pháp cho kết
quả cao nhất khi giải quyết bài toán này. CRFs là phương pháp được các nhà nghiên
cứu rất quan tâm hiện nay bởi những ưu điểm nổi trội như cho phép biểu diễn thuộc
tính phụ thuộc vào các thành phần của dữ liệu quan sát, kết hợp nhiều thuộc tính
phong phú từ dữ liệu một cách mềm dẻo. Hơn nữa, huấn luyện CRFs thực hiện dựa
trên việc tối ưu hoá hàm log-likelihood - bản chất là một hàm lồi, do đó cho phép thu
được tối ưu toàn cục. Xuất phát từ những lý do trên, luận văn lựa chọn mô hình trường
ngẫu nhiên có điều kiện để giải quyết bài toán phân tách cụm danh từ tiếng Việt.
Chương sau sẽ trình bày kỹ hơn về mô hình này.
13
Chương 2: Mô hình trường ngẫu nhiên có điều kiện
Bài toán phân tích dữ liệu dạng chuỗi hay gán nhãn dữ liệu dạng chuỗi trong
ngôn ngữ học thường được mô tả như việc ánh xạ chuỗi dữ liệu đầu vào thành chuỗi
nhãn tương ứng. Ví dụ, một số bài toán trong xử lý ngôn ngữ tự nhiên như tách từ,
phân tích cú pháp, nhận dạng thực thể tên, phân tách cụm từ, …. Bài toán này cũng
xuất hiện khá nhiều trong các lĩnh vực khác như tin sinh học, nhận dạng tiếng nói,
trích chọn thông tin. Một trong những phương pháp phổ biến để giải quyết bài toán
gán nhãn và phân đoạn là sử dụng các mô hình Markov ẩn (Hidden Markov Models,
HMMs) hoặc mô hình máy hữu hạn trạng thái dựa vào xác suất. Mô hình Markov ẩn là
một dạng của mô hình sinh, định nghĩa phân phối xác suất đồng thời p(X,Y) với X và
Y là các biến ngẫu nhiên biểu diễn chuỗi quan sát và chuỗi nhãn tương ứng. Để tính
xác suất đồng thời này, mô hình sinh phải liệt kê tất cả các chuỗi quan sát có thể; trong
nhiều miền ứng dụng thì điều này là không thể thực hiện được trừ khi các thành phần
được biểu diễn như những đơn vị riêng biệt, độc lập với các thành phần khác trong
chuỗi quan sát. Nói cách khác, tại một thời điểm, quan sát hiện tại chỉ phụ thuộc vào
trạng thái tại thời điểm đó. Giả thiết này chỉ phù hợp cho một vài tập dữ liệu đơn giản,
vì hầu hết các chuỗi quan sát trong thế giới thực đều được biểu diễn bởi nhiều thuộc
tính có ảnh hưởng lẫn nhau và phụ thuộc vào nhiều quan sát.
Đây là một trong những vấn đề cơ bản khi giải quyết bài toán gán nhãn dữ liệu
dạng chuỗi. Như vậy, rõ ràng một mô hình khắc phục được nhược điểm trên phải thoả
mãn hai tiêu chí: thứ nhất, bài toán suy diễn trong mô hình có thể thực hiện được; thứ
hai, loại bỏ được giả thiết độc lập của chuỗi quan sát. Một cách để thoả mãn được hai
tiêu chí này là sử dụng mô hình xác định phân phối có điều kiện p(Y|X) - là xác suất
của chuỗi trạng thái với điều kiện đã biết chuỗi quan sát, thay vì tính xác suất đồng
thời của chuỗi trạng thái và chuỗi quan sát như trên. Vì mô hình là có điều kiện, phụ
thuộc toàn cục vào X nên có thể sử dụng nhiều thuộc tính đa dạng, phong phú. Ví dụ,
trong các bài toán xử lý ngôn ngữ tự nhiêu, những thuộc tính hữu ích như các từ láng
giềng, tiền tố, hậu tố, chữ viết hoa, và các thông tin ngữ nghĩa từ các nguồn như
WordNet.
Trường ngẫu nhiên có điều kiện (Conditional Random Fields, CRFs) [18] được
McCallum giới thiệu năm 2000 là một mô hình đồ thị vô hướng để gán nhãn và phân
đoạn dữ liệu dạng chuỗi dựa theo hướng tiếp cận có điều kiện như trên. Ưu điểm chính
của CRFs so với mô hình Markov ẩn là bản chất có điều kiện của nó, cho phép biểu
diễn được nhiều thuộc tính phong phú, và bài toán suy diễn có thể giải được. Hơn nữa
CRFs cũng tránh được vấn đề “bias”, nhược điểm của mô hình Markov entropy cực
14
đại (Maximum entropy Markov models, MEMMs) [18] và các mô hình Markov có
điều kiện dựa trên mô hình đồ thị có hướng. CRFs cho kết quả tốt hơn cả MEMMs và
HMMs trong nhiều bài toán gãn nhãn chuỗi dữ liệu trong thế giới thực [8, 23].
Phần sau sẽ trình bày những nét khái quát về mô hình đồ thị, làm cơ sở để từ đó
giới thiệu về mô hình CRFs.
2.1. Mô hình đồ thị
Cho G (V , E ) là một đồ thị với V là tập các đỉnh và E là tập các cạnh. Trong
đó V X Y với X, Y là tập các biến ngẫu nhiên, được biểu diễn bằng các nút hình
tròn. X thường là tập các biến đầu vào mà ta quan sát được, và Y là tập các biến đầu ra
mà ta cần dự đoán. Nếu giữa hai nút không có cạnh nối thì hai nút đó độc lập có điều
kiện. Độc lập có điều kiện nghĩa là hai biến ngẫu nhiên a, b độc lập với một biến ngẫu
nhiên cho trước c nếu hai biến này độc lập với phân phối xác suất có điều kiện của
chúng, hay p(a, b | c) p(a | c) p(b | c) . Những đồ thị biểu diễn được tính chất độc lập có
điều kiện của các phân phối cơ sở như này được gọi là đồ thị độc lập, vì đồ thị có thể
biểu diễn tính chất độc lập có điều kiện của các phân phối cơ sở.
Độc lập có điều kiện là một khái niệm quan trọng vì nó có thể được sử dụng để
phân tích một phân phối xác suất phức tạp thành tích của các thừa số, trong đó mỗi
thừa số chứa tập con các biến ngẫu nhiên tương ứng. Khái niệm này giúp cho các tính
toán phức tạp trở nên hiệu quả hơn.
Kí hiệu các chữ thường đậm x, y, s, v… là vector biểu diễn chuỗi dữ liệu quan
sát, vector biểu diễn chuỗi trạng thái.…. Phân phối xác suất đồng thời sẽ được phân
tích thành tích các thừa số s với v s là tập con các biến ngẫu nhiên tương ứng cấu
thành nên thừa số s này.
p( v) s ( v s )
s
(2.1)
Hai dạng phổ biến nhất của mô hình đồ thị là mô hình đồ thị có hướng và mô
hình đồ thị vô hướng. Điểm khác nhau của hai dạng này là cách phân tích phân phối
xác suất đồng thời thành tích các thừa số. Phần sau sẽ trình bày về mô hình đồ thị vô
hướng.
Mô hình đồ thị vô hướng
Khái niệm clique: Trong lý thuyết đồ thị, một clique trong một đồ thị vô hướng
G là một tập các đỉnh V thoả mãn: với mỗi cặp đỉnh thuộc V luôn tồn tại một cạnh nối.
15
Do vậy một đồ thị con được tạo ra từ V sẽ là một đồ thị đầy đủ. Kích thước của một
clique là số đỉnh của nó.
Một clique tối đa (maximal clique) là tập các đỉnh V sao cho đồ thị con được
tạo ra từ V là một đồ thị con đầy đủ và không là tập đỉnh con của bất kỳ đồ thị đầy đủ
lớn hơn nào khác.
Kí hiệu C là tập clique tối đa của đồ thị. Với mỗi clique c C , gọi c ( v c ) là
hàm tiềm năng của các biến ngẫu nhiên v C . Mô hình đồ thị vô hướng sẽ phân tích xác
suất đồng thời p( v) thành tích các hàm tiềm năng:
p( v)
1
C (v C )
Z cC
(2.2)
Hàm tiềm năng có thể là hàm bất kỳ nhưng phải thoả mãn điều kiện hàm
dương, nhận giá trị thực. Vì tính tổng quát này nên hàm tiềm năng không nhất thiết
phải là một hàm xác suất. Do đó, cần đưa thêm hệ số chuẩn hoá Z đảm bảo tổng xác
suất của tất cả các chuỗi đầu vào bằng 1 tức là
p( v) 1 . Hệ số Z được tính theo
v
công thức:
Z c ( v c )
v
(2.3)
cC
Việc tính toán Z là một trong những thách thức khi học tham số mô hình. Để
đơn giản, các nhà nghiên cứu thường xấp xỉ giá trị này.
2.2. Mô hình trường ngẫu nhiên có điều kiện
Kí hiệu X là biến ngẫu nhiên tương ứng với chuỗi quan sát và Y là biến ngẫu
nhiên tương ứng với chuỗi nhãn. Mỗi thành phần Y i của Y là một biến ngẫu nhiên
nhận trá trị trong tập hữu hạn các trạng thái S.
Một CRF là một mô hình đồ thị vô hướng phụ thuộc toàn cục vào biến ngẫu
nhiên biểu diễn chuỗi quan sát. Một cách hình thức, định nghĩa G (V , E ) là một đồ thị
vô hướng sao cho mỗi nút v V tương ứng với một biến ngẫu nhiên biểu diễn thành
phần Yv của Y. Nếu biến ngẫu nhiên Y v tuân theo tính chất Markov đối với đồ thị G tức là xác suất của biến ngẫu nhiên Y v khi đã biết X và tất cả các biến ngẫu nhiên khác
Y{u|u v, {u,v} V} bằng xác suất của biến ngẫu nhiên Y v khi đã biết X và các biến
ngẫu nhiên khác tương ứng với các đỉnh kề với đỉnh v trong đồ thị:
p(Yv | X, Yu, u v, {u,v} V) = p(Yv | X, Yu, (u,v) E)
- Xem thêm -
.PDF 
55 
494 
65 
