Séminaire de Probabilités commun ICJ/UMPA

Partitionnement optimal par minimisation convexe

par Christophe Giraud

Europe/Paris
salle 435 (UMPA)

salle 435

UMPA

Description
Un problème fondamental en analyse de données est de partitionner, en aveugle, des données en K groupes distincts. Ce partitionnement peut être l'objectif final (découverte de "communautés" dans les données) ou une étape intermédiaire permettant de réduire la dimension et/ou la complexité algorithmique lors de l'apprentissage. Nous illustrerons à travers divers modèles probabilistes simples, comment ce partitionnement peut être réalisé à l'aide d'un algorithme de minimisation convexe, pour des vitesses de séparation optimales. Nous expliquerons aussi comment cet algorithme est relié à deux algorithmes standards pour le partitionnement: Kmeans et le spectral clustering.