Thuật toán Entropy cực đại

Thuật toán Entropy cực đại

(Tác giả: Tuan Anh Luu – Nguồn: viet.jnlp.org)

Đối với bài toán phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mô hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng / đều nhất có thể”. Tập dữ liệu học (tức là tập gồm các dữ liệu đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mô hình, đó là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mô hình sẽ tiến hành tính toán để có được một phân phối cho Entropy cực đại.
Ví dụ một mô hình Entropy cực đại: “Giả sử với bộ phân lớp về lĩnh vực kinh tế trên báo VnEconomy có bốn lớp chính được chỉ ra là ngân_hàng, chứng_khoán, bất_động_sản, doanh_nghiệp. Các thống kê dữ liệu chỉ ra rằng trung bình 70% các tài liệu trong lớp ngân_hàng có chứa từ vay_vốn. Như vậy một cách trực quan có thể thấy rằng nếu một tài liệu D có chứa từ vay_vốn thì xác suất được phân vào lớp ngân_hàng là 70% và xác suất phân vào ba lớp còn lại là 10% đối với mỗi lớp. Nếu tài liệu D không chứa từ vay_vốn thì xác suất phân phối của D là 25% đều cho mỗi lớp.” Trong ví dụ trên, “nếu tài liệu chứa cụm từ vay_vốn thì có xác suất phân vào lớp ngân_hàng là 70%” là một ràng buộc của mô hình.
1. Các ràng buộc và đặc trưng
Trong nguyên lý Entropy cực đại, chúng ta sử dụng tập dữ liệu mẫu làm để thiết lập ràng buộc cho phân phối điều kiện. Với mỗi ràng buộc được mô tả bởi một đặc tính của tập dữ liệu học. Một đặc trưng trong mô hình Entropy cực đại được biểu diễn bởi một hàm fi(d, c), trong đó d là tài liệu và c là lớp. Entropy cực đại cho phép giới hạn mô hình phân phối để có thu các giá trị kỳ vọng cho mỗi đặc trưng của tập dữ liệu. Vì vậy, ta có thể đặt xác suất phân phối của dữ liệu d cho lớp c là P(c|d) thỏa mãn phương trình sau:
Trong quá trình huấn luyện, phân phối tài liệu P(d) là không biết và chúng ta không cần quan tâm tới nó. Vì vậy, ta chỉ sử dụng tập dữ liệu mẫu như là một điều kiện để phân phối dữ liệu tuân theo ràng buộc sau:
2.Mô hình Entropy cực đại
Mô hình xác suất Entropy cực đại cung cấp một cách đơn giản để kết hợp các đặc trưng của tài liệu trong những ngữ cảnh khác nhau để ước lượng xác suất của một số lớp xuất hiện cùng với một số ngữ cảnh này. Tư tưởng cơ bản của phương pháp Entropy cực đại là tìm ra một mô hình có phân phối xác suất thỏa mãn mọi ràng buộc quan sát được từ dữ liệu mà không đưa thêm bất kì một giả thiết nào khác. Theo nguyên lý Entropy cực đại, phân phối cần đáp ứng dữ liệu quan sát và làm cực đại độ đo Entropy có điều kiện:
Trong đó p* là phân xác suất tối ưu.
Mô hình Entropy cực đại xây dựng các đặc trưng từ tập dữ liệu huấn luyện. Mỗi đặc trưng được biểu diễn dưới một hàm nhận một trong hai giá trị đúng hoặc sai. Tập các ràng buộc sẽ được thiết lập từ các đặc trưng này. Một ràng buộc là một điều kiện từ dữ liệu buộc mô hình phải thỏa mãn. Mỗi đặc trưng fi được gán cho một trọng số λi . Khi đó, bài toán phân lớp được đưa về bài toán ước lượng xác suất có điều kiện:

Trong đó Z(d) là biểu thức chuẩn hóa để đảm bảo điều kiện Σp(c | d ) = 1. Từ đó đưa ra công thức sau:

3. Entropy cực đại cho phân lớp văn bản

Để áp dụng mô hình Entropy cực đại cho một miền, chúng ta cần phải chọn ra một tập các đặc trung để sử dụng thiết lập các ràng buộc. Đối với phân lớp văn bản với mô hình Entropy cực đại, chúng ta sử dụng số lượng từ như là các đặc trưng. Trong nghiên cứu này cho với mỗi từ kết hợp, ta đưa ra một đặc tính như sau:
Trong đó, N(d, w) là số lần từ w xuất hiện trong tài liệu d, và N(d) là số lượng các từ có trong tài liệu d.
Trong công thức này, nếu một từ xuất hiện thường xuyên trong một tài liệu, ta sẽ tính trọng số cho các cặp từ này và thấy rằng trọng số đó sẽ cao hơn so với trọng số của các từ ghép trong tài liệu. Trong hầu hết ngôn ngữ tự nhiên sử dụng Entropy cực đại thì các đặc trưng thường là đặc trưng nhị phân. Trong phân lớp văn bản, chúng ta mong muốn các đặc trưng được tính bằng số lần suất hiện của một từ trong một tài liệu có thể củng cố cho phân lớp.
Một trong những khía cạnh đặc biệt của Entropy cực đại là nó không bị bất kỳ giả thuyết độc lập nào ràng buộc. Ví dụ, với cụm từ “Buenos Aires”, hai từ này hầu như luôn xuất hiện động thời cùng nhau.Với giả thiết Naïve Bayes sẽ đếm số từ xuất hiện hai lần trong cụm từ này. Mặt khác, Entropy cực đại sẽ giảm giá trị trọng số λi của mỗi đặc trưng đi một nửa. Một trong những hệ của việc không phụ thuộc vào
bất kỳ giả thuyết độc lập nào đó là các sơ đồ và các cụm từ có thể được thêm vào các đặc trưng của Entropy cực đại một cách dễ dàng mà không cần lo lắng rằng các đặc tính này chồng lên nhau.
􀂾 Ưu điểm của mô hình Entropy cực đại:
– Cho phép khả năng hầu như không hạn chế trong việc biểu diễn các vấn đề phức tạp về tri thức thông qua dạng các hàm đặc trưng.
– Có thể giải quyết nhiều dạng thuộc tính khác nhau.
– Các giả thiết không cần phải độc lập với nhau.
– Trọng số của các đặc trưng được xác định một cách tự động.
—————-&&—————

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: