Giá trị của thông tin có thể là âm?

Question

Có cơ hội để nhận được giá trị của tăng thông tin là tiêu cực không? Nó được tính theo công thức trong bài báo sau. Tôi không thể viết công thức, bởi vì nó bao gồm một số ký hiệu cứng.

http://citeseerx.ist.psu.edu

Cảm ơn!

Answer 1

IG(Y|X) = H(Y) - H(Y|X) >= 0, vì H(Y) >= H(Y|X) trường hợp xấu nhất là X và Y là độc lập, do đó H(Y|X)=H(Y)

Một cách khác để suy nghĩ về nó là bằng cách quan sát các biến X ngẫu nhiên dùng một số giá trị, chúng ta hoặc là đạt được không hay một số thông tin về Y (bạn không mất bất kỳ).

---

EDIT

Hãy để tôi làm rõ lợi ích thông tin trong bối cảnh cây quyết định (mà thực sự tôi đã có trong tâm trí ở nơi đầu tiên khi tôi xuất thân từ một nền học máy).

Giả sử một vấn đề phân loại nơi chúng tôi đưa ra một tập hợp các trường hợp và nhãn (các lớp rời rạc).

Ý tưởng chọn thuộc tính nào được chia theo từng nút của cây, là chọn đối tượng chia thuộc tính lớp thành hai nhóm thuần nhất có thể (ví dụ entropy thấp nhất).

Đây là lần lượt tương đương với chọn các tính năng với mức tăng thông tin cao nhất kể từ

InfoGain = entropyBeforeSplit - entropyAfterSplit 

nơi entropy sau khi chia tay là tổng entropy của từng ngành trọng bởi số lượng các trường xuống chi nhánh đó.

Bây giờ không tồn tại sự phân chia các giá trị lớp có thể sẽ tạo ra một trường hợp có độ tinh khiết thậm chí tệ hơn (entropy cao hơn) so với trước khi tách.

Lấy ví dụ đơn giản này về vấn đề phân loại nhị phân. Tại một nút nhất định, chúng tôi có 5 trường hợp dương và 4 trường hợp âm (tổng cộng là 9). Do đó entropy (trước khi chia tách) là:

H([4,5]) = -4/9*lg(4/9) -5/9*lg(5/9) = 0.99107606 

Bây giờ, hãy xem xét một số trường hợp chia tách.Các kịch bản trường hợp tốt nhất là các thuộc tính hiện chia tách các trường hợp một cách hoàn hảo (tức là một chi nhánh là tất cả tích cực, khác tất cả tiêu cực):

[4+,5-] 
    / \  H([4,0],[0,5]) = 4/9*(-4/4*lg(4/4)) + 5/9*(-5/5*lg(5/5)) 
    / \      = 0   // zero entropy, perfect split 
[4+,0-] [0+,5-] 

sau đó

IG = H([4,5]) - H([4,0],[0,5]) = H([4,5])  // highest possible in this case 

Hãy tưởng tượng rằng thuộc tính thứ hai là điều tồi tệ nhất trường hợp có thể, trong đó một trong các nhánh được tạo không nhận được bất kỳ trường hợp nào thay vì tất cả các trường hợp đi xuống trường hợp khác (có thể xảy ra nếu ví dụ thuộc tính không đổi trong các trường hợp, do đó vô ích):

[4+,5-] 
    / \  H([4,5],[0,0]) = 9/9 * H([4,5]) + 0 
    / \      = H([4,5]) // the entropy as before split 
[4+,5-] [0+,0-] 

và

IG = H([4,5]) - H([4,5],[0,0]) = 0    // lowest possible in this case 

Bây giờ ở đâu đó ở giữa hai trường hợp này, bạn sẽ thấy bất kỳ số lượng các trường hợp như:

[4+,5-] 
    / \  H([3,2],[1,3]) = 5/9 * (-3/5*lg(3/5) -2/5*lg(2/5)) 
    / \      + 4/9 * (-1/4*lg(1/1) -3/4*lg(3/4)) 
[3+,2-] [1+,3-] 

và

IG = H([4,5]) - H([3,2],[1,3]) = [...] = 0.31331323 

vì vậy không vấn đề làm thế nào bạn chia những 9 các trường hợp, bạn luôn nhận được thông tin tích cực trong thông tin. Tôi nhận ra điều này là không có bằng chứng toán học (đi đến MathOverflow cho điều đó!), Tôi chỉ nghĩ một ví dụ thực tế có thể giúp đỡ.

(Lưu ý: Tất cả các tính toán theo Google)

Answer 2

Chắc chắn có thể.

lợi Thông tin chỉ là sự thay đổi trong entropy thông tin từ một tiểu bang khác:

IG (Ex, a) = H (Ex) - H (Ex | a)

Đó thay đổi trạng thái có thể đi theo một trong hai hướng - nó có thể là dương hoặc âm.

này rất dễ dàng để nhìn thấy bằng ví dụ: các thuật toán Tree

Quyết định làm việc như thế này: tại một nút nào đó, bạn tính toán entropy thông tin của nó (đối với biến độc lập).

Bạn có thể nghĩ về điều này như sau: thông tin entropy là các biến phân loại/rời rạc do phương sai là các biến liên tục). Variance, tất nhiên, chỉ là hình vuông của độ lệch chuẩn. Ví dụ: nếu chúng tôi đang tìm kiếm giá dự đoán dựa trên các tiêu chí khác nhau và chúng tôi đã nhóm dữ liệu của mình một cách tùy ý thành hai nhóm, trong đó giá cho nhóm A là (50, 60 và 70) và giá cho nhóm B là (50, 55, 60), nhóm B có phương sai thấp nhất - tức là chúng gần nhau. Tất nhiên phương sai không thể là số âm (vì sau khi bạn tính tổng khoảng cách của mỗi điểm từ giá trị trung bình, bạn hãy đặt nó) nhưng sự khác biệt về phương sai chắc chắn có thể.

Để xem điều này liên quan đến Entropy/Information Gain như thế nào, giả sử chúng tôi không dự đoán giá nhưng khác, như khách truy cập vào trang web của chúng tôi sẽ trở thành người dùng đã đăng ký hoặc người đăng ký cao cấp hay không. Biến độc lập ở đây là rời rạc, không liên tục như giá cả, vì vậy bạn không thể tính phương sai một cách có ý nghĩa. Entropy thông tin là cái được sử dụng thay thế. (Nếu bạn nghi ngờ sự tương đồng gần đây giữa phương sai và IE, bạn nên biết rằng hầu hết các thuật toán cây quyết định có khả năng xử lý cả biến rời rạc và liên tục, trong trường hợp sau, thuật toán sẽ sử dụng phương sai như tiêu chí tách, thay vì sử dụng IG.Trong bất kỳ trường hợp nào, sau khi bạn tính toán entropy thông tin cho một nút cụ thể, bạn chia dữ liệu tại nút đó (toàn bộ tập dữ liệu nếu bạn ở nút gốc) trên mọi giá trị cho mỗi biến, sau đó cho mỗi phân chia, tính toán IE cho cả hai nhóm và lấy IE trung bình có trọng số. Tiếp theo, hãy phân chia kết quả trong IE trung bình có trọng số thấp nhất và so sánh nó với nút IE (đó rõ ràng là chỉ là một nhóm duy nhất). Nếu IE trung bình có tỷ lệ chia tách đó là thấp hơn nút IE, sau đó bạn chia dữ liệu tại nút đó (tạo thành nhánh), nếu không, thì bạn dừng lại, nghĩa là nút đó không thể chia tách được nữa - Bạn đang ở phía dưới.

Tóm lại, tại trung tâm của thuật toán cây quyết định là tiêu chí để xác định có chia tách một nút hay không - đó là cách chúng được tạo. Tiêu chí đó là liệu IG là dương hay âm.

Answer 3

Đối với bất kỳ ai khác gặp phải câu hỏi này, mặc dù ở độ tuổi của nó, tôi đưa ra câu trả lời và lời khuyên này.

Đầu tiên, câu trả lời là không, nó không được âm. Khả năng tuyệt đối tồi tệ nhất là không có thay đổi, hoặc số IG bằng không. Nếu bạn muốn bằng chứng, hãy tìm kiếm bằng chứng đầy đủ về MathOverFlow như Amro đã chỉ ra.

Bây giờ để được tư vấn. Nếu bạn chỉ làm cấp độ đầu tiên của một cây quyết định, có vẻ như rõ ràng rằng nó sẽ không bao giờ đi lên tiêu cực. Tuy nhiên, khi xây dựng cây đầu tiên của tôi bằng cách sử dụng thông tin Gain, tôi thấy mình với một lợi ích tiêu cực bởi nhánh thứ ba của tôi. Điều này không có vẻ hữu ích hoặc có thể, vì vậy tôi tranh giành để kiểm tra toán học của tôi. Toán học là tốt. Phần tôi có sai là phần đầu tiên của công thức cơ sở. Tôi đã sử dụng câu trả lời từ cấp trên như entropy bắt đầu của tôi, nhưng điều này là sai vì nó bao gồm thông tin từ các tập dữ liệu khác. Bạn cần đảm bảo rằng đối với entropy bắt đầu của bạn, bạn xác định entropy cho chi nhánh đó! Điều này có nghĩa là "entropy bắt đầu" của bạn thực sự có thể cao hơn so với mức trước đó.

Nói cách khác, khi tính toán IG, hãy đảm bảo bạn chỉ sử dụng tập dữ liệu hiện tại.