Apprendre les nombres d’un modèle probabiliste

Tous les modèles probabilistes vus jusqu’ici arrivaient avec leurs nombres déjà en place. Un réseau bayésien venait avec ses tables de probabilités conditionnelles remplies ; une gaussienne, avec une moyenne et une variance. Quelqu’un a bien dû les y mettre. Cet article porte sur le comment, et il se scinde nettement en deux : le cas où chaque variable est observée, qui est presque trivialement facile, et le cas où l’une ne l’est pas, qui exige un algorithme véritablement différent.

A. La vraisemblance, et les trois temps

Fixons un modèle de paramètres $\theta$. La vraisemblance d’un jeu de données est la probabilité que le modèle attribue exactement aux observations obtenues, laquelle est un produit pour des exemples indépendants :

$$P(\mathbf{d} \mid h_\theta) = \prod_{j=1}^{N} P(d_j \mid h_\theta).$$

L’estimation par maximum de vraisemblance retient le $\theta$ qui maximise cette quantité. La recette est toujours la même en trois temps : écrire la vraisemblance, dériver son logarithme, annuler la dérivée.

Déballez 25 bonbons d’un sachet de proportion de cerises inconnue $\theta$ et trouvez-en 18 à la cerise. Alors $P(\mathbf{d} \mid h_\theta) = \theta^{18}(1-\theta)^{7}$, donc

$$L = 18\log\theta + 7\log(1-\theta), \qquad \frac{dL}{d\theta} = \frac{18}{\theta} - \frac{7}{1-\theta} = 0 \;\Rightarrow\; \theta = \frac{18}{25} = 0{,}72 .$$

Une grille sur deux millions de valeurs de $\theta$ concorde à six décimales : la log-vraisemblance vaut $-14{,}823833$ en $0{,}72$, contre $-14{,}847959$ en $0{,}70$ et $-14{,}849407$ en $0{,}74$.

La réponse est la proportion observée, ce que tout le monde aurait deviné. La valeur de la dérivation est qu’elle prouve que cette intuition est le maximisant, et que les trois mêmes temps fonctionnent encore là où aucune intuition ne s’impose.

Le passage au logarithme mérite deux défenses. Mathématiquement, il ne peut pas déplacer un maximum, $\log$ étant strictement croissant. Numériquement, un produit de milliers de probabilités s’effondre à zéro en virgule flottante, pas une somme de logarithmes - d’où le code de production qui vit en espace logarithmique.

B. Pourquoi les données complètes rendent un réseau bon marché

Donnez aussi un emballage aux bonbons, rouge ou vert, avec une probabilité dépendant du parfum. Trois paramètres désormais : $\theta$, $\theta_1 = P(\text{rouge} \mid \text{cerise})$, $\theta_2 = P(\text{rouge} \mid \text{citron})$. Avec 12 cerise-rouge, 6 cerise-vert, 2 citron-rouge et 5 citron-vert,

$$L = 12\log(\theta\theta_1) + 6\log(\theta(1-\theta_1)) + 2\log((1-\theta)\theta_2) + 5\log((1-\theta)(1-\theta_2)).$$

Développez les logarithmes et tout terme contenant $\theta_1$ ne contient rien d’autre. Les dérivées partielles sont des équations indépendantes, chacune étant de nouveau le problème à un paramètre :

$$\theta = 0{,}72, \qquad \theta_1 = \tfrac{12}{18} = 0{,}666667, \qquad \theta_2 = \tfrac{2}{7} = 0{,}285714 .$$

Nelder–Mead sur la vraisemblance complète à trois paramètres tombe à $1{,}4 \times 10^{-8}$ près de ces valeurs, pour une log-vraisemblance de $-30{,}468975$.

Ce découplage est toute la raison pour laquelle l’apprentissage d’un réseau bayésien à données complètes est rapide. Chaque table de probabilités conditionnelles s’ajuste en comptant à l’intérieur de son propre cas de conditionnement, sans recherche ni itération - un ensemble de problèmes de comptage indépendants plutôt qu’une optimisation jointe.

La figure s’ouvre avec les deux curseurs d’emballage sur les valeurs arrondies $0{,}67$ et $0{,}29$, si bien que sa log-vraisemblance totale affiche $-30{,}469740$. Appuyez sur caler sur les estimations comptées : les curseurs passent aux valeurs du maximum de vraisemblance, et le total au $-30{,}468975$ cité plus haut.

C. Le cas continu, et pourquoi les moindres carrés

Pour $N$ tirages d’une gaussienne, annuler les deux dérivées partielles donne

$$\mu = \frac{\sum_j x_j}{N}, \qquad \sigma = \sqrt{\frac{\sum_j (x_j - \mu)^2}{N}} .$$

Notez le dénominateur. Sur dix mesures de somme $51{,}0$ dont les écarts quadratiques somment à $3{,}98$, cela donne $\mu = 5{,}1$ et $\sigma = 0{,}630872$, là où diviser par $N-1$ donne $0{,}664998$ - soit un facteur $\sqrt{N/(N-1)} = 1{,}054093$ d’écart. Les deux répondent correctement à des questions différentes : l’une maximise la vraisemblance, l’autre est sans biais. On n’a jamais demandé au maximum de vraisemblance d’être sans biais.

Un corollaire utile en tombe. Ajustez $y$ comme normal autour de $\theta_1 x + \theta_2$ à variance fixée, et la seule part de la log-vraisemblance dépendant des paramètres est $-\sum_j (y_j - \theta_1 x_j - \theta_2)^2$. Minimiser l’erreur quadratique est le maximum de vraisemblance sous bruit gaussien, ce qui explique pourquoi les moindres carrés sont le choix par défaut et non une commodité consacrée par l’usage.

D. Ce qu’il fait d’un événement jamais vu

Déballez un bonbon, trouvez-le à la cerise, et la recette annonce $\theta = 1$ : le citron est impossible, de probabilité exactement nulle, affirmation dont aucune preuve ultérieure ne permet de ressortir par multiplication. Le maximum de vraisemblance lit « pas encore observé » comme « ne peut pas se produire ».

La réparation bayésienne est un a priori. Pour $\theta \in [0,1]$, le choix naturel est une loi Beta, dont la propriété utile est la conjugaison : un a priori $\text{Beta}(a,b)$ avec $c$ cerises et $\ell$ citrons donne un a posteriori $\text{Beta}(a+c, b+\ell)$. La mise à jour est une addition, et l’a posteriori reste dans la même famille : la croyance peut donc être mise à jour indéfiniment sans que la représentation grossisse.

$\text{Beta}(a,b)$ se comporte comme $a+b-2$ observations imaginaires déjà comptées. Voyez $\text{Beta}(2,2)$ - un bonbon imaginaire de chaque parfum - traiter le cas pathologique :

L’a priori fait son travail tôt puis s’efface : il est la différence entre $0{,}6$ et une prétention à la certitude à une observation, et vaut trois millièmes et demi à 250. Notez aussi que le maximum de vraisemblance est exactement le MAP sous a priori uniforme, et qu’ajouter un à chaque effectif - le bricolage de terrain standard - est la moyenne a posteriori sous $\text{Beta}(1,1)$. C’était un a priori depuis toujours.

E. Bayes naïf, et un zéro

Un modèle de Bayes naïf suppose les attributs conditionnellement indépendants sachant la classe, donc $P(C, x_1, \ldots, x_n) = P(C)\prod_i P(x_i \mid C)$ : pour $n$ attributs booléens, $2n+1$ paramètres, tous ajustés par comptage.

Prenons 14 articles étiquetés théorique ou appliqué, décrits par le fait que chacun contient une preuve, utilise un jeu de données et rapporte un banc d’essai. Six sont théoriques et huit appliqués, les a priori valent donc $3/7$ et $4/7$ :

Un article avec preuve et rien d’autre obtient $5/21$ contre $1/448$, soit une probabilité a posteriori de $320/323 = 0{,}990712$. Sensé.

Regardez maintenant le zéro. Aucun article théorique ne rapporte de banc d’essai, donc $P(\text{banc} = 1 \mid \text{théorique}) = 0$. Classons un article avec preuve, sans jeu de données et avec banc d’essai : le score théorique est un produit contenant ce zéro, il vaut donc exactement zéro. La probabilité a posteriori $P(\text{théorique})$ est nulle quelle que soit la preuve, quel que soit l’a priori. Une valeur d’attribut absente des données d’entraînement détient un droit de veto sur la prédiction entière - et en classification de textes, où la plupart des mots manquent à la plupart des classes, c’est la situation ordinaire et non un cas limite.

Le lissage add-one change $0/6$ en $1/8$, et le même article obtient $105/4096$ contre $27/1000$ : une probabilité a posteriori de $4375/8983 = 0{,}487031$ contre $0{,}512969$. Une quasi-égalité honnête au lieu d’une certitude, et le classifieur lissé étiquette encore correctement les 14 articles d’entraînement.

L’hypothèse d’indépendance est bien sûr fausse - les articles à bancs d’essai tendent à avoir des jeux de données - et partout où les attributs sont dépendants au sein d’une même classe, les indices partagés sont comptés deux fois : il ne faut donc pas croire les probabilités. Les classements survivent quand même, parce que la décision est un $\arg\max$ et que le double comptage gonfle généralement les deux scores ensemble. Fiez-vous à la classe, pas au nombre.

F. Quand les effectifs ne peuvent pas être relevés

Tout ce qui précède exigeait des données complètes. Cachez une variable - de quel groupe vient un point, quel thème a écrit un document - et la vraisemblance d’un exemple observé devient une somme sur ce que la variable cachée aurait pu être :

$$P(x \mid \theta) = \sum_{z} P(x, Z = z \mid \theta).$$

Le logarithme d’une somme ne se scinde pas : les paramètres ne se découplent plus et il n’y a pas de forme close à annuler.

L’espérance–maximisation substitue des effectifs espérés aux effectifs qu’il ne peut pas relever :

$$\theta^{(i+1)} = \arg\max_{\theta} \sum_{z} P(Z = z \mid \mathbf{x}, \theta^{(i)}) \, L(\mathbf{x}, Z = z \mid \theta).$$

L’étape E calcule la loi a posteriori des variables cachées sous les paramètres courants - l’appartenance fractionnaire attribuée à un point est sa responsabilité. L’étape M applique les formules à données complètes en remplaçant chaque effectif par une somme de responsabilités. Pour un mélange de gaussiennes, cela donne

$$r_{jk} = \frac{w_k \mathcal{N}(x_j \mid \mu_k, \sigma_k)}{\sum_{k'} w_{k'} \mathcal{N}(x_j \mid \mu_{k'}, \sigma_{k'})}, \qquad w_k = \frac{n_k}{N}, \quad \mu_k = \frac{\sum_j r_{jk}x_j}{n_k}, \quad \sigma_k = \sqrt{\frac{\sum_j r_{jk}(x_j - \mu_k)^2}{n_k}},$$

avec $n_k = \sum_j r_{jk}$. Ce sont les formules gaussiennes de la section C, pondérées.

G. Une exécution mesurée, et là où le k-moyennes perd

Vingt points sur une droite : huit d’une composante étroite près de zéro ($-0{,}8$, $-0{,}7$, $-0{,}2$, $0{,}0$, $0{,}1$, $0{,}5$, $1{,}1$, $1{,}3$) et douze d’une composante bien plus large près de cinq ($1{,}7$, $3{,}0$, $3{,}3$, $3{,}4$, $4{,}0$, $4{,}2$, $4{,}6$, $4{,}8$, $6{,}9$, $7{,}1$, $7{,}2$, $9{,}2$), les étiquettes étant retirées.

Depuis un départ grossier - moyennes 0 et 5, écarts-types tous deux égaux à 1 - la log-vraisemblance monte de $-56{,}616239$ à $-46{,}633131$ en 82 itérations, sans jamais redescendre, et se fixe sur

$$w = (0{,}347288, 0{,}652712), \quad \mu = (0{,}128189, 4{,}581627), \quad \sigma = (0{,}731077, 2{,}367312).$$

La plus grande responsabilité par point retrouve les vingt étiquettes cachées.

La figure s’arrête à l’itération 81, une avant les 82 annoncées plus haut, parce que sa tolérance d’arrêt diffère ; la log-vraisemblance de départ et d’arrivée, $-56{,}616239$ et $-46{,}633131$, est la même que dans l’exécution décrite ici.

La montée monotone est garantie : chaque itération maximise une borne inférieure touchant la log-vraisemblance aux paramètres courants, donc une baisse signale un bogue. Le maximum global ne l’est pas - sur 400 relances aléatoires, 385 ont atteint $-46{,}633131$ et 15 se sont arrêtées à $-48{,}277387$, un point fixe moins bon dont aucune itération ne permet de sortir.

Comparez maintenant le k-moyennes sur les mêmes points. Sa coupure optimale - vérifiée en énumérant les 19 partitions contiguës, ce n’est donc pas un minimum local - a pour centres $0{,}333333$ et $5{,}245455$, une somme des carrés intra-groupe de $47{,}347273$, et elle place $x = 1{,}7$ dans le groupe étroit. Cela fait un point d’écart avec la réponse d’EM et un point d’écart avec la vérité.

La raison est instructive. $x = 1{,}7$ se trouve à $1{,}571811$ de la moyenne étroite ajustée et à $2{,}881627$ de la large : la seule distance le livre, et la distance est tout ce dont dispose le k-moyennes. EM compare des densités :

$$0{,}347288 \times \mathcal{N}(1{,}7 \mid 0{,}128189, 0{,}731077) = 0{,}018788, \qquad 0{,}652712 \times \mathcal{N}(1{,}7 \mid 4{,}581627, 2{,}367312) = 0{,}052436,$$

soit des responsabilités de $0{,}263789$ et $0{,}736211$. La composante large est 3,24 fois plus étalée et porte le poids le plus lourd, et les deux comptent. Le point est plus éloigné de cette composante et reste plus susceptible d’en provenir.

Ailleurs, les responsabilités sont le plus souvent tranchées mais pas partout : $x = 1{,}1$ se partage $0{,}677$ / $0{,}323$ et $x = 1{,}3$ se partage $0{,}555$ / $0{,}445$. EM ajuste des largeurs de composantes et des poids de mélange, que le k-moyennes ne représente pas du tout.

Points clés

• À données complètes, le maximum de vraisemblance tient en trois temps et la réponse est un rapport d’effectifs ; les paramètres d’un réseau se découplent, si bien que l’ajuster est un ensemble de problèmes de comptage indépendants.
• La gaussienne du maximum de vraisemblance divise par $N$, non par $N-1$, et elle explique pourquoi les moindres carrés sont la bonne perte sous bruit gaussien.
• Le maximum de vraisemblance attribue une probabilité nulle à l’inobservé, ce qui détruit une prédiction de Bayes naïf par un seul facteur nul. Un a priori Beta est la réparation de principe, et le lissage add-one en est un cas particulier.
• Les variables cachées mettent une somme dans le logarithme et brisent le découplage. EM remplace les effectifs par des effectifs espérés, ne diminue jamais la vraisemblance et n’atteint qu’un maximum local - relancez-le donc.
• Parce qu’EM modélise largeur et poids plutôt que la seule distance, il retrouve des structures inaccessibles à l’affectation dure.

Et ensuite

Toutes les instances d’EM vues ici ajustaient un modèle statique. Les deux mêmes étapes ajustent un modèle qui change dans le temps - l’étape E devient le lissage avant-arrière, et la raison pour laquelle il faut un lissage plutôt qu’un filtrage est qu’estimer une transition exige des indices postérieurs à celle-ci.