Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

Bayesian Optimization (BO) methods are often used to optimize an unknown function f(���) that is costly to evaluate. They typically work in an iterative manner. In each iteration, given a set of observation points, BO algorithms select k ��� 1 points to be evaluated. The results of those points are then added to the set of observations and the procedure is repeated until a stopping criterion is met. The goal is to optimize the function f(���) with a small number of experiment evaluations. While this problem has been extensively studied, most existing approaches ignored some real world constraints frequently encountered in practical applications. In this thesis, we extend the BO framework in a number of important directions to incorporate some of these constraints. First, we introduce a constrained BO framework where instead of selecting a precise point at each iteration, we request a constrained experiment that is characterized by a hyper-rectangle in the input space. We introduce efficient sequential and non-sequential algorithms to select a set of constrained experiments that best optimize f(���) within a given budget. Second, we introduce one of the first attempts in batch BO where instead of selecting one experiment at each iteration, a set of k > 1 experiments is selected. This can significantly speedup the overall running time of BO. Third, we introduce scheduling algorithms for the BO framework when: 1) it is possible to run concurrent experiments; 2) the durations of experiments are stochastic, but with a known distribution; and 3) there is a limited number of experiments to run in a fixed amount of time. We propose both online and offline scheduling algorithms that effectively handle these constraints. Finally, we introduce a hybrid BO approach which switches between the sequential and batch mode. The proposed hybrid approach provides us with a substantial speedup against sequential policies without significant performance loss. / Graduation date: 2013

In this thesis, we do an algorithmic study of optimization problems in budgeted auctions, and some well known covering problems in the multi-agent setting. We give new results for the design of approximation algorithms, online algorithms and hardness of approximation for these problems. Along the way we give new insights for many other related problems. Budgeted Auction. We study the following allocation problem which arises in budgeted auctions (such as advertisement auctions run by Google, Microsoft, Yahoo! etc.) : Given a set of m indivisible items and n agents; agent i is willing to pay b[subscript ij] for item j and has an overall budget of B[subscript i] (i.e. the maximum total amount he is willing to pay). The goal is to allocate items to the agents so as to maximize the total revenue obtained. We study the computation complexity of the above allocation problem, and give improved results for the approximation and the hardness of approximation. We also study the above allocation problem in an online setting. Online version of the problem has motivation in the sponsored search auctions which are run by search engines. Lastly, we propose a new bidding language for the budgeted auctions: decreasing bid curves with budget constraints. We make a case for why this language is better both for the sellers and for the buyers. Multi-agent Covering Problems. To motivate this class of problems, consider the network design problem of constructing a spanning tree of a graph, assuming there are many agents willing to construct different parts of the tree. The cost of each agent for constructing a particular set of edges could be a complex function. For instance, some agents might provide discounts depending on how many edges they construct. The algorithmic question that one would be interested in is: Can we find a spanning tree of minimum cost in polynomial time in these complex settings? Note that such an algorithm will have to find a spanning tree, and partition its edges among the agents. Above are the type of questions that we are trying to answer for various combinatorial problems. We look at the case when the agents' cost functions are submodular. These functions form a rich class and capture the natural properties of economies of scale or the law of diminishing returns.We study the following fundamental problems in this setting- Vertex Cover, Spanning Tree, Perfect Matching, Reverse Auctions. We look at both the single agent and the multi-agent case, and study the approximability of each of these problems.

Visual recognition research develops algorithms and representations to autonomously recognize visual entities such as objects, actions, and attributes. The traditional protocol involves manually collecting training image examples, annotating them in specific ways, and then learning models to explain the annotated examples. However, this is a rather limited way to transfer human knowledge to visual recognition systems, particularly considering the immense number of visual concepts that are to be learned. I propose new forms of active learning that facilitate large-scale transfer of human knowledge to visual recognition systems in a cost-effective way. The approach is cost-effective in the sense that the division of labor between the machine learner and the human annotators respects any cues regarding which annotations would be easy (or hard) for either party to provide. The approach is large-scale in that it can deal with a large number of annotation types, multiple human annotators, and huge pools of unlabeled data. In particular, I consider three important aspects of the problem: (1) cost-sensitive multi-level active learning, where the expected informativeness of any candidate image annotation is weighed against the predicted cost of obtaining it in order to choose the best annotation at every iteration. (2) budgeted batch active learning, a novel active learning setting that perfectly suits automatic learning from crowd-sourcing services where there are multiple annotators and each annotation task may vary in difficulty. (3) sub-linear time active learning, where one needs to retrieve those points that are most informative to a classifier in time that is sub-linear in the number of unlabeled examples, i.e., without having to exhaustively scan the entire collection. Using the proposed solutions for each aspect, I then demonstrate a complete end-to-end active learning system for scalable, autonomous, online learning of object detectors. The approach provides state-of-the-art recognition and detection results, while using minimal total manual effort. Overall, my work enables recognition systems that continuously improve their knowledge of the world by learning to ask the right questions of human supervisors. / text

Classification in machine learning has been extensively studied during the pastdecades. Many solutions have been proposed to output accurate classifiers and toobtain statistical grantees on the unseen observations. However, when machinelearning algorithms meet concrete industrial or scientific applications, new computationalcriteria appear to be as important to satisfy as those of classificationaccuracy. In particular, when the output classifier must comply with a computationalbudget needed to obtain the features that are evaluated at test time, wetalk about "budgeted" learning. The features can have different acquisition costsand, often, the most discriminative features are the costlier. Medical diagnosis andweb-page ranking, for instance, are typical applications of budgeted learning. Inthe former, the goal is to limit the number of medical tests evaluate for patients,and in the latter, the ranker has limited time to order documents before the usergoes away.This thesis introduces a new way of tackling classification in general and budgetedlearning problems in particular, through a novel framework lying in theintersection of supervised learning and decision theory. We cast the classificationproblem as a sequential decision making procedure and show that this frameworkyields fast and accurate classifiers. Unlike classical classification algorithms thatoutput a "one-shot" answer, we show that considering the classification as a seriesof small steps wherein the information is gathered sequentially also providesa flexible framework that allows to accommodate different types of budget constraintsin a "natural" way. In particular, we apply our method to a novel type ofbudgeted learning problems motivated by particle physics experiments. The particularityof this problem lies in atypical budget constraints and complex cost calculationschemata where the calculation of the different features depends on manyfactors. We also review similar sequential approaches that have recently known aparticular interest and provide a global perspective on this new paradigm.

La prise de décision est un domaine 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. En 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. En robotique, l’objectif premier est l’efficacité, dans le but d’être déployés en environnement réel. Cependant en robotique ce que l’on peut appeler le budget et qui concerne les limitations inhérentes au matériel, comme les temps de calculs, les actions limitées disponibles au robot ou la durée de vie de la batterie du robot, ne sont 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 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 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. / Decision-making is a highly researched field in science, be it in neuroscience to understand the processes underlying animal decision-making, or in robotics to model efficient and rapid decision-making processes in real environments. In neuroscience, this problem is resolved online with sequential decision-making models based on reinforcement learning. In robotics, the primary objective is efficiency, in order to be deployed in real environments. However, in robotics what can be called the budget and which concerns the limitations inherent to the hardware, such as computation times, limited actions available to the robot or the lifetime of the robot battery, are often not taken into account at the present time. We propose in this thesis to introduce the notion of budget as an explicit constraint in the robotic learning processes applied to a localization task by implementing a model based on work developed in statistical learning that processes data under explicit constraints, limiting the input of data or imposing a more explicit time constraint. In order to discuss an online functioning of this type of budgeted learning algorithms, we also discuss some possible inspirations that could be taken on the side of computational neuroscience. In this context, the alternation between information retrieval for location and the decision to move for a robot may be indirectly linked to the notion of exploration-exploitation compromise. We present our contribution to the modeling of this compromise in animals in a non-stationary task involving different levels of uncertainty, and we make the link with the methods of multi-armed bandits.

Cette thèse aborde le problème de classification en apprentissage statistique sous un angle nouveau en rajoutant une dimension séquentielle au processus de classification. En particulier, nous nous intéressons au cas de l'apprentissage à contraintes de budget (ou apprentissage budgété) où l'objectif est de concevoir un classifieur qui, tout en apportant des prédictions correctes, doit gérer un budget computationnel, consommé au fur et à mesure que les différents attributs sont acquis ou évalués. Les attributs peuvent avoir des coûts d'acquisition différents et il arrive souvent que les attributs les plus discriminatifs soient les plus coûteux. Le diagnostic médical et le classement de pages web sont des exemples typiques d'applications de l'apprentissage budgété. Pour le premier, l'objectif est de limiter le nombre de tests médicaux que le patient doit endurer et, pour le second, le classement doit se faire dans un temps assez court pour ne pas faire fuir l'usager. Au cours de cette thèse, nous nous sommes intéressés à des contraintes de budget atypiques, que la conception de trigger nous a motivés à investiguer. Les triggers sont un type de classifieurs rapides, temps-réel et sensibles aux coûts qui ont pour objectif de filtrer les données massives que les accélérateurs de particules produisent et d'en retenir les événements les plus susceptibles de contenir le phénomène étudié, afin d'être enregistrés pour des analyses ultérieures. La conception de trigger impose des contraintes computationnelles strictes lors de la classification mais, surtout, exhibe des schémas complexes de calcul du coût de chaque attributs. Certains attributs sont dépendants d'autres attributs et nécessitent de calculer ces derniers en amont, ce qui a pour effet d'augmenter le coût de la classification. De plus, le coût des attributs peut directement dépendre de leur valeur concrète. On retrouve ce cas de figure lorsque les extracteurs d'attributs améliorent la qualité de leur sortie avec le temps mais peuvent toujours apporter des résultats préliminaires. Enfin, les observations sont regroupées en sacs et, au sein du même sac, certaines observations partagent le calcul d'un sous-ensemble d'attributs. Toutes ces contraintes nous ont amenés à formaliser la classification sous un angle séquentiel.Dans un premier temps, nous proposons un nouveau cadriciel pour la classification rapide en convertissant le problème initial de classification en un problème de prise décision. Cette reformulation permet d'un part d'aborder la séquentialité de manière explicite, ce qui a pour avantage de pouvoir aisément incorporer les différentes contraintes que l'on retrouve dans les applications réelles, mais aussi d'avoir à disposition toute une palette d'algorithmes d'apprentissage par renforcement pour résoudre le nouveau problème. Dans une seconde partie, nous appliquons notre modèle de classification séquentielle à un problème concret d'apprentissage à contraintes de budget et démontrant les bénéfices de notre approche sur des données simulées (à partir de distributions simplifiées) de l'expérience LHCb (CERN). / Classification in machine learning has been extensively studied during the pastdecades. Many solutions have been proposed to output accurate classifiers and toobtain statistical grantees on the unseen observations. However, when machinelearning algorithms meet concrete industrial or scientific applications, new computationalcriteria appear to be as important to satisfy as those of classificationaccuracy. In particular, when the output classifier must comply with a computationalbudget needed to obtain the features that are evaluated at test time, wetalk about “budgeted” learning. The features can have different acquisition costsand, often, the most discriminative features are the costlier. Medical diagnosis andweb-page ranking, for instance, are typical applications of budgeted learning. Inthe former, the goal is to limit the number of medical tests evaluate for patients,and in the latter, the ranker has limited time to order documents before the usergoes away.This thesis introduces a new way of tackling classification in general and budgetedlearning problems in particular, through a novel framework lying in theintersection of supervised learning and decision theory. We cast the classificationproblem as a sequential decision making procedure and show that this frameworkyields fast and accurate classifiers. Unlike classical classification algorithms thatoutput a “one-shot” answer, we show that considering the classification as a seriesof small steps wherein the information is gathered sequentially also providesa flexible framework that allows to accommodate different types of budget constraintsin a “natural” way. In particular, we apply our method to a novel type ofbudgeted learning problems motivated by particle physics experiments. The particularityof this problem lies in atypical budget constraints and complex cost calculationschemata where the calculation of the different features depends on manyfactors. We also review similar sequential approaches that have recently known aparticular interest and provide a global perspective on this new paradigm.

Master’s thesis aims at understanding the process of planning and implementation of development project. It focuses in particular on the description and analysis of various stages of the project, especially in terms of their management and elimination of potential risks. The first part of the thesis deals mainly with theoretical introduction of the topic and definition of basic concepts and methods. The second part of the work is already trying to map a specific development project and to analyze its real progress. This section also proposed other possible approaches to addressing certain specific tasks within the individual phases and the elimination of potential risks that the project actually occurred, including the proposal of optimal process for managing development project.