SVM and SMO

### 支持向量机（SVM）与序列最小优化（SMO） #### 支持向量机（SVM）简介 支持向量机（Support Vector Machine, SVM）是一种广泛应用于分类与回归任务的监督学习模型。其核心思想是通过在特征空间中找到一个最优超平面来实现对数据的最大化间隔划分。SVM可以处理线性可分、线性不可分以及非线性可分的数据集，并且具有良好的泛化能力。 #### 1.1 线性SVM 线性SVM是最简单形式的支持向量机。它假设训练数据集为\( \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\} \)，其中每个样本\( x_i \)位于\( d \)-维空间内，而对应的标签\( y_i \)属于集合\( \{+1, -1\} \)。线性SVM的目标是找到一个能够正确分类所有训练样本的超平面，并且使得这个超平面到最近的训练样本的距离（即“间隔”）最大化。这个超平面可以通过以下函数表示： \[ f(x) = \text{sgn}(w \cdot x - b) \] 其中\( w \)是权重向量，\( b \)是偏置项，而\( \text{sgn} \)是符号函数。 #### 1.2 对偶问题 为了求解SVM中的最优化问题，通常采用拉格朗日乘子法将其转换为对偶问题。这样做的好处是可以利用核技巧处理非线性可分的数据。对偶问题的形式为： \[ \max_{\alpha} W(\alpha) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} y_i y_j \alpha_i \alpha_j \langle x_i, x_j \rangle \] \[ \text{s.t. } 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^{N} \alpha_i y_i = 0 \] 其中\( \alpha_i \)是拉格朗日乘子，\( C \)是正则化参数，而\( \langle x_i, x_j \rangle \)表示内积运算。 #### 1.3 非线性SVM 当数据不是线性可分时，可以通过引入核函数（Kernel Function）的方法将原始特征空间映射到高维空间中，使得数据在新空间中变得线性可分。常见的核函数有多项式核、径向基核（Radial Basis Function, RBF）等。 #### 1.4 不完美分割 在实际应用中，数据往往无法完全被线性分割。为了解决这个问题，SVM允许某些样本点被误分类，并通过引入松弛变量（Slack Variables）来控制这种不完美的分割。这会导致对偶问题的形式发生改变，从而影响最终的决策边界。 #### 1.5 KKT条件 Karush-Kuhn-Tucker（KKT）条件是一组必要条件，用于确定非线性规划问题的最优解。对于SVM而言，KKT条件可以帮助我们检查当前的解是否满足最优化问题的要求。这些条件包括： 1. **互补松弛性**：\( \alpha_i [y_i (w^T x_i - b) - 1] = 0 \) 2. **拉格朗日乘子非负**：\( \alpha_i \geq 0 \) 3. **原问题约束**：\( y_i (w^T x_i - b) \geq 1 \) #### 1.6 不使用阈值b检查KKT条件 在实践中，有时需要在不知道偏置项\( b \)的情况下检查KKT条件。此时可以通过观察支持向量（即那些恰好位于分类边界上的样本点）来近似计算\( b \)。 #### 2. SMO算法 序列最小优化（Sequential Minimal Optimization, SMO）是一种专门用于解决SVM中大规模数据集优化问题的有效算法。SMO算法的基本思路是在每次迭代过程中选择两个拉格朗日乘子进行优化。 #### 2.1 优化两个\( \alpha_i \)的步骤 在每次迭代中，SMO算法选择两个拉格朗日乘子\( \alpha_i \)和\( \alpha_j \)进行优化。优化过程包括： 1. **计算当前的\( \alpha_i \)和\( \alpha_j \)** 2. **更新\( \alpha_i \)和\( \alpha_j \)的边界条件** 3. **计算新的\( \alpha_i \)和\( \alpha_j \)的值** #### 2.2 SMO算法：成功优化后的更新步骤 一旦两个拉格朗日乘子\( \alpha_i \)和\( \alpha_j \)被成功优化，就需要更新相关的变量，包括： 1. **更新阈值\( b \)** 2. **更新缓存中的拉格朗日乘子值** 3. **更新误差缓存** #### 2.3 SMO算法：选择两个\( \alpha_i \)进行优化 在SMO算法中，选择哪两个拉格朗日乘子进行优化是一个关键步骤。常见的策略包括： 1. **随机选择** 2. **基于启发式的规则选择** #### 3. C++实现 该文档还包括了SVM的C++实现细节，具体包括以下几个方面： #### 3.1 主程序流程 主程序主要负责读取数据、初始化模型参数、调用优化算法并输出结果。 #### 3.2 考察示例例程 这部分内容描述了如何通过考察特定样本点的状态来决定是否需要对其进行优化。 #### 3.3 采取步骤例程 这部分内容详细介绍了如何更新两个选定的拉格朗日乘子，并确保它们满足KKT条件。 #### 3.4 评估分类函数 为了评估模型性能，需要定义一个分类函数，该函数能够根据训练好的模型对新样本进行分类。 #### 3.5 计算内积函数 内积函数是SVM中的核心组件之一，尤其是在使用核函数的情况下。这部分内容介绍了几种常用的内积计算方法。 #### 3.6 核函数 核函数用于将低维数据映射到高维空间，以便在高维空间中实现线性分割。这部分内容列举了几种常用的核函数。 #### 3.7 输入与输出 这部分内容介绍了如何从命令行获取参数、读取数据以及保存和加载模型参数。 #### 3.8 计算错误率 计算模型的错误率是评估模型性能的关键步骤之一。 #### 3.9 多分类 对于多分类问题，SVM通常采用一对多（One-vs-One或One-vs-All）的策略来扩展二分类模型。 #### 3.10 Makefile 这部分内容提供了编译C++代码所需的Makefile文件示例。 #### 附录 A 权重向量平行支持面 附录部分提供了关于SVM决策边界的相关数学推导。 #### 附录 B 对偶问题的目标函数 附录还详细介绍了SVM对偶问题的目标函数及其求解方法。 通过以上内容，我们可以清晰地了解到SVM与SMO算法的基本原理及其实现细节。这些理论和实践知识对于理解和应用SVM模型至关重要。