You are here: Machine Learning for Precision Health»Efficient Max-Margin Decision Forests

Efficient Max-Margin Decision Forests

Efficient Decision-Forest Learning with SVM-Like Maximum Margin Separation

The classic decision forest uses a univariate split test, with feature space coordinate-aligned splits, e.g. thresholds for of the kth feature element of the input feature vector v.However, such a decision boundary can require many binary tests to make the joint decision boundary approximate the maximum margin class separation.

Efficient Decision Forest Learning Diagram

Maximum margin decision boundary is achievable with decision forests and few trees using differentiable information gain. This figure shows a comparison of the decision boundary locations for a 3 category classification task: circles (red), diamonds (yellow), and pluses (green). The boundary locations for 1, 10 and 100 trees are shown in the first, second and third columns respectively. The top row shows the sub-optimal boundaries using an enhanced forest with oblique hyperplanes and conventional brute force search for optimal boundary parameters, while the bottom row shows the optimal maximum margin solution when differentiable information gain is solution is used.
 

An alternative is to approximate the maximum margin decision boundary using far fewer but stronger weak learner models, such as hyperplanes or conic functions, and this is especially true if differentiable information gain is used.

We augment the classic forest with differentiable information gain that we optimize through gradient ascent, for such stronger learners demonstrate (figure) how it yields maximum margin fidelity with fewer trees (T=number of trees) which helps endow the trained forest with superior generalization for accurate predictions on non-training data.

References

[1] Albert Montillo, J. Tu, J. Shotton, J. Winn, J. E. Iglesias, D. Metaxas, , and A. Criminisi. Entangled Forests and Differentiable Information Gain Maximization. In Decision Forests for Computer Vision and Medical Image Analysis. Springer, 2013.