Khóa luận Xây dựng mô hình ngôn ngữ cho Tiếng Việt

Mô hình ngôn ngữ Ngram - Cao Văn Việt K51KHMT ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Cao Văn Việt XÂY DỰNG MÔ HÌNH NGÔN NGỮ CHO TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Khoa học máy tính HÀ NỘI – 2010 LỜI CẢM ƠN Đầu tiên, cho phép tôi gửi lời cảm ơn sâu sắc tới TS Lê Anh Cường, người đã trực tiếp hướng dẫn, chỉ bảo và tạo điều kiện cho tôi trong quá trình hoàn thành luận văn này. Đồng thời tôi cũng xin gửi lời cảm ơn chân thành tới các thầy cô giáo trường Đại học Công Nghệ, đặc biệt là các thầy cô trong bộ môn Khoa học Máy tính , những người đã trực tiếp giảng dạy, hướng dẫn và tạo điều kiện cho tôi trong quá trình học tập và thực hành ở trường. Cuối cùng, tôi xin gửi gời cảm ơn tới tất cả các bạn đồng học và gia đình đã ủng hộ, giúp đỡ tôi hoàn thành luận văn TÓM TẮT Mô hình ngôn ngữ là một bộ phận quan trọng của lĩnh vực xử lý ngôn ngữ tự nhiên. Có rất nhiều lĩnh vực trong xử lý ngôn ngữ tự nhiên sử dụng mô hình ngôn ngữ như: kiểm lỗi chính tả, dịch máy hay phân đoạn từ... Trên thế giới đã có rất nhiều nước công bố nghiên cứu về mô hình ngôn ngữ áp dụng cho ngôn ngữ của họ nhưng ở Việt Nam, việc nghiên cứu và xây dựng một mô hình ngôn ngữ chuẩn cho tiếng Việt vẫn còn mới mẻ và gặp nhiều khó khăn. Chính điều này đã gợi ý và thúc đẩy chúng tôi lựa chọn và tập trung nghiên cứu vấn đề này để có thể tạo điều kiện cho việc xử lý ngôn ngữ tiếng Việt vốn vô cùng phong phú của chúng ta. Luận văn sẽ trình bày khái quát về mô hình ngôn ngữ, đồng thời chỉ ra các khó khăn còn tồn tại để rồi đưa ra những phương pháp khắc phục, trong đó trọng tâm nghiên cứu các phương pháp làm mịn. Trong luận văn này này, chúng tôi sử dụng chủ yếu bộ công cụ mã nguồn mở SRILIM để xây dựng mô hình ngôn ngữ cho tiếng Việt, sau đó áp dụng mô hình ngôn ngữ đã tạo ra để tính toán độ hỗn loạn thông tin của văn bản và dịch máy thống kê. Kết quả có được sẽ là cơ sở chính để chúng tôi chỉ ra phương pháp làm mịn nào là tốt nhất khi sử dụng trong việc xây dựng mô hình ngôn ngữ tiếng Việt. MỤC LỤC Chương 1 Giới thiệu vấn đề ................................................................................ 1 1.1 Đặt vấn đề: ......................................................................................................... 1 1.2 Mục tiêu: ............................................................................................................ 1 1.3 Cấu trúc của luận văn: ........................................................................................ 2 Chương 2 Mô hình ngôn ngữ Ngram: ................................................................. 3 2.1 Khái quát: ........................................................................................................... 3 2.2 Công thức tính “xác suất thô”: ............................................................................ 3 2.3 Khó khăn khi xây dựng mô hình ngôn ngữ N-gram ............................................ 4 2.3.1 Phân bố không đều: .................................................................................................4 2.3.2 Kích thước bộ nhớ của mô hình ngôn ngữ................................................................5 2.4 Các phương pháp làm mịn .................................................................................. 5 2.4.1 Các thuật toán chiết khấu (discounting): .................................................................5 2.4.2 Phương pháp truy hồi:..............................................................................................8 2.4.3 Phương pháp nội suy: ............................................................................................10 2.4.4 Phương pháp làm mịn Kneser - Ney: .....................................................................10 2.4.5 Phương pháp làm mịn Kneser - Ney cải tiến bởi Chen - GoodMan: .......................12 2.5 Kỹ thuật làm giảm kích thước dữ liệu: .............................................................. 13 2.5.1 Loại bỏ (pruning):..................................................................................................13 2.5.2 Đồng hóa (Quantization):.......................................................................................15 2.5.3 Nén (Compression):...............................................................................................16 2.6 Độ đo:............................................................................................................... 16 2.6.1 Entropy – Độ đo thông tin:.....................................................................................16 2.6.2 Perplexity – Độ hỗn loạn thông tin:........................................................................18 2.6.3 Error rate – Tỉ lệ lỗi: ..............................................................................................18 Chương 3 Ứng dụng của mô hình ngôn ngữ trong mô hình dịch máy thống kê: 19 3.1 Dịch máy: ......................................................................................................... 19 3.2 Dịch máy thống kê:........................................................................................... 19 3.2.1 Giới thiệu: .............................................................................................................19 3.2.2 Nguyên lý và các thành phần: ................................................................................19 3.2.3 Mô hình dịch: ........................................................................................................21 3.2.4 Bộ giải mã: ............................................................................................................25 3.3 Các phương pháp đánh giá bản dịch: ................................................................ 25 3.3.1 Đánh giá trực tiếp bằng con người: ........................................................................25 3.3.2 Đánh giá tự động: phương pháp BLEU ..................................................................26 Chương 4 Thực nghiệm: ................................................................................... 28 4.1 Công cụ: ........................................................................................................... 28 4.1.1 Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện: ..........................................28 4.1.2 Công cụ tách từ cho tiếng Việt - vnTokenizer: .......................................................28 4.1.3 Bộ công cụ xây dựng mô hình ngôn ngữ - SRILM: ................................................29 4.1.4 Bộ công cụ xây dựng mô hình dịch máy thống kê – MOSES: ................................32 4.2 Dữ liệu huấn luyện: .......................................................................................... 34 4.3 Kết quả: ............................................................................................................ 34 4.3.1 Số lượng các cụm ngram:.......................................................................................34 4.3.2 Tần số của tần số: ..................................................................................................36 4.3.3 Cut-off (loại bỏ):....................................................................................................39 4.3.4 Các phương pháp làm mịn: ....................................................................................40 4.3.5 Áp dụng vào mô hình dịch máy thống kê: ..............................................................41 Chương 5 Kết luận............................................................................................ 43 Tài liệu tham khảo................................................................................................ 44 Danh sách các bảng sử dụng trong luận văn: Bảng 4-1: số lượng các cụm Ngram trong văn bản huấn luyện với âm tiết .................35 Bảng 4-2: số lượng các cụm Ngram trong văn bản huấn luyện với từ.........................36 Bảng 4-3: tần số của tần số các cụm Ngram áp dụng cho âm tiết ...............................37 Bảng 4-4: tần số của tần số các cụm Ngram với từ.....................................................38 Bảng 4-5: bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết .............39 Bảng 4-6: bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ .......................40 Bảng 4-7: độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết ...............40 Bảng 4-8: độ hỗn loạn thông tin của các phương pháp làm mịn cho từ.......................41 Bảng 4-9: điểm BLEU của bản dịch máy với mô hình ngôn ngữ sử dụng dữ liệu huấn luyện có kích thước nhỏ (50Mb) ................................................................................41 Bảng 4-10: điểm BLEU của bản dịch máy với mô hình Ngram sử dụng dữ liệu huấn luyện có kích thước lớn (300Mb)...............................................................................42 Danh sách các hình sử dụng trong luận văn: Hình 3-1: mô hình dịch máy thống kê từ tiếng Anh sang tiếng Việt ...........................20 Hình 3-3: sự tương ứng một - một giữa câu tiếng Anh và câu tiếng Pháp...................21 Hình 3-4: sự tương ứng giữa câu tiếng Anh với câu tiếng Tây Ban Nha khi cho thêm từ vô giá trị (null) vào đầu câu tiếng Anh .......................................................................22 Hình 3-5: sự tương ứng một - nhiều giữa câu tiếng Anh với câu tiếng Pháp...............22 Hình 3-6: sự tương ứng nhiều - nhiều giữa câu tiếng Anh với câu tiếng Pháp. ...........22 Hình 3-7: mô hình dịch dựa trên cây cú pháp.............................................................25 Hình 3-8: sự trùng khớp của các bản dịch máy với bản dịch mẫu...............................26 Hình 4-1: số lượng các cụm Ngram với âm tiết khi tăng kích thước dữ liệu ...............35 Hình 4-2: số lượng các cụm Ngram với từ khi tăng kích thước dữ liệu.......................36 Hình 4-3: số lượng các cụm Ngram (âm tiết) có tần số từ 1 đến 10 ............................37 Hình 4-4: số lượng các cụm Ngram (từ) có tần số từ 1 đến 10....................................38 1 Chương 1 Giới thiệu vấn đề 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 [10]. 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 sâu về ngôn ngữ học. 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à cụm từ có trong các văn bản. Cốt lõi nhất của các phương pháp xử lý ngôn ngữ tự nhiên dựa trên thống kê chính là việc xây dựng mô hình ngôn ngữ. 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 [2][10]. Nói đơ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à bao nhiêu. Ví dụ: khi áp dụng mô hình ngôn ngữ cho tiếng Việt: P[“hôm qua là thứ năm”] = 0.001 P[“năm thứ hôm là qua”] = 0 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ô hình ngôn ngữ có nhiều hướng tiếp cận, nhưng chủ yếu được xây dựng theo mô hình Ngram. Vấn đề này sẽ trình bày rõ ràng hơn trong chương 2. 1.2 Mục tiêu: 2 Mục tiêu chính của luận văn là tìm hiểu lý thuyết về mô hình Ngram 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 dịch máy thống kê, chúng tôi đã 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ữ. Để đạt được thành tựu đó, chúng tôi cũng đã phải tìm hiểu lý thuyết dịch máy thống kê và thực nghiệm dựa trên bộ công cụ Moses. 1.3 Cấu trúc của luận văn: Luận văn có cấu trúc như sau: Chương 2 xem xét các vấn đề liên quan đến mô hình ngôn ngữ Ngram, các sự cố gặp phải và cách khắc phục. Chương 3 đề cập đến lý thuyết mô hình dịch máy thống kê. Chương 4, 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ữ, mô hình dịch máy thống kê và các kết quả đạt được Chương 5 tổng kết lại những gì luận văn đạt được và đưa ra kế hoạch nghiên cứu trong tương lai. 3 Chương 2 Mô hình ngôn ngữ Ngram: 2.1 Khái quát: Nhiệm vụ của mô hình ngôn ngữ là cho biết xác suất của một câu w 1w 2...w m là bao nhiêu. Theo công thức Bayes: P(AB) = P(B|A) * P(A), thì: P(w 1w 2…w m) = P(w 1) * P(w 2|w 1) * P(w 3|w 1w 2) *…* P(w m|w 1w 2…w m-1) Theo công thức này, 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(w m|w 1,w 2,…, w m-1) = P(w m|w m-n,w n-m+1, …,w m-1) Nếu áp dụng xấp xỉ Markov, xác suất xuất hiện của một từ (w m) được coi như chỉ phụ thuộc vào n từ đứng liền trước nó (w m-nw m-n+1…w m-1) chứ không phải phụ thuộc vào toàn bộ dãy từ đứng trước (w 1w 2…w m-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(w 1w 2…w m) = P(w 1) * P(w 2|w 1) * P(w 3|w 1w 2) *…* P(w m-1|w m-n-1w m-n …w m-2)* P(w m|w m-nw m-n+1…w m-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ừ. Mô hình ngôn ngữ này gọi là mô hình ngôn ngữ N-gram. Một cụm N-gram là một dãy con gồm n phần tử liên tiếp của 1 dãy các phần tử cho trước (trong bộ dữ liệu huấn luyện) [2]. Ví dụ: cụm 2-gram “tôi đã” thuộc câu “tôi đã từng đọc quyển sách ấy”. Các phần tử được xét ở đây thường là kí tự, từ hoặc cụm từ; tùy vào mục đích sử dụng. Dựa vào số phần tử của 1 cụm N-gram, ta có các tên gọi cụ thể: N = 1: Unigram N = 2: Bigram N = 3: Trigram 2.2 Công thức tính “xác suất thô”: 4 Gọi C(w i-n+1...w i-1w i) là tần số xuất hiện của cụm w i-n+1...w i-1w i trong tập văn bản huấn luyện. Gọi P(w i|w i-n+1...w i-1) là xác suất w i đi sau cụm w i-n+1..w i-2w i-1. Ta có công thức tính xác suất như sau: P(w i|w i-n+1...w i-1) = C(w i-n+1...w i-1w i)  w C(w i-n+1...w i-1w) Dễ thấy,  w C(w i-n+1..w i-1w) chính là tần số xuất hiện của cụm w i-n+1...w i-1 trong văn bản huấn luyện. Do đó công thức trên viết lại thành: P(w i|w i-n+1...w i-1) = C(w i-n+1...w i-1w i) C(w i-n+1...w i-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. 2.3 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: 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ả tồi. Với V là kích thước bộ từ vựng, ta sẽ 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 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. 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 Ngram 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. 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 Ngram 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 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ố thưa như đã đề cập ở phần 2.4.1, người ta đã đưa ra các phương pháp “làm mịn” 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) 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 (có xuất hiện khi thống kê) thành một giá trị phù hợp (tổng xác suất không đổi). Các phương pháp làm mịn có thể được chia ra thành 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 Ngram 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 Ngram không xuất hiện trong tập huấn luyện dựa vào các cụm Ngram ngắn hơn 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 Ngram dựa vào xác suất của các cụm Ngram ngắn hơn. 2.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 Ngram chưa từng xuất hiện trong tập huấn luyện [10]. 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 Ngram. Ở đây đề cập đến 3 thuật toán chiết khấu phổ biến: 6  Thuật toán Add-one  Thuật toán Witten-Bell  Thuật toán Good-Turing 2.4.1.1 Phương pháp làm mịn Add-one: Thuật toán làm mịn Add-one cộng thêm 1 vào tần số xuất hiện của tất cả các cụm N-gram rồi nhân với phân số chuẩn hóa (để bảo toàn tổng xác suất). Với unigram, khi cộng thêm 1 vào tần số của mỗi cụm unigram, thì tổng số cụm unigram đã xuất hiện bằng: M’ = M + V với M là tổng số cụm unigram đã xuất hiện V là kích thước bộ từ vựng Để bảo toàn tổng số cụm unigram vẫn bằng M, thì tần số mới của các cụm unigram được tính lại theo công thức: C i* = (C i+1) M M’ với C i là tần số của cụm unigram trước khi làm mịn Như vậy, xác suất của các cụm unigram cũng được tính lại: P i* = C i* M = (C i+1) M + V Xét các cụm N-gram với N>1, thay M bằng C(w i-n+1...w i-1) thì xác suất của cụm w i-n+1...w i-1w i được tính theo công thức sau: P(w i|w i-n+1...w i-1) = C(w i-n+1...w i-1w i) + 1 C(w i-n+1...w i-1) + V Chúng ta có thể thấy thuật toán này sẽ làm thay đổi đáng kể xác suất của các cụm Ngram đã xuất hiện trong tập huấn luyện nếu kích thước bộ từ điển V là rất lớn. Trong thực nghiệm, một vài cụm Ngram có xác suất giảm đi gần 10 lần, do kích thước bộ từ điển là lớn trong khi tần số xuất hiện của cụm Ngram đó không cao. Để thuật toán thêm hiệu quả, người ta sử dụng công thức sau: P(w 1w 2...w n) = C(w 1w 2...w n) +  C(w 1w 2...w n-1) + M 7 Công thức trên là một phiên bản cải tiến thông dụng của thuật toán add-one. Để bảo toàn tổng xác suất của tất cả các cụm Ngram, thì  được chọn trong khoảng [0, 1], với một số giá trị thông dụng sau:   = 0: không làm mịn   = 1: thuật toán add-one   = 12: được gọi là thuật toán Jeffreys - Perks 2.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 unigram, gọi T là số cụm unigram khác nhau đã xuất hiện, còn M là tổng số các cụm unigram đã thống kê, khi đó tổng số sự kiện sẽ là (T+M), và xác suất để gặp cụm unigram lần đầu tiên (hay tổng xác suất của các cụm unigram chưa xuất hiện lần nào) được tính bằng: TT+M Gọi V là kích thước bộ từ vựng, còn Z là số cụm unigram 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 unigram chưa xuất hiện lần nào (có tần số bằng 0) được tính bằng: P* = TZ(T+M) Và xác suất xuất hiện của các cụm unigram có tần số khác 0 được tính lại theo công thức: P(w) = c(w)T+M với c(w) là số lần xuất hiện của cụm w 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(w i-n+1...w i-1) thì xác suất của cụm w i-n+1...w i-1w i với C(w i-n+1...w i-1w i) = 0 được tính theo công thức sau: 8 P(w i|w i-n+1...w i-1) = T(w i-n+1...w i-1) Z(w i-n+1...w i-1)(C(w i-n+1...w i-1) + T(w i-n+1...w i-1)) Với C(w i-n+1...w i-1w i) > 0, thì xác suất cụm w i-n+1...w i-1w i tính bằng công thức: P(w i|w i-n+1...w i-1) = C(w i-n+1...w i-1w i) C(w i-n+1...w i-1) + T(w i-n+1...w i-1) 2.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 N-gram xuất hiện c lần. Như vậy: N 0 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) N 1 là số cụm n-gram có tần số 1 (số cụm N-gram xuất hiện 1 lần) … N c có thể hiểu đơn giản là: N c =  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) * N c+1 N c 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: P(w) = c*N với N =  c =  c = 0 N cc =  c =  c = 0 N cc* =  c =  c = 0 N c+1(c+1) 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 tần số. Để đơn giản, người ta chọn k đủ lớn dựa vào kết quả huấn luyện (ví dụ giá trị lớn nhất) 2.4.2 Phương pháp truy hồi: Trong các phương pháp chiết khấu như Add-One hay Witten-Bell, nếu cụm w i-n+1...w i-1w i không xuất hiện trong tập huấn luyện, và cụm w i-n+1...w i-1 cũng không xuất hiện, thì xác suất của cụm w i-n+1...w i-1w i sau khi làm mịn vẫn bằng 0. Phương pháp truy hồi tránh rắc rối trên bằng cách ước lượng xác suất các cụm Ngram chưa 9 xuất hiện lần nào dựa vào xác suất của các cụm Ngram ngắn hơn có xác suất khác 0 [10][4]. Cụ thể, xác suất của cụm w i-n+1...w i-1w i được tính lại theo công thức sau: P B(w i|w i-n+1...w i-1) =  P(w i|w i-n+1...w i-1) nếu C(w i-n+1...w i-1w i) > 0  * P B(w i|w i-n+2...w i-1) nếu C(w i-n+1...w i-1w i) = 0 Áp dụng cho bigram, ta có: P B(w i|w i-1) =  P(w i|w i-1) nếu C(w i-1w i) > 0  * P(w i) nếu C(w i-1w i) = 0 Công thức trên có thể viết lại thành: P B(w i|w i-1) = P(w i|w i-1) + (w i-1w i) *  * P(w i) với u(x) =  1 nếu C(x) = 0 0 nếu C(x) > 0 Tương tự, khi áp dụng cho trigram ta có: P B(w i|w i-2w i-1) =   P(w i|w i-2w i-1) nếu C(w i-2w i-1w i ) > 0  1 * P(w i|w i-1) nếu C(w i-2w i-1w i ) = 0 và C(w i-1w i ) > 0  2 * P(w i) nếu C(w i-2w i-1w i ) = 0 và C(w i-1w i ) = 0 Công thức trên cũng có thể viết lại thành: P B(w i|w i-2w i-1) = P(w i|w i-2w i-1) + (w i-2w i-1w i) *  1 * P(w i|w i-1) + (w i-1w i) *  2 * P(w i) Sự chính xác của mô hình truy hồi phụ thuộc vào các tham số  1 và  2. Có vài kỹ thuật giúp lựa chọn được những tham số này, tùy theo tập huấn luyện và mô hình ngôn ngữ. Một cách đơn giản, có thể chọn  1 và  2 là các hằng số. Tuy nhiên rất khó có thể chọn được hai hằng số để tổng xác suất của tất cả các cụm Ngram không thay đổi. Việc chọn hằng số không chính xác, sẽ làm ảnh hưởng lớn đến độ chính xác của cả mô hình ngôn ngữ. Do đó, ta có thể chọn tham số  như một hàm của Ngram:  1 =  1(w i-1w i) và  2 =  2(w i-1w i) Tuy nhiên, trong phương pháp truy hồi, tổng xác suất của tất cả các cụm Ngram sẽ luôn lớn hơn 1, do xác suất của các cụm Ngram đã xuất hiện thì không thay đổi, trong khi xác suất của các cụm Ngram chưa xuất hiện thì được tăng lên. Do đó, để thuật toán chính xác hơn, thì ta cần kết hợp nó với một thuật toán chiết khấu như 10 Witten-Bell hay Good-Turing để làm giảm xác suất của các cụm Ngram đã xuất hiện. Do đó, trong thực tế, chúng ta có công thức sau: P(w i|w i-2w i-1) =   P’(w i|w i-2w i-1) nếu C(w i-2w i-1w i) > 0  1 * P’(w i|w i-1) nếu C(w i-2w i-1w i) = 0 và C(w i-1w i) > 0  2 * P’(w i) nếu C(w i-2w i-1w i) = 0 và C(w i-1w i) = 0 Trong đó P’ chính là xác suất của cụm Ngram khi áp dụng thuật toán làm mịn chiết khấu. 2.4.3 Phương pháp nội suy: Phương pháp này có chung nguyên lý với phương pháp truy hồi: “sử dụng các cụm Ngram ngắn hơn để tính xác suất của cụm Ngram dài hơn”[1][2]. Tuy nhiên, phương pháp này khác phương pháp truy hồi ở điểm: phương pháp này không phụ thuộc vào sự xuất hiện của các cụm Ngram. Công thức tính xác suất theo phương pháp nội suy như sau: P I(w i|w i-n+1...w i-1) = P(w i|w i-n+1...w i-1) + (1-)P I(w i|w i-n+2...w i-1) Áp dụng cho bigram và trigram ta có: P I(w i|w i-1) = P(w i|w i-1) + (1-)P(w i) P I(w i|w i-n+1...w i-1) =  1P(w i|w i-2w i-1) +  2P(w i|w i-1) +  3P(w i) với  i  i = 1 Ở công thức trên, do tổng của tất cả các tham số  bằng 1 nên để đơn giản ta có thể chọn tất cả  bằng nhau và bằng 13. Tuy nhiên, cũng có thể chọn các tham số  như là một hàm của Ngram:  1 =  1(w i-2w i-1w i),  2 =  2(w i-1w i) và  3 =  3(w i) 2.4.4 Phương pháp làm mịn Kneser - Ney: Thuật toán Kneser-Ney xây dựng theo hai mô hình: truy hồi và nội suy, tuy nhiên trong thuật toán này không cần phải áp dụng các thuật toán chiết khấu trước khi áp dụng công thức truy hồi.  Mô hình truy hồi: 11 P BKN(w i|w i-n+1..w i-1) =    C(w i-n+1...w i) - D C(w i-n+1...w i-1) nếu C(w i-n+1...w i) > 0 (w i-n+1...w i-1)P BKN(w i|w i-n+2...w i-1) nếu C(w i-n+1...w i) = 0 Trong đó: o P BKN(w i) = N(vw i) - D  w N(vw) với N(vw) là số lượng từ v khác nhau xuất hiện trước w trong tập huấn luyện o (w i-n+1..w i-1) = 1 -  w:C(w i-n+1..w i-1w)>0 C(w i-n+1..w i-1w) - D C(w i-n+1..w i-1) 1 -  w:C(w i-n+1..w i-1w>0) P BKN(w|w i-n+2..w i-1) Như vậy: P BKN(w i|w i-2w i-1) =    C(w i-2w i-1w i) - D C(w i-2w i-1) nếu C(w i-2w i-1w i) > 0 (w i-2w i-1)P BKN(w i|w i-1) nếu C(w i-2w i-1w i) = 0 P BKN(w i|w i-1) =    C(w i-1w i) - D C(w i-1) nếu C(w i-1w i) > 0 (w i-1)P BKN(w i) nếu C(w i-1w i) = 0 P BKN(w i) = N(vw i) - D  w N(vw)  Mô hình nội suy: P IKN(w i|w i-n+1..w i-1) = C(w i-n+1..w i) - D C(w i-n+1..w i-1) + (w i-n+1..w i-1)P IKN(w i|w i-n+2..w i-1) Trong đó: o (w i-n+1..w i-1) = D N(w i-n+1..w i-1v) C(w i-n+1..w i-1) với N(w i-n+1..w i-1v) là số lượng từ v khác nhau xuất hiện liền sau cụm w i-n+1..w i trong tập huấn luyện 12 o P IKN(w i) = N(vw i) - D  w N(vw) +  1V với N(vw) là số lượng từ v khác nhau xuất hiện liền trước từ w trong tập huấn luyện. o  = D N(v)  w N(vw) Như vậy: P IKN(w i|w i-2w i-1) = C(w i-2w i-1w i) - D C(w i-2w i-1) + (w i-2w i-1)P IKN(w i|w i-1) P IKN(w i|w i-1) = C(w i-1w i) - D C(w i-1) + (w i-1)P IKN(w i) P IKN(w i) = N(vw i) - D  w N(vw) +  1V Trong cả 2 mô hình nội suy và truy hồi, D được chọn: D = N 1 N1 + 2N 2 2.4.5 Phương pháp làm mịn Kneser - Ney cải tiến bởi Chen - GoodMan: Công thức tính toán của thuật toán Kneser-Ney cải tiến bởi Chen và GoodMan giống công thức của thuật toán Kneser-Ney, tuy nhiên hằng số D bị thay đổi. Chen và GoodMan chọn D như sau: D =   0 nếu c(w i-n+1..w i) = 0 D 1 nếu c(w i-n+1.. w i) = 1 D 2 nếu c(w i-n+1.. w i) = 2 D 3 nếu c(w i-n+1.. w i) >= 3 Với Y = N 1 (N 1 + 2N 2) D 1 = 1 - 2Y N 2 N 1 D 2 = 1 - 3Y N 3 N 2 13 D 3 = 1 - 4Y N 4 N 3 Trong đó: N i là số lượng cụm N-gram có số lần xuất hiện bằng i Chú ý rằng: với mỗi bậc của N-gram ta lại có một bộ 3 hằng số trên. Điều đó có nghĩa là: unigram, bigram, ... có các hằng số trên là khác nhau. 2.5 Kỹ thuật làm giảm kích thước dữ liệu: Các kỹ thuật này làm giảm kích thước của mô hình ngôn ngữ. Mặc dù đều có chung một mục tiêu, nhưng mỗi kỹ thuật lại có hiệu quả khác nhau. Có ba kỹ thuật chính, bao gồm:  Pruning (loại bỏ): làm giảm số lượng các cụm Ngram trong mô hình ngôn ngữ bằng cách loại bỏ các cụm Ngram không quan trọng  Quantization (lượng tử hóa): thay đổi cấu trúc thông tin của mỗi cụm Ngram trong mô hình ngôn ngữ.  Compression (nén): nén cấu trúc dữ liệu sử dụng trong việc lưu trữ các cụm Ngram trong mô hình ngôn ngữ 2.5.1 Loại bỏ (pruning): Số lượng các cụm Ngram xuất hiện vài lần trong tập huấn luyện thường là lớn so với tổng số các cụm Ngram. Các cụm Ngram đó thường là lỗi ngữ pháp trong tập huấn luyện, hoặc là một số dạng đặc biệt như: tên riêng, từ viết tắt, ... [10] Những cụm Ngram này thường rất ít sử dụng trong thực tế, do đó việc tồn tại của chúng có thể làm ảnh hưởng đến độ chính xác của mô hình ngôn ngữ. Chính vì lý do đó, kỹ thuật pruning tập trung vào việc loại bỏ các cụm Ngram như vậy. Có 2 phương pháp chính:  Cut-off (cắt bỏ): phương pháp này tập trung vào việc loại bỏ các cụm Ngram có tần số thấp trong tập huấn luyện  Weighted difference: phương pháp này tập trung vào việc đánh giá và loại bỏ các cụm Ngram không hiệu quả dựa vào xác suất của các cụm Ngram trước và sau khi làm mịn theo phương pháp truy hồi. 2.5.1.1 Cắt bỏ (cut-off): Phương pháp này là phương pháp thông dụng, thường được sử dụng để làm giảm kích thước mô hình ngôn ngữ. Trong thực tế, trong tập văn bản huấn luyện, có rất 14 nhiều cụm bigram và trigram chỉ xuất hiện một hoặc hai lần trong đoạn văn bản chứa trên một triệu từ. Khi loại bỏ các cụm Ngram này ra khỏi mô hình ngôn ngữ, thông tin về chúng (bao gồm tần số và xác suất) của chúng vẫn có thể nhận lại được thông qua việc sử dụng mô hình truy hồi hay nội suy. Phương pháp cut-off hoạt động như sau: Nếu cụm Ngram xuất hiện ít hơn k lần trong tập văn bản huấn luyện thì cụm Ngram đó sẽ bị loại bỏ ra khỏi mô hình ngôn ngữ. Khi tính toán, nếu gặp lại các cụm Ngram này, thì tần số và xác suất của chúng sẽ được tính toán thông qua các phương pháp làm mịn đã trihf bày ở trên. Trong một mô hình ngôn ngữ, chúng ta có thể sử dụng các tham số k khác nhau với các cụm Ngram có độ dài khác nhau. Ví dụ: với unigram thì sử dụng k = 10, với bigram thì k = 1, và trigram thì k =5 Như vậy, việc chọn tham số k cho phương pháp cut-off chính là vấn đề chính của kỹ thuật này. Nếu k quá lớn, chúng ta sẽ bỏ sót thông tin về một số cụm Ngram, hiệu suất của ứng dụng cũng bị giảm. Nhưng ngược lại, nếu k quá nhỏ, thì kích thước của mô hình ngôn ngữ cũng giảm không đáng kể. Có 2 cách để chọn k: chọn k theo phương pháp chạy thử nhiều lần hoặc chọn k theo tỉ lệ phần trăm số lượng các cụm Ngram. Chọn k theo phương pháp chạy thử nhiều lần nghĩa là ta dùng phương pháp cut-off cho mô hình ngôn ngữ với nhiều giá trị k khác nhau rồi đánh giá độ hỗn loạn thông tin(perplexity) của tập văn bản đầu vào sau khi sử dụng phương pháp cut-off. Sau khi có kết quả, ta sẽ chọn tham số k sao cho mô hình ngôn ngữ là hiệu quả nhất (độ hỗn loạn thông tin của tập văn bản huấn luyện và kích thước mô hình ngôn ngữ đều thấp). Kỹ thuật này giúp chúng ta chọn được k phù hợp, tuy nhiên rất mất thời gian do phải chạy thử với rất nhiều giá trị của k. Tuy nhiên, để đạt được một mô hình ngôn ngữ hiệu quả thì đây là một phương pháp tốt. Phương pháp thứ hai, chọn k dựa theo tỷ lệ phần trăm của số lượng các cụm Ngram phải bảo đảm rằng số cụm Ngram xuất hiện không quá k lần chiếm h% so với tổng số các cụm Ngram. Ví dụ: nếu h=50, thì chọn k sao cho số lượng các cụm Ngram xuất hiện không quá k lần (sẽ bị loại bỏ) chiếm 50% tổng số các cụm Ngram đã thống kê. Phương pháp này tuy nhanh hơn nhưng độ chính xác không cao bằng phương pháp thứ nhất đã đề cập ở trên 15 2.5.1.2 Sự khác biệt trọng số (Weighted difference): Phương pháp cut-off chỉ quan tâm đến việc loại bỏ các cụm Ngram có tần số thấp, trong khi phương pháp weighted difference(sự khác biệt trọng số) thì quan tâm đến nhiều thông tin trong mô hình ngôn ngữ hơn như mối quan hệ giữa các cụm Ngram, xác suất của từng cụm Ngram, ... [10] Như đã trình bày ở các phần trên, nếu một cụm Ngram không xuất hiện trong tập huấn luyện, thì xác suất của nó được ước lượng thông qua xác suất của các cụm Ngram ngắn hơn (phương pháp làm mịn kiểu truy hồi) Do đó, nếu xác suất thực tế của một cụm Ngram xấp xỉ với xác suất có được theo công thức truy hồi, thì chúng ta chẳng cần lưu trữ cụm Ngram đó làm gì nữa. Đó chính là ý tưởng của phương pháp weighted difference. Sự khác biệt trọng số của một cụm Ngram được định nghĩa bằng: w.d.factor = K * log((xác suất ban đầu) - log(xác suất truy hồi)) K chính là tham số sử dụng trong phương pháp làm mịn Good Turing. Dựa vào nhân tố w.d.factor ở trên, chúng ta sẽ biết nên giữ lại hay loại bỏ một cụm Ngram. Nếu w.d.factor nhỏ hơn một ngưỡng nhất định, thì cụm Ngram đó sẽ bị loại bỏ khỏi mô hình ngôn ngữ. Và ngưỡng nhất định đó chúng ta có thể bằng cách tìm theo phương pháp thử sai hoặc đặt nó bằng một giá trị hằng số. Trong thực tế, phương pháp này mất nhiều thời gian hơn phương pháp cut-off do phải tính toán hệ số w.d.factor cho tất cả các cụm Ngram trong mô hình ngôn ngữ. Và sự khác biệt lớn nhất giữa 2 phương pháp loại bỏ này chính là phương pháp weighted different chỉ hoạt động trong mô hình ngôn ngữ kiểu truy hồi, còn phương pháp cut-off thì chỉ hoạt động trong mô hình ngôn ngữ lưu trữ dữ liệu dưới dạng tần số. 2.5.2 Đồng hóa (Quantization): Thuật toán quantization (đồng hóa) làm giảm số lượng bit dùng để lưu trữ các biến trong mô hình ngôn ngữ. Thuật toán này gồm hai bước chính Bước thứ nhất, liệt kê và lưu trữ tất cả các tần số của các cụm Ngram vào một bảng. Sau đó, thay thế tần số của các cụm Ngram trong mô hình ngôn ngữ bằng chỉ số của tần số trong bảng. Như vậy, thay vì sử dụng b = log 2(tần số lớn nhất) bit để lưu trữ tần số của một cụm Ngram, thì chúng ta chỉ cần sử dụng b’ = log 2(kích thước của bảng) bit cho mỗi cụm Ngram. Do kích thước của bảng nhỏ hơn nhiều so với giá trị tần số lớn nhất của các cụm Ngram nên b’ < b, tức là kích thước mô hình ngôn ngữ đã giảm so với cách lưu trữ ban đầu. 16 Tuy nhiên, để tăng tính hiệu quả, ở bước thứ hai, thuật toán này đồng hóa một số giá trị trong bảng tần số. Điều đó có nghĩa là, một số giá trị trong bảng có giá trị gần với nhau sẽ được thay thế bằng một con số chung. Sau bước này, chúng ta sẽ thu được một bảng tần số với ít giá trị hơn, cũng tức là đã làm giảm kích thước của mô hình ngôn ngữ đi một lần nữa. 2.5.3 Nén (Compression): Mô hình ngôn ngữ nào cũng có một cấu trúc dữ liệu. Do đó nếu cấu trúc dữ liệu đó được nén lại bằng các thuật toán nén, thì kích thước của mô hình ngôn ngữ tất nhiên là giảm. Tuy nhiên, khi một mô hình ngôn ngữ bị nén, thì độ chính xác và tốc độ của mô hình ngôn ngữ đều giảm (do phải giải nén, hoặc bị mất dữ liệu do thuật toán nén chưa tốt) [10] Do không hiệu quả nên kỹ thuật này hiện nay không còn phổ biến như hai kỹ thuật trên, tuy vẫn được sử dụng bởi Microsoft (trong modul kiểm lỗi chính tả của Microsoft Office 2007) 2.6 Độ đo: Để xây dựng được một hình ngôn ngữ hiệu quả, chúng ta phải có cách để đánh giá chúng. Dưới đây là một số phương pháp phổ biến để đánh giá một mô hình ngôn ngữ:  Entropy - Độ đo thông tin  Perplexity - Độ hỗn loạn thông tin  Error rate - Tỉ lệ lỗi 2.6.1 Entropy – Độ đo thông tin: Entropy là thước đo thông tin, có giá trị rất lớn trong xử lý ngôn ngữ. Nó thể hiện mức độ thông tin trong ngữ pháp, thể hiện sự phù hợp của một câu với một ngôn ngữ, và dự đoán được từ tiếp theo trong cụm Ngram[1][10]. Entropy của một biến ngẫu nhiên X được tính theo công thức: H(X) = -  x  X p(x)log 2p(x) Xét các câu gồm hữu hạn m từ W = (w 1, w 2, ..., w m) trong ngôn ngữ L. Ta có công thức tính entropy như sau: 17 H(w 1, w 2, ..., w m) = -  W  L p(w 1, w 2, ..., w m)log 2p(w 1, w 2, ..., w m) Từ công thức trên, ta có thể đưa ra công thức tính tỉ lệ entropy trên các từ như sau: 1 m H(w 1, w 2, ..., w m) = - 1 m  W  L p(w 1, w 2, ..., w m)log 2p(w 1, w 2, ..., w m) Thực tế thì tỉ lệ entropy trên các từ thường được sử dụng vì giá trị của nó không phụ thuộc vào độ dài các câu [9]. Tuy nhiên, để tính được entropy của một ngôn ngữ L theo công thức trên thì ta phải xét tới các câu dài vô hạn (tất cả các câu có thể có trong ngôn ngữ L), đó là điều không thể. Do đó, ta có thể tính xấp xỉ tỉ lệ entropy trên các từ theo công thức sau: H(L) = - lim m   1m H(w 1, w 2, ..., w m) = - lim m   1m  W  L p(w 1, w 2, ..., w m)log 2p(w 1, w 2, ..., w m) Định lý Shannon-McMillan-Breiman đã chỉ ra rằng nếu ngôn ngữ ổn định (chứa các câu gồm các từ với cấu trúc thông dụng) thì công thức trên có thể biến đổi thành: H(L) = - lim m   1m log p(w 1, w 2, ..., w m) Với công thức trên, ta có thể sử dụng công thức Bayes và xác suất của các n- gram để tính p(w 1, w 2, ..., w n): H(L) = - lim m   1m log [ p(w n|w 1w 2..w n-1) * p(w n+1|w 2w 3.. w n) * ... * p(w m |w m-n+1...w m-1) ] Công thức trên đã được biến đổi qua nhiều bước với các xấp xỉ gần đúng, do vậy để tăng tính chính xác khi sử dụng độ đo entropy thì câu kiểm tra cần phải đủ dài và tổng quát (phân tán rộng) để tránh tập trung vào các xác suất lớn (chỉ chứa các cụm thông dụng). Các bước biến đổi gần đúng công thức trên khiến giá trị H(L) tính theo công thức cuối cùng sẽ lớn hơn giá trị H(L) gốc. Do vậy, khi tính H(L) của các mô hình ngôn 18 ngữ khác nhau trên ngôn ngữ L, mô hình nào cho H(L) nhỏ hơn thì mô hình ngôn ngữ đó thể hiện chính xác ngôn ngữ L hơn. 2.6.2 Perplexity – Độ hỗn loạn thông tin: Độ hỗn loạn thông tin (perplexity) cũng được dùng làm thước đo để đánh giá độ chính xác của một mô hình ngôn ngữ. Trong mô hình ngôn ngữ, độ hỗn loạn thông tin của một văn bản với từ “cái” thể hiện số từ có thể đi sau từ “cái”. Độ hỗn loạn thông tin của một mô hình ngôn ngữ nói chung, có thể hiểu đơn giản là số lựa chọn từ trung bình mà mô hình ngôn ngữ phải đưa ra quyết định. Như vậy, độ hỗn loạn thông tin càng thấp, thì độ chính xác của mô hình ngôn ngữ càng cao. Độ hỗn loạn thông tin có thể tính theo công thức: P(L) = 2H(L) Ví duL dãy kí tự a, b, …, z có perplexity là 26 còn bảng mã ASCII có perplexity là 256. 2.6.3 Error rate – Tỉ lệ lỗi: Người ta thường sử dụng độ đo entropy và perplexity để so sánh độ chính xác của các mô hình ngôn ngữ khi xây dựng một mô hình ngôn ngữ tổng quát. Trong các bài toán cụ thể, người ta sử dụng tỉ lệ lỗi để so sánh độ chính xác của các mô hình ngôn ngữ [10]. Soát lỗi chính tả: xét tỉ lệ giữa số lỗi phát hiện sai hoặc không phát hiện được trên tổng số lỗi có trong văn bản. Phân đoạn từ: xét tỉ lệ giữa từ phân đoạn sai trên tổng số từ có trong văn bản Bỏ dấu tự động: xét tỉ lệ giữa số từ bị bỏ dấu nhầm trên tổng số từ có trong văn bản Tỉ lệ lỗi thấp chứng tỏ mô hình ngôn ngữ hiệu quả. Việc sử dụng tỉ lệ lỗi để đánh giá đưa lại kết quả chính xác nhất khi muốn chọn lựa mô hình ngôn ngữ phù hợp để giải quyết bài toán cụ thể. Tỉ lệ lỗi thường tỉ lệ thuận với giá trị entropy nhưng đôi khi mức độ tăng/giảm của tỉ lệ lỗi và entropy không đều. 19 Chương 3 Ứng dụng của mô hình ngôn ngữ trong mô hình dịch máy thống kê: 3.1 Dịch máy: Dịch tự động hay còn gọi là dịch máy là một trong những ứng dụng quan trọng của xử lý ngôn ngữ tự nhiên, là sự kết hợp của ngôn ngữ, dịch thuật và khoa học máy tính[2]. Như tên gọi, dịch tự động thực hiện dịch một ngôn ngữ này (gọi là ngôn ngữ nguồn) sang một hoặc nhiều ngôn ngữ khác (gọi là ngôn ngữ đích) một cách tự động dựa vào máy tính mà không có sự can thiệp của con người. Dịch máy có hai hướng tiếp cận chính như sau:  Hướng luật (Rules-based): dịch dựa vào các luật viết tay. Các luật này dựa trên từ vựng hoặc cú pháp của ngôn ngữ. Ưu điểm của phương pháp này là có thể giải quyết được một số trường hợp dịch , nhưng thường mất rất nhiều công sức khi xây dựng và tính khả chuyển không cao.  Thống kê (Statistical): tạo ra bản dịch sử dụng phương pháp thống kê dựa trên bản dịch song ngữ. 3.2 Dịch máy thống kê: 3.2.1 Giới thiệu: Dịch máy thống kê là một hướng tiếp cận của dịch máy đặc trưng bởi việc sử dụng các phương pháp học máy. Thay vì xây dựng các từ điển, các quy luật chuyển đổi bằng tay, hệ dịch này tự động xây dựng các từ điển, các quy luật dựa trên kết quả thống kê có được từ các kho ngữ liệu. Chính vì vậy, dịch máy thống kê có tính khả chuyển cao áp dụng được cho bất kỳ cặp ngôn ngữ nào. Ý tưởng đầu tiên về dịch máy thống kê được giới thiệu bởi Warren Weaver vào năm 1949. Tuy nhiên, khi dịch máy thống kê mới được giới thiệu lại bởi các nhà nghiên cứu thuộc trung tâm nghiên cứu IBM Thomas J. Watson vào năm 1991, nó mới bắt đầu được chú y và thu hút được rất nhiều nhà nghiên cứu. Cho tới hôm nay, dịch máy thống kê đang là phương pháp dịch thuật được nghiên cứu rộng rãi nhất. 3.2.2 Nguyên lý và các thành phần: Cho trước câu ngôn ngữ nguồn f, mục tiêu của mô hình dịch máy là tìm ra câu e của ngôn ngữ đích sao cho xác suất P(e|f) là cao nhất. 20 Có nhiều cách tiếp cận để tính được xác suất P(e|f), tuy nhiên cách tiếp cận trực quan nhất là áp dụng công thức Bayes: P(e|f) = P(e)P(f|e)P(f) Trong đó P(f|e) là xác suất câu ngôn ngữ nguồn là bản dịch của câu ngôn ngữ đích, còn P(e) là xác suất xuất hiện câu e trông ngôn ngữ. Việc tìm kiếm câu e* phù hợp chính là việc tìm kiếm e* làm cho giá tri P(e*)P(f|e*) là lớn nhất. Để mô hình dịch là chính xác, thì công việc tiếp theo là phải tìm ra tất cả các câu e* có thể có trong ngôn ngữ đích từ câu ngôn ngữ nguồn f. Thực hiện công việc tìm kiếm hiệu quả chính là nhiệm vụ của bộ giải mã (decoder). Như vậy, một mô hình dịch máy bao gồm 3 thành phần:  Mô hình ngôn ngữ: Tính toán được xác suất của câu ngôn ngữ nguồn. Thành phần này chính là mô hình ngôn ngữ đã được mô tả ở phần 2 của luận văn  Mô hình dịch: Cho biết xác suất của câu ngôn ngữ nguồn là bản dịch từ câu ngôn ngữ đích .  Bộ giải mã: Tìm kiếm tất cả các câu ngôn ngữ đích e có thể có từ câu ngôn ngữ nguồn f. Mô hình dịch từ tiếng Anh sang tiếng Việt có thể hình dung thông qua biểu đồ dưới đây: Hình 3-1: mô hình dịch máy thống kê từ tiếng Anh sang tiếng Việt Mô hình dịch của mô hình ngôn ngữ đã được trình bày ở chương 2 của luận văn. Ở hai phần 3.2.3 và 3.2.4, luận văn chỉ đề cập đến hai thành phần còn lại của mô hình dịch máy thống kê. 21 3.2.3 Mô hình dịch: Mô hình dịch có 3 hướng tiếp cận chính:  Mô hình dịch dựa trên từ (word-based)  Mô hình dịch dựa trên cụm từ (phrase-based)  Mô hình dịch dựa trên cú pháp (syntax-based) Cả 3 hướng tiếp cận trên đều dựa trên một tư tưởng. Đó là sự tương ứng giữa hai câu (alignment) 3.2.3.1 Sự gióng hàng (alignment): Tất cả các mô hình dịch thống kê đều dựa trên sự tương ứng của từ. Sự tương ứng của từ ở đây chính là một ánh xạ giữa một hay nhiều từ của ngôn ngữ nguồn với một hay nhiều từ của ngôn ngữ đích trong tập hợp các câu văn bản song ngữ.[2] Theo nguyên tắc, chúng ta có thể có mối liên hệ tùy ý giữa các từ của ngôn ngữ nguồn với các từ của ngôn ngữ đích. Tuy nhiên, để cho đơn giản, mô hình dịch máy dựa trên từ (word-based) đưa ra một giả định: mỗi từ của ngôn ngữ đích chỉ tương ứng với một từ của ngôn ngữ nguồn. Nếu áp dụng giả định này, chúng ta có thể biểu diễn một sự tương ứng từ bằng chỉ số của các từ trong ngôn ngữ nguồn tương ứng với từ trong ngôn ngữ đích. Như trong ví dụ ở hình 3.1[2] dưới đây có thể biểu diễn một tương ứng từ giữa tiếng Pháp và tiếng Anh bởi một dãy các chỉ số như sau: A = 2, 3, 4, 5, 6, 6, 6. Hình 3-2: sự tương ứng một - một giữa câu tiếng Anh và câu tiếng Pháp Trong thực tế, có rất nhiều từ ở ngôn ngữ đích không tương ứng với từ nào trong ngôn ngữ nguồn. Để cho tổng quát, ta thêm một từ vô giá trị (null) vào đầu câu ngôn ngữ nguồn và những từ ở ngôn ngữ đích không tương ứng với từ nào sẽ được ánh xạ 22 với từ vô giá trị đó. Hình 3.2[2] ở dưới thể hiện một tương ứng từ giữa hai câu tiếng Anh và tiếng Tây Ban Nha khi cho thêm từ vô giá trị vào đầu câu tiếng Anh. Hình 3-3: sự tương ứng giữa câu tiếng Anh với câu tiếng Tây Ban Nha khi cho thêm từ vô giá trị (null) vào đầu câu tiếng Anh Trong khi mô hình dịch dựa trên từ (word-based) chỉ giải quyết trường hợp một từ của ngôn ngữ đích chỉ tương ứng bởi một từ của ngôn ngữ nguồn, thì mô hình dịch dựa trên cụm từ (pharse-based) có thể giải quyết cả hai trường hợp còn lại là: một từ của ngôn ngữ này tương ứng với nhiều từ của ngôn ngữ kia và nhiều từ của ngôn ngữ này tương ứng với nhiều từ của ngôn ngữ kia. Hình 3.3 và 3.4[2] ở dưới minh họa các tương ứng nói trên. Hình 3-4: sự tương ứng một - nhiều giữa câu tiếng Anh với câu tiếng Pháp Hình 3-5: sự tương ứng nhiều - nhiều giữa câu tiếng Anh với câu tiếng Pháp. 3.2.3.2 Mô hình dịch dựa trên từ (Word-based): Mô hình dịch dựa trên từ là thế hệ đầu tiên của mô hình dịch máy thống kê và được nghiên cứu và phát triển bởi IBM[2]. Như đã trình bày ở phần 3.2.3.1, mô hình dịch này dựa trên sự tương ứng của các từ theo tương ứng một một (một từ của ngôn ngữ này chỉ tương ứng với một từ của ngôn ngữ kia và ngược lại). Cụ thể hơn, giả sử 23 câu ngôn ngữ nguồn là e 1e 2...e n và câu ngôn ngữ đích là f 1f 2...f m, khi đó mỗi từ f j chỉ tương ứng với 1 và chỉ 1 từ trong câu ngôn ngữ nguồn hoặc là không tương ứng với từ nào. Do đó, một sự tương ứng giữa các từ của câu ngôn ngữ nguồn và câu ngôn ngữ đích có thể biểu diễn bằng một dãy m số: {a 1, a 2, ... a m} trong đó a j là chỉ số của từ trong ngôn ngữ nguồn tương ứng với từ f j của ngôn ngữ đích(a j nhận các giá trị từ 1 đến l). Với mô hình IBM thứ nhất, giả định rằng mỗi biến a j là độc lập, khi đó tương ứng tối ưu nhất chính là: a = am1 arg ax  i = m i = 1 p(a i)*p(f i|e a i) Như vậy, theo mô hình IBM thứ nhất, chúng ta có thể tính xác suất P(f|e) theo công thức sau: P(f|e) =  i = m i = 1  a i = n a i = 0 p(a i)*p(f i|e a i) Tuy nhiên trên thực tế, mô hình IBM thứ nhất này có chất lượng dịch không cao. Ở các mô hình IBM tiếp theo, người ta cải tiến các công thức và đưa ra những tương ứng, cũng như tính lại xác suất P(f|e) một cách tốt hơn. Tuy nhiên, do tiếp cận theo hướng tương ứng một một giữa các từ, nên mô hình dịch dựa trên từ nói chung và các mô hình dịch IBM nói riêng đã không còn phổ biến. Hiện nay, các mô hình dịch theo hướng cụm từ được sử dụng rộng rãi và dần trở nên phổ biến hơn. 3.2.3.3 Mô hình dịch dựa trên cụm từ (Phrase-based): Trong thực tế, người ta thường dựa vào cụm từ để dịch nhiều hơn là dựa vào từ. Ví dụ như cụm “take time” được dịch là “mất thời gian” trong khi nếu dịch theo từ, thì kết quả sẽ là “giữ” và “thời gian”. Rõ ràng có thể thấy, dịch dựa vào cụm từ sẽ cho kết quả tốt hơn so với dịch dựa vào từ. Có nhiều mô hình dịch dựa trên cụm từ nhưng luận văn này chỉ đề cập đến mô hình của Koehn[2]. Với mô hình dịch này, một câu ngôn ngữ nguồn e được tách thành các cụm từ e 1 , e 2 , ..., e n ; sau đó các cụm này được dịch ra thành các cụm thuộc ngôn ngữ đích f i . Cuối cùng các cụm f i này được sắp xếp lại theo một thứ tự nhất định. 24 Xác suất dịch trong mô hình dịch dựa trên cụm từ phụ thuộc vào xác suất dịch của cụm từ và xác suất bóp méo. Trọng số ( f i | e i ) là xác suất dịch cụm e i thành cụm f i , còn xác suất bóp méo d thể hiện xác suất sắp xếp các cụm f i là chính xác. Sự bóp méo trong dịch máy thống kê dựa trên cụm từ là thước đo khoảng cách giữa vị trí của một cụm từ trong ngôn ngữ nguồn so với ngôn ngữ đích. Cụ thể hơn, sự bóp méo được biểu diễn bởi d(a i - b i-1), trong đó a i là vị trí bắt đầu của cụm từ f i , còn b i-1 là vị trí kết thúc của cụm từ f i-1 và d(a i - b i-1) =  |a i - b i-1 - 1| với  là một hằng số nhỏ. Khi đó, xác suất dịch P(f|e) được tính theo công thức: P(f|e) =  i = n i = 1 ( f i | e i ) d(a i - b i-1) 3.2.3.4 Mô hình dịch dựa trên cú pháp (Syntax-based): Cả 2 mô hình dịch dựa trên từ và cụm từ đều chỉ quan tâm đến sự tương ứng và ngữ nghĩa của từng từ trong câu ngôn ngữ nguồn và đích mà không quan tâm tới ngữ pháp, hình thái của cả 2 câu. Mô hình dịch dựa trên cú pháp không chỉ quan tâm tới ngữ nghĩa của từng từ mà còn chú trọng tới cú pháp của câu. Với mô hình dịch này, một câu ngôn ngữ nguồn e sẽ được phân tích thành cây cú pháp[8]. Cây cú pháp này sẽ được sắp xếp lại để phù hợp với cú pháp của câu ngôn ngữ đích. Sau đó, một số từ mới có thể được chèn vào cây hiện tại cho phù hợp hơn với cú pháp của ngôn ngữ đích. Cuối cùng, các từ trong cây cú pháp của câu ngôn ngữ nguồn sẽ được dịch sang ngôn ngữ đích và ta thu được câu ngôn ngữ đích từ cây cú pháp trên. Hình 3.7 [8] dưới đây mô tả các bước làm việc của một mô hình dịch dựa trên cú pháp từ tiếng Anh sang tiếng Nhật. 25 Hình 3-6: mô hình dịch dựa trên cây cú pháp 3.2.4 Bộ giải mã: Như đã trình bày ở các phần trên, nhiệm vụ của bộ giải mã chính là: cho trước câu ngôn ngữ nguồn f, tìm câu ngôn ngữ đích e tốt nhất được dịch từ f. Câu ngôn ngữ đích e tốt nhất chính là câu làm cho giá trị P(f|e)*P(e) là lớn nhất[2]. Do không gian tìm kiếm là rất lớn, nên bộ giải mã trong mô hình dịch máy thống kê thường áp dụng các thuật toán tìm kiếm tối ưu. Thuật toán mà bộ giải mã thường áp dụng có tên là A*, là một trong các phương pháp tìm kiếm tốt nhất - đầu tiên. Giải thuật A* có thể tóm tắt như sau: tại mỗi bước mở rộng không gian tìm kiếm, ta sử dụng các hàm ước lượng, đánh giá trọng số để kết quả tìm được luôn là tốt nhất có thể và là kết quả tìm thấy đầu tiên. 3.3 Các phương pháp đánh giá bản dịch: Đánh giá độ chính xác của hệ thống dịch máy là một nhiệm vụ rất vất vả và khó khăn. Để đánh giá độ chính xác của bản dịch, ta có thể đánh giá trực tiếp thông qua người dùng hoặc đánh giá tự động bằng máy tính. 3.3.1 Đánh giá trực tiếp bằng con người: Để đánh giá độ chính xác của hệ thống dịch máy, ta có thể để con người trực tiếp đánh giá. Chúng ta có thể đưa ra một thước đo cho độ trôi chảy của bản dịch (ví dụ từ 1 đến 5 hay từ 1 đến 10 tùy thuộc vào độ trôi chảy của bản dịch), sau đó cho những người tham gia đánh giá đánh giá các câu trong bản dịch theo thang điểm đó. Như vậy, văn bản nào có điểm trung bình càng cao, thì chất lượng bản dịch đó càng tốt. Ngoài ra, cũng có thể đánh giá độ trôi chảy, độ chính xác của bản dịch thông qua thời gian 26 mà người đọc đọc hiểu được bản dịch đó. Rõ ràng, bản dịch nào mà người đọc đọc hiểu càng nhanh, thì bản dịch đó càng chính xác. Phương án đánh giá bản dịch bằng chính con người tuy rất dễ thực hiện, nhưng chi phí thì rất lớn, và nếu bản dịch có kích thước càng lớn thì phương pháp này càng kém hiệu quả. Ngày nay, các mô hình dịch máy đều áp dụng phương pháp đánh giá tự động, chi phí thấp nhưng hiệu quả cũng khá là cao. 3.3.2 Đánh giá tự động: phương pháp BLEU BLEU là một phương pháp dùng để đánh giá chất lượng bản dịch được đề xuất bới IBM tại hội nghị ACL ở Philadelphie vào tháng 7-2001. Ý tưởng chính của phương pháp này là so sánh kết quả bản dịch tự động bằng máy với các bản dịch mẫu của con người, bản dịch máy nào càng giống với bản dịch mẫu của con người thì bản dịch đó càng chính xác. Việc so sánh trên được thực hiện thông qua việc thống kê sự trùng khớp của các từ trong hai bản dịch có tính đến thứ tự của chúng trong câu (phương pháp n-grams theo từ)[9]. Trong ví dụ như hình 3.6, có 2 bản dịch bằng máy được đem so sánh với 3 bản dịch mẫu của con người. Có thể thấy rằng, bản dịch thứ máy nhất có nhiều từ chung (đóng khung) với các bản dịch mẫu hơn bản dịch máy thứ hai, nên theo phương pháp này có thể kết luận : bản dịch máy thứ nhất chính xác hơn bản dịch máy thứ hai Hình 3-7: sự trùng khớp của các bản dịch máy với bản dịch mẫu Với một bản dịch máy và bản dịch mẫu thứ n, phương pháp BLEU trước tiên thống kê số lần tối thiểu của cụm Ngram xuất hiện trong từng cặp câu (câu dịch máy và câu dịch mẫu), sau đó đem tổng trên chia cho tổng số cụm Ngram trong toản bản dịch máy. Tỉ lệ trùng khớp của một bản dịch máy và bản dịch mẫu thứ n được tính theo công thức : 27 P n =  s  bản dịch máy  w  s số lượng tối thiểu cụm w có trong bản mẫu  s  bản dịch máy  w  s số lượng cụm n-gram w trong bản dịch máy Trong đó s là các câu trong bản dịch máy, w là các cụm ngram có trong câu s. Điểm BLEU đánh giá một bản dịch máy với n bản dịch mẫu được tính theo công thức : BLEU = BP * (1N  i = N i = 1 log p i) Trong đó : BP =  1 nếu c>r e(1-r/c) với c<=r với c là độ dài của bản dịch máy, r là độ dài lớn nhất của các bản dịch mẫu N là số lượng các bản dịch mẫu Từ công thức trên, có thể thấy giá trị BLEU nằm trong khoảng 0 đến 1. Bản dịch nào có điểm BLEU càng cao, chứng tỏ độ trùng khớp giữa bản dịch máy và bản dịch mẫu càng nhiều, thì bản dịch đó càng chính xác. 28 Chương 4 Thực nghiệm: 4.1 Công cụ: Để xây dựng mô hình ngôn ngữ Ngram cho tiếng Việt, chúng tôi đã xây dựng và sử dụng một số công cụ sau: 4.1.1 Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện: Bộ công cụ này được chúng tôi cài đặt bằng ngôn ngữ C#. Bộ công cụ có các công cụ như: lấy nội dung văn bản từ các trang báo mạng, chuẩn hóa văn bản, cắt và ghép các tệp văn bản. Để có kích thước tệp văn bản lớn phục vụ cho quá trình huấn luyện mô hình ngôn ngữ, chúng tôi đã phải xây dựng một chương trình có nhiệm vụ lọc nội dung văn bản từ các file html. Chương trình này tự động tìm tất cả các file có định dạng html trong một thư mục nào đó, bỏ các đoạn mã, bỏ các thẻ, link, bảng, hình ảnh, ... chỉ giữ lại nội dung văn bản rồi ghi lại dưới định dạng txt. Sau đó, chúng tôi tiếp tục xây dựng một chương trình khác, có nhiệm vụ chuẩn hóa văn bản. Chương trình này có các chức năng chính như: chuẩn hóa dấu cách, chuẩn hóa dấu cho tiếng Việt (ví dụ: hoà sửa thành hòa, vìên sửa thành viền, ...), tách ra mỗi câu trên một dòng. Đặc biệt, do văn bản đầu ra của chương trình dùng cho quá trình huấn luyện mô hình ngôn ngữ, nên chương trình này của chúng tôi còn có thêm một số tính năng như: thay thế các từ đặc biệt bởi một từ nào đó đặc trưng hơn (ví dụ: tên người, số, ngày tháng, ...), xóa bỏ các câu quá ngắn, xóa bỏ các câu các từ không có trong từ điển tiếng Việt. Ngoài ra, để tăng và giảm kích thước tệp văn bản một cách dễ dàng, chúng tôi còn xây dựng thêm các tiện ích cắt và ghép tệp văn bản. Tiện ích này giúp người dùng dễ dàng tạo được file văn bản có kích thước phù hợp để dễ dàng huấn luyện và khảo sát mô hình ngôn ngữ. 4.1.2 Công cụ tách từ cho tiếng Việt - vnTokenizer: VnTokenizer là chương trình tách từ tiếng Việt tự động, được thực hiện bởi một nhóm GV thuộc Khoa Toán Cơ Tin học, trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội thực hiện. Phiên bản đầu tiên của chương trình được viết từ năm 2001 và phiên bản mới nhất được nâng cấp ngày 28/12/2009 có một số tính năng chính như sau: 29  Tách các đơn vị từ vựng trong từ điển kèm thông tin từ loại.  Tách các dấu chấm câu, các ký hiệu chữ và số.  Tách các tên riêng, ngày tháng, các số (nguyên, thập phân)  Các mẫu tự cần tách được chỉ định trong tệp ngoài. Tệp này sử dụng các biểu thức chính quy (regular expressions) để định nghĩa các mẫu cần tách, do đó việc mở rộng tính năng cho chương trình để tách các mẫu chưa gặp rất dễ dàng, chỉ cần thêm định nghĩa cho mẫu chưa gặp vào tệp này. Dưới đây là một bài thơ sau khi sử dụng chương trình vnTokenizer: em ơi rất có_thể . anh chết giữa chiến_trường . đôi môi tươi đạn xé . chưa bao_giờ được hôn ! nhưng dù chết em ơi . yêu em anh không_thể . hôn em bằng đôi môi . của một người nô_lệ ! 4.1.3 Bộ công cụ xây dựng mô hình ngôn ngữ - SRILM: SRILM là bộ công cụ để xây dựng và áp dụng các mô hình ngôn ngữ thống kê , chủ yếu là để sử dụng trong nhận dạng tiếng nói, gắn thẻ thống kê và phân khúc, và dịch máy thống kê. Bộ công cụ này được phát triển bởi “Phòng thí nghiệm và nghiên cứu công nghệ giọng nói SRI” từ năm 1995, có thể chạy trên nền tảng Linux cũng như Windows. SRILM bao gồm các thành phần sau:  Một tập hợp các thư viện C + + giúp cài đặt mô hình ngôn ngữ, hỗ trợ cấu trúc dữ liệu và các chức năng tiện ích nhỏ.  Một tập hợp các chương trình thực thi thực hiện nhiệm vụ xây dựng mô hình ngôn ngữ, đào tạo và thử nghiệm mô hình ngôn ngữ trên dữ liệu, gắn thẻ hoặc phân chia văn bản, ... 30 Bộ công cụ SRILM có rất nhiều chương trình con, để xây dựng mô hình ngôn ngữ ta sử dụng 2 chương trình chính sau: 4.1.3.1 Ngram-count: Chương trình Ngram-count thống kê tần số xuất hiện của các cụm Ngram. Kết quả của việc thống kê được ghi lại vào một tệp hoặc sử dụng chúng để xây dựng mô hình ngôn ngữ [6]. Kết quả của việc thống kê được ghi lại theo định dạng sau: \data\ ngram 1=n1 ngram 2=n2 ... ngram N=nN \1-grams: p w [bow] ... \2-grams: p w1 w2 [bow] ... \N-grams: p w1 ... wN ... \end\ Văn bản trên bắt đầu với một tiêu đề giới thiệu số lượng các cụm Ngram với chiều dài là 1, 2, ...n. Tiếp theo, là từng đoạn chứa thông tin về các cụm Ngram có độ dài từ 1 đến n, mỗi đoạn bắt đầu bằng từ khóa \N-grams: trong đó N là độ dài của các cụm Ngram được liệt kê ở bên dưới. Mỗi dòng tiếp theo của từng đoạn bắt đầu bằng một số thực là logarit cơ số 10 xác suất của cụm Ngram, tiếp theo là n từ w1, w2, ... wn của cụm Ngram đó, và cuối cùng là trọng số truy hồi của cụm Ngram đó (có thể có) Chương trình Ngram có một số tùy chọn chính sau: 31 -text textfile: thống kê tần số các cụm Ngram từ tệp văn bản đầu vào textfile. Tệp văn bản này có thể chứa mỗi câu trên một dòng. Kí hiệu kết thúc và bắt đầu dòng mới sẽ được tự động thêm vào nếu trong tệp đầu vào chưa có. Các dòng trống trong tệp này cũng bị loại bỏ. -order n : thiết lập độ dài lớn nhất của các cụm Ngram sẽ thống kê bằng n. Giá trị mặc định nếu không thiết lập tham số này là n = 3 -memuse: hiển thị thông tin bộ nhớ mà chương trình sử dụng -lm lmfile: xây dựng mô hình ngôn ngữ truy hồi từ các tần số vừa thống kê, sau đó ghi lại vào tệp lmfile theo định dạng ở trên. -gtnmin count: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Tham số này thiết lập giá trị tần số nhỏ nhất với các cụm Ngram có độ dài là n. Tất cả các cụm ngram có độ dài là n, có tần số nhỏ hơn count sẽ bị loại bỏ khỏi mô hình ngôn ngữ Và dưới đây là một số tham số thiết lập phương pháp làm mịn cho mô hình ngôn ngữ. Nếu không tham số nào dưới đây được thiết lập thì chương trình sẽ sử dụng phương pháp làm mịn Good-Turing. -wbdiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử dụng phương pháp làm mịn Witten-Bell cho N-gram với độ dài là n. -kndiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử dụng phương pháp làm mịn của Kneser-Ney được thay đổi bởi Chen và GoodMan cho N- gram với độ dài là n. -ukndiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử dụng phương pháp làm mịn của Kneser-Ney với độ dài là n. -addsmoothn delta: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Làm mịn bằng cách thêm một lượng delta vào tần số của tất cả các cụm Ngram với độ dài là n. -interpolaten: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Tính toán tần số của các cụm Ngram có độ dài là n bằng cách nội suy từ các cụm Ngram có độ dài nhỏ hơn. 4.1.3.2 Ngram: Ngram là chương trình áp dụng mô hình ngôn ngữ để tính xác suất của một câu, tính toán độ hỗn loạn thông tin của văn bản, hay dùng để sinh các câu tiếp theo của 32 một văn bản [6]. Mô hình ngôn ngữ được đọc từ tập tin ghi theo định dạng đã trình bày ở phần 4.3.1, còn việc tính toán của chương trình bị chi phối bởi các tham số chính như sau: -order n : thiết lập độ dài lớn nhất của các cụm Ngram sẽ thống kê bằng n. Giá trị mặc định nếu không thiết lập tham số này là n = 3 -memuse: hiển thị thông tin bộ nhớ mà chương trình sử dụng -lm file: đọc mô hình ngôn ngữ từ tệp file. Tham số này là tham số bắt buộc, trừ khi tham số -null được chọn. -null: không sử dụng mô hình ngôn ngữ đọc từ tệp, mà sử dụng một mô hình ngôn ngữ đặt biệt (xác suất bằng 1 cho tất cả các từ). Tham số này thường được sử dụng trong việc gỡ lỗi. -ppl textfile: tính toán điểm(logarit cơ số 10 của xác suất) và độ hỗn loạn thông tin của tất cả các câu trong tệp textfile, mỗi câu viết trên một dòng. -gen number: sinh ngẫu nhiên number câu từ mô hình ngôn ngữ. 4.1.4 Bộ công cụ xây dựng mô hình dịch máy thống kê – MOSES: Moses là một hệ thống dịch máy thống kê cho phép người dùng xây dựng các mô hình dịch cho bất kỳ cặp ngôn ngữ nào với đầu vào là một tập hợp các văn bản song ngữ, được nhiều trường đại học, nhóm nghiên cứu nổi tiếng về xử lý ngôn ngữ tự nhiên và dịch máy thống kê như Edinburg (Scotland), RWTH Aachen (Germany), ... tham gia phát triển. Đây là phần mềm có chất lượng khá tốt, khả năng mở rộng cao được dùng để xây dựng nhiều hệ thống dịch thử nghiệm cho nhiều cặp ngôn ngữ như Anh-Czech, Anh-Trung, Anh-Pháp, ... Bộ công cụ Moses cho phép người dùng tạo ra một hệ thống dịch máy thống kê dựa trên cây cú pháp kết hợp với cụm từ một cách khá đơn giản. Hệ thống dịch máy thống kê này chứa một số thành phần sau: - tệp phrase-table: tệp này chứa các cụm song ngữ theo định dạng: “cụm từ ở ngôn ngữ đích | cụm từ ở ngôn ngữ nguồn | xác suất” Ví dụ: he ||| anh ấy ||| 0.3 go to ||| đi đến ||| 0.4 33 Những dòng trên có nghĩa là xác suất dịch cụm từ “he” thành cụm từ “anh ấy” là 0.3 và xác suất dịch cụm “go to” thành “đi đến” là 0.4 hay có thể hiểu đơn giản là P(đi đến | go to) = 0.4 Chú ý rằng cách lưu trữ xác suất này được dùng trong mô hình dịch dựa trên cây cú pháp, nên cách lưu trữ của nó ngược lại với xác suất như đã trình bày ở phần 3.2.3.3 (mô hình dịch máy dựa trên từ). - tệp moses.ini chứa các tham số cho bộ giải mã như: đường dẫn đến tệp phrase- table, đường dẫn đến tệp chứa mô hình ngôn ngữ, số lượng tối đa cụm từ của ngôn ngữ đích được dịch bởi một cụm từ của ngôn ngữ nguồn, .... Để xây dựng được mô hình dịch thống kê, ta có thể sử dụng script: train- model.perl với một số tham số sau: --root-dir -- cài đặt thư mục gốc nơi lưu trữ các tệp đầu ra --corpus -- tên của tệp văn bản huấn luyện (bao gồm cả 2 ngôn ngữ nguồn và đích) --e -- đuôi mở rộng của tệp văn bản huấn luyện ngôn ngữ đích --f -- đuôi mở rộng của tệp văn bản huấn luyện ngôn ngữ nguồn --lm -- language model: :: : thiết lập file cấu hình mô hình ngôn ngữ theo định dạng đã trình bày trong phần 4.3.1 --max-phrase-length -- độ dài lớn nhất của các cụm từ lưu trữ trong tệp phrase- table Ví dụ, để xây dựng một mô hình dịch máy thống kê có chứa các tệp cấu hình tại thư mục hiện tại, tệp văn bản huấn luyện tên là “corpus”, đuôi mở rộng của tệp ngôn ngữ nguồn tiếng Anh là .en còn đuôi mở rộng của tệp ngôn ngữ tiếng Việt là .vn, tệp chứa các thông số của mô hình ngôn ngữ là tệp “lm.txt”, ta có thể sử dụng câu lệnh sau: train-model.perl --root-dir . --f en --e vn --corpus corpus -lm 0:3:lm.txt Sau khi sử dựng script trên để xây dựng mô hình dịch, ta sẽ có được các tệp cấu hình đã trình bày ở trên. Khi đó, để dịch một câu từ ngôn ngữ nguồn sang ngôn ngữ đích, ta có thể sử dụng câu lệnh như sau: echo ‘câu tiếng anh cần dịch” | moses -f moses.ini Ví dụ dưới đây minh họa câu lệnh dùng để dịch câu “may i use your pen ?” từ tiếng Anh sang tiếng Việt. 34 echo 'may i use your pen ?' | moses -f moses.ini Câu lệnh trên sẽ cho ra output trên màn hình là: “tôi có thể sử dụng bút của bạn không ?”. Để hiển thị rõ việc dịch các cụm từ, ta có thể thêm tham số -t vào câu lệnh trên, cụ thể: echo “may i use your pen ?' | moses -f moses.ini -t Sau khi thực hiện câu lệnh trên, màn hình sẽ hiển thị đầu ra của quá trình dịch là: “tôi |1-1| có thể |0-0| sử dụng |2-2| bút |4-4| của bạn |3-3| không ? |5-5|” Kết quả trên có thể hiểu là: cụm từ “i” ở vị trí 1 trong câu được dịch thành cụm từ “tôi”, cụm từ “may” ở vị trí 0 (vị trí đầu tiên) được dịch thành cụm từ “có thể”, .... Rõ ràng, qua ví dụ này ta thấy có cả sự sắp xếp lại thứ tự các cụm từ trong câu. Muốn thực hiện việc dịch cho tệp văn bản, ta có thể thêm tham số -input-file tên_file_đầu_vào để thực hiện việc dịch tệp văn bản đó. Ngoài ra chương trình còn có rất nhiều tham số và chức năng khác, nhưng do giới hạn của luận văn nên chưa được trình bày ở đây. 4.2 Dữ liệu huấn luyện: Dữ liệu huấn luyện sử dụng trong mô hình ngôn ngữ là dữ liệu văn bản, được chúng tôi tải về từ các trang báo mạng như: dantri.com.vn, vnexpress.net, vietnamnet.vn, ... Sau khi tải từ các trang báo mạng về máy tính dưới dạng các file html, chúng tôi cho chạy qua các công cụ đã miêu tả ở phần 4.1.1, (phân đoạn từ, chuẩn hóa, ....) Kết quả thu được hơn 300 Mb dữ liệu văn bản đã chuẩn hóa dưới hai dạng: âm tiết và từ. Dữ liệu huấn luyện sử dụng trong mô hình dịch là tập văn bản chứa hơn 60.000 câu song ngữ Anh Việt, có được từ dự án KC trước đó. 4.3 Kết quả: 4.3.1 Số lượng các cụm ngram: Hệ thống của chúng tôi thống kê số lượng cụm Ngram với kích thước tập văn bản huấn luyện tăng dần trong hai trường hợp là: âm tiết và từ. 35 4.3.1.1 Số lượng các cụm Ngram với tiếng Việt dựa trên âm tiết: Số âm tiết trong văn bản huấn luyện Số lượng cụm Ngram unigram bigram trigram 687.003 4.567 155.297 86.069 1.203.440 4.953 299.039 178.001 2.177.198 5.549 318.888 264.599 3.778.983 5.796 358.262 432.089 4.071.536 5.814 631.253 375.105 9.765.347 6.360 666.968 954.041 17.420.051 6.706 850.333 1.613.000 58.854.325 7.712 1.835.726 13.162.180 Bảng 4-1: số lượng các cụm Ngram trong văn bản huấn luyện với âm tiết 0 2000000 4000000 6000000 8000000 10000000 12000000 14000000 16000000 S ố lư ợ ng c ác c ụm N -g ra m 2-gram 3-gram Hình 4-1: số lượng các cụm Ngram với âm tiết khi tăng kích thước dữ liệu 36 4.3.1.2 Số lượng các cụm Ngram với tiếng Việt dựa trên từ: Số từ trong văn bản huấn luyện Số lượng cụm Ngram unigram bigram trigram 940.032 15.627 268.019 93.194 1.687.023 19.057 406.975 167.114 2.334.297 20.452 517.773 238.531 3.303.231 20.683 535.861 588.976 7.778.893 26.920 1.116.428 790.995 13.814.890 27.798 1.554.965 1.255.119 15.286.851 31.609 1.794.882 1.613.000 24.366.642 36.279 3.780.751 17.410.504 Bảng 4-2: số lượng các cụm Ngram trong văn bản huấn luyện với từ 0 5000000 10000000 15000000 20000000 25000000 S ố lư ợ ng c ác c ụm N -g ra m 2-gram 3-gram Hình 4-2: số lượng các cụm Ngram với từ khi tăng kích thước dữ liệu 4.3.2 Tần số của tần số: Trong khi xây dưng mô hình ngôn ngữ, chúng tôi cũng đã thống kê được tần số của tần số các cụm Ngram với kích thước tập văn bản huấn luyện rất lớn (hơn 54 triệu 37 với âm tiết và hơn 25 triệu với từ. Việc thống kê như vậy sẽ giúp chúng tôi chọn được các tham số phù hợp cho các phương pháp làm mịn, và xây dựng cấu trúc dữ liệu phù hợp hơn 4.3.2.1 Với âm tiết: Số lượng cụm ngram có tần số unigram bigram trigram 1 514 742.986 8.428.814 2 225 263.052 1.834.374 3 128 141.940 773.793 4 119 92.484 428.780 5 80 65.979 272.156 6 84 50.620 188.533 7 45 40.048 138.643 8 50 32.422 107.227 9 57 26.961 84.581 10 53 22.759 68.083 >10 6.355 351.791 619.766 Bảng 4-3: tần số của tần số các cụm Ngram áp dụng cho âm tiết 0 2000000 4000000 6000000 8000000 10000000 1 2 3 4 5 6 7 8 9 Tần số S ố lư ợ n g c ác c ụ m N -g ra m 2-gram 3-gram Hình 4-3: số lượng các cụm Ngram (âm tiết) có tần số từ 1 đến 10 38 4.3.2.2 Với từ: Số lượng cụm ngram có tần số unigram bigram trigram 1 2526 2.014.193 12603741 2 1669 558.703 2.077.917 3 1.363 267.004 769.502 4 1.052 161.639 394.105 5 895 108.849 238.249 6 792 79.277 157.384 7 689 60.829 113.525 8 638 48.450 84.245 9 520 39.188 64.686 10 509 32.688 51.210 >10 25.624 393.618 394.167 Bảng 4-4: tần số của tần số các cụm Ngram với từ 0 5000000 10000000 15000000 20000000 1 2 3 4 5 6 7 8 9 Tần số S ố lư ợ ng c ác c ụm N -g ra m 2-gram 3-gram Hình 4-4: số lượng các cụm Ngram (từ) có tần số từ 1 đến 10 39 4.3.2.3 Nhận xét: Như vậy, qua cả 2 trường hợp, có thể nhận thấy số lượng các cụm Ngram có tần số bằng 1 và 2 chiếm tỉ lệ rất lớn trong tổng số các cụm Ngram (trên 50%). Như vậy, nếu sử dụng các phương pháp loại bỏ như đã trình bày ở phần 2.6 thì sẽ tiết kiệm được khá nhiều bộ nhớ, đồng thời sẽ làm tăng tốc độ mà không làm giảm độ chính xác của mô hình ngôn ngữ. 4.3.3 Cut-off (loại bỏ): Dựa vào kết quả thống kê tần số của tần số các cụm Ngram như đã trình bày ở phần 5.2, chúng tôi áp dụng phương pháp loại bỏ (cut-off) cho tập văn bản huấn luyện có kích thước lớn nhất với các tham số khác nhau. Dưới đây là bảng thể hiện kích thước bộ nhớ sử dụng và độ hỗn loạn thông tin (perplexity) của mô hình ngôn ngữ khi áp dụng phương pháp cut-off với các tham số khác nhau. 4.3.3.1 Với âm tiết: Loại bỏ unigram có tần số không lớn hơn: Loại bỏ bigram có tần số không lớn hơn: Loại bỏ trigram có tần số không lớn hơn: Bộ nhớ sử dụng (MB) Độ hỗn loạn thông tin (perplexity) 0 0 0 149 31,89 2 2 2 58 44,80 5 5 2 56 45,60 10 5 3 36 51,36 1 3 5 24 56,04 5 5 5 16 57,22 Bảng 4-5: bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết 4.3.3.2 Với từ: 40 Loại bỏ unigram có tần số không lớn hơn: Loại bỏ bigram có tần số không lớn hơn: Loại bỏ trigram có tần số không lớn hơn: Bộ nhớ sử dụng (MB) Độ hỗn loạn thông tin (perplexity) 0 0 0 234 37,77 2 2 2 68 81,12 5 5 2 63 87,38 10 5 3 36 106,23 1 3 5 24 113,94 5 5 5 21 121,79 5 3 10 16 127,17 Bảng 4-6: bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ 4.3.4 Các phương pháp làm mịn: Chúng tôi đã áp dụng các phương pháp làm mịn khác nhau với tập văn bản huấn luyện có kích thước lớn nhất, sau đó sử dụng mô hình ngôn ngữ xây dựng được để tính độ hỗn loạn thông tin của tập văn bản huấn luyện. Dưới đây là bảng thể hiện độ hỗn loạn thông tin của tập văn bản huấn luyện khi áp dụng mô hình ngôn ngữ với các phương pháp làm mịn khác nhau: Addone, Witten-Bell, Good-Turing, Nội suy Kneser- Ney, Truy hồi Kneser-Ney, Nội suy Kneser-Ney và Truy hồi Kneser-Ney cải tiến bởi Chen-GoodMan. 4.3.4.1 Với âm tiết: Add-1 WB GT Nội suy KN Truy hồi KN Nội suy KN cải tiến Truy hồi KN cải tiến 1-gram 656.09 656.09 656.09 656.09 607.09 656.09 656.09 2-gram 112.60 100.21 98.73 98.43 99.49 99.26 101.43 3-gram 173.44 44.90 43.73 30.56 32.75 31.90 35.20 Bảng 4-7: độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết 41 4.3.4.2 Với từ: Add-1 WB GT Nội suy KN Truy hồi KN Nội suy KN cải tiến Truy hồi KN cải tiến 1-gram 906.07 906.09 906.07 906.07 906.07 906.09 906.09 2-gram 201.02 149.21 146.7 188.01 192.11 192.28 199.17 3-gram 449.77 32.62 37.77 34.9 38.79 36.80 42.16 Bảng 4-8: độ hỗn loạn thông tin của các phương pháp làm mịn cho từ 4.3.5 Áp dụng vào mô hình dịch máy thống kê: Sau khi xây dựng được mô hình Ngram với các phương pháp làm mịn khác nhau, chúng tôi sử dụng các mô hình Ngram đó vào mô hình dịch máy thống kê dịch từ tiếng Anh sang tiếng Việt. Bằng cách sử dụng các mô hình dịch máy thống kê đó dịch một đoạn văn bản tiếng Anh sang tiếng Việt sau đó tính điểm BLEU cho bản dịch, chúng tôi biết được phương pháp làm mịn nào là tốt nhất khi áp dụng trong mô hình dịch máy thống kê. Dữ liệu dùng để huấn luyện cho mô hình Ngram gồm 2 tập: một tập có kích thước nhỏ (khoảng 50Mb) để xây dựng mô hình ngôn ngữ tới 4-gram và một tập có kích thước lớn (300Mb) để xây dựng mô hình ngôn ngữ tới 3-gram. Dữ liệu dùng để huấn luyện cho mô hình dịch là một tập văn bản chứa hơn 60.000 câu song ngữ Anh Việt. Dưới đây là bảng điểm BLEU của bản dịch khi sử dụng các mô hình Ngram áp dụng các phương pháp làm mịn khác nhau: Add-1 WB GT Nội suy KN Truy hồi KN Nội suy KN cải tiến Truy hồi KN cải tiến 1-gram 0.0767 0.0767 0.0767 0.0767 0.0767 0.0767 0.0767 2-gram 0.0864 0.0909 0.0905 0.0904 0.0903 0.0902 0.0901 3-gram 0.0903 0.0937 0.0947 0.0974 0.0970 0.0977 0.0972 4-gram 0.2231 0.2423 0.2420 0.2412 0.2306 0.2420 0.2401 Bảng 4-9: điểm BLEU của bản dịch máy với mô hình ngôn ngữ sử dụng dữ liệu huấn luyện có kích thước nhỏ (50Mb) 42 Add-1 WB GT Nội suy KN Truy hồi KN Nội suy KN cải tiến Truy hồi KN cải tiến 1-gram 0.0819 0.819 0.0819 0.0819 0.0819 0.0819 0.0819 2-gram 0.0963 0.0979 0.0997 0.0996 0.0994 0.0992 0.0990 3-gram 0.1015 0.1213 0.1387 0.1285 0.1256 0.1267 0.1265 Bảng 4-10: điểm BLEU của bản dịch máy với mô hình Ngram sử dụng dữ liệu huấn luyện có kích thước lớn (300Mb) Như vậy có thể thấy, phương pháp làm mịn GoodTuring là tốt nhất khi áp dụng cho mô hình ngôn ngữ sử dụng trong dịch máy thống kê. Ngoài ra cũng có thể thấy, việc tăng kích thước dữ liệu huấn luyện cũng sẽ làm tăng độ chính xác của mô hình ngôn ngữ Ngram. Nếu như tập huấn luyện có kích thước lớn, thì chúng ta chỉ cần xây dựng mô hình Ngram tới 3-gram là đủ để sử dụng trong dịch máy thống kê. 43 Chương 5 Kết luận Luận văn hướng tới mục tiêu xây dựng mô hình ngôn ngữ Ngram cho tiếng Việt, tuy đã xem xét được tất cả các mục tiêu như trong phần giới thiệu nhưng do thời gian có hạn, nên một số vấn đề vẫn chưa hoàn chỉnh. Tuy nhiên, luận văn cũng đạt được một số kết quả: .  Cài đặt được một số công cụ giúp đỡ cho việc xây dựng mô hình ngôn ngữ như: chuẩn hóa văn bản, tách từ bằng ngôn ngữ C#.  Cài đặt được một số phương pháp làm mịn, loại bỏ cơ bản cho mô hình ngôn ngữ bằng ngôn ngữ C#.  Tìm kiếm và chuẩn hóa được hơn 300Mb dữ liệu văn bản lấy từ các trang báo online.  Cài đặt và chạy thành công bộ mã nguồn mở Moses trên Linux và Srilm trên cả hai môi trường Linux và Window.  Sử dụng bộ công cụ mã nguồn mở SRILM để xây dựng mô hình ngôn ngữ cho tiếng Việt.  Sử dụng công cụ Moses để xây dựng mô hình dịch máy thống kê, áp dụng mô hình ngôn ngữ với các phương pháp làm mịn khác nhau. Do thời gian có hạn, nên hiện tại luận văn mới chỉ nghiên cứu được độ tin cậy của các phương pháp làm mịn trong mô hình ngôn ngữ khi áp dụng cho tiếng Việt và mô hình dịch máy thống kê từ tiếng Anh sang tiếng Việt. Trong tương lai, chúng tôi sẽ tập trung vào các ứng dụng khác của mô hình ngôn ngữ như: kiểm lỗi chính tả, tách từ 44 Tài liệu tham khảo [1] Chris Manning and Hinrich Schutze, Foundations of Statistical Natural Language Processing, MIT Press. Cambridge, May 1999. [2] Daniel Jurafsky and James H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition, chapter 6, February 2000. [3] Stanley F. Chen and Joshua Goodman, An Empirical Study of Smoothing Techniques for Language Modelin, computer science group, August 1998. [4] R. Kneser and H. Ney, Improved backing-off for M-gram language modeling, Acoustics, Speech, and Signal Processing, 1995. ICASSP-95., 1995 International Conference on [5] Andreas stolcke, Entropy-based pruning of backoff language models, in proceedings of the ARPA Workshop on human language technology, 1998 [6] Andreas stolcke, SRILM – an extensible language modeling toolkit, Conference on spoken language processing, 2002 [7] Adam Lopez , Statistical Machine Translation, University of Edinburgh, 2004 [8] Kenji Yamada and Kevin Knight, A Syntax-based Statistical Translation Model, Information Sciences Institute, University of Southern California [9] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu, Bleu: a Method for Automatic Evaluation of Machine Translation, IBM T. J. Watson Research Center, Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL), Philadelphia, July 2002 [10] Tô Hồng Thắng, Building language model for vietnamese and its application, graduation thesis, 2008