Che cosa è “l'entropia e le informazioni di guadagno”?

StackOverflow https://stackoverflow.com/questions/1859554

Domanda

Sto leggendo questo libro (NLTK) ed è fonte di confusione. Entropia è definito come:

L'entropia è la somma delle probabilità di ogni etichetta volte il registro di probabilità che la stessa etichetta

Come posso applicare entropia e massima entropia in termini di text mining?Qualcuno può dare un semplice esempio (visual)?

È stato utile?

Soluzione

Presumo che l'entropia è stato menzionato nel contesto della costruzione di alberi di decisione.

Per illustrare, immaginare il compito di di apprendimento per classificare primi-nomi a maschio/femmina gruppi.Che è dato un elenco di nomi di ogni etichettato con m o f, vogliamo imparare modello che si adatta ai dati e può essere utilizzato per prevedere il sesso di un nuovo invisibile primo nome.

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

Il primo passo è decidere cosa caratteristiche i dati sono rilevanti per la classe di destinazione vogliamo prevedere.Alcuni esempi di funzionalità includono:prima/ultima lettera, la lunghezza, il numero di vocali, finisce con una vocale, ecc..Così, dopo l'estrazione delle caratteristiche, i nostri dati, assomiglia a questo:

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

L'obiettivo è quello di costruire un albero di decisione.Un esempio di un albero sarebbe:

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

in pratica ogni nodo rappresentano un test eseguito su un singolo attributo, e andiamo a sinistra o a destra a seconda del risultato del test.Osserviamo che attraversano la struttura fino a quando non si raggiunge un nodo foglia che contiene la classe di stima (m o f)

Quindi, se si esegue il nome Amro giù questo albero, iniziamo con i test "è la lunghezza<7?"e la risposta è sì, così andiamo giù quel ramo.Di seguito il ramo, il prossimo test "è il numero di vocali<3?"di nuovo restituisce vero.Questo porta ad un nodo foglia con etichetta m, e , quindi, la previsione è maschio (che mi capita di essere, così l'albero predetto l'esito correttamente).

L'albero di decisione è costruito in un top-down, ma la domanda è: come si fa a scegliere quale attributo di dividere a ogni nodo?La risposta è: trovare la funzione che meglio si divide la classe di destinazione nel più puro possibile nodi figli (ie:i nodi che non contengono un mix di maschile e femminile, piuttosto puro nodi con una sola classe).

Questa misura di purezza è chiamato il informazioni.Esso rappresenta il previsto quantità di informazioni che sarebbero necessari per specificare se una nuova istanza (primo nome) dovrebbe essere classificato maschio o femmina, dato l'esempio che ha raggiunto il nodo.Si calcola che in base al numero di maschi e femmine classi di nodo.

Entropia d'altra parte è una misura di impurità (l'opposto).Esso è definito per un binario di classe con i valori a/b come:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

Questo entropia binaria funzione è raffigurato nella figura sottostante (variabile casuale può assumere uno dei due valori).Raggiunge il suo massimo quando la probabilità è p=1/2, il che significa che p(X=a)=0.5 o allo stesso modop(X=b)=0.5 avere un 50%/50% di probabilità di essere a o b (l'incertezza è massima).L'entropia funzione è a zero, il minimo la probabilità è p=1 o p=0 con assoluta certezza (p(X=a)=1 o p(X=a)=0 rispettivamente, ultimo implica p(X=b)=1).

https://en.wikipedia.org/wiki/File:Binary_entropy_plot.svg

Naturalmente, la definizione di entropia può essere generalizzata per una variabile casuale discreta X con N risultati (non solo due):

entropy

(il log la formula è di solito presa come logaritmo in base 2)

Torniamo al nostro compito di nome classifica, vediamo un esempio.Immaginare che, a un certo punto durante il processo di costruzione dell'albero, abbiamo preso in considerazione la seguente divisione:

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

Come si può vedere, prima della divisione abbiamo avuto 9 maschi e 5 femmine, cioè P(m)=9/14 e P(f)=5/14.Secondo la definizione di entropia:

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

Accanto ci si confronta con l'entropia calcolata considerando la divisa da due rami figlio.Nel ramo di sinistra di ends-vowel=1, abbiamo:

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

e il ramo di destra ends-vowel=0, abbiamo:

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

Uniamo la sinistra/destra entropie utilizzando il numero di istanze giù ogni ramo fattore peso (7 casi andati a sinistra, e 7 istanze è andato a destra), e di ottenere il finale di entropia dopo la divisione:

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

Ora, confrontando l'entropia prima e dopo la divisione, si ottiene una misura di l'information gain, o come quantità di informazioni che abbiamo guadagnato facendo la divisione utilizzando quella particolare caratteristica:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Si può interpretare il calcolo di cui sopra come segue:facendo la divisione con il end-vowels funzione, siamo stati in grado di ridurre l'incertezza nel sotto-albero di previsione risultato di una piccola quantità di 0.1518 (misurata in bit come unità di informazione).

Ad ogni nodo dell'albero, questo calcolo è effettuato per ogni funzione, e la funzione con l' maggiori informazioni guadagno viene scelto per la divisione in avido modo (in modo da favorire la funzionalità che producono puro divide con bassa incertezza/entropia).Questo processo viene applicato ricorsivamente dalla radice-nodo, e si ferma quando un nodo foglia contiene le istanze di tutti con la stessa classe (non c'è bisogno di dividere ulteriormente).

Nota che ho saltato alcune dettagli che sono oltre la portata di questo post, compreso il modo di gestire numerici caratteristiche, i valori mancanti, l'overfitting e potatura alberi, ecc..

Altri suggerimenti

Per cominciare, sarebbe meglio per capire the measure of information.

Come facciamo measure le informazioni?

Quando qualcosa di improbabile accade, si può dire che è una grande notizia.Inoltre, quando si dice qualcosa di prevedibile, non è davvero interessante.Quindi, per quantificare questo interesting-ness, la funzione deve soddisfare

  • se la probabilità dell'evento è di 1 (prevedibile), quindi la funzione dà 0
  • se la probabilità dell'evento è vicino a 0, allora la funzione deve dare elevato numero
  • se la probabilità 0.5 eventi accade dare one bit di informazioni.

Una misura naturale che soddisfano i vincoli di

I(X) = -log_2(p)

dove p è la probabilità dell'evento X.E l'unità è in bit, la stessa bit computer utilizza.0 o 1.

Esempio 1

Fiera di coin flip :

La quantità di informazioni che possiamo ottenere da un coin flip?

Risposta : -log(p) = -log(1/2) = 1 (bit)

Esempio 2

Se un meteorite colpisce la Terra domani, p=2^{-22} quindi siamo in grado di ottenere un campione di 22 bit di informazione.

Se il Sole sorge domani, p ~ 1 quindi è 0 bit di informazione.

Entropia

Quindi, se prendiamo l'attesa interesting-ness di un evento Y, che poi è l'entropia.cioèl'entropia è un valore atteso di interessante-ness di un evento.

H(Y) = E[ I(Y)]

Più formalmente, l'entropia è il numero di bit di un evento.

Esempio

Y = 1 :un evento X si verifica con probabilità p

Y = 0 :un evento X non si verifica con probabilità 1-p

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
     = - p log p - (1-p) log (1-p)

Log in base 2 di log di tutti.

Non posso darti la grafica, ma forse mi può dare una chiara spiegazione.

Supponiamo di avere un canale di informazione, come una luce che lampeggia una volta ogni giorno, rossa o verde.La quantità di informazioni che vuol trasmettere?La prima ipotesi potrebbe essere un po ' al giorno.Ma cosa succede se aggiungiamo blu, in modo che il mittente ha tre opzioni?Ci piacerebbe avere una misura di informazioni in grado di gestire altre cose rispetto a potenze di due, ma ancora essere additivo (il modo in cui moltiplicando il numero di possibili messaggi da due aggiunge un po').Si potrebbe fare questo prendendo registro2(numero di possibili messaggi), ma si scopre che c'è un modo più generale.

Supponiamo che siamo di nuovo in rosso e in verde, ma rosso lampadina si è bruciata (questa è conoscenza comune) in modo che la lampada deve sempre lampeggiare in verde.Il canale è ora inutile, sappiamo che il prossimo flash sarà così i lampi trasmettere nessuna informazione, nessuna notizia.Ora abbiamo riparare il bulbo ma imporre una regola che la lampadina rossa potrebbe non flash due volte in una riga.Quando la spia lampeggia in rosso, sappiamo che il prossimo flash sarà.Se si tenta di inviare un flusso di bit da questo canale, troverete che è necessario codificare con lampi di quello che hai a bit (il 50% in più, in realtà).E se si vuole descrivere una sequenza di lampeggi, è possibile farlo con un minor numero di bit.Lo stesso vale se ogni flash è indipendente (context-free), ma lampi verdi sono più comuni di rosso:il più inclinata la probabilità minore è il numero di bit necessari per descrivere la sequenza, e la meno informazioni che contiene tutto il senso al tutto-verde, la lampadina bruciata limite.

Si scopre che c'è un modo per misurare la quantità di informazioni in un segnale, basato sulla probabilità dei simboli diversi.Se la probabilità di ricevere simbolo xio è pio, quindi prendere in considerazione la quantità

-log pio

La più piccola pio, il più grande di questo valore.Se xio diventa due volte più improbabile, questo valore aumenta di una quantità fissa (log(2)).Questo dovrebbe ricordare di aggiungere un bit di un messaggio.

Se non sappiamo che cosa il simbolo sarà (ma sappiamo che la probabilità), si può calcolare la media di questo valore, quanto si ottiene, sommando le varie possibilità:

I = -Σ pio log(pio)

Questo è il contenuto informativo in un flash.

Red bulb burnt out: prosso = 0, pverde=1, I = -(0 + 0)  = 0
Red and green equiprobable: prosso = 1/2, pverde = 1/2, I = -(2 * 1/2 * log(1/2)) = log(2)
Three colors, equiprobable: pio=1/3, I = -(3 * 1/3 * log(1/3)) = log(3)
Green and red, green twice as likely: prosso=1/3, pverde=2/3, I = -(1/3 log(1/3) + 2/3 log(2/3)) = log(3) - 2/3 log(2)

Questo è il contenuto delle informazioni, o l'entropia del messaggio.È massima quando i diversi simboli sono equiprobabili.Se sei un fisico si utilizza il logaritmo naturale, se sei un informatico si utilizzi il log2 e avere piccole.

Vi consiglio davvero di leggere Informazioni in Teoria, metodi bayesiani e MaxEnt.Il punto di partenza è questo (è liberamente disponibile online) libro di David Mackay:

http://www.inference.phy.cam.ac.uk/mackay/itila/

Quei metodi di inferenza sono davvero molto più generale rispetto a solo il text mining e non riesco a concepire come si possa imparare come applicare questo alla PNL, senza possibilità di imparare alcune delle nozioni di base contenute in questo libro o altri introduttivo libri di Machine Learning e di MaxEnt metodi bayesiani.

La connessione tra entropia e probabilità, la teoria di informazioni, l'elaborazione e la memorizzazione è davvero molto, molto profondo.Per dare un assaggio di esso, c'è un teorema dovuto a Shannon, che afferma che la massima quantità di informazioni che è possibile passare senza errore tramite un rumoroso canale di comunicazione è uguale all'entropia del processo di rumore.C'è anche un teorema che si collega a quanto si può comprimere un pezzo di dati per occupare il minimo possibile di memoria nel computer di entropia del processo che ha generato i dati.

Io non credo che sia davvero necessario che si va a conoscere tutti quei teoremi sulla teoria della comunicazione, ma non è possibile imparare questa, senza possibilità di imparare le nozioni di base su ciò che è l'entropia, come è calcolato, qual è il suo rapporto con l'informazione e l'inferenza, ecc...

Quando avevo l'implementazione di un algoritmo per calcolare l'entropia di un immagine che ho trovato questi link, vedere qui e qui.

Questo è il pseudo-codice che ho usato, è necessario adattarsi a lavorare con il testo, piuttosto che immagini ma il principio dovrebbe essere lo stesso.

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)

Ho ottenuto questo codice da qualche parte, ma non riesco a scavare il link.

In modo informale

entropia è la disponibilità di informazioni o conoscenze, la Mancanza di informazioni porta a difficoltà nella previsione del futuro, che è ad alta entropia (parola successiva previsione di text mining) e la disponibilità di informazioni/conoscenza ci aiuterà più realistica previsione del futuro (bassa entropia).

Pertinenti informazioni di qualsiasi tipo ridurre l'entropia e ci aiuta a prevedere più realistico futuro, che le informazioni possono essere parola "carne" è presente nella frase o la parola "carne" non è presente.Questo è chiamato L'Information Gain

Formalmente

entropia è la mancanza di un ordine di predicability

Come la lettura di un libro su NLTK sarebbe interessante leggere su MaxEnt Modulo di Classificatore http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Per il text mining classificazione la procedura potrebbe essere:pre-elaborazione (tokenizzazione, cottura a vapore, funzione di selezione con Informazioni di Guadagno ...), la trasformazione numerici (frequenza o TF-IDF) (penso che questo è il passaggio chiave per capire quando utilizzare il testo come input per un algoritmo che accettano solo numerico) e quindi classificare con MaxEnt, sicuro che questo è solo un esempio.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top