该部分主要是复习一下机器学习概率分布的相关知识。这里的概率分布主要讲两个方面：其一是密度估计(Density Estimation)，主要是频率学派和贝叶斯学派的方法。其次是共轭先验，主要是方便后验概率计算。本笔记分上下两个部分，第一部分是这里的各个分布概述；第二部分是指数族分布和非参数估计。这一篇记录第二部分。
注：本文仅属于个人学习记录而已！参考Chris Bishop所著Pattern Recognition and Machine Learning(PRML)以及由Elise Arnaud, Radu Horaud, Herve Jegou, Jakob Verbeek等人所组织的Reading Group。
目录
1.指数族分布
对于之前提到的伯努利分布、二项分布、高斯分布等等都可以归类于指数族分布，指数族形式是\(p(x \mid \eta) = h(x) g(\eta) exp(\eta^T u(x))\)，其中，x可以是标量也可以是向量，\(\eta\)是该分布的自然参数(natural parameters), \(u(x)\)是x的函数。此外，\(g(\eta)\)是归一化因子，因此可以得到:
\[g(\eta)^{-1} = \int h(x) exp(\eta^T u(x)) dx\]对\(\eta\)求微分得到： \(- \nabla \ln g(\eta) = E_{p(x \mid \eta)}[u(x)]\)
这里对满足IID的数据集\(X = (X_n) _{n=1}^N\)使用最大似然估计，形式如下:
\[p(X) = (\prod_{n=1}^N h(x_n)) g(\eta)^N exp(\eta^T \sum_{n=1}^N u(x_n))\]我们对参数\(\eta\)求导，得到：
\[- \nabla \ln g(\eta_{ML}) = \frac{1}{N} \sum_{n=1}^N u(x_n)\]由此知\(\sum_{n=1}^N u(x_n)\)是充分统计量。结合刚才归一化因子的微分公式，可以得到：
\[E_{p(x \mid \eta_{ML})}[u(x)] = \frac{1}{N} \sum_{n=1}^N u(x_n)\]使用了最大似然之后，自然要想如何使用贝叶斯呢？给定了\(p(x \mid \eta)\)，先验概率\(p(\eta)\)选择共轭分布，可以使得后验概率和先验具有相同的形式。对于指数族分布，他们的共轭分布如下:
\[p(\eta \mid \chi, v) = f(\chi,v)g(\eta)^v exp(v \eta^T \chi)\]合起来后得到:
\[p(\eta \mid \chi,v) \propto g(\eta)^{N+v} exp(\eta^T (v \chi + \sum_{n=1}^N u(x_n)))\]书本上具体写了从指数族分布中推断出其他分布的例子。
2.非参方法
之前我们所描述的都是参数估计，都是在努力拟合一个特定的分布。现在我们可以使用非参数方法得到更加灵活(flexible)的方法。非参数估计，是指在不考虑原总体分布或者不做关于参数假定的前提下，进行统计检验和判断分析的一系列方法的总称。非参数估计的基本思路是用已知样本在x处出现的频度来近似p(x)。即考虑一个非常小的区域R，概率\(P = \int_R p(x)dx\)，对于样本区域无穷大的数据点，我们发现有\(K \approx NP\)个点在R区域内。 而对于区域R的容积(volume,考虑x可能是多维)和概率的关系是\(P \approx p(x)V\)。因此，有\(p(x) \approx K / (NV)\)。一个比较经典的应用是用直方图绘制概率密度图。
通过直方图做概率密度估计，告诉我们两件事情：第一、为了估计在给定某一点的概率密度，我们需要考虑该点附近的一些点，而“附近”就意味着我们需要一些距离的度量，比如欧几里得距离，在直方图中“附近”是由直方图中一个个小组的宽度决定的。第二、这个宽度不能太大也不能太小，他控制着模型的复杂度。基于这两点，我们将会讲两个比较常用的概率密度估计方法：核密度估计(kernel estimators) 和最近邻(nearest neighbours)方法。
假设我们观测到N个数据，是由未知的概率密度p(x)在D维空间中产生。在这里我们采用欧几里得距离。上面提到对于概率 \(P = \int _R p(x)dx\) 表示每个数据有概率P掉进区域R，假设一共有K个掉进，那么根据二项分布得：
\[Bin(K \mid N,P) = \frac{N!}{K!(N-K)!} P^K (1-P)^{1-K}\]它的期望\(E(K/N) = P\)，而方差\(var(K/N) = P(1-P)/N\)，如果N很大，那么K近似等于NP，同时如果R很小，之前我们有P是近似于p(x)V的。由此我们得到之前的式子： \(p(x) = \frac{K}{NV}\)。我们可以这样分析这个式子：固定K，从数据中得到V，这种方法是K最近邻法(K-nearest-neighbour)；此外，固定V，从数据中得到K，这种方法是核方法（kernel approach）。都可以证明在N趋近于无穷大时，同时V随着N增大而趋近于0，K随着N增大而趋近于无穷大，两种方法都可以使估计值收敛到真实概率密度。
2.1核密度估计
这里我们假设R是非常小的超立方体(hypercube)，x点是待估计概率密度的点，定义：如果点y落在x附近的R里，即\(\mid u = x-y \mid \le \frac{1}{2}\)，那么k(u)=1，否则k(u)=0; 这里k(u)就是核函数的一种，这种方法也称之为“Parzen窗口”法。因此，对于宽度为h的超立方体，落入点的个数\(K = \sum_{n=1}^N k(\frac{x-x_n}{h})\)。同时我们知道\(p(x) \approx K/(NV); \ \ V = h^D\)，所以有：
\[p(x) = \frac{1}{N} \sum_{n=1}^N \frac{1}{h^D} k(\frac{x-x_n}{h})\]选择平滑的核函数，也会使得估计变得平滑，比如选择高斯核，那么估计结果如下：
\[p(x) = \frac{1}{N} \sum_{n=1}^N \frac{1}{(2\pi h^2)^{1/2}} exp(- \frac{\mid\mid x-x_n \mid\mid^2}{2h^2}))\]核函数可以随意的选择，只有满足两个条件\(k(u) \ge 0, \ \ \int k(u)d(u) = 1\)。 核密度估计是没有训练过程的，它只是简单的存储数据，计算复杂度会随着数据维度增大而线性增大。 对于核密度估计而已，该估计中所有的核的宽度都是h，即选定核函数后，对于不同的x，h都是一致的。如果h太大，导致估计结果过平滑(over-smoothing)，丢失了原有的结构。相反，如果h太小，就好导致估计有很大噪声。所以，h需要更具数据集空间大小而进行选择。
2.1K近邻
K近邻(KNN)法依然是基于局部近似的。对于一个待估计概率密度的点x，我们需要计算距离它最近的K个点的区域的体积V（可以选择K个点中距离X最远的点的距离为h，\(v=h^D\)），得到最终的结果。同样，我们可以想到K控制着概率密度估计的平滑程度，如何选择K也是同样的问题。需要注意的是K近邻做出的模型并不是真实的概率密度模型，因为他在所有空间上的积分不收敛（近邻区域会重叠）。
在本章也是本节的最后一部分，展示了K近邻不仅能够用于概率密度估计，也可以用于分类。假设观测到N个数据，在类别\(C_k\)中有\(N_k\)个数据点，对于带估计点x，周围空间V里含有\(K_k\)在\(C_k\)里，用K近邻估计在\(C_k\)下的概率密度是\(p(x \mid C_k) = \frac{K_k}{N_kV}\)，不考虑条件概率，则是\(p(x) = \frac{K}{NV}\)。对于类别的先验概率是\(p(C_k) = \frac{N_k}{N}\)。
之后，我们使用贝叶斯理论，可以得到后验概率是
\[p(C_k \mid x) = \frac{p(x \mid C_k) p(C_k)}{p(x)} = \frac{K_k}{K}\]同样这里的K控制着决策边界的平滑度，K越大，最终得到的区域越大，区域个数越少。对于K=1时，K近邻有一个属性：在N趋近于无穷大时，错误率最大是最优的分类器的两倍。不过对应的证明论文，我没有看。
到目前讨论的K近邻和核密度估计，都需要把所以的训练数据存储起来，每次估计都有全部计算一遍，如果训练数据很大，那么计算量也会非常的大。解决的办法是使用一些树结构来更加快速的找到K个近邻的点，而不用搜索所有的训练数据点。
注：K近邻可以用三种方法进行简化，第一是部分距离法：即定义部分距离，如果计算得到的部分距离都大于最邻近距离，那整体距离一定大于最邻近距离，即不是最邻近点；第二是预分类法（也称搜索树，在特征空间中首先找到m个有代表性的样本点，用这些点代表一部分训练样本；待识别模式x首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。这种方法是一个次优的搜索算法；第三是对样本进行浓缩（仅保留对决策边界有贡献的样本，删除没有贡献的样本，如删除周围固定区域内全为同类的样本）、剪枝（删除噪声点，如那些类别与周围多数不一致的样本)。
可是，非参数的方法仍然是非常有限的！在以后的章节介绍了参数的方法，使得模型的复杂度独立于数据集的大小，并且能够很好的表征训练数据。