Metric learning via perturbing hard-to-classify instances

Constraint selection is an effective means to alleviate the problem of a massive amount of constraints in metric learning. However, it is difficult to find and deal with all association constraints with the same hard-to-classify instance (i.e., an instance surrounded by dissimilar instances), negatively affecting metric learning algorithms. To address this problem, we propose a new metric learning algorithm from the perspective of selecting instances, Metric Learning via Perturbing of Hard-to-classify Instances (ML-PHI), which directly perturbs the hard-to-classify instances to reduce over-fitting for the hard-to-classify instances. ML-PHI perturbs hard-to-classify instances to be closer to similar instances while keeping the positions of the remaining instances as constant as possible. As a result, the negative impacts of hard-to-classify instances are effectively reduced. We have conducted extensive experiments on real data sets, and the results show that ML-PHI is effective and outperforms state-of-the-art methods.