Abstract
The approximation of nonlinear kernels via linear feature maps has recently gained interest due to their applications in reducing the training and testing time of kernel-based learning algorithms. Current random projection methods avoid the curse of dimensionality by embedding the nonlinear feature space into a low dimensional Euclidean space to create nonlinear kernels. We introduce a Layered Random Projection (LaRP) framework, where we model the linear kernels and nonlinearity separately for increased training efficiency. The proposed LaRP framework was assessed using the MNIST hand-written digits database and the COIL-100 object database, and showed notable improvement in object classification performance relative to other state-of-the-art random projection methods.
Introduction
Kernel methods are fundamental to machine learning, enabling the learning of complex, nonlinear patterns by implicitly mapping data into high-dimensional feature spaces. However, these methods face significant computational challenges: the "Curse of Dimensionality," where explicit high-dimensional operations are prohibitive, and the "Curse of Support," where the number of support vectors grows with the dataset size, slowing down inference.
While existing random feature map techniques attempt to mitigate these issues by embedding data into lower-dimensional Euclidean spaces, they often require a massive number of random features to maintain accuracy. The Layered Random Projection (LaRP) framework addresses this by separately modeling linear kernels and nonlinearities, allowing for a more efficient and compact representation.
Methods
The LaRP framework adopts an architecture similar to a neural network but utilizes randomized projections instead of fully learned weights. It consists of alternating layers designed to capture discriminative features efficiently.
Localized Random Projection Ensemble (LRPE) Layers
Instead of dense random matrices, LaRP employs banded Toeplitz matrices. This choice introduces sparsity and "local" connectivity, significantly accelerating matrix operations. Each kernel within these matrices is randomly sampled from a uniform distribution $[a, b]$.
Nonlinearity (NONL) Layers
The NONL layers involve two primary components:
- Absolute Value Rectification (AVR): A non-saturating nonlinearity ($|x|$) that avoids vanishing gradient issues.
- Sliding-Window Median Regularization (SMR): A $3 \times 3$ median filter that enforces spatial consistency and enhances robustness to noise.
Unlike standard deep learning, LaRP only optimizes the upper and lower bounds ($a$ and $b$) of the uniform distributions using iterative scaled conjugate gradient optimization, rather than training every individual weight.
Results and Discussion
The framework was evaluated on the MNIST handwritten digits database and the COIL-100 object database. The primary metric for comparison was the test error rate against other state-of-the-art random projection methods, including Fastfood, Random Kitchen Sinks (RKS), and Tensor Sketching (TS).
As shown in the results, LaRP significantly outperforms competing methods while using a much smaller feature space. On MNIST, LaRP achieved a test error of 1.30%, surpassing CM TS (1.44%) despite using 32 times fewer features ($2^{10}$ vs $2^{15}$). The performance gap was even more pronounced on the COIL-100 dataset, where LaRP achieved a 0.36% error rate compared to 3.96% for the next best method.
These results demonstrate that a structured, layered approach to random projections can yield highly compact and discriminative data representations, effectively overcoming the limitations of single-shot projection methods.
Conclusion
The LaRP framework provides a novel way to approximate nonlinear kernels by decomposing the process into alternating linear and nonlinear layers. By leveraging sparsity through banded matrices and spatial regularization via median filtering, LaRP achieves state-of-the-art accuracy with significantly reduced dimensionality. Future work will explore inter-kernel information flow and the application of LaRP to broader computer vision tasks such as semantic segmentation.
Summary updated