Luận văn Thạc sĩ: Nghiên cứu mô hình ngôn ngữ N-Gram và ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu

Chia sẻ: Tran Tien Tung | Ngày: | Loại File: PDF | Số trang:71

Thêm vào BST

Báo xấu

170
lượt xem 31
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mời các bạn cùng tham khảo tài liệu Luận văn Thạc sĩ: Nghiên cứu mô hình ngôn ngữ N-Gram và ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu. Một trong những vấn đề có tính cấp thiết trong lĩnh vực xử lí ngôn ngữ tự nhiên tiếng Việt nói riêng và khoa học công nghệ trong đời sống xã hội nói chung.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ: Nghiên cứu mô hình ngôn ngữ N-Gram và ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT&TT CAO ĐỨC TƯ NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM VÀ ỨNG DỤNG TRONG BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT KHÔNG DẤU CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01 LUẬN VĂN THẠC SĨ : KHOA HỌC MÁY TÍNH Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT&TT CAO ĐỨC TƯ NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM VÀ ỨNG DỤNG TRONG BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT KHÔNG DẤU CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01 LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. VŨ TẤT THẮNG Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1 LỜI CAM ĐOAN Tôi xin cam đoan, toàn bộ nội dung liên quan tới đề tài đƣợc trình bày trong luận văn là bản thân tôi tự tìm hiểu và nghiên cứu, dƣới sự hƣớng dẫn khoa học của TS. Vũ Tất Thắng Viện công nghệ thông tin thuộc Viện Khoa học và Công nghệ Việt Nam. Các tài liệu, số liệu tham khảo đƣợc trích dẫn đầy đủ nguồn gốc. Tôi xin chịu trách nhiệm trƣớc pháp luật lời cam đoan của mình. Thái Nguyên, ngày 30 tháng 9 năm 2011 Học viên Cao Đức Tư Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2 LỜI CẢM ƠN Luận văn được hoàn thành bởi sự nỗ lực của bản thân, sự giúp đỡ tận tình của các thầy cô trường Đại học công nghệ thông tin và truyền thông thuộc Đại học Thái Nguyên, thầy cô Viện công nghệ thông tin thuộc Viện Khoa học và Công nghệ Việt Nam.Đã tận tình chỉ dạy, giúp đỡ em trong cả quá trình học tập và hoàn thành luận văn. Xin bày tỏ lòng biết ơn sâu sắc đến TS. Vũ Tất Thắng Viện công nghệ thông tin thuộc Viện Khoa học và Công nghệ Việt Nam, người đã tận tình chỉ dẫn tôi trong suốt quá trình xây dựng đề cương và hoàn thành luận văn. Xin cảm ơn các anh chị em trong lớp cao học K8 đã giúp đỡ, đóng góp ý kiến chia sẽ những kinh nghiệm học tập, nghiên cứu trong suốt khóa học. Mặc dù đã cố gắng hết sức để hoàn thành luận văn , song không thể tránh khỏi sai sót. Xin kính mong nhận được nhận xét và sự đóng góp của qu ý Thầy Cô và bạn bè. Thái Nguyên, ngày 30 tháng 9 năm 2011 Học viên Cao Đức Tư Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3 MỤC LỤC 1 CHƢƠNG 1: GIỚI THIỆU CHUNG ............................................................. 5 1.1.Đặt vấn đề: ............................................................................................ 5 1.2.Mục tiêu: ............................................................................................... 7 1.3.Cấu trúc của luận văn: ........................................................................... 7 CHƢƠNG 2: MÔ HÌNH NGÔN NGỮ N-GRAM .......................................... 8 2.1.Giới thiệu chung .................................................................................... 8 2.2.Công thức tính “xác suất thô” ................................................................ 9 2.3.Vần đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram.................. 10 2.4.Các phƣơng pháp làm mịn ................................................................... 11 2.5.Kỹ thuật làm giảm kích thƣớc dữ liệu:................................................. 19 2.6.Độ đo .................................................................................................. 23 2.7.Tổng kết chƣơng ................................................................................. 23 CHƢƠNG 3: XÂY DỰNG N-GRAM CHO TIẾNG VIỆT .......................... 27 3.1.Giới thiệu ............................................................................................ 27 3.2.Công cụ tách từ cho tiếng Việt - vnTokenizer.................................. 3427 3.3.Bộ công cụ SRILM ............................................................................. 35 3.4.Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện......................... 39 3.5.Phƣơng pháp tách câu, tách từ, gán nhãn từ loại và phân tích cú pháp. .............................................................................................................. 3340 3.6.Dữ liệu huấn luyện .............................................................................. 40 3.7.Kết quả xây dựng mô hình................................................................... 40 3.8.Tần số của tần số ................................................................................. 49 3.9.Cut-off (loại bỏ) .................................................................................. 52 3.10.Các phƣơng pháp làm mịn ................................................................. 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4 3.11.Tổng kết chƣơng ............................................................................... 55 CHƢƠNG 4: ỨNG DỤNG N-GRAM TRONG BÀI TOÁN ........................ 56 THÊM DẤU TIẾNG VIỆT .......................................................................... 56 4.1. Bài toán thêm dấu tiếng Việt .............................................................. 56 4.2. Các phƣơng pháp đánh giá kết quả thêm dấu:..................................... 57 4.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có: ........................... 59 4.4. Đề xuất hệ thống: ............................................................................... 63 4.5. Thử nghiệm hệ thống: ........................................................................ 66 CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI .... 6760 5.1. Các kết quả đạt đƣợc: ..................................................................... 6760 5.2.Hạn chế và hƣớng phát triển của đề tài: ........................................... 6760 TÀI LIỆU THAM KHẢO ............................................................................ 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5 DANH MỤC CÁC KÝ HIỆU VIẾT TẮT Viết tắt Diễn giải Ý nghĩa ACL Association for Computational Hiệp hội ngôn ngữ học tính toán Linguistics SMS Short Message Services Dịch vụ tin nhắn SRI Stanford Research Institute học viện nghiên cứu sờ ten phoóc LM language Model Mô hình ngôn ngữ MM Maximum Mactching Khớp tối đa LRMM Left Right Max Matching tìm đoạn tƣơng ứng dài nhất tính từ trái/phải WFST Weighted finite-state Transducer Mạng chuyển dịch trạng thái có trọng số Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6 DANH MỤC HÌNH Hình 3-1. Quy trình tách từ .......................................................................... 34 Hình 3-2 Số lƣợng các cụm n-gram với âm tiết tăng kích thƣớc dữ liệu ....... 48 Hình 3-3: số lƣợng các cụm N-gram với từ khi tăng kích thƣớc dữ liệu ....... 49 Hình 3-4: số lƣợng các cụm Ngram (âm tiết) có tần số từ 1 đến 10 .............. 50 Hình 3-5. Số lƣợng các cụm Ngram (từ) có tần số từ 1 đến 10 ..................... 51 Hình 4-1. Sự trùng khớp của các bản dịch máy với bản dịch mẫu ............ 5158 Hình 4-2. Lƣu đồ thực hiện mô hình ứng dụng trong VietPad ...................... 60 Hình 4-3. Lƣu đồ thực hiện của mô hình N-gram ......................................... 55 Hình 4-4. Lƣu đồ thực hiện của mô hình đề xuất ...................................... 6356 Hình 4.5. Mô hình test thêm dấu đề xuất. ................................................. 6659 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7 DANH MỤC BẢNG Bảng 3 -1. Số lƣợng các cụm n-gram trong văn bản huấn luyện với âm tiết . 48 Bảng 3-2: Số lƣợng các cụm N-gram trong văn bản huấn luyện với từ ..... 4942 Bảng 3-3: Tần số của tần số các cụm N-gram áp dụng cho âm tiết ........... 5043 Bảng 3-4. Tần số của tần số các cụm Ngram với từ ...................................... 51 Bảng 3-5: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết ................................................................................................................. 4552 Bảng 3-6: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ ......... 53 Bảng 3-7: Độ hỗn loạn thông tin của các phƣơng pháp làm mịn cho âm tiết ................................................................................................................. 5447 Bảng 3-8: Độ hỗn loạn thông tin của các phƣơng pháp làm mịn cho từ .... 5447 MỞ ĐẦU 1. Lý do chọn đề tài: Trong lĩnh vực xử lí ngôn ngữ tự nhiên, sử dụng các mô hình ngôn ngữ sẽ giúp giới hạn không gian tìm kiếm để có các giải pháp tốt nhất có thể có trong khoảng thời gian ngắn. Chúng ta cần ƣớc lƣợng độ hợp lý của câu văn đƣợc đƣa ra trong ngôn ngữ thực tế. Trong thực tế, chúng ta có thể thực hiện từng phần, mỗi phần là một chuỗi các từ. Vì ngôn ngữ thực ra chỉ đƣợc học từ sự quan sát và vì chúng ta không bao giờ quan sát hết đƣợc ngôn ngữ tự nhiên để có thể xem xét tất cả các câu có thể xảy ra. Hiện tại, chúng ta có thể dễ dàng tìm thấy ngày càng nhiều những hệ thống dịch tự động miễn phí trên mạng nhƣ: Systran, Reverso, WorldLingo, IBM translator… Những hệ thống này cho phép dịch tự động các văn bản với một cặp ngôn ngữ chọn trƣớc (ví dụ: dịch một văn bản giữa tiếng Anh và tiếng Pháp, hoặc tiếng Anh và tiếng Việt). Tuy nhiên, chất lƣợng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8 dịch là vấn đề mà ngƣời sử dụng quan tâm vì đa số các hệ thống dịch tự động hiện nay có chất lƣợng khá thấp. Ví dụ, để dịch văn bản giữa tiếng Việt và tiếng Anh chúng ta có thể chọn sử dụng hệ thống dịch của Google nhƣng chất lƣợng dịch theo chiều Việt-Anh là thấp so với chiều dịch Anh-Việt, và đặt biệt thấp cho dịch Việt-Anh với văn bản đầu vào là tiếng Việt không dấu. Vấn đề đặt ra là, làm sao để chuẩn hóa văn bản đầu vào cho hệ thống dịch. Ở đó thêm dấu, hay chuẩn hóa dấu văn bản là một vấn đề rất quan trọng. Từ những vấn đề trên cũng nhƣ những kiến thức đã đƣợc học tôi lựa chọn đề tài: “Nghiên cứu mô hình Ngôn ngữ N-gram và ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu”, một trong những vấn đề có tính cấp thiết trong lĩnh vực xử lí ngôn ngữ tự nhiên tiếng Việt nói riêng và khoa học công nghệ trong đời sống xã hội nói chung. 2. Mục đích và nhiệm vụ:  Mục tiêu Về học thuật: Đề tài này tập trung vào việc ứng dụng một số phƣơng pháp tách từ, tiếng, phƣơng pháp làm mịn trong mô hình ngôn ngữ N-gram nhằm tăng hiệu quả thêm dấu cho tiếng Việt không dấu. Về phát triển và triển khai ứng dụng: Kết quả của đề tài sẽ ứng dụng trong việc hỗ trợ trong việcthêm dấu cho tiếng Việt không dấu.  Nhiệm vụ - Nghiên cứu các vấn đề khi xây dựng mô hình ngôn ngữ N-gram - Nghiên cứu các phƣơng pháp làm mịn trong mô hình ngôn ngữ N- gram. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9 - Nghiên cứu các kỹ thuật làm giảm kích thƣớc dữ liệu. 3. Phƣơng pháp nghiên cứu: Nghiên cứu N-gram thông qua tài liệu về cơ sở thống kê của phƣơng pháp xử lý ngôn ngữ tự nhiên và cơ sở của nó. Nghiên cứu phƣơng pháp xác định ngôn ngữ văn bản thực tế đƣợc các chƣơng trình thêm dấu tự động sử dụng. Tìm hiểu, vận dụng và kế thừa các thuật tuán và quy trình đã công bố kết quả. Áp dụng mô hình ngôn ngữ cho bài toán thêm dấu, có đối sánh với kết quả của các phƣơng pháp thêm dấu tự động khác. 4. Đối tƣợng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Nghiên cứu về mô hình ngôn ngữ N-gram, và các kỹ thuật liên quan tới việc làm trơn hóa phân bố xác suất của mô hình. - Phạm vi nghiên cứu: Nghiên cứu về mô hình ngôn ngữ N gram, và ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu sử dụng mô hình ngôn ngữ N-gram. 5. Ý nghĩa khoa học của luận văn.  Ý nghĩa khoa học - Trình bày các kiến thức toán học cơ bản về mô hình ngôn ngữ N-gram , lý thuyết độ phức tạp của thuật toán. - Trình bày các phƣơng pháp làm mịn trong mô hình N-gram.  Ý nghĩa thực tiễn Cài đặt hoàn chỉnh chƣơng trình thêm dấu cho tiếng Việt không dấu Đƣa ra kết quả so sánh với những phần mềm đã có. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10 6. Bố cục của luận văn Mở đầu 1. Lý do chọn đề tài. 2. Mục đích và nhiệm vụ. 3. Phƣơng pháp nghiên cứu. 4. Đối tƣợng và phạm vi nghiên cứu. 5. Ý nghĩa khoa học và thực tiễn của luận văn Chƣơng 1.Giới thiệu chung 1.1. Đặt vấn đề 1.2. Mục tiêu 13. Cấu trúc Chƣơng 2. Mô hình ngôn ngữ N-gram 2.1.Giới thiệu chung 2.2.Vấn đề công thức tính “xác suất thô”. 2.3.Vấn đề khi xây dựng mô hình ngôn ngữ N-gram. 2.4.Các phƣơng pháp làm min. 2.5.Kỹ thuật làm giảm kích thƣớc dữ liệu. 2.6.Độ đo 2.7.Tổng kết chƣơng Chƣơng 3.Xây dựngN-gram cho tiếng Việt 3.1. Giới thiệu. 3.2. Công cụ tách từ cho tiếng việt-VnTokenizer. 3.3. Bộ công cụ SRILM. 3.4. Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện. 3.5. Phƣơng pháp tách câu, tách từ, gán nhãn từ loại và phân tích cú pháp. 3.6. Dữ liệu huấn luyện. 3.7. Kết quả xây dựng mô hình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11 3.8. Tần số của tần số 3.9. Cut-of ( loại bỏ) 3.10. Các phƣơng pháp làm mịn. 3.11. Tổng kết chƣơng Chƣơng 4.Ứng dụng N-gram trong bài toán thêm dấu tiếng Việt 4.1.Bài toán thêm dấu tiếng Việt. 4.2. Các phƣơng pháp đánh giá kết quả thêm dấu. 4.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có. 4.4. Đề xuất hệ thống. 4.5. Thử nghiệm hệ thống. Chƣơng 5: Kết luận và hƣớng phát triển của đề tài 5.1. Các kết quả đạt đƣợc: 5.2.Hạn chế và hƣớng phát triển của đề tài: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12 CHƢƠNG 1: GIỚI THIỆU CHUNG 1.1.Đặt vấn đề: Ngôn ngữ tự nhiên là những ngôn ngữ đƣợc con ngƣời sử dụng trong các giao tiếp hàng ngày: nghe, nói, đọc, viết[13]. Mặc dù con ngƣời có thể dễ dàng hiểu và học các ngôn ngữ tự nhiên, việc làm cho máy hiểu đƣợc ngôn ngữ tự nhiên không phải là chuyện dễ dàng. Sở dĩ có khó khăn là do ngôn ngữ tự nhiên có các bộ luật, cấu trúc ngữ pháp phong phú hơn nhiều các ngôn ngữ máy tính, hơn nữa để hiểu đúng nội dung các giao tiếp, văn bản trong ngôn ngữ tự nhiên cần phải nắm đƣợc ngữ cảnh của nội dung đó. Do vậy, để có thể xây dựng đƣợc một bộ ngữ pháp, từ vựng hoàn chỉnh, chính xác để máy có thể hiểu ngôn ngữ tự nhiên là một việc rất tốn công sức và đòi hỏi ngƣời thực hiện phải có hiểu biết rất sâu sắc về ngôn ngữ học. Mô hình ngôn ngữ là một phân bố xác suất trên các tập văn bản[8],[13]. Nói một cách đơn giản, mô hình ngôn ngữ có thể cho biết xác suất một câu (hoặc cụm từ) thuộc một ngôn ngữ là có xác suất sinh ra là bao nhiêu. Ví dụ 1.1: Khi áp dụng mô hình ngôn ngữ cho tiếng Việt, ta có thể có một kết quả có dạng tƣơng tự nhƣ sau: P[“ngày mai trời sẽ mưa”] ~ 0.001 P[“trời mưa sẽ mai ngày”] ~ 0 Với các vấn đề của xử lí ngôn ngữ tự nhiên, việc sử dụng các mô hình ngôn ngữ để xác định xác suất xẩy ra nhƣ trên sẽ giúp giới hạn lại không gian tìm kiếm, để có thể tìm ra các giải pháp tốt nhất trong một khoảng thời gian đủ ngắn. Cốt lõi nhất của các phƣơng pháp để máy tính xử lý ngôn ngữ tự nhiên chính là việc xây dựng mô hình ngôn ngữ, mà ngày nay ngƣời ta thƣờng dùng ở dạng mô hình thống kê. Các phƣơng pháp xử lý ngôn ngữ tự nhiên dựa trên thống kê không nhằm tới việc con ngƣời tự xây dựng mô hình ngữ pháp mà lập chƣơng trình cho máy tính có thể “học” nhờ vào việc thống kê các từ và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13 cụm từ có trong các văn bản. Trong các mô hình ngôn ngữ tiếng nói, thì N- gram là một trong số những mô hình đƣợc sử dụng rộng rãi nhất. Mục tiêu của luận văn, là nghiên cứu nắm bắt đƣợc những vấn đề cốt lõi của mô hình ngôn ngữ N-gram, đặc biệt là các kỹ thuật làm trơn các phân bố xác suất thống kê (Smoothing techniques), nhằm nâng cao chất lƣợng về lƣợng giá xác suất bởi mô hình. Ngoài ra, luận văn hƣớng tới việc đƣa ra một ứng dụng cụ thể của mô hình này cho tiếng Việt, mà cụ thể là bài toán thêm dấu cho văn bản tiếng Việt không dấu. Dấu là một thành phần không thể thiếu và mang những thông tin, nội dung quan trọng của văn bản tiếng Việt. Chúng không là mẫu tự mà là một phần của mẫu tự. Tuy nhiên có rất nhiều trƣờng hợp mà ngƣời sử dụng đã loại bỏ các thành phần này, chẳng hạn trong các tin nhắn SMS qua điện thoại, các liên lạc kiểu thƣ điện tử, chat, … Khái niệm dấu ở đây không chỉ giới hạn với 5 ký hiệu về dấu thanh điệu đƣợc thể hiện trong chữ Việt để thể hiện cho sáu loại thanh điệu khác nhau: ngang, huyền, ngã, hỏi, sắc, và nặng. Mà hơn thế nữa, nó còn bao gồm các nhiều dấu phụ trợ cho 5 nguyên âm không dấu: a, i, u, e, o để tạo lập các ký tự đủ đa dạng cho việc ký âm các nguyên âm tiếng Việt, a ă â e ê i o ô ơ u ƣ y. Ngoài ra chữ Việt có thêm dấu gạch trên đầu d để ký âm cho một phụ âm khác là đ. Trong đa số trƣờng hợp, ngƣời đọc văn bản phải nội suy đƣợc dấu tƣơng ứng của các đoạn văn không dấu, cố gắng hiểu đƣợc ý nghĩa chuyển tải của mỗi đoạn văn dựa theo ngữ cảnh của cả văn bản. Đối với các hệ thống xử lí văn bản tự động thì đây chính là một nhập nhằng rất khó giải quyết, đặc biệt là các hệ thống phân tích cú pháp, hệ thống tìm kiếm, hệ thống dịch tự động, … Đề tài này sẽ tập trung vào một phƣơng pháp cơ bản là sử dụng mô hình ngôn ngữ N-gram để tính toán các khả năng thêm giấu với xác suất cao nhất, giúp máy tính tự động thêm dấu cho các văn bản không dấu tiếng Việt. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14 1.2.Mục tiêu: Mô hình ngôn ngữ đƣợc áp dụng trong rất nhiều lĩnh vực của xử lý ngôn ngữ tự nhiên nhƣ: kiểm lỗi chính tả, dịch máy hay phân đoạn từ... Chính vì vậy, nghiên cứu mô hình ngôn ngữ chính là tiền đề để nghiên cứu các lĩnh vực tiếp theo. Mục tiêu chính của luận văn là tìm hiểu lý thuyết về mô hình N-gram và các vấn đề trong đó, đặc biệt là các phƣơng pháp làm mịn. Về thực nghiệm, luận văn có sử dụng bộ công cụ SRILM để xây dựng mô hình ngôn ngữ cho tiếng Việt với các phƣơng pháp làm mịn khác nhau. Bằng việc áp dụng các mô hình ngôn ngữ khác nhau đó vào bài toán thêm dấu cho tiếng Việt không dấu, và chỉ ra đƣợc phƣơng pháp làm mịn nào là tốt nhất khi áp dụng cho mô hình ngôn ngữ tiếng Việt. 1.3.Cấu trúc của luận văn: Sau phần giới thiệu chung và mục tiêu nghiên cứu đƣợc trình bày ở Chƣơng 1, phần còn lại của Luận văn đƣợc cấu trúc nhƣ sau: Chƣơng 2: Nghiên cứu các vấn đề của mô hình ngôn ngữ N-gram, các sự cố gặp phải và cách khắc phục trong việc xây dựng tối ƣu mô hình N-gram. Chƣơng 3: Luận văn tập trung vào việc mô tả thực nghiệm, bao gồm công việc xây dựng và cài đặt những chƣơng trình hỗ trợ việc xây dựng đƣợc mô hình ngôn ngữ. và các kết quả đạt đƣợc. Chƣơng 4: Tập trung vào việc áp dụng mô hình ngôn ngữ trong bài toán thêm dấu cho tiếng Việt không dấu. Chƣơng 5: Tổng kết những gì luận văn đã đạt đƣợc và đƣa ra kế hoạch nghiên cứu trong tƣơng lai. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15 CHƢƠNG 2: MÔ HÌNH NGÔN NGỮ N-GRAM 2.1.Giới thiệu chung Mô hình ngôn ngữ thống kê cho phép gán (ƣớc lƣợng) xác suất cho một chuỗi m phần tử (thƣờng là từ) P(w1w2…wm) tức là cho phép dự đoán khả năng một chuỗi từ xuất hiện trong ngôn ngữ đó. Theo công thức Bayes: P(AB) = P(B|A) * P(A), thì ta dễ dàng suy ra đƣợc. P(w1w2…wm) = P(w1) * P(w2|w1) * P(w3|w1w2) *…* P(wm|w1w2…wm-1). Theo công thức này thì bài toán tính xác suất của mỗi chuỗi từ quy về bài toán tính xác suất của một từ với điều kiện biết các từ trƣớc nó (có thể hiểu P(w1)=P(w1|start) là xác suất để w1 đứng đầu chuỗi hay nói cách khác ngƣời ta có thể đƣa thêm ký hiệu đầu dòng start vào mỗi chuỗi). Trong thực tế, dựa vào giả thuyết Markov ngƣời ta chỉ tính xác suất của một từ dựa vào nhiều nhất N từ xuất hiện liền trƣớc nó, và thông thƣờng N=0,1,2,3. Vì vậy nhiều ngƣời gọi mô hình ngôn ngữ là mô hình N-gram, trong đó N là số lƣợng từ ( bao gồm cả từ cần tính và các từ ngữ cảnh phía trƣớc). Theo công thức Bayes, mô hình ngôn ngữ cần phải có một lƣợng bộ nhớ vô cùng lớn để có thể lƣu hết xác suất của tất cả các chuỗi độ dài nhỏ hơn m. Rõ ràng, điều này là không thể khi m là độ dài của các văn bản ngôn ngữ tự nhiên (m có thể tiến tới vô cùng). Để có thể tính đƣợc xác suất của văn bản với lƣợng bộ nhớ chấp nhận đƣợc, ta sử dụng xấp xỉ Markov bậc n: P(wm|w1,w2,…, wm-1) = P(wm|wm-n,wn-m+1, …,wm-1). Nếu áp dụng xấp xỉ Markov, xác suất xuất hiện của một từ (wm) đƣợc coi nhƣ chỉ phụ thuộc vào n từ đứng liền trƣớc nó (wm-nwm-n+1…wm-1) chứ không phải phụ thuộc vào toàn bộ dãy từ đứng trƣớc (w1w2…wm-1). Nhƣ vậy, công thức tính xác suất văn bản đƣợc tính lại theo công thức: P(w1w2…wm) = P(w1) * P(w2|w1) * P(w3|w1w2) *… * P(wm-1|wm-n-1wm-n …wm-2)* P(wm|wm-nwm-n+1…wm-1). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16 Với công thức này, ta có thể xây dựng mô hình ngôn ngữ dựa trên việc thống kê các cụm có ít hơn n+1 từ. Các mô hình N-gram đƣợc hình dung thông qua ví dụ nhƣ sau: Ví dụ 2.1: Giả sử cần tính xác suất p=P(nên | không thầy đố mày làm):  Mô hình 1-Gram(unigram )tính xác suất của một từ mà không phụ thuộc vào các từ trƣớc nó, tức là không có ngữ cảnh: p=P(nên)  Mô hình 2-Gram(bigram ) tính xác suất của một từ dựa vào một từ trƣớc nó: p=P(nên|mày)  Mô hình 3-Gram(trigram ) tính xác suất của một từ dựa vào hai từ trƣớc nó: p=P(nên|mày làm) 2.2.Công thức tính “xác suất thô” Gọi C(wi-n+1...wi-1wi) là tần số xuất hiện của cụm wi-n+1...wi-1wi trong tập văn bản huấn luyện. Gọi P(wi|wi-n+1...wi-1) là xác suất wi đi sau cụm wi-n+1..wi-2wi-1. Ta có công thức tính xác suất nhƣ sau: C(wi-n+1...wi-1wi) P(wi|wi-n+1...wi-1) =  C(wi-n+1...wi-1w) w Dễ thấy,  C(wi-n+1..wi-1w) chính là tần số xuất hiện của cụm wi-n+1...wi-1 w trong văn bản huấn luyện. Do đó công thức trên viết lại thành: C(wi-n+1...wi-1wi) P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17 Tỉ lệ ở vế phải còn gọi là tỉ lệ tần số. Cách tính xác suất dựa vào tỉ lệ tần số còn gọi là ƣớc lƣợng xác suất cực đại. Cũng có thể gọi đây là công thức tính “xác suất thô” để phân biệt với các cách tính xác suất theo các thuật toán sẽ xét ở phần sau. 2.3.Vần đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram 2.3.1.Phân bố không đều Với mô hình N-gram đƣợc xây dựng theo công thức “xác suất thô”, sự phân bố không đều trong tập văn bản huấn luyện có thể dẫn đến các ƣớc lƣợng không chính xác. Khi các n-gram phân bố thƣa, nhiều cụm n-gram không xuất hiện hoặc chỉ có số lần xuất hiện nhỏ, việc ƣớc lƣợng xác suất để đánh giá các câu có chứa các cụm n-gram này sẽ cho ta một kết quả không tốt. Với V là kích thƣớc bộ từ vựng, ta sẽ có V cụm n-gram có thể sinh từ bộ từ vựng. Tuy nhiên, thực tế thì số cụm n-gram có nghĩa và thƣờng gặp chỉ chiếm rất ít. Ví dụ 2.2: Tiếng Việt có số lƣợng âm tiết nhiều hơn con số mà ở đây ta tạm đặt là 5000 âm tiết khác nhau, ta có tổng số cụm 3-gram có thể có là: 5.0003 = 125.000.000.000. Tuy nhiên, số cụm 3-gram thống kê đƣợc chỉ xấp xỉ 1.500.000. Nhƣ vậy sẽ có rất nhiều cụm 3-gram không xuất hiện hoặc chỉ xuất hiện rất ít nên khả năng rất dễ xẩy ra là nó không xuất hiện trong dữ liệu huấn luyện mô hình. Khi tính toán xác suất của một câu, có rất nhiều trƣờng hợp sẽ gặp cụm n-gram chƣa xuất hiện trong dữ liệu huấn luyện bao giờ. Điều này làm xác suất của cả câu bằng 0, trong khi câu đó có thể là một câu hoàn toàn đúng về mặt ngữ pháp và ngữ nghĩa. Đề khắc phục tình trạng này, ngƣời ta phải sử dụng một số phƣơng pháp “làm mịn” kết quả thống kê mà chúng ta sẽ đề cập ở phần 2.5. 2.3.2.Kích thƣớc bộ nhớ của mô hình ngôn ngữ Khi kích thƣớc tập văn bản huấn luyện lớn, số lƣợng các cụm n-gram và kích thƣớc của mô hình ngôn ngữ cũng rất lớn. Nó không những gây khó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18 khăn trong việc lƣu trữ mà còn làm tốc độ xử lý của mô hình ngôn ngữ giảm xuống do bộ nhớ của máy tính là hạn chế. Để xây dựng mô hình ngôn ngữ hiệu quả, chúng ta phải giảm kích thƣớc của mô hình ngôn ngữ mà vẫn đảm bảo độ chính xác. Vấn đề này sẽ đƣợc giải quyết ở phần 2.6 2.4.Các phƣơng pháp làm mịn Để khắc phục tình trạng các cụm n-gram phân bố ngƣời ta đã đƣa ra các phƣơng pháp “làm mịn” các kết quả thống kê nhằm đánh giá chính xác hơn (mịn hơn) xác suất của các cụm n-gram. Các phƣơng pháp “làm mịn” đánh giá lại xác suất của các cụm n-gram bằng cách: ● Gán cho các cụm n-gram có xác suất 0 (không xuất hiện trong tập huấn luyện) một giá trị khác 0. ● Thay đổi lại giá trị xác suất của các cụm n-gram có xác suất khác 0 khác (có xuất hiện khi thống kê) thành một giá trị phù hợp (tổng xác suất của tất cả các khả năng N-gram khác nhau phải đảm bảo là không đổi, với giá trị là 100%). Các phƣơng pháp làm mịn có thể đƣợc chia ra thành một số loại nhƣ sau: ● Chiết khấu (Discounting): giảm (lƣợng nhỏ) xác suất của các cụm n-gram có xác suất lớn hơn 0 để bù cho các cụm n-gram không xuất hiện trong tập huấn luyện. ● Truy hồi (Back-off) : tính toán xác suất các cụm n-gram không xuất hiện trong tập huấn luyện dựa vào các cụm n-gram thành phần có độ dài ngắn hơn và có xác suất lớn hơn 0 ● Nội suy (Interpolation): tính toán xác suất của tất cả các cụm n- gram dựa vào xác suất của các cụm n-gram ngắn hơn. 2.4.1.Các thuật toán chiết khấu (discounting) Vấn đề của các thuật toán chiết khấu là giảm xác suất của các cụm n- gram có xác suất lớn hơn 0 và bù cho các cụm N-gram chƣa từng xuất hiện trong tập huấn luyện[13]. Các thuật toán dạng này sẽ trực tiếp làm thay đổi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn