Qu'est-ce que « gain d'entropie et de l'information »?

Question

Je lis ce livre ( NLTK ) et il est source de confusion. Entropy est définie comme :

  

Entropy est la somme de la probabilité de chaque étiquette   fois la probabilité de journal de cette même étiquette

Comment puis-je appliquer entropie et entropie maximale en termes de text mining? Quelqu'un peut-il me donner un exemple simple, simple (visuel)?

Answer 1

Je suppose que l'entropie a été mentionné dans le cadre de la construction arbres de décision .

Pour illustrer, imaginez la tâche de href="https://en.wikipedia.org/wiki/Supervised_learning" apprentissage qui correspond aux données et peuvent être utilisées pour prédire le sexe d'un nouveau premier nom invisible.

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

La première étape est décider que caractéristiques des données sont pertinentes à la classe cible que nous voulons prévoir. Certaines fonctions par exemple les suivantes: première / dernière lettre, longueur, nombre de voyelles, il ne se termine par une voyelle, etc .. Ainsi, après extraction de caractéristiques, nos données ressemble à:

# 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

Le but est de construire un . Un exemple d'un serait:

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

essentiellement chaque noeud représente un test effectué sur un seul attribut, et nous allons à gauche ou à droite en fonction du résultat du test. Nous continuons à traverser l'arbre jusqu'à ce que nous atteignons un nœud feuille qui contient la prédiction de classe (ou m f)

Donc, si nous courons le nom Amro cet arbre, nous commençons par le test " est la longueur <7? " et la réponse est oui , donc nous nous engageons dans cette branche. À la suite de la branche, le test suivant " est le nombre de voyelles <3 " à nouveau évalué à true . Cela conduit à un nœud feuille marqué m, et donc la prédiction est mâle (que je trouve être, de sorte que l'arbre prédit le résultat correctement ).

L'arbre de décision est construit de façon descendante , mais est de savoir comment faire la question vous choisissez quel attribut à diviser à chaque noeud? La réponse est de trouver la fonction qui divise le mieux la classe cible dans les noeuds les plus purs possibles pour les enfants (par exemple: les noeuds qui ne contiennent pas un mélange des deux hommes et les femmes, les nœuds plutôt purs avec une seule classe).

Cette mesure de pureté est appelé informations . Il représente le montant rel="noreferrer"> attendue de Entropy d'autre part est une mesure de impureté (le contraire). Il est défini pour une classe binaire href="https://en.wikipedia.org/wiki/Binary_classification" avec des valeurs a / b comme:

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

est représenté sur la figure ci-dessous (variable aléatoire peut prendre l'une des deux valeurs). Elle atteint son maximum lorsque la probabilité est p=1/2, ce qui signifie que p(X=a)=0.5 ou similarlyp(X=b)=0.5 ayant un 50% / 50% de chances d'être soit a ou b (incertitude est maximale). La fonction d'entropie est à zéro minimum lorsque la probabilité est p=1 ou p=0 avec une certitude absolue (p(X=a)=1 ou p(X=a)=0 respectivement, celle-ci implique p(X=b)=1).

Bien sûr, la définition de l'entropie peut être généralisée à une variable aléatoire discrète X avec des résultats N (pas seulement deux):

(la log dans la formule est généralement considéré comme le logarithme du )

---

Retour à notre tâche de classification nom, permet de regarder un exemple. Imaginez à un moment donné au cours du processus de construction de l'arbre, nous envisageons la scission suivante:

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

Comme vous pouvez le voir, avant la scission que nous avions 9 hommes et 5 femmes, à savoir P(m)=9/14 et P(f)=5/14. Selon la définition de l'entropie:

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

Ensuite, nous comparer avec l'entropie calculée après avoir examiné la scission en regardant deux branches de l'enfant. Dans la branche gauche de ends-vowel=1, nous avons:

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

et la branche droite de ends-vowel=0, nous avons:

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

Nous combinons la gauche / droite entropies en utilisant le nombre de cas en bas de chaque branche comme facteur de poids

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

en comparant l'entropie avant et après la scission, nous obtenons une mesure de gain d'information , ou la quantité d'informations que nous avons acquise en faisant la scission en utilisant cette caractéristique particulière:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Vous pouvez interpréter le calcul ci-dessus comme suit: en faisant la scission avec la fonction end-vowels, nous avons pu réduire l'incertitude dans les résultats de prédiction sous-arbre par une petite quantité de 0,1518 (mesurée en les bits comme manière gourmande (favorisant ainsi les caractéristiques qui produisent pur se divise avec une faible incertitude / entropie). Ce procédé est appliqué de manière récursive à partir du nœud racine vers le bas, et s'arrête quand un nœud feuille contient toutes les instances ayant la même classe (pas besoin de le diviser plus loin).

Notez que je sauté sur une détails qui dépassent le cadre de ce poste, y compris la façon de traiter , valeurs manquantes , overfitting et < a href = "https://en.wikipedia.org/wiki/Pruning_%28decision_trees%29" rel = "noreferrer"> taille arbres, etc ..

Answer 2

Pour commencer, il serait préférable de comprendre the measure of information.

Comment pouvons-nous measure les informations?

Quand quelque chose arrive peu probable, nous disons que c'est une grande nouvelles. Aussi, quand nous disons quelque chose prévisible, ce n'est pas vraiment intéressant. Donc, pour quantifier cette interesting-ness, la fonction doit satisfaire

• si la probabilité de l'événement est une (prévisible), la fonction donne 0
• si la probabilité de l'événement est proche de 0, la fonction doit donner nombre
• si la probabilité de 0,5 événements se produit, il donne one bit d'informations.

Une mesure naturelle qui satisfont aux contraintes est

I(X) = -log_2(p)

où p est la probabilité de X d'événements. Et l'appareil est en bit, le même bit ordinateur utilise. 0 ou 1.

Exemple 1

flip pièce de monnaie:

Combien d'informations pouvons-nous aller d'un coin flip?

Réponse: -log(p) = -log(1/2) = 1 (bit)

Exemple 2

Si un météore frappe la Terre demain, p=2^{-22} alors nous pouvons obtenir 22 bits d'information.

Si le Soleil se lève demain, p ~ 1 alors il est 0 bit d'information.

Entropy

Donc, si nous prenons l'attente sur la interesting-ness d'un Y d'événement, il est alors l'entropie. à-dire l'entropie est une valeur attendue de la Etreté intéressante d'un événement.

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

Plus formellement, l'entropie est le nombre attendu de bits d'un événement.

Exemple

Y = 1: un événement X se produit avec une probabilité p

Y = 0: un événement X ne se produit pas avec une 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 base 2 pour tous les log.

Answer 3

Je ne peux pas vous donner des graphiques, mais je peux peut-être donner une explication claire.

Supposons que nous ayons un canal d'information, comme une lumière qui clignote une fois par jour soit rouge ou vert. Combien d'informations il transmettre? La première estimation pourrait être un bit par jour. Mais si l'on ajouter du bleu, de sorte que l'expéditeur a trois options? Nous aimerions avoir une mesure d'information qui peut gérer les choses autres que des puissances de deux, mais encore additif (la façon dont la multiplication du nombre de messages possibles par deux ajoute un bit). Nous pourrions le faire en prenant journal ₂ (nombre de messages possibles), mais il se trouve qu'il ya une façon plus générale.

Supposons que nous sommes de retour au rouge / vert, mais l'ampoule rouge a brûlé (ce qui est de notoriété publique) de telle sorte que la lampe doit toujours clignoter en vert. Le canal est maintenant inutile, nous savons ce que le prochain flash sera de sorte que les flashes véhiculent aucune information, pas de nouvelles. Maintenant, nous réparons l'ampoule, mais imposons une règle que l'ampoule rouge ne peut pas clignoter deux fois de suite. Lorsque le témoin clignote en rouge, nous savons ce que le prochain flash sera. Si vous essayez d'envoyer un flux de bits par ce canal, vous constaterez que vous devez encoder avec plus de flashes que vous avez bits (50% de plus, en fait). Et si vous voulez décrire une séquence de clignotements, vous pouvez le faire avec moins de bits. Le même si chaque flash est indépendant (hors-contexte), mais clignote en vert sont plus fréquents que le rouge: plus biaisé la probabilité que moins de bits dont vous avez besoin pour décrire la séquence, et moins d'informations qu'il contient, tout le chemin à la tout vert, limite brûlée ampoule au départ.

Il se trouve qu'il ya un moyen de mesurer la quantité d'informations dans un signal, sur la base des probabilités des différents symboles. Si la probabilité de symbole recevoir x _i est p _i , puis considérer la quantité

-log pi

Le plus petit p _i est élevée, plus cette valeur. Si x _i devient deux fois plus improbable, cette valeur augmente d'un montant fixe (log (2)). Cela devrait vous rappeler d'ajouter un bit à un message.

Si nous ne savons pas ce que le symbole sera (mais nous savons que les probabilités) alors nous pouvons calculer la moyenne de cette valeur, combien nous aurons, en sommant sur les différentes possibilités:

I = -Σ pi log(pi)

Ceci est le contenu de l'information dans un flash.

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

Ceci est le contenu de l'information ou l'entropie, du message. Il est maximal lorsque les différents symboles sont équiprobables. Si vous êtes un physicien que vous utilisez le journal naturel, si vous êtes un informaticien vous utilisez journal ₂ et obtenez des bits.

Answer 4

Je recommande vraiment que vous lisez Théorie de l'information, les méthodes bayésiens et MaxEnt. Le point de départ est la suivante (disponible gratuitement en ligne) livre de David Mackay:

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

Ces méthodes d'inférence sont vraiment beaucoup plus générale que l'exploitation minière juste texte et je ne peux pas imaginer vraiment comment on pourrait apprendre comment appliquer cela à la PNL sans apprendre quelques-unes des bases générales contenues dans ce livre ou d'autres livres d'introduction sur l'apprentissage de la machine et Maxent méthodes de Bayes.

Le lien entre l'entropie et la théorie des probabilités pour le traitement de l'information et le stockage est vraiment, vraiment profond. Pour donner un avant-goût de celui-ci, il y a un théorème de Shannon qui indique que le montant maximum d'informations que vous pouvez passer sans erreur par un canal de communication bruyante est égale à l'entropie du processus de bruit. Il y a aussi un théorème qui se connecte à quel point vous pouvez compresser un morceau de données pour occuper la mémoire minimale possible dans votre ordinateur à l'entropie du processus qui a généré les données.

Je ne pense pas qu'il soit vraiment nécessaire que vous allez apprendre à tous ces théorèmes sur la théorie de la communication, mais il est impossible d'apprendre cela sans apprendre les notions de base sur ce qui est l'entropie, la façon dont il est calculé, ce qui est sa relation avec l'information et inférence, etc ...

Answer 5

Quand j'exécutait un algorithme pour calculer l'entropie d'une image que je trouve ces liens, voir ici et .

Ceci est le pseudo-code je, vous aurez besoin de l'adapter à travailler avec le texte plutôt que des images, mais les principes doivent être les mêmes.

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

Je suis arrivé ce code de quelque part, mais je ne peux pas creuser le lien.

Answer 6

Officieusement

entropie est la disponibilité de l'information ou de la connaissance, le manque d'information conduit à des difficultés en matière de prévision de l'avenir qui est haute entropie (prédiction du mot suivant dans l'exploration de texte) et la disponibilité des informations / connaissances nous aidera prévision plus réaliste de l'avenir (faible entropie).

Les informations pertinentes de tout type permettra de réduire l'entropie et nous aide à prédire un avenir plus réaliste, que l'information peut être mot « viande » est présent dans la phrase ou le mot « viande » n'est pas présent. Ceci est appelé Informations Gain

---

Formellement

entropie est le manque d'ordre de predicability

Answer 7

Comme vous lisez un livre sur NLTK il serait intéressant que vous lisez sur MaxEnt Module classificateur http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

Pour la classification des mines de texte, les étapes pourraient être: pré-traitement (tokens, à la vapeur, fonction sélection avec gain d'information ...), la transformation numérique (fréquence ou TF-IDF) (Je pense que c'est l'étape clé comprendre lors de l'utilisation du texte comme entrée à un algorithme qui acceptent uniquement numérique), puis classer avec Maxent que cela est juste un exemple.