MÔ HÌNH MAXIMUM ENTROPY VÀ ỨNG DỤNG

- Trong luận văn này, em tập trung tìm hiểu về mô hình cực đại entropy và áp dụng mô hình để xây dựng chương trình phân loại văn bản Tiếng Việt tự động dựa trên tập dữ liệu huấn luyện.
- Giới thiệu mô hình cực đại entropy.
- 12Chương 3: Mô hình cực đại entropy.
- 123.1 Tổng quát mô hình cực đại entropy.
- 153.2 Mô hình cực đại entropy.
- 223.3 Lựa chọn đặc trưng.
- 223.3.1 Ý nghĩa của việc lựa chọn đặc trưng.
- 243.3.2 Cơ sở lựa chọn đặc trưng.
- Hình 3.1: Lựa chọn đặc trưng .
- Phương pháp phân loại được nghiên cứu trong luận văn là mô hình cực đại entropy [Berger, 1996 và Della Pietra, 1997]..
- 1.2 Giới thiệu mô hình cực đại entropy Mô hình cực đại entropy là phương pháp phân loại văn bản được sử dụng rộng rãi trong nhiều lĩnh vực của xử lý ngôn ngữ tự nhiên như: ngôn ngữ mô hình hóa [Chen và Rosenfeld, 1999], gán nhãn từ loại [Ratnaparkhi, 1996], phân loại văn bản [Beeferman, 1999].
- Mô hình cực đại entropy là kỹ thuật dùng để đánh giá phân phối xác suất của dữ liệu văn bản.
- Dữ liệu đã được gán nhãn được sử dụng để lấy ra tập các ràng buộc cho mô hình mà nó mô tả đặc điểm riêng cho từng lớp cụ thể có thể được gán cho văn bản cần phân lớp.
- Một yếu tố trong quá trình huấn luyện của mô hình cực đại entropy chính là việc lựa chọn các vector đặc trưng cho từng lớp.
- Mô hình cực đại entropy có được tối ưu hay không là phụ thuộc rất nhiều vào việc lựa chọn này..
- Tuy nhiên, mô hình cực đại entropy đòi hỏi một chi phí khá lớn cho việc tính toán để ước lượng chính xác các tham số của mô hình.
- 1998], mô hình cực đại Entropy [Berger, 1996 và Della Pietra, 1997].
- Phương pháp phân loại văn bản tiếng Việt được sử dụng trong luận văn là mô hình cực đại Entropy [Berger, 1996 và Della Pietra, 1997].
- Phần lý thuyết của mô hình trình bày về cách biểu diễn của dữ liệu huấn luyện.
- Nguyên lý hoạt động của mô hình cực đại entropy.
- Để hiểu sâu sắc thuật toán, luận văn đề ra mục tiêu xây dựng từ đầu thuật toán mô hình cực đại entropy (chương trình phân loại văn bản tiếng Việt) cũng như ứng dụng chặn nội dung web.
- Để phân loại văn bản người ta sử dụng nhiều cách tiếp cận khác nhau như dựa trên từ khóa, dựa trên ngữ nghĩa các từ có tần số xuất hiện cao, mô hình cực đại entropy [Berger, 1996 và Della Pietra, 1997], tập thô.
- Rất nhiều phương pháp đã được áp dụng như: mô hình hồi quy [Fuhr, 1991], k-nearest neighbors [Dasarathy, 1991], Naïve Bayes [Joachims, 1997], cây quyết định [Fuhr, 1991], học luật quy nạp [William & Yorm, 1996], Support vector Machine [Vapnik, 1995], mô hình cực đại entropy [Berger, 1996 và Della Pietra, 1997].
- Mỗi ràng buộc thể hiện một đặc trưng của dữ liệu huấn luyện.
- Phương pháp cực đại entropy dựa vào các đặc trưng đó xây dựng các mô hình có giá trị kỳ vọng của các đặc trưng của dữ liệu huấn luyện là gần giống nhất với giá trị lý thuyết.
- Các phương pháp huấn luyện mô hình từ dữ liệu huấn luyện đã được giới thiệu ở trên.
- Cụ thể với mô hình cực đại entropy, thuật toán IIS chỉ có thể tính toán được các tham số dựa trên các vector đặc trưng.
- 2.4 Các phương pháp phân loại văn bản.
- y= 1: văn bản.
- yi = -1 văn bản.
- Chương 3: Mô hình cực đại entropy.
- Dựa trên tài liệu mô hình cực đại entropy của [Adam L.
- Dưới đấy là những cơ sở lý thuyết cơ bản về mô hình cực đại entropy.
- 3.1 Tổng quát mô hình cực đại entropy.
- Xác suất mô hình (p) của hệ thống dịch tự động cho mỗi từ hay cụm từ tiếng Pháp f là một ước lượng p(f) của xác suất mà hệ thống sẽ lựa chọn f được dịch với nghĩa là “in” trong tiếng Anh.
- Với những thông tin này, chúng ta có thể dùng làm ràng buộc đầu tiên trong xác suất mô hình (p) của chúng ta: p(dans.
- bây giờ chúng ta đã có thể xử lý để tìm ra mô hình phù hợp mà nó tuân theo phương trình này.
- Tất nhiên, có vô số các xác suất mô hình (p) mà nó thỏa mãn ràng buộc trên.
- Một mô hình mà thỏa mãn ràng buộc trên có thể là p(dans.
- nói cách khác, mô hình luôn luôn dự đoán đó là “dans”.
- 1/5 Với mô hình này, nó phân bố tổng xác suất ngang bằng nhau trong số 5 từ (cụm từ) có thể được lựa chọn để dịch, là mô hình đều nhất phụ thuộc vào các hiểu biết của chúng ta.
- mà mô hình sẽ cấp một xác suất ngang nhau cho mọi từ (cụm từ) tiếng Pháp có thể được dịch.
- Chúng ta có thể sử dụng thông tin này cho việc cập nhập mô hình của chúng ta trong bài toán dịch bằng cách yêu cầu xác suất mô hình (p) thỏa mãn 2 ràng buộc sau: p(dans.
- Chúng ta có thể kết hợp thông tin này vào mô hình của chúng ta như một ràng buộc thứ 3: p(dans.
- ½ Chúng ta có thể một lần nữa tìm ra các xác suất mô hình (p) ngang bằng nhau hơn ứng với các ràng buộc trên, nhưng bây giờ việc lựa chọn không còn là hiển nhiên nữa.
- Điều này gần giống như việc chúng ta lựa chọn các xác suất mô hình (p) tại mỗi bức như chúng ta đã làm trong ví dụ trên.
- 3.2 Mô hình cực đại entropy.
- Nhiệm vụ của chúng ta là xây dựng mô hình có tính ngẫu nhiên thống kê mà nó miêu tả chính xác các hành vi của bài toán bất kỳ.
- Chúng ta sẽ biểu diễn bằng xác suất p(y|x) mà mô hình ấn định y trong ngữ cảnh x.
- Chúng ta cũng sẽ sử dụng p(y|x) để biểu diễn cho toàn bộ phân phối xác suất có điều kiện bởi mô hình.
- Như vậy một xác suất mô hình p(y|x) chính là một thành phần của P.
- 3.2.2 Thống kê, đặc trưng và ràng buộc.
- Mục đích của chúng ta là xây dựng một mô hình thống kê của bài toán mà nó phát sinh xác suất p̃(x,y) mẫu huấn luyện.
- Khối kiến trúc của mô hình này sẽ là một tập các thống kê của mẫu huấn luyện.
- Chúng ta làm điều này bằng các ràng buộc các giá trị kỳ vọng mà mô hình ấn định cho các hàm đặc trưng (f) tương ứng.
- Giá trị kỳ vọng của f quan hệ với xác suất mô hình p(y|x) như sau:.
- Bằng cách thu hẹp sự chú ý tới những xác suất mô hình, p(y|x), như trong công thức (3), chúng ta loại trừ các mô hình được xem xét mà nó không thích hợp với mẫu huấn luyện dựa vào cách thông thường mà output của bài toán sẽ đưa ra đặc trưng f..
- một ràng buộc là một phương trình giữa giá trị kỳ vọng của hàm đặc trưng trong mô hình và giá trị kỳ vọng của nó trong dữ liệu huấn luyện..
- Giả thiết rằng chúng ta có n hàm đặc trưng fi, nó quyết định những thống kê mà chúng ta cảm thấy là quan trọng trong quá trình mô hình hóa.
- Chúng ta muốn mô hình của chúng ta phù hợp với những thống kê đó.
- Ẽ(fi) for i n}} (4) Trong số các mô hình p € C, triết lý cực đại entropy yêu cầu rằng chúng ta lựa chọn phân phối mà ngang bằng nhau nhất.
- Với định nghĩa này, chúng ta đã sẵn sàng để biểu diễn nguyên lý của cực đại entropy: Để lựa chọn mô hình từ một tập C các phân phối xác suất được chấp nhận, lựa chọn mô hình p.
- vì vậy, luôn luôn tồn tại một mô hình duy nhất p* với cực đại entropy trong bất kỳ tập ràng buộc C nào.
- Chúng ta tìm được:.
- Nói cách khác, Mô hình cực đại entropy đưa ra các ràng buộc C có dạng tham số pλ* trong công thức (10), trong đó giá trị λ* có thể được tính bằng cách cực đại hóa hàm đối ngẫu ψ(λ).
- (13) Dễ dang có thể kiểm tra được rằng hàm đối ngẫu ψ(λ) của phần trước chính là log-likelihood hàm số mũ của xác suất mô hình pλ:.
- (14) Với cách giải thích này, kết quả của phần trước có thể được viết lại như sau: Mô hình p.
- C với cực đại entropy là mô hình trong đó họ tham số pλ(y|x) mà nó cực đại likelihood của xác suất mẫu huấn luyện p̃.
- xác suất mô hình tối ưu pλ* 1.
- 3.3 Lựa chọn đặc trưng.
- Từ những phần trước chúng ta đã chia bài toán mô hình hóa thống kê thành 2 bước: bước thứ nhất là tìm các sự kiện thích hợp về dữ liệu.
- 3.3.1 Ý nghĩa của việc lựa chọn đặc trưng.
- Chỉ một tập con của tập các đặc trưng sẽ được sử dụng vào mô hình cuối cùng của chúng ta.
- Một cách ngắn gọn, chúng ta muốn thêm vào mô hình chỉ một tập con S của toàn bộ tập đặc trưng ứng cử F.
- Bây giờ chúng ta biểu diễn tập mô hình được xây dựng bởi các đặc trưng của tập S là C(S).
- Hình 3.1: Lựa chọn đặc trưng.
- 3.3.2 Cơ sở lựa chọn đặc trưng.
- Điều đó quyết định không gian của mô hình: C(S.
- Như công thức (19), tập đặc trưng này quyết định tập các mô hình: C(S U f.
- (21) Mô hình tối ưu trong không gian mô hình này là:.
- (22) Thêm đặc trưng f̃ cho phép mô hình psυf̃ tính toán tốt hơn với mẫu huấn luyện.
- xác suất mô hình pS hợp nhất các đặc trưng.
- Với mỗi đặc trưng ứng cử f € F: a) Tính xác suất mô hình PSυf sử dụng thuật toán 1 b) Tính lượng gia tăng của log-likelihood từ những đặc trưng được thêm vào sử dụng công thức (23) 3.
- Nhắc lại rằng một xác suất mô hình pS có tập các tham số λ, với mỗi đặc trưng trong tập S.
- Xác suất mô hình pSυf chứa tập các tham số này, cộng với tham số mới α, tương ứng với f.
- Vì vậy, khi quyết định độ gia tăng trên xác suất mô hình pS, chúng ta ràng buộc rằng mô hình tốt nhất chứa các đặc trưng Sυf phải có dạng như sau:.
- Chỉ duy nhất tham số mà nó phân biệt được các mô hình có dạng (24) là α.
- Trong số các mô hình đó, chúng ta quan tâm tới mô hình mà nó làm tăng tính gần đúng..
- Chúng ta sẽ biểu diễn sự tăng thêm của mô hình này bởi:.
- và mô hình tối ưu bởi:.
- Tại bước này, những đặc trưng nào không làm tăng entropy của mô hình thì sẽ bị loại bỏ..
- Với ưu điểm mềm dẻo và linh hoạt của mô hình cực đại entropy, luận văn sử dụng mô hình cực đại entropy để giải quyết bài toán phân loại văn bản.
- Lý thuyết mô hình cực đại entropy được trình bày chi tiết tại chương 3 với những khái niệm về dữ liệu huấn luyện, thống kê, đặc trưng và các ràng buộc.
- Nguyên lý hoạt động của mô hình cực đại entropy với bài toán phân loại văn bản.
- Dựa trên những cơ sở lý thuyết của mô hình cực đại entropy để phát triển chương trình phân loại văn bản.
- Bằng việc thay đổi đó sẽ giúp tìm ra được mô hình hoàn thiện nhất ứng với những tập dữ liệu huấn luyện khác nhau.
- Hàm gán giá trị cho mảng đặc trưng.
- Trả lại giá trị kỳ vọng mô hình của cặp đặc trưng với nhãn tag và ngữ cảnh context double delta_lamda(int tag, int context).
- Trả lại giá trị Δλ của cặp đặc trưng (tag, context) void lamda(double delta_lamda_init, int loop).
- MÔ HÌNH MAXIMUM ENTROPY VÀ ỨNG DỤNG