支持向量机

作者: fighting_coder | 来源:发表于2019-08-26 22:21 被阅读0次

【转载】pluskid的SVM系列博文
【机器学习实战】第6章支持向量机（Support Vector
SVM支持向量机
编程作业（六）
支持向量机-QA
支持向量机
机器学习——libSVM（一）
支持向量机&&聚类
支持向量机
【9%】100小时机器学习——支持向量机SVM

支持向量机(svm)是一种用于分类的算法，它的思想是找出一条平面最大间隔的将数据集分开。它可以分为硬间隔分类和软间隔分类。

1.硬间隔分类器
给定数据集 $\{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\}$ ,要找出一条平面 $y=w^Tx+b$ 最大间隔的分割数据集的优化函数可以表示为
$\max \min dist(w^T,b)$
$s.t \quad y_i(w^Tx_i+b)>0; i=1,2,...n$
$dist(w^T,b)$ 表示数据上的数据到平面的距离,意思表示为从n个样本点中找到，离平面最近的那个点的距离，使这个距离最大化，同时使样本点分类正确。根据点到平面的距离公式， $dist(w^T,b)$ 可以表示为
$dist(w^T,b)=\frac{|w^Tx+b|}{||w||}$
优化函数可以替换为：
$\max \limits_{w,b} \min \limits_{x_i,i=1,2,3...} \frac{|w^Tx_i+b|}{||w||}$
可以优化为：
$\max \limits_{w,b} \frac{1}{||w||} \min \limits_{x_i,i=1,2,3...}y_i(w^Tx_i+b)$
假设 $\min \limits_{x_i,i=1,2,3...}y_i(w^Tx_i+b)$ 存在最小值 $\gamma$ ,由于w,b作为超平面的系数，可以缩放，有无数个，可以直接令 $\gamma$ =1，是不会影响分类效果，方便优化计算，最终的优化函数化简为：
$\min \limits_{w,b} \frac{1}{2}||w||$
$s.t \quad y_i(w^Tx_i+b)>=1; i=1,2,...n$

2.拉格朗日函数
上面带约束的优化函数可以用拉格朗日乘子法构造拉格朗日函数(Lagrange function)再通过求解其对偶问题(dual problem)得到原始问题的最优解。拉格朗日函数为
$L(w,b,\alpha)=\frac{1}{2}||w|| + \sum_{i=1}^n\alpha_i(1-y_i(w^Tx_i+b)$
原问题可以表示为
$\begin{cases} \min \limits_{w,b} \max \limits_{\alpha} L(w,b,\alpha)\\ s.t \quad \alpha_i>=0 \end{cases}$
对偶问题可以表示为
$\begin{cases} \max \limits_{\alpha} \min \limits_{w,b} L(w,b,\alpha)\\ s.t \quad \alpha_i>=0 \end{cases}$
在svm 中原问题和对偶问题同解，所以可以直接通过求解对偶问题。
对w,b求偏导
$\begin{cases} \frac{\partial L}{\partial w}= w-\sum_{i=1}^n\alpha_iy_ix_i=0 \\ \frac{\partial L}{\partial b}=\sum_{i=1}^n\alpha_iy_i=0 \end{cases}$
得出
$w=\sum_{i=1}^n\alpha_iy_ix_i=0$
将其带入到L中得到关于 $\alpha$ 的优化函数
$L(\alpha)=\sum_{i=1}^n\alpha_i -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t \quad \alpha_i>=0 \quad \sum_{i=1}^n\alpha_iy_i=0$

关于b的求解可以通过kkt条件，
$\begin{cases} \alpha_i>=0 \\ \alpha_i(1-y_i(w^Tx_i+b))=0\\ 1-y_i(w^Tx_i+b)<=0 \end{cases}$
$\alpha>0$ 的点为支持向量找出这些点如 $(x_k,y_k)$ ，有kkt条件可以计算出:
$b=y_k-\sum_{i=1}^n\alpha_iy_ix_ix_k$

3.软间隔分类器
软间隔的svm 分类器的思想是允许分类有一些错误，在原来的优化函数上加一个惩罚项。在硬间隔分类器上是严格要求 $y_i(w^Tx_i+b)>=1$ ,现在允许少数点可以划分错误。表达式为
$\max(0,1-y_i(w^Tx_i+b))$
加入到原来的优化函数中
$\frac{1}{2}||w|| + C\sum_{i=1}^n\max(0,1-y_i(w^Tx_i+b))$
C>0为惩罚系数，可以将上式优化为
$\frac{1}{2}||w|| + C\sum_{i=1}^n\xi_i$
$s.t. \quad y_i(w^Tx_i+b)>=1-\xi_i \\ \xi_i>=0$
与硬间隔类似，我们可以通过拉格朗日乘子法将其转换为对偶问题进行求解
$L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||+C\sum_{i=1}^n\xi_i+\sum_{i=1}^n\alpha_i(1-\xi_i-y_i(w^Tx_i+b)-\sum_{i=1}^n\beta_i\xi_i$
先最小化 $\min \limits_{w,b,\xi}$ ,分别对w,b, $\xi$ 求导
$\begin{cases} \frac{\partial L}{\partial w}= w-\sum_{i=1}^n\alpha_iy_ix_i=0 \\ \frac{\partial L}{\partial b}=\sum_{i=1}^n\alpha_iy_i=0\\ \frac{\partial L}{\partial \xi}=C-\alpha_i-\beta_i=0 \end{cases}$
最后得到的优化函数和硬间分类器是一样的，只是 $\alpha$ 的限制不一样
$L(\alpha)=\sum_{i=1}^n\alpha_i -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t \quad 0<= \alpha_i<=C ,\quad \sum_{i=1}^n\alpha_iy_i=0$
软间隔分类的kkt条件
$\begin{cases} \alpha_i>=0，\beta_i>=0 \\ \alpha_i(1-y_i(w^Tx_i+b))=0\\ 1-y_i(w^Tx_i+b)<=0\\ \beta_i\xi_i=0 \end{cases}$
参数b也可以通过kkt条件求解

SMO算法
前面都是关于如何计算w,b，SMO（Sequential Minimal Optimization，序列最小优化)是用来求解 $\alpha$ ,它的基本思想是将原问题求解 (α1,α2,...,αN) 这 N 个参数的问题分解成多个子二次规划的问题分别求解，每个子问题只需要求解其中的 2 个参数，每次通过启发式选择两个变量进行优化，不断循环，直到达到函数的最优值。之前关于 $\alpha$ 的优化函数如下：
$L(\alpha)=\sum_{i=1}^n\alpha_i -\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t \quad 0<= \alpha_i<=C ,\quad \sum_{i=1}^n\alpha_iy_i=0$
假设选择两个变量 $\alpha_1,\alpha_2$ ,其他变量 $\alpha_i(i=3,4....N)$ 是固定的，原来的式子可以化简为只包含 $\alpha1,\alpha2$ 的式子
$\min \limits_{\alpha_1,\alpha_2} w(\alpha_1,\alpha_2)=\frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22}\alpha_2^2+ \\ y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha1-\alpha2) +y_1\alpha_1\sum_{i=3}^ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^ny_i\alpha_iK_{i2}$
$s.t \quad \alpha_1y1+\alpha_2y2=-\sum_{i=1}^ny_i\alpha_i=\xi \\ 0 \leq \alpha_i \leq C$
通过求导得到关于 $\alpha$ 的最优解为：
$\begin{cases} \alpha_2^{new,unc}=\alpha_2^{old} + \frac{y_2(E_1-E_2)}{\eta}\\ \eta=K_{11}+K_{22}-2K{1,2}\\ \end{cases}$
由于 $\alpha_2$ 是受条件约束的，约束条件如下当y1不等于y2时
$\begin{cases} L\leq\alpha_2\leq H\\ L=\max(0,\alpha_2^{old}-\alpha_1^{old})\\ H = \min(C,C+\alpha_2^{old}-\alpha_1^{old}) \end{cases}$
当y1=y2时
$\begin{cases} L\leq\alpha_2\leq H\\ L=\max(0,\alpha_2^{old}+\alpha_1^{old})\\ H = \min(C,C+\alpha_2^{old}+\alpha_1^{old}) \end{cases}$
最后可得
$\alpha_2^{new}=\begin{cases} H ; \alpha_2>H\\ alpha_2^{new,unc} ; L \leq \alpha_2 \leq H\\ L; \alpha_2<L \end{cases}$
$\alpha_1^{new}=\alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})$
关于阈值b和插值E的更新
每次更新完 $\alpha_1,\alpha_2$ 以后， $b^{new}$ 的更新公式为
$b_1^{new}=-E_1-y1K_{11}(\alpha_1^{new}-\alpha_1^{old})-y2K_{21}(\alpha_2^{new}-\alpha_2^{old})+b_1^{old}$
$b_2^{new}=-E_2-y1K_{12}(\alpha_2^{new}-\alpha_2^{old})-y2K_{22}(\alpha_2^{new}-\alpha_2^{old})+b_2^{old}$
$E_i$ 的更新公式如下
$E_i^{new}=\sum_{j=1}^n\alpha_jy_jK_{ij}+b^{new}-y_i$

【转载】pluskid的SVM系列博文
基本篇：支持向量机: Maximum Margin Classifier —— 支持向量机简介。支持向量机: Su...
【机器学习实战】第6章支持向量机（Support Vector
第6章支持向量机支持向量机概述支持向量机(Support Vector Machines, SVM)：是一...
SVM支持向量机
线性支持向量机# 径向支持向量机# 最优参数##
编程作业（六）
支持向量机支持向量机本部分练习，我们将在2D示例数据集上使用支持向量机。通过在这些数据集上使用支持向量机，将帮...
支持向量机-QA
Q1：SVM的类型有哪些？三类：线性可分支持向量机、线性支持向量机、非线性支持向量机线性可分支持向量机：当训练数...
支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
机器学习——libSVM（一）
一、什么是支持向量机支持向量机（Support Vector Machine,SVM）也称为支持向量网络。是一类...
支持向量机&&聚类
支持向量机SVM（Support Vector Machine）一、支持向量机的原理 Support Vecto...
支持向量机
问题 1. 支持向量机是如何进行数据分类？ 2. 支持向量机求解过程 3. 支持向量机是怎么对线性不...
【9%】100小时机器学习——支持向量机SVM
支持向量机