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]:
Thanks for all these valuable and insightful suggestions. In what follows our responses. All responses marked with an * have already been included in the updated version of the arXiv submission. The others are currently been investigated.

- '...Does the framework easily extend to other classification techniques?'

*Response: The learned transformation at each node reduces intra-class variation and increases inter-class separation. Thus, such learned (transformed) representation can potentially help in other classification tasks as well, e.g., subspace based methods [A]. We have incorporated such comment in the revised paper, see Sec.1.


- 'All dataset images used were scaled down to 16x16. How does this method perform on truly high-dimensional data?'; 'All the images were resized to 16 x 16': It's ambiguous whether this was for just YaleB, or all the datasets?; '... the feature space is very large ...'

*Response: Such image resize is only applied to the Extend YaleB and MNIST, which gives a 256-dimensional feature. Given d-dimensional features, in this paper, we only focus on a d*d-sized square transformation matrix. A potential solution to handle high-dimensional data is to learn a 'fat' r*d-sized transformation matrix (r<<d) to compress the data while enhancing the discriminability, as discussed in [A]. This has been mentioned in the revised version, see Sec.2.4.


- 'Is there a reason that not all experiments were performed with each of the datasets?'; '... in all 3 of these plots.'

*Response: We first compare as many learners in a tree context for accuracy and testing time; then we only compare with learners that are widely adopted for random forests. See revised version, Sec.3, for a clarification.


- '...timing results aren't too informative when reported for a single dataset.'

Response: We can observe from the second paragraph in Sec.2.4, the testing time is determined only by the feature dimension and the tree depth, as explained in detail in another response.


- 'Experiments showing the effect of noise/mislabeld examples would be interesting as the impact of such imperfections on this scheme is unclear.'

*Response: The first two terms in (3) will significantly reduce the intra-class variation/noise; and the final results combines multiple random trees, thereby expecting the proposed framework to be very robust to noise. This is the subject of future investigation. We have clarified this in the discussion, Sec.4.


- 'Section 3.2, Paragraph 2, Sentence 1: What is the reason for mentioning that classes arriving at a node are randomly split into two categories? Why is it being introduced here as a new source of randomness?'

*Response: In (3), we learn a transformation optimized for two class problem. The proposed strategy reduces a multi-class problem into a two-class problem at each node for transformation learning; furthermore, it introduces node randomness to avoid duplicated trees generated. This has been further clarified in Sec.2.5.


- 'For the Kinect experiment, ... It would have been better to follow the setup in (Denil et al., 2013) ...'; '...but it would be nice to include a comparison to Denil et al (the dataset providers).'

Response: As training using the complete Kinect dataset requires considerable time and computation resources, we decided on a reduced scale of experiments, sufficient to show the advantage of the proposed approach over popular learners. Further experiments are ongoing.


- 'Did you consider applying a difference of convex programming approach to (1) instead of gradient descent?'

Response: We adopted a gradient descent approach only for its efficiency and simplicity. It is probably not the best approach, and we leave it open for discussions and improvements.


- ' 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.'

*Response: Assume each learned transformation matrix is of size r*d (r=d in the paper, but r is allowed to be a constant much smaller than d). Each split test consists of two matrix multiplications of complexity O(r*d) using a sequential implementation. With the modern architecture, p processes are usually assigned to each multiplication, which reduces the complexity to O(r*d/p) plus some small overhead. Thus, each split test can be reduced to linear complexity. However, we agree 'virtually computationally free' is over-stressed, and we revised it to 'low computational complexity'.


- 'One question I have is how dependent this method is on image alignment.'

*Response: The proposed method is robust to misalignment. One main objective of the learned transformation is to reduce the intra-class variations, which includes misalignment. As an example, in a separate work, we demonstrate the success in face recognition across poses using the learned transformation, see [A].


- 'Pixel descriptors for kinect ... forming a 96-dim descriptor -- is this correct? ... '

*Response: Each pixel is represented using depth difference from its 96 equally spaced neighbors with radius 8, 32 and 64 repletely, forming a 288-dim descriptor. We have further clarified this in Sec.3.3.


[A] Q. Qiu and G. Sapiro, 'Learning transformations for clustering and classification', CoRR, vol. abs/1309.2074, 2013.  http://arxiv.org/abs/1309.2074