凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

支持向量机基础简述_支持向量机是基于经验风险最小化原则构造的，因此有更好的泛华性能

作者：凡人多烦事01 | 2024-04-02 10:53:41

踩

支持向量机是基于经验风险最小化原则构造的，因此有更好的泛华性能

学习笔记来自《知识发现》—史忠植

支持向量机(support vector machine,SVM)建立在学习理论的结构风险最小化原则之上。

主要思想：针对两分类问题，在高位空间中寻找一个超平面作为两类的分割，以保>证最小的分类错误率。
优点：SVM可以处理 线性不可分 情况。

1.统计学习问题

1.1 经验风险

机器学习问题就是根据 l 个独立同分布的观测样本

\begin{matrix} (1.1) & (x_{1}, y_{1}), (x_{2}, y_{2}), . . ., (x_{l}, y_{l}) \end{matrix}

$(x_1,y_1),(x_2,y_2),...,(x_l,y_l) \tag{1.1}$ 在一组函数

f (x, w)

${f(x,w)}$ 中,找到一个最优的函数

f (x, w_{0})

$f(x,w_0)$ ，对依赖关系进行估计，使 期望风险

\begin{matrix} (1.2) & R (w) = \int L (y, f (x, w)) d F (x, y) \end{matrix}

$R(w)=\int L(y,f(x,w))dF(x,y) \tag{1.2}$ 最小，其中

f (x, w)

${f(x,w)}$ 称为预测函数集，

w

$w$ 为函数的广义参数。

f (x, w)

${f(x,w)}$ 可以表示任何函数集。

L (y, f (x, w))

$L({y,f(x,w)})$ 为用

f (x, w)

${f(x,w)}$ 对y进行预测造成的损失。
传统学习方法中，采用经验风险最小化(empririal risk minimization,ERM)准则，即用样本定义 、经验风险：

\begin{matrix} (1.3) & R_{e m p} (w) = \frac{1}{2} \sum_{i = 1}^{l} L (x, f (x, w)) \end{matrix}

$R_{emp}(w) = {1\over2}\sum_{i=1}^lL(x,f(x,w)) \tag{1.3}$
机器学习就是要设计学习算法使

R_{e m p} (w)

$R_{emp}(w)$ 最小化，作为对式(2)的估计。

1.2 VC维

模式识别中，VC维：对一个指示函数集，如果存在 h个样本能够被函数集里的函数按照所有可能的 $2^h$ 中形式分开，则称函数集能够把h个样本打散。函数集里的VC维就是它能打散的最大样本数目h。

有界实函数的VC维可以通过用一定的阈值将他转化成指示函数来定义

2.支持向量机

2.1 线性可分

假设存在训练样本 $(x_1,y_1),...,(x_l,y_l),x \in R^n,y \in \{+1,-1\}$ ,l为样本数，n为输入维数，在线性可分的情况下就会有一个超平面使得这两类样本完全分开，描述为

\begin{matrix} (2.1.1) & (\vec{w} \cdot \vec{x}) + \vec{b} = 0 \end{matrix}

$({\overrightarrow w} \cdot {\overrightarrow x})+{\overrightarrow b} = 0 \tag{2.1.1}$ 分类如下：

\vec{w} \cdot {\vec{x}}_{i} + \vec{b} \geq 0 ， 对 于 y_{i} = + 1

$\overrightarrow w \cdot \overrightarrow x_i + \overrightarrow b \ge0，对于y_i=+1$

\vec{w} \cdot {\vec{x}}_{i} + \vec{b} \leq 0 ， 对 于 y_{i} = - 1

$\overrightarrow w \cdot \overrightarrow x_i + \overrightarrow b \le0，对于y_i=-1$

\vec{w}

$\overrightarrow w$ 是超平面的法线方向，

\frac{\vec{w}}{‖ w ‖}

${\overrightarrow w} \over \Vert w \Vert$ 为单位向量，其中

‖ w ‖

$\Vert w \Vert$ 为欧式模函数。

如果训练数据可以无误差地被划分，以及每一类数据与超平面距离最近的向量与超平面之间的距离最大，则称这个超平面为最优超平面

图 2.1 最 优 超 平 面

$图2.1 最优超平面$ 在线性可分情况下，可以将求解最优超平面看成解二次型规划的问题。因此，对权值

w

$w$ 和偏移

b

$b$ 的最优值，使得权值代价函数最小化

\begin{matrix} (2.1.2) & m i n Φ (w) = \frac{1}{2} ‖ w ‖ \end{matrix}

$min \Phi(w)={1 \over 2}{\Vert w \Vert} \tag{2.1.2}$ 满足约束条件

\begin{matrix} (2.1.3) & y_{i} (w \cdot x_{i} + b) - 1 \geq 0, i = 1, 2, . . ., l \end{matrix}

$y_i(w \cdot x_i+b)-1 \ge0,\quad i=1,2,...,l \tag{2.1.3}$ 可由Lagrange乘子法求解，引入Lagrange乘子

α_{i} \geq 0 (i = 1, 2, . . ., l)

$\alpha_i \ge0(i=1,2,...,l)$

\begin{matrix} (2.1.4) & L (w, b, α) = \frac{1}{2} {‖ w ‖}^{2} - \sum_{i = 1}^{l} α_{i} y_{i} (x_{i} \cdot w + b) - 1 \end{matrix}

$L(w,b,\alpha)={1\over 2}{\Vert w \Vert}^2-\sum_{i=1}^l{\alpha_i{{y_i(x_i \cdot w+b)-1}}} \tag{2.1.4}$ 这里

L

$L$ 的极值点为鞍点，可取

L

$L$ 对

w

$w$ 和

b

$b$ 的最小值

w = w^{*}, b = b^{*}

$w=w^* ,b=b^*$ ,以及对

α

$\alpha$ 的最大值

α = α^{*}

$\alpha = \alpha^*$ .对

L

$L$ 求导可得

\begin{matrix} (2.1.5) & \frac{\partial L}{\partial b} = \sum_{i = 1}^{l} y_{i} α_{i} = 0 \end{matrix}

${\partial L\over \partial b}=\sum_{i=1}^l{y_i\alpha_i}=0 \tag{2.1.5}$

\begin{matrix} (2.1.6) & \frac{\partial L}{\partial w} = w - \sum_{i = 1}^{l} y_{i} α_{i} x_{i} = 0 \end{matrix}

${\partial L\over \partial w}=w-\sum_{i=1}^l{y_i\alpha_ix_i}=0 \tag{2.1.6}$ 其中，

\frac{\partial L}{\partial w} = (\frac{\partial L}{\partial w_{1}}, \frac{\partial L}{\partial w_{2}}, . . ., \frac{\partial L}{\partial w_{l}})

${\partial L\over \partial w}=({\partial L\over \partial w_1},{\partial L\over \partial w_2},...,{\partial L\over \partial w_l})$ . SVM通过求解二次规划，得到对应的

α^{*}

$\alpha^*$ 和

w^{*}

$w^*$

\begin{matrix} (2.1.7) & w^{*} = \sum_{i = 1}^{l} y_{i} α_{i} x_{i} \end{matrix}

$w^* = \sum_{i=1}^l{y_i\alpha_ix_i} \tag{2.1.7}$ 最优平面如图2.1。
经过变换线性可分条件下的原问题成为对偶问题，求解下式的极大化

\begin{matrix} (2.1.8) & max_{α} W (α) = \sum_{i = 1}^{l} α - \frac{1}{2} \sum_{i = 1}^{l} \sum_{j = 1}^{l} α_{i} α_{j} y_{i} y_{j} x_{i} \cdot x_{j} = Γ \cdot I - \frac{1}{2} Γ \cdot D Γ \end{matrix}

$\operatorname*{max}_{\alpha}W(\alpha)=\sum_{i=1}^l{\alpha}-{{1\over2}{\sum_{i=1}^l}{\sum_{j=1}^l}{\alpha_i\alpha_jy_iy_jx_i \cdot x_j}}=\Gamma \cdot I - {1\over 2}\Gamma \cdot D\Gamma \tag{2.1.8}$ 满足约束

\begin{matrix} (2.1.9) & \sum_{i = 1}^{l} y_{i} α_{i} = 0, i = 1, 2, . . ., l \end{matrix}

$\sum_{i=1}^l{y_i\alpha_i}=0,\quad i=1,2,...,l \tag{2.1.9}$ 其中，

Γ = (α_{1}, α_{2}, . . ., α_{l})

$\Gamma=(\alpha_1,\alpha_2,...,\alpha_l)$ ,

I = (1, 1, . . ., 1)

$I=(1,1,...,1)$ ,

D

$D$ 是

l \times l

$l\times l$ 的对称矩阵，各个单元为

\begin{matrix} (2.1.10) & D_{i j} = y_{i} y_{j} x_{i} \cdot x_{j} \end{matrix}

$D_{ij}=y_iy_jx_i \cdot x_j \tag{2.1.10}$ 在对这类约束优化问题的求解和分析中，Karush-Kuhn-Tucher(KKT)条件将起重要作用。式(2.9)的解必须满足

\begin{matrix} (2.1.11) & α_{i} {y_{i} (w \cdot x_{i} + b) - 1} = 0, i = 1, 2, . . ., l \end{matrix}

$\alpha_i{\{y_i(w \cdot x_i +b)-1\}}=0,\quad i=1,2,...,l \tag{2.1.11}$ 由式(2.7)可知，当

α_{i} = 0

$\alpha_i=0$ 的样本对分类问题不起作用，只有

α_{i} > 0

$\alpha_i\gt 0$ 的样本对

w^{*}

$w^*$ 起作用，才决定分类结果。 这样的样本定义为支持向量。
选用一个支持向量样本

x_{i}

$x_i$ ,可以求得

b^{*}

$b^*$ 为

\begin{matrix} (2.1.12) & b^{*} = y_{i} - w \cdot x_{i} \end{matrix}

$b^* = y_i - w \cdot x_i \tag{2.1.12}$ 对输入样本

x

$x$ 测试时，计算

\begin{matrix} (2.1.13) & d (x) = x \cdot w^{*} + b^{*} = \sum_{i = 1}^{l} y_{i} α_{i}^{*} (x \cdot x_{i}) + b^{*} \end{matrix}

$d(x) = x \cdot w^* +b^* = \sum_{i=1}^ly_i\alpha_i^* (x \cdot x_i) + b^* \tag{2.1.13}$ 根据

s (x)

$s(x)$ 的符号来确认

x

$x$ 的归属。

2.2 线性不可分

线性可分的判别函数建立在欧式距离的基础上，即有 $K(x_i,x_j) = x_i \cdot x_j=x_i^Tx_j$ .而非线性问题，可将样本 $x$ 映射到某个高维特征空间 $H$ 如图2.2，并在 $H$ 中使用线性分类器，即将 $x$ 做变换 $\Phi:R^d \rightarrow H$

\begin{matrix} (2.2.1) & x \to Φ (x) = (ϕ_{1} (x), ϕ_{2} (x), \dots, ϕ_{i} (x), \dots)^{T} \end{matrix}

$x\rightarrow\Phi(x) = (\phi_1(x),\phi_2(x),…,\phi_i(x),…)^T \tag{2.2.1}$ 其中，

ϕ_{i} (x)

$\phi_i(x)$ 是实函数。

![输入空间到特征空间的映射][2]

图 2.2 输 入 空 间 到 特 征 空 间 的 映 射

$图2.2 输入空间到特征空间的映射$ 如果以特征向量

Φ (x)

$\Phi(x)$ 代替输入向量

x

$x$ ，则由式(2.1.10)和式(2.1.13)可知

\begin{matrix} (2.2.2) & D_{i j} = y_{i} y_{j} Φ (x_{i}) \cdot Φ (x_{j}) \end{matrix}

$D_{ij}=y_iy_j\Phi(x_i) \cdot \Phi(x_j) \tag{2.2.2}$

\begin{matrix} (2.2.3) & d (x) = Φ (x) \cdot w^{*} + b = \sum_{i = 1}^{l} α_{i} y_{i} Φ (x_{i}) \cdot Φ (x) + b^{*} \end{matrix}

$d(x)=\Phi(x) \cdot w^* +b = \sum_{i=1}^l \alpha_iy_i\Phi(x_i) \cdot \Phi(x) + b^* \tag{2.2.3}$ 不论是寻优函数式(2.1.8)还是分类函数式(2.1.13)都只涉及训练样本之间的内积

(x_{i} \cdot x_{j})

$(x_i \cdot x_j)$ .*根据泛函数相关理论，只要一种核函数

K (x_{i} \cdot x_{j})

$K(x_i \cdot x_j)$ 满足Mercer条件，它就对应某一空间中的内积。* 在最优分类面中采用适当的内积函数

K (x_{i} \cdot x_{j})

$K(x_i \cdot x_j)$ 就可实现某一非线性变换后的线性分类，而计算复杂度却没增加，那么式(2.1.8)可变为

\begin{matrix} (2.2.4) & max_{α} W (α) = \sum_{i = 1}^{l} α - \frac{1}{2} \sum_{i = 1}^{l} \sum_{j = 1}^{l} α_{i} α_{j} y_{i} y_{j} K (x_{i}, x_{j}) \end{matrix}

${\operatorname*{max}_{\alpha}}W(\alpha)=\sum_{i=1}^l{\alpha}-{{1\over2}{\sum_{i=1}^l}{\sum_{j=1}^l}{\alpha_i \alpha_j y_i y_j K(x_i,x_j)}} \tag{2.2.4}$

则对应的分类函数为

\begin{matrix} (2.2.5) & d (x) = x \cdot w^{*} + b^{*} = \sum_{i = 1}^{l} y_{i} α_{i}^{*} K (x, x_{j}) + b^{*} \end{matrix}

$d(x) = x \cdot w^* +b^* = \sum_{i=1}^l y_i\alpha_i^* K(x,x_j) + b^* \tag{2.2.5}$
这就是支持向量机。

对给定的 $K(x,y)$ ,存在对应的 $\Phi(x)$ 的充要条件是：对于任意给定的函数 $g(x)$ ，当 $\int_a^bg(x)^2dx$ 有限时，有

\begin{matrix} (2.2.6) & \int_{a}^{b} \int_{a}^{b} K (x, y) g (x) g (y) d x d y \geq 0 \end{matrix}

$\int_a^b\int_a^bK(x,y)g(x)g(y)dxdy\ge0 \tag{2.2.6}$ 该条件不容易实际操作，可通过多项式逼近 $K(x,y)$ 实现，因为多项式满足Mercer条件。
构造类型判定函数的学习机称为支持向量机，在支持向量机中构造的复杂性取决于支持向量机的数目，而不是特征空间的维数。示意图如图2.3.

图 2.3 支 持 向 量 机 示 意 图

$图2.3 支持向量机示意图$ 对非线性问题支持向量机，首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在该空间中求广义最优分类面。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/351951