FML Chapter 5 | FlowerMouse Blog

type

status

date

slug

summary

Separable

Explanation from QWQ

🤖

在支持向量机（SVM）的优化问题中，从原始形式转换到简化形式的过程涉及到一些关键的数学推导和几何理解。让我们详细解释一下这个转换过程。

原始优化问题

原始的优化问题是找到一个分离超平面，使得其几何间隔最大化。根据几何间隔的定义，我们有：

这里, 是样本点的标签（+1 或 -1），和分别是超平面的法向量和偏置项。

转换过程

第一步：非负性约束

由于样本是线性可分的，对于最优的，必须对所有都是非负的。因此，我们可以将绝对值去掉，直接使用。

第二步：尺度不变性

注意到表达式对于的正数倍缩放是不变的。也就是说，如果我们同时将和缩放相同的正数倍，该表达式的值不会改变。因此，我们可以限制的尺度，使得。

第三步：简化目标函数

在上述尺度限制下，我们可以将优化问题简化为：

进一步简化为：

这是因为对于最优解，最小的应该等于 1。

总结

通过上述步骤，我们将原始的优化问题转换成了一个更简单的形式，即最大化，同时满足所有样本点都位于正确的一侧，并且距离超平面的最小距离为 1。这种转换不仅简化了优化问题，还使得求解过程更加直观和高效。

相比于直接求解原优化问题，求解对偶优化问题的优势何在？

🤖

求解支持向量机（SVM）的对偶问题相比于直接求解原问题，具有以下优势：

1. 核技巧的引入

对偶问题的形式通过内积（如）表示样本之间的关系，这使得可以隐式引入核函数 。通过核技巧，SVM能够高效地处理非线性可分数据，将输入空间映射到高维特征空间而无需显式计算映射函数。而原问题直接依赖于特征向量，难以直接应用核方法。

2. 优化变量规模的灵活性

原问题的变量是权重向量和偏置，其维度等于特征数量 。当特征维度极高（例如文本分类中的词袋模型）时，直接求解原问题计算复杂度较高。

对偶问题的变量是拉格朗日乘子，其数量等于样本数量 。当样本数（例如小样本高维数据）时，对偶问题更高效。此外，实际场景中许多会稀疏化为零，只有支持向量对应的非零，进一步降低了计算量。

3. 支持向量的显式利用

对偶问题的解直接关联到支持向量（即的样本），这些样本决定了分类边界。这种稀疏性使得模型预测时仅需计算支持向量的核函数，预测效率更高。

4. 优化算法的适配性

对偶问题更适配高效的优化算法，例如序列最小优化（SMO）。SMO通过分解问题为子问题迭代求解，适合处理对偶形式中的拉格朗日乘子。而原问题通常需要通用凸优化工具，计算复杂度较高。

5. 对偶间隙与理论保证

SVM原问题和对偶问题在强对偶性下具有相同的解，且对偶问题本身是凸优化问题，保证了全局最优解的存在性。

何时选择原问题？

当特征维度 远小于样本数 （例如低维稠密数据）时，直接求解原问题可能更高效，因为此时原问题的变量规模比对偶问题更小。

总结

对偶问题的核心优势在于核化能力、变量规模适配性和稀疏性，使其成为处理高维、非线性问题的首选形式。而原问题在低维稠密数据中可能更直接有效。实际选择时需结合数据特征和应用场景。

SVM的奇妙性质：

convex optimizatin problem （quadratic programming）

SVM的两个marginal hyperplanes 为

SVM的权重向量 w 是 support vectors 的线性组合

support vectors 一定属于在 marginal hyperplanes 上的向量，因此不在 marginal hyperplanes 上的向量不影响最终结果

解 h 是唯一的，但是支撑向量 support vectors 不一定是唯一的

The hypothesis solution depends only on inner products between vectors and not directly on the vectors themselves.

margin可以表示为的范数形式。

the average error of the algorithm is upper bounded by the average fraction of support vectors.

Non-separable

Intuition

对于不可分的情况，我们不能得到对于所有的都有

因此引入松弛变量 slack variables :

对于的被称为 outlier。

那么我们就有两个目标，一是最大化 margin, 二是使得尽可能小，所以优化的目标函数如下，第一项是为了最小化 margin，第二项是使 outlier 偏离的程度尽可能小，而是一个超参数，一般根据 n-fold cross-validation 来确定。

Primal Optimization Problem

surrogate loss:

当 p = 1 时对应的损失函数是 hinge loss:

当 p = 2 时对应的损失函数是 quadratic hinge loss:

💡

这是引入松弛变量的写法，还有一种写法是不引入松弛变量 (p=1) ：

Lagrangian

KKT Conditions

Dual Optimization Problem

convex problem，全局最优性

support vector 要么在 marginal hyperplane 上，要么就是 outlier，并且

和separable的情况一样，的解是唯一的，但是 support vectors 的组合不是唯一的。

Margin Theory

Margin loss function

Empirical margin loss

Given a sample and a hypothesis , the empirical margin loss is defined by

由于

那么根据之前通过leave-one-out error 分析处理的算法的上界的解释可以推广为

the fraction of the points in the training sample S that have been misclassified or classified with confidence less than .

Lipschitz函数

Lipschitz(利普席茨)函数是一类具有有界变化率的函数。一个函数被称为Lipschitz函数，如果存在一个非负常数，使得对于所有的和，都满足以下不等式：

其中，被称为 Lipschitz 常数。该定义表示函数在任意两个点之间的变化量受到了一个有界的限制，即函数的变化率不会无限增长或减小。

换句话说，对于Lipschitz函数，存在一个常数，使得在定义域内的任意两个点之间，函数值的变化量不会超过两点之间自变量的变化量与的乘积。

Lemma

这里我理解的求期望的过程是类似于多维随机变量求期望的公式：

当与独立时，可以简化为：

由于随机变量相互之间是独立的，因此可以先对求期望，然后再对求，依次下去。

Margin bound

a larger value of ρ decreases the complexity term (second term), but tends to increase the empirical margin-loss ̂RS,ρ(h) (first term) by requiring from a hypothesis h a higher confidence margin.