分类器的符号、它到边界的几何距离,以及拟合时使用的目标函数,彼此相关但不同。只有所有有限 Gram 矩阵均为对称半正定时,核函数(kernel)才可描述实特征空间的内积。
分数有尺度,距离没有
仿射分类器分数为 f ( x ) = w T x + b f(x)=w^Tx+b f ( x ) = w T x + b ,其中 w ≠ 0 w\ne0 w = 0 ,并按符号预测。对 c > 0 c>0 c > 0 ,把 ( w , b ) (w,b) ( w , b ) 换成 ( c w , c b ) (cw,cb) ( c w , c b ) 不改变边界和符号,却令每个分数乘 c c c 。有符号几何距离是 ( w T x + b ) / ∥ w ∥ (w^Tx+b)/\|w\| ( w T x + b ) /∥ w ∥ ;除以范数消去这个任意正尺度。标签 y ∈ { − 1 , 1 } y\in\{-1,1\} y ∈ { − 1 , 1 } 的有符号间隔(margin)为 y ( w T x + b ) / ∥ w ∥ y(w^Tx+b)/\|w\| y ( w T x + b ) /∥ w ∥ 。
对仿射分数 f ( x ) = w T x + b f(x)=w^Tx+b f ( x ) = w T x + b (w ≠ 0 w\ne0 w = 0 )与带标签的观察 ( x , y ) (x,y) ( x , y ) (y ∈ { − 1 , 1 } y\in\{-1,1\} y ∈ { − 1 , 1 } ),函数间隔(functional margin)为 y f ( x ) yf(x) y f ( x ) ,几何间隔(geometric margin)为 y f ( x ) / ∥ w ∥ yf(x)/\|w\| y f ( x ) /∥ w ∥ 。当且仅当函数间隔为正时,该观察被正确分类。
数据严格线性可分时,可重新缩放,使最小有符号分数为 1。硬间隔支持向量机(hard-margin SVM)在 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\ge1 y i ( w T x i + b ) ≥ 1 约束下最小化 1 2 ∥ w ∥ 2 \tfrac12\|w\|^2 2 1 ∥ w ∥ 2 。最接近观察点到边界距离为 1 / ∥ w ∥ 1/\|w\| 1/∥ w ∥ ,两个支撑平面距离为 2 / ∥ w ∥ 2/\|w\| 2/∥ w ∥ ;这些数值依赖所述归一化。若约束不可行,硬间隔问题没有可行解;优化方法不能令相同特征上的矛盾标签变成可分。
约束 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\ge1 y i ( w T x i + b ) ≥ 1 固定的是函数间隔,不是距离。位于间隔上的点到边界的距离是 1 / ∥ w ∥ 1/\|w\| 1/∥ w ∥ ,而它会随 w w w 改变。把 ( w , b ) (w,b) ( w , b ) 乘以 c > 0 c>0 c > 0 ,每个函数间隔都乘 c c c ,而每个几何间隔不变;所以单看函数间隔很大,并不能说明点离边界有多远。
例题:两个观察与证书
一维负类观察为 x = 0 x=0 x = 0 ,正类观察为 x = 4 x=4 x = 4 。约束是 − b ≥ 1 -b\ge1 − b ≥ 1 和 4 w + b ≥ 1 4w+b\ge1 4 w + b ≥ 1 ;相加得 4 w ≥ 2 4w\ge2 4 w ≥ 2 ,故每个可行解均有 w ≥ 1 / 2 w\ge1/2 w ≥ 1/2 。可行选择 w = 1 / 2 w=1/2 w = 1/2 、b = − 1 b=-1 b = − 1 达到下界,并最小化 1 2 w 2 = 1 / 8 \tfrac12w^2=1/8 2 1 w 2 = 1/8 。边界是 x = 2 x=2 x = 2 ,每个观察点距边界 2,支撑平面之间距离为 4。
对偶(dual)证书以另一方式显示下界。取乘子 α − = α + = 1 / 8 \alpha_- = \alpha_+ =1/8 α − = α + = 1/8 ,均非负;∑ α i y i = 0 \sum\alpha_i y_i=0 ∑ α i y i = 0 ,且 ∑ α i y i x i = 4 / 8 = 1 / 2 = w \sum\alpha_i y_i x_i=4/8=1/2=w ∑ α i y i x i = 4/8 = 1/2 = w 。两个约束都取等,故满足互补松弛性(complementary slackness)。对偶目标为 1 / 4 − 1 2 ( 1 / 2 ) 2 = 1 / 8 1/4-\tfrac12(1/2)^2=1/8 1/4 − 2 1 ( 1/2 ) 2 = 1/8 ,等于可行原始(primal)目标,因此证明最优。这不需要声称每个问题的每个数据点都有正乘子。
合页损失改变了优化问题
对分数和标签,合页损失(hinge loss)为 max ( 0 , 1 − y f ( x ) ) \max(0,1-yf(x)) max ( 0 , 1 − y f ( x )) 。达到或超过所需函数间隔时为零,落在其内时为正;分错或分数为零时至少为 1。一种常见软间隔(soft-margin)目标是
1 2 ∥ w ∥ 2 + C ∑ i max ( 0 , 1 − y i ( w T x i + b ) ) , C > 0. \frac12\|w\|^2+C\sum_i\max(0,1-y_i(w^Tx_i+b)),\qquad C>0. 2 1 ∥ w ∥ 2 + C i ∑ max ( 0 , 1 − y i ( w T x i + b )) , C > 0.
这里把损失相加;改用平均值会改变 C C C 的数值意义,所以比较时须写明惯例。正则项偏好较小范数,损失项惩罚间隔违反。某候选值较低,只能证明另一候选在该 C C C 下非最优,本身不能证明前者全局最优。
概念视角 代数
把合页损失看成最优松弛量 引入松弛变量 ξ i ≥ 0 \xi_i\ge0 ξ i ≥ 0 ,满足 y i ( w T x i + b ) ≥ 1 − ξ i y_i(w^Tx_i+b)\ge1-\xi_i y i ( w T x i + b ) ≥ 1 − ξ i ,并最小化 1 2 ∥ w ∥ 2 + C ∑ i ξ i \tfrac12\|w\|^2+C\sum\limits_i\xi_i 2 1 ∥ w ∥ 2 + C i ∑ ξ i 。对固定的 ( w , b ) (w,b) ( w , b ) ,可取的最小 ξ i \xi_i ξ i 是 max ( 0 , 1 − y i ( w T x i + b ) ) \max(0,1-y_i(w^Tx_i+b)) max ( 0 , 1 − y i ( w T x i + b )) ,因为 ξ i \xi_i ξ i 必须同时不小于 0 0 0 与 1 − y i ( w T x i + b ) 1-y_i(w^Tx_i+b) 1 − y i ( w T x i + b ) 。对松弛量取最小,恰好回到上面的目标,所以带约束的松弛形式与无约束的合页形式描述同一个问题。在松弛形式中,ξ i \xi_i ξ i 是第 i i i 个观察违反间隔的量;在合页形式中,同一个数是分数上的损失。
例题:比较两个参数选择
沿用上述两个观察。硬间隔解 ( w , b ) = ( 1 / 2 , − 1 ) (w,b)=(1/2,-1) ( w , b ) = ( 1/2 , − 1 ) 的合页损失为零,目标为 1 / 8 1/8 1/8 。对 ( w , b ) = ( 1 / 4 , − 1 / 2 ) (w,b)=(1/4,-1/2) ( w , b ) = ( 1/4 , − 1/2 ) ,两个有符号分数均为 1 / 2 1/2 1/2 ,每个合页损失均为 1 / 2 1/2 1/2 ,目标是 1 2 ( 1 / 4 ) 2 + C ( 1 ) = 1 / 32 + C \tfrac12(1/4)^2+C(1)=1/32+C 2 1 ( 1/4 ) 2 + C ( 1 ) = 1/32 + C 。当且仅当 0 < C < 3 / 32 0<C<3/32 0 < C < 3/32 时它严格小于 1 / 8 1/8 1/8 ;C = 3 / 32 C=3/32 C = 3/32 时相等。比较表明在该严格范围内硬间隔参数不是此软间隔目标的最优解,但没有求出全局软间隔最小值。
若同一特征向量分别有 +1 和 -1 标签,共同分数 s s s 在硬间隔下须同时满足 s ≥ 1 s\ge1 s ≥ 1 及 s ≤ − 1 s\le-1 s ≤ − 1 ,不可能成立。两个合页损失之和 max ( 0 , 1 − s ) + max ( 0 , 1 + s ) ≥ 2 \max(0,1-s)+\max(0,1+s)\ge2 max ( 0 , 1 − s ) + max ( 0 , 1 + s ) ≥ 2 :∣ s ∣ ≤ 1 |s|\le1 ∣ s ∣ ≤ 1 时等于 2,其外更大。软间隔公式可为此矛盾赋有限损失;只使用该特征向量的确定性分类器不能同时正确标记两者。
核函数是有结构的相似度
若存在实内积空间 H H H 与映射 ϕ : X → H \phi:\mathcal X\to H ϕ : X → H ,使对所有 x , z x,z x , z 都有 K ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z ) ⟩ K(x,z)=\langle\phi(x),\phi(z)\rangle K ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z )⟩ ,则函数 K : X × X → R K:\mathcal X\times\mathcal X\to\mathbb R K : X × X → R 称为核函数。对点 x 1 , … , x n x_1,\dots,x_n x 1 , … , x n ,Gram 矩阵为 G = ( K ( x i , x j ) ) i , j G=(K(x_i,x_j))_{i,j} G = ( K ( x i , x j ) ) i , j 。
命题 11.1.5
(核函数的 Gram 矩阵半正定)
若 K K K 是核函数,则对任何有限选择 x 1 , … , x n x_1,\dots,x_n x 1 , … , x n ,Gram 矩阵 G G G 对称,且对每个 c ∈ R n c\in\mathbb R^n c ∈ R n 都有 c T G c ≥ 0 c^TGc\ge0 c T G c ≥ 0 。
对称性来自 ⟨ ϕ ( x ) , ϕ ( z ) ⟩ = ⟨ ϕ ( z ) , ϕ ( x ) ⟩ \langle\phi(x),\phi(z)\rangle=\langle\phi(z),\phi(x)\rangle ⟨ ϕ ( x ) , ϕ ( z )⟩ = ⟨ ϕ ( z ) , ϕ ( x )⟩ ,即 K ( x , z ) = K ( z , x ) K(x,z)=K(z,x) K ( x , z ) = K ( z , x ) 。对实系数 c i c_i c i ,
∑ i , j c i c j K ( x i , x j ) = ∥ ∑ i c i ϕ ( x i ) ∥ 2 ≥ 0. \sum_{i,j}c_i c_j K(x_i,x_j)=\left\|\sum_i c_i\phi(x_i)\right\|^2\ge0. i , j ∑ c i c j K ( x i , x j ) = i ∑ c i ϕ ( x i ) 2 ≥ 0.
因此核函数的每个有限 Gram 矩阵均为对称半正定(PSD)。要求涉及所有 有限输入选择,不只是某一抽样矩阵。找到一个具有负二次型的 Gram 矩阵足以否定候选核函数;只检查一个正矩阵却不能证明普遍性。接近零的特征值亦需小心数值近似。
例题:证明一个核函数、否定另一个
实数输入下设 K ( x , z ) = 1 + x z K(x,z)=1+xz K ( x , z ) = 1 + x z 。特征映射 ϕ ( x ) = ( 1 , x ) \phi(x)=(1,x) ϕ ( x ) = ( 1 , x ) 给出 K ( x , z ) = ϕ ( x ) T ϕ ( z ) K(x,z)=\phi(x)^T\phi(z) K ( x , z ) = ϕ ( x ) T ϕ ( z ) ;等价地,任意有限 Gram 二次型等于 ( ∑ i c i ) 2 + ( ∑ i c i x i ) 2 ≥ 0 (\sum\limits_i c_i)^2+(\sum\limits_i c_i x_i)^2\ge0 ( i ∑ c i ) 2 + ( i ∑ c i x i ) 2 ≥ 0 ,故每个有限样本均符合半正定条件。
相反考虑 L ( x , z ) = 1 − x z L(x,z)=1-xz L ( x , z ) = 1 − x z 。输入 0、2 的 Gram 矩阵为 ( 1 1 1 − 3 ) \begin{pmatrix}1&1\\1&-3\end{pmatrix} ( 1 1 1 − 3 ) 。取 c = ( 0 , 1 ) c=(0,1) c = ( 0 , 1 ) ,得 c T G c = − 3 < 0 c^T Gc=-3<0 c T G c = − 3 < 0 ,故非半正定;在包含这两个输入的定义域上,L L L 不可能是实内积核函数。负对角元素已构成反例:特征向量的平方范数不能为负。口头称为“相似度”并不足以支持核技巧(kernel trick)。
常见错误
(只用一个正的 Gram 矩阵来验证核函数)
单个半正定的 Gram 矩阵不能使函数成为核函数。对 L ( x , z ) = 1 − x z L(x,z)=1-xz L ( x , z ) = 1 − x z ,在 x = 0 x=0 x = 0 的单点 Gram 矩阵是 ( 1 ) (1) ( 1 ) ,是半正定;但上面在输入 0 0 0 与 2 2 2 的二点矩阵却不是。候选核函数必须对每个有限输入集都通过,或者被证明为特征向量的内积。
为何感知机更新界需要间隔
感知机更新与最小化 SVM 目标不是同一操作。为每个输入加入偏置坐标:x ~ = ( x , 1 ) \widetilde x=(x,1) x = ( x , 1 ) 、w ~ = ( w , b ) \widetilde w=(w,b) w = ( w , b ) 。从零开始,当 y w ~ T x ~ ≤ 0 y\widetilde w^T\widetilde x\le0 y w T x ≤ 0 时更新 w ~ ← w ~ + y x ~ \widetilde w\leftarrow\widetilde w+y\widetilde x w ← w + y x 。等号惯例很重要:它决定分数零的观察是否触发更新。
设有限训练集中每个 i i i 的增广输入 x ~ i = ( x i , 1 ) \widetilde x_i=(x_i,1) x i = ( x i , 1 ) 满足 ∥ x ~ i ∥ ≤ R \|\widetilde x_i\|\le R ∥ x i ∥ ≤ R ,且存在单位向量 u u u ,使每个 i i i 都有 y i u T x ~ i ≥ γ > 0 y_iu^T\widetilde x_i\ge\gamma>0 y i u T x i ≥ γ > 0 。从 w ~ = 0 \widetilde w=0 w = 0 开始,当 y w ~ T x ~ ≤ 0 y\widetilde w^T\widetilde x\le0 y w T x ≤ 0 时更新 w ~ ← w ~ + y x ~ \widetilde w\leftarrow\widetilde w+y\widetilde x w ← w + y x 。无论观察以何种次序出现,感知机的总更新次数至多为 ( R / γ ) 2 (R/\gamma)^2 ( R / γ ) 2 。
经 T T T 次更新,参数在 u u u 方向的投影至少为 T γ T\gamma T γ ,因为每次更新至少增加 γ \gamma γ 。一次更新时范数平方变为
∥ w ~ + y x ~ ∥ 2 = ∥ w ~ ∥ 2 + 2 y w ~ T x ~ + ∥ x ~ ∥ 2 ≤ ∥ w ~ ∥ 2 + R 2 . \|\widetilde w+y\widetilde x\|^2=\|\widetilde w\|^2+2y\widetilde w^T\widetilde x+\|\widetilde x\|^2\le\|\widetilde w\|^2+R^2. ∥ w + y x ∥ 2 = ∥ w ∥ 2 + 2 y w T x + ∥ x ∥ 2 ≤ ∥ w ∥ 2 + R 2 . 由更新条件,中间项非正。从零开始得 ∥ w ~ T ∥ 2 ≤ T R 2 \|\widetilde w_T\|^2\le TR^2 ∥ w T ∥ 2 ≤ T R 2 。由 Cauchy–Schwarz,T γ ≤ u T w ~ T ≤ ∥ w ~ T ∥ ≤ R T T\gamma\le u^T\widetilde w_T\le\|\widetilde w_T\|\le R\sqrt T T γ ≤ u T w T ≤ ∥ w T ∥ ≤ R T ,故 T > 0 T>0 T > 0 时 T ≤ ( R / γ ) 2 T\le(R/\gamma)^2 T ≤ ( R / γ ) 2 。论证需要分隔向量和半径假设,并非对矛盾或不可分数据的普遍保证;它限制一次运行的总更新数,不是每一轮所需更新数。
证明透视
线性进展对平方根增长 这个证明让两个量互相对抗。间隔假设使投影 u T w ~ u^T\widetilde w u T w 每次更新至少增加 γ \gamma γ ,所以它至少是线性的 T γ T\gamma T γ 。更新条件使交叉项 2 y w ~ T x ~ 2y\widetilde w^T\widetilde x 2 y w T x 非正,所以范数平方每次更新至多增加 R 2 R^2 R 2 ,即 ∥ w ~ T ∥ ≤ R T \|\widetilde w_T\|\le R\sqrt T ∥ w T ∥ ≤ R T 。Cauchy–Schwarz 在 u u u 为单位向量时把两者连起来:投影不能超过范数。线性的下界不可能长期低于平方根的上界,这就迫使 T ≤ ( R / γ ) 2 T\le(R/\gamma)^2 T ≤ ( R / γ ) 2 。
每个假设各有作用。取 u u u 为单位向量,才能把 γ \gamma γ 与 R R R 比较;把 u u u 重新缩放,只会缩放 γ \gamma γ ,数据本身不变。交叉项的符号正是用到“只在分错时更新”之处。u u u 的存在就是可分假设:没有它就不存在 γ \gamma γ ,论证无从收尾。
例题:上界与实际追踪
一维正类点为 x = 2 x=2 x = 2 ,负类点为 x = 0 x=0 x = 0 。增广分隔向量 ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) 对两个观察的有符号分数均为 1,范数为 2 \sqrt2 2 ,故其单位归一化的间隔是 γ = 1 / 2 \gamma=1/\sqrt2 γ = 1/ 2 。增广输入范数为 5 \sqrt5 5 和 1,取 R = 5 R=\sqrt5 R = 5 ;定理给出至多 ( 5 / ( 1 / 2 ) ) 2 = 10 (\sqrt5/(1/\sqrt2))^2=10 ( 5 / ( 1/ 2 ) ) 2 = 10 次更新。
反复按正类、负类次序处理。从 ( w , b ) = ( 0 , 0 ) (w,b)=(0,0) ( w , b ) = ( 0 , 0 ) 开始,正类分数为零,更新成 ( 2 , 1 ) (2,1) ( 2 , 1 ) ;负类分数为 1,故加上 − ( 0 , 1 ) -(0,1) − ( 0 , 1 ) 得 ( 2 , 0 ) (2,0) ( 2 , 0 ) 。下一轮正类分数为 4,不更新;负类分数为零,更新成 ( 2 , − 1 ) (2,-1) ( 2 , − 1 ) 。此时两个有符号分数都为正:正类为 3,负类为 1。本次共更新三次,远低于上界;若算法不在零分数更新,这条追踪便不同,因此惯例是题目的一部分。
可分假设不能省略。
反例模式
没有分隔向量时的错误次数上界 有人以为感知机在任何有限训练集上都会停止。取单个输入 x = 1 x=1 x = 1 ,增广为 x ~ = ( 1 , 1 ) \widetilde x=(1,1) x = ( 1 , 1 ) ,它出现两次,一次标签为 + 1 +1 + 1 ,一次为 − 1 -1 − 1 。此时不存在分隔向量。从 w ~ = 0 \widetilde w=0 w = 0 开始,先处理 + 1 +1 + 1 的副本:分数为 0 0 0 ,规则更新成 w ~ = ( 1 , 1 ) \widetilde w=(1,1) w = ( 1 , 1 ) 。− 1 -1 − 1 的副本有 y w ~ T x ~ = − 2 ≤ 0 y\widetilde w^T\widetilde x=-2\le0 y w T x = − 2 ≤ 0 ,故更新成 w ~ = ( 1 , 1 ) − ( 1 , 1 ) = 0 \widetilde w=(1,1)-(1,1)=0 w = ( 1 , 1 ) − ( 1 , 1 ) = 0 。一轮之后参数回到 0 0 0 ,同样的两次更新永远重复。上界 ( R / γ ) 2 (R/\gamma)^2 ( R / γ ) 2 不适用,因为不存在 γ > 0 \gamma>0 γ > 0 。补救办法是加上可分假设,或改用能容许矛盾标签的其他算法或损失,例如软间隔目标。
对偶证书从哪里来
证书要有用,必须清楚其不等式。对硬间隔约束取乘子 α i ≥ 0 \alpha_i\ge0 α i ≥ 0 ,构造
L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i α i ( 1 − y i ( w T x i + b ) ) . L(w,b,\alpha)=\frac12\|w\|^2+\sum_i\alpha_i\bigl(1-y_i(w^Tx_i+b)\bigr). L ( w , b , α ) = 2 1 ∥ w ∥ 2 + i ∑ α i ( 1 − y i ( w T x i + b ) ) .
在任意可行 ( w , b ) (w,b) ( w , b ) 下,每个括号均非正,故 L ( w , b , α ) ≤ 1 2 ∥ w ∥ 2 L(w,b,\alpha)\le\tfrac12\|w\|^2 L ( w , b , α ) ≤ 2 1 ∥ w ∥ 2 。对所有 w , b w,b w , b 取下确界,所得因而是每个可行原始目标的下界。b b b 的系数是 − ∑ i α i y i -\sum\limits_i\alpha_i y_i − i ∑ α i y i ;若该和不为零,对 b b b 取下确界便无下界。在零和约束下,对 w w w 最小化二次式得到 w = ∑ i α i y i x i w=\sum\limits_i\alpha_i y_i x_i w = i ∑ α i y i x i 及对偶值
g ( α ) = ∑ i α i − 1 2 ∥ ∑ i α i y i x i ∥ 2 . g(\alpha)=\sum_i\alpha_i-\frac12\left\|\sum_i\alpha_i y_i x_i\right\|^2. g ( α ) = i ∑ α i − 2 1 i ∑ α i y i x i 2 .
因此任何非负且符合零和条件的乘子都给出有效下界。若一个明确可行的原始点达到相同值,就没有可行点更好:仅用弱对偶已足以证明最优。例题一的两值均为 1 / 8 1/8 1/8 。互补松弛性说明最优时哪些约束可有正乘子,但在退化解中,位于间隔上的观察也可有零乘子。此公式的 ∥ w ∥ \|w\| ∥ w ∥ 不包括偏置 b b b ;若另一模型对偏置正则化,其对偶会不同。
设 α i ≥ 0 \alpha_i\ge0 α i ≥ 0 且 ∑ i α i y i = 0 \sum\limits_i\alpha_iy_i=0 i ∑ α i y i = 0 ,并令 g ( α ) = ∑ i α i − 1 2 ∥ ∑ i α i y i x i ∥ 2 g(\alpha)=\sum\limits_i\alpha_i-\tfrac12\bigl\|\sum\limits_i\alpha_iy_ix_i\bigr\|^2 g ( α ) = i ∑ α i − 2 1 i ∑ α i y i x i 2 。硬间隔问题的每个可行 ( w , b ) (w,b) ( w , b ) 都满足 1 2 ∥ w ∥ 2 ≥ g ( α ) \tfrac12\|w\|^2\ge g(\alpha) 2 1 ∥ w ∥ 2 ≥ g ( α ) 。若某个可行 ( w , b ) (w,b) ( w , b ) 使 1 2 ∥ w ∥ 2 = g ( α ) \tfrac12\|w\|^2=g(\alpha) 2 1 ∥ w ∥ 2 = g ( α ) ,则它是最优解。
记 v = ∑ i α i y i x i v=\sum\limits_i\alpha_iy_ix_i v = i ∑ α i y i x i 。对可行 ( w , b ) (w,b) ( w , b ) ,每个括号 1 − y i ( w T x i + b ) 1-y_i(w^Tx_i+b) 1 − y i ( w T x i + b ) 均非正,故 1 2 ∥ w ∥ 2 ≥ L ( w , b , α ) \tfrac12\|w\|^2\ge L(w,b,\alpha) 2 1 ∥ w ∥ 2 ≥ L ( w , b , α ) 。展开 L L L ,并用 ∑ i α i y i = 0 \sum\limits_i\alpha_iy_i=0 i ∑ α i y i = 0 消去 b b b ,
L ( w , b , α ) = 1 2 ∥ w ∥ 2 − w T v + ∑ i α i = 1 2 ∥ w − v ∥ 2 − 1 2 ∥ v ∥ 2 + ∑ i α i ≥ g ( α ) . L(w,b,\alpha)=\tfrac12\|w\|^2-w^Tv+\sum_i\alpha_i=\tfrac12\|w-v\|^2-\tfrac12\|v\|^2+\sum_i\alpha_i\ge g(\alpha). L ( w , b , α ) = 2 1 ∥ w ∥ 2 − w T v + i ∑ α i = 2 1 ∥ w − v ∥ 2 − 2 1 ∥ v ∥ 2 + i ∑ α i ≥ g ( α ) . 若某个可行点达到 g ( α ) g(\alpha) g ( α ) ,则每个可行点的目标值都至少是该值,所以它是最优解。
概念视角 几何
最大间隔即两类之间最接近的一对点 数据严格可分时,两个支撑平面之间的最优间距 2 / ∥ w ∥ 2/\|w\| 2/∥ w ∥ ,等于两类凸包之间的欧氏距离(Euclidean distance),而边界是凸包上最接近一对点的垂直平分线。对偶乘子就是这两点的权重:∑ α i y i = 0 \sum\alpha_iy_i=0 ∑ α i y i = 0 使正类与负类的权重总和相等,w w w 则与两点之差成比例。在两个观察点的例子中,两个凸包就是点 0 0 0 与点 4 4 4 ,距离 4 = 2 / ∥ w ∥ 4=2/\|w\| 4 = 2/∥ w ∥ 。
展开对偶范数会出现 x i T x j x_i^Tx_j x i T x j 。以有效核函数替换这些项,相当于使用特征向量 ϕ ( x i ) \phi(x_i) ϕ ( x i ) 作同一构造。这不代表每个看似对称的公式都有效,也不代表只在一个训练集检查 Gram 矩阵便能证明整个定义域有效;它亦不会自动选择特征尺度或超参数。模型选择应只用训练数据拟合学得的预处理,选设定时不查最终测试标签,然后在保留数据评估选定流程。完美拟合训练观察是关于这些观察的证据,本身不保证泛化。
间隔分数亦不能自动当成已校准概率。其符号在选定阈值下提供决策,大小则依惯例量度归一化或未归一化距离;两者都不表示分数为 2 就代表正类概率 88%。若需要概率,须另行指定校准程序并适当验证。正则化参数 C C C 影响范数与训练损失的取舍,但其合适值取决于损失惯例、特征尺度及任务。每个特征乘 2 却不调整模型,会改变固定 w w w 的意义,也可能改变拟合最优解。
在线性例子中,把 ( w , b ) = ( 1 / 2 , − 1 ) (w,b)=(1/2,-1) ( w , b ) = ( 1/2 , − 1 ) 乘 2,边界仍为 x = 2 x=2 x = 2 、符号不变;函数间隔变为 2,但范数也加倍,故几何间隔仍为 2。缩放后仍可行,但正则项由 1 / 8 1/8 1/8 增至 1 / 2 1/2 1/2 ,所以不是硬间隔最小解。此检查把归一化、几何和优化连起来,并没有把分数当成概率。
练习
快速检查
(一维中,观察 x = 3 x=3 x = 3 、y = + 1 y=+1 y = + 1 由 ( w , b ) = ( 2 , − 2 ) (w,b)=(2,-2) ( w , b ) = ( 2 , − 2 ) 评分。求它的函数间隔与几何间隔,并求 ( 4 , − 4 ) (4,-4) ( 4 , − 4 ) 的这两个间隔。)
用 f ( x ) = w x + b f(x)=wx+b f ( x ) = w x + b ,几何间隔再除以 ∣ w ∣ |w| ∣ w ∣ 。
解答 · 答案 对 ( 2 , − 2 ) (2,-2) ( 2 , − 2 ) :f ( 3 ) = 4 f(3)=4 f ( 3 ) = 4 ,所以函数间隔为 4 4 4 ,几何间隔为 4 / 2 = 2 4/2=2 4/2 = 2 。对 ( 4 , − 4 ) (4,-4) ( 4 , − 4 ) :f ( 3 ) = 8 f(3)=8 f ( 3 ) = 8 ,函数间隔为 8 8 8 ,几何间隔为 8 / 4 = 2 8/4=2 8/4 = 2 。重新缩放改变函数间隔,但不改变几何间隔。
快速检查
(某分数为 f ( x ) = 0.3 f(x)=0.3 f ( x ) = 0.3 。分别在 y = + 1 y=+1 y = + 1 与 y = − 1 y=-1 y = − 1 时求合页损失。)
用 max ( 0 , 1 − y f ( x ) ) \max(0,1-yf(x)) max ( 0 , 1 − y f ( x )) 。
解答 · 答案 y = + 1 y=+1 y = + 1 :max ( 0 , 1 − 0.3 ) = 0.7 \max(0,1-0.3)=0.7 max ( 0 , 1 − 0.3 ) = 0.7 。y = − 1 y=-1 y = − 1 :y f ( x ) = − 0.3 yf(x)=-0.3 y f ( x ) = − 0.3 ,损失为 max ( 0 , 1.3 ) = 1.3 \max(0,1.3)=1.3 max ( 0 , 1.3 ) = 1.3 。对正确标签,小的正分数仍在间隔之内,损失 0.7 0.7 0.7 ;标签错了,损失超过 1 1 1 。
快速检查
(判断 K ( x , z ) = x z K(x,z)=xz K ( x , z ) = x z 与 K ′ ( x , z ) = − x z K'(x,z)=-xz K ′ ( x , z ) = − x z 在 R \mathbb R R 上是否为有效核函数。)
为其中一个找特征映射,为另一个找单点 Gram 矩阵。
解答 · 答案 K ( x , z ) = x z K(x,z)=xz K ( x , z ) = x z 是核函数,特征映射为 ϕ ( x ) = x \phi(x)=x ϕ ( x ) = x 。对 K ′ K' K ′ ,在 x = 1 x=1 x = 1 的单点 Gram 矩阵为 ( − 1 ) (-1) ( − 1 ) ,取 c = 1 c=1 c = 1 得 c T G c = − 1 < 0 c^TGc=-1<0 c T G c = − 1 < 0 ,所以 K ′ K' K ′ 不是核函数。
快速检查
(观察:x = 0 x=0 x = 0 、y = − 1 y=-1 y = − 1 与 x = 2 x=2 x = 2 、y = + 1 y=+1 y = + 1 。求硬间隔解,并说明 α = ( 1 / 2 , 1 / 2 ) \alpha=(1/2,1/2) α = ( 1/2 , 1/2 ) 可作为其最优性的证书。)
先把两个约束相加来界定 w w w ,再计算 g ( α ) g(\alpha) g ( α ) 。
解答 · 答案 约束为 − b ≥ 1 -b\ge1 − b ≥ 1 与 2 w + b ≥ 1 2w+b\ge1 2 w + b ≥ 1 。相加得 2 w ≥ 2 2w\ge2 2 w ≥ 2 ,故 w ≥ 1 w\ge1 w ≥ 1 ,而 ( w , b ) = ( 1 , − 1 ) (w,b)=(1,-1) ( w , b ) = ( 1 , − 1 ) 可行,目标为 1 2 \tfrac12 2 1 。对 α = ( 1 / 2 , 1 / 2 ) \alpha=(1/2,1/2) α = ( 1/2 , 1/2 ) :∑ α i y i = − 1 2 + 1 2 = 0 \sum\alpha_iy_i=-\tfrac12+\tfrac12=0 ∑ α i y i = − 2 1 + 2 1 = 0 ,∑ α i y i x i = 1 2 ⋅ 2 = 1 \sum\alpha_iy_ix_i=\tfrac12\cdot2=1 ∑ α i y i x i = 2 1 ⋅ 2 = 1 ,故 g ( α ) = 1 − 1 2 ⋅ 1 2 = 1 2 g(\alpha)=1-\tfrac12\cdot1^2=\tfrac12 g ( α ) = 1 − 2 1 ⋅ 1 2 = 2 1 。这等于原始目标,所以 ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) 最优。