跳转至

非线性 SVM 压轴计算题：异或（XOR）四步完整解法

  • 章节：第7章 · 支持向量机（7.3 核函数 / 7.4 对偶问题与决策函数）
  • 题型：给数据 + 给核 → 求决策函数 \(f(\boldsymbol x)\) 的完整计算题（范围内最硬的一类）。
  • 出处：方法忠于课本 7 章——对偶问题（min 版，内积换核）、决策函数式 7.94 \(f(\boldsymbol x)=\operatorname{sign}\!\big(\sum_i\alpha_i^*y_iK(\boldsymbol x,\boldsymbol x_i)+b^*\big)\)、多项式核式 7.88 \((\boldsymbol x\cdot\boldsymbol z+1)^p\)（此处 \(p=2\)）。题目本身为作业/PPT 计算题，非课本原例。

一、整道题在干什么（全局四步）

目标和线性 SVM 一样：求一个分类器 \(f(\boldsymbol x)\)，输入点就判 +1 / −1。路径固定四步，每步为下一步服务：

\[\underbrace{\text{核矩阵 }\boldsymbol K}_{\text{备好内积}}\to\underbrace{\text{对偶问题}}_{\text{列出优化}}\to\underbrace{\text{解出 }\boldsymbol\alpha^*}_{\text{得到乘子}}\to\underbrace{\text{决策函数 }f(\boldsymbol x)}_{\text{最终分类器}}\]

题目

\[X_1=(-1,-1),\,y_1=-1;\quad X_2=(-1,1),\,y_2=1;\quad X_3=(1,-1),\,y_3=1;\quad X_4=(1,1),\,y_4=-1\]

核函数（多项式核 \(p=2\)）：\(K(\boldsymbol x,\boldsymbol z)=(1+\boldsymbol x\cdot\boldsymbol z)^2\)。

这是异或（XOR）问题：对角两点一类、反对角两点另一类，线性不可分，必须靠核。

二、第一步——核矩阵 K

\(K(X_i,X_j)=(1+X_i\cdot X_j)^2\)。同一点 \(X_i\cdot X_i=2\Rightarrow K=(1+2)^2=9\)；不同点 \(X_i\cdot X_j\in\{0,-2\}\Rightarrow K=(1+0)^2=1\) 或 \((1-2)^2=1\)。故对角 9、非对角全 1：

\[\boldsymbol K=\begin{bmatrix}9&1&1&1\\1&9&1&1\\1&1&9&1\\1&1&1&9\end{bmatrix}\]

作用：把"任意两点经核后的值"提前算好，供对偶问题调用。

三、第二步——对偶问题（要背的 min 版，内积换核 K）

\[\min_{\boldsymbol\alpha}\ \frac12\sum_{i=1}^4\sum_{j=1}^4\alpha_i\alpha_j y_iy_j K(X_i,X_j)-\sum_{i=1}^4\alpha_i$$ $$\text{s.t.}\quad \sum_{i=1}^4\alpha_i y_i=0,\qquad \alpha_i\ge0\]

逐块含义：每对点 \((i,j)\) 贡献 \(\alpha_i\alpha_j y_iy_j K_{ij}\)；\(y_iy_j\) 同号 \(+1\)、异号 \(-1\)；末尾 \(-\sum\alpha_i\)。

代入数字（\(\boldsymbol y=(-1,+1,+1,-1)\)）：

  • 对角项（\(y_i^2=1,K=9\)）：\(\frac12\cdot9\sum\alpha_i^2=\frac92(\alpha_1^2+\alpha_2^2+\alpha_3^2+\alpha_4^2)\)。
  • 交叉项（\(K=1\)，系数 \(\frac12\times2=1\)，符号看 \(y_iy_j\)）：
\[-\alpha_1\alpha_2-\alpha_1\alpha_3+\alpha_1\alpha_4+\alpha_2\alpha_3-\alpha_2\alpha_4-\alpha_3\alpha_4\]

（\(\alpha_1\alpha_4\) 同号 \((-,-)\)、\(\alpha_2\alpha_3\) 同号 \((+,+)\) 取 \(+\)；其余四对异号取 \(-\)。）

完整目标函数：

\[\min_{\boldsymbol\alpha}\ \frac92(\alpha_1^2+\alpha_2^2+\alpha_3^2+\alpha_4^2)-\alpha_1\alpha_2-\alpha_1\alpha_3+\alpha_1\alpha_4+\alpha_2\alpha_3-\alpha_2\alpha_4-\alpha_3\alpha_4-(\alpha_1+\alpha_2+\alpha_3+\alpha_4)\]

等式约束代入 \(\boldsymbol y\)：\(-\alpha_1+\alpha_2+\alpha_3-\alpha_4=0\)。

给分点：很多题写到"目标函数 + 两行约束"即给分。

四、第三步——解出 α*

四点完全对称 ⟹ 猜最优解 \(\alpha_1^*=\alpha_2^*=\alpha_3^*=\alpha_4^*=\alpha\)，代入验证：

  • 等式约束 \(-\alpha+\alpha+\alpha-\alpha=0\) ✓ 自动满足。
  • 目标变单变量。用 \(\sum_{i,j}y_iy_jK_{ij}=\underbrace{36}_{\text{对角}4\times9}+\underbrace{(-4)}_{\text{非对角}}=32\)，其中非对角和 \(=\big(\sum y_i\big)^2-\sum y_i^2=0-4=-4\)。于是
\[\frac12\cdot32\,\alpha^2-4\alpha=16\alpha^2-4\alpha\]
  • 求导令零：\(32\alpha-4=0\Rightarrow \alpha=\frac18\)。
\[\boxed{\alpha_1^*=\alpha_2^*=\alpha_3^*=\alpha_4^*=\tfrac18}\]

四个 \(\alpha^*>0\) ⟹ 四点全是支持向量（XOR 题特点）。

五、第四步——决策函数 f(x)

模板（式 7.94）：

\[f(\boldsymbol x)=\operatorname{sign}\!\Big(\sum_{i=1}^4\alpha_i^*y_i K(\boldsymbol x,X_i)+b^*\Big)\]

\(b^*=0\)（用 KKT 验，非空口对称）：对支持向量 \(X_1\)，\(\sum_j\alpha_j^*y_jK(X_1,X_j)=\frac18(-9+1+1-1)=-1\)，代 \(y_1(\cdot+b^*)=1\Rightarrow(-1)(-1+b^*)=1\Rightarrow b^*=0\)。

代入 \(\alpha_i^*=\frac18\)、\(\boldsymbol y=(-1,+1,+1,-1)\)：

\[f(\boldsymbol x)=\operatorname{sign}\!\Big(\tfrac18\big[-K(\boldsymbol x,X_1)+K(\boldsymbol x,X_2)+K(\boldsymbol x,X_3)-K(\boldsymbol x,X_4)\big]\Big)\]

把核展开（\(\boldsymbol x=(x_1,x_2)\)，\(K(\boldsymbol x,X_i)=(1+\boldsymbol x\cdot X_i)^2\)）：

\[K_1=(1-x_1-x_2)^2,\quad K_2=(1-x_1+x_2)^2,\quad K_3=(1+x_1-x_2)^2,\quad K_4=(1+x_1+x_2)^2\]

逐项展开 \(-K_1+K_2+K_3-K_4\)，常数项、\(x_1\)、\(x_2\)、\(x_1^2\)、\(x_2^2\) 全部抵消，只剩交叉项：

\[-K_1+K_2+K_3-K_4=-8x_1x_2\]

再乘 \(\frac18\)：

\[f(\boldsymbol x)=\operatorname{sign}(-x_1x_2)\]

回代验证全对： \(X_1(-1,-1)\!:\,-(-1)(-1)=-1\to\) 负 ✓；\(X_2(-1,1)\!:\,-(-1)(1)=+1\to\) 正 ✓；\(X_3(1,-1)\!:+1\to\) 正 ✓；\(X_4(1,1)\!:-1\to\) 负 ✓。

决策边界 \(x_1x_2=0\)（两条坐标轴）正好把异或四点分开——核函数把线性不可分的 XOR 解决了。

易错点 / 提醒

  • ⚠️ 决策函数展开的精确系数：方括号 \(-K_1+K_2+K_3-K_4=-8x_1x_2\)，\(\times\frac18=-x_1x_2\)。若中途写成 \(-2x_1x_2\) 之类是笔误，但因 \(\operatorname{sign}\) 对正数倍缩放不变，\(\operatorname{sign}(-8x_1x_2)=\operatorname{sign}(-x_1x_2)\) 仍是同一分类器，最终答案不受影响。
  • ⚠️ \(b^*\) 别只写"由对称性为 0"，最好用一个支持向量的 KKT 条件 \(y_s\big(\sum_i\alpha_i^*y_iK(X_s,X_i)+b^*\big)=1\) 解出来，更稳。
  • 对偶目标的交叉项符号来自 \(y_iy_j\)，不是核（核这里全 1）；别把符号算错。
  • 非对角和的速算技巧：\(\sum_{i\ne j}y_iy_j=\big(\sum_i y_i\big)^2-\sum_i y_i^2\)。本题 \(\sum y_i=0\)，省去逐项加。
  • 给分梯度：写出"对偶目标 + 约束"基本稳；再解出 \(\alpha^*\)、写出 \(f(\boldsymbol x)\) 即满分。