Projection Convexe pour Garantir l'Inégalité Triangulaire (Bachelor’s Report)

Institution : Collège de France – CIRB, Équipe « Ecology & Evolution of Health »
Programme : Licence (Bachelor)
Auteur : Nassim Arifette
Encadrant : Laurent Jacob
Période : Jusqu’en juillet 2023

Vue d’ensemble du projetCopy link to section

Ce travail présente une méthode pour intégrer, pendant l’entraînement d’un Transformer phylogénétique (Phyloformer), une projection convexe sur le cône métrique afin de garantir que les matrices de distances prédites respectent toujours l’inégalité triangulaire. Nous comparons le modèle de base et la version « metric-nearness » via des métriques de perte L1 et de qualité topologique (distance RF).

Contexte & MotivationCopy link to section

• Phylogénie : reconstruction rapide d’arbres évolutifs à partir d’alignements de séquences multiples (MSA).
• Transformers comme Phyloformer offrent de la vitesse, mais leurs sorties n’assurent pas la cohérence métrique (violations possibles de l’inégalité triangulaire).
• Importance : des distances métriques garantissent la stabilité des algorithmes de reconstruction d’arbres (Neighbor-Joining) et l’interprétabilité des résultats.

Données & MatérielCopy link to section

• Dataset : 1 000 séquences génétiques, distances de référence calculées par une méthode classique.
• Infrastructure : GPU Nvidia Tesla V100 (32 Go), 30 min par configuration.
• Paramètres :
  • Époques : 20
  • Learning rates : 1e-3 → 1e-6
  • Batch size : 8
  • Optimiseur : Adam
  • Projection : 1 itération de Dykstra‐like par batch

MéthodeCopy link to section

1. Prédiction : $D_{hat} = f_{\theta}(X)$, matrice symétrique, diag zéro
2. Projection : $D_{tilde} = Proj_{Mcone}(D_{hat})$ via un algorithme de proximité métrique $\ell_2$ (variante Brickell et al.)
3. Calcul de perte : L = ||D_tilde - D_star||_1
4. Mise à jour : descente de gradient sans rétroprop à travers la projection

Résultats clésCopy link to section

• Projection : élimine strictement toutes les violations métriques.
• Impact topologique : la qualité RF des arbres Neighbor-Joining reste comparable dans les expériences du rapport.
• Trade-off : légère hausse de la perte L1, mais matrices désormais théoriquement cohérentes.

LimitationsCopy link to section

• Convergence : entraînement limité à 20 époques.
• Un seul dataset : généralisation non évaluée sur d’autres alignements.

Recommandations pratiquesCopy link to section

• Pour des analyses requérant des distances métriques (clustering, MDS, NJ), ajouter une projection en post-processing ou pendant l’entraînement.
• Ajuster le nombre d’itérations de projection (ℓ₁ vs ℓ₂) selon le budget de calcul.
• En cas de gros MSA (> 1 000 séquences), étudier des heuristiques ou sous-échantillonnages pour réduire $O(n^3)$ des contraintes.

Perspectives & travaux futursCopy link to section

1. Projection à l’inférence uniquement, pour comparer coût/avantage.
2. Entraînements plus longs et multi-graines pour estimer la variance.
3. Étendre aux normes ℓ₁, pondérées, ou à des contraintes additionnelles (ultramétrie).
4. Publication du code et benchmark sur d’autres référentiels phylogénétiques publics.