Search

The increasing size of available data has led machine learning specialists to consider more complex models in order to achieve better performance. From a theoretical point of view, statistical learning under resource constraints has known a growing interest in the machine learning community. Many settings were developed to formalize budgeted limitations. In this thesis, we are motivated by these challenges, where we consider classical learning problems under the ``frugal lens". First, we tackle support recovery in a sparse linear regression problem, with one pass over data. We develop an online greedy algorithm named "online orthogonal matching pursuit" that actively selects covariates in a sequential way, with guarantees on its computational complexity that is adaptive to the unknown magnitude of the regression coefficients. Second, we consider the problem of model selection aggregation of experts. We present procedures that achieve fast rates under various budgeted settings and discuss the attainability of fast rates in different settings. Third, we tackle the problem of online prediction of individual sequences, where no distributional assumption is made in the process of generating data. We consider some natural budgeted constraints on the number of experts used for prediction and the number of observed feedbacks. We develop new strategies for each setting and discuss the attainability of constant regrets. Finally, we consider the problem of fixed confidence best arm identification. Given a confidence level, the learner wants to identify the arm with the largest mean using the least number of queries possible. We suppose that simultaneous queries are possible and prove that significant improvement can be made with respect to the BAI standard algorithms by taking the unknown covariance of the arms into consideration., Depuis le début du développement de la théorie de l'apprentissage statistique, un intérêt particulier a été porté aux méthodes efficaces en temps de calcul ainsi qu'en espace de stockage nécessaire, afin qu'elles soient utilisables en pratique. Ceci a motivé plusieurs théoriciens à formaliser différents problèmes d'apprentissage statistique sous contrainte d'accès aux données et aux ressources computationnelles. Dans cette thèse, nous avons considéré plusieurs problèmes d'apprentissage statistiques et d'apprentissage séquentiel, sous différents types de contraintes. Le premier problème traité concerne la régression parcimonieuse sous une contrainte de nature computationnelle. Nous développons un algorithme effectuant un seul passage sur les données (celles-ci sont supposées arriver en temps réel) avec une limitation sur l'espace mémoire disponible. Le deuxième problème traité concerne l'agrégation d'experts. Nous revisitons ce problème dans le cas où l'accès aux données est limité et développons des méthodes permettant d'atteindre des taux rapides pour l'excès de risques. Le problème suivant concerne l'agrégation d'experts pour la prédiction des suites individuelles fixes. Nous introduisant un formalisme similaire à celui utilisé dans le problème précédent: nous supposons que pour chaque tour, le joueur a une contrainte sur le nombre d'experts à utiliser pour la prédiction et une contrainte sur le nombre de pertes d'experts individuels observées après avoir fait une prédiction. Nous présentant des procédures pour chaque cas et développons des garanties théoriques sur le regret cumulé des stratégies présentées. Le dernier problème considéré est une instance du problème de l'identification du meilleur bras dans le cadre de la théorie des bandits stochastiques. Nous présentons une extension du formalisme standard en permettant le tirage de plusieurs bras simultanément. Dans ce cadre nous montrons que de nouvelles bornes, potentiellement meilleurs que les bornes classiques, sont possibles, et nous présentons des procédures permettant de les atteindre.

The performance of a machine learning algorithm is dependent on the quality of the available data for model development. However, in practical situations, the availability of the data is variable and can be limited. This limitation creates a budget problem for data-driven techniques and the objective in such situations is to develop the best model given the available data. In this article, we examine the budgeted learning problem for spatial data within the urban context. We demonstrate the effectiveness of a novel approach for inferring the attributes of spatial data when the data for the model is budgeted. This is achieved using urban functions - which describe the designated use of a geographical space - to infer the types of streets in a city. We evaluated the approach by comparing the performance of the model using the data in each urban function (the budget) against the results from the aggregate of all the functions (all data). The results indicate that with our model, individual urban functions are sufficient to infer the type attributes of streets.

International audience; The problem of keyword spotting i.e. identifying keywords in a real-time audio stream is mainly solved by applying a neural network over successive sliding windows. Due to the difficulty of the task, baseline models are usually large, resulting in a high computational cost and energy consumption level. We propose a new method called SANAS (Stochastic Adaptive Neural Architecture Search) which is able to adapt the architecture of the neural network on-the-fly at inference time such that small architectures will be used when the stream is easy to process (silence, low noise, ...) and bigger networks will be used when the task becomes more difficult. We show that this adaptive model can be learned end-to-end by optimizing a trade-off between the prediction performance and the average computational cost per unit of time. Experiments on the Speech Commands dataset [1] show that this approach leads to a high recognition level while being much faster (and/or energy saving) than classical approaches where the network architecture is static.

International audience; Recent years have seen a fast growth in the number of applications of Machine Learning algorithms from Computer Science to Robotics. Nevertheless, while most such attempts were successful in maximizing robot performance after a long learning phase, to our knowledge none of them explicitly takes into account the budget in the algorithm evaluation: e.g. budget limitation on the learning duration or on the maximum number of possible actions by the robot. In this paper, we introduce an algorithm for robot spatial localization based on image classification using a sequential budgeted learning framework. This aims to allow the learning of policies under an explicit budget. In this case our model uses a constraint on the number of actions that can be used by the robot. Our approach enables to reduce the problem to a classification task under budget constraint. We apply this algorithm to a localization problem in a simulated environment. We compare it first to simple neural networks for the classification part and second to different techniques of policy selection. The results show that the model can effectively learn an efficient active sensing policy (i.e. alternating between sensor measurement and movement to get additional information in different positions) in order to optimize its localization performance under each tested fixed budget. We also show that with this algorithm the simulated robot can transfer the learned policy as well as knowledge about which budget gives the best performance/budget ratio in a given environment to other environments with similar properties. We finally test the algorithm with real navigation data acquired in an indoor environment with the PR2 robot. Altogether, these results suggest a promising framework for enabling budgeted localization in robots and avoiding to make robots relearn everything from scratch in each new environment.

Decision-making is a vast domain of scientific research, investigated by several different disciplines, such as in Neuroscience to understand the processes underlying decision-making in animals, in Robotics to propose efficient and rapid decision-making algorithms working in a variety of tasks. From the point of view of Neuroscience, this problem is usually solved with online processes through models of sequential decision-making based on the reinforcement learning framework. From the point of view of Robotics, the primary objective is to come up with efficient solutions that work in the real world. However, nowadays in Robotics, researches most often neglect what we can call the budget and which concerns the inherent material limitations of a robot such as the computation time, the limited number of possible actions, or the limited life duration of the robot's batteries.In this PhD work, we propose to introduce the notion of budget as an explicit constraint in Robotics learning processes applied to a localization task. To do so, we first test a model based on recent developments in statistical learning, which can treat data under budget constraints either by limiting the number of processed data or by fixing an explicit time limitation. Moreover, in order to progress towards a online version of this type of budgeted learning algorithms, we discuss possible inspirations from computational neuroscience. Within this framework, the alternation between information seeking for localization and decisions to move within the environment can be indirectly linked to the exploration-exploitation trade-off. We finally present our contribution to the modeling of this trade-off in animals performing a non-stationary task under different levels of uncertainty, and make the link with bandit methods.; La prise de décision est un domaine vaste et très étudié en sciences, que ce soit en neurosciences pour comprendre les processus sous tendant la prise de décision chez les animaux, qu’en robotique pour modéliser des processus de prise de décision efficaces et rapides dans des tâches en environnement réel. Du point de vue des neurosciences, ce problème est résolu online avec des modèles de prises de décision séquentiels basés sur l’apprentissage par renforcement. Du point de vue de la robotique, l’objectif premier est l’efficacité, dans le but d’être déployés en environnement réel. Cependant, dans le cas de la robotique, ce que l’on peut appeler le budget et qui concerne les limitations inhérentes au matériel, comme par exemple les temps de calculs, les actions limitées disponibles au robot ou la durée de vie de la batterie du robot, ne sont, le plus souvent, pas prises en compte à l’heure actuelle.Nous nous proposons dans ce travail de thèse d’introduire la notion de budget comme contrainte explicite dans les processus d’apprentissage robotique appliqués à une tâche de localisation en mettant en place un modèle basé sur des travaux récents développés en apprentissage statistique qui traitent les données sous contrainte de budget, en limitant l’apport en données ou en posant une contrainte de temps plus explicite.Dans le but d’envisager à plus long terme un fonctionnement online de ce type d’algorithmes d’apprentissage budgétisé, nous discutons aussi certaines inspirations possibles qui pourraient être prises du côté des neurosciences computationnelles. Dans ce cadre, l’alternance entre recherche d’information pour la localisation et la décision de se déplacer pour un robot peuvent être indirectement liés à la notion de compromis exploration-exploitation. Nous présentons notre contribution à la modélisation de ce compromis chez l’animal dans une tâche non stationnaire impliquant différents niveaux d’incertitude, et faisons le lien avec les méthodes de bandits manchot.

The continuous increase, witnessed in the last decade, of both the amount of available data and the areas of application of machine learning, has lead to a demand for both learning and planning algorithms that are capable of handling large-scale problems. Thus scalability has become an important characteristic of modern machine learning algorithms. In this thesis we concentrate on tractable approaches to both learning and planning, capable of solving problems in high-dimensional spaces. We investigate multiple forms of high-dimensionality, where dimensionality can refer to the number of samples to be processed, the number of samples available for training, the dimensionality of the feature space, or even the dimensionality of the state-space. We present work on classifier cascades, developing a novel framework for interpreting, training, and employing such structures of classifiers. A Boosting algorithm developed in this framework highlights its ability to jointly train the classifiers at the cascade nodes. The work presented on goal-planning also results in a novel framework, this time for automatic macro-action discovery in imitation learning, specifically addressing problems with large state-spaces as well as with observation signals of high-dimensionality. The proposed DPBoost algorithm is capable of solving very complex goal-planning tasks where previous state-of-the-art fails. Addressing computer hardware limitations, and in particular memory limitations, we propose a new learning framework, which we call reservoir learning, which attempts to directly account for this limited memory during the training process. In particular we propose to consider learning in the presence of a reservoir in which the learner may store samples. Based on Boosting we develop a novel strategy for populating this reservoir which avoids redundancy by taking into account the joint behavior of samples. Finally high-dimensionality is also addressed in its most typical setting, that is when the feature space is large. We propose novel feature selection algorithms in the context of classification. Based on information theoretic tools, these algorithms attempt to maximize the joint mutual information between the selected, continuous, variables and the, discrete, class label variable.