第二章 信息量和熵.

Presentation on theme: "第二章 信息量和熵."— Presentation transcript:

1 第二章 信息量和熵

2 信息量和熵 离散变量的非平均信息量 离散集的平均自信息量－熵 离散集的平均互信息量 信息不等式 凸函数和互信息的凸性
连续随机变量的互信息和微分熵

3 2.1 离散变量的非平均信息量

4 p(xkyj)= p(xk|yj)ω(yj)= p(yj|xk)q(xk)
输入，输出空间定义 输入空间X={xk,k=1,2,…,K},概率记为q(xk) 输出空间Y={yj,j=1,2,…,J},概率记为ω(yj) 联合空间XY={xkyj ;k=1,2,…,K;j=1,2,…,J}, 概率为p(xkyj) p(xkyj)= p(xk|yj)ω(yj)= p(yj|xk)q(xk)

5 非平均互信息量 p(xk) 例2.1.1 输入消息 码字 收到0 收到01 收到011 X1 X2 X3 X4 X5 X6 X7 x8
000 001 010 011 100 101 110 111 1/8 1/4 1/2 1

6 非平均互信息量 p(xk) 输入消息 码字 收到0 收到01 收到011 X1 X2 X3 X4 X5 X6 X7 x8 000 001
010 011 100 101 110 111 1/8 1/4 1/16 1/6 1/3 2/3 1

7 非平均互信息量 p(xk) 例2.1.2 输入消息 码字 收到0 收到01 收到011 X1 X2 000 111 1/2 1-p p
1 p

8 非平均互信息量

9 非平均互信息量 定义2.1.1(非平均互信息量) 给定一个二维离散型随机变量{(X, Y), (xk, yj), rkj, k=1~K; j=1~J}（因此就给定了两个离散型随机变量 {X, xk, qk, k=1~K}和{Y, yj, wj, j=1~J}）。事件xk∈X与事件yj∈Y的互信息量定义为

10 非平均互信息量 其中底数a是大于1的常数。常用a=2或a=e，当a=2时互信息量的单位为“比特”。 几点说明： （1）I(xk; yj)=loga(rkj/(qkwj))。因此有对称性： I(xk; yj)=I(yj; xk)。 （2）当rkj=qkwj时I(xk; yj)=0。（当两个事件相互独立时，互信息量为0）。 （3）当rkj>qkwj时I(xk; yj)>0，当rkj<qkwj时I(xk; yj)<0。（当两个事件正相关时，互信息量为正值，当两个事件负相关时，互信息量为负值）。

11 条件互信息和联合事件互信息 三个事件集的条件互信息定义为 可以推广到任意有限多个空间情况

12 互信息的可加性 u2 u3 u1 系统 u1 u2 u3 系统

13 互信息量特性： 对称性 可加性 互信息量的值域： -infinite ~ +infinite, 即全体实数

14 离散变量的非平均自信息量 定义：给定集合｛X, q(xk)｝,事件xk∈X的自信息量定义为：

15 非平均自信息的性质 非负性 体现先验不确定性大小

16 条件自信息和联合自信息

17 自信息、条件自信息和互信息 I(xk) I(yj) I(xk ;yj)

18 2.2 离散集的平均自信息量－熵

19 熵 (平均自信息量——熵) 离散型随机变量{X, xk, qk, k=1~K}的平均自信息量（又称为熵）定义为如下的H(X)，其中底数a是大于1的常数。 集X中事件出现的平均不确定性

20 熵 注意： （1）事件xk的自信息量值为I(xk)=loga(1/qk)，因此H(X)是随机变量X的各事件自信息量值的“数学期望”。 （2）定义H(X)时，允许某个qk=0。（此时将qkloga(1/qk) 通盘考虑）此时补充定义qkloga(1/qk)=0。这个定义是合理的，因为

21 H(X)=ploga(1/p)+(1-p)loga(1/(1-p)) 。
熵 例 离散型随机变量X有两个事件x1和x2， P(X=x1)=p，P(X=x2)=1-p。 则X的平均自信息量（熵）为 H(X)=ploga(1/p)+(1-p)loga(1/(1-p)) 。 观察H(X)（它是p的函数，图2.2.1给出了函数图象，该图象具有某种对称性），有 当p=0或p=1时，H(X)=0。（随机变量X退化为常数时，熵为0） 当0<p<1时，H(X)>0。p越靠近1/2， H(X)越大。 （X是真正的随机变量时，总有正的熵。随机性越大，熵越大） 当p=1/2时，H(X)达到最大。（随机变量X的随机性最大时，熵最大。特别如果底数a=2，则H(X)=1比特）

22 条件熵（定义2.2.2） XY独立时有H(X|Y)=H(X)

23 联合熵

24 熵的性质 对称性 非负性 确定性 扩展性 可加性 极值性 是H(P)上凸函数

25 熵是概率矢量的函数 P＝(p1, p2, …, pk)可以看作是K维矢量,当 ,常称作是概率矢量;
故HK(P)=HK(p1, p2, …, pk)是概率矢量P的函数

26 熵的性质－对称性 矢量的各分量p1,p2,…pk的次序任意改变时，熵值不变
熵函数的值只与概率分布或将1分割成的K个实数的取值有关，而与这K个实数和K个事件采取何种一一对应方式无关

27 熵的性质－非负性 HK(P) = HK(p1, p2, …, pK) ≥0 可由单个事件自信息量的非负性得到

28 熵的性质－确定性 若事件集X中有一个事件为必然事件，其余事件为不可能事件，则此集合的熵值为0

29 熵的性质－扩展性

30 熵的性质－可加性 p1 p2 p3 p4 q11 q12 q13 q14 H(p1q11,p1q12,…,p4q44)=H(p1…,p4)+p1H(q11,…,q14)+…+p4H(q41,…,q44)

31 相对熵和条件相对熵 相对熵用于度量两个概率分布P(x)与Q(x)的距离 两个随机变量集合的条件相对熵定义为 相对熵和条件相对熵满足可加性

32 熵的唯一性 熵函数的形式是唯一的 对称性 扩展性 可加性 极值性

33 2.3 离散集的平均互信息量

34 平均互信息量 定义2.4.1(平均互信息量) 给定一个二维离散型随机变量{(X, Y), (xk, yj), rkj, k=1~K; j=1~J}（因此就给定了两个离散型随机变量{X, xk, qk, k=1~K}和{Y, yj, wj, j=1~J}）。X与Y的平均互信息量定义为如下的I(X; Y)：

35 平均互信息量 注意：事件对(xk, yj)的互信息量值为I(xk; yj)。此外，可以定义半平均互信息量I(xk; Y)和I(X; yj)。

36 平均互信息量的性质 对称性 I(X;Y)=I(Y;X) 平均互信息用熵与条件熵表示
平均互信息与熵的关系: I(X;Y) ≤H(X) or H(Y) 若X是Y的确定的函数X=g(Y)，则I(X;Y)=H(X)≤H(Y); 若Y是X的确定的函数Y=g(X)，则I(X; Y)=H(Y)≤H(X)。

37 平均互信息量 一般印象 （平均互信息量I(X; Y)的各种性质与我们对“互信息量”这个名词的直观理解非常吻合）。
一般情形：总有0≤I(X; Y)≤min{H(X), H(Y)}。 一种极端情形：若X与Y相互独立，则I(X; Y)=0。 另一种极端情形：若X、Y中有一个完全是另一个的确定的函数，则I(X; Y)=min{H(X), H(Y)}。

38 平均互信息量 H(X) H(Y) I(X;Y) H(Y|X) H(X|Y)

39 平均条件互信息与联合互信息

40 链式法则 熵的链式法则 平均互信息量的链式法则

41 信息不等式与信息处理定理

42 凸函数 凸集R：a，b属于R，qa+(1-q)b也属于R，其中0≤q≤1 概率矢量： 矢量a的所有分量非负，且和为1
上凸函数 下凸函数

43 凸函数的性质 定理2.5.1：如果函数f(x)的二阶导数是处处非负，则f(x)是严格下凸的。 f(a)是上凸的，－f(a)是下凸的
f1(a),…,fL(a)是R上的上凸函数，c1,…,cL是正数，c1f1(a)+…+cLfL(a)也是上凸函数

44 K-T条件 f(a)是定义域R上的上凸函数，a是概率矢量。偏导数 存在且连续， f(a)在R上为极大的 充分必要条件 其中l为一常数。

45 信息不等式 基础不等式:对于任意的x>0, lnx≤x-1,等号成立当且仅当x=1 Jensen不等式：
f(a)是上凸函数，E[f(a)]≤f[E(a)],E为求数学期望 信息散度不等式： D(p||q)≥0,等号成立当且仅当 对所有的x，p(x)=q(x)

46 信息不等式 互信息量不等式：I(X;Y)≥0 证明：I(X;Y)=D(p(x,y)||p(x)p(y))≥0
最大熵定理：H(X)≤log|X|，|X|是X中元素的数目，等号等概的时候成立。 条件降低熵：H(X|Y) ≤H(X),X与Y独立时等号成立

47 信息不等式 对数和不等式：a1,a2,…an和b1,b2,…bn都非负 Fano不等式 可以弱化为：

48 信息处理定理 Z出现情况下，X和Y独立 系统1 系统2 X Z Y

49 信息处理定理

50 熵的性质－凸性 相对熵的凸性：D(p||q)是概率分布对(p,q)的下凸函数： H(P)是P的上凸函数

51 互信息的凸性 记离散型随机变量X的事件为1，2，…，K。 记X的概率分布为P(X=k)=qk，k=1~K。
记离散型随机变量Y的事件为1，2，…，J。 记条件概率P(Y=j|X=k)=p(j|k)。则 rkj=P((X, Y)=(k,j))=qkp(j|k)，（概率论中的乘法公式） wj=P(Y=j)=∑k qkp(j|k)，（概率论中的全概率公式）

52 互信息的凸性 p(y | x)给定，I(X; Y)是q(x)的上凸函数 q(x)给定，I(X; Y)是p(y | x)的下凸函数

53 互信息的凸性 设条件概率{p(j|k)，k=1~K，j=1~J}被确定。此时I(X; Y)是概率向量q=(q1, q2, …, qK)的函数。我们希望找到这样的概率向量，使得对应的I(X; Y)达到最大。这就是说，记 我们希望找到这样的K维概率向量a=(a1, a2, …, aK)，使得

54 互信息的凸性 K维概率向量a=(a1, a2, …, aK)使得
当且仅当：以a为X的概率向量的时候，I(X=k; Y)对所有ak>0的k都取一个相同的值C； I(X=k; Y)对所有满足ak=0的k都取值不超过上述的相同值C 。

55 互信息的凸性 I(X=k; Y)表示什么？表示事件X=k与随机变量Y之间的“半平均互信息量”。

56 p(0|0)=1-u；p(1|0)=u；p(0|1)=u；p(1|1)=1-u。
互信息的凸性 例 设X的事件有0、1； Y的事件有0、1； 已知 p(0|0)=1-u；p(1|0)=u；p(0|1)=u；p(1|1)=1-u。 当X服从等概分布（a0=P(X=0)=1/2；a1=P(X=1)=1/2）时，I(X;Y)达到最大。因为此时

57 互信息的凸性

58 2.4 连续随机变量的互信息和微分熵

59 连续随机变量的互信息 定义 给定二维连续型随机变量{(X, Y), f(X,Y)(x, y)}（因此就给定了两个连续型随机变量{X, fX(x)}和{Y, fY(y)}）。事件x∈X与事件y∈Y的互信息量定义为

60 连续随机变量的平均互信息 I(X; Y | Z) I(XY; Z)
定义 给定二维连续型随机变量{(X, Y), f(X,Y)(x, y)}（因此就给定了两个连续型随机变量{X, fX(x)}和{Y, fY(y)}）。 X与Y的平均互信息量定义为 I(X; Y | Z) I(XY; Z)

61 性质 非负性 对称性 数据处理定理 关系

62 连续随机变量的微分熵 （连续型随机变量为什么不能类似地定义平均自信息量——熵？这是因为，连续型随机变量的事件有无穷多个，每个事件发生的概率无穷小。如果类似地定义熵，则熵是无穷大。因此只能定义所谓“微分熵”，而“微分熵”的直观合理性大打折扣） 微分熵的定义 给定连续型随机变量{X, fX(x)}。 X的微分熵定义为

63 互信息与微分熵 连续随机变量的微分熵 HC(XY) HC(Y | X)， HC(Y | X) ≤HC(Y)
I(X ; Y)＝HC(X)－HC(X | Y)＝HC(Y)－HC(Y | X) ＝HC(X)+HC(Y)－HC(X, Y) HC(X, Y)＝HC(X)+HC(Y)－I(X ; Y)

64 均匀随机变量的微分熵 例 设X~U(a, b)，求X的微分熵（我们将发现， X的微分熵未必非负）。

65 正态随机变量的微分熵 例 设X~N(m, σ2)，求X的微分熵（我们将发现， X的微分熵未必非负）。

66 正态随机变量的微分熵 例2.7.3 熵功率 微分熵不具有非负性

67 练习： 试求指数分布连续信源的熵

68 微分熵的极大化 1.峰值功率受限 2.平均功率受限 3.平均功率大于等于熵功率 均匀分布微分熵最大：HC(X) ≤log 2M
高斯分布微分熵最大 3.平均功率大于等于熵功率

69 习题 10个硬币中有一个重量偏轻，其他9个为标准重量。在不用砝码的天平上至多称多少次，就能发现这个轻的硬币？怎样称？用天平称的信息论含义是什么？