Tài liệu Luận văn sử dụng mô hình ngôn ngữ bloom filter trong cải tiến dịch máy thống kê

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TT SỬ DỤNG MÔ HÌNH NGÔN NGỮ BLOOM FILTER TRONG CẢI TIẾN DỊCH MÁY THỐNG KÊ TRẦN TIẾN THÀNH THÁI NGUYÊN 2015 3 LỜI CAM ĐOAN Em - Trần Tiến Thành, học viên lớp Cao học K12E Trường Đại học Công nghệ thông tin và Truyền thông Thái Nguyên - cam kết Luận văn thạc sỹ khoa học máy tính: “Sử dụng mô hình ngôn ngữ Bloom Filter trong cải tiến dịch máy thống kê” là công trình nghiên cứu của bản thân em dưới sự hướng dẫn của thầy giáo TS. Nguyễn Văn Vinh, Bộ môn Khoa học máy tính, Khoa Công nghệ thông tin – Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. Các kết quả trong luận văn tốt nghiệp là trung thực, không sao chép toàn văn của bất kỳ công trình nào khác. Thái Nguyên, ngày 05 tháng 10 năm 2015 TÁC GIẢ Trần Tiến Thành 4 LỜI CẢM ƠN Em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo, TS. Nguyễn Văn Vinh, Bộ môn Khoa học máy tinh, Khoa Công nghệ thông tin - Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã khuyến khích và tận tình hướng dẫn em trong suốt quá trình thực hiện luận văn. Em cũng xin cảm ơn anh Trần Hồng Việt, nghiên cứu sinh Trường Đại học Công nghệ, giảng viên Trường Đại học Kinh tế kĩ thuật công nghiệp đã hết lòng giúp đỡ em trong quá trình thực hiện đề tài. Nhờ sự quan tâm chỉ bảo và những ý kiến đóng góp quý báu của thầy và của anh em mới có thể hoàn thành luận văn này. Em xin chân thành cảm ơn tập thể các thầy, cô giáo Trường Đại học Công nghệ thông tin và Truyền thông Thái Nguyên đã tận tình giảng dạy truyền đạt cho em những kiến thức, kinh nghiệm quý báu trong suốt những năm học vừa qua. Em cũng xin cảm ơn Sở Giáo dục và Đào tạo Phú Thọ, Trường THPT Minh Đài đã tạo điều kiện về kinh phí và thời gian để em có thể học tập và hoàn thành luận văn. Cuối cùng em xin chân thành cảm ơn gia đình, người thân đã hết lòng giúp đỡ, hỗ trợ về vật chất lẫn tinh thần giúp em yên tâm học tập và nghiên cứu trong suốt quá trình học tập và thực hiện luận văn. Trong khoảng thời gian có hạn, cũng như kiến thức còn nhiều hạn chế luận văn không tránh khỏi những sai sót về nội dung cũng như hình thức. Kính mong nhận được sự góp ý của quý thầy cô, bạn bè và đồng nghiệp. Thái Nguyên, ngày 05 tháng 10 năm 2015 TÁC GIẢ Trần Tiến Thành 5 DANH SÁCH CÁC TỪ VIẾT TẮT Đầy đủ Viết tắt BF Bloom Filter BF-LM Mô hình ngôn ngữ dựa trên Bloom Filter LF-BF-LM Mô hình ngôn ngữ Log-Frequency Bloom Filter 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 NLP Xử lý ngôn ngữ tự nhiên PDS Cấu trúc dữ liệu xác suất RDS Cấu trúc dữ liệu ngẫu nhiên SMT Dịch máy bằng phương pháp thống kê 6 DANH MỤC CÁC HÌNH VẼ Hình Tên hình Trang Hình 1 Kiến trúc của một hệ thống SMT 14 Hình 2 Minh họa dịch máy thống kê dựa vào cụm Ví dụ về hàm băm. Các xâu ký tự được chuyển thành chữ Hình 3 ký đại diện. 15 35 Cặp khóa ki và giá trị ai của tập S được ánh xạ thông qua Hình 4 hàm băm vào bảng băm. Xuất hiện xung đột giữa 2 phần tử k1 và k3. 36 Hình 5 Huấn luyện Bloom Filter 37 Hình 6 Truy vấn Bloom Filter 38 Hình 7 Lỗi một phía trong Bloom Filter 39 7 MỤC LỤC MỞ ĐẦU .......................................................................................................... 9 1. Đặt vấn đề .................................................................................................... 9 2. Đối tượng và phạm vi nghiên cứu............................................................ 10 3. Nhiệm vụ nghiên cứu ................................................................................ 10 4. Những nội dung nghiên cứu chính .......................................................... 10 NỘI DUNG ..................................................................................................... 11 CHƯƠNG I .................................................................................................... 11 TỔNG QUAN VỀ DỊCH MÁY THỐNG KÊ DỰA VÀO CỤM TỪ ............. 11 VÀ MÔ HÌNH NGÔN NGỮ........................................................................... 11 1.1 Dịch máy thống kê dựa trên cụm từ ...................................................... 11 1.1.1 Dịch máy và dịch máy thống kê ............................................................. 11 1.1.2 Dịch máy thống kê dựa trên cụm ......................................................... 15 1.2.1 N-gram ................................................................................................... 17 1.2.2 Mô hình ngôn ngữ ................................................................................ 19 1.2.3 Huấn luyện mô hình ngôn ngữ ............................................................ 21 1.2.3.1 Ước lượng cực đại hóa khả năng (Maximium Likelihood Estimation MLE)................................................................................................................ 21 1.2.3.2 Các phương pháp làm mịn .................................................................. 22 1.2.3.2.1 Kneser-Ney ...................................................................... 24 1.2.3.2.2 Kneser-Ney cải tiến (Modified Kneser-Ney - MKN) ...... 25 1.2.3.2.3 Stupid Backoff ................................................................. 26 1.3 Đánh giá mô hình ngôn ngữ ................................................................... 27 1.3.1 Entropy – Độ đo thông tin .................................................................... 27 1.3.2 Độ hỗn loạn thông tin (Perplexity)...................................................... 29 1.3.3 Tỉ lệ lỗi (Error rate) ............................................................................... 30 1.4 Đánh giá chất lượng dịch tự động dựa trên điểm BLEU .................... 31 CHƯƠNG 2 .................................................................................................... 32 8 MÔ HÌNH NGÔN NGỮ BLOOM FILTER.................................................... 32 2.1 Các cấu trúc dữ liệu xác suất (PDS) ...................................................... 33 2.2 Hàm băm (Hash function) ...................................................................... 35 2.3 Bloom Filter cơ bản................................................................................. 37 2.4 Mô hình ngôn ngữ Bloom Filter ............................................................ 43 2.4.1 Bloom Filter tần số log (Log-frequency Bloom Filter).......................... 43 2.4.2 Bộ lọc dựa vào chuỗi con (sub-sequence filtering) ............................... 45 CHƯƠNG 3 .................................................................................................... 47 ỨNG DỤNG BLOOM FILTER CHO HỆ DỊCH MÁY THỐNG KÊ DỰA VÀO CỤM TỪ ................................................................................................ 47 3.1 Hệ dịch máy thống kê mã nguồn mở Moses ......................................... 47 3.2 Tích hợp Mô hình ngôn ngữ Bloom Filter vào hệ thống Moses ......... 48 3.2.1 Xây dựng LM với RandLM và SRILM ................................................ 48 3.2.1.1 Ngữ liệu ............................................................................... 49 3.2.1.2 Thuật toán làm mịn ............................................................. 53 3.2.1.3. Xây dựng LM với SRILM và RandLM .............................. 53 3.3 Thử nghiệm và đánh giá ......................................................................... 65 KẾT LUẬN .................................................................................................... 78 TÀI LIỆU THAM KHẢO ............................................................................ 79 9 MỞ ĐẦU 1. Đặt vấn đề Mô hình ngôn ngữ (Language Model - LM) là một phần không thể thiếu trong lĩnh vực xử lý ngôn ngữ tự nhiên. Mô hình ngôn ngữ được sử dụng ở các lĩnh vực trong xử lý ngôn ngữ tự nhiên như: nhận dạng tiếng nói, kiểm lỗi chính tả, phân đoạn từ hay dịch máy thống kê… Để ứng dụng tốt mô hình ngôn ngữ phải lớn, cũng chính vì vậy mà việc tìm kiếm không gian lưu trữ là vô cùng quan trọng trong mô hình ngôn ngữ. Chính vì thế, luận văn này tôi lựa chọn và thực hiện đề tài: “Sử dụng mô hình ngôn ngữ Bloom Filter trong cải tiến dịch máy thống kê”. Trong luận văn này, chúng tôi nghiên cứu và tìm hiểu mô hình ngôn ngữ xây dựng dựa trên cấu trúc dữ liệu Bloom Filter. Không lưu trữ toàn bộ tập n-gram giống như các mô hình truyền thống, loại mô hình ngôn ngữ này sử dụng một quy trình mã hóa đặc biệt, cho phép chia sẻ một cách hiệu quả các bit khi lưu trữ thông tin thống kê n-gram, nhờ đó tiết kiệm đáng kể bộ nhớ. Sau khi tìm hiểu sơ lược về mô hình ngôn ngữ, chúng ta sẽ nghiên cứu kiểu cấu trúc dữ liệu dựa trên Bloom Filter là Bloom Map. Qua các thử nghiệm, chúng tôi chỉ ra sự ưu việt của các mô hình ngôn ngữ dựa trên Bloom Filter trên cả phương diện dung lượng và tính hiệu quả khi ứng dụng trong thực tế, cụ thể ở đây là hệ thống dịch máy bằng phương pháp thống kê với Moses [2]. 10 2. Đối tượng và phạm vi nghiên cứu - Luận văn này chúng tôi nghiên cứu về n-gram và cách ước lượng, tính toán biễu diễn mô hình ngôn ngữ. - Thực hiện thử nghiệm với dữ liệu tiếng Việt. 3. Nhiệm vụ nghiên cứu - Thông qua luận văn, trình bày các hiểu biết cơ bản cần biết về mô hình ngôn ngữ như n-gram, các thuật toán làm mịn được sử dụng trong mô hình ngôn ngữ và các thước đo để đánh giá một mô hình ngôn ngữ. - Luận văn tập trung nghiên cứu về các trúc dữ liệu dựa trên Bloom Filter được sử dụng cho mô hình ngôn ngữ cụ thể là Log-Frequency Bloom Filter. - Thực hiện thử nghiệm xây dựng mô hình ngôn ngữ trên một ngữ liệu tiếng Việt và một ngữ liệu tiếng Anh.. - Ngoài ra, luận văn còn giới thiệu sơ lược về dịch máy thống kê, thử nghiệm dịch máy thống kê với hệ thống dịch máy mã nguồn mở Moses sử dụng các mô hình ngôn ngữ xây dựng ở chương 3. 4. Những nội dung nghiên cứu chính Luận văn được trình bày thành 3 phần: MỞ ĐẦU NỘI DUNG Chương 1 - Tổng quan về dịch máy thống kê dựa vào cụm từ và mô hình ngôn ngữ Chương 2 - Mô hình ngôn ngữ Bloom Filter Chương 3 - Ứng dụng Bloom Filter cho hệ dịch máy thống kê dựa vào cụm từ KẾT LUẬN 11 NỘI DUNG CHƯƠNG I TỔNG QUAN VỀ DỊCH MÁY THỐNG KÊ DỰA VÀO CỤM TỪ VÀ MÔ HÌNH NGÔN NGỮ 1.1 Dịch máy thống kê dựa trên cụm từ 1.1.1 Dịch máy và dịch máy thống kê Dịch máy (Machine Translation - MT) xuất hiện từ thập kỷ 50 của thế kỷ trước và đặc biệt được phát triển mạnh mẽ từ thập kỷ 80 cho đến ngày nay. Trên thế giới, hiện tại có rất nhiều hệ dịch máy thương mại nổi tiếng như Systrans, Kant, … hay những hệ dịch máy mở tiêu biểu là hệ dịch của Google, hỗ trợ hàng chục cặp ngôn ngữ phổ biến như Anh-Pháp, Anh-Trung, Anh-Nhật, Hoa-Nhật, … Các cách tiếp cận MT chia làm bốn lớp chính là dịch trực tiếp (direct), dịch dựa trên luật chuyển đổi (transfer), dịch liên ngữ (interlingua) và dịch dựa vào thống kê (statistical MT). Trước đây, phương pháp dịch dựa trên luật chuyển đổi và dịch liên ngữ chủ yếu dựa vào cú pháp có thời gian phát triển khá dài và hiện vẫn còn được sử dụng phổ biến trong nhiều hệ dịch thương mại. Những hệ dịch máy loại này này đã đạt được kết quả khá tốt với những cặp ngôn ngữ tương đồng nhau về cú pháp như AnhPháp, Anh-Tây Ban Nha, … nhưng còn gặp nhiều hạn chế đối với các cặp ngôn ngữ có cú pháp rất khác nhau như Anh-Trung, Anh-Nhật, … Dịch Anh-Việt, Việt-Anh ở nước ta cũng vấp phải những khó khăn tương tự do sự khác biệt về mặt cấu trúc ngữ pháp và tính nhập nhằng của ngữ nghĩa. Hệ thống dịch Anh-Việt dựa trên luật chuyển đổi được thương mại hóa đầu tiên ở Việt Nam là EVTran. Nhiều nghiên cứu với yêu cầu tăng chất lượng dịch hiện nay vẫn đang được thực hiện và có thể thích nghi với đặc điểm của các cặp ngôn ngữ khác nhau. 12 Dịch máy thống kê (SMT) là một phương pháp dịch máy, trong đó các bản dịch được tạo ra trên cơ sở các mô hình thống kê có các tham số được bắt nguồn từ việc phân tích các cặp câu song ngữ. Các phương pháp tiếp cận thống kê tương phản với các phương pháp tiếp cận dựa trên luật trong dịch máy cũng như với dịch máy dựa trên ví dụ. Những ý tưởng đầu tiên của dịch máy thống kê đã được giới thiệu bởi Warren Weaver vào năm 1949 [1], bao gồm cả những ý tưởng của việc áp dụng lý thuyết thông tin của Claude Shannon. Dịch máy thống kê được tái giới thiệu vào năm 1991 bởi các nhà nghiên cứu làm việc tại Trung tâm nghiên cứu Thomas J. Watson của IBM[2] và đã góp phần đáng kể trong sự hồi sinh việc quan tâm đến dịch máy trong những năm gần đây. Ngày nay nó là phương pháp dịch máy được nghiên cứu nhiều nhất. Dịch máy bằng phương pháp thống kê (Statistical Machine Translation) đã chứng tỏ là một hướng tiếp cận đầy đầy tiềm năng bởi những ưu điểm vượt trội so với các phương pháp dịch máy dựa trên cú pháp truyền thống qua nhiều thử nghiệm về dịch máy. Thay bằng việc xây dựng các từ điển, các 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ừ dữ liệu. Vì thế, dịch máy dựa vào thống kê có tính khả chuyển cao, có khả năng áp dụng được cho cặp ngôn ngữ bất kỳ. Hệ thống SMT được đề xuất lần đầu tiên bởi Brown năm 1990 sử dụng mô hình kênh nhiễu và đã phát triển áp đảo trong ngành MT nhiều năm trở lại đây. Thêm vào đó dịch máy thống kê có những ưu điểm sau: Dịch máy (MT) là vấn đề quyết định: Cho trước những từ trong ngôn ngữ nguồn, chúng ta phải quyết định chọn những từ trong ngôn ngữ đích. Vì vậy, nó tạo cho chúng ta một cảm giác là có thể giải quyết nó bằng định lý quyết định thống kê. Điếu đó dẫn đến cách tiếp cận thống kê được đề xuất. 13 Mối quan hệ giữa đối tượng ngôn ngữ như từ, cụm từ và cấu trúc ngữ pháp thường yếu và mơ hồ. Để mô hình hóa những phụ thuộc này, chúng ta cần một công thức hóa như đưa ra phân phối xác suất mà nó có thể giải quyết với những vấn đề phụ thuộc lẫn nhau. Để thực hiện MT, chúng ta nhất thiết phải kết hợp nhiều nguồn trí thức. Trong dịch thống kê, chúng ta dựa vào toán học để thực hiện kết hợp tối ưu của các nguồn trí thức. Trong dịch máy thống kê (SMT), trí thức dịch được học một cách tự động từ dữ liệu huấn luyện. Với kết quả như vậy, việc phát triển một hệ dịch dựa vào thống kê sẽ rất nhanh so với hệ dịch dựa vào luật. SMT khá phù hợp với ứng dụng nhúng mà ở đây MT là một phần của ứng dụng lớn hơn. Ví dụ, trong dịch các bài nói chuyện, máy nhận dạng tiếng nói sẽ được thêm vào. SMT xem như rất phù hợp với cách tiếp cận này bởi vì nó tận dụng được sức mạnh của ngôn ngữ tự nhiện. Việc đưa ra khái niệm “chính xác” của mối quan hệ ngữ pháp, ngữ nghĩa, văn phong là rất khó khăn nếu không nói là không thể. Vì vậy, việc hình thức hóa vấn đề này càng chính xác càng tốt không thể dựa vào sự giằng buộc bởi các luật mô tả chúng. Thay vào đó, trong cách tiếp cận thống kê, các giả định mô hình được kiểm định bằng thực nghiệm dựa vào dữ liệu huấn luyện. SMT đã cho chất lượng dịch khá tốt. Hệ thống CANDIDE của IBM được coi là một trong những hệ dịch tốt nhất hiện nay trên thế giới. Chất lượng đạt trên 80%. Với phương pháp dịch trực tiếp, từng từ được dịch từ ngôn ngữ nguồn sang ngôn ngữ đích. Trong dịch dựa trên luật chuyển đổi, đầu tiên chúng ta cần phải phân tích cú pháp của câu vào, rồi áp dụng các luật chuyển đổi để biến đổi cấu trúc câu này ở ngôn ngữ nguồn sang cấu trúc của ngôn ngữ đích; 14 cuối cùng ta mới dịch ra câu hoàn chỉnh. Đối với dịch liên ngữ, câu vào được phân tích thành một dạng biểu diễn trừu tượng hóa về ngữ nghĩa, được gọi là “interlingua”, sau đó ta tìm cách xây dựng câu đích phù hợp nhất với “interlingua” này. Dịch máy thống kê có cách tiếp cận hoàn toàn khác, khả năng dịch có được là dựa trên các mô hình thống kê được huấn luyện từ các ngữ liệu song ngữ. Kiến trúc chung của một hệ thống SMT được thể hiện trong hình 1. Mô hình của Brown (hay còn gọi là mô hình IBM) [7] biểu diễn quá trình dịch bằng một mô hình kênh nhiễu (noisy channel model) bao gồm ba thành phần: một mô hình dịch (translation model), có nhiệm vụ liên hệ các từ, cụm từ tương ứng của các ngôn ngữ khác nhau; một mô hình ngôn ngữ (LM), đại diện cho ngôn ngữ đích; một bộ giải mã (decoder), kết hợp mô hình dịch và mô hình ngôn ngữ để thực hiện nhiệm vụ dịch. Ngôn ngữ nguồn ( f ) Tiền xử lý Bộ giải mã f *  arg max Pr(e | f ) Mô hình ngôn ngữ Pr(e) Mô hình dịch Pr(f | e) Hậu xử lý Ngôn ngữ đích ( e ) Hình 1: Kiến trúc của một hệ thống SMT 15 1.1.2 Dịch máy thống kê dựa trên cụm He Anh ấy is a good là một bác sỹ doctor giỏi Hình 2: Minh họa dịch máy thống kê dựa vào cụm Với dịch dựa trên cụm, một chuỗi các từ liên tiếp (cụm) được dịch sang ngôn ngữ đích, với độ dài cụm ngôn ngữ nguồn và đích có thể không giống nhau. Hình 2 minh họa phương pháp dịch cụm: câu vào được chia thành một số cụm; từng cụm một được dịch sang ngôn ngữ đích và sau đó các cụm được đảo trật tự theo một cách nào đó rồi ghép với nhau. Kết quả ta thu được câu dịch trong ngôn ngữ đích. Nếu gọi ngôn ngữ nguồn là f và ngôn ngữ đích là e, ta sẽ cố gắng tối đa hóa xác suất Pr( f | e) với mong muốn có được bản dịch tốt nhất. Trong thực tế tồn tại hơn một bản dịch đúng cho cùng một câu, mục đích của ta là tìm ra câu ngôn ngữ e phù hợp nhất khi cho trước câu ngôn ngữ nguồn f. Dịch dựa vào cụm áp dụng mô hình kênh nhiễu, sử dụng công thức Bayes ta có: arg max ePr(e| f )  arg max ePr( f |e) Pr(e) Pr( f ) Vì Pr(f) là không thay đổi đối với e, bài toán trở thành việc tìm câu e nhằm cực đại hoá giá trị Pr( f | e) Pr(e) , Pr( f | e) Pr(e) có giá trị cực đại khi Pr( f | e) và Pr(e) cực đại. Việc xây dựng mô hình ngôn ngữ cần sử dụng một ngữ liệu đơn ngữ lớn, trong khi đó mô hình dịch lại cần đến ngữ liệu song ngữ 16 tốt. Bộ giải mã được sử dụng để tìm ra câu dịch tốt nhất khi đã biết được Pr(e) . Để có được câu dịch, câu nguồn được chia thành I cụm liên tiếp f1I . Giả sử rằng phân phối xác suất là như nhau đối với các cụm này. Mỗi cụm fi trong f1I được dịch thành cụm tương ứng trong ngôn ngữ đích ei . Các cụm trong ngôn ngữ đích có thể đảo ví trí cho nhau. Quá trình dịch cụm được mô hình hóa bởi phân phối xác suất  ( f i | ei ) . Việc đảo vị trí (reodering) của các cụm đầu ra được mô hình bởi phân phối xác suất d(ai – bi-1), trong đó ai đại diện cho vị trí bắt đầu của cụm trong câu nguồn được dịch thành cụm thứ i trong câu đích, và bi-1 là ký hiệu chỉ vị trí kết thúc của cụm trong câu nguồn được dịch thành cụm (i-1) trong câu đích. Ở đây chúng ta sử dụng mô hình đảo cụm như sau: d (a i bi 1)   a i bi1 1| | Trong đó α là giá trị tham số thích hợp. Muốn xác định độ dài phù hợp của câu dịch, ta đưa thêm thừa số ω khi sinh ra câu trong ngôn ngữ đích. Qua quá trình tìm kiếm câu dịch tối ưu thừa số này sẽ được tối ưu. Độ dài của câu trong ngôn ngữ đích càng dài khi thừa số này càng lớn hơn 1. Như vậy, câu dịch tốt nhất e được sinh ra từ câu nguồn theo mô best hình trong là: e best  arg max Pr(e | f )  arg max Pr( f | e)Pr LM (e) e e Với Pr( f | e) được phân tích: I I Pr( f | e1 )    ( f 1 I i 1 |e ) d(a  b i i i ) i 1 length ( e ) 17 1.2 Tổng quan về 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. 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à ngày nghỉ lễ”] = 0.001 P[“nghỉ lễ là qua hôm ngày”] = 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. 1.2.1 N-gram Phương pháp đơn giản nhất để ngắt một chuỗi kí tự thành các thành phần nhỏ hơn gọi là các chuỗi con. Mỗi chuỗi con n-từ như vậy được gọi là ngram. Với n = 1 ta gọi là unigram hay còn gọi là từ; Với n = 2 ta gọi là bigram; Với n = 3 ta gọi là trigram. Nếu một chuỗi kí tự có rất nhiều n-gram hợp lệ thì ta có thể kết luận chuỗi kí tự đó là chuỗi hợp lệ. Kí hiệu b(y/x) là xác suất mà từ y theo sau từ x. Chúng ta có thể ước lượng xác suất này dựa vào Corpus. Xác suất bigram điều kiện là thương số của phép chia số lần xuất hiện cụm “xy” cho số lần xuất hiện từ “x” trong Corpus, được kí hiệu là p(x|y). Ví dụ về xác suất bigram điều kiện: 18 P(qua | hôm,): ta có thể hiểu là xác suất để từ “qua” xuất hiện sau từ “hôm”. Về giá trị này, chúng ta có thể xác định trực tiếp và tự động từ corpus tiếng Anh. Giả sử trong corpus mà ta test, “hôm” xuất hiện 468 lần, còn “hôm qua” xuất hiện 63 lần, thì P(qua | hôm) = 63/468 = 0,13. Tương tự, ta có định nghĩa tương tự đối với xác suất trigram điều kiện. Ví dụ về xác suất trigram điều kiện: P(là | hôm qua): ta có thể hiểu là xác suất để từ “là” xuất hiện sau dãy hai từ “ hôm qua”. Giả sử trong corpus mà ta test, “hôm qua là” xuất hiện 9 lần, còn “hôm qua” xuất hiện là 28 lần, như vậy P(là | hôm qua) = 9/28 = 0,32. Ta nhận thấy rằng 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 ướ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ệt 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. Ví dụ, nếu chúng ta muốn ước 19 lượng xác suất 3-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 đó: Pr(w1, w2, ..., wi) ≈ Pr(wi|wi-2, wi-1) Hình 1: Mô hình Markov bậc 2 Một cách tổng quát, gọi từ i w i  n 1 là một n-gram chiều dài n kết thúc bằng w . Khi đó để ước lượng xác xuất n-gram cho một chuỗi chiều dài N ta sử i dụng công thức: N Pr(w1 )   Pr(wi | wi n1) N i 1 i 1 1.2.2 Mô hình ngôn ngữ Trước hết chúng ta xem xét về trật tự từ. Giả sử trong cách dịch của chúng ta, có một hộp chứa các từ và chúng ta muồn lấy chúng ra theo một thứ tự hợp lý. Nhưng giả sử rằng chúng ta có vài hộp khác nhau, tương ứng là tập các nghĩa của cách dịch các từ ở hộp trên. Chúng ta có thể tìm thứ tự từ tốt nhất của mỗi hộp nhưng làm thế nào để chúng ta chọn câu của ngôn ngữ đích hợp lý nhất. Câu trả lời là chúng ta sử dụng mô hình n-gram, gán xác suất cho bất kì một dãy các từ có thể hiểu được. Sau đó chúng ta chọn ra dãy có thể nhất (xác suất cao nhất). Ví dụ: dãy các từ “hôm qua là ngày nghỉ lễ” và “tôi vẫn phải đi làm” là có thể hiểu được (có thể tồn tại) ngược lại dãy “nghỉ lễ là qua hôm ngày” và “đi tôi vẫn làm phải” là không thể hiểu được (không tồn tại). Về ngôn ngữ học, theo truyền thống chúng ta chia các dãy các từ này thành hai loại: đúng ngữ pháp và sai ngữ pháp nhưng trong dịch máy chúng ta luôn luôn phải chọn giữa hai câu đúng ngữ pháp. Ví dụ: Cách dịch nào là tốt hơn trong (A) và (B) (A) Hôm qua là ngày nghỉ lễ nhưng tôi vẫn phải đi làm. (B) Ngày hôm qua là nghỉ lễ nhưng tôi vẫn phải đi làm. 20 Mặt khác, trong nhận dạng tiếng nói người ta sử dụng khá nhiều xác suất theo kinh nghiệm gán cho dãy các từ. Ví dụ: “nghỉ lễ là” đúng hơn là “là nghỉ lễ”. Phương pháp sử dụng ở đây là dựa vào bigram hoặc trigram để chuyển chúng thành xác suất để so sánh. Để gán xác suất cho toàn bộ một câu, ta nhân xác suất điều kiện n-gram mà nó bao gồm. Vì vậy, một câu tốt (càng đúng ngữ pháp) là câu mà có nhiều dãy n-gram. Ví dụ trong bigram ta có: P(Hôm qua là ngày nghỉ lễ) = P(Hôm | đầu câu) * P(qua | Hôm) * P(là | qua) * P(ngày | là) * P(nghỉ | ngày) * P(cuổi câu | nghỉ lễ) Dễ dàng thấy rằng điều này có ích như thế nào đối với trật tự từ. Dựa vào cách tính xác suất như trên ta thấy rằng câu “Hôm qua là ngày nghỉ lễ” tốt hơn “Nghỉ lễ ngày là qua hôm”. Như vậy, ta có thể coi toàn bộ các chủ đề về gán xác suất cho một câu được gọi là mô hình ngôn ngữ. Mô hình ngôn ngữ không chỉ có ích cho thứ tự các từ mà còn có ích cho việc chọn nghĩa giữa các cách dịch khác nhau. Ví dụ: Cho 2 câu (A) và (B) (A) Áo trắng em đến trường, cùng đàn chim ca rộn ràng. (B) Em đến trường áo trắng, cùng đàn chim ca rộn ràng. Quyết định này dịch từ tiếng Anh sang tiếng Việt, cụm từ “Áo trắng em đến trường” dùng để chỉ nữ sinh còn “Em đến trường áo trắng” lại dùng để 21 chỉ trang phục. Nếu trong corpus của chúng ta, giả sử trigram “Áo trắng em đến trường” xuất hiện 10 lần, trong khi “Em đến trường áo trắng” không xuất hiện (hoặc khá nhỏ so với “Áo trắng em đến trường”) thì (A) là câu tốt hơn (được chọn). Điều đó có nghĩa là ta có thể giả quyết vấn đề nhập nhằng ngữ nghĩa chỉ dựa vào ngôn ngữ đích. 1.2.3 Huấn luyện mô hình ngôn ngữ Khi huấn luyện (xây dựng) một mô hình ngôn ngữ ta cần chuẩn bị dữ liệu là một ngữ liệu đơn ngữ (corpus) (kích thước dữ liệu huấn luyện lớn sẽ cho mô hình ngôn ngữ tốt) 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 đều cần đến tần suất của các n-gram, vì vậy ta cần đếm tần suất xuất hiện của các n-gram từ 1-gram cho đến số bậc mô hình đang huấn luyện. 1.2.3.1 Ước lượng cực đại hóa khả năng (Maximium Likelihood Estimation - MLE) Để xây dựng một mô hình ước lượng cực đại hóa khả năng với tần suất tương đối của các n-gram trong ngữ liệu ta có thể sử dụng kết quả đếm các ngram. Với ước lượng cực đại hoá khả năng, 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. Pr ( ) MLE wi c( wi )  c( w ) i' i' Với c( wi ')  | wi'| là số lần xuất hiện của từ w i' 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 Brown1, một ngữ liệu với một triệu 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à Pr MLE (Chinese)  400  0.0004 . 1000000