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

Die Entropie ist die Summe der Wahrscheinlichkeit jedes Etiketts mit der Protokollwahrscheinlichkeit desselben Etiketts

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

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, zu lernen , Vornamen in männliche / weibliche Gruppen einzuteilen . Das ist eine Liste von Namen, die jeweils entweder mit moder gekennzeichnet fsind. Wir möchten ein Modell lernen , das zu den Daten passt und verwendet werden kann, um das Geschlecht eines neuen unsichtbaren Vornamens vorherzusagen.

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

Der erste Schritt besteht darin, zu entscheiden, welche Merkmale der Daten für die Zielklasse relevant sind, die wir vorhersagen möchten. Einige Beispielfunktionen umfassen: erster / letzter Buchstabe, Länge, Anzahl der Vokale, endet er mit einem Vokal usw. Nach der Merkmalsextraktion sehen unsere Daten also wie folgt 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

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 wird, und wir gehen je nach Testergebnis nach links oder rechts. Wir durchqueren den Baum so lange, bis wir einen Blattknoten erreichen, der die Klassenvorhersage enthält ( moderf )

Wenn wir also den Namen Amro in diesem Baum ausführen , testen wir zunächst " Ist die Länge <7? " Und die Antwort lautet " Ja ". Also gehen wir diesen Zweig hinunter. Nach der Verzweigung wird der nächste Test " Ist die Anzahl der Vokale <3? " Erneut als wahr ausgewertet . Dies führt zu einem beschrifteten Blattknoten m, und daher ist die Vorhersage männlich (was ich zufällig bin, also hat der Baum das Ergebnis korrekt vorhergesagt ).

Der Entscheidungsbaum wird von oben nach unten erstellt. Die Frage ist jedoch, wie Sie auswählen, welches Attribut an jedem Knoten aufgeteilt werden soll. Die Antwort lautet: Finden Sie die Funktion, die die Zielklasse am besten in die reinsten untergeordneten Knoten aufteilt (dh Knoten, die keine Mischung aus männlichen und weiblichen Knoten enthalten, sondern reine Knoten mit nur einer Klasse).

Dieses Maß an Reinheit wird als Information bezeichnet . Es stellt die erwartete Menge an Informationen dar , die erforderlich wären, 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.

Die Entropie hingegen ist ein Maß für die Verunreinigung (im Gegenteil). Es ist für eine Binärklasse mit Wertena/ definiertbals:

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 ist p=1/2, was bedeutet, dass p(X=a)=0.5oder in ähnlicher Weise p(X=b)=0.5eine 50% / 50% ige Chance besteht, entweder aoder zu sein b(die Unsicherheit ist maximal). Die Entropiefunktion ist bei einem Minimum von Null, wenn die Wahrscheinlichkeit p=1oder p=0mit vollständiger Sicherheit ist ( p(X=a)=1oder p(X=a)=0letztere impliziert p(X=b)=1).

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

(Das login der Formel wird normalerweise als Logarithmus zur Basis 2 verwendet. )

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 können, hatten wir vor der Trennung 9 Männer und 5 Frauen, dh P(m)=9/14und P(f)=5/14. Nach der Definition der 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 anhand von zwei untergeordneten Zweigen betrachtet wurde. Im linken Zweig von ends-vowel=1haben wir:

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

und den richtigen Zweig von ends-vowel=0haben 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

Durch Vergleichen der Entropie vor und nach der Aufteilung erhalten wir nun ein Maß für den Informationsgewinn oder wie viele Informationen wir durch die Aufteilung mit diesem bestimmten Merkmal gewonnen haben:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Sie können die obige Berechnung wie folgt interpretieren: Durch die Aufteilung mit dem end-vowelsFeature konnten wir die Unsicherheit im Ergebnis der Unterbaumvorhersage um einen kleinen Betrag von 0,1518 (gemessen in Bits als Informationseinheiten ) reduzieren .

An jedem Knoten des Baums wird diese Berechnung für jedes Merkmal durchgeführt, und das Merkmal mit dem größten Informationsgewinn wird für die Aufteilung auf gierige Weise ausgewählt (wodurch Merkmale bevorzugt werden, die reine erzeugen Teilungen mit geringer Unsicherheit / Entropie ). Dieser Prozess wird vom Stammknoten abwärts rekursiv angewendet und stoppt, wenn ein Blattknoten Instanzen enthält, die alle dieselbe Klasse haben (keine weitere Aufteilung erforderlich).

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

Zunächst wäre es am besten zu verstehen the measure of information.

Wie machen wir measuredie Informationen?

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 dies zu quantifizieren interesting-ness, sollte die Funktion erfüllt sein

• 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, werden one bitInformationen gegeben.

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 das Gerät ist in bit, das gleiche Bit Computer verwendet. 0 oder 1.

Beispiel 1

Fairer Münzwurf:

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

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

Beispiel 2

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

Wenn die Sonne morgen aufgeht, p ~ 1 es 0 Informationen.

Entropie

Wenn wir also die Erwartung interesting-nesseines Ereignisses annehmen Y, dann ist es die Entropie. dh Entropie ist ein erwarteter Wert für die Interessantheit eines Ereignisses.

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

Formal 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.

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 Vermutung könnte ein Bit pro Tag sein. Aber was ist, wenn wir Blau hinzufügen, sodass der Absender drei Optionen hat? Wir möchten ein Maß an Informationen haben, das andere Dinge als Zweierpotenzen verarbeiten kann, aber dennoch additiv ist (die Art und Weise, wie die Anzahl möglicher Nachrichten mit zwei multipliziert wird) fügt ein Bit hinzu). Wir könnten dies tun, indem wir Protokoll _{2 nehmen} (Anzahl möglicher Nachrichten) nehmen, aber es stellt sich heraus, dass es einen allgemeineren Weg gibt.

Angenommen, wir sind wieder rot / grün, aber die rote Glühbirne ist durchgebrannt (dies ist allgemein bekannt), sodass die Lampe immer grün blinken muss. Der Kanal ist jetzt nutzlos, wir wissen, was der nächste Blitz sein wirdDie Blitze vermitteln also keine Informationen, keine Nachrichten. Jetzt reparieren wir die Glühbirne, legen aber die Regel fest, dass die rote Glühbirne nicht zweimal hintereinander blinken darf. Wenn die Lampe rot blinkt, wissen wir, wie der nächste Blitz aussehen 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 (kontextfrei) ist, grüne Blitze jedoch häufiger auftreten als rote: Je verzerrter die Wahrscheinlichkeit, desto weniger Bits benötigen Sie zur Beschreibung der Sequenz und desto weniger Informationen enthält sie bis zum Vollgrüne, durchgebrannte Glühbirnengrenze.

Es stellt sich heraus, dass es eine Möglichkeit gibt, die Informationsmenge in einem Signal basierend auf den Wahrscheinlichkeiten der verschiedenen Symbole zu messen. Wenn die Wahrscheinlichkeit, das Symbol x _{i zu} empfangen, p _{i ist} , berücksichtigen Sie die Menge

-log p i

Je kleiner p _{i ist} , desto größer ist dieser Wert. Wenn x _i 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 summieren:

I = -Σ p i log (p i )

Dies ist der Informationsgehalt in einem Blitz.

Rote Glühbirne durchgebrannt: p rot = 0, p grün = 1, I = - (0 + 0) = 0
Rot und Grün gleich wahrscheinlich: p rot = 1/2, p grün = 1/2 , I = - (2 * 1/2 * log (1/2)) = log (2)
Drei Farben, gleich wahrscheinlich: p i = 1/3, I = - (3 * 1/3 * log (1/3)) = log (3)
Grün und Rot, Grün doppelt so wahrscheinlich: p rot = 1/3 , p grü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 Protokoll ₂ und erhalten Bits.

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

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

Diese Inferenzmethoden sind wirklich viel allgemeiner als nur Text Mining, und ich kann mir nicht wirklich vorstellen, wie man lernen würde, wie man dies auf NLP anwendet, ohne einige der allgemeinen Grundlagen zu lernen, die in diesem Buch oder 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, 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 übertragen können, gleich der Entropie des Rauschprozesses ist. Es gibt auch einen Satz, der verbindet, wie viel Sie ein Datenelement komprimieren können, um den minimal möglichen Speicherplatz in Ihrem Computer zu belegen, mit der Entropie des Prozesses, der die Daten generiert hat.

Ich denke nicht, dass es wirklich notwendig ist, dass Sie sich mit all diesen Theoremen der Kommunikationstheorie vertraut machen, 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 Informationen und Schlussfolgerungen steht usw. ...

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.

Informell

Entropie ist die Verfügbarkeit von Informationen oder Wissen. Mangelnde Informationen führen zu Schwierigkeiten bei der Vorhersage der Zukunft, die eine hohe Entropie darstellt (Vorhersage des nächsten Wortes im Text Mining), und die Verfügbarkeit von Informationen / Wissen hilft uns, die Zukunft realistischer vorherzusagen (niedrige Entropie).

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

Formal

Entropie ist mangelnde Ordnung der Vorhersagbarkeit

Wenn Sie ein Buch über NLTK lesen, wäre es interessant, wenn Sie das MaxEnt Classifier Module lesen http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Für die Klassifizierung von Text Mining können folgende Schritte erforderlich sein: Vorverarbeitung (Tokenisierung, Dämpfen, Merkmalsauswahl mit Informationsgewinn ...), Umwandlung in numerisch (Frequenz oder TF-IDF) (ich denke, dies ist der wichtigste Schritt, den Sie bei der Verwendung verstehen müssen Text als Eingabe für einen Algorithmus, der nur numerische Werte akzeptiert) und anschließend mit MaxEnt klassifiziert. Dies ist nur ein Beispiel.