Đề tài Nghiên cứu bài toán xác định collocation trong tiếng việt

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Ệ 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 Cán bộ hƣớng dẫn: Th.S Trần Thị Oanh Cán bộ đồng hƣớng dẫn: CN. Nguyễn Minh Tuấn HÀ NỘI - 2009 Lời cảm ơn Trƣớc hết, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sƣ Tiến sỹ Hà Quang Thụy, Thạc sỹ Trần Thị Oanh và Cử nhân Nguyễn Minh Tuấn, những ngƣời đã tận tình quan tâm, chỉ bảo và hƣớng dẫn tôi trong suốt quá trình thực hiện Khóa luận tốt nghiệp. Tôi xin chân thành cảm ơn các thầy cô đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu tạ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 1.2. Collocation trong các ứng dụng Xử lý ngôn ngữ tự nhiên .......................... 4 Chƣơng 2. CÁC PHƢƠNG PHÁP XÁC ĐỊNH COLLOCATION ........................... 6 2.1. Phƣơng pháp Tần suất (Frequency) ............................................................ 7 2.2. Phƣơng pháp Kỳ vọng và Phƣơng sai (Mean & Variance) ....................... 11 2.3. Kiểm thử Giả thuyết (Hypothesis testing) ................................................ 16 2.3.1. Kiểm thử t (t test) ............................................................................. 17 2.3.2. Kiểm thử Giả thuyết để đo sự khác biệt giữa hai tập hợp (Hypothesis testing of differences)....................................................................... 19 2.4. Kiểm thử khi-bình phƣơng (Pearson’s chi-square test) ............................ 21 2.5. Các tỉ lệ likelihood (Likelihood ratios) ..................................................... 26 2.5.1. Tỉ lệ likelihood (Likelihood ratio) .................................................... 26 2.5.2. Các tỉ lệ tần suất tƣơng đối (Relative Frequency Ratios) .................. 29 2.6. Thông tin tƣơng hỗ MI (Mutual information) ........................................... 30 Chƣơng 3. COLLOCATION TRONG TIẾNG VIỆT ............................................. 36 3.1. Đặc điểm từ vựng Tiếng Việt ................................................................... 36 3.1.1. Đơn vị cấu tạo từ ............................................................................ 36 3.1.2. Phƣơng thức cấu tạo từ ................................................................... 36 3.1.3. Biến thể của từ ................................................................................ 37 3.1.4. Những quá trình diễn ra trong sự phát triển từ vựng Tiếng Việt ...... 38 3.2. Khái niệm collocation trong Tiếng Việt ................................................... 40 3.3. Bài toán xác định collocation trong Tiếng Việt ........................................ 41 Chƣơng 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ ........................................................ 44 4.1. Dữ liệu thực nghiệm ................................................................................ 44 4.1.1. Chuẩn bị dữ liệu ............................................................................... 44 4.1.2. Tiền xử lý dữ liệu ............................................................................. 44 4.2. Thiết kế thực nghiệm ............................................................................... 45 4.2.1. Phƣơng pháp thực nghiệm........................................................................ 45 4.3. Kết quả thực nghiệm và đánh giá kết quả ................................................. 46 Kết luận .................................................................................................................. 49 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 Bảng 18. Các collocation có giá trị khi-bình phƣơng cao nhất ....................................... 43 Bảng 19. Cấu hình phần cứng sử dụng trong thực nghiệm ............................................. 45 Bảng 20. Giá trị ngƣỡng cho các phƣơng pháp xác định collocation .............................. 46 Bảng 21. Đánh giá độ chính xác của các phƣơng pháp xác định collocation .................. 47 Bảng 22. Một số collocation thu đƣợc từ thực nghiệm ................................................... 48 Danh sách các hình Hình 1. Sử dụng cửa sổ collocation 3 từ để lấy đƣợc các bigram ở một khoảng cách. .. 12 Hình 2. Biểu đồ tần suất biểu diễn vị trí tƣơng đối của strong với các “từ trung tâm”: opposition, support, for. .................................................................................. 14 Hình 3. Phân loại cụm từ cố định Tiếng Việt. .............................................................. 41 1 Lời mở đầu 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 tự động, tóm tắt văn bản và xây dựng từ điển... [17] 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 các collocation trong kho ngữ liệu. Có nhiều phƣơng pháp để giải quyết bài toán xác định collocation, trong đó có phƣơng pháp xác định dựa vào thống kê. Phƣơng pháp thống kê sử dụng các kỹ thuật toán học khác nhau và các kho ngữ liệu lớn để mở rộng xấp xỉ các mô hình suy rộng về hiện tƣợng ngôn ngữ, dựa trên các ví dụ thực tế về các hiện tƣợng ngôn ngữ đƣợc cung cấp bởi kho ngữ liệu mà không bổ sung vào các thành phần tri thức khác. Khóa luận 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 về collocation, các phƣơng pháp xác định collocation từ các ngôn ngữ khác nhau và lựa chọn phƣơng pháp, thi hành chƣơng trình thực nghiệm để kiểm chứng tính khả thi của chúng trên kho ngữ liệu Tiếng Việt. 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 riêng về ngôn ngữ và những cách dùng từ cũng nhƣ kết hợp từ khác nhau. Cách kết hợp từ hay cách dùng từ là những cách nhìn khái quát nhất về khái niệm collocation. Collocation rất phổ biến trong ngôn ngữ tự nhiên và đƣợc gặp trong mọi tài liệu chuyên hoặc không chuyên. Khái niệm collocation là một khái niệm khó hiểu đối với những ngƣời không chuyên về ngôn ngữ học. Có rất nhiều cách khác nhau để định nghĩa collocation, tuy nhiên chƣa có một định nghĩa thật đầy đủ và chính xác, đặc biệt là khi không có một ranh giới rõ ràng phân biệt giữa collocation và các cụm từ đƣợc kết hợp ngẫu nhiên (cụm từ tự do) [17]. Một số tác giả trong lĩnh vực văn học và thống kê định nghĩa collocation nhƣ một cụm từ gồm hai hay nhiều từ thƣờng xuyên cùng xuất hiện theo một thói quen đặc biệt. Ví dụ, Choueka đã đƣa ra định nghĩa “Collocation là một chuỗi hai hay nhiều từ liên tiếp nhau, có các đặc trƣng về cú pháp và ngữ nghĩa, và ý nghĩa của nó không thể đƣợc rút ra từ nghĩa của các thành phần cấu tạo nên nó” hay cũng vậy “Collocation có thể đƣợc hiểu là sự kết hợp các từ (hoặc các nhóm từ) thƣờng xuyên đƣợc sử dụng cùng với nhau theo cách nói thông thƣờng” [20]. Theo Firth [17], collocation là sự sắp xếp từ theo thói quen hoặc theo phong tục (the habitual or customary places of the word). Benson và Morton [17] định nghĩa collocation là: sự kết hợp từ tùy ý và thƣờng tái diễn (an arbitrary and recurrent word combination). Theo Lin [19], collocation đƣợc định nghĩa là sự kết hợp từ theo thói quen. 4 Kết hợp các định nghĩa của nhiều nhà khoa học, có thể đƣa ra một định nghĩa chung nhất về collocation nhƣ sau. Định nghĩa: Collocation là một cụm từ gồm hai hay nhiều từ trở lên thƣờng đi liền với nhau theo một trật tự nhất định (theo cách nói của ngƣời bản xứ). 1.1.2. Đặc trƣng của collocation Smadja [24] đƣa ra bốn đặc trƣng của collocation có ích trong các ứng dụng Xử lý ngôn ngữ tự nhiên. a. Tính “độc đoán” (Arbitrary): điều này có nghĩa là không chấp nhận bất 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ó khăn nhất trong xử lý ngôn ngữ tự nhiên, và trong trí tuệ nhân tạo. Việc dịch đúng dƣờng nhƣ là không thể nếu không có những hiểu biết về văn bản. Theo Gitsaki [14], một collocation trong ngôn ngữ này khác với chính nó trong ngôn ngữ khác, vì thế việc dịch collocation là một việc không dễ. Thông tin về collocation cũng là chủ yếu trong các công việc tóm tắt văn bản (Text simplification task). Điều này đòi hỏi phải có những kỹ thuật để thay thế các từ khó bởi những từ đơn giản hơn. Không có hiểu biết về collocation và các ràng buộc liên quan thì có thể dẫn đến những văn bản không dùng đƣợc. Collocation cũng quan trọng trong lĩnh vực xây dựng từ điển (Computational lexicography). Chúng đƣợc sử dụng để mô tả một cách đầy đủ các mục từ vựng. Theo Richardson “đối với một phân tích từ điển chi tiết, chỉ các collocation có mặt trong từ điển mới cung cấp thêm các đặc điểm biểu diễn trực tiếp các mối quan hệ ngữ nghĩa trong các mục từ” [17]. Smith [25] xem xét các collocation để tìm ra các sự kiện liên quan đến thông tin ngày tháng và địa điểm trong văn bản không có cấu trúc. 6 Chƣơng 2. CÁC PHƢƠNG PHÁP XÁC ĐỊNH COLLOCATION Những năm gần đây, các phƣơng pháp thống kê đƣợc sử dụng nhiều để giải quyết các bài toán về ngôn ngữ tự nhiên, trong đó có Bài toán xác định collocation [20]. Trong ngôn ngữ học, có sự khác biệt lớn giữa các phép đo về sự kết hợp từ vựng đƣợc sử dụng trong việc phát hiện và trích ra (bán tự động) các collocation. Có 3 nhóm số đo sau [16]: a. Các số đo dựa vào tần suất (dựa hoàn toàn vào tần suất của sự đồng xuất hiện các từ). b. Các số đo dựa vào thông tin lý thuyết: ví dụ, thông tin tƣơng hỗ MI (mutual information), entropy. c. Các số đo dựa vào thống kê: ví dụ, chi-square ( ), t-test, log-likelihood, hệ số Dice. Các độ đo trên cùng những tính chất toán học (Dunning, 1993; Manning & Schütze, 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 & Ka