Tài liệu 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 trong tiếng việt

i .. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG VŨ CHÍ HIẾU 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 TRONG TIẾNG VIỆT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2016 ii ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG VŨ CHÍ HIẾU 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 TRONG TIẾNG VIỆT Chuyên ngành: Khoa học máy tính Mã số: 60 48 0101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Giáo viên hướng dẫn: TS. VŨ TẤT THẮNG Thái Nguyên – 2016 iii i 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. Thái Nguyên, ngày 20 tháng 3 năm 2016 Học viên Vũ Chí Hiếu ii LỜI CẢM ƠN Tôi xin gửi lời cảm ơn tới trường Đại học CNTT&TT – Đại học Thái Nguyên đã tạo điều kiện và tổ chức khóa học này để tôi có thể có điều kiện tiếp thu kiến thức mới và có thời gian để hoàn thành Luận văn Cao học này. Tôi xin được cảm ơn TS.Vũ Tất Thắng, 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. Tôi xin chân thành cảm ơn các thày cô đã truyền đạt cho em những kiến thức quý báu trong quá trình học Cao học và làm Luận văn. Tôi chân thành cảm ơn các bạn bè, anh chị em trong lớp cao học K13 đã 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. Cuối cùng tôi kính gửi thành quả này đến gia đình và người thân của tôi, những người đã hết lòng chăm sóc, dạy bảo và động viên tôi để tôi có kết quả ngày hôm nay. Mặc dù tôi đã cố gắng hoàn thành Luận văn trong phạm vi và khả năng cho phép nhưng chắc chắn không tránh khỏi những thiếu sót. Xin kính mong nhận được sự cảm thông và tận tình chỉ bảo của quý Thầy Cô và các bạn. Thái Nguyên, ngày 20 tháng 3 năm 2016 Học viên Vũ Chí Hiếu iii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii LỜI NÓI ĐẦU .................................................................................................. 1 CHƯƠNG I: MÔ HÌNH NGÔN NGỮ N-GRAM ............................................ 3 1.1. Giới thiệu chung: ........................................................................................... 3 1.2. Công thức tính “xác suất thô”: ...................................................................... 5 1.3. Vấn đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram: ......................... 5 1.3.1. Phân bố không đều:............................................................................................ 5 1.3.2. Kích thước bộ nhớ của mô hình ngôn ngữ: ....................................................... 6 1.4. Các phương pháp làm mịn:............................................................................ 6 1.4.1. Các thuật toán chiết khấu (discounting): .......................................................... 7 1.4.1.1. Phương pháp làm mịn Add-One: ........................................................................... 7 1.4.1.2. Phương pháp làm mịn Witten - Bell: ..................................................................... 9 1.4.1.3. Phương pháp làm mịn Good - Turing: ................................................................. 10 1.4.2. Phương pháp truy hồi: ..................................................................................... 11 1.4.3. Phương pháp nội suy: ...................................................................................... 12 1.4.4. Phương pháp làm mịn Kneser - Ney: .............................................................. 13 1.4.5. Phương pháp làm mịn Chen - GoodMan: ........................................................ 14 1.5. Kỹ thuật làm giảm kích thước dữ liệu: ........................................................ 15 1.5.1. Đồng hóa (Quantization): ................................................................................ 16 1.5.2. Loại bỏ (pruning): ............................................................................................ 16 1.5.2.1. Cắt bỏ (cut-off):.................................................................................................... 17 1.5.2.2. Sự khác biệt trọng số (Weighted difference): ...................................................... 18 1.5.3. Nén (Compression): ......................................................................................... 19 1.6. Độ đo trong đánh giá mô hình: .................................................................... 19 1.6.1. Entropy - Độ đo thông tin: ............................................................................... 19 1.6.2. Perplexity - Độ hỗn loạn thông tin: ................................................................. 21 1.6.3. Error rate - Tỉ lệ lỗi: ......................................................................................... 22 CHƯƠNG II: XÂY DỰNG N-GRAM CHO TIẾNG VIỆT .......................... 23 2.1. Giới thiệu: ....................................................................................................... 23 iv 2.2. Công cụ tách từ cho tiếng Việt - vnTokenizer:............................................... 23 2.3. Bộ công cụ SRILM: ........................................................................................ 27 2.3.1. N-gram-count: .................................................................................................... 27 2.3.2. N-gram:............................................................................................................... 29 2.4. Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện: ................................. 30 2.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: ......... 31 2.5.1. Tách câu: ............................................................................................................ 31 2.5.2. Tách từ: ............................................................................................................... 33 2.5.3. Gán nhãn từ loại: ................................................................................................ 36 2.5.4. Phân tích cú pháp: .............................................................................................. 38 2.6. Dữ liệu huấn luyện:......................................................................................... 39 2.7. Kết quả xây dựng mô hình:............................................................................. 39 2.7.1. Số lượng các cụm N-gram với tiếng Việt dựa trên âm tiết: ............................... 39 2.7.2. Số lượng các cụm N-gram với tiếng Việt dựa trên từ: ....................................... 40 2.8. Phân bố thống kê của tần số các cụm N-gram:............................................... 41 2.8.1. Với âm tiết. ......................................................................................................... 41 2.8.2. Với từ:................................................................................................................. 42 2.9. Phương pháp loại bỏ (Cut-off ): ..................................................................... 44 2.9.1. Với âm tiết .......................................................................................................... 44 2.9.2.Với từ:.................................................................................................................. 44 2.10. Các phương pháp làm mịn: ........................................................................... 45 2.10.1. Với âm tiết: ....................................................................................................... 45 2.10.2. Với từ:............................................................................................................... 45 CHƯƠNG III: Ứ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 ................................................... 47 3.1. Tổng quan: ...................................................................................................... 47 3.2. Bài toán sửa lỗi dấu thanh trong tiếng Việt: ................................................... 48 3.2.1. Phát biểu bài toán: ............................................................................................... 48 3.2.2. Đặc điểm: ............................................................................................................ 48 3.2.3. Hướng giải quyết: ............................................................................................. 49 3.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có: ...................................... 49 3.3.1. Công cụ AMPad: ................................................................................................. 49 v 3.3.2. VietPad:............................................................................................................... 50 3.4. Đề xuất hệ thống: ............................................................................................ 51 3.5. Cài đặt thử nghiệm và đánh giá hệ thống ....................................................... 54 KẾT LUẬN ..................................................................................................... 58 HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI .......................................................... 59 vi DANH MỤC ẢNH Hình 2 - 1: Quy trình tách từ .....................................................................................24 Hình 2 - 2: Số lượng các cụm N-gram với âm tiết khi tăng kích thước dữ liệu .............40 Hình 2 - 3: số lượng các cụm N-gram với từ khi tăng kích thước dữ liệu ...................41 Hình 2 - 4: Số lượng các cụm N-gram (âm tiết) có tần số từ 1 đến 10 .....................42 Hình 2 - 5: Số lượng các cụm Ngram (từ) có tần số từ 1 đến 10 ..............................43 Hình 3 - 1: Thêm dấu tiếng Việt tự động bằng AMPad ............................................50 Hình 3 - 2: Gõ tiếng Việt không dấu trên VietPad....................................................51 Hình 3 - 3: Lưu đồ thực hiện của mô hình đề xuất ...................................................52 Hình 3 - 4: Giao diện chương trình ...........................................................................55 Hình 3 - 5: Chương trình thực hiện khi văn bản đầu vào hoàn toàn không có dấu...............55 Hình 3 - 6: Chương trình thực hiện khi văn bản đầu vào có các từ có dấu xen kẽ .............56 vii DANH MỤC BẢNG BIỂU Bảng 2- 1: Số lượng các cụm N-gram trong văn bản huấn luyện với âm tiết ..............39 Bảng 2- 2: Số lượng các cụm N-gram trong văn bản huấn luyện với từ ..................40 Bảng 2- 3: Tần số của tần số các cụm N-gram áp dụng cho âm tiết .........................42 Bảng 2- 4: Tần số của tần số các cụm Ngram với từ ................................................43 Bảng 2- 5: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết............44 Bảng 2- 6: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ ...................45 Bảng 2- 7: Độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết .............45 Bảng 2- 8: Độ hỗn loạn thông tin của các phương pháp làm mịn cho từ .................46 1 LỜI NÓI ĐẦU 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. 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. 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ụ: 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 = 10-3 P[“trời mưa sẽ mai ngày”] ~ 10-11 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. Như vậy, 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 2 kê các từ và 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 sửa lỗi dấu thanh trong tiếng Việt. 3 CHƯƠNG I: MÔ HÌNH NGÔN NGỮ N-GRAM 1.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. 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). - Với n = 1, unigram. - 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. Ví dụ 1.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ó. P=P(nên|chí thì) 5 1.2. 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. 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: P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1wi)  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: P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1wi) C(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. 1.3. Vấn đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram: 1.3.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.0003 = 125.000.000.000 Tuy nhiên, số cụm 3gram thống kê được chỉ xấp xỉ 1.500.000. Như vậy sẽ có rất nhiều cụm 3gram 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.4 1.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ó 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.5 1.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ố 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 Ngram 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. 1.4.1. 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 Ngram 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.4.1.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à: p c 1 nv (1.4.1) 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) n v (1) Ta có , f (1) n(1)  (c  1) (1) là tần suất của unigram, c(1) là số lần xuất n v (1) 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, i>1, ta có ,  C (w w ...w 1 i 1 2 w)  C ( w1w2 ...wi 1 ) w Do đó: P( wi | w1w2 ...wi 1 )  C ( w1w2 ...wi )  1 (1.4.2) C ( 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-𝛼). p Trong đó, 𝛼<1. Đặc biệt, khi = Perks. c (1.4.3) n  v 1 , được gọi là phương pháp Jeffreys – 2 9 Đặt 𝑀= 𝛼𝑉, khi đó (1.4.2) có thể viết lại thành: 1 C ( w1w2 ...wi )  M ( ) V P( wi | w1w2 ...wi 1 )  C ( w1w2 ...wi 1 )  M Dễ thấy với một Unigram, tỷ số 1 V chính là xác suất xảy ra của mỗi unigram Hay P( wi | wi 1 )  C ( wi 1wi )  MP( wi ) C ( wi 1 )  M 1.4.1.2. 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 Uni-gram chưa xuất hiện lần nào) được tính bằng: T 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: P* = T 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: P(w) = c(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: P(wi|wi-n+1...wi-1) = T(wi-n+1...wi-1) Z(wi-n+1...wi-1)(C(wi-n+1...wi-1) + T(wi-n+1...wi-1)) Với C(wi-n+1...wi-1wi) > 0, thì xác suất cụm wi-n+1...wi-1wi tính bằng công thức: P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1wi) C(wi-n+1...wi-1) + T(wi-n+1...wi-1) 1.4.1.3. Phương pháp làm mịn Good - Turing: Thuật toán Good - Turing dựa trên việc tính toán Nc, với Nc là số cụm Ngram xuất hiện c lần. Như vậy: N0 là số cụm N-gram có tần số 0 (số cụm N-gram không xuất hiện lần nào) N1 là số cụm N-gram có tần số 1 (số cụm N-gram xuất hiện 1 lần) … Nc có thể hiểu đơn giản là: Nc =  w : count ( w)  c Khi đó, thuật toán Good-Turing sẽ thay thế tần số c bằng một tần số mới c* theo công thức: c* = (c+1) * Nc+1 Nc Xác suất của một cụm N-gram với tần số là c được tính lại theo công thức: c= c= c= c* P(w) = với N =  Ncc =  Ncc* =  Nc+1(c+1) N c=0 c=0 c=0 Trên thực tế, người ta không tính toán và thay thế mọi tần số c bởi một tần số mới c*. Người ta chọn một ngưỡng k nhất định, và chỉ thay thế tần số c bởi tần số mới c* khi c nhỏ hơn hoặc bằng k, còn nếu c lớn hơn k thì giữ nguyên