Information Theory - wll

让我们来看看伟大的王立威教授在它的信息论课程中讲到了哪些书本上需要的内容，让我们进而反复思考，认真揣摩，深入理解！然后看书。

《Elements of Information Theory》 - second edition, Thomas M. Cover, Joy A. Thomas

都是最最最最最最最基础的内容（？）

上面没有，有点慌。

2024/4/23

Error Correcting Codes

• 你要考虑两方面的问题，第一个是coding长度要大到一定程度，第二是要computational efficient

对于linear code，一般使用 [n,k] 或者 [n,k,d] 来表示

• 这里n为codeword的长度，k是information bits的数量，也就共有 $2^k$ 的要映射到 $2^n$ 里，距离是 $d$ 至少。

对于nonlinear code，一般用 (n,M,d) 来表示。

线性码是一种编码方式，其中编码后的码字（codewords）形成一个线性空间

回忆一下怎么构造Hamming Code

• 首先构造矩阵 $H_{37}$

$$H=\pmatrix{1&0&0&1&1&0&1\\0&1&0&1&0&1&1\\0&0&1&0&1&1&1}$$

• 然后求出 $\ker H$ ，这个 $\ker H$ 就是 Hamming Code，这里 $\ker H \subseteq F_2^7$
  • 非常容易证明任何两个 vector 之间的 Hamming distance 是大于等于 3 bit 的

Lemma1: For linear code C：

• $$\min_{x\not =y,x,y \in C} d_H(x,y)=\min_{x \in C,x\not= 0} ||x||$$

从而 Hamming Code 是 [7,4,3] code

decoding

那么如何efficiently decoding呢

idea：如果它在我的纠错范围之外，我就不管它。

考虑接收方收到的vector $y=c_i+r$ 这里 r 要么是零向量，要么是单位向量 $e_i$，一个很简单的纠错方式是 $Hy=Hc_i+Hr=Hr$，要么等于零，要么等于某一列。

这里的H可以算是Parity check matrix，它的原意是奇偶校验，这里就理解成H乘上每个space里的元素乘积都是零。

encoding

对于一个general的linear code [n,k]，一个 ${0,1}^k \to {0,1}^n$

如果有一组基，选$k$个，就可以用线性组合的方式一一映射。所以可以有一个

$$\Phi:x \cdot G$$

一定可以让

$$G=[I_{k,k}\mid P_{k,n-k}]$$

这个 G 是一个Generator matrix。

我们把写成这个样子的Generator matrix这个叫做Normal Form。

$$x\cdot G=(x,xP)$$

对于Hamming code的generator matrix就是 $HG^T=0$

也就是说 $H$ 其实可以写成 $[P^T \mid I_{n-k,n-k}]$

extension; shortening

• [7,4,3] 的第三个表示Hamming distance
• 可以让codeword变长或者变短，期待是修改这个Hamming dist
• 对于shortening，对于 (n,M,d) 的non-linear的code，可以shorten到 (n-1,M/2,d)
• 对于 (n,M,d)，其中d是奇数的non-linear的code，可以到(n+1,M,d+1)，这个考虑d是奇数，所以距离为d的只可能其中1的个数的奇偶性不同，则增加一位即可增加一个距离。

more:

• cyclic coding

• quadratic residual

• Hamming distance的16个codeword，取1的那些位置不是随便取的，GF(7)

• 如果某个数 $x \in GF(7)$，那么 $x=y^2 (\mod 7)$ for some y

Channel Capacity

• —-CHAPTER 7—-

• (Conceptual) channel capacity

  $$C\triangleq \max_{P(X)} I(X;Y)$$

我可以一次性传输 $M$ 个东西，也就是原始的message是 $\lg M$ 的长度的，如果编码后的长度为 $n$，定义这时候的传输速率 $R=\frac{\ln M}{n}$

如果一个速率是 achievable 的话，任何错误率epsilon，都存在一个纠错码能够让错误不超过 epsilon。

memoryless:两次传输之间没有关系。

Rate:所谓的 rate 就是平均来讲我每次传输了多少的信息量。 $\log M/n$

2024/5/14

The Chennel Coding Theorem

• (也叫)香农第二定理：
  • If RC, R is not achiable.
• 专注于平均错误率，可以非常简单地做一个改变，让最坏的codeword的错误率也小于某个bound。

为什么需要Error Correcting Code呢？因为我们不关注传输了多少信息，关注的是互信息。

achieve rate：存在一个M，存在一个code，使得R=log M/n，且使得错误不超过epsilon。也就是以这个速率发送的时候，你可以define这个code的长度M和这个code。在这一套传输的时候你的错误率是小于epsilon的。这个错误率是平均的，但其实和最坏的差不多。后面会说到。

Asymptotic Equipartition Property

• 类似一种大数定律。
• 小白都能懂得信息论（更改版本）：渐近均分性 - 知乎 (zhihu.com)

定义 $g(x)=\log \frac{1}{p(x)}$ 是一个关于 $x$ 的函数。

注意到我们的大数定律是，在 $n \to \infty$ 时，

$$P(\frac{1}{n}\sum g(x_i)-Eg(X)\ge \epsilon)\to 0$$

代入 $g(x)$，我们有

$$P(\frac{1}{n}\log \frac{1}{P(x_1,x_2,...x_n)}-H(x) \ge \epsilon) \to 0$$

也就是

$$P(P(x_1,x_2,...x_n)\in 2^{-n(H(x)\pm\epsilon})) \to 1$$

这是什么意思？如果一个sequence满足这个，概率和 $2^{-nH(X)}$ 一样就叫 typical sequence。

typical sequence的数量是远远小于 $2^n$ 的，但随机draw一个序列，它是typical sequence的概率是接近1的。就是剩下的序列虽然很多，但是出现的概率基本为零。

定义typical sets

$$A_\epsilon^n=\{(x_1,...x_n)\mid P(x_1,..x_n) \in2^{-n(H(x)\pm \epsilon)}\}$$

Joint Typical Sequence

$x_1,y_1,x_2,y_2…x_n,y_n$ 如果是一个joint typical seq，要求同时满足下面三个。

这里的 $P$ 是一个概率密度函数

$$P(x_1,y_1,x_2,y_2,...,x_n,y_n)\approx 2^{-nH(x,y)}\\ P(x_1,x_2,...,x_n)\approx 2^{-nH(x)}\\ P(y_1,y_2,...,y_n)\approx 2^{-nH(y)}$$

满足2和3的情况的，大约的比例是这么多：

$$\frac{2^{nH(x,y)}}{2^{nH(x)}2^{nH(y)}}=2^{-nI(x;y)}$$

所以最后的结论就是

如果我randomly draw $X_1,…X_n$, 然后独立地draw $Y_1,…Y_n$，那么 $X_1,Y_1,…X_n,Y_n$ 是Joint typical seq（满足上面三个条件）的概率大约是 $2^{-nI(X;Y)}$。

24/05/28

什么叫做joint typical sequence呢？

相对于一个联合分布 $P(X,Y)$ 定义 joint tpical seq.

如果从 $(X_i,Y_i)\sim P(X,Y)$ 中sample出来的，并且 $(X_i,Y_i),(X_j,Y_j)$ 之间iid，对于序列 $(x_1,…x_n,y_1,…y_n)$，我们有 $P([X_1,Y_1,..X_n,Y_n\text{是joint typical seq}])\approx 1$。

但是如果 $X$ 和 $Y$ 之间是independent地draw的话，根据上节课的内容，draw出来的seq如果要满足joint typical seq，关于$P(X,Y)$的joint typical seq的概率是 $2^{-nI(X;Y)}$。

Proof of Channel Coding Them

总共有 $m$ 个message，为 $w_1,w_2,…w_M$，通过encoding变成 $c_1,c_2,…c_M,c_i\in {0,1}^n,n>\log_2M$

所以 $Rate=\log_2M/n$ （至多，简单起见先取等号），则有 $M=2^{nR}$。

simplified setting： $w1,w_2,…w{nR}$ 上的均匀分布

考虑random encoding：

有 $P(X),P(Y),P(Y\mid X),P(X,Y);P(Y\mid X)$

这里面的 $P(Y\mid X)$ 就是信道， $P(X)$ 设成使得mutual information取到最大值的 $P(X)$。

也就确定了 $P(X,Y),P(Y)$。

考虑对 $w1,w_2…w{nR}$ 随机encode成 $n$ bit的，每一个比特都让他独立同分布随机生成。

每一个 $c{ij}$ 都是通过 $P(X)$ 来生成的， $P(X)$ 是使得 $C:=\max{P(X)} I(X;Y)$ 那个取到最大值的 $P(X)$。

所以这里 $ci=(x{i1},…x_{in})$。

我要解码 $(y1,y_2,…y_n)$，方法是如果对于 $(x{i1},y1,…x{in},y_n)$ 是唯一的jointly typical sequence，那么我们可以解码 $c_i$，否则认为失败了。

核心的问题是，这里的错误率是多少？

两种可能的错误，第一种是不存在joint的。注意到我input是 $P(X)$，output是 $P(Y)$，这个信道是 $P(Y\mid X)$，也就是之类的 $X$ 和 $Y$ 的联合概率是 $P(X,Y)$，所以不存在joint的概率几乎不存在。

第二种是，如果不止一个，那么除了真实的 $X$，还有另外一个 $X$ 是一个和 $Y$ 独立的东西，这个概率是 $2^{-nI(X;Y)}$。

这东西和那个一张随机的二分图不断加边，直到出现环，有没有一点内在的联系啊。

好，上面说得是平均的意义上，那么：

第一，对于code而言，因为期望上能让code的error小，所以一定存在一个code的error小。

第二，对于一个好的code，我们知道平均的code的error

$$Err(C)=\frac{1}{2^{nR}}\sum_{i=1}^{2^{nR}}Err(c_i)$$

如果这个Err不超过$\epsilon$

那么我去找最好的codeword，找最好的一半的codeword，那么这最好的一半里最差的codeword的错误不超过$2\epsilon$。（类似于中位数trick）

24/06/04

对于另一半部分，Fano’s Ineq

给定任意的 $X,Y$ 满足 $X\in \mathcal H, |\mathcal H|<\infty$，我们用 $Y$ 估计 $X$，有 $\hat X=g(Y)$，则

$$P_e:=Pr(\hat X\not = X)\ge \frac{H(Y\mid X)-1}{\log |\mathcal H|}$$

证明：
定义 $E:=X=g(Y)?0:1$

一方面那么 $H(X,E\mid Y)=H(X\mid Y)+H(E\mid XY)=H(X\mid Y)$

另一方面

$$\begin{align*} H(X,E\mid Y)=&H(E\mid Y)+H(X\mid E,Y)\\\le& 1+H(X\mid E,Y)\\ =&1+P(E=1)H(X\mid Y,E=1)+P(E=0)H(X\mid Y,E=0)\\ =&1+P_eH(X\mid Y,E=0)\\ \le&1+P_e\log_2\mathcal H \end{align*}$$

所以

$$P_e\ge \frac{H(Y\mid X)-1}{\log |\mathcal H|}$$

证毕。

于是我们重新考虑，当 $R>C$ 的时候，存在一个错误界限。

回忆一下，对于信道难道不是这样吗？message的个数是 $2^{nR}$，codeword的长度是 $n$，然后我收到了 $Y$，我要estimate是哪个 $X$。

如果是uniform的，那么

$$\begin{align*} nR=&H(x)\\=&H(X\mid Y)+I(X;Y)\\ \le&P_e(\log_2\mathcal |H|+1)+nC\\ =&P_e(nR+1)+nC\\ \end{align*}$$

也就证明了如果 $R>C$，就不行。

Finsher Information and the Cramer-Rao ineq

对于一个unbiased的estimator，如果 $\phi$ 是关于 $f$ 的unbiased estimator

$$\mathbb E_{X\sim f(\cdot;\theta)}[\phi(x)]=\theta$$

定义 score function

$$S(x;\theta)=\frac{\partial}{\partial \theta} \ln f(x;\theta)$$

则

$$\mathbb E [S(X,\theta)]=\int_{-\infty}^{\infty}[\frac{\partial}{\partial \theta}\ln f(x;\theta)] f(x;\theta)\mathrm d x \\=\frac{\partial}{\partial \theta}\int f(x,\theta) dx\\ =\frac{\partial}{\partial \theta} 1=0$$

Fisheries Info of a parameter $\theta$ w.r.t. a sample $X$ is defined as:

$$I(\theta):=E[S(X;\theta)^2]=Var(S(X;\theta))$$

可以证明等价于

$$I(\theta)=E[\frac{\partial^2}{\partial^2\theta}\ln f(X;\theta)]$$

暴力展开一下是可以证的。

这个东西有什么用呢？能够刻画，所有unbiased的estimator，它的variance最小能小到多少。有个定理是说

Lecture15.pdf (stanford.edu)

$$Var_\theta(\phi(X)) \ge \frac{1}{I(\theta)}$$

对于一个参数是这样的，但是我们可以定义Fisher Information Matrix，也是一个半正定的Matrix。

---

鉴于我只学了两天，我觉得这不是一个好文明，虽然这是一门好课，但是我绩点怕是又要没了。

所以我决定把第二章，第三章的summary再看一下

第二章

熵的定义，互信息的定义，条件熵的定义，相对熵的定义，互信息

$$I(X;Y)=H(X)+H(Y)-H(X,Y)=D(p(x,y)||p(x)p(y))$$

KL散度大于等于零（P28），熵和互信息和相对熵满足一系列的链式法则。

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

log sum 不等式是：

$$\sum_{i=1}^n a_i\log \frac{a_i}{b_i}\ge \left(\sum_{i=1}^n a_i\right)\log \frac{\sum_{i=1}^n a_i}{\sum _{i=1}^n b_i}$$

Fano’s ineuqality（P38）

---

第三章

AEP的内容，讲 Almost all events are almost equally surprising.几乎所有的序列都是，如果iid的每个元素，那么总出现概率趋向于 $2^{-nH(X)}$。这些集合个数则正负一个 $\epsilon$。

还有一个GVM的bound

Gilbert-Varshamov Bound (asymptotic)

Probabilistic Method

Probability Calculation

$$q=\mathbb{P}\left\{d_H(s_1, s_2) \leq d \text{ bits}\right\}$$

where (d_H) denotes the Hamming distance.

• Uniformly random generate $(2^n)$ (n)-bit strings.
• $$d < \frac{m}{2}$$

Probability Bound

$$\mathbb{P}\left\{\exists s_i, s_j \; d_H(s_i, s_j) \leq d \text{ bits}\right\} \leq \binom{2^n}{2} q$$

Considering a random code selection from (${0, 1}^n$) with equal probability, Chernoff bound is applied:

$$\Pr[|c_i - c_j| < \delta m]$$

where $(c_i, c_j)$ are codewords, $X_i$ is an indicator variable for the $i$-th bit.

Chernoff Bound Application:

$$\Pr\left[\left|c_i - c_j\right| < \delta m\right] = \Pr\left[\frac{1}{m}\sum X_i-(\frac{1}{2}) \leq \left(\frac{1}{2} - \delta\right)\right] \leq e^{-m D_B(\delta || \frac{1}{2})}$$

where

$$D_B(\delta || \frac{1}{2}) = \delta \ln (2\delta) + (1 - \delta) \ln (2(1-\delta)) = \ln 2 + H(\delta)$$

Union Bound

$$\Pr[\exists i, j, s.t. |c_i - c_j| < \delta m] \leq C_{2^n}^2 \cdot \Pr[|c_i - c_j| < \delta m]$$

To ensure the probability is close to zero:

$$\frac{1}{2} \cdot 2^n \cdot (2^n - 1) \cdot \frac{1}{2^m} \cdot e^{-m H(\delta)} < 1$$

This simplifies to:

$$\ln 2 \cdot (2n - 1) - \ln 2 - m \cdot H(\delta) < 0$$

Solving for (m):

$$m > \frac{2n - 1}{H(\delta) \ln 2}$$