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   - [16] 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 Computer Vision Matlab Toolbox      Version 3.40
 Copyright 2014 Piotr Dollar.  [pdollar-at-gmail.com]
 Licensed under the Simplified BSD License [see external/bsd.txt]

Generated by m2html © 2003