Pegasos：大规模数据上的SVM优化算法

"Pegasos是Primal Estimated sub-GrAdient SOlver for SVM，是一种针对支持向量机（SVM）的优化算法，尤其适用于大规模数据集。它通过随机子梯度下降法来求解SVM的优化问题，降低了对训练集大小的依赖，提升了算法在处理大型数据集时的效率。" 支持向量机（SVM）是机器学习领域中一种广泛使用的分类模型，其优化问题通常表现为一个带有正则化项的约束二次规划问题。传统SVM求解器如SMO（Sequential Minimal Optimization）需要处理整个训练集，这在数据量巨大时会变得非常耗时。Pegasos算法引入了随机子梯度下降策略，每次迭代仅基于一个随机选取的样本进行，显著减少了计算量。 Pegasos算法的基本步骤如下： 1. 初始化权重向量`w1`为零向量。 2. 在第`t`次迭代中，随机选择一个训练样本`xi`。 3. 使用该样本构建目标函数的近似，并计算子梯度`g_t`。 4. 通过步长`η`更新权重向量`w`，公式为`w_{t+1} = w_t - η * g_t`。 5. 可选地，可以进行投影操作，确保权重向量保持在允许的范数范围内（例如，不超过`1/λ`）。 Pegasos的一个变体是引入迷你批量（mini-batch）迭代，每次迭代使用`k`个样本，这在一定程度上平衡了计算效率和收敛速度。当`k=m`时，算法退化为处理完整的训练集，即批处理或确定性迭代。对于稀疏特征向量，Pegasos能够有效地利用实例的稀疏性，减少计算复杂性。 Pegasos算法以其高效性和对大规模数据集的适应性，成为了SVM优化的一个重要工具。它不仅在理论上提供了理论保证（如O(1/λ)的迭代次数），而且在实践中展现出良好的性能，特别是在文本分类等需要处理大量特征的场景下。通过调整参数如步长和迷你批量大小，Pegasos可以灵活地适应不同的问题和计算资源。