TL;DR
The Layered Random Projection (LaRP) framework reimagines how we approximate complex nonlinear kernels for machine learning. By decomposing the approximation into alternating layers of linear, localized random projections and non-saturating nonlinearities, LaRP achieves state-of-the-art classification accuracy on standard benchmarks while using significantly fewer random features than previous methods.
What Problem Does This Paper Address?
Kernel methods are a staple of machine learning, allowing algorithms to learn complex, nonlinear patterns by implicitly mapping data into high-dimensional feature spaces (the "kernel trick"). However, they suffer from two major "curses":
- The Curse of Dimensionality: Explicitly working in these high-dimensional spaces is computationally prohibitive.
- The Curse of Support: As training datasets grow, the number of "support vectors" required to define the decision boundary grows unboundedly, leading to sluggish training and testing speeds.
While previous "random feature map" techniques (like those by Rahimi and Recht) attempted to solve this by embedding data into lower-dimensional Euclidean spaces, they often require a massive number of random features to maintain accuracy. The authors of this paper identify a gap: most existing methods don't separately model the linear and nonlinear components of the kernel, missing out on potential efficiencies.
Methods
The authors introduce LaRP, a framework that mimics the architecture of a neural network but relies on randomized projections. It consists of two alternating types of layers:
- Localized Random Projection Ensemble (LRPE) Layers: Instead of dense random matrices, LaRP uses banded Toeplitz matrices. This choice is crucial because it introduces sparsity and "local" connectivity, which speeds up matrix operations significantly. Each kernel within these matrices is randomly sampled from a uniform distribution $[a, b]$.
- Nonlinearity (NONL) Layers: These layers consist of two steps:
- Absolute Value Rectification (AVR): A non-saturating nonlinearity ($|x|$) that helps the model learn complex projections without the vanishing gradient issues of older activation functions.
- Sliding-Window Median Regularization (SMR): A $3 \times 3$ median filter that enforces spatial consistency and makes the model more robust to noise or uncertainties in the data.
Unlike deep learning models where every weight is learned, LaRP only trains the upper and lower bounds ($a$ and $b$) of the uniform distributions used to generate the random kernels. This is done using iterative scaled conjugate gradient optimization.
Datasets
The framework was evaluated on two classic computer vision benchmarks:
- MNIST: The standard database of 70,000 handwritten digits.
- COIL-100: A dataset containing 100 different objects filmed at various angles (36 views per object for training, the rest for testing).
Key Insights and Ideas
- Separation of Concerns: By modeling linear kernels and nonlinearities in separate, alternating layers, the framework can capture more complex discriminative features than a single-shot random projection.
- Efficiency through Sparsity: The use of banded Toeplitz matrices isn't just a mathematical convenience; it allows for "localized" features, similar to how convolutional layers work in CNNs, but with the computational benefits of random projections.
- Compactness is King: The most striking insight is that LaRP outperforms existing methods while using a fraction of the features. While competitors often use $2^{12}$ (4,096) or $2^{15}$ (32,768) features, LaRP achieves better results with just $2^{10}$ (1,024) features.
- Spatial Regularization: Incorporating a median filter (SMR) directly into the feature mapping process helps preserve information while smoothing out noise, a step often overlooked in pure kernel approximation papers.
Key Results
The LaRP framework demonstrated a clear advantage over state-of-the-art methods like Fastfood, Random Kitchen Sinks (RKS), and Tensor Sketching (TS):
- MNIST: LaRP achieved a test error of 1.30%, outperforming the best competitor (CM TS at 1.44%) despite using 32 times fewer features.
- COIL-100: The results here were even more dramatic. LaRP reached a test error of 0.36%, whereas the next best method (CM TS) sat at 3.96%.
- Dimensionality Reduction: The authors proved that you don't need "big" feature maps to get "big" results; a well-structured, layered approach allows for much more compact and discriminative data representations.
Limitations and Future Work
While the results are impressive, the paper notes a few areas for further exploration:
- Inter-kernel Information: The current model treats kernels somewhat independently; the authors suggest investigating how information flows between kernels to further refine the feature maps.
- Task Generalization: The study focused on object classification. Future work will look at applying LaRP to other domains like image saliency and semantic segmentation.
- Hyperparameter Sensitivity: While training the distribution bounds $[a, b]$ is efficient, the paper doesn't deeply explore how sensitive the model is to the initial number of layers or the specific window size of the median filter beyond the $3 \times 3$ default.
Summary updated