无监督学习-1-密度估计

密度估计

密度估计是一类重要的无监督学习方法，通过从分布 中观测得到的独立同分布的样本集合 ，我们估计 的概率分布 。

密度估计本质上是仍然是参数估计问题，可以使用MLE解决，即

$$\hat{p} = \arg\max_p \mathcal{L}(X_1,X_2,\cdots,X_n;p) = \arg\max_p \prod_{i=1}^np(X_i)$$

然而上述优化问题要在无穷大的解空间

$$\left\{p:p\geq 0 , \int p = 1\right\}$$

上求解，这几乎不可解。

因此有三种解决方案来规避上述问题：

• 参数化密度估计
• 无参密度估计
• 核方法

参数化密度估计

参数化即预先给定数据一个分布，并且通过MLE去学习分布。假设数据 服从高斯分布 , 即

$$p(x;\mu,\sigma)=\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{1}{2}(x-\mu)^2\right)$$

使用MLE求解，有

$$\hat{\mu},\hat{\sigma} = \arg\max_{\mu,\sigma} \sum_{i=1}^n\log p(x_i;\mu,\sigma)$$

可得

$$\mu^\star = \frac{1}{n}\sum_{i=1}^nX_i$$ $$\sigma^\star = \sqrt{\frac{1}{n}\sum_{i=1}^n(X_i-\mu^\star)^2 }$$

无参密度估计

无参密度估计中的一个代表是Histograms，即将密度以直方图的形式展现。

Histograms 算法

为方便讨论，不失一般性，假设数据分布在 上， 将数据分成 组，

$$B_1 = [0,\frac{1}{K}),B_2 = [\frac{1}{K},\frac{2}{K}),\cdots,B_K = [\frac{K-1}{K},1)$$

计算每组中数据元素个数

$$n_k = \sum_{i=1}^n\mathbb{I}(X_i\in B_k)$$

密度估计为

$$\hat{p}(x) = K\sum_{k=1}^K\frac{n_k}{n}\mathbb{I}(X_i\in B_k)$$

正确性

要说明算法正确性，需要验证该函数是否是一个概率密度函数。不难验证

$$\begin{split} \int \hat{p}(x) dx & = \int K\sum_{k=1}^K\frac{n_k}{n}\mathbb{I}(X_i\in B_k) dx \\ & = K\sum_{k=1}^K\frac{n_k}{n}\int\mathbb{I}(X_i\in B_k) dx \\ & = K\sum_{k=1}^K\frac{n_k}{n} \frac{1}{K} dx \\ & = \sum_{k=1}^K\frac{n_k}{n} dx \\ & = 1 \end{split}$$

因此这是一个概率密度函数，正确性得证。

推导

定义在集合 上的分段概率密度为

$$p(x;b_1,b_2,\cdots,b_K) = b_k\quad\texttt{if}\quad x\in B_k$$

上式可被改写为

$$p(x;b_1,b_2,\cdots,b_K) = \prod_{k=1}^K b_k^{\mathbb{I}(x\in B_k)}$$

且满足

$$p(x)\geq 0, \int p(x)dx =1$$

当分为 段时，有

$$\sum_{k=1}^K \frac{b_k}{K} = \sum_{k=1}^K \int_{B_k} p(x)dx = \int p(x)dx =1$$

为了估计 ，使用 MLE

$$b_k = \arg\max_{b_k} \mathcal{L}(X_1,\cdots,X_n;b_1,\cdots,b_K)\quad \texttt{s.t.} \quad \sum_{k=1}^K \frac{b_k}{K} = 1$$

展开 log likelihood 可得

$$\begin{split} \mathcal{L}(X_1,\cdots,X_n;b_1,\cdots,b_K) & =\sum_{i=1}^n \log p(X_i) \\ & =\sum_{i=1}^n\sum_{k=1}^K \mathbb{I}(X_i\in B_k) \log b_k \\ & =\sum_{k=1}^K\log b_k\sum_{i=1}^n \mathbb{I}(X_i\in B_k) \\ & =\sum_{k=1}^K \log b_kn_k \end{split}$$

使用拉格朗日乘子法

$$\sum_{k=1}^K \log b_kn_k - \lambda\left(\sum_{k=1}^K \frac{b_k}{K} - 1\right)$$

由一阶条件（导数为0）可得

$$\hat{b_k} = \frac{Kn_k}{n}, \lambda=\frac{1}{n}$$

即

$$\hat{p}(x) = K\sum_{k=1}^K\frac{n_k}{n}\mathbb{I}(X_i\in B_k)$$

超参选取

另一个问题是如何选取超参数 。一个直觉的想法是最小化均方误差

$$\texttt{MSE}=\mathbb{E}_D\left[ \left(\hat{p}-p^\star\right)^2 \right]$$

其中 是预测分布， 是真实分布。展开可得

$$\begin{split} \mathbb{E}_D\left[ \left(\hat{p}-p^\star\right)^2 \right] & = \mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] + \mathbb{E}_D\left[\hat{p}\right] -p^\star\right)^2 \right] \\ & = \mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] \right)^2\right] + \mathbb{E}_D\left[ \left( \mathbb{E}_D\left[\hat{p}\right] -p^\star\right)^2 \right] \\ & \quad + \mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] \right)\left( \mathbb{E}_D\left[\hat{p}\right] -p^\star\right)\right] \end{split}$$

因为 和 独立于 ，我们有

$$\begin{split} \mathbb{E}_D\left[ \left(\hat{p}-p^\star\right)^2 \right] & = \mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] \right)^2\right] + \left( \mathbb{E}_D\left[\hat{p}\right] -p^\star\right)^2\\ & \quad + \mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] \right)\right] \left( \mathbb{E}_D\left[\hat{p}\right] -p^\star\right) \\ & = \underset{\texttt{variance term}}{\mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] \right)^2\right]} + \underset{\texttt{bias term}^2}{\left( \mathbb{E}_D\left[\hat{p}\right] -p^\star\right)^2} \end{split}$$

即 MSE 由方差项和误差项的平方组成，我们接下来分别考虑这两项。

由于 服从二项分布

$$n_k = \sum_{i=1}^n \mathbb{I}(X_i\in B_k) \sim \mathbb{B}\left(n,\int_{B_k}p^\star(s)ds\right)$$

有

$$\mathbb{E}\left(\hat{p}(x)\right) = K\sum_{i=1}^K\frac{\mathbb{E}(n_k)}{n}\mathbb{I}(x\in B_k) = K\sum_{i=1}^Kp_k^\star\mathbb{I}(x\in B_k)$$

不失一般性，假设 。则

$$\mathbb{E}\left(\hat{p}(x)\right)= K\int_{B_k}p_k^\star(s)ds$$

首先考虑误差项：

$$\begin{split} \mathbb{E}[\hat{p}(x)] - p^\star(x) &= K\int_{B_k} p^\star(s)ds - p^\star(x) \\ &= K\int_{B_k} p^\star(s)ds - p^\star(x) \cdot K\int_{B_k}ds \\ &= K\int_{B_k} p^\star(s)ds - K\int_{B_k}p^\star(x)ds \\ &= K\int_{B_k} \left(p^\star(s) - p^\star(x)\right) ds \end{split}$$

当真实分布满足 条件

$$|p^\star(x)-p^\star(y)| \leq L |x-y|\quad \forall x,y \in [0,1)$$

有

$$\begin{split} \mathbb{E}[\hat{p}(x)] - p^\star(x) &= K\int_{B_k} \left(p^\star(s) - p^\star(x)\right) ds \\ &\leq K\int_{B_k} \left|p^\star(s) - p^\star(x)\right| ds \\ &\leq K\int_{B_k} L\left|s-x\right| ds \\ &\leq K\int_{B_k} \frac{L}{K} ds \\ &\leq \frac{L}{K} \end{split}$$

当 增大时，误差减小

然后考虑方差项 ：

$$\begin{split} \mathbb{V}\left[\hat{p}(x)\right] & = \mathbb{V}\left[\frac{Kn_k}{n}\right] \\ & = \frac{K^2}{n^2}\mathbb{V}\left[n_k\right] \\ & = \frac{K^2}{n^2} \left(n\int_{B_k}p^\star(s)ds\left(1-\int_{B_k}p^\star(s)ds\right)\right) \\ & = \frac{K^2}{n} p_k^\star(x) \left(1-p_k^\star(x)\right) \end{split}$$

其中 。当 足够大时，有 ， 则

$$\begin{split} \mathbb{V}\left[\hat{p}(x)\right] & \leq \frac{K^2}{n} p_k^\star(x) \\ & \approx \frac{K}{n} p^\star(x) \\ \end{split}$$

假设 有上界 ， 即 ，则有

$$p_k^\star(x) = \int_{B_k} p^\star(s)ds \leq \int_{B_k} \left|p^\star(s)\right|ds \leq \int_{B_k} \gamma ds \leq \frac{\gamma}{K}$$

综上所述，有

$$\begin{split} \texttt{MSE}(\hat{p}, p^\star) & = \underset{\texttt{variance term}}{\mathbb{E}_D\left[ \left(\hat{p} - \mathbb{E}_D\left[\hat{p}\right] \right)^2\right]} + \underset{\texttt{bias term}^2}{\left( \mathbb{E}_D\left[\hat{p}\right] -p^\star\right)^2} \\ & \leq \frac{K^2}{n} p_k^\star(x) \left(1-p_k^\star(x)\right) + \left(\frac{L}{K}\right)^2 \\ & \leq \frac{K^2}{n} p_k^\star(x) + \left(\frac{L}{K}\right)^2 \\ & \leq \frac{\gamma K}{n} + \left(\frac{L}{K}\right)^2 \end{split}$$

由于 均非负，最小值在关键点处取得，即

$$\frac{\partial \texttt{MSE}(\hat{p}, p^\star)}{\partial K} =0$$

解得

$$K_{opt} = \left(\frac{2nL^2}{\gamma}\right)^{\frac{1}{3}} \sim O\Big(C(L,\gamma)n\Big)^{\frac{1}{3}}$$

因此有

$$K_{opt}=\left(\frac{2nL^2}{\gamma}\right)^{\frac{1}{3}}$$

因此有收敛性保证

$$\texttt{MSE}_{K_{opt}}(\hat{p}_{hist}, p^\star) \leq \frac{\gamma K_{opt}}{n} + \left(\frac{L}{K_{opt}}\right)^2 = \frac{3\gamma^2L^2}{2^\frac{2}{3}n^\frac{2}{3}} \sim O\left(n^{-\frac{2}{3}}\right)$$