2.1 Entropy

编码：必须唯一可解，不出现歧义
Huffman编码
Prefix-free codes:前缀码。有一组code words $c_{1}c_{2}\dots c_{n}$,$\forall c_{i},c_{j}(i\neq j)$使得$c_{i},c_{j}$都不互为前缀。前缀码是可唯一解码的。
克拉夫特不等式：设符号表原始符号为

$$S=\{s_{1},s_{2},\dots,s_n\}$$

^ee60fa

在大小为$r$的字符集熵编码为可唯一解码的码字长度为$\ell_{1},\ell_{2},\dots,\ell _{n}$，则

$$\sum_{i=1}^n r^{-\ell_{i}}\leq 1$$

Definition: The entropy $H(X)$ of a discrete random variable $X$ is defined by

$$H(X) = -\sum_{x\in \mathscr{H}}p(x)\log p(x)= E_{p}\log \frac{1}{p(X)}$$

其中$E_{p}$代表$X$的概率分布为$p$时后面函数的期望：

$$E_{p}g(X)=\sum_{x \in \mathscr{H}}g(x)p(x)$$

Lemma:

1. $H(X)\geq 0$
2. $H_{b}(X)=(\log_{b}a)H_{a}(X)$

2.2 Joint Entropy, Conditional Entropy

Definition: Joint Entropy

$$H(X,Y)=-\sum_{x\in\mathscr{H}}\sum_{y\in\mathscr{y}}p(x,y)\log p(x,y)=-E\log p(X,Y)$$

Conditional Entropy:
If $(X,Y)\sim p(x,y)$, then the conditional entropy $H(Y|X)$ is defined as:

$$\begin{align} H(Y|X) & =\sum_{x\in\mathscr{H}}p(x)H(Y|X=x) \\ & =-\sum_{x\in \mathscr{H}}p(x)\sum_{y\in \mathscr{Y}}p(y|x)\log p(y|x) \\ & =-\sum_{x\in \mathscr{H}}\sum_{y\in \mathscr{Y}}p(x,y)\log(p(y|x)) \\ & = -E_{p(x,y)}\log p(Y|X) \end{align}$$

Theorem(Chain rule):

$$H(X,Y) = H(X)+H(Y|X)$$

Corollary:

$$H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$$

2.3 Relative Entropy and Mutual Information

Relative Entropy definition:

$$\begin{align} D(p\mid \mid q) & = \sum_{x\in\mathscr{H}}p(x)\log \frac{p(x)}{q(x)} \\ & =E_{p}\log \frac{p(X)}{q(X)} \end{align}$$

We used convention that $0\log \frac{0}{q}=0,p\log \frac{p}{0}=\infty$

性质：

1. 非负性，且$D(p | |q)=0\Leftrightarrow p=q$
2. 非对称，不满足三角不等式

Mutual information: relative entropy between the joint distribution and the product distribution

$$I(X;Y)=\sum_{x\in \mathscr{H}}\sum_{y\in \mathscr{Y}}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$$

例子：当$X,Y$独立，$p(x,y)=p(x)p(y)$,则$I(X,Y)=0$

熵和共同信息之间的关系：
容易验证

$$I(X;Y)=H(Y)-H(Y|X)$$

由上一节的$H(X,Y) = H(X)+H(Y|X)$，有

$$I(X;Y)=H(X)+H(Y)-H(X,Y)$$

当$Y=X$时，$I(X;X)=H(X)+H(X)-H(X|X)=H(X)$

相对熵不是真正的距离度量。首先是非对称性：$D(p_{X_{1}}\mid p_{X_{2}})\neq D(p_{X_{2}}\mid p_{X_{1}})$。而且，当$\exists X=x \ \text{such that}\ p_{X_{1}}(x)\neq 0,p_{X_{2}}(x)=0$时，相对熵会发散。但是，我们还是经常将其看成一种对概率分布距离的反映。而且，相对熵与概率的距离度量有紧密联系。比如，

$$D(p_{X}\mid\mid p_{Y})\geq \frac{1}{2\ln 2} \mid\mid p_{X}-p_{Y}\mid\mid_{1}^2$$

其中$\mid\mid p_{X}-p_{Y}\mid\mid_{1}=\sum_{a}\mid p_{X}(a)-p_{Y}(a)\mid$

2.5 Chain Rules for Entropy, Relative Entropy and Mutual Information

1. 熵的链式法则：
   $X_{1},X_{2},\dots,X_{n}$的联合分布为$p(x_{1},\dots,x_{n})$，则

   $$H(X_{1},X_{2},\dots,X_{n})=\sum_{i=1}^{n}H(X_{i}|X_{i-1},\dots,X_{1})$$

   Conditional mutual information:

   $$I(X;Y|Z)=H(X|Z)-H(X|Y,Z)$$

2. 信息的链式法则：

   $$I(X_{1},X_{2},\dots,X_{n};Y)=\sum_{i=1}^nI(X_{i};Y|X_{i-1},X_{i-2},\dots,X_{1})$$

   Conditional Relative Entropy:

   $$D(p(y|x)\mid\mid q(y|x))=\sum_{x}p(x)\sum_{y}p(y|x)\log \frac{p(y|x)}{q(y|x)}$$

3. 相对熵的链式法则：

$$D(p(x,y)\mid\mid q(x,y))=D(p(x)\mid\mid q(x))+D(p(y|x)\mid\mid q(y|x))$$

Proof:

$$\begin{align} D(p(x,y)\mid\mid q(x,y)) & =\sum_{x}\sum_{y}p(x,y)\log \frac{p(x,y)}{q(x,y)} \\ & =\sum_{x}\sum_{y}p(x,y) \log \frac{p(x)p(y\mid x)}{q(x)q(y\mid x)} \\ & = \sum_{x}\sum_{y}p(x,y)\log \frac{p(x)}{q(x)} + \sum_{x}\sum_{y}p(x,y)\log \frac{p(x)}{q(x)} \\ & = D(p(x)\mid \mid q(x) )+ D(p(y|x)\mid\mid q(y|x)) \end{align}$$

2.6 Jensen Inequality and its Consequences:

下凸（Convex）函数：$f''(x)>0$
上凸(Concave，凹)函数：$f''(x)<{0}$

推论（共同信息非负）: $I(X;Y)=D(p(x,y)\mid\mid p(x)p(y))\geq 0$,上式为0当且仅当$X,Y$独立
推论: $D(p(y|x)\mid\mid q(y|x))\geq 0$，上式为0当且仅当$p(y|x)=q(y|x),\forall x,y,p(x)>0$
推论: $I(X;Y|Z)\geq 0$，上式为0当且仅当给定Z条件下$X,Y$相互独立。

下面证明，在概率空间$\mathscr{H}$上均匀分布的概率分布有最大的熵。
Theorem 2.6.4: $H(X)\leq \log|\mathscr{H}|$，其中$|\mathscr{H}|$代表了$X$的取值的元素个数。上式取等号当且仅当$X$是在$\mathscr{H}$上的均匀分布。
proof: let $u(x)=\frac{1}{|\mathscr{H}|}$，$p(x)$为$X$的概率分布函数，则

$$D(p\mid\mid u)=\sum p(x)\log \frac{p(x)}{u(x)} = \log |\mathscr{H}|-H(X)\geq 0$$

得证。

Theorem 2.6.5(条件约化熵)：

$$H(X|Y)\leq H(X)$$

上式取等号当且仅当$X,Y$独立。
proof: $0\leq I(X;Y)=H(X)-H(X|Y)$

Theorem 2.6.6: $H(X_{1},X_{2},\dots,X_{n})\leq \sum_{i=1}^n H(X_{i})$，上式取等当且仅当各个$X_{i}$之间相互独立

2.7 The Log Sum Inequality and its Applications

Theorem 2.7.1(Log sum inequality): 对于非负的$a_{1},a_{2},\dots,a_{n}$和$b_{1},b_{2},\dots,b_{n}$,

$$\sum_{i=1}^n a_{i}\log \frac{a_{i}}{b_{i}} \geq \left( \sum_{i=1}^n a_{i} \right)\log \frac{ \sum_{i=1}^n a_{i} }{\sum_{i=1}^n b_{i}}$$

取等条件为$\frac{a_{i}}{b_{i}}=\text{const}$
proof: $f(t)= t\log t$ is strictly convex, so

$$\sum_{i}\alpha_{i}t_{i}\log t_{i} \geq\left( \sum_{i}\alpha_{i}t_{i} \right)\log \sum_{i}\alpha_{i}t_{i}$$

令$\alpha_{i}=\frac{a_{i}}{\sum_{j}b_{j}},t_{i}=\frac{a_{i}}{b_{i}}$即可得证。
我们可以用log sum inequality 去证明很多凸性得到的结果，例如上面的”相对熵非负“这个定理。

Theorem 2.7.2:$D(p\mid \mid q)$ 对于pair $(p,q)$而言是凸的。换言之，若$(p_{1},q_{1}),(p_{2},q_{2})$是两对概率分布函数，那么

$$D(\lambda p_{1}+(1-\lambda)p_{2}\mid\mid\lambda q_{1}+(1-\lambda)q_{2})\leq\lambda D(p_{1}\mid\mid q_{1})+(1-\lambda)D(p_{2}\mid\mid q_{2})$$

for all $0\leq\lambda\leq 1$

Proof:
对左侧应用log sum inequality,即$a_{1}=\lambda p_{1},a_{2}=(1-\lambda)p_{2},b_{1}=\lambda p_{1},b_{2}=(1-\lambda)q_{2}$

$$\begin{aligned} \left(\lambda p_1(x)+(1\right. & \left.-\lambda) p_2(x)\right) \log \frac{\lambda p_1(x)+(1-\lambda) p_2(x)}{\lambda q_1(x)+(1-\lambda) q_2(x)} \\ & \leq \lambda p_1(x) \log \frac{\lambda p_1(x)}{\lambda q_1(x)}+(1-\lambda) p_2(x) \log \frac{(1-\lambda) p_2(x)}{(1-\lambda) q_2(x)} \end{aligned}$$

对x求和即可得证。

Theorem 2.7.3(Concavity of entropy)
$H(p)$是p的凹函数。
Proof：

$$H(p)= \log|\mathscr{H}|-D(p\mid\mid u)$$

其中$u$是$|\mathscr{H}|$个结果上均匀分布的分布函数。因此函数H的凹性直接源于函数D的凸性。
或：取随机变量$X_{1},X_{2}$使得$X_{1}\sim p_{1}(x),X_{2}\sim p_{2}(x)$，并令$Z=X_{\theta}$，随机变量$\theta$满足的分布为：

$$\theta = \begin{cases} 1 & p=\lambda \\ 2 & p=1-\lambda \end{cases}$$

于是$Z\sim\lambda p_{1}+(1-\lambda)p_{2}$。由于条件（Conditioning）会减少熵，于是有

$$H(Z)\geq H(Z|\theta)$$

或等价地，

$$H(\lambda p_{1}+(1-\lambda)p_{2})\geq\lambda H(p_{1})+(1-\lambda)H(p_{2})$$

Theorem 2.7.4: 令$(X,Y)\sim p(x,y) = p(x)p(y\mid x)$。共同信息$I(X;Y)$在固定的$p(y\mid x)$下是$p(x)$的凹函数，在固定$p(x)$的情况下是$p(y\mid x)$的凸函数。
证明：

1. $I(X;Y)=H(Y)-H(Y|X)=H(Y)-\sum_{x}p(x)H(Y\mid X=x)$.
   若$p(y\mid x)$固定，那么$p(y)\propto p(x)$，而$H(Y)$是凹函数，第二项成正比，从而$I$此时是凹函数。
2. 固定$p(x)$,考虑两个条件分布$p_{1}(y\mid x),p_{2}(y\mid x).$对应的联合分布为$p_{i}(x,y)=p(x)p_{i}(y\mid x),i=1,2$，对应的边缘分布为$p(x),p_{1}(y);p(x),p_{2}(y)$.
   考虑二者的混合条件分布：
   $$
   p_{\lambda}(y\mid x)=\lambda p_{1}(y\mid x)+(1-\lambda)p_{2}(y\mid x)
   $$
   则联合分布为：$p_{\lambda}(x,y)=\lambda p_{1}(x,y)+(1-\lambda)p_{2}(x,y)$，$Y$的分布也是二者混合：

   $$p_{\lambda}(y)=\lambda p_{1}(y)+(1-\lambda)p_{2}(y)$$

   如果令$q_{\lambda}(x,y)=p(x)p_{\lambda}(y)$为边缘分布之积，就有

   $$q_{\lambda}(x,y)=\lambda q_{1}(x,y)+(1-\lambda)q_{2}(x,y)$$

   由于共同信息就是$p_{\lambda}$与$q_{\lambda}$之间的相对熵，即：$I(X;Y)=D(p_{\lambda}\mid\mid q_{\lambda})$
   相对熵是p,q的凸函数，因此$I(X,Y)$在该条件下也是凸的。

2.8 Data Processing Inequality

数据处理不等式可被用来证明，对数据的任何操作都不能提高我们从数据中得出的推断能力。

定义：随机变量$X,Y,Z$被称为按顺序构成马尔可夫链（记作$X\to Y\to Z$），若Z的条件分布只取决于Y，且Y的条件分布只取决于X，即$p(x,y,z)=p(x)p(y\mid x)p(z\mid y)$
一些简单的推论：

1. $X\to Y\to Z$当且仅当$X,Z$给定Y下条件独立，即$p(x,z\mid y)=p(x\mid y)p(z\mid y)$
2. $X\to Y\to Z$隐含着$Z\to Y\to X$
3. $Z=f(Y)\implies X\to Y\to Z$

我们可以证明一个重要也很实用的定理：对Y的任何（确定性或随机的）处理都不能提高Y中包含X的信息。
Theorem 2.8.1: If $X\to Y\to Z$, then $I(X;Y)\geq I(X;Z)$
根据链式法则，

$$\begin{align} I(X;Y,Z)&=I(X;Z)+I(X;Y\mid Z) \\ &=I(X;Y)+I(X;Z\mid Y) \end{align}$$

由于上述性质1，$I(X;Z|Y)=0$，又$I(X;Y|Z)\geq0$，则 $I(X;Y)\geq I(X;Z)$

推论：$Z=g(Y)$，那么$I(X;Y)\geq I(X;g(Y))$。只需知道$X\to Y\to g(Y)$就行。
推论2：$X\to Y\to Z\implies I(X;Y\mid Z)\leq I(X;Y)$
应注意，当XYZ不构成马尔可夫链时有可能$I(X;Y|Z)>I(X;Y)$。例如，X,Y分别为独立抛硬币的结果，令$Z=X+Y$。那么$I(X;Y)=0$（XY独立），但是

$$I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)=\frac{1}{2}\text{bit}$$

2.9 热力学第二定律

热力学第二定律的其中一种表述为：孤立系统的熵永不减少。在统计物理中，熵通常用系统微观态数目的对数定义。这和我们对熵的定义相同，如果每个态都等概率的话。但为什么系统熵会增加呢？
我们可以使用马尔可夫链的建模来进行解释。我们假设已知当前状态时，系统的未来状态与过去状态独立。

1. 设$\mu_{n},\mu _{n'}$时两个n时刻的马尔可夫链的状态空间上的分布函数。于是$p(x_{n},x_{n+1})=p(x_{n})r(x_{n+1}\mid x_{n}),q(x_{n},x_{n+1})=q(x_{n})r(x_{n+1}\mid x_{n})$，于是

   $$\begin{aligned} & D\left(p\left(x_n, x_{n+1}\right) \| q\left(x_n, x_{n+1}\right)\right) \\ & \quad=D\left(p\left(x_n\right) \| q\left(x_n\right)\right)+D\left(p\left(x_{n+1} \mid x_n\right) \| q\left(x_{n+1} \mid x_n\right)\right) \\ & \quad=D\left(p\left(x_{n+1}\right) \| q\left(x_{n+1}\right)\right)+D\left(p\left(x_n \mid x_{n+1}\right) \| q\left(x_n \mid x_{n+1}\right)\right) \end{aligned}$$

   后两等号中第一个右侧为0，又相对熵恒非负，所以
   $D(\mu_{n}\mid\mid \mu_{n}')\geq D(\mu_{n+1}\mid\mid \mu_{n+1}')$
2. 相对稳定点的熵逐渐减小。如果取$\mu_{n}'$为稳定点$\mu$，那么$D(\mu _n\mid\mid \mu)\geq D(\mu_{n+1}\mid\mid \mu)$，即演化过程中状态不断靠近稳态。
3. 若稳态分布是均匀的，那么熵增加。一般来讲相对熵减小不意味着熵增加，最典型的例子是一个非均匀分布作为稳态的马尔可夫链。但若稳态分布是均匀分布，那么

   $$D(\mu_{n}\mid \mu)=\log|\mathscr{H}|-H(\mu_{n})=\log|\mathscr{H}|-H(X_{n})$$

   此时相对熵单减意味着熵单增。

定义概率转移矩阵的双随机性(doubly sthochastic)：
概率转移矩阵$[P_{i j}],P_{i j} = \text{Pr}\{X_{n+1}=j|X_{n}=i\}$是双随机的，若

$$\begin{align} \sum_{i}P_{i j} = 1, & j=1,2,\dots \\ \sum_{j}P_{i j }= 1, & i=1,2,\dots \end{align}$$

A stochastic process Y is stationary if the moments are not affected by a time shift.
Remark: The uniform distribution is a stationary distribution of P if and only if the probability transition matrix is doubly stochastic.

4. The conditional entropy $H(X_{n}|X_{1})$ increases with n for a stationary Markov process.
   If a Markov process is stationary, then $H(X_{n})$ is constant. So the entropy is nonincreasing. However ,we'll prove that $H(X_{n}\mid X_{1})$ increases with $n$. Thus the conditional unceertainty of the future increases.
   proof:

   $$\begin{aligned} H\left(X_n \mid X_1\right) & \geq H\left(X_n \mid X_1, X_2\right) & & \text { (conditioning reduces entropy) } \\ & =H\left(X_n \mid X_2\right) & & \text { (by Markovity) } \\ & =H\left(X_{n-1} \mid X_1\right) & & \text { (by stationarity). } \end{aligned}$$

5. Shuffles increase entropy. If $T$ is a shuffle of a deck of cards and $X$ is the initial random position of the cards in the deck and if the choice of the shuffle $T$ is independent of X, then $H(TX)\geq H(X)$, where $TX$ is the permutation of the deck induced by the shuffle $T$ on the initial permutation $X$.

2.10 Sufficient Statistics

这一节我们将看到数据处理不等式在说明统计学重要问题上的威力。
设我们有一族以$\theta$为下标的概率分布函数$\{f_{\theta}(x)\}$,令$X$是它的一个采样。令$T(X)$为$X$的统计量，如样本方差或样本平均。那么$\theta\to X\to T(X)$。根据数据处理不等式，有

$$I(\theta ;T(X))\leq I(\theta;X)$$

定义：$T(X)$函数被称为相对函数族$\{f_{\theta}(X)\}$的充分统计量，若$X$在给定$T(X)$下独立于$\theta$，换言之$\theta\to T(X)\to X$构成Markov Chain

例子：

1. 设$X_{1},X_{2},\dots,X_{n}$是独立同分布的掷硬币序列，有一个未知量$\theta=\text{Pr}(X_{i}=1)$，给定n，1的数量是$\theta$的一个充分统计量。我们可以证明，给定$T$，所有具有相同个数1的序列等可能，且独立于$\theta$。

   $$\text{Pr}\left\{ (X_{1},X_{2},\dots,X_{n})=(x_{1},x_{2},\dots x_{n})\mid \sum_{i=1}^n X_{i}=k \right\}=\begin{cases} \frac{1}{C_{n}^k} & \text{if}\sum_{i=1}^n x_{i}=k \\ 0, & \text{otherwise} \end{cases}$$

2. 若$X$是以$\theta$为均值，1为方差的正态分布，

   $$f_{\theta}(X)=\frac{1}{\sqrt{ 2\pi }}\exp{-\frac{(x-\theta)^2}{2}}=\mathscr{N}(\theta,1)$$

   且$X_{1},X_{2},\dots,X_{n}$是独立，具有该分布的，那么$\bar{X}_{n}=\sum_{i=1}^nX_{i}$是$\theta$的一个充分统计。
3. 若$f_{\theta}\sim U(\theta,\theta+1)$，则$\theta$的一个充分统计量为

   $$T(X_{1},X_{2},\dots,X_{n})=(\max \{X_{1},X_{2},\dots X_{n}\},\min\{X_{1},X_{2},\dots,X_{n}\})$$

   最小充分统计量(Minimal sufficient statistic)是其他全部充分统计量的函数构成的充分统计量。
   定义： 一个统计量 $T(X)$ 是相对于 $\{f_{\theta}(X)\}$ 的最小统计量，如果它是其他所有充分统计量$U$的函数. 用数据处理不等式的语言来讲，这意味着

   $$\theta\to T(X)\to U(X)\to X$$

   $T(X)$最大程度地压缩了样本中关于$\theta$的信息。其他统计量中可能包含有额外的无关信息。例如，对有均值$\theta$的正态分布而言，给出奇数样本的平均和偶数样本平均的函数对是充分统计量，但不是最小的。

2.11 Fano's Inequality

设我们已知随机变量$Y$，希望猜测与之关联的$X$.Fano把这种猜测的正确概率与条件熵$H(X\mid Y)$联系起来。在本章的问题中我们可以证明，$H(X\mid Y)=0\Leftrightarrow X=f(Y)$因此当且仅当$H(X\mid Y)=0$,我们可以无误地从$Y$的值猜出$X$的值。
进一步，如果条件熵存在但很小，我们希望能以高概率正确猜出$X$。
设$X\sim p(x)$，$Y$由条件概率$p(y\mid x)$依赖于$X$。从$Y$中，我们计算$g(Y)=\hat{X}$，这是对$X$的一个估计。希望找出$\hat{X}\neq X$的概率。注意到$X\to Y\to \hat{X}$，
定义$P_{e}=\text{Pr}\{\hat{X}\neq X\}$

Theorem (Fano's Inequality):

$$H(P_{e})+P_{e}\log(\mathscr{|H|}-1)\geq H(X\mid Y)$$

或弱化为：$1+P_{e}\log|\mathscr{H}|\geq H(X|Y)$

证明：令

$$E=\begin{cases} 1, & \hat{X}=X \\ 0, & \hat{X}\neq X \end{cases}$$

$$\begin{align} H(E,X\mid Y) & = H(E\mid Y)+H(X\mid E,Y) \leq H(P_{e})+P_{e}\log(|\mathscr{H}|-1) \\ & =H(X\mid Y)+H(E\mid X,Y)=H(X\mid Y) \end{align}$$

Leave a Comment

Plain Markdown

Post Comment

Markdown Preview