这一节纯理论,前方贼高能!!!
很直接地,向量机就是在找一条可以把在同一个空间的两样东西分开的线,数学一点的图:
由上面的讨论,有定义:
ω T x + b = 0 \omega^T x+b=0 ω T x + b = 0 分类决策函数 是:y = f ( x ) = s i g n ( ω T ∙ x + b = 0 ) y=f(x)=sign(\omega^T \bullet x+b=0 ) y = f ( x ) = s i g n ( ω T ∙ x + b = 0 ) ω \omega ω 线 这个名词代替超平面 这个名词,但是千万不要简单地以为向量机的维度就是一二维的!
当线$f(x)=sign(\omega^T \bullet x+b=0 ) $确定的时候,每一个点对线的距离为:r = ω ∙ x i + b r=\omega\bullet x_i+b r = ω ∙ x i + b γ ^ i = y ( w T x + b ) \widehat{\gamma}_i = y(w^Tx + b) γ i = y ( w T x + b ) γ ^ \widehat{\gamma} γ 函数间隔(functional margin)
可以从符号看到分类的正确性
可以从大小看到分类的确信度
定义关于训练数据集T的超平面的函数间隔为:T中所有样本点的函数间隔最小值:γ ^ = min i = 1 , . . . , N γ ^ i \widehat{\gamma} =\min \limits_{i=1,...,N} \widehat{\gamma}_i γ = i = 1 , . . . , N min γ i 支持向量 的时候会讲到.和 和 和 在 同 时 扩 大 或 缩 小 时 , 会 让 在同时扩大或缩小时,会让 在 同 时 扩 大 或 缩 小 时 , 会 让 归一化 处理之后,可以得到:几何间隔(geometrical margin) γ i = γ ^ i ∣ ∣ ω ∣ ∣ \gamma_i=\frac{\widehat{\gamma}_i}{||\omega||} γ i = ∣ ∣ ω ∣ ∣ γ i γ = γ ^ ∣ ∣ ω ∣ ∣ \gamma=\frac{\widehat{\gamma}}{||\omega||} γ = ∣ ∣ ω ∣ ∣ γ γ i = y i ( ω ∣ ∣ ω ∣ ∣ ∙ x i + b ∣ ∣ ω ∣ ∣ ) \gamma_i= y_i \big (\frac{\omega}{||\omega||} \bullet x_i+\frac{b}{||\omega||} \big ) γ i = y i ( ∣ ∣ ω ∣ ∣ ω ∙ x i + ∣ ∣ ω ∣ ∣ b )
归一化之后,这个间隔指的才是直观意义上点到线的距离损失函数 ,此处省略,好好想想吧
看图上的两条虚线(Gap),他存在的意义就在于,当我的Gap越大,就证明我这条线和dataset的距离越远。
明显这是个几何参量定义，所以用几何间隔 定义下，有最大间隔分离超平面：max ω , b γ \max \limits_{\omega , b} \gamma ω , b max γ s . t . γ i = y i ( ω ∣ ∣ ω ∣ ∣ ∙ x i + b ∣ ∣ ω ∣ ∣ ) ≥ γ s.t. \quad \gamma_i= y_i \big (\frac{\omega}{||\omega||} \bullet x_i+\frac{b}{||\omega||} \big ) \ge \gamma s . t . γ i = y i ( ∣ ∣ ω ∣ ∣ ω ∙ x i + ∣ ∣ ω ∣ ∣ b ) ≥ γ
最大间隔分离超平面具有存在唯一性,此处不作证明
显然,这里换成函数间隔 来往下走是更好的选择:max ω , b γ ^ ∣ ∣ ω ∣ ∣ \max \limits_{\omega , b}\frac { \widehat{\gamma}}{||\omega||} ω , b max ∣ ∣ ω ∣ ∣ γ s . t . γ i = y i ( ω ∙ x i + b ) ≥ γ ^ s.t. \quad \gamma_i= y_i \big ( \omega \bullet x_i+{b}\big ) \ge \widehat{\gamma} s . t . γ i = y i ( ω ∙ x i + b ) ≥ γ γ ^ = 1 \widehat{\gamma}=1 γ = 1
这种做法称为硬间隔最大化 ,指的是gap的不可变性
为了后续的公式化简,最大值也作了一点trick:(1.1) min ω , b 1 2 ∣ ∣ ω ∣ ∣ 2 \min\limits_{\omega , b} \frac12 ||\omega||^2 \tag{1.1} ω , b min 2 1 ∣ ∣ ω ∣ ∣ 2 ( 1 . 1 ) (1.2) s . t . y i ( ω ∙ x i + b ) − 1 ≥ 0 s.t. \quad y_i \big ( \omega \bullet x_i+{b}\big ) -1 \ge 0 \tag{1.2} s . t . y i ( ω ∙ x i + b ) − 1 ≥ 0 ( 1 . 2 )
显然,在训练完之后,这条线是不是只会和线(或Gap)上的点有关系,所以就称满足
y i ( ω ∙ x i + b ) − 1 = 0 \quad y_i \big ( \omega \bullet x_i+{b}\big ) -1 = 0 y i ( ω ∙ x i + b ) − 1 = 0 支持向量(Support Vector)
所以SVM的中文读法是支持向量 \quad ,而不是支持 \quad ,重点!!!
两条虚线之间的距离称为间隔(margin) ,虚线称为间隔边界
gap=2 ∣ ∣ ω ∣ ∣ \frac2{||\omega||} ∣ ∣ ω ∣ ∣ 2
回到凸二次(w,b)规划(convex quadratic programming)问题,显然,从高数我们就可以知道,在这种情况下,我们应该引入
拉格朗日算子
在单不等式约束中:L ( x , y , λ ) = f ( x , y ) + λ ∙ ( g ( x , y ) − c ) \mathcal{L}(x,y,\lambda) = f(x,y) + \lambda\bullet(g(x,y)-c) L ( x , y , λ ) = f ( x , y ) + λ ∙ ( g ( x , y ) − c ) L ( x , y , λ 1 , . . . , λ k ) = f ( x , y ) − ∑ i − 1 k λ i g i ( x , y ) \mathcal{L}(x,y,\lambda_1,...,\lambda_k) = f(x,y) - \sum_{i-1}^k\lambda_i g_i(x,y) L ( x , y , λ 1 , . . . , λ k ) = f ( x , y ) − i − 1 ∑ k λ i g i ( x , y )
其中,f为原函数,g为约束函数.λ 为 拉 格 朗 日 算 子 \lambda 为拉格朗日算子 λ 为 拉 格 朗 日 算 子
故代入(1.1)和(1.2)得:L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 − ∑ i = 1 k α i [ y i ( w T x i + b ) − 1 ]   , α i ≥ 0 \mathcal{L}(w,b,\alpha) = \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{k}\alpha_i[y_i(w^Tx_i + b) - 1] \; \quad ,\alpha_i \geq 0 L ( w , b , α ) = 2 1 ∣ ∣ w ∣ ∣ 2 2 − i = 1 ∑ k α i [ y i ( w T x i + b ) − 1 ] , α i ≥ 0 L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 − ∑ i = 1 k α i y i ( w T x i + b ) + ∑ i = 1 k a i , α i ≥ 0 \mathcal{L}(w,b,\alpha) = \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{k}\alpha_i y_i(w^Tx_i + b) +\sum_{i=1}^k a_i\; \quad ,\alpha_i \geq 0 L ( w , b , α ) = 2 1 ∣ ∣ w ∣ ∣ 2 2 − i = 1 ∑ k α i y i ( w T x i + b ) + i = 1 ∑ k a i , α i ≥ 0
在规划有解的前提下 ,由拉格朗日对称性,函数的优化可以转化为极大极小问题:
ψ ( a ) = m a x ⎵ α i ≥ 0 m i n ⎵ w , b L ( w , b , α ) \psi(a)=\underbrace{max}_{\alpha_i \geq 0} \;\underbrace{min}_{w,b}\; \mathcal{L}(w,b,\alpha) ψ ( a ) = α i ≥ 0 m a x w , b m i n L ( w , b , α )
(1)m i n ⎵ w , b L ( w , b , α ) \underbrace{min}_{w,b}\; \mathcal{L}(w,b,\alpha) w , b m i n L ( w , b , α )
由于要求最小值,变量为w,b,不妨分别对他们求偏导并置零:∂ L ∂ ω = 0   ⇒ ω = ∑ i = 1 k α i y i x i \frac{\partial \mathcal{L}}{\partial \omega} = 0 \;\Rightarrow \omega = \sum\limits_{i=1}^{k}\alpha_iy_ix_i ∂ ω ∂ L = 0 ⇒ ω = i = 1 ∑ k α i y i x i
∂ L ∂ b = 0   ⇒ ∑ i = 1 k α i y i = 0 \frac{\partial \mathcal{L}}{\partial b} = 0 \;\Rightarrow \sum\limits_{i=1}^{k}\alpha_iy_i = 0 ∂ b ∂ L = 0 ⇒ i = 1 ∑ k α i y i = 0 KaTeX parse error: No such environment: align at position 7: \begin{̲a̲l̲i̲g̲n̲}̲ \psi(\alpha) &…
版本二:y i , a i y_i,a_i y i , a i KaTeX parse error: No such environment: align* at position 7: \begin{̲a̲l̲i̲g̲n̲*̲}̲ \psi(\alpha) &…
(2)对p s i ( a ) = m a x ⎵ α i ≥ 0 m i n ⎵ w , b L ( w , b , α ) psi(a)=\underbrace{max}_{\alpha_i \geq 0} \;\underbrace{min}_{w,b}\; \mathcal{L}(w,b,\alpha) p s i ( a ) = α i ≥ 0 m a x w , b m i n L ( w , b , α )
ϕ = m i n ⎵ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ∙ x j ) − ∑ i = 1 N α i \phi = \underbrace{min}_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \bullet x_j) - \sum\limits_{i=1}^{N} \alpha_i ϕ = α m i n 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j ( x i ∙ x j ) − i = 1 ∑ N α i s . t . ∑ i = 1 N a i y i = 0 , a i ≥ 0 s.t. \sum_{i=1}^Na_iy_i=0 \quad ,a_i \geq 0 s . t . i = 1 ∑ N a i y i = 0 , a i ≥ 0
KKT条件是说最优值必须满足以下条件：
L(a, b, x)对x求导为零；
h(x) =0;
a*g(x) = 0;
KKT的意义是:非线性规划问题能有最优化解法的充分必要条件,主要是因为,很明显,超平面在维度上去之后,显然不是一个线性分类问题,所以要先解决低维向高维转换的可能性
由于篇幅问题,可以参考参考文献的KKT条件-知乎 和 extra-3,会有很好的解释
事实证明,用拉格朗日算子可以实现.a i ∗ ( y i ( ω ∗ ∙ x i + b ∗ ) − 1 ) = 0 a_i^*(y_i(\omega^*\bullet x_i+b^*)-1)=0 a i ∗ ( y i ( ω ∗ ∙ x i + b ∗ ) − 1 ) = 0
自此,我们已经就可以得到结果啦:ω ∗ = ∑ i = 1 N a i ∗ y i x i \omega^*=\sum_{i=1}^N a_i^* y_ix_i ω ∗ = i = 1 ∑ N a i ∗ y i x i a j ∗ > 0 a_j^*>0 a j ∗ > 0 b ∗ = y j − ∑ i = 1 N a i ∗ y i ( x i ∙ x j ) b^*=y_j -\sum_{i=1}^N a_i^* y_i(x_i\bullet x_j) b ∗ = y j − i = 1 ∑ N a i ∗ y i ( x i ∙ x j )
由于上一节说了,我们取了一个γ ^ = 1 \widehat{\gamma}=1 γ = 1 异常点
因为在硬间隔中我们就规定了函数间隔是1,面对这种异常点,往往硬间隔在训练的时候是不会自动去除而严重影响结果的.
所以这里的重点在于,引入一个松弛变量,放宽间隔:y i ( w ∙ x i + b ) ≥ 1 − ξ i y_i(w\bullet x_i +b) \geq 1- \xi_i y i ( w ∙ x i + b ) ≥ 1 − ξ i m i n     1 2 ∣ ∣ w ∣ ∣ 2 2 + C ∑ i = 1 m ξ i min\;\; \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i m i n 2 1 ∣ ∣ w ∣ ∣ 2 2 + C i = 1 ∑ m ξ i 调参党 需要手动给出的参数
这次其实和上一节的唯一差别就是,拉格朗日算子由两个(w,b)改变到三个(w,b,ξ \xi ξ ξ \xi ξ ξ \xi ξ ∂ L ∂ ξ = 0   ⇒ C − α i − μ i = 0 , μ i > 0 \frac{\partial L}{\partial \xi} = 0 \;\Rightarrow C- \alpha_i - \mu_i = 0 \quad ,\mu_i>0 ∂ ξ ∂ L = 0 ⇒ C − α i − μ i = 0 , μ i > 0 一摸一样 的.a i ≥ 0 a_i \geq 0 a i ≥ 0 0 ≤ a i ≤ C 0\leq a_i\leq C 0 ≤ a i ≤ C
当a i = C a_i=C a i = C a i a_i a i C − α i − μ i = 0 C- \alpha_i - \mu_i = 0 \quad C − α i − μ i = 0
如果0≤ξi≤1,那么点被正确分类，但是却在超平面和自己类别的支持向量之间。如图中的样本2和4.
如果ξi=1,那么点在分离超平面上，无法被正确分类。
如果ξi>1,那么点在超平面的另一侧，也就是说，这个点不能被正常分类。如图中的样本1和3.
线性支持向量机还有另外一种解释如下：m i n ⎵ w , b [ 1 − y i ( w ∙ x + b ) ] + + λ ∣ ∣ w ∣ ∣ 2 2 \underbrace{ min}_{w, b}[1-y_i(w \bullet x + b)]_{+} + \lambda ||w||_2^2 w , b m i n [ 1 − y i ( w ∙ x + b ) ] + + λ ∣ ∣ w ∣ ∣ 2 2 [ 1 − y i ( w ∙ x + b ) ] + [1-y_i(w \bullet x + b)]_{+} [ 1 − y i ( w ∙ x + b ) ] + L ( y ( w ∙ x + b ) ) = [ 1 − y i ( w ∙ x + b ) ] + L(y(w \bullet x + b)) = [1-y_i(w \bullet x + b)]_{+} L ( y ( w ∙ x + b ) ) = [ 1 − y i ( w ∙ x + b ) ] + [ z ] + = { z z > 0 0 z ≤ 0 [z]_{+}= \begin{cases} z & {z >0}\\ 0& {z\leq 0} \end{cases} [ z ] + = { z 0 z > 0 z ≤ 0
自此线性情况就讲完了.
这个是用来求解a的,理论来说是现实实现svm最需要的掌握的算法(让求a的速度变快),
https://zhuanlan.zhihu.com/p/29212107
http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
在线性不可分的时候,我们可以通过核函数 将数据映射到核函数对应的特征空间(比如二维转到三维)中.
在特征空间中,使用线性学习器分类
就好像是平面的数据,用某个规则突起其中一些特征数据,然后用一个线性平面去分类,然后将这个线性平面和三维特征空间的交线再投影回原来的平面中
其实说了这么久的核核核,其实就是变换对,功能是特征空间的变换,所以只要符合是正定核 ,即对称函数的kernel就能被称为一个核
由线性泛函的观点来说,这样的变换可以快速地变换自变量来推出公式:f ( x ) = ∑ i = 1 n a i y i < x i , x > + b f(x)=\sum^n_{i=1}a_i y_i<x_i,x>+b f ( x ) = i = 1 ∑ n a i y i < x i , x > + b f ( x ) = ∑ i = 1 n a i y i < ϕ ( x i ) , ϕ ( x ) > + b f(x)=\sum^n_{i=1}a_i y_i<\phi (x_i),\phi (x)>+b f ( x ) = i = 1 ∑ n a i y i < ϕ ( x i ) , ϕ ( x ) > + b
如果你想请我吃个南五的话
##参考文献理解SVM的三层境界 范数 s.t. 拉格朗日乘子 拉格朗日对偶性 KKT条件-知乎 SVM-wiki sign符号函数 泛函分析 非线性分析 SMO SMO2 extra-1 extra-2 extra-3 extra-4
《统计学习方法》，李航著；
