统计学习笔记(1-7章)

基础知识：

先验概率和后验概率:

先验概率就是事情发生前的预测概率.
后验概率是一种条件概率，它限定了事件为隐变量取值，而条件为观测结果。一般的条件概率，条件和事件可以是任意的.
贝叶斯公式P(y|x) = ( P(x|y) * P(y) ) / P(x)中,P(y|x)是后验概率,P(x|y)是条件概率,P(y)是先验概率.

判别式模型和生成式模型:

判别式模型直接学习**决策函数f(X)或条件概率分布P(Y|X)**作为预测的模型.往往准确率更高,并且可以简化学习问题.如k近邻法/感知机/决策树/最大熵模型/Logistic回归/线性判别分析(LDA)/支持向量机(SVM)/Boosting/条件随机场算法(CRF)/线性回归/神经网络
生成式模型由数据学习联合概率分布P(X,Y),然后由P(Y|X)=P(X,Y)/P(X)求出条件概率分布作为预测的模型,即生成模型.当存在隐变量时只能用生成方法学习.如混合高斯模型和其他混合模型/隐马尔可夫模型(HMM)/朴素贝叶斯/依赖贝叶斯(AODE)/LDA文档主题生成模型

损失函数和风险函数:

损失函数度量模型一次预测的好坏.常用的损失函数有:0-1损失函数,平方损失函数,绝对损失函数,对数似然损失函数.
损失函数的期望是理论上模型关于联合分布P(X,Y)的平均意义下的损失,称为风险函数,也叫期望风险.但是联合分布是未知的,期望风险不能直接计算.
当样本容量N趋于无穷时经验风险趋于期望风险,但现实中训练样本数目有限.

经验风险最小化和结构风险最小化:

模型关于训练数据集的平均损失称为经验风险.经验风险最小化的策略就是最小化经验风险.当样本数量足够大时学习效果较好.比如当模型是条件概率分布,损失函数是对数损失函数时,经验风险最小化就等价于极大似然估计.但是当样本容量很小时会出现过拟合.
结构风险最小化等于正则化.结构风险在经验风险上加上表示模型复杂度的正则化项.比如当模型是条件概率分布,损失函数是对数损失函数,模型复杂度由模型的先验概率表示时,结构风险最小化就等价于最大后验概率估计.(一般是在经验风险最小化后面加上正则化项)

过拟合是指学习时选择的模型所包含的参数过多,以致于对已知数据预测得很好,但对未知数据预测很差的现象.模型选择旨在避免过拟合并提高模型的预测能力.
正则化是模型选择的典型方法.正则化项一般是模型复杂度的单调递增函数,比如模型参数向量的范数.
交叉验证是另一常用的模型选择方法,可分为简单交叉验证,K折交叉验证,留一交叉验证等.
KKT条件:通常我们要求解的最优化条件有如下三种:

无约束优化问题:通常使用求导,使导数为零,求解候选最优值
有等式约束的优化问题:通常使用拉格朗日乘子法,即把等式约束用拉格朗日乘子和优化问题合并为一个式子,通过对各个变量求导使其为零,求解候选最优值.拉格朗日乘数法其实是KKT条件在等式约束优化问题的简化版.
有不等式约束的优化问题:通常使用KKT条件.即把不等式约束,等式约束和优化问题合并为一个式子.假设有多个等式约束h(x)和不等式约束g(x),则不等式约束引入的KKT条件如下:,实质是最优解在g(x)<0区域内时,约束条件不起作用,等价于对μ置零然后对原函数的偏导数置零;当g(x)=0时与情况2相近.结合两种情况,那么只需要使L对x求导为零,使h(x)为零,使μg(x)为零三式即可求解候选最优值.

感知机

感知机是二类分类的线性模型,属于判别模型.感知机学习旨在求出将训练数据进行线性划分的分离超平面.是神经网络和支持向量机的基础.
模型:, w叫作权值向量,b叫做偏置,sign是符号函数.
感知机的几何解释:wx+b对应于特征空间中的一个分离超平面S,其中w是S的法向量,b是S的截距.S将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类.
策略:假设训练数据集是线性可分的,感知机的损失函数是误分类点到超平面S的总距离.因为误分类点到超平面S的距离是,且对于误分类的数据来说,总有成立,因此不考虑1/||w||,就得到感知机的损失函数:,其中M是误分类点的集合.感知机学习的策略就是选取使损失函数最小的模型参数.
算法:感知机的最优化方法采用随机梯度下降法.首先任意选取一个超平面w0,b0,然后不断地极小化目标函数.在极小化过程中一次随机选取一个误分类点更新w,b,直到损失函数为0.,其中η表示步长.该算法的直观解释是:当一个点被误分类,就调整w,b使分离超平面向该误分类点接近.感知机的解可以不同.
对偶形式:假设原始形式中的w0和b0均为0,设逐步修改w和b共n次,令a=nη,最后学习到的w,b可以表示为.那么对偶算法就变为设初始a和b均为0,每次选取数据更新a和b直至没有误分类点为止.对偶形式的意义在于可以将训练集中实例间的内积计算出来,存在Gram矩阵中,可以大大加快训练速度.

感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数，在这个过程中一次随机选取一个误分类点使其梯度下降

k近邻法

k近邻法根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测.k值的选择,距离度量及分类决策规则是k近邻法的三个基本要素.当k=1时称为最近邻算法.
模型:当训练集,距离度量,k值以及分类决策规则确定后,特征空间已经根据这些要素被划分为一些子空间,且子空间里每个点所属的类也已被确定.
策略:

距离:特征空间中两个实例点的距离是相似程度的反映,k近邻算法一般使用欧氏距离(L2范数),也可以使用更一般的Lp距离或Minkowski距离.
k值:k值较小时,整体模型变得复杂,容易发生过拟合.k值较大时,整体模型变得简单.在应用中k一般取较小的值,通过交叉验证法选取最优的k.
分类决策规则:k近邻中的分类决策规则往往是多数表决,多数表决规则等价于经验风险最小化.

算法:根据给定的距离度量,在训练集中找出与x最邻近的k个点,根据分类规则决定x的类别y.
kd树:

kd树就是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构.kd树更适用于训练实例数远大于空间维数时的k近邻搜索.(类似二叉搜索树)
构造:可以通过如下递归实现:在超矩形区域上选择一个坐标轴和此坐标轴上的一个切分点,确定一个超平面,该超平面将当前超矩形区域切分为两个子区域.在子区域上重复切分直到子区域内没有实例时终止.通常依次选择坐标轴和选定坐标轴上的中位数点为切分点,这样可以得到平衡kd树.
搜索:从根节点出发,若目标点x当前维的坐标小于切分点的坐标则移动到左子结点,否则移动到右子结点,直到子结点为叶结点为止.以此叶结点为”当前最近点”,递归地向上回退,在每个结点:(a)如果该结点比当前最近点距离目标点更近,则以该结点为”当前最近点”(b)”当前最近点”一定存在于该结点一个子结点对应的区域,检查该结点的另一子结点对应的区域是否与以目标点为球心,以目标点与”当前最近点”间的距离为半径的超球体相交.如果相交,移动到另一个子结点,如果不相交,向上回退.持续这个过程直到回退到根结点,最后的”当前最近点”即为最近邻点.

朴素贝叶斯

朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法.首先学习输入/输出的联合概率分布,然后基于此模型,对给定的输入x,利用贝叶斯定理求出后验概率最大的输出y.属于生成模型.(个人认为有点太偏数学计算)
模型:首先学习先验概率分布,然后学习条件概率分布.如果估计实际,需要指数级的计算,所以朴素贝叶斯法对条件概率分布作了条件独立性的假设,上式变成.在分类时,通过学习到的模型计算后验概率分布,由贝叶斯定理得到,将条件独立性假设得到的等式代入,并且注意到分母都是相同的,所以得到朴素贝叶斯分类器:
朴素贝叶斯将实例分到后验概率最大的类中,这等价于期望风险最小化.
算法:使用极大似然估计法估计相应的先验概率和条件概率,计算条件独立性假设下的实例各个取值的可能性,选取其中的最大值作为输出.
用极大似然估计可能会出现所要估计的概率值为0的情况,在累乘后会影响后验概率的计算结果,使分类产生偏差.可以采用贝叶斯估计,在随机变量各个取值的频数上赋予一个正数..Sj为j属性可能取值数量,当λ=0时就是极大似然估计.常取λ=1,称为拉普拉斯平滑.
如果是连续值的情况,可以假设连续变量服从高斯分布,然后用训练数据估计参数.

决策树

决策树是一种基本的分类与回归方法.它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布.主要优点是模型具有可读性,分类速度快.
模型:分类决策树由结点和有向边组成.结点分为内部结点(表示一个特征或属性)和叶结点(表示一个类).决策树的路径具有互斥且完备的性质.
策略:决策树学习本质上是从训练数据集中归纳出一组分类规则.我们需要的是一个与训练数据矛盾较小,同时具有很好的泛化能力的决策树.从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中常采用启发式方法近似求解.
算法:决策树学习算法包含特征选择,决策树的生成与决策树的剪枝过程.生成只考虑局部最优,剪枝则考虑全局最优.
特征选择:如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的.扔掉这样的特征对决策树学习的精度影响不大.

信息熵:熵是衡量随机变量不确定性的度量.熵越大,随机变量的不确定性就越大.信息熵是信息量的期望.条件熵表示在已知随机变量X的条件下随机变量Y的不确定性.
信息增益:表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.定义为集合D的经验熵与特征A在给定条件下D的经验条件熵之差,也就是训练数据集中类与特征的互信息.
信息增益算法:计算数据集D的经验熵,计算特征A对数据集D的经验条件熵,计算信息增益,选取信息增益最大的特征.
信息增益比:信息增益值的大小是相对于训练数据集而言的,并无绝对意义.使用信息增益比可以对这一问题进行校正.

决策树的生成:

ID3算法:核心是在决策树各个结点上应用信息增益准则选择信息增益最大且大于阈值的特征,递归地构建决策树.ID3相当于用极大似然法进行概率模型的选择.由于算法只有树的生成,所以容易产生过拟合.
C4.5算法:C4.5算法与ID3算法相似,改用信息增益比来选择特征.

决策树的剪枝:

在学习时过多考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,产生过拟合现象.解决方法是对已生成的决策树进行简化,称为剪枝.
设树的叶结点个数为|T|,每个叶结点有Nt个样本点,其中k类样本点有Ntk个,剪枝往往通过极小化决策树整体的损失函数来实现,其中经验熵.剪枝通过加入a|T|项来考虑模型复杂度,实际上就是用正则化的极大似然估计进行模型选择.
剪枝算法:剪去某一子结点,如果生成的新的整体树的损失函数值小于原树,则进行剪枝,直到不能继续为止.具体可以由动态规划实现.

CART算法:

CART既可以用于分类也可以用于回归.它假设决策树是二叉树,内部结点特征的取值为”是”和”否”.递归地构建二叉树,对回归树用平方误差最小化准则,对分类数用基尼指数最小化准则.
回归树的生成:在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域.选择第j个变量和它取的值s作为切分变量和切分点,并定义两个区域,遍历变量j,对固定的j扫描切分点s,求解.用选定的对(j,s)划分区域并决定相应的输出值,直到满足停止条件.
基尼指数:假设有K个类,样本属于第k类的概率为pk,则概率分布的基尼指数为,表示不确定性.在特征A的条件下集合D的基尼指数定义为,表示分割后集合D的不确定性.基尼指数越大,样本集合的不确定性也就越大. *基尼指数是信息熵中﹣logP在P=1处一阶泰勒展开后的结果*
分类树的生成:从根结点开始,递归进行以下操作:设结点的训练数据集为D,对每个特征A和其可能取的每个值a,计算A=a时的基尼指数,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点,生成两个子结点,直至满足停止条件.停止条件一般是结点中的样本个数小于阈值,或样本集的基尼指数小于阈值,或没有更多特征.
CART剪枝:
Tt表示以t为根结点的子树,|Tt|是Tt的叶结点个数.可以证明当时,Tt与t有相同的损失函数值,且t的结点少,因此t比Tt更可取,对Tt进行剪枝.自下而上地对各内部结点t计算,并令a=min(g(t)),自上而下地访问内部节点t,如果有g(t)=a,进行剪枝,并对t以多数表决法决定其类,得到子树T,如此循环地生成一串子树序列,直到新生成的T是由根结点单独构成的树为止.利用交叉验证法在子树序列中选取最优子树.

如果是连续值的情况,一般用二分法作为结点来划分.

logistic回归和最大熵模型

逻辑斯谛分布:分布函数f(x)以点(μ,1/2)为中心对称,γ的值越小,曲线在中心附近增长得越快.
逻辑斯谛回归模型:对于给定的输入x,根据和计算出两个条件概率值的大小,将x分到概率值较大的那一类.将偏置b加入到权值向量w中,并在x的最后添加常数项1,得到和.如果某事件发生的概率是p,则该事件发生的几率(此处几率指该事件发生概率与不发生概率之比)是p/1-p,对数几率是log(p/1-p),那么,也就是说在逻辑斯谛回归模型中,输出Y=1的对数几率是输入x的线性函数,线性函数值越接近正无穷,概率值就越接近1,反之则越接近0.
似然估计:给定x的情况下参数θ是真实参数的可能性.
模型参数估计:对于给定的二分类训练数据集,对数似然函数为,也就是损失函数.其中P(Y=1|x)=π(x),对L(w)求极大值,就可以得到w的估计值.问题变成了以对数似然函数为目标函数的最优化问题.
多项逻辑斯谛回归: 当问题是多分类问题时,可以作如下推广:设Y有K类可能取值,,,实际上就是one-vs-all的思想,将其他所有类当作一个类,问题转换为二分类问题.
最大熵原理:学习概率模型时,在所有可能的概率模型中,熵最大的模型是最好的模型.直观地,最大熵原理认为模型首先要满足已有的事实,即约束条件.在没有更多信息的情况下,那些不确定的部分都是”等可能的“.
最大熵模型:给定训练数据集,可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布,其中v表示频数,N表示样本容量.用特征函数f(x,y)=1描述x与y满足某一事实,可以得到特征函数关于P(X,Y)的经验分布的期望值和关于模型P(Y|X)与P(X)的经验分布的期望值,假设两者相等,就得到了约束条件.定义在条件概率分布P(Y|X)上的条件熵为,则条件熵最大的模型称为最大熵模型.
最大熵模型的学习就是求解最大熵模型的过程.等价于约束最优化问题,将求最大值问题改为等价的求最小值问题.引入拉格朗日乘子将原始问题转换为无约束最优化的对偶问题.首先求解内部的极小化问题,即求L(P,W)对P(y|x)的偏导数,并令偏导数等于0,解得.可以证明对偶函数等价于对数似然函数,那么对偶函数极大化等价于最大熵模型的极大似然估计.之后可以用最优化算法求解得到w.
最大熵模型与逻辑斯谛回归模型有类似的形式,它们又称为对数线性模型.模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计.
算法:似然函数是光滑的凸函数,因此多种最优化方法都适用.

改进的迭代尺度法(IIS):假设当前的参数向量是w,如果能找到一种方法w->w+δ使对数似然函数值变大,就可以重复使用这一方法,直到找到最大值.
逻辑斯谛回归常应用梯度下降法,牛顿法或拟牛顿法.

两个都是模型，类似Relu和sigmoid函数

支持向量机

模型:支持向量机(SVM)是一种二类分类模型.它的基本模型是定义在特征空间上的间隔最大的线性分类器.支持向量机还包括核技巧,使它成为实质上的非线性分类器.分离超平面,分类决策函数.
策略:间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题. (二次规划：在限制田间Ax<=b的条件下，找一个n维的向量x，使得fx=1/2 X转置QX+C转置X为最小 凸二次规划：凸二次函数的二次规划)
当训练数据线性可分时,通过硬间隔最大化,学习出线性可分支持向量机.当训练数据近似线性可分时,通过软间隔最大化,学习出线性支持向量机.当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机.
核技巧:当输入空间为欧式空间或离散集合,特征空间为希尔伯特空间时,核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积.通过核函数学习非线性支持向量机等价于在高维的特征空间中学习线性支持向量机.这样的方法称为核技巧.
考虑一个二类分类问题,假设输入空间与特征空间为两个不同的空间,输入空间为欧氏空间或离散集合,特征空间为欧氏空间或希尔伯特空间.支持向量机都将输入映射为特征向量,所以支持向量机的学习是在特征空间进行的.
支持向量机的最优化问题一般通过对偶问题化为凸二次规划问题求解,具体步骤是将等式约束条件代入优化目标,通过求偏导求得优化目标在不等式约束条件下的极值.
线性可分支持向量机:

当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开.利用间隔最大化得到唯一最优分离超平面和相应的分类决策函数称为线性可分支持向量机.
函数间隔:一般来说,一个点距离分离超平面的远近可以表示分类预测的确信程度.在超平面确定的情况下,|wx+b|能够相对地表示点x距离超平面的远近,而wx+b与y的符号是否一致能够表示分类是否正确.所以可用来表示分类的正确性及确信度,这就是函数间隔.注意到即使超平面不变,函数间隔仍会受w和b的绝对大小影响.
几何间隔:一般地,当样本点被超平面正确分类时,点x与超平面的距离是,其中||w||是w的l2范数.这就是几何间隔的定义.定义超平面关于训练数据集T的几何间隔为超平面关于T中所有样本点的几何间隔之最小值.可知,当||w||=1时几何间隔和函数间隔相等.
硬间隔最大化:对线性可分的训练集而言,这里的间隔最大化又称为硬间隔最大化.直观解释是对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类.求最大间隔分离超平面即约束最优化问题:
将几何间隔用函数间隔表示,并且注意到函数间隔的取值并不影响最优化问题的解,不妨令函数间隔=1,并让最大化1/||w||等价为最小化||w||^2/2,问题变为凸二次规划问题.
支持向量和间隔边界:与分离超平面距离最近的样本点的实例称为支持向量.支持向量是使最优化问题中的约束条件等号成立的点.因此对y=+1的正例点和y=-1的负例点,支持向量分别在超平面H1:wx+b=+1和H2:wx+b=-1.H1和H2平行,两者之间形成一条长带,长带的宽度称为间隔,H1和H2称为间隔边界.在决定分离超平面时只有支持向量起作用,所以支持向量机是由很少的”重要的”训练样本确定的.由对偶问题同样可以得到支持向量一定在间隔边界上.
对偶算法: 引进拉格朗日乘子,定义拉格朗日函数,根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:.先求对w,b的极小值.将L(w,b,a)分别对w,b求偏导数并令其等于0,得,代入拉格朗日函数得

,这就是极小值.接下来对极小值求对a的极大,即是对偶问题.

将求极大转换为求极小.由KKT条件成立得到,其中j为使aj*>0的下标之一.所以问题就变为求对偶问题的解a*,再求得原始问题的解w*,b*,从而得分离超平面及分类决策函数可以看出w和b都只依赖训练数据中ai*>0的样本点(xi,yi),这些实例点xi被称为支持向量.

线性支持向量机:

如果训练数据是线性不可分的,那么上述方法中的不等式约束并不能都成立,需要修改硬间隔最大化,使其成为软间隔最大化.
线性不可分意味着某些特异点不能满足函数间隔大于等于1的约束条件,可以对每个样本点引进一个松弛变量,使函数间隔加上松弛变量大于等于1,约束条件变为,同时对每个松弛变量,支付一个代价,目标函数变为,其中C>0称为惩罚参数,C值越大对误分类的惩罚也越大.新目标函数包含了两层含义:使间隔尽量大,同时使误分类点的个数尽量小.
软间隔最大化:学习问题变成如下凸二次规划问题:
可以证明w的解是唯一的,但b的解存在一个区间.线性支持向量机包含线性可分支持向量机,因此适用性更广.
对偶算法: 原始问题的对偶问题是,构造拉格朗日函数,先求对w,b,ξ的极小值,分别求偏导并令导数为0,得,代入原函数,再对极小值求a的极大值,得到,
利用后三条约束消去μ,再将求极大转换为求极小,得到对偶问题.
由KKT条件成立可以得到,j是满足0<aj*<C的下标之一.问题就变为选择惩罚参数C>0,求得对偶问题(凸二次规划问题)的最优解a*,代入计算w和b,求得分离超平面和分类决策函数.因为b的解并不唯一,所以实际计算b时可以取所有样本点上的*平均值.
支持向量:在线性不可分的情况下,将对应与ai*>0的样本点(xi,yi)的实例点xi称为支持向量.软间隔的支持向量或者在间隔边界上,或者在间隔边界与分类超平面之间,或者再分离超平面误分一侧.
合页损失函数:可以认为是0-1损失函数的上界,而线性支持向量机可以认为是优化合页损失函数构成的目标函数.

非线性支持向量机:

如果分类问题是非线性的,就要使用非线性支持向量机.主要特点是使用核技巧.
非线性分类问题:用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间,然后在新空间里用线性分类学习方法从训练数据中学习分类模型.
核函数:设X是输入空间(欧式空间的子集或离散集合),H为特征空间(希尔伯特空间),一般是高维甚至无穷维的.如果存在一个从X到H的映射使得对所有x,z属于X,函数K(x,z)满足条件,点乘代表内积,则称K(x,z)为核函数.
核技巧:基本思想是通过一个非线性变换将输入空间对应于一个特征空间,使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机).在学习和预测中只定义核函数K(x,z),而不显式地定义映射函数.对于给定的核K(x,z),特征空间和映射函数的取法并不唯一.注意到在线性支持向量机的对偶问题中,目标函数和决策函数都只涉及输入实例与实例之间的内积,xixj可以用核函数K(xi,xj)=Ф(xi)Ф(xj)来代替.当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型.在实际应用中,往往依赖领域知识直接选择核函数.
正定核:通常所说的核函数是指正定核函数.只要满足正定核的充要条件,那么给定的函数K(x,z)就是正定核函数.设K是定义在XX上的*对称函数,如果任意xi属于X,K(x,z)对应的Gram矩阵是半正定矩阵,则称K(x,z)是正定核.这一定义在构造核函数时很有用,但要验证一个具体函数是否为正定核函数并不容易,所以在实际问题中往往应用已有的核函数.
算法:选取适当的核函数K(x,z)和适当的参数C,将线性支持向量机对偶形式中的内积换成核函数,构造并求解最优化问题,选择最优解a的一个正分量0<aj<C计算,构造决策函数.

常用核函数:

多项式核函数(polynomial kernel function):,对应的支持向量机是一个p次多项式分类器,分类决策函数为.
高斯核函数(Gaussian krenel function):,对应的支持向量机是高斯径向基函数(RBF)分类器.分类决策函数为.
字符串核函数(string kernel function): 核函数不仅可以定义在欧氏空间上,还可以定义在离散数据的集合上.字符串核函数给出了字符串中长度等于n的所有子串组成的特征向量的余弦相似度.

序列最小最优化(SMO)算法:

SMO是一种**快速求解凸二次规划问题*的算法.基本思路是:如果所有变量都满足此优化问题的KKT条件,那么解就得到了.否则,选择两个变量*,固定其他变量,针对这两个变量构建一个二次规划问题.不断地将原问题分解为子问题并对子问题求解,就可以求解原问题.注意子问题两个变量中只有一个是自由变量**,另一个由等式约束确定.
两个变量二次规划的求解方法:假设选择的两个变量是a1,a2,其他变量是固定的,于是得到子问题,ε是常数,目标函数式省略了不含a1,a2的常数项.考虑不等式约束和等式约束,要求的是目标函数在一条平行于对角线的线段上的最优值,问题变为单变量的最优化问题.假设初始可行解为aold,最优解为anew,考虑沿着约束方向未经剪辑的最优解anew,unc(即未考虑不等式约束).对该问题求偏导数,并令导数为0,代入原式,令,得到,经剪辑后a2的解是,L与H是a2new所在的对角线段端点的界.并解得.
变量的选择方法:在每个子问题中选择两个变量优化,其中至少一个变量是违反KKT条件的.第一个变量的选取标准是违反KKT条件最严重的样本点,第二个变量的选取标准是希望能使该变量有足够大的变化,一般可以选取使对应的|E1-E2|最大的点.在每次选取完点后,更新阈值b和差值Ei.