CAp 2016 - Conférence sur l'Apprentissage Automatique

Programme synthétique

Lundi 04/07/2016

Hackday

Mardi 05/07/2016

08h30 - 09h00Accueil des participants
09h00 - 10h30
Session 1 : Algorithmes de bandit et apprentissage par renforcement
10h30 - 11h00Pause café
11h00 - 12h30
Session 2 : Apprentissage de métriques et de représentations
12h30 - 14h00Déjeuner
14h00 - 15h00Présentation invitée : Alexandre Gramfort
15h00 - 16h00
Session 3 : Neurosciences – Séries temporelles
16h00 - 16h30Pause café
16h30 - 18h15
Session 4 : Optimisation
18h15 - 20h00Apéro - Posters

Mercredi 06/07/2016

Demi-journée industrielle

09h00 - 10h00Présentation invitée : Olivier Chapelle
10h00 - 10h30
Communication industrielle 1
10h30 - 11h00Pause café
11h00 - 12h00Présentation invitée : Cédric Archambeau
12h00 - 12h30
Communication industrielle 2
12h30 - 14h00Déjeuner

Demi-journée structuration de la communauté

14h00 - 16h00Session structuration de la communauté || Session doctorants
16h00 - 16h30AG CAp
17h00 - MinuitVisite aux iles du Frioul et diner

Jeudi 07/07/2016

09h00 - 10h15
Session 5 : Systèmes de recommandation – Multi-agents
10h15 - 10h45Pause café
10h45 - 12h30
Session 6 : Transfert, multi-tâches et multi-vues
12h30 - 14h00Déjeuner
14h00 - 16h00
Session 7 : Parcimonie et approximation de rang faible
16h00 - 16h30Clôture




Conférenciers invités





Programme détaillé

Mardi 5 juillet

  • Session 1 : Algorithmes de bandit et apprentissage par renforcement

    • 09h00 – 09h30    Aurélien Garivier, Pierre Ménard et Gilles Stoltz Explore First, Exploit Next: The True Shape of Regret in Bandit Problem (pdf).

      Résumé: We revisit lower bounds on the regret in the case of multi- armed bandit problems. We obtain non-asymptotic bounds and provide straightforward proofs based only on well- known properties of Kullback-Leibler divergences. These bounds show that in an initial phase the regret grows al- most linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. The proof tech- niques come to the essence of the arguments used and they are deprived of all unnecessary complications.

    • 09h30 – 10h00    Julien Perolat, Bilal Piot, Bruno Scherrer et Olivier Pietquin On the Use of Non-Stationary Strategies for Solving Two-Player Zero-Sum Markov Games (pdf).

      Résumé: The main contribution of this paper consists in extending several non-stationary Reinforcement Learning (RL) algorithms and their theoretical guarantees to the case of γ-discounted zero-sum Markov Games (MGs). As in the case of Markov Decision Processes (MDPs), non-stationary algorithms are shown to exhibit better performance bounds compared to their stationary counterparts. The obtained bounds are generically composed of three terms : 1) a dependency over γ (discount factor), 2) a concentrability coefficient and 3) a propagation error term. This error, depending on the algorithm, can be caused by a regression step, a policy evaluation step or a best-response evaluation step. As a second contribution, we empirically demonstrate, on generic MGs (called Garnets), that non-stationary algorithms outperform their stationary counterparts. In addition, it is shown that their performance mostly depends on the nature of the propagation error. Indeed, algorithms where the error is due to the evaluation of a best-response are penalized (even if they exhibit better concentrability coefficients and dependencies on γ ) compared to those suffering from a regression error.

    • 10h00 – 10h15    Frédéric Guillou, Romaric Gaudel et Philippe Preux Compromis exploration-exploitation pour système de recommandation à grande échelle (pdf).

      Résumé: Les systèmes de recommandation recommandent à des utilisateurs un ou des produits qui pourraient les intéresser. La recommandation se fonde sur les retours des utilisateurs par le passé, lors des précédentes recommandations. La recommandation est donc un problème séquentiel et le système de recommandation recommande (i) pour obtenir une bonne récompense, mais aussi (ii) pour mieux cerné l'utilisateur/les produits et ainsi obtenir de meilleures récompenses par la suite. Quelques approches récentes ciblent ce double objectif mais elles sont trop gourmandes en temps de calcul pour s'appliquer à certaines applications de la vie réelle. Dans cet article, nous présentons un système de recommandation fondé sur la factorisation de matrice et les bandits manchots. Plusieurs expériences sur de grandes base de données montrent que l'approche proposée fournit de bonnes recommendations en moins d'une milli-seconde par recommandation.

    • 10h15 – 10h30    Aurélia Léon et Ludovic Denoyer Policy-gradient Methods for Decision Trees (pdf).

      Résumé: We propose a new type of decision trees able to learn at the same time how inputs fall in the tree and which predictions are associated to the leaves. The main advantage of this approach is to be based on the optimization of a global loss function instead of using heuristic-based greedy techniques, while keeping the good characteristics of decision trees. The learning algorithm is inspired by reinforcement learning and based on gradient-descent based methods, allowing a fast optimization. Moreover the algorithm is not limited to (mono-label) classification task and can be used for any predictive problem while a derivable loss function exist. Experimental results show the effectiveness of the method w.r.t baselines.

  • Session 2 : Apprentissage de métriques et de représentations

    • 11h00 – 11h30    Maria-Irina Nicolae, Eric Gaussier, Amaury Habrard et Marc Sebban Apprentissage de similarités pour la classification de séries temporelles multivariées .

      Résumé: Les séries temporelles multivariées apparaissent naturellement dans de nombreaux domaines d'application, comme la santé, la bioinformatique, le traitement de signal ou encore la finance. La plupart de ces applications nécessitent de pouvoir comparer des séries temporelles entre elles. Dans ce contexte, la DTW est la mesure de comparaison la plus classiquement utilisée car elle permet de tirer partie des similarités ou différences temporelles entre les séries. Cependant, il existe peu de travaux visant à améliorer cette métrique par apprentissage. Dans cet article, nous proposons une nouvelle approche d'apprentissage de similarités basées sur la DTW, afin d'améliorer la tâche de classification de séries temporelles. Notre méthode permet d’utiliser la similarité apprise au sein d’un classifieur linéaire pour lequel nous fournissons des garanties théoriques sous la forme d’une borne en généralisation sur l’erreur de classification. Notre étude expérimentale montre que l'approche proposée est efficace, tout en utilisant des classifieurs parcimonieux.

    • 11h30 – 12h00    Gabriella Contardo et Ludovic Denoyer Apprentissage de représentation pour l’acquisition adaptative de features sous contrainte de coût (pdf).

      Résumé: Ce papier présente différents modèles d'acquisition séquentielle pour le problème d'apprentissage budgété sensible au coût. Nous proposons une formalisation stochastique de ce problème dans lequel nous considérons que les variables des entrées ont un coût. Les modèles proposés se caractérisent par trois aspects clés : (i) ils peuvent acquérir les variables de manière adaptative au regard de l'exemple en entrée, (ii) les variables peuvent être acquises par block (plusieurs à la fois), et (iii) ils reposent sur l'apprentissage de représentation. Ces trois propriétés permettent de passer efficacement à l'échelle, i.e de traiter des datasets où le nombre de features est élevé, et peuvent gérer toute entrée partiellement observée. Nous illustrons l'efficacité de nos approches sur une variété de datasets dans différents cas de coûts.

    • 12h00 – 12h30    Valentina Zantedeschi, Rémi Emonet et Marc Sebban Apprentissage de combinaisons convexes de métriques locales avec garanties de généralisation (pdf).

      Résumé: Ces dix dernières années, l'apprentissage de métriques a permis une amélioration des approches d'apprentissage automatique basées sur des fonctions de distance ou de similarité.  Dans ce contexte, l'apprentissage de \emph{métriques locales} s'est montré très efficace de part sa capacité à prendre en compte les non-linéarités des données et de mieux capturer les caractéristiques de l'application considérée.  Cependant, il est bien connu que l'apprentissage de métriques locales présente un risque de sur-apprentissage et pose des problèmes lors de la comparaison de deux instances qui sont assignées à des modèles locaux différents.  Dans cet article, nous traitons ces problématiques en proposant un nouvel algorithme de combinaison linéaire de modèles locaux (C2LM).  À partir d'un partitionnement de l'espace en régions et d'un modèle (fonction de distance/similarité) pour chaque région, C2LM définit une métrique entre deux points comme une combinaison pondérée de modèles locaux.  Deux termes de régularisation spatiale assurent une évolution graduelle des vecteurs de poids et une influence plus importante des modèles les plus proches.  Notre approche a la particularité d'être définie dans un cadre de régression, de marcher implicitement à différentes échelles et d'être assez générique pour s'appliquer aux similarités et aux distances.  Nous fournissons des garanties théoriques dans le cadre de la robustesse algorithmique.  Les expériences réalisées sur deux jeux de données montrent que C2LM atteint systématiquement une précision en régression meilleure que l'état de l'art, même avec un nombre de paires d'apprentissage limité.

  • Session 3 : Neurosciences - Séries temporelles

    • 14h00 – 15h    Conférence invitée : Alexandre Gramfort, When machines look at neurons: learning from neuroscience time series.

      Résumé : Understanding how the brain works in healthy and pathological conditions is considered as one of the challenges for the 21st century. After the first electroencephalography (EEG) measurements in 1929, the 90’s was the birth of modern functional brain imaging with the first functional MRI (fMRI) and full head magnetoencephalography (MEG) system. By offering noninvasively unique insights into the living brain, imaging has revolutionized in the last twenty years both clinical and cognitive neuroscience. Over the last 10 to 15 years, driven by more open data and recent algorithmic progress the field of brain imaging and electrophysiology has embraced a new set of tools in order to extract knowledge from data. Using statistical machine learning new applications have emerged, going from brain computer interaction systems, "mind reading" and cortical source imaging at a millisecond time scale. In this talk, I will briefly review some statistical and algorithmic challenges raised by the different techniques and show how modern computational and machine learning tools can help uncover neural activations in multivariate time series.

    • 15h00 – 15h30    Sylvain Takerkart, Guillaume Auzias, Lucile Brun et Olivier Coulon An Automatic Brain Morphometry Framework based on Structural Pattern Analysis of Cortical Folding (pdf).

      Résumé: Studying the topography of the cortex has proved valuable in order to characterize populations of subjects. In particular, the recent interest towards the deepest parts of the cortical folds, the sulcal pits, has opened new  avenues in that regard. In this paper, we describe a fully automatic brain morphometry framework based on the study of the spatial organization of cortical folding. Our framework uses attributed graphs to model local patterns of sulcal pits -- the deepest points of the cortical folds, and further relies on three original contributions. First, a graph kernel is defined to provide a new similarity measure between pit-graphs, with few parameters that can be efficiently estimated from the data. Secondly, we present a searchlight scheme dedicated to brain morphometry, yielding dense information maps covering the full cortical surface. Finally, a multi-scale inference strategy is designed to jointly analyze the searchlight information maps obtained at different spatial scales. We demonstrate the effectiveness of our framework by studying gender differences and cortical asymmetries: we show it can both localize informative regions and estimate  their preferred spatial scales, while providing results which are consistent with the literature. Thanks to the modular design of our kernel and the vast array of available kernel methods, it can easily be extended to include a more detailed description of the sulcal patterns and solve different statistical problems. Therefore, we suggest that our framework should be useful for both reaching a better understanding of the normal brain and defining imaging biomarkers in clinical settings.

    • 15h30 – 16h00    Asma Dachraoui, Antoine Cornuejols et Alexis Bondu A Novel Algorithm for Online Classification of Time Series when Delaying Decision is Costly (pdf).

      Résumé: Aiding to make decisions as early as possible by learning from past experiences is becoming increasingly important in many application domains.  In these settings, information can be gained by waiting for more evidences to arrive, thus helping to make better decisions that incur lower misclassification costs, but, meanwhile, the cost associated with delaying the decision generally increases, rendering the decision less attractive. Learning requires then to solve an optimization problem combining two types of competing costs.  In the growing literature on online decision making, very few works have explicitly incorporated the cost of delay in the decision procedure. One recent work \cite{A3DBC:ecml-15} has introduced a general formalization of this optimization problem. However, the algorithm presented there to solve it is based on a clustering step, with all the attendant necessary choices of parameters that can heavily impact the results.  In this paper, we adopt the same conceptual framework but we present a more direct technique involving only one parameter and lower computational demands. Extensive experimental comparisons between the two methods on synthetic and real data sets show the superiority of our method when the classification of the incomplete time series is difficult, which corresponds to a large fraction of the applications.

  • Session 4 : Optimisation

    • 16h30 – 17h00    Igor Colin, Aurélien Bellet, Joseph Salmon et Stéphan Clémençon Un algorithme de Gossip pour l’optimisation décentralisée de fonctions sur les paires (pdf).

      Résumé: In decentralized networks (of sensors, connected objects, etc.), there is an important need for efficient algorithms to optimize a global cost function, for instance to learn a global model from the local data collected by each computing unit. In this paper, we address the problem of decentralized minimization of pairwise functions of the data points, where these points are distributed over the nodes of a graph defining the communication topology of the network. This general problem finds applications in ranking, distance metric learning and graph inference, among others. We propose new gossip algorithms based on dual averaging which aims at solving such problems both in synchronous and asynchronous settings. The proposed framework is flexible enough to deal with constrained and regularized variants of the optimization problem. Our theoretical analysis reveals that the proposed algorithms preserve the convergence rate of centralized dual averaging up to an additive bias term. We present numerical simulations on Area Under the ROC Curve (AUC) maximization and metric learning problems which illustrate the practical interest of our approach.

    • 17h00 – 17h30    Alain Rakotomamonjy, Sokol Koço et Liva Ralaivola Sur l’utilisation du gradient inexact pour l’accélération des méthodes parcimonieuses (pdf).

      Résumé: Dans ce travail, nous nous intéressons à l'adaptation de méthodes parcimonieuses lorsque le gradient de la fonction objective est difficile à calculer, ou son coût de calcul est prohibitif.  Nos contributions se présentent sous deux formes : d'abord nous présentons des méthodes qui permettent de construire des estimations du gradient à partir d'un sous-ensemble des exemples; ensuite, nous proposons des critères d'arrêt liés à la taille des sous-ensembles.  Des justifications théoriques sont données pour chaque contribution.  Dans la partie expérimentale, nous étudions l'impact des méthodes proposées sur deux algorithmes parcimonieux communément utilisés : Frank-Wolfe et Orthogonal Matching Pursuit.  Les résultats sur des exemples jouet montrent que le gradient inexact peut être tout aussi efficace que le gradient complet, à condition que le bon critère d'arrêt soit utilisé.

    • 17h30 – 18h00    Emmanuel Daucé et Hongliang Zhong Optimisation quadratique pour l’apprentissage en ligne d’un bandit contextuel (pdf).

      Résumé: Nous développons un algorithme d'apprentissage en ligne de classifieurs multiclasses dans le cas où l'information de classification apparaît sous une forme binaire (réponse correcte ou incorrecte). L'absence d'information de label explicite conduit à échantillonner de manière aléatoire l'espace des labels, sur le modèle des bandits contextuels.  L'algorithme développé repose sur l'optimisation à chaque essai d'une fonction de coût, sur le modèle de l'approche ``Passive Agressive'' (Crammer et al, 2006).  L'analyse mathématique permet de mettre en évidence des bornes sur la somme des coûts cumulés, à la fois dans le cas séparable et dans le cas non séparable, comparables aux bornes obtenues dans le cas supervisé.  Les expériences numériques confirment le bon comportement de l'algorithme d'apprentissage, à la fois sur des données de grande dimension et sur des jeux de données non-linéairement séparables.

    • 18h00 – 18h15    Albert Thomas, Stéphan Clémençon et Alexandre Gramfort Learning Hyperparameters for Unsupervised Anomaly Detection (pdf).

      Résumé: Unsupervised anomaly detection boils down to the estimation of a scoring function that can rank observations according to their degree of abnormality. While all available algorithms require the specification of parameters, no labelled data is available to assess their performance, making parameter tuning a challenge. This work presents a two step solution to this issue. The first step consists in using empirical estimates of Mass Volume (MV) curves. The area under the MV curves is computed on left-out data to select the best hyperparameters while preventing overfitting. The second step uses the concept of model ensembling. Using several random splits of the data, the variance of the estimates is reduced by averaging the solutions obtained for each split. The method is applied to state-of-the-art algorithms belonging to the family of kernel, nearest neighbors and partitioning methods. Results demonstrate that the proposed approach offers a viable solution to the important practical problem of model selection, and that it allows to boost performance of anomaly detection algorithms on both simulated and real data sets.

Mercredi 6 juillet

  • Session industrielle I

    • 9h00 – 10h    Conférence invitée : Olivier Chapelle, Prédiction des taux de réponse pour la publicité en ligne.

      Résumé : Les estimations de taux de click et de conversion sont des tâches au coeur de la publicité en ligne. Je vais présenter un ensemble de techniques d’apprentissage basé sur la régression logistique qui est spécifiquement conçu pour faire face aux spécificités de la publicité en ligne. Le système qui en découle présente les caractéristiques suivantes : il est facile à mettre en oeuvre et à déployer; il peut être entrainé sur des téraoctets de données; et il fournit des modèles avec une précision au niveau de l’état de l’art.

    • 10h – 10h30    Communication industrielle 1 : Yann Jacob, Tony Bourdier et Sandra Mellot Prédiction du comportement de navigation des internautes pour la levé de fonds en ligne (pdf).

      Résumé: La collecte de fonds au profit d'associations s'effectue de plus en plus en ligne, ce qui offre des possibilités nouvelles de personnalisation dans le processus de sollicitation. Des études empiriques montrent que les internautes sont individuellement sensibles aux interfaces web et qu'elles influent significativement sur leurs réactions. La personnalisation en temps réel des interfaces permettrait ainsi de maximiser la collecte. Cette pratique est déjà répandue dans le cadre du ciblage publicitaire pour le e-commerce, mais n'a jamais été proposée pour la levée de fonds en ligne. Contrairement au ciblage publicitaire, il ne s'agit pas recommander des produits (inexistants dans ce contexte) mais personnaliser des interfaces pour favoriser les réactions positives des internautes, ce qui nécessite une approche spécifique. Pour cela nous avons défini et collecté un nouveau type de données basé sur l'usage du site web : les types d'interactions. Volontairement contraints par des considérations éthiques, en nous empêchant en particulier de collecter des données personnelles sur les internautes, nous émettons l'hypothèse que les données d'usage permettent de prédire la réaction des utilisateurs à une interface. Nous proposons un nouveau modèle de prédiction du comportement des utilisateurs, basé sur un réseau de neurones récurrent. Nous validons notre hypothèse en mesurant les performances de notre modèle à partir de données collectées durant 8 mois sur le site d'une grande ONG. Les résultats montrent que le style d'interaction est un facteur significatif pour prédire le comportement d'un internaute.

  • Session industrielle II

    • 11h00 – 12h    Conférence invitée : Cédric Archambeau, Amazon: A Playground for Machine Learning.

      Résumé : Within Amazon, a company with over 200 millions of active consumers, over 2 million active seller accounts and over 180.000 employees, there are hundreds of problems which can be tackled using Machine Learning. In this talk, I will give an overview of a number of Machine Learning applications and explain how they fit within the Amazon ecosystem. While Machine Learning is routinely used in recommendation, fraud detection and ad allocation, it plays a key role in devices such as the Kindle or the Echo, as well as the automation of Kiva enabled fulfilment centres, statistical machine translation or automated Fresh produce inspection.

    • 12h00 – 12h30    Communication industrielle 2 : Antoine Bonnefoy, Ismael Ouamlil, Jean-Baptiste Veyrieras et Pierre Mahé Sélection de variables structurée par régularisation jointe dans un cadre multi-tâches (pdf).

      Résumé: Motivated by diagnostic applications in the field of clinical microbiology, we introduce a joint input/output regularization method to perform structured variable selection in a multi-task setting where tasks can exhibit various degrees of correlation. Our approach extensively relies on the tree-structured group-lasso penalty and explicitly combines hierarchical structures defined across features and task by means of the Cartesian product of graphs to induce a global hierarchical group structure. A vectorization procedure is then used to solve the resulting multi-task problem with standard mono-task optimization algorithms developed for the overlapping group-lasso problem. Experimental results on simulated and real data demonstrate the interest of the approach.

Jeudi 7 juillet

  • Session 5 : Systèmes de recommandation - Multi-agents

    • 09h00 – 09h15    Damien Sileo et Vincent Guigue Apprentissage relationnel pour la recommandation et la prédiction de données manquantes (pdf).

      Résumé: La recommandation joue le rôle primordial de mettre en relation des utilisateurs avec ce qui leur correspond le mieux. Les applications s’étendent du ciblage publicitaire aux catalogues de films et plus généralement, c’est l’ensemble des outils d’accès à l’information en ligne qui se personnalise. Les historiques de notes ou de navigation sont les principales sources d’information pour produire les recommandations en établissant des profils qui caractérisent des utilisateurs et les contenus. Un des enjeux majeurs du domaine est d’exploiter toutes les informations sur le contenu et/ou l’utilisateur pour améliorer la pertinence des recommandations. Dans cette étude, nous proposons un cadre unifié axé à la fois vers la prédiction de notes et celle des attributs contextuels des items et des utilisateurs (genre des films, sexe des utilisateurs...). Nous utilisons le formalisme de l’apprentissage de représentations pour projeter l’ensemble des concepts dans un espace latent puis nous tirons parti des relations explicites pour prédire les données manquantes ou implicites. Nous évaluons notre approche sur le jeu de données Movielens et obtenons des résultats qui dépassent l’état de l’art.

    • 09h15 – 09h30    Florian Strub, Jérémie Mary et Romaric Gaudel Filtrage Collaboratif Hybride avec des Auto-encodeurs (pdf).

      Résumé: Le filtrage collaboratif (CF) exploite les retours des utilisateurs pour leur fournir des recommandations personnalisées. Lorsque ces algorithmes ont accès à des informations complémentaires, ils ont de meilleurs résultats et gèrent plus efficacement le démarrage à froid. Bien que les réseaux de neurones (NN) remportent de nombreux succès en traitement d'images, ils ont reçu beaucoup moins d'attention dans la communauté du CF. C'est d'autant plus surprenant que les NN apprennent comme les algorithme de CF une représentation latente des données. Dans cet article, nous introduisons une architecture de NN adaptée au CF (nommée CFN) qui prend en compte la parcimonie des données et les informations complémentaires. Nous montrons empiriquement sur les bases de données MovieLens et Douban que CFN bât l'état de l'art et profite des informations complémentaires. Nous fournissons une implémentation de l'algorithme sous forme d'un plugin pour Torch.

    • 09h30 – 09h45    Elie Guàrdia Sebaoun, Vincent Guigue et Patrick Gallinari Apprentissage de trajectoires temporelles pour la recommandation dans les communautés d’utilisateurs (pdf).

      Résumé: Les systèmes de recommandation sont devenus centraux, non seulement dans le e-commerce mais dans la façon même dont on accède à l'information. Des problèmes de CRM aux réseaux sociaux, la personnalisation est omniprésente et propose de nouveaux défis scientifiques aussi bien en terme d'efficacité que de passage à l'échelle. Les méthodes à variable latentes tendent à exploiter des informations contextuelles de plus en plus variées (information textuelle, interactions sociales, temps) et permettent la définition de profils utilisateur de plus en plus riches. Cet article se concentre sur les aspects temporels de la contextualisation et, plus précisément, les dynamiques utilisateur. En caractérisant les transition des utilisateurs entre les items, nous proposons un modèle de recommandation personnalisée capable d'expliquer ses propositions. En prédisant le prochain produit qu'un utilisateur va voir et s'il va ou non l'aimer, notre système devient proactif.

    • 09h45 – 10h00    Jonathan Louedec, Laurent Rossi, Aurélien Garivier, Chevalier Max et Josiane Mothe Algorithme de bandit et obsolescence : un modèle pour la recommandation (pdf).

      Résumé: Un nombre croissant de systèmes numériques font appel à des algorithmes de bandits pour combiner efficacement exploration de l'environnement et exploitation de l'information accumulée. Les modèles de bandits classiques sont toutefois assez naïfs: ils se bornent à un nombre fixé de choix disponibles (appelés bras), et à des réponses ne variant pas au cours du temps. Ces limitations. Pour les moteurs de recommandation, par exemple, il s'agit de limitations sévères: de nouveaux items à recommander apparaissent régulièrement, et les anciens ont une tendance prévisible à perdre de l'attractivité. Pour faire face à ces problèmes, des stratégies capables de gérer l'évolution temporelle du gain moyen associé à chaque bras ont été proposées. Si ces stratégies sont assez générales, elles ne sont pas forcément les plus efficaces dans le cas où la forme de cette évolution temporelle est largement connue a priori.  Dans cet article nous proposons deux nouvelles stratégies capable de prendre en compte d'une part l'obsolescence progressive de chaque bras, et d'autre part l'arrivée de nouveaux bras: Fading-UCB, pour laquelle nous fournissons une analyse détaillée de la borne supérieure de regret, et Trust and abandon. Nous montrons expérimentalement que les deux stratégies proposées permettent d'obtenir de meilleures performances que celles obtenues par les stratégies de l'état de l'art.

    • 10h00 – 10h15    Rodrigues Christophe, Henry Soldano, Gauvain Bourgne et Celine Rouveirol Collaborative Decision in Multi Agent Learning of Action Models (pdf).

      Résumé: We address collaborative decision in the Multi-Agent Consistency-based online learning of relational action models. This framework considers a community of agents, each of them learning and rationally acting following their relational action model. It relies on the idea that when agents communicates, on a utility basis, the observed effect of past actions to other agents, this results in speeding up the online learning process of each agent in the community. In the present article, we discuss how collaboration in this framework can be extended at the individual decision level. More precisely, we first discuss how an agent ability to predict the effect of some action in its current state is enhanced when it takes into account all the action models in the community. Second, we consider the situation in which an agent fails to produce a plan using its own action model, and show how it can interact with the other agents in the community in order to select an appropriate action to perform. Such  a community aided action selection strategy will help the agent to revise its action model and to increase its ability to solve its current goal as well as future ones.

  • Session 6 : Transfert, multi-tâches et multi-vues

    • 10h45 – 11h15    Maxime Sangnier, Olivier Fercoq et Florence d’Alché-Buc Multi-task Learning for Quantile Curves Estimation (pdf).

      Résumé: Building upon kernel-based multi-task learning, a novel methodology for estimating and predicting simultaneously several conditional quantiles is proposed. We particularly focus on curbing the embarrassing phenomenon of quantile crossing. Moreover, this framework comes along with theoretical guarantees and an efficient coordinate descent learning algorithm. Numerical experiments on benchmark datasets highlight the enhancements of our approach regarding the prediction error, the crossing occurrences and the training time.

    • 11h15 – 11h45    Michaël Perrot et Amaury Habrard Transfert et bornes rapides pour l’apprentissage de métriques (pdf).

      Résumé: Dans ce papier nous nous intéressons au transfert d'hypothèses pour l'apprentissage de métriques. L'idée est de considérer que, lors de la phase d'apprentissage, l'algorithme a accès à une métrique source venant d'un problème différent mais raisonnablement proche du problème considéré. L'intérêt de cette métrique source est d'apporter une information supplémentaire. Pour prendre en compte cette nouvelle information nous considérons ici que l'algorithme d'apprentissage résout un problème d'optimisation avec régularisation biaisée. Le but de ce papier est de présenter une analyse théorique de ce cadre de travail. Ainsi, en considérant des contraintes raisonnables sur la fonction de perte, nous montrons qu'il est possible de dériver une borne en généralisation liée à la Complexité de Rademacher de la classe de métriques considérée par l'algorithme. Nous montrons que cette borne dépend fortement de la qualité de la métrique source et que si celle-ci est performante pour le problème considéré alors il est possible d'améliorer le taux de convergence de la borne. Celui-ci passe alors de $\mathcal{O}( \frac{1}{\sqrt{n}} )$ à $\mathcal{O}( \frac{1}{n} )$. Finalement, nous montrons que notre analyse théorique peut s'appliquer à de nombreuses fonctions de pertes et termes de régularisation, justifiant de l'intérêt de l'approche.

    • 11h45 – 12h15    Anil Goyal, Emilie Morvant, Pascal Germain et Massih-Reza Amini Théorèmes PAC-Bayésiens pour l’apprentissage multi-vue (pdf).

      Résumé: Dans ce papier, nous étudions la problématique de l'apprentissage multi-vues dont l'objectif est de tirer avantage de différentes représentations des données. Dans ce contexte, de nombreuses méthodes d'apprentissage automatique existent. Cependant peu d'études théoriques ont été menées lorsque le nombre de vues est strictement supérieur àdeux. Par le présent travail, nous désirons remédier à ce manque d'études théoriques générales en proposant une analyse PAC-Bayésienne de l'apprentissage multivues. Nous concentrons notre étude aux cas où le modèle de classification binaire appris prend la forme d'un vote de majorité. Nous énonçons, puis démontrons, deux théorèmes généraux permettant de considérer différentes relations entre les risques réels et empiriques. En outre, nous les spécialisons à trois relations fréquemment utilisées dans les approches PAC-Bayésiennes classiques.

    • 12h15 – 12h30    Ievgen Redko et Younès Bennani Décomposition en facteurs non négatifs pour l’adaptation de domaine non supervisée (pdf).

      Résumé: L'apprentissage par transfert est le processus par lequel un individu utilise un apprentissage acquis dans une situation pour l'appliquer à une autre situation. Dans ce papier, nous présentons une nouvelle méthode pour l'adaptation de domaine non supervisée qui vise à aligner deux domaines (distributions de probabilités) en utilisant un ensemble commun de vecteurs de base dérivés de vecteurs propres de chaque domaine. Nous utilisons des techniques de factorisation matricielle non-négative pour générer un plongement non-négatif qui minimise la distance entre les projections des données source et cible. Nous présentons une justification théorique de notre approche en montrant la cohérence de la fonction de similarité définie en utilisant la projection obtenue. Nous validons notre approche sur des ensembles de données de référence et montrons qu'elle surpasse plusieurs méthodes d'adaptation de domaine.

  • Session 7 : Parcimonie et approximation de rang faible

    • 14h00 – 14h30    Guillaume Rabusseau, Borja Balle et Shay B. Cohen Low-Rank Approximation of Weighted Tree Automata (pdf).

      Résumé: We describe a technique to minimize weighted tree automata (WTA), a powerful formalism that subsumes probabilistic context-free grammars (PCFGs) and latent-variable PCFGs. Our method relies on a singular value decomposition of the underlying Hankel matrix defined by the WTA. Our main theoretical result is an efficient algorithm for computing the SVD of an infinite Hankel matrix implicitly represented as a WTA. We evaluate our method on real-world data originating in newswire treebank. We show that our approach achieves lower perplexity than previous methods for PCFG minimization, and also is much more stable due to the absence of local optima.

    • 14h30 – 15h00    Romain Warlop, Jérémie Mary et Alessandro Lazaric Parallel Higher Order Alternating Least Square for Tensor Recommender System (pdf).

      Résumé: Many modern recommender systems rely on matrix factorization techniques to produce personalized recommendations on the basis of the feedback that users provided on different items in the past. The feedback may take different forms, such as the rating of a movie, or the number of times a user listened to the songs of a given music band. In some situations, the user can perform several actions on each item, and in this case the feedback is multidimensional. For instance, the user of an e-commerce website can either click on a product, add the product to their cart or buy it. Another example is restaurant rating, where the user may rate not only the quality of the food but also service and decoration. When dealing with multiple actions, one cannot view the recommendation problem as a matrix complexion unless the problem is considered as a series of multiple independent problems. In this work we propose to use a tensor approach to learn all this feedback simultaneously and benefit from transferring knowledge between each kind of feedback. Our work can be seen as a transfer learning application to recommender system as well as a multi-task recommender system learning where each task represents each action a user can perform. The proposed approach perform effective parallel tensor factorization in order to complete the tensor and make recommendation that we validate experimentally.

    • 15h00 – 15h15    François-Xavier Dupé Analyse de la consistance des atomes sélectionnés pour des généralisations d’Orthogonal Matching Pursuit (pdf).

      Résumé: Nous proposons plusieurs généralisations de l’algorithme Orthogonal Matching Pursuit (OMP) qui permet de trouver des solutions parcimonieuses lors de l’optimisation de fonctions différentiable. Une analyse de la consistance des atomes sélection est présentée basé sur une nouvelle condition elle-même basée sur une propriété de déviation diagonale restreinte. Pour les dimensions finies ou infinie, nous présentons des versions plus réalistes de l’algorithme que nous étendons aussi au cas où le gradient est mal connu. Enfin, nous proposons une méthode simple pour insérer des contraintes supplémentaires sans être trop invasif.

    • 15h15 – 15h30    Ronan Hamon, Valentin Emiya et Cédric Févotte Factorisation archétypale en matrices non-négatives avec données manquantes (pdf).

      Résumé: L'analyse archétypale (AA), ou factorisation convexe en matrices non-négatives (CNMF), est une variante de la factorisation en matrices non-négatives (NMF), dans laquelle les composantes obtenues sont exprimées comme une combinaison convexe d'exemples appelés archétypes. Dans cette contribution, nous proposons d'étendre AA/CNMF au cas où la matrice des données et la matrice des archétypes sont partiellement observées. Après avoir reformulé le problème dans ce contexte de données manquantes, nous proposons un algorithme de type Majorisation-Minimisation pour l'estimation des facteurs de la décomposition puis la reconstruction des données manquantes. Une comparaison est réalisée sur des données synthétiques, mettant en évidence une amélioration des performances de reconstruction de données manquantes par rapport à la NMF classique. L'écart de performance se révèle particulièrement intéressant lorsque le bruit est important ou que le nombre de données manquantes est grand.

    • 15h30 – 15h45    Charlotte Laclau et Mohamed Nadif Modèle de mélange parcimonieux pour la classification croisée et la sélection de variables .

      Résumé: La classification croisée ou co-clustering est une approche efficace en apprentissage non supervisé en raison de sa capacité à partitionner simultanément l'ensemble des objets et des variables qui les décrivent. Cependant, dans un contexte de grande dimension, les méthodes de co-clustering peuvent rencontrer des difficultés dues à la présence de variables de bruit/non pertinentes. Pour éviter de dégrader la performance de ce type de méthodes, nous proposons un modèle de mélange tenant compte simultanément des deux objectifs : co-clustering et sélection de variables. Nous nous limiterons au cas des données binaires sachant que cette approche peut être étendue à d'autres types de données. Les résultats expérimentaux sur des données simulées et des données réelles montrent l'intérêt de notre approche.

    • 15h45 – 16h00    Guillaume Rabusseau Higher-Order Low-Rank Regression (pdf).

      Résumé: This paper proposes an efficient algorithm (HOLRR) to handle regression tasks where the outputs have a tensor structure. We formulate the regression problem as the minimization of a least square criterion under a multilinear rank constraint, a difficult non convex problem. HOLRR computes efficiently an approximate solution of this problem, with solid theoretical guarantees. A kernel extension is also presented. Experiments on synthetic and real data show that HOLRR outperforms multivariate and multilinear regression methods and is considerably faster than existing tensor methods.

  • Session "Posters"

    Voici les numéros des grilles sur lesquelles acrocher vos posters.

    Numéro de posterAuteur & Titre
    1 Igor Colin, Aurélien Bellet, Joseph Salmon and Stéphan Clémençon. Un Algorithme de Gossip pour l'Optimisation Décentralisée de Fonctions sur les Paires
    2 Elie Guàrdia Sebaoun, Vincent Guigue and Patrick Gallinari. Apprentissage de trajectoires temporelles pour la recommandation dans les communautés d’utilisateurs
    3 Jonathan Louedec, Laurent Rossi, Aurélien Garivier, Chevalier Max and Josiane Mothe.Algorithme de bandit et obsolescence : un modèle pour la recommandation
    4 Yann Jacob, Tony Bourdier and Sandra Mellot.Prédiction du comportement de navigation des internautes pour la levée de fonds en ligne
    5 Antoine Bonnefoy, Ismael Ouamlil, Jean-Baptiste Veyrieras and Pierre Mahé. Sélection de variables structurée par régularisation jointe dans un cadre multi-tâches
    6 Maxime Sangnier, Olivier Fercoq and Florence d'Alché-buc. Multi-task learning for quantile curves estimation
    7 Albert Thomas, Stéphan Clémençon and Alexandre Gramfort. Learning hyperparameters for unsupervised anomaly detection
    8 Maria-Irina Nicolae, Eric Gaussier, Amaury Habrard and Marc Sebban. Apprentissage de similarités pour la classification de séries temporelles multivariées
    9 Ievgen Redko and Younès Bennani.Décomposition en facteurs non négatifs pour l'adaptation de domaine non supervisée
    10 Michaël Perrot and Amaury Habrard. Transfert et Bornes Rapides pour l'Apprentissage de Métriques
    11 Guillaume Rabusseau, Borja Balle and Shay B. Cohen. Low-Rank Approximation of Weighted Tree Automata
    12 Guillaume Rabusseau. Higher-Order Low-Rank Regression
    13 Alain Rakotomamonjy, Sokol Koço and Liva Ralaivola. Sur l'utilisation du gradient inexact pour l'accélération des méthodes parcimonieuses
    14 Charlotte Laclau and Mohamed Nadif. Modèle de mélange parcimonieux pour la classification croisée et la sélection de variables
    15 Valentina Zantedeschi, Rémi Emonet and Marc Sebban. Apprentissage de Combinaisons Convexes de Métriques Locales avec Garanties de Généralisation
    16 Aurélia Léon and Ludovic Denoyer. Policy-gradient Methods for Decision Trees
    17 Anil Goyal, Emilie Morvant, Pascal Germain and Massih-Reza Amini. Théorèmes PAC-Bayésiens pour l'apprentissage multi-vues
    18 Ronan Hamon, Valentin Emiya and Cédric Févotte. Factorisation archétypale en matrices non-négatives avec données manquantes
    19 Damien Sileo and Vincent Guigue.Apprentissage relationnel pour la recommandation et la prédiction de données manquantes
    20 Frédéric Guillou, Romaric Gaudel and Philippe Preux. Compromis exploration-exploitation pour système de recommandation à grande échelle
    21 Gabriella Contardo and Ludovic Denoyer.Apprentissage de représentation pour l'acquisition adaptative de features sous contrainte de coût.
    22 Rodrigues Christophe, Henry Soldano, Gauvain Bourgne and Celine Rouveirol. Collaborative decision in multi agent learning of action models
    23 Emmanuel Daucé and Hongliang Zhong.Optimisation quadratique pour l'apprentissage en ligne d'un bandit contextuel
    24 Asma Dachraoui, Antoine Cornuejols and Alexis Bondu. A Novel Algorithm for Online Classification of Time Series when Delaying Decision is Costly
    25 Julien Perolat, Bilal Piot, Bruno Scherrer and Olivier Pietquin. On the Use of Non-Stationary Strategies for Solving Two-Player Zero-Sum Markov Games
    26 Florian Strub, Jérémie Mary and Romaric Gaudel. Filtrage Collaboratif Hybride avec des Auto-encodeurs
    27 François-Xavier Dupé. Analyse de la consistance des atomes sélectionnés pour des généralisations d’Orthogonal Matching Pursuit
    28 Romain Warlop, Jérémie Mary and Alessandro Lazaric. Parallel Higher Order Alternating Least Square for Tensor Recommender System
    29 Aurélien Garivier, Pierre Ménard and Gilles Stoltz. Explore First, Exploit Next: The True Shape of Regret in Bandit Problem
    30 Sylvain Takerkart, Guillaume Auzias, Lucile Brun and Olivier Coulon. An automatic brain morphometry framework based on structural pattern analysis of cortical folding