Distance Metric Learning through Minimization of the Free Energy

The success of many machine learning and pattern recognition tasks relies on the choice of an appropriate distance metric, that will be effective in capturing differences between the data. To date, there have been several approaches that attempt to learn distance metrics directly from the input data. Recent works have reported new and more sophisticated methods for learning these distance functions. However, the correct metric choice is problem specific and may dictate the success or failure of the learning algorithm [1]. Distance metric learning consists in choosing the distance metric using information contained in the training data. The resulting distance metrics are widely used to improve performance of metric-based methods, such as nearest neighbors classification [2] or k-means clustering [3]. Depending on the problem, appropriate distance metrics can achieve substantial improvements over the standard Euclidean distance metric [4, 5]. With this in mind distance metric learning plays a crucial role in many pattern recognition tasks, including classification [5, 1], regression [6], clustering [4, 7, 8], feature selection [9, 10], and ranking [11].

Distance metric learning methods can be divided into three categories: supervised, semi-supervised, and unsupervised. Supervised methods for classification aim to ensure that patterns belonging to the same class are close to each other, and those from different classes are farther apart [5, 12]. Semi-supervised methods for clustering use the information to form pairwise similarity or dissimilarity constraints [7, 13], and unsupervised methods learn a distance metric that preserves distance relations between most of the patterns for unsupervised dimensionality reduction [14]. In the supervised context, a popular class of distance metrics is the Mahalanobis distance (see Section 2). The distance metric generalizes the standard Euclidean distance by admitting arbitrary linear scalings and rotations. More precisely, learning the distance metric is equivalent to finding an optimal linear transformation that best serves the classification purpose.

While distance metric learning has achieved considerable success in many learning tasks, there remain some challenges to be addressed. For example, the learning process should be flexible enough to support a variety of constraints realized across distinct problem domains and learning paradigms. Distance metric learning approaches based on convex optimizations are formulated under specific constraints, i.e., the matrix must be positive semidefinite, which are unable to generalize well for different tasks. Another challenge is the ability to solve complex constraints, so that the learned distance metric generalizes well to unseen test data. The issue typically arises in distance metric learning methods that take non-convex objective functions with spurious local minima, such as the stochastic neighbors in neighborhood component analysis (NCA) [15] which uses gradient descent. This paper focuses on providing a solution to these obstacles.

For distance metrics learned using complex constraints and non-convex objective functions, an important question entails what is the best distance metric that can be achieved for a given data set? The problem is reminiscent of a typical situation in statistical physics, which allows us to apply its concepts for solving the distance metric learning problem. Rather than performing a gradient-driven iterative search, the basic idea involves applying random transformations on the metric space, i.e., scalings and rotations, in search of a distance metric that minimizes the objective function. This provides a natural way to learn the desired distance metric. The learning process can be intuitively seen as stretching the metric space until some heuristic is satisfied, e.g., similar patterns are closer together and dissimilar patterns are farther apart (see Fig. 1).

In this paper we introduce a novel approach for learning the distance metric. Our approach differs from other distance metric learning methods in the following ways. We formulate this task as a typical problem in statistical physics. Particularly, we treat the distance metric learning problem as finding the ground state of a complex physical system. The heuristic is identified with the energy of the system, which we minimize by Metropolis Monte Carlo. This allows one to learn the distance metric for non-trivial constraints and non-convex objective functions with spurious local minima. As a case study, we consider stochastic nearest neighbors in NCA, but the same approach can be used for other heuristics. Our numerical experiments reveal that the resulting distance metric leads to significant improvements in accuracy for nearest neighbors classification. Several state-of-the-art distance metric learning methods are used for fair comparison.

The paper is organized as follows. Section 2 briefly reviews the existing literature on distance metric learning. Section 3 describes the proposed method. Section 4 demonstrates numerical experiments on nearest neighbors classification. Section 5 discusses important aspects of the proposed distance metric learning method. Section 6 draws the conclusions.

Distance metric learning consists in choosing a suitable distance measure from information in the training data. A popular class of distance metrics is the Mahalanobis distance:

due to its wide use in many application domains and because it provides a flexible way of learning an appropriate distance metric for complex problems [16, 17]. $M$ is a symmetric positive semidefinite matrix that can be factorized into $M=AA^{T}$, given a linear transformation $A$. The distance $d_{M}$ between patterns $u$ and $v$ is equivalent to the Euclidean distance after performing the linear transformation:

The distance metric generalizes the standard Euclidean distance by admitting arbitrary linear scalings and rotations (see Fig. 1), where cross terms (or product between different components) can appear in distance computations through the off-diagonal elements of $M$. The current problem is to learn the linear transformation $u\rightarrow Au$, or its quadratic form $M=A^{T}A$, that parametrizes the corresponding distance metric. While learning is unconstrained for linear transformations, for the quadratic form we must ensure that $M$ remains positive semidefinite. As a result, most of distance metric learning methods fall into three broad categories: eigenvalue methods based on second-order statistics, convex optimizations over the space of positive semidefinite matrices, and non-convex optimizations.

The classes of problems in pattern recognition have a close mathematical connection to those in statistical physics [29]. In relation with pattern recognition, statistical physics has paved the road for much of the research done in academia and industry, ranging from the revival of connectionism [30] to modern day deep learning [31]. Moreover, a parallel can be drawn between statistical physics - the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature, and distance metric learning - the search of an appropriate metric by which to measure distances between patterns. As a result, we can employ concepts from statistical physics to learn the distance metric.

The focus of this work is on distance metric learning methods that contain complex constraints and non-convex objective functions, which make them susceptible to getting stuck in spurious local minima rather than the global optimum. For example, the gradient descent used in NCA often converges to local solutions representing suboptimal distance metrics. To solve this issue, we formulate the task as a minimization of the free energy of a statistical system which is equivalent to the distance metric learning problem, under constraints on the distance metric. By analogy with statistical physics, we represent the set of distances between patterns as the constituents of a physical system, where the corresponding energy is given by the constraints or objective function. Since ground states and other low energy states are extremely rare among all possible states of a macroscopic system, we can expect that the methods from statistical physics used to find them are more than capable to search for the global optimum distance metric.

In this section, we describe some experiments to evaluate the performance of distance metric learning methods. As a case study, we consider the stochastic nearest neighbors in NCA (see Eq. (4)) for our method, but other non-convex heuristics can be used. The proposed method is compared to the standard Euclidean distance and state-of-the-art distance metric learning methods listed in Table 1, which includes those based on eigenvalue decomposition, convex optimization, and non-convex optimization. Comparisons are also made with Random Forest (RF) [35]. For our experiments we consider supervised learning for nearest neighbors classification.

To make fair comparisons, we consider the following configurations for the experiments. The numerical experiments are empirically tested in the context of nearest neighbors classification, where the number of neighbors is varied between 1 and 40, and the best classification accuracy is chosen. RF is trained with 100 decision trees. We use the source codes of the distance metric learning methods supplied by the authors, and tune their parameters to get the best results. DMLFE uses an annealing procedure which starts with $T=0.1$ and successively reduces the temperature by a multiplicative factor of $\alpha=0.9$. Monte Carlo steps are repeated until convergence or a maximum number of steps is reached.

We compare the distance metric learning methods on 36 data sets from UCI [36, 37] and LIBSVM [38] machine learning repositories. The information of these data sets is summarized in Table 2. The classification accuracies are obtained by averaging over five runs of two-fold cross-validation. Divisions of the data sets for training and testing are made randomly. The features of the patterns are normalized into the interval $[0,1]$, which significantly improves performance of many standard distance metric learning methods.

Table 3 shows the average classification accuracies obtained by the competing methods. Fig. 4 further illustrates side by side comparisons of the results in Table 3. Since many points lie below the diagonal line, we can conclude that DMLFE presents a clear advantage over other approaches to nearest neighbors classification. Particularly, we find that our methods beats the standard Euclidean distance and is competitive with RF. The approach also seems to widely outperform distance metric learning methods based on eigenvalue decomposition and convex optimization. Lastly, we observe that the Monte Carlo annealing procedure obtains better distance metrics than gradient descent for stochastic neighbors in NCA. The data sets where our method performs poorly can be explained by one of two causes: 1) convergence to a local minimum due to fast annealing, or 2) insufficient Monte Carlo steps. Another plausible reason is that the free energy landscape is not represented by a complex surface with numerous local minima, which occurs in many situations in statistical physics such as spin glasses, but rather by a well-behaved surface with pronounced global minimum, where even gradient-based searches can find the optimal solution.

We rank the methods based on their classification accuracy on each data set, e.g., a rank of one is assigned to the method that has the highest accuracy, a rank of two to the method obtaining the second higher accuracy, and so on. The average ranks and other statistics of the competing methods are listed in the last rows of Table 3. We find that our approach achieves better results than NCA because the annealing procedure can overcome spurious local minima in which the gradient descent gets stuck. Our approach also significantly outperforms all other distance metric learning methods and has comparable classification performance to random forest (RF), which is often regarded as one of the best classifiers [39].

To detect whether there are significant differences among the results, we follow Demsar [40] for statistical comparisons of classifiers over many data sets. In each case we test the null-hypothesis that the distance metric learning methods obtain the same results on average. We start with the Wilcoxon signed rank [41] and Friedman [42] tests. The p-value for the Wilcoxon test is less than the confidence level of $\alpha=0.05$ for all competing methods except RF, so we can reject the null-hypothesis as shown in Table 4. Similar conclusions can be made about the Friedman test where the p-value is $10^{-23}$. Then we proceed to the Bonferroni-Dunn [43] and Nemenyi [44] post-hoc tests to determine which distance metric learning methods perform the same or significantly different from our proposed method. The post-hoc tests can identify significant differences between the control method, which we take to be DMLFE, and other competing methods by computing a critical difference. Two distance metric learning methods are deemed significantly different if their average ranks differ by at least the critical difference [45]:

where $q_{\alpha}$ is the critical value, $n_{c}=13$ and $n_{t}=36$ are the number of competing methods and number of data sets, respectively. We consider the Nemenyi and Bonferroni-Dunn tests at a confidence level of $\alpha=0.05$, with critical differences of $3.04$ and $2.64$, respectively. Fig. 5 graphically represents the significant differences among the performances of the different distance metric learning methods. Any distance metric learning method outside the marked area is deemed significantly different from the control method, or DMLFE. We find that the post-hoc tests reject the null-hypothesis for all competing methods except DMLMJ, LMNN, and RF as shown in Table. 4. The statistical results allow us to conclude that our method significantly outperforms competing distance metric learning methods, and its performance is on par with RF.

In this section we outline some important factors which lead to the preferred utilization of DMLFE. We start by considering the choice of temperature, which plays a crucial role in the performance of our proposed distance metric learning method. An annealing procedure will usually guarantee proper convergence to the global minimum, while quenching can get stuck in spurious local minima. However, there are many situations where quenching might provide “good enough” results and avoid the larger computational costs of annealing. For example, some problems in physics contain many degenerate ground states which are easy to obtain, such as spin glasses, while others are composed of one unique minimum that can be found even with gradient-based searches. One can then imagine that similar situations might occur when learning the distance metric.

To analyze the temperature effects we conduct experiments on several of the considered data sets. Fig. 6 plots evolution of the energy (or objective function) when using the annealing procedure or multiple quenching with random initialization of the distance matrix. It follows that annealing often results in better solutions (see Figs. 6(b-e)), achieving states that are closer to the ground state in energy, but at the cost of many more Monte Carlo Steps. However, there are situations where multiple quenching can achieve similar or even better results than annealing but with much fewer steps (see Fig. 6(a)). This resembles the case of a frustrated system with nearly degenerate ground states, as mentioned above. While the choice of an annealing procedure with decaying temperature ensures finding the optimal solution, one may still opt to perform several runs with the simpler and faster quenching for different initializations, and then retain only the result with the lowest obtained energy.

We also analyze the performance of competing distance metric learning methods with the number of nearest neighbors. Fig. 7 illustrates the classification accuracy as we vary the methods from one to forty nearest neighbors in three of the data sets. We find that our method significantly outperforms NCA for all neighborhoods, which reaffirms our previous conclusion that the Monte Carlo annealing procedure achieves better solutions than gradient descent for stochastic nearest neighbors. In Fig. 7(a), DMLFE achieves better performance than state-of-the-art methods for all neighborhoods, while only for the best performing number of nearest neighbors in Fig. 7(b). Interestingly, in Fig. 7(c) we find that our method achieves better classification accuracy using much fewer nearest neighbors than competing methods based on eigenvalue decomposition and convex optimization. Table 5 reveals similar findings based on statistics over all data sets of the number of nearest neighbors that results in best classification. This suggests that the proposed method with stochastic nearest neighbors can achieve better classification with smaller computational cost than competing distance metric learning methods.

In this paper we developed a novel distance metric learning method. We showed that learning the distance metric can be formulated as a typical problem in statistical physics: distances represent constituents of a physical system and the corresponding energy is given by the leave-one-out classification error in Eq. (4). Then we demonstrated that this problem is equivalent to minimizing the free energy of a complex physical system. We proposed an approach to find the ground state using Metropolis Monte Carlo simulations. This allows one to learn the distance metric for non-trivial constraints and non-convex objective functions with spurious local minima. As a case study, we considered stochastic neighbors in NCA, but the same approach can be used for other heuristics. The experimental results on synthetic and real-world data sets demonstrate that the proposed method significantly outperforms other state-of-the-art distance metric learning methods for nearest neighbors classification. Future works should be directed towards the construction of more complex objective functions targeted for specific applications.