在线推广企业网站的方法,wordpress关键字内链,上海网站营销seo电话,wordpress get_the_time()目录 一. SVM的优越性二. SVM算法推导小节概念 在开始讲述SVM算法之前#xff0c;我们先来看一段定义#xff1a; 支持向量机(Support VecorMachine, SVM)本身是一个二元分类算法#xff0c;支持线性分类和非线性分类的分类应用#xff0c;同时通过OvR或者OvO的方式可以应用… 目录 一. SVM的优越性二. SVM算法推导小节概念 在开始讲述SVM算法之前我们先来看一段定义 支持向量机(Support VecorMachine, SVM)本身是一个二元分类算法支持线性分类和非线性分类的分类应用同时通过OvR或者OvO的方式可以应用在多元分类领域中能够直接将SVM应用于回归应用中
在不考虑集成学习算法或者特定的数据集时SVM在分类算法中可以说是一种特别优秀的算法一. SVM的优越性
在Logistic回归算法中 我们追求是寻找一条决策边界即找到一条能够正确划分所有训练样本的边界 当所有样本正确划分时损失函数已降至最低模型不再优化
在SVM算法中 我们追求是寻找一条最优决策边界 那什么是最优呢SVM提出的基本思想是寻找一条决策边界使得该边界到两边最近的点间隔最大这样做得目的在于相比于其他边界svm寻找到的边界对于样本的局部扰动容忍性最好对新进样本更容易判断正确也就是说此时决策边界具有最好的鲁棒性二. SVM算法推导 注意下面讲述的是线性分类这里我们换一种思路寻找最佳决策边界
首先假设决策边界为 y ω → ⋅ x → b y \overrightarrow{\omega }\cdot \overrightarrow{x} b yω ⋅x b 公式解释1 为什么要这么设方程呢 我们希望通过向量点乘来确定距离 换句话说希望通过向量点乘来确定正负样本的边界 为了寻找最佳决策边界我们可以 以上述决策边界为中心线向两边做平行线让这两条平行线过两边最近的样本点此时会形成一条“街道”最佳决策边界就是使这条街道最宽的那个决策边界。 补充一点 在Logistic回归算法中我们人为的将数据集设为10 在SVM算法中我们人为的将数据集设为1-1 参数说明 width街宽 ω → \overrightarrow{\omega } ω 决策边界的法向量 u − → \overrightarrow{u_{-} } u− 街边上的负样本向量 u → \overrightarrow{u_{} } u 街边上的正样本向量 单位向量 a → ∥ a ∥ \frac{\overrightarrow{a}}{\left \| a \right \| } ∥a∥a 向量点乘几何的意义 a → ⋅ b → ∣ a → ∣ ∣ b → ∣ cos θ \overrightarrow{a}\cdot \overrightarrow{b} \left | \overrightarrow{a} \right| |\overrightarrow{b} | \cos \theta a ⋅b a ∣b ∣cosθ 可以理解为 a → \overrightarrow{a} a 在 b → \overrightarrow{b} b 上的投影长度乘以 ∣ b → ∣ |\overrightarrow{b}| ∣b ∣的模长 对于训练集中的任何一个数据我们总会取到一个合适长度的 ω → \overrightarrow{\omega } ω 以及一个适合的常数b得到 { ω → ⋅ u → b ≥ 1 ω → ⋅ u − → b ≤ − 1 \left\{\begin{matrix}\overrightarrow{\omega }\cdot \overrightarrow{u_{} } b\ge 1 \\\overrightarrow{\omega }\cdot \overrightarrow{u_{-} } b\le -1 \end{matrix}\right. {ω ⋅u b≥1ω ⋅u− b≤−1
即可以合并为 y i ( ω → ⋅ u i → b ) ≥ 1 y_{i} (\overrightarrow{\omega }\cdot \overrightarrow{u_{i} } b)\ge1 yi(ω ⋅ui b)≥1 而对于街边点而言满足 y i ( ω → ⋅ u i → b ) 1 y_{i} (\overrightarrow{\omega }\cdot \overrightarrow{u_{i} } b)1 yi(ω ⋅ui b)1 注意这些街边点对于决定决策边界取决定性作用因此被称为支持向量这样我们就可以用数学方式将上述街宽抽象出来 w i d t h ( u → − u − → ) ⋅ w → ∥ w ∥ width (\overrightarrow{u_{}}-\overrightarrow{u_{-}} )\cdot \frac{\overrightarrow{w}}{\left \| w \right \| } width(u −u− )⋅∥w∥w 推导式子就可以进一步得到 w i d t h ( u → − u − → ) ⋅ w → ∥ w ∥ width (\overrightarrow{u_{}}-\overrightarrow{u_{-}} )\cdot \frac{\overrightarrow{w}}{\left \| w \right \| } width(u −u− )⋅∥w∥w u → ⋅ ω → ∥ ω → ∥ − u − → ⋅ ω → ∥ ω → ∥ \frac{\overrightarrow{u_{}}\cdot\overrightarrow{\omega _{}} }{\left \| \overrightarrow{\omega\mathrm{} } \right \| }-\frac{\overrightarrow{u_{-}}\cdot\overrightarrow{\omega _{}} }{\left \| \overrightarrow{\omega\mathrm{} } \right \| } ∥ω ∥u ⋅ω −∥ω ∥u− ⋅ω 1 − b ∥ w → ∥ − − 1 − b ∥ w → ∥ \frac{1-b}{\left \| \overrightarrow{w} \right \| } -\frac{-1-b}{\left \| \overrightarrow{w} \right \| } ∥w ∥1−b−∥w ∥−1−b 2 ∥ w → ∥ \frac{2}{\left \| \overrightarrow{w} \right \| } ∥w ∥2
此时我们要求街宽最大即是求 m i n ( ∥ w → ∥ ) min({\left \| \overrightarrow{w} \right \| }) min( w )这里为了后续求导方便将值写成 m i n ( 1 2 ∥ w → ∥ 2 ) min(\frac{1}{2}\left \| \overrightarrow{w} \right \| ^{2} ) min(21 w 2)
需要明确街边最大值的条件是基于支持向量的而支持向量是属于数据集的因此我们的问题就变成了 { m i n ( 1 2 ∥ w → ∥ 2 ) s . t . y i ( ω → ⋅ x → b ) − 1 ≥ 0 \left\{\begin{matrix}min(\frac{1}{2}\left \| \overrightarrow{w} \right \| ^{2} ) \\s.t. y_{i} (\overrightarrow{\omega }\cdot \overrightarrow{x } b)-1\ge0 \end{matrix}\right. {min(21 w 2)s.t.yi(ω ⋅x b)−1≥0
这是一个典型的条件极值问题我们用拉格朗日乘数法得到拉格朗日函数为 L 1 2 ∥ w → ∥ 2 − ∑ i 1 m β i [ y i ( ω → ⋅ x → b ) − 1 ] , ( β i ≥ 0 ) L \frac{1}{2}\left \| \overrightarrow{w} \right \| ^{2} -\sum_{i1}^{m} \beta _{i}[ y_{i} (\overrightarrow{\omega }\cdot \overrightarrow{x } b)-1] ,(\beta _{i}\ge 0) L21 w 2−i1∑mβi[yi(ω ⋅x b)−1],(βi≥0)
这里的约束是不等式约束所以要使用KKT条件(KKT是拉格朗日乘数法的一种泛化形式此时 β i ≥ 0 \beta _{i}\ge0 βi≥0)而KKT条件的计算方式为 max β ≥ 0 min w , b L ( w , b , β ) \max_{\beta \ge 0} \min_{w,b}L(w,b,\beta ) β≥0maxw,bminL(w,b,β) ∂ L ∂ w w − ∑ i 1 m β i x ( i ) y ( i ) 0 ⇒ w ∑ i 1 m β i x ( i ) y ( i ) \frac{\partial L}{\partial w} w-\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)}0\Rightarrow w\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} ∂w∂Lw−i1∑mβix(i)y(i)0⇒wi1∑mβix(i)y(i) ∂ L ∂ b − ∑ i 1 m β i y ( i ) 0 ⇒ 0 ∑ i 1 m β i y ( i ) \frac{\partial L}{\partial b} -\sum_{i1}^{m} \beta _{i}y^{(i)}0\Rightarrow 0\sum_{i1}^{m} \beta _{i} y^{(i)} ∂b∂L−i1∑mβiy(i)0⇒0i1∑mβiy(i) 公式解释 β \beta β是每个样本对应的拉格朗日乘子 对于非支持向量而言 β 0 \beta0 β0即对非支持向量无约束 则 y ( i ) ∗ 0 0 y^{(i)}*00 y(i)∗00 对于支持向量而言 β 0 \beta0 β0即对支持向量有约束 则 正样本支持向量 ∗ 1 负样本支持向量 ∗ ( − 1 ) 0 正样本支持向量\ast 1负样本支持向量\ast (-1)0 正样本支持向量∗1负样本支持向量∗(−1)0 此时 L ( β ) L(\beta) L(β)为 L ( β ) 1 2 ∥ w → ∥ 2 − ∑ i 1 m β i [ y ( i ) ( ω T ⋅ x ( i ) b ) − 1 ] L(\beta)\frac{1}{2}\left \| \overrightarrow{w} \right \| ^{2} -\sum_{i1}^{m} \beta _{i}[y^{(i)} (\omega ^{T} \cdot x^{(i)} b)-1] L(β)21 w 2−∑i1mβi[y(i)(ωT⋅x(i)b)−1] 1 2 ω T ω − ∑ i 1 m β i y ( i ) ω T ⋅ x ( i ) − b ∑ i 1 m β i y ( i ) ∑ i 1 m β i \frac{1}{2}\omega ^{T}\omega -\sum_{i1}^{m} \beta _{i}y^{(i)}\omega ^{T} \cdot x^{(i)}-b\sum_{i1}^{m} \beta _{i}y^{(i)}\sum_{i1}^{m} \beta _{i} 21ωTω−∑i1mβiy(i)ωT⋅x(i)−b∑i1mβiy(i)∑i1mβi 1 2 ω T ∑ i 1 m β i x ( i ) y ( i ) − ∑ i 1 m β i y ( i ) ω T x ( i ) ∑ i 1 m β i \frac{1}{2}\omega ^{T}\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} -\sum_{i1}^{m} \beta _{i}y^{(i)}\omega ^{T}x^{(i)}\sum_{i1}^{m} \beta _{i} 21ωT∑i1mβix(i)y(i)−∑i1mβiy(i)ωTx(i)∑i1mβi − 1 2 ω T ∑ i 1 m β i x ( i ) y ( i ) ∑ i 1 m β i -\frac{1}{2}\omega ^{T}\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} \sum_{i1}^{m} \beta _{i} −21ωT∑i1mβix(i)y(i)∑i1mβi − 1 2 ( ∑ j 1 m β j x ( j ) y ( j ) ) T ( ∑ i 1 m β i x ( i ) y ( i ) ) ∑ i 1 m β i -\frac{1}{2}(\sum_{j1}^{m} \beta _{j} x^{(j)}y^{(j)})^{T}(\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} )\sum_{i1}^{m} \beta _{i} −21(∑j1mβjx(j)y(j))T(∑i1mβix(i)y(i))∑i1mβi − 1 2 ∑ j 1 m β j x ( j ) T y ( j ) ∑ i 1 m β i x ( i ) y ( i ) ∑ i 1 m β i -\frac{1}{2}\sum_{j1}^{m} \beta _{j} x^{(j)^{T}}y^{(j)}\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} \sum_{i1}^{m} \beta _{i} −21∑j1mβjx(j)Ty(j)∑i1mβix(i)y(i)∑i1mβi ∑ i 1 m β i − 1 2 ∑ i 1 m ∑ j 1 m β i β j y ( i ) y ( j ) x ( j ) T x ( i ) \sum_{i1}^{m} \beta _{i}-\frac{1}{2}\sum_{i1}^{m}\sum_{j1}^{m} \beta _{i}\beta _{j} y^{(i)}y^{(j)}x^{(j)^{T}} x^{(i)} ∑i1mβi−21∑i1m∑j1mβiβjy(i)y(j)x(j)Tx(i)
即 { L ( β ) ∑ i 1 m β i − 1 2 ∑ i 1 m ∑ j 1 m β i β j y ( i ) y ( j ) x ( j ) T x ( i ) s . t : ∑ i 1 m β i y ( i ) 0 \left\{\begin{matrix}L(\beta)\sum_{i1}^{m} \beta _{i}-\frac{1}{2}\sum_{i1}^{m}\sum_{j1}^{m} \beta _{i}\beta _{j} y^{(i)}y^{(j)}x^{(j)^{T}} x^{(i)} \\s.t:\sum_{i1}^{m} \beta _{i} y^{(i)}0 \end{matrix}\right. {L(β)∑i1mβi−21∑i1m∑j1mβiβjy(i)y(j)x(j)Tx(i)s.t:∑i1mβiy(i)0
解到这一步我们发现L函数只与 β \beta β有关所以此时可以直接极大化我们的优化函数且 max β ≥ 0 l ( β ) ⟶ min β ≥ 0 − l ( β ) \max_{\beta \ge 0}l(\beta ) \longrightarrow \min_{\beta \ge 0}-l(\beta ) β≥0maxl(β)⟶β≥0min−l(β) 因此求解 β \beta β就变成了 { min β ≥ 0 1 2 ∑ i 1 m ∑ j 1 m β i β j y ( i ) y ( j ) x ( j ) T x ( i ) − ∑ i 1 m β i s . t : ∑ i 1 m β i y ( i ) 0 \left\{\begin{matrix}\min_{\beta \ge 0}\frac{1}{2}\sum_{i1}^{m}\sum_{j1}^{m} \beta _{i}\beta _{j} y^{(i)}y^{(j)}x^{(j)^{T}} x^{(i)}-\sum_{i1}^{m} \beta _{i} \\s.t:\sum_{i1}^{m} \beta _{i} y^{(i)}0 \end{matrix}\right. {minβ≥021∑i1m∑j1mβiβjy(i)y(j)x(j)Tx(i)−∑i1mβis.t:∑i1mβiy(i)0
但是对于 β \beta β可以使用SMO算法求得对于SMO算法我们先放一放
这里假设我们用SMO求得了 β \beta β的最优解那么我们可以分别计算得到对应的 w ∑ i 1 m β i x ( i ) y ( i ) w\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} w∑i1mβix(i)y(i) b一般使用所有支持向量的计算均值作为实际值
怎么得到支持向量呢 β 0 \beta0 β0该样本不是支持向量 β 1 \beta1 β1该样本是支持向量
小节
对于线性可分的m个样本(x1,y1)(x2,y2)… x为n维的特征向量y为二元输出即1-1SVM的输出为wb分类决策函数
通过构造约束问题 { min β ≥ 0 1 2 ∑ i 1 m ∑ j 1 m β i β j y ( i ) y ( j ) x ( j ) T x ( i ) − ∑ i 1 m β i s . t : ∑ i 1 m β i y ( i ) 0 \left\{\begin{matrix}\min_{\beta \ge 0}\frac{1}{2}\sum_{i1}^{m}\sum_{j1}^{m} \beta _{i}\beta _{j} y^{(i)}y^{(j)}x^{(j)^{T}} x^{(i)}-\sum_{i1}^{m} \beta _{i} \\s.t:\sum_{i1}^{m} \beta _{i} y^{(i)}0 \end{matrix}\right. {minβ≥021∑i1m∑j1mβiβjy(i)y(j)x(j)Tx(i)−∑i1mβis.t:∑i1mβiy(i)0 使用SMO算法求出上述最优解 β \beta β 找到所有支持向量集合 S ( x ( i ) , y ( i ) ) ( β 0 , i 1 , 2 , . . . , m ) S (x^{(i)}, y^{(i)}) (\beta 0,i1,2,...,m) S(x(i),y(i))(β0,i1,2,...,m) 从而更新wb w ∑ i 1 m β i x ( i ) y ( i ) w\sum_{i1}^{m} \beta _{i} x^{(i)}y^{(i)} w∑i1mβix(i)y(i) b 1 S ∑ i 1 S ( y s − ∑ i 1 m β i x ( i ) T y ( i ) x s ) b\frac{1}{S} \sum_{i1}^{S}(y^{s}- \sum_{i1}^{m} \beta _{i} x^{(i)^{T}}y^{(i)}x^{s} ) bS1∑i1S(ys−∑i1mβix(i)Ty(i)xs)
构造最终的分类器为 f ( x ) s i g n ( w ∗ x b ) f(x)sign(w\ast xb) f(x)sign(w∗xb) x0时y-1x0时y0x0时y1注意假设不会出现0若出现正负样本随意输出一个即0.00000001或-0.00000001都可以概念
最后我们定义具体概念
分割超平面(Separating Hyperplane)将数据集分割开来的直线、平面叫分割超平面
支持向量(Support Vector)离分割超平面最近的那些点叫做支持向量
间隔(Margin)支持向量数据点到分割超平面的距离称为间隔任何一个支持向量到分割超平面的距离都是相等的 感谢阅读 如果喜欢这篇文章记得点赞和转发哦 有任何想法或问题欢迎留言交流我们下次见 本文相关代码存放位置
祝愉快
