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

ĐẠ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ồ