The space of compile-time transformations and or run-time options which can improve the performance of a given code is usually so large as to be virtually impossible to search in any practical time-frame. Thus, heuristics are leveraged which can suggest good but not necessarily best configurations. Unfortunately, since such heuristics are tightly coupled to processor architecture performance is not portable; heuristics must be tuned, traditionally manually, for each device in turn. This is extremely laborious and the result is often outdated heuristics and less effective optimisation. Ideally, to keep up with changes in hardware and run-time environments a fast and automated method to generate heuristics is needed. Recent works have shown that machine learning can be used to produce mathematical models or rules in their place, which is automated but not necessarily fast. This thesis proposes the use of active machine learning, sequential analysis, and active feature acquisition to accelerate the training process in an automatic way, thereby tackling this timely and substantive issue. First, a demonstration of the efficiency of active learning over the previously standard supervised machine learning technique is presented in the form of an ensemble algorithm. This algorithm learns a model capable of predicting the best processing device in a heterogeneous system to use per workload size, per kernel. Active machine learning is a methodology which is sensitive to the cost of training; specifically, it is able to reduce the time taken to construct a model by predicting how much is expected to be learnt from each new training instance and then only choosing to learn from those most profitable examples. The exemplar heuristic is constructed on average 4x faster than a baseline approach, whilst maintaining comparable quality. Next, a combination of active learning and sequential analysis is presented which reduces both the number of samples per training example as well as the number of training examples overall. This allows for the creation of models based on noisy information, sacrificing accuracy per training instance for speed, without having a significant affect on the quality of the final product. In particular, the runtime of high-performance compute kernels is predicted from code transformations one may want to apply using a heuristic which was generated up to 26x faster than with active learning alone. Finally, preliminary work demonstrates that an automated system can be created which optimises both the number of training examples as well as which features to select during training to further substantially accelerate learning, in cases where each feature value that is revealed comes at some cost.

Cette thèse propose de s'intéresser au problème de la prédiction en apprentissage statistique sous contrainte de coût, notamment du coût de l'information utilisée par le système de prédiction. Les approches classiques d'apprentissage statistique utilisent généralement le seul aspect de la performance en prédiction pour évaluer la qualité d'un modèle, ignorant le coût potentiel du modèle, par exemple en quantité de données utilisées en apprentissage (nombre d'exemples, nombre d'étiquette, mémoire) ou en inférence (quantité de features -ou caractéristiques-). Nous proposons plus particulièrement dans ce manuscrit plusieurs approches pour l'inférence sous contrainte de coût en terme de caractéristiques. Nous développons trois modèles qui intègrent pendant l'apprentissage une notion du coût de l'information utilisée pour la prédiction, avec pour objectif de contraindre le coût de la prédiction en inférence. Nous présentons un modèle de sélection de features appliqué au démarrage à froid en recommendation, puis deux méthodes adaptatives d'acquisition de caractéristiques, qui permettent un meilleur compromis coût/prédiction, dans un cadre plus général. Nous utilisons des méthodes d'apprentissage de représentations avec des architectures type réseau de neurones récurrents et des algorithmes par descente de gradient pour l'apprentissage. La dernière partie du manuscrit s'intéresse au coût lié aux étiquettes, usuellement dénommé apprentissage actif dans la littérature. Nous présentons nos travaux pour une approche nouvelle de ce problème en utilisant le méta-apprentissage ainsi qu'une première instanciation basée sur des réseaux récurrents bi-directionnels. / This thesis studies the problem of machine learning under budget constraints, in particular we propose to focus on the cost of the information used by the system to predict accurately. Most methods in machine learning usually defines the quality as the performance (e.g accuracy) on the task at hand, but ignores the cost of the model itself: for instance, the number of examples and/or labels needed during learning, the memory used, or the number of features required to predict at test-time. We propose more specifically in this manuscript several methods for cost-sensitive prediction w.r.t. the quantity of features used. We present three models that learn to predict under such constraint, i.e that learn a strategy to gather only the necessary information in order to predict well but with a small cost. The first model is a static approach applied on cold-start recommendation. We then define two adaptive methods that allow for a better trade-off between cost and accuracy, in a more generic setting. We rely on representation learning techniques, along with recurrent neural networks architecture and gradient descent algorithms for learning. In the last part of the thesis, we propose to study the problem of active-learning, where one aims at constraining the amount of labels used to train a model. We present our work for a novel approach of the problem using meta-learning, with an instantiation using bi-directional recurrent neural networks.