Kernel Geometric Mean Metric Learning

Abstract

Geometric mean metric learning (GMML) algorithm is a novel metric learning approach proposed recently. It has many advantages such as unconstrained convex objective function, closed form solution, faster computational speed, and interpretability over other existing metric learning technologies. However, addressing the nonlinear problem is not effective enough. The kernel method is an effective method to solve nonlinear problems. Therefore, a kernel geometric mean metric learning (KGMML) algorithm is proposed. The basic idea is to transform the input space into a high-dimensional feature space through nonlinear transformation, and use the integral representation of the weighted geometric mean and the Woodbury matrix identity in new feature space to generalize the analytical solution obtained in the GMML algorithm as a form represented by a kernel matrix, and then the KGMML algorithm is obtained through operations. Experimental results on 15 datasets show that the proposed algorithm can effectively improve the accuracy of the GMML algorithm and other metric algorithms.

1. Introduction

It is well known that the distance measure is one of the most commonly used measures to describe the similarity between samples. At present, various distance metrics have been proposed, such as the Euclidean distance and Mahalanobis distance. However, these distance metric expressions are fixed, i.e., there are non-adjustable parameters, which result in varying degrees of effectiveness in dealing with various problems. Thus, an effective distance metric is proposed by constructing learning from training samples. From the definition of the distance metric, it follows that any binary function $d\left(x,x^{\prime }\right)$ defined in the feature space is called a distance function, provided that the four conditions of symmetry, self-similarity, non-negativity, and trigonometric inequality are satisfied simultaneously. Thus, any binary function

$$d_M\left(x,x^{\prime }\right)={\left(x-x^{\prime }\right)}^{\mathrm{T}}M\left(x-x^{\prime }\right),$$

(1)

is a distance function determined by any symmetric positive definite (SPD) matrix M, where $x,x^{\prime }$ are two samples, and usually M is called a metric matrix. The purpose of metric learning is to use training samples to learn a metric matrix M such that the resulting distance function $d_M\left(x,x^{\prime }\right)$ can improve the performance of the learning algorithm or satisfy some application requirements. Thus, metric learning has wide applications in many fields, such as pattern recognition [1,2], data mining [3,4,5], information security [6,7], bioinformatics [8,9], and medical diagnosis [10,11,12].

Because of the wide application space, metric learning techniques have received a lot of attention, and many excellent algorithms have been proposed. Xing [13] first proposed a metric learning algorithm. The main idea of the algorithm is to learn a metric matrix so that the distance between similar pairs of samples is small and the distance between dissimilar pairs of samples is large. The algorithm can make the distribution of similar pairs of samples more compact in the new metric space, while the distribution of dissimilar pairs is more discrete. The proposal of this algorithm marked the real development of metric learning, and many subsequent research works were inspired by this algorithm. Davis [14] proposed an information theoretic metric learning algorithm. The basic idea of the algorithm is to assume the existence of a priority metric matrix $M_0$, while ensuring that the distance between similar pairs of samples is less than a threshold and the distance between dissimilar pairs of samples is greater than a threshold. By minimizing the relative entropy between the multivariate Gaussian distributions corresponding to M and $M_0$, Wang [15] proposed an information geometry metric learning algorithm. The basic idea of the algorithm is to use the category labeling information of the training samples to construct a kernel matrix that can reflect the desired distance between samples. Construct an actual kernel matrix describing the realistic distance relationship between the samples using the eigenvectors of the samples as well as the metric matrix M. The metric matrix M is then solved by minimizing the distance between these two kernel matrices. Weinberger [16] proposed a metric learning algorithm based on the maximum margin. The basic idea is to define an interval function between similar samples of each sample and other classes of samples. The metric matrix is then solved by minimizing the distance between similar pairs of samples and maximizing the defined interval.

Geometric mean metric learning algorithm was proposed by Pourya [17] in 2016. The essence of most metric learning algorithms is to minimize the distance between similar pairs of samples rather than maximize the distance between similar pairs of samples. Therefore, the sign of the term corresponding to the dissimilar pair of samples in the objective function is usually negative, while the strategy of the geometric mean metric learning model is to use the inverse matrix of the metric matrix M to represent the distance between dissimilar pairs of samples. The advantage of this approach is that the sign of the item corresponding to the dissimilar pair of samples in the objective function becomes positive, which reduces the difficulty of solving the model. Its objective function is as follows:

$$\begin{array}{cc}\hfill & \underset{M>0}{min}\sum _{\left(x_{1i},x_{2i}\right)\in D^{+}}{d}_M\left(x_{1i},x_{2i}\right)+\sum _{\left({\overline{x}}_{1j},{\overline{x}}_{2j}\right)\in D^{-}}{d}_{M^{-1}}\left({\overline{x}}_{1j},{\overline{x}}_{2j}\right),\hfill \end{array}$$

(2)

where the similar pair sample set $D^{+}$ and the dissimilar pair sample set $D^{-}$ can be expressed as

$$\left\{\begin{array}{c}{D}^{+}=\left\{\left(x_{1i},x_{2i}\right)\mid x_{1i},x_{2i}\in R^d\mathrm{are}\mathrm{in}\mathrm{the}\mathrm{same}\mathrm{class},i=1,2,\dots ,n\right\},\hfill \\ D^{-}=\left\{\left({\overline{x}}_{1j},{\overline{x}}_{2j}\right)\mid {\overline{x}}_{1j},{\overline{x}}_{2j}\in R^d\mathrm{are}\mathrm{in}\mathrm{different}\mathrm{class},j=1,2,\dots ,m\right\}.\hfill \end{array}\right.$$

(3)

Although the GMML algorithm has some advantages, such as unconstrained convex objective function, closed-form solution and interpretability, and faster calculation speed [18], it is actually a linear learning method and does not work well to address non-linear problems. Because kernel methods are the key technology for addressing nonlinear problems, kernel algorithms [19,20,21,22,23] have been proposed. In view of this, kernel geometric mean metric learning algorithm is proposed. The closed-form solution of GMML algorithm in the high-dimensional feature space is rephrased. Then, the solution is generalized as a form of the kernel matrix by using the integral representation of the weighted geometric mean and the Woodbury matrix identity, leading to the KGMML algorithm. It retains the advantages of the GMML algorithm, while effectively addressing nonlinear problems.

The structure of this paper is organized as follows: In Section 2, some lemmas of weighted geometric mean and Woodbury matrix identity are formulated. Then, in Section 3, the optimization problem is discussed, then the extension to the weighted geometric mean and solution are discussed. The setup of the experiment, the analysis of parameter sensitivity, and experimental results are given in Section 4. Finally, our conclusions are summarized in Section 5.

2. Preliminaries

Lemma 1

([24]). For any $t\in (0,1)$, A is $n\times n$ positive definite, B is $n\times n$ Hermitian, and the following equation holds:

$$A{♯}_{t}B=\frac{2sin\left(\pi t\right)}{\pi }A{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}{\left((1-s)I+(1+s)B^{-1}A\right)}^{-1}ds,$$

which is the integral representation of the $A,B$ weighted geometric mean, where I is the identity matrix, and ${♯}_t$ represents the weighted geometric mean with weight t

Lemma 2

([25]). If A is a $n\times n$ invertible matrix corrected by $UCV$, where U is the $n\times k$ matrix, C is the $k\times k$ matrix, and V is the $k\times n$ matrix, then the Woodbury matrix identity is

$${(A+UCV)}^{-1}=A^{-1}-A^{-1}U{\left(C^{-1}+V{A}^{-1}U\right)}^{-1}V{A}^{-1}.$$

Lemma 3

([24]). For any $t\in (0,1)$, A is $n\times n$ positive definite, B is $n\times n$ Hermitian, and the following equation holds:

$$A{♯}_{t}B=A{\left(B^{-1}A\right)}^{-t}.$$

3. Main Results

3.1. Optimization Problem

The core of the kernel method is to transform the linearly inseparable point set in the low-dimensional space into the high-dimensional space through a nonlinear transformation $\Phi \left(·\right)$, making it linearly separable. In this process, it is not necessary to know the specific analytical expression of the nonlinear transformation, but only know the inner product $〈\Phi \left(x\right),\Phi \left(x^{\prime }\right)〉$ after the transformation of the two samples $x,x^{\prime }$, and $〈\Phi \left(x\right),\Phi \left(x^{\prime }\right)〉$ can be represented by a kernel function, i.e., $〈\Phi \left(x\right),\Phi \left(x^{\prime }\right)〉=k\left(x,x^{\prime }\right)$, where $k\left(x,x^{\prime }\right)$ is a kernel function. For ease of presentation, we first derive the model using $\Phi \left(·\right)$ and then replace it with the kernel function to obtain the final kernel geometric mean metric learning algorithm. Let $D_{\Phi }^{+}$ and $D_{\Phi }^{-}$ represent the similarity sample set $D^{+}$ and the non-similar pair sample set $D^{-}$ mapped to the point set in the high-dimensional space $\mathcal{F}$, that is

$$\left\{\begin{array}{c}{D}_{\Phi }^{+}=\left\{\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)\mid \Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\in \mathcal{F}\mathrm{are}\mathrm{in}\mathrm{the}\mathrm{same}\mathrm{class},i=1,2,\dots ,n\right\},\hfill \\ D_{\Phi }^{-}=\left\{\left(\Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\right)\mid \Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\in \mathcal{F}\mathrm{are}\mathrm{in}\mathrm{different}\mathrm{class},j=1,2,\dots ,m\right\}.\hfill \end{array}\right.$$

(4)

In high dimensional space, the objective function (2) can be written in the following form:

$$\begin{array}{cc}\hfill & \underset{M_{\Phi }>0}{min}\sum _{\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)\in D_{\Phi }^{+}}{d}_{M_{\Phi }}\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)+\sum _{\left(\Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\right)\in D_{\Phi }^{-}}{d}_{{M_{\Phi }}^{-1}}\left(\Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\right)\hfill \\ \hfill =& \underset{M_{\Phi }>0}{min}\sum _{\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)\in D_{\Phi }^{+}}{\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right)}^{\mathrm{T}}{M}_{\Phi }\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right)\hfill \\ \hfill & +\sum _{\left(\Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\right)\in D_{\Phi }^{-}}{\left(\Phi \left({\overline{x}}_{1j}\right)-\Phi \left({\overline{x}}_{2j}\right)\right)}^{\mathrm{T}}{M}_{\Phi }^{{}^{-1}}\left(\Phi \left({\overline{x}}_{1j}\right)-\Phi \left({\overline{x}}_{2j}\right)\right).\hfill \end{array}$$

(5)

where $d_{M_{\Phi }}\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)={\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right)}^{\mathrm{T}}{M}_{\Phi }\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right)$ represents the distance metric in the high dimensional space and $M_{\Phi }$ is the metric matrix.

Rewriting the distance uses traces, Equation (5) can be turned into the following optimization problem:

$$\begin{array}{cc}\hfill & \underset{M_{\Phi }>0}{min}\sum _{\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)\in D_{\Phi }^{+}}tr\left(M_{\Phi }\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right){\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right)}^{\mathrm{T}}\right)\hfill \\ \hfill & +\sum _{\left(\Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\right)\in D_{\Phi }^{-}}tr\left(M_{\Phi }^{{}^{-1}}\left(\Phi \left({\overline{x}}_{1j}\right)-\Phi \left({\overline{x}}_{2j}\right)\right){\left(\Phi \left({\overline{x}}_{1j}\right)-\Phi \left({\overline{x}}_{2j}\right)\right)}^{\mathrm{T}}\right)\hfill \\ \hfill =& \underset{M_{\Phi }>0}{min}tr\left(M_{\Phi }{S}_{\Phi }\right)+tr\left(M_{\Phi }^{{}^{-1}}{D}_{\Phi }\right)\hfill \\ \hfill \stackrel{△}{=}& \underset{M_{\Phi }>0}{min}h\left(M_{\Phi }\right),\hfill \end{array}$$

(6)

where $S_{\Phi }$, $D_{\Phi }$ are

$$\begin{array}{cc}\hfill S_{\Phi }& =\sum _{\left(\Phi \left(x_{1i}\right),\Phi \left(x_{2i}\right)\right)\in D_{\Phi }^{+}}\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right){\left(\Phi \left(x_{1i}\right)-\Phi \left(x_{2i}\right)\right)}^{\mathrm{T}},\hfill \\ \hfill D_{\Phi }& =\sum _{\left(\Phi \left({\overline{x}}_{1j}\right),\Phi \left({\overline{x}}_{2j}\right)\right)\in D_{\Phi }^{-}}\left(\Phi \left({\overline{x}}_{1j}\right)-\Phi \left({\overline{x}}_{2j}\right)\right){\left(\Phi \left({\overline{x}}_{1j}\right)-\Phi \left({\overline{x}}_{2j}\right)\right)}^{\mathrm{T}}.\hfill \end{array}$$

(7)

Differentiating $h\left(M_{\Phi }\right)$ with respect to $M_{\Phi }$ yields

$$\nabla h\left(M_{\Phi }\right)=S_{\Phi }-M_{\Phi }^{-1}{D}_{\Phi }{M}_{\Phi }^{-1}.$$

(8)

Then, $\nabla h\left(M\right)$ is set to 0, which implies that

$$M_{\Phi }{S}_{\Phi }{M}_{\Phi }=D_{\Phi },$$

(9)

and it is clear that the above equation is a Riccati equation. Since $S_{\Phi }$ and $D_{\Phi }$ are usually positive definite matrices, Equation (9) has a unique positive solution which is the midpoint of the geodesic joining ${S_{\Phi }}^{-1}$ to $D_{\Phi }$ [26], that is

$$M_{\Phi }={S_{\Phi }}^{-1}{♯}_{1/2}{D}_{\Phi }={S_{\Phi }}^{-1/2}{\left({S_{\Phi }}^{1/2}{D}_{\Phi }{S_{\Phi }}^{1/2}\right)}^{1/2}{S_{\Phi }}^{-1/2}.$$

(10)

3.2. Extension to Weighted Geometric Mean and Solution

To incorporate the weighted geometric mean, it is necessary to take into account the determination of weights for the objective function. When assigning linear weights for $S{{}_{\Phi }}^{-1}$ and $D_{\Phi }$, only the metric matrix $M_{\Phi }$ can be uniformly scaled by a constant factor. Consequently, it is illogical to assign linear weights to the two components in Equation (5). Nevertheless, by employing nonlinear weights derived from the SPD manifold Riemannian geometry, the weights can be transformed into trade-offs between the two terms. Thus, the Riemann distance ${\delta }_R$ is introduced, and the problem of finding the minimum value of $h\left(M_{\Phi }\right)$ is equivalent to solving the minimum value of the following optimization problem:

$$\underset{M_{\Phi }⪰0}{min}{\delta }_R^2\left(M_{\Phi },{S_{\Phi }}^{-1}\right)+{\delta }_R^2\left(M_{\Phi },D_{\Phi }\right),$$

(11)

where the Riemannian distance between SPD matrices X and Y is denoted by ${\delta }_R^2(X,Y)={∥log\left(Y^{-1/2}X{Y}^{-1/2}\right)∥}_F$, and ${∥.∥}_F$ is the Frobenius norm of a matrix. A linear parameter $t\in [0,1]$ is introduced to trade off the relationship of the two terms in the formula:

$$\underset{M_{\Phi }⪰0}{min}(1-t){\delta }_R^2\left(M_{\Phi },{S_{\Phi }}^{-1}\right)+t{\delta }_R^2\left(M_{\Phi },D_{\Phi }\right)\stackrel{△}{=}\underset{M_{\Phi }>0}{min}{h}_t\left(M_{\Phi }\right).$$

(12)

Because $h_t\left(M_{\Phi }\right)$ is still geodesically convex [17], Equation (12) has a unique positive solution, that is,

$$\begin{array}{c}\hfill M_{\Phi }={S_{\Phi }}^{-1}{♯}_t{D}_{\Phi }.\end{array}$$

(13)

Theorem 1.

The solution $M_{\Phi }={S_{\Phi }}^{-1}{♯}_t{D}_{\Phi }$ of the objective function (5) can be rewritten as

$$\begin{array}{c}\hfill M_{\Phi }=Q_{\Phi }{\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}{Q_{\Phi }}^{\mathrm{T}},\end{array}$$

where the kernel matrix $K_{PQ}={P_{\Phi }}^{\mathrm{T}}{Q}_{\Phi }=K_{P_1{Q}_1}-K_{P_1{Q}_2}-K_{P_2{Q}_1}+K_{P_2{Q}_2}$,

$$\begin{array}{cc}\hfill P_{\Phi }& =\left[\Phi \left(x_{11}\right)\Phi \left(x_{12}\right)\cdots \Phi \left(x_{1n}\right)\right]-\left[\Phi \left(x_{21}\right)\Phi \left(x_{22}\right)\cdots \Phi \left(x_{2n}\right)\right]\stackrel{△}{=}{P}_{\Phi 1}-P_{\Phi 2},\hfill \\ \hfill Q_{\Phi }& =\left[\Phi \left({\overline{x}}_{11}\right)\Phi \left({\overline{x}}_{12}\right)\cdots \Phi \left({\overline{x}}_{1m}\right)\right]-\left[\Phi \left({\overline{x}}_{21}\right)\Phi \left({\overline{x}}_{22}\right)\cdots \Phi \left({\overline{x}}_{2m}\right)\right]\stackrel{△}{=}{Q}_{\Phi 1}-Q_{\Phi 2},and\hfill \end{array}$$

$$\begin{array}{c}{K}_{P_1{Q}_1}={P_{\Phi 1}}^{\mathrm{T}}{Q}_{\Phi 1}=\left[\begin{array}{ccc}〈\Phi \left(x_{11}\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left(x_{11}\right),\Phi \left({\overline{x}}_{1m}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left(x_{1n}\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left(x_{1n}\right),\Phi \left({\overline{x}}_{1m}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left(x_{11},{\overline{x}}_{11}\right)& \cdots & k\left(x_{11},{\overline{x}}_{1m}\right)\\ ⋮& \ddots & ⋮\\ k\left(x_{1n},{\overline{x}}_{11}\right)& \cdots & k\left(x_{1n},{\overline{x}}_{1m}\right)\end{array}\right]\\ K_{P_1{Q}_2}={P_{\Phi 1}}^{\mathrm{T}}{Q}_{\Phi 2}=\left[\begin{array}{ccc}〈\Phi \left(x_{11}\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left(x_{11}\right),\Phi \left({\overline{x}}_{2m}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left(x_{1n}\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left(x_{1n}\right),\Phi \left({\overline{x}}_{2m}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left(x_{11},{\overline{x}}_{21}\right)& \cdots & k\left(x_{11},{\overline{x}}_{2m}\right)\\ ⋮& \ddots & ⋮\\ k\left(x_{1n},{\overline{x}}_{21}\right)& \cdots & k\left(x_{1n},{\overline{x}}_{2m}\right)\end{array}\right]\\ K_{P_2{Q}_1}={P_{\Phi 2}}^{\mathrm{T}}{Q}_{\Phi 1}=\left[\begin{array}{ccc}〈\Phi \left(x_{21}\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left(x_{21}\right),\Phi \left({\overline{x}}_{1m}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left(x_{2n}\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left(x_{2n}\right),\Phi \left({\overline{x}}_{1m}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left(x_{21},{\overline{x}}_{11}\right)& \cdots & k\left(x_{21},{\overline{x}}_{1m}\right)\\ ⋮& \ddots & ⋮\\ k\left(x_{2n},{\overline{x}}_{11}\right)& \cdots & k\left(x_{2n},{\overline{x}}_{1m}\right)\end{array}\right]\\ K_{P_2{Q}_2}={P_{\Phi 2}}^{\mathrm{T}}{Q}_{\Phi 2}=\left[\begin{array}{ccc}〈\Phi \left(x_{21}\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left(x_{21}\right),\Phi \left({\overline{x}}_{2m}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left(x_{2n}\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left(x_{2n}\right),\Phi \left({\overline{x}}_{2m}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left(x_{21},{\overline{x}}_{21}\right)& \cdots & k\left(x_{21},{\overline{x}}_{2m}\right)\\ ⋮& \ddots & ⋮\\ k\left(x_{2n},{\overline{x}}_{21}\right)& \cdots & k\left(x_{2n},{\overline{x}}_{2m}\right)\end{array}\right].\end{array}$$

Proof. 

According to Lemma 1,

$$\begin{array}{cc}\hfill M_{\Phi }& =S_{\Phi }^{-1}{♯}_t{D}_{\Phi }\hfill \\ \hfill & =\frac{2sin\left(\pi t\right)}{\pi }{S}_{\Phi }^{-1}{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}((1-s)I+(1+s)D_{\Phi }^{-1}{S}_{\Phi }^{-1}{)}^{-1}\mathrm{d}s\hfill \\ \hfill & =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}((1-s)S_{\Phi }+(1+s)D_{\Phi }^{-1}{)}^{-1}\mathrm{d}s\hfill \\ \hfill & =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}((1-s)S_{\Phi }+(1+s)D_{\Phi }^{-1}{)}^{-1}\mathrm{d}s.\hfill \end{array}$$

(14)

According to the definitions of $P_{\Phi }$ and $Q_{\Phi }$, $S_{\Phi }$ and $D_{\Phi }$ can be written as $S_{\Phi }=P_{\Phi }{P}_{\Phi }^{\mathrm{T}},D_{\Phi }=Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}$. Substituting them into Equation (14), it is clear that

$$\begin{array}{cc}\hfill M_{\Phi }& =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}((1-s)P_{\Phi }{P}_{\Phi }^{\mathrm{T}}+(1+s){\left(Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}\right)}^{-1}{)}^{-1}\mathrm{d}s.\hfill \end{array}$$

(15)

For convenience in the following discussion, we introduce the notation

$$G={\left(\left(1-s\right)P_{\Phi }{P}_{\Phi }^{\mathrm{T}}+\left(1+s\right){\left(Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}\right)}^{-1}\right)}^{-1}.$$

From Lemma 2, it follows that

$$\begin{array}{c}\hfill \begin{array}{c}G={(A+UCV)}^{-1}=A^{-1}-A^{-1}U{\left(C^{-1}+V{A}^{-1}U\right)}^{-1}V{A}^{-1},\hfill \end{array}\end{array}$$

(16)

where $A=\left(1+s\right){\left(Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}\right)}^{-1}$, $U=P_{\Phi }$, $C=(1-s)I$, $V=P_{\Phi }^{\mathrm{T}}$. Then, taking it into Equation (15), one has

$$\begin{array}{cc}\hfill M_{\Phi }& =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}[\frac{Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}}{1+s}-\frac{Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}}{1+s}·P_{\Phi }{\left(\frac{I^{-1}}{1-s}+P_{\Phi }^{\mathrm{T}}·\frac{Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}}{1+s}·P_{\Phi }\right)}^{-1}{P}_{\Phi }^{\mathrm{T}}\frac{Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}}{1+s}]\mathrm{d}s\hfill \\ \hfill & =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}[\frac{Q_{\Phi }{Q}_{\Phi }^{\mathrm{T}}}{1+s}-\frac{Q_{\Phi }}{1+s}·{K_{PQ}}^{\mathrm{T}}{\left(\frac{I^{-1}}{1-s}+\frac{K_{PQ}{K_{PQ}}^{\mathrm{T}}}{1+s}\right)}^{-1}\frac{K_{PQ}{Q_{\Phi }}^{\mathrm{T}}}{1+s}]\mathrm{d}s\hfill \\ \hfill & =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}{Q}_{\Phi }[\frac{I}{1+s}-\frac{{K_{PQ}}^{\mathrm{T}}}{1+s}{\left(\frac{I^{-1}}{1-s}+\frac{K_{PQ}{K_{PQ}}^{\mathrm{T}}}{1+s}\right)}^{-1}\frac{K_{PQ}}{1+s}]Q_{\Phi }^{\mathrm{T}}\mathrm{d}s\hfill \\ \hfill & =\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}{Q}_{\Phi }((1+x)I+(1-x){K_{PQ}}^{\mathrm{T}}{K}_{PQ}{)}^{-1}{Q}_{\Phi }^{\mathrm{T}}\mathrm{d}s\hfill \\ \hfill & =Q_{\Phi }\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}{\left(\left(1+s\right){\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{-1}\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)+\left(1-s\right)\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)\right)}^{-1}\mathrm{d}s{Q}_{\Phi }^{\mathrm{T}}\hfill \\ \hfill & =Q_{\Phi }{\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{-1}\frac{2sin\left(\pi t\right)}{\pi }{\int }_{-1}^1{(1-s)}^{-t}{(1+s)}^{t-1}{\left(\left(1-s\right)I+\left(1+s\right){\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{-1}\right)}^{-1}\mathrm{d}s{Q}_{\Phi }^{\mathrm{T}}\hfill \\ \hfill & =Q_{\Phi }\left[{\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{-1}{♯}_{t}I\right]Q_{\Phi }^{\mathrm{T}}.\hfill \end{array}$$

(17)

From Lemma 3, it follows that

$$\begin{array}{cc}\hfill M_{\Phi }=& Q_{\Phi }{\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{-1}{\left({\left(I·{K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{-1}\right)}^{-t}{Q}_{\Phi }^{\mathrm{T}}\hfill \\ \hfill =& Q_{\Phi }{\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}{Q_{\Phi }}^{\mathrm{T}}.\hfill \end{array}$$

(18)

   □

Theorem 2.

The distance $d_{M_{\Phi }}(x,x^{\prime })={\left(\Phi \left(x\right)-\Phi \left(x^{\prime }\right)\right)}^{\mathrm{T}}{M}_{\Phi }\left(\Phi \left(x\right)-\Phi \left(x^{\prime }\right)\right)$ of any two sample x and $x^{\prime }$ can be rewritten as

$$d_{M_{\Phi }}(x,x^{\prime })=(K_{xQ}-K_{x^{\prime }Q}){\left({K_{PQ}}^T{K}_{PQ}\right)}^{t-1}({K_{xQ}}^{\mathrm{T}}-{K_{x^{\prime }Q}}^{\mathrm{T}}).$$

where $K_{xQ}=\Phi {\left(x\right)}^{\mathrm{T}}{Q}_{\Phi }=K_{x{Q}_1}-K_{x{Q}_2}$, $K_{x^{\prime }Q}=\Phi {\left(x^{\prime }\right)}^{\mathrm{T}}{Q}_{\Phi }=K_{x^{\prime }{Q}_1}-K_{x^{\prime }{Q}_2}$, and

$$\begin{array}{c}{K}_{x{Q}_1}=\Phi {\left(x\right)}^{\mathrm{T}}{Q}_{\Phi 1}=\left[\begin{array}{ccc}〈\Phi \left(x_1\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left(x_1\right),\Phi \left({\overline{x}}_{1n}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left(x_n\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left(x_n\right),\Phi \left({\overline{x}}_{1n}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left(x_1,{\overline{x}}_{11}\right)& \cdots & k\left(x_1,{\overline{x}}_{1n}\right)\\ ⋮& \ddots & ⋮\\ k\left(x_n,{\overline{x}}_{11}\right)& \cdots & k\left(x_n,{\overline{x}}_{1n}\right)\end{array}\right]\\ K_{x{Q}_2}=\Phi {\left(x\right)}^{\mathrm{T}}{Q}_{\Phi 2}=\left[\begin{array}{ccc}〈\Phi \left(x_1\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left(x_1\right),\Phi \left({\overline{x}}_{2n}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left(x_n\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left(x_n\right),\Phi \left({\overline{x}}_{2n}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left(x_1,{\overline{x}}_{21}\right)& \cdots & k\left(x_1,{\overline{x}}_{2n}\right)\\ ⋮& \ddots & ⋮\\ k\left(x_n,{\overline{x}}_{21}\right)& \cdots & k\left(x_n,{\overline{x}}_{2n}\right)\end{array}\right]\\ K_{x^{\prime }{Q}_1}=\Phi {\left(x^{\prime }\right)}^{\mathrm{T}}{Q}_{\Phi 1}=\left[\begin{array}{ccc}〈\Phi \left({x^{\prime }}_1\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left({x^{\prime }}_1\right),\Phi \left({\overline{x}}_{1n}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left({x^{\prime }}_n\right),\Phi \left({\overline{x}}_{11}\right)〉& \cdots & 〈\Phi \left({x^{\prime }}_n\right),\Phi \left({\overline{x}}_{1n}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left({x^{\prime }}_1,{\overline{x}}_{11}\right)& \cdots & k\left({x^{\prime }}_1,{\overline{x}}_{1n}\right)\\ ⋮& \ddots & ⋮\\ k\left({x^{\prime }}_n,{\overline{x}}_{11}\right)& \cdots & k\left({x^{\prime }}_n,{\overline{x}}_{1n}\right)\end{array}\right]\\ K_{x^{\prime }{Q}_2}=\Phi {\left(x^{\prime }\right)}^{\mathrm{T}}{Q}_{\Phi 2}=\left[\begin{array}{ccc}〈\Phi \left({x^{\prime }}_1\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left({x^{\prime }}_1\right),\Phi \left({\overline{x}}_{2n}\right)〉\\ ⋮& \ddots & ⋮\\ 〈\Phi \left({x^{\prime }}_n\right),\Phi \left({\overline{x}}_{21}\right)〉& \cdots & 〈\Phi \left({x^{\prime }}_n\right),\Phi \left({\overline{x}}_{2n}\right)〉\end{array}\right]=\left[\begin{array}{ccc}k\left({x^{\prime }}_1,{\overline{x}}_{21}\right)& \cdots & k\left({x^{\prime }}_1,{\overline{x}}_{2n}\right)\\ ⋮& \ddots & ⋮\\ k\left({x^{\prime }}_n,{\overline{x}}_{21}\right)& \cdots & k\left({x^{\prime }}_n,{\overline{x}}_{2n}\right)\end{array}\right].\end{array}$$

Proof. 

According to Theorem 1,

$$\begin{array}{c}{d}_{M_{\Phi }}(x,x^{\prime })={\left(\Phi \left(x\right)-\Phi \left(x^{\prime }\right)\right)}^{\mathrm{T}}{Q}_{\Phi }{\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}{Q}_{\Phi }^{\mathrm{T}}\left(\Phi \left(x\right)-\Phi \left(x^{\prime }\right)\right)\hfill \\ ={\left(\Phi \left(x\right)-\Phi \left(x^{\prime }\right)\right)}^{\mathrm{T}}\left(Q_{\Phi 1}-Q_{\Phi 2}\right){\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}{\left(Q_{\Phi 1}-Q_{\Phi 2}\right)}^{\mathrm{T}}\left(\Phi \left(x\right)-\Phi \left(x^{\prime }\right)\right)\hfill \\ =(K_{x{Q}_1}-K_{x{Q}_2}-K_{x^{\prime }{Q}_1}+K_{x^{\prime }{Q}_2}){\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}({K_{x{Q}_1}}^{\mathrm{T}}-{K_{x{Q}_2}}^{\mathrm{T}}-{K_{x^{\prime }{Q}_1}}^{\mathrm{T}}+{K_{x^{\prime }{Q}_2}}^{\mathrm{T}})\hfill \\ =(K_{xQ}-K_{x^{\prime }Q}){\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}({K_{xQ}}^{\mathrm{T}}-{K_{x^{\prime }Q}}^{\mathrm{T}})\hfill \end{array}$$

(19)

   □

Equation (19) can be taken as the final distance metric of the kernel geometric mean metric learning algorithm. The algorithm is summarized in Algorithm 1.

Algorithm 1 Kernel geometric mean metric learning algorithm.

Input: Similar pair sample set $D^{+}$, dissimilar pair sample set $D^{-}$, and two samples x, $x^{\prime }$. Parameter: t: $t\in [0,1]$, the weight coefficient in Equation (13), p: kernel parameters. Output: $d_{M_{\Phi }}(x,x^{\prime })$ the distance learned for KGMML, Step 1. Compute kernel matrices $K_{P_1{Q}_1}$, $K_{P_1{Q}_2}$, $K_{P_2{Q}_1}$, $K_{P_2{Q}_2}$, and $K_{PQ}$ according to Theorem 1. Step 2. Compute kernel matrices $K_{xQ}$ and $K_{x^{\prime }Q}$ according to Theorem 2. Step 3. Compute the Schur (spectral) decomposition of ${\left({K_{PQ}}^{\mathrm{T}}{K}_{PQ}\right)}^{t-1}$=$U{\Lambda }^{t-1}U=A$, where U denotes the eigenvalue of ${K_{PQ}}^{\mathrm{T}}{K}_{PQ}$, and $\Lambda$ denotes the eigenvector of ${K_{PQ}}^{\mathrm{T}}{K}_{PQ}$. Step 4. Compute $d_{M_{\Phi }}(x,x^{\prime })=(K_{xQ}-K_{x^{\prime }Q})A({K_{xQ}}^{\mathrm{T}}-{K_{x^{\prime }Q}}^{\mathrm{T}})$.

4. Experiment

4.1. Experimental Setup

To verify the effectiveness of Algorithm 1, simulation experiments were conducted on 15 UCI [27] datasets, where the basic information is shown in

Table 1. Characteristics of experimental datasets.

	Datasets	Of Features	Of Instances	Of Classes
1	Pima	8	768	2
2	Vehicle	18	846	4
3	German	24	1000	2
4	Segment	18	2310	7
5	Heart-Disease	13	270	2
6	Lymphgraphy	18	148	4
7	Liver-Disorders	6	345	2
8	Hayes-Roth	4	160	3
9	Ionosphere	34	351	2
10	Glasses	9	214	6
11	Balance-Scale	4	625	3
12	Usps	256	9298	10
13	Mnist	784	4000	10
14	DNA	180	3186	2
15	Spambase	57	4601	2

. We divided the dataset into large and small datasets according to the size of the sample size (1–11 were small datasets, and 12–15 were large datasets; a sample size greater than 3000 is considered a large dataset, and a sample size of less than 3000 is considered a small dataset).

Next, some efficient algorithms are described for distance metric learning, and the proposed method is compared with existing excellent classical algorithms. The specific introduction is given in

Table 2. Brief description of the distance metric learning method used in this paper.

	Name	Description
1	Euclidean	The Euclidean distance metric [28].
2	DMLMJ	Distance metric learning through maximization of the Jeffrey divergence [28].
3	LMNN	Large margin nearest neighbor classification [16].
4	GB-LMNN	Non-linear transformations with gradient boosting [29].
5	GMML	Geometric mean metric learning [17].
6	Low-rank	Low-rank geometric mean metric learning [30].
7	KGMML	The kernelized version of GMML

. These algorithms are all from the original author’s homepage. The kernel function used in the experiment is the Gaussian kernel function. For the KGMML, the settings of t and p are given in detail in the next subsection. In this paper, 5-fold cross-validation is repeated 10 times to measure the average accuracy. Moreover, as a preprocessing step, each feature of the experimental dataset is scaled to the one with zero mean and unit variance.

4.2. Parameter Sensitivity Analysis

To determine the impact of these two parameters on the KGMML algorithm, the experiments are conducted on five datasets selected from 15 datasets. Five-fold cross validation is used to choose the best t-value, and the two-step method is used to test different t-values. The above approach is used to find the best t-value, and its precision can be verified in Figure 1 and Figure 2. Firstly, obtain the optimal t in the set $\left\{0.1,0.3,0.5,0.7,0.9\right\}$, and the result is shown in Figure 1. Secondly, test 5 t-values using intervals with a step size of 0.02. As shown in Figure 2, the variation of accuracy in the test interval with a step size of 0.02 is not significant, so we choose the middle t-value of 0.05. When the p-value is 10, the precision has an inflection point in Figure 3, and the precision is higher at the inflection point. Thus, the p-value is chosen as 10. Vary t in the set $\left\{0.1,0.3,0.5,0.7,0.9\right\}$, and p is fixed.

4.3. Experimental Results

The accuracy of each compared algorithm on 15 datasets is shown in

Table 3. Classification errors on UCI dataset. The best result is highlighted in boldface.

	Datasets	GMML	DMLMJ	LMNN	GB-LMNN	Euclidean	Low-Rank	KGMML
1	Pima	27.66	30.18	33.82	37.14	27.27	29.58	25.17
2	Vehicle	22.09	25.75	46.53	41.24	33.53	41.32	21.21
3	German	27.41	24.79	30.50	29.32	31.53	26.96	24.40
4	Segment	4.13	3.64	5.19	4.55	6.93	5.59	3.22
5	Heart-Disease	20.82	19.73	31.52	18.51	33.33	22.52	18.97
6	Lymphography	56.88	73.62	70.76	60.21	75.13	57.57	53.75
7	Liver-Disorders	35.00	30.05	30.46	34.88	31.88	41.86	30.17
8	Hayes-Roth	37.69	16.84	31.33	31.35	16.67	39.55	19.52
9	Ionosphere	15.34	11.27	5.71	4.29	1.43	17.26	11.54
10	Glasses	36.96	33.08	30.20	23.30	30.23	33.64	32.47
11	Balance-Scale	12.84	8.62	12.80	15.20	14.40	12.31	9.19
12	Usps	3.72	2.88	33.11	10.60	10.55	4.08	2.82
13	Mnist	9.65	16.44	86.80	82.62	17.12	75.34	8.32
14	DNA	23.65	21.75	22.32	22.84	27.63	26.24	23.05
15	Spambase	19.33	18.27	38.60	15.80	16.09	11.43	11.20

, where the best result on each dataset is shown in boldface. Compared with the other six algorithms, our algorithm achieves the highest accuracy on the eight datasets of pima, vehicle, german, segment, usps, mnist, lymphgraphy and spambase. From the experimental results, we conclude that our proposed KGMML algorithm is more accurate than the GMML algorithm on all 15 datasets. The accuracy of the KGMML algorithm can be improved by roughly 2% to 4% over the GMML algorithm in small datasets, and the improvement is generally smaller for large datasets. In the small dataset, the Hayes-Roth dataset improves accuracy by 18.17%; in the large dataset, the Spambase dataset improves accuracy by 8.13%. The analysis reveals that the accuracy improvement is greater when the number of features is relatively small in both large and small datasets.

Table 4. Win/tie/loss counts of each algorithm between the results obtained the KGMML algorithm and other classical algorithms.

Datasets	KGMML
	GMML	DMLMJ	LMNN	GB-LMNN	Euclidean	Low-Rank
Pima	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0
Vehicle	0/1/0	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0
German	1/0/0	0/1/0	1/0/0	1/0/0	1/0/0	1/0/0
Segment	1/0/0	0/1/0	1/0/0	1/0/0	1/0/0	1/0/0
Usps	1/0/0	0/1/0	1/0/0	1/0/0	1/0/0	1/0/0
Mnist	0/1/0	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0
Glasses	1/0/0	0/1/0	0/0/1	0/0/1	0/1/0	1/0/0
DNA	0/1/0	0/0/1	0/0/1	0/1/0	1/0/0	1/0/0
Heart-Disease	1/0/0	0/1/0	1/0/0	0/1/0	1/0/0	1/0/0
Lymphography	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0
Liver-Disorders	1/0/0	0/1/0	0/1/0	1/0/0	0/1/0	1/0/0
Hayes-Roth	1/0/0	0/0/1	1/0/0	1/0/0	0/0/1	1/0/0
Ionosphere	1/0/0	0/1/0	0/0/1	0/0/1	0/0/1	1/0/0
Spambase	1/0/0	1/0/0	1/0/0	1/0/0	1/0/0	0/1/0
Balance	1/0/0	0/1/0	1/0/0	1/0/0	1/0/0	1/0/0
Total	12/3/0	5/8/2	11/1/3	9/2/2	11/2/2	14/1/0

lists the average running time of the GMML algorithm and the KGMML algorithm on the dataset, which shows that the proposed algorithm does not drag down the running efficiency of the original algorithm. All experimental methods are implemented on MATLABR2018b (64-bit), and the simulations are run on a laptop with an Intel Core i5 (2.5 GHz) processor.

To show the performance advantages of the KGMML algorithm, a score statistic is performed on the KGMML algorithm and other classic algorithms. The scoring process is as follows. Assuming that A is the result of using the KGMML algorithm on a certain dataset, and B is the result of uniting the KGMML algorithm on this dataset (that is, using other algorithms), firstly, comparative analysis of A and B is performed by using a 5% significance level t test. In a statistical sense, if $A>B$, it is considered that the result A obtained by using the KGMML algorithm on this dataset wins the result B using other algorithms. Thus, the statistical result of the score on this dataset is recorded as “1/0/0”. If $A<B$, the score statistics result is recorded as “0/0/1”. If $A=B$, it means that A and B are the same in the statistical sense. Thus, it is considered that they are tied and recorded as “0/1/0”. It is evident that the notation “5/0/0” signifies that the outcomes achieved by the KGMML algorithm outperform those of other algorithms across five datasets. On each dataset and the overall score, the statistical results of the KGMML algorithm are listed in Table 4.

5. Conclusions

In this paper, kernel geometric mean metric learning is proposed for the nonlinear distance metric with the introduction of a kernel function. Traditional metric learning methods aim to learn global linear metrics; for most data, there are nonlinear relationships, so traditional methods are not suitable for nonlinear problems. The experimental results on the UCI dataset show that the algorithm can effectively improve the accuracy of the GMML algorithm. Especially for small datasets, the highest can reach more than 40%, and the proposed algorithm can address nonlinear problems.

In practice, only a small amount of data is tagged, while most of the data remains untagged. Therefore, the question of how to make the best use of this large amount of untagged data prompted us to think. Under the partial marker learning framework, the real class markers of the training samples are usually hidden in a set of candidate markers and are no longer explicit, which makes the construction of learning algorithms more difficult than the traditional classification problems, and the research results are still less available. In future work, we will try to improve the inaccurate similarity pair problem existing in the kernel-based geometric mean metric learning algorithm. Using the partial labeling metric learning algorithm proposed in recent years, a partial labeling algorithm based on kernel geometric mean metric learning will be proposed.