f k x x; kl , 2
l 1
10


对类别绿，k=1；对类别红，k=2 T ~ N 1,0 ,I 对类别绿，10个均值从正态分布产生： kl T 对类别红，10个均值从正态分布产生：kl ~ N 0,1 , I 方差 2 1 5
f x 0 1 x


其中 0为弹簧的初始长度， 1为物质的弹性系数，由材料 的性质所决定 对给定的弹簧，我们不知道其弹性系数，但我们可以通过 测量不同外力下的形变来估计弹性系数
函数逼近

但测量会有误差 ，这样考虑统计模型的观点： Y f X 其中E 0且为随机误差，与X独立 当有足够多的数据时，最小二乘能得到精确预测，并且我 们能正确（偏差小）、精确（方差小）地预测任意外力下 的形变 如果科学知识告诉我们应该应该选择非线性模型，如 sigmoid模型，我们仍然可以用最小二乘法求解，只是计算 可能稍复杂

在目标点附近很难收集到k个邻居：维数灾难 (curse of
dimensionality)
维数灾难

邻域不再是“局部的” ：考虑输入在p维单位超立方体上的 均匀分布，选取目标点的超立方体的邻居，覆盖比例为r， 则边长为： l e p r r1 p

当维数p=10时，边长为 e10 0.01 0.63, e10 0.1 0.80

结果为最大后验估计（MAP），亦称贝叶斯分类器
贝叶斯最优分类器的结果
贝叶斯分类器

ˆ x arg max P g | X x ? 为什么不用贝叶斯分类器 G gG 因为通常我们不知道 P g | X x

在上例中我们是已知数据产生的过程

每个类的概率密度为10个高斯的均匀混合


贝叶斯分类器

knn是贝叶斯分类器的直观实现


不知道 P g | X x ，在x附近的小邻域类别为g的数目
用频数近似概率

在点上取条件放宽为在目标点的邻域内取条件

如果取
Gg 1 Y 0 otherwise
P G g | X x E Y | X x





| X x
对每个输入x，使风险函数最小 k
gG j 1
ˆ x arg min L G ,g P G | X x arg min G j j
gG gG gG
j:G j g
P G
j
arg min 1 P g | X x arg max P g | X x

可能是一个封闭的解析解 也可能要通过数值计算的方法迭代计算得到
函数逼近

但可能我们选定的函数族中的任何函数都不能很 好表示 f

0.14
0.12 0.0
0.185
0.175 0.185
k的选择：偏差—方差折中

较小的k：预测更灵活，但太灵活可能会导致过拟合， 从而估计方差更大 较大的k：预测更稳定，但可能不够灵活，不灵活通常 与偏差/不准确有关
当k较小时，训练误差较小，但测试误差一般较大 当k较大时，训练误差较大，但测试误差一般较小
维数灾难
e
e p r r1 p
r
函数逼近

考虑连续数据的回归问题：给定X，Y的最佳预测为 回归函数：
f x E Y | X x

为了预测，我们需要知道 f ，但通常我们并不知道 f

有时科学知识（如物理化学定律）告诉我们f 的形式 如胡克定律指出：在弹性限度内，弹簧的的形变 f 跟引起 形变的外力x，即
1 T ˆ X X XT y 并最小化训练样本上的平均损失：

ˆ 收敛于 随着样本数目的增多， E X X E XY
T 1

但模型受到线性假设的限制
knn vs. 线性回归

通过用样本均值来逼近数学期望，knn和线性回归最 终都得到近似条件期望。但二者对模型的假设截然 不同：

则贝叶斯分类器与回归函数之间的关系为：
knn vs. 线性回归

当 n, k 且 k n 0时，knn的估计 ˆ x E Y | X x f Y|X
即该估计是一致的。


但通常没有那么多样本
T f x f x X 线性回归假设 的结构是线性的：
i 1 2

拟合 f
例：一个回归例子（续）
样本数据点
拟合得到的曲线
1阶多项式拟合
3阶多项式拟合
例：一个回归例子（续）
10阶多项式拟合
训练正确率和测试误差
一些术语

有监督学习：

给定包含输入特征 X i和对应响应 Yi的训练样本，学习Y与 X之间的关系 对新的输入x，预测其响应y

如果输出值Y的类型是连续值：回归
哲学思想

理解各种技术背后的基本思想，以知道如何和在 什么情况采用这些技术 先理解比较简单的方法，以便掌握更复杂的技术
正确评价方法的性能很重要，以便知道该方法在 什么情况下工作得好，在什么情况下工作得不好 [简单的方法通常和那些很华丽时髦的方法工作得 一样好！]


一个例子
IR2上从未知分布产生的200 点，其中类别G={绿，红} 各100个点 。 我们能建立一 个规则，预测将来的点的颜 色的规则吗？
在前面200个点上训练，在10,000个数据上测试的结果
统计决策理论

令 X IR p 表示一个实值的随机输入向量， Y IR 表示实值的随机输出变量
损失函数： L Y , f X


风险函数（损失函数的期望）：
R f E XY L Y , f X E X E Y | X
例：一个回归例子

例：

y f ( x ) 0.5 0.4sin(2 x ) 然后对每个数据加上高斯噪声， 0.05
目标：

f ( x, ) 0 1 x

n
M xM （RSS）
RSS ( ) f xi , yi

著名的支持向量机（support vector machine, SVM）与核平滑有 许多相同之处
维数灾难

似乎有了合理大的训练数据集，使用knn平均总能 逼近理论上的最佳条件期望


我们能找到接近任意x的相当大的观测值邻域，并对它 们取平均 这样就不必考虑线性会回归了

但在高维空间中，knn法将失败



经验告诉我们，当二元正态分布的相关系数为0.5时，意味着线性 关系仍能工作得很好 事实上，有时候人们既没有从理论上，也没有从经验上分析就直 接采用线性模型
函数逼近

更通用的做法是选择一个函数族，参数形式为
f x f x

其中为参数集合 可以用最小二乘法求解，也可以用更一般的极大 似然法来求解
第三部分：统计学习基础

有监督学习概述

[ESL] Chp2
[ESL] Chp3
[Wasserman] Chp13

回归分析



模型评估与选择

[ESL] Chp7/8
[ESL] Trevor Hastie, Robert Tibshirani, Jerome Friedman 著 “The Elements of Statistical Leanring”，范明，柴玉梅，昝红英译《统计学习基础—数据挖掘、 推理与预测》， 电子工业出版社，2004
比较两种最简单的预测方法

线性回归 k近邻法（k - nearest neighbors, knn）
线性回归

输入p维向量，扩展成p+1维： X 1, X 1 , , X p

向量均为列向量

类别G=绿时，Y=0；否则Y=1。
Y用X的线性函数来建模
ˆ XT ˆ ˆ f X X Y 0 j j

根据公司的业绩和经济学数据，预测今后6个月的股票价格 根据患者血液的红外光谱，估计糖尿病患者血液中葡萄糖的含 量

如果输出值Y为离散值：分类

根据数字图像，识别手写的邮政编码数据 根据邮件中单词和字符的比例，识别email是否为垃圾邮 件
目标
根据训练数据， 正确预测未见过的测试样本 理解哪些输入影响输出 怎样评价预测的质量

如果在观测x邻域中某一类明显占优势，则观测 样本也更可能属于该类。分类规则为邻域成员 的多数票 ˆ x0 0.5 红 if y ˆ G x0 ˆ x0 0.5 绿 if y
15-近邻分类：训练集上的错误率为12%
过拟合

knn比线性回归表现稍好 但我们应警惕过拟合(overfitting)问题

线性回归：假定 f x 可以用一个全局线性函数很好近似 knn：假定 f x 可以用一个局部常量函数很好近似

后者看上去更合理：可以逼近更多的函数类，但必 须为这种灵活性付出高昂代价
knn

很多现代的学习过程是knn的变种

核平滑：每个样本的权重不是0/1，而是随样本点到目标 点的距离平滑减至0
ˆ G 0 G ˆ,G L G 1 otherwise



风险函数为
ˆ E ˆ ˆ X R G E X E G| X L G , G G , X L G, G X