机器学习知识点总结SVMSVM二分类模型特征空间上间隔最大的线性分类器学习目标在n维数据空间中找到一个超平面学习策略最大化间隔分类超平面f ( x ) w T x b f(x)w^Txbf(x)wTxb,f ( x ) f(x)f(x)小于0对应于y − 1 y-1y−1的数据点f ( x ) f(x)f(x)大于0对应于y 1 y1y1的数据点f ( x ) 0 f(x)0f(x)0对应于超平面上的点。定义点到超平面的函数间隔γ i ^ y i ( w T x i b ) \hat{\gamma_i}y_i(w^Tx_ib)γi​^​yi​(wTxi​b), 在超平面确定的情况下∣ w T x b ∣ |w^Txb|∣wTxb∣能够表示点x xx距离超平面的远近利用y yy和f ( x ) f(x)f(x)的符号可以判断分类正确性。为什么要乘以y yy?当分类错误时y yy和f ( x ) f(x)f(x)异号此时γ ^ \hat{\gamma}γ^​为负我们希望最大化这个间隔即令它接近0使得被错误分类的这个点更接近超平面当分类正确时同样我们也希望最大化间隔使它尽可能大于0使得被正确分类的点更远离超平面。因此可以通过函数间隔将所有样本点统一起来。无论是分错的还是分对的样本点都可以令间隔最大化来改善分类性能。超平面关于训练集T TT的函数间隔定义为T TT中所有样本点( x i , y i ) (x_i,y_i)(xi​,yi​)的函数间隔最小值γ ^ min ⁡ γ i ^ \hat{\gamma}\min \hat{\gamma_i}γ^​minγi​^​, (i1,…,n)。几何间隔γ ~ y w T x b ∣ ∣ w ∣ ∣ γ ^ ∣ ∣ w ∣ ∣ \tilde{\gamma}y\frac{w^Txb}{||w||}\frac{\hat{\gamma}}{||w||}γ~​y∣∣w∣∣wTxb​∣∣w∣∣γ^​​。成比例地改变w ww和b bb会影响函数间隔。最大化间隔分类器当超平面离数据点的间隔越大分类的确信度confidence越高。注意当分类错误时这个间隔为负当分类正确时这个间隔为正最大间隔分类器目标函数max ⁡ γ ~ \max \tilde{\gamma}maxγ~​, 满足约束条件y i ( w T x i b ) γ i ^ ⩾ γ ^ , i 1 , . . . , n y_i(w^Tx_ib)\hat{\gamma_i} \geqslant \hat{\gamma}, i1,...,nyi​(wTxi​b)γi​^​⩾γ^​,i1,...,n训练集函数间隔定义为所有样本点间隔的最小值我们令γ ^ 1 \hat{\gamma}1γ^​1则上式转化为:max ⁡ 1 ∣ ∣ w ∣ ∣ , s . t . , y i ( w T x i b ) ⩾ 1 , i 1 , . . . , n \max \frac{1}{||w||}, \ \ s.t., y_i(w^Tx_ib)\geqslant 1, i1,...,nmax∣∣w∣∣1​,s.t.,yi​(wTxi​b)⩾1,i1,...,n所有满足y i ( w T x i b ) 1 y_i(w^Tx_ib)1yi​(wTxi​b)1的点称为支持向量。上述目标函数等价于max ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 s . t . , y i ( w T x i b ) ⩾ 1 , i 1 , . . . , n \max \frac{1}{2}||w||^2 \ \ s.t., y_i(w^Tx_ib)\geqslant 1, i1,...,nmax21​∣∣w∣∣2s.t.,yi​(wTxi​b)⩾1,i1,...,n问题求解对偶算法。通过拉格朗日对偶性变换为对偶问题通过求解与原问题等价的对偶问题得到原始问题的最优解。好处对偶问题更容易求解更容易引入核函数推广到非线性分类问题。构建拉格朗日函数将约束条件融合到目标函数中L ( w , b , α ) 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i 1 n α i ( y i ( w T x i b ) − 1 ) \mathcal{L}(w,b,\alpha)\frac{1}{2}||w||^2-\sum_{i1}^{n} \alpha_i (y_i(w^T x_i b)-1)L(w,b,α)21​∣∣w∣∣2−i1∑n​αi​(yi​(wTxi​b)−1)令θ ( w ) max ⁡ α i ⩾ 0 L ( w , b , α ) \theta(w)\max_{\alpha_i \geqslant 0 } \mathcal{L}(w,b,\alpha)θ(w)αi​⩾0max​L(w,b,α)当某个约束条件不满足时θ ( w ) ∞ \theta(w)\inftyθ(w)∞当所有约束条件都满足时θ ( w ) 1 2 ∣ ∣ w ∣ ∣ 2 \theta(w)\frac{1}{2}||w||^2θ(w)21​∣∣w∣∣2。因此要求在满足约束条件下最小化1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^221​∣∣w∣∣2等价于最小化θ ( w ) \theta(w)θ(w)所以目标函数转换为min ⁡ w , b θ ( w ) min ⁡ w , b max ⁡ α i ⩾ 0 L ( w , b , α ) p ∗ \min_{w,b} \theta(w)\min_{w,b} \max_{\alpha_i \geqslant 0} \mathcal{L}(w,b,\alpha)p^*w,bmin​θ(w)w,bmin​αi​⩾0max​L(w,b,α)p∗将最大最小交换获得原始问题的对偶问题max ⁡ α i ⩾ 0 min ⁡ w , b L ( w , b , α ) d ∗ \max_{\alpha_i \geqslant 0} \min_{w,b} \mathcal{L} (w,b,\alpha)d^*αi​⩾0max​w,bmin​L(w,b,α)d∗上述的交换需要满足KKT条件才有d ∗ p ∗ d^* p^*d∗p∗, 这时可以通过求解对偶问题来间接地求解原始问题。