Abstract
This paper proposes a novel methodology for optimizing distance metrics in machine learning models by determining an optimal Mahalanobis matrix. By leveraging the Delta Test, a nonparametric noise estimator, as an objective function for a Genetic Algorithm, the authors identify transformations that minimize noise variance in the input space. The approach is evaluated on the Stereopsis regression problem and the Santa Fe laser time-series benchmark. Results demonstrate significant improvements in predictive accuracy, particularly when projecting high-dimensional data into lower-dimensional manifolds.
Introduction
In distance-based machine learning models, such as $k$-Nearest Neighbors ($k$-NN), the "curse of dimensionality" presents a significant challenge. Irrelevant or highly correlated input variables can introduce noise that obscures meaningful patterns, leading to poor generalization. While standard scaling techniques ensure variables occupy similar ranges, they often fail to account for complex inter-variable relationships. This paper addresses the problem by optimizing a Mahalanobis transformation matrix to warp or project the input space, ensuring that the distance between points reflects their true functional relationship to the output.
Methodology
The Mahalanobis Matrix
Rather than relying on standard Euclidean distance, the authors utilize the Mahalanobis distance, defined by a matrix $M$. This matrix can be diagonal, performing simple variable scaling, or factorized into a non-square matrix $S$ to project data into a lower-dimensional subspace. This flexibility allows the model to perform automatic variable selection and dimensionality reduction simultaneously.
Nonparametric Noise Estimation: The Delta Test
A key innovation of this work is the use of the Delta Test as the optimization objective. The Delta Test estimates the variance of noise in a dataset without requiring the construction of a predictive model. It operates on the principle that if two input points are sufficiently close, their outputs should also be close; any residual difference as the input distance approaches zero is attributed to noise.
Optimization Workflow
The researchers employ a Genetic Algorithm (GA) to search for the Mahalanobis matrix $M$ that minimizes the noise estimate provided by the Delta Test. Once the optimal transformation is identified, the data is projected, and a standard $k$-NN regressor is applied for final predictions.
Experimental Results
Stereopsis Regression Problem
The method was first tested on a 4-variable stereopsis dataset. The baseline $k$-NN model achieved a Normalized Mean Squared Error (NMSE) of 0.16. By optimizing a 1D projection matrix, the researchers uncovered a clear underlying manifold, reducing the NMSE to 0.01—a 16-fold improvement.
Santa Fe Laser Benchmark
The approach was further validated using the Santa Fe Laser dataset (SantaFeA), a chaotic time-series benchmark. Using a 12-dimensional window of past values, the optimized 5D projection reduced the NMSE from a baseline of 0.088 to 0.026.
Discussion and Conclusion
The study demonstrates that using noise estimation as a "compass" for input space transformation is highly effective. While optimizing full projection matrices is computationally more demanding than simple scaling, the gains in accuracy are substantial. Future work will focus on more efficient optimization algorithms to handle higher-dimensional datasets and exploring the applicability of this Mahalanobis optimization to other model architectures like Support Vector Machines.
Summary updated