Understanding Stacking of Random Hyperplanes for Enhanced Classification

Stacking, random hyperplanes Usman Roshan

Stacking A method to combine classifiers Instead of majority vote or boosting use non- linearized outputs to create new features Then apply a classifier on the new representation Closely related to representation learning Stacked generalization Very little theory is known but works in practice

Random hyperplanes Use random hyperplanes in stacking to make new features Similar to extreme learning machines This simple method tends to perform very well In fact random hyperplanes work very well for dimensionality reduction

Johnson-Lindenstrauss lemma Given any and n and k >= O(log(n)/ 2), for any set of P of n points in Rdthere exists a lower dimensional mapping f(x) (x in P) to Rksuch that for any u,v in P 2 f(u)- f(v) 2 (1+e) u-v 2 (1-e) u-v Furthermore, this mapping can be found in randomized polynomial time. Simply let each random vector be randomly sampled from thenormal Gaussian distribution. Why does this work? Because random projections of vectors preserve length and we model distance between vectors u and v as vectors.

Classification on random hyperplanes Method: For i = 0 to k do: Create random vector w where each wi is uniformly sampled between 0 and 1 Project training data X (each row is datapoint xj) onto w. Let projection zibe Xw Append zias new row to Z Do the same for test data X and call the new representation Z Run linear SVM on Z and predict on Z How does this perform in comparison to liblinear on original data X and X ?

Empirical results Random UCI datasets Linear SVM applied to random hyperplanes Compared to linear SVM on original data Similar results reported elsewhere