硬间隔SVM的拉格朗日求解与对偶问题详解

硬间隔支持向量机(SVM)是机器学习中的一个重要概念，它在解决二分类问题时，通过在特征空间中寻找一个能够最大化训练样本间正负类别的间隔的最优超平面。SVM分为硬间隔和支持向量机、非线性SVM等类别，其中硬间隔SVM假设数据是完全线性可分的。 硬间隔SVM的具体实现中，给定训练样本集D，每个样本(x_i, y_i)，其中y_i属于{-1, 1}，目标是找到一个超平面w·x + b = 0，使得所有正样本到此超平面的距离（几何间隔）都大于或等于1。这里的w是法向量决定方向，b是偏移量决定距离。计算样本x到超平面的距离公式为：d = |w·x + b| / ||w||。 目标函数可以表示为最小化范数的平方加上错误惩罚项，即：minimize ||w||^2 + C * Σ |y_i*(w·x_i + b)|，其中C是正则化参数，用于平衡间隔大小和模型复杂度。硬间隔SVM的目标是使所有样本点到超平面的距离至少为1，这被称为间隔最大化。 为了求解这个优化问题，引入拉格朗日乘子法，构造拉格朗日函数L(w, b, α)，其中α是拉格朗日乘子。对偶问题的目标是最大化拉格朗日函数关于α的下界，即maximize LDual(α)，其形式为：maximize Σ α_i - 1/2 * Σ Σ α_i*α_j*y_i*y_j*(w·x_i)(w·x_j) + b*Σ α_i*y_i，其中α_i ≥ 0且对所有i，α_i*y_i <= 1。 KKT条件是求解对偶问题的重要工具，它们确保了原始问题和对偶问题的等价性。KKT条件包括stationarity（梯度等于零）、complementary slackness（拉格朗日乘子与不等式约束的关系）和feasibility（变量满足约束条件）。 SMO (Sequential Minimal Optimization) 是一种常用的算法，用于解决大规模数据集下的硬间隔SVM对偶问题。SMO通过局部搜索更新两个拉格朗日乘子α_i 和 α_j，使其满足KKT条件，然后迭代地更新w和b。当所有样本点满足间隔最大化条件时，或者达到预设的迭代次数，算法停止。 硬间隔SVM是一种强大的二分类工具，其核心在于寻找最大间隔超平面，通过拉格朗日函数和对偶问题的形式化处理，结合KKT条件和SMO算法，可以高效地解决线性可分数据的学习任务。理解并掌握这些原理对于实际应用和进一步研究SVM方法至关重要。