Two dimensional Large Margin Nearest Neighbor for Matrix Classification

Kun Song, Feiping Nie, Junwei HanIJCAI 2017 · DOI

Introduction

The $k$-nearest neighbor (KNN) classifier is a fundamental tool in machine learning, yet its efficacy is entirely dependent on the distance metric employed. While Large Margin Nearest Neighbor (LMNN) is a standard for learning these metrics, it is traditionally designed for vector data. When applied to matrix-structured data, such as images, researchers typically "vectorize" the input. For a $64 \times 64$ pixel image, this results in a 4,096-dimensional vector, leading to two significant issues: the destruction of spatial relationships between rows and columns, and the "curse of dimensionality," where millions of parameters increase computational costs and the risk of overfitting.

To address these challenges, the authors introduce 2DLMNN (Two-dimensional Large Margin Nearest Neighbor), a metric learning approach that operates directly on matrix data. By preserving the inherent grid structure, 2DLMNN offers improved accuracy and significant computational speedups.

The 2DLMNN Framework

Instead of learning a single, massive Mahalanobis matrix, 2DLMNN learns two smaller projection matrices: a left projection matrix ($U$) to capture row-wise information and a right projection matrix ($V$) for column-wise information. This bilateral projection ($U^T XV$) ensures that the spatial integrity of the data is maintained throughout the learning process.

The model's objective function balances two goals:

  1. Pull: Minimizing the distance between a sample and its "target neighbors" of the same class.
  2. Push: Penalizing "imposters" from different classes that enter the local neighborhood, thereby establishing a large margin of separation.

Optimization and Convergence

Because solving for $U$ and $V$ simultaneously is complex, the authors utilize an alternating iterative framework. By fixing one matrix and solving for the other using sub-gradient descent, the algorithm monotonically decreases the objective function. As shown in the experimental results, this process typically converges rapidly.

Convergence of the 2DLMNN objective function across various datasets and dimensions, demonstrating rapid stabilization within 10 iterations.

Experimental Evaluation

The performance of 2DLMNN was evaluated across six diverse image datasets, including face recognition (UMIST, AR, Extended Yale-B), handwritten digits (USPS), pollen grains (POLLEN), and rotated objects (Coil-100).

Key Results

  • Superior Accuracy: 2DLMNN consistently outperformed 1D-LMNN and other baselines. For instance, on the Coil-100 dataset, it achieved 98.89% accuracy compared to 94.63% for the 1D version.
  • Parameter Efficiency: For a $64 \times 64$ image, 2DLMNN requires only 8,192 parameters, whereas a 1D method requires approximately 16.7 million. This reduction is the primary reason for the model's robustness against overfitting.
  • Effective Feature Reduction: When used for dimensionality reduction, 2DLMNN proved superior to the common two-step "2DLDA + 1DLMNN" pipeline, indicating that learning the projection and the metric simultaneously is more effective.
Comparison of classification accuracy between 2DLMNN and the 2DLDA+1DLMNN pipeline across different datasets as a function of feature dimension.

Conclusion

2DLMNN represents a significant advancement in metric learning for matrix data. By avoiding vectorization, it preserves spatial correlations and drastically reduces the parameter space, leading to faster training and higher classification accuracy. While the method is sensitive to initialization—often mitigated using 2DPCA—and requires hyperparameter tuning for the "pull/push" balance, it provides a robust foundation for future extensions into higher-order tensor data.

Summary updated

BibTeX
@inproceedings{song2017two,
  author = {Kun Song and Feiping Nie and Junwei Han},
  title = {{Two dimensional Large Margin Nearest Neighbor for Matrix Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/383},
}
Figure