基础

本文基本上参考《李航-统计学习方法》进行学习、排版。

1. 二类分类模型；
2. 基本模型是定义在特征空间上、间隔最大的线性分类器；
3. 学习策略是间隔最大化，可形式化为求解凸二次规划问题，等价于正则化的损失函数最小化问题；
4. 和感知机有何区别：SVM是间隔最大化；
5. 模型细分类：
   （1）线性可分支持向量机：数据线性可分时，通过硬间隔最大化，学习线性上分类的SVM。
   （2）线性支持向量机（软间隔支持向量机）：数据近似线性可分时，通过软间隔最大化，学习线性SVM。
   （3）非线性支持向量机：数据线性不可分，通过核技巧（kernal） 以及软间隔最大化，学习非线性的SVM。
6. 核函数（kernal）：
   输入空间为欧氏空间（多维），或者离散集合，特征空间为希尔伯特空间（完备性）时，核函数表示了，从输入空间映射到特征空间得到的特征向量之间的内积。（之后再解释）
7. 最开始应该如何定义数据集和系数的维度？笔者不太理解《李航-统计学习方法》中，在对偶问题中，是否直接将$x_i$xi​视作一个点？
   笔者的理解：
   单个点计算情况

$y_i$yi​	($w$w	$x_i$xi​	+	$b$b )
1*1	1*d	d*1		1*1

$Y= \left[ \begin{matrix} y_1 \\ y_2 \\ ...\\ y_n\\ \end{matrix} \right]$Y=⎣⎢⎢⎡​y1​y2​...yn​​⎦⎥⎥⎤​

$\omega= \left[ \begin{matrix} \omega_1 \\ \omega_2 \\ ...\\ \omega_d\\ \end{matrix} \right]$ω=⎣⎢⎢⎡​ω1​ω2​...ωd​​⎦⎥⎥⎤​

$x_i= \left[ \begin{matrix} x_{i,1} \\ x_{i,2} \\ ...\\ x_{i,d} \\ \end{matrix} \right]$xi​=⎣⎢⎢⎡​xi,1​xi,2​...xi,d​​⎦⎥⎥⎤​

$X= \left[ \begin{matrix} x_{1}^{T} \\ x_{2}^{T} \\ ...\\ x_{n}^{T} \\ \end{matrix} \right]$X=⎣⎢⎢⎡​x1T​x2T​...xnT​​⎦⎥⎥⎤​

7.1 线性可分SVM

7.1.1 线性可分SVM定义

假设给定一个特征空间上的训练数据集为：
$T= \{ (x_1,y_1),...,(x_i,y_i),...,(x_N,y_N) \}$T={(x1​,y1​),...,(xi​,yi​),...,(xN​,yN​)}

$y_i \in y=[-1,+1]$yi​∈y=[−1,+1]

其中，$x_i \in x \equiv R^n$xi​∈x≡Rn 称作第i个特征向量，或者实例（理解为样本点）。

定义7.1（线性可分SVM）： 这里是引用《李航-统计学习方法》
给定的线性可分训练数据集，通过间隔最大化或者等价求解 —> 凸二次规划问题，学习到模型即分离超平面，以及判断函数：
$w^* * x+b=0 \\ \tag{7.1} f(x) = sign(w^* * x+b)$w∗∗x+b=0f(x)=sign(w∗∗x+b)(7.1)

7.1.2 函数间隔和集合间隔

函数间隔概念：分类准确度存在确定程度，在确定$w^* * x+b=0$w∗∗x+b=0 的超平面之后，能够得到目标点距离超平面的距离，距离越远，说明判断的确信程度更高。利用变量$y(w^* * x+b)$y(w∗∗x+b)来表示正确性和确信程度。

定义7.2（函数间隔，有hat）： 这里是引用《李航-统计学习方法》
给定的数据集T以及超平面$(w,b)$(w,b)，定义样本点和超平面的函数间隔为
$\hat{\gamma_{i}} = y_i * (w* x_i + b) \tag{7.3}$γi​^​=yi​∗(w∗xi​+b)(7.3)
此外，定义超平面$(w,b)$(w,b)关于训练数据集T的函数间隔为超平面关于所有样本点的函数间隔的最小值【也就是，最靠近】
$\hat{\gamma} = min \hat{\gamma_{i}} \tag{7.4}$γ^​=minγi​^​(7.4)

定义7.3（几何间隔，无hat）： 这里是引用《李航-统计学习方法》
由于$w$w的值对于距离有影响，所以需要进行规范化，使得它的范数为1。如果$||w||=1$∣∣w∣∣=1则两种间隔相同。
${\gamma_i} = y_i * (\frac{w}{||w||}*x_i + \frac{b}{||w||} ) \tag{7.5}$γi​=yi​∗(∣∣w∣∣w​∗xi​+∣∣w∣∣b​)(7.5)
类推，超平面关于关于训练数据集T的几何间隔为超平面关于所有样本点的几何间隔的最小值【也就是，最靠近】
${\gamma} = min {\gamma_{i}} \tag{7.6}$γ=minγi​(7.6)

7.1.3 间隔最大化（学习策略）

直观解释：找到“几何间隔”最大化的超平面，以达到最大的确信程度来进行分类。（尚未涉及可能出现分类混杂于彼此的样本小现象）

1. 最大间隔分离超平面
   $\max_{w,b}\ \gamma \\ subject \ to \ \hat{\gamma_i} = y_i * (\frac{w}{||w||}*x_i + \frac{b}{||w||} ) \\ \hat{\gamma} = min \hat{\gamma_{i}}$w,bmax​ γsubject to γi​^​=yi​∗(∣∣w∣∣w​∗xi​+∣∣w∣∣b​)γ^​=minγi​^​
   由于几何间隔的“地板”为$\gamma$γ，然后再最大化这个指标，写作：
   $\max_{w,b}\ \ \gamma \\ s.t. \ y_i * (\frac{w}{||w||}*x_i + \frac{b}{||w||} ) \geq {\gamma} \tag{7.10}$w,bmax​  γs.t. yi​∗(∣∣w∣∣w​∗xi​+∣∣w∣∣b​)≥γ(7.10)
   写成函数间隔（带hat）的形式，可能存在$\lambda$λ使得距离进行拉伸，
   $\lambda w ,\lambda b --> \lambda \gamma$λw,λb−−>λγ，所以取$\gamma = 1$γ=1
   重新写最优化问题：
   $\min_{w,b}\ \frac{1}{2}||w||^2 \\ s.t. \ y_i(w*x_i + b) - 1 \geq 0, \ i=1,2,...,N$w,bmin​ 21​∣∣w∣∣2s.t. yi​(w∗xi​+b)−1≥0, i=1,2,...,N
   求解之后，得到：超平面+分类决策函数

2. 最大间隔分离超平面的存在性及唯一性
   存在性：数据集线性可分，而且目标函数有下界，因此有解。而且，如果$w=0$w=0则无法单纯依靠系数$b$b得到分类，因此解满足$w \neq 0$w̸​=0
   唯一性：分别证明$w$w以及$b$b
   （1）证明$w$w：
   假设有两个$w$w符合要求，即$(w_1,b_1)$(w1​,b1​)以及$(w_2,b_2)$(w2​,b2​)；
   因为取最优的最小值，得到$||w_1||=||w_2||=const$∣∣w1​∣∣=∣∣w2​∣∣=const；
   令$w = \frac{w_1 + w_2}{2}$w=2w1​+w2​​以及$b = \frac{b_1 + b_2}{2}$b=2b1​+b2​​，则没法达到最小值，有$c \leq ||w||$c≤∣∣w∣∣；
   依靠模的计算，有$||w|| \leq \frac{1}{2}||w_1|| + \frac{1}{2}||w_2|| = c$∣∣w∣∣≤21​∣∣w1​∣∣+21​∣∣w2​∣∣=c；
   （夹逼）因此有$||w|| = \frac{1}{2}||w_1|| + \frac{1}{2}||w_2||$∣∣w∣∣=21​∣∣w1​∣∣+21​∣∣w2​∣∣，$w_1,w_2$w1​,w2​角度为0，方向相同，$w_1 = \lambda w_2, |\lambda|=1$w1​=λw2​,∣λ∣=1，$\lambda$λ取-1时，则$w=0$w=0不满足存在性，应该取1，则有$w_1 = w_2$w1​=w2​
   （2）证明$b$b：

7.1.4 学习的对偶算法

笔者疑问：对偶问题求解相比原始问题有何优势？

引子1：拉格朗日

1. 原始问题：各式子均可微
   $\min_{x \in R^n}{f(x)} \\ s.t. \ {c_i(x) \leq 0} \\ h_j(x) = 0$x∈Rnmin​f(x)s.t. ci​(x)≤0hj​(x)=0
2. 引进拉格朗日函数:$\alpha_i \geq 0$αi​≥0
   $L(x,\alpha, \beta) = f(x) + \sum_{i=1}^{k}{\alpha_i c_{i}(x)} + \sum_{i=1}^{l}{\beta_j h_{j}(x)}$L(x,α,β)=f(x)+i=1∑k​αi​ci​(x)+i=1∑l​βj​hj​(x)
   引入 $x$x的函数：注意max底下并没有x，说明其中的$f(x)$f(x)项并没有起到最大化效果。$p$p表示原始问题。
   $\theta_P(x) = \max_{\alpha, \beta; \alpha \geq 0}{L(x,\alpha,\beta)}$θP​(x)=α,β;α≥0max​L(x,α,β)
   换言之：
   假设$x$x引发两个条件，即存在$i,j$i,j使得$c_i(x) \leq 0 ,h_j(x) = 0$ci​(x)≤0,hj​(x)=0无法成立，因为$\alpha_i, \beta_j -> +\infty$αi​,βj​−>+∞则
   $\max_{\alpha, \beta; \alpha \geq 0} \sum_{i=1}^{k}{\alpha_i c_{i}(x)} = +\infty \\ \max_{\alpha, \beta; \alpha \geq 0} \sum_{i=1}^{l}{\beta_j h_{j}(x)} = +\infty$α,β;α≥0max​i=1∑k​αi​ci​(x)=+∞α,β;α≥0max​i=1∑l​βj​hj​(x)=+∞
   因此有：
   $\theta_P(x) = \max_{\alpha, \beta; \alpha \geq 0}{L(x,\alpha,\beta)}= \begin{cases} f(x), Conditions Satisfied\\ +\infty, NotSatisfied \\ \end{cases}$θP​(x)=α,β;α≥0max​L(x,α,β)={f(x),ConditionsSatisfied+∞,NotSatisfied​
3. 考虑原始问题$\min_{x \in R^n}{f(x)}$minx∈Rn​f(x) 则有“拉格朗日极小极大问题”：
   $\min_{x \in R^n}{f(x)}=\min_{x \in R^n}{\theta_P(x) }=\min_{x\in R^n}\max_{\alpha, \beta; \alpha \geq 0}{L(x,\alpha,\beta)}$x∈Rnmin​f(x)=x∈Rnmin​θP​(x)=x∈Rnmin​α,β;α≥0max​L(x,α,β)
4. 原始问题的值：$p^* = \min_{x \in R^n}{\theta_P(x) }$p∗=minx∈Rn​θP​(x)

引子2：拉格朗日对偶问题

1. “拉格朗日极大极小问题”（$min,max$min,max的下标一样需要跟进）：
   $\max_{\alpha, \beta; \alpha \geq 0 }{\theta_D(\alpha, \beta) }=\max_{\alpha, \beta; \alpha \geq 0} \min_{x \in R^n}{L(x,\alpha,\beta)}$α,β;α≥0max​θD​(α,β)=α,β;α≥0max​x∈Rnmin​L(x,α,β)
   对偶问题的值：$d^* = \max_{\alpha, \beta; \alpha \geq 0 }{\theta_D(\alpha, \beta) }$d∗=maxα,β;α≥0​θD​(α,β)
2. 对偶问题和原始问题的关系：
   （1）
   $\theta_D(\alpha, \beta) = \min_{x \in R^n}{L(x,\alpha,\beta)} \leq L(x,\alpha,\beta) \\ \leq \max_{\alpha, \beta; \alpha \geq 0}{L(x,\alpha,\beta)} = \theta_P(x)$θD​(α,β)=x∈Rnmin​L(x,α,β)≤L(x,α,β)≤α,β;α≥0max​L(x,α,β)=θP​(x)
   即有，$\theta_D(\alpha, \beta) \leq \theta_P(x)$θD​(α,β)≤θP​(x)
   所以两者的最优值有大小关系，$d^* = \max_{\alpha, \beta; \alpha \geq 0 }{\theta_D(\alpha, \beta) } \leq \min_{x \in R^n}{\theta_P(x) }=p^*$d∗=α,β;α≥0max​θD​(α,β)≤x∈Rnmin​θP​(x)=p∗

（2）$x^*$x∗是原始问题的解，$\alpha^*,\beta^*$α∗,β∗是对偶问题的解
<— 充分必要条件 —>
KKT条件（图片来自于《统计学习方法-李航》）
拉格朗日函数要对$x,\alpha,\beta$x,α,β求导得0，其他满足于前文所示条件。

如何进行学习的对偶算法

由7.1.3我们得到应该求得的最优化凸二次规划问题

$\min_{w,b}\ \frac{1}{2}||w||^2 \\ s.t. \ y_i(w*x_i + b) - 1 \geq 0, \ i=1,2,...,N$w,bmin​ 21​∣∣w∣∣2s.t. yi​(w∗xi​+b)−1≥0, i=1,2,...,N

构造拉格朗日函数：在此拉格朗日中的$x$x为问题中的$\omega, b$ω,b

$L(\omega,b, \alpha, \beta) = f(\omega,b) + \sum_{i=1}^{k}{\alpha_i c_{i}(\omega,b)} + \sum_{i=1}^{l}{\beta_j h_{j}(\omega,b)} \\ = \frac{1}{2}||w||^2 + \sum_{i=1}^{k}{\alpha_i (1 - y_i(w*x_i + b))} \\ = \frac{1}{2}||w||^2 - \sum_{i=1}^{k}{\alpha_i y_i(w*x_i + b)} + \sum_{i=1}^{k}{\alpha_i * 1}$L(ω,b,α,β)=f(ω,b)+i=1∑k​αi​ci​(ω,b)+i=1∑l​βj​hj​(ω,b)=21​∣∣w∣∣2+i=1∑k​αi​(1−yi​(w∗xi​+b))=21​∣∣w∣∣2−i=1∑k​αi​yi​(w∗xi​+b)+i=1∑k​αi​∗1

通过对偶问题来求解，极大极小问题

$\max_{\alpha; \alpha \geq 0} \min_{\omega b \in R^n}{L(\omega,b,\alpha)}$α;α≥0max​ωb∈Rnmin​L(ω,b,α)

（1）先求解 $\min_{\omega b \in R^n}{L(\omega,b,\alpha)}$minωb∈Rn​L(ω,b,α): 对于$\omega,b$ω,b求导

$\nabla_{\omega} L(\omega,b,\alpha) = w-\sum_{i=1}^{N}{\alpha_i y_ix_i }=0 \\ \nabla_{b} L(\omega,b,\alpha) = - \sum_{i=1}^{N}{\alpha_i y_i} = 0$∇ω​L(ω,b,α)=w−i=1∑N​αi​yi​xi​=0∇b​L(ω,b,α)=−i=1∑N​αi​yi​=0

所以，得到目标的表达式和另外的条件。如果看下表，则$\omega$ω不应该按照如下公式表示，$x_i$xi​需要转置。（但暂时不看向量的积的维度问题）

$y_i$yi​	($w$w	$x_i$xi​	+	$b$b )
1*1	1*d	d*1		1*1

$w = \sum_{i=1}^{N}{\alpha_i y_ix_i } \\ \sum_{i=1}^{N}{\alpha_i y_i} = 0$w=i=1∑N​αi​yi​xi​i=1∑N​αi​yi​=0

将其代入$L(\omega,b,\alpha)$L(ω,b,α)之中，得到

$L(\omega,b,\alpha) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \\ -\sum_{i=1}^{N} \alpha_i y_i ((\sum_{j=1}^{N} \alpha_j y_j x_j) \cdot x_i +b) + \sum_{i=1}^{N} \alpha_i \\ =\sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)$L(ω,b,α)=21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​yi​((j=1∑N​αj​yj​xj​)⋅xi​+b)+i=1∑N​αi​=i=1∑N​αi​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)

得到下一步的输入物：

$\min_{\omega, b \in R^n}{L(\omega,b,\alpha)} = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)$ω,b∈Rnmin​L(ω,b,α)=i=1∑N​αi​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)

（2）开始求极大极小中的极大问题，

$\max_{\alpha; \alpha \geq 0} \min_{\omega b \in R^n}{L(\omega,b,\alpha)}\\ = \max_{\alpha} \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \\ s.t. \ \sum_{i=1}^{N}{\alpha_i y_i} = 0\\ \alpha_i \geq 0$α;α≥0max​ωb∈Rnmin​L(ω,b,α)=αmax​i=1∑N​αi​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)s.t. i=1∑N​αi​yi​=0αi​≥0

转化为极小问题

$\min_{\alpha; \alpha \geq 0} {L(\omega,b,\alpha)}\\ = \min_{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) -\sum_{i=1}^{N} \alpha_i\\ s.t. \ \sum_{i=1}^{N}{\alpha_i y_i} = 0\\ \alpha_i \geq 0$α;α≥0min​L(ω,b,α)=αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​s.t. i=1∑N​αi​yi​=0αi​≥0

支持向量

将训练数据集中对应于$\alpha_i &gt;0$αi​>0的样本点$(x_i, y_i)$(xi​,yi​)的实例$x_i \in R^n$xi​∈Rn称为支持向量。由于存在KKT条件，$\alpha_i (y_i (w * x_i +b)-1)=0$αi​(yi​(w∗xi​+b)−1)=0，需要解同时符合

$y_i (w * x_i +b)=1$yi​(w∗xi​+b)=1

因此$x_i$xi​是在间隔边界上。

优缺点

【参考 https://blog.****.net/x1kz18nkbqg/article/details/78690795 】
SVM算法的主要优点有：

1. 解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果。
2. 仅仅使用一部分支持向量来做超平面的决策，无需依赖全部数据。
3. 有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题。
4. 样本量不是海量数据的时候，分类准确率高，泛化能力强。

SVM算法的主要缺点有：

1. 如果特征维度远远大于样本数，则SVM表现一般。
2. SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用。
3. 非线性问题的核函数的选择没有通用标准，难以选择一个合适的核函数。
4. SVM对缺失数据敏感。

用于回归问题

【参考】
https://blog.****.net/x1kz18nkbqg/article/details/78690795
https://blog.****.net/luoshixian099/article/details/51121767

参考书目

1. 李航-统计学习方法
2. 西瓜书
3. 清华大学深圳研究生院袁春ppt