算法工程师面试题十一之熵

╰+攻爆jí腚メ 2023-01-06 04:21 197阅读 0赞

# 前言 #

*  文章来源：LawsonAbs（CSDN）
 *  我们可以从很多角度来解释自信息，熵这些专业术语，比如从编码长度这个角度考虑，对于26个英文字母，自信息就是该字母的最佳编码长度，整段文本的最佳编码大小就是熵，这种编码方式也就是俗称的熵编码。

--------------------

熵是一个很有趣的概念，它与生活紧密相连，特别是在信息学中。NLP是一门与语言打交道的学科，语言就是用来传递信息，所以自然语言处理和熵自然紧密联系。

# 1 熵 #

## 1.1 定义 ##

*  熵是用于衡量信息量大小东西，其单位是比特。（举个例子：质量是用于衡量物体属性的东西，其基本单位是kg）  
    某件事不确定性（概率）越大，则就需要越多的信息（去验证这件事的真假），那么熵就越大；

对于任意一个随机变量X，它的熵的定义如下：  
 H ( x ) = − ∑ x ∈ X p ( x ) l o g p ( x ) H(x) = -\\sum\_\{x \\in X\} p(x) log p(x) H(x)=−x∈X∑p(x)logp(x)  
其中`p(x)` 表示变量发生的概率。

## 1.2 性质 ##

首先可以看一下这个上面这个函数表达式的性质

*  变量的不确定性越大，熵也就越大。即可以把熵理解成：要把变量确定下来所需要的信息量。

> 几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。

# 3 互信息 #

互信息：作为两个随机事件“相关性”的量化度量。（有点儿像数学中的相关系数）所谓两个事件相关性的量化度量，就是：消息y能够对确定变量x所能提供的消息量。这个概念和条件熵有点儿互补的意思。  
 I ( x , y ) = ∑ x ∈ X ∑ y ∈ Y p ( x , y ) l o g p ( x , y ) p ( x ) p ( y ) = H ( x ) − H ( x ∣ y ) \\begin\{aligned\} I(x,y)& = \\sum\_\{x\\in X\} \\sum\_\{y\\in Y\}p(x,y) log\\frac\{p(x,y)\}\{p(x)p(y)\}\\\\ &=H(x) - H(x|y) \\end\{aligned\} I(x,y)=x∈X∑y∈Y∑p(x,y)logp(x)p(y)p(x,y)=H(x)−H(x∣y)

## 3.1 性质 ##

*  互信息是一个取值在 0到 `min(H(x),H(y))`之间的函数，当x 和 y 完全相关时，它的取值是 H(x)，同时H(x) = H(y) ；当二者完全无关时，它的取值是0。

## 3.2 用途 ##

互信息可以用在文本中单词的歧义消除中。

# 4 相对熵（KL散度） #

是两个随机分布之间距离的度量。

## 4.1 定义：两个概率密度函数为 p(x) 和 q(x) 之间的相对熵或KL散度距离定义为： ##

D ( p ∣ ∣ q ) = ∑ x ∈ X p ( x ) l o g p ( x ) q ( x ) = E p l o g p ( x ) q ( x ) \\begin\{aligned\} D(p||q) &= \\sum\_\{x \\in X\} p(x) log \\frac\{p(x)\}\{q(x)\}\\\\ &=E\_p log\\frac\{p(x)\}\{q(x)\} \\end\{aligned\} D(p∣∣q)=x∈X∑p(x)logq(x)p(x)=Eplogq(x)p(x)

## 4.2 性质 ##

*  相对熵总是非负，而且，当且仅当p=q时为零。
 *  相对熵不满足对称性，因此它并非两个分布之间的真正距离。

# 5 条件熵 #

## 5.1 定义 ##

假设y是随机变量，且我们知道其和  x x x 的联合概率分布 p ( x , y ) p(x,y) p(x,y)，以及在 y y y 取不同值的前提下 x x x 的条件概率分布。那么定义在y的条件下的条件熵是：  
 H ( x ∣ y ) = − ∑ x ∈ X , y ∈ Y p ( x , y ) l o g p ( x ∣ y ) H(x|y) = - \\sum\_\{x\\in X,y \\in Y\} p(x,y) logp(x|y) H(x∣y)=−x∈X,y∈Y∑p(x,y)logp(x∣y)

同时，也可以定义有两个条件的条件熵：  
 H ( x ∣ y , z ) = − ∑ x ∈ X , y ∈ Y p ( x , y , z ) l o g p ( x ∣ y , z ) H(x|y,z) = - \\sum\_\{x\\in X,y\\in Y\} p(x,y,z) log p(x|y,z) H(x∣y,z)=−x∈X,y∈Y∑p(x,y,z)logp(x∣y,z)

## 5.2 性质 ##

*  在知道  y y y 这个信息之后，关于 x x x的不确定性就下降了。  
     H ( x ) ≥ H ( x ∣ y ) ≥ H ( x ∣ y , z ) H(x) \\geq H(x|y) \\geq H(x|y,z) H(x)≥H(x∣y)≥H(x∣y,z)

# 参考资料 #

*  Thomas M.Cover《信息学导论》
 *  吴军著.《数学之美》
 *  邱锡鹏《NNDL》