最优化理论与支持向量机

最优化理论与支持向量机摘要 近几年来, 机器学习方法得到了广泛的应用, 在其理论研究和算法实现方面都取得了重大进展成为机器学习领域的前沿热点课题. 支持向量机也受到广泛的关注, 它以统计学习为基础, 建立在计算学习理论的结构风险最小化原则之上, 具有简洁的数学形式, 已成为机器学习和数据挖掘领域的主要工具. 本文主要是对最优化理论的概述以及对支持向量机的简单介绍. 通过对最优化理论与支持向量机的学习, 进一步深入研究相关理论与实验知识.关键词: 样本集 类标识 支持向量机 回归1． 最优化理论本学期主要学习了最优化的一些基本理论, 一类分类问题, 二类分类问题, 多类分类问题, 回归问题. 分类问题的主要思想是通过给定的样本集1,{()}n m i x y R R i i T =⊂⨯=寻找一个定值函数:m f R R →. 以便利用f 来判断任一输入m i x R ∈的类标识. 另外, 分类问题根据数据样本的个数可分为一类分类问题, 二类分类问题, 多类分类问题. 根据定值函数的线性和非线性性, 可分为线性分类问题和非线性分类问题. 对于分类问题研究最多的是二类分类问题和多类分类问题.近几年来, 机器学习方法得到了广泛的应用,在其理论研究和算法实现方面都取得了重大进展成为机器学习领域的前沿热点课题. 不少学者将机器学习的方法应用与机械产品寿命的预测, 而其中人工神经网络和支持向量机等方法在寿命预测中应用较多. 由于人工神经网络存在对样本数量与质量具有高依赖性, 且对于小样本情况易陷入局部最优等问题, 而以统计学理论为基础的支持向量机, 具有严格的理论和数学基础, 可以不像神经网络的结构设计需要依赖于设计者的经验知识和先验知识, 因此, 利用支持向量机理论实现趋势预测分析已成为研究新热点.基于数据的机器学习是一种重要的知识发现方法, 是人工智能最具智能特征、最前言的研究领域之一. 机器学习主要研究计算机如何模拟或实现人类的学习能力, 以获取新的知识技能, 重新组织已有的知识结构, 使之不断改善自身的性能. 机器学习是人类智能的核心问题, 是使计算机具有人工智能的根本途径, 基于数据的机器学习问题作为人工智能研究领域的一个重要方面. 其研究的主要问题是从一组观测数据集出发, 得到一些不能通过原理分析而得到的规律, 进而利用这些规律对未来数据或无法观测到的数据进行预测和分析.迄今为止, 关于机器学习还没有一种被共同接受的理论框架, 关于其实现方法大致可以分为以下三种[1].第一种是经典的统计预测方法[2]. 现有机器学习方法共同的重要理论基础之一是统计学. 在这类方法中, 模型中参数的相关形式是已知的, 用训练样本来估计参数需要已知样本的分布形式, 因此具有很大的局限性. 另外传统的统计学研究的是样本数目趋于无穷大时的渐进理论, 但在实际问题中, 样本数量却是有限的, 因此一些理论上很优秀的学习方法在实际应用中可能表现的不尽人意.第二种方法是经验非线性方法, 如人工神经网络(ANN)方法[3][4], 神经网络学习方法对于逼近实数值、离散值或向量值的目标函数提供了一种健壮性很强的方法. 对于某些类型的问题, 如学习解释复杂的现实世界中的传感器数据, 人工神经网络是目前知道的最有效的学习方法, 这种方法利用已知样本建立非线性模型, 克服了传统参数估计方法的困难, 人工神经网络已在很多的实际问题中取得了惊人的成功, 如手写识别, 图像识别, 语音识别. 但是这种方法缺少统一的教学理论, 过度拟合训练也是人工神经网络学习中的重要问题. 尽管人工神经网络对训练数据表现非常好, 过度拟合也会导致数据泛化到新的数据时性能很差.第三种方法是统计学习理论(Statistical Learning Theory, SLT)[5], 与传统的统计学习相比, SLT是一种专门研究小样本情况下机器学习规律的理论. 该理论针对小样本统计问题建立了一套新的理论体系, 在这种体系下的统计推理规则不仅考虑了对渐进性能的要求, 而且追求在现有有限信息条件下得到的最优结果.Vapnik等人从20世纪60年代开始致力于此方面的研究, 到90年代中期随着其理论的不断发展成熟, 也由于神经网络等学习方法在理论上缺乏实质性的进展, SLT开始受到越来越广泛的重视.支持向量机(SVM)[6]是Cortes和Vapnik于1995年在VC维理论和结构风险最这种小原理基础上提出的一种机器学习方法,它是借助优化方法解决机器学习问题的新工具,能够尽量提高学习机的推广能力, 即使由有限数据集得到的判别函数对独立的测试集仍能够得到较小的误差. 此外SVM是一个凸二次规划, 能够保证找到的解释全局最优解. 这些特点使SVM成为一种优秀的基于数据的机器学习方法, SVM是机器理论中最新的内容, 也是最实用的部分, 其主要内容在1992年到1995年间基本完成, 目前仍处于基本发展阶段. 可以说SLT之所以从20世纪90年代以来受到越来越多的重视,很大程度上是因为它发展出来了SVM这一通用的基于数据的机器学习方法.SVM在解决小样本、非线性及高维模式识别问题中表现出特别的优势,并能够推广到函数拟合等其他机器学习问题中. 与传统机器学习方法不同, SVM首先通过非线性变换将原始的样本空间映射到高维的特征空间,然后在这个行空间中求取最优线性分类面,而这种非线性变换是通过定义适当的内积函数实现的.SVM成功的解决了高维问题和局部极小值问题.在SVM中只要定义不同的内积函数,就可以实现多项式逼近、贝叶斯分类器、径向基函数(RBF)方法、多层感知器网络等很多现有的学习算法. 在解决高维问题中, 神经网络等方法容易陷入一个又一个局部极小值. SVM使用了大因子来控制学习机器的训练过程，使其只选择具有最大分类间隔的分类超平面. 最优超平面对线性不可分的情况引入松弛项来控制经验风险从而使其在满足分类要求的情况下具有好的推广能力, 寻找最优超平面的过程最终转化为凸二次型优化问题而得到全局最优解.SVM方法具有较好的理论基础, 在一些领域的应用中表现出来与众不同的优秀的泛化性能, 因此, SVM在解决分类、回归和密度函数估计等机器学习方面获得了非常好的效果, 并成功应用在模式识别、回归估计和概率密度函数估计等方面. 例如在模式识别方面,SVM 在手写数字识别、语音识别、文本分类、信号处理、图像分类和识别等多个领域都有不俗的表现. SVM 在精度上已经超过传统的学习算法或与之不相上下.SVM 在解决有限样本、高维模式识别、非线性等复杂问题中表现出许多特有的优势, 目前SVM 已被成功应用于识别、回归、分类问题中.2． 线性支持向量机所谓最优化技术就是找出使得目标函数值达到最小或最大的自变量值的方法. 最优化问题从其分类看有经典无约束最优化问题和有约束最优化问题.无约束极值问题的数学模型为min ()xf x 其中12[,,]T n x x x x =称为优化变量,()f ⋅函数称为目标函数, 该数学表示的含义亦即求取一组x 向量, 使得最优化目标函数()f x 为最小, 故这样的问题又称为最小化问题, 那么只需给目标函数()f x 乘以一个负号就能立即将最大化问题转换成最小化问题. 所以最优化问题研究的一般全是最小化问题.有约束最优化问题的数学模型为min ().. ()0,xf x s t G x ≤其中12[,,]T n x x x x =. 该数学表达式的含义为求取一组x 向量, 使得在满足约束条件()0G x ≤的前提下能够使目标函数()f x 最小化. 在实际遇到的最优化问题中, 有时约束条件可能是很复杂的, 它既可以是等式约束, 也可以是不等式约束; 既可以是线性的, 也可以是非线性的, 有时甚至不能用纯数学函数来描述.一般的约束问题可以既包含等式约束又包含不等式约束, 其一般形式为min ().. ()0,1,, ()0,1,,xi j f x s t c x i pc x j p p q≤===++ 这类问题称为一般约束问题其中12[,,]T n x x x x =, 称()f x 称为目标函数, 称()0,1,,, ()0,1,,i j c x i p c x j p p q ≤===++为约束条件, 并称()i c x 为约束函数.此外称满足条件的点为可行点, 并称全体可行点组成的集合为可行域. 该数学表达式的含义为求取一组x 向量, 使得在满足约束条件()0,1,,, ()0,1,,i j c x i p c x j p p q ≤===++的前提下能够使目标函数()f x 最小化.在学习过程中, 我们着重研究的是二类分类问题的支持向量机(Support Vector Machine,简称SVM), 以及在SVM 基础上得到的其他类型的支持向量机, 比如: 双生支持向量机(TSVM-Twin support vector machine)[7], 最小二乘支持向量机(LSTSVM-least square support vector machine)[8], 有界支持向量机(TBSVM-twin bound support vector machine)[9], 支持向量回归机(SVR-support vector regression)[10]等. 在二类分类问题模型基础上进行改进可得到多类分类问题的分类器.SVM 涉及到两个凸规划问题——原始问题和对偶问题, 由这两个问题的解之间的关系建立算法. 因此优化理论也是SVM 的重要理论基础.下面介绍一下经典支持向量机(SVM), 双生支持向量机(TSVM)以及支持向量回归机(SVR).2.1. 线性软间隔支持向量机设1{(,)}{1}n m i i i x y R =⊂⨯±是二类数据集, 其中i x 是行向量. 线性软间隔SVM 的基本思想是通过求解一个二次规划问题, 得到两个平行边界超平面, 进而得到分类超平面. 线性软间隔SVM 对应的原始问题为21,,1min 2.. (,)1, 0, 1,,,n i i w b i i i w C s t y w x b i n ξξξ=+<>+≥≥=∑ 其Wolfe 对偶形式为111112.. 0, 0, 1,,,min ,n n n i j i j i j i i j i n i i i i s t C i n y y x x yαααααα=====≤≤=<>-∑∑∑∑ (2.1)其中1(,,)T n n R ααα=∈是Lagrange 乘子向量. 通过求解问题(2.1), 可得分类超平面,0w x b +=<>. 具体算法如下.算法1. (线性软间隔二类SVM)步1. 给出训练集1{(,)}{1}n m i i i x y R =⊂⨯±.步2. 选择适当的参数0C >, 求解问题(2.1), 得最优解1(,,)T nααα***=⋅⋅⋅. 步3. 计算1ni i i i y x ωα**==∑. 选择α*的一个正分量0j C α*<<, 计算 1,n j i i i j i b y y x x α**==-<>∑.步4. 构造分离超平面,0x b ω**<>+=和决策函数()sgn(,)f x x b ω**=<>+.2.2. 线性双生支持向量机TSVM 的基本思想是通过求解两个二次规划问题得到两个非平行边界超平面, 进而得到两个非平行的分类超平面. TSVM 对应的原始问题为()()()()1111111112121211 min ,,2 .. ,0,T T TSVM Aw e b Aw e b c e w b s t Bw e b e ξξξξ+++-++≥≥()()()()2222222221212112 min ,,2 .. ,0,ξξξξT T TSVM Bw e b Bw e b c e w b s t Aw e b e +++++≥≥其中,A B 分别是数据样本中两类样本组成的列向量,12,e e 分别是与,A B 列数相同, 元素全为1的列向量;12,c c 是大于0的参数; ξ是松弛变量.其Wolfe 对偶形式为(简记为DTSVM1、DTSVM2)分别为()()12111 min 2.. 0,T T T T DTSVM G H H G e s t c ααααα--≤≤ (2.2) ()()11212 min 2.. 0,T T T T DTSVM G H H G e s t c αββββ--≤≤ (2.3)其中,αβ是Lagrange 乘子向量,12[ ],[ ].H A e G B e ==通过求解问题(2.2)和(2.3), 可得分类超平面110T x w b +=和220.T x w b +=算法2. (线性TSVM )步1. 给出训练集1{(,)}{1}n m i i i x y R =⊂⨯±.步2. 选择适当的参数0C >, 求解问题(1.2)和(1.3), 得最优解1(,,)T nααα***=⋅⋅⋅. 步3. 计算1ni i i i y x ωα**==∑. 选择α*的一个正分量0j C α*<<, 计算 1,n j i i i j i b y y x x α**==-<>∑.步4. 构造分离超平面,0x b ω**<>+=和决策函数()sgn(,)f x x b ω**=<>+.2.3. 线性支持向量回归机SVM 最初是为分类问题设计的, 已得到了广泛的应用. 近年来, SVM 在回归方面也表现了极好的性能. SVR 有线性回归和非线性回归, 对于线性回归, 考虑用线性回归函数估计样本数据. 和SVM 算法相似, SVR 算法最终也是转化为一个求解凸二次规划问题.线性支持向量回归机[7]的基本思想是找一个带状区域, 尽可能使数据点分布于这个带状区域中. SVR 原始问题为21,1min 2.. , 1,,, (<,>), 1,,, +(,)n i i i w b i i i i w s t y b i n w x b i n C w x y εεξη=+≤=+≤=-<>-∑（+）其中ε是大于0的参数.其Wolfe 对偶形式为()()()()()1111,112 .. 0, 01,,.min ,0, , n n n n i i j j i j i i i i i i j i i ni i i i i s t i n x x y C C αβαβαβαβεαβαβαβ======≤≤=--<>-+---≤≤∑∑∑∑∑ (2.4) 其中,αβ是Lagrange 乘子向量.通过求解问题(2.4),可得分类超平面,0.i w x b += 具体算法如下.算法3. (线性支持向量回归机)步1. 给出训练集1{(,)}{1}n m i i i x y R =⊂⨯±.步2. 选择适当的参数0,0C ε>>, 求解问题(1.4), 得最优解11(,,) (,,).T T n n αααβββ******=⋅⋅⋅=⋅⋅⋅，.步3. 计算*1()ni i i i x ωαβ**==-∑. 选择α*的一个正分量0j C α*<<, 计算*,j j b y w x ε*=-<>-,或者选择β*的一个正分量0j C β*<<, 计算*,j j b y w x ε*=-<>+ 步4. 构造决策函数(),f x x b ω**=<>+.步5. 对任一测试点n x R ∈, 其输出**(),f x w x b =<>+.此外还学习了一些多类支持向量机的模型. 如多元双生支持向量机(Multi-twin support vector machine, 简记为MTSVM), 多生支持向量机(Multiple birth support vector machine, 简记为MBSVM)等.2.4. 多元双生支持向量机(MTSVM)多元双生支持向量机是在TSVM 基础上采用了一对余的方法处理数据的, 为每一类数据利用最小二乘原理构造一个分类超平面, 使得该类数据点尽可能靠近这一超平面, 同时尽可能的排斥其它类数据. 本文中用到的数据点中的第i 类用,1,i c n i A R i c ⨯∈=表示, 剩余的其它类看作是另一类, 用()111[,,,,],1,i c c n T T T T i i i c B A A A A R i c -⨯-+=∈=表示. MTSVM 基本思想是对于c 类问题, 为每一类找到一个超平面,0,1,,.i i w x b i c <>+==使得除第i 类之外的的数据点尽可能靠近这一超平面, 同时尽可能的排斥第i 类数据.MTSVM 第i 类数据点对应的原始问题为1222,,11min22.. (B ), 0, ,1,,,i i i T i i i i j j j j i w b i i i i i i i A w e b C s t w e b e i j c ξξξξξ≠++-++≥≥=∑ 其中21()11, , 0.i i c c c i i i e R e R C ⨯-⨯∈∈>此规划的wolfe 对偶为()21111min2 .. 0,1,,,i c c T T T T i i i i i i i i i i i i G H H G e s t C i c ααααα-==-≤≤=∑∑ (2.5)其中12[,], [,].i i i i i i H A e G B e ==通过求解问题(2.5), 得到第i 类数据点对应的分类超平面,0i i w x b <>+=.具体算法如下.算法4. (MTSVM)步1. 给出训练集1{(,)}{1,,}n m i i i x y R c =⊂⨯.步2. 对每一个{1,,}i c ∈, 取,\i i X X X X X +-==.步3. 选择适当的参数0i C >, 求解问题(2.5), 得最优解1(,,),1,,.i i i T ni c ααα***=⋅⋅⋅= 步4. 令[;],i i i u w b =, 计算*1*()T i i i i i u H H G α-=-.步5. 构造分离超平面,0i i x b ω**<>+=和决策函数(),i i i f x x b ω**=<>+.步6. 对任一测试点m x R ∈, 若1()()min i k i c i f x f x w ≤≤=, 则判断x 属第k 类.2.5. 多生支持向量机(MBSVM)MBSVM 基本思想是对于c 类问题, 为每一类找到一个超平面,0,1,,.i i w x b i c <>+==使得第i 类的数据点尽可能靠近这一超平面, 同时尽可能的排斥其它类数据. MBSVM 与MTSVM 不同之处在于MBSVM 是把数据中的一类数据点放到约束条件中, 其它类点作为另一类, 放在目标函数中.MBSVM 第i 类数据点对应的原始问题为1222,,1min2.. (), 0,i i i T i i i i i i i w b i i k i i k k B w e b C e s t A w e b e ξξξξ++++≥≥ 其中12()11, , 0.i i c c c i i i e R e R C -⨯⨯∈∈>此规划的wolfe 对偶为()211min 2 .. 0,i T T T T i i i i i i i i i i G H H G e s t C ααααα--≤≤ (2.6)其中21[,], [,].i i i i i i G A e H B e == 通过求解问题(2.6)得到其中第i 类的分类超平面,0i i w x b <>+=.具体算法如下.算法6. (MBSVM)步1. 给出训练集1{(,)}{1,,}n m i i i x y R c =⊂⨯.步2. 对每一个{1,,}i c ∈, 取,\i i X X X X X +-==.步3. 选择适当的参数0i C >, 求解问题(2.6), 得最优解1(,,),1,,.i i i T ni c ααα***=⋅⋅⋅= 步4. 令[;],i i i u w b =, 计算*1*()T i i i i i u H H G α-=-.步5. 构造分离超平面,0i i x b ω**<>+=和决策函数(),i i i f x x b ω**=<>+.步6. 对任一测试点m x R ∈, 若1()()max i k i c i f x f x w ≤≤=, 则判断x 属第k 类.3． 非线性支持向量机在日常生活中遇到的分类问题, 大部分是线性不可分的问题. 对于线性不可分问题, 通过引入核函数:m m k R R R ⨯→, 利用核函数的特征映射将数据映射到高维特征空间, 使得映射后的数据是(近似)线性可分的. 常见的核函数主要有:高斯径向基核:22(,)exp{/}k x y x y σ=--或22(,)exp{/2},(0).k x y x y σσ=-->多项式核:(,)(,),(,0).d k x y x y c c R d =<>+∈> 利用核函数定义, 问题(2.1)可改进为如下11110,0,1,,.1min (,)2 .. n n n i j i j i j i i j i n i i i i C i n y y k x x s t y αααααα=====≤≤=-∑∑∑∑ (3.1)算法1可改进为算法3. (加核二类SVM)步1. 给出训练集1{(,)}{1}n m i i i x y R =⊂⨯±.步2. 选择适当的参数0C >, 求解问题(1.1), 得最优解1(,,)T nααα***=⋅⋅⋅. 步3. 计算1ni i i i y x ωα**==∑. 选择α*的一个正分量0j C α*<<, 计算 1,nj i i i j i b y y k x x α**==-<>∑.步4. 构造分离超平面,0x b ω**<>+=和决策函数()sgn(,)f x k x b ω**=<>+.利用核函数定义, 问题(2.2)和(2.3)改进为如下()()12111 min 2.. 0,T T T T DTSVM G H H G e s t c ααααα--≤≤ (3.2) ()()11212 min 2.. 0,T T T T DTSVM G H H G e s t c αββββ--≤≤ (3.3)其中,αβ是Lagrange 乘子向量, 12[(,) ], [(,) ].H K A X e G K B X e == 算法与算法2是相同的.此外还学习了一些其它支持向量机的模型, 此处不再一一列举.4. 结论近年来, 支持向量机受到广泛的关注, SVM 是在统计学习理论VC 维理论和结构风险最小原理的基础上发展起来的一种新的机器学习方法. 它以统计学习为基础, 建立在计算学习理论的结构风险最小化原则之上, 具有简洁的数学形式, 能进行直观的几何解释并具有良好的泛化能力, 避免了局部最优解, 且需要人为设定的参数较少, 便于使用, 为小样本机器学习提供了一种新方法, 以用于模式识别、回归分析和函数逼近等领域. 支持向量机已成为机器学习和数据挖掘领域的主要工具.由于它具有一些传统机器学习方法所不能匹敌的优势而成为目前国内外研究的一个热点问题, 并已成功应用于众多模式识别领域.通过学习本门课程我了解到了许多与分类相关的知识. 今后将会在此基础上不断改进, 继续学习. 随着研究的不断深入, 新问题、新思想将会不断涌现, 这必将促进SVM 方法在实际应用中发挥更大的作用.参考文献[1] F.Mulier.Vapnik-Chervonenkis(VC) learning theory and its applications. IEEE Transactions on NeuralNetwork, 1999, 10(5): 985-987.[2] 黄风岗, 宁克欧. 模式识别. 哈尔滨工业大学出版社, 1998.[3] S.Haykin. Neural networks: A comprehensive Foundation. Pearson Education Inc. 1999.[4] 高隽. 人工神经网络原理及仿真实例. 北京: 机械工业出版社, 2003.[5] 张学工. 关于统计学习理论与支持向量机. 自动化学报, 2000, 26(1): 32-42.[6] Cortes C, Vapnik V. Support-vector network. Mach Learn. Springer, 1995, 20: 273-297.[7] Jayadeva K, Khemchandani R, Chandra S. Twin support vector machines for patternclassification. IEEE Trans Pattern Anal Mach Intell. 2007, 29(5): 905-10.[8] M. Arun Kumar, M. Gopal. Least squares twin support vector machines for pattern classification. ExpertSystems with Applications. 2009.[9] Yuan-Hai Shao, Chun-Huan Zhang, Xiao-Bo Wang, Nai-Yang Deng.Improvements on twin supportvectormachines. IEEE Transactions on Neural Network, 2011.[10] Debasish Basak, Srimanta Pal, Dipak Chandia Patranabis. Support Vector Regression. 2007.。