Qu'est-ce que "entropie et gain d'information"?

Je lis ce livre ( NLTK) et c'est déroutant. Entropie est définie comme:

Entropie est la somme de la probabilité de chaque étiquette fois la probabilité logarithmique de cette même étiquette

Comment entropie et maximum d'entropie, en termes d'exploration de texte? Quelqu'un peut-il me donner un exemple simple et facile (visuel)?

310
demandé sur rayryeng 2009-12-07 14:54:32

7 réponses

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

Pour illustrer, imaginez la tâche deapprendre àclasser prénoms en groupes masculins/féminins. C'est la liste des noms de chaque marquées avec m ou f, nous voulons apprendre modèle, ce qui correspond aux données et peut être utilisé pour prédire le sexe d'un nouveau invisible, premier-nom.

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 consiste à décider quoi caractéristiques les données sont pertinentes pour la classe cible nous voulons prédire. Voici quelques exemples de caractéristiques: première / dernière Lettre, Longueur, Nombre de voyelles, se termine-t-elle par une voyelle, etc.. Donc, après l'extraction des fonctionnalités, nos données ressemblent à:

# 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 arbre de décision . Un exemple d'arbre {[37] } serait:

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

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

Donc, si nous exécutons le nom Amro dans cet arbre, nous commençons par tester " est la longueur" et la réponse est oui, donc on aller dans cette direction. Après la branche, le test suivant " est le nombre de voyelles " évalue à nouveau true . Cela conduit à un nœud feuille étiqueté m, et donc la prédiction est mâle (ce que je suis, donc l'arbre a prédit le résultat correctement).

L'arbre de décision est construit de manière descendante, mais la question Est de savoir comment choisir quel attribut diviser à chaque nœud? La réponse est de trouver la fonctionnalité qui divise le mieux la classe cible en nœuds enfants les plus purs possibles (c'est-à-dire: les nœuds qui ne contiennent pas un mélange de mâles et de femelles, des nœuds plutôt purs avec une seule classe).

Cette mesure de pureté est appelé le informations. Il représente la quantitéattendue d'informations qui serait nécessaire pour spécifier si une nouvelle instance (prénom) doit être classée Mâle Ou Femelle, compte tenu de l'exemple qui a atteint le nœud. Nous le calculons basé sur le nombre de classes masculines et féminines au nœud.

L'Entropie sur l'autre main est une mesure de impureté (à l'opposé). Il est défini pour un classe binaire avec des valeurs a/b comme:

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

Cette fonction d'entropie binaire est représentée dans la figure ci-dessous (variable aléatoire peut prendre l'une des deux valeurs). Il atteint son maximum lorsque la probabilité est p=1/2, ce qui signifie que {[18] } ou de la même manière p(X=b)=0.5 ayant une chance de 50%/50% d'être a ou b (l'incertitude est au maximum). La fonction d'entropie est au minimum zéro lorsque la probabilité est p=1 ou p=0 avec une certitude complète (p(X=a)=1 ou p(X=a)=0 respectivement, ce dernier implique p(X=b)=1).

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

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

entropie

(le log, dans la formule, est généralement considéré comme le logarithme de la base 2)


Revenons à notre tâche de classification des noms, regardons un exemple. Imaginez à un moment donné au cours du processus de construction de l'arbre, nous étions considérant la division 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, nous avions 9 mâles et 5 femelles, c'est à dire 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 comparons avec l'entropie calculée après avoir considéré la scission en regardant deux branches enfants. 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 les entropies gauche / droite en utilisant le nombre d'instances vers le bas chaque branche comme facteur de poids (7 instances sont allées à gauche, et 7 instances sont allées à droite), et obtenir l'entropie finale après la scission:

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

Maintenant, en comparant l'entropie avant et après la scission, nous obtenons une mesure de le gain d'informations, ou comment beaucoup d'informations, nous avons gagné en faire la fente à l'aide de cette fonctionnalité:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Vous pouvez interpréter le calcul ci-dessus comme suit: en faisant la division avec la fonction end-vowels, nous étions capable de réduire l'incertitude dans le résultat de la prédiction du sous-arbre d'une petite quantité de 0,1518 (mesurée en bits comme unités d'information ).

À chaque nœud de l'arbre, ce calcul est effectué pour chaque caractéristique, et la caractéristique avec le gain d'information le plus important est choisie pour la division de manière gourmande (favorisant ainsi les caractéristiques qui produisent desdivisions pures avec une faible incertitude / entropie). Ce processus est appliqué récursivement à partir du nœud racine vers le bas, et s'arrête lorsqu'un nœud feuille contient des instances ayant toutes la même classe (pas besoin de le diviser davantage).

Notez que j'ai sauté sur certains détails, qui sont au-delà de la portée de ce post, y compris la façon de gérer numériques caractéristiques, les valeurs manquantes, le surajustement et élagage arbres, etc..

975
répondu Amro 2016-02-04 13:01:23

Pour commencer, il serait mieux de comprendre the measure of information.

Comment pouvons-nous measure l'information?

Quand quelque chose d'improbable se produit, nous disons que c'est une grande nouvelle. De plus, quand on dit quelque chose de prévisible, ce n'est pas vraiment intéressant. Donc, pour quantifier cela interesting-ness, la fonction devrait satisfaire

  • si la probabilité de l'événement est 1 (prévisible), alors la fonction donne 0
  • si la probabilité de l'événement est proche de 0, alors la fonction devrait donner haute nombre
  • si la probabilité 0.5 événements se produit, il donne {[6] } d'information.

Une mesure naturelle qui satisfait les contraintes est

I(X) = -log_2(p)

p est la probabilité de l'événement X. Et l'unité est dans bit, le même Bit que l'ordinateur utilise. 0 ou 1.

Exemple 1

Juste pile ou face :

Combien d'informations pouvons-nous obtenir d'une pièce de Monnaie 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 c'est 0 bit d'information.

Entropie

Donc, si nous prenons l'attente de la interesting-ness d'un événement Y, puis c'est l'entropie. c'est-à-dire que l'entropie est une valeur attendue de l'intérêt d'un événement.

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

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

Exemple

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

Y = 0: un événement X ne se produit pas avec la 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)

Logarithme de base 2 pour tous les journaux.

37
répondu VforVitamin 2014-10-17 04:37:04

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

Supposons que nous ayons un canal d'information, comme une lumière qui clignote une fois par jour en rouge ou en vert. Combien d'informations transmet-il? La première estimation pourrait être un bit par jour. Mais que faire si nous ajoutons bleu, de sorte que l'expéditeur a trois options? Nous aimerions avoir une mesure de l'information qui peut gérer des choses autres que des puissances de deux, mais qui reste additive (la façon dont on multiplie le nombre de les messages possibles par deux ajoute un peu). Nous pourrions le faire en prenant journal2(nombre de messages possibles), mais il s'avère, 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é (c'est de notoriété publique) de sorte que la lampe doit toujours clignoter en vert. La chaîne est maintenant inutile, nous savons quel sera le prochain flash donc les flashs ne transmettent aucune information, aucune nouvelle. Maintenant Nous réparons l'ampoule mais imposons une règle que l'ampoule rouge peut pas clignoter deux fois de suite. Lorsque la lampe clignote en rouge, nous savons quel sera le prochain flash. Si vous essayez d'envoyer un flux de bits par ce canal, vous constaterez que vous devez l'encoder avec plus de flashs que vous n'avez de 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. La même chose s'applique si chaque flash est indépendant (sans contexte), mais les flashs verts sont plus fréquents que le rouge: plus la probabilité est biaisée, moins vous avez besoin de bits pour décrire le séquence, et moins il contient d'informations, jusqu'à la limite entièrement verte, brûlée par les ampoules.

Il s'avère qu'il existe un moyen de mesurer la quantité d'informations dans un signal, en fonction des probabilités des différents symboles. Si la probabilité de recevoir symbole x, je p, je, alors compte de la quantité

-log pi

Plus Pi est petit, plus cette valeur est grande. 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 quel sera le symbole (mais nous connaissons les probabilités) alors nous pouvons calculer la moyenne de cette valeur, combien nous obtiendrons, en additionnant les différentes possibilités:

I = -Σ pi log(pi)

C'est le contenu de l'information en un seul 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)

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

20
répondu Beta 2009-12-07 13:45:44

Je vous recommande vraiment de lire sur la théorie de L'Information, les méthodes bayésiennes et MaxEnt. Le point de départ est ce livre (disponible gratuitement en ligne) de David Mackay:

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

Ces méthodes d'inférence sont vraiment beaucoup plus générales que l'exploration de texte et je ne peux pas vraiment imaginer comment on apprendrait à l'appliquer à la PNL sans apprendre certaines des bases générales contenues dans ce livre ou d'autres livres d'introduction sur la Machine Apprentissage et méthodes bayésiennes MaxEnt.

La connexion entre l'entropie et la théorie des probabilités au traitement et au stockage de l'information est vraiment, vraiment profonde. Pour donner un avant-goût de celui-ci, il y a un théorème dû à Shannon qui stipule que la quantité maximale d'informations que vous pouvez passer sans erreur à travers un canal de communication bruyant est égale à l'entropie du processus de bruit. Il y a aussi un théorème qui relie combien vous pouvez compresser un morceau de données pour occuper le minimum possible mémoire 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 appreniez tous ces théorèmes sur la théorie de la communication, mais il n'est pas possible d'apprendre cela sans apprendre les bases sur ce qu'est l'entropie, comment elle est calculée,Quelle est sa relation avec l'information et l'inférence, etc...

8
répondu Rafael S. Calsaverini 2009-12-14 17:42:55

Lorsque j'implémentais un algorithme pour calculer l'entropie d'une image, j'ai trouvé ces liens, voir ici et ici .

C'est le pseudo-code que j'ai utilisé, vous devrez l'adapter pour travailler avec du texte plutôt que des images mais les principes devraient ê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)

J'ai ce code de quelque part, mais je ne peux pas creuser le lien.

4
répondu Matt Warren 2009-12-07 13:35:46

De manière Informelle

L'entropie {[2] } est la disponibilité de l'information ou de la connaissance, le manque d'information entraînera des difficultés dans la prédiction de l'avenir qui est une entropie élevée (prédiction du mot suivant dans l'exploration de texte) et la disponibilité de l'information/de la connaissance nous aidera à une prédiction plus réaliste de l'avenir (faible entropie).

Informations pertinentes de tout type permettra de réduire l'entropie et nous aide à prédire l'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é Gain d'Informations


Officiellement

L'entropie est un manque d'ordre de prédicabilité

2
répondu Waseem Ahmad Naeem 2018-08-01 17:26:59

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

Pour la classification d'exploration de texte, les étapes peuvent être: prétraitement (tokenisation, vaporisation, sélection d'entités avec Gain D'informations ...), transformation en numérique (fréquence ou TF-IDF) (je pense que c'est l'étape clé à comprendre lors de l'utilisation du texte en entrée d'un algorithme qui n'accepte que numérique) et ensuite classer avec MaxEnt, bien sûr que ce n'est qu'un exemple.

0
répondu Paulo 2015-03-26 12:33:51