之前【三步走】的学习方法
有没有一种学习方法**不遵循【模型假设+参数估计】
人们通过记忆和行动来推理学习
思考即回忆、进行类比Thinking is reminding,making analogies
One takes the behavior of one’s company[近朱者赤,近墨者黑]

参数化(Parametric) vs.非参数化(Non-parametric)
非参数化:
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 :基于相似度的推理


信用评分
分类:好/坏(good/poor)
特征:
| 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 | ? |

距离度量:

Voronoi Diagram
Voronoi tessellation
也称为 Dirichlet tessellation
Voronoi decomposition
对于任意欧氏空间的离散点集合S,以及几乎所有的点x, S中一定有一个和x最接近的点

KNN:示例(3-NN)
| 顾客 | 年龄 | 收入(K) | 卡片数 | 结果 | 距David距离 |
|---|---|---|---|---|---|
| John | 35 | 35 | 3 | No | ( 35 − 27 ) 2 + ( 35 − 50 ) 2 + ( 3 − 2 ) 2 = 15.16 \sqrt{(35-27)^2+(35-50)^2+(3-2)^2}=15.16 (35−27)2+(35−50)2+(3−2)2=15.16 |
| Mary | 22 | 50 | 2 | Yes | ( 22 − 37 ) 2 + ( 50 − 50 ) 2 + ( 2 − 2 ) 2 = 15 \sqrt{(22-37)^2+(50-50)^2+(2-2)^2}=15 (22−37)2+(50−50)2+(2−2)2=15 |
| Hannah | 63 | 200 | 1 | No | ( 63 − 37 ) 2 + ( 200 − 50 ) 2 + ( 1 − 2 ) 2 = 152.23 \sqrt{(63-37)^2+(200-50)^2+(1-2)^2}=152.23 (63−37)2+(200−50)2+(1−2)2=152.23 |
| Tom | 59 | 170 | 1 | No | ( 59 − 37 ) 2 + ( 170 − 50 ) 2 + ( 1 − 2 ) 2 = 122 \sqrt{(59-37)^2+(170-50)^2+(1-2)^2}=122 (59−37)2+(170−50)2+(1−2)2=122 |
| Nellie | 25 | 40 | 4 | Yes | ( 25 − 37 ) 2 + ( 40 − 50 ) 2 + ( 4 − 2 ) 2 = 15.74 \sqrt{(25-37)^2+(40-50)^2+(4-2)^2}=15.74 (25−37)2+(40−50)2+(4−2)2=15.74 |
| David | 37 | 50 | 2 | Yes | - |
新来了一个David顾客,求他的结果
Minkowski或
L
λ
L_\lambda
Lλ度量:
d
(
i
,
j
)
=
(
∑
k
=
1
p
∣
x
k
(
i
)
−
x
k
(
j
)
∣
λ
)
1
λ
d(i,j)=\left(\sum_{k=1}^{p}|x_k(i)-x_k(j)|^\lambda\right)^{\frac{1}{\lambda}}
d(i,j)=(k=1∑p∣xk(i)−xk(j)∣λ)λ1
k: 指的是维度,i和j指不同的数据点
计算在相同维度上不同点差值的绝对值的
λ
\lambda
λ次方,然后不同维度求和再开
λ
\lambda
λ次方
当
λ
\lambda
λ次方取不同值时,
L
λ
L_\lambda
Lλ距离表示的就是如下图形

欧几里得距离 ( λ = 2 ) (\lambda=2) (λ=2) d i j = ∑ k = 1 p ( x i k − x j k ) 2 d_{ij}=\sqrt{\sum_{k=1}^{p}(x_{ik}-x_{jk})^2} dij=k=1∑p(xik−xjk)2
曼哈顿距离 Manhattan Distance
城市街区距离City block Dis.
出租车距离 Taxi Distance
或L1度量(
λ
=
1
\lambda=1
λ=1):
d
(
i
,
j
)
=
∑
k
=
1
p
∣
x
k
(
i
)
−
x
k
(
j
)
∣
d(i,j)=\sum_{k=1}^{p}|x_k(i)-x_k(j)|
d(i,j)=k=1∑p∣xk(i)−xk(j)∣
在曼哈顿,街区都类似如下,不能走斜线,


加权欧氏距离
Mean Censored Euclidean
Weighted Euclidean Distance
∑
k
(
x
j
k
−
x
j
k
)
2
/
n
\sqrt{\sum_k(x_{jk}-x_{jk})^2/n}
k∑(xjk−xjk)2/n
欧氏距离每多一个维度,距离就更大一些,除以n后,维度的影响就降低了
Bray-Curtis Dist
∑
k
∣
x
j
k
−
x
j
k
∣
/
∑
k
(
x
j
k
−
x
j
k
)
\sum_{k} |x_{jk}-x_{jk}|\bigg/\sum_{k} (x_{jk}-x_{jk})
k∑∣xjk−xjk∣/k∑(xjk−xjk)
两个数据量点的差值和除以两个数据点的和的和
一般用于生物学上描述多样性用的比较多
堪培拉距离C anberra Dist.
∑
k
∣
x
j
k
−
x
j
k
∣
/
(
x
j
k
−
x
j
k
)
k
\frac{\sum_{k} {|x_{jk}-x_{jk}|\big/(x_{jk}-x_{jk})}}{k}
k∑k∣xjk−xjk∣/(xjk−xjk)
就是在Bray- Curtis Dist基础上做一些缩放

| 顾客 | 年龄 | 收入(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 |


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

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




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

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





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






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

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


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

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

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

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

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

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


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

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

Kw=x轴宽度的1/32,就是将数据分成32份,每1/32的数据对当前的影响较大一些
最右的图,1/16是调参调出来的,但是和简单线性回归比,不知道是不是发生过拟合(对噪声拟合了一些),效果不好确定
选择一个合适的 Kw 非常重要,不仅是对核回归,对所有局部加权学习器都很重要(包括distance weighted 距离加权回归)

不一定局部加权回归是最好的,因为参数量(
β
T
\beta^T
βT)很大,因此需要数据量很大才适合
贪婪学习与主动学习(active learner)是有区别的,(主动学习是:先训练一部分,然后问teacher,这个数据的label是什么,然后把label加到训练了,然后学了一段时间后,再问,而且每次问都是挑一些对下一步有用的)


懒惰 :等待查询再泛化(generalization,一般化)
懒惰学习器
贪婪 :查询之前就泛化(y=f(x))
贪婪学习器
如果它们共享相同的假设空间,懒惰学习可以表示更复杂的函数
( e.g. H=线性函数)