École Nationale Supérieure de
Techniques Avancées

Résumé

Ce travail est une analyse du clustering spectral par matrice à noyau dans un contexte de streaming. En supposant que les données x1, x2, . . . arrivent en un flux continu et qu’un petit nombre L d’entre elles peut- être conservé dans le pipeline d’apprentissage, la matrice à noyau de Gram ne peut être calculé qu’autour de sa diagonale : K = X⊤ X ⊙T où X ∈ Rp×n est la matrice des données et T ∈ {0, 1}n×n est un masque ne gardant que les éléments qui peuvent être calculés dans ce cadre en ligne. Lorsque n, p, L → +∞ avec p/n → c ∈ ]0, +∞[ et (2L − 1)/n → ε ∈ ]0, +∞[, on montre comment la distribution spectrale limite de K peut être calculée et on étudie le comportement des valeurs propres et vecteurs propres isolés, qui portent l’information. Cette analyse révèle que c affecte bien plus la performance que ε, qui peut heureusement être gardé petit. On détaille la manière de réaliser un clustering spectral en ligne et on applique notre algorithme à une tâche de classification d’images. Ce travail est un nouveau pas vers une meilleur compréhension du machine learning pour réaliser des algorithmes utilisant efficacement leurs ressources.