Threshold Auto-Tuning Metric Learning

摘要

It has been reported repeatedly that discriminative learning of distancemetric boosts the pattern recognition performance. A weak point of ITML-basedmethods is that the distance threshold for similarity/dissimilarity constraintsmust be determined manually and it is sensitive to generalization performance,although the ITML-based methods enjoy an advantage that the Bregman projectionframework can be applied for optimization of distance metric. In this paper, wepresent a new formulation of metric learning algorithm in which the distancethreshold is optimized together. Since the optimization is still in the Bregmanprojection framework, the Dykstra algorithm can be applied for optimization. Anon-linear equation has to be solved to project the solution onto a half-spacein each iteration. Na"{i}ve method takes $O(LMn^{3})$ computational time tosolve the nonlinear equation. In this study, an efficient technique that cansolve the nonlinear equation in $O(Mn^{3})$ has been discovered. We have provedthat the root exists and is unique. We empirically show that the accuracy ofpattern recognition for the proposed metric learning algorithm is comparable tothe existing metric learning methods, yet the distance threshold isautomatically tuned for the proposed metric learning algorithm.