8.4 Algorithme VEM

Nous avons vu qu’avec l’approximation variationnelle le VE-step consiste à maximiser le critère \(\mathbb Q\mapsto J(\mathbb Q, \theta')= \mathcal H(\mathbb Q) + \mathbb E_{\mathbb Q}\left[\log \mathbb P_{\theta'}(\mathbf A,\mathbf Z) \right]\), où \(\theta'\) désigne le valeur courante du paramètre \(\theta\). Il est intéressant de noter que la maximisation du M-step de l’algorithme VEM \(\theta\mapsto \mathbb E_{\tilde{\mathbb Q}}[\log \mathbb P_{\theta}(\mathbf A, \mathbf Z)]\) est équivalent à la maximisation \(\theta\mapsto J(\tilde{\mathbb Q}, \theta)\), car \(\mathcal H(\mathbb Q)\) ne dépend pas de \(\theta\). Autrement dit, on peut voir l’algorithme VEM comme un algorithme de maximisation \((\mathbb Q, \theta)\mapsto J(\mathbb Q, \theta)\) en alternant la maximisation entre \(\mathbb Q\) et \(\theta\). Nous pouvons alors réécrire l’algorithme comme ci-dessous.

Algorithme VEM (Version 2).

Entrée: observations \(\mathbf A\), nombre de blocs \(Q\), point initial \(\theta^0\).

Sortie: Paramètre \(\hat\theta^{k+1}\), loi variationnelle \(\tilde{\mathbb Q}\).

Procédure: A l’itération \(k\):

VE-step: Calculer \[\tilde{\mathbb Q}=\arg\max_{\mathbb Q\in\mathcal Q}J(\mathbb Q, \theta^k).\]
M-step: Calculer \[\begin{align*} \theta^{k+1} =\arg\max_{\theta\in\Theta}J(\tilde{\mathbb Q}, \theta). \end{align*}\]

En fait, \(J(\mathbb Q, \theta)\) est une borne inférieure de la log-vraisemblance des données incomplètes \(\ell(\theta) = \log(\mathbb P_{\boldsymbol \theta}(\mathbf A))\), aussi appelé ELBO pour evidence lower bound.

Theorem 8.1 On a \[\ell(\theta)\geq J({\mathbb Q}, \theta)\quad\text{pour tout }\theta\in\Theta, \mathbb Q\in\mathcal Q.\]

Proof. En (8.6) on a montré que \[\begin{align*} \mathrm{KL}\left(\mathbb Q~\|~\mathbb P_{\theta}(\mathbf Z|\mathbf A)\right) &= -\mathcal H(\mathbb Q) - \mathbb E_{\mathbb Q}\left[\log \mathbb P_{\theta}(\mathbf A,\mathbf Z) \right] +\mathbb E_{\mathbb Q}\left[\underbrace{\log \mathbb P_{\theta}(\mathbf A)}_{=\ell(\theta) \text{ (constante en }\mathbf Z)}\right]\\ &= - J(\mathbb Q, \theta) +\ell(\theta). \end{align*}\] Par la positivité de la divergence de Kullback-Leibler, il s’en suit que \[\begin{align*} \ell(\theta) &= J(\mathbb Q, \theta) + \mathrm{KL}\left(\mathbb Q~\|~\mathbb P_{\theta}(\mathbf Z|\mathbf A)\right)\\ &\geq J(\mathbb Q, \theta). \end{align*}\]

En général, il n’y a pas de garantie de convergence de l’algorithme VEM vers le maximum de vraisemblance. En revanche, en pratique ça marche très bien. Et dans le cas particulier du SBM, il existe des résultats théoriques qui justifient son utilisation (en gros, asymptotiquement, l’approximation variationnelle est bonne, i.e. on a convergence vers la vraie loi conditionnelle).

M-step dans le SBM. A l’étape M, on maximise le critère \(J(\mathbb Q, \boldsymbol\theta)\) en \(\boldsymbol \theta\) qui a deux parties: \(\boldsymbol \theta=(\boldsymbol \pi,\boldsymbol \gamma)\). On voit en (8.7) que \(J\) n’a pas de termes qui fait intervenir les deux paramètres \(\boldsymbol \pi\) et \(\boldsymbol \gamma\). On peut alors traiter la maximisation de \(J\) en \(\boldsymbol \pi\) indépendamment de celle en \(\boldsymbol \gamma)\).

Proposition 8.2 (M-step en \(\boldsymbol\pi\)) Soient \((\tau_{i,q})_{i,q}\) les paramètres variationnels courants. La solution du M-step en \(\boldsymbol \pi\) est explicite et donnée par \[ \forall 1\le q \le Q, \quad \hat \pi_q = \frac 1 n \sum_{i=1}^n \tau_{i,q}. \]

Proof. On obtient le résultat par les dérivées partielles de \(J(\mathbb Q, \boldsymbol\theta)\) par rapport aux \(\pi_q\) et en ajoutant la contrainte \(\sum_q \hat \pi_q =1\).

Pour ce qui est de la maximisation en les \(\gamma_{q \ell}\), cela dépend de la famille de lois \(F(\cdot ; \gamma)\) que l’on considère. Prenons le cas simple d’un graphe binaire, où \(F(\cdot ; \gamma)\) est la loi de Bernoulli de paramètre \(\gamma\).

Proposition 8.3 (M-step en \(\boldsymbol\gamma\) dans le SBM binaire) Soient \((\tau_{i,q})_{i,q}\) les paramètres variationnels courants. Dans le SBM bianire, la solution du M-step en \(\boldsymbol \gamma\) est explicite et donnée par \[ \hat \gamma_{q,\ell} = \frac{ \sum_{i\neq j} \tau_{i,q} \tau_{j,\ell} A_{i,j}} {\sum_{i \neq j} \tau_{i,q} \tau_{j,\ell} },\quad q\leq \ell. \]

Proof. Le terme de \(J\) qui dépend des \(\gamma_{q,\ell}\) s’écrit \[\begin{align*} \sum_{1\le q,\ell \le Q} \sum_{i <j} &\tau_{i,q} \tau_{j,\ell} \log [\gamma_{q,\ell}^{A_{i,j}} (1-\gamma_{q,\ell} )^{1-A_{i,j}}] \\ &= \sum_{1\le q,\ell \le Q} \sum_{i< j} \tau_{i,q} \tau_{j,\ell} \left[ A_{i,j} \log \gamma_{q,\ell} + (1-A_{i,j}) \log (1-\gamma_{q,\ell}) \right]. \end{align*}\] On obtient le résultat par les dérivées partielles de ce terme par rapport aux \(\gamma_{q,\ell}\).

On peut interprêter le paramètre \(\hat \gamma_{q,\ell}\) comme la fréquence moyenne d’arêtes entre les groupes \(q\) et \(\ell\). En fait, dans le cas idéal tous les paramètres variationnels \(\tau_{i,q}\) ne prennent que deux valeurs: 0 et 1. Dans ce cas, les \((\tau_{i,q})_{i,q}\) indiquent l’appartenance des noeuds au \(Q\) groupes et \(\hat \gamma_{q,\ell}\) est la proportion d’arêtes présentes entre les noeuds dans les groupes \(q\) et \(\ell\).

Dans le cas général, où chaque \(\tau_{i,q}\) estime la probabilité que le noeud \(i\) appartient au groupe \(q\), \(\hat\gamma_{q,\ell}\) est une moyenne pondérées par les poids \(\tau_{i,q}\tau_{j,\ell}\) qui prend en compte l’incertitude qu’on a sur le clustering des noeuds.

Typiquement, les sommes qui apparaissent dant l’estimateur du maximum de vraisemblance de \(\gamma\) dans la famille de lois \(\{F(\cdot;\gamma)\}_\gamma\) deviennent des sommes pondérées dans le M-step de l’algorithme VEM et les poids sont donnés par les paramètres variationnels \((\tau_{i,q})_{i,q}\)