  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.
