关于SVM的一点笔记

一. 简单了解

1.感知机(perceptron)

感知机是一种类似于生物中神经细胞功能的人工神经元，它可以把一个或者多个输入($x_1$x1​, $x_2$x2​, $x_3$x3​, …)根据权重($w_1$w1​, $w_2$w2​, $w_3$w3​, …)与输入值乘积之和(即$\sum_{j}w_jx_j$∑j​wj​xj​)转变为-1或+1输出，而判断的依据是$\sum_{j}w_jx_j$∑j​wj​xj​是否大于或者小于某个阈值(threshold)，这就是感知机的基本原理，同样可以表述为：
$output=\begin{cases} -1 &amp;if \ \sum_{j}w_jx_j&lt;threshold\\ +1 &amp;if \ \sum_{j}w_jx_j≥threshold \end{cases}$output={−1+1​if ∑j​wj​xj​<thresholdif ∑j​wj​xj​≥threshold​
如果我们令X={$x_1$x1​, $x_2$x2​, $x_3$x3​, …}，W={$w_1$w1​, $w_2$w2​, $w_3$w3​, …}，则对向量$\vec{x}$x∈X，向量$\vec{w}$w∈W，记
$f(x)=sign(\vec{x} \cdot \vec{w} + b)$f(x)=sign(x⋅w+b)
式中$\vec{x}$x为空间的特征向量，$\vec{w}$w为权值向量(weight)，b为阈值，又被称为偏置(bias)，$\vec{x} \cdot \vec{w}$x⋅w 为$\vec{x}$x和$\vec{w}$w的点积。
那么有
$f(x)=\begin{cases} -1 &amp;if \ \vec{x} \cdot \vec{w} + b&lt;0\\ +1 &amp;if \ \vec{x} \cdot \vec{w} + b≥0 \end{cases}$f(x)={−1+1​if x⋅w+b<0if x⋅w+b≥0​

2. 线性回归

线性回归主要就是要根据已有的数据拟合出一条较为符合预期的直线，用这条直线对新的数据进行合理预测。例如，各类价格走势预测、商品销量预测等。
对于最基本的线性回归问题，我们令其公式为：
$h(x)=h_θ(x)=θ_0+θ_1x_1+θ_2x_2+...+θ_ix_i$h(x)=hθ​(x)=θ0​+θ1​x1​+θ2​x2​+...+θi​xi​
式中，$θ_0$θ0​类似于感知机中的阈值b，$θ_i$θi​则类似于感知机中的权重$w$w。
然后我们需要引入损失函数(cost function)：
$J(θ)=\frac{1}{2}\sum_{i=1}^{m}(h_θ(x^{(i)})^2-y^{(i)})^2$J(θ)=21​i=1∑m​(hθ​(x(i))2−y(i))2
它表示每一项预测值与实际值差平方之和的二分之一，若我们可以找到$J$J($\theta$θ)的最小值，那么我们就认为函数$h_\theta(x)$hθ​(x)为我们找的线性回归函数。
下面我们讨论如何求得$J$J($\theta$θ)的最小值 min$J$J($\theta$θ)：
$J$J($\theta$θ)对每一个$\theta$θ求偏导，则有：
$\begin{aligned} \frac{\partial J(\theta)}{\partial \theta_j} &amp;=\frac{\partial }{\partial \theta_j} \frac{1}{2}(h_\theta(x)-y)^2\\ &amp;= 2\cdot\frac{1}{2}(h_\theta(x)-y)\cdot\frac{\partial }{\partial \theta_j} (h_\theta(x)-y)\\ &amp;= (h_\theta(x)-y) \cdot\frac{\partial }{\partial \theta _j}(\sum_{i=0}^n\theta_ix_i-y)\\ &amp;= (h_\theta(x)-y)x_j \end{aligned}$∂θj​∂J(θ)​​=∂θj​∂​21​(hθ​(x)−y)2=2⋅21​(hθ​(x)−y)⋅∂θj​∂​(hθ​(x)−y)=(hθ​(x)−y)⋅∂θj​∂​(i=0∑n​θi​xi​−y)=(hθ​(x)−y)xj​​
那么我们可以得到：
$\theta_j:=\theta_j+\alpha\sum_{i=1}^m(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$θj​:=θj​+αi=1∑m​(y(i)−hθ​(x(i)))xj(i)​
上式即为$\theta_j$θj​梯度下降的数学表达形式，即可得到参数$\theta_j$θj​，从而我们就得到了$h(x)$h(x)的确切表达式。
但是，我们在拟合时会出现过度拟合的情况，从而我们需要引入另外一项——惩罚项。惩罚项在一定程度上可以防止出现过度拟合的情况。
那么，加入惩罚项后的$J$J($\theta$θ)方程为：
$J(θ)=\frac{1}{2}\sum_{i=1}^{m}(h_θ(x^{(i)})^2-y^{(i)})^2+\lambda\sum_{j=1}^n\theta_j^2$J(θ)=21​i=1∑m​(hθ​(x(i))2−y(i))2+λj=1∑n​θj2​

3. logistic回归

logistic函数的值域介于0到1之间，其函数表达式为：
$logistic=g(z)=\frac{1}{1+e^{-z}}$logistic=g(z)=1+e−z1​
承接线性回归部分，将函数$h(x)=h_θ(x)=θ_0+θ_1x_1+θ_2x_2+...+θ_ix_i$h(x)=hθ​(x)=θ0​+θ1​x1​+θ2​x2​+...+θi​xi​转变为$h_\theta(x)=g(\theta^T\cdot x)$hθ​(x)=g(θT⋅x)，那么，$h_\theta(x)$hθ​(x)的函数值将介于0与1之间，使其结果概率化。与此同时，当当概率大于等于0.5，就判断为1，否则，判断为0。
从而，我们得到0与1两类数据。

二、SVM的实现

1.数学建模

SVM算法实际上就是一个数学优化问题，我们需要在一个多维空间上找到一个超平面（如果是二维平面，那么这个超平面就是一条直线），使到此超平面的距离最小的点的距离最大（这个距离我们称之为Margin）。鉴于表述与理解的方便，我们就以二维平面为例进行引入。
我们首先设上图中黄色直线的方程为A$x$x+B$y$y+C=0，然后把$x$x换为$x_1$x1​，$y$y换为$x_2$x2​，那么原直线方程就变为了A$x_1$x1​+B$x_2$x2​+C=0，同时，我们还可以将此方程写为$\left[ \begin{matrix} A&amp;B\\ \end{matrix} \right] \left[ \begin{matrix} x_1\\ x_2 \end{matrix} \right]+C=0$[A​B​][x1​x2​​]+C=0
若我们令
$\left[ \begin{matrix} A&amp;B\\ \end{matrix} \right]=\omega^T， \left[ \begin{matrix} x_1\\ x_2 \end{matrix} \right]=x， C=\gamma$[A​B​]=ωT，[x1​x2​​]=x，C=γ
那么上述方程还可写为$\omega^T\cdot x+\gamma=0$ωT⋅x+γ=0，实际上，对于多维空间而言，其超平面上式也是适用的。
由高中数学知识我们就可以得到，空间内一点到该超平面的距离d满足：
$d=\frac{|\omega^T\cdot x+\gamma|}{||\omega||}$d=∣∣ω∣∣∣ωT⋅x+γ∣​
式中，$||\omega||$∣∣ω∣∣为向量ω的模，$x$x为样本点的坐标，ω和γ即为要求超平面的参数。
如上图所示，我们假设已经找到了一个超平面$\omega^T\cdot x+\gamma=0$ωT⋅x+γ=0且距离超平面最近的点到此超平面的距离为d（即黄色线与粉红线之间的距离为d），那么则对此空间内任意一点都有
$\frac{|\omega^T\cdot x+\gamma|}{||\omega||}≥d$∣∣ω∣∣∣ωT⋅x+γ∣​≥d
如果我们把在超平面以上的判定为+1类，把在超平面以下的判定为-1类，那么有
$y^{(i)}=\begin{cases} -1 &amp;if \ \frac{\omega^T\cdot x+\gamma}{||\omega||}≤-d\\ +1 &amp;if \ \frac{\omega^T\cdot x+\gamma}{||\omega||}≥d \end{cases}$y(i)={−1+1​if ∣∣ω∣∣ωT⋅x+γ​≤−dif ∣∣ω∣∣ωT⋅x+γ​≥d​
整理可得
$y^{(i)}=\begin{cases} -1 &amp;if \ \frac{\omega^T\cdot x+\gamma}{||\omega||\cdot d}≤-1\\ +1 &amp;if \ \frac{\omega^T\cdot x+\gamma}{||\omega||\cdot d}≥1 \end{cases}$y(i)={−1+1​if ∣∣ω∣∣⋅dωT⋅x+γ​≤−1if ∣∣ω∣∣⋅dωT⋅x+γ​≥1​
若此时，我们令$\frac{\omega^T}{||\omega||\cdot d}=\omega^T_b$∣∣ω∣∣⋅dωT​=ωbT​，$\frac{\gamma}{||\omega||\cdot d}=\gamma_b$∣∣ω∣∣⋅dγ​=γb​
那么有
$y^{(i)}=\begin{cases} -1 &amp;if \ \omega^T_b\cdot x+\gamma_b≤-1\\ +1 &amp;if \ \omega^T_b\cdot x+\gamma_b≥1 \end{cases}$y(i)={−1+1​if ωbT​⋅x+γb​≤−1if ωbT​⋅x+γb​≥1​
此时，若我们就把$\omega^T_b,\gamma_b$ωbT​,γb​叫做$\omega^T,\gamma$ωT,γ，那么我们可以得到$y^{(i)}=\begin{cases} -1 &amp;if \ \omega^T\cdot x+\gamma≤-1\\ +1 &amp;if \ \omega^T\cdot x+\gamma≥1 \end{cases}$y(i)={−1+1​if ωT⋅x+γ≤−1if ωT⋅x+γ≥1​
利用一些数学技巧，我们可以了解到上式等价于
$y^{(i)}\cdot (\omega^T\cdot x^{(i)}+\gamma)≥1$y(i)⋅(ωT⋅x(i)+γ)≥1
通过上述推导我们可以知道，只有存在一个$x^{(i)}$x(i)使得上式中的等号成立时，我们才能找到那个支持向量，从而可以求得最大的Margin，得到超平面方程。
当上式中的等号成立时，我们有
$d=\frac{|\omega^T\cdot x+\gamma|}{||\omega||}=\frac{1}{||\omega||}$d=∣∣ω∣∣∣ωT⋅x+γ∣​=∣∣ω∣∣1​
则，我们需要求min$\frac{1}{||\omega||}$∣∣ω∣∣1​，等价于求min$\frac{1}{||\omega||^2}$∣∣ω∣∣21​(鉴于以后求导的方便)
我们便可以针对SVM给出其数学描述：
$min_{\omega,\gamma}\frac{1}{2}||\omega||^2\\ s.t. \ \ y^{(i)}\cdot (\omega^T\cdot x^{(i)}+\gamma)≥1,i=1,2,3,...,m$minω,γ​21​∣∣ω∣∣2s.t.  y(i)⋅(ωT⋅x(i)+γ)≥1,i=1,2,3,...,m