Learning Transformations for Classification Forests
Authors: Qiang Qiu, Guillermo Sapiro
ICLR 2014

Abstract: This work introduces a transformation-based learner model for classification forests. The weak learner at each split node plays a crucial role in a classification tree. We propose to optimize the splitting objective by learning a linear transformation on subspaces using nuclear norm as the optimization criteria. The learned linear transformation restores a low-rank structure for data from the same class, and, at the same time, maximizes the separation between different classes, thereby improving the performance of the split function. Theoretical and experimental results support the proposed framework.


Peer review:
[Review]:
Summary

This paper introduces a new split node learner for use in classification trees. The learner is parameterized by a d x d dimensional matrix T (d is the input dimension) and two subspaces, one for each class in a binary classification problem. At test time, a data point is transformed by T and assigned to the class whose subspace is best able to approximate the transformed point (least L2 residual). For each split node, the transformation T is learned by (locally) minimizing a non-convex objective function that is a difference of nuclear norms of transformed data matrices. Theoretical justification is given for the objective, showing that if the objective is 0 then the transformed subspaces for the two classes is orthogonal.

Empirical results are shown on four datasets and indicate that the proposed method obtains good performance.

Novelty and Quality

To my knowledge, the proposed split objective is novel. The paper is very well written and the method is explained in a clear manner. 
 
Pros

+ The split objective and learner is novel and well motivated.
+ Experimental performance is convincing compared to other split learners.
+ The theoretical justification for the method is compelling and the presentation is clear.

Cons / Questions for author feedback

Details of the experimental setup are missing in some cases:
 - What d-dimensional feature vectors are computed for each experiment? And what is d in each case? This is explained for the Kinect experiment, but not for the others.
 - Sec. 3.1 “we further evaluate the effect of randomness introduced by randomly dividing classes arriving at each split node into two categories.” I don’t follow how the experiment described here evaluates this source of randomness. This simply reports accuracy on the 15-scenes dataset. I was expected an experiment that controlled for this source of randomness.
 - For the Kinect experiment, why did you use only test images (450 for training/50 for testing)? It would have been better to follow the setup in (Denil et al., 2013) so that the results in the paper are comparable to Denil et al.’s results.

The paper is missing a discussion of the drawbacks of the proposed approach. For example, decision trees with decision stumps are often applied to problems where the feature space is very large (or even infinite). How could the proposed approach be modified to work in these cases?

Did you consider applying a difference of convex programming approach to (1) instead of gradient descent?

Sec 2.4: “... only involves matrix multiplication, which is virtually computationally free at the testing time.” This seems like a odd claim. If d is large, then these matrix multiplications are far from free.