Luận văn Xây dựng mô hình ngôn ngữ cho Tiếng Việt

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG…………….. LUẬN VĂN Xây dựng mô hình ngôn ngữ cho Tiếng Việt 1 Sinh viên: Lƣu Văn Sơn - CT1102 LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy, các cô khoa Công nghệ Thông tin Trường Đại học Dân lập Hải Phòng đã tận tình dạy d kiến thức quý báu trong suốt bốn năm học vừa qua. Em xin tỏ lòng biết ơn sâu sắc đến Ths Nguyễn Thị Xuân Hương, người đã tận tình giúp đỡ và truyền đạt nhiều kinh nghiệm để đề tài có thể được thực hiện và hoàn thành. Cuối cùng em xin gửi lời cảm ơn chân thành tới tất cả người thân và bạn bè đã giúp đỡ, động viên em rất nhiều trong quá trình học tập cũng như thực hiện đề tài. Em xin trân thành cảm ơn! Hải Phòng, tháng 07 năm 2011. Sinh viên Lưu Văn Sơn 2 Sinh viên: Lƣu Văn Sơn - CT1102 MỤC LỤC DANH MỤC CHỮ VIẾT TẮT ........................................................................................... 4 ....................................................................................................... 4 DANH MỤC BẢNG ............................................................................................................. 4 M ............................................................................................................................... 5 CHƢƠNG 1: TỔNG QUAN VỀ MÔ HÌNH NGÔN NGỮ .......................................... 6 1.1 N-gram .................................................................................................. 6 1.2 Xây dựng mô hình ngôn ngữ ................................................................ 7 1.2.1 Ước lượng cực đại hóa khả năng (MLE) ...................................... 7 1.2.2 Các phương pháp làm mịn ............................................................ 8 1.3 Kỹ thuật làm giảm kích thước dữ liệu ................................................ 16 1.3.1 Loại bỏ (pruning): ....................................................................... 17 1.3.2 Đồng hóa (Quantization) ............................................................. 19 1.3.3 Nén (Compression) ..................................................................... 19 1.4 Đánh giá mô hình ngôn ngữ ................................................................ 19 1.4.1 Entropy – Độ đo thông tin........................................................... 19 1.4.2 Perplexity – Độ hỗn loạn thông tin ............................................. 21 1.4.3 MSE - Lỗi trung bình bình phương............................................. 22 CHƢƠNG 2: NG DỤNG CỦA MÔ HÌNH NGÔN NGỮ TRONG DỊCH MÁY THỐNG KÊ…… ................................................................................................................ 23 2.1 Dịch máy ............................................................................................. 23 2.2 Dịch máy thống kê .............................................................................. 24 2.2.1 Giới thiệu ..................................................................................... 24 2.2.2 Nguyên lý và các thành phần ...................................................... 26 2.2.3 Mô hình dịch ............................................................................... 27 2.2.4 Bộ giải mã ................................................................................... 32 2.3 Các phương pháp đánh giá bản dịch ................................................... 33 2.3.1 Đánh giá trực tiếp bằng con người .............................................. 33 2.3.2 Đánh giá tự động: phương pháp BLEU ...................................... 33 CHƢƠNG 3: THỰC NGHIỆM ................................................................................... 35 3.1 Cài đặt hệ thống .................................................................................. 35 3 Sinh viên: Lƣu Văn Sơn - CT1102 3.1.1 Cấu hình và hệ điều hành. ........................................................... 35 3.1.2 Các công cụ sử dụng. .................................................................. 35 3.1.3 Các bước huấn luyện dich và kiểm tra. ....................................... 36 3.1.4 Chuẩn hóa dữ liệu. ...................................................................... 36 3.1.5 Xây dựng mô hình ngôn ngữ. ..................................................... 36 3.1.6 Xây dựng mô hình dịch. .............................................................. 36 3.1.7 Hiệu chỉnh trọng số. .................................................................... 37 3.1.8 Dịch máy. .................................................................................... 37 3.1.9 Đánh giá kết quả dịch .................................................................. 37 3.2 Bộ công cụ xây dựng mô hình ngôn ngữ - SRILM: ........................... 38 3.2.1 Ngram-count: .............................................................................. 38 3.2.2 Ngram: ......................................................................................... 40 3.3 Bộ công cụ xây dựng mô hình dịch máy thống kê – MOSES: ........... 41 3.4 Kết quả thực nghiệm khi đánh giá N-gram trong ứng dụng SMT...... 43 KẾT LUẬN ......................................................................................................................... 45 TÀI LIỆU THAM KHẢO ................................................................................................. 46 4 Sinh viên: Lƣu Văn Sơn - CT1102 DANH MỤC CHỮ VIẾT TẮT LM: Mô hình ngôn ngữ MKN: Phương pháp làm mịn Kneser-Ney cải tiến MLE: Ước lượng cực đại hóa khả năng MSE: Lỗi trung bình bình phương MT: Dịch máy SMT: Dịch máy bằng phương pháp thống kê DANH MỤC HÌNH Hình 1.1: Mô hình Markov bậc 2 .................................................................. 7 ......................................... 23 Hình 2.2 : Tăng kích cỡ LM cải thiện điểm BLEU .................................... 25 Hình 2.3 : Kiến trúc của một hệ thống SMT ............................................... 26 Hình 2.4 : Mô hình dịch máy thống kê từ tiếng Anh sang tiếng Việt ......... 27 Hình 2.5: Sự tương ứng một - một giữa câu tiếng Anh và câu tiếng Pháp . 28 Hình 2.6: 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 ................................... 28 Hình 2.7 : Sự tương ứng một - nhiều giữa câu tiếng Anh với câu tiếng Pháp ... 29 Hình 2.8 : Sự tương ứng nhiều - nhiều giữa câu tiếng Anh với câu tiếng Pháp... .......................................................................................................... 29 Hình 2.9: Minh họa dịch máy thống kê dựa vào cụm từ ............................ 30 Hình 2.10: Mô hình dịch dựa trên cây cú pháp ........................................... 32 Hình 2.11: Sự trùng khớp của các bản dịch máy với bản dịch mẫu ........... 34 DANH MỤC BẢNG Bảng 3.1:Thống kê các cụm N-gram với các phương pháp làm mịn ......... 43 Bảng 3.2: Kết quả theo độ đo BLEU khi đánh giá SMT với các mô hình N- gram khác nhau ........................................................................................... 43 5 Sinh viên: Lƣu Văn Sơn - CT1102 Mô hình ngôn ngữ là một thành phần quan trọng trong các ứng dụng như nhận dạng tiếng nói, phân đoạn từ, dịch thống kê, … Và chúng thường được mô hình hóa sử dụng các n-gram. 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. 3 chương: Chương 1: : trình bày khái quát lý thuyết về mô hình ngôn ngữ, các khó khăn còn tồn tại 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, Chương 2: kê, , bộ công cụ mã nguồn mở SRILIM để xây dựng mô hình ngôn ngữ cho tiếng Việt và MOSES để dịch máy thống kê, . 6 Sinh viên: Lƣu Văn Sơn - CT1102 CHƢƠNG 1: TỔNG QUAN VỀ MÔ HÌNH NGÔN NGỮ Mô hình ngôn ngữ (Language Model - LM) là các phân phối xác suất trên một ngữ liệu đơn ngữ, được sử dụng trong nhiều bài toán khác nhau của xử lý ngôn ngữ tự nhiên, ví dụ như: dịch máy bằng phương pháp thống kê, nhận dạng giọng nói, nhận dạng chữ viết tay, sửa lỗi chính tả, …. Thực chất, LM là một hàm chức năng có đầu vào là một chuỗi các từ và đầu ra là điểm đánh giá xác suất một người bản ngữ có thể nói chuỗi đó. Chính vì vậy, một mô hình ngôn ngữ tốt sẽ đánh giá các câu đúng ngữ pháp, trôi chảy cao hơn một chuỗi các từ có thứ tự ngẫu nhiên, như trong ví dụ sau: P(“hôm nay trời nắng”) > P(“trời nắng nay hôm”) 1.1 N-gram Cách thông dụng nhất được dùng để mô hình hóa ngôn ngữ vào trong LM là thông qua các n-gram. Với mô hình n-gram, chúng ta coi một văn bản, đoạn văn bản là chuỗi các từ liền kề nhau, w1, w2, …, wn-1, wn, và sau đó phân tích xác suất của chuỗi với công thức xác suất kết hợp: 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) và do vậy mỗi từ sẽ liên quan có điều kiện tới toàn bộ các từ trước nó (ta sẽ gọi đây là lịch sử của sự kiện hoặc từ đó). Tuy nhiên, việc sử dụng toàn bộ các từ trước đó để đoán nhận từ tiếp theo là không thể thực hiện được vì hai nguyên nhân sau. Đầu tiên là phương pháp này không khả thi về mặt tính toán do tốn quá nhiều thời gian, tài nguyên hệ thống cho mỗi lần dự đoán. Hai là, trong rất nhiều trường hợp, chỉ sau khi duyệt vài từ trong lịch sử, ta đã nhận thấy rằng đó là một câu chưa từng gặp trước đây. Bởi vậy kể cả khi đã biết toàn bộ lịch sử của một từ, xác suất của nó vẫn có thể là không biết. Thay vào đó, các mô hình ngôn ngữ thường ước lượng tương đối xác suất dựa trên giả định Markov (hay mô hình Markov ẩn), rằng từ tiếp theo chỉ chịu ảnh hưởng từ một vài từ trước đó. Một mô hình Markov bậc n giả định rằng chỉ n từ trước đó có liên hệ ngữ cảnh với từ đang cần xác định. Việc quyết định bao nhiêu từ trước đó mà LM quan tâm được gọi là bậc n (order) của LM, và thường được gọi là 1-gram (unigram), 2-gram (bigram), 3-gram (trigram), 4-gram (fourgram) tương ứng với các mô hình Markov bậc một, hai, ba, bốn. 7 Sinh viên: Lƣu Văn Sơn - CT1102 Ví dụ, nếu chúng ta muốn ước lượng xác suất 2-gram của một từ wi với mô hình Markov bậc 2 thì chúng ta sẽ dựa trên hai từ trước đó:P(w1,w2,…,wi)=P(wi/wi- 2,wi-1) Hình 1.1: Mô hình Markov bậc 2 Một cách tổng quát, 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) 1.2 Xây dựng mô hình ngôn ngữ Để xây dựng (huấn luyện) một mô hình ngôn ngữ ta cần một ngữ liệu đơn ngữ (corpus) có kích thước tương đối và một bộ ước lượng thống kê có nhiệm vụ mô hình hóa lượng xác suất của ngữ liệu. Các bộ ước lượng được mà LM sử dụng, theo những cách khác nhau, đều cần đến tần suất của các n-gram, do đó chúng ta cần phải đếm số lần xuất hiện của các n-gram từ 1-gram cho đến số bậc mô hình chúng ta đang huấn luyện. 1.2.1 Ƣớc lƣợng cực đại hóa khả năng (MLE) Chúng ta có thể sử dụng kết quả đếm các n-gram để xây dựng một mô hình ước lượng cực đại hóa khả năng (Maximium Likelihood Estimation - MLE) với tần suất tương đối của các n-gram trong ngữ liệu. Với MLE, xác suất một unigram nhất định nào đó sẽ xuất hiện tiếp theo đơn giản là tần suất nó xuất hiện trong ngữ liệu. trong đó c(wi‟) = |wi‟| chính là số lần xuất hiện của từ wi‟ trong ngữ liệu. Phương pháp này được gọi như vậy bởi vì nó cực đại hóa giá trị đầu ra để mô hình hóa ngữ liệu huấn luyện. Ví dụ, trong ngữ liệu Brown, một ngữ liệu với một triệu wi-3 wi-2 wi-1 wi wi+1 8 Sinh viên: Lƣu Văn Sơn - CT1102 từ, từ khóa “Chinese” xuất hiện 400 lần. Vậy thì xác suất mà một mô hình ngôn ngữ dùng MLE sẽ gán cho unigram “Chinese” là Xác suất điều kiện của một n-gram tổng quát với bậc > 1 là: tức là tần suất một từ nào đó thường xuyên xuất hiện sau lịch sử có bậc n-1. Để minh họa, ta tiếp tục ví dụ trên, xác suất bigram “Chinese food” xuất hiện là số lần từ “food” xuất hiện sau từ “Chinese” chia cho c(Chinese) = 400. Trong ngữ liệu Brown, cụm từ “Chinese food” xuất hiện 120 lần, nên: PMLE(food|Chinese) = 0.3 1.2.2 Các phƣơng pháp làm mịn Tuy MLE là một phương pháp dễ hiểu, dễ sử dụng để ước lượng xác suất cho mô hình, nhưng trong thực tế ta gặp phải vấn đề dữ liệu thưa (data sparseness problem). Tức là tập ngữ liệu dùng để xây dựng LM dù lớn đến mấy, cũng chỉ là tập hữu hạn các câu trong vô số câu có thể của một ngôn ngữ tự nhiên. Do đó một LM chỉ sử dụng MLE sẽ gán xác suất bằng 0 cho nhiều n-gram tốt. Để giảm thiểu vấn đề này, người ta thường không sử dụng MLE mà thay vào đó là các phương pháp ước lượng xác suất thống kê phức tạp hơn. Các phương pháp này được gọi là làm mịn (smoothing) hay trừ hao (discounting), khi mà một phần xác suất từ các sự kiện trong mô hình sẽ được dành cho những sự kiện chưa từng xuất hiện. Việc lấy từ cái gì và trừ hao như thế nào là một đề tài vẫn đang được nghiên cứu nhiều. Ví dụ, cách cổ điển nhất của làm mịn là phương pháp Add-one smoothing, trong phương pháp này, ta thêm một lượng 1l vào kết quả đếm số lần xuất hiện của mọi từ vựng trong ngữ liệu. Hai khái niệm quan trọng được sử dụng trong quá trình làm mịn các mô hình ngôn ngữ là backoff và interpolation. Khi LM gặp một n-gram chưa biết, việc tính xác suất sẽ sử dụng thông tin từ (n-1)-gram, nếu sự kiện (n-1)-gram cũng chưa từng xuất hiện trong quá trình huấn luyện thì LM lại sử dụng thông tin xác suất từ (n-2)- gram, … Và cứ tiếp tục như vậy cho đến khi tính được xác suất của n-gram. Quá trình này được gọi là backoff và được định nghĩa như sau: 9 Sinh viên: Lƣu Văn Sơn - CT1102 Trong đó là hệ số trừ hao dựa trên tần suất xuất hiện của 1 1w ii n trong lịch sử và là tham số backoff. Khi số lượng từ vựng đủ lớn, chúng ta có thể sẽ cần gán xác suất bằng 0 cho một số từ ngoài từ điển (out of vocabulary - OOV) khi ở mức unigram. Chẳng hạn khi ta có một cuốn từ điển chuyên ngành và không muốn chia sẻ lượng xác suất của các từ vựng đó (các danh từ chung, các số thực đặc biệt, …) cho các OOV. Một cách khác là chúng ta làm mịn LM và dành một lượng xác suất nhỏ gán cho các từ ngoài từ điển khi ở mức unigram. Phương pháp Interpolation kết hợp thông tin thống kê n-gram qua tất cả các bậc của LM. Nếu bậc của LM là n thì công thức đệ quy interpolation như sau: P(w i|w i-n+1...w i-1) = P(w i|w i-n+1...w i-1) + (1- )P(w i|w i-n+2...w i-1) Trong đó là trọng số quyết định bậc nào của LM có ảnh hưởng lớn nhất đến giá trị đầu ra. Tổng trọng số được sử dụng cho tất cả các bậc n-gram bằng một. Có nhiều cách để xác định giá trị cho các trọng số này, đối với phương pháp interpolation đơn giản thì các giá trị này giảm theo số bậc n-gram. Tuy nhiên thường thì chúng sẽ được tính toán tùy theo điều kiện ngữ cảnh cụ thể, tức là theo tần suất của các bậc n-gram trong lịch sử. Các trọng số này không được tính toán từ dữ liệu huấn luyện, mà sử dụng tập dữ liệu held-out riêng biệt – tập này chỉ được dùng để huấn luyện các tham số, mà trong trường hợp này là các giá trị . Cần phải nhận thấy rằng sự khác biệt cơ bản giữa hai phương pháp này là interpolation sử dụng thông tin từ các bậc thấp hơn ngay cả khi dữ liệu xác suất của n-gram cần tính đã khác 0; trong khi backoff thì lại chỉ tìm kiếm đến dữ liệu khác 0 gần nhất. Những tiểu mục tiếp theo trong phần này sẽ trình bày về một số phương pháp làm mịn phổ biến nhất hiện nay. 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. 10 Sinh viên: Lƣu Văn Sơn - CT1102 1.2.2.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. 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: Thuật toán Add-one Phương pháp 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). 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 Trong đó V là kích thước bộ từ vựng 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 Trong đó đượ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 (MLE) = 1: phương pháp add-one = 1 2 : được gọi là phương pháp Jeffreys – Perks Và M là cụm N-gram có thể có bằng VN Thuật toá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 để 11 Sinh viên: Lƣu Văn Sơn - CT1102 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: T T+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* = T Z(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: 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) Thuật toá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: 12 Sinh viên: Lƣu Văn Sơn - CT1102 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ớ