做网站销售的话术,网络广告策划方案,购买网站空间的方法,婚纱网站建设一、1.感知机模型#xff1a;感知器模型是SVM、神经网络、深度学习等算法的基础;感知器模型就是试图找到一条直线#xff0c;能够把所有的“1”类和“-1”类分隔开#xff0c;如果是高维空间中#xff0c;感知器模型寻找的就是一个超平面#xff0c;能够把所有的二元类别分…一、1.感知机模型感知器模型是SVM、神经网络、深度学习等算法的基础;感知器模型就是试图找到一条直线能够把所有的“1”类和“-1”类分隔开如果是高维空间中感知器模型寻找的就是一个超平面能够把所有的二元类别分割开。感知器模型的前提是数据是线性可分的。目标是找到一个超平面即 感知器模型为: 感知器模型正确分类预测和实际类别一致yθx0y为实际值θx为预测值错误分类预测和实际类别不一致yθx0所以我们可以定义我们的损失函数为期望使分类错误的所有样本(k条样本)到超平面的距离之和最小。 即 (去绝对值符号分类错误0,分子加”—“)简化损失函数因为此时分子和分母中都包含了θ值当分子扩大N倍的时候分母也会随之扩大也就是说分子和分母之间存在倍数关系所以可以固定分子或者分母为1然后求另一个即分子或者分母的倒数的最小化作为损失函数简化后的损失函数为分母为1: (即 ,分子分母相抵消模长对结果无影响)。 直接使用梯度下降法就可以对损失函数求解不过由于这里的k是分类错误的样本点集合不是固定的所以我们不能使用批量梯度下降法(BGD)求解只能使用随机梯度下降(SGD)或者小批量梯度下降(MBGD)一般在感知器模型中使用SGD来求解。二、1.SVM(支持向量机)支持向量机(Support Vecor Machine, SVM)本身是一个二元分类算法是对感知器算法模型的一种扩展现在的SVM算法支持线性分类和非线性分类的分类应用并且也能够直接将SVM应用于回归应用中同时通过OvR或者OvO的方式我们也可以将SVM应用在多元分类领域中。在不考虑集成学习算法不考虑特定的数据集的时候在分类算法中SVM可以说是特别优秀的。 在感知器模型中算法是在数据中找出一个划分超平面让尽可能多的数据分布在这个平面的两侧从而达到分类的效果但是在实际数据中这个符合我们要求的超平面是可能存在多个的。SVM思想在感知器模型中我们可以找到多个可以分类的超平面将数据分开并且优化时希望所有的点(预测正确的点)都离超平面尽可能的远但是实际上离超平面足够远的点基本上都是被正确分类的所以这个是没有意义的反而比较关心那些离超平面很近的点这些点比较容易分错。所以说我们只要让离超平面比较近的点尽可能的远离这个超平面那么我们的模型分类效果应该就会比较不错。SVM其实就是这个思想。名词概念 线性可分(Linearly Separable)在数据集中如果可以找出一个超平面将两组数据分开那么这个数据集叫做线性可分数据。 线性不可分(Linear Inseparable)在数据集中没法找出一个超平面能够将两组数据分开那么这个数据集就叫做线性不可分数据。 分割超平面(Separating Hyperplane)将数据集分割开来的直线/平面叫做分割超平面。支持向量(Support Vector)离分割超平面最近的那些点叫做支持向量。 间隔(Margin)支持向量数据点到分割超平面的距离称为间隔。支持向量到超平面的距离为在SVM中支持向量到超平面的函数距离一般设置为1∵ ∵ ∴ SVM模型是让所有的分类点在各自类别的支持向量远离超平面的一侧同时要求支持向量尽可能的远离这个超平面用数学公式表示如下W^{T}(w_1,w_2,...,w_n)(s.t: 指”受限制于...“) (对偶问题则SVM原始目标函数/损失函数为 将此时的目标函数和约束条件使用KKT条件转换为拉格朗日函数从而转换为无约束的优化函数。引入拉格朗日乘子后优化目标变成g(x)小于等于0 当L取最大值 g(x)等于0 消去g(x) KKT条件分析 根据拉格朗日对偶化特性将该优化目标转换为等价的对偶问题来求解从而优化目标变成所以对于该优化函数而言可以先求优化函数对于w和b的极小值然后再求解对于拉格朗日乘子β的极大值。 首先求让函数L极小化的时候w和b的取值这个极值可以直接通过对函数L分别求w和b的偏导数得到将求解出来的w和b带入优化函数L中定义优化之后的函数如下 通过对w、b极小化后我们最终得到的优化函数只和β有关所以此时我们可以直接极大化我们的优化函数得到β的值从而可以最终得到w和b的值。β值的求解使用SMO算法 假设存在最优解β* 根据w、b和β的关系可以分别计算出对应的w值和b值(一般使用所有支持向量的计算均值来作为实际的b值) 这里的(xs,ys)即支持向量根据KKT条件中的对偶互补条件(松弛条件约束)支持向量必须满足一下公式2.线性可分SVM算法流程输入线性可分的m个样本数据{(x1,y1),(x2,y2),...,(xm,ym)}其中x为n维的特征向量y为二元输出取值为1或者-1SVM模型输出为参数w、b以及分类决策函数。构造约束优化问题使用SMO算法求出上式优化中对应的最优解β* 找出所有的支持向量集合S; 更新参数w*、b*的值构建最终的分类器3.线性可分SVM总结 1. 要求数据必须是线性可分的 2. 纯线性可分的SVM模型对于异常数据的预测可能会不太准 3. 对于线性可分的数据线性SVM分类器的效果非常不错。三、1.SVM的软间隔模型 线性可分SVM中要求数据必须是线性可分的才可以找到分类的超平面但是有的时候线性数据集中存在少量的异常点由于这些异常点导致了数据集不能够线性划分直白来讲就是正常数据本身是线性可分的但是由于存在异常点数据导致数据集不能够线性可分 如果线性数据中存在异常点导致没法直接使用SVM线性分割模型的时候我们可以通过引入软间隔的概念来解决这个问题 硬间隔可以认为线性划分SVM中的距离度量就是硬间隔在线性划分SVM中要求函数距离一定是大于1的最大化硬间隔条件为 软间隔SVM对于训练集中的每个样本都引入一个松弛因子(ξ)使得函数距离加上松弛因子后的值是大于等于1这表示相对于硬间隔对样本到超平面距离的要求放松了。(引入松弛因子(ξ)) 松弛因子(ξ)越大表示样本点离超平面越近如果松弛因子大于1那么表示允许该样本点分错所以说加入松弛因子是有成本的过大的松弛因子可能会导致模型分类错误所以最终的目标函数就转换成为注函数中的Camp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;0是惩罚参数是一个超参数类似L1/L2 norm的参数C越大表示对误分类的惩罚越大也就是越不允许存在分错的样本C越小表示对误分类的惩罚越小 也就是表示允许更多的分错样本存在C值的给定需要调参。 同线性可分SVM根据KKT条件构造软间隔最大化的约束问题对应的拉格朗日函数如下 从而将我们的优化目标函数转换为优化目标同样满足KKT条件所以使用拉格朗日对偶将优化问题转换为等价的对偶问题 先求优化函数对于w、b、ξ的极小值这个可以通过分别对优化函数L求w、b、ξ的偏导数得从而可以得到w、b、ξ关于β和μ之间的关系。 将w、b、ξ的值带入L函数中就可以消去优化函数中的w、b、ξ定义优化之后的函数如下最终优化后的目标函数/损失函数和线性可分SVM模型基本一样除了约束条件不同而已 也就是说也可以使用SMO算法来求解。在硬间隔最大化的时候支持向量比较简单就是离超平面的函数距离为1的样本点就是支持向量。 在软间隔中根据KKT条件中的对偶互补条件: β(1-ξ-y(wxb))0和μ(-ξ)0以及C-β-μ0从而有 当0βi≤C的时候并且ξi0的样本点均是支持向量(即所有的0βiC)。即满足|wxb|1的所有样本均是支持向量。(取等号时所有样本都分对不考虑 第二个KKT条件) 当0βiC对应的样本就是支持向量。 注软间隔和硬间隔中的支持向量的规则是一样的 则x1是支持变量2.SVM的软间隔模型算法流程输入线性可分的m个样本数据{(x1,y1),(x2,y2),...,(xm,ym)}其中x为n维的特征向量y为二元输出取值为1或者-1SVM模型输出为参数w、b以及分类决策函数。step 1:选择一个惩罚系数C0构造约束优化问题Step2:使用SMO算法求出上式优化中对应的最优解β* step3:找出所有的支持向量集合S; step4:更新参数w*、b*的值 step5:构建最终的分类器3.SVM的软间隔模型总结 1. 可以解决线性数据中携带异常点的分类模型构建的问题 2. 通过引入惩罚项系数(松弛因子)可以增加模型的泛化能力即鲁棒性 3. 如果给定的惩罚项系数C越小表示在模型构建的时候就允许存在越多的分类错误的样本 也就表示此时模型的准确率会比较低如果惩罚项系数越大表示在模型构建的时候就越不允许存在分类错误的样本也就表示此时模型的准确率会比较高。四、1.非线性可分SVM 不管是线性可分SVM还是加入惩罚系数后的软间隔线性可分SVM其实都要求数据本身是线性可分的对于完全不可以线性可分的数据这两种算法模型就没法解决这个问题了 结合多项式回归在处理非线性可分数据时候的作用在SVM的线性不可分的数据上如果将数据映射到高维空间中那么数据就会变成线性可分的从而就可以使用线性可分SVM模型或者软间隔线性可分SVM模型。也就是说对于线性不可分SVM模型来讲重点在于低维特征数据到高维特征数据之间的映射。定义一个从低维特征空间到高维特征空间的映射函数Ф非线性可分SVM的优化目标函数 可以看到的是只需要将原来的低维空间中的两个向量的点积转换为高维空间中两个向量的点积即可。问题这样一来问题就解决了吗似乎是的拿到非线性数据就找一个映射然后一股脑把原来的数据映射到新空间中再做线性 SVM 即可。不过事实上没有这么简单其实刚才的方法稍想一下就会发现有问题在最初的例子里做了一个二阶多项式的转换对一个二维空间做映射选择的新空间是原始空间的所有一阶和二阶的组合得到了5个维度如果原始空间是三维那么我们会得到9维的新空间如果原始空间是n维那么我们会得到一个n(n3)/2维的新空间这个数目是呈爆炸性增长的这给计算带来了非常大的困难而且如果遇到无穷维的情况就根本无从计算。2.核函数 假设函数Ф是一个从低维特征空间到高维特征空间的一个映射那么如果存在函数K(x,z), 对于任意的低维特征向量x和z都有 称函数K(x,z)为核函数(kernal function)在低维空间上的计算值等价于向量做维度扩展后的点乘的结果。 核函数在解决线性不可分问题的时候采取的方式是使用低维特征空间上的计算来避免在高维特征空间中向量内积的恐怖计算量也就是说此时SVM模型可以应用在高维特征空间中数据可线性分割的优点同时又避免了引入这个高维特征空间恐怖的内积计算量。 即用低维空间中少的内积的计算量来让模型具有高维空间中的线性可分的优点。例设两个向量 和而即是到前面说的五维空间的映射因此映射过后的内积为而同时我们可以发现有一下公式可以发现两者之间非常相似所以我们只要乘上一个相关的系数就可以让这两个式子的值相等这样不就将五维空间的一个内积转换为两维空间的内积的运算。现有有两个两维的向量进行二阶多项式扩展然后进行内积计算这个时候映射高维后计算的计算量为11次乘法4次加法采用近似计算的计算量为3次乘法2次加法采用加系数后的近似计算的计算量为4次乘法2次加法核函数总结1. 核函数可以自定义核函数必须是正定核函数即Gram矩阵是半正定矩阵 2. 核函数的价值在于它的效果相当于将特征进行从低维到高维的转换但核函数它是在低维空间上的计算而将实质上的分类效果表现在了高维上也就如上文所说的避免了直接在高维空间中的复杂计算 3. 通过核函数可以将非线性可分的数据转换为线性可分数据五、SVR做回归用了解即可六.坐标下降上升法原理(搬运自https://blog.csdn.net/u010626937/article/details/75044343)假设要求解下面的优化问题在这里我们需要求解m个变量αi一般来说是通过梯度下降这里是求最大值所以应该叫上升等算法来求解每一次迭代对所有m个变量αi也就是α向量进行一次性优化。这里指的是一个向量的所有分量。通过每次迭代中的误差调整α向量中每个元素的值。而坐标上升法坐标上升与坐标下降可以看做是一对坐标上升是用来求解max最优化问题坐标下降用于求min最优化问题的思想是每次迭代只调整一个变量αi的值其他变量的值在这次迭代中固定不变。(这里指的是一个向量中的一个分量)。最里面语句的意思是固定除αi之外的所有αj(i不等于j)这时W可看作只是关于αi的函数那么直接对αi求导优化即可。这里我们进行最大化求导的顺序i是从1到m可以通过更改优化顺序来使W能够更快地增加并收敛。如果W在内循环中能够很快地达到最优那么坐标上升法会是一个很高效的求极值方法。用个二维的例子来说明下坐标下降法我们需要寻找f(x,y)x2xyy2的最小值处的(x*, y*)也就是下图的F*点的地方.假设我们初始的点是A图是函数投影到xoy平面的等高线图颜色越深值越小我们需要达到F*的地方。那最快的方法就是图中黄色线的路径一次性就到达了其实这个是牛顿优化法但如果是高维的话这个方法就不太高效了因为需要求解矩阵的逆这个不在这里讨论。我们也可以按照红色所指示的路径来走。从A开始先固定x沿着y轴往让f(x, y)值减小的方向走到B点然后固定y沿着x轴往让f(x, y)值减小的方向走到C点不断循环直到到达F*。反正每次只要我们都往让f(x, y)值小的地方走就行了这样脚踏实地一步步走每一步都使f(x, y)慢慢变小总有一天皇天不负有心人的。到达F*也是时间问题。到这里你可能会说这红色线比黄色线贫富差距也太严重了吧。因为这里是二维的简单的情况嘛。如果是高维的情况而且目标函数很复杂的话再加上样本集很多那么在梯度下降中目标函数对所有αi求梯度或者在牛顿法中对矩阵求逆都是很耗时的。这时候如果W只对单个αi优化很快的时候坐标下降法可能会更加高效。数学例题讲解下面以如下的优化问题为例在迭代的过程中每次固定x2更新x1在确定了x1的条件下固定x1更新x2。即每次迭代求解也即求解假设我们首先固定x2,来更新x1令其为0得到再固定x1得到令其为0得到不断按照上述的过程直到算法收敛。七、SMO可略过序列最小优化算法(Sequential minimal optimization, SMO)是一种用于解决SVM训练过程中所产生的优化问题的算法。 于1998年由John Platt发明。SMO的思想类似坐标上升算法我们需要优化一系列的αα的值我们每次选择尽量少的 来优化不断迭代直到函数收敛到最优值。梯度提升算法采用增量完成迭代SMO利用自身完成迭代如 。目标函数假定存在一个β*(β1,β2,...,βm)是我们最终的最优解那么根据KKT条件我们可以计算出w和b的最优解如下 进而我们可以得到最终的分离超平面为:拉格朗日乘子法和KKT的对偶互补条件为 β、μ和C之间的关系为根据这个对偶互补条件我们有如下关系式也就是说我们找出的最优的分割超平面必须满足下列的目标条件(g(x)): 拉格朗日对偶化要求的两个限制的初始条件为 从而可以得到解决问题的思路如下 首先初始化后一个β值让它满足对偶问题的两个初始限制条件 然后不断优化这个β值使得由它确定的分割超平面满足g(x)目标条件而且在优化过程中始终保证β值满足初始限制条件。 备注这个求解过程中和传统的思路不太一样不是对目标函数求最小值而是让g(x)目标条件尽可能的满足。 在这样一个过程中到底如何优化这个β值呢整理可以发现β值的优化必须遵循以下两个基本原则 每次优化的时候必须同时优化β的两个分量因为如果只优化一个分量的话新的β值就没法满足初始限制条件中的等式约束条件了。 每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说本来应当是大于1的yg(x)结果越是小于1就表示违反g(x)目标条件就越多。 或者换一种思路来理解因为目标函数中存在m个变量直接优化比较难利用启发式的方法/EM算法的思想每次优化的时候只优化两个变量将其它的变量看成常数项这样SMO算法就将一个复杂的优化算法转换为一个比较简单的两变量优化问题了。认为β1、β2是变量其它β值是常量从而将目标函数转换如下(C是常数项) 由于 ,并且y21也就是我们使用β2来表示β1的值 将上式带入目标优化函数就可以消去β1从而只留下仅仅包含β2的式子。V1,V2消去beta1 考虑β1和β2的取值限定范围假定新求出来的β值是满足我们的边界限制的即如下所示当y1y2的时候β1β2k 由于β的限制条件我们可以得到可以发现SMO算法中是选择两个合适的β变量做迭代其它变量作为常量来进行优化的一个过程那么这两个变量到底怎么选择呢??? 每次优化的时候必须同时优化β的两个分量因为如果只优化一个分量的话新的β值就没法满足初始限制条件中的等式约束条件了。 每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说本来应当是大于等于1的越是小于1违反g(x)目标条件就越多。SMO算法在选择第一个β变量的时候需要选择在训练集上违反KKT条件最严重的样本点。一般情况下先选择0βC的样本点(即支持向量)只有当所有的支持向量都满足KKT条件的时候才会选择其它样本点。因为此时违反KKT条件越严重在经过一次优化后会让变量β尽可能的发生变化从而可以以更少的迭代次数让模型达到g(x)目标条件。在选择第一个变量β1后在选择第二个变量β2的时候希望能够按照优化后的β1和β2有尽可能多的改变来选择也就是说让|E1-E2|足够的大当E1为正的时候选择最小的Ei作为E2当E1为负的时候选择最大的Ei作为E2。 备注如果选择的第二个变量不能够让目标函数有足够的下降那么可以通过遍历所有样本点来作为β2直到目标函数有足够的下降如果都没有足够的下降的话那么直接跳出循环重新选择β1在每次完成两个β变量的优化更新之后需要重新计算阈值b和差值Ei。当0β1newC时有 化简可得 同样的当β2的取值为: 0β2C的时候我们也可以得到最终计算出来的b为当更新计算阈值b后就可以得到差值Ei为
