Skip to Main content Skip to Navigation
Poster communications

MDDAG: learning deep decision DAGs in a Markov decision process setup

D. Benbouzid 1 Róbert Busa-Fekete 2, 3 Balázs Kégl 2, 4, 5
1 AppStat
LAL - Laboratoire de l'Accélérateur Linéaire
5 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : In this paper we propose an algorithm that builds sparse decision DAGs (directed acyclic graphs) out of a list of features or base classifiers. The basic idea is to cast the DAG design task as a Markov decision process. Each instance can decide to use or to skip each base classifier, based on the current state of the classifier being built. The result is a sparse decision DAG where the base classifiers are selected in a data-dependent way. The development of algorithm was directly motivated by improving the traditional cascade design in applications where the computational requirements of classifying a test instance are as important as the performance of the classifier itself. Beside outperforming classical cascade designs on benchmark data sets, the algorithm also produces interesting deep structures where similar input data follows the same path in the DAG, and subpaths of increasing length represent features of increasing complexity.
Document type :
Poster communications
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download
Contributor : Sabine Starita <>
Submitted on : Thursday, January 23, 2014 - 5:02:18 PM
Last modification on : Wednesday, October 14, 2020 - 3:56:47 AM
Long-term archiving on: : Thursday, April 24, 2014 - 12:15:56 PM


Files produced by the author(s)


  • HAL Id : in2p3-00935607, version 1



D. Benbouzid, Róbert Busa-Fekete, Balázs Kégl. MDDAG: learning deep decision DAGs in a Markov decision process setup. 25th Annual Conference on Neural Information Processing Systems (NIPS 2011), Dec 2011, Granada, Spain. ⟨in2p3-00935607⟩



Record views


Files downloads