CSCI3230 L04 · Part 3/6 Kernel SVM

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2026T1 本讲：L04，第 3 部分 / 共 6 部分 · 原件 L04-Support-Vector-Machine-2026T1.pdf（本地课件） p.32–41 定位：区分显式特征映射与核函数，用内积计算在高维空间训练而不显式展开特征。前后：上一份 Support Vector Machine · 下一份 Soft-margin SVM

p.32 分节页。

在原空间分不开，换什么（p.33–35）【新】

上一部分的方法要求一条直线能把两类完全分开。如果正类集中在圆心附近，负类围在外圈，一条直线只能把平面切成两个半平面，不能单独圈住中间。p.33–34此时改变的是描述样本的坐标，不是把标签偷偷调换，也不是把求解器再运行久一点。

先区分原特征与新特征。原输入 $x=(x_1,x_2)^T\in\mathbb R^2$ 有两个数字；p.35给一个固定映射

\phi(x)=(x_1^2,x_2^2,\sqrt2x_1x_2)^T\in\mathbb R^3.

$\phi$ 是函数名，读作“phi”；它接收一个二维点，输出一个三维点。三项依次是第一坐标平方、第二坐标平方、两个坐标的交叉乘积再乘 $\sqrt2$ 。这个根号不是随意装饰，稍后内积展开会用到它。

补充·数值例（自取）：点 $(1,2)^T$ 的新坐标是 $(1,4,2\sqrt2)^T$ 。令新空间权重 $v=(1,1,0)^T,b=-3$ ，则新分数为 $v^T\phi(x)+b=1+4-3=2$ 。对 $(0,1)^T$ ，新分数为 $0+1-3=-2$ 。输入仍是二维记录，只是计算规则用了它的平方特征。

令分数为零，得到 $x_1^2+x_2^2=3$ ，在原平面里是一条圆；若把新坐标叫 $z_1,z_2,z_3$ ，同一条件是 $z_1+z_2=3$ ，在新空间里是平面。所以“高维线性”和“原空间非线性”可以同时成立，所说的空间不同。

这里的例子把圆外判正、圆内判负；若任务标签相反，可把权重和偏移同乘−1。映射本身没规定正负方向，方向由训练决定。也不能认为随便升维都有效：若映射把异类点映到同一坐标，任何线性分类器仍无法分开。训练与新样本必须使用同一个可计算函数，不能给训练点人工编号后就说学会了泛化。

核函数计算的是内积（p.36–38）

p.36把训练约束的 $x_i$ 换成 $\phi(x_i)$ ，原理不变，但显式展开可能很长。p.37观察到对偶训练只需要新向量之间的内积，因此定义

K(x,z)=\phi(x)^T\phi(z).

输入是两个原空间样本，输出是一个标量。映射 $\phi$ 输出向量，核 $K$ 输出内积，二者不能混叫“把点升维的函数”。可以类比两份长清单的匹配分数，但数学结论必须是确实等于同一映射下的内积，不能把任意相似度都当合法核。

继续上节的映射，补充取 $x=(1,2)^T,z=(2,1)^T$ 。显式新坐标为 $(1,4,2\sqrt2)$ 与 $(4,1,2\sqrt2)$ ，内积为 $1\times4+4\times1+8=16$ 。原内积为 $1\times2+2\times1=4$ ，平方也为16。这样就有希望不用写三维向量，直接算 $(x^Tz)^2$ ；下一节证明它对任意输入都成立，而不是只对这一对数字巧合。

p.36–38的两幅公式图完整连接如下。映射到 $D$ 维以后， $w\in\mathbb R^D$ ：

\min_{w,b}\frac12\lVert w\rVert^2,\qquad y_i(w^T\phi(x_i)+b)\ge1.

固定映射后，其对偶为

\max_{\alpha}\left[\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)\right], \quad\alpha_i\ge0,\quad\sum_i\alpha_i y_i=0.

把每个映射内积换成 $K(x_i,x_j)$ 就是核对偶；可行条件没有变。原页红色删除线与箭头表示这次替换，并不是把二次项删去。求出乘子后可用 $b=y_s-\sum_i\alpha_i y_i K(x_i,x_s)$ 恢复偏移，其中 $\alpha_s>0$ ，条件同硬间隔。p.37对一般 $n$ 维二次映射比较复杂度：展开平方与交叉项需要 $O(n^2)$ 项，而先算一个原内积再平方只需 $O(n)$ 。这里比较的是一次核值计算，不能据此把整个SVM训练复杂度写成 $O(n)$ 。

训练时，原对偶中的每个 $x_i^Tx_j$ 替成 $K(x_i,x_j)$ ，求出的未知数仍是每样本一个 $\alpha_i$ 。预测时，p.38使用

f(x)=\sum_i\alpha_i y_iK(x_i,x)+b.

先算新点与第 $i$ 个训练点的核值，再乘该点的带符号权重，再把各项求和加偏移，最后才看符号。核值自身不是类别或概率。

补充·预测走一遍（只演示计算，不声称这些是某题最优参数）：用上面的二次核，取两个存储点 $(1,0)^T,(0,1)^T$ ，标签分别+1、−1，乘子都为0.5，偏移0。对新点 $(2,1)^T$ ，两个核值为4和1，分数 $0.5\times4-0.5\times1=1.5$ ，预测正类。即使核值都非负，标签的正负仍使最终分数可正可负。

核技巧节约的是显式展开高维特征的一类成本，不是免费训练。 $m$ 个样本的完整核矩阵有 $m^2$ 个位置；1000个样本就是100万个核值。选择线性模型、核模型时，特征维度与样本数都要考虑。

讲义核函数小测（p.39–40）

题面（L04-Support-Vector-Machine-2026T1.pdf · Quiz · p.39）

p.39 Which of the following function $\kappa(x_i,x_j)$ can be the kernel function of the transformation:

$x=(x^{(1)},x^{(2)})\Rightarrow\phi(x)=((x^{(1)})^2,(x^{(2)})^2,\sqrt2x^{(1)}x^{(2)})$

In other words, which one can make $\kappa(x_i,x_j)=\phi(x_i)^{T}\phi(x_j)$ ?

A $\kappa(x_i,x_j)=x_i^{T}x_j$

B $\kappa(x_i,x_j)=(x_i^{T}x_j)^2$

C $\kappa(x_i,x_j)=x_i^{T}+x_j$

D $\kappa(x_i,x_j)=x_i^{T}/x_j$

E $\kappa(x_i,x_j)=\sqrt2x_i^{T}x_j$

公式按讲义重排。下面保留原问题的全部候选，再逐步判断。

p.39问：对于上节三维映射，哪个表达式等于 $\phi(x_i)^T\phi(x_j)$ ？候选B为 $(x_i^Tx_j)^2$ ，p.40通过展开验证。下面逐步走，不只记选项。

设两点为 $x_i=(a,b)^T,x_j=(c,d)^T$ 。换短字母只为避免下标挤在一起，没有更换题目。映射后分别为 $(a^2,b^2,\sqrt2ab)^T$ 和 $(c^2,d^2,\sqrt2cd)^T$ 。对应坐标相乘后相加：

\begin{aligned} \phi(x_i)^T\phi(x_j) &=a^2c^2+b^2d^2+(\sqrt2ab)(\sqrt2cd)\\ &=(ac)^2+(bd)^2+2(ac)(bd)\\ &=(ac+bd)^2\\ &=(x_i^Tx_j)^2. \end{aligned}

第一行是内积定义；第二行把因子重排并使用 $\sqrt2\sqrt2=2$ ；第三行认出平方和公式；最后一行把短记号换回原内积。若映射第三坐标少了 $\sqrt2$ ，交叉项系数会变成1，这个核就不再匹配。

p.39的向量相除候选没有定义成标准内积运算，不需要替它发明一种含义。做映射核题的可靠方法是从内积定义展开，而不是看到“平方特征”就无条件猜平方核。

小检查（补充）：把 $\phi(x)$ 改成 $(x_1^2,x_2^2)^T$ ，原来的平方核仍成立吗？

参考答案

不成立。新内积只有 $a^2c^2+b^2d^2$ ，没有交叉项 $2abcd$ 。例如两个点都为 $(1,1)^T$ ，新内积为2，而原内积的平方为4。这一反例已足以否定“对所有输入相同”。

补充 · 名字叫相似度，还不一定能当内积核（通识讲解；演示数据不属于原题）。

内积核有一个可以检查的后果：对任意样本和实数系数 $c_i$ ，必须有 $\sum_{i,j}c_ic_jK(x_i,x_j)\ge0$ 。原因是该和等于 $\lVert\sum_i c_i\phi(x_i)\rVert^2$ ，平方长度不能负。这就是核矩阵半正定的来源，不是要求表格中每个元素都为正。

演示两样本的候选“相似度矩阵”为 $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ ，全部元素为正且对称；取 $c=(1,-1)^T$ ，二次型为 $1-2-2+1=-2$ ，所以不能来自普通实内积映射。反过来，一个矩阵里出现负的非对角项也不自动非法：向量夹角大于直角，内积本来就能为负。

核函数把隐式特征空间的几何带进优化，不能只凭“两个对象越像就给越大数”保证 SVM 对偶仍具有需要的凸优化性质。具体核的参数条件也要一起保留。

补充：两个点已经足以否决一个“相似度核”

自编候选相似度在两点上的矩阵是 $K=\begin{pmatrix}1&2\\2&1\end{pmatrix}$ 。它对称、对角为正、所有条目都正，看起来并不奇怪。但取系数向量 $c=(1,-1)^T$ ，有 $c^TKc=1-2-2+1=-2<0$ ，所以它不能是实内积特征映射在这两个点上的Gram矩阵。

为什么这个检验有效？若 $K_{ij}=\phi(x_i)^T\phi(x_j)$ ，则

\sum_{i,j}c_i c_jK_{ij} =\left\lVert\sum_i c_i\phi(x_i)\right\rVert_2^2\ge0.

左边就是二次型，右边是一个向量长度的平方，绝不可能为负。此例等价于要求两个长度都为1的向量内积为2，已违反内积的几何限制。

发现一组样本不半正定，就能否决“对所有样本合法”的说法；但检查一组样本恰好半正定，不能证明函数对任意输入集合都合法。要证明平方多项式核，正文给出的显式映射对任意输入成立，证据强度与一个数值矩阵测试不同。分清反例和一般证明，才不会把程序测过一个矩阵当作核函数定理。

常见核与不同任务（p.41）

p.41列出下面三类核（公式按讲义重排）。参数不是训练样本的坐标，而是决定比较方式的超参数。

名称	本页形式	怎样读
多项式	$K(x,z)=(x^Tz)^d$	先内积，再取正整数次数；此处 $d$ 是次数，不是前文特征维度
Sigmoid	$K(x,z)=\tanh(\beta x^Tz+\theta)$	内积缩放平移后经过双曲正切
Gaussian / RBF	$K(x,z)=\exp(-\lVert x-z\rVert_2^2/(2\sigma^2))$	由距离决定相似性， $\sigma>0$ 为宽度

原图还附三段用途说明：多项式核在原变量的多项式特征空间度量相似性；sigmoid形式与神经元双曲正切激活、双层感知机模型联系起来；Gaussian被介绍为没有明确数据先验时可尝试的变换。三张曲线依次展示多项式起伏、sigmoid饱和与Gaussian钟形。它们不是三套数据的分类边界，也不证明sigmoid-SVM等同于任意训练好的双层网络。

补充·RBF数值直觉：令 $\sigma=1$ 。同一点到自身距离0，指数为0，核值1；两点距离2，平方距离4，指数为−2，核值约0.1353。若仍相距2但把宽度改成2，指数变成−0.5，核值约0.6065。同样距离被较大的宽度认为更相似。这里1并不表示“属于正类的概率100%”，只是核值最大。

更小的宽度使每个样本的影响更局部，更大的宽度让远点也彼此相似。下一篇的 $C$ 是另一个旋钮：它控制违反间隔的代价。一个改变输入的比较方式，一个改变训练目标里的权衡，不能混成同一个“复杂度参数”。实际库也可能用 $\gamma=1/(2\sigma^2)$ ，这时 $\gamma$ 变大反而对应宽度变小。

补充·适用边界：多项式库实现可能加入缩放和常数，不一定正好是本页的齐次形式；sigmoid并非任意参数、任意输入范围都满足正半定核条件。所谓合法内积核，意味着任意有限样本产生的Gram矩阵符合相应内积性质，而不是仅仅公式看起来平滑。第一次学习先会核值和映射的区别，不必先证明一般核定理。

历史一维映射几何练习见附录 A1。它属于2025T1官方节选中的题，不据此断言2026T1考试安排。

本讲核心考点

核函数直接计算映射后内积（p.37–40，A 级：往年卷 SVM 映射题）。
原空间非线性边界可以来自高维线性分类器（p.33–35，A 级）。

附录

A1 作业/往年题演练（非讲义内容）：一维传感器点的二维映射

题面（Final-Exam-CSCI3230-Record-2025T1-官方节选.pdf · Part III Q1 · PDF p.3；扫描件，视觉读取）

p.3 1. (5%) A robot is using a SVM classifier for 1D sensor. The data $X\in\mathbb{R}$ is found to be not linearly separable. The training data points are:

Positive (+): $x_1=0,x_3=3,x_4=4$

Negative (-): $x_2=1$

To solve this, a feature mapping function $\Phi(X)=(X,(X-1)^2)$ is used to project the data into a 2D space.

(a) Calculate the 2D coordinates for all four data points $(x_1,x_2,x_3,x_4)$ after applying the mapping $\Phi(X)$ . Then, draw these 4 points in the 2D space and write the function of the line of decision boundary. (2%)

(b) In this new 2D space, which of the points $(x_1,x_2,x_3,x_4)$ are the support vectors? (2%)

(c) If the robot collects one more negative data point at $x_5=1.5$ , would its mapped position in the 2D space affect the decision boundary (margin) you drew in (a)? Justify your answer. (1%)

公式按原题重排。这里以当前实际核对的2025官方节选PDF p.3为题面；页上印刷页码是6，不能混作PDF页号。它是旧年份的几何练习，不代表当前学期题目。

(a) 先映射，再画线。 用 $(u,v)$ 表示新坐标，避免把一维输入与二维点混叫 $x$ 。映射规则 $u=x,v=(x-1)^2$ ，逐点计算：

原编号	原输入	计算第二坐标	新坐标	标签
1	0	$(0-1)^2=1$	$(0,1)$	+1
2	1	$(1-1)^2=0$	$(1,0)$	−1
3	3	$(3-1)^2=4$	$(3,4)$	+1
4	4	$(4-1)^2=9$	$(4,9)$	+1

现在找的是新平面的直线。计算 $v-u$ ：正点1、3号都是1，4号为5；负点2号为−1。于是正侧支撑线 $v-u=1$ 、负侧支撑线 $v-u=-1$ ，中线 $v=u$ 。规范参数 $w=(-1,1)^T,b=0$ ，范数 $\sqrt2$ ，总宽度 $\sqrt2$ 。

为什么这不是“随便画条可分线”？1号正点与2号负点的距离为 $\sqrt{(1-0)^2+(0-1)^2}=\sqrt2$ 。任何候选间隔都不能超过这对异类点之间的距离；本候选已达到它，所以是最大间隔。水平中线 $v=0.5$ 虽也可分，却只有宽1，不是最优。

(b) 先声明支持向量定义。 按“落在支撑面上”的几何定义，1、2、3号都贴面，4号严格在外。按“非零对偶系数”的计算定义，本例可取 $\alpha_1=\alpha_2=1$ ，其余零；合成 $w=(0,1)^T-(1,0)^T=(-1,1)^T$ ，已经满足全部条件。3号贴面却可零系数，这是退化例子，不要把它当矛盾。答题写清两种含义，比声称未经证实的唯一官方判分更可靠。

(c) 新负点先用同一映射，再验旧约束。 $x_5=1.5$ 映成 $(1.5,0.25)$ ，旧分数为 $-1.5+0.25=-1.25$ ；负标签乘后为1.25，已经在旧负支撑面外。旧解仍满足新点约束；1、2号造成的间隔上界也没有消失，因此原最大间隔仍最优，边界与宽度保持。

这个步骤说明不能凭原一维坐标左右移动来猜边界变化。真正要比较的是映射后的坐标及功能间隔，新增训练点与新增测试点的用途也不同。

回到正文：常见核与不同任务

来源与证据

页码按当前本地阅读版 PDF；L04 共69页，未把旧年份讲义当成本学期原件。
原件：L04-Support-Vector-Machine-2026T1.pdf（本地课件），p.32–41；均为当前 PDF 页号。
本次正文逐页核对本讲原件；文末历史题明确标旧年份，只作练习，不据此推断本学期考核要求。
往年卷仅证明相应年份考过；2024 卷及 2025 节选未公开的选择题不作推断。