Luận văn thạc sĩ: Mô hình ngôn ngữ n-gram và ứng dụng sửa lỗi dấu thanh trong tiếng Việt

Luận văn thạc sĩ nghiên cứu mô hình ngôn ngữ n-gram cho tiếng Việt, ứng dụng hiệu quả trong sửa lỗi dấu thanh, nâng cao xử lý ngôn ngữ tự nhiên.

• Tác giả: Vũ Chí Hiếu
• Người hướng dẫn: TS. Vũ Tất Thắng
• Trường học: Đại học Công nghệ Thông tin & Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu mô hình ngôn ngữ n-gram cho tiếng Việt và ứng dụng sửa lỗi dấu thanh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: MÔ HÌNH NGÔN NGỮ N-GRAM
• 1.1. Giới thiệu chung
• 1.2. Công thức tính “xác suất thô”
• 1.3. Vấn đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram
• 1.4. Phân bố không đều
• 1.5. Kích thước bộ nhớ của mô hình ngôn ngữ
• 1.6. Các phương pháp làm mịn
• 1.6.1. Các thuật toán chiết khấu (discounting)
• 1.6.2. Phương pháp làm mịn Add-One
• 1.6.3. Phương pháp làm mịn Witten - Bell
• 1.6.4. Phương pháp làm mịn Good - Turing
• 1.6.5. Phương pháp truy hồi
• 1.6.6. Phương pháp nội suy
• 2. CHƯƠNG 2: XÂY DỰNG N-GRAM CHO TIẾNG VIỆT
• 2.1. Công cụ tách từ cho tiếng Việt - vnTokenizer
• 2.2. Bộ công cụ SRILM
• 2.3. Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện
• 2.4. 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
• 2.5. Gán nhãn từ loại
• 2.6. Phân tích cú pháp
• 2.7. Dữ liệu huấn luyện
• 2.8. Kết quả xây dựng mô hình
• 2.9. Số lượng các cụm N-gram với tiếng Việt dựa trên âm tiết
• 2.10. Số lượng các cụm N-gram với tiếng Việt dựa trên từ
• 2.11. Phân bố thống kê của tần số các cụm N-gram
• 2.12. Với âm tiết. Phương pháp loại bỏ (Cut-off)
• 2.13. Với âm tiết
• 2.14. Các phương pháp làm mịn
• 2.15. Với âm tiết
• 3. CHƯƠNG 3: ỨNG DỤNG N-GRAM TRONG BÀI TOÁN BÀI TOÁN SỬA LỖI DẤU THANH TRONG TIẾNG VIỆT
• 3.1. Bài toán sửa lỗi dấu thanh trong tiếng Việt
• 3.2. Phát biểu bài toán
• 3.3. Hướng giải quyết
• 3.4. Các hệ thống thêm dấu ứng dụng về N-gram đã có
• 3.5. Công cụ AMPad
• 3.6. Đề xuất hệ thống
• 3.7. Cài đặt thử nghiệm và đánh giá hệ thống
• HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI

Tóm tắt

I. Mô hình ngôn ngữ N gram

Mô hình ngôn ngữ N-gram là một trong những phương pháp phổ biến trong xử lý ngôn ngữ tự nhiên, cho phép ước lượng xác suất cho một chuỗi từ. Mô hình này dựa trên giả thuyết Markov, trong đó xác suất của một từ chỉ phụ thuộc vào n từ trước đó. Việc sử dụng mô hình N-gram giúp giảm thiểu kích thước bộ nhớ cần thiết để lưu trữ các xác suất, đồng thời vẫn đảm bảo độ chính xác trong việc dự đoán các chuỗi từ. Tuy nhiên, việc xây dựng mô hình này gặp phải một số khó khăn như phân bố không đều của các cụm từ trong tập huấn luyện và kích thước bộ nhớ lớn cần thiết cho các mô hình phức tạp hơn. Để khắc phục những vấn đề này, các phương pháp làm mịn được áp dụng nhằm cải thiện độ chính xác của các ước lượng xác suất.

1.1. Giới thiệu chung

Mô hình ngôn ngữ N-gram cho phép ước lượng xác suất cho một chuỗi từ bằng cách sử dụng các cụm từ có độ dài khác nhau. Mô hình này được xây dựng dựa trên các dữ liệu huấn luyện, trong đó xác suất của một từ được tính toán dựa trên các từ đứng trước nó. Việc áp dụng mô hình này trong tiếng Việt gặp phải một số thách thức do sự phong phú và đa dạng của ngôn ngữ. Đặc biệt, việc tính toán xác suất cho các cụm từ chưa xuất hiện trong tập huấn luyện có thể dẫn đến các kết quả không chính xác. Do đó, việc áp dụng các phương pháp làm mịn là cần thiết để cải thiện độ chính xác của mô hình.

1.2. Vấn đề khó khăn khi xây dựng mô hình

Một trong những vấn đề lớn nhất khi xây dựng mô hình ngôn ngữ N-gram là sự phân bố không đều của các cụm từ trong tập huấn luyện. Nhiều cụm từ có thể không xuất hiện hoặc chỉ xuất hiện với tần suất rất thấp, dẫn đến việc ước lượng xác suất không chính xác. Điều này đặc biệt quan trọng trong tiếng Việt, nơi mà số lượng âm tiết và từ vựng rất phong phú. Ngoài ra, kích thước bộ nhớ của mô hình cũng là một yếu tố cần xem xét, vì khi kích thước tập huấn luyện lớn, số lượng các cụm N-gram cũng tăng theo, gây khó khăn trong việc lưu trữ và xử lý.

II. Xây dựng N gram cho tiếng Việt

Việc xây dựng mô hình N-gram cho tiếng Việt đòi hỏi các công cụ và phương pháp tách từ hiệu quả. Công cụ tách từ như vnTokenizer và bộ công cụ SRILM được sử dụng để tạo ra các tập văn bản huấn luyện. Quá trình này bao gồm việc tách câu, tách từ, gán nhãn từ loại và phân tích cú pháp. Dữ liệu huấn luyện được xây dựng từ các văn bản tiếng Việt phong phú, giúp tạo ra các cụm N-gram với độ chính xác cao. Kết quả cho thấy số lượng các cụm N-gram với tiếng Việt dựa trên âm tiết và từ có sự khác biệt rõ rệt, điều này cho thấy sự cần thiết của việc áp dụng các phương pháp làm mịn để cải thiện độ chính xác của mô hình.

2.1. Công cụ tách từ cho tiếng Việt

Công cụ tách từ là một phần quan trọng trong việc xây dựng mô hình N-gram cho tiếng Việt. vnTokenizer là một trong những công cụ phổ biến, giúp tách từ một cách chính xác và hiệu quả. Việc tách từ chính xác sẽ ảnh hưởng trực tiếp đến chất lượng của các cụm N-gram được tạo ra. Ngoài ra, bộ công cụ SRILM cũng được sử dụng để hỗ trợ trong việc xây dựng các mô hình ngôn ngữ, giúp tối ưu hóa quá trình huấn luyện và đánh giá mô hình.

2.2. Dữ liệu huấn luyện

Dữ liệu huấn luyện là yếu tố quyết định đến chất lượng của mô hình N-gram. Việc thu thập và xử lý dữ liệu từ các nguồn khác nhau giúp tạo ra một tập dữ liệu phong phú và đa dạng. Số lượng các cụm N-gram với tiếng Việt dựa trên âm tiết và từ được thống kê, cho thấy sự phân bố tần suất của các cụm từ. Các phương pháp làm mịn được áp dụng để cải thiện độ chính xác của các ước lượng xác suất, từ đó nâng cao hiệu quả của mô hình trong việc xử lý ngôn ngữ tự nhiên.

III. Ứng dụng N gram trong bài toán sửa lỗi dấu thanh

Bài toán sửa lỗi dấu thanh trong tiếng Việt là một ứng dụng quan trọng của mô hình N-gram. Việc phát hiện và sửa lỗi dấu thanh giúp cải thiện độ chính xác trong việc xử lý văn bản tiếng Việt. Hệ thống đề xuất sử dụng mô hình N-gram để xác định xác suất của các từ có dấu và không có dấu, từ đó đưa ra các gợi ý sửa lỗi chính xác. Các công cụ như AMPad đã được phát triển để hỗ trợ trong việc thêm dấu cho văn bản tiếng Việt, cho thấy tính ứng dụng cao của mô hình N-gram trong thực tế.

3.1. Bài toán sửa lỗi dấu thanh

Bài toán sửa lỗi dấu thanh trong tiếng Việt là một thách thức lớn trong xử lý ngôn ngữ tự nhiên. Việc xác định đúng dấu thanh cho các từ có thể ảnh hưởng đến ý nghĩa của câu. Mô hình N-gram được áp dụng để ước lượng xác suất của các từ có dấu, từ đó giúp phát hiện và sửa lỗi một cách hiệu quả. Hệ thống cần phải được huấn luyện trên một tập dữ liệu phong phú để có thể đưa ra các gợi ý sửa lỗi chính xác.

3.2. Đề xuất hệ thống

Hệ thống sửa lỗi dấu thanh được đề xuất dựa trên mô hình N-gram có khả năng học từ các dữ liệu huấn luyện. Hệ thống này sử dụng các thuật toán để xác định xác suất của các từ có dấu và không có dấu, từ đó đưa ra các gợi ý sửa lỗi. Việc cài đặt thử nghiệm và đánh giá hệ thống cho thấy tính hiệu quả của mô hình trong việc cải thiện độ chính xác của văn bản tiếng Việt. Các kết quả thử nghiệm cho thấy mô hình có thể đạt được độ chính xác cao trong việc sửa lỗi dấu thanh.

Nội dung chính

## Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ xử lý ngôn ngữ tự nhiên (XLNN), việc xây dựng các mô hình ngôn ngữ chính xác và hiệu quả đóng vai trò then chốt. Luận văn tập trung nghiên cứu mô hình ngôn ngữ N-gram cho tiếng Việt, một ngôn ngữ đơn lập với đặc thù phức tạp về dấu thanh và cấu trúc từ vựng. Theo thống kê, kho dữ liệu huấn luyện gồm hơn 200MB văn bản chuẩn hóa, với khoảng 687.726 cụm N-gram âm tiết và 940.751 cụm N-gram từ được thu thập từ các trang báo mạng lớn như dantri.vn. Vấn đề chính được đặt ra là làm thế nào để mô hình N-gram có thể ước lượng xác suất chính xác cho các chuỗi từ trong tiếng Việt, đồng thời ứng dụng mô hình này để sửa lỗi dấu thanh – một thách thức lớn trong xử lý tiếng Việt.

Mục tiêu nghiên cứu bao gồm: (1) phân tích và xây dựng mô hình ngôn ngữ N-gram phù hợp với tiếng Việt; (2) áp dụng các kỹ thuật làm mịn (smoothing techniques) nhằm cải thiện độ chính xác của mô hình; (3) phát triển hệ thống tự động sửa lỗi dấu thanh dựa trên mô hình N-gram. Phạm vi nghiên cứu tập trung vào dữ liệu thu thập trong giai đoạn trước năm 2016, chủ yếu từ các nguồn báo mạng tiếng Việt. Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu quả xử lý ngôn ngữ tự nhiên cho tiếng Việt, góp phần phát triển các ứng dụng như nhận dạng tiếng nói, dịch máy, và soát lỗi chính tả với độ chính xác cao hơn.

## Cơ sở lý thuyết và phương pháp nghiên cứu

### Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng lý thuyết mô hình ngôn ngữ thống kê, trong đó mô hình N-gram là trọng tâm. Mô hình N-gram sử dụng giả thuyết Markov bậc n để ước lượng xác suất xuất hiện của một từ dựa trên n từ đứng trước đó, với n thường là 1 (Uni-gram), 2 (Bi-gram) hoặc 3 (Tri-gram). Các khái niệm chính bao gồm:

- **Xác suất thô (Maximum Likelihood Estimation)**: Ước lượng xác suất dựa trên tần số xuất hiện của các cụm từ trong tập huấn luyện.
- **Phương pháp làm mịn (Smoothing techniques)**: Bao gồm Add-One, Witten-Bell, Good-Turing, Kneser-Ney và các phương pháp truy hồi, nội suy nhằm khắc phục vấn đề phân bố không đều và các cụm N-gram chưa xuất hiện.
- **Kỹ thuật giảm kích thước mô hình**: Pruning (cắt bỏ), Quantization (đồng hóa), và Compression (nén) để tối ưu bộ nhớ và tốc độ xử lý.
- **Độ đo đánh giá mô hình**: Entropy, Perplexity và Error rate được sử dụng để đánh giá chất lượng mô hình.

### Phương pháp nghiên cứu

Nguồn dữ liệu chính là hơn 200MB văn bản tiếng Việt chuẩn hóa, thu thập từ các trang báo mạng lớn. Dữ liệu được xử lý qua các bước: lọc, chuẩn hóa, tách câu, tách từ bằng công cụ vnTokenizer với độ chính xác khoảng 94%, gán nhãn từ loại và phân tích cú pháp. Mô hình N-gram được xây dựng và huấn luyện sử dụng bộ công cụ SRILM, với cỡ mẫu lên đến gần 1 triệu cụm N-gram từ và âm tiết.

Phương pháp phân tích bao gồm thống kê tần số xuất hiện các cụm N-gram, áp dụng các thuật toán làm mịn để cải thiện ước lượng xác suất, và sử dụng các kỹ thuật pruning để giảm kích thước mô hình mà không làm giảm độ chính xác. Quá trình nghiên cứu kéo dài trong suốt khóa học thạc sĩ, với các giai đoạn thu thập dữ liệu, xây dựng mô hình, thử nghiệm và đánh giá kết quả.

## Kết quả nghiên cứu và thảo luận

### Những phát hiện chính

1. **Phân bố N-gram không đều**: Khoảng 5.000 âm tiết tiếng Việt tạo ra số lượng lớn các cụm 3-gram tiềm năng, nhưng chỉ có khoảng 1% trong số đó thực sự xuất hiện trong dữ liệu huấn luyện, dẫn đến nhiều cụm N-gram chưa từng xuất hiện gây khó khăn cho việc ước lượng xác suất.

2. **Hiệu quả của các phương pháp làm mịn**: Phương pháp Kneser-Ney cải tiến bởi Chen-Goodman cho kết quả độ hỗn loạn thông tin (Perplexity) thấp nhất, giảm khoảng 15-20% so với phương pháp Add-One truyền thống, cho thấy khả năng ước lượng xác suất chính xác hơn.

3. **Tác động của kỹ thuật pruning**: Áp dụng phương pháp cắt bỏ với ngưỡng k phù hợp (Uni-gram k=10, Bi-gram k=1, Tri-gram k=5) giúp giảm kích thước mô hình đến 40% mà không làm tăng đáng kể độ hỗn loạn thông tin, cải thiện tốc độ xử lý.

4. **Ứng dụng sửa lỗi dấu thanh**: Hệ thống sửa lỗi dấu thanh dựa trên mô hình N-gram đạt tỉ lệ lỗi thấp hơn 5% trên tập kiểm thử, vượt trội so với các hệ thống trước đó, đặc biệt hiệu quả với các văn bản đầu vào không dấu hoặc có dấu xen kẽ.

### Thảo luận kết quả

Nguyên nhân chính của phân bố không đều là đặc thù ngôn ngữ tiếng Việt với số lượng âm tiết lớn và cấu trúc từ phức tạp. Việc áp dụng các kỹ thuật làm mịn như Kneser-Ney giúp khắc phục vấn đề này bằng cách tận dụng thông tin từ các cụm N-gram ngắn hơn, cải thiện độ chính xác ước lượng xác suất. Kết quả này phù hợp với các nghiên cứu trong lĩnh vực xử lý ngôn ngữ tự nhiên cho các ngôn ngữ đơn lập khác.

Kỹ thuật pruning không chỉ giảm kích thước mô hình mà còn loại bỏ các cụm N-gram ít ý nghĩa hoặc lỗi ngữ pháp, từ đó nâng cao hiệu quả mô hình. Dữ liệu có thể được trình bày qua biểu đồ thể hiện mối quan hệ giữa ngưỡng cắt bỏ và độ hỗn loạn thông tin, minh họa sự cân bằng giữa kích thước mô hình và độ chính xác.

Ứng dụng sửa lỗi dấu thanh chứng minh tính khả thi và hiệu quả của mô hình N-gram trong thực tế, góp phần nâng cao chất lượng các hệ thống xử lý tiếng Việt, đặc biệt trong các ứng dụng nhập liệu và dịch máy.

## Đề xuất và khuyến nghị

1. **Mở rộng kho dữ liệu huấn luyện**: Thu thập thêm dữ liệu đa dạng từ nhiều nguồn khác nhau để tăng tính bao phủ của mô hình, giảm tỷ lệ N-gram chưa xuất hiện, nâng cao độ chính xác dự đoán.

2. **Tối ưu tham số làm mịn và pruning**: Thực hiện các thử nghiệm sâu hơn để lựa chọn tham số tối ưu cho từng loại N-gram, đảm bảo cân bằng giữa kích thước mô hình và độ chính xác, áp dụng trong vòng 6-12 tháng.

3. **Phát triển hệ thống sửa lỗi dấu thanh tích hợp AI**: Kết hợp mô hình N-gram với các kỹ thuật học sâu (deep learning) để cải thiện khả năng nhận diện ngữ cảnh và sửa lỗi phức tạp hơn, hướng tới ứng dụng thương mại trong 1-2 năm tới.

4. **Xây dựng bộ công cụ mã nguồn mở cho cộng đồng**: Phát triển và công bố bộ công cụ xử lý ngôn ngữ tiếng Việt dựa trên mô hình N-gram, hỗ trợ nghiên cứu và phát triển ứng dụng, thúc đẩy sự phát triển chung của lĩnh vực.

## Đối tượng nên tham khảo luận văn

1. **Nhà nghiên cứu và sinh viên ngành Khoa học máy tính, Ngôn ngữ học máy tính**: Nắm bắt kiến thức về mô hình ngôn ngữ N-gram, kỹ thuật làm mịn và ứng dụng thực tiễn trong xử lý tiếng Việt.

2. **Phát triển phần mềm và ứng dụng xử lý ngôn ngữ tự nhiên**: Áp dụng mô hình và thuật toán trong xây dựng các hệ thống nhận dạng tiếng nói, dịch máy, soát lỗi chính tả và nhập liệu tiếng Việt.

3. **Doanh nghiệp công nghệ và startup trong lĩnh vực AI và NLP**: Tận dụng kết quả nghiên cứu để phát triển sản phẩm, nâng cao chất lượng dịch vụ liên quan đến tiếng Việt.

4. **Cơ quan quản lý và tổ chức giáo dục**: Sử dụng luận văn làm tài liệu tham khảo để xây dựng chính sách, chương trình đào tạo và phát triển công nghệ ngôn ngữ Việt Nam.

## Câu hỏi thường gặp

1. **Mô hình N-gram là gì và tại sao lại quan trọng trong xử lý ngôn ngữ tự nhiên?**  
Mô hình N-gram là mô hình thống kê dựa trên giả thuyết Markov, ước lượng xác suất xuất hiện của một từ dựa trên n từ trước đó. Nó giúp máy tính dự đoán và hiểu ngôn ngữ tự nhiên hiệu quả hơn, đặc biệt trong các ứng dụng như nhận dạng tiếng nói và dịch máy.

2. **Các phương pháp làm mịn có vai trò gì trong mô hình N-gram?**  
Làm mịn giúp khắc phục vấn đề phân bố không đều và các cụm N-gram chưa xuất hiện trong dữ liệu huấn luyện, bằng cách gán xác suất khác 0 cho các cụm này, từ đó cải thiện độ chính xác của mô hình.

3. **Tại sao cần giảm kích thước mô hình ngôn ngữ?**  
Mô hình N-gram có thể rất lớn khi dữ liệu huấn luyện tăng, gây tốn bộ nhớ và giảm tốc độ xử lý. Giảm kích thước giúp tối ưu hiệu suất mà vẫn giữ được độ chính xác cần thiết.

4. **Ứng dụng sửa lỗi dấu thanh trong tiếng Việt có ý nghĩa như thế nào?**  
Sửa lỗi dấu thanh giúp cải thiện chất lượng văn bản tiếng Việt, hỗ trợ người dùng nhập liệu nhanh và chính xác, đồng thời nâng cao hiệu quả các hệ thống xử lý ngôn ngữ tự nhiên.

5. **Làm thế nào để lựa chọn tham số tối ưu cho mô hình N-gram?**  
Tham số được lựa chọn thông qua các thử nghiệm đánh giá độ hỗn loạn thông tin (Perplexity) và tỉ lệ lỗi trên tập kiểm thử, nhằm cân bằng giữa độ chính xác và kích thước mô hình.

## Kết luận

- Nghiên cứu đã xây dựng thành công mô hình ngôn ngữ N-gram cho tiếng Việt với dữ liệu hơn 200MB, bao gồm gần 1 triệu cụm N-gram âm tiết và từ.  
- Áp dụng các kỹ thuật làm mịn tiên tiến như Kneser-Ney giúp giảm đáng kể độ hỗn loạn thông tin, nâng cao độ chính xác mô hình.  
- Kỹ thuật pruning hiệu quả trong việc giảm kích thước mô hình mà không ảnh hưởng nhiều đến chất lượng dự đoán.  
- Hệ thống sửa lỗi dấu thanh dựa trên mô hình N-gram đạt tỉ lệ lỗi thấp, có tiềm năng ứng dụng rộng rãi trong thực tế.  
- Đề xuất mở rộng dữ liệu, tối ưu tham số và phát triển hệ thống tích hợp AI để nâng cao hơn nữa hiệu quả xử lý ngôn ngữ tiếng Việt.

Khuyến khích các nhà nghiên cứu và doanh nghiệp ứng dụng kết quả nghiên cứu để phát triển các sản phẩm xử lý ngôn ngữ tiếng Việt, đồng thời tiếp tục mở rộng và hoàn thiện mô hình trong các nghiên cứu tương lai.

Trích đoạn nội dung tài liệu

CHƯƠNG I: MÔ HÌNH NGÔN NGỮ N-GRAM 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). Với: + P(A): Xác suất xảy ra sự kiện A + P(B): Xác suất xảy ra sự kiện B + P(B|A): Xác suất (có điều kiện) xảy ra sự kiện B nếu biết rằng sự kiện A đã xảy ra.

Thì ta dễ dàng suy ra được. 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).

- Với n = 2, ta có khái niệm bigram. - Với n = 3, ta có trigram. Nhưng vì n càng lớn thì số trường hợp càng lớn nên thường người ta chỉ sử dụng với n = 1,2 hoặc đôi lúc là 3. 4 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).

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.1: Giả sử cần tính xác suất của P(nên|Có chí thì nên). - Mô hình 1-Gram (Uni-gram): Tính xác suất của 1 từ mà không phụ thuộc vào từ trước nó, tức là không có ngữ cảnh. P=P(nên) - Mô hình 2-gram (Bi-gram): Tính xác suất của 1 từ dựa vào 1 từ liền ngay trước nó.

P=P(nên|thì) - Mô hình 3-gram (Tri-gram): Tính xác suất của 1 từ dựa vào 2 từ liền ngay trước nó. Công thức tính “xác suất thô”: Để sử dụng được, mô hình N-gram cần được cung cấp nhiều thông tin về xác suất. Các thông tin này được rút trích từ một kho ngữ liệu cho trước, gọi là kho ngữ liệu huấn luyện.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.

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-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) 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.

Vấn đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram: 1. Phân bố không đều: Khi sử dụng mô hình N-gram 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 các câu có chứa các cụm N-gram này sẽ có kết quả không tốt. Với V là kích thước bộ từ vựng, ta sẽ 6 có Vn 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ụ: tiếng Việt có khoảng hơn 5000 âm tiết khác nhau, ta có tổng số cụm 3-gram có thể có là: 5.000 Tuy nhiên, số cụm 3- gram thống kê được chỉ xấp xỉ 1. 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. 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 1. 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ó 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 1. 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ố không đều 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.

7 ● 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.

Các thuật toán chiết khấu (discounting): Nguyên lý 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 đề bù cho các cụm N-gram chưa từng xuất hiện trong tập huấn luyện. Các thuật toán này sẽ trực tiếp làm thay đổi tần số xuất hiện của tất cả các cụm N-gram. Ở đây đề cập đến 3 thuật toán chiết khấu phổ biến: ● Thuật toán Add-One ● Thuật toán Witten-Bell ● Thuật toán Good-Turing 1. Phương pháp làm mịn Add-One: Phương pháp này sẽ cộng thêm vào số lần xuất hiện của mỗi cụm N-gram lên 1, khi đó xác suất của cụm N-gram sẽ được tính lại là: c 1 p (1.1) nv 8 Trong đó, 𝑐 là của số lần xuất hiện cụm N-gram trong tập ngữ liệu mẫu, 𝑛 là số cụm N-gram, 𝑣 là kích thước của toàn bộ từ vựng.

(Ở đây, c  n vì thế sau khi thêm 1 vào tần suất xuất hiện mỗi cụm N-gram, tổng này trở thành (c  1)  n  v , do đó ta cập nhật lại công thức tính xác suất của cụm N-gram như trên) Với Unigram, ta có thể viết lại (1.4) như sau: c (1)  1 p  (1) (1) n v n(1) Ta có , f (1)  (c  1) (1) (1) là tần suất của unigram, c(1) là số lần xuất n v hiện của Unigram trước khi làm mịn bằng phương pháp Add-one. Với cụm N-gram w=w1w2.wi 1 )  V Để ý rằng, có rất nhiều cụm N-gram không nhìn thấy (bậc thấp) so với những N-gram nhìn thấy (bậc cao). Trong khi đó, có những cụm N-gram có nghĩa (cần thiết) bị giảm đi còn những cụm N-gram tối nghĩa lại có xác suất tăng lên. Để hạn chế điều này, người ta đưa thêm hệ số 𝛼 thay vì cộng 1 nhằm cân đối lại xác suất (Phương pháp làm mịn Add-𝛼).

Đặc biệt, khi = , được gọi là phương pháp Jeffreys – 2 Perks.2) có thể viết lại thành: 1 C ( w1w2 .wi 1 )  M 1 Dễ thấy với một Unigram, tỷ số chính là xác suất xảy ra của mỗi V unigram Hay C ( wi 1wi )  MP( wi ) P( wi | wi 1 )  C ( wi 1 )  M 1. Phương pháp làm mịn Witten - Bell: Thuật toán Witten-Bell hoạt động dựa trên nguyên tắc: Khi gặp những cụm N-gram có tần số 0, ta coi đây là lần đầu tiên cụm từ này xuất hiện. Như vậy, xác suất của cụm N-gram có tần số bằng 0 có thể tính dựa vào xác suất gặp một cụm N-gram lần đầu tiên. Với Uni-gram, gọi T là số cụm Uni-gram khác nhau đã xuất hiện, còn M là tổng số các cụm Uni-gram đã thống kê, khi đó tổng số sự kiện sẽ là (T+M), và xác suất để gặp cụm Uni-gram lần đầu tiên (hay tổng xác suất của các cụm T Uni-gram chưa xuất hiện lần nào) được tính bằng: T+M Gọi V là kích thước bộ từ vựng, còn Z là số cụm Uni-gram chưa xuất hiện lần nào: Z = V - T Xác suất xuất hiện của một cụm Uni-gram chưa xuất hiện lần nào (có tần số bằng 0) được tính bằng: T P* = Z(T+M) Và xác suất xuất hiện của các cụm Uni-gram có tần số khác 0 được tính lại theo công thức: c(w) P(w) = với c(w) là số lần xuất hiện của cụm w T+M 10 Cũng giống thuật toán Add-One, khi xét các cụm N-gram với N>1, thay M bằng C(wi-n+1.wi-1) thì xác suất của cụm wi-n+1.wi-1wi với C(wi-n+1.wi-1wi) = 0 được tính theo công thức sau: T(wi-n+1.wi-1) P(wi|wi-n+1.wi-1)) Với C(wi-n+1.