# binaryTreeTrain

## PURPOSE

Train binary decision tree classifier.

## SYNOPSIS

function [tree,data,err] = binaryTreeTrain( data, varargin )

## DESCRIPTION

     Train binary decision tree classifier.

     Highly optimized code for training decision trees over binary variables.
     Training a decision stump (depth=1) over 5000 features and 10000 training
     examples takes 70ms on a single core machine and *7ms* with 12 cores and
     OpenMP enabled (OpenMP is enabled by default, see toolboxCompile). This
     code shares similarities with forestTrain.m but is optimized for binary
     labels. Moreover, while forestTrain is meant for training random decision
     forests, this code is tuned for use with boosting (see adaBoostTrain.m).

     For more information on how to quickly boost decision trees see:
       [1] R. Appel, T. Fuchs, P. Dollár, P. Perona; "Quickly Boosting
       Decision Trees – Pruning Underachieving Features Early," ICML 2013.
     The code here implements a simple brute-force strategy with the option to
     sample features used for training each node for additional speedups.
     Further gains using the ideas from the ICML paper are possible. If you
     use this code please consider citing our ICML paper.

     During training each feature is quantized to lie between [0,nBins-1],
     where nBins<=256. Quantization is expensive and should be performed just
     once if training multiple trees. Note that the second output of the
     algorithm is the quantized data, this can be reused in future training.

     USAGE
      [tree,data,err] = binaryTreeTrain( data, [pTree] )

     INPUTS
      data       - data for training tree
       .X0         - [N0xF] negative feature vectors
       .X1         - [N1xF] positive feature vectors
       .wts0       - [N0x1] negative weights
       .wts1       - [N1x1] positive weights
       .xMin       - [1xF] optional vals defining feature quantization
       .xStep      - [1xF] optional vals defining feature quantization
       .xType      - [] optional original data type for features
      pTree      - additional params (struct or name/value pairs)
       .nBins      - [256] maximum number of quanizaton bins (<=256)
       .maxDepth   - [1] maximum depth of tree
       .minWeight  - [.01] minimum sample weigth to allow split
       .fracFtrs   - [1] fraction of features to sample for each node split
       .nThreads   - [inf] max number of computational threads to use

     OUTPUTS
      tree       - learned decision tree model struct w the following fields
       .fids       - [Kx1] feature ids for each node
       .thrs       - [Kx1] threshold corresponding to each fid
       .child      - [Kx1] index of child for each node (1-indexed)
       .hs         - [Kx1] log ratio (.5*log(p/(1-p)) at each node
       .weights    - [Kx1] total sample weight at each node
       .depth      - [Kx1] depth of each node
      data       - data used for training tree (quantized version of input)
      err        - decision tree training error

     EXAMPLE

     See also binaryTreeApply, adaBoostTrain, forestTrain

     Piotr's Image&Video Toolbox      Version 3.21
     Copyright 2013 Piotr Dollar.  [pdollar-at-caltech.edu]
     Please email me if you find bugs, or have suggestions or questions!
     Licensed under the Simplified BSD License [see external/bsd.txt]