1. 概率：q(x)q(x) 表示认为 xx 发生的可能性是多少；
  2. 信息：真正发生 xx 后 −log⁡q(x)-\log{q(x)} 表示这个结果的意外程度；
  3. 交叉熵：真实世界不断产生数据 x∼px\sim p，平均的意外程度；h(p,q)=ep[−log⁡q(x)]h(p, q)=\mathbb{e}_{p}[-\log{q(x)}]，表示按照模型 qq 面对真实的世界 pp，长期平均有多么意外；
  4. 熵：如果模型完美 p=qp=q，仍然存在 h(p)h(p)，这是由于真实世界本身的随机性；
  5. KL 散度：DK(P∣∣Q)=H(P,Q)−H(P)D_{K}(P||Q)=H(P,Q)-H(P)，排除真实世界本身的不可预测性之后，由于模型错误产生的额外意外；

熵和互信息的关系·

相对熵(KL 距离)·

相对熵衡量的是同一事件空间中两个概率分布的差异，不是距离。

在同一事件空间中，概率分布 P(X)P(X) 对应的每个事件如果用 Q(x)Q(x) 编码，平均每个基本事件编码长度增加了多少比特。

用 D(p∣∣q)D(p||q) 表示 KLKL 距离，计算公式为

D(p∣∣q)=∑x∈XP(x)log⁡2P(x)Q(x)D(p||q) = \sum_{x\in X}P(x)\log_2{\dfrac{P(x)}{Q(x)}}

两分布相似度越高，相对熵越小。

  • 非负性（由吉布斯不等式可证）

若 ∑i=1npi=∑i=1nqi=1\displaystyle\sum_{i=1}^{n}p_i=\displaystyle\sum_{i=1}^{n}q_i=1，则 −∑i=1npilog⁡pi≤−∑i=1npilog⁡qi-\displaystyle\sum_{i=1}^np_i\log{p_i}\leq -\displaystyle\sum_{i=1}^np_i\log{q_i}，当且仅当 ∀i,pi=qi\forall i,p_i=q_i​时取等

  • 不满足对称性（交叉熵 −- 相对熵）
  • 不满足三角不等式

数据处理不等式·

如果 ZZ 的条件分布仅依赖 YY 的分布，与 XX 条件独立，随机变量 X,Y,ZX,Y,Z 构成马尔科夫链，满足 I(X;Z∣Y)=0I(X;Z|Y)=0

记为 X→Y→ZX\rightarrow Y\rightarrow Z，则 I(X;Y)≥I(X;Z)I(X;Y)\geq I(X;Z)​。如果 Z=g(Y)Z=g(Y)，则 I(X;Y)≥I(X;g(Y))I(X;Y)\geq I(X;g(Y)).

数据越传损失的越多；数据 YY 的函数不会增加关于 XX 的信息量~

如果 X→Y→ZX\rightarrow Y \rightarrow Z，则 I(X;Y)≥I(X;Y∣Z)I(X;Y)\geq I(X;Y|Z)​。

通过观察 ZZ，XX 与 YY 的依赖会降低~

Fano 不等式·

(+﹏+)~晕，待续……

渐进均分性·

收敛·

  • 收敛：图像逐渐趋近于某条横线

∀ε>0,∃N∈N+\forall \varepsilon > 0, \exist N\in N^+，当 n>Nn>N 时，满足 ∣an−a∣<ε|a_n-a|<\varepsilon，即 lim⁡n→∞∣an−a∣=0\displaystyle\lim_{n\to \infty}{|a_n-a|}=0，记作 an→aa_n\to a

  • 几乎确定收敛：图像逐渐趋近于某条横线，但是有几个点各色

∀ε>0,∃N∈N+\forall \varepsilon > 0, \exist N\in N^+，当 n>Nn>N 时，满足 P(∣an−a∣<ε)=1P(|a_n-a|<\varepsilon)=1，即 P(lim⁡n→∞∣an−a∣≤ε)=1P(\displaystyle\lim_{n\to \infty}{|a_n-a|}\leq \varepsilon)=1

  • 依概率收敛：

δ>0,∃N∈N+\delta>0, \exist N\in N^+，当 n>Nn>N 时，满足 ∣P(∣an−a∣<ε)−1∣≤δ|P(|a_n-a|<\varepsilon)-1|\leq \delta，即 lim⁡n→∞P(∣an−a∣≤ε)=1\displaystyle\lim_{n\to \infty}P({|a_n-a|}\leq \varepsilon)=1，记作 an→Paa_n\stackrel{P}\to a​.

大数定理·

  • 强大数定理：μn\mu_n 一直向 μ\mu 靠近

∀ε>0,P(lim⁡n→∞∣μn−μ∣<ε)=1\forall \varepsilon > 0, P(\displaystyle\lim_{n\to \infty}{|\mu_n-\mu|<\varepsilon})= 1

  • 弱大数定理：μn\mu_n 向 μ\mu 靠近的可能性越来越大

∀ε>0,lim⁡n→∞P(∣μn−μ∣<ε)=1\forall \varepsilon > 0,\displaystyle\lim_{n\to \infty}P({|\mu_n-\mu|<\varepsilon})= 1

渐进均分定理(AEP)·

当序列足够长，其中一部分序列就会显示出某种固定的性质，即各个符号出现的频率接近于概率，而这些序列的的概率则趋近于相等，且它们的和非常接近于 11。这些序列就是 典型序列。其余不具备这种性质的序列，称之为 非典型序列，这些非典型序列的出现概率之和接近于零。序列的长度越长，典型序列的总概率就越接近于 11​，它的各个序列的出现概率越趋近于相等，这种现象称为 渐进均分性。

数学定义为：若 X1,X2,⋯ ,XnX_1,X_2,\cdots,X_n 满足 i.i.di.i.d

1nlog⁡1P(X1,X2⋯ ,Xn)→PH(X)\frac{1}{n}\log{\dfrac{1}{P(X_1, X_2\cdots, X_n)}} \stackrel{P}\to H(X)

典型集·

若 X1,X2,⋯ ,XnX_1,X_2,\cdots,X_n 是概率密度函数为 p(x)p(x) 的 i.i.di.i.d，满足

∣−1nlog⁡P(X1,X2⋯ ,Xn)−H(X)∣≤ε  ⟺  2−n(H(X)+ε)≤P(X1,X2,⋯ ,Xn)≤2−n(H(X)−ε)\begin{aligned} &|-\frac{1}{n}\log{P(X_1, X_2\cdots, X_n)} - H(X)| \leq \varepsilon\\ &\iff 2^{-n(H(X)+\varepsilon)}\leq P(X_1, X_2,\cdots, X_n)\leq 2^{-n(H(X)-\varepsilon)} \end{aligned}

称该序列为典型集，记作 Aε(n)A_{\varepsilon}^{(n)}.

性质

  • 若 x1,x2,⋯ ,xn∈Aε(n)x_1,x_2,\cdots,x_n \in A_{\varepsilon}^{(n)}，则 H(X)−ε≤−1nlog⁡P(X1,X2⋯ ,Xn)≤H(X)+εH(X)-\varepsilon\leq-\frac{1}{n}\log{P(X_1,X_2\cdots,X_n)}\leq H(X)+\varepsilon​
  • ∣Aε(n)∣≤2n(H(X)+ε)|A_{\varepsilon}^{(n)}|\leq 2^{n(H(X)+\varepsilon)}，典型集中的元素个数
  • 当 n→∞n\to \infty 时，P(Aε(n))>1−εP(A_{\varepsilon}^{(n)})>1-\varepsilon
  • 当 n→∞n\to \infty，∣Aε(n)∣≥(1−ε)2n(H(X)−ε)|A_{\varepsilon}^{(n)}|\geq(1-\varepsilon)2^{n(H(X)-\varepsilon)}

数据压缩·

数据压缩时把一个完整的概率空间缩小到典型集，而典型集相对整个空间来说时非常小的，且高概率出现，这就起到了压缩的作用。

典型集的个数很少

如果全空间有 nn 个元素，根据性质 2 它大概有 2nH2^{nH} 个元素。

lim⁡n→∞2nH(X)2n=lim⁡n→∞2n(H(X)−1)=0,(H(X)≤1)\displaystyle\lim_{n\to\infty}\dfrac{2^{nH(X)}}{2^n}=\displaystyle\lim_{n\to \infty}2^{n(H(X)-1)}=0,(H(X)\leq1)​

这说明典型集的个数相对于全空间来说时很小的，但他确实高频率出现的。

数据压缩·

  1. 将集合元素按照某种顺序排列；
  2. 指定下标可表示 Aϵ(n)A_{\epsilon}^{(n)} 中的每个序列；
  3. ∣Aε(n)∣≤2n(H+ε)|A_{\varepsilon}^{(n)}|\leq 2^{n(H+\varepsilon)} 需要 n(H+ε)+1n(H+\varepsilon)+1 比特；
  4. 编码加 00，则编码 Aε(n)A_{\varepsilon}^{(n)} 需要 n(H+ε)+2n(H+\varepsilon)+2​比特；
  5. 同理，对于非典型集 Aε(n)A_{\varepsilon}^{(n)} 需要 nlog⁡∣X∣+1n\log{|\mathcal{X}|}+1 比特，编码加 11 需要 nlog⁡∣X∣+2n\log{|\mathcal{X}|}+2 比特；
  6. 获得一个 Xn\mathcal{X}^n 一个编码方案；

其中非典型集的比特数是用全空间序列计算的，因为典型集个数很少，可以用全空间元素个数代替非典型集元素个数，误差可以忽略。

编码方案·

设 l(xn)l(x^n) 表示相应于 xnx^n 的码字长度，若 nn 充分大，使得 P(Aε(n))≥1−εP(A_{\varepsilon}^{(n)})\geq 1-\varepsilon，于是码字长度的期望满足

E(1nl(Xn))≤H(X)+εE(\dfrac{1}{n}l(X^n)) \leq H(X)+\varepsilon

因此，从平均意义上，用 nH(x)nH(x) 比特可以表示序列 XnX^n

熵率·

前文中的渐进均分性(AEP)表示平均意义下使用 nH(X)nH(X) 比特足够描述 nn 个 i.i.di.i.d​的随机变量，但是随机变量不独立，比如平稳随机过程时……

马尔科夫链·

用马尔科夫链可以减少研究随机过程问题的维度。

马尔科夫过程的每一步结果最多只与上一步有关，与其它步骤无关，数学表示为

P(X1,X2,⋯ ,Xn)=P(X1)P(X2∣X1)P(X3∣X2)⋯P(Xn∣Xn−1)P(X_1, X_2,\cdots, X_n) = P(X_1)P(X_2|X_1)P(X_3|X_2)\cdots P(X_n|X_{n-1})

马尔科夫链不是一个真正与历史无关的过程，通过链式法则，历史的信息可以传递到现在。

信道容量·

香农信道容量公式

C=Blog⁡21+SNC = B \log_2{1 + \dfrac{S}{N}}

对于典型干扰环境 SN<<1\dfrac{S}{N}<<1，则有

CB≈1.44SN\dfrac{C}{B} \approx 1.44 \dfrac{S}{N}

  • 在信道中当传输系统的 SN\dfrac{S}{N} 下降时，可以用增加系统传输带宽 BB 的办法来保持信道容量 CC 不变；
  • 在高斯白噪声干扰情况下，在平均功率受限的信道上，实现有效和可靠通信的最佳信号是具有白噪声统计特性的信号。

参考资料·

  1. https://www.jiqizhixin.com/articles/0224
  2. https://zhuanlan.zhihu.com/p/149188816