SVM介绍 推导 总结

### SVM介绍、推导与总结 #### （一）SVM基础 **1. 对偶问题** 在优化理论中，对偶问题是与原问题相对应的一个问题。原问题通常表示为： \[ \min f_0(x), x \in \mathbb{R}^n \\ \text{s.t. } f_i(x) \leq 0, i = 1, 2, \ldots, m \\ h_i(x) = a_i x - b_i = 0, i = 1, 2, \ldots, p \] 其中\(f_0(x)\)是要最小化的目标函数，\(f_i(x)\)和\(h_i(x)\)分别是不等式约束和等式约束。 假设该问题的最优解为\(p^*\)，即\(p^* = \inf\{f_0(x)\}\)。为了寻找\(p^*\)的下界，可以通过构建Lagrange函数实现： \[ L(x, \lambda, v) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} v_i h_i(x) \] 其中\(\lambda_i \geq 0\)。 由于原问题的约束条件为\(f_i(x) \leq 0\)和\(h_i(x) = 0\)，因此\(L(x, \lambda, v) \leq f_0(x)\)。由此，可以得出\(L\)的最优解与\(p^*\)之间的关系： \[ \inf\{L(x, \lambda, v)\} \leq \inf\{f_0(x)\} = p^* \] 为了找到最好的下界，即最大化\(\inf\{L(x, \lambda, v)\}\)，我们需要考虑以下的对偶问题： \[ \max \inf\{L(x, \lambda, v)\} \\ \text{s.t. } \lambda_i \geq 0 \] **2. 强对偶定理** 强对偶定理描述的是原问题的最优值\(p^*\)与其对偶问题的最优值\(d^*\)之间的关系。若\(p^* = d^*\)，则称这一情况为强对偶。在这种情况下，我们可以通过解决对偶问题来获得原问题的解。 **3. KKT 条件** KKT条件是用于判断非线性规划问题是否存在最优解的一组必要条件。如果\(x^*\)满足KKT条件，则存在\(\lambda^*, v^*\)，使得Lagrange函数 \[ L(x, \lambda, v) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} v_i h_i(x) \] 满足： 1. \(f_i(x^*) \leq 0\) 2. \(h_i(x^*) = 0\) 3. \(\lambda_i^* \geq 0\) 4. \(\sum_{i=1}^{m} \lambda_i^* f_i(x^*) = 0\) 5. \(\nabla_x L(x^*, \lambda^*, v^*) = \nabla_x f_0(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla_x f_i(x^*) + \sum_{i=1}^{p} v_i^* \nabla_x h_i(x^*) = 0\) 其中，前三个条件是原问题的约束条件，第四个条件称为互补松弛条件，第五个条件是关于\(x^*\)的偏导数为零，即\(x^*\)为\(L(x, \lambda, v)\)的极值点。根据强对偶定理，如果\(x^*\)满足KKT条件，则\(x^*\)是原问题的解。 #### （二）SVM总结 **1. 介绍与背景** SVM（Support Vector Machine，支持向量机）是一种广泛应用于分类和回归分析的监督学习模型。SVM的主要特点是能够在小样本集上表现良好，并且具有较强的泛化能力，不易发生过拟合现象。由于SVM在许多实际问题中取得了非常好的效果，它促进了统计学习理论的发展。 **（1）线性分类** 在机器学习中，线性分类器是指那些能够通过一个或多个线性函数（在一维、二维、三维等空间中表现为直线、平面或超平面）来划分不同类别数据的方法。对于线性分类器而言，其核心任务是确定一个最佳的分类界面，以便能够尽可能正确地区分不同类别的样本。SVM就是一种基于线性分类的算法，它通过寻找一个最优的超平面来实现分类目的。 **（2）SVM思想** 对于线性可分的数据集，SVM试图找到一个能够最大化类别之间间隔的决策边界。这种最大化间隔的思想有助于提高模型的泛化能力。SVM通过定义支持向量和支持边界来实现这一点，其中支持向量是最接近决策边界的样本点，而支持边界则是通过这些支持向量来定义的。支持向量和它们对应的支撑边界共同决定了最终的决策面。 **2. SVM数学表达** SVM的目标是找到一个分类间隔最大的决策面。给定一个决策面方程\(g(x) = w^T x + b\)，其中\(w\)是权重向量，\(b\)是偏置项。我们定义\(g(x) > 0\)表示一类，\(g(x) < 0\)表示另一类。为了量化分类间隔，我们可以考虑决策面两侧的支持向量。假设\(x_1\)和\(x_2\)是两个支持向量，那么它们满足\(w^T x_1 + b = 1\)和\(w^T x_2 + b = -1\)。由此，分类间隔\(r\)可以通过以下方式计算： \[ r = \frac{2}{||w||} \] 这里的分类间隔\(r\)定义为决策边界到支持向量的距离的两倍除以权重向量的模长。最大化\(r\)即是最大化分类间隔，从而得到一个最优的决策面。 通过对SVM的基本原理及其数学表达式的深入理解，我们可以更好地应用和支持向量机算法解决实际问题中的分类和回归任务。