A Primal Framework for Indefinite Kernel Learning

Kernel methods have been widely applied in machine learning to solve complex nonlinear problems. Kernel selection is one of the key issues in kernel methods, since it is vital for improving generalization performance. Traditionally, the selection of kernel is restricted to be positive definite which makes their applicability partially limited. Actually, in many real applications such as gene identification and object recognition, indefinite kernels frequently emerge and can achieve better performance. However, compared to positive definite ones, indefinite kernels are more complicated due to the non-convexity of the subsequent optimization problems, which leads to the incapability of most existing kernel algorithms. Some indefinite kernel methods have been proposed based on the dual of support vector machine (SVM), which mostly emphasize on how to transform the non-convex optimization to be convex by using positive definite kernels to approximate indefinite ones. In fact, the duality gap in SVM usually exists in the case of indefinite kernels and therefore these algorithms do not indeed solve the indefinite kernel problems themselves. In this paper, we present a novel framework for indefinite kernel learning derived directly from the primal of SVM, which establishes several new models not only for single indefinite kernel but also extends to multiple indefinite kernel scenarios. Several algorithms are developed to handle the non-convex optimization problems in these models. We further provide a constructive approach for kernel selection in the algorithms by using the theory of similarity functions. Experiments on real world datasets demonstrate the superiority of our models.     

Feature space interpretation of SVMs with indefinite kernels

Kernel methods are becoming increasingly popular for various kinds of machine learning tasks, the most famous being the support vector machine (SVM) for classification. The SVM is well understood when using conditionally positive definite (cpd) kernel functions. However, in practice, non-cpd kernels arise and demand application in SVM. The procedure of "plugging" these indefinite kernels in SVM often yields good empirical classification results. However, they are hard to interpret due to missing geometrical and theoretical understanding. In this paper, we provide a step toward the comprehension of SVM classifiers in these situations. We give a geometric interpretation of SVM with indefinite kernel functions. We show that such SVM are optimal hyperplane classifiers not by margin maximization, but by minimization of distances between convex hulls in pseudo-Euclidean spaces. By this, we obtain a sound framework and motivation for indefinite SVM. This interpretation is the basis for further theoretical analysis, e.g., investigating uniqueness, and for the derivation of practical guidelines like characterizing the suitability of indefinite SVM.     

Kernel Discriminant Analysis for Positive Definite and Indefinite Kernels

Kernel methods are a class of well established and successful algorithms for pattern analysis thanks to their mathematical elegance and good performance. Numerous nonlinear extensions of pattern recognition techniques have been proposed so far based on the so-called kernel trick. The objective of this paper is twofold. First, we derive an additional kernel tool that is still missing, namely kernel quadratic discriminant (KQD). We discuss different formulations of KQD based on the regularized kernel Mahalanobis distance in both complete and class-related subspaces. Secondly, we propose suitable extensions of kernel linear and quadratic discriminants to indefinite kernels. We provide classifiers that are applicable to kernels defined by any symmetric similarity measure. This is important in practice because problem-suited proximity measures often violate the requirement of positive definiteness. As in the traditional case, KQD can be advantageous for data with unequal class spreads in the kernel-induced spaces, which cannot be well separated by a linear discriminant. We illustrate this on artificial and real data for both positive definite and indefinite kernels.     

两阶段不定核支持向量机

近年来,在机器学习的各个领域出现了越来越多不定的度量核矩阵,使得不定核支持向量机(IKSVM)得到了广泛关注。但是,现有IKSVM算法通常不能较好地解决高维数据所带来的信息冗余和样本稀疏等问题。针对此研究现状,对现有主流的IKSVM算法进行了研究,并基于再生核Kre?n空间(RKKS)中对IKSVM问题的稳定化定义,从理论上证明了IKSVM问题的本质为不定核主成分分析(IKPCA)降维后空间中的支持向量机(SVM)问题,进一步地提出求解IKSVM问题的新型学习框架TP-IKSVM。TP-IKSVM通过将IKSVM问题的求解拆分为IKPCA和SVM两个阶段,充分地发挥了IKPCA在处理高维数据的信息冗余和样本稀疏等方面的优势,同时结合SVM以有效分类。在真实数据集上的实验结果表明,TP-IKSVM的分类精度优于现有主流的IKSVM算法。     

A Novel Indefinite Kernel Dimensionality Reduction Algorithm: Weighted Generalized Indefinite Kernel Discriminant Analysis

Kernel methods are becoming increasingly popular for many real-world learning problems. And these methods for data analysis are frequently considered to be restricted to positive definite kernels. In practice, however, indefinite kernels arise and demand application in pattern analysis. In this paper, we present several formal extensions of kernel discriminant analysis (KDA) methods which can be used with indefinite kernels. In particular they include indefinite KDA (IKDA) based on generalized singular value decomposition (IKDA/GSVD), pseudo-inverse IKDA, null space IKDA and range space IKDA. Similar to the case of LDA-based algorithms, IKDA-based algorithms also fail to consider that different contribution of each pair of class to the discrimination. To remedy this problem, weighted schemes are incorporated into IKDA extensions in this paper and called them weighted generalized IKDA algorithms. Experiments on two real-world data sets are performed to test and evaluate the effectiveness of the proposed algorithms and the effect of weights on indefinite kernel functions. The results show that the effect of weighted schemes is very significantly.     

基于串核的音乐风格聚类

给出了一种新的映射音乐到R°空间的方法和基于串核的音乐风格聚类法.利用统计方法分析大量音乐的旋律轮廓线得到合适的编码模式,用它把旋律轮廓线编码为有限字母表(8个字母)的字符串.利用连续子串嵌入法把音乐串显式映射到高维R°空间,并用核表示这一映射.通过用基于核的山方法选择聚类的适合初始点,最后使用基于核的K-means方法聚类音乐数据集,比较了3个不同串核在5个音乐数据集上的聚类性能.     

Towards kernelizing the classifier for hyperbolic data

Data hierarchy, as a hidden property of data structure, exists in a wide range of machine learning applications. A common practice to classify such hierarchical data is first to encode the data in the Euclidean space, and then train a Euclidean classifier. However, such a paradigm leads to a performance drop due to distortion of data embedding in the Euclidean space. To relieve this issue, hyperbolic geometry is investigated as an alternative space to encode the hierarchical data for its higher ability to capture the hierarchical structures. Those methods cannot explore the full potential of the hyperbolic geometry, in the sense that such methods define the hyperbolic operations in the tangent plane, causing the distortion of data embeddings. In this paper, we develop two novel kernel formulations in the hyperbolic space, with one being positive definite (PD) and another one being indefinite, to solve the classification tasks in hyperbolic space. The PD one is defined via mapping the hyperbolic data to the Drury-Arveson (DA) space, which is a special reproducing kernel Hilbert space (RKHS). To further increase the discrimination of the classifier, an indefinite kernel is further defined in the Kreĭn spaces. Specifically, we design a 2-layer nested indefinite kernel which first maps hyperbolic data into the DA spaces, followed by a mapping from the DA spaces to the Kreĭn spaces. Extensive experiments on real-world datasets demonstrate the superiority of the proposed kernels.     

Kernels, regularization and differential equations

Many common machine learning methods such as support vector machines or Gaussian process inference make use of positive definite kernels, reproducing kernel Hilbert spaces, Gaussian processes, and regularization operators. In this work these objects are presented in a general, unifying framework and interrelations are highlighted.With this in mind we then show how linear stochastic differential equation models can be incorporated naturally into the kernel framework. And vice versa, many kernel machines can be interpreted in terms of differential equations. We focus especially on ordinary differential equations, also known as dynamical systems, and it is shown that standard kernel inference algorithms are equivalent to Kalman filter methods based on such models.In order not to cloud qualitative insights with heavy mathematical machinery, we restrict ourselves to finite domains, implying that differential equations are treated via their corresponding finite difference equations.     

Image reconstruction from scattered Radon data by weighted positive definite kernel functions

We propose a novel kernel-based method for image reconstruction from scattered Radon data. To this end, we employ generalized Hermite–Birkhoff interpolation by positive definite kernel functions. For radial kernels, however, a straightforward application of the generalized Hermite–Birkhoff interpolation method fails to work, as we prove in this paper. To obtain a well-posed reconstruction scheme for scattered Radon data, we introduce a new class of weighted positive definite kernels, which are symmetric but not radially symmetric. By our construction, the resulting weighted kernels are combinations of radial positive definite kernels and positive weight functions. This yields very flexible image reconstruction methods, which work for arbitrary distributions of Radon lines. We develop suitable representations for the weighted basis functions and the symmetric positive definite kernel matrices that are resulting from the proposed reconstruction scheme. For the relevant special case, where Gaussian radial kernels are combined with Gaussian weights, explicit formulae for the weighted Gaussian basis functions and the kernel matrices are given. Supporting numerical examples are finally presented.     

普适性核度量标准比较研究

核方法是一类应用较为广泛的机器学习算法,已被应用于分类、聚类、回归和特征选择等方面.核函数的选择与参数优化一直是影响核方法效果的核心问题,从而推动了核度量标准,特别是普适性核度量标准的研究.对应用最为广泛的5种普适性核度量标准进行了分析与比较研究,包括KTA,EKTA,CKTA,FSM和KCSM.发现上述5种普适性度量标准的度量内容为特征空间中线性假设的平均间隔,与支持向量机最大化最小间隔的优化标准存在偏差.然后,使用模拟数据分析了上述标准的类别分布敏感性、线性平移敏感性、异方差数据敏感性,发现上述标准仅是核度量的充分非必要条件,好的核函数可能获得较低的度量值.最后,在9个UCI数据集和20Newsgroups数据集上比较了上述标准的度量效果,发现CKTA是度量效果最好的普适性核度量标准.     

Polynomial summaries of positive semidefinite kernels

Polynomials have proven to be useful tools to tailor generic kernels to specific applications. Nevertheless, we had only restricted knowledge for selecting fertile polynomials which consistently produce positive semidefinite kernels. For example, the well-known polynomial kernel can only take advantage of a very narrow range of polynomials, that is, the univariate polynomials with positive coefficients. This restriction not only hinders intensive exploitation of the flexibility of the kernel method, but also causes misuse of indefinite kernels. Our main theorem significantly relaxes the restriction by asserting that a polynomial consistently produces positive semidefinite kernels, if it has a positive semidefinite coefficient matrix. This sufficient condition is quite natural, and hence, it can be a good characterization of the fertile polynomials. In fact, we prove that the converse of the assertion of the theorem also holds true in the case of degree 1. We also prove the effectiveness of our main theorem by showing three corollaries relating to certain applications known in the literature: the first and second corollaries, respectively, give generalizations of the polynomial kernel and the principal-angle (determinant) kernel. The third corollary shows extended and corrected sufficient conditions for the codon-improved kernel and the weighted-degree kernel with shifts to be positive semidefinite.     

一种改进的再生核支持向量机回归模型

基于支持向量机核函数的条件,将Sobolev Hilbert空间的再生核函数进行改进,给出一种新的支持向量机核函数,并提出一种改进的最小二乘再生核支持向量机的回归模型,该回归模型的参数被减少,且仿真实验结果表明：最小二乘支持向量机的核函数采用改进的再生核函数是可行的,改进后的再生核函数不仅具有核函数的非线性映射特征,而且也继承了该再生核函数对非线性逐级精细逼近的特征,回归的效果比一般的核函数更为细腻。     

String kernels construction and fusion: a survey with bioinformatics application

The kernel method, especially the kernel-fusion method, is widely used in social networks, computer vision, bioinformatics, and other applications. It deals effectively with nonlinear classification problems, which can map linearly inseparable biological sequence data from low to high-dimensional space for more accurate differentiation, enabling the use of kernel methods to predict the structure and function of sequences. Therefore, the kernel method is significant in the solution of bioinformatics problems. Various kernels applied in bioinformatics are explained clearly, which can help readers to select proper kernels to distinguish tasks. Mass biological sequence data occur in practical applications. Research of the use of machine learning methods to obtain knowledge, and how to explore the structure and function of biological methods for theoretical prediction, have always been emphasized in bioinformatics. The kernel method has gradually become an important learning algorithm that is widely used in gene expression and biological sequence prediction. This review focuses on the requirements of classification tasks of biological sequence data. It studies kernel methods and optimization algorithms, including methods of constructing kernel matrices based on the characteristics of biological sequences and kernel fusion methods existing in a multiple kernel learning framework.     

Some sets of orthogonal polynomial kernel functions

Kernel methods provide high performance in a variety of machine learning tasks. However, the success of kernel methods is heavily dependent on the selection of the right kernel function and proper setting of its parameters. Several sets of kernel functions based on orthogonal polynomials have been proposed recently. Besides their good performance in the error rate, these kernel functions have only one parameter chosen from a small set of integers, and it facilitates kernel selection greatly. Two sets of orthogonal polynomial kernel functions, namely the triangularly modified Chebyshev kernels and the triangularly modified Legendre kernels, are proposed in this study. Furthermore, we compare the construction methods of some orthogonal polynomial kernels and highlight the similarities and differences among them. Experiments on 32 data sets are performed for better illustration and comparison of these kernel functions in classification and regression scenarios. In general, there is difference among these orthogonal polynomial kernels in terms of accuracy, and most orthogonal polynomial kernels can match the commonly used kernels, such as the polynomial kernel, the Gaussian kernel and the wavelet kernel. Compared with these universal kernels, the orthogonal polynomial kernels each have a unique easily optimized parameter, and they store statistically significantly less support vectors in support vector classification. New presented kernels can obtain better generalization performance both for classification tasks and regression tasks.     

基于多标签的内核配置图及其应用

Linux内核提供了灵活的内核配置项机制,便于针对不同的应用场景进行个性化定制.但内核配置项的数量巨大且增长快速,配置项的默认值在不同内核版本中经常改变,即使专业的内核团队设置配置项也面临很多挑战.针对上述问题,提出基于多标签的内核配置图,该图包含内核配置项间的依赖关系、功能标签、性能标签、安全标签和配置项使能率.此外,该图提供了可视化功能,更加直观、高效、人性化.该内核配置图在内核配置项异常值检测、内核启动优化、内核裁剪、内核安全增强、内核性能优化、内核配置项智能问答等场景均可应用.且将内核配置图应用到检索场景,实现了面向内核配置项的检索框架KCIR(kernel config information retrieval),该框架基于内核配置图对查询语句和内核配置项描述文本进行了扩展,实验评估表明KCIR和传统检索框架相比,检索效果有显著提升,验证了内核配置图在实际应用中的有效性和实用性.     

基于最大熵的模糊核聚类图像分割方法

传统聚类算法易陷入局部极值,在数据线性不可分时分类效果较差。为此,提出一种基于最大熵的模糊核聚类图像分割方法。采用最大熵算法对原始图像进行初步分割,求得初始聚类中心;引入Mercer核函数,把输入空间的样本映射到高维特征空间,并在特征空间中进行图像分割。实验结果表明,该方法能减少迭代次数,使分类结果更稳定,从而较好地把目标从背景中分割出来。     

A primal perspective for indefinite kernel SVM problem

Indefinite kernel support vector machine(IKSVM)has recently attracted increasing attentions in machine learning.Since IKSVM essentially is a non-convex problem,existing algorithms either change the spectrum of indefinite kernel directly but risking losing some valuable information or solve the dual form of IKSVM whereas suffering from a dual gap problem.In this paper,we propose a primal perspective for solving the problem.That is,we directly focus on the primal form of IKSVM and present a novel algorithm termed as IKSVM-DC for binary and multi-class classification.Concretely,according to the characteristics of the spectrum for the indefinite kernel matrix,IKSVM-DC decomposes the primal function into the subtraction of two convex functions as a difference of convex functions(DC)programming.To accelerate convergence rate,IKSVM-DC combines the classical DC algorithm with a line search step along the descent direction at each iteration.Furthermore,we construct a multi-class IKSVM model which can classify multiple classes in a unified form.A theoretical analysis is then presented to validate that IKSVM-DC can converge to a local minimum.Finally,we conduct experiments on both binary and multi-class datasets and the experimental results show that IKSVM-DC is superior to other state-of-the-art IKSVM algorithms.     

基于空间句法和最短路径的图核

针对图模式识别领域中现有图核方法对反映图本身拓扑结构的节点特征挖掘不够充分的问题,提出了基于空间句法和最短路径的图核。借鉴建筑学与城市规划学科中的空间句法理论构造分布于图节点上的拓扑特征的量化描述,基于此提出了可表示、计算,正定、适用范围较广的空间句法核和基于最短路径的空间句法核,进而借助支持向量机实现了非精确图匹配。不同于其他图核方法,该方法对图的拓扑特征表达能力强,通用性较好。实验结果表明,所设计的图核在分类精度方面相较于最短路径核有较显著的改善。     

多路径高斯核模糊C均值聚类算法

聚类算法单一迭代路径限制了参数优值的搜索。提出一种多路径高斯核模糊C均值聚类算法（MGKFCMs）,MGKFCMs算法首先取核目标函数及模糊隶属度函数中的核函数为高斯核函数;然后利用梯度法得到聚类中心迭代公式,并基于该迭代公式和粒子群算法作聚类中心的并行参数迭代,在每一次聚类迭代时,选择聚类目标函数值小的路径作为参数迭代最终路径。对比分析了MGKFCMs算法的相关性质,通过仿真实验验证了所提算法的有效性。     

基于距离量度的边际核设计及应用

很多情况下,研究者掌握了一些分类数据的生成信息,这些信息能够为核函数提供有价值的分类特征.已有大量结合生成模型构造核函数的研究,边际核是其中较新的研究成果.以边际核理论为基础,在边际核特征空间中引入特征向量之间的距离作为相似性的量度,构造了基于距离量度的边际核函数.随后将它和原边际核均应用于具体的grbB(旋转酶B亚单位)氨基酸序列分类实验中,实验结果表明:基于距离量度的边际核拥有比原边际核更佳的识别效率,且也具备一定的推广能力.