The Uniformly Rotated Mondrian Kernel
This work addresses the need for rotation-invariant kernels in kernel machines for large-scale problems, but it is incremental as it builds on the existing Mondrian kernel framework.
The authors tackled the problem of improving the Mondrian kernel's invariance under rotations by applying a uniform random rotation to the input space before the Mondrian process, resulting in a closed-form expression for the approximated isotropic kernel and a uniform convergence rate. They demonstrated improved performance over the Mondrian kernel on a debiased dataset, though specific numerical gains were not detailed in the abstract.
Random feature maps are used to decrease the computational cost of kernel machines in large-scale problems. The Mondrian kernel is one such example of a fast random feature approximation of the Laplace kernel, generated by a computationally efficient hierarchical random partition of the input space known as the Mondrian process. In this work, we study a variation of this random feature map by applying a uniform random rotation to the input space before running the Mondrian process to approximate a kernel that is invariant under rotations. We obtain a closed-form expression for the isotropic kernel that is approximated, as well as a uniform convergence rate of the uniformly rotated Mondrian kernel to this limit. To this end, we utilize techniques from the theory of stationary random tessellations in stochastic geometry and prove a new result on the geometry of the typical cell of the superposition of uniformly rotated Mondrian tessellations. Finally, we test the empirical performance of this random feature map on both synthetic and real-world datasets, demonstrating its improved performance over the Mondrian kernel on a dataset that is debiased from the standard coordinate axes.