Statistic Estimation

Parametric distribution estimation

参数的极大似然估计

假如 $x$ 是一个概率分布 $p_x(\cdot)$ 中的参数，对于给定的一个观测值（observation），$p_x(y)$ 是似然函数（likelihood function），通常我们会考虑似然函数的对数，也就是

$$ l(x)=\log p_x(y) $$

如果 $p_x(y)=0$，就定义 $l(x)=-\infty$。

参数 $x$ 的极大似然估计，就是：

$$ \hat{x}_{\mathrm{ml}}=\operatorname{argmax}_{x} p_{x}(y)=\operatorname{argmax}_{x} l(x) $$

有时候，还会对参数$x$有一些先验的约束。总之，极大似然估计其实就是一个优化问题：

$$ \begin{array}{ll} \text { maximize } & l(x)=\log p_{x}(y) \\ \text { subject to } & x \in C \end{array} $$

如果，对数似然函数$l$是凹函数（也即似然函数是对数凹），先验约束 $C$ 是一个凸集，那么，这就是个凸优化问题！

我们先考虑一个线性模型：

$$ y_{i}=a_{i}^{T} x+v_{i}, \quad i=1, \ldots, m $$

$x$ 是参数，$y_i$ 是观测值，$a_i$ 是常数，$v_i$ 是观测误差或者随机噪音，进一步假设 $v_i$ 是独立同分布（i.i.d）且具有密度函数 $p$。

于是求 $x$ 的极大似然估计就是要：

$$ \text { maximize }_x \quad \sum_{i=1}^{m} \log p\left(y_{i}-a_{i}^{T} x\right) $$

• 如果认为 $v_i$ 是服从正态分布的，那么就有对数似然函数： $$ l(x)=-(1 / 2) \log (2 \pi \sigma)-\frac{1}{2 \sigma^{2}}\|A x-y\|_{2}^{2} $$

  其中$A=(a_1^T, ..., a_m^T)^T$，从而有：

  $$ x_{\mathrm{ml}}=\operatorname{argmin}_{x}\|A x-y\|_{2} $$

• 如果认为 $v_i$ 是服从拉普拉斯分布，即有密度函数 $p(z)=(1 / 2 a) e^{-|z| / a}$，那么 $$ {x_{\mathrm{ml}}}=\operatorname{argmin}_{x}\|A x-y\|_{1} $$

• 如果认为 $v_i$ 是服从 $[-a,a]$ 上的均匀分布，那么 ${x_{\mathrm{ml}}}$ 是任意满足 $\|A x-y\|_{\infty} \leq a$ 的参数。

一个关于 Laplace 分布的介绍

如果假定 $v_i$ 服从正态分布，那么其实就是回归分析中最小化偏差平方和；服从拉普拉斯分布，就是最小化偏差的绝对值和，后者更具备稳健性。

协方差矩阵的极大似然估计

考虑有一个随机向量 $y$，服从均值为 0 的高斯分布，现在给出一组样本 $y_1,y_2,...,y_N$，想要估计协方差矩阵 $R=\mathbf{E} \, y y^{T}$，这个随机向量具有密度函数

$$ p_{R}(y)=(2 \pi)^{-n / 2} \operatorname{det}(R)^{-1 / 2} \exp \left(-y^{T} R^{-1} y / 2\right) $$

从而可以写出它的对数似然函数

$$ l(R)=\log p_{R}\left(y_{1}, \ldots, y_{N}\right)=-(N n / 2) \log (2 \pi)-(N / 2) \log \operatorname{det} R-(N / 2) \operatorname{tr}\left(R^{-1} Y\right) $$

其中 $Y=\frac{1}{N} \sum_{k=1}^{N} y_{k} y_{k}^{T}$，尽管 $l(R)$ 并不是一个在 $\mathrm{S}^n_{++}$ 上的凸函数，但是可以做一个换元 $S=R^{-1}$，就变成了 $$ l(S)=-(N n / 2) \log (2 \pi)+(N / 2) \log \operatorname{det} S-(N / 2) \operatorname{tr}(S Y) $$

于是就有优化问题： $$ \begin{array}{ll} \text { maximize } & \log \operatorname{det} S-\operatorname{tr}(S Y) \\ \text { subject to } & S \in \mathcal{S} \end{array} $$

这就是一个凸优化问题，（应用矩阵微积分的知识）直接求梯度可以得到显式解$S=Y^{-1}$，从而$R=Y$。自然约束下$\mathcal{S}=\mathrm{S}^n_{++}$，如果再加上一些其它的凸约束，一样是容易求解的。

####最大化后验概率

Nonparametric distribution estimation

现在我们考虑一个取值于集合$\left\{\alpha_{1}, \ldots, \alpha_{n}\right\} \subseteq \mathbf{R}$的离散型随机变量$X$：

$$ \operatorname{prob}\left(X=\alpha_{k}\right)=p_{k} $$

显然，概率单纯形$\left\{p\in\mathbf{R}^{n}\mid p\succeq 0, \mathbf{1}^{T} p=1\right\}$是一个凸集，并且它与这样的随机变量是一一对应的。

一般地，在某些先验信息下，我们希望找到一个满足我们要求的随机变量，比如最大化期望、最大熵、最大化KL散度等。可以说明，很多先验信息（概率约束）都可以是凸的，我们优化的目标，也是常是凸的。

convex probability bounds

设$f:\mathbf{R} \to \mathbf{R}$，那么：

$$ \mathbf{E} f(X)=\sum_{i=1}^{n} p_{i} f\left(\alpha_{i}\right) $$

是$p$的线性函数。所以对于随机变量矩的约束，都是线性的：

$$ \mathbf{E} X=\sum_{i=1}^{n} \alpha_{i} p_{i}, \quad \mathbf{E} X^{2}=\sum_{i=1}^{n}\alpha_{i}^{2} p_{i} $$

取$f$是某个集合的示性函数$I_C$，我们得到：

$$ \operatorname{prob}(X \in C)=c^{T} p, \quad c_{i}=\left\{\begin{array}{ll} 1 & \alpha_{i} \in C \\ 0 & \alpha_{i} \notin C . \end{array}\right. $$

也是$p$的线性函数。

方差是一个凹的二次函数：

$$ \operatorname{var}(X)=\mathbf{E} X^{2}-(\mathbf{E}X)^{2}=\sum_{i=1}^{n} \alpha_{i}^{2}p_{i}- \left(\sum_{i=1}^{n}\alpha_{i}p_{i}\right)^{2} $$

所以对随机变量$X$给定方差的下界是一个凸的约束。

条件概率是分式线性的：

$$ \begin{array}{c} \operatorname{prob}(X \in A \mid X \in B)=c^{T} p / d^{T} p \\ c_{i}=\left\{\begin{array}{ll} 1 & \alpha_{i} \in A \cap B \\ 0 & \alpha_{i} \notin A \cap B \end{array}, \quad d_{i}=\left\{\begin{array}{ll} 1 & \alpha_{i} \in B \\ 0 & \alpha_{i} \notin B \end{array}\right.\right. \end{array} $$

对它做概率约束也是线性的：

$$ l \leq \operatorname{prob}(X \in A \mid X \in B) \leq u \Rightarrow l d^{T} p \leq c^{T} p \leq u d^{T} p $$

$X$的信息熵

$$ H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i} $$

是凹函数。因此最大化信息熵是一个凸的问题。

KL散度$D_{KL}(p\lVert q)=\sum_{i=1}^n p_i \log \frac{p_i}{q_i} $对$(p, q)$是凸的。因此最小化与一个给定分布的KL散度这一问题是凸的。

Chebyshev and Chernoff bounds

Chebyshev bounds

随机变量的切比雪夫界，在已知该随机变量的矩信息（如，均值和方差）的基础上，给出了该随机变量在某个确定集合上取值的概率上界。

设随机向量 $X$ 的支集为 $S \in \mathrm{R}^m$，如果我们知道信息：

$$ \mathrm{E} f_{i}(X)=a_{i}, \quad i=1, \ldots, n $$

特别地，我们令 $f_0$ 是常值函数，且 $\mathrm{E}f_0(x)=a_0=1$ . 令：

$$ f(z)=\sum_{i=0}^{n} x_{i} f_{i}(z), \quad x_i \in \mathrm{R} $$

现在我们希望求出 $X$ 在集合 $C \subseteq S$ 上的取值概率的上界。

假如说我们能找到一组 $x_i$ 使得 $f(z)\geqslant\mathbf{1}_C(z)$，于是我们知道，这时候：

$$ \mathrm{E} f(X)=a^{T} x \geq \mathrm{E}\,\mathbf{1}_{C}(X)=\mathrm{P}(X \in C) $$

从而，我们想要找的上界 $\mathrm{P}(X \in C)$，刚好就是在满足 $f(z)\geqslant\mathbf{1}_C(z)$ 这个条件下，$a^T x$ 的最小值

$$ \begin{array}{ll} \operatorname{minimize} & x_{0}+a_{1} x_{1}+\cdots+a_{n} x_{n} \\ \text {subject to } & f(z)=\sum_{i=0}^{n} x_{i} f_{i}(z) \geq 1 \text { for } z \in C \\ & f(z)=\sum_{i=0}^{n} x_{i} f_{i}(z) \geq 0 \text { for } z \in S, z \notin C \end{array} $$

决策变量 $x\in \mathrm{R}^{n+1}$。注意到目标函数是线性的，但是约束条件，如果集合 $C$ 和 $S$ 不是一个有限集，或者更进一步，$C$ 和 $S$ 是不可列集(uncountable set)，约束条件有无穷多个。

这类线性规划问题我们称之为 Semi-Infinite Linear Program .

尽管上面这个问题表述出来并不是那么的显然，但是它的对偶是非常 ituitive 的！

由于约束条件可能有无穷多个，对于每一个 $z \in S$，我们都要赋予一个对偶变量，那么，就不妨设该问题的对偶变量是一个关于 $z \in S$ 的函数！设为 $p(z)$ .

接着我们可以写出问题的对偶函数：

$$ g(z)=\inf _{x_{0}, \cdots,\; x_{n}} x_{0}+ a_{1} x_{1}+\cdots+a_{n} x_{n}+\int_{C} p\left(z\right)\left[1-\sum_{i=1}^{n} x_{i} f_{i} (z)\right] \mathrm{d} z \\ -\int_{S / C} p(z) \cdot \sum_{i=0}^{n} x_{i} f_i(z) \mathrm{d} z $$

在这里，求和就变成了积分！

注意到 $f_0$ 是一个常值函数，继续整理得： $$ \begin{aligned} g(z) = \inf_{x_0, \cdots, \;x_n} \; & x_{0}\left[1-\int_{C} p(z) f_{0}(z) d z-\int_{S/C} p(z) f_{0}(z) d z\right] \\ +&\sum_{i=1}^{n} x_{i}\left[a_{i}-\int_{C} p(z) f_{i}(z) d z-\int_{S / C} p(z) f_{i}(z) d z\right] +\int_{c} p(z) d z \end{aligned} $$

于是，我们得到，对偶问题就是：

$$ \begin{aligned} \max &\int_{C} p(z) \mathrm{d} z\\ \text{s.t.}&\int_{C} p(z) \mathrm{d} z=1 \\ &\int_{S} p(z) f_{i}(z) \mathrm{d} z=a_{i} , \;\, i=1, \ldots ,n \\ & \;p(z) \geqslant 0, \;\; z\in S \end{aligned} \quad \Longrightarrow \quad \begin{aligned} \max \; & \int_C p(\mathrm{d} z) \\ \text {s.t. } & \int_S p(\mathrm{d} z)=1 \\ & \int_S f_i(z) p(\mathrm{d} z)=a_i, \;\, i=1, \ldots, n \\ & p \geqslant 0, \end{aligned}\notag $$

最后一行的非负约束来自对偶变量的要求。这个对偶问题的意义非常的明显了，$p(z)$ 要求是一个概率分布，约束条件是矩的约束，目标是最大化这个概率分布在某个区域里的取值。

但是这个对偶问题并不具备计算上的实用性，对于原来的问题，我们可以利用逼近的思想一步步增加线性的约束条件，来逼近最优值。

设 $S=\mathrm{R}_{+}, C=[1, +\infty), f_0(z) = 1, f_1(z) = z$，已知 $\mathrm{E} f_1(X) = \mathrm{E}X=\mu$，于是，根据上面的理论 $$ \mathrm{P}(X \geqslant 1) \leqslant \left[ \begin{array}{ll} \min \; & x_0+\mu x_1 \\ \text{ s.t.} & x_0 \geq 0, \quad x_1 \geq 0 \\ & x_0+x_1 \geq 1 \end{array} \right] = \min\{1, \mu\} $$ 如果 $\mu \in [0, 1]$，那么 $\mathrm{P}(X \geqslant 1)\leqslant \mu $ .

Probability bounds with known first and second moments

Chernoff bounds

对于一个 $\mathrm{R}$ 上的随机变量 $X$，它的 Chernff bound 是 $$ \begin{aligned} \mathrm{P}(X \geqslant u) & = \mathrm{P}(e^{\lambda X} \geqslant e^{\lambda u}) \leqslant \frac{\mathrm{E}[e^{\lambda X}]}{e^{\lambda u}}, \;\, \forall\lambda \geqslant 0 & \qquad \text{(Markov inequality)}\\ \mathrm{P}(X \geqslant u) & \leqslant \inf_{\lambda \geqslant 0} \mathrm{E}[e^{\lambda (X- u)}] & \qquad \text{(Chernff bound)} \end{aligned}\notag $$ 两边取对数，就有等价形式 $$ \log \mathrm{P}(X \geqslant u) \leqslant \inf_{\lambda \geqslant 0} \{ -\lambda u + \log \mathrm{E}e^{\lambda X}\} $$ 因为 $\log \mathrm{E}e^{\lambda X}$ 一定是一个（关于 $\lambda$ 的）凸函数，因此右边总是一个凸优化问题。

比如说，对于标准正态分布来说，其 $$ \log \mathrm{E} e^{\lambda X}=\lambda^2 / 2 $$ 于是 $$ \log \mathrm{P}(X \geqslant u) \leqslant \inf_{\lambda \geqslant 0} \{- \lambda u + \lambda^2/2\} = -u^2/2 \;\; \Rightarrow\;\; \mathrm{P}(X \geqslant u)\leqslant e^{-u^2/2} $$ 这种思想完全可以推广到 $n$ 维空间。

为了得到 $\mathrm{P}(X \in C)$ 的上界，首先定义 $$ f(z)=e^{\lambda^T z+\mu} \, \qquad (\lambda \in \mathrm{R}^n, \, \mu \in \mathrm{R}) $$ 如果 $\forall z, f(z) \geqslant \mathbf{1}_C(z)$，就有 $$ \mathrm{P}(X \in C) = \mathrm{E} \,\mathbf{1}_C(X) \leqslant \mathrm{E} f(X) $$ 于是，只要 $\lambda, \mu$ 满足 $f(z) \geqslant1 \Rightarrow \lambda^T z + \mu \geqslant 0, \; \forall z \in C$，就成立 $$ \mathrm{P}(X \in C) \leqslant \mathrm{E}\exp(\lambda ^T X + \mu) $$ 两边取对数 $$ \log \mathrm{P}(X \in C) \leqslant \mu + \log\mathrm{E}\exp(\lambda ^T X) $$ 此时的 Chernoff bound 是 $$ \begin{aligned} \log \mathrm{P}(X \in C) & \leqslant \inf_{\lambda, \mu} \{ \mu + \log\mathrm{E}\exp(\lambda ^T X) \mid -\lambda^T z \leq \mu \text { for all } z \in C \} \\ & = \inf _\lambda\left(\sup _{z \in C}\left(-\lambda^T z\right)+\log \mathrm{E} \exp \left(\lambda^T X\right)\right) \\ & =\inf_\lambda \left(S_C(-\lambda)+\log \mathrm{E} \exp \left(\lambda^T X\right)\right) \end{aligned} $$ 这里 $S_C$ 是 $C$ 的支撑函数 (support function)。上面的 Chernoff bound 的计算完全是一个凸优化问题。