C++实现支持向量机：从数学原理到高性能分类器实战

1次阅读

共计 1755 个字符，预计需要花费 5 分钟才能阅读完成。

支持向量机 (SVM) 是一种经典的监督学习算法，特别适合中小规模数据集的分类任务。与神经网络相比，SVM 在样本量较少时更容易获得良好泛化性能，且数学可解释性更强。但当数据量极大或需要端到端特征学习时，深度学习通常更具优势。

硬间隔 SVM 的优化目标可表示为：

\min_{w,b} \frac{1}{2}||w||^2 \quad \text{s.t.} \quad y_i(w^Tx_i + b) \geq 1

通过拉格朗日乘子法转化为对偶问题：

L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum \alpha_i[y_i(w^Tx_i + b)-1]

当数据线性不可分时，引入核函数 $K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$ 将样本映射到高维空间。常用 RBF 核：

K(x_i,x_j) = \exp(-\gamma ||x_i - x_j||^2)

// Google C++ 风格类定义
template <typename Kernel>
class SVM {
public:
  void train(const Eigen::MatrixXd& X, const Eigen::VectorXi& y);
  Eigen::VectorXi predict(const Eigen::MatrixXd& X);
private:
  Kernel kernel_;  // 核函数模板
  Eigen::VectorXd alpha_;  // 拉格朗日乘子
  double bias_ = 0;       // 决策超平面偏置
};

// 时间复杂度 O(n^2) per iteration
void SVM::updateAlpha(int i1, int i2) {
  // 1. 计算预测误差
  double E1 = predict(X.row(i1)) - y(i1);

  // 2. 计算边界约束
  double L = std::max(0, alpha_(i2)-alpha_(i1));
  double H = std::min(C, C + alpha_(i2)-alpha_(i1));

  // 3. 更新乘子
  double eta = kernel_(i1,i1) + kernel_(i2,i2) - 2*kernel_(i1,i2);
  alpha_(i2) += y(i2)*(E1-E2)/eta;
  alpha_(i2) = std::clamp(alpha_(i2), L, H);
}

#pragma omp parallel for
for (int i = 0; i < n_samples; ++i) {
  // 并行计算核矩阵
  K_(i,j) = std::exp(-gamma_ * (X.row(i)-X.row(j)).squaredNorm());
}

数据规模	原生实现(MB)	优化后(MB)
10,000	800	320
100,000	OOM	2500

// 使用 AVX 指令加速向量内积
__m256d sum = _mm256_setzero_pd();
for (int i = 0; i < n/4; ++i) {__m256d a = _mm256_load_pd(v1 + i*4);
  __m256d b = _mm256_load_pd(v2 + i*4);
  sum = _mm256_fmadd_pd(a, b, sum);
}