Fn H
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Ngọc Bích
NGHIÊN CỨU BÀI TOÁN XÁC ĐỊNH
COLLOCATION TRONG TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin

HÀ NỘI - 2009

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ


Tôi cũng xin gửi lời cảm ơn tới các anh chị trong SIS Lab đã tận tình giúp đỡ, hỗ trợ
cho tôi về kiến thức chuyên môn.
Cuối cùng, tôi muốn gửi lời cảm ơn tới gia đình, bạn bè, những ngƣời thân yêu luôn
bên cạnh động viên, là nguồn cổ vũ để tôi hoàn thành Khóa luận tốt nghiệp.
Tôi xin chân thành cảm ơn! Sinh viên
Phạm Thị Ngọc Bích

Tóm tắt nội dung
Collocation là những cụm từ (gồm hai hay nhiều từ) thƣờng đƣợc sử dụng với nhau.
Bài toán xác định collocation trong một kho ngữ liệu đã và đang nhận đƣợc nhiều sự quan
tâm, nghiên cứu của các nhà khoa học trên thế giới. Có rất nhiều phƣơng pháp để giải
quyết bài toán này, song hiện nay, các phƣơng pháp thống kê đang đƣợc sử dụng phổ biến
bởi những ngƣời làm trong lĩnh vực Xử lý ngôn ngữ tự nhiên.
Khóa luận tốt nghiệp với đề tài “Nghiên cứu bài toán xác định collocation trong
Tiếng Việt” tập trung nghiên cứu một số phƣơng pháp thống kê điển hình (Tần suất, Kỳ
vọng và phƣơng sai, Kiểm thử t, Kiểm thử khi-bình phƣơng, Tỷ lệ likehood, Thông tin
tƣơng hỗ) để trích chọn collocation. Khóa luận đã tiến hành thử nghiệm xác định
collocation tiếng Việt cho kết quả tƣơng ứng với các phƣơng pháp kiểm thử thống kê nói
trên. Thông qua kết quả thử nghiệm, Khóa luận nhận thấy phƣơng pháp Kiểm thử khi-
bình phƣơng phù hợp nhất để xác định collocation trong tiếng Việt.

Mục lục
Lời mở đầu ............................................................................................................... 1
Chƣơng 1. TỔNG QUAN VỀ BÀI TOÁN XÁC ĐỊNH COLLOCATION ............... 3
1.1. Khái niệm collocation ................................................................................ 3
1.1.1. Định nghĩa collocation ....................................................................... 3
1.1.2. Đặc trƣng của collocation .................................................................. 4

Tài liệu tham khảo .................................................................................................. 50
Tài liệu Tiếng Việt ............................................................................................. 50
Tài liệu Tiếng Anh ............................................................................................. 50
Phụ lục ................................................................................................................... 53
1. Bảng phân phối t ...................................................................................... 53
2. Bảng phân phối .................................................................................. 54 Danh sách các bảng
Bảng 1. Tìm kiếm collocation dựa vào tần suất. ............................................................. 7
Bảng 2. Các mẫu từ loại dùng cho việc lọc collocation. ................................................. 8
Bảng 3. Tìm kiếm collocation: bộ lọc từ loại của Justeson và Katz. ............................... 9
Bảng 4. Các danh từ w xuất hiện thƣờng xuyên nhất trong các mẫu strong w và
powerful w ...................................................................................................... 10
Bảng 5. Tìm kiếm collocation dựa vào Kỳ vọng và phƣơng sai.................................... 15
Bảng 6. Xếp hạng 10 bigram xuất hiện với cùng tần suất là 20 với Kiểm thử t............. 19
Bảng 7. Kiểm thử giả thuyết để đo sự khác biệt giữa hai tập hợp: các từ xuất hiện có ý
nghĩa với powerful và strong. ......................................................................... 20
Bảng 8. Bảng 2x2 chỉ ra sự phụ thuộc của sự xuất hiện new và companies. ................. 22
Bảng 9. Tƣơng ứng của vache và cow trong hai kho ngữ liệu đã sắp xếp tƣơng ứng. ... 25
Bảng 10. Phép thử cho sự độc lập của các từ trong các kho ngữ liệu khác nhau, sử dụng
. .................................................................................................................. 25
Bảng 11. Cách tính toán giá trị likelihood của Dunning. ................................................ 27
Bảng 12. Các bigram có chứa powerful với hạng cao nhất theo phép thử likelihood ratio
của Dunning. .................................................................................................. 28
Bảng 13. Phép thử tỉ lệ tần suất của Damerau. ............................................................... 30
Bảng 14. Tìm kiếm collocation dựa vào thông tin tƣơng hỗ. .......................................... 31
Bảng 15. Sự phù hợp của chambre và house, communes và house trong kho ngữ liệu. .. 32
Bảng 16. Thông tin tƣơng hỗ từ các dữ liệu rải rác. ....................................................... 33
Bảng 17. Các định nghĩa khác nhau về thông tin tƣơng hỗ. ............................................ 35

Khóa luận gồm bốn chƣơng, nội dung đƣợc mô tả sơ bộ nhƣ sau:
Chƣơng 1. Tổng quan về bài toán xác định collocation giới thiệu khái niệm
collocation, đặc trƣng của collocation. Chƣơng này cũng nêu lên tầm quan
trọng cũng nhƣ ứng dụng của collocation trong lĩnh vực Xử lý ngôn ngữ tự
nhiên.
Chƣơng 2. Các phương pháp xác định collocation phân tích các phƣơng pháp
thống kê đang đƣợc sử dụng phổ biến để xác định collocation, một số đánh
giá ƣu nhƣợc điểm cũng nhƣ mức độ phù hợp của từng phƣơng pháp đối
với mỗi loại collocation và dữ liệu khác nhau.
Chƣơng 3. Collocation trong Tiếng Việt trình bày đặc điểm của Tiếng Việt,
khái niệm collocation trong Tiếng Việt và phát biểu Bài toán xác định
collocation trong Tiếng Việt.
Chƣơng 4. Thực nghiệm và đánh giá trình bày nội dung thử nghiệm sử dụng
các phƣơng pháp Tần suất (Frequency), Kiểm thử t (t test), Kiểm thử khi-
bình phương (chi-square test), Tỉ lệ likelihood (Likelihood ratio), và Thông
2

tin tương hỗ (Mutual information) để xác định collocation trong tập văn bản
Tiếng Việt. Qua đó, Khóa luận cũng đánh giá mức độ phù hợp của các
phƣơng pháp đó trong Tiếng Việt.
Phần kết luận tổng kết và tóm lƣợc nội dung chính của khóa luận.
3

Chƣơng 1. TỔNG QUAN VỀ BÀI TOÁN XÁC ĐỊNH
COLLOCATION
1.1. Khái niệm collocation
1.1.1. Định nghĩa collocation
Ngôn ngữ tự nhiên là một hệ thống giao tiếp mở và rất mềm dẻo. Con ngƣời thƣờng
tự do truyền đạt nội dung họ muốn bằng những dạng ngôn ngữ khác nhau (nói, viết) và
bằng những thứ ngôn ngữ khác nhau. Mỗi thứ tiếng trên thế giới đều có những đặc trƣng

kỳ một sự biến thể nào về cú pháp hoặc ngữ nghĩa đối với collocation.
b. Tính “phụ thuộc lĩnh vực” (Domain-dependent): việc xử lý văn bản
trong một lĩnh vực đòi hỏi sự hiểu biết về các thuật ngữ có liên quan và
các collocation trong lĩnh vực đó.
c. Tính “lặp lại” (Recurrent): các collocation là sự kết hợp từ đƣợc lặp lại
thƣờng xuyên trong ngữ cảnh xác định.
d. Tính “cụm từ cố kết” (Cohesive lexical cluster): đặc trƣng này đƣợc hiểu
nhƣ là sự xuất hiện của một hay một vài từ thƣờng bao hàm sự xuất hiện
của một collocation chứa nó.
1.2. Collocation trong các ứng dụng Xử lý ngôn ngữ tự nhiên
Collocation có ích trong nhiều ứng dụng Xử lý ngôn ngữ tự nhiên, ví dụ nhƣ sinh
ngôn ngữ tự nhiên, dịch máy, tóm tắt văn bản và xây dựng từ điển... Chính vì tầm quan
trọng của collocation, nên ngƣời ta đặt ra một vấn đề là làm thế nào để xác định
collocation.
Bài toán xác định collocation (hay còn gọi là Bài toán trích chọn collocation –
Collocation extraction) đƣợc phát biểu nhƣ sau “Xác định collocation là việc sử dụng
máy tính để trích chọn ra các collocation một cách tự động từ một kho ngữ liệu (copus)”.
Howarth và Nasi [16] cho rằng hầu hết trong các đoạn văn bản đều có chứa ít nhất
một collocation.
5

Sinh ngôn ngữ tự nhiên (Natural language generation) là việc tạo câu hoặc văn bản
từ một trình diễn phi ngôn ngữ. Có thể nhìn nhận việc phân tích ngôn ngữ là dịch từ ngôn
ngữ tự nhiên sang một kiểu trình diễn có ý nghĩa khác. Vì vậy, cần xem xét việc sinh
ngôn ngữ (language generation) nhƣ là phép dịch ngƣợc lại từ một trình diễn có ý nghĩa
sang ngôn ngữ tự nhiên. Việc phân tích một bài luận khó hơn việc phân tích các câu riêng
lẻ, việc sinh ra văn bản cũng khó hơn nhiều việc sinh ra chuỗi các câu độc lập. Để có một
văn bản dễ hiểu, phải dựa vào các nguyên tắc sắp xếp từ và câu theo đặc trƣng riêng của
mỗi loại ngôn ngữ [22].
Dịch tự động (Machine translation) đƣợc xem nhƣ là một trong những công việc khó

1999) [13][20] và sự phù hợp của chúng trong việc xác định collocation (Krenn & Evert,
2001) [18] đã đƣợc thảo luận rộng rãi trong lĩnh vực ngôn ngữ học. Độ đo đƣợc lựa chọn
sẽ gán cho mỗi cặp từ một điểm số để đánh giá sự kết hợp từ. Điểm số này đƣợc tính toán
dựa nhiều vào tần suất xuất hiện từ.
Trong khi các số đo về sự kết hợp có giá trị thống kê trong việc phát hiện
collocation, cần chú ý rằng có vài công việc cần làm với các đặc trƣng của ngôn ngữ. Vì
thế, việc nghiên cứu, lựa chọn, tiến hành một phép đo phải đƣợc kết hợp chặt chẽ với các
tiêu chuẩn về ngôn ngữ trong việc phát hiện collocation.
Chƣơng này sẽ trình bày một số phƣơng pháp thống kê để xác định collocation, đó
là: Frequency – tần suất, Mean and variance - dựa vào Kỳ vọng và phƣơng sai của
khoảng cách giữa từ trung tâm và việc sắp xếp từ, Hypothesis testing – kiểm thử Giả
thuyết, Likelihood ratio – Tỷ lệ likelihood, và Mutual information – thông tin tƣơng hỗ.
Kho ngữ liệu (corpus) đƣợc sử dụng trong các ví dụ minh họa là các ấn phẩm của tờ
New York Times (từ tháng 8 đến tháng 11 năm 1990). Kho ngữ liệu này có 115 MB dữ
liệu văn bản và khoảng 14 triệu từ. Thông thƣờng, cả những cụm từ cố định hay không cố
định đều có thể là collocation [20].
7

2.1. Phƣơng pháp Tần suất (Frequency)
Phƣơng pháp đơn giản nhất để tìm kiếm collocation trong một tập văn bản là đếm số
lần xuất hiện các từ. Nếu hai từ cùng xuất hiện với nhau nhiều, thì đó là dấu hiệu cho thấy
sự kết hợp của chúng mang một chức năng đặc biệt.
Bảng 1 chỉ ra các bigram xuất hiện nhiều nhất trong copus và tần suất xuất hiện của
chúng. Ngoại trừ New York, tất cả các biagram đều là các cặp từ chức năng.

Bảng 1. Tìm kiếm collocation dựa vào tần suất.
C(.) là tần suất của một từ trong kho ngữ liệu
Có một phƣơng pháp rất đơn giản để cải thiện các kết quả (Justeson & Katz 1995):
cho các cụm từ dự tuyển qua một bộ lọc từ loại [20]. Bộ lọc này sẽ chỉ cho đi qua những
mẫu có khả năng là một cụm từ (phrase). Justeson và Katz đã đƣa ra các mẫu trong Bảng

nhƣ thế này.
Cả strong tea và powerful tea đều không xuất hiện trong kho ngữ liệu ví dụ (New
York Times). Nhƣng nếu tìm kiếm trên kho ngữ liệu rộng hơn, sẽ thấy 799 lần xuất hiện
strong tea và 17 lần xuất hiện powerful tea, chứng tỏ rằng strong tea là cách dùng từ đúng
(việc tìm kiếm này đƣợc thực hiện trên AltaVista vào 28 tháng 3 năm 1998) [20].
Phƣơng pháp tìm kiếm collocation của Justeson và Katz đã chứng minh một điều
quan trọng: Một kỹ thuật định lƣợng đơn giản (trong trƣờng hợp này là bộ lọc tần suất)
11

kết hợp với một chút ít hiểu biết về ngôn ngữ học (về từ loại) trở thành một phƣơng pháp
khá hay.
Có thể sử dụng thêm danh sách từ dừng (là các từ có tần suất xuất hiện cao, nhƣng
không phải là động từ, danh từ hay tính từ...) để nâng cao hiệu quả của phƣơng pháp này.
2.2. Phƣơng pháp Kỳ vọng và Phƣơng sai (Mean & Variance)
Phƣơng pháp Tần suất làm việc khá hiệu quả với các cụm danh từ, và chỉ thực sự có
ích với các cụm từ cố định (fixed phrase). Tuy nhiên ở nhiều ngôn ngữ, có những
collocation bao gồm các từ đứng trong mối quan hệ mềm dẻo hơn với nhau. Phƣơng pháp
Kỳ vọng và phƣơng sai (Mean & Variance) [24] khắc phục đƣợc điều này bằng cách tính
toán khoảng cách giữa hai từ và tìm ra chiều rộng của phân bổ khoảng cách ấy. Nếu phân
bổ hẹp (khoảng cách giữa cách đỉnh phân bổ nhỏ), thì có thể tìm ra collocation. Nhƣng
nếu phƣơng sai cao, các đỉnh đƣợc phân bổ ngẫu nhiên thì ko thể tìm đƣợc collocation.
Xét động từ knock và một trong những từ có tần suất xuất hiện cao nhất cùng với nó
là door. Đây là một số ví dụ lấy từ kho ngữ liệu:
a. She knocked on his door
b. They knocked at the door
c. 100 women knocked on Donaldon’s door
d. A man knocked on the metal front door
Các từ xuất hiện ở giữa knocked và door là khác nhau và khoảng cách giữa hai từ
thay đổi, cho nên phƣơng pháp Tần suất sẽ không sử dụng đƣợc ở đây. Nhƣng có đủ tính
hợp thức trong các mẫu để cho phép chúng ta xác định đƣợc rằng trong tình huống này,

Ví dụ, trung bình khoảng cách giữa knocked và door đƣợc tính nhƣ sau:

Câu:

Các bigram:

13 (Giả sử rằng Donaldson’s là 3 từ tố Donaldson, ’, s). Nếu door xuất hiện trƣớc
knocked thì khoảng cách giữa hai từ là một số âm. Ví dụ, nếu có the door that she
knocked on thì khoảng cách giữa knocked và door là -3.
Nếu khoảng cách là nhƣ nhau trong mọi trƣờng hợp thì phƣơng sai bằng 0. Nếu các
khoảng cách đƣợc phân bổ ngẫu nhiên (trong trƣờng hợp hai từ tình cờ xuất hiện cùng
nhau) thì giá trị phƣơng sai sẽ cao. Thƣờng thì độ lệch mẫu đƣợc sử dụng để
đánh giá sự biến đổi khoảng cách giữa hai từ. Độ lệch cho các ví dụ về knocked... door là:

Kỳ vọng và độ lệch mô tả phân bổ của các khoảng cách giữa hai từ trong một kho
ngữ liệu. Dựa vào điều này, ta có thể tìm ra collocation bằng cách tìm cặp từ có độ sai
lệch thấp nhất. Độ lệch thấp có nghĩa là hai từ gần như thƣờng xuất hiện ở cùng một
khoảng cách. Nếu độ lệch bằng 0 thì chứng tỏ hai từ xuất hiện chính xác ở cùng một
khoảng cách.
Hình 2 là ví dụ minh họa phân bổ về khoảng cách của một từ đối với một từ khác (từ
trung tâm).

2a. Vị trí của strong đối với opposition ( ) 14


pháp Kỳ vọng và phƣơng sai cho kết quả tìm kiếm collocation không khác mấy so với
phƣơng pháp Tần suất của Justeson và Katz.
Nếu trung bình lớn hơn rất nhiều so với 1.0 thì độ lệch thấp sẽ cho biết các cụm từ
nào đáng đƣợc quan tâm.
Ví dụ:
- Cặp từ previous / games (khoảng cách là 2) tƣơng ứng với các cụm từ nhƣ in the
previous 10 games hoặc in the previous 15 games...
- Cặp từ minus / points tƣơng ứng với các cụm từ nhƣ minus 2 percentage points,
minus 3 percentage points...
16

Độ lệch cao chỉ ra rằng hai từ không có mối quan hệ mật thiết với nhau. Điều này
đƣợc chứng minh qua nhóm thứ hai (gồm 4 cặp từ với giá trị phƣơng sai cao) trong ví dụ
ở Bảng 5.
Phƣơng pháp tìm kiếm collocation dựa vào giá trị kỳ vọng và phƣơng sai đƣợc trình
bày ở trên là của Smadja [24]. Smadja chỉ ra rằng phƣơng pháp của ông khá thành công
trong việc trích ra các thuật ngữ (với độ chính xác ƣớc lƣợng khoảng 80%) và trong việc
xác định các cụm từ phù hợp cho việc sinh ngôn ngữ – natural language generation
(Smadja và McKeown 1990 [23]).
Tuy nhiên, sự kết hợp knocked / door không phải collocation ta muốn phân loại –
mặc dù có thể nó rất có ích cho mục đích sinh văn bản (text generation). Phƣơng pháp
phát hiện collocation dựa vào phƣơng sai là một phƣơng pháp phù hợp nếu chúng ta
muốn tìm kiếm kiểu kết hợp từ nhƣ knocked... door.
2.3. Kiểm thử Giả thuyết (Hypothesis testing)
Trong thực tế, có nhiều sự kết hợp từ mà giá trị tần suất cao và phƣơng sai thấp.
Điều mà chúng ta cần tìm hiểu, đó là có hay không hai từ xuất hiện cùng với nhau thƣờng
xuyên mà không phải là sự xuất hiện ngẫu nhiên. Việc đánh giá một biến cố có xảy ra hay
không là một trong những bài toán kinh điển. Nó thƣờng bị ẩn đi trong các thuật ngữ của
Kiểm thử Giả thuyết (hypothesis testing). Có một giả thuyết đƣợc gọi là Giả thuyết Không
(null hypothesis) , chỉ xét sự kết hợp từ ngẫu nhiên. Ta sẽ tính toán xác suất p mà biến