百面算法工程师 | 支持向量机——SVM

时间：2024-05-03 11:37:43

文章目录

        • 15.1 SVM
        • 15.2 SVM原理
        • 15.3 SVM解决问题的类型
        • 15.4 核函数的作用以及特点
        • 15.5 核函数的表达式
        • 15.6 SVM为什么引入对偶问题
        • 15.7 SVM使用SGD及步骤
        • 15.8 为什么SVM对缺失数据敏感
        • 15.9 SVM怎么防止过拟合

欢迎大家订阅我的专栏一起学习共同进步

祝大家早日拿到offer！ let’s go

????????????http://t.****img.cn/dfcH3????????????

15.1 SVM

支持向量机（Support Vector Machine，SVM）是一种机器学习算法，广泛应用于分类和回归分析中。其基本原理是找到一个最优的超平面，将不同类别的数据分开，同时最大化分类边界的间隔。SVM的核心思想是通过将低维空间的数据映射到高维空间，从而使得数据线性可分。在高维空间中，SVM寻找一个能够最大化间隔的超平面，这个超平面被称为最优超平面。

SVM在分类问题中的工作原理是将输入数据映射到一个高维特征空间中，并找到一个能够将不同类别的数据分开的超平面。为了找到这个最优超平面，SVM通过最大化间隔（样本到超平面的距离）来确保分类的鲁棒性和泛化能力。在实际应用中，由于数据通常不是线性可分的，因此SVM引入了核函数来将数据映射到高维空间，从而使得数据在高维空间中线性可分。

SVM的优点包括：

  1. 在高维空间中处理非线性问题：通过使用核函数，SVM可以将数据映射到高维空间，从而处理非线性问题。
  2. 泛化能力强：由于SVM最大化间隔，因此具有很好的泛化能力，对于新数据的分类效果较好。
  3. 可解释性强：最优超平面是由支持向量决定的，这些支持向量是最靠近超平面的数据点，因此SVM具有较强的可解释性。

然而，SVM也存在一些缺点，包括：

  1. 对参数调节和核函数的选择较为敏感。
  2. 训练时间较长，特别是在大规模数据集上。
  3. 在处理噪声较多的数据集时，可能会出现过拟合的问题。
  4. 用SVM解决多分类问题存在困难

总的来说，SVM是一种强大的机器学习算法，在许多分类和回归问题中都有良好的表现。

15.2 SVM原理

以下是支持向量机（SVM）的推导过程

支持向量机（SVM）推导

  1. 基本概念

假设我们有一个数据集 ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) {(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)} (x1​,y1​),(x2​,y2​),...,(xn​,yn​)，其中 x i x_i xi​ 是输入特征， y i y_i yi​ 是对应的类别标签。对于二分类问题， y i y_i yi​ 可以是 − 1 -1 −1 或 + 1 +1 +1。

  1. SVM的目标

SVM的目标是找到一个超平面，可以最大化类别之间的间隔，并且使得所有的数据点都被正确分类。超平面可以表示为 w ⋅ x + b = 0 w \cdot x + b = 0 w⋅x+b=0，其中 w w w 是法向量， b b b 是偏置项。

  1. 最大间隔分类器

我们定义超平面到最近的数据点的距离为间隔（margin）。最大间隔分类器的目标是最大化这个间隔。这可以形式化为以下优化问题：

maximize 2 ∥ w ∥ subject to y i ( w ⋅ x i + b ) ≥ 1 , for all  i \text{maximize} \quad \frac{2}{\lVert w \rVert} \\ \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1, \quad \text{for all } i maximize∥w∥2​subject toyi​(w⋅xi​+b)≥1,for all i

这是一个凸二次优化问题。

  1. 对偶问题

通过拉格朗日乘子法，我们可以将原始问题转化为对偶问题。我们引入拉格朗日乘子 α i ≥ 0 \alpha_i \geq 0 αi​≥0，并定义拉格朗日函数：

L ( w , b , α ) = 1 2 ∥ w ∥ 2 − ∑ i = 1 n α i [ y i ( w ⋅ x i + b ) − 1 ] L(w, b, \alpha) = \frac{1}{2}\lVert w \rVert^2 - \sum_{i=1}^{n} \alpha_i [y_i(w \cdot x_i + b) - 1] L(w,b,α)=21​∥w∥2−i=1∑n​αi​[yi​(w⋅xi​+b)−1]

然后对 w w w 和 b b b 求偏导并令其等于零，得到：

w = ∑ i = 1 n α i y i x i ∑ i = 1 n α i y i = 0 w = \sum_{i=1}^{n} \alpha_i y_i x_i \\ \sum_{i=1}^{n} \alpha_i y_i = 0 w=i=1∑n​αi​yi​xi​i=1∑n​αi​yi​=0

将这些结果代入拉格朗日函数，我们得到对偶问题：

maximize W ( α ) = ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i ⋅ x j subject to α i ≥ 0 , ∑ i = 1 n α i y i = 0 \text{maximize} \quad W(\alpha) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{n} \alpha_i \alpha_j y_i y_j x_i \cdot x_j \\ \text{subject to} \quad \alpha_i \geq 0, \quad \sum_{i=1}^{n} \alpha_i y_i = 0 maximizeW(α)=i=1∑n​αi​−21​i,j=1∑n​αi​αj​yi​yj​xi​⋅xj​subject toαi​≥0,i=1∑n​αi​yi​=0

这是一个凸二次优化问题，其解决方案给出了最优的超平面。

  1. 从对偶问题中得到分离超平面

通过解决对偶问题，我们得到了一组拉格朗日乘子 α i ∗ \alpha_i^* αi∗​。然后，我们可以使用它们来计算权重向量 w w w：

w = ∑ i = 1 n α i ∗ y i x i w = \sum_{i=1}^{n} \alpha_i^* y_i x_i w=i=1∑n​αi∗​yi​xi​

并且选择任意一个支持向量 x i x_i xi​ 来计算偏置项 b b b：

b = y i − w ⋅ x i b = y_i - w \cdot x_i b=yi​−w⋅xi​

  1. 非线性SVM

对于非线性问题，我们可以使用核函数将输入空间映射到更高维的特征空间。这样，我们就可以在特征空间中找到一个线性超平面来分隔数据。

支持向量机是一种强大的分类器，通过最大化间隔来优化超平面位置，从而提高了分类的鲁棒性。通过解决对偶问题，我们可以得到优雅的解决方案，并且通过核函数，SVM可以处理非线性问题。

15.3 SVM解决问题的类型

支持向量机（SVM）是一种非常强大的监督学习算法，它在许多问题领域都有广泛的应用。以下是SVM能够解决的一些主要问题：

  1. 二分类问题：SVM最初是用于二分类问题的，它可以有效地将数据划分为两个类别，并找到最优的超平面以实现最大间隔分类。

  2. 多分类问题：虽然SVM最初是为二分类设计的，但可以使用一些技巧来扩展它以解决多分类问题，例如一对一（One-vs-One）或一对其他（One-vs-Rest）策略。

  3. 线性可分问题：当数据可以通过一个超平面完全分割成两个类别时，SVM表现最好。

  4. 线性不可分问题：通过使用核函数，SVM可以处理线性不可分的情况，将数据映射到更高维的特征空间中，使其变得线性可分。

  5. 回归问题：SVM也可以用于解决回归问题。通过引入一个适当的损失函数和辅助

相关文章