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

hấn mạnh từ “coi” và “chắc chắn” ? Đó là vì các phần tử thực sự của tập S thì luôn được xác định chính xác, nhưng có một xác suất lỗi false positive sẽ xuất hiện nếu như k bit tương ứng thực ra được thiết lập do các phần tử trong tập huấn luyện mà phần tử đang xét thì không thuộc tập này. Đây được gọi là lỗi-một-phía. Cần chú ý là, thay vì thực sự lưu trữ tập S, sử dụng Bloom Filter, thực chất chúng ta chỉ đang lưu trữ một đại diện của nó – B, một mảng bit cỡ m. Các phần tử trong S do đó thực chất bị mất: chúng ta sẽ không thể khôi phục được tập đó từ Bloom Filter. Tuy nhiên, nếu chúng ta chỉ quan tâm đến liệu một phần tử có nằm trong tập S hay không thì Bloom Filter lại có thể thực hiện được, đồng thời tiết kiệm đáng kể bộ nhớ trong khi tốc độ truy vấn lại không đổi. Một ưu điểm đáng chú ý nữa của Bloom Filter, như được trình bày sau đây, đó là mặc dù không thể tránh khỏi, nhưng lỗi-một-phía của Bloom Filter lại là yếu tố mà ta có thể kiểm soát được. Hình 6: Lỗi-một-phía trong Bloom Filter Nếu chúng ta coi các hàm băm có phân phối đều và hoàn toàn ngẫu nhiên, tức là chúng sẽ chọn các vị trí trong mảng m-bit với xác suất tương đương nhau thì xác suất một bit bất kỳ được thiết lập bằng 1 bởi một hàm băm là 1/m. Xác suất một bit bất kỳ không phải là 1 sau khi thực hiện một hàm băm là: Xác suất một bit vẫn là 0 sau khi mới chỉ có một phần tử chạy qua k hàm băm là: Xác suất một bit vẫn là 0 sau quá trình huấn luyện: Như vậy sau quá trình huấn luyện, xác suất một bit xác định nào đó có giá trị bằng 1 là: Biểu đồ 1: Tỉ lệ lỗi và Không gian lưu trữ (giữ nguyên n) [24] Biểu đồ 2: Tỉ lệ lỗi và Số lượng khóa (giữ nguyên m) [24] Nếu một phần tử nào đó không phải là thành viên của tập S, xác suất nó lúc nào cũng trỏ tới những bit bằng 1 đối với tất cả k hàm băm nó được chạy qua, gây ra lỗi false positive, là: Sử dụng giới hạn của cơ số logarit tự nhiên, công thức trên tương đương: Để xác suất lỗi là nhỏ nhất, từ công thức trên ta lấy đạo hàm thì sẽ tính được số hàm băm k tối ưu là: tức là một nửa số bit của mảng BF nên được thiết lập giá trị bằng 1 sau quá trình huấn luyện. Điều này sẽ dẫn đến xác suất lỗi false positive là: Như vậy là nếu giữ nguyên n, xác suất lỗi giảm nếu m tăng (sử dụng nhiều không gian lưu trữ hơn). Còn nếu m không đổi thì tỉ lệ lỗi tăng nếu n tăng. Hai biểu đồ 1 và 2 có thể chỉ ra sự tương quan giữa tỉ lệ lỗi với không gian lưu trữ, và số lượng khóa (số phần tử trong tập S). Cấu trúc của Bloom Filter không cho phép liệt kê hoặc lấy giá trị các phần tử lưu trong đó một cách trực tiếp. Ta cũng không thể loại bỏ một đối tượng khỏi Bloom Filter mà không làm hỏng các phần tử khác. Thế nhưng BF vẫn là một trong những cấu trúc dữ liệu xác suất được sử dụng rộng rãi trong NLP do sự đơn giản và hiệu quả của nó. Các ứng dụng của BF có thể kể đến như trong kiểm tra chính tả, các ứng dụng cơ sở dữ liệu [12] và định tuyến mạng [6]. Mô hình ngôn ngữ sử dụng Bloom Filter Năm 2007, Talbot và Osborne lần đầu tiên giới thiệu phương pháp sử dụng một cấu trúc lưu trữ dữ liệu có mất mát như BF để mô hình ngôn ngữ, và cũng đưa ra ý tưởng giúp giảm tỉ lệ lỗi false positive, tích hợp cả khóa và giá trị trong Bloom Filter với việc công bố hai cấu trúc dữ liệu Log Frequency Bloom Filter [35, 36] và Bloom Map [37]. Bloom Filter tần số log (Log-frequency Bloom Filter) Khả năng lưu trữ hiệu quả dữ liệu thống kê n-gram vào trong BF có được là do phân phối dạng Zipf (luật Zipf) Tham khảo thêm trên Wikipedia: ’s_law của các từ trong một ngữ liệu ngôn ngữ tự nhiên. Theo luật này, thì trong một ngữ liệu thông thường, từ xảy ra thường xuyên nhất nhiều gấp đôi từ xảy ra thường xuyên thứ hai, từ này lại nhiều bằng hai lần từ xảy ra thường xuyên thứ tư, … Lấy ví dụ đối với ngữ liệu Brown, “the” là từ xảy ra nhiều nhất, chiếm 7% tổng số từ. Đúng theo luật Zipf, từ có số lượng xếp thứ hai là “of” chiếm khoảng trên 3.5% một chút. Và chỉ cần khoảng 135 từ là đã chiếm một nửa tổng số từ của ngữ liệu Brown (theo Wikipedia). Như vậy tức là chỉ có một số ít sự kiện xảy ra thường xuyên trong khi hầu hết các sự kiện khác đều hiếm khi xảy ra. Để biến BF thành một cấu trúc dữ liệu hỗ trợ lưu trữ cặp khóa – giá trị, với khóa là n-gram còn giá trị là số lần xuất hiện n-gram trong ngữ liệu. Nhằm tối thiểu hóa số bit cần sử dụng, một thuật toán có tên mã hóa tần số log (log-frequency encoding) được sử dụng. Số lần xuất hiện của các n-gram c(x) trước tiên được lượng tử hóa thành qc(x) sử dụng công thức: Điều này có nghĩa là tần suất xuất hiện của các n-gram sẽ bị suy giảm theo hàm mũ khi sử dụng quy trình mã hóa tần số log. Tuy nhiên do có sự khác biệt lớn trong phân phối của các sự kiện này nên tỉ lệ của mô hình vẫn được lưu giữ gần như nguyên vẹn trong BF-LM. Kích thước khoảng giá trị qc(x) được quyết định bởi cơ số b trong công thức trên. Từng n-gram được lưu trữ vào trong BF cùng với giá trị qc(x) được biểu diễn bằng một số nguyên j tăng từ 1 đến qc(x). Đến giai đoạn kiểm tra thì tần suất của một n-gram được lấy ra bằng cách đếm tăng dần lên bắt đầu từ 1. Với mỗi loạt k hàm băm có kết quả trỏ tới các giá trị bằng 1 trong mảng bit BF, thì giá trị của n-gram lại được tăng thêm 1 đơn vị. Quá trình này tiếp diễn cho đến khi một hàm băm nào đó trỏ đến bit 0 trong mảng hoặc đạt đến giá trị đếm tối đa. Và khi đó giá trị đếm hiện tại trừ đi một được trả lại, chính là cận trên của qc(x) n-gram đó. Đối với hầu hết các n-gram thì quá trình này chỉ diễn ra một hoặc hai lần nhờ có quy trình mã hóa tần số log. Đặc tính lỗi-một-phía của Bloom Filter đảm bảo rằng giá trị lượng tử hóa qc(x) không thể lớn hơn giá trị được trả lại này. Quá trình huấn luyện và kiểm tra được minh họa qua Thuật toán 1 và Thuật toán 2 [35]. Thuật toán 1: Thuật toán huấn luyện BF Đầu vào:, và Đầu ra: Bloom Filter for all x in do c(x) = tần suất của n-gram x in qc(x) = giá trị lượng tử hóa của c(x) for j = 1 to qc(x) do for i = 1 to k do hi(x) = giá trị băm của sự kiện {x, j} với hi BF[hi(x)] = 1 end for end for end for return BF Thuật toán 2: Thuật toán kiểm tra BF Đầu vào: x, MAXQCOUNT, và BF Đầu ra: Cận trên của giá trị c(x) trong for j = 1 to MAXQCOUNT do for i = 1 to k do hi(x) = giá trị băm của sự kiện {x, j} với hi if BF[hi(x)] = 0 then return E[c(x) | qc(x) = j] end if end for end for Số lần xuất hiện của n-gram sau đó được ước lượng sử dụng công thức: tiếp theo một thuật toán làm mịn sẽ được sử dụng để lấy ra lượng xác suất thực tế sẽ sử dụng trong tính toán [36]. Bộ lọc dựa vào chuỗi con Các mô hình ngôn ngữ n-gram chuẩn lưu trữ xác suất điều kiện của n-gram trong một ngữ cảnh cụ thể. Hầu hết các mô hình ngôn ngữ 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