监督学习是指利用带有标记的样本数据来完成拟合或者分类任务。第 2 章介绍的统计 
学习方法需要已知先验概率 p(wi) 和类条件概率密度 p(x|wi) 的形式，其中类条件概率需 
要通过参数化或者非参数化方法进行估计。然而，在特征维数较高、内在关系复杂或者样 
本数量较少时，很难精确估计类条件概率密度。若能够直接通过样本数据生成拟合函数或 
者判别函数，则能够在一定程度上避免统计学习方法的局限。 
基于样本数据的拟合函数或者分类器设计需要确定三个要素：.1 拟合函数或者分类器 
类型（参数化函数集合）；.2 拟合或分类的目标准则，即最优化模型的目标函数；.3 拟合 
函数或者分类模型的参数值，即设计最优化算法。不同的函数类型、不同的目标准则以及 
不同的优化算法决定了不同的拟合或分类效果。 
本章内容分成 5 节： 
3.1 节介绍的最小二乘法主要用于解决线性回归问题，而线性概率回归方法主要用于 
解决逻辑回归（或分类）问题。 
3.2 节首先介绍支持向量机，主要用于解决线性二分类问题；接着介绍软间隔支持向量 
机，用于处理少量样本无法线性分类的情形；最后介绍支持向量回归，用于解决鲁棒线性 
回归问题。 
3.3 节介绍的核方法主要用于解决非线性拟合或分类问题。其主要思路是将低维空间 
的非线性回归或分类问题转换成高维空间的线性回归或分类问题，然后设计核函数并使用 
最小二乘法或者支持向量机来实现拟合或分类功能。 
3.4 节介绍神经网络以及误差反向传播算法。由于神经网络的强大拟合能力，其能够实 
现复杂非线性拟合或分类功能，并广泛应用于语音和图像处理。 
3.5 节介绍复合学习方法，通过构建多个学习器来实现稳定可靠的学习或分类任务。复 
合方法包括空间上的并行方式、时间上的序贯方式以及在结构上的嵌套方式。除了基本的 
集成学习算法外，本节还简要介绍了迁移学习、终身学习和元学习的基本原理。 
3.1 最小二乘法 
3.1.1 线性回归 
统计回归是指在给定自变量 x1, · · · , xd 观测值的情况下对因变量 y 进行预测，在社会 
和科学领域有着很多应用。若因变量表示庄稼的收成，则自变量可以是雨量、光照、土质 
等因素。在动态系统中，因变量往往是系统输出，而自变量是系统的过去行为表现。 
令 x = [x1, · · · , xd]T。从数学描述来看，统计回归是指寻找一个回归量 g(x) 使其跟因 
变量的观测值 y 尽量接近，即 |y .g(x)| 的值尽量小。.y = g(x) 称为预测值。在没有 x 和 
y 的先验信息时，线性回归通常有如下形式: 
g(x) = xTθ, x, θ ∈ Rd (3.1) 
43
假如在 t = 1, 2, · · · ,N 时刻能够获得自变量和因变量的观测值，分别记为 xt 和 yt， 
则线性回归的拟合函数可定义为
VN(θ) = 
1 
N 
N Σt=1
[yt . xTt
θ]2 
= 
1 
N ∥YN .XNθ∥2 
(3.2) 
式中 
YN =.... 
y1
... 
yN
....
, XN =.... 
xT1
... 
xT
N
.... 
线性拟合的目的是去寻找 θ 值使 VN(θ) 达到最小，即 
. θ = arg min 
θ 
VN(θ) 
s.t. VN(θ) = 
1 
N ∥YN .XNθ∥2 
上述优化问题的最优解也称为最小二乘估计。 
1. 最小二乘解 
通过对函数 VN(θ) 求导置零，得到如下正规方程： 
XT
NXNθ = XT
NYN 
当矩阵 XN 列满秩时，上述正规方程有唯一解： 
. θN = (XT
NXN).1XT
NYN = X.N
YN 
式中：“.”为 Moore-Penrose 伪逆。 
2. 最优解的几何意义 
上述线性拟合的最小二乘解可以从几何角度进行解释。正规方程等式可以写成如下等 
价形式： 
XT
N(XN . θN . YN) = 0 
从上式可以看出，回归向量 XN 和残差向量 EN = YN .XN . θN 正交。因此，可以通过建 
立上述正交方程来获得最小二乘解。 
44
3.1.2 逻辑回归 
针对二值分类问题，假设训练数据集为 {XN,CN} = {xn, cn}Nn
=1，其中 cn ∈ {0, 1}。 
令 xn 属于类别 cn = 1 的概率为 
p(cn = 1|xn) = σ(wTxn + b) = 
ewTxn+b 
1 + ewTxn+b = 
1 
1 + e.wTxn.b 
式中：σ(·) ∈ [0, 1] 为 Logistic 或者 Sigmoid 函数。 
根据上述概率定义可得 
log p(cn = 1|xn) 
p(cn = 0|xn) 
= wTxn + b 
由于概率似然比的对数为线性函数，因此求解 w 和 b 的问题称为线性概率回归。 
二项逻辑回归可以推广到多项逻辑回归。若离散型随机变量 cn 的取值集合为 {1, 2, · · · , 
K}，则多项逻辑回归模型可写成 
p(cn = k|xn) = 
ewT
k xn+bk 
1 + 
K.1 Σk=1 
ewT
k xn+bk 
, k = 1, · · · ,K . 1 
p(cn = K|xn) = 
1 
1 + 
K.1 Σk=1 
ewT
k xn+bk 
(3.3) 
1. 逻辑回归的优化 
对于二分类问题，假设各训练数据相互独立，似然函数可写成 
p(CN|XN,w, b) = 
NΠn=1 
p(cn|xn,w, b) 
= 
NΠn=1 
pcn(cn = 1|xn,w, b)p1.cn(cn = 0|xn,w, b) 
相应的对数似然函数可以写成 
L(w, b) = 
N Σn=1 
cn log σ(wTxn + b) + (1 . cn) log(1 . σ(wTxn + b)) 
= 
N Σn=1 
log(1 . σ(wTxn + b)) + 
N Σn=1 
cn(wTxn + b) 
通过极大似然法可获得最优参数 w, b： 
{w., b.} = arg max 
w,b 
L(w, b) 
45
由于上述最优化问题不能直接得到闭式解，因此用梯度上升法来迭代计算，其中涉及的梯 
度信息包括 
.wL(w, b) = 
N Σn=1 [cnxn . σ(wTxn + b)xn] 
.bL(w, b) = 
N Σn=1 [cn . σ(wTxn + b)] 
利用关系式 .xσ(x) = σ(x)[1 . σ(x)] 可简化上式的梯度计算。梯度上升法通过如下公式进 
行迭代更新： 
wk+1 = wk + η.wL(wk, bk) 
bk+1 = bk + η.bL(wk, bk) 
式中：η 为迭代步长，k 为迭代次数。 
2. 逻辑回归的凹函数特性 
当 b = 0 时，对数似然函数 L(w) 是关于 w 的凹函数，因此梯度上升法能够收敛到全 
局最优解。接下来将证明 L(w) 为凹函数。L(w) 的 Hessian 矩阵为 
Hi,j = 
.2L 
.wi.wj 
= . 
N Σn=1 
xn,ixn,jσ(wTxn)[1 . σ(wTxn)] 
对于任意的向量 z，如下不等式成立： 
Σi,j 
ziHi,jzj = .Σi,j,n 
zixn,izjxn,jσ(wTxn)[1 . σ(wTxn)] 
. .Σn 
σ(wTxn)[1 . σ(wTxn)](Σi 
zixn,i)2 
. 0 
因此，L(w) 是关于 w 的凹函数。 
3.1.3 均方误差估计 
对于线性拟合模型 y = xTw，其中 x 为随机输入向量，w 为权重向量，y 为期望输 
出。权重向量 w 通过最小化期望输出和实际输出之间的均方误差进行求解： 
w. = argmin 
w 
J(w) 
s.t. J(w) = E[∥y . xTw∥2] 
46
通过对 J(w) 关于 w 求导置零得到 
.J(w) 
.w 
= 2E[x(y . xTw)] = 0 (3.4) 
由此得到 
w. = E.1[xxT]E[xy] (3.5) 
式中：E[xxT] 和 E[xy] 分别为自相关矩阵和互相关矩阵，通常需要知道概率分布函数来计 
算理论期望值或者通过对大量样本计算经验期望值。Robbins 和 Monro 利用随机逼近理论 
提供了一种解决方案。考虑如下形式方程： 
E[f(xk,w)] = 0 
式中：f(·) 为非线性函数；xk(k = 1, 2, · · · ) 为满足同分布的随机向量序列；w 为未知参数 
向量。
可以看出，线性方程 (3.4) 是上述方程一类特殊形式。随机逼近算法采用如下迭代策略： 
w.(k) = w.(k . 1) + ρkf(xk,w.(k . 1)) 
式中：ρk 为时变步长。 
针对上述迭代方程，当序列 ρk 满足条件 
∞Σk=1 
ρk → ∞, 
∞Σk=1 
ρ2
k < ∞ 
时，估计值 w.k 将均方收敛到方程 E[f(xk,w)] = 0 的真实解 w.，即 
lim 
k→∞E[∥w.(k) . w.∥2] = 0 
例 3.1（随机逼近） 
考虑简单方程 E[xk . w] = 0。令 ρk = 1/k，则迭代策略为 
w.(k) = w.(k . 1) + 
1
k 
[xk . w.(k . 1)] = 
k . 1 
k 
w.(k . 1) + 
1
k
xk 
可以看出，当 k 值趋向于无穷时，有 w.(k) → 
k Σi=1 
xi 
k 
。 
对于线性方程(3.4)，随机逼近的迭代方程可写成 
w.(k) = w.(k . 1) + ρkxk (yk . xTk
w.(k . 1)) 
上述迭代算法将收敛到最小均方估计值。 
47
3.2 支持向量机 
支持向量机最初由学者 Vapnik 提出，其基本模型主要用于解决二分类问题。SVM 分 
类器不同于一般的分类器，具有更好的鲁棒性和泛化能力，因此被广泛应用于线性分类和 
非线性分类。 
3.2.1 标准支持向量机 
给定一个二分类数据集 D = {xt, yt}N t=1，其中 yt ∈ {+1,.1}。若两类样本是线性可分 
的，则存在一个超平面 
wTxt + b = 0 
使得 
yt = { 1, wTxt + b > 0 
.1, wTxt + b < 0 
若两类样本线性可分，则意味存在 w 和 b 使得任意样本对 {(xt, yt)}N t=1 都满足 yt[wTxt + 
b] > 0。 
1. 支持向量机模型 
数据集 D 中每个样本 xt 到分类超平面的距离为 
γt = |wTxt + b| 
∥w∥ 
= 
yt[wTxt + b] 
∥w∥ 
定义间隔 γ 为整个数据集 D 中所有样本到超平面的最短距离： 
γ = min 
t |γt| 
若间隔 γ 越大，则分割超平面对两类数据的划分越稳定，不容易受到观测噪声等因素 
的影响（如图 3.1 所示）。支持向量机的设计目标是寻找超平面的参数 (w, b) 使得最小间 
隔 γ 最大化，即 
max 
w,b 
2γ 
s.t. yt[wTxt + b] 
∥w∥ 
> γ, .t = 1, · · · ,N 
由于满足 wTxt + b = 0 的 (w, b) 值存在尺度不确定性，为此可以限制 ∥w∥γ = 1，使 
得上述优化问题等价转换成 
max 
w,b 
2 
∥w∥ 
s.t. yt[wTxt + b] . 1, .t = 1, · · · ,N 
48
或者 
min 
w,b 
∥w∥2 
2 
s.t. yt[wTxt + b] . 1, .t = 1, · · · ,N 
(3.6) 
不难看出，上述优化问题为凸优化问题。当两类样本线性可分时，该优化问题具有强对偶性。 
数据集中所有满足 yt[wTxt + b] = 1 的样本点称为支持向量。由于支持向量机是具有 
间隔最大的分类超平面，因此其通常具有唯一性。 
图 3.1 分类间隔与最优超平面 
2. 支持向量机的优化 
对支持向量机所对应的优化问题式 (3.6) 采用拉格朗日方法进行求解。其对应的拉格 
朗日函数可以写成
L(w, b,λ) = ∥w∥2 
2 
+ 
N Σt=1 
λt (1 . yt[wTxt + b]), λt . 0 (3.7) 
分别计算 L 关于 w、b 的导数并置零，得到 
w = 
N Σt=1 
λtytxt (3.8) 
0 = 
N Σt=1 
λtyt (3.9) 
将式 (3.8) 代入式 (3.7)，然后利用式 (3.9) 得到如下拉格朗日对偶函数： 
J(λ) = .
1
2 
N,N Σ t=1,k=1 
λtλkytykxTt
xk + 
N Σt=1 
λt 
49
由此，支持向量机的对偶优化问题可以写成 
max 
λ . 
1
2 
N,N Σ t=1,k=1 
λtλkytykxTt
xk + 
N Σt=1 
λt 
s.t. 
N Σt=1 
λtyt = 0 
λt . 0 
(3.10) 
当原优化问题 (3.6) 具有强对偶性或者数据集线性可分时，可以通过最大化对偶优化问题 
来进行求解。不难看出对偶问题的目标函数是凹函数，而约束条件为线性约束。因此，最 
大化对偶优化问题能获得全局最优解。通常采用比较高效的序贯最小优化算法。每次迭代 
选择变量 λi 和 λj，在固定其他参数后，对偶优化问题式 (3.10) 仅需优化两个参数，其对 
应的约束可重写成 
λiyi + λjyj = c (3.11) 
式中：c = . Σ t.=i,j 
λtyt。 
通过上述等式可以消去变量 λj，得到一个关于 λi 的单变量二次规划问题，仅存在的 
约束为 λi . 0。由此可以得到单变量二次规划问题的闭式解，从而提高优化效率。 
根据优化理论中的 KKT 互补松弛条件，最优解 (λ.t
,w., b.) 需要满足 
λ.t
[1 . yt(w.Txt + b.)] = 0 
若样本不在约束边界上，即 1.yt(w.Txt +b.) < 0，则对应的 λt = 0；若样本在约束边界 
上，则 λt 可以不为零。 
支持向量机的最优权重向量 w 需满足式 (3.8)，即 w 的最优值依赖 λt，而非零的 λt 
值只发生在支持向量上。因此，支持向量机的分类超平面表达式只依赖支持向量，具有很 
好的稀疏特性。这就是该分类器称为“支持向量机”的原因。 
通过求解对偶优化问题式 (3.10) 获得对偶变量 λt 的最优值后，根据式 (3.8) 得到最优 
权重 w.。到目前为止，如何求解偏置 b 的最优值还没有得到解决。通过互补松弛分析，非 
零 λt 所对应的样本 xt 被确定为支持向量。若 xt 为支持向量，则最优偏置 b 通过求解如 
下方程来获得： 
yt[w.Txt + b.] = 1 
或者 
b. = yt . w.Txt (3.12) 
最终的支持向量分类器可以写成
yt = sgn[w.Txt + b.] 
50
3. 支持向量机算法描述及示例 
综上所述，给定线性可分训练数据集合，支持向量机的分类超平面可以通过算法 3.1来 
获得。 
算法 3.1（支持向量机学习算法） 
输入：线性可分训练数据集合 {xt, yt}N t=1。 
（1）构造并求解对偶优化问题式 (3.10)，得到最优解 {λ.t 
}N t=1。 
（2）通过式 (3.8) 计算权重向量 w.，确定非零 λ.t
对应的样本为支持向量，并通过式 (3.12) 
得到最优偏置 b.。 
（3）求得分类超平面 w.Tx + b. = 0。 
输出：分类决策函数 yt = sgn[w.Txt + b.]。 
接下来将通过一个简单例子来阐述支持向量机的应用。 
例 3.2（支持向量机示例） 
给定正样本点 x1 = (3, 3), x2 = (4, 3) 和负样本点 x3 = (1, 1)，试设计线性可分支持向 
量机。
解：该问题可以采用几何方法或代数方法来求解。 
第一种方法为几何方法。根据支持向量机的基本原理，首先确定支持向量 (3, 3) 和 
(1, 1)，然后根据支持向量确定最优分类面为 
x1 + x2 = 4 
第二种方法为代数方法，即采用算法 3.1进行求解。首先，根据给定数据对偶优化问题 
可以写成 
min 
λ 
1
2Σi Σj 
1
2
(18λ21
+ 25λ22
+ 2λ23
+ 42λ1λ2 . 12λ1λ3 . 14λ2λ3) . λ1 . λ2 . λ3 
s.t. λ1 + λ2 . λ3 = 0 
λi . 0, i = 1, 2, 3 
求解上述优化问题可得最优解 λ = (1/4, 0, 1/4)。然后，根据式 (3.8) 和式 (3.12) 可得最优 
权重向量 (1/2, 1/2) 和最优偏置值 .2。由此可以得到如下分类决策函数： 
y = sgn (x1 
2 
+ 
x2 
2 . 2) 
51
3.2.2 软间隔与正则化 
标准支持向量机主要是针对线性可分的数据集，即约束条件相对比较严格。当数据集 
线性不可分时，标准支持向量机无法找到最优解（如图 3.2 所示）。为解决该问题，引入松 
弛变量 ξt 来容忍不满足约束条件的样本，但是需要对其进行惩罚。根据该思想，改进支持 
向量机的优化问题可以写成 
min 
w,b,ξ 
∥w∥2 
2 
+ c 
N Σt=1 
ξt 
s.t. yt[wTxt + b] . 1 . ξt 
ξt . 0, .t = 1, · · · ,N 
(3.13) 
其中，参数 c > 0 用来控制间隔和松弛变量惩罚之间的平衡。引入松弛变量的间隔称为软 
间隔。 
图 3.2 软间隔与正则化 
类似于标准支持向量机的求解方式，构建如下拉格朗日函数： 
L(w, b, ξ,λ,α) = ∥w∥2 
2 
+ c 
N Σt=1 
ξt 
+ 
N Σt=1 
λt[1 . ξt . yt(wTxt + b)] . 
N Σt=1 
αtξt 
式中：λt, αt . 0 为拉格朗日乘子。 
对上述拉格朗日函数关于 w、b、ξt 求偏导置零，得到 
52
..
..........
.........
w = 
N Σt=1 
λtytxt 
0 = 
N Σt=1 
λtyt 
c = λt + αt 
(3.14) 
将上式代入拉格朗日函数后得到如下对偶优化问题： 
max 
λ 
N Σt=1 
λt . 
1
2 
N,N Σ t=1,k=1 
λtλkytykxTt
xk 
s.t. 
N Σt=1 
λtyt = 0 
0 . λt . c, .t = 1, · · · ,N 
(3.15) 
通过最大化上述凹优化问题可以获取 λt 的全局最优解，然后将其代入式 (3.14) 得到权重 
向量的 w 最优解。接下来将讨论如何求解最优偏置 b。 
根据优化理论的 KKT 互补松弛条件，可以得到 
λt (yt[wTxt + b] + ξt . 1)= 0 
αtξt = 0 
c = λt + αt 
通过 λt 的值可以判断样本 xt 是否为支持向量。若 λt > 0，则样本 xt 满足 yt[wTxt+b]+ξt = 
1。同时，根据约束 λt + αt = c，判断出当 0 < λt < c 时，αt > 0 并且 ξt = 0。因此，若 
0 < λt < c，偏置 b 的最优解可以从其对应的样本和标记得到 
b. = 
1 
yt . w.Txt = yt . w.Txt (3.16) 
最终，基于软间隔正则化的支持向量分类器可以写成 
yt = sgn[w.Txt + b.] 
算法 3.2（软间隔支持向量机学习算法） 
输入：训练数据集合 {xt, yt}N t=1。 
（1）选择惩罚参数 c，构造并求解对偶优化问题式 (3.15)，得到最优解 {λ.t 
}N t=1。 
（2）通过式 (3.14) 计算权重向量 w.，确定 0 < λ.t
< c 对应的样本为支持向量，并通过 
53
式 (3.16) 得到最优偏置 b.。 
（3）求得分类超平面 w.Tx + b. = 0。 
输出：分类决策函数 yt = sgn[w.Txt + b.]。 
3.2.3 支持向量回归 
具有软间隔的支持向量机式 (3.13) 可以表示成经验风险 + 正则化的形式： 
min 
w,b 
N Σt=1 
max(0, 1 . yt[wTxt + b]) + ∥w∥2 
2c 
式中：max(0, 1 . yt[wTxt + b]) 为损失函数；∥w∥2 
2c 
为正则化项。 
接下来将基于上述正则化形式设计支持向量回归模型。 
不同于分类问题，我们希望获得一个回归模型 wTxt + b，使其与 yt 尽可能接近。支 
持向量回归与传统回归不同的地方在于容许 wTxt + b 和 yt 之间存在最多 . 的偏差，当 
|yt . wTxt . b| > . 时才计算损失（如图 3.3 所示）。 
图 3.3 支持向量回归 
支持向量回归的优化形式可以写成 
min 
w,b 
N Σt=1 
max{0, |yt . wTxt . b| . .} + ∥w∥2 
2c 
或者 
min 
w,b, ˉ ξ,ξ 
∥w∥2 
2 
+ c 
N Σt=1
(ˉξt + ξ
t
) 
s.t. yt . wTxt . b . . + ˉξt 
wTxt + b . yt . . + ξ
t 
54
ˉξt . 0, ξ
t . 0, .t = 1, · · · ,N 
对应的拉格朗日函数可以写成 
L(w, b, ˉ ξ, ξ, ˉ λ,λ, ˉα,α) 
= ∥w∥2 
2 
+ c 
N Σt=1
(ˉξt + ξ
t
) . 
N Σt=1 
ˉαt ˉξt . 
N Σt=1 
αtξ
t 
+ 
N Σt=1 
ˉλ
t[yt . wTxt . b . . . ˉξt] + 
N Σt=1 
λt[wTxt + b . yt . . . ξ
t
] 
式中：ˉ λ,λ, ˉα,α . 0 为拉格朗日乘子。 
对上述拉格朗日函数关于 w、b、 ˉ ξ、ξ 求导置零，可得 
w = 
N Σt=1
(ˉλ
t . λt)xt 
0 = 
N Σt=1
(ˉλ
t . λt) 
c = ˉλ
t + ˉαt 
c = λt + αt 
(3.17) 
将上式代入拉格朗日函数，得到如下对偶优化问题： 
max 
ˉ λ,λ 
N Σt=1 
yt[ˉλ
t . λt] . .(ˉλ
t + λt) 
. 
1
2 
N,N Σ t=1,k=1
(ˉλt . λt)(ˉλ
k . λk)xTt
xk 
s.t. 
N Σt=1
(ˉλ
t . λt) = 0 
0 . ˉλ
t, λt . c, .t = 1, · · · ,N 
(3.18) 
通过求解上述对偶优化问题得到 ˉλ
t、λt 的最优值，代入式 (3.17) 进一步得到 w 的最 
优解。接下来讨论如何获偏置 b 的最优解。 
根据优化理论的 KKT 松弛互补条件可以得到 
ˉλ
t[yt . wTxt . b . . . ˉξt] = 0 
λt[wTxt + b . yt . . . ξ
t
] = 0 
55
(c . ˉλ
t)ˉξt = 0, (c . λt)ξ
t 
= 0 
c = ˉλ
t + ˉαt 
c = λt + αt 
若 0 < ˉλ
t < c，则有 ˉξt = 0。因此，最优偏置可以从上述第一个等式计算得到 
b = yt + . . w.Txt (3.19) 
最终得到支持向量回归模型：yt = w.Txt + b.。 
算法 3.3（支持向量回归学习算法） 
输入：训练数据集合 {xt, yt}N t=1，回归容许偏差 .。 
（1）选择惩罚参数 c，构造并求解对偶优化问题式 (3.18)，得到最优解 {ˉλ
.t
, λ.t 
}N t=1。 
（2）通过式 (3.17) 计算权重向量 w.，确定 0 < ˉλ
.t
< c 对应的样本为支持向量，并通过 
式 (3.19) 得到最优偏置 b.。 
输出：支持向量回归模型 yt = w.Txt + b.。 
3.3 核方法与正则化 
不同于线性回归，非线性映射通常具有比较复杂的几何特征，其通常记成 
y = f(x) 
为了能够便于处理，通常需要寻找 f(·) 函数的参数化形式，使得该参数化回归函数具 
有灵活表示形式，而且能够覆盖所有合理的非线性行为。接下来讨论如何采用基函数或者 
核函数来实现非线性函数的参数化表示。 
3.3.1 广义线性模型 
给定样本 (x, y)，广义线性估计可以表示成 
.y = g(x,α) = 
K Σk=1 
αk.k(x) (3.20) 
式中：.k(·) 为预先选择的基函数。 
通常，基函数的选择有不同的形式，它们赋予了非线性函数研究的统一框架。 
若采用泰勒展开来获得非线性函数的近似线性化表示，则其对应的基函数为 
.k(x) = xk := { d Πi=1 
xβi 
i | 
d Σi=1 
βi = k, βi . 0} 
56
这类基函数也称为多项式基函数。多项式或者泰勒展开通常由 Weierstrass 定理来保证其 
拟合精度：任何定义在有界闭区间上的连续函数，总能够找到多项式展开使得其误差处处 
（一致）小于某一固定值。上述多项式展开有时也称为 Volterra 展开。 
常见的基函数包括多尺度基函数 .k(x)，具有如下特征： 
（1）所有的基函数 .k(x) 均由一个母函数生成，该母函数表示为 κ(·) : R → R； 
（2）基函数 .k(x) 可以表示成
.k(x) = κ[βk(x . γk)]. 
式中：βk 为尺度膨胀参数；γk 为平移参数。 
常见的母函数包括傅里叶级数、高斯钟函数、分段定常函数和 Sigmoid 函数。 
采用多尺度基函数，非线性映射函数 f(x) 可以近似表示成 
f(x) = 
K Σk=1 
αkκ[βk(x . γk)] (3.21) 
值得注意的是，单变量的基函数可以分为局部基函数和全局基函数。局部基函数是指 
函数值在局部发生剧烈变化，如高斯钟、分段定常和 Sigmoid 函数。全局基函数是指函数 
值对定义域上的所有值均会产生较大变化，如傅里叶变换和 Volterra 展开。 
1. 有限维空间的线性可分容量 
广义线性拟合能够解决复杂的非线性拟合问题，同时也能够解决低维空间不可分的分 
类问题。比如二维空间中的四点 {(0, 0), (0, 1), (1, 0), (1, 1)}，若映射函数为异或运算，则 
(0, 0) 和 (1, 1) 为一类，而 (0, 1) 和 (1, 0) 为另一类。显然，这两类数据不能简单地由一条 
直线分割开来。低维空间中的不可分问题通常用以下方法来解决：先通过非线性方法将回 
归向量变换到高维空间，再进行线性分类。上述方法的合理性用模式可分性 Cover 定理来 
说明：“假设样本空间不是稠密分布的，将复杂的模式分类问题非线性地投影到高维空间， 
比投影到低维空间更容易线性可分。” 
考虑 l 维空间中的 N 个点，若任意 l + 1 个点不在 (l . 1) 维超平面上时，则这些 
点具有良态分布。通常，具有良态分布的 3 个样本点不会出现在二维平面上的同一条直 
线上。 
定理 3.1（Function Counting 定理） 若采用 l . 1 维的超平面对具有良态分布的 N 个 l 
维样本进行二分类，其分类结果数 P(N, l) 可以表示成 
P(N, l) =..
...
.. 
2 
l Σi=0 ( N . 1 
i ), N > l + 1 
2N, N . l + 1 
式中 
( N . 1 
i )= 
(N . 1)! 
(N . 1 . i)!i! 
57
考虑到 N 个样本所有可能的二分类组合数有 2N 种，而且当 N . l+1 时有 P(N, l) = 
2N。因此，N 个 l 维样本可线性分类的概率为 
PlN
= P(N, l) 
2N =..
...
.. 
1 
2N.1 
l Σi=0 ( N . 1 
i ), N > l + 1 
1, N . l + 1 
通过对 Function Counting 定理的分析得到结论：在给定样本数量 N 的情况下，若 
式 (3.21) 中基函数的数量 K 越大，则线性可分的概率越大。因此，使用非线性函数将低 
维回归向量投影到高维空间行进线性分类的方法具有基本理论支撑。 
2. 核函数 
当 d 维回归向量通过 .(x) 转换到很高维新特征向量时，其对应的拟合计算量就会增 
加，从而导致维数灾难。基于新特征向量 .(x)，接下来将考虑如何设计支持向量机。 
类似于标准支持向量机的推导，新特征向量对应的最优权重 w 可以表示成 
w. = 
N Σt=1 
λtyt.(xt) 
在新特征空间中，对新样本 xt+1 的分类可以表示成 
yt+1 = sgn( N Σt=1 
λtyt.T(xt).(xt+1) + b.) 
从上述分类器可以看出，虽然 .(x) 可能维度很高而且难以表示，但是分类器中与 .(x) 相 
关的项 .T(xt).(xt+1) 是一个标量。因此，若知道 .T(x).(z) 的表达式，特征空间的分类 
器就能够快速计算。在这里，κ(x, z) = .T(x).(z) 称为内积核函数。 
定理 3.2 对称函数 κ(x, z)=κ(z, x) 为正定核函数的充分必要条件为任意数据集 {x1, · · · , 
xm} 所对应的如下核矩阵总是半正定的： 
K =
....... 
κ(x1, x1) κ(x1, x2) · · · κ(x1, xm) 
κ(x2, x1) κ(x2, x2) · · · κ(x2, xm) 
... 
...
... ... 
κ(xm, x1) κ(xm, x2) · · · κ(xm, xm)
....... 
上述定理表明，若核函数所对应的核矩阵是半正定的，它就能作为核函数使用。反之， 
对于任意一个半正定核矩阵，总能找到一个与之对应的特征映射函数 .(·)。 
采用核函数能够避免对高维特征向量的直接计算，然而核函数的选择对分类器的性能 
至关重要。在不知道特征映射函数的情况下，并不知道什么样的核函数是合适的。常用的 
核函数有如下几类： 
58
高斯核： 
κ(x, z) = exp(.∥x . z∥2 
2σ2 ) 
式中：σ 为参数。 
线性核： 
κ(x, z) = (xTz)r 
式中：r 为参数。 
多项式核： 
κ(x, z) = (xTz + c)r 
式中：r 为参数。 
拉普拉斯核： 
κ(x, z) = exp(.t∥x . z∥) 
式中：t 为参数。 
Spline 核： 
κ(x, z) = B2p+1(∥x . z∥2) 
式中：Bn 样条曲线由 n + 1 个单位区间函数 [.1/2, 1/2] 卷积得到。 
Sigmoid 核： 
κ(x, z) = tanh(βxTz + θ), β > 0, θ < 0 
基于上述几种基本核函数，通过如下一系列组合操作可以得到新的核函数： 
（1）线性组合 α1κ1(x, z) + α2κ2(x, z), .α1, α2 > 0 是核函数； 
（2）直积组合 κ1(x, z)κ2(x, z) 是核函数； 
（3）对于任意函数 g(x) : Rd → R，g(x)g(z) 和 g(x)κ(x, z)g(z) 是核函数； 
（4）指数和多项式组合：exp[κ(x, z)] 和 [κ(x, z)]r 是核函数。 
3. 表示定理 
表示定理在实际应用中具有重要作用：通过有限训练样本能够对经验损失函数进行快 
速优化，即使待估计函数具有很高维度。 
定理 3.3（表示定理） 令 Ω : [0,+∞) → R 为任意严格单调增函数，L : R2 → R 为任意非 
负损失函数，H 为再生核希尔伯特空间。下列最小正则化问题 
min 
f∈H 
N Σt=1 
L[yt, f(xt)] + λΩ(∥f∥2) (3.22) 
59
的最优解具有如下表示形式： 
f(x) = 
N Σt=1 
θtκ(x, xt) 
上述表示定理对损失函数没有限制，对正则化项仅要求单调递增，甚至不要求其为凸 
函数。这意味着对于一般损失函数和正则化项，最优解都能表示为核函数的线性组合，这 
体现了核函数在实际应用中的重要性。 
例 3.3（核表示的最小平方解） 
令 (xi, yi)(i = 1, 2, · · · ,N) 为训练样本。试设计最小平方线性分类器，即 
min 
g∈H 
N Σi=1
(yi . g(xi))2 
解：由表示定理能够得到 
g(x) = 
N Σj=1 
ajκ(x, xj) 
因此，函数 g 的求解转换成参数 a 的求解。令 
J(a) = 
N Σi=1 (yi . 
N Σj=1 
ajκ(xi, xj))2 
= (y .Ka)T(y .Ka) 
则最优 a 可通过求解如下最小二乘问题获得： 
a. = arg min 
a 
J(a) 
通过对 a 求导置零得到 
a. = K.1y 
从而最优函数 g(x) 可以写成 
g(x) = aTp(x) = yTK.1p(x) 
式中 
p(x) = [κ(x, x1), · · · , κ(x, xN)]T 
60
3.3.2 核支持向量机 
核方法的思想可以拓展标准支持向量机并用于解决非线性分类问题。类似于标准支持 
向量机的求解步骤，首先将对偶问题式 (3.10) 改写成 
max 
λ . 
1
2 
N,N Σ t=1,k=1 
λtλkytykκ(xt, xk) + 
N Σt=1 
λt 
s.t. 
N Σt=1 
λtyt = 0 
λt . 0 
式中：κ(xt, xk) 为选择的核函数。 
如式 (3.8) 所示，标准支持向量机的权重向量依赖特征 xt。若采用转换后的高维特征 
向量 .(xt)，则权重向量具有很高的维度，很难进行计算或存储。为此，在核支持向量机 
处理过程中，往往不显式表示最优权重向量，而是给出如下形式的分类器： 
y = sgn( N Σt=1 
λtytκ(xt, x) + b) 
类似于式 (3.12)，上式中偏置 b 的值由支持向量来获得。若 λt0 .= 0，则 xt0 或者 .(xt0) 为 
支持向量。为了避免对高维特征向量 .(xt0) 直接处理，最优偏置通过如下核函数计算得到： 
b. = yt0 . 
N Σt=1 
λtytκ(xt, xt0) 
由于核函数的强大能力，可以构造如下核函数来解决异或逻辑函数线性不可分的难题： 
κ(x, z) = (1 + xTz)2 = .T(x).(z) 
该核函数所对应的特征变换函数为 
.(x) = [1,√2x1,√2x2,√2x1x2, x21
, x22
]T 
3.3.3 正则化理论 
式 (3.22) 给出一个正则化优化问题的广义表示形式，其中包含误差项和正则化项。给 
定样本集合 {xt, yt}N t=1，岭回归优化问题可以写成 
min 
w 
1
2 
N Σt=1 
∥yt . wTxt∥2 + 
λ
2 ∥w∥2 (3.23) 
61