Ce qui est « gain d’entropie et d’information » ?

Question

Je suis à la lecture de ce livre (NLTK) et il est source de confusion. L'entropie est définie comme:

L'entropie est la somme de la probabilité de chaque étiquette fois le journal de probabilité de la même étiquette

Comment puis-je appliquer l'entropie et l'entropie maximale en termes d'exploration de texte? Quelqu'un peut-il me donner un simple exemple (visuel)?

Answer 1

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

Pour illustrer, imaginez la tâche de l'apprentissage à classer premier-les noms en mâle/femelle groupes. C'est la liste des noms de chaque marquées avec m ou f, nous voulons apprendre un modèle qui s'adapte 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 est de décider ce que les caractéristiques des données sont pertinentes pour la classe cible nous voulons prédire. Quelques exemples de fonctionnalités: la première/dernière lettre, la longueur, le nombre de voyelles, il se termine par une voyelle, etc.. Donc après extraction de caractéristiques, notre apparence des données:

# 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'objectif est de construire un arbre de décision. Un exemple d'un arbre 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ésentent un test effectué sur un seul attribut, et nous allons à gauche ou à droite selon le résultat de l'essai. Nous gardons de la traversée de l'arbre jusqu'à ce que nous arrivons à un nœud feuille qui contient la classe de prédiction (m ou f)

Donc, si nous courons le nom Amro en bas de cet arbre, nous commençons par tester "est le legth<7?" et la réponse est oui, alors nous aller dans cette direction. À la suite de la branche, le prochain test "est le nombre de voyelles<3?" encore une fois évalue à true. Cela conduit à un nœud feuille étiquetée m, et donc la prédiction est de sexe masculin (ce qui m'arrive d'être, si l'arbre a prédit le résultat correctement).

L'arbre de décision est construit de haut en bas de la mode, mais la question est de savoir comment vous choisissez l'attribut à split à chaque nœud? La réponse est de trouver la fonction qui mieux divise la classe cible dans la plus pure possible nœuds enfants (ie: les nœuds qui ne contiennent pas un mélange des deux, mâle et femelle, plutôt pure nœuds avec une seule classe).

Cette mesure de la pureté est appelée l' information. Il représente le prévu quantité d' informations qui seraient nécessaires pour préciser si une nouvelle instance (première du nom) doivent être classés de sexe masculin ou féminin, donné l'exemple qui atteint le nœud. Nous le calculons sur la base du nombre d'hommes et de femmes des classes au nœud.

L'entropie sur l'autre main est une mesure de l'impureté (au contraire). Il est défini pour un binaire de la classe avec les valeurs de a/b comme:

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

Cette entropie binaire fonction est illustré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 qu' p(X=a)=0.5 ou de mêmep(X=b)=0.5 a 50%/50% de chances d'être soit a ou b (incertitude est à son maximum). L'entropie de la fonction est à zéro minimum lorsque la probabilité est - p=1 ou p=0 avec une complète certitude (p(X=a)=1 ou p(X=a)=0 respectivement, ce dernier implique p(X=b)=1).

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 (et pas seulement deux):

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

---

De retour à notre tâche de classification nom, permet de regarder un exemple. Imaginez à un certain moment au cours du processus de construction de l'arbre, nous avons examiné la répartition:

     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

À côté de nous comparer avec l'entropie calculée après avoir tenu compte de la scission en regardant les deux branches enfants. Dans la branche gauche de l' ends-vowel=1, nous avons:

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

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

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

Nous combinons la gauche/droit des entropies en utilisant le nombre d'occurrences de chaque branche comme facteur de pondération (7 cas allés à gauche, et 7 cas allés à droite), et le dernier entropie après la scission de:

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 gain d'informations, ou la quantité d'informations que nous avons acquises par 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 scission avec l' end-vowels fonctionnalité, nous avons été en mesure de réduire l'incertitude dans le sous-arbre de prédiction des résultats par 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 fonction, et la fonction avec le plus grand gain d'informations est choisi pour le split, dans un gourmand (favorisant ainsi les caractéristiques qui produisent de la pure divise avec une faible incertitude/entropie). Ce processus est appliqué de manière récursive à partir de la racine-noeud en bas, et s'arrête quand un nœud feuille contient des instances ayant tous la même classe (pas besoin de le diviser encore plus).

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érique caractéristiques, valeurs manquantes, le surajustement et l'élagage des arbres, etc..

Answer 2

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

Comment pouvons-nous measure l'information?

Quand quelque chose improbable se produit, nous disons que c'est une grande nouvelle. Aussi, si nous disons quelque chose de prévisible, il n'est pas vraiment intéressant. Afin de quantifier cette interest-ness, la fonction doit satisfaire

• si la probabilité de l'événement est de 1 (prévisible), alors la fonction renvoie 0
• si la probabilité de l'événement est proche de 0, alors la fonction donne infiniment grand nombre

Un naturel qui satisfont les contraintes

I(X) = -log(p)

où p est la probabilité de l'événement X.

Exemples

Si une météorite frappe la Terre de demain, p=e^{-22} alors qu'il est de 22.

Si le soleil se lève demain, p ~ 1 alors qu'il est de 0.

L'entropie

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

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

Exemple

Y = 1 : X Y = 0 : cas X ne se produit pas

• H(Y) = - p(y_1) log( p(y_1) ) - p(y_0) log ( p(y_0) ) *

(L'entropie est habituellement notée H)

Answer 3

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

Supposons que nous avons un canal d'information, comme une lumière qui clignote une fois tous les deux jours, soit en rouge ou en vert. Quelle quantité d'information est-il transmettre? La première suppose que peut-être un peu 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 d'autres choses que des puissances de deux, mais encore être en additif (de la même façon que le fait de multiplier le nombre de messages par deux ajoute un bit). Nous pourrions le faire en prenant log₂(nombre de messages), mais il s'avère, il ya une façon plus générale.

Supposons que nous sommes de retour à rouge/vert, mais l'ampoule rouge a brûlé (ce qui est la connaissance commune) de sorte que la lampe doit toujours clignoter en vert. Le canal est désormais inutile, nous savons ce que le prochain flash sera de sorte que les éclairs ne donnent pas d'information, pas de nouvelles. Maintenant, nous réparer l'ampoule, mais imposer une règle que l'ampoule rouge peut clignote pas deux fois dans une rangée. Lorsque le voyant clignote en rouge, nous savons ce que le prochain flash sera. Si vous essayez d'envoyer un flux de bits par ce canal, vous verrez que vous devez coder avec plus de bouffées de chaleur 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. La même chose s'applique si chaque flash est indépendant (context-free), mais les bouffées de chaleur sont plus fréquentes que le rouge: la plus biaisée de la probabilité le moins de bits, vous devez décrire la séquence, et le moins d'informations qu'il contient, tout le chemin vers le tout-vert, ampoule brûlée limite.

Il s'avère qu'il y est une façon de mesurer la quantité d'informations dans un signal, basé sur les probabilités des différents symboles. Si la probabilité de recevoir symbole x_i p_i, alors compte de la quantité

-log pi

Le plus petit p_j', plus cette valeur est grande. Si x_i devient deux fois plus rare, l'augmentation de cette valeur par un montant fixe (log(2)). Cela devrait vous rappeler de l'ajout d'un bit à un message.

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

I = -Σ pi log(pi)

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

Ampoule rouge brûlé: prouge = 0, pvert=1, I = -(0 + 0) = 0
Le rouge et le vert équiprobable: prouge = 1/2, pvert = 1/2, I = -(2 * 1/2 * log(1/2)) = log(2)
Trois couleurs, équiprobable: pi=1/3, I = -(3 * 1/3 * log(1/3)) = log(3)
Le vert et le rouge, le vert deux fois plus susceptibles: prouge=1/3, pvert=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 l'entropie, du message. Elle est maximale lorsque les différents symboles sont équiprobable. Si vous êtes un physicien vous utilisez le logarithme naturel, si vous êtes un chercheur en informatique-vous utilisez log₂ et obtenir des morceaux.

Answer 4

Je vous recommande vraiment de vous lire à propos de la Théorie de l'Information, les méthodes bayésiennes et MaxEnt. L'endroit pour commencer est-ce (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éral que juste de l'exploration de texte et je ne peux pas vraiment imaginer comment on pourrait apprendre comment appliquer cela à la PNL sans apprendre certains principes de base contenus dans ce livre d'introduction ou d'autres livres sur l'Apprentissage de la Machine et MaxEnt méthodes bayésiennes.

La connexion entre l'entropie et de la théorie des probabilités à l'information, le traitement et le stockage est vraiment, vraiment profond. Pour donner un avant-goût de la, il y a un théorème dû à Shannon, qui indique que le montant maximum de renseignements vous pouvez passer sans erreur par un bruit de canal de communication est égale à l'entropie de la source de bruit processus. Il y a également un théorème qui relie la façon dont beaucoup vous pouvez compresser un morceau de données pour occuper le minimum possible de la mémoire de votre ordinateur à l'entropie du processus qui a généré les données.

Je ne pense pas qu'il faut vraiment que vous allez apprendre au sujet de tous ces théorèmes sur la théorie de la communication, mais il n'est pas possible d'apprendre sans avoir à apprendre les notions de base sur ce qu'est l'entropie, comment il est calculé, qu'est-ce que c'est la relation avec l'information et l'inférence, etc...

Answer 5

Quand j'étais mise en œuvre d'un algorithme pour le calcul de l'entropie d'une image que j'ai trouvé ces liens, voir ici et ici.

C'est le pseudo-code que j'ai utilisé, vous aurez besoin de l'adapter pour travailler avec du texte plutôt que des images mais le principe doit être le même.

//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 eu ce code à partir de quelque part, mais je ne peux pas creuser le lien.