Learning with Asymmetric Kernels: Least Squares and Feature Interpretation

Given training samples $\{\bm{x}_{i},y_{i}\}_{i=1}^{m}$ with $\bm{x}\in\mathbb{R}^{d}$ and $y\in\{+1,-1\}$, a discriminant function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is constructed to classify the input samples. For linearly inseparable problems, a non-linear feature mapping $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{p}$ is needed, where $\mathbb{R}^{p}$ is a high-dimensional space.

LS-SVMs with PSD kernels can be solved by the following optimization problem [15],

where the discriminant function $f$ is formulated as $f(\bm{x})=\bm{\omega}^{\top}\phi(\bm{x})+b$. When the kernel is generalized to a non-PSD one, the primal problem is as follows [11],

where $\phi_{+}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{p_{1}}$ and $\phi_{-}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{p_{2}}$ are two non-linear feature mappings, both $\mathbb{R}^{p_{1}}$ and $\mathbb{R}^{p_{2}}$ are potential high-dimensional spaces. The discriminant function here is formulated as $f(\bm{x})=\bm{\omega}_{+}^{\top}\phi_{+}(\bm{x}_{i})+\bm{\omega}_{-}^{\top}\phi_{-}(\bm{x}_{i})+b$.

Although the feature interpretations of (LABEL:ls-svm) and (LABEL:indefinite-ls-svm) are not the same, their dual problems share the same formulation as below,

The kernel trick, which gives the feature interpretation of (4), is different for different types of kernels. If the kernel is PSD then,

If the kernel is non-PSD but has a positive decomposition, for which the conceptual condition and a practice judgment can be found in [13], the kernel trick becomes,

where $\mathcal{K}_{+}$ and $\mathcal{K}_{-}$ are two PSD kernels.

When looking at the framework of LS-SVM from the viewpoint of solving (4), there is not any problem if $\bm{K}$ is asymmetric. It is still well-defined and a solution can be readily obtained. The key problem is to analyze what we really learn if $\bm{K}$ is asymmetric.

First, we define a generalized kernel trick to present a kernel as an inner product of two mappings $\phi_{s}$ and $\phi_{t}$.

Different from the classical kernel trick, the above definition allows different $\phi_{s}$ and $\phi_{t}$, of which even the dimension $d_{s}$ and $d_{t}$ could be different. In this paper, we consider the case $d:=d_{s}=d_{t}$ then both $\mathcal{K}(\bm{u},\bm{v})$ and $\mathcal{K}(\bm{v},\bm{u})$ are well-defined and the kernel matrix for training data is square but asymmetric. Definition 1 is compatible with the existing symmetric kernels, including PSD and indefinite ones.

1. 1.

   The symmetric and positive semi-definite kernel $\mathcal{K}(u,v)$ can be defined as follows:

   $$\mathcal{K}(\bm{u},\bm{v})=\left<\phi(\bm{u}),\phi(\bm{v})\right>,\forall\bm{u},\bm{v}\in\mathbb{R}^{d},$$

   in the situation when, two feature mappings $\phi_{s}$ and $\phi_{t}$ are identical $\phi:=\phi_{s}=\phi_{t}$. $\phi_{s},\phi_{t}\in\mathbb{R}^{d}\rightarrow\mathbb{R}^{p}$.

2. 2.

   The symmetric and indefinite kernel $\mathcal{K}(u,v)$ can be defined as follows:

   	$\displaystyle\mathcal{K}(\bm{u},\bm{v})$	$\displaystyle=\mathcal{K}_{1}(\bm{u},\bm{v})-\mathcal{K}_{2}(\bm{u},\bm{v})$
   		$\displaystyle=\left<\phi_{1}(\bm{u}),\phi_{1}(\bm{v})\right>-\left<\phi_{2}(\bm{u}),\phi_{2}(\bm{v})\right>$
   		$\displaystyle=\left[\begin{array}[]{cc}\phi_{1}(\bm{u})\\ \phi_{2}(\bm{u})\end{array}\right]^{\top}\left[\begin{array}[]{cc}\phi_{1}(\bm{v})\\ -\phi_{2}(\bm{v})\end{array}\right]$
   		$\displaystyle:=\left<\phi_{s}(\bm{u}),\phi_{t}(\bm{v})\right>,\forall\bm{u},\bm{v}\in\mathbb{R}^{d},$

   in the situation when two feature mappings $\phi_{s}$ and $\phi_{t}$ are not identical, $\mathcal{K}_{1}$ and $\mathcal{K}_{2}$ are two PSD kernels and $\phi_{1}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{p_{1}}$ and $\phi_{2}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{p_{2}}$ are two high-dimensional feature mappings corresponding to $\mathcal{K}_{1}$ and $\mathcal{K}_{2}$, respectively. $\mathbb{R}^{p_{1}}$ and $\mathbb{R}^{p_{2}}$ are two high-dimensional spaces.

The kernel trick associated with an asymmetric kernel contains two different feature mappings. Using the concept from directed graphs, we call them source and target features, respectively. Then for each sample, e.g., a node in a directed graph, we can extract two features from different views and classify the sample in the framework of the least squares support vector machine, which is hence called Ask-LS. The AsK-LS in the primal space takes the following form,

where $e_{i},h_{i}\in\mathbb{R}$ and $\gamma$ is the regularization coefficient of misclassification errors. In AsK-LS (LABEL:asy_ls_svm), the sample plays different roles and can have different meanings in different tasks. In the matrix decomposition, the features could be given as column and row vectors, which could lead to an asymmetric kernel for unsupervised learning [20].

Now let us investigate the dual problem of (LABEL:asy_ls_svm), of which the kernel trick for an asymmetric kernel is crucial.

The primal-dual relationship between (LABEL:asy_ls_svm) and (6) for asymmetric kernels is characterized by Proposition 1, which also includes symmetric kernels. In that case, both the primal and dual formulations reduce to the classical LS-SVM, as shown below.

Symmetric and asymmetric kernels lead to a unified linear system. When the data size is not very large, (6) is easy to solve. For large-scale problems, one can consider the fixed-size [32, 33], Nyström approximation [34], for the latter of which necessary modifications are required. In the early work by Schmidt [35], an asymmetric kernel has a pair of adjoint eigenfunctions corresponding to the eigenvalue, thus the modified Nyström approximation for asymmetric kernels leads to a standard singular value decomposition. When the kernel is asymmetric, we simultaneously obtain two functions $f_{s},f_{t}$. To fully use the asymmetric information, we need to merge them together. Averaging is a simple way and other ensemble methods like the stacked generalization [36] can be also used. Overall, we summarize the algorithm for AsK-LS in the following.

Kullback-Leibler divergence is the measure of how one probability distribution $Q$ is different from another probability distribution $P$:

which is asymmetric. KL divergence has been successfully used in many fields, e.g., VAE [37] and GAN [38, 39]. From KL divergence, one can evaluate the similarity between two probability distributions by the exponentiation as follows:

where $a\in\mathbb{R}^{+}$ is a hyperparameter to control the scale of the kernel (14), $s$ denotes a sample and $P_{i}$,$P_{j}$ are probability distributions estimated by samples $s_{i}$ and $s_{j}$, respectively. Since KL divergence is asymmetric, the kernel matrix is also asymmetric. Thus the AsK-LS can be utilized to directly learn with the asymmetric KL kernel rather than its symmetry [21].

We conduct image classification experiments on the Corel database [40]. The Corel database contains 80 concept groups e.g., autumn, aviation, dog, and elephant. And 10 classes of those groups are picked: beaches, bus, dinosaurs, elephants, flowers, foods, horses, monuments, snow mountains, and African people & villages. There are 100 images per class: 90 for training and 10 for testing. We follow the standard feature extraction method [21] to obtain a sequence of 64-dimensional discrete cosine transform feature vectors $\bm{X}=\{\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{l}\}$ of an image where $l$ is the number of feature vectors.

In the experiment, we use the Gaussian mixture model (GMM) with 256 diagonal Gaussian components to estimate the probability distribution $P_{i}(\bm{X}_{i})$ of the image feature vector sequence $\bm{X}_{i}$. Since the KL divergence for two GMMs can not be calculated by the formulation (13) directly, we use the Monte Carlo method to calculate it. Then kernel value between two images is given by the KL kernel similarity (14) of these two probability distributions.

The corresponding asymmetric KL divergence has been widely used in learning tasks. However, due to that KL divergence violates the symmetry requirement, it has never been directly used in the kernel-based learning. Now with the AsK-LS, we can use it in classification tasks. As a comparison, the SVM and the LS-SVM are used with a symmetric KL kernel [21]. For the parameters, i.e., the hyperparameter $a$ and regularization parameter $\gamma$ in all the three models is tuned by 10-folds cross-validation. The AsK-LS outputs two classifiers and here we simply average them.

The image classification is a multi-classes task where we utilize the one-vs-rest scheme, for which the average Micro-F1 and Macro-F1 scores are reported in Table I. The AsK-LS achieves better performance, showing that learning with the asymmetric information can help.

Nodes classification with an asymmetric adjacency matrix is a task that needs to learn from asymmetric metrics. In this task, nodes in a directed graph $\mathcal{H}=\{\mathcal{N},\mathcal{E}\}$ with nodes set $\mathcal{N}$ and edges set $\mathcal{E}$ are classified. Its adjacency matrix showing the connection among nodes is defined as follows,

where $j\rightarrow i$ means that there is a link pointing to node $i$ from node $j$. This model has wide applications and here we consider five directed graphs, namely Cora, Citeseer, and Pubmed [41], AM-photo, and AM-computer [42]. Details of the data set could be found in Table II. For the first three widely used graphs, the nodes and edges present documents and citations, respectively. For the latter two, the nodes present goods, and the edges mean the two goods are frequently bought together. The node classification is originally a multi-classes task where we utilize the one-vs-rest scheme and focus on Micro-F1 and Macro-F1 scores.

A directed graph is fully characterized by its adjacency matrix. However, in existing kernel methods, one cannot directly use the adjacency matrix as a kernel. Therefore, the current mainstream is to first do feature embedding [17, 18, 19] to extract the asymmetric information and then do classification based on the extracted features. In the experiment, For the embedding, we use a SOTA embedding method NERD [19], which utilizes random walk to extract node embeddings $\phi_{s}(v)$ and $\phi_{t}(v)$ as source feature and target feature of each node $v\in\mathcal{N}$ on a directed graph. We combine them as a unified feature $\phi(v)=[\phi^{\top}_{s}(v),\phi^{\top}_{t}(v)]^{\top}$ which then defines a symmetric kernel that can be used in classical kernel-based learning methods, e.g., the SVM and the LS-SVM, and results are reported in the third and the fourth columns in Table III.

Since the asymmetric information can be extracted by the embedding method, the performance of that is much better than using existing kernel methods with the adjacency matrix by symmetrization $(\mathcal{A}+\mathcal{A}^{\top})/2$, of which micro-/macro- F1 scores are listed in the 5th and the 6th column in Table III.

Now we have the AsK-LS and can directly learn with the adjacency matrix without the feature embedding. Before sending the adjacency matrix to the AsK-LS, we pre-process it by its in-degree $d_{i}=\sum_{j=1}^{m}\mathcal{A}_{ij}$ (the same pre-process is also applied for the SVM and the LS-SVM). The Micro- and Macro-F1 scores of the AsK-LS are reported in the last column in Table III. The performance is much better than the SVM and the LS-SVM with the symmetrization of the kernel, indicating that the asymmetric information is helpful. For the comparison with the SOTA embedding methods, the AsK-LS is better or at least comparable, showing the effectiveness of AsK-LS for extracting the asymmetric information.

We have shown that the proposed AsK-LS can learn with asymmetric kernels. Since asymmetric kernels are more general than symmetric ones, learning with asymmetric kernels is promising to get improvement, if there is an efficient method to get a suitable kernel. In the case in our paper, kernels are pre-given, then the performance is determined by the choice of kernels. In the previous sections, the asymmetric information, i.e., measuring the difference by KL divergence and directed distance, is important, thus the corresponding asymmetric kernels lead to a good performance. If not the case, a specific asymmetric kernel is not necessarily better than the symmetric one, e.g., the RBF kernel.

We conduct classification experiments on several datasets from the UCI database[43], where 60% of the data are randomly picked up for training and the rest for testing. Two asymmetric kernels, called SNE kernel and T kernel, are considered here. They have been used for dimension reduction [14] but have not been used for classification, since before there was no classification method that can learn with asymmetric kernels directly. The formulations are given as below,

1. 1.

   The SNE kernel with the parameter $\sigma\in\mathbb{R}$:

   $$\mathcal{K}_{\rm{SNE}}(\bm{x},\bm{y})=\frac{\exp(-\|\bm{x}-\bm{y}\|_{2}^{2})/\sigma^{2}}{\sum_{\bm{z}\in\bm{X}}\exp(-\|\bm{x}-\bm{z}\|_{2}^{2})/\sigma^{2}},$$

2. 2.

   The T kernel:

   $$\mathcal{K}_{\rm{T}}(\bm{x},\bm{y})=\frac{(1+\|\bm{x}-\bm{y}\|^{2}_{2})^{-1}}{\sum_{\bm{z}\in\bm{X}}(1+\|\bm{x}-\bm{z}\|^{2}_{2})^{-1}},$$

where $\bm{X}$ stands for the training set.

The classification accuracy of the AsK-LS with the two asymmetric kernels is reported in Table IV, together with the accuracy of the LS-SVM with the RBF kernel (all the parameters are tuned by 10-folds cross-validation). Generally speaking, the best choice of kernels is problem-dependent and one cannot assert which kernel is good in advance. But at least, the proposed AsK-LS makes it possible to use asymmetric kernels. With delicately designing or efficiently learning, asymmetric kernels could lead to a good performance.