wake-up-neo.com

Was ist "Entropie und Informationsgewinn"?

Ich lese dieses Buch ( NLTK ) und es ist verwirrend. Entropie ist definiert als :

Die Entropie ist die Summe der Wahrscheinlichkeit jedes Etiketts multipliziert mit der Log-Wahrscheinlichkeit desselben Etiketts

Wie kann ich Entropie und maximale Entropie in Bezug auf Text Mining anwenden? Kann mir jemand ein einfaches Beispiel geben (visuell)?

329
TIMEX

Ich gehe davon aus, dass Entropie im Zusammenhang mit der Erstellung von Entscheidungsbäumen erwähnt wurde.

Stellen Sie sich zur Veranschaulichung die Aufgabe vor, LernenEinteilen von Vornamen in männliche/weibliche Gruppen. Das ist eine Liste von Namen, die entweder mit m oder f beschriftet sind. Wir möchten ein Modell lernen, das zu den Daten passt und zur Vorhersage des Geschlechts verwendet werden kann eines neuen unsichtbaren Vornamens.

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

Der erste Schritt ist Entscheiden Welche Merkmale der Daten sind für die Zielklasse relevant, die wir möchten vorhersagen. Einige Beispiele für Features sind: erster/letzter Buchstabe, Länge, Anzahl der Vokale, endet es mit einem Vokal usw. Nach der Feature-Extraktion sehen unsere Daten folgendermaßen aus:

# 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

Das Ziel ist es, einen Entscheidungsbaum zu erstellen. Ein Beispiel für einen Baum wäre:

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

grundsätzlich stellt jeder Knoten einen Test dar, der für ein einzelnes Attribut durchgeführt wurde, und wir gehen je nach Ergebnis des Tests nach links oder rechts. Wir durchlaufen den Baum so lange, bis wir einen Blattknoten erreichen, der die Klassenvorhersage enthält (m oder f)

Wenn wir also den Namen Amro über diesen Baum laufen lassen, testen wir zunächst " ist die Länge <7?" und die Antwort lautet ja , also gehen wir diesen Ast runter. Nach der Verzweigung ergibt der nächste Test " ist die Anzahl der Vokale <3?" erneut wahr. Dies führt zu einem Blattknoten mit der Bezeichnung m, und daher ist die Vorhersage männlich (was ich zufällig bin, also hat der Baum das Ergebnis vorhergesagt richtig ).

Der Entscheidungsbaum ist von oben nach unten aufgebaut , aber die Frage ist, wie Sie auswählen, welches Attribut an jedem Knoten aufgeteilt werden soll. Die Antwort ist, die Funktion zu finden, die die Zielklasse am besten in möglichst reine Kinderknoten aufteilt (dh Knoten, die keine Mischung aus männlichen und weiblichen, eher reinen Knoten mit nur einer Klasse enthalten).

Dieses Maß für Reinheit wird als Information bezeichnet. Es stellt die erwartete Menge an Informationen dar, die erforderlich wäre, um anzugeben, ob eine neue Instanz (Vorname) anhand des Beispiels, das den Knoten erreicht hat, als männlich oder weiblich klassifiziert werden soll . Wir berechnen es basierend auf der Anzahl der männlichen und weiblichen Klassen am Knoten.

Entropie ist dagegen ein Maß für Verunreinigung (das Gegenteil). Es ist für eine Binärklasse mit den Werten a/b definiert als:

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

Diese binäre Entropiefunktion ist in der folgenden Abbildung dargestellt (Zufallsvariable kann einen von zwei Werten annehmen). Es erreicht sein Maximum, wenn die Wahrscheinlichkeit p=1/2 Ist, was bedeutet, dass p(X=a)=0.5 oder ähnlich p(X=b)=0.5 eine 50%/50% ige Chance hat, entweder a oder zu sein b (die Unsicherheit ist maximal). Die Entropiefunktion ist auf dem Minimum Null, wenn die Wahrscheinlichkeit mit vollständiger Sicherheit p=1 Oder p=0 Ist (p(X=a)=1 oder p(X=a)=0, letzteres impliziert p(X=b)=1).

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

Natürlich kann die Definition der Entropie für eine diskrete Zufallsvariable X mit N Ergebnissen (nicht nur zwei) verallgemeinert werden:

entropy

(das log in der Formel wird normalerweise als Logarithmus zur Basis 2 ) genommen


Zurück zu unserer Aufgabe der Namensklassifizierung, schauen wir uns ein Beispiel an. Stellen Sie sich vor, wir haben irgendwann während der Erstellung des Baums die folgende Aufteilung in Betracht gezogen:

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

Wie Sie sehen, hatten wir vor der Trennung 9 Männer und 5 Frauen, d. H. P(m)=9/14 und P(f)=5/14. Nach der Definition von Entropie:

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

Als nächstes vergleichen wir es mit der Entropie, die berechnet wurde, nachdem die Aufteilung durch Betrachten von zwei untergeordneten Zweigen berücksichtigt wurde. Im linken Zweig von ends-vowel=1 Haben wir:

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

und den rechten Zweig von ends-vowel=0 haben wir:

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

Wir kombinieren die linken/rechten Entropien unter Verwendung der Anzahl der Instanzen in jedem Zweig als Gewichtsfaktor (7 Instanzen gingen nach links und 7 Instanzen gingen nach rechts) und erhalten die endgültige Entropie nach der Aufteilung:

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

Wenn wir nun die Entropie vor und nach der Teilung vergleichen, erhalten wir ein Maß für Informationsgewinn , oder wie viel Information wir gewonnen haben indem Sie die Aufteilung mit dieser speziellen Funktion durchführen:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Sie können die obige Berechnung folgendermaßen interpretieren: Durch die Aufteilung mit der Funktion end-vowels Konnten wir die Unsicherheit im Ergebnis der Unterbaumvorhersage um einen kleinen Betrag von 0,1518 (gemessen in - Bits als Informationseinheiten ).

An jedem Knoten des Baumes wird diese Berechnung für jedes Merkmal durchgeführt und das Merkmal mit dem größten Informationsgewinn wird für die Aufteilung auf eine gierige Weise ausgewählt (also Bevorzugung von Merkmalen, die pure splitten mit geringer Unsicherheit/Entropie). Dieser Prozess wird rekursiv vom Wurzelknoten abwärts angewendet und stoppt, wenn ein Blattknoten Instanzen enthält, die alle dieselbe Klasse haben (es ist nicht erforderlich, sie weiter aufzuteilen).

Beachten Sie, dass ich einige Details übersprungen habe, die über den Rahmen dieses Beitrags hinausgehen, einschließlich des Umgangs mit numerischen Funktionen , fehlenden Werten , Überanpassung und Beschneiden Bäume, etc ..

1032
Amro

Zunächst ist es am besten, the measure of information Zu verstehen.

Wie können wir die Informationen measure?

Wenn etwas Unwahrscheinliches passiert, sagen wir, dass es eine große Neuigkeit ist. Auch wenn wir etwas Vorhersehbares sagen, ist es nicht wirklich interessant. Um diesen interesting-ness Zu quantifizieren, sollte die Funktion erfüllen

  • wenn die Wahrscheinlichkeit des Ereignisses 1 ist (vorhersehbar), gibt die Funktion 0
  • wenn die Wahrscheinlichkeit des Ereignisses nahe bei 0 liegt, sollte die Funktion eine hohe Zahl ergeben
  • wenn Ereignisse mit einer Wahrscheinlichkeit von 0,5 auftreten, erhalten Sie one bit Informationen.

Eine natürliche Maßnahme, die die Einschränkungen erfüllt, ist

I(X) = -log_2(p)

dabei ist p die Wahrscheinlichkeit des Ereignisses X. Und die Einheit befindet sich in bit, das gleiche Bit, das der Computer verwendet. 0 oder 1.

Beispiel 1

Fairer Münzwurf:

Wie viele Informationen können wir mit einem Münzwurf erhalten?

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

Beispiel 2

Wenn morgen ein Meteor die Erde trifft, p=2^{-22}, Können wir 22 Bits an Informationen erhalten.

Wenn die Sonne morgen aufgeht, ist p ~ 1 Eine Information von 0 Bit.

Entropie

Nehmen wir also die Erwartung an interesting-ness Eines Ereignisses Y, dann ist es die Entropie. die Entropie ist ein erwarteter Wert der Interessantheit eines Ereignisses.

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

Genauer gesagt ist die Entropie die erwartete Anzahl von Bits eines Ereignisses.

Beispiel

Y = 1: Ein Ereignis X tritt mit der Wahrscheinlichkeit p auf

Y = 0: Ein Ereignis X tritt nicht mit der Wahrscheinlichkeit 1-p auf

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

Protokollbasis 2 für alle Protokolle.

41
VforVitamin

Ich kann Ihnen keine Grafiken geben, aber vielleicht kann ich eine klare Erklärung geben.

Angenommen, wir haben einen Informationskanal, z. B. ein Licht, das jeden Tag einmal rot oder grün blinkt. Wie viele Informationen vermittelt es? Die erste Schätzung könnte ein bisschen pro Tag sein. Was aber, wenn wir Blau hinzufügen, damit der Absender drei Optionen hat? Wir möchten ein Maß an Informationen haben, das mit anderen Dingen als Zweierpotenzen umgehen kann, aber dennoch additiv ist (die Art und Weise, wie die Anzahl der möglichen Nachrichten mit zwei multipliziert wird addiert ein Bit). Wir könnten dies tun, indem wir das Protokoll nehmen2(Anzahl der möglichen Nachrichten), aber es stellt sich heraus, dass es einen allgemeineren Weg gibt.

Angenommen, wir sind wieder in Rot/Grün, aber die rote Lampe ist durchgebrannt (das ist allgemein bekannt), sodass die Lampe immer grün blinken muss. Der Kanal ist jetzt unbrauchbar, wir wissen, was der nächste Blitz sein wird damit die Blitze keine Informationen, keine Nachrichten übermitteln. Jetzt reparieren wir die Glühbirne, schreiben aber vor, dass die rote Glühbirne nicht zweimal hintereinander blinken darf. Wenn die Lampe rot blinkt, wissen wir, was der nächste Blitz sein wird. Wenn Sie versuchen, einen Bitstrom über diesen Kanal zu senden, müssen Sie ihn mit mehr Blitzen codieren, als Sie Bits haben (tatsächlich 50% mehr). Und wenn Sie eine Folge von Blitzen beschreiben möchten, können Sie dies mit weniger Bits tun. Gleiches gilt, wenn jeder Blitz unabhängig ist (kontextfrei), aber grüne Blitze häufiger sind als rote: Je verzerrter die Wahrscheinlichkeit, desto weniger Bits müssen Sie für die Beschreibung der Sequenz und je weniger Informationen sie enthalten, bis hin zum Vollgrüne, durchgebrannte Begrenzung.

Es hat sich herausgestellt, dass es eine Möglichkeit gibt, die Informationsmenge in einem Signal basierend auf den Wahrscheinlichkeiten der verschiedenen Symbole zu messen. Wenn die Wahrscheinlichkeit des Empfangs des Symbols xich ist pich, dann überlegen Sie sich die Menge

 - log pich

Der kleinere pichJe größer dieser Wert ist. Wenn xich doppelt so unwahrscheinlich wird, erhöht sich dieser Wert um einen festen Betrag (log (2)). Dies sollte Sie daran erinnern, einer Nachricht ein Bit hinzuzufügen.

Wenn wir nicht wissen, wie das Symbol aussehen wird (aber wir kennen die Wahrscheinlichkeiten), können wir den Durchschnitt dieses Wertes berechnen, wie viel wir erhalten, indem wir die verschiedenen Möglichkeiten aufsummieren:

 I = - & # 931 pich log (pich) 

Dies ist der Informationsgehalt in einem Blitz.

 Rote Glühbirne durchgebrannt: prot = 0, pgrün= 1, I = - (0 + 0) = 0 
 Rot und Grün gleich wahrscheinlich: prot = 1/2, pgrün = 1/2, I = - (2 * 1/2 * log (1/2)) = log (2) 
 Drei Farben, gleich wahrscheinlich: pich= 1/3, I = - (3 * 1/3 * log (1/3)) = log (3) 
 Grün und rot, grün doppelt so wahrscheinlich: prot= 1/3, pgrün= 2/3, I = - (1/3 log (1/3) + 2/3 log (2/3)) = log (3) - 2/3 log (2) 

Dies ist der Informationsgehalt oder die Entropie der Nachricht. Es ist maximal, wenn die verschiedenen Symbole gleich wahrscheinlich sind. Wenn Sie Physiker sind, verwenden Sie das natürliche Protokoll, wenn Sie Informatiker sind, verwenden Sie das Protokoll2 und Bits bekommen.

21
Beta

Ich empfehle Ihnen wirklich, über Informationstheorie, Bayes'sche Methoden und MaxEnt zu lesen. Der Ausgangspunkt ist dieses (online frei erhältliche) Buch von David Mackay:

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

Diese Inferenzmethoden sind sehr viel allgemeiner als nur Text Mining, und ich kann mir nicht wirklich vorstellen, wie man dies auf NLP anwenden kann, ohne einige der allgemeinen Grundlagen zu lernen, die in diesem Buch oder in anderen einführenden Büchern über maschinelles Lernen und MaxEnt Bayesian enthalten sind Methoden.

Die Verbindung zwischen Entropie und Wahrscheinlichkeitstheorie zur Informationsverarbeitung und -speicherung ist wirklich sehr tief. Um einen Vorgeschmack darauf zu geben, gibt es einen Satz von Shannon, der besagt, dass die maximale Menge an Informationen, die Sie fehlerfrei über einen verrauschten Kommunikationskanal weitergeben können, gleich der Entropie des Rauschprozesses ist. Es gibt auch einen Satz, der angibt, wie viel Sie ein Datenelement komprimieren können, um so wenig Speicher wie möglich auf Ihrem Computer zu belegen, und der die Entropie des Prozesses angibt, der die Daten generiert hat.

Ich denke nicht, dass es wirklich notwendig ist, all diese Theoreme der Kommunikationstheorie kennenzulernen, aber es ist nicht möglich, dies zu lernen, ohne die Grundlagen darüber zu lernen, was Entropie ist, wie sie berechnet wird, in welcher Beziehung sie zu Information und Inferenz steht usw ...

informell

Entropie ist Verfügbarkeit von Informationen oder Wissen. Mangel an Informationen führt zu Schwierigkeiten bei der Vorhersage der Zukunft. Dies ist eine hohe Entropie (nächste Wortvorhersage in Text Mining). Die Verfügbarkeit von Informationen/Wissen wird uns dabei helfen, realistischere Vorhersagen zu treffen der Zukunft (niedrige Entropie).

Relevante Informationen jeglicher Art verringern die Entropie und helfen uns dabei, eine realistischere Zukunft vorherzusagen. Diese Informationen können sein, dass Wort "Fleisch" im Satz vorhanden ist oder Wort "Fleisch" nicht vorhanden ist. Dies wird Informationsgewinn genannt


Formal

Entropie ist ein Mangel an Vorhersagbarkeitsreihenfolge

4

Als ich einen Algorithmus zur Berechnung der Entropie eines Bildes implementierte, fand ich diese Links, siehe hier und hier .

Dies ist der Pseudocode, den ich verwendet habe. Sie müssen ihn anpassen, um mit Text und nicht mit Bildern zu arbeiten, aber die Prinzipien sollten dieselben sein.

//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)

Ich habe diesen Code von irgendwoher bekommen, aber ich kann den Link nicht ausgraben.

4
Matt Warren

Wenn Sie ein Buch über NLTK lesen, ist es interessant, dass Sie über das MaxEnt-Klassifizierungsmodul lesen http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Für die Text-Mining-Klassifizierung könnten die folgenden Schritte erforderlich sein: Vorverarbeitung (Tokenisierung, Dämpfen, Feature-Auswahl mit Information Gain ...), Umwandlung in numerische (Frequenz oder TF-IDF) (meiner Meinung nach ist dies der wichtigste Schritt, den Sie bei der Verwendung verstehen sollten Text als Eingabe für einen Algorithmus, der nur numerische Werte akzeptiert) und anschließend mit MaxEnt klassifiziert. Dies ist nur ein Beispiel.

0
Paulo