Il valore del guadagno di informazioni può essere negativo?

Question

C'è una possibilità di ottenere il valore del guadagno di informazioni negativo? Viene calcolato in base alla formula nel seguente documento. Non riesco a scrivere la formula, perché include alcune notazioni difficili.

http://citeseerx.ist.psu.edu

Grazie!

Answer 1

IG(Y|X) = H(Y) - H(Y|X) >= 0, poiché H(Y) >= H(Y|X) caso peggiore è che X e Y sono indipendenti, così H(Y|X)=H(Y)

Un altro modo di pensare è che, osservando la variabile casuale X prendendo qualche valore, ci sia guadagniamo alcuna o alcune informazioni Y (non ne perdi nessuno).

---

EDIT

Vorrei chiarire guadagno informazioni nel contesto di alberi di decisione (che in realtà avevo in mente in primo luogo come mi è venuto da una macchina apprendimento di sottofondo).

Assumere un problema di classificazione in cui viene fornito un insieme di istanze ed etichette (classi discrete).

L'idea di scegliere quale attributo dividere per ciascun nodo dell'albero, è selezionare la funzione che divide l'attributo di classe nei due gruppi di istanze più puri possibili (ossia l'entropia più bassa).

Questo è a sua volta equivalente a raccogliere la funzione con il più alto guadagno informazioni dal

InfoGain = entropyBeforeSplit - entropyAfterSplit 

dove l'entropia dopo la scissione è la somma delle entropie di ogni ramo ponderata per il numero di istanze di scorrimento quel ramo.

Ora non esiste una possibile divisione dei valori di classe che genererà un caso con una purezza ancora peggiore (maggiore entropia) rispetto a prima della divisione.

Prendi questo semplice esempio di un problema di classificazione binaria. In un determinato nodo abbiamo 5 istanze positive e 4 negative (totale di 9). Pertanto l'entropia (prima della divisione) è:

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

Ora si considerano alcuni casi di suddivisione.La migliore delle ipotesi è che l'attributo attuale suddivide i casi perfettamente (cioè un ramo è tutto positivo, l'altro tutti negativi):

[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-] 

poi

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

immaginare che il secondo attributo è il peggiore caso possibile, dove uno dei rami creati non ottiene alcuna istanza piuttosto tutte le istanze passano all'altra (potrebbe accadere se per esempio l'attributo è costante tra le istanze, quindi inutile):

[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-] 

e

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

Ora da qualche parte tra questi due casi, si vedrà un qualsiasi numero di casi come:

[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-] 

e

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

quindi non importa quanto si divide coloro 9 istanze, ottieni sempre un guadagno positivo nelle informazioni. Mi rendo conto che questa non è una prova matematica (vai su MathOverflow per questo!), Ho solo pensato che un esempio reale potrebbe aiutare.

(Nota: Tutti i calcoli secondo Google)

Answer 2

sicuro che può.

ottenere informazioni è proprio il cambiamento di informazioni entropia da uno stato all'altro:

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

Questo cambiamento di stato può andare in entrambe le direzioni: può essere positivo o negativo.

Questo è facile da vedere con l'esempio: algoritmi Albero

decisione funziona così: in un dato nodo, si calcola la sua entropia informazioni (per la variabile indipendente).

Si può pensare in questo modo: l'entropia delle informazioni è per le variabili categoriali/discrete come la varianza è per le variabili continue). La varianza, ovviamente, è solo il quadrato della deviazione standard. Ad esempio, se stiamo cercando di prevedere il prezzo in base a vari criteri e abbiamo raggruppato arbitrariamente il nostro set di dati in due gruppi, in cui i prezzi per il gruppo A sono (50, 60 e 70) e i prezzi per il gruppo B sono (50, 55, 60), il gruppo B ha la varianza più bassa - cioè, sono vicini. Ovviamente la varianza non può essere negativa (perché dopo aver sommato le distanze di ogni punto dalla media, lo si piazza) ma la differenza di varianza può certamente essere.

Per vedere come questo si riferisce a Entropia di informazioni/Guadagno di informazioni, supponiamo di non prevedere il prezzo ma qualcos'altro, ad esempio se il visitatore del nostro sito diventerà un utente registrato o un abbonato premium o nessuno dei due. La variabile indipedente qui è discreta, non continua come il prezzo, quindi non è possibile calcolare la varianza in modo significativo. L'entropia delle informazioni è invece ciò che viene utilizzato. (Se dubitate della stretta analogia qui tra varianza e IE, dovreste sapere che la maggior parte degli algoritmi per le decisioni decisionali in grado di gestire variabili discrete e continue, in quest'ultimo caso, l'algoritmo utilizzerà la varianza come criterio di scissione, piuttosto che usare IG.)

In ogni caso, dopo aver calcolato l'entropia di informazioni per un dato nodo, si suddividono i dati su quel nodo (che è l'intero set di dati se si è nel nodo radice) su ogni valore per ogni variabile, poi per ogni divisione, calcola l'IE per entrambi i gruppi e prendi la media ponderata di IE. Quindi prendi la divisione che risulta nella IE media ponderata più bassa e confrontala con il nodo IE (che ovviamente è solo un singolo gruppo). Se la media ponderata IE per la suddivisione è inferiore a il nodo IE, quindi si suddividono i dati su quel nodo (formando un ramo), in caso contrario, si interrompe, ovvero, quel nodo non può essere ulteriormente suddiviso - sei in fondo.

In sintesi, il cuore dell'algoritmo dell'albero decisionale è il criterio per determinare se suddividere un nodo, ovvero come sono costruiti. Questo criterio è se l'IG è positivo o negativo.

Answer 3

Per chiunque incontri questa domanda, nonostante la sua età, offro questa risposta e consiglio.

Innanzitutto, la risposta è no, non può essere negativa. La peggiore possibilità in assoluto non è un cambiamento, o un IG di zero. Se vuoi delle prove, vai a cercare le prove complete su MathOverFlow come ha fatto notare Amro.

Ora per il consiglio. Se si esegue solo il primo livello di un albero decisionale, sembra ovvio che non si presenterà mai negativo. Tuttavia, quando ho costruito il mio primo albero utilizzando il guadagno di informazioni, mi sono trovato con un guadagno negativo dalla mia terza ramificazione. Questo non mi è sembrato utile o possibile, quindi mi sono affrettato a controllare i miei calcoli. La matematica andava bene. La parte che avevo errata era la prima parte della formula di base. Stavo usando la risposta dal livello superiore come mia entropia iniziale, ma questo è sbagliato perché include informazioni provenienti da altri set di dati. È necessario assicurarsi che per l'entropia di partenza si determini l'entropia per quel ramo da solo! Ciò significa che la tua "entropia iniziale" potrebbe effettivamente essere più alta di quanto non fosse al livello precedente a questa.

In altre parole, quando si calcola l'IG, assicurarsi di utilizzare solo il set di dati corrente.