信息论基本概念

单符号离散模型

信源每次输出一个单一符号，信宿每次接收一个单一符号
信源（事件X）
$\begin{pmatrix} X\\ P(X) \\ \end{pmatrix} = \begin{Bmatrix} a_1 && a_2 && ... && a_n\\ p(a_1) && p(a_2) && ... && p(a_n) \\ \end{Bmatrix}$
信宿（事件Y）
$\begin{pmatrix} Y\\ P(Y) \\ \end{pmatrix} = \begin{Bmatrix} b_1 && b_2 && ... && b_m\\ p(b_1) && p(b_2) && ... && p(b_m) \\ \end{Bmatrix}$

自信息

$I(a_i) = -log_2p(a_i)$ -- 自信息量
$I(a_ib_j) = -log_2p(a_ib_j)$ -- 联合自信息量
$I(a_i|b_j) = -log_2p(a_i|b_j)$ -- 条件自信息量

其中 $I(a_i)$ 表示 $a_i$ 的不确定度， $I(a_i|b_j)$ 表示已知 $b_j$ 的情况下， $a_i$ 仍存在的不确定度

熵（平均信息量）

信源熵
$H(X) = E(I(a_i)) = \sum p(a_i)I(a_i) = - \sum p(a_i)log_2p(a_i)$
联合熵
$H(XY) = E(I(a_ib_j)) = \sum \sum p(a_ib_j)I(a_ib_j) = - \sum p(a_ib_j)log_2p(a_ib_j)$
条件熵
$H(X|Y) = E(I(a_i|b_j)) = \sum \sum p(a_ib_j)I(a_i|b_j) = - \sum p(a_ib_j)log_2p(a_i|b_j)$

互信息

信源发出 $a_i$ 的概率为 $p(a_i)$
信宿收到 $b_j$ 时推测信源发出 $a_i$ 的概率为 $p(a_i|b_j)$
互信息量定义为：
$I(a_i;b_j) = log_2 \frac{p(a_i|b_j)}{p(a_i)} = I(a_i) - I(a_i|b_j)$
$b_j$ 对 $a_i$ 的互信息量可以理解为， $a_i$ 的不确定度减去 $b_j$ 确定后 $a_i$ 的不确定度，即 $b_j$ 确定后消除的对 $a_i$ 的不确定度

平均互信息量

$I(X;Y) = \sum \sum p(a_ib_j) I(a_i;b_j)$
其物理意义：
1）信源的先验不确定度- 信道疑义度
$I(X;Y) = H(X) - H(X|Y)$
2）信宿熵 - 信道噪声
$I(X;Y) = H(Y) - H(Y|X)$
3）通信前的熵 - 通信后产生统计性联系的熵
$I(X;Y) = H(X) + H(Y) - H(XY)$

image.png

信道容量

信道转移矩阵
$\begin{Bmatrix} p(b_1|a_1) & p(b_2|a_1) & ... & p(b_m|a_1) \\ ... &&&\\ p(b_1|a_n) & p(b_2|a_n) & ... & p(b_m|a_n) \\ \end{Bmatrix}$

如果信源熵为 $H(X)$ ，由于信道存在干扰，一般情况下输出端只能接收到 $I(X;Y)$

定义信道的信息传输率 $R = I(X;Y)$

平均互信息是信源无条件分布概率
${p(a_i)}$ 和信道转移概率 ${p(b_j|a_i)}$ 的函数，当信道特性（信道转移概率）固定后，互信息随着信源分布概率变化，且为上凸函数

找到一种信源概率分布，使信息传输率最大，定义这个最大的信息传输率为传输容量 $C = max R = max I(X;Y)$

相对熵与交叉熵

相对熵也称KL散度，在信息理论中，相对熵是用来度量使用基于Q的编码来编码来自P的样本平均所需的额外的比特个数。典型情况下，P表示数据的真实分布，Q表示数据的理论分布，模型分布，或P的近似分布。
$D_{KL(p||q)} = \sum p(x)log(\frac {p(x)}{q(x)})$
相对熵也可以衡量两个随机分布之间的距离

$D_{KL(p||q)} = \sum p(x)log(p(x)) - \sum p(x)log(q(x))$

定义交叉熵 $H(p,q) = \sum p(x)log(q(x))$

$D_{KL(p||q)} = H(X) - H(p,q)$

多符号离散平稳模型

信源每次输出一个符号序列，序列的每一位都是随机的，而前后符号是有统计关系的，若信源发出的符号序列的概率分布与时间无关，我们称之为多符号离散平稳信源。

二维平稳信源

信源发出的符号序列中，每两个符号看作一组，每组 $X = X_1X_2$ 代表一个消息，为了便于分析，我们假设组与组之间是统计独立的，但是要注意这与实际情况并不相符，由此得出的信源熵仅仅是近似值。
假设 $X_1,X_2 \in \left\{ a_1, a_2, ..., a_n \right\}$
则 $X \in \left\{ a_1a_1, ..., a_1a_n, a_2a_1, ..., a_na_n \right\}$
$\alpha_i = (a_{i1}a_{i2})$ ， $i = 1,2,...,n^2$
$\sum p(\alpha_i) = 1$
$\begin{pmatrix} X \\ P(X) \\ \end{pmatrix} = \begin{Bmatrix} \alpha_1 & \alpha_2 & ... & \alpha_i \\ p(\alpha_1) & p(\alpha_2) & ... & p(\alpha_i) \\ \end{Bmatrix}$

信源熵为 $H(X) = H(X_1X_2) = H(X_1) + H(X_2|X_1)$

N维平稳信源

信源熵为 $H(X) = H(X_1X_2) = H(X_1) + H(X_2|X_1) + H(X_3|X_1X_2) + ... + H(X_N|X_1X_2...X_{N-1})$

极限熵

信源平均每发一个符号所提供的信息量为
$H_N(X) = \frac 1N H(X_1X_2...X_N)$
当 $N -> \infty$ 时， $H_{\infty} = \lim_{N->\infty} \frac1NH(X_1X_2...X_N) = \lim_{N->\infty} H(X_N|X_1X_2...X_{N-1})$ ，称为极限熵
在研究实际信源时，必须求出极限熵才能确切地表达每发一个符号提供的信息量，而这是比较困难的

马尔可夫信源

在许多信源的输出序列中，符号之间的依赖是有限的，任何时刻信源发生的概率只与前面若干个符号有关。
在随机变量序列中，时刻m+1的随机变量 $X_{m+1}$ 只与前面发生的m个随机变量有关，与更前面的随机变量无关，这种信源称为马尔可夫信源
因此，极限熵 $H_{\infty} = H(X_{m+1}|X_1X_2...X_m)$

在机器学习上的应用

使用交叉熵作为loss function

在分类学习时，真实label的概率分布为Y，预测label的概率分布为A，要使A尽量接近Y，可以最小化 $D_{KL(p||q)}$ ，由于H(Y)是常数，因此可以简化为最小化 $-H(p,q)$
$min -\sum y log(a)$

最大熵模型

基本思想：在满足约束的情况下，最大化 $P(Y|X)$ 的条件熵，使用 $P(Y|X)$ 来进行预测

从训练数据中，根据极大似然估计，可以求出经验分布 $P'(X)$ 和 $P'(XY)$
特征函数 $f(x, y) = \left\{ \begin{array} {} 1 & x,y满足某一事实\\ 0 & 其他\\ \end{array} \right.$
用特征函数的期望建立约束，有n个特征函数，就有n个约束
$\sum p'(xy)f(x,y) = \sum p'(x)p(y|x)f(x,y)$

建立最优化模型
$max -\sum p'(x)p(y|x)log(p(y|x))$
$s.t. \sum p'(xy)f_i = \sum p'(x)p(y|x)f_i, i = 1,2,...,n$
$\sum_y p(y|x) = 1$

决策树模型

建立树模型，每个节点代表一个特征的划分，使用0-1 loss function
节点划分是一个NP-hard问题，考虑采用启发式算法，根据规则每次选择最好的节点
其中一个规则是该节点可以提供最多的信息，即熵减小最多，熵越小，loss function越小，所以实际上是选择使loss function减小最多的节点
设数据集为D，特征为A，分割前的熵为H(D)，分割后有多个数据集 $D_1, D_2,...$ ，分割后的熵为 $H(D,A) = \frac {D_1}{D}H(D_1) + \frac {D_2}{D}H(D_2) + ...$ ，因此信息增益为 $g(D,A) = H(D) - H(D,A)$ ，选择信息增益最大的特征

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,254评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,875评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 158,682评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,896评论 1赞 285
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,015评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,152评论 1赞 291
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,208评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,962评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,388评论 1赞 304
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,700评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,867评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,551评论 4赞 335
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,186评论 3赞 317
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,901评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,142评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,689评论 2赞 362
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,757评论 2赞 351