Classifieur d'entropie maximale (MaxEnt)

Classifieur d’entropie maximale (MaxEnt)

Jean-Philippe Fauconnier

IRIT - Toulouse

15 février 2013

(IRIT - Toulouse) 15 février 2013 1 / 31

1 Introduction

2 Entropie

3 Modèle MaxEnt

4 Conclusion

5 Références


IntroductionUn modèle de Maximum d’Entropie (MaxEnt) :est un classifieur probabiliste linéaire et discriminant.

1 classifieurLe MaxEnt prédit une classe (∈ Ensemble de valeurs discrètes)

2 probabilisteÀ chaque individu est associé une probabilité d’appartenance à chacune desclasses (dont la somme est 1).

3 log-linéaireUn classifieur log-linéaire tente d’estimer les poids (~w) du modèle parrégression linéaire.

4 discriminantPour estimer les poids (~w), un modèle discriminant s’entraînera sur unensemble de samples sans nécessiter de probabilités conditionnelles (cf.Modèles génératifs).


Introduction

Le MaxEnt s’inscrit dans :

1 une maximisation de l’entropieLe MaxEnt consiste à choisir, pour un phénomène donné, une distributionqui maximise l’entropie (Shannon), c’est-à-dire « l’incertitude ».

2 le principe du rasoir d’Occam« L’hypothèse la plus simple est souvent la bonne »La plus simple, la moins contrainte, c’est-à-dire qui ne présume pas au-delàde ce qui est connu.

3 le principe d’indifférence (Laplace)En cas d’information manquante, le mieux à faire est de considérer lesévénements comme équiprobables (distribution uniforme).


1 Introduction

2 Entropie

3 Modèle MaxEnt

4 Conclusion

5 Références


Entropie de ShannonL’entropie est :

- une fonction, fondamentale en théorie de l’information, qui retourne à laquantité d’information délivrée/contenue par une source S (Shannon, 1948).

Pour une source S comportant n symboles, un symbole i a une probabilité pid’apparaître. Alors l’entropie de la source S est définie comme suit :

H(S) =−∑n

i=1 pi log2(pi)

⇒ entropie, une mesure de « surprise », d’« incertitude »

Source :

- Plus la source émet des infos différentes, plus l’entropie (incertitude) est grande

- Et inversement.


Entropie de ShannonExemple

Une source S qui émet 10 valeurs :

- qui prennent toujours le même symbole (ici « a »).

- p(a) = 1- H(S) = −(1 ∗ log2(1)) = 0

Entropie est nulle.


Entropie de ShannonExemple

Une source S qui émet 10 valeurs :

- qui prennent équitablement deux symboles (ici « a » et « b »)

- p(a) = 12 et p(b) = 1

2

- H(S) = −(2 ∗ (0, 5 ∗ log2(0, 5))) = 1

Entropie positive


Entropie de ShannonExempleUne source S qui émet 10 valeurs :

- qui prennent trois symboles (ici « a », « b » et « c »)

- p(a) = 25 , p(b) =

13 et p(c) = 1

3

- H(S) = −( (25 ∗ log2(25)) + (2 ∗ (13 ∗ log2(

13))) ) = 1,585 ...

Entropie positive(IRIT - Toulouse) 15 février 2013 9 / 31

Entropie de ShannonExempleUne source S qui émet 10 valeurs :

- qui prennent chacune un symbôle différent (ici de « a » à « j »)

- Chaque p(n) = 110

- H(S) = −10 ∗ (0, 1 ∗ log2(0, 1)) = 3,321 ...

Entropie maximaleDans ce cas-ci, la distribution est uniformeet la source S est maximalement informative.


Entropie de ShannonLe principe d’entropie maximale

Principe :

(Jaynes, 1957)Information theory provides a constructive criterion for setting up probabilitydistributions on the basis of partial knowledge, and leads to a type ofstatistical inference which is called the maximum entropy estimate. It is leastbiased estimate possible on the given information (...)

Pour représenter une connaissance imparfaite par une distribution(loi de probabilité), il est nécessaire :

1 d’identifier toutes les distributions qui respectent les contraintes observéessur les données (e.g : moyennes observées, etc.)

2 et de choisir celle qui maximise l’entropie (unique)


Entropie de ShannonVers les modèles d’entropie maximale

Pourquoi ?La distribution avec l’entropie maximale est celle

- qui est la plus uniforme (équidistribution)

- et, donc, celle qu’il serait le moins arbitraire d’utiliser pour représenter uneconnaissance imparfaite.

- En pratique, c’est la distribution qui contient le moins de cas particuliers quidivergent de ce qui est le plus probable.

Idée centrale de l’entropie maximaleOn ne présume pas au-delà des données.


1 Introduction

2 Entropie

3 Modèle MaxEnt

4 Conclusion

5 Références


Modèle MaxEnt

Un classifieur d’entropie maximale (modèle MaxEnt) :

- Reprend le principe d’entropie maximale

- Autrement dit, maximise l’entropie pour prédire un phénomène aléatoire

Dans l’élaboration d’un MaxEnt, il y a trois étapes :

1 Constituer un set d’entraînement qui va permettre de « capturer » aupossible le comportement d’un phénomène aléatoire.

2 Déterminer les traits qui rendent compte de ce phénomène aléatoire.Un trait = fonction qui fournit une information à propos des données.

3 Choisir le modèle qui maximise l’entropie tout en restant consistantvis-à-vis des contraintes.

Dans le MaxEnt, les traits sont utilisés comme des contraintes.


Modèle MaxEntÉtape 1

Constitution d’un set d’entraînement :

- La première étape vise à constituer un corpus reprenant des échantillons duphénomène aléatoire.

- De ce corpus, il est possible de tirer (x1, y1), (x2, y2), ..., (xN , yN) samples où :

1 x = information contextuelle et x ∈ X2 y = classes et y ∈ Y

Exemple en TA :

- Nous désirons modéliser le comportement d’un traducteur lorsqu’il doit choisirun mot français pour traduire la proposition « in » en anglais.

- 5 classes : « dans », « en », « à », « au cours de », « pendant »

- E.g de samples : (in avril, en), (in this, dans)


Modèle MaxEntÉtape 2Sélection des traits

- Quels indices sont informatifs pour la prise de décision ?

- Au-delà des statistiques d’observation empirique (e. g : p(en) = 12 et p(dans)

= 12 ), intérêt pour donner de l’importance à d’autres statistiques au travers

des traits (e.g : une régularité récurrente).

Dans le modèle :

- Un trait, dit aussi feature, est une fonction binaire dépendante de x quiapporte une information sur la décision de y .

- E.g : Savoir que lorsque « in » est suivi d’un nom de mois, il est classé dans« en »

f (x , y) ={

1 si y = « en » et si x = « in Avril »0 sinon


Modèle MaxEntÉtape 2 : Traits et contraintes

Les traits :

- sont considérés comme des contraintes

- ont des poids qui leur sont associés

Contraintes :

- Une contrainte est une égalité que doit satisfaire le modèle cible

- En pratique, le modèle doit respecter l’égalité entre

1 La valeur attendue de p(f ) dans le set d’entraînement2 La valeur attendue de p(f ) dans le modèle cible



Contrainte pour le trait f :

- La valeur attendue d’un trait f du point de vue du set d’entraînement

p(f ) =∑x,y

p(x , y)f (x , y)

- La valeur attendue d’un trait f du point de vue du modèle

p(f ) =∑x,y

p(x)p(y|x)f (x , y)

- Et la contrainte pour le trait f :

p(f ) = p(f )



Pourquoi contraindre ?

1 C’est un moyen d’exiger que la valeur attendue respecte la distributionempirique observée dans le set d’entraînement.

2 Ainsi, lorsque l’on découvre une statistique qu’on trouve utile, il est possiblede lui donner de l’importance en exigeant que le modèle soit en accord avecelle.

3 Premier corollaire, un modèle qui ne respecte pas ces contraintes est :

1 Un modèle qui n’est pas en accord avec le set d’entraînement2 Un modèle inconsistant

4 Deuxième corollaire, la résolution du MaxEnt est un problèmed’optimisation sous contraintes.

→ On cherche à maximiser l’entropie tout en respectant des contraintes.


Modèle MaxEntScénarios d’optimisation sous contraintes (Berger, 1996)

Soit P l’espace des hypothèses et C1, C2 et C3 des contraintes.


Modèle MaxEntÉtape 2 : exemple (1)

Exemple simple (Berger, 1996) :

- La première contrainte (implicite) est que :p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1

→ A ce niveau, il existe une infinité de modèles qui répondent à cette contrainte.

Un modèle d’entropie maximale qui répond à cette contrainte :

1 p(dans) = 1/5

2 p(en) = 1/5

3 p(à) = 1/5

4 p(au cours de) = 1/5

5 p(pendant) = 1/5


Modèle MaxEntÉtape 2 : exemple (2)Un autre exemple (Ratnaparkhi, 1997) :

1 Pour la distribution p(x , y) où x ∈{ in Avril, in this} et y ∈ {en, dans}.

2 Avec pour contrainte : p(in Avril,en) + p(in this, en) = 0,6

p(x , y) en dansin avril ? ?in this ? ?total 0,6 1

⇒ Maximiser l’entropie revient à uniformiser le modèle selon la contrainte.

p(a, b) 0 1x 0,3 0,2y 0,3 0,2

total 0,6 0,4 1


Modèle MaxEntÉtape 3Choisir le modèle qui maximise l’entropie :Le modèle d’entropie maximale a pour sortie :

P(y |x) = 1Z (x)

exp

(n∑

i=1

wifi (x , y)

)où

- P(y |x) désigne la probabilité que individu x (contexte) appartienne à la classe y

- La fonction fi est une fonction binaire appelée trait qui permet de définir lescontraintes du modèle.

- Z(x) est une constante de normalisation

- Chaque x est encodé comme vecteur avec n traits fi

- avec un poids wi associé à chaque trait

Comment estimer les poids ?Quels sont les poids qui maximisent l’entropie ?


Modèle MaxEntÉtape 3 : Maximisation de l’entropie

Trouver des poids qui :

- maximisent l’entropie

- respectent les contraintes

Maximiser la fonction d’entropie :Pour estimer les valeurs des paramètres w , le MaxEnt doit maximiser la fonctiond’entropie associé à chaque p(x , y) :

p(x , y) = argmaxp(x,y)∈C

H(p(x , y))

où H est la fonction d’entropie, p(x,y) le modèle cible et C l’espace descontraintes.

Or, computationnellement, il est difficile (voire impossible) de calculerdirectement ce problème d’optimisation sous contraintes.



Solution :Mathématiquement, il est prouvé :

1 l’estimation d’un maximum d’entropie (sous contraintes) est équivalent àl’estimation du maximum de vraissemblance (sans contraintes) sur lesdonnées du set d’entraînement (Berger, 1996).

2 et une solution itérative converge vers ce modèle unique.



Estimation du maximum de vraissemblance :

- est une méthode statistique pour estimer les poids (paramètres) d’un modèle(distribution) à partir des samples du set d’entraînement (échantillons)

- Trouver le maximum de vraissemblance est un problème d’optimisation noncontraint.

- Ainsi, trouver les poids w peut s’effectuer ainsi :

w = argmaxw

∑x ,y

p(x , y) log p(y |x)

où p(x , y) est la fréquence empirique observée de x associé à la classe y dans lesdonnées d’entraînement.



Algorithmes itératifs :

1 Il est prouvé mathématiquement que certains algorithmes itératifsconvergent vers la solution à chaque itération.

2 Plusieurs algorithmes :

- GIS (Darroch & Ratcliff, 1972)- IIS (Berger, 1996)- GIS avec correction feature (Curran & Clark, 2003)- L-BFGS


1 Introduction

2 Entropie

3 Modèle MaxEnt

4 Conclusion

5 Références


Conclusion

Quelques implémentations :

- Apache OpenNLP (GIS)

- SharpEntropy (GIS)

- AI : :MaxEntropy (GIS et L-BFGS)

- MaxEnt Modeling Toolkit (GIS et L-BFGS)

- MegaM (CG et L-BFGS)

- etc.


1 Introduction

2 Entropie

3 Modèle MaxEnt

4 Conclusion

5 Références


Références- BERGER, A., PIETRA, V. et PIETRA, S. (1996). A Maximum Entropy approach to Natural

Language Processing. Computational linguistics, 22(1) :39-71.

- BERGER, A. (1997). The Improved Iterative Scaling Algorithm : A Gentle Introduction, Techreport. School of Computer Science, Carnegie Mellon University.

- CANDITO, M. (2012), Classification : MaxEnt. In Cours de M2 Linguistique Informatique,Paris 7.

- CURRAN, J. R., & CLARK, S. (2003). Investigating GIS and smoothing for maximumentropy taggers. In Proceedings of the tenth conference on European chapter of theAssociation for Computational Linguistics, volume 1, pages 91-98. Association forComputational Linguistics.

- JAYNES, E. T. (1957). Information theory and statistical mechanics. Physical review,106(4), 620.

- RATNAPARKHI, A. (1996). A Maximum Entropy model for Part-of-Speech Tagging. InProceedings of the conference on empirical methods in natural language processing, volume1, pages 133-142. Philadelphia, PA.

- RATNAPARKHI, A. (1997). A Simple Introduction to Maximum Entropy Models for NaturalLanguage Processing, Tech report. Dept. of Computer and Informative Science, University ofPennsylvania.

- SHANNON, C. E. (1948). A Mathematical Theory of Communication, Bell System TechnicalJournal, vol. 27.


Data & Analytics

Classifieur d'entropie maximale (MaxEnt)