L'algorithme de Chow-Liu

le meilleur arbre de dépendances est un arbre couvrant de poids maximal

1 · CRITÈRE

$$\hat T=\arg\max_{T}\;\ell(T),\qquad \ell(T)=n\sum_{(i,j)\in T}\hat I_{ij}\;-\;n\sum_{i=1}^{p}\hat H_i$$

$$\text{cas gaussien : }\quad\hat I_{ij}=-\tfrac12\log\!\left(1-\hat\rho_{ij}^{\,2}\right)$$

2 · KRUSKAL PAS À PAS, OU TON PROPRE ARBRE

arbre construit — clique une arête pour l'ajouter ou l'enlever

critère : arêtes triées par $\hat I_{ij}$ — cliquables aussi

observations $n$ Vrai arbre

Espace ou → : étape de Kruskal. Cliquer une arête passe en mode libre : construis un arbre et compare son poids au maximum. Avec $n$ petit, l'arbre estimé s'écarte du vrai.

3 · RAPPELS

$$p_T(x)=\prod_{i=1}^{p}p(x_i)\prod_{(i,j)\in T}\frac{p(x_i,x_j)}{p(x_i)\,p(x_j)}$$

Dans $\ell(T)$, seul le poids de l'arbre $\sum_{(i,j)\in T}\hat I_{ij}$ dépend de $T$ : on cherche l'arbre couvrant de poids maximal.
Kruskal : arêtes par $\hat I$ décroissant, on garde celles qui ne ferment pas de cycle, jusqu'à $p-1$ arêtes. Coût $O(p^2\log p)$.
Cas gaussien : $\hat I_{ij}$ croît avec $|\hat\rho_{ij}|$, donc même arbre qu'avec les corrélations ; la matrice de précision de l'arbre est nulle hors des arêtes (indépendances conditionnelles).
Si la vraie loi est un arbre, Chow-Liu le retrouve quand $n\to\infty$ ; les arêtes faibles sont les premières confondues quand $n$ est petit.
Ici, le vrai arbre a pour corrélations d'arêtes 0,80 · 0,65 · 0,55 · 0,70 · 0,60 · 0,45 ; les autres corrélations en sont les produits le long des chemins.