Feasibility Based Large Margin Nearest Neighbor Metric Learning
This work addresses a specific bottleneck in metric learning for kNN classification, offering an incremental improvement over existing methods.
The paper tackled the issue of LMNN's dependence on pre-selected target neighbors by introducing a feasibility measure and a weighting scheme to enhance its optimization, resulting in improved accuracy on synthetic and real datasets compared to regular LMNN.
Large margin nearest neighbor (LMNN) is a metric learner which optimizes the performance of the popular $k$NN classifier. However, its resulting metric relies on pre-selected target neighbors. In this paper, we address the feasibility of LMNN's optimization constraints regarding these target points, and introduce a mathematical measure to evaluate the size of the feasible region of the optimization problem. We enhance the optimization framework of LMNN by a weighting scheme which prefers data triplets which yield a larger feasible region. This increases the chances to obtain a good metric as the solution of LMNN's problem. We evaluate the performance of the resulting feasibility-based LMNN algorithm using synthetic and real datasets. The empirical results show an improved accuracy for different types of datasets in comparison to regular LMNN.