美文网首页
信息论基本概念

信息论基本概念

作者: echo_ye4 | 来源:发表于2020-03-20 16:44 被阅读0次

    单符号离散模型

    信源每次输出一个单一符号,信宿每次接收一个单一符号
    信源(事件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_ja_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),选择信息增益最大的特征

    相关文章

      网友评论

          本文标题:信息论基本概念

          本文链接:https://www.haomeiwen.com/subject/wswkyhtx.html