Khronos

Description scientifique

L’énorme production de données, connue sous le nom de phénomène du big data, a bouleversé la vision classique dans les domaines scientifiques et informatiques, notamment dans le domaine de l’apprentissage automatique statistique. 

Dans de nombreux problèmes réels, notamment liés à Internet, mais pas seulement, des flux massifs de données sont produits en continu. C'est par exemple le cas de nouveaux types de données décrivant la diffusion d'informations sur les réseaux sociaux (dynamiques sociales), l'organisation du contenu textuel des blogs (modèles thématiques), les différentes activités humaines dans les vidéos (reconnaissance d'actions humaines) et les goûts des utilisateurs (filtrage collaboratif) disponibles sur le Web. 

Au-delà de leur nature séquentielle, les données présentent généralement une structure interne complexe, comme celles décrivant les courbes de consommation électrique, ou pour lesquelles l'hypothèse de base de l'apprentissage automatique stipulant que les observations sont distribuées de manière identique et indépendante par rapport à une distribution de probabilité fixe n'est plus vérifiée. 

L'équipe-action Khronos s'est attachée à concevoir des algorithmes d'apprentissage évolutifs capables de résoudre des tâches complexes telles que la classification multiclasse à grande échelle ou la récupération de signaux, et de traiter des données dont la structure est potentiellement inconnue.

Principaux résultats et travail à venir

Récupération de signal adaptative à grande échelle

Thèse de doctorat de Dmitrii Ostrovskii : Estimation distribuée des signaux non-stationnaires avec une structure locale inconnue

Nous nous intéressons à certains problèmes de statistiques de grande dimension où le signal présente une structure locale inconnue, comme par exemple la récupération d'images texturées, la segmentation de la parole et les problèmes de récupération parcimonieuse en traitement statistique du signal. 

Dans ce cas, il est impossible de calculer a priori un filtre linéaire performant. Nous avons proposé d'utiliser un filtrage non linéaire estimable à partir de données de faible complexité grâce à l'opérateur de transformée de Fourier discrète et à la norme l1. Nous avons fourni dans [2] une condition suffisante simple, appelée invariance par décalage approximative, pour l'efficacité de cette procédure, et nous avons montré que plusieurs modèles statistiques importants satisfont à cette condition, notamment la régression à noyau non paramétrique et l'estimation du signal spectral de raies [3]. 

Nous avons montré que l'invariance par décalage approximative garantit l'existence d'un filtre oracle avec de bonnes performances statistiques, et que le filtre non linéaire appris par notre procédure présente des performances similaires à celles de l'oracle.

Algorithmes d'apprentissage évolutifs pour le filtrage collaboratif distribué et la classification multi-classes à grande échelle

Thèse de doctorat de Bikash Joshi : Algorithmes d'apprentissage pour les grandes masses de données : Application à la classification multi-classes et à l'optimisation distribuée asynchrone

Afin d'éviter une mise à l'échelle indésirable de la complexité de l'échantillon par rapport au nombre de classes, nous avons conçu une nouvelle approche basée sur l'apprentissage d'une combinaison de caractéristiques de similarité entre instances et classes. 

Les similarités sont calculées en identifiant une classe avec l'ensemble de ses exemples représentatifs. Nous avons étudié la cohérence de l'apprentissage avec des paires d'observations et de classes en analysant le graphe de dépendance associé et avons montré qu'une réduction de la classification multiclasse initiale des exemples en une classification binaire de paires d'exemples et de classes permet d'apprendre un vecteur de paramètres unique dont la dimension ne dépend pas du nombre de classes. 

Nous avons démontré empiriquement que cette approche est compétitive par rapport aux approches de classification multiclasse de pointe, notamment en ce qui concerne la macro-mesure F, qui privilégie la prédiction correcte des classes rares plutôt que la précision de la classification. De plus, le nombre de paramètres appris par l'algorithme est de l'ordre de 107 fois inférieur à celui des modèles de classification multiclasses conventionnels, ce qui rend cette approche intéressante pour la classification à grande échelle.

Coordinateurs

Massih-Reza Amini (LIG)

Thomas Burger (CEA)

Julie Fontecave (TIMC-IMAG)

Anatoli Juditsky (LJK)

Valorisation

Collaboration industrielle

Khronos a été le tremplin du projet FUI Calypso (2015-2017) avec Purch et Kelkoo sur la publicité en ligne.

Diffusion scientifique

• Organisation à Grenoble de la Conférence sur l’Apprentissage Automatique (CAP 2017) du 28 au 30 juin 2017.
• En partenariat avec l’équipe-action Persyvact2, organisation à Grenoble du workshop international sur les outils statistiques pour la fouille de données (22 et 23 mai 2016), ainsi que des écoles de printemps et d’été sur les statistiques de grande dimension et l’optimisation pour les big data (juin 2014) et sur l’apprentissage parcimonieux à grande échelle (avril 2015).

Publications significatives

[1] Babbar R., Partalas I., Gaussier E., Amini M.-R., Amblard C. Learning Taxonomy Adaptation in Large-scale Classication. Journal of Machine Learning Research (JMLR), 17(98) :1{37, 2016

[2] Ostrovsky D., Harchaoui Z., Juditsky A., Nemirovski A. Structure-blind signal recovery. 30th Annual Conference on Neural Information Processing Systems (NIPS 29), pp. 4817{4825, 2016.

[3] Harchaoui Z., Juditsky A., Nemirovski A., Ostrovsky D. Adaptive recovery of signals by convex optimization. Proceedings of the 28th Conference on Learning Theory (COLT), pp. 929{955, 2015.

[4] Joshi B., Amini M.-R., Partalas I., Ralaivola L., Usunier N., Gaussier E. On Binary Reduction of Large-scale Multiclass Classication Problems. 14th International Symposium on Intelligent Data Analysis (IDA), pp. 132{144, 2015

[5] Babbar R., Partalas I., Gaussier  E., Amini M.-R. On Flat versus Hierarchical Classi cation in Large-Scale Taxonomies. 27th Annual Conference on Neural Information Processing Systems (NIPS 26), pp.1824{1832, 2013.