下面$P,Q$表示概率测度,$p=\mathrm{d}P/\mathrm{d}x,q=\mathrm{d}Q/\mathrm{d}x$ 表示概率密度函数

记 $p\wedge q=\min(p,q),\ p\vee q=\max(p,q),a_-=\max\{0,-a\}, a_+=\max\{a,0\}$

Hellinger distance

$$\mathcal{H}^2(P,Q)=\int(\sqrt{p}-\sqrt{q})^2\,\mathrm{d}x=2-2\int\sqrt{pq}\,\mathrm{d}x$$

可以证明其满足距离的定义,且 $0\leq \mathcal{H}^2(P,Q)\leq 2$

如果 $P=\bigotimes_{i=1}^{n} P_i,Q=\bigotimes_{i=1}^{n} Q_i$

则 $$\mathcal{H}^2(P,Q)=2-2\prod\limits_{i=1}^{n}(1-\frac{1}{2}\cdot \mathcal{H}^2(P_j,Q_j))$$

Total variation distance

$$\mathrm{TV}(P,Q)=\sup_{A}\lvert P(A)-Q(A)\rvert=\sup\limits_{A}\big\lvert \int_A(p-q)\,\mathrm{d}x \big\rvert$$

可以证明其满足距离的定义,且 $0\leq \mathrm{TV}(P,Q)\leq 1$,这可以由下式得到

$$\mathrm{TV}(P,Q)=\frac{1}{2}\int\lvert p-q\rvert\,\mathrm{d}x=1-\int p\wedge q\,\mathrm{d}x$$

Kullback divergence

$$KL(P,Q)=\int p\log \frac{p}{q}\,\mathrm{d}x$$ , 如果 $P\ll Q$

可以利用 Jensen inequality 证明其非负

$$\int p\log \frac{p}{q}\,\mathrm{d}x=-\int p\log \frac{q}{p}\,\mathrm{d}x\ge-\log\int q\,\mathrm{d}x\ge 0$$

但是不满足对称性(所以不叫 distance),可以构造 $KL(P,Q)+KL(Q,P)$ 来满足对称性

如果 $P=\bigotimes_{i=1}^{n} P_i,Q=\bigotimes_{i=1}^{n} Q_i$

$$KL(P\mid\mid Q)=\sum_{j=1}^{n}KL(P_j,Q_j)$$

另一个十分有用的性质时对于正态分布来说

现考察其 KL 散度,记 $\varphi(x)=\frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\},\varphi(x+t)=\frac{1}{\sqrt{2\pi}}\exp\{-(x+t)^2/2\}$,则其KL 散度为

$$\begin{align}KL(\varphi(x),\varphi(x+t)&=\int_{-\infty}^{+\infty} \frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}\left(\frac{(x+t)^2-x^2}{2}\right)\,\mathrm{d}x\\&=\int_{-\infty}^{+\infty} \frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}\frac{t^2}{2}\,\mathrm{d}x+\int_{-\infty}^{+\infty} \frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}\left(-tx\right)\,\mathrm{d}x\\&=\frac{t^2}{2}+0=\frac{t^2}{2}\end{align}$$

$\chi^2$ divergence

$$\chi^2(P,Q)=\int q\cdot \left(\frac{p}{q}-1\right)^2\,\mathrm{d}x$$

同样其也不满足对称性。可以证明其有性质

$\chi^2(P,Q)=\int \frac{p^2}{q}\,\mathrm{d}x-1$

如果 $P=\bigotimes_{i=1}^{n} P_i,Q=\bigotimes_{i=1}^{n} Q_i$

$$\chi^2(P,Q)=\prod\limits_{i=1}^{n}(1+\chi^2(P_i,Q_i))-1$$

Csizsar f-divergence

上述四个都是 Csizsar f-divergence 的特殊情况,其定义为 $$D(P,Q)=\int q\cdot f(p/q) \mathrm{d}x$$,其中要求 $f$ 是在 $\mathbb{R}^+$ 上的凸函数。之前四个距离分别是 $f(x)=\lvert x-1\rvert/2$, $f(x)=(\sqrt{x}-1)^2$ , $f(x)=x\log x$ 和 $f(x)=(x-1)^2$

距离相关的不等式

Le Cam’s Inequallities

为方便,分别记 Hellinger、Total variation 和 KL 散度为 $H,T,K$

式一

$$\int p\wedge q\,\mathrm{d}x\ge\frac{1}{2}(\int\sqrt{pq}\,\mathrm{d}x)^2=\frac{1}{2}(1-H^2/2)^2$$

证明:只需注意到 $\int p\wedge q\,\mathrm{d}x+\int p\vee q\,\mathrm{d}x=2$

则有

$$\begin{align}(\int\sqrt{pq}\,\mathrm{d}x)^2&=(\int\sqrt{p\wedge q\ \cdot\ p\vee q}\,\mathrm{d}x)^2\\&\leq\int p\wedge q\,\mathrm{d}x\ \cdot\ \int p\vee q\,\mathrm{d}x\\&=\int p\wedge q\,\mathrm{d}x\ \cdot\ \left(2-\int p\wedge q\,\mathrm{d}x\right)\\&\leq 2\int p\wedge q\,\mathrm{d}x\end{align}$$

式二

$$H^2/2\leq V\leq H\sqrt{1-H^2/4}\leq H$$

证明:

左边: $V=1-\int p\wedge q\,\mathrm{d}x\ge 1-\int pq\,\mathrm{d}x=H^2/2$

右边:注意到式一推导过程中可以推导出

$$(1-H^2/2)^2=(\int\sqrt{pq}\,\mathrm{d}x)^2=(1-V)(1+V)=1-V^2$$

由此导出 $V^2\leq H^2(1-H^2/4)$

式三

$$H^2\leq K$$

证明:由于 $-\log(x+1)\ge -x,\ (x>-1)$,代入 KL 散度计算中有

$$\begin{align}K&=-\int p\log(q/p)\,\mathrm{d}x\\&=-2\int p\log(\sqrt{q/p})\,\mathrm{d}x\\&=-2\int p\log(\sqrt{q/p}-1+1)\,\mathrm{d}x\\&\ge -2\int p(\sqrt{q/p}-1)\,\mathrm{d}x\\&=2-2\int(\sqrt{pq})\,\mathrm{d}x=H^2\end{align}$$

综合之前我们可以得到 $V\leq H\leq\sqrt{K}$,但这并不是最优的,因为我们可以证明下式

Pinsker’s Inequalities

$$V\leq\sqrt{K/2}$$

令 $\psi(x)=x\log x-x+1,x\ge 0$,并定义 $0\log 0=0$

注意到 $\psi(0)=1,\psi(1)=0,\psi’(1)=0,\psi’’(x)=1/x\ge 0,\psi(x)\ge 0$

可以精巧地构造出下列不等式,使用高中的导数知识求导即可证明

$$(x-1)^2\leq (4/3+2x/3)\psi(x)$$

于是

$$\begin{align}V&=\frac12\int\lvert p-q\rvert \,\mathrm{d}x\\&=\frac12\int\lvert p/q-1\rvert q\,\mathrm{d}x\\&\leq\frac12\int\sqrt{4/3+2p/3q}\cdot\sqrt{\psi(p/q)}\cdot q\,\mathrm{d}x\\&\leq \frac{1}{2}\sqrt{\int (4q/3+2p/3)\,\mathrm{d} x}\sqrt{\int q\cdot\psi(p/q)\,\mathrm{d} x}\\&=\frac{1}{2}\sqrt{2}\sqrt{K}=\sqrt{K/2}\end{align}$$

刻画 $K$ 和 $V$ 的另一个不等式

$V\leq 1-\frac{1}{2}\exp\{-K\}$

证明:使用 Jensen 不等式有

$$\begin{align}(\int\sqrt{pq}\,\mathrm{d}x)^2&=\exp\{2\log\int\sqrt{pq}\,\mathrm{d}x\}\\&=\exp\{2\log\int p\sqrt{\frac{q}{p}}\,\mathrm{d}x\}\\&\ge\exp\{2\int p\log\sqrt{\frac{q}{p}}\,\mathrm{d}x\}\\&=\exp\{-K\}\end{align}$$

所以有 $\int p\wedge q\,\mathrm{d}x\ge \frac{1}{2}\exp\{-K\}$

即 $V=1-\int p\wedge q\,\mathrm{d}x\leq 1-\frac{1}{2}\exp\{-K\}$

刻画 K 和 $\chi^2$ 不等式

$K\leq\log(1+\chi^2)\leq \chi^2$

证明: 使用 Jensen 不等式有

$$\log(1+\chi^2)=\log\int \frac{p^2}{q}\,\mathrm{d}x\ge\int p\log\frac{p}{q}\,\mathrm{d}x=K $$

所以我们通过给出 $\chi^2$ 的上界可以同样控制住 $K$。

刻画误差下界

本文是为非参数统计中刻画误差下界服务的。其关心的值为

$$p_{err,1}=\int\limits_\psi\max\limits_{j=0,1}\mathbb{P}_j[\psi\neq j]\ge \frac{1}{2}\inf\limits_\psi\{\mathbb{P}_0[\psi\neq 0]+\mathbb{P}_1[\psi\neq 1]\}=\frac{1}{2}(\mathbb{P}_0[\psi^\ast\neq 0]+\mathbb{P}_1[\psi^\ast\neq 1])$$

其中 $\psi^\ast$ 为极大似然估计,为 $\psi^\ast=\boldsymbol{1}[P_0<P_1]$ 其中 $P_0,P_1$ 是 $\mathbb{P}_0,\mathbb{P}_1$ 对应的概率密度函数。

注意到 $\frac{1}{2}(\mathbb{P}_0(\psi^\ast\neq 0))+\mathbb{P}_1(\psi^\ast\neq 1))=\frac{1}{2}\int P_0\wedge P_1=(1-V)/2$

由此我们得

  • 如果 $V \leq\alpha <1$, 则 $p_{err,1}\ge\frac{1-\alpha}{2}$ (立得)
  • 如果 $H\leq\alpha <2$, 则 $p_{err,1}\ge\frac{1-\sqrt{\alpha(1-\alpha/4)}}{2}$ (使用 $V\leq H\sqrt{1-H^2/4}$)
  • 如果 $\mathrm{K}(\mathbb{P}_1,\mathbb{P}_0)\leq\alpha <1$ (或 $\chi^2(\mathbb{P}_0,\mathbb{P}_1)\leq\alpha<1$, 则 $p_{err,1}\ge\max\{\frac{1}{4}e^{-\alpha},\frac{1-\sqrt{\alpha/2}}{2}\}$ (使用 $V\leq\sqrt{K/2}$ 和 $V\leq 1-\frac{1}{2}\exp\{-K\}$)