动机

• 之前【三步走】的学习方法

  • 估计问题特性（如分布）
  • 做出模型假设
    • LSE，Decision Tree，MAP，MLE，Naive Bayes ，…
  • 找到最优的参数

• 有没有一种学习方法**不遵循【模型假设+参数估计】

• 人们通过记忆和行动来推理学习

• 思考即回忆、进行类比Thinking is reminding,making analogies

• One takes the behavior of one’s company[近朱者赤，近墨者黑]

基本概念

• 参数化(Parametric) vs.非参数化(Non-parametric)

  • 参数化：
    • 设定一个特定的函数形式
    • 优点：简单，容易估计和解释
    • 可能存在很大的偏置（bias）：实际的数据分布可能不遵循假设的分布

• 非参数化：

  • 分布或密度的估计是数据驱动的(data-driven)
  • 需要事先对函数形式作的估计相对更少

• Instance-Based Learning (IBL):基于实例的学习
  or Instance Based Methods (IBM):基于实例的方法

• Memory-Based Learning :基于记忆的学习

• Case-Based Learning :基于样例的学习

• Similarity-Based Learning :基于相似度的学习

• Case-Based Reasoning :基于样例的推理

• Memory-Based Reasoning :基于记忆的推理

• Similarity-Based Reasoning :基于相似度的推理

基于实例的学习

• 无需构建模型一一仅存储所有训练样例
• 直到有新样例需要分类才开始进行处理
  
  如上图，2个发了信用卡，3个没发，只需要存下来，新来了一个人要不要发新用卡，看他和哪些类似，发送和发信用卡的类似，那就给他发信用卡。

基于实例的概念表示

• 一个概念$c_i$可以表示为:
  • 样例的集合 c i = { e i 1 , e i 2 , . . . } c_i = \{e_{i1}, e_{i2},...\} ci​={ei1​,ei2​,...},
  • 一个相似度估计函数$f$,以及
  • —个阈值0
• 一个实例’a’属于概念$c_i$,当
  • 'a’和c_i的某些e_j相似，并且
  • $f(e_j,a)>\theta$。

1. 最近邻

• $相似度\leftarrow \to 距离$
  一般用距离来描述相似度，成反比关系，距离越大，相似度越小
  

最近邻的例子

信用评分
分类：好/坏(good/poor)
特征：

• L = 延迟还款的次数/年
• R =收入/花销

name	L	R	G/P
A	0	1.2	G
B	25	0.4	P
C	5	0.7	G
D	20	0.8	P
E	30	0.85	P
F	11	1.2	G
G	7	1.15	G
H	15	0.8	P

如上在二维坐标系中的表示，因为在欧氏空间中表示的，那用欧氏距离表示，

name	L	R	G/P
I	6	1.15	?
J	22	0.45	?
K	15	1.2	?

距离度量：

• 缩放的欧氏距离 $\sqrt{(L_1-L_2{)}^2+(10R_1-10R_2{)}^2}$

理论结果

• 无限多训练样本下1-NN的错误率界限：
  $$Err(Bytes)\le Err(1-NN)\le Err(Bytes)\left(2-\frac{K}{K-1}Err(Bayes)\right)$$
• 证明很长（参照Duda et al, 2000）
• 因此1-NN的错误率不大于Bayes方法错误率的2倍

最近邻（1- NN）:解释

• Voronoi Diagram

• Voronoi tessellation

• 也称为 Dirichlet tessellation

• Voronoi decomposition

• 对于任意欧氏空间的离散点集合S,以及几乎所有的点x, S中一定有一个和x最接近的点

  • -没有说“所有的点”是因为有些点可能和两个或多个点距离相等（在边界上）
    -如果是边界上的点，则可以随机、按概率算或其它

问题

• 最近邻的点是噪音怎么办？
• 解决方法
  • 用不止一个邻居
  • 在邻居中进行投票 $\to$k-近邻（KNN)
    如上面的例子，如果用1-近邻，则会是黑色，如上，用3近邻，因此是绿色。

K-近邻(KNN)

KNN:示例(3-NN)

顾客	年龄	收入(K)	卡片数	结果	距David距离
John	35	35	3	No	$\sqrt{(35-27{)}^2+(35-50{)}^2+(3-2{)}^2}=15.16$
Mary	22	50	2	Yes	$\sqrt{(22-37{)}^2+(50-50{)}^2+(2-2{)}^2}=15$
Hannah	63	200	1	No	$\sqrt{(63-37{)}^2+(200-50{)}^2+(1-2{)}^2}=152.23$
Tom	59	170	1	No	$\sqrt{(59-37{)}^2+(170-50{)}^2+(1-2{)}^2}=122$
Nellie	25	40	4	Yes	$\sqrt{(25-37{)}^2+(40-50{)}^2+(4-2{)}^2}=15.74$
David	37	50	2	Yes	-

新来了一个David顾客，求他的结果

• 计算David与其它顾客的距离，找到最小的3个距离，这三个投票得是YES

KNN讨论1 ：距离度量

• Minkowski或$L_{\lambda }$度量: $$d(i,j)={\left(\sum _{k=1}^p|x_k(i)-x_k(j){|}^{\lambda }\right)}^{\frac{1}{\lambda }}$$
  k: 指的是维度，i和j指不同的数据点
  计算在相同维度上不同点差值的绝对值的$\lambda$次方，然后不同维度求和再开$\lambda$次方
  当$\lambda$次方取不同值时，$L_{\lambda }$距离表示的就是如下图形
  

• 欧几里得距离$(\lambda =2)$ $$d_{ij}=\sqrt{\sum _{k=1}^p(x_{ik}-x_{jk}{)}^2}$$

• 曼哈顿距离 Manhattan Distance
  城市街区距离City block Dis.
  出租车距离 Taxi Distance
  或L₁度量($\lambda =1$): $$d(i,j)=\sum _{k=1}^p|x_k(i)-x_k(j)|$$
  在曼哈顿，街区都类似如下，不能走斜线，
  

  • 切比雪夫距离(Chebyshev Distance)
    棋盘距离(Chessboard Dis.)
    $L_{\infty }$
    $$d(i,j)=\underset{k}{\max }|x_k(i)-x_k(j)|$$
    国际象棋可以走斜线，因此两点之间取决于x差值和y差值的最大值

• 加权欧氏距离
  Mean Censored Euclidean
  Weighted Euclidean Distance
  $$\sqrt{\sum _k(x_{jk}-x_{jk}{)}^2/n}$$
  欧氏距离每多一个维度，距离就更大一些，除以n后，维度的影响就降低了

• Bray-Curtis Dist $$\sum _k|x_{jk}-x_{jk}|/\sum _k(x_{jk}-x_{jk})$$
  两个数据量点的差值和除以两个数据点的和的和
  一般用于生物学上描述多样性用的比较多

• 堪培拉距离C anberra Dist.$$\frac{{\sum }_k|x_{jk}-x_{jk}|/(x_{jk}-x_{jk})}{k}$$
  就是在Bray- Curtis Dist基础上做一些缩放

KNN 讨论2：属性

• 邻居间的距离可能被某些取值特别大的属性所支配
  • e.g.收入 $Dis(John,Rachel)=\sqrt{(35-45{)}^2+(95000-215000{)}^2+(3-2{)}^2}$
    -对特征进行**归一化(Normalization)**是非常重要的(e.g.,把数值归一化到[0-1])
  • Log, Min-Max, Sum,Max…
  • log只是对数据进行了放缩，没有归一化到[0-1],有个优点：数据会变得相对均匀
  • Min-Max：$\frac{Score-Min}{Max-Min}$
  • Sum: $\frac{Score}{\sum Score}$
  • Max：$\frac{Score}{Max}$

KNN:属性归一化

顾客	年龄	收入(K)	卡片数	结果
John	35/63=0.55	35/200=0.175	3/4=0.75	No
Mary	22/63=0.34	50/200=0.25	2/4=0.5	Yes
Hannah	63/63=1	200/200=1	1/4=0.25	No
Tom	59/63=0.93	170/200=0.85	1/4=0.25	No
Nellie	25/63=0.39	40/200=0.2	4/4=1	Yes
David	37/63=0.58	50/200=0.25	2/4=0.5	Yes

KNN:属性加权

• 一个样例的分类是基于所有属性的
  • 与属性的相关性无关——无关的属性也会被使用进来
• 根据每个属性的相关性进行加权 $$d_{WE}(i,j)={\left(\sum _{k=1}^p{w}_k(x_k(i)-x_k(j){)}^2\right)}^{\frac{1}{2}}$$
• 在距离空间对维度进行缩放
  • 如$\sqrt{(L_1-L_2{)}^2+(10R_1-10R_2{)}^2}$
  • w_k = 0 $\to$消除对应维度(特征选择)
• 一个可能的加权方法：
  使用互信息(mutual information)/(属性,类别）
  $I(X,Y)=H(X)+H(Y)-H(X,Y)$ H:熵(entropy)
  Y是类别，最后的标签
  $H(X,Y)=-\sum p(x,y)logp(x,y)$ 联合熵 (joint entropy)(利用熵的公式$H(y)=-\sum p(y)logp(y)$)
  x和y接近关系不同，互信息不同，利用互信息来代表这个维度的重要性w_k

KNN讨论3:连续取值目标函数

• 离散输出-投票
• 连续取值目标函数
  • k个近邻训练样例的均值
    $$红色：实例的真实值蓝色：估计值$$
    
    3近邻相比1近邻，比较平滑，阶梯没那么多；k越大，相对越平滑，但也可能损失掉细节，

KNN讨论4 : k的选择

• 多数情况下k=3
• 取决于训练样例的数目
  • 更大的k不一定带来更好的效果
• 交叉验证
  • Leave-one-out (Throw-one-out, Hold-one-out)
    • 每次：拿一个样例作为测试，所有其他的作为训练样例
      KNN本来就是看样例点和其它点的距离，少算一个，拿它当测试，因此KNN天然适合用leave-one-out方法来做；如果n个样例，那就可以做n次，求评价指标时就可以求均值，看在验证集上k是多少最好
• KNN是稳定的
  • 样例中小的混乱不会对结果有非常大的影响
    k越大，相对越稳定，但是会丢掉好多细节

KNN讨论5：打破平局

• 如果k=3并且每个近邻都属于不同的类 ?（一般都不等于类别数，因为可能每个恰好属于不同类，而且一般不等于偶数，很容易出现对半情况）
  • P(W|X)=1/3
  • 或者找一个新的邻居(4^th)
  • 或者取最近的邻居所属类
  • 或者随机选一个
  • 或者 …

之后会讨论一个更好的解决方案（距离加权）

KNN 讨论 6: 关于效率

• KNN算法把所有的计算放在新实例来到时，实时计算开销大
• 加速对最近邻居的选择
  • 先检验临近的点
  • 忽略比目前找到最近的点更远的点
• 通过 KD-tree 来实现：(k dimension tree)
  • KD-tree: k 维度的树 (数据点的维度是 k)
  • 基于树的数据结构
  • 递归地将点划分到和坐标轴平行的方形区域内

KD-Tree: ( 1) 构建

• 从一系列数据点出发
  

Pt	X	Y
1	0.00	0.00
2	1.00	4.31
3	0.13	2.85
…	…	…

• • 我们可以选择一个维度 X 和分界值 V 将数据点分为两组： X > V 和 X <= V
    
• 接下来分别考虑每个组，并再次分割(可以沿相同或不同的维度)
  
• 持续分割每个集合中的数据点， 从而构建一个树形结构
  每个叶节点表示为一系列数据点的列表（分割时是将数据点均匀分割，使分割后两个区域的数据点大致相同）
  

在每个节点维护一个额外信息：这个节点下所有数据点的 (紧) 边界
紧边界，一个只包含数据点的矩形区域

用启发式的方法去决定如何分割

• 沿哪个维度分割？
  • 范围最宽的维度（范围最大的，即数据点饭不最散的）
• 分割的值怎么取？
  • 数据点在分割维度的中位数
  • 为什么是「中位数」而不是「均值」？（尽量让每个区域数据点数目相同）
• 什么时候停止分割？
  • 当剩余的数据点少于 m，或者
  • 区域的宽度达到最小值
    （数据点也不用严格小于m，小于m只是一个权衡）

KD-Tree: ( 2) 查询

• 遍历树，来查找所查询数据点的最近邻居
  
• 先检验临近的点 ：关注距离所查询数据点最近的树的分支
  节点分支是由原则的，如大于根节点（0.5)的在右子树，而查询点如果大于0.5,则可以缩小范围–右子树，
  
  到了这一步，如图看y，又可以确定在某一子树上，
  
• 达到一个叶节点后 ：计算节点中每个数据点距离目标点的距离
  
  

接着回溯检验我们访问过的每个树节点的另一个分支

• 每次我们找到一个最近的点，就更新距离的上界
  如发现距离另外一个分支的一些点更近，此时更新查询点的距离的上界
  
• 利用这个最近距离以及每个树节点下数据的边界信息，（如果新找到的边界已经比目前找到的最近邻更远，则不可能存在更近的点。因此就不计算这个新分支上的点了）
  我们可以对一部分不可能包含最近邻居的分支进行剪枝
  
  
  
  因此我们只计算了上述的点（记录边界是为了剪枝减小计算量的）

KNN 总览：优点与缺点

优点

• 概念上很简单，但可以处理复杂的问题(以及复杂的目标函数)
  • e.g. 图片分类
• 通过对k-近邻的平均， 对噪声数据更鲁棒
• 容易理解 ：预测结果可解释(最近邻居)
• 训练样例中呈现的信息不会丢失
  • 因为样例本身被**显式(explictly)**地存储下来了
• 实现简单、稳定、没有参数(除了 k)
• 方便进行 leave-one-out 测试

缺点

• 内存开销
  • 需要大量的空间存储所有样例
  • 通常来说，需要存储任意两个点之间的距离 O(n²) ； K-DTrees O(nlogn)
• CPU 开销
  • 分类新样本需要更多的时间(因此多用在离线场景)
• 很难确定一个合适的距离函数
  • 特别是当样本是由复杂的符号表示时(距离需要自己定义，影响到相似度的计算，也就是knn的计算）
• 不相关的特征 对距离的度量有负面的影响
  • 基于先验证知识或统计给予一定的权重，引用了新参数

下一个问题

• 回忆：用多个邻居使得对噪声数据鲁棒
  这些邻居的贡献是一样的吗？
• 解决方案
  • 对数据加权
  • 更接近所查询数据点的邻居赋予更大的权$\to$距离加权近邻

距离加权 KNN (Distance-weighted KNN)

距离加权 KNN

• 一种加权函数
  • w_i = K(d(x_i, x_q))
    K是Kernel function(kernel方向，在后面的向量机里也会提到）
  • d(x_i, x_q) ：查询数据点与 x_i 之间的关系
  • K( ·) ：决定每个数据点权重的核函数（距离越大，权重越低）
• 输出: 加权平均： $predict=\sum w_i{y}_i/\sum w_i$ (使得加权平均式没有经过太大的放缩)
• 核函数 K(d(x_i, x_q))
  • 1/d², $e^{-d}$, 1/(1+d), … 应该和距离 d 成反比

回顾

距离加权 NN
加d₀，平滑了很多，smoothing flater，这个还是很有用的，它是一个常数

下面的公式用了正态分布的高斯核函数，几乎接近完美

基于实例/记忆的学习器： 4 个要素

1. 一种距离度量
2. 使用多少个邻居？
3. 一个加权函数(可选)
4. 如何使用已知的邻居节点？

1-NN

基于记忆的学习器：4 个要素

1. 一种距离度量 欧式距离
2. 使用多少个邻居？ 一个
3. 一个加权函数(加权) 无
4. 如何使用已知的邻居节点？ 和邻居节点相同

K-NN

基于记忆的学习器：4 个要素

1. 一种距离度量 欧式距离
2. 使用多少个邻居？ K 个
3. 一个加权函数(加权) 无
4. 如何使用已知的邻居节点？ K 个邻居节点投票（或平均Mean）

距离加权 KNN

基于记忆的学习器： 4 个要素

1. 一种距离度量 缩放的欧式距离
2. 使用多少个邻居？ 所有的，或K 个
3. 一个加权函数(可选)
   $w_i=exp(-D(x_i,query{)}^2/K_w^2)$
   K_w ：核宽度。非常重要（是个常量，需手动指定）
4. 如何使用已知的邻居节点？每个输出的加权平均 $predict=\sum w_i{y}_i/\sum w_i$

扩展：局部加权回归 (Locally weighted regression)

• 回归：对实数值目标函数做估计/预测
• 局部： 因为函数的估计是基于与所查询数据点相近的数据
• 加权：每个数据点的贡献由它们与所查询数据点的距离决定

局部加权回归 (例子)

上面例子中局部加权回归用4个线性直线（有两个几乎重合）很好的拟合了数据，和简单回归效果好很多，如果分的足够小的话，每一个小块一定是线性的

局部加权回归

基于记忆的学习器：4 个要素

1. 一种距离度量 缩放的欧式距离
2. 使用多少个邻居？ 所有的，或K 个
3. 一个加权函数(可选)
   e.g. $w_i=exp(-D(x_i,query{)}^2/K_w^2)$
   K_w ：核宽度。非常重要
4. 如何使用已知的邻居节点？
   首先构建一个局部的线性模型。拟合 $\beta$ 最小化局部的加权平方误差和: $$\underline{\beta }=\underset{\beta }{\mathrm{argmin}}\sum _{k=1}^N{w}_k^2(y_k-{\beta }^T{x}_k{)}^2$$
   那么 $y_{predict}={\underline{\beta }}^T{x}_{query}$

真实测试样例下 不同基于实例的算法表现举例

线性回归

第一个： 不能使用线性假设
第三个：看起来就像是噪声数据的影响

• 连接所有点
  

1- 近邻

甚至比连接所有点还差，比如第二个没有连接所有点平滑

K -近邻（k=9）

以上三个图都是在开始和结束也损失掉很大的细节

距离加权回归（核回归）

K_w=x轴宽度的1/32，就是将数据分成32份，每1/32的数据对当前的影响较大一些
最右的图，1/16是调参调出来的，但是和简单线性回归比，不知道是不是发生过拟合（对噪声拟合了一些），效果不好确定

选择一个合适的 K_w 非常重要，不仅是对核回归，对所有局部加权学习器都很重要（包括distance weighted 距离加权回归）

局部加权回归

不一定局部加权回归是最好的，因为参数量(${\beta }^T$)很大，因此需要数据量很大才适合

懒惰学习与贪婪学习 Lazy learner and Eager Learner

贪婪学习与主动学习(active learner)是有区别的,(主动学习是：先训练一部分，然后问teacher，这个数据的label是什么，然后把label加到训练了，然后学了一段时间后，再问，而且每次问都是挑一些对下一步有用的）

不同的学习方法

• 贪婪学习
  比如： 先建一个模型，从过去的数据集里得到一个模型，这个模型是：总结中经验，产生任何行动都是有老鼠。现在来了一个点，就说看到一只老鼠。
  之前说的：线性回归、决策树、贝叶斯的方法都是eager leaner
  
• 懒惰学习 (例如基于实例的学习)
  lazy leaner ：比如：有一对样例，啥都不干 只保存，来了一个新的例子，它和电脑很像，就认为它是电脑
  

懒惰学习vs. 贪婪学习(lazy learner vs eager leaner)

懒惰

• 懒惰 ：等待查询再泛化(generalization,一般化)

  • 训练时间 ：短
  • 测试时间 ：很长

• 懒惰学习器

  • 可以得到局部估计(如KNN）

贪婪

• 贪婪 ：查询之前就泛化（y=f(x))

  • 训练时间 ：长
  • 测试时间：短

• 贪婪学习器

  • 对于每个查询使用相同的模型
  • 倾向于给出全局估计（比如决策树的搜索过程得到的是局部估计，梯度下降也是局部最优）

如果它们共享相同的假设空间，懒惰学习可以表示更复杂的函数
( e.g. H=线性函数)

基于实例的学 习总结

• 基本概念与最近邻方法
• K近邻方法
  • 基本算法
  • 讨论：更多距离度量；属性：归一化、加权；连续取值目标函数； k 的选择；打破平局；关于效率(K-Dtree的构建与查询)
• 距离加权的KNN
• 基于实例的学习器的四要素
• 扩展：局部加权回归
• 真实测试样例下的算法表现举例
• 懒惰学习与贪婪学习