TV距离与KL散度的不等式

对于概率分布P,Q，我们建立了total variation距离和KL散度间的Pinsker不等式（见 Pinsker不等式证明摘录）．Total variation距离的一个平凡的上界是1，但KL散度大的时候甚至会比这个平凡上界弱，我们还可以考虑如下的BH不等式，它给出了总比1小的界．

\begin{aligned}
\|P-Q\| _ {\mathrm{TV}}&=\sup _ A|P(A)-Q(A)|,\\
D _ {\mathrm{KL}}(P\|Q)&=
\begin{cases}
\mathbb E _ P\Big[\log\frac{\mathrm dP}{\mathrm dQ}\Big],& P\ll Q,\\
+\infty,& P\not\ll Q.
\end{cases}
\end{aligned}

定理（Pinsker不等式）：考虑\log的底数取\mathrm e，那么
\|P-Q\| _ {\mathrm{TV}}\leqslant \sqrt{\frac12D _ {\mathrm{KL}}(P\|Q)}.

定理（Bretagnolle-Huber不等式）：

\|P-Q\| _ {\mathrm{TV}}\leqslant \sqrt{1-\exp(-D _ {\mathrm{KL}}(P\| Q))}.

由于对正数x有\sqrt{1-x}\leqslant \sqrt{1-x+x^2/4}=1-x/2，上式立马有推论

\|P-Q\| _ {\mathrm{TV}}\leqslant 1-\frac12\exp(-D _ {\mathrm{KL}}(P\| Q)).

---

为了证明BH不等式，可以从Hellinger距离获得启发（Bhattacharyya系数）．

设测度\mu满足P\ll\mu和Q\ll\mu（如\mu=P+Q），记

\begin{gathered}
p=\frac{\mathrm{d}P}{\mathrm{d}\mu},\quad q=\frac{\mathrm{d}Q}{\mathrm{d}\mu},\\
\rho=\int\sqrt{pq}\, \mathrm{d}\mu.
\end{gathered}

那么0\leqslant\rho\leqslant1，这是因为由Cauchy-Schwarz不等式，

\rho\leqslant\Big(\int p\, \mathrm{d}\mu\int q\, \mathrm{d}\mu\Big)^{1/2}=1.

TV距离和KL散度可写成

\begin{gathered}
\|P-Q\| _ {\mathrm{TV}}=\frac12\int|p-q|\, \mathrm{d}\mu,\\
D _ {\mathrm{KL}}(P\|Q)=\int p\ln\frac{p}{q}\, \mathrm{d}\mu.
\end{gathered}
引理：\|P-Q\| _ {\mathrm{TV}}^2\leqslant {1-\rho^2}.

引理：D _ {\mathrm{KL}}(P\|Q)\geqslant-2\ln\rho.

证明这两个引理（点击展开）

由Cauchy-Schwarz不等式，

\begin{aligned}
\|P-Q\| _ {\mathrm{TV}}&\leqslant\frac12\Big(\int(\sqrt{p}-\sqrt{q})^2\, \mathrm{d}\mu\int(\sqrt{p}+\sqrt{q})^2\, \mathrm{d}\mu\Big)^{1/2}\\
\|P-Q\| _ {\mathrm{TV}}^2&\leqslant\frac14\int(p+q-2\sqrt{pq})\, \mathrm{d}\mu\int(p+q+2\sqrt{pq})\, \mathrm{d}\mu\\
&=\frac14(2-2\rho)(2+2\rho)\\
&=1-\rho^2.
\end{aligned}

对于KL散度，只需考虑P\ll Q，此时

\begin{aligned}
&D _ {\mathrm{KL}}(P\|Q)=\mathbb E _ P\Big[\ln\frac{\mathrm{d}P}{\mathrm{d}Q}\Big]\\
={}&-2\, \mathbb E _ P\ln\sqrt\frac{q}{p}\geqslant-2\ln\mathbb{E} _ P\sqrt\frac{q}{p}\\
={}&-2\ln\int p\sqrt\frac{q}{p}\, \mathrm{d}\mu=-2\ln\rho.
\end{aligned}引理得证．

BH不等式可轻易证出：

\begin{aligned}
&\sqrt{1-\exp(-D _ {\mathrm{KL}}(P\|Q))}\geqslant\sqrt{1-\exp(2\ln\rho)}\\={}&\sqrt{1-\rho^2}\geqslant\|P-Q\| _ {\mathrm{TV}}.
\end{aligned}

Donsker-Varadhan变分表示

KL散度的Donsker-Varadhan变分表示在信息论和机器学习理论里都有重要的地位．

定理：设P是一个可测空间\mathcal{X}上的概率测度，而Q是\mathcal{X}上的满足Q\ll P的概率测度，那么：对实可测函数f，当\mathbb{E} _ {\mathrm{x}\sim P}[\mathrm{e}^{f(\mathrm{x})}]<+\infty时，有

\ln \mathbb{E} _ {P}(\mathrm{e}^{f(\mathrm{x})})=\sup _ Q \big(\mathbb{E} _ Q(f(\mathrm{x}))-D _ {\mathrm{KL}}(Q\|P)\big).

上确界的分布Q^\ast（Gibbs分布）满足

\frac{\mathrm{d}Q^\ast}{\mathrm{d}P}(x)=\frac{\mathrm{e}^{f(x)}}{\mathbb{E} _ P(\mathrm{e}^{f(\mathrm{x})})}.

换个角度，如果令\mathcal{F}=\{f\mid \mathbb{E}(\mathrm{e}^{f})<+\infty\}，那么

D _ {\mathrm{KL}}(Q\|P)=\sup _ {f\in\mathcal{F}}\big(\mathbb{E} _ Q(f(\mathrm{x}))-\ln\mathbb{E} _ P(\mathrm{e}^{f(\mathrm{x})})\big).

上确界的f^\ast=\ln\frac{\mathrm{d}Q}{\mathrm{d}P}．

这就提供了个对偶视角．

---

可以先证明\ln \mathbb{E} _ {P}(\mathrm{e}^{f(\mathrm{x})})是\mathbb{E} _ Q(f(\mathrm{x}))-D _ {\mathrm{KL}}(Q\|P)的一个上界．

由于假设了Q\ll P，可设g=\mathrm{d}Q/\mathrm{d}P，那么由Jensen不等式

\begin{aligned}
&\mathbb{E} _ Q(f(\mathrm{x}))-D _ {\mathrm{KL}}(Q\|P)\\
={}&\mathbb E _ Q(f)-\mathbb E _ Q (\ln g)=\mathbb{E} _ Q\Big[\ln\frac{\mathrm{e}^f}{g}\Big]\\
\leqslant{}&\ln \mathbb{E} _ Q\Big[\frac{\mathrm{e}^f}{g}\Big]=\ln\mathbb{E} _ P[\mathrm{e}^f].
\end{aligned}

然后考虑取等条件，即\mathrm{e}^f/g=C．此时\mathbb{E} _ Q\ln C=\ln \mathbb{E} _ P(\mathrm{e}^f)，即C=\mathbb{E} _ P(\mathrm{e}^f)．于是最优分布Q^\ast满足\mathrm{d}Q^\ast/\mathrm{d}P=\mathrm{e}^f/C=\mathrm{e}^f/\mathbb{E} _ P(\mathrm{e}^f)．

当f是变动的，取等变为\mathrm{e}^f=C\frac{\mathrm{d}Q}{\mathrm{d}P}，那么f=\ln C+\ln\frac{\mathrm{d}Q}{\mathrm{d}P}，注意到原式在f相差一个常数项时保持不变，因此可令C=0，f=\ln\frac{\mathrm{d}Q}{\mathrm{d}P}．

Bernoulli分布的KL散度

设有两个参数分别为p,q的Bernoulli分布，它们之间的KL散度下面记为d(p,q)．

d(p,q)=p\ln\frac{p}{q}+(1-p)\ln\frac{1-p}{1-q}.

下界

由Pinsker不等式，d(p,q)有下界

d(p,q)=p\ln\frac pq+(1-p)\ln\frac{1-p}{1-q}\geqslant 2(p-q)^2.

命题：固定p，对q\geqslant p，有

d(p,q)\geqslant\frac{(p-q)^2}{2q}.

简单推导

设q>p，注意到p\ln p/q可以用积分表示，

\begin{aligned}
&d(p,q)=p\int _ q^p\frac{\mathrm{d}t}{t}+(1-p)\int _ {1-q}^{1-p}\frac{\mathrm{d}t}{t}\\
={}&p\int _ q^p\frac{\mathrm{d}t}{t}-(1-p)\int _ {q}^{p}\frac{\mathrm{d}t}{1-t}=\int _ q^p\frac{p(1-t)-t(1-p)}{t(1-t)}\, \mathrm{d}t\\
={}&\int _ p^q\frac{t-p}{t(1-t)}\, \mathrm{d}t.
\end{aligned}

对t\in(p,q)，t(1-t)<t<q，因此

d(p,q)>\int _ p^q\frac{t-p}{q}\, \mathrm{d}t=\frac{(q-p)^2}{2q}.

命题：函数d(p,q)都任意一个参数（p或q）的单调性都是先减后增，最小值0在p=q时取到．若q固定，p趋于0或1，d(p,q)趋于有限值；若p固定，q趋于0或1，d(p,q)趋于+\infty．

可以定义

d^{-1}(p;c)=\sup\{q\in[0,1]\mid d(p,q)\leqslant c\}.

命题：设c\in[0,1]，那么

d^{-1}(p;c)\leqslant p+c+\sqrt{c^2+2cp}\leqslant p+\sqrt{2pc}+2c.

利用前面命题的下界，d(p,q)\leqslant c（q>p）时，有(q-p)^2/(2q)\leqslant c，q^2-2(c+p)q+p^2\leqslant 0，q\leqslant p+c+\sqrt{c^2+2cp}．

上界

KL散度的一个上界是\chi^2散度．

定义：两个分布P,Q如果P\ll Q，则\chi^2散度定义为

D _ {\chi^2}(P\|Q)=\mathbb{E} _ Q\Big[\Big(\frac{\mathrm{d}P}{\mathrm{d}Q}-1\Big)^2\Big]=\mathbb{E} _ Q\Big(\frac{\mathrm{d}P}{\mathrm{d}Q}\Big)^2-1.

如果有概率函数p(x),q(x)，那么可知

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

定理：D _ {\mathrm{KL}}(P\|Q)\leqslant D _ {\chi^2}(P\|Q)，这是因为（由\ln x\leqslant x-1）

\begin{aligned}
&D _ {\mathrm{KL}}(P\|Q)=\mathbb{E} _ Q\Big[\frac{\mathrm{d}P}{\mathrm{d}Q}\ln\frac{\mathrm{d}P}{\mathrm{d}Q}\Big]\\
\leqslant{}&\mathbb{E} _ Q\Big(\frac{\mathrm{d}P}{\mathrm{d}Q}\Big)^2-\mathbb{E} _ Q\frac{\mathrm{d}P}{\mathrm{d}Q}=D _ {\chi^2}(P\|Q).
\end{aligned}

下面的定理给出了Bernoulli参数分别为样本均值和总体均值时KL散度的上界，比较经典的结果．

定理：令\mathrm{x} _ i\in[0,1]，i=1,\dots,n，是n个独立的变量，样本均值\mathrm{s}=\frac1n\sum \mathrm{x} _ i，总体均值\mu=\mathbb{E}(\mathrm{x} _ i)．那么，

\mathbb{E}[\exp(n\cdot d(\mathrm{s},\mu))]\leqslant 2+C\sqrt n.

有估计\mathbb{E}[\exp(n\cdot d(\mathrm{s},\mu))]\sim \sqrt n：成立不等式\sqrt n\leqslant\mathbb{E}[\exp(n\cdot d(\mathrm{s},\mu))]\leqslant 2\sqrt n，只对几个小n不成立．

证明需要比较细致的分析．

首先将\mathrm{x} _ i的分布化归到Bernoulli分布．由KL散度的凸性（可知D _ {\mathrm{KL}}(\cdot\|Q)是定义在单纯形上的凸函数），而p\mapsto [p,1-p]是仿射变换，因而复合起来，可知d(p,q)对p是凸函数．所以，d(\mathrm{s},\mu)对\mathrm{x} _ i是凸函数．把这个函数记为x _ i\mapsto \varphi(x _ i)，那么\varphi(x)=\varphi[(1-x)\cdot0+x\cdot 1]\leqslant(1-x)\varphi(0)+x\varphi(1)，于是\mathbb{E}\varphi(\mathrm{x} _ i)\leqslant (1-\mu)\varphi(0)+\mu\varphi(1)．右边正是\mathbb{E} _ {\mathrm{y} _ i\sim \mathrm{Bernoulli}(\mu)}\varphi(\mathrm{y} _ i)，这表明把\mathrm{x} _ i的分布换成\mathrm{Bernoulli}(\mu)，期望增加．

因此最终只需要考虑n个i.i.d的\mathrm {Bernoulli}(\mu)的变量，不妨仍记为\mathrm{x} _ i．此时n\mathrm{s}=\sum \mathrm{x} _ i\sim \mathrm{Binomial}(n,\mu)．具体计算，\mathbb{E}[\exp(n\cdot d(\mathrm{s},\mu))]为

\begin{gathered}
\sum _ {k=0}^n\binom{n}{k}\mu^k(1-\mu)^{n-k}\exp\Big\{n \frac kn\ln\frac{k}{n\mu}+n\Big(1-\frac{k}{n}\Big)\ln\frac{n-k}{n(1-\mu)}\Big\}\\
=\sum _ {k=0}^n\binom{n}{k}\Big(\frac{k}{n}\Big)^k\Big(\frac{n-k}{n}\Big)^{n-k}
=2+\sum _ {k=1}^{n-1}\binom{n}{k}\frac{k^k(n-k)^{n-k}}{n^n}.
\end{gathered}

每一项都可以用阶乘的Stirling-Robbins估计：

\sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{\frac{1}{12n+1}} \lt n! \lt \sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{\frac{1}{12n}}.

下面采用的是弱化些的版本，将指数上下界的(\frac1{12n+1},\frac1{12n})换为(0,\frac1{4n})．

下面证明这个版本．

令a _ n=n!\mathbin/(\sqrt{2\pi n}(n/e)^n)，比值是

\begin{gathered}
\frac{a _ {n+1}}{a _ n}=\frac{n+1}{\sqrt{\frac{n+1}{n}}\frac{(n+1)^{n+1}}{n^n\mathrm{e}}}=\frac{\mathrm{e}}{(1+1/n)^{n+1/2}}\\
\ln\frac{a _ n}{a _ {n+1}}=\Big(n+\frac12\Big)\ln\Big(1+\frac1n\Big)-1.
\end{gathered}

利用不等式\frac{1}{n+1/2}<\ln(1+1/n)<\frac12(\frac1n+\frac{1}{n+1})，得

\begin{gathered}
\begin{aligned}
0&<\Big(n+\frac12\Big)\ln\Big(1+\frac1n\Big)-1\\
&<\frac12\Big(n+\frac12\Big)\Big(\frac1n+\frac{1}{n+1}\Big)-1\\
&=-\frac12+\frac{n}{2(n+1)}+\frac{1}{4n}+\frac{1}{4(n+1)}\\
&=\frac{1}{4n}-\frac{1}{4(n+1)}.
\end{aligned}\\
1<\frac{a _ n}{a _ {n+1}}<\exp\Big(\frac{1}{4n}-\frac{1}{4(n+1)}\Big).
\end{gathered}

如果令b _ n=a _ n/\exp(\frac1{4n})，那么\{b _ n\}是递增数列，且极限与\{a _ n\}相同，都是1．上式还表明\{a _ n\}递减趋于1，故b _ n\lt 1\lt a _ n，此即1\lt a _ n\lt \exp(\frac1{4n})．

利用这个估计，

\begin{gathered}
\frac{n!}{n^n}=\sqrt{2\pi n}\frac{1}{\mathrm{e}^n}\exp\Big(\frac{\theta _ n}{4n}\Big),\quad 0<\theta _ n<1.\\
\binom{n}{k}\frac{k^k(n-k)^{n-k}}{n^n}=\frac{n!}{k!(n-k)!}\frac{k^k(n-k)^{n-k}}{n^n}\\
=\frac{1}{\sqrt{2\pi k(1-\frac kn)}}\exp\Big(\frac{\theta _ n}{4n}-\frac{\theta^\prime _ k}{4k}-\frac{\theta^{\prime\prime} _ {n-k}}{4(n-k)}\Big)\\
<\frac{1}{\sqrt{2\pi n\frac kn(1-\frac kn)}}\exp\Big(\frac{1}{4n}\Big).
\end{gathered}

于是要计算1/\sqrt{\frac kn(1-\frac kn)}的求和．这个k/n的函数在(0,\frac 12)递减，在(\frac 12,1)递增，不难看出n为奇数或偶数时都有

\begin{gathered}
\frac1n\sum _ {k=1}^{n-1}\frac{1}{\sqrt{\frac kn(1-\frac kn)}}<\int _ 0^1\frac{1}{\sqrt{x(1-x)}}\, \mathrm{d}x\\
=\Beta\Big({\frac12},\frac12\Big)=\frac{\Gamma(\frac12)\Gamma(\frac12)}{\Gamma(1)}=\pi.\\
\mathbb{E}<2+\mathrm{e}^{1/(4n)}\sqrt\frac{n\pi}{2}.
\end{gathered}

如果是Robbins估计，上面的指数系数可以优化到1．

参数化

利用KL散度的Donsker-Varadhan变分表示，可以用参数化的方式来表示d(p,q)．

设f(x)=kx，那么\mathrm{x}\sim\mathrm{Bernoulli}(q)时，\mathbb{E}f(\mathrm{x})=kq；当\mathrm{x}\sim \mathrm{Bernoulli}(p)时，\mathbb{E}\mathrm{e}^{f(\mathrm{x})}=p\, \mathrm{e}^{k}+1-p．于是

\begin{aligned}
d(q,p)&=\sup _ f \big(\mathbb{E} _ Q(f(\mathrm{x}))-\ln\mathbb{E} _ P(\mathrm{e}^{f(\mathrm{x})})\big)\\
&=\sup _ f \big(kq-\ln(1-p+p\, \mathrm{e}^k)\big).
\end{aligned}

上确界的f^\ast=\ln\frac{\mathrm{d}Q}{\mathrm{d}P}+c．那么f(1)=\ln (q/p)+c，f(0)=\ln[(1-q)\mathbin/(1-p)]+c，所以最优k是\ln\frac{q(1-p)}{p(1-q)}．

命题：考虑n个独立的随机变量\mathrm{x} _ i，满足\mathrm{x} _ i\in[0,1]，样本均值\mathrm{s}=\frac1n\sum \mathrm{x} _ i，总体均值\mu=\mathbb{E}(\mathrm{x} _ i)，那么

\begin{gathered}
d _ k(q,p):=kq-\ln(1-p+p\, \mathrm{e}^k).\\
\mathbb{E}[\exp(n\cdot d _ k(\mathrm{s},\mu))]\leqslant 1.
\end{gathered}

可以很快地推导出来．由指数函数的凸性，\exp(ks)\leqslant (1-s)\mathrm{e}^0+s\, \mathrm{e}^k，两边同除右边，n次方后取期望，就得到上式．