Élagage fonctionnel géométrique pour la détection de ruptures dans les modèles de la famille exponentielle à faible dimension.

 La détection de ruptures est un problème central de l’apprentissage non supervisé, notamment en génomique. Nous proposons deux méthodes efficaces d’élagage fonctionnel pour la détection de ruptures dans des modèles de la famille exponentielle de faible dimension (p≤5) : GeomFPOP pour la détection hors ligne de ruptures multiples et MdFOCuS pour la détection en ligne d’une rupture.
Ces méthodes reposent sur des outils de géométrie computationnelle permettant un élagage efficace des candidats et conduisant à une complexité en temps quasi-linéaire. La règle d’élagage de GeomFPOP utilise une heuristique géométrique pour mettre à jour et élaguer les candidats potentiels de rupture au fil du temps. La règle d’élagage de MdFOCuS exploite un lien avec un problème d’enveloppe convexe, ce qui simplifie la recherche de la rupture à élaguer. Ces deux règles montrent des améliorations significatives de la complexité computationnelle pour les modèles de faible dimension (p≤5) dans des études de simulation. Les implémentations Rcpp traitent plus de 2x10^6 observations en une minute pour un signal sans rupture avec un bruit gaussien i.i.d. Les performances sont également confirmées sur des données réelles : des données génomiques pour GeomFPOP et des données de la National Basketball Association (NBA) pour MdFOCuS.

Travail commun avec Gaetano Romano, Paul Fearnhead, Vincent Runge et Guillem Rigaill