Chapter 6:Similarity-Based Methods

①Similarity Measure

相似度的衡量方法： Euclidean Distance（欧几里得距离）：

d(x,x_1) = |x-x_1|

Mahalanobi Distance（马氏距离）：

d(x,x^`) = (x-x^`)^TQ(x-x^`)

，其中Q是一个半正定的协方差矩阵，是多维度数据之间的方差。马氏距离比高斯距离考虑的更全面，因为他把数据的维度和数据的大小都考虑了进来。中间的Q矩阵就是起到这个作用，

Q = \Sigma^{-1}

Cossim Similarity:这个是余弦距离，

cossim(x,x^{`}) = \frac{x*x^`}{|x||x^`|}

常用于在文本向量相似度的比较之中。 Jccard Coeffcient：

J(S_1,S_2) = \frac{|S_1 \cap S_2|}{|S_1 \cup S_2|}

这个比较方法常用于在集合的对比，也就是推荐系统的优良性度量里面。

②Nearest Neighbor

Two competing Principles: ①拟合数据并且得到较低的in-sample error ②in-sample error必须是可信的，可以作为out-of-sample的估计 规则：用最近邻的k个点的变量的类别来指定当前点的类别 Voronoi图：是由一组连续的两邻点直接的垂直平分线组成的连续多边形。 最近邻算法不需要训练过程，所以它是可以实现In-sample error为0的，因为in-sample error就是训练集里面产生的。

③VC Dismension

由于kNN算法理论上是可以拟合任何数据，所以它是可以shatter任何数据，所以它的VC维是无限的，这和凸边型是一样的。

④Feasible of Nearest

在KNN里面的label是一个固定的值，它的概率是百分之一百，我们假设他和logistic regression一样，label是由一定的概率组成。

\pi(x) = P[y = +1|x]

，当

\pi(x) >= \frac{1}{2}:label = +1;otherwise:label = -1;

再假设

\eta(x) = min(\pi(x), 1-\pi(x))

if(\pi(x) >= \frac{1}{2}):e(f(x)) = p[f(x) != y] = p[y != 1] = p[y = -1] = 1 - \pi(x) <= \pi(x)

otherwise:e(f(x)) = p[f(x) != y] = p[y = 1] = \pi(x) <= 1-\pi(x)

summarise:e(f(x)) = \eta(x) = min(\pi(x), 1-\pi(x))

因为f(x)是我们的最优分类器，所以上面的

e(f(x))

就是我们能够对一个点做到最好的

E_{in}

的结果了。

上面就是最好情况，现在来看看普通情况：

e(g_N(x)) = P[g_N(x) != y] = P[g_N(x) = 1 | y = -1] + P[g_N(x) = -1|y=1]

这个时候x的类别是由离x最近的那个点决定的。所以：

e(g_N(x)) = \pi(x)(1-\pi(x_{[1]})) + \pi(x_{[1]})(1-\pi(x))

e(g_N(x)) = 2\pi(x)(1-\pi(x)) + \sigma_N(x)

\sigma_N = (2\pi(x)-1)(\pi(x) - \pi(x_{[1]}))

当N足够大的时候，在一个有限的空间里面，

x

和

x_{[1]}

可以无限接近，那么

\sigma_N -> 0

，两边取期望：

e(g_N(x)) <= 2e(f(x))

E_{out}(g_N) <= 2E_{out}^*

这只是一种大概的证明方法，如果要更加细致一点： 首先由

E[x^2] <= E[x]^2

，回到上面的式子：

e(g_N(x)) = 2\pi(x)(1-\pi(x)) + \sigma_N(x)

，两边取期望：

E_{out}(g_N) <= 2E_{out}^*(1-E_{out}^*)+E_x[\sigma_N(x)]

如果上面的不等式满足N是非常大的一个数，而且

\pi(x)

是平滑的而且是连续的，那么

\sigma_N -> 0

，所以后面那一项就可以去掉了。

⑤The power of the nearest neighbor

KNN的能力上面已经证明过了，虽然VC维是无穷，以至于表面上看起来没有上面作用，但是实际证明已经表面他的最高错误界限是最优的两倍，也就是说他至少是可以做到最优化分类器的两倍。 K参数控制了这个模型的复杂度，大的K可以使我们得到更加平滑的结果。当k = N的时候，那么整一个分类器就是一个常数的了。

⑥Proper K value

一般是K = 3就够了：

if(k == 3):E_{out}(g_N) <= E_{out}^* + 3E[\eta^2(x)]

if(k == 5):E_{out}(g_N) <= E_{out}^* + 10E[\eta^3(x)]

很明显，k = 5的效果肯定是比k = 3要好的，但是相对来说，增长这么一点准确率根本不算什么，hardly worth the effort，不值得我们这么做。 但是这必须要满足两个假设:

\frac{k}{N} ->0

这是为了保证这k个点一定要和当前点足够接近 k->+

\infty

是为了保证有足够多靠近的点 满足上面情况那么这个knn分类器是就是最优的。

⑧Improving the efficiency of Nearest Neighbor

对于KNN，有好处也有坏处。 不需要任何的训练过程，直接就可以运行，但是他的训练复杂度转移到了预测上面。优化方法有两个:

Data Condensing

数据压缩，按照最完美的方法，完美要求保留下来的数据集S要和原来的数据空间是一样的，也就是R整体实数，这是一个很苛刻的条件，基本达不到，所以退一步，只要求保留下来的数据集S和训练集空间上匹配就好了，也就是和训练集得到的预测结果一样即可。

Condensed nearest neighbor algorithm

1.初始化压缩数据集S为随机的K个来自训练集的点。 2.选择一个点，使得这个点在训练集合压缩集上的分类不是一致的。 3.把这个不一致点的最近的点放进压缩集 最多重复N步。

Data Editing and Data Condensing Data Editing是数据编辑，是去掉噪音点，如果有一个点是和大致数据走向是不一致点的，那么这个点很有可能就是噪音点。 Data Condensing是数据压缩，把一些多余的点去掉减少计算复杂度。

Efficient Search

首先要提到的就是分支界限法： 1.把整一个数据集S分成

S_1

和

S_2

2.如果当前点到

S_1

的中心

u_1

的距离比到

s_2

的中心

u_2

要短，我们就可以忽略

S_2

了。 3.假设a是在集合

S_1

的最近点，如果存在

|x-a| <= |x- u_2|-r_2

，那么a就是最近点了。

Cluster algorithm for Technique above

前面的算法提到了需要聚类，现在就来提一下聚类算法。 目标是选择M个聚类出来。 1.随便选择一个初始点作为中心点。 repeat： 2.选择一个离当前的中心点最远的点，作为第二个中心点，直到凑够了M个中心点。 end; 3.用在当前聚类里面的均值来更新中心点，直到收敛即可。

⑧Nonparametric and Parametric

无参数的模型： 1.没有参数。 2.一般是存储训练数据作为预测使用。 3.如果k或者N选择适当的话，是一定收敛的。 收敛性是无参模型的一大特征。 参数模型： 1.有参数 2.使用一些参数来代表从训练数据里面学习的信息，而无需存储训练数据。 3.只有假设集包含了target function的情况下才会收敛，否则是不会收款的。 半参数模型： 1.需要特定的参数 2.总是会收敛 最典型的参数模型就是线性回归了，逻辑回归，SVM都是，而无参模型就是KNN，半参模型神经网络就是。因为神经网络在理论上是可以拟合任何的数据。

⑨The Confusing Matrix

混淆矩阵是一种可以用来痕量分类效果的一种方法。

这个矩阵就很容易可以看出哪个类别和哪个类别容易混淆。只需要计算有多少个原本类别是

C_1

分类成

C_2

的即可。

⑩KNN for regression

做回归就很简单了，直接可以使用K个最近点的均值即可。 如果k=1的时候，那么函数就会是阶梯型的阶梯函数。当

x->\infty

，函数是一个常数。

11.Radial Basis Function

在KNN里面，只有K个最近点会影响x的类别判断。在RBF里面，所以的点都会不同程度的为当前点做出贡献。常用的核函数有两个：高斯核，window。

高斯函数

一般我们看到的都是归一化之后的，但是这里还不需要，后面的密度估计会需要了。另外一个重要的组成部分就是r，scale。这是指定了核函数的宽度。

意思是r是长度的单位，也就是随着x增长而增长的单位长度。scale r越小，那么我们会越重视近距离点的贡献。

加上分母的原因是使得权值相加为1. 最后得到的就当前的类别。可以直接类比KNN左回归，也可以做分类，或者加上sigmoid函数做逻辑回归。

window 函数

代会原式子其实就是KNN本身。

12.RBF Networks

解释的两个方向：

一个就是刚刚的式子。这样是把高斯函数隆起的这个小山峰放在当前判断的x点上：

第二种方法就是改写上面的式子：

这样就是把高斯函数的小山峰放在了每一个点x上，在X点处就是对x左的贡献：

高度是W，在预测中需要计算的。在当前的这些bump里面，高度是不一样的，如果我们把它改写一下，把w都变成是固定的，或者说把他们变成参数在训练的时候固定下来：

这样就变成了RBF Networks了。

可以看到参数型的RBF会衰减到0，而非参数的不会。具体证明如下：

13.overfitting

N个参数，对于数据的拟合能力肯定是很强的了，那么过拟合的可能性肯定很高，这个时候就需要处理过拟合的问题了。 解决办法很简单，既然是参数多，那么减少一点参数即可：

偏执项是需要的，如果没有偏执项，在类别的均值不是0的话，整个学习曲线可能会变的扭曲。需要注意的是因为u是在高斯函数里面，所以u参数不是线性的，也就是说这个时候运行基础函数是依赖于参数的，这种情况下对于模型的性能提升是很大的。k指定的是假设集的大小，r值的就是一个假设的复杂度。

14.Learning for RBF Networks

有两个参数是需要学习，而u参数是非线性的，直接求导计算的话玩不来，所以需要先确定：

根据上面的各种需求就可以求导即可，比如regression，或者是带regular的regression直接套公式即可。

15.KMean均值

上面RBF Network的第一步就是要确定中心点，这里就可以使用k均值算法了。

对上述式子求导即可。

聚类问题是一个NP-hard的问题，但有时候没有必要找到最好的问题，只需要找到比较好的就可以了，然后后面还有w线性参数的优化调整。

16.Probability Density Estimation

x的概率密度是将聚类推广到更精细的表达。密度估计的任务是估计对于给定的x点有多少可能会生成和x相似的点。要知道这个问题，就需要知道数据集里面有多少个和x相似的点。这里的相似度指的其实是距离。

①直方图

把当前空间分成m个相等大小而互不相交的立方体，然后计算每一个立方体里面的点的个数：

加上1/N是为了积分为1，密度积分一定要为1。

但是要满足两个假设，v->0，每一个小空间要趋向于0，这样可以保证空间里面的点是足够接近x的，N*V->

\infty

，这样可以保证有足够多喝x相邻的点存在。

②KNN

KNN方法做密度估计问题。对每一个点进行按圆扩张，知道包含了k个点。

比如要计算x的密度，那么在x点按圆形扩张，知道包含了k个点，然后按照如下公式：

很明显，这样画出来的图像有小尖快，局部对称。但是要注意的是，KNN估计密度的空间必须要有边界，因为上面的参数c就是归一化的，如果没有边界，归一化参数c是求不出来的。k要趋向无穷而k/N要趋向于0使得n远大于k，这样可以保证收敛。

RBF估计

继承了高斯函数形状以及收敛性，如果想要减少bump的话是可以增大scale r的。

17.GMMs

高斯混合模型。一个数据点是有多高斯模型互相贡献而成的，需要求这些高斯模型的参数。

w是这个模型贡献百分比，积分为1。 最大似然估计：

E-M算法求解： 先假设一个变量

\gamma

，这个变量是指定当前第i个高斯分布对第j个数据点左贡献的百分比。

learning from data这本书对于E-M算法没有过多的讲解，都是直观解释，在李航老师的统计学习方法里面的公式推导较为完善，前面的博客也提到。但是对于E-M算法是有两种解释方法的，但是结果都是一样的，一般通俗的是比较好理解的。