entropy

shannon entropy

积分形式:

假设 , 有且仅有一个为

如果要从中找到那个为 的 , 用二分可以在 轮求出

如果我们每次用 比特来存储我们二分的猜测 ( 表示猜 , 表示猜 )

那么 “满足 的 ” 这条信息值 比特

猜测出来的 比特信息正好对应 的二进制

如果每个 为 的概率可以不同, 那么我们可能知道哪些 更可能取

那我们平均猜测的次数就可能少于 , 即所需的信息量更少

于是香农用 表达一条信息理论上的最小编码长度, 即所需的信息量

用 表示 的概率

可以算出上面的 时,

进一步有

other definitions

joint entropy

conditional entropy

mutual information

Huffman encoding

上面的香农熵看起来很像哈夫曼编码

事实上, 如果哈夫曼编码平均长度为 , 那么

例如, 有 个符号, 出现频率为

那么

可以看到极为接近, 且满足

KL Divergence

definition

记

(注意前面是 是概率密度, 后面 是分布函数)

那么 KL 散度定义为

同时定义 对 的交叉熵

KL 散度实际上是 的交叉熵与 的熵的差:

它表示分布 与 的编码信息的期望差异程度 (相似度)

property of KL divergence

1. 非负性:

   , 当且仅当 时取等

2. 凸性

3. 链式法则:

   给出联合分布

   对于条件概率的 KL 散度的期望是

   其中 是 的 边际分布

   那么有

   由于 , 所以

4. 独立性

   由 可以得到当 独立时

   这正好体现了独立的信息是可加的

It is not a metric

KL 散度不是一般意义上的度量 (距离), 因为不满足对称性和三角不等式

即使构造出 满足对称性, 也无法满足三角不等式

connections with statistical concepts

mutual information

对于联合分布 , 定义互信息为

令 为 的分解 (factorization), 即分解成两个分量

那么

这样看, 互信息表示了联合分布与其分量的差异程度

maximum likelihood estimation

最大似然估计里我们希望最大化

假设采样足够多数据得到的实际的频率分布为

期望对数似然希望最大化 , 即

这正是使 与 的 KL 散度最小化的 , 因为:

Shannon Channel Capacity Theorem

definition

对于一个带宽为 的 AWGN 通道:

其中 方差 , 是方差为 的高斯噪声

useful inequality

定义:

则

其中 是 正态分布

利用 展开

这一步是因为

对于 ,

所以

所以

• 这说明在方差为 的概率密度函数中, 高斯分布 有着最大的信息熵

定义 属于指数族, 如果

如正态分布,

取 后:

定义:

即

其中 是 的充分统计量, 是 的分量

则

其中 是任意阶矩与 相同 (在 上的期望一致) 且 与 无关的指数族函数

Nyquist-Shannon Sampling Theorem

如果一个连续时间信号的频谱严格限制在 Hz 内，那么只要采样频率大于等于 Hz，就可以无失真地完全重建信号

即带宽 Hz 的信号，每秒最多只有 个独立的自由度, 只能在这 个自由度上各塞一个符号; 如果大于 , 相邻符号的频谱就会有重叠, 导致失真

Nyquist

Nyquist-Shannon Sampling Theorem 说明每秒最多发送 个符号, 每个符号 个 bit

connection with entropy

Shannon 取符号的长度为 , 即一个符号传输后的有效信息量是多少

因为 代表了观察到的信息, 减去噪声 即为原本 经过传输保留下来的信息量

由上述不等式,

并且

所以

根据 Nyquist, 每秒最多发送 个符号, 每个符号信息量 (bit 数) 为

所以信道容量为

实际上 的单位如果是电压, 那么 代表功率, 正比于方差, 所以比值 (功率作比变成 dB) 不变

而 Nyquist 定理中, 记输入 一共有 种取值, 可以按文章开头的猜测哪一个 的情形来看, 那么

所以无噪声时, 直接代入 即可, 有噪声时无法获得 , 用