Chapter 6:Similarity-Based Metho

2019-01-31 本文已影响3人冒绿光的盒子

①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$ ，所以后面那一项就可以去掉了。