Relatore : Patrick GALLINARI

Co-relazione : DENOYER Ludovic

A General Sequential Model for Constrained Classification

This thesis introduces a body of work on sequential models for classification. These models allow for a much more flexible and general approach to classification tasks. Many tasks ultimately require the classification of some object, but cannot be han- dled with a single atomic classification step. This is the case for tasks where in- formation is either not immediately available upfront, or where the act of accessing different aspects of the object being classified may present various costs (due to time, computational power, monetary cost, etc.). The goal of this thesis is to introduce a new method, which we call datum-wise classification, that is able to handle these more complex classifications tasks by modelling them as sequential processes. We begin with a brief overview of supervised classification and reinforcement learning. We build on these two subjects to show how the supervised classification task can be modelled as a sequential decision process, which we call a ‘datum-wise classifier’. The datum-wise classifier can be trained using standard reinforcement learning algorithms. We introduce two example situations, based on text classifica- tion and image classification tasks, and demonstrate the advantages of classification as a sequential process. We continue by showing that with a slight modification of the reward function defining our datum-wise classification tasks, we can impose sparsity-like penalties on the model, thus allowing us to handle a much larger family of tasks. In effect, by imposing a negative penalty on certain information acquisition actions the classifier performs, we show that we are imposing an L0 -like penalty on the useage of features by the model. We begin by demonstrating how our model performs relative to more standard linear sparse classifiers such as the L1 -regularized linear SVM and the LASSO. We then demonstrate how, by including more complex (and not necessarily convex) regularizations on the model, we can handle more complex tasks such as classification with costly features, hard limits on feature usage, and even spatially constrained features. Of course the quasi-combinatorial aspect of these tasks means that training time can be problematic for certain tasks, especially if the number of features (and therefore actions) is high. We finish by presenting two new reinforcement learning algorithms that are able to drastically reduce the complexity of our original RL training algorithm, and show that they are able to find ‘good’ policies for problems that are not tractable with the current set of algorithms.

Pubblicazioni 2011-2014

• 2014
  • G. Dulac‑Arnold : “A General Sequential Model for Constrained Classification”, these, difesa 02/07/2014, relatore Gallinari, Patrick, co-relazione : Denoyer, Ludovic (2014)
  • G. Dulac‑Arnold, L. Denoyer, N. Thome, M. Cord, P. Gallinari : “Sequentially Generated Instance-Dependent Image Representations for Classification”, International Conference on Learning Representations, ICLR 2014, Banff, Canada (2014)
• 2012
  • G. Dulac‑Arnold, L. Denoyer, Ph. Preux, P. Gallinari : “Sequential approaches for learning datum-wise sparse representations”, Machine Learning, vol. 89 (1-2), pp. 87-122, (Springer Verlag) (2012)
  • G. Dulac‑Arnold, L. Denoyer, P. Gallinari : “Lecture Séquentielle de Documents pour la Classification”, CORIA, Bordeaux, France, pp. 245-259 (2012)
  • G. Dulac‑Arnold, L. Denoyer, Ph. Preux, P. Gallinari : “Fast Reinforcement Learning with Large Action Sets Using Error-Correcting Output Codes for MDP Factorization”, Machine Learning and Knowledge Discovery in Databases, vol. 7524, Lecture Notes in Computer Science, Bristol, United Kingdom, pp. 180-194, (Springer) (2012)
  • G. Dulac‑Arnold, L. Denoyer, Ph. Preux, P. Gallinari : “Classification Localement Parcimonieuse par Méthodes Séquentielles”, CAP 2012 - Conférence Francophone sur l'Apprentissage Automatique, Nancy, France (2012)
  • G. Dulac‑Arnold, L. Denoyer, Ph. Preux, P. Gallinari : “Apprentissage par renforcement rapide pour des grands ensembles d’actions en utilisant des codes correcteurs d’erreur”, Journées Francophones sur la planification, la décision et l'apprentissage pour le contrôle des systèmes - JFPDA 2012, Villers-lès-Nancy, France, pp. 12 p (2012)
• 2011
  • G. Dulac‑Arnold, L. Denoyer, Ph. Preux, P. Gallinari : “Datum-wise classification. A sequential Approach to sparsity”, ECML PKDD 2011 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, vol. 6911, Lecture Notes in Computer Science, Athens, Greece, pp. 375-390, (Springer) (2011)
  • G. Dulac‑Arnold, L. Denoyer, P. Gallinari : “Text Classification: A Sequential Reading Approach”, 33^rd European Conference on Information Retrieval (ECIR 2011), vol. 6611, Lecture Notes in Computer Science, Dublin, Ireland, pp. 411-423, (Springer Berlin / Heidelberg) (2011)