线性可分支持向量机与硬间隔最大化
线性可分支持向量机
给定线性可分训练数据集， 通过间隔最大化或等价地求解相应地凸二次规划问题学习得到的分类超平面为：
\[w^* · x + b^* = 0 \tag{7.1}\]以及相应的分类决策函数
\[f(x) = sign(w^* · x + b^*) \tag{7.2}\]称为线性可分支持向量机
函数间隔和几何间隔
函数间隔 (functional margin)
在超平面 $w · x + b = 0$确定的情况下， $\mid w · x + b \mid$ 能够相对地表示点 $x$ 距离超平面的远近。 而 $w · x + b$ 的符号与类标记 $y$ 的符号是否一致能够表示分类是否正确。 所以可以用量 $y(w · x + b)$ 表示分类的正确性及确信度， 这就是 函数间隔 (functional margin) 的概念。
对于给定的训练数据集 $T$ 和 超平面 $(w, b)$， 定义超平面 $(w, b)$ 关于样本点 $(x_i, y_i)$ 的函数间隔：
\[\hat \gamma_i = y_i (w · x_i + b) \tag{7.3}\]定义超平面 $(w, b)$ 关于训练数据集 $T$ 的函数间隔 为 超平面 $(w, b)$ 关于 $T$ 中所有样本点 $(x_i, y_i)$ 的函数间隔之最小值， 即：
\[\hat \gamma = \min_{i=1, ..., N} \hat \gamma_i \tag{7.4}\]几何间隔 (geometric margin)
函数间隔可以表示分类预测的正确性及确信度。 但是选择分离超平面时， 只有函数间隔还不够。 因为只要成比例地改变 $w$ 和 $b$， 例如将它们改为 $2w$ 和 $2b$， 超平面并没有改变， 但函数间隔却成为原来的2倍。
这一事实启示我们， 可以对分类超平面的法向量 $w$ 加某些约束， 如规范化， $|w| = 1$, 使得间隔是确定的。 这时函数间隔成为几何间隔(geometric margin)。
对于给定的训练数据集 $T$ 和 超平面 $(w, b)$， 定义超平面 $(w, b)$ 关于样本点 $(x_i, y_i)$的几何间隔为：
\[\gamma_i = y_i (\frac{w}{\|w\|} · x_i + \frac{b}{\|w\|}) \tag{7.5}\]定义超平面 $(w, b)$ 关于训练数据集 $T$ 的几何间隔 为 超平面 $(w, b)$ 关于 $T$ 中所有样本点 $(x_i, y_i)$ 的几何间隔之最小值， 即：
\[\gamma = \min_{i=1, ..., N} \gamma_i \tag{7.6}\]超平面$(w, b)$关于样本点$(x_i, y_i)$的几何间隔一般是实例点到超平面的带符号的距离(signed distance)， 当样本点被超平面正确分类时就是实例点到超平面的距离。
从函数间隔和几何间隔的定义 (式 (7.3) ~ 式 (7.6)) 可知， 函数间隔和几何间隔有下面的关系：
\[\gamma_i = \frac{\hat \gamma_i}{\|w\|} \tag{7.7}\] \[\gamma = \frac{\hat \gamma}{\|w\|} \tag{7.8}\]如果 $|w| = 1$， 那么函数间隔和几何间隔相等。 如果超平面参数 $w$ 和 $b$ 成比例地改变 (超平面没有改变)，函数间隔也按此比例改变， 而几何间隔不变。
