Search

The rapid progress in artificial intelligence (AI) and machine learning has opened unprecedented analytics possibilities in various team and individual sports, including baseball, basketball, and tennis. More recently, AI techniques have been applied to football, due to a huge increase in data collection by professional teams, increased computational power, and advances in machine learning, with the goal of better addressing new scientific challenges involved in the analysis of both individual players’ and coordinated teams’ behaviors. The research challenges associated with predictive and prescriptive football analytics require new developments and progress at the intersection of statistical learning, game theory, and computer vision. In this paper, we provide an overarching perspective highlighting how the combination of these fields, in particular, forms a unique microcosm for AI research, while offering mutual benefits for professional teams, spectators, and broadcasters in the years to come. We illustrate that this duality makes football analytics a game changer of tremendous value, in terms of not only changing the game of football itself, but also in terms of what this domain can mean for the field of AI. We review the state-of-the-art and exemplify the types of analysis enabled by combining the aforementioned fields, including illustrative examples of counterfactual analysis using predictive models, and the combination of game-theoretic analysis of penalty kicks with statistical learning of player attributes. We conclude by highlighting envisioned downstream impacts, including possibilities for extensions to other sports (real and virtual).

We study sampling algorithms for $\beta$-ensembles with time complexity less than cubic in the cardinality of the ensemble. Following Dumitriu & Edelman (2002), we see the ensemble as the eigenvalues of a random tridiagonal matrix, namely a random Jacobi matrix. First, we provide a unifying and elementary treatment of the tridiagonal models associated to the three classical Hermite, Laguerre and Jacobi ensembles. For this purpose, we use simple changes of variables between successive reparametrizations of the coefficients defining the tridiagonal matrix. Second, we derive an approximate sampler for the simulation of $\beta$-ensembles, and illustrate how fast it can be for polynomial potentials. This method combines a Gibbs sampler on Jacobi matrices and the diagonalization of these matrices. In practice, even for large ensembles, only a few Gibbs passes suffice for the marginal distribution of the eigenvalues to fit the expected theoretical distribution. When the conditionals in the Gibbs sampler can be simulated exactly, the same fast empirical convergence is observed for the fluctuations of the largest eigenvalue. Our experimental results support a conjecture by Krishnapur et al. (2016), that the Gibbs chain on Jacobi matrices of size $N$ mixes in $\mathcal{O}(\log(N))$., Comment: 37 pages, 8 figures, code at https://github.com/guilgautier/DPPy

International audience; Face recognition from a single image per person is a challenging problem because the training sample is extremely small. We consider a variation of this problem. In our problem, we recognize only one person, and there are no labeled data for any other person. This setting naturally arises in authentication on personal computers and mobile devices, and poses additional challenges because it lacks negative examples. We formalize our problem as one-class classification, and propose and analyze an algorithm that learns a non-parametric model of the face from a single labeled image and a stream of unlabeled data. In many domains, for instance when a person interacts with a computer with a camera, unlabeled data are abundant and easy to utilize. This is the first paper that investigates how these data can help in learning better models in the single-image-per-person setting. Our method is evaluated on a dataset of 43 people and we show that these people can be recognized 90% of time at nearly zero false positives. This recall is 25+% higher than the recall of our best performing baseline. Finally, we conduct a comprehensive sensitivity analysis of our algorithm and provide a guideline for setting its parameters in practice.

International audience; In this paper, we consider the problem of conditional anomaly detection that aims to identify data instances with an unusual response or a class label. We develop a new non-parametric approach for conditional anomaly detection based on the soft harmonic solution, with which we estimate the confidence of the label to detect anomalous mislabeling. We further regularize the solution to avoid the detection of isolated examples and examples on the boundary of the distribution support. We demonstrate the efficacy of the proposed method on several synthetic and UCI ML datasets in detecting unusual labels when compared to several baseline approaches. We also evaluate the performance of our method on a real-world electronic health record dataset where we seek to identify unusual patient-management decisions.

The purpose of this study was to provide a univariate and multivariate analysis of genomic microbial data and salivary mass-spectrometry proteomic profiles for dental caries outcomes. In order to determine potential useful biomarkers for dental caries, a multivariate classification analysis was employed to build predictive models capable of classifying microbial and salivary sample profiles with generalization performance. We used high-throughput methodologies including multiplexed microbial arrays and SELDI-TOF-MS profiling to characterize the oral flora and salivary proteome in 204 children aged 1–8 years (n=118caries-free,n=86caries-active). The population received little dental care and was deemed at high risk for childhood caries. Findings of the study indicate that models incorporating both microbial and proteomic data are superior to models of only microbial or salivary data alone. Comparison of results for the combined and independent data suggests that the combination of proteomic and microbial sources is beneficial for the classification accuracy and that combined data lead to improved predictive models for caries-active and caries-free patients. The best predictive model had a 6% test error, >92% sensitivity, and >95% specificity. These findings suggest that further characterization of the oral microflora and the salivary proteome associated with health and caries may provide clinically useful biomarkers to better predict future caries experience.

The objective of this paper is to understand what characteristics and features of clinical data influence physician’s decision about ordering laboratory tests or prescribing medications the most. We conduct our analysis on data and decisions extracted from electronic health records of 4486 post-surgical cardiac patients. The summary statistics for 335 different lab order decisions and 407 medication decisions are reported. We show that in many cases, physician’s lab-order and medication decisions are predicted well by simple patterns such as last value of a single test result, time since a certain lab test was ordered or time since certain procedure was executed.

L'apprentissage par renforcement (reinforcement learning, RL) est un paradigme de l'apprentissage automatique qui nous permet de concevoir des algorithmes qui apprennent à prendre des décisions et à interagir avec le monde. Les algorithmes de RL peuvent être classés comme hors ligne ou en ligne. Dans le cas hors ligne, l'algorithme dispose d'un ensemble de données fixe, avec lequel il doit calculer une bonne stratégie de prise de décision. Dans le cas en ligne, l'agent doit collecter efficacement des données par lui-même, en interagissant avec l'environnement : c'est le problème que l'on appelle exploration en apprentissage par renforcement. Cette thèse présente des contributions théoriques et pratiques sur le RL en ligne. Nous étudions la performance dans le pire des cas des algorithmes de RL dans des environnements finis, c'est-à-dire, ceux qui peuvent être modélisés avec un nombre fini d'états, et où l'ensemble des actions qui peuvent être prises par un agent est aussi fini. Cette performance se dégrade à mesure que le nombre d'états augmente, alors qu'en pratique, l'espace d'états peut être arbitrairement grand ou continu. Pour résoudre ce problème, nous proposons des algorithmes à noyaux qui peuvent être implémentés pour des espaces d'états généraux, et pour lesquels nous proposons des résultats théoriques sous des hypothèses faibles sur l'environnement. Ces algorithmes reposent sur une fonction noyau qui mesure la similarité entre différents états, qui peut être définie sur des espaces d'état arbitraires, y compris des ensembles discrets et des espaces euclidiens, par exemple. De plus, nous montrons que nos algorithmes à noyaux sont capables d'apprendre dans des environnements non stationnaires en utilisant des fonctions noyau dépendantes du temps, et nous proposons et analysons des versions approximatives de nos méthodes pour réduire leur complexité de calcul. Finalement, nous introduisons une autre approximation de nos méthodes à noyaux, qui peut être implémentée avec des algorithmes d'apprentissage par renforcement profond et intégrer de différentes méthodes d'apprentissage de représentation pour définir un noyau. Reinforcement learning (RL) is a powerful machine learning framework to design algorithms that learn to make decisions and to interact with the world. Algorithms for RL can be classified as offline or online. In the offline case, the algorithm is given a fixed dataset, based on which it needs to compute a good decision-making strategy. In the online case, an agent needs to efficiently collect data by itself, by interacting with the environment: that is the problem of exploration in reinforcement learning. This thesis presents theoretical and practical contributions to online RL. We investigate the worst-case performance of online RL algorithms in finite environments, that is, those that can be modeled with a finite amount of states, and where the set of actions that can be taken by an agent is also finite. Such performance degrades as the number of states increases, whereas in real-world applications the state set can be arbitrarily large or continuous. To tackle this issue, we propose kernel-based algorithms for exploration that can be implemented for general state spaces, and for which we provide theoretical results under weak assumptions on the environment. Those algorithms rely on a kernel function that measures the similarity between different states, which can be defined on arbitrary state-spaces, including discrete sets and Euclidean spaces, for instance. Additionally, we show that our kernel-based algorithms are able to handle non-stationary environments by using time-dependent kernel functions, and we propose and analyze approximate versions of our methods to reduce their computational complexity. Finally, we introduce a scalable approximation of our kernel-based methods, that can be implemented with deep reinforcement learning and integrate different representation learning methods to define a kernel function.

Reinforcement learning (RL) is a powerful machine learning framework to design algorithms that learn to make decisions and to interact with the world. Algorithms for RL can be classified as offline or online. In the offline case, the algorithm is given a fixed dataset, based on which it needs to compute a good decision-making strategy. In the online case, an agent needs to efficiently collect data by itself, by interacting with the environment: that is the problem of exploration in reinforcement learning. This thesis presents theoretical and practical contributions to online RL. We investigate the worst-case performance of online RL algorithms in finite environments, that is, those that can be modeled with a finite amount of states, and where the set of actions that can be taken by an agent is also finite. Such performance degrades as the number of states increases, whereas in real-world applications the state set can be arbitrarily large or continuous. To tackle this issue, we propose kernel-based algorithms for exploration that can be implemented for general state spaces, and for which we provide theoretical results under weak assumptions on the environment. Those algorithms rely on a kernel function that measures the similarity between different states, which can be defined on arbitrary state-spaces, including discrete sets and Euclidean spaces, for instance. Additionally, we show that our kernel-based algorithms are able to handle non-stationary environments by using time-dependent kernel functions, and we propose and analyze approximate versions of our methods to reduce their computational complexity. Finally, we introduce a scalable approximation of our kernel-based methods, that can be implemented with deep reinforcement learning and integrate different representation learning methods to define a kernel function.; L'apprentissage par renforcement (reinforcement learning, RL) est un paradigme de l'apprentissage automatique qui nous permet de concevoir des algorithmes qui apprennent à prendre des décisions et à interagir avec le monde. Les algorithmes de RL peuvent être classés comme hors ligne ou en ligne. Dans le cas hors ligne, l'algorithme dispose d'un ensemble de données fixe, avec lequel il doit calculer une bonne stratégie de prise de décision. Dans le cas en ligne, l'agent doit collecter efficacement des données par lui-même, en interagissant avec l'environnement : c'est le problème que l'on appelle exploration en apprentissage par renforcement. Cette thèse présente des contributions théoriques et pratiques sur le RL en ligne. Nous étudions la performance dans le pire des cas des algorithmes de RL dans des environnements finis, c'est-à-dire, ceux qui peuvent être modélisés avec un nombre fini d'états, et où l'ensemble des actions qui peuvent être prises par un agent est aussi fini. Cette performance se dégrade à mesure que le nombre d'états augmente, alors qu'en pratique, l'espace d'états peut être arbitrairement grand ou continu. Pour résoudre ce problème, nous proposons des algorithmes à noyaux qui peuvent être implémentés pour des espaces d'états généraux, et pour lesquels nous proposons des résultats théoriques sous des hypothèses faibles sur l'environnement. Ces algorithmes reposent sur une fonction noyau qui mesure la similarité entre différents états, qui peut être définie sur des espaces d'état arbitraires, y compris des ensembles discrets et des espaces euclidiens, par exemple. De plus, nous montrons que nos algorithmes à noyaux sont capables d'apprendre dans des environnements non stationnaires en utilisant des fonctions noyau dépendantes du temps, et nous proposons et analysons des versions approximatives de nos méthodes pour réduire leur complexité de calcul. Finalement, nous introduisons une autre approximation de nos méthodes à noyaux, qui peut être implémentée avec des algorithmes d'apprentissage par renforcement profond et intégrer de différentes méthodes d'apprentissage de représentation pour définir un noyau.

Reinforcement learning (RL) is a powerful machine learning framework to design algorithms that learn to make decisions and to interact with the world. Algorithms for RL can be classified as offline or online. In the offline case, the algorithm is given a fixed dataset, based on which it needs to compute a good decision-making strategy. In the online case, an agent needs to efficiently collect data by itself, by interacting with the environment: that is the problem of exploration in reinforcement learning. This thesis presents theoretical and practical contributions to online RL. We investigate the worst-case performance of online RL algorithms in finite environments, that is, those that can be modeled with a finite amount of states, and where the set of actions that can be taken by an agent is also finite. Such performance degrades as the number of states increases, whereas in real-world applications the state set can be arbitrarily large or continuous. To tackle this issue, we propose kernel-based algorithms for exploration that can be implemented for general state spaces, and for which we provide theoretical results under weak assumptions on the environment. Those algorithms rely on a kernel function that measures the similarity between different states, which can be defined on arbitrary state-spaces, including discrete sets and Euclidean spaces, for instance. Additionally, we show that our kernel-based algorithms are able to handle non-stationary environments by using time-dependent kernel functions, and we propose and analyze approximate versions of our methods to reduce their computational complexity. Finally, we introduce a scalable approximation of our kernel-based methods, that can be implemented with deep reinforcement learning and integrate different representation learning methods to define a kernel function., L’apprentissage par renforcement (reinforcement learning, RL) est un paradigme de l’apprentissage automatique qui nous permet de concevoir des algorithmes qui apprennent à prendre des décisions et à interagir avec le monde. Les algorithmes de RL peuvent être classés comme hors ligne ou en ligne. Dans le cas hors ligne, l’algorithme dispose d’un ensemble de données fixe, avec lequel il doit calculer une bonne stratégie de prise de décision. Dans le cas en ligne, l’agent doit collecter efficacement des données par lui-même, en interagissant avec l’environnement : c’est le problème que l’on appelle exploration en apprentissage par renforcement. Cette thèse présente des contributions théoriques et pratiques sur le RL en ligne. Nous étudions la performance dans le pire des cas des algorithmes de RL dans des environnements finis, c’est-à-dire, ceux qui peuvent être modélisés avec un nombre fini d’états, et où l’ensemble des actions qui peuvent être prises par un agent est aussi fini. Cette performance se dégrade à mesure que le nombre d’états augmente, alors qu’en pratique, l’espace d’états peut être arbitrairement grand ou continu. Pour résoudre ce problème, nous proposons des algorithmes à noyaux qui peuvent être implémentés pour des espaces d’états généraux, et pour lesquels nous proposons des résultats théoriques sous des hypothèses faibles sur l’environnement. Ces algorithmes reposent sur une fonction noyau qui mesure la similarité entre différents états, qui peut être définie sur des espaces d’état arbitraires, y compris des ensembles discrets et des espaces euclidiens, par exemple. De plus, nous montrons que nos algorithmes à noyaux sont capables d’apprendre dans des environnements non stationnaires en utilisant des fonctions noyau dépendantes du temps, et nous proposons et analysons des versions approximatives de nos méthodes pour réduire leur complexité de calcul. Finalement, nous introduisons une autre approximation de nos méthodes à noyaux, qui peut être implémentée avec des algorithmes d’apprentissage par renforcement profond et intégrer de différentes méthodes d’apprentissage de représentation pour définir un noyau.

In this thesis, we study the problem of sequential optimization under stochastic environments. At each round, we can query a data point from the environment, and receive a noisy reward. We first focus on the case where the environment is abstracted as a finite search space, then we investigate also on a more general setting where the environment is composed of an infinite number of points or even continuous. In both cases, the cost of a single query would be high, and we thus aim at identify the (near)-optimum as efficiently as possible. The whole study is motivated by numerous real scenarios including, but not limited to, clinical trial, A/B testing, advertisement placement optimization. We therefore conclude by some particular focus on one of its most important contributions for the machine learning community, i.e. hyper-parameter optimization.; Dans cette thèse, nous étudions le problème d’optimisation séquentielle dans des environnements stochastiques. A chaque instant, nous pouvons interroger un point de l’environnement, et recevoir une récompense bruitée. Nous nous concentrons d’abord sur le cas où l’environnement est représenté par un nombre fini de points, et ensuite sur le cas plus général où l’environnement est composé d’un nombre infini dénombrable de points, voire continu. Dans les deux cas, le coût d’une requête pouvant être élevée, nous envisageons ainsi à repérer au plus vite le point (quasi)-optimal. Cette étude est motivée par de nombreux scénarios réels comme, entre autres, les essais cliniques, les tests A/B, ou l’optimisation des placements publicitaires. Ainsi pour terminer, nous nous intéressons en particulier à l’une de ces applications plus importantes pour la communauté d’apprentissage statistique, c’est-à-dire l’optimisation des hyper-paramètres.

Dans cette thèse, nous étudions le problème d’optimisation séquentielle dans des environnements stochastiques. A chaque instant, nous pouvons interroger un point de l’environnement, et recevoir une récompense bruitée. Nous nous concentrons d’abord sur le cas où l’environnement est représenté par un nombre fini de points, et ensuite sur le cas plus général où l’environnement est composé d’un nombre infini dénombrable de points, voire continu. Dans les deux cas, le coût d’une requête pouvant être élevée, nous envisageons ainsi à repérer au plus vite le point (quasi)-optimal. Cette étude est motivée par de nombreux scénarios réels comme, entre autres, les essais cliniques, les tests A/B, ou l’optimisation des placements publicitaires. Ainsi pour terminer, nous nous intéressons en particulier à l’une de ces applications plus importantes pour la communauté d’apprentissage statistique, c’est-à-dire l’optimisation des hyper-paramètres. In this thesis, we study the problem of sequential optimization under stochastic environments. At each round, we can query a data point from the environment, and receive a noisy reward. We first focus on the case where the environment is abstracted as a finite search space, then we investigate also on a more general setting where the environment is composed of an infinite number of points or even continuous. In both cases, the cost of a single query would be high, and we thus aim at identify the (near)-optimum as efficiently as possible. The whole study is motivated by numerous real scenarios including, but not limited to, clinical trial, A/B testing, advertisement placement optimization. We therefore conclude by some particular focus on one of its most important contributions for the machine learning community, i.e. hyper-parameter optimization.

Imagine that we have access to a simulator that models the behaviour of some complex numerical task. Being considered as a black box, we can only get useful information by running the simulator with different inputs. For example, the process of inferring the 3D structure of a protein from its amino-acid sequence can be regarded as such a complex task, that can be modelled by a simulator. The inputs of the simulator are the amino-acid sequences and the outputs are the predicted 3D structures. A popular family of methods seek to optimize a suitable energy function – produced by the simulator – that describes the relation between the structure of a protein and its amino-acid sequence. These meth- ods are of interest because they are able to build protein structures without prior knowl- edge on solved structures.In this thesis, we model the previous scenarios as a sequential optimization problem under stochastic environments. At each round, we can query a data point from the environment, and receive a noisy reward. We first focus on the case where the environment is abstracted as a finite search space, then we investigate also on a more general setting where the environment is composed of an infinite number of points or even continuous. In both cases, the cost of a single query would be high, and we thus aim at identify the (near)-optimum as efficiently as possible. The whole study is motivated by numerous real scenarios including, but not limited to, clinical trial, A/B testing, advertisement placement optimization. We therefore conclude by some particular focus on one of its most important contributions for the machine learning community, i.e. hyper-parameter optimization., Imaginons que nous ayons accès à un simulateur qui modélise le comportement d’une tâche numérique complexe. Considéré comme une boîte noire, nous ne pouvons obtenir des informations utiles qu’en exécutant le simulateur avec différentes entrées. Par exemple, le processus d’inférence de la structure 3D d’une protéine à partir de sa séquence d’acides aminés peut être considéré comme une tâche complexe, qui peut être modélisée par un simulateur. Les entrées du simulateur sont les séquences d’acides aminés et les sorties sont les structures 3D prédites. Une famille populaire de méthodes cherche à optimiser une fonction énergétique appropriée - produite par le simulateur - qui décrit la relation entre la structure d’une protéine et sa séquence d’acides aminés. Ces méthodes sont intéressantes car elles sont capables de construire des structures de protéines sans connaissance préalable des structures résolues.Dans cette thèse, nous modélisons des scénarios précédents comme un problème d’optimisation séquentielle dans des environnements stochastiques. A chaque instant, nous pouvons interroger un point de l’environnement, et recevoir une récompense bruitée. Nous nous concentrons d’abord sur le cas où l’environnement est représenté par un nombre fini de points, et ensuite sur le cas plus général où l’environnement est composé d’un nombre infini dénombrable de points, voire continu. Dans les deux cas, le coût d’une requête pouvant être élevée, nous envisageons ainsi à repérer au plus vite le point (quasi)-optimal. Cette étude est motivée par de nombreux scénarios réels comme, entre autres, les essais cliniques, les tests A/B, ou l’optimisation des placements publicitaires. Ainsi pour terminer, nous nous intéressons en particulier à l’une de ces applications plus importantes pour la communauté d’apprentissage statistique, c’est-à-dire l’optimisation des hyper-paramètres.

Designing an adaptive sequence of exercises in Intelligent Tutoring Systems (ITS) requiresto characterize the gaps of the student and to use this characterization in a relevantpedagogical strategy. Since a student does no more than a few tens of exercises in a session,these two objectives compete. Machine learning called these exploration-exploitationtrade-offs in sequential decision making the bandits problems. In this thesis, we studydifferent bandits setups for intelligent tutoring systems.The rested rotting bandits are a sequential decision problem in which the reward associatedwith an action may decrease when it is selected. It models the situation where the studentimproves when he works and the ITS aims the least known subject to fill the most importantgaps. We design new algorithms and we prove that for an unknown horizon T, and withoutany knowledge on the decreasing behavior of the K arms, these algorithms achieve problemdependentregret bound of O(logT); and a problem-independent one of Oe(pKT). Ourresult substantially improves over existing algorithms, which suffers minimax regretOe(K1=3T2=3). These bounds are at a polylog factor of the optimal bounds on the classicalstationary bandit; hence our conclusion: rotting bandits are not harder than stationary ones.In the restless rotting bandits, the reward may decrease at each round for all the actions.They model different situations such as the obsolescence of content in recommendersystems. We show that the rotting algorithms designed for the rested case match theproblem-independent lower bounds and a O(logT) problem-dependent one. The latter wasshown to be unachievable in the general case where rewards can increase. We conclude:the rotting assumption makes the restless bandits easier.Targeting the least known topic may be interesting before an exam but during the curriculum- when all the subjects are not yet understood - it can lead to failure in the learning of thestudent. We study a Partially Observable Markov Decision Process in which we aim atmastering as many topics as fast as possible. We show that under relevant assumptions onthe learning of the student, the best oracle policy targets the most known topic under themastery threshold. Since this optimal oracle does not need to know the transition dynamicsof the POMDP, we design a learning policy with classical bandits tools, hence avoidingthe data-intensive methods of POMDP learning., Proposer des séquences adaptatives d’exercices dans un Environnement informatique pourl’Apprentissage Humain (EIAH) nécessite de caractériser les lacunes de l’élève et d’utilisercette caractérisation dans une stratégie pédagogique adaptée. Puisque les élèves ne fontque quelques dizaines de questions dans une session de révision, ces deux objectifs sonten compétition. L’apprentissage automatique appelle problème de bandits ces dilemmesd’exploration-exploitation dans les prises de décisions séquentielles. Dans cette thèse,nous étudions trois problèmes de bandits pour une application dans les systèmes éducatifsadaptatifs.Les bandits décroissants au repos sont un problème de décision séquentiel dans lequel larécompense associée à une action décroît lorsque celle-ci est sélectionnée. Cela modélisele cas où un élève progresse quand il travaille et l’EIAH cherche à sélectionner le sujetle moins maîtrisé pour combler les plus fortes lacunes. Nous présentons de nouveauxalgorithmes et nous montrons que pour un horizon inconnu T et sans aucune connaissancesur la décroissance des K bras, ces algorithmes atteignent une borne de regret dépendantedu problème O(logT); et une borne indépendante du problème Oe(pKT). Nos résultatsaméliorent substantiellement l’état de l’art, ou seule une borne minimax Oe(K1=3T2=3) avaitété atteinte. Ces nouvelles bornes sont à des facteurs polylog des bornes optimales sur leproblème stationnaire, donc nous concluons : les bandits décroissants ne sont pas plus dursque les bandits stationnaires.Dans les bandits décroissants sans repos, la récompense peut décroître à chaque tour pourtoutes les actions. Cela modélise des situations différentes telles que le vieillissementdu contenu dans un système de recommandation. On montre que les algorithmes conçuspour le problème "au repos" atteignent les bornes inférieures agnostiques au problèmeet une borne dépendante du problème O(logT). Cette dernière est inatteignable dans lecas général où la récompense peut croître. Nous concluons : l’hypothèse de décroissancesimplifie l’apprentissage des bandits sans repos.Viser le sujet le moins connu peut être intéressant avant un examen, mais pendant lecursus - quand tous les sujets ne sont pas bien compris - cela peut mener à l’échec del’apprentissage de l’étudiant. On étudie un Processus de Décision Markovien PartiellementObservable (POMDP, selon l’acronyme anglais) dans lequel on cherche à maîtriser le plusde sujets le plus rapidement possible. On montre que sous des hypothèses raisonnablessur l’apprentissage de l’élève, la meilleure stratégie oracle sélectionne le sujet le plusconnu sous le seuil de maîtrise. Puisque cet oracle optimal n’a pas besoin de connaîtrela dynamique de transition du POMDP, nous proposons une stratégie apprenante avecdes outils "bandits" classiques, en évitant ainsi les méthodes gourmandes en données del’apprentissage de POMDP.

Combinatorial stochastic semi-bandits appear naturally in many contexts where the exploration/exploitation dilemma arises, such as web content optimization (recommendation/online advertising) or shortest path routing methods. This problem is formulated as follows: an agent sequentially optimizes an unknown and noisy objective function, defined on a power set $\mathcal{P}([n])$. For each set $A$ tried out, the agent suffers a loss equal to the expected deviation from the optimal solution while obtaining observations to reduce its uncertainty on the coordinates from $A$. Our objective is to study the efficiency of policies for this problem, focusing in particular on the following two aspects: statistical efficiency, where the criterion considered is the regret suffered by the policy (the cumulative loss) that measures learning performance; and computational efficiency. It is sometimes difficult to combine these two aspects in a single policy. In this thesis, we propose different directions for improving statistical efficiency, while trying to maintain the computational efficiency of policies.In particular, we have improved optimistic methods by developing approximation algorithms and refining the confidence regions used. We also explored an alternative to the optimistic methods, namely randomized methods, and found them to be a serious candidate for combining the two types of efficiency.; Les problèmes de semi-banditsstochastiques combinatoires se présentent naturellement dans de nombreux contextes où le dilemme exploration/exploitation se pose, tels que l’optimisation de contenu web (recommandation/publicité en ligne) ou encore les méthodes de routage à trajet minimal. Ce problème est formulé de la manière suivante : un agent optimise séquentiellement une fonction objectif inconnue et bruitée, définie sur un ensemble puissance $\mathcal{P}([n])$. Pour chaque ensemble $A$ testé,l'agent subit une perte égale à l'écart espéré par rapport à la solution optimale tout en obtenant des observations lui permettant de réduire son incertitude sur les coordonnées de $A$. Notre objectif est d'étudier l'efficience des politiques pour ce problème, en nous intéressant notamment aux deux aspects suivants : l'efficience statistique, où le critère considéré est le regret subi par la politique (la perte cumulée) qui mesure la performance d'apprentissage ; et l'efficience computationnelle (i.e., de calcul). Il est parfois difficile de réunir ces deux aspects dans une seule politique. Dans cette thèse, nous proposons différentes directions pour améliorer l'efficience statistique, tout en essayant de maintenir l'efficience computationnelle des politiques. Nous avons notamment amélioré les méthodes optimistes en développant des algorithmes d'approximation et en affinant les régions de confiance utilisées. Nous avons également exploré une alternative aux méthodes optimistes, à savoir les méthodes randomisées, et avons constaté qu'elles constituent un candidat sérieux pour pouvoir réunir les deux types d'efficience.

Determinantal point processes (DPPs) generate random configuration of points where the points tend to repel each other. The notion of repulsion is encoded by the sub-determinants of a kernel matrix, in the sense of kernel methods in machine learning. This special algebraic form makes DPPs attractive both in statistical and computational terms. This thesis focuses on sampling from such processes, that is on developing simulation methods for DPPs. Applications include numerical integration, recommender systems or the summarization of a large corpus of data. In the finite setting, we establish the correspondence between sampling from a specific type of DPPs, called projection DPPs, and solving a randomized linear program. In this light, we devise an efficient Markov-chain-based sampling method. In the continuous case, some classical DPPs can be sampled by computing the eigenvalues of carefully randomized tridiagonal matrices. We provide an elementary and unifying treatment of such models, from which we derive an approximate sampling method for more general models. In higher dimension, we consider a special class of DPPs used for numerical integration. We implement a tailored version of a known exact sampler, which allows us to compare the properties of Monte Carlo estimators in new regimes. In the context of reproducible research, we develop an open-source Python toolbox, named DPPy, which implements the state of the art sampling methods for DPPs; Un processus ponctuel déterminantal (DPP) génère des configurations aléatoires de points ayant tendance à se repousser. La notion de répulsion est encodée par les sous-déterminants d’une matrice à noyau, au sens des méthodes à noyau en apprentissage artificiel. Cette forme algébrique particulière confère aux DPP de nombreux avantages statistiques et computationnels. Cette thèse porte sur l'échantillonnage des DPP, c'est à dire sur la conception d'algorithmes de simulation pour ce type de processus. Les motivations pratiques sont l'intégration numérique, les systèmes de recommandation ou encore la génération de résumés de grands corpus de données. Dans le cadre fini, nous établissons la correspondance entre la simulation de DPP spécifiques, dits de projection, et la résolution d'un problème d'optimisation linéaire dont les contraintes sont randomisées. Nous en tirons une méthode efficace d'échantillonnage par chaîne de Markov. Dans le cadre continu, certains DPP classiques peuvent être simulés par le calcul des valeurs propres de matrices tridiagonales aléatoires bien choisies. Nous en fournissons une nouvelle preuve élémentaire et unificatrice, dont nous tirons également un échantillonneur approché pour des modèles plus généraux. En dimension supérieure, nous nous concentrons sur une classe de DPP utilisée en intégration numérique. Nous proposons une implémentation efficace d'un schéma d'échantillonnage exact connu, qui nous permet de comparer les propriétés d'estimateurs Monte Carlo dans de nouveaux régimes. En vue d'une recherche reproductible, nous développons une boîte à outils open-source, nommée DPPy, regroupant les différents outils d'échantillonnage sur les DPP.

The main advantage of non-parametric models is that the accuracy of the model (degreesof freedom) adapts to the number of samples. The main drawback is the so-called "curseof kernelization": to learn the model we must first compute a similarity matrix among allsamples, which requires quadratic space and time and is unfeasible for large datasets.Nonetheless the underlying effective dimension (effective d.o.f.) of the dataset is often muchsmaller than its size, and we can replace the dataset with a subset (dictionary) of highlyinformative samples. Unfortunately, fast data-oblivious selection methods (e.g., uniformsampling) almost always discard useful information, while data-adaptive methods thatprovably construct an accurate dictionary, such as ridge leverage score (RLS) sampling,have a quadratic time/space cost.In this thesis we introduce a new single-pass streaming RLS sampling approach thatsequentially construct the dictionary, where each step compares a new sample only withthe current intermediate dictionary and not all past samples. We prove that the size ofall intermediate dictionaries scales only with the effective dimension of the dataset, andtherefore guarantee a per-step time and space complexity independent from the number ofsamples. This reduces the overall time required to construct provably accurate dictionariesfrom quadratic to near-linear, or even logarithmic when parallelized.Finally, for many non-parametric learning problems (e.g., K-PCA, graph SSL, online kernellearning) we we show that we can can use the generated dictionaries to compute approximatesolutions in near-linear that are both provably accurate and empirically competitive.; L’avantage principal des méthodes d’apprentissage non-paramétriques réside dans le faitque la nombre de degrés de libertés du modèle appris s’adapte automatiquement au nombred’échantillons. Ces méthodes sont cependant limitées par le "fléau de la kernelisation":apprendre le modèle requière dans un premier temps de construire une matrice de similitudeentre tous les échantillons. La complexité est alors quadratique en temps et espace, ce quis’avère rapidement trop coûteux pour les jeux de données de grande dimension.Cependant, la dimension "effective" d’un jeu de donnée est bien souvent beaucoup pluspetite que le nombre d’échantillons lui-même. Il est alors possible de substituer le jeude donnée réel par un jeu de données de taille réduite (appelé "dictionnaire") composéexclusivement d’échantillons informatifs. Malheureusement, les méthodes avec garantiesthéoriques utilisant des dictionnaires comme "Ridge Leverage Score" (RLS) ont aussi unecomplexité quadratique.Dans cette thèse nous présentons une nouvelle méthode d’échantillonage RLS qui met àjour le dictionnaire séquentiellement en ne comparant chaque nouvel échantillon qu’avecle dictionnaire actuel, et non avec l’ensemble des échantillons passés. Nous montrons quela taille de tous les dictionnaires ainsi construits est de l’ordre de la dimension effectivedu jeu de données final, guarantissant ainsi une complexité en temps et espace à chaqueétape indépendante du nombre total d’échantillons. Cette méthode présente l’avantage depouvoir être parallélisée.Enfin, nous montrons que de nombreux problèmes d’apprentissage non-paramétriquespeuvent être résolus de manière approchée grâce à notre méthode.

This thesis studies several extensions of multi-armed bandit problem, where a learner sequentially selects an action and obtains the reward of the action. Traditionally, the only information the learner acquires is about the obtained reward while information about other actions is hidden from the learner. This limited feedback can be restrictive in some applications like recommender systems, internet advertising, packet routing, etc. Usually, these problems come with structure, similarities between users or actions, additional observations, or any additional assumptions. Therefore, it is natural to incorporate these assumptions to the algorithms to improve their performance. This thesis focuses on multi-armed bandit problem with some underlying structure usually represented by a graph with actions as vertices. First, we study a problem where the graph captures similarities between actions; connected actions tend to grand similar rewards. Second, we study a problem where the learner observes rewards of all the neighbors of the selected action. We study these problems under several additional assumptions on rewards (stochastic, adversarial), side observations (adversarial, stochastic, noisy), actions (one node at the time, several nodes forming a combinatorial structure in the graph). The main contribution of this thesis is to design algorithms for previously mentioned problems together with theoretical and empirical guarantees. We also introduce several novel quantities, to capture the difficulty of some problems, like effective dimension and effective independence number.; Dans cette thèse nous étudions différentes généralisations du problème dit « du bandit manchot ». Le problème du bandit manchot est un problème de décision séquentiel au cours duquel un agent sélectionne successivement des actions et obtient une récompense pour chacune d’elles. On fait généralement l’hypothèse que seule la récompenseassociée à l’action choisie est observée par l’agent, ce dernier ne reçoit aucune information sur les actions non choisies. Cette hypothèse s’avère parfois très restrictive pour certaines applications telles que les systèmes de recommandations, la publicité en ligne, le routage de paquets, etc. Ces types de problèmes sont en effet souvent très structurés : les utilisateurs et/ou les actions disponibles peuvent par exemple présenter certaines similitudes, ou l’agent peut parfois recevoir davantage d’information de l’environnement, etc. Il paraît dès lors assez naturel de tenir compte de la connaissance de la structure du problème pour améliorer les performances des algorithmes d’apprentissage usuels. Dans cette thèse, nous nous focalisons sur les problèmes de bandits présentant une structure pouvant être modélisée par un graphe dont les noeuds représentent les actions. Dans un premier temps, nous étudierons le cas où les arêtes du graphe modélisent les similitudes entre actions : deux actions connectées auront tendance à fournir des récompenses similaires. Dans un second temps, nous analyserons le cas où l’agent observe les récompenses de toutes les actions adjacentes à l’action choisie dans le graphe. Pour les deux cas précédents, nous dissocierons plusieurs sous-cas : récompenses stochastiques ou adversariales, informations additionnelles stochastiques adversariales ou bruitée, une ou plusieurs actions sélectionnées simultanément. Notre contribution principale a été d’élaborer de nouveaux algorithmes permettant de traiter efficacement les problèmes évoqués précédemment, et de démontrer théoriquement et empiriquement le bon fonctionnement de ces algorithmes. Nos travaux nous ont également amenés à introduire de nouvelles grandeurs, telles que la dimension effective et le nombre d’indépendance effectif, afin de caractériser la difficulté des différents problèmes.

Determinantal point processes (DPPs) generate random configuration of points where the points tend to repel each other. The notion of repulsion is encoded by the sub-determinants of a kernel matrix, in the sense of kernel methods in machine learning. This special algebraic form makes DPPs attractive both in statistical and computational terms. This thesis focuses on sampling from such processes, that is on developing simulation methods for DPPs. Applications include numerical integration, recommender systems or the summarization of a large corpus of data. In the finite setting, we establish the correspondence between sampling from a specific type of DPPs, called projection DPPs, and solving a randomized linear program. In this light, we devise an efficient Markov-chain-based sampling method. In the continuous case, some classical DPPs can be sampled by computing the eigenvalues of carefully randomized tridiagonal matrices. We provide an elementary and unifying treatment of such models, from which we derive an approximate sampling method for more general models. In higher dimension, we consider a special class of DPPs used for numerical integration. We implement a tailored version of a known exact sampler, which allows us to compare the properties of Monte Carlo estimators in new regimes. In the context of reproducible research, we develop an open-source Python toolbox, named DPPy, which implements the state of the art sampling methods for DPPs; Un processus ponctuel déterminantal (DPP) génère des configurations aléatoires de points ayant tendance à se repousser. La notion de répulsion est encodée par les sous-déterminants d’une matrice à noyau, au sens des méthodes à noyau en apprentissage artificiel. Cette forme algébrique particulière confère aux DPP de nombreux avantages statistiques et computationnels. Cette thèse porte sur l'échantillonnage des DPP, c'est à dire sur la conception d'algorithmes de simulation pour ce type de processus. Les motivations pratiques sont l'intégration numérique, les systèmes de recommandation ou encore la génération de résumés de grands corpus de données. Dans le cadre fini, nous établissons la correspondance entre la simulation de DPP spécifiques, dits de projection, et la résolution d'un problème d'optimisation linéaire dont les contraintes sont randomisées. Nous en tirons une méthode efficace d'échantillonnage par chaîne de Markov. Dans le cadre continu, certains DPP classiques peuvent être simulés par le calcul des valeurs propres de matrices tridiagonales aléatoires bien choisies. Nous en fournissons une nouvelle preuve élémentaire et unificatrice, dont nous tirons également un échantillonneur approché pour des modèles plus généraux. En dimension supérieure, nous nous concentrons sur une classe de DPP utilisée en intégration numérique. Nous proposons une implémentation efficace d'un schéma d'échantillonnage exact connu, qui nous permet de comparer les propriétés d'estimateurs Monte Carlo dans de nouveaux régimes. En vue d'une recherche reproductible, nous développons une boîte à outils open-source, nommée DPPy, regroupant les différents outils d'échantillonnage sur les DPP.