Data-adaptive Kernel Learning And Its Applications

This thesis investigates kernel methods,a significant nonlinear approach in machine learning.Kernel methods have been extensively used in a variety of machine learning tasks such as classification,clustering,and dimensionality reduction.The key question in kernel methods is to develop or learn a flexible kernel to fit the data.This thesis mainly focuses on three important aspects of kernel learning:nonparametric kernel learning,indefinite kernel learning,and kernel approximation in large scale situations.It includes approximation analysis of learning algorithms,similarity algorithm design,and applications to visual tracking.The contributions of this thesis are listed as follows.We present a data-adaptive nonparametric kernel learning framework.In model formulation,we directly impose an adaptive matrix on the kernel/Gram matrix in an entry-wise strategy.Since we do not specify the formulation of the adaptive matrix,each entry in the adaptive matrix can be directly and flexibly learned from the data.Specifically,the proposed kernel learning framework can be seamlessly embedded to support vector machines?SVM?and support vector regression?SVR?,which has the capability of enlarging the margin between classes and reducing the model generalization error.Theoretically,we demonstrate that the objective function of our model embedded in SVM/SVR is gradient-Lipschitz continuous.Thereby,the training process for kernel and parameter learning in SVM/SVR can be efficiently optimized in a unified framework.Further,to address the scalability issue in nonparametric kernel learning framework,we conduct a decomposition-based scalable approach for our model with theoretical guarantees and experimental validation.Experimentally,the proposed nonparametric kernel learning model embedded in SVM/SVR achieves encouraging performance on various classification and regression benchmark datasets when compared with other representative kernel learning based algorithms.To address out-of-sample extensions in nonparametric kernel learning,i.e.,just obtains the similarity values but the kernel function is unknown,this thesis aims to learn an underlying kernel function for an arbitrary given kernel matrix.To be specific,the out-of-sample extension issue is formulated as a regression problem in a new hyper-reproducing kernel Kre??n spaces?hyper-RKKS?,which can be solved by the derived kernel ridge regression?KRR?and support vector regression?SVR?in this space.Theoretically,we devise the estimated learning rate of these two regularized regression algorithms in this space.Experimental results on several benchmarks suggest that the proposed method is able to learn a kernel function from an arbitrary given kernel matrix with the state-of-the-art performance.Since we cannot predict the underlying kernel is positive definite or indefinite in out-of-sample extensions,this paper investigates indefinite kernel learning in details and builds an indefinite kernel learning framework for kernel logistic regression.The pro-posed model is analysed in the Reproducing Kernel Kre??n Spaces?RKKS?and then becomes non-convex.Using the positive decomposition of a non-positive definite ker-nel,the derived model can be decomposed into the difference of two convex functions.Accordingly,a concave-convex procedure is introduced to solve the non-convex optimiza-tion problem.Since the concave-convex procedure?CCCP?has to solve a sub-problem in each iteration,we propose a concave-inexact-convex procedure?CCICP?algorithm to accelerate the solving process with theoretical guarantees.Specifically,we study the asymptotical properties of least squares regularized regression with indefinite kernels in RKKS.We modify the traditional error decomposition technique,prove asymptotical convergence results for the introduced hypothesis error based on matrix perturbation the-ory,and derive learning rates of such problem in RKKS.Experimental results on several benchmarks suggest that the proposed model performs favorably against the standard?positive-definite?kernel logistic regression and other competitive indefinite learning based algorithms.For indefinite kernel learning,we need to conduct eigenvalue decomposition for an indefinite kernel matrix,which makes it infeasible to large scale situations.The traditional kernel approximation method,random Fourier features?RFF?,requires the shift-invariant property and the positive definiteness on the kernel.The condition is too strict and excludes many kernels including indefinite kernels and dot-product kernels such as polynomial kernels.To consider the scalability for these kernels in large scale situations,we propose a double variational Bayesian framework in RFF,by placing the Dirichlet process prior on the spectral distribution of random features.By doing so,our model takes full advantage of high flexibility on the number of components and has capability of approximating an arbitrary kernel on a wide scale.In model inference,an efficient variational method is devised for parameter estimation by incorporating the merits of stochastic variational inference and non-conjugate variational inference,which makes the variational method quite efficient.Experimental results demonstrate the effectiveness of our nonparametric Bayesian model for kernel approximation.Further,its application to classification tasks shows that our method outperforms other representative random feature mapping based algorithms on various classification benchmark datasets.Based on the above analyses on kernel methods,we apply kernel methods to visual tracking in computer vision.This paper proposes a kernelized multiple nonnegative cod-ing model for robust visual tracking.By the kernel mapping,our model breaks through the restriction that a candidate should be represented by a dictionary in a linear combi-nation scheme,and accordingly exploits its nonlinear representation ability for tracking.This paper also introduces an ensemble strategy with a series of local dictionaries to comprehensively exploit the appearance information carried by all the constituted dic-tionaries.The weights of these dictionaries are automatically learned from the unified optimization framework.Specifically,the existing methods explicitly impose the nonneg-ative constraint to coefficient vectors,but in the proposed model,we directly deploy an efficient?₂norm regularization to achieve the similar nonnegative purpose with theoreti-cal guarantees to accelerate the solving process.Experimental results on Object Tracking Benchmark demonstrate that our tracker is able to achieve promising performance when compared to other representative methods.