支持向量机基本原理
- 格式：docx
- 大小：38.43 KB
- 文档页数：10
支持向量机基本原理
支持向量机基本原理
支持向量机（Support Vector Machine，SVM）是一种基于统计学习理论的分类器，广泛应用于模式识别、图像处理、生物信息学等领域。
SVM在处理高维数据和小样本问题时表现出色，具有较强的泛化能力和鲁棒性。
一、线性可分支持向量机
1.1 概念定义
给定一个训练数据集$D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中$x_i\in R^n$为输入样本，$y_i\in\{-1,1\}$为输出标记。
线性可分支持向量机的目标是找到一个超平面将不同类别的样本分开，并使得该超平面到最近的样本点距离最大。
设超平面为$x^Tw+b=0$，其中$w\in R^n$为法向量，$b\in R$为截距，则样本点$x_i$到超平面的距离为：
$$
r_i=\frac{|x_i^Tw+b|}{||w||}
$$
对于任意一个超平面，其分类效果可以用间隔来度量。
间隔指的是两个异类样本点到超平面之间的距离。
因此，最大化间隔可以转化为以下优化问题：
$$
\max_{w,b}\quad \frac{2}{||w||}\\
s.t.\quad y_i(x_i^Tw+b)\geq1,\quad i=1,2,...,N
$$
其中，$y_i(x_i^Tw+b)-1$为样本点$x_i$到超平面的函数间隔。
因为函数间隔不唯一，因此我们需要将其转化为几何间隔。
1.2 函数间隔与几何间隔
对于一个给定的超平面，其函数间隔定义为：
$$
\hat{\gamma}_i=y_i(x_i^Tw+b)
$$
而几何间隔定义为：
$$
\gamma_i=\frac{\hat{\gamma}_i}{||w||}
$$
可以证明，对于任意一个样本点$x_i$，其几何间隔$\gamma_i$都是该点到超平面的最短距离。
因此，我们可以将最大化几何间隔转化为以下优化问题：
$$
\max_{w,b}\quad \frac{2}{||w||}\\
s.t.\quad y_i(x_i^Tw+b)\geq\gamma,\quad i=1,2,...,N
$$
其中$\gamma$是任意正数。
由于最大化$\frac{2}{||w||}$等价于最小化$||w||^2$，因此上述问题可以进一步转化为以下二次规划问题：
$$
\min_{w,b}\quad \frac{1}{2}||w||^2\\
s.t.\quad y_i(x_i^Tw+b)-1\geq0,\quad i=1,2,...,N
$$
1.3 求解线性可分支持向量机
对于上述二次规划问题，可以使用拉格朗日乘子法来求解。
引入拉格朗日乘子$\alpha_i\geq0$，则原问题的拉格朗日函数为：
$$
L(w,b,\alpha)=\frac{1}{2}||w||^2-
\sum_{i=1}^{N}\alpha_i[y_i(x_i^Tw+b)-1]
$$
对$w$和$b$求偏导数，令其等于0，得到：
$$
w=\sum_{i=1}^{N}\alpha_iy_ix_i\\
\sum_{i=1}^{N}\alpha_iy_i=0
$$
将上述结果代入原问题中，则可以得到对偶问题：
$$
\max_{\alpha}\quad \sum_{i=1}^{N}\alpha_i-
\frac{1}{2}\sum_{i,j=1}^{N}\alpha_i\alpha_jy_iy_jx_i^Tx_j\\
s.t.\quad \alpha_i\geq0,\quad i=1,2,...,N\\
\sum_{i=1}^{N}\alpha_iy_i=0
$$
其中，$\alpha$是拉格朗日乘子向量。
通过求解对偶问题，我们可以得到最优的超平面参数$w^*$和$b^*$。
二、非线性支持向量机
2.1 核函数
在实际应用中，很多情况下样本点不是线性可分的。
为了处理这种情况，我们可以将输入空间映射到一个更高维的特征空间，使得样本在该空间中线性可分。
设$\phi(x)$为从原始输入空间到特征空间的映射函数，则我们可以将原问题转化为：
$$
\max_{\alpha}\quad \sum_{i=1}^{N}\alpha_i-
\frac{1}{2}\sum_{i,j=1}^{N}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x _j)\\
s.t.\quad \alpha_i\geq0,\quad i=1,2,...,N\\
\sum_{i=1}^{N}\alpha_iy_i=0
$$
由于计算$\phi(x)$的复杂度较高，因此我们可以使用核函数来避免直接计算。
核函数$K(x,z)=\phi(x)^T\phi(z)$满足Mercer条件时，可以表示为：
$$
K(x,z)=\sum_{i=1}^{N}\alpha_iy_ix_i^Tx_j+\theta_0
$$
其中$\theta_0$是常数项。
2.2 常用核函数
常见的核函数有：
（1）线性核函数
$$
K(x,z)=x^Tz
$$
（2）多项式核函数
$$
K(x,z)=(x^Tz+1)^p
$$
（3）高斯径向基核函数
$$
K(x,z)=\exp(-\frac{||x-z||^2}{2\sigma^2})
$$
（4）Sigmoid核函数
$$
K(x,z)=\tanh(\beta x^Tz+\theta)
$$
其中，$p$、$\sigma$、$\beta$、$\theta$均为超参数，需要通过交叉验证等方法进行调参。
三、支持向量机的推广
3.1 多分类问题
对于多分类问题，我们可以使用一对多的方法进行处理。
具体来说，
我们将每个类别作为正例，其余类别作为负例，训练$n$个二分类器。
在预测时，对于一个新样本点$x$，将其输入到每个二分类器中进行预测，并选择置信度最高的分类结果。
3.2 不平衡分类问题
在实际应用中，很多情况下不同类别的样本数量存在较大差异。
此时，我们可以采用一些策略来解决不平衡分类问题：
（1）调整损失函数权重：对于少数类样本增加损失函数权重。
（2）欠采样：随机删除多数类样本。
（3）过采样：随机复制少数类样本或生成新的少数类样本。
（4）阈值移动：调整决策阈值使得准确率和召回率达到平衡。
3.3 支持向量回归问题
支持向量回归（Support Vector Regression，SVR）是一种基于
SVM的回归方法。
与分类问题不同，SVR的目标是找到一个超平面使得训练样本点与该超平面之间的距离最小。
具体来说，对于给定的训练数据集
$D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中$x_i\in R^n$为输入
样本，$y_i\in R$为输出标记。
SVR的目标是最小化以下损失函数：
$$
\min_{w,b,\xi,\xi^*}\quad
\frac{1}{2}||w||^2+C\sum_{i=1}^{N}(\xi_i+\xi_i^*)\\
s.t.\quad y_i-w^Tx_i-b\leq \epsilon+\xi_i\\
w^Tx_i+b-y_i\leq \epsilon+\xi_i^*\\
\xi_i,\xi_i^*\geq0,\quad i=1,2,...,N
$$
其中$\epsilon$为预测误差上限，$C$为惩罚参数。
求解上述问题时，需要使用对偶问题和核函数。
四、总结
支持向量机是一种强大的分类器和回归器，在处理高维数据和小样本
问题时表现出色。
通过使用核函数可以将其扩展到非线性情况。
在实
际应用中，我们需要根据具体问题选择合适的核函数和调整超参数。
同时，对于不平衡分类问题和支持向量回归问题，我们也可以使用支持向量机进行处理。
