信息论中的重要不等式

相对熵和互信息 附 信息论中的重要不等式 2 主要内容 信息论中的重要不等式相对熵互信息 对数函数基本不等式詹森不等式费诺不等式 3 1 4重要不等式 对任意实数对任何两组满足条件的实数 等号成立的充要条件是 对数函数的基本不等式 4 重要不等式 对任何两组实数 对数和不等式 5 重要不等式 詹森不等式是一个随机变量 表示的数学期望 是上凸函数 则费诺不等式是在中取值的随机变量 记则 6 相对熵 互熵 两个概率分布 差异性 的度量值 也是一种重要的信息度量 同一字母集上两个概率分布的相对熵 对任意概率分布pi 它对其他概率分布qi的自信息量 logqi取数学期望时的差异 7 相对熵的性质 等号成立是概率分布对的凸函数 8 互信息 9 互信息 I 信息量 不确定程度的减小量如果信道是无噪的 当信源发出消息x后 信宿必能准确无误地收到该消息 彻底消除对x的不确定度 所获得的信息量就是x的不确定度 即x本身含有的全部信息 信宿在收信前后 其消息的概率分布发生了变化 即其概率空间变了 10 1 互信息 1 yj对xi的互信息I xi yj 即 I xi yj I xi I xi yj p xi 先验概率 信源发xi的概率p xi yj 后验概率 信宿收到yj后 推测信源发xi的概率 含义 互信息I xi yj 自信息I xi 条件自信息I xi yj I xi 信宿收到yj之前 对信源发xi的不确定度 I xi yj 信宿收到yj之后 对信源发xi的不确定度 I xi yj 收到yj而得到 关于xi 的互信息 不确定度的减少量 互信息 11 2 xi对yj的互信息I yj xi 含义 信源发xi前 后 信宿收到yj的不确定度的减少 互信息 12 2 互信息的性质 1 对称性 I xi yj I yj xi 2 X与Y独立时 I xi yj 0 3 I xi yj 可为正 负 03 条件互信息给定zk条件下 xi与yj间互信息 互信息 13 I xi yj 可为正 负 0的举例设yj代表 闪电 则当xi代表 打雷 时 I xi yj 0 I xi yj I xi 0当xi代表 下雨 时 I xi yj I xi I xi yj 0当xi代表 雾天 时 I xi yj I xi I xi yj 0当xi代表 飞机正点起飞 时 I xi yj I xi I xi yj 0 互信息 14 平均互信息 为了客观地测度信道中流通的信息 定义互信息量I xi yj 在联合概率空间p x y 中的统计平均值为Y对X的平均互信息量 X对Y的平均互信息量 15 平均互信息 由关系式 可以推导出 表示通过信源和信道来观测到达信宿信息量 而没有观察信宿 16 平均互信息 表示通过信道和信宿来观察到达信宿信息量 而没有观察信源 17 平均互信息 18 1 Y对X 2 X对Y 3 合写 平均互信息 表达式 H X H X Y H Y H Y X H X H Y H XY 19 1 I X Y H X H X Y 1 H X 信源熵 X的不确定度H X Y 已知Y时 对X仍剩的不确定度 结论 Y已知 使得对X的不确定度减小了 即获得了I X Y 的信息量 2 H X 信源含有的平均信息量 有用总体 I X Y 信宿收到的平均信息量 有用部分 结论 H X Y 因信道有扰而丢失的平均信息量 故称损失熵 平均互信息 物理意义 20 2 I Y X H Y H Y X I X Y 1 H Y 信宿收到的平均信息量I X Y 信道传输的平均信息量 结论 H Y X 因信道有扰而产生的称噪声熵 散布度 2 H Y Y的先验不定度H Y X 发出X后 关于Y的后验不定度 结论 I Y X 发X前后 Y不定度的减少量 平均互信息 物理意义 21 3 I X Y H X H Y H XY H X H Y 通信前 整个系统的先验不确定度H XY 通信后 整个系统仍剩的不确定度I X Y 通信前后 整个系统不确定度的减少量 即传输的互信息 结论 I X Y 平均每传送一个信源符号时 流经信道的平均 有用 信息量 平均互信息 物理意义 22 文氏图 I X Y H X H X Y H Y H Y X H XY H X H Y X H Y H X Y H XY I X Y H X H Y H X Y H Y X H Y H X I X Y H XY 23 文氏图 I X Y H X H X Y H Y H Y X H XY H X H Y X H Y H X Y H XY I X Y H X H Y H X Y H Y X H Y H X I X Y H XY 24 1 非负性 I X Y 0 尽管I xi yj 的某些元素可为负2 对称性 I X Y I Y X 3 极值性 I X Y H X I X Y H Y 特例 I X Y H X H X Y 当H X Y 0时 I X Y H X 信道无噪 X Y一一对应 当I X Y 0时 H X Y H X 信道中断 X Y独立 平均互信息 性质 25 4 凸函数性 1 I X Y 是信源概率分布P X 的上凸函数 最大值 信道容量的基础 2 I X Y 是信道转移概率P Y X 的下凸函数 最小值 率失真函数的基础 平均互信息 性质 26 让一百万只猴子花一百万年的时间来打字 我们就能最终得到一本圣经 如今 我们搞定了 只花了经过相当程度缩减的时间 借助我们特别训练的马尔可夫猴 我们可以实时的重写整部圣经了 27 马尔可夫链 离散时间 马尔可夫链 因安德烈 马尔可夫 A A Markov 1856 1922 得名 是数学中具有马尔可夫性质的离散时间随机过程 该过程中 在给定当前知识或信息的情况下 过去 即当期以前的历史状态 对于预测将来 即当期以后的未来状态 是无关的 28 马尔可夫链 马尔可夫性质是概率论中的一个概念 随机过程被称为是具有马尔可夫性质 当给定现在状态时该过程的未来状态的条件概率分布 仅依赖于当前状态 换句话说 在给定现在状态时 它与过去状态 即该过程的历史路径 是条件独立的 具有马尔可夫性质的过程通常称之为马尔可夫过程 29 马尔可夫链 马尔可夫过程Markovprocess一类随机过程 它的原始模型马尔可夫链 由俄国数学家A A 马尔可夫于1907年提出 该过程具有如下特性 在已知目前状态 现在 的条件下 它未来的演变 将来 不依赖于它以往的演变 过去 例如森林中动物头数的变化构成 马尔可夫过程 在现实世界中 有很多过程都是马尔可夫过程 如液体中微粒所作的布朗运动 传染病受感染的人数 车站的候车人数等 都可视为马尔可夫过程 30 马尔可夫链 关于该过程的研究 1931年A H 柯尔莫哥洛夫在 概率论的解析方法 一文中首先将微分方程等分析的方法用于这类过程 奠定了马尔可夫过程的理论基础 1951年前后 伊藤清建立的随机微分方程的理论 为马尔可夫过程的研究开辟了新的道路 1954年前后 W 费勒将半群方法引入马尔可夫过程的研究 流形上的马尔可夫过程 马尔可夫向量场等都是正待深入研究的领域 31 马尔可夫链 马氏链模型描述一类重要的随机动态过程的模型 系统在每个时期所处的状态是随机的 从一时期到下时期的状态按一定概率转移 下时期状态只取决于本时期状态和转移概率已知现在 将来与过去无关 无后效性 马氏链的两个重要类型1 正则链 从任一状态出发经有限次转移能以正概率到达另外任一状态 2 吸收链 存在吸收状态 一旦到达就不会离开的状态 且从任一非吸收状态出发经有限次转移能以正概率到达吸收状态 32 如果随机变量与关于条件独立 即称为马尔可夫链 齐次马尔可夫链 如果转移概率与所处的状态无关 即 马尔可夫链 33 定理若是一个马尔可夫链 则若是齐次马尔可夫链 则 马尔可夫链 34 数据处理定理 当消息通过多级处理器时 随着处理器数目的增多 输入消息与输出消息之间的平均互信息量趋于变小 X Y Z构成马氏链 平均互信息 应用 35 数据处理定理I X Z I X Y I X Z I Y Z 意义 信息不增原理 每经一次处理 可能丢失一部分信息 平均互信息 应用 36 符号xi与符号对yjzk之间的互信息量定义为 I xi yjzk log 定义 条件互信息量是在给定zk条件下 xi与yj之间的互信息量 定义为 I xi yj zk log 三维 平均互信息量 37 I xi yjzk I xi zk I xi yj zk 说明 一个联合事件yjzk出现后所提供的有关xi的信息量I xi yjzk 等于zk事件出现后提供的有关xi的信息量I xi zk 加上在给定zk条件下再出现yj事件后所提供的有关xi的信息量I xi yj zk 三维 平均互信息量 I xi yjzk I xi yj I xi zk yj 38 I xi yjzk I xi zkyj 证明 因为所以I xi yjzk I xi zkyj 三维 平均互信息量 39 I X YZ I X Y I X Z Y I X YZ I X Z I X Y Z I YZ X I Y X I Z X Y 三维联合集XYZ上的平均互信息量 40 数据处理定理I X Z I X Y I X Z I Y Z 意义 信息不增原理 每经一次处理 可能丢失一部分信息 平均互信息 应用 41 证明 图中X是输入消息集合Y是第一级处理器的输出消息集合Z为第二级处理器的输出消息集合假设 在Y条件下X与Z相互独立 可得 即得 1 42 而且 2 又由I X YZ I X Y I X Z Y 和I X YZ I X ZY I X Z I X Y Z 得 I X Z I X Y I X Z Y I X Y Z 综合 1 2 得 I X Z I X Y 将I YZ X I Y X I Z X Y 中的X代替Y Y代替Z Z代替X得I XY Z I X Z I Y Z X 再将式 右边的X和Y互换得 I XY Z I Y Z I X Z Y 43 由式 和 得 I X Z I Y Z X I Y Z I X Z Y 所以 有I X Z I Y Z I X Z Y I Y