论文总字数：38589字

摘 要

核方法是机器学习中卓有成效的统计学习技术，是改善学习器解决非线性问题能力的核心方法。但囿于传统的统计学习理论，大多数核方法都要求核矩阵半正定。然而在诸多现实应用场景中，使用不定核通常能获得更好的性能。因此，不定核支持向量机(IKSVM)在机器学习领域中正逐渐受到人们的重视。

不定核支持向量机与传统支持向量机所不同的地方在于，它本质上是一个非凸优化问题。当前业界领先的算法大致可以归结于两种策略：直接改变不定核矩阵的特征谱；解决不定核支持向量机的非凸对偶问题。但这些策略都或多或少地改变了不定核本身，因此可能会导致一些与核相关的重要信息丢失，进而影响算法性能。

在本课题中，我们直接把研究重点聚焦于不定核支持向量机的非凸主问题，并且提出了名为IKSVM-DC的新型算法。根据不定核矩阵谱的特点，算法把要优化的非凸目标函数分解为两个凸函数之差的形式，然后将其重构为能被凸差算法(DCA)求解的凸差规划问题(DCP)。为了加速算法收敛，IKSVM-DC在每一轮迭代中，进一步将经典凸差算法和Armijo线搜索方法相结合。我们还会给出一个用来证明算法能够收敛到局部最小值的理论分析。最后，在大量国际标准数据集上的系统性实验表明，IKSVM-DC比当今业界领先的不定核支持向量机算法还要表现得更加优秀。

关键词：不定核支持向量机，凸差规划，核方法，非凸主问题

Abstract

Kernel method is a highly effective technique in machine learning and a core way to improve the ability of learner to solve the nonlinear learning problems. Due to the limitation of traditional statistical learning theory, most of kernel methods require the corresponding kernel matrix to be symmetric and positive semi-definite. Nevertheless, in many practical applications, indefinite kernels ordinarily get better performance. Consequently, indefinite kernel support vector machine (IKSVM) has recently attracted increasing attentions in machine learning.

Different from traditional support vector machines, indefinite kernel support vector machine essentially is a non-convex optimization problem. The state-of-the-art related algorithms generally fall into two categories: directly change the spectrum of the indefinite kernel matrix; aim to solve the dual form of indefinite kernel support vector machine. However, these strategies change the indefinite kernel more or less, which most probably lead to the loss of some important information related to the kernel, and then affect the algorithm performance.

The proposed novel algorithm termed as IKSVM-DC directly focus on the non-convex primal form of indefinite kernel support vector machine. According to the properties of the spectrum for the indefinite kernel matrix, the proposed algorithm decomposes the non-convex objective function into the subtraction of two convex functions and thus reformulates the primal problem as a difference of convex functions programming (DCP) which can be optimized by the difference of convex functions algorithm (DCA). For the sake of higher convergence rate of algorithm, IKSVM-DC further combines the difference of convex functions algorithm with an Armijo line search step at each iteration. We will present a theoretical analysis to validate that our method can converge to a local minimum. Systematical experiments on massive international standard datasets demonstrate the superiority of IKSVM-DC compared to the state-of-the-art related algorithms.

KEY WORDS: Indefinite kernel support vector machine, Difference of convex functions programming, Kernel method, Non-convex primal problem

目 录

摘 要 I

Abstract II

第一章 绪论 1

1.1 研究背景及意义 1

1.1.1 不定核支持向量机 1

1.1.2 凸差规划 2

1.2 研究现状及局限性 3

1.2.1 谱变换 3

1.2.2 对偶问题 4

1.3 研究动机及目标 4

第二章 支持向量机 6

2.1 支持向量机模型 6

2.1.1 最大间隔分类器 6

2.1.2 软间隔支持向量机 8

2.1.3 核方法 8

2.2 从主问题求解支持向量机 9

2.2.1 表示定理 9

2.2.2 求解主问题 9

2.3 从对偶问题求解支持向量机 10

2.3.1 拉格朗日乘子法和对偶理论 10

2.3.2 求解对偶问题 11

2.4 对偶间隔 13

第三章 基于凸差规划的不定核支持向量机 16

3.1 不定核支持向量机主问题 16

3.1.1 再生核Kreǐn空间与推广表示定理 16

3.1.2 再生核Kreǐn空间中的不定核主问题 17

3.2 基于凸差规划的不定核支持向量机 18

3.2.1 凸差规划 18

3.2.2 不定核主问题转化为凸差规划问题 18

第四章 理论分析 22

4.1 迭代过程可减小目标函数值 22

4.2 解序列包含目标函数梯度信息 23

4.3 算法收敛至局部最优解 23

第五章 实验验证 25

5.1 实验方案 25

5.2 实验结果 26

第六章 总结与展望 30

6.1 总结 30

6.2 展望 30

致 谢 32

参考文献 33

绪论

支持向量机以其深厚的理论背景和独到的应用优势成为机器学习中非常重要的基础模型。为了使模型更加适应于实际问题的具体需要，更好地结合问题先验知识，支持向量机通常会与不定核方法相结合。与当前主流的不定核支持向量机算法有所不同，我们尝试直接把研究重点聚焦在不定核支持向量机的非凸主问题上，从全新的视角进一步开展对不定核支持向量机的研究工作，设计出性能卓越的新型算法。

在本章中，我们首先简要介绍本课题的相关研究背景及其意义，对不定核支持向量机和凸差规划进行必要的说明。然后，我们会分析当前业界顶尖相关算法的研究现状和局限性，诸如谱变换、正定核替代以及非凸对偶问题求解等方法。最后，我们会提出本次研究工作的动机和目标。

研究背景及意义

不定核支持向量机

支持向量机(Support Vector Machine, SVM)是机器学习领域中举足轻重的监督学习模型。它在解决高维模式识别问题中有许多独到的优势，并且非常适合于解决小样本问题，在诸多应用领域中都已经大放异彩。支持向量机模型建立在VC维理论以及结构风险最小化原理的基础之上。它可以利用较少的样本信息，就能在模型复杂度和学习能力之间寻求最佳折中，从而获得较优的拟合和泛化能力。

剩余内容已隐藏，请支付后下载全文，论文总字数：38589字