无模型 最近邻 概率密度估计

机器学习

---

源自学长的一篇论文

考虑一个分类问题：$X\in\mathbb{R}^m \mapsto y\in\{c_1,c_2,\cdots,c_q\}$，样本集：$X^i\in \mathcal{D}$
对一个新样本，我们要计算其类别，考虑贝叶斯规则：

$$P(y^i\mid X^i) = \frac{p(X^i\mid y^i)p(y^i)}{p(X^i)}$$
由此只需要计算出$p(y)$和$p(X\mid y)$即可

先计算$p(y)$，考虑$y$的分布，单纯$y$的产生是相互独立的并服从多项式分布，$y \overset{i.i.d}{\sim} \mathrm{Multinomi}(\phi_1, \cdots, \phi_q)$，设$y=(0,0,1,0,0)^T$，也即只有发生事件的那个为$1$，这样分布就可以用乘法表示

$$p(y\mid \phi) = \prod_{j=1}^q \phi_j^{y_j}$$
并且
$$\sum_{j=1}^q \phi_j = 1$$
在数据集$\mathcal{D}$的似然函数为
$$\begin{align*} p(\mathcal{D}\mid \phi) & = \prod_{i=1}^N p(y^{(i)}\mid \phi) \\ & = \prod_{i=1}^N \prod_{j=1}^q \phi_j^{y_j^{(i)}} \\ & = \prod_{j=1}^q \phi_j^{\sum_{i=1}^N y_j^{(i)}} \\ & = \prod_{j=1}^q \phi_j^{m_j} \end{align*}$$
设$m_j = \sum_{i=1}^N y_j^{(i)}$，代表了$y_j=1$发生的次数，也就是上面的$y=c_j$发生的次数
对数似然
$$\begin{align*} \log p(\mathcal{D}\mid \phi) & = \sum_{j=1}^N m_j \ln \phi_j \end{align*}$$
对其求极大值，并且要满足上面的约束条件，所以用拉格朗日乘数法
$$F(\lambda,\phi) = \sum_{j=1}^q m_j \ln \phi_j + \lambda \left( \sum_{j=1}^q \phi_j -1 \right)$$
$$\begin{align*} \frac{\partial F(\lambda,\phi)}{\partial\phi_k} & = \frac{m_k}{\phi_k} + \lambda = 0 \\ \frac{\partial F(\lambda,\phi)}{\partial\lambda} & = \sum_{j=1}^q \phi_j -1 = 0 \end{align*}$$
解方程得
$$\begin{align*} \lambda & = -N \\ \phi_k & = \frac{m_k}{N} \end{align*}$$

也即是，多项式分布的参数是在整个数据集中各个统计值所占的比例

---

接下来计算$p(X\mid y)$，由于$X$为连续的，所以其表示在整个输入空间中的条件密度函数，我们的主要目的就是根据现有的观测值，估计出该密度函数，也就是说要估计出联合概率分布函数$p(X,y)$，任何一个密度估计函数都可以用到这个地方。因为每个X有多个属性，所以在估计的时候要考虑属性之间的相关关系。现在的问题变成了如何估计样本全部属性的联合概率函数

$$p(X_1,X_2,\cdots,X_m \mid y)$$

首先，我们无法直接估计该函数，因为，如果直接根据样本得到该函数每一个点的位置，这个在连续属性中肯定是不可能的（连续属性有无穷多个位置），即使到离散里面，这样简单的估计也是很不准确的，因为这种直接估计的方法的自由度太大，需要得到的值太多，相应的，就需要非常多而且能覆盖几乎所有空间的样本，这样基本上是不现实的。另外一种降低自由度的方法就是参数估计，假设每一个单个属性或者多个属性组符合一个参数化的分布（通常是指数族分布），再根据属性之间的相关性来估计最佳的参数，这种做法的缺点是太依赖先验，每个属性的参数化分布的形式、属性之间的相关关系等。

学长这个地方用了一种“新奇”的估计方法，利用近邻法则，直接根据新样本$\hat{X}$和已有的观测数据，直接获得该样本在$q$个$y$值中的联合概率$p(\hat{X} \mid y)$，然后利用上面的贝叶斯公式计算出所有的$p(y \mid \hat{X})$，则$\hat{X}$的类别就是概率最大的类别。这个方法依据样本$X$与其他所有同类别样本的最短距离$d$来计算，他这里用的是欧式距离

首先定义了一个$\mathcal{U}(\tau) = p(d \geq \tau)$，代表最短距离大于等于$\tau$的概率，$\mathcal{U}(0) = p(d\geq 0) = 1, \mathcal{U}(\infty) = p(\tau \geq \infty) = 0$

学长这里对$\mathcal{U}(\tau)$进行求导，我这里不是太明白这个式子是怎么来的，学长是这样说的

我们知道随着$\tau$的增加$\mathcal{U}(\tau)$将会减少，$\mathcal{U}(\tau)$的减少量正比于样本$X_k$两侧的其他间隔$\Delta \tau$的$N-1$个样本点，关系公式如下所示

$$\frac{\mathrm{d}\mathcal{U}}{\mathrm{d}\tau} \approx -2\cdot(N-1)\cdot p(X_k)\cdot \mathcal{U}(\tau)$$

接下来就是解这个微分方程，设$T = -2\cdot(N-1)\cdot p(X_k)$，$\mathcal{U}'=T\mathcal{U}$得，$\mathcal{U}(\tau) = Ce^{T\tau}$，再有上面的$\mathcal{U}(0)=1, \mathcal{U}(\infty)= 0$

$$\mathcal{U}(\tau) = e^{T\tau} = e^{-2\cdot \tau (N-1)\cdot p(X_k)}$$

首先来看一下，$\mathcal{U}(\tau)$与最近邻距离$\tau_k$的概率$p(\tau_k)$之间的关系

由此

$$p(\tau) = \underset{\Delta\tau\rightarrow0}{\mathrm{lim}}\frac{\mathcal{U}(\tau)-\mathcal{U}(\tau+\Delta\tau)}{\Delta\tau} = -\mathcal{U}'(\tau)$$

然后学长通过计算$\log_2\tau_k$的期望$\mathrm{E}[\log_2\tau_k]$来计算$X_k$的概率，$\tau_k$为$X_k$的最近邻距离

$$\begin{align*} \mathrm{E}[\log_2\tau_k] & = \int_0^{+\infty}p(\tau_k)\cdot\log_2\tau_k\mathrm{d}\tau_k \\ & = \int_0^{+\infty} - \frac{\mathrm{d}\mathcal{U}}{\mathrm{d}\tau_k}\cdot \log_2 \tau_k\mathrm{d}\tau_k \\ & \approx \int_0^{+\infty}2(N-1)p(X_k)e^{-2\tau_k (N-1)\cdot p(X_k)} \log_2 \tau_k \mathrm{d}\tau_k \\ & = \int_0^{+\infty} e^{-\delta}\cdot \log_2\frac{\delta}{2(N-1)p(X_k)}\mathrm{d}\delta \qquad // \quad \delta = 2\tau_k(N-1)p(X_k) \\ & = \int_0^{+\infty} e^{-\delta}\log_2 \delta \mathrm{d}\delta - \int_0^{+\infty} e^{-\delta}\log_2 (2(N-1)p(X_k))\mathrm{d}\delta \\ & = -\log_2(2(N-1)p(X_k)) - \frac{\gamma}{\ln 2} \qquad // \quad \gamma = - \int_0^{+\infty}e^{-\delta}\ln\delta\mathrm{d}\delta \end{align*}$$

然后在这里，又一处我不是很理解的地方，学长直接让函数的期望等于函数本身

$$E[\log_2 \tau_k] = \log_2 \tau_k$$

这个等式怎么来的不知道，这里应该有什么高深的数学知识我不知道。根据这个等式很容易求出联合分布

$$\begin{align*} \log_2 \tau_k & = -\log_2 (2(N-1)p(X_k)) - \frac{\gamma}{\ln2} \\ \log_2p(X_k) & = -\log_2\tau_k - \log_2(2(N-1)) - \frac{\gamma}{\ln2} \\ p(X_k) & = 2^{-\left( \log_2\tau_k + \log_2(2(N-1)) + \frac{\gamma}{\ln2} \right)} \end{align*}$$

这里算出来的概率是同一类别下的$p(X_k\mid y_k=c)$，最近点也是同一类别下的最近点，最终要再除以归一项，$X_k$在各个类别下计算出的值的和

---

接下来是扩展到多维的，思路类似，由于有两个地方没弄明白，不急着往后
先整理下现在有的东西

• $\mathcal{U}(\tau)$：最短距离$d$至少为$\tau$的概率
• $p(\tau) = -\frac{\mathrm{d}\mathcal{U}}{\mathrm{d}\tau}$：最短距离$d$等于$\tau$的概率
• $V_r(\tau)$：半径为$\tau$的$r$维球的体积，$V_1(\tau) = 2\tau, V_1'(\tau) = 2 \quad V_2(\tau) = \pi \tau^2,V_2'(\tau) = 2\pi \tau$
• $p(X \mid y)$：条件联合概率密度函数
• $\mathrm{E}[\log_2\tau_k]$：函数$\log_2\tau_k$的期望，这里$\tau_k$为样本$X_k$的最近距离

不明白的两个公式

• $\frac{\mathrm{d}\mathcal{U}}{\mathrm{d}\tau} \approx -2\cdot(N-1)\cdot p(X_k)\cdot \mathcal{U}(\tau)$
• $E[\log_2 \tau_k] = \log_2 \tau_k$

关于第二条不明白的地方：$\tau_k$本身就表示在训练集里面距离样本$X_k$最近距离，该距离就是一个唯一的值？（啊哈～），那么这个地方的$\mathrm{E}[\log_2\tau_k]$就表示$\log_2\tau_k$这个函数的预期的结果，是计算出来的，而后面的$\log_2\tau_k$是实际的结果，因为前面一整套均是一个估计值，而最近距离$\tau$才是观测值，那么用此处的等式相等来得出想要的联合概率密度函数$p(X_k)$也就能说的过去