Khóa luận Tìm hiểu mô hình ngôn ngữ sử dụng phương pháp bloom filter

này cũng lại sử dụng một số phương pháp nội suy để kết hợp xác suất điều kiện của n-gram đang xét với xác suất n-gram bậc thấp hơn. Phụ thuộc vào phương pháp làm mịn được sử dụng, có thể chúng ta còn cần đến các thông số thống kê phụ cho từng n-gram như số lượng hậu tố (đối với làm mịn Witten-Bell, Kneser-Ney) hay tiền tố ngữ cảnh (đối với làm mịn Kneser-Ney, Stupid Backoff). Chúng ta có thể sử dụng một BF duy nhất để lưu trữ những số liệu thống kê này nhưng cần chỉ rõ loại của chúng (tần suất xuất hiện thô, số tiền tố, số hậu tố, …), bằng cách sử dụng các tập k hàm băm khác nhau cho từng loại. Lý do nên lưu trữ các dữ liệu thống kê này một cách trực tiếp vào BF, thay vì lưu các xác suất được tính toán sẵn là: (i) tính hiệu quả của quy trình mã hóa nêu trên dựa vào phân phối tần suất dạng Zipf; điều này là hoàn toàn đúng cho dữ liệu thống kê n-gram trong ngữ liệu ngôn ngữ tự nhiên, nhưng lại có thể là không đúng cho xác suất được ước lượng của chúng; (ii) sử dụng dữ liệu thống kê ngữ liệu trực tiếp, chúng ta có thể tiết kiệm cả không gian lưu trữ đồng thời giảm tỉ lệ lỗi nhờ sử dụng các thông tin trung gian khác được kết xuất từ ngữ liệu. Phân tích về tỉ lệ lỗi ở phần trên chỉ tập trung vào lỗi false positive của BF. Nhưng thực tế, không giống như các cấu trúc dữ liệu thông thường khác, độ chính xác của mô hình BF còn phụ thuộc vào các yếu tố khác trong hệ thống và cách thức mô hình được truy vấn. Chúng ta có thể tận dụng tính đơn điệu của không gian sự kiện n-gram trong ngữ liệu ngôn ngữ tự nhiên để thiết lập một cận trên cho tần suất của tất cả các n-gram này. Nhờ đó mà có thể giảm bớt số lần thực hiện vòng lặp lớn trong thuật toán kiểm tra (Thuật toán 2). Cụ thể là, nếu đã lưu trữ các n-gram bậc thấp hơn trong BF, ta có thể nói rằng một n-gram không thể tồn tại nếu bất kỳ chuỗi con nào của nó không tồn tại, ý tưởng này được gọi là bộ lọc dựa vào chuỗi con (sub-sequence filtering) [35]. Do quy trình lưu trữ tần suất BF sử dụng không bao giờ đánh giá thấp tần suất của một sự kiện, nên: tần suất của một n-gram không thể lớn hơn tần suất của chuỗi con ít xảy ra nhất của nó. Bộ lọc này giảm tỉ lệ lỗi của các mô hình ngôn ngữ BF với phương pháp làm mịn nội suy, bằng cách sử dụng giá trị nhỏ nhất được trả lại bởi các mô hình bậc thấp làm cận trên cho các mô hình cấp cao hơn. Bloom Map Bloom Map [37] được phát triển dựa trên nghiên cứu của Chazelle với một cấu trúc có tên là Bloomier Filter [10]. Bloom Map ra đời nhằm giải quyết nhu cầu lưu trữ hiệu quả cặp {khóa, giá trị} trong một cấu trúc dữ liệu tiết kiệm bộ nhớ. Không giống như LF-BF, Bloom Map không bị hạn chế với mã hóa chỉ các số nguyên dương. Giả sử chúng ta có một bảng ánh xạ khóa – giá trị cần mã hóa như sau: M = {(x1, v(x1)), … , (xi, v(xi)), …} i = 1, …, n với các khóa: X = {x1, …, xn} được lấy ra từ một tập ban đầu U cỡ u (u n), các giá trị là phần tử của một tập cố định: V = {v1, v2,…, vb} trong đó mỗi phần tử trong tập V này phải là giá trị của ít nhất một khóa nào đó thuộc tập X. Ta giả sử phân phối của các giá trị trên các khóa được đại diện bởi véc tơ không đổi sau: với. Cấu trúc dữ liệu này, bao gồm một bảng ánh xạ khóa – giá trị và một véc tơ phân phối xác suất được gọi là một - map. Giải pháp đầu tiên được đề xuất để xây dựng một - map ngẫu nhiên là Bloom Map đơn giản: đây là một cải tiến của Bloom Filter, thay vì sử dụng k hàm băm ngẫu nhiên độc lập với nhau, chúng ta sẽ sử dụng một mảng của các mảng k hàm băm độc lập ngẫu nhiên. Trong một ma trận như vậy, số dòng được cố định và bằng số lượng các giá trị (i=1,…,b). Số lượng cột ở mỗi dòng không bằng nhau, tức là nó là một hàm của số thứ tự dòng: số phần tử ở mỗi hàng i đại diện cho ki hàm băm được chọn cho giá trị vi. Nghĩa là với mỗi , ta chọn ki hàm băm . Giả sử chúng ta muốn lưu cặp khóa – giá trị (x, vi). Để thực hiện việc này, ta tính hi, j(x) . Ví dụ nếu chúng ta muốn lưu x vào hàng thứ i của ma trận hàm băm, chúng ta lần lượt đặt giá trị bit bằng 1 cho ki bit trong Bloom Filter: Trong bước kiểm tra, nếu chúng ta muốn xem liệu một phần tử có tồn tại trong B không, chúng ta kiểm tra x với mỗi từng hàng trong ma trận hàm băm [hi,j(x)]: Nếu phần tử x đó tồn tại trong B thì giá trị được trả lại sẽ là giá trị tương ứng với hàng i mà tại đó mọi giá trị bit được ánh xạ từ các hàm băm trong hàng đó có giá trị bằng 1. Nghĩa là: Nếu qval(x) = => trả lại Nếu qval(x) => trả lại giá trị vc , với c = max{qval(x)} Quá trình xây dựng và truy vấn một Bloom Map đơn giản được minh họa bằng Thuật toán 3 và Thuật toán 4. Tỉ lệ lỗi: Ta có tập các khóa cùng với giá trị của chúng: Chúng ta quan tâm đến ba loại lỗi sau: False positive - được gán cho một giá trị (tìm được một giá trị trong Bloom Map cho một khóa không được chèn vào trong Bloom Map) False negative – khóa bị gán nhầm là mang giá trị (giá trị được chèn vào trong Bloom Map trong giai đoạn huấn luyện lại không được tìm thấy trong giai đoạn kiểm tra) Gán nhầm giá trị (Missassignment) - bị gán nhầm một giá trị là (có giá trị được trả lại khi truy vấn khóa x, nhưng không phải giá trị đúng) Nếu tất cả các cặp khóa – giá trị được chèn vào Bloom Filter trong giai đoạn huấn luyện đều thuộc tập M, thì giá trị sẽ không bao giờ bị trả lại, nói cách khác, Bloom Map đơn giản không có lỗi false negative. Tuy nhiên, với cách giải thích tương tự như đối với Bloom Filter cơ bản, sẽ luôn tồn tại lỗi false positive. Thuật toán 3: Xây dựng một Bloom Map đơn giản Đầu vào: Bảng ánh xạ M, mảng bit B, tập các hàm băm Đầu ra: Bloom Map đơn giản (B, H) for do for do end for end for Thuật toán 4: Truy vấn một Bloom Map đơn giản Đầu vào: Bloom Map đơn giản (B, H), một khóa Đầu ra: for do if then end if end for if then return else return end if Hơn nữa, do có thể tồn tại nhiều hơn một dòng trong ma trận hàm băm thỏa mãn toán tử trong công thức … tạo ra một giá trị chỉ mục i sai, đồng thời lại trùng hợp là giá trị lớn nhất, nên việc gán sai giá trị cũng có thể xảy ra. Nếu ta gọi m là số bit trong B, là tỉ lệ bit vẫn mang giá trị là 0 sau quá trình huấn luyện, và , Talbot và Obsborne [37] đã tính được rằng cả , tỉ lệ lỗi false positive và , tỉ lệ lỗi gán sai giá trị có một cận trên tại: Qua một quá trình tối ưu hóa dựa trên thừa số Lagrange, một số chỉ số được tính toán cho kết quả như sau: Cỡ của bộ lọc bit: Số lượng hàm băm cho giá trị thứ i: Số lượng bit dành cho mỗi khóa: với > 0 là một hằng số đại diện cho cận trên của tỉ lệ lỗi false positive do người sử dụng thiết lập. Để hiểu rõ hơn chi tiết các bước tính toán để ra được các chỉ số này, người đọc có thể tham khảo thêm trong [37]. Bloom Map nhanh: Cấu trúc dữ liệu Bloom Map vừa được giới thiệu ở trên chỉ là nền tảng cơ bản cho một loại Bloom Map nhanh, dựa trên việc sử dụng cây nhị phân, cùng với những đặc tính của Bloom Map cơ bản như không có lỗi false negative, tỉ lệ lỗi false positive và gán sai giá trị có thể kiểm soát được. Cấu trúc dữ liệu Bloom Map này có hai dạng, được gọi là Bloom Map tiêu chuẩn và Bloom Map nhanh. Bloom Map nhanh tuy sử dụng nhiều không gian lưu trữ hơn một chút ít nhưng có ưu điểm là sử dụng ít bit hơn trong quá trình truy vấn khóa – giá trị. Số lượng bit trung bình cần cho một khóa là: và số bit cần dùng trong quá trình truy vấn là: 3 (khi ) (khi ) Lưu ý: Từ nay trở đi trong khóa luận này, ta sẽ gọi chung các mô hình ngôn ngữ sử dụng cấu trúc dữ liệu dựa trên Bloom Filter là BF-LM. Mô hình ngôn ngữ xây dựng sử dụng cấu trúc dữ liệu Log-Frequency Bloom Filter được viết tắt là LF-BF-LM; nếu sử dụng cấu trúc dữ liệu Bloom Map thì được gọi là BloomMap-LM. Chương 3 Thử nghiệm: Xây dựng LM với RandLM và SRILM Các thử nghiệm trình bày trong luận văn này đều được thực hiện trên cùng một máy tính cấu hình như sau: CPU: Intel Core2Duo 1.86GHz x 2 RAM: 2GB DDR2 Hệ điều hành: Linux Mint 8 Helena 32-bit Trong chương này, chúng tôi trình bày thử nghiệm xây dựng các mô hình ngôn ngữ với hai công cụ RandLM và SRILM [34]. Các mô hình ngôn ngữ BF-LM được xây dựng với công cụ mã nguồn mở RandLM Mã nguồn RandLM có thể được download miễn phí từ: . Công cụ này được phát triển để xây dựng LM dung lượng thấp nhờ sử dụng các cấu trúc dữ liệu xác suất, điển hình là Bloom Filter. Sau khi biên dịch, công cụ này tạo ra hai file thực thi là buildlm và querylm. File buildlm được dùng để xây dựng các mô hình ngôn ngữ. Còn file querylm sử dụng để truy vấn LM, trả lại kết quả thống kê n-gram hoặc xác suất điều kiện log. Các mô hình ngôn ngữ chuẩn, không mất mát được xây dựng sử dụng SRI Language Modelling Toolkit (SRILM) Tài liệu hướng dẫn và mã nguồn của SRILM có thể được download miễn phí từ: . SRILM là một dự án mã nguồn mở bao gồm nhiều chương trình, thư viện C++ và script hỗ trợ trong việc xây dựng và thử nghiệm các mô hình ngôn ngữ cho nhận dạng tiếng nói hoặc các ứng dụng khác. Nó hỗ trợ nhiều kiểu mô hình ngôn ngữ khác nhau dựa trên thống kê về n-gram. SRILM đã được phát triển từ năm 1995 ở Phòng nghiên cứu công nghệ tiếng nói SRI, và vẫn còn đang được tiếp tục sửa chữa, mở rộng bởi nhiều nhà nghiên cứu trong cộng đồng NLP. Ngữ liệu Thử nghiệm này được thực hiện trên hai ngữ liệu: một ngữ liệu đơn ngữ tiếng Anh có dung lượng lớn và một ngữ liệu nhỏ tiếng Việt. Ngữ liệu tiếng Anh là ngữ liệu chính, các LM xây dựng từ ngữ liệu này sẽ được sử dụng trong thử nghiệm về dịch máy thống kê với Moses ở chương sau. Ngữ liệu tiếng Anh: Ngữ liệu đơn ngữ tiếng Anh là bộ ngữ liệu tổng hợp từ nhiều nguồn khác nhau, được sử dụng tại ACL 2010 – Workshop lần thứ năm , gồm 48.6 triệu câu, dung lượng 5.7 GB không nén, các câu trong ngữ liệu đã được đảo thứ tự một cách ngẫu nhiên. Thống kê chi tiết hơn về ngữ liệu này có thể được tham khảo ở bảng 1. Bảng 1: Thống kê ngữ liệu News Shuffle Dung lượng 5.7 GB Gzip 2.4 GB Số lượng câu 48,653,883 Số lượng từ 1,133,192,971 Độ dài trung bình câu 23 Đây là một ngữ liệu lớn, do hạn chế về thời gian và tài nguyên hệ thống thử nghiệm nên chỉ một phần ngữ liệu này được trích xuất và sử dụng cho các thử nghiệm trong khuôn khổ luận văn này (bộ ngữ liệu lớn nhất được sử dụng trong thử nghiệm là 1 GB dữ liệu văn bản). Toàn bộ ngữ liệu được chuyển thành chữ thường sử dụng script lowercase.perl (script này nằm trong một bộ script hỗ trợ sẽ được giới thiệu chi tiết hơn ở chương sau). scripts/lowercase.perl working-dir/corpus/news_lowercased Các tập ngữ liệu đã được trích xuất và tiền xử lý ở trên được sử dụng để huấn luyện các mô hình ngôn ngữ 3-gram và 4-gram sử dụng hai bộ công cụ SRILM và RandLM. Dung lượng các tập ngữ liệu này được thể hiện trong Bảng 2. Bảng 2: Thống kê các tập ngữ liệu tiếng Anh được sử dụng để xây dựng LM (Set 14) Set 1 Set 2 Set 3 Set 4 Số lượng câu 2,137,817 4,275,634 6,413,452 8,551,269 Số lượng từ 49,817,252 99,590,072 149,379,391 199,163,279 Độ dài trung bình câu (từ) 23 23 23 23 Cỡ từ điển 409,785 584,968 717,013 824,974 Dung lượng 0.25 GB 0.50 GB 0.75 GB 1.00 GB Gzip 103.4 MB 206.8 MB 310.1 MB 413.5 MB Ngữ liệu tiếng Việt: Một ngữ liệu nhỏ đơn ngữ tiếng Việt cũng được sử dụng với mục đích củng thêm cố kết quả với việc thử nghiệm trên nhiều ngữ liệu khác nhau. Ngữ liệu này được xây dựng từ nhiều bài viết trên “Báo Lao động” phiên bản điện tử “Báo Lao động” điện tử: thuộc nhiều lĩnh vực khác nhau như khoa học, kinh tế, thể thao, văn hóa [1]. Các thống kê về ngữ liệu này được liệt kê trong bảng dưới đây: Bảng 3: Thống kê về ngữ liệu Tiếng Việt “Báo Lao động” điện tử Thống kê chung Dung lượng 78.4 MB Gzip 25.9 MB Số lượng câu 557,736 Số lượng từ 12,516,790 Độ dài trung bình câu 22.4 Thống kê n-gram 1-gram 257,446 2-gram 2,639,657 3-gram 1,428,292 4-gram 1,198,019 Thuật toán làm mịn Mô hình ngôn ngữ không mất mát được huấn luyện sử dụng thuật toán làm mịn Kneser-Ney cải tiến (MKN). Do trong những thử nghiệm này, chúng ta chỉ quan tâm đến đặc tính, hiệu suất của các cấu trúc dữ liệu (không mất mát và có mất mát thông tin) mà không cần xác suất chính xác của từng sự kiện, nên thuật toán Stupid Backoff của Google được sử dụng trong quá trình xây dựng BF-LM vì nó nhanh và đơn giản. Hơn nữa chất lượng của thuật toán làm mịn Stupid Backoff đã được chứng minh là xấp xỉ với thuật toán MKN với ngữ liệu lớn [5]. Xây dựng LM với SRILM và RandLM Với ngữ liệu tiếng Anh: Các mô hình ngôn ngữ SRILM được xây dựng từ các tập ngữ liệu trên sử dụng lệnh sau: ./ngram-count -order 3 -interpolate –kndiscount -text /corpus/news.lowercased_1GB.gz -lm model_sri_1.00GB_3-grams.txt Câu lệnh trên sẽ tạo ra một mô hình ngôn ngữ 3-gram trong file model_sri_1.00GB_3-grams.txt từ file ngữ liệu news.lowercased_1GB.gz (SRILM cho phép đầu vào và đầu ra sử dụng file nén). Ta cũng có thể yêu cầu SRILM tạo ra những mô hình ngôn ngữ bậc cao hơn như 4-gram, 5-gram, thậm chí cao hơn nữa. Nhưng khi tham số này tăng thì lượng bộ nhớ cần dùng cũng tăng lên rất nhanh. SRILM sử dụng RAM để lưu trữ kết quả đếm n-gram tạm thời, với cấu hình máy tính thử nghiệm đã nêu trên (sử dụng 2GB RAM), chúng tôi đã xây dựng được mô hình ngôn ngữ 3-gram từ tập ngữ liệu 1GB; nhưng không tạo được mô hình 4-gram với cùng lượng dữ liệu do thiếu RAM trong bước thống kê n-gram. Tham số -kndiscount yêu cầu SRILM sử dụng thuật toán Kneser-Ney cải tiến trong bước làm mịn. Các thuật toán làm mịn khác có thể được dùng trong SRILM là Good-Turing hay Witten-Bell. Việc xây dựng mô hình tốn khoảng 10 phút cho tập ngữ liệu 0.25GB (Set 1) cho đến vài tiếng đối với tập ngữ liệu 1GB (Set 4). Sau khi xây dựng ta có thể xem có bao nhiêu n-gram mỗi bậc trong file mô hình ngôn ngữ vừa được tạo ra (head –n 5 model_sri_1.00GB_3-grams.txt). Bảng 4: Thống kê số lượng các n-gram trong các tập ngữ liệu 1-gram 2-gram 3-gram Set 1 409,806 6,322,122 4,648,704 Set 2 585,002 9,720,557 9,294,600 Set 3 717,048 12,354,288 13,813,750 Set 4 825,026 14,549,604 18,171,077 Đối với RandLM, xây dựng mô hình ngôn ngữ có thể được thực hiện theo 3 cách: i) từ ngữ liệu đã được chia từ sẵn; ii) từ một tập các cặp n-gram và số lần xuất hiện của nó (cặp ngram-count); iii) từ một mô hình ngôn ngữ backoff đã được xây dựng trước đó với định dạng ARPA (định dạng của mô hình ngôn ngữ được tạo ra từ SRILM). Nếu xây dựng theo cách đầu tiên hoặc thứ hai, mô hình được gọi là CountRandLM, sử dụng loại thứ ba thì được gọi là BackoffRandLM. CountRandLM có thể sử dụng làm mịn StupidBackoff hoặc Witten-Bell. BackoffRandLM có thể sử dụng bất kỳ phương pháp làm mịn nào mà SRILM hỗ trợ. Ví dụ ta xây dựng BloomMap-LM 3-gram từ tập ngữ liệu 1GB sử dụng lệnh sau: ./buildlm –struct BloomMap –falsepos 8 –values 8 –output-prefix randlm_3-grams_1.00GB –input-path /corpus/news.lowercased_1GB.gz –order 3 –working-mem 1500 Tham số -falsepos quyết định tỉ lệ lỗi false positive của cấu trúc dữ liệu, ví dụ -falsepos 8 cho ta tỉ lệ lỗi là 1/28. Tham số values quyết định khoảng lượng tử hóa của mô hình, bậc của logarit sử dụng trong quá trình lượng tử hóa sẽ là 21/values nếu ta sử dụng tham số -values 8. Tham số order xác định bậc của mô hình n-gram. Tham số input-path: đường dẫn tới ngữ liệu được dùng để tạo LM. Đặc biệt tham số -struct quyết định cấu trúc dữ liệu được sử dụng để xây dựng mô hình ngôn ngữ. Hiện tại, RandLM hỗ trợ hai loại cấu trúc dữ liệu là Log-Frequency Bloom Filter (-struct LogFreqBloomFilter) và Bloom Map (-struct BloomMap). Sử dụng RandLM, chúng tôi sẽ xây dựng các mô hình ngôn ngữ với cả hai loại cấu trúc dữ liệu này để so sánh kích thước cũng như hiệu quả của từng cấu trúc dữ liệu. Tham số “-working-mem 1500” có nghĩa là cho phép sử dụng 1500MB trong quá trình sắp xếp các n-gram. Các file được tạo ra sau quá trình xây dựng LM với câu lệnh trên bao gồm: randlm_3-grams_1.00GB.BloomMap Mô hình ngôn ngữ randlm_3-grams_1.00GB.counts.sorted.gz Thống kê n-gram randlm_3-grams_1.00GB.stats.gz Thống kê kết quả đếm randlm_3-grams_1.00GB.vcb.gz File chứa từ vựng Cả hai file .stats.gz và .counts.sorted.gz đều có thể được khai báo sử dụng lại, tránh tính toán nhiều lần khi cần xây dựng thêm LM từ bộ ngữ liệu giống nhau. Điều này là rất cần thiết do trong thử nghiệm nhiều khi cần xây dựng LM nhiều lần với giá trị các tham số khác nhau. Ví dụ: ./buildlm –struct BloomMap –falsepos 8 –values 10 –order 3 –output-prefix randlm_3-grams_1.00GB_values10 –input-path randlm_3-grams_1.00GB.counts.sorted.gz -input-type counts -stats-path randlm_3-grams_1.00GB.stats.gz –working-mem 1500 sẽ xây dựng một BloomMap-LM mới từ cùng ngữ liệu đã sử dụng trước đó nhưng với giá trị lượng tử hóa khác (–values 10) mà không cần tính toán lại các file thống kê. Thời gian để xây dựng các BF-LM sử dụng RandLM lâu hơn khi xây dựng các mô hình ngôn ngữ chuẩn cùng bậc, cùng lượng dữ liệu trong SRILM; mất xấp xỉ 20 tiếng RandLM mới xây dựng xong mô hình ngôn ngữ 3-gram với 1GB ngữ liệu (Set 4). RandLM lưu trữ mọi thứ trên đĩa cứng, nên việc thống kê, sắp xếp cũng mất nhiều thời gian hơn. Nhưng bù lại, RandLM lại có thể xây dựng các mô hình ngôn ngữ bậc cao hơn, sử dụng nhiều dữ liệu hơn SRILM. Ví dụ, trên máy tính thử nghiệm, RandLM đã có thể xây dựng thành công mô hình ngôn ngữ 4-gram từ 1GB ngữ liệu huấn luyện, trong khi SRILM thì không thể. Tuy thời gian huấn luyện của RandLM lâu hơn SRILM nhưng đó không phải là vấn đề lớn, vì ta chỉ xây dựng mô hình ngôn ngữ một lần duy nhất. Hơn nữa, dung lượng các mô hình ngôn ngữ Bloom Filter xây dựng từ RandLM chiếm ít bộ nhớ hơn các mô hình chuẩn từ SRILM rất nhiều. Bảng 5 thống kê dung lượng các mô hình ngôn ngữ 3-gram tạo bởi hai công cụ này (không nén) với các bộ ngữ liệu kích thước khác nhau. Bảng 5: Kích thước các loại LM khác nhau trên các tập ngữ liệu Set 1 Set 2 Set 3 Set 4 BloomMap 52.5 MB 86.6 MB 114.4 MB 138.8 MB Log-Freq BF 63.4 MB 102.1 MB 136.8 MB 181.5 MB SRILM 290.7 MB 511.6 MB 710.4 MB 893.4 MB Qua bảng trên ta có thể thấy rằng dung lượng các mô hình ngôn ngữ tạo bởi RandLM chỉ bằng khoảng 1/6 lần dung lượng mô hình ngôn ngữ chuẩn tạo bởi SRILM nếu sử dụng cấu trúc dữ liệu Bloom Map, và bằng khoảng 1/5 lần nếu sử dụng cấu trúc dữ liệu Log-Frequency Bloom Filter. Với cùng các tham số khi xây dựng bằng RandLM, nhưng LM với cấu trúc dữ liệu LF-BF có kích thước lớn hơn LM với cấu trúc dữ liệu Bloom Map (khoảng 20 - 30%). Biểu đồ 3: Dung lượng các LM tạo từ RandLM và SRILM Nhìn vào biểu đồ 3, ta có thể kết luận rằng càng sử dụng nhiều dữ liệu huấn luyện, thì càng tiết kiệm được không gian lưu trữ; nghĩa là tỉ lệ chênh lệch giữa dung lượng LM chuẩn và mô hình xây dựng bằng công cụ RandLM tạo ra từ cùng một ngữ liệu huấn luyện càng tăng. Thế nhưng để trả lời cho câu hỏi liệu việc tiết kiệm dung lượng này làm hiệu quả LM giảm như thế nào so với LM chuẩn thì cần phải được trả lời bằng thực nghiệm. Với ngữ liệu tiếng Việt: Kết quả xây dựng LM bậc 2, 3 và 4 từ bộ ngữ liệu tiếng Việt được thể hiện trong biểu đồ dưới đây: Biểu đồ 4: Dung lượng các LM tiếng Việt Các LM này được xây dựng với bậc n-gram khác nhau, từ 2-gram cho đến 4-gram. Kết quả thể hiện trong biểu đồ một lần nữa cho thấy sự chênh lệch lớn về dung lượng giữa các mô hình ngôn ngữ SRILM chuẩn và RandLM. Chương 4 Thử nghiệm: Hệ thống dịch máy thống kê với Moses Các mô hình được xây dựng ở trên sẽ được dùng trong dịch máy thống kê sử dụng hệ thống dịch máy mã nguồn mở Moses [21]. Kết quả dịch sau đó được đánh giá bằng điểm BLEU. Qua đó ta có thể so sánh hiệu quả của mô hình ngôn ngữ sử dụng Bloom Filter với mô hình ngôn ngữ chuẩn truyền thống. Dịch máy thống kê Giới thiệu về dịch máy và dịch máy thống kê Các mô hình ngôn ngữ n-gram được sử dụng rất nhiều trong các bài toán của Xử lý ngôn ngữ tự nhiên như xử lý tiếng nói, kiểm tra chính tả, nhận dạng chữ viết, dịch máy, … Mục này sẽ minh họa một ứng dụng cụ thể của LM với việc giới thiệu sơ lược LM được sử dụng như thế nào trong một hệ thống Dịch máy thống kê dựa trên cụm (Phrase-based Statistical Machine Translation) [22]. Dịch máy (Machine Translation - MT) là một hướng phát triển có lịch sử lâu đời từ thập kỷ 50 và được phát triển mạnh mẽ từ thập kỷ 80 cho đến nay. Hiện tại, trên thế giới có rất nhiều hệ dịch máy thương mại nổi tiếng trên thế giới 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). 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à vẫn còn được sử dụng phổ biến trong nhiều hệ dịch thương mại. Các 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ư Anh-Phá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 khác nhau như Anh-Trung, Anh-Nhật, … Ở Việt Nam, dịch Anh-Việt, Việt-Anh 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 [23]. Hiện nay, nhiều nghiên cứu với mong muốn tăng chất lượng dịch vẫn đang được thực hiện thích nghi với đặc điểm của các cặp ngôn ngữ khác nhau. 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 vì 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. Chính vì vậy, 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. Trong 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; 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 8. 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. Thường thì LM được gán trọng số cao hơn các thành phần khác trong hệ thống dịch, bởi vì ngữ liệu đơn ngữ dùng để huấn luyện LM lớn hơn nhiều ngữ liệu song ngữ, do đó có độ tin cậy lớn hơn. Och [28] đã chỉ ra rằng việc tăng kích cỡ của LM cải thiện điểm BLEU – tiêu chuẩn phổ biến để đánh giá chất lượng dịch máy. Hình 7, trích từ [19], cho thấy sự cải thiện chất lượng dịch khi tăng kích cỡ LM. Hình 7: Tăng kích cỡ LM cải thiện điểm BLEU [19] Trong mô hình đầu tiên của Brown, mô hình dịch dựa trên kiểu từ-thành-từ [8] và chỉ cho phép ánh xạ một từ trong ngôn ngữ nguồn đến một từ trong ngôn ngữ đích. Nhưng trong thực tế, ánh xạ này có thể là một-một, một-nhiều, nhiều-nhiều hoặc một-không. Thế nên nhiều nhà nghiên cứu đã cải tiến chất lượng của SMT bằng cách sử dụng dịch dựa trên cụm (phrase-based translation) [22][26]. Tiền xử lý Ngôn ngữ nguồn ( f ) Bộ giải mã Hậu xử lý Mô hình ngôn ngữ Pr(e) Mô hình dịch Pr(f | e) Ngôn ngữ đích ( e ) Hình 8: Kiến trúc của một hệ thống SMT [20] Dịch máy thống kê dựa trên cụm That songwriter wrote many romantic songs Nhạc sĩ đó đã viết nhiều bài hát lãng mạn Hình 9: Minh họa dịch máy thống kê dựa vào cụm Trong 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ác nhau. Hình 9 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. Cuối cùng ta thu được câu dịch trong ngôn ngữ đích. Giả sử ta gọi ngôn ngữ nguồn là f và ngôn ngữ đích là e, chúng ta sẽ cố gắng tối đa hóa xác suất với mong muốn có được bản dịch tốt nhất. Thực tế là tồn tại rất nhiều 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 sử dụng mô hình kênh nhiễu, áp dụng công thức Bayes ta có: Do Pr(f) là không đổi đối với e, vấn đề trở thành việc tìm câu e nhằm tối đa hóa . 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ữ tốt. Bộ giải mã được sử dụng để chia câu nguồn thành các cụm và sinh ra các khả năng dịch có thể cho mỗi cụm nhờ sự trợ giúp của bảng cụm (phrase table). Để sinh ra được câu dịch, câu nguồn được chia thành I cụm liên tiếp . Chúng ta 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 trong được dịch thành cụm tương ứng trong ngôn ngữ đích . 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 . 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 , 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 rất đơn giản như sau: với giá trị thích hợp cho tham số α. Để xác định độ dài thích hợp của câu dịch, chúng ta đưa thêm vào thừa số ω khi sinh ra câu trong ngôn ngữ đích. Thừa số này sẽ được tối ưu qua quá trình tìm kiếm câu dịch tối ưu. Thừa số này càng lớn hơn 1 thì độ dài của câu trong ngôn ngữ đích càng dài. Nói tóm lại, câu dịch tốt nhất ebest được sinh ra từ câu nguồn theo mô hình trong [22] là: ở đây được phân tích thành: Điểm BLEU Đánh giá chất lượng các hệ thống dịch có thể được thực hiện thủ công bởi con người hoặc tự động. Quá trình đánh giá thủ công cho điểm cho các câu dịch dựa trên sự trôi chảy và chính xác của chúng. Phần lớn mọi người cho rằng đây là phương pháp đánh giá chính xác nhất. Thế nhưng công việc đánh giá thủ công này lại tiêu tốn quá nhiều thời gian, đặc biệt khi cần so sánh nhiều mô hình ngôn ngữ, nhiều hệ thống khác nhau. Công bằng mà nói, mỗi phương pháp đều có ưu nhược điểm riêng. Tuy đánh giá tự động không thể phản ánh được hết mọi khía cạnh của chất lượng dịch, nhưng nó có thể nhanh chóng cho ta biêt: chất lượng của hệ dịch ở tầm nào, có tăng lên hay không sau khi cải tiến hoặc thay đổi một tham số nào đó. Trong thực tế, hai phương pháp này vẫn được sử dụng đồng thời, và điểm BLEU là độ đo chất lượng hệ dịch phổ biến nhất hiện nay, được đề xuất bởi Papineni năm 2002 [32]. BLEU tính điểm bằng cách đối chiếu kết quả dịch với tài liệu dịch tham khảo và tài liệu nguồn. Mặc dù [9] chỉ ra rằng điểm BLEU thường không thực sự tương quan với đánh giá thủ công của con người với các loại hệ thống khác nhau, thế nhưng vẫn có thể khá chính xác để đánh giá trên cùng một hệ thống, hoặc những hệ thống tương tự nhau. Chính vì vậy, trong khóa luận này, điểm BLEU được sử dụng làm thước đo chất lượng dịch, từ đó so sánh các loại mô hình ngôn ngữ khác nhau. Baseline system Chúng tôi xây dựng hệ thống dịch sử dụng GIZA++ 2.0 [29], SRILM [34] và bộ huấn luyện cực tiểu hóa tỉ lệ lỗi (Minimum Error Rate Training – MERT) [27] để gióng hàng các từ, xây dựng mô hình ngôn ngữ, tối ưu hóa các trọng số sử dụng trong quá trình dịch. Mô hình ngôn ngữ sử dụng trong huấn luyện là một mô hình 3-gram với thuật toán làm mịn Kneser-Ney cải tiến. MERT được thực hiện trên tập ngữ liệu phát triển được sử dụng tại WMT năm 2008, gồm 2000 cặp câu song ngữ Đức – Anh (thống kê ở bảng 7). Bảng cụm được tạo ra sau quá trình huấn luyện có dung lượng 800.8 MB; một bảng hỗ trợ đảo vị trí từ (lexical reordering table) [15][38] cũng được tạo ra có dung lượng 186.5 MB. Trong quá trình xây dựng và thử nghiệm trên hệ thống dịch này, chúng tôi có sử dụng một số script hỗ trợ Download từ Script MTeval: ftp://jaguar.ncsl.nist.gov/mt/resources/mteval-v11b.pl bao gồm: Bộ tách từ tokenizer.perl Script chuyển toàn bộ văn bản sang chữ thường lowercase.perl SGML-Wrapper có nhiệm vụ đóng gói dữ liệu theo định dạng XML của hệ thống tính điểm NIST BLEU : wrap-xml.perl Script NIST MTeval version 11b mteval-v11b.pl dùng để tính điểm BLEU Ngữ liệu Hệ thống dịch được huấn luyện sử dụng ngữ liệu Europarl [18] song ngữ Đức – Anh version 3 gồm 1.2 triệu câu trong mỗi ngôn ngữ. Thế nhưng sau khi loại bỏ bớt các câu có độ dài lớn hơn 40 từ tương ứng ở cả hai ngôn ngữ, chỉ còn khoảng gần 1 triệu cặp câu (mất 268,000 cặp câu). Nguyên nhân ta cần phải làm như vậy là vì quá trình huấn luyện bằng GIZA++ tốn rất nhiều thời gian nếu có nhiều câu dài. Thống kê đầy đủ về ngữ liệu này sau khi lọc có thể được tham khảo ở bảng 7. Mô hình ngôn ngữ tiếng Anh dùng trong huấn luyện hệ thống dịch được xây dựng từ ngữ liệu Europarl đơn ngữ tiếng Anh (xem thống kê chi tiết ở bảng 6). Bảng 6: Thống kê chi tiết ngữ liệu Europarl đơn ngữ tiếng Anh dùng để xây dựng LM huấn luyện hệ thống dịch Dung lượng 200.6 MB Gzip 62.7 MB Số lượng câu 1,412,546 Số lượng từ 38,280,717 Độ dài trung bình câu 27 Cỡ từ điển (từ) 100,795 Bảng 7: Thống kê ngữ liệu song ngữ Đức – Anh dùng để huấn luyện, phát triển và đánh giá Trong bước đánh giá thì đó là văn bản nguồn tiếng Đức và văn bản dịch tham khảo bằng tiếng Anh hệ thống dịch Tiếng Đức Tiếng Anh Huấn luyện Số lượng câu 997,575 Số lượng từ 20,341,901 21,432,529 Độ dài câu trung bình (từ) 20.4 21.5 Cỡ từ điển (từ) 226,387 74,581 Phát triển Số lượng câu 2000 Số lượng từ 55,118 58,761 Độ dài câu trung bình (từ) 27.6 29.4 Cỡ từ điển (từ) 8,796 6,118 Đánh giá Số lượng câu 2000 Số lượng từ 54,232 58,055 Độ dài câu trung bình (từ) 27.1 29.0 Cỡ từ điển (từ) 8,669 6058 Kết quả thử nghiệm Hệ thống dịch được thử nghiệm với các mô hình ngôn ngữ SRILM và RandLM, với việc dịch 2000 câu tiếng Đức. Thời gian để dịch hết 2000 câu này khi sử dụng mô hình ngôn ngữ SRILM là 98 phút, đối với BloomMap-LM là 124 phút và với LF-BF-LM là 117 phút. Như vậy là khi sử dụng các loại BF-LM, thời gian dịch lâu hơn khi sử dụng mô hình ngôn ngữ chuẩn khoảng 1.3 lần. Khoảng thời gian dịch lâu hơn này không phải là tồi khi ta xem xét đến phần bộ nhớ đã tiết kiệm được nhờ sử dụng các LM dựa trên Bloom Filter. Bảng 8: Thời gian dịch 2000 câu tiếng khi sử dụng các loại LM khác nhau Loại LM Thời gian dịch (phút) SRI-LM 98 BloomMap-LM 124 LF-BF-LM 117 Hình 9: Định dạng XML của NIST MT TRANSLATED ENGLISH TEXT TRANSLATED ENGLISH TEXT ... TRANSLATED ENGLISH TEXT TRANSLATED ENGLISH TEXT ... Để đánh giá kết quả dịch, chúng tôi sử dụng điểm BLEU. Do đó, sau khi dịch, kết quả được đóng gói lại theo định dạng XML của hệ thống tính điểm NIST MT. Hình 9 là một ví dụ của định dạng XML này. Script MTeval sử dụng ba đầu vào để đánh giá kết quả dịch: file chứa văn bản ở ngôn ngữ nguồn, file chứa kết quả dịch ở ngôn ngữ đích và một file dịch chuẩn dùng để tham chiếu. Điểm BLEU cho kết quả dịch với các LM khác nhau được thể hiện trong bảng 9. Các mô hình ngôn ngữ này đều được xây dựng từ tập ngữ liệu Set 4 gồm 1 GB ngữ liệu tiếng Anh. Nhìn vào kết quả này ta có thể thấy rằng nếu cùng sử dụng mô hình 3-gram thì hệ thống dịch sử dụng mô hình ngôn ngữ SRI-LM có điểm cao hơn khi sử dụng mô hình các mô hình BF-LM. Nhưng sự chênh lệch này không phải là lớn, trong trường hợp này là SRILM cho điểm cao hơn BloomMap-LM 3.5%, cao hơn LF-BF-LM 4%, nên ta có thể coi các điểm số này là tương đương nhau với cùng bậc n-gram. Thế nhưng, như đã nói ở phần trên, với cấu hình máy tính dùng cho thử nghiệm, ta chỉ có thể xây dựng mô hình ngôn ngữ 4-gram nếu sử dụng BF-LM. Sử dụng mô hình ngôn ngữ 4-gram BF-LM này (sử dụng cấu trúc dữ liệu Bloom Map) trong hệ thống dịch cho điểm số là 19.93, cao hơn rõ rệt khi sử dụng mô hình ngôn ngữ SRI-LM với 18.25 điểm. Bảng 9: Điểm BLEU cho kết quả dịch với các LM khác nhau Cỡ LM Điểm BLEU SRI-LM 3-gram 893.4 MB 18.25 BloomMap-LM 3-gram 138.8 MB 17.63 LF-BF-LM 3-gram 181.5 MB 17.55 BloomMap-LM 4-gram 302.2 MB 19.93 Ta đã biết rằng dung lượng các LF-BF-LM rõ ràng là cao hơn BloomMap-LM. Nhưng qua thử nghiệm trong thực tế dịch, điểm BLEU của hệ thống sử dụng LF-BF-LM không hề cao hơn so với khi sử dụng BloomMap-LM (với cùng bậc n-gram). Thậm chí sử dụng BloomMap-LM điểm số còn nhỉnh hơn một chút. Hơn thế nữa, thời gian dịch khi sử dụng 2 loại mô hình này có sự chênh lệch không lớn. Nhìn vào kết quả này, ta có thể thấy rõ ưu thế của cấu trúc dữ liệu Bloom Map so với cấu trúc dữ liệu Log-Frequency Bloom Filter, vừa sử dụng ít bộ nhớ hơn, vừa hiệu quả hơn. Kết luận Qua các chương của khóa luận, chúng tôi đã trình bày lý thuyết và thử nghiệm các mô hình ngôn ngữ xây dựng dựa trên hai cấu trúc dữ liệu Bloom Filter là Log-Frequency Bloom Filter và Bloom Map. Đây là các cấu trúc dữ liệu có ưu điểm nổi bật là khả năng tiết kiệm đáng kể bộ nhớ nhờ có sự chia sẻ bit dùng trong lưu trữ. Tuy phải đánh đổi điều này với một xác suất lỗi khác 0, nhưng xác suất lỗi này lại là yếu tố có thể điều khiển được. Từ kết quả các thử nghiệm, ta có thể nhận thấy các mô hình ngôn ngữ Bloom Filter có hiệu quả xấp xỉ các lossless LM chuẩn nhưng tốc độ truy vấn chậm hơn. Thế nhưng điều quan trọng là nó cho phép ta xây dựng các LM có bậc cao hơn, sử dụng ngữ liệu lớn hơn; giải quyết được yêu cầu vừa tiết kiệm tài nguyên mà vẫn tận dụng được tri thức của các ngữ liệu lớn. Trong tương lai, tôi mong muốn tiếp tục nghiên cứu các mô hình ngôn ngữ có nền tảng là các PDS và áp dụng vào xây dựng một hệ thống dịch máy thống kê Anh – Việt, Việt - Anh với ngữ liệu lớn. Hơn thế nữa, việc nghiên cứu ứng dụng của chúng trong các bài toán khác cũng vẫn còn rộng mở. PHỤ LỤC Chương trình truy vấn RandLM GenStats.h #ifndef GENSTATS_H #define GENSTATS_H #include "RandLMParams.h" #include "RandLMTool.h" #include "RandLM.h" namespace randlm { class GenStats { public: // Constructor GenStats(int argc, char ** argv) { inParam = argv; randlm_ = NULL; test_data_ = NULL; vocab = NULL; order_ = 0; corpus_data_ = false; getcounts_ = false; outputFile = ""; assert(load()); } // Destructor ~GenStats() { delete randlm_; delete test_data_; } // Token a string into a vector static void Tokenize(const string& str, vector& tokens, const string& delimiters = ":") { // Skip delimiters at beginning. string::size_type lastPos = str.find_first_not_of(delimiters, 0); // Find first "non-delimiter". string::size_type pos = str.find_first_of(delimiters, lastPos); while (string::npos != pos || string::npos != lastPos) { // Found a token, add it to the vector. tokens.push_back(str.substr(lastPos, pos - lastPos)); // Skip delimiters. Note the "not_of" lastPos = str.find_first_not_of(delimiters, pos); // Find next "non-delimiter" pos = str.find_first_of(delimiters, lastPos); } } // reads ngrams from file and writes scores them to stdout, output file bool query(); // check and format user's input vector formatTestInfo(string info); // set test info bool setTestInfo(vector testInfo); private: // load RandLM file into memory bool load(); RandLM* randlm_; // RandLM file CountRandLM* count_randlm_; // use this if return only counts TestCorpus* test_data_; // Test data Vocab* vocab; // Vocabulary info int order_; // order of LM bool corpus_data_; // input file is corpus or ngrams ? bool getcounts_; // if != NULL, return only counts char ** inParam; // argv string outputFile; // output file }; } endif // GENSTATS GenStats.cpp #include #include using namespace std; #include "genstats.h" #include namespace randlm { // Query bool GenStats::query() { assert(test_data_ != NULL); WordID sentence[Corpus::kMaxSentenceWords]; double start = clock(); int len = 0; int found = 0; uint64_t counter = 0; long sentenceNo = 0; bool out = false; ofstream output; // open output file for writing if(outputFile != "") { out = true; output.open (outputFile.c_str()); } // query as sentences if (corpus_data_) { while (test_data_->nextSentence(&sentence[0], &len)) { cout << "SENTENCE No." << sentenceNo + 1 << ": "; if(out) output << "SENTENCE No." << sentenceNo + 1 << ": "; for (int i = 0; i < len; i++) { cout getWord(sentence[i]) << " "; if(out) output getWord(sentence[i]) << " "; } cout << endl; if(out) output << endl; if (len + at least one word continue; for (int i = 1; i < len; ++i) { int start = std::max(0, i - order_ + 1); if (getcounts_) { // return counts if((i-start+1) < order_) continue; for(int j = 0; j < i-start+1; j++) { cout getWord(sentence[start+j]) << " "; if(out) output getWord(sentence[start+j]) << " "; } cout << ": " getCount(&sentence[start], i - start + 1) << std::endl; if(out) output << ": " getCount(&sentence[start], i - start + 1) << std::endl; } else { // return probs if((i-start+1) < order_) continue; for(int j = 0; j < i-start+1; j++) { coutgetWord(sentence[start+j]) << " "; if(out) output getWord(sentence[start+j]) << " "; } cout << ": " getProb(&sentence[start], i - start + 1, &found) << std::endl; if(out) output << ": " getProb(&sentence[start], i - start + 1, &found) << std::endl; } ++counter; } cout << endl; if(out) output << endl; sentenceNo++; } // query as ngrams } else { while (test_data_->nextSentence(&sentence[0], &len)) { assert(len <= order_); for(int j = 0; j < len; j++) { cout getWord(sentence[j]) << " "; output getWord(sentence[j]) << " "; } cout << ": "; if(out) output << ": "; if (getcounts_) { // return counts cout getCount(&sentence[0], len) << std::endl; if(out) output getCount(&sentence[0], len) << std::endl; } else { // return probs cout getProb(&sentence[0], len, &found) << std::endl; if(out) output getProb(&sentence[0], len, &found) << std::endl; } ++counter; } } output.close(); std::cerr << "Time elapsed: " << (clock() - start)/CLOCKS_PER_SEC << std::endl; return true; }// end query // Load LM bool GenStats::load() { assert(randlm_ == NULL); // read and trim path string lmpath = inParam[1]; RandLMUtils::trim(lmpath); // load RandLMFile fin(lmpath, std::ios::in); RandLMInfo* info = new RandLMInfo(&fin); randlm_ = RandLM::initRandLM(info, &fin, 1); info = NULL; assert(randlm_ != NULL); std::cerr << "Loaded RandLM." << std::endl; // read LM's order order_ = randlm_->getOrder(); return true; }// end load // check and format test info vector GenStats::formatTestInfo(string in) { // return vector 'fail' if input not valid vector arr, fail; string info = in; fail.push_back(" "); // at least 2 params if(info.find(":") == string::npos) return fail; // write output to file or not ? if(info.find(">") != string::npos) { vector tmp; Tokenize(info, tmp, ">"); if(tmp.size() == 2) { outputFile = tmp[1]; RandLMUtils::trim(outputFile); info = tmp[0]; } else { return fail; } } // test valid params Tokenize(info, arr); for(int i = 0; i< arr.size(); i++) RandLMUtils::trim(arr[i]); if(arr.size() != 2 && arr.size() != 3) return fail; if( arr[1] != "corpus" && arr[1] != "ngrams" && arr[1] != "c" && arr[1] != "n") return fail; if(arr.size() == 3) if( arr[2] != "1" && arr[2] != "0" && arr[2] != "true" && arr[2] != "false") return fail; // all params are valid, return formatted info vector return arr; }// end formatTestInfo bool GenStats::setTestInfo(vector testInfo) { // if corpus data then add symbols string test_type = testInfo[1]; if(test_type == "c") test_type = "corpus"; if(test_type == "n") test_type = "ngrams"; corpus_data_ = test_type == InputData::kCorpusFileType; vocab = randlm_->getVocab(); assert(vocab != NULL); test_data_ = new TestCorpus(testInfo[0], vocab, order_, corpus_data_); assert(test_data_ != NULL); // return only counts or smoothed probs getcounts_ = (testInfo.size() == 3) ? (RandLMUtils::StringToBool(testInfo[2])) : false; // if return counts, cast RandLM into CountRandLM if (getcounts_) { count_randlm_ = dynamic_cast(randlm_); assert(count_randlm_ != NULL); } }// end setTestInfo }// end GenStatsMain.cpp #include #include using namespace std; #include "genstats.h" using namespace randlm; int main(int argc, char ** argv) { // init genstats, load LM into RAM GenStats genstats(argc, argv); string testInfo = ""; vector infoArr; cout << endl << "GENERATE STATS (counts, probabilities)" << endl; cout :\ [:]" << endl; cout << "Example: test1:corpus:true" << endl; cout << "Type 'quit' or 'exit' to stop program." << endl; do { do{ infoArr.clear(); cout << "Info of test: "; getline(cin, testInfo); if(testInfo != "exit" && testInfo != "quit") // validate user's input infoArr = genstats.formatTestInfo(testInfo); else break; }while(infoArr.size() <= 1); // quit if(testInfo == "exit" || testInfo == "quit") break; // set test info genstats.setTestInfo(infoArr); // process queries assert(genstats.query()); }while(1); return 0; } Tài liệu tham khảo Tiếng Việt: [1] Nguyễn Văn Vinh. “Xây dựng chương trình dịch tự động Anh-Việt bằng phương pháp dịch thống kê”. Luận văn Thạc sĩ, Đại học Công nghệ, ĐHQGHN, 2005. Tiếng Anh: [2] Algoet, P. H. and Cover, T. M.. “A sandwich proof of the Shannon-McMillan-Breiman Theorem”. The Annals of Probability, 1988, 16(2): pages 899-909. [3] Bahl, L. R., Baker J. K., Jelinek F. and Mercer R. L.. “Perplexity - a measure of the difficulty of speech recognition tasks”. Acoustical Society of America Journal 62, 1977, pages 63–66. [4] Bloom, B. H.. “Space/time trade-offs in hash coding with allowable errors”. Commun. ACM, 1970. [5] Brants, T., Popat, A. C., Xu, P., Och, F. J., and Dean, J.. “Large language models in machine translation”. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), 2007, pages 858–867. [6] Broder, A. and Mitzenmacher, M., “Network applications of bloom filters: A survey”. In In Proc. of Allerton Conference, 2002. [7] Brown P. F., Cocke J., Della Pietra V., Della Pietra S., Jelinek F., Lafferty J. D., Mercer R. L., and Roossin P. S.. “A statistical approach to machine translation”. Computational Linguistics, 1990, 6(2): pages 79–85. [8] Brown et al. “The Mathematics of Statistical Machine Translation: Parameter Estimation”. Computational Linguistics, 19(2), 1993. [9] Callison-Burch, Chris, Miles Osborne, and Philipp Koehn. “Re-evaluating the role of Bleu in machine translation research”. In EACL 2006: Proceedings the Eleventh Conference of the European Chapter of the Association for Computational Linguistics, 2006. [10] Chazelle, B., Kilian, J., Rubinfeld, R., and Tal, A.. “The bloomier filter: an efficient data structure for static support lookup tables”. In SODA ’04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, 2004, pages 30–39. [11] Chen, S. and Goodman, J.. “An empirical study of smoothing tech-niques for language modeling”. Computer Speech & Language, 1999, 13: pages 359–393(35). [12] Costa, L. H. M. K., Fdida, S., and Duarte, O. C. M. B. “Incremental service deployment using the hop-by-hop multicast routing protocol”. IEEE/ACM Trans. Netw., 2006, 14(3): pages 543–556. [13] de Laplace, M.. “A Philosophical Essay on Probabilities”. Dover Publications, 1996. [14] Fallis, D.. “The reliability of randomized algorithms”. Br J Philos Sci, 2000, 51(2): pages 255-271. [15] Galley M. and Manning C. D.. “A simple and effective hierarchical phrase reordering model”. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Honolulu, Hawaii, October. Association for Computational Linguistics, 2008, pages 848–856. [16] Golin, M., Raman, R., Schwarz, C., Smid, M., and C, S. J. C.. “Randomized data structures for the dynamic closest-pair problem”. In In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, 1993, pages 301-310. [17] Kneser, R. and Ney, H., “Improved backing-off for m-gram language modelling”. In Proceedings of the IEEE Conference on Acoustics, Speech and Signal Processing, 1995, volume 1, pages 181–184. [18] Koehn, P.. “Europarl: A multilingual corpus for evaluation of machine translation”, 2003. Available at ˜koehn/publications/europarl.ps. [19] Koehn, P.. “Empirical Methods in Natural Language Processing”. From course slides at 2007. [20] Koehn, P. and Chris Callison-Burch. “Introduction to statistical machine translation”. ESSLLI 2005 tutorial, 2005. [21] Koehn, P. and Hoang, H.. “Factored translation models”. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), 2007, pages 868–876. [22] Koehn, P., Och, F. J., and Marcu, D.. “Statistical phrase-based translation”. In NAACL ’03: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, Morristown, NJ, USA. Association for Computational Linguistics, 2003, pages 48–54. [23] Le Khanh Hung. “One method of interlingual translation”. In National Conference on IT Research, Development and Applications of ICT, 2003. [24] Levenberg, A. D. “Bloom filter and lossy dictionary based language models”. Dissertation, master of science, School of Informatics, University of Edinburgh, 2007. [25] Manning, C. D. and Sch¨utze, H.. “Foundations of Statistical Natural Language Processing”. The M.I.T. Press. Massachusetts, 1999. [26] Masao Utiyama. “A survey of statistical machine translation”. Lecture slides, Kyoto University, 2006. [27] Och, F. J.. “Minimum error rate training in statistical machine translation”. In ACL ’03: Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, Morristown, NJ, USA. Association of Computational Linguistics, 2003, pages 160–167. [28] Och, F. “The Google Statistical Machine Translation System for the 2005 NIST MT Evaluation”. Oral presentation at the 2005 NIST MT Evaluation workshop, 2005. [29] Och F.J. and Hermann Ney. “Improved statistical alignment models”. In Proceedings of ACL, 2000. [30] Pagh, A., Pagh, R., and Rao, S. S.. “An optimal bloom filter replacement”. In SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, 2005, pages 823–829. [31] Pagh, R. and Rodler, F. F., “Lossy dictionaries”. In ESA ’01: Proceedings of the 9th Annual European Symposium on Algorithms, London, UK. Springer-Verlag, 2001, pages 300–311. [32] Papineni K., S. Roukos, T. Ward, and W. J. Zhu. “Bleu: a method for automatic evaluation of machine translation”. In Proc. of the 40th Annual Meeting of the Association for Computational Linguistics (ACL), Philadelphia, PA, July, 2002, pages 311–318. [33] Pugh, W.. “Skip lists: A probabilistic alternative to balanced trees”. Commun. ACM, 1990, 33(6): pages 668-676. [34] Stolcke, A., “Srilm – an extensible language modeling toolkit”. In Proc. Intl. Conf. on Spoken Language Processing, 2002. [35] Talbot, D. and Osborne, M., “Randomised language modelling for statistical machine translation”. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, Prague, Czech Republic. Association for Computational Linguistics, 2007a, pages 512–519. [36] Talbot, D. and Osborne, M., “Smoothed Bloom filter language models: Tera-scale LMs on the cheap”. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), 2007b, pages 468–476. [37] Talbot, D. and Talbot, J.. “Bloom maps”. In Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Society for Industrial and Applied Mathematics, 2008. [38] Tillmann C.. “A unigram orientation model for statistical machine translation”. In Daniel Marcu Susan Dumais and SalimRoukos, editors, Proceedings of HLT-NAACL 2004: Short Papers, Boston, Massachusetts, USA, May 2 - May 7. Association for Computational Linguistics, 2004, pages 101–104. [39] To Hong Thang. “Building language model for Vietnamese and its application”. Dissertation, Bachelor of IT, College of Technology, Vietnam National University, 2008.