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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thạc Huy TÌM HIỂU MÔ HÌNH NGÔN NGỮ SỬ DỤNG PHƯƠNG PHÁP BLOOM FILTER KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thạc Huy TÌM HIỂU MÔ HÌNH NGÔN NGỮ SỬ DỤNG PHƯƠNG PHÁP BLOOM FILTER KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Văn Vinh HÀ NỘI - 2010 Tóm tắt nội dung Mô hình ngôn ngữ là một thành phần quan trọng trong các ứng dụng như nhận dạng tiếng nói, phân đoạn từ, dịch thống kê, … Và chúng thường được mô hình hóa sử dụng các n-gram. Trong khóa luậ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 hai kiểu cấu trúc dữ liệu dựa trên Bloom Filter là Log-Frequency Bloom Filter và 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 [21]. Mục lục TÓM TẮT NỘI DUNG i MỤC LỤC ii LỜI CẢM ƠN iv DANH MỤC TỪ VIẾT TẮT v DANH MỤC HÌNH vi MỞ ĐẦU 1 CHƯƠNG 1 - Tổng quan về mô hình ngôn ngữ 3 1.1 N-gram 3 1.2 Xây dựng mô hình ngôn ngữ 4 1.2.1 Ước lượng cực đại hóa khả năng (MLE) 5 1.2.2 Các phương pháp làm mịn 5 1.2.2.1 Kneser-Ney 7 1.2.2.2 Kneser-Ney cải tiến (Modified Kneser-Ney) 8 1.2.2.3 Stupid Backoff 9 1.3 Đánh giá mô hình ngôn ngữ 10 1.3.1 Perplexity 10 1.3.2 MSE 11 CHƯƠNG 2 - Các cấu trúc dữ liệu dựa trên Bloom Filter 13 2.1 Các cấu trúc dữ liệu xác suất (PDS) 14 2.2 Hàm băm 16 2.3 Bloom Filter cơ bản 17 2.4 Mô hình ngôn ngữ sử dụng Bloom Filter 22 2.4.1 Bloom Filter tần số log 23 2.4.2 Bộ lọc dựa vào chuỗi con 25 2.4.3 Bloom Map 26 CHƯƠNG 3 - Thử nghiệm: Xây dựng LM với RandLM và SRILM 32 3.1 Ngữ liệu 33 3.2 Thuật toán làm mịn 35 3.3 Xây dựng LM với SRILM và RandLM 35 CHƯƠNG 4 - Thử nghiệm: Dịch máy thống kê với Moses 40 4.1 Dịch máy thống kê 40 4.1.1 Giới thiệu về dịch máy thống kê 40 4.1.2 Dịch máy thống kê dựa trên cụm 43 4.1.3 Điểm BLEU 45 4.2 Baseline System 46 4.3 Ngữ liệu 46 4.4 Kết quả thử nghiệm 48 KẾT LUẬN 50 PHỤ LỤC 51 Lời cảm ơn Trước tiên, tôi muốn gửi lời cảm ơn chân thành tới giảng viên, TS. Nguyễn Văn Vinh, cảm ơn sự chỉ bảo tận tình của thầy trong suốt thời gian hướng dẫn tôi thực tập chuyên ngành và nghiên cứu khóa luận này. Tôi cũng xin cảm ơn anh Tống Tùng Khánh và anh Vương Hoài Thu trong nhóm Digital Content Solution ở Công ty cổ phần tin học Lạc Việt, hai anh đã nhiệt tình giúp đỡ tôi với đề tài này và đóng góp nhiều ý kiến quý báu để khóa luận được hoàn thiện hơn. Nếu không có sự hướng dẫn của thầy và các anh, tôi đã không thể hoàn thành được khóa luận này. Sự động viên, khích lệ của bố mẹ, anh chị tôi là nguồn động lực, nguồn hỗ trợ lớn lao. Và tôi cũng rất cảm ơn tất cả những người bạn đại học đã cùng chia sẻ quãng thời gian ý nghĩa của đời sinh viên dưới mái trường Đại học Công nghệ - ĐHQGHN. Chúc các bạn có kết quả tốt nghiệp tốt và thành công trong cuộc sống. Danh mục từ 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ê Danh mục hình Hình 1: Mô hình Markov bậc 2 4 Hình 2: Ví dụ về hàm băm 16 Hình 3: Ví dụ về bảng băm. Xung đột trong bảng băm 17 Hình 4: Huấn luyện Bloom Filter 18 Hình 5: Truy vấn Bloom Filter 19 Hình 6: Lỗi-một-phía trong Bloom Filter 20 Hình 7: Tăng kích cỡ LM cải thiện điểm BLEU 42 Hình 8: Kiến trúc của một hệ thống SMT 43 Hình 9: Minh họa dịch máy thống kê dựa vào cụm 43 Mở đầu Mô hình ngôn ngữ (Language Model - LM) là một thành phần quan trọng trong nhiều ứng dụng như dịch máy, nhận dạng tiếng nói, … Các LM luôn cố gắng mô phỏng ngôn ngữ tự nhiên một cách chính xác nhất. Từ nhiều nghiên cứu và thử nghiệm [19, 28], chúng ta có thể thấy rằng mô hình ngôn ngữ với ngữ liệu càng lớn, bậc càng cao thì mô phỏng càng chính xác. Trước đây việc xây dựng các ngữ liệu lớn rất khó khăn. Nhưng với sự bùng nổ của Internet như hiện nay, khối lượng thông tin sẵn có là vô cùng lớn. Sẽ thật là lãng phí nếu như chúng ta không tận dụng kho ngữ liệu khổng lồ này. Do đó trong những năm gần đây, kích thước các tập ngữ liệu dùng để huấn luyện LM đã phát triển đáng kinh ngạc, chúng lớn đến mức không còn có thể lưu trữ được trong bộ nhớ của những siêu máy tính với nhiều Gigabytes bộ nhớ RAM. Điều này khiến cho nỗ lực mô phỏng chính xác hơn ngôn ngữ tự nhiên bằng cách sử dụng các ngữ liệu lớn với kiểu mô hình truyền thống trở nên vô nghĩa, vì cần phải cắt giảm kích cỡ của ngữ liệu để LM có thể được chứa vừa trong bộ nhớ máy tính. Điều này đi ngược lại với mục đích ban đầu của việc tạo ra những tập ngữ liệu ngày càng lớn hơn. Hạn chế này đòi hỏi các nhà nghiên cứu cần tìm ra những phương pháp khác để mô hình hóa ngôn ngữ nếu vẫn muốn tận dụng lợi thế mà các bộ ngữ liệu lớn mang lại. Một giải pháp để thực hiện yêu cầu này là bỏ đi sự chính xác, chấp nhận mất mát một lượng thông tin nhất định khi mô hình ngôn ngữ từ ngữ liệu. Nghĩa là thay vì các LM không mất mát (losses LM), ta sử dụng các LM có mất mát thông tin (lossy LM). Các nghiên cứu về lossy LM tạo ra một lớp các loại cấu trúc dữ liệu mới là Cấu trúc dữ liệu ngẫu nhiên (Randomized Data Structure, viết tắt là RDS), hay còn gọi là Cấu trúc dữ liệu xác suất (Probabilistic Data Structure - PDS). Vài cấu trúc dữ liệu điển hình loại này là Skip List [33], Sparse Partition [16], Lossy Dictionary [31], Bloom Filter [4]. Ở Việt Nam cũng đã có một số nghiên cứu về vấn đề mô hình ngôn ngữ [39], nhưng mới chỉ dừng lại ở việc sử dụng các mô hình ngôn ngữ chuẩn. Khóa luận này nghiên cứu và tìm hiểu về mô hình ngôn ngữ dựa trên Bloom Filter do những cải tiến đáng chú ý những năm gần đây của loại cấu trúc dữ liệu này để xây dựng mô hình ngôn ngữ [35, 36, 37]. Nội dung khóa luận tập trung nghiên cứu khả năng tiết kiệm bộ nhớ, không gian lưu trữ của loại LM này và hiệu quả của nó, so với các LM tiêu chuẩn [34], thông qua một ứng dụng cụ thể là hệ thống dịch máy thống kê Moses. Chương 1 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ữ. Chương 2 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 và Bloom Map. Chương 3 thử nghiệm xây dựng mô hình ngôn ngữ trên một ngữ liệu tiếng Anh và một ngữ liệu tiếng Việt.. Chương 4 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 nguồn mở Moses sử dụng các mô hình ngôn ngữ xây dựng ở chương 3. Chương 1 Tổng quan về mô hình ngôn ngữ Mô hình ngôn ngữ (Language Model - LM) là các phân phối xác suất trên một ngữ liệu đơn ngữ, được sử dụng trong nhiều bài toán khác nhau của xử lý ngôn ngữ tự nhiên, ví dụ như: dịch máy bằng phương pháp thống kê, nhận dạng giọng nói, nhận dạng chữ viết tay, sửa lỗi chính tả, … Thực chất, LM là một hàm chức năng có đầu vào là một chuỗi các từ và đầu ra là điểm đánh giá xác suất một người bản ngữ có thể nói chuỗi đó. Chính vì vậy, một mô hình ngôn ngữ tốt sẽ đánh giá các câu đúng ngữ pháp, trôi chảy cao hơn một chuỗi các từ có thứ tự ngẫu nhiên, như trong ví dụ sau: Pr(“hôm nay trời nắng”) > Pr(“trời nắng nay hôm”) N-gram Cách thông dụng nhất được dùng để mô hình hóa ngôn ngữ vào trong LM là thông qua các n-gram. Với mô hình n-gram, chúng ta coi một văn bản, đoạn văn bản là chuỗi các từ liền kề nhau, w1, w2, …, wN-1, wN, và sau đó phân tích xác suất của chuỗi với công thức xác suất kết hợp: và do vậy mỗi từ sẽ liên quan có điều kiện tới toàn bộ các từ trước nó (ta sẽ gọi đây là lịch sử của sự kiện hoặc từ đó). Tuy nhiên, việc sử dụng toàn bộ các từ trước đó để đoán nhận từ tiếp theo là không thể thực hiện được vì 2 nguyên nhân sau. Đầu tiên là phương pháp này không khả thi về mặt tính toán do tốn quá nhiều thời gian, tài nguyên hệ thống cho mỗi lần dự đoán. Hai là, trong rất nhiều trường hợp, chỉ sau khi duyệt vài từ trong lịch sử, ta đã nhận thấy rằng đó là một câu chưa từng gặp trước đây. Bởi vậy kể cả khi đã biết toàn bộ lịch sử của một từ, xác suất của nó vẫn có thể là không biết. Thay vào đó, các mô hình ngôn ngữ thường ước lượng tương đối xác suất dựa trên giả định Markov (hay mô hình Markov ẩn), rằng từ tiếp theo chỉ chịu ảnh hưởng từ một vài từ trước đó [25]. Một mô hình Markov bậc n giả định rằng chỉ n từ trước đó có liên hệ ngữ cảnh với từ đang cần xác định. Việc quyết định bao nhiêu từ trước đó mà LM quan tâm được gọi là bậc n (order) của LM, và thường được gọi là 1-gram (unigram), 2-gram (bigram), 3-gram (trigram), 4-gram (fourgram) tương ứng với các mô hình Markov bậc một, hai, ba, bốn. Ví dụ, nếu chúng ta muốn ước 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 đó: wi-3 wi-2 wi-1 wi wi+1 Hình 1: Mô hình Markov bậc 2 Một cách tổng quát, gọi là một n-gram chiều dài n kết thúc bằng từ wi. Khi đó để ước lượng xác suất n-gram cho một chuỗi chiều dài N ta sử dụng công thức: Xây dựng mô hình ngôn ngữ Để xây dựng (huấn luyện) một mô hình ngôn ngữ ta cần một ngữ liệu đơn ngữ (corpus) có kích thước tương đối và một bộ ước lượng thống kê có nhiệm vụ mô hình hóa lượng xác suất của ngữ liệu. Các bộ ước lượng được mà LM sử dụng, theo những cách khác nhau, đều cần đến tần suất của các n-gram, do đó chúng ta cần phải đếm số lần xuất hiện của các n-gram từ 1-gram cho đến số bậc mô hình chúng ta đang huấn luyện. Ước lượng cực đại hóa khả năng (MLE) Chúng ta có thể sử dụng kết quả đếm các n-gram để xây dựng một mô hình ước lượng cực đại hóa khả năng (Maximium Likelihood Estimation - MLE) với tần suất tương đối của các n-gram trong ngữ liệu. Với MLE, xác suất một unigram nhất định nào đó sẽ xuất hiện tiếp theo đơn giản là tần suất nó xuất hiện trong ngữ liệu. trong đó c(wi’) = |wi’| chính là số lần xuất hiện của từ wi’ trong ngữ liệu. Phương pháp này được gọi như vậy bởi vì nó cực đại hóa giá trị đầu ra để mô hình hóa ngữ liệu huấn luyện. Ví dụ, trong ngữ liệu Brown , một ngữ liệu với một triệu từ, từ khóa “Chinese” xuất hiện 400 lần. Vậy thì xác suất mà một mô hình ngôn ngữ dùng MLE sẽ gán cho unigram “Chinese” là . Xác suất điều kiện của một n-gram tổng quát với bậc > 1 là: tức là tần suất một từ nào đó thường xuyên xuất hiện sau lịch sử có bậc n – 1. Để minh họa, ta tiếp tục ví dụ trên, xác suất bigram “Chinese food” xuất hiện là số lần từ “food” xuất hiện sau từ “Chinese” chia cho c(Chinese) = 400. Trong ngữ liệu Brown, cụm từ “Chinese food” xuất hiện 120 lần, nên: PrMLE(food|Chinese) = 0.3 Các phương pháp làm mịn Tuy MLE là một phương pháp dễ hiểu, dễ sử dụng để ước lượng xác suất cho mô hình, nhưng trong thực tế ta gặp phải vấn đề dữ liệu thưa (data sparseness problem). Tức là tập ngữ liệu dùng để xây dựng LM dù lớn đến mấy, cũng chỉ là tập hữu hạn các câu trong vô số câu có thể của một ngôn ngữ tự nhiên. Do đó một LM chỉ sử dụng MLE sẽ gán xác suất bằng 0 cho nhiều n-gram tốt. Để giảm thiểu vấn đề này, người ta thường không sử dụng MLE mà thay vào đó là các phương pháp ước lượng xác suất thống kê phức tạp hơn. Các phương pháp này được gọi là làm mịn (smoothing) hay trừ hao (discounting), khi mà một phần xác suất từ các sự kiện trong mô hình sẽ được dành cho những sự kiện chưa từng xuất hiện. Việc lấy từ cái gì và trừ hao như thế nào là một đề tài vẫn đang được nghiên cứu nhiều. Ví dụ, cách cổ điển nhất của làm mịn là phương pháp Add-one smoothing [13], trong phương pháp này, ta thêm một lượng vào kết quả đếm số lần xuất hiện của mọi từ vựng trong ngữ liệu. Hai khái niệm quan trọng được sử dụng trong quá trình làm mịn các mô hình ngôn ngữ là backoff và interpolation. Khi LM gặp một n-gram chưa biết, việc tính xác suất sẽ sử dụng thông tin từ (n-1)-gram, nếu sự kiện (n-1)-gram cũng chưa từng xuất hiện trong quá trình huấn luyện thì LM lại sử dụng thông tin xác suất từ (n-2)-gram, … Và cứ tiếp tục như vậy cho đến khi tính được xác suất của n-gram. Quá trình này được gọi là backoff và được định nghĩa như sau: Trong đó là hệ số trừ hao dựa trên tần suất xuất hiện của trong lịch sử và là tham số backoff. Khi số lượng từ vựng đủ lớn, chúng ta có thể sẽ cần gán xác suất bằng 0 cho một số từ ngoài từ điển (out of vocabulary - OOV) khi ở mức unigram. Chẳng hạn khi ta có một cuốn từ điển chuyên ngành và không muốn chia sẻ lượng xác suất của các từ vựng đó (các danh từ chung, các số thực đặc biệt, …) cho các OOV. Một cách khác là chúng ta làm mịn LM và dành một lượng xác suất nhỏ gán cho các OOV khi ở mức unigram. Phương pháp Interpolation kết hợp thông tin thống kê n-gram qua tất cả các bậc của LM. Nếu bậc của LM là n thì công thức đệ quy interpolation như sau: Trong đó là trọng số quyết định bậc nào của LM có ảnh hưởng lớn nhất đến giá trị đầu ra. Tổng trọng số được sử dụng cho tất cả các bậc n-gram bằng một. Có nhiều cách để xác định giá trị cho các trọng số này, đối với phương pháp interpolation đơn giản thì các giá trị này giảm theo số bậc n-gram. Tuy nhiên thường thì chúng sẽ được tính toán tùy theo điều kiện ngữ cảnh cụ thể, tức là theo tần suất của các bậc n-gram trong lịch sử. Các trọng số này không được tính toán từ dữ liệu huấn luyện, mà sử dụng tập dữ liệu held-out riêng biệt – tập này chỉ được dùng để huấn luyện các tham số, mà trong trường hợp này là các giá trị . Cần phải nhận thấy rằng sự khác biệt cơ bản giữa hai phương pháp này là interpolation sử dụng thông tin từ các bậc thấp hơn ngay cả khi dữ liệu xác suất của n-gram cần tính đã khác 0; trong khi backoff thì lại chỉ tìm kiếm đến dữ liệu khác 0 gần nhất. Những tiểu mục tiếp theo trong phần này sẽ trình bày về một số phương pháp làm mịn phổ biến nhất hiện nay, như Kneser-Ney [17] hay Stupid backoff của Google [5]. Kneser-Ney Thuật toán làm mịn Kneser-Ney (KN) được phát triển bởi Reinhard Kneser và Hermann Ney, công bố năm 1995 [17]. Trong thuật toán KN, xác suất của một unigram không tỉ lệ thuận với tần suất xuất hiện của nó, mà với số tiền tố mà nó có. Có thể minh họa như sau, bigram “San Francisco” rất phổ biến trong cuốn sách “Lịch sử thành phố San Francisco”. Với tần suất bigram này cao như vậy thì nếu sử dụng các phương pháp đơn giản, tần suất của từng từ “San” và “Francisco” cũng sẽ phải rất cao. Tuy nhiên trong thuật toán KN thì xác suất Pr(Francisco) lại có thể là rất thấp, vì từ “Francisco” thường chỉ đứng sau từ “San”. Do các LM bậc thấp thường được sử dụng cho việc tính xác suất backoff của các LM bậc cao hơn, nên thuật toán KN muốn tận dụng sự lãng phí lượng xác suất này trong các thuật toán trước đó để dành cho các sự kiện có khả năng xảy ra lớn hơn. Trước tiên chúng ta định nghĩa số lượng tiền tố của một từ như sau: Thuật ngữ dùng để chỉ số lượng các từ xuất hiện một lần hoặc nhiều hơn và ký tự chỉ một từ bất kỳ nào đó. Thay vì sử dụng tần suất như trong MLE, tần suất thô của mỗi từ được thay thế bằng số lượng từ (khác nhau) đứng trước từ đó. Vậy thì xác suất của unigram trong thuật toán KN được tính là: tức là bằng số lượng tiền tố của từ wi chia cho tổng số tiền tố của tất cả các unigram trong ngữ liệu. Đối với các bậc cao hơn, xác suất này được tính như sau: trong đó tử số: và mẫu số là tổng số lượng tiền tố của tất cả các n-gram có cùng chiều dài . Mô hình đầy đủ của thuật toán KN được nội suy và có dạng như sau: với: là số lượng hậu tố (khác nhau) xuất hiện sau từ ; và D là tham số trừ hao. Kneser-Ney cải tiến (Modified Kneser-Ney) Thuật toán làm mịn Kneser-Ney cải tiến (Modified Kneser-Ney - MKN) được phát triển từ thuật toán KN, là kết quả nghiên cứu của Chen và Goodman, công bố năm 1999 [11], tức là 4 năm sau sự ra đời của thuật toán KN. Thuật toán KN dùng phương pháp trừ hao tuyệt đối (absolutely discounting), trừ đi một giá trị D duy nhất, 0 < D < 1, cho mọi kết quả đếm khác 0. Thuật toán MKN nâng cao hiệu quả của KN bằng cách sử dụng các giá trị trừ hao khác nhau trong những trường hợp khác nhau, dựa trên giá trị đếm của mỗi n-gram. Công thức tổng quát của MKN là: trong đó: và: với ni là tổng số n-gram có kết quả đếm là i của mô hình bậc n đang được nội suy. Tổng tất cả các phân phối phải bằng một, do đó: trong đó N2 và N3+ tương ứng đại diện cho số sự kiện có kết quả đếm là hai và ba hoặc nhiều hơn ba. Stupid Backoff Thuật toán Kneser-Ney và Kneser-ney cải tiến ở trên tuy hiệu quả trong thực tế nhưng việc tính toán lại khá phức tạp, khối lượng tính toán sẽ trở nên rất lớn khi dữ liệu nhiều, chẳng hạn như ngữ liệu n-gram Trillion Words của Google. Google sử dụng một thuật toán làm mịn đơn giản, tên là Stupid Backoff. Thuật toán này sử dụng tần suất tương đối của các n-gram một cách trực tiếp như sau: trong đó là một hằng số có giá trị bằng 0.4. Quá trình đệ quy kết thúc ngay khi đạt đến mức unigram: trong đó N là cỡ của ngữ liệu huấn luyện. Brants [5] đã tuyên bố rằng khi có lượng dữ liệu đủ lớn, thì hiệu quả của Stupid Backoff xấp xỉ làm mịn MKN. Lý do ở đây ký hiệu S được sử dụng thay cho P là để nhấn mạnh rằng phương pháp này trả lại điểm số tương đối chứ không phải là xác suất đã được chuẩn hóa. Đánh giá mô hình ngôn ngữ Perplexity Sau khi LM đã được huấn luyện, chúng ta cần phải đánh giá chất lượng của mô hình. Cách đánh giá chính xác nhất một mô hình ngôn ngữ là kiểm tra trong thực tế. Ví dụ trong nhận dạng tiếng nói, chúng ta có thể so sánh hiệu quả của 2 mô hình ngôn ngữ bằng cách chạy bộ nhận dạng ngôn ngữ 2 lần, mỗi lần với 1 mô hình và xem mô hình nào cho kết quả chính xác hơn. Nhưng cách này lại rất tốn thời gian, vì thế, chúng ta cần 1 công cụ mà có thể nhanh chóng đánh giá hiệu quả của một mô hình. Perplexity (PP) [3] là thước đo thường được dùng cho công việc này. Perplexity thực chất là một dạng biến đổi của entropy chéo (cross entropy) của mô hình. Entropy chéo là cận trên của entropy. Entropy là một khái niệm cơ bản trong Thuyết thông tin, đánh giá lượng thông tin của dữ liệu bằng độ đo sự không chắc chắn. Nếu một biến ngẫu nhiên x tồn tại trong khoảng X của thông tin đang được đánh giá với phân phối xác suất là p, thì khi đó entropy của x được định nghĩa là: Ví dụ khi tung một đồng xu, x chỉ có thể là mặt ngửa hoặc mặt sấp và xác suất trong cả hai trường hợp. Nhưng khi tung một hột xúc xắc 6 mặt, khoảng giá trị có thể của kết quả rộng hơn, và các xác suất là . Vì hành động tung xúc xắc có độ đo không chắc chắn lớn hơn, nên entropy của nó cũng cao hơn hành động tung đồng xu. Entropy chéo của một mô hình là độ đo thông tin giữa hai phân phối xác suất. Đối với một phân phối xác suất q nào đó mà chúng ta sử dụng để mô hình hóa phân phối xác suất p, entropy chéo được định nghĩa là: Định lý Shannon-McMillan-Breiman [3] chỉ ra rằng đối với cả entropy và entropy chéo chúng ta đều có thể bỏ đi thành phần p nếu chuỗi giá trị x đủ dài. Nếu chúng ta cần tính entropy cho từng từ thì chỉ việc chia cho tổng số từ: Perplexity được định nghĩa là . Do entropy chéo là cận trên của entropy, , chúng ta sử dụng entropy chéo trong Perplexity để không bao giờ đánh giá thấp entropy thực sự của mô hình. Perplexity của một mô hình được đánh giá trên tập kiểm tra. Trong thực tế, Perplexity là thước đo đầu tiên để đánh giá một mô hình ngôn ngữ, và có thể được coi là hàm của cả cả ngôn ngữ và mô hình. Trên phương diện là hàm của mô hình, nó đánh giá một mô hình mô phỏng ngôn ngữ chính xác đến mức độ nào. Còn trên phương diện là hàm của ngôn ngữ, nó đo tính phức tạp của ngôn ngữ. MSE Các mô hình LM có mất mát không đảm bảo xác suất chính xác vì nó lưu trữ dữ liệu không đầy đủ, do đó làm biến dạng phân phối xác suất thông thường. Chính vì lý do này mà ta không thể sử dụng các phương pháp đo dựa trên Entropy như Perplexity để đánh giá chất lượng của mô hình. Tuy nhiên chúng ta vẫn có thể sử dụng một mô hình đảm bảo phân phối xác suất thông thường làm chuẩn mực để so sánh xem các lossy LM khác biệt như thế nào so với mô hình này. Điều này có thể được thực hiện bằng cách sử dụng Lỗi trung bình bình phương (Mean Square Error - MSE) của lossy LM và lossless LM, đều được huấn luyện và kiếm tra sử dụng các tập ngữ liệu giống nhau. trong đó X là xác suất sự kiện i trong lossless LM và X’ là xác suất của cùng sự kiện đó trong lossy LM. Chương 2 Các cấu trúc dữ liệu dựa trên Bloom Filter Từ khi ra đời đến nay, việc mô hình ngôn ngữ đã có nhiều phát triển đáng kể cùng với các thuật toán làm mịn ngày càng tốt hơn [5]. Thế nhưng cũng có không ít thách thức mà LM phải đối mặt. Đó là làm thế nào tạo ra được mô hình đại diện hiệu quả ngôn ngữ tự nhiên, bằng cách sử dụng nhiều dữ liệu, tăng bậc mô hình n-gram (n = 6, 7, 8, …) nhưng không quá phức tạp trong tính toán và sử dụng ít bộ nhớ. Một tập ngữ liệu như của Google là quá lớn (24GB khi đã nén), không thể chứa vừa trong bộ nhớ RAM thông thường. Điều này thúc đẩy các nhà nghiên cứu cần tìm ra một giải pháp thay thế cách biểu diễn n-gram truyền thống, nếu vẫn muốn tận dụng ưu thế của các tập ngữ liệu lớn mà không cần sử dụng các phương thức tốn kém truyền thống như hệ thống siêu máy tính trong môi trường điện toán phân tán của Google. Trong chương này chúng ta sẽ tìm hiểu một loại cấu trúc dữ liệu có khả năng đáp ứng phần nào những yêu cầu nêu trên, đó chính là Bloom Filter (BF) [4], sử dụng một dạng mã hóa có mất mát thông tin (lossy encoding), ý tưởng của BF là thay vì lưu trữ toàn bộ các n-gram, chúng ta chỉ lưu một tập đại diện mang tính ngẫu nhiên của nó. Mã hóa có mất mát thông tin là một loại kỹ thuật phổ biến thường được dùng trong lưu trữ đa phương tiện như chuẩn nén JPEG cho hình ảnh, MP3 cho âm thanh hay MPEG cho nén video. Trong đó một phần dữ liệu bị mất đi khi mã hóa, nhưng đại diện mới được tạo thành vẫn chứa đựng khá đầy đủ các thông tin hữu ích sau khi được giải mã. Bloom Filter là một cấu trúc dữ liệu xác suất, đầu tiên được xây dựng chỉ để trả lời cho câu hỏi “Liệu phần tử x có thuộc tập S hay không ?” Nếu kết quả là có thì ta gọi đó là một HIT, còn ngược lại thì ta gọi là MISS. Có hai loại lỗi có thể xảy ra khi trả lời câu hỏi truy vấn trên, đó là false positive và false negative. Lỗi false positive xảy ra khi đối tượng được truy vấn không thuộc tập S, , nhưng lại HIT. Còn false negative thì ngược lại với false positive, tức là một đối tượng bị kết luận là MISS trong khi thực tế thì không phải như vậy. Cấu trúc dữ liệu thống kê nào chỉ gặp một trong hai loại lỗi này được gọi là có lỗi một phía (one-side error) và lỗi hai phía trong trường hợp còn lại. BF là cấu trúc dữ liệu chỉ có lỗi một phía. Cấu trúc dữ liệu này yêu cầu dung lượng lưu trữ thấp hơn khá nhiều ngưỡng dưới của thuyết Entropy nhưng lại có tỉ lệ lỗi khá thấp và có thể xác định được. Bloom Filter nguyên bản không hỗ trợ lưu trữ cả cặp khóa-giá trị. Tuy nhiên Talbot và Osborne [35, 36, 37] đã đề xuất những cách cho phép tích hợp giá trị vào trong mô hình ngôn ngữ Bloom Filter. Cách thức thực hiện điều này được mô tả trong nội dung của chương. Các cấu trúc dữ liệu xác suất (PDS) Một bước quan trọng trong khâu thiết kế của một chương trình là tìm cách thích hợp để lưu trữ và xử lý dữ liệu. Việc đánh giá và lựa chọn cẩn trọng cấu trúc dữ liệu được sử dụng trong chương trình có ý nghĩa rất quan trọng: lựa chọn đúng có thể làm tăng đáng kể hiệu năng của chương trình, tiết kiệm tài nguyên, dễ dàng bảo trì hệ thống trong tương lai; ngược lại, khả năng vận hành của hệ thống có thể bị hạn chế do khối lượng tính toán quá lớn hay hoạt động thiếu ổn định, thậm chí không hoạt động được với những tập dữ liệu lớn nếu sử dụng một cấu trúc dữ liệu tồi. Tồn tại nhiều dạng cấu trúc dữ liệu khác nhau, phù hợp cho những mục đích sử dụng khác nhau. Một số cấu trúc dữ liệu chỉ là những kho chứa dữ liệu thông thường, trong khi một số khác lại được dùng cho những ứng dụng đặc biệt và chỉ phát huy được hiệu năng tối đa trong điều kiện nhất định. Trong nhiều trường hợp, tập ngữ liệu quá lớn đến nỗi không một siêu máy tính nào hiện tại có khả năng quản lý được. Và cũng không có cấu trúc dữ liệu chuẩn nào có thể lưu trữ được nó. Ví dụ như, trong lĩnh vực dịch máy thống kê, năm 2006, Google đã khiến cả cộng đồng ngành NLP phải sửng sốt khi họ công bố một ngữ liệu Ngram khổng lồ . Với khoảng 3 tỉ từ, dung lượng là 24 GB khi đã nén, tập ngữ liệu này quá lớn thậm chí với hệ thống bộ nhớ của những siêu máy tính. Hiển nhiên là ta có thể được lưu trữ nó trong ổ đĩa cứng, nhưng ví dụ như với dịch máy thống kê (SMT), một mô hình ngôn ngữ có thể được truy vấn hàng trăm nghìn lần mỗi câu, vậy nên rõ ràng đây không phải là một phương án khả thi. Chúng ta cần tìm ra một hướng tiếp cận khác cho những tập ngữ liệu đồ sộ như thế này. Một hướng tiếp cận khả thi là thay vì tìm cách biểu diễn chính xác một tập ngữ liệu lớn, không mất mát (lossless), ta chấp nhận ý tưởng sử dụng một tập đại diện có mất mát (lossy) của nó. Nghĩa là bằng cách sử dụng một vài kỹ thuật nào đó: Một lượng dữ liệu mà ta kiểm soát được bị mất đi. Tổn hại đến sự toàn vẹn dữ liệu gây ra bởi lượng dữ liệu đã mất có thể được coi là nhỏ nếu so sánh với không gian lưu trữ ta đã tiết kiệm được. Đồng thời từ chỗ không thể kiểm soát được dữ liệu (không sử dụng được trong các chương trình do tập này quá lớn, thời gian tìm kiếm lâu, …), giờ đây ta đã có thể kiểm soát được chúng. Hướng tiếp cận này phát triển thành một lớp cấu trúc dữ liệu mới, được gọi là các Cấu trúc dữ liệu ngẫu nhiên (Randomised Data Structure - RDS) hay còn được gọi là các Cấu trúc dữ liệu xác suất (Probabilistic Data Structure). Trong các PDS, dữ liệu được mã hóa cẩn thận và tối ưu dưới dạng có mất mát, và từ “ngẫu nhiên” ám chỉ các cấu trúc dữ liệu này dựa trên những thuật toán mã hóa mang tính ngẫu nhiên nhất định. Một thuật toán ngẫu nhiên có thể được định nghĩa là “thuật toán sử dụng các lựa chọn tùy ý, không xác định trước trong quá trình tính toán” [14]. Một phần dữ liệu sẽ bị mất khi được mã hóa vào một PDS. Tuy nhiên thông tin vẫn sẽ được lưu trữ sao cho dạng mới này của dữ liệu vẫn hiệu quả tương đương dạng biểu diễn chính xác (không mất mát) của nó. Nhiều loại cấu trúc dữ liệu xác suất đã được nghiên cứu, phát triển và ứng dụng trong những năm gần đây [30]. Một số cấu trúc dữ liệu loại này có thể kể đến như Skip List [33], Sparse Partition [16], Lossy Dictionary [31], và một cấu trúc dữ liệu tuy đã được đề xuất từ khá lâu nhưng hiện tại lại tiếp tục được nghiên cứu nhiều - Bloom Filter [24, 35, 36, 37]. Nhận thấy một số ưu điểm như tốc độ, khả năng tiết kiệm bộ nhớ đáng kể của Bloom Filter [24], chúng tôi đã chọn nghiên cứu loại cấu trúc dữ liệu này và trình bày trong khóa luận. Cấu trúc dữ liệu Bloom Filter cơ bản sẽ được giới thiệu trong phần sau của chương này. Tiếp đó là cải tiến đơn giản để có thể lưu trữ dữ liệu theo cặp {khóa, giá trị} – Logarithmic Frequency Bloom Filter (hay Bloom Filter tần số log) [35]; và một dạng cải tiến phức tạp hơn được ra đời sau là Bloom Map [37]. Hàm băm Một thành phần rất quan trọng được sử dụng trong Bloom Filter đó là các hàm băm. Chính vì vậy trước khi đi sâu tìm hiểu cấu trúc dữ liệu BF ở các phần sau, mục này trình bày vài nét sơ lược về hàm băm. Hàm băm (Hash function) là một hàm ánh xạ phần tử từ tập này sang một tập khác (thường là nhỏ hơn). Cây Hàm băm DFA2C4ED Cây táo Hàm băm BE34C87A Cây cam Hàm băm 7CD4ADE INPUT OUTPUT Hình 2: Ví dụ về hàm băm. Các xâu ký tự được chuyển thành chữ ký đại diện. Phần tử cần được băm là từ tập S có cỡ n, tập này nằm trong tập dữ liệu ban đầu U với và . Đại diện của phần tử đó trong miền b được gọi là chữ ký hoặc dấu ấn của dữ liệu. Hàm h này phải mang tính ổn định, có nghĩa là nếu cùng một dữ liệu đi qua hàm h nhiều lần thì luôn cho kết qua giống nhau. Đồng thời nếu đầu ra của hai phần tử qua hàm h khác nhau thì ta cũng có thể kết luận hai phần tử đó là khác nhau. Khóa ki được đưa vào hàm băm h(ki), kết quả của hàm băm này trỏ đến một ô trong bảng giá trị cỡ m: (được gọi là bảng băm), ô đó chứa giá trị ai. Đặc tính đáng chú ý của bảng giá trị băm này là thời gian tìm kiếm không phụ thuộc vào kích cỡ của tập dữ liệu được mã hóa vào bảng. Hình 3 minh họa cấu trúc một bảng băm. a4 … … a2 … … ??? … … … … S U Hình 3: Cặp khóa ki và giá trị ai của tập S được ánh xạ thông qua 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. Để có một hàm băm tốt thì giá trị của nó phải có phân phối đều. Số lượng giá trị chúng ta có thể lưu trữ với b-bits là 2b. Nếu tập S lớn và thì một số phần tử thuộc tập S sẽ xung đột với nhau khi được ánh xạ từ không gian lớn cỡ w vào không gian nhỏ hơn là b. Chúng ta có thể tối thiểu hóa va chạm nếu chọn được hàm băm có đầu ra phân phối đều trên b. Bởi vì nếu hàm băm không có phân phối đều, đầu ra của chúng sẽ chỉ tập trung ánh xạ vào một số vị trí trong bảng băm, trong khi nhiều vị trí khác lại bị bỏ trống. Bloom Filter cơ bản Các cấu trúc dữ liệu dựa trên Bloom Filter được sử dụng để xây dựng mô hình ngôn ngữ có nguồn gốc từ Bloom Filter (BF) cơ bản [4]. BF, trước tiên là một cấu trúc dữ liệu xác suất (PDS), hỗ trợ truy vấn kiểm tra một đối tượng có thuộc tập hợp hay không. BF sử dụng một thuật toán mã hóa độc đáo cho phép nó tiết kiệm đáng kể không gian lưu trữ, thời gian truy vấn bất biến không phụ thuộc vào kích cỡ của tập cần đại diện và có tỉ lệ lỗi-một-phía điều khiển được. Hình 4: Huấn luyện Bloom Filter Một BF đại diện cho một tập với n phần tử được lấy ngẫu nhiên từ tập ban đầu U cỡ N (). Bộ nhớ đáng kể nhất mà BF sử dụng là một mảng bit cỡ m. Trước quá trình huấn luyện, mảng này chỉ chứa các giá trị 0. Để huấn luyện BF, chúng ta sử dụng k hàm băm độc lập, mỗi hàm băm có đầu ra trỏ đến một vị trí trong mảng bít m tùy theo giá trị đầu vào x, . Mỗi phần tử x trong tập S cỡ n chúng ta đang cần biểu diễn được băm k lần sử dụng k hàm băm nêu trên, và bit tương ứng với đầu ra của mỗi hàm băm trong bảng m được thiết lập giá trị bằng 1. Như vậy là với mỗi phần tử , k vị trí tương ứng được “bật lên”, nếu một bit hk nào đó đã có giá trị bằng 1 rồi thì bit đó vẫn giữ nguyên trạng thái. Nghĩa là, một khi đã được thiết lập, giá trị này sẽ không bao giờ bị thay đổi nữa qua cả quá trình huấn luyện. Cần lưu ý rằng có thể tồn tại khả năng k hàm băm của một phần tử có đầu ra không trỏ đến k vị trí riêng biệt trong mảng bit, BF không tránh sự va chạm này. Các bit trong mảng do cơ chế này mà có thể được chia sẻ cho các phần tử dùng chung, đem lại khả năng tiết kiệm đáng kể bộ nhớ cho BF, tuy nhiên lại tồn tại một xác suất lỗi false positive khác 0. Hình 5: Truy vấn Bloom Filter Để kiểm tra một phần tử nào đó có thuộc tập đã được mã hóa trong BF hay không, chúng ta lại đưa nó chạy qua k hàm băm trên. Nếu tất cả các bit được tham chiếu bởi k hàm băm có giá trị bằng 1 thì ta coi phần tử đó thuộc tập hợp; còn nếu tồn tại bất cứ giá trị nào bằng 0 thì chúng ta biết chắc chắn nó không thuộc tập hợp. Tại sao ở đây cần phải nhấ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 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.