Decision Jungles: Compact and Rich Models for Classification
Randomized decision trees and forests have a rich history in machine learning and have seen considerable success in application, perhaps particularly so for computer vision. However, they face a fundamental limitation: given enough data, the number of nodes in decision trees will grow exponentially with depth. For certain applications, for example on mobile or embedded processors, memory is a limited resource, and so the exponential growth of trees limits their depth, and thus their potential accuracy. This paper proposes decision jungles, revisiting the idea of ensembles of rooted decision directed acyclic graphs (DAGs), and shows these to be compact and powerful discriminative models for classification. Unlike conventional decision trees that only allow one path to every node, a DAG in a decision jungle allows multiple paths from the root to each leaf. We present and compare two new node merging algorithms that jointly optimize both the features and the structure of the DAGs efficiently. During training, node splitting and node merging are driven by the minimization of exactly the same objective function, here the weighted sum of entropies at the leaves. Results on varied datasets show that, compared to decision forests and several other baselines, decision jungles require dramatically less memory while considerably improving generalization.
Summary of the paper: This paper revisits the idea 
      of decision DAGs for classification. Unlike a decision tree, a decision 
      DAG is able to merge nodes at each layer, preventing the tree from growing 
      exponentially with depth. This represents an alternative to decision-trees 
      utilizing pruning methods as a means of controlling model size and 
      preventing overfitting. The paper casts learning with this model as an 
      empirical risk minimization problem, where the idea is to learn both the 
      DAG structure along with the split parameters of each node. Two algorithms 
      are presented to learn the structure and parameters in a greedy layer-wise 
      manner using an information-gain based objective. Compared to several 
      baseline approaches using ensembles of fixed-size decision trees, 
      ensembles of decision DAGs seem to provide improved generalization 
      performance for a given model size (as measured by the total number of 
      nodes in the ensemble). Quality: This paper is of generally 
      good quality. The related work seems to have been throughly investigated, 
      the model and algorithms make intuitive sense, and the experiments are 
      fairly compelling and do a good job of investigating the effects of 
      varying different design parameters. One aspect that seems to be missing 
      is a comparison of the training and evaluation times of different 
      approaches. This is an important consideration in these models that I 
      think should be addressed. Clarity: The paper is quite clear 
      for the most part. The writing is good, the model is well-presented, and 
      the experiments are fairly easy to comprehend. One minor detail that I am 
      not quite clear on is whether the ensemble is trained with bagging in 
      addition to the other randomized elements of the learning algorithm. Also, 
      the authors suddenly refer to energy in section 3.1, is this the same as 
      the empirical risk? Finally, there is a minor grammatical error at the end 
      of the LSearch description: "for considerably less compute." 
      Originality: The ideas underlying this paper are fairly well 
      established (decision DAGs, ensembles, empirical risk minimization and 
      information gain). However, the novelty of this paper is in combining 
      these ideas into a cohesive model, and providing intuitive algorithms to 
      learn it. Significance: Random forests are a heavy favorite 
      among machine learning practitioners, and therefore any related method 
      that improves upon them without significantly increasing their 
      computational or implementation overhead could have a large 
      impact.