台交大信息论 Lecture 5

课程主页:https://ocw.nctu.edu.tw/course_detail-c.php?bgid=8&gid=0&nid=612&pid=973

http://shannon.cm.nctu.edu.tw/it18.htm

老师主页:http://shannon.cm.nctu.edu.tw/

课程视频:https://www.youtube.com/playlist?list=PLj6E8qlqmkFsWS54o6gNWeDGXeI7c3eUd

这次回顾第五讲,这一讲主要介绍了Fano不等式以及KL散度,对应视频9-11。

Fano不等式

令$X,Y$为两个相关随机变量,$X$取值于$\mathcal X$,$Y$取值于$\mathcal Y$,$\mathcal X$有限,$\mathcal Y$可数无限。假设$\hat{X}:=g(Y)$为通过观测$Y$得到对于$X$的估计,其中$g: \mathcal{Y} \rightarrow \mathcal{X}$是给定的估计函数。定义误差概率

那么如下不等式成立

其中

证明1

证明:

定义

那么利用条件熵的链式法则可得

注意$X,Y$可以唯一确定$E$,所以

此时上述等式化为

利用条件熵小于等于无条件熵,我们可得

对于另一项,首先有

其次回顾如下不等式

注意在$E=1$的条件下,$X$共有$|\mathcal X| -1$的可选值,因此

所以

结合上述两个部分我们有

证明2

证明:

注意到$X \rightarrow Y \rightarrow \hat{X}$是马氏链,利用数据压缩定理可得

利用互信息的定义可得

如果能证明

那么原不等式即可得证。

注意到

以及

我们得到

KL散度和变分距离

KL散度

随机变量$X,\hat X$定义在集合$\mathcal X$,那么KL散度$D(X | \hat{X})$或$D\left(P_{X} | P_{\hat{X}}\right)$定义为

备注:KL散度也称为相对熵。

非负性

等号成立当且仅当$P_{X}(x)=P_{\hat{X}}(x)$对所有$x \in \mathcal{X}$。

证明:

等号成立当且仅当

互信息和KL散度

利用定义不难看出

因为

分布的细化

给定定义在$\mathcal X$上的分布$P_{X}$,将$\mathcal X$划分为$k$个不相交集合$\mathcal{U}_{1}, \mathcal{U}_{2}, \ldots, \mathcal{U}_{k}$,满足

定义一个新的分布$P_{U}$,该分布取值于$\mathcal{U}=\{1,2, \ldots, k\}$,其中

那么$P_X$被称为$P_U$的细化($k-$细化)。

细化不会减少散度

令$P_X$和$P_{\hat X}$为$P_U$和$P_{\hat U}$的细化($k-$细化),那么

证明:

首先对任意$i \in\{1,2, \ldots, k\}$,我们有

等号成立当且仅当

因此

等号成立当且仅当对所有$i$以及$x\in \mathcal U_i$

变分距离

分布$P_{X}$和$P_{\hat{X}}$定义在相同集合$\mathcal{X}$,两个分布的变分距离定义为

变分距离满足如下性质

证明:

变分距离和散度的关系:Pinsker不等式

证明:

1.定义

那么

2.定义随机变量

那么$P_X,P_{\hat X}$是$P_U, P_{\hat U}$的细化,由之前的定理可得

3.证明

那么上述不等式等价于

求导即可证明结果。

上界

如果$D\left(P_{X} | P_{\hat{X}}\right)<\infty$,那么

这里不提供证明。

条件散度

给定$Z$,$X$和$\hat X$的条件散度为:

给定$P_Z$,$P_{X|Z}$和$P_{\hat X}$的条件散度定义为:

条件互信息和条件散度的关系
链式法则

$P_{X^n}$和$Q_{X^n}$是定义在$\mathcal X^n$上的概率分布,那么

更一般的,我们有

其中$i=1$时,

证明:

利用概率的链式法则即可。

条件不减少散度

证明:

等号成立当且仅当对任意$x, z$

独立性不增加散度

$X$独立于$Z$,$\hat X$独立于$\hat Z$,那么

独立性的可加性

$X$独立于$Z$,$\hat X$独立于$\hat Z$,那么

信息度量的凹凸性

常用结论

下面介绍几个常用结论,部分证明从略。

1

$H(P_X)$关于$P_X$是凹函数,即对于所有$\lambda \in [0,1]$

等号成立当且仅当对所有$x$,都有$P_{X}(x)=P_{\tilde{X}}(x)$

证明:

利用如下函数为凹函数即可证明:

2

互信息的定义为

将$I(X;Y)$重写为

那么,对于固定的$P_{Y | X}$,$I(X ; Y)$关于$P_X$是凹函数,即

等号成立当且仅当对于任意$y \in \mathcal{Y}$,

对于固定的$P_X$,$I(X ; Y)$关于$P_{Y|X}$是凸函数,即

等号成立当且仅当

3

$D\left(P_{X} | P_{\hat{X}}\right)$关于$\left(P_{X}, P_{\hat{X}}\right)$是凸函数,即

等号成立当且仅当

假设检验

形式

$X_{1}, \ldots, X_{n}$是一列观测值,观测值属于分布$P_{X^{n}}$(零假设)或分布$P_{\hat{X}^{n}}$(备择假设)。假设表示为

定义决策映射

接受域

错误种类

贝叶斯假设检验

根据下式选择$\phi$

NP引理

对于假设检验问题,通过似然比定义接受域

那么对于其他任意接受域$\mathcal B$以及对应的第一类错误$\alpha_n$,第二类错误$\beta_n$,我们有

证明:

等号成立当且仅当

Chernoff-Stein引理

iid序列$X^{n}$属于分布$P_{X^{n}}$(零假设)或分布$P_{\hat{X}^{n}}$(备择假设),$\forall \varepsilon\in (0,1)$,最佳第二类错误满足,

其中$\beta_{n}^{*}(\varepsilon)=\min _{\alpha_{n} \leq \varepsilon} \beta_{n}$

证明:

首先证明存在接受域满足

步骤1:定义典型散度集:

在上述集合中的$x^n$满足

步骤2:计算第一类错误

根据大数定律,我们有

因此对于充分大的$n$,我们有

步骤3:计算第二类错误

因此

这推出

由$\delta > 0$的任意性,我们可得

接着证明反方向的不等式,即对于任意满足

第二类错误都满足

事实上,我们有

因此

这说明

由$\delta >0$的任意性可得

瑞利信息度量

瑞利熵

给定参数$\alpha > 0,\alpha\neq 1$,给定离散随机变量$X$以及分布$P_X$,$X$取值于空间$\mathcal X$,阶数为$\alpha$的瑞利熵为

瑞利散度

引理

证明:

利用洛必达法则即可。

本文标题:台交大信息论 Lecture 5

文章作者:Doraemonzzz

发布时间:2020年07月13日 - 21:56:00

最后更新:2020年07月20日 - 18:07:23

原始链接:http://doraemonzzz.com/2020/07/13/台交大信息论 Lecture 5/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。