计算机语言学数学基础

2018-10-11 本文已影响0人 Milkmilkmilk

计算语言学的数学基础

信息论基础

1. 理解熵的最初提出

考虑以下的最优编码问题：
有A,B两个站点要传输关于甲乙两个人是否在房间的信息，根据大量的以往的经验，甲乙两个人在房间的状态可能性如下表所示，A发送信息，B接受信息，发送的信息是二进制的。

房间状态	房间没有人	只有甲在房间	只有乙在房间	两人都在房间
概率	0.5	0.125	0.125	0.25

我们要让发送的二进制信息能够反映出甲乙的状态，所以要对信息进行编码。
我们可以使用两位二进制数据。

00 表示房间没有人
01 表示只有甲在房间
10 表示只有乙在房间
11 表示都在房间

这样的话平均发送的信息编码长度是 2 位（每次都是2位）。
其实我们可以使用长度不同的编码。比如使用

0 表示房间没有人
10 表示两个人都在房间
110 表示只有甲在房间
111 表示只有乙在房间

注意：编码问题，上述为什么没有使用到1，1不是更加短吗？可以这么理解B在接收信息的时候，是按位的。比如说110，先接收1，发现没有1状态就继续接收1，发现没有11，就继续接收0，发现110是事先商量好的状态，所以就可以解码成只有甲在房间，如果说使用了1状态进行编码了，那么收到110就可能认为A发送了3次，分别是1状态1状态0状态

而这样的编码的平均发送的信息编码长度是
$1*0.5+2*0.25+3*0.125+3*0.125 = 1.75$
所以这样的编码是更好的，而且其实这个编码对于这个问题是最优的。

其实这个问题的解决就是构造哈夫曼编码树。另外我们可以考虑，如果计算机每次发送的不是二进制，而是三进制或者是十进制，那么我们如何确定最优的编码呢？其实这个是多叉哈夫曼编码树，同样是贪心的思想，但是要多考虑一下树结构的完整性，才能够贪心正确。

而香农就是直接把上面的流程转化成了公式的形式。对于传输二进制信息，给我们其信息状态的概率分布，那么每个状态应该给的编码长度是 $-log_2(p(x))$ 。比如说上面的房间没有人的概率是 $0.5$ , 而 $-log_2(0.5) = 1$ 从而给编码为1。其余的也可以进行计算，不再重复。
那么平均发送的信息的编码长度就是 $\sum_{i=0}^{n} p(x) \lceil -log_2(p(x)) \rceil$ 。而最后这个期望值就是熵最初的定义，可以理解为在一个编码问题中最优编码下的发送一个信息的平均需要二进制信息的位数。

2.现在熵的演化和作用

Def : 针对一个随机变量X，其有熵的定义为
$H(X) = \sum_{x\epsilon X}^{}-p(x)log_a(p(x))$

可以发现的是相比之前的熵，现在这个定义的熵。
（1）log底是可以自己设置的了。
（2） $-log_ap(x)$ 没有向上取了。

其实也可以理解，对于（1）可以更加灵活了，甚至可以去考虑非二进制下最优编码，并且香农在提出这个的时候是按照10的，此时单位叫做香农。（可能有错）但是a其实一般都不是十分重要，因为不同底只相差一个倍数关系。对于（2）因为我们要推广到更大的使用范围上，不拘泥于实际编码中，我们的码位是一个整数。

基本的熵的性质，最大值，最小值，以及熵表示信息的混乱程度不赘述。

3. 各种熵

联合熵：

Def：针对两个随机变量X,Y,设其联合分布密度为p(x,y),X,Y的联合熵定义为：
$H(X,Y) = \sum_{x\epsilon X}^{}\sum_{y\epsilon Y}^{}-p(x,y)log_a(p(x,y))$

条件熵：

Def：针对两个随机变量X,Y,设其联合分布密度为p(x,y),则给定X下Y的条件熵定义为：
$\begin{equation} \begin{aligned} H(Y|X) &= -\sum_{x\epsilon X}p(x)H(Y|X=x) \\ &=\sum_{x\epsilon X}p(x) \left [ -\sum_{y\epsilon Y}p(y|x)log p(y|x) \right] \\ &=-\sum_{x\epsilon X}\sum_{y\epsilon Y}p(x,y)log p(y|x) \end{aligned} \end{equation}$

注：条件熵的推导是很有启发的，第一式子是定义，最后一个式子一般用来计算，并且可以知道条件熵的定义和一般人想像的不太一样，不是 $p(y|x)log p(y|x)$ 。

链式规则：

$H(X,Y)=H(X)+H(Y|X)$

链式规则的推导：

$\begin{equation} \begin{aligned} H(X)+H(Y|X) &= \sum_{x\epsilon X} p(x)log p(x) + \sum_{x\epsilon X} \sum_{y\epsilon Y} p(x,y)log p(y|x)\\ &= \sum_{x\epsilon X} \sum_{y\epsilon Y} p(x,y)log p(x)+\sum_{x\epsilon X} \sum_{y\epsilon Y} p(x,y)log p(y|x)\\ &= \sum_{x\epsilon X} \sum_{y\epsilon Y} p(x,y)(log p(x)+log p(y|x))\\ &= \sum_{x\epsilon X} \sum_{y\epsilon Y} p(x,y)log p(x,y)\\ &=H(X,Y) \end{aligned} \end{equation}$

理解：这个链式规则是很重要的，可以引出互信息。

互信息

$I(X;Y)=H(X)-H(X|Y)=\sum_{x,y}p(x,y) log \frac{ p(x,y)}{p(x)p(y)}$

这个互信息是基于上述的链式规则的。
$\begin{equation} H(Y)+H(X|Y) = H(X,Y) = H(X)+H(Y|X)\\ H(Y)+H(X|Y) = H(X)+H(Y|X)\\ H(X)-H(X|Y) = H(Y)-H(Y|X)\\ I(X;Y) = H(X)-H(X|Y) = H(Y)-H(Y|X)=I(Y;X)\\ \end{equation}$

理解：

（1)有一种比较经典的理解方式是信息增益。熵表示数据的信息量，数据混乱度越高，信息量越大。而 $H(X)$ 是X的信息量。 $H(X|Y)$ 是给定Y分布下的X的信息量。那么 $I(X;Y)=H(X)-H(X|Y)$ 也就是说给不给定Y对X信息量的变化影响。
（2）互信息用在决策树特征选择。

针对自然语言处理里的熵和互信息。

词熵（熵率）：(待理解多状态和多随机变量的区别)
为了能够对两个不同分布的熵进行比较，实际情况就如同上面多个最优编码问题之间比如问题1是甲乙两个人在不在房间，状态有4个。问题2是甲乙丙三个人在不在房间，状态有8个。这样这两个问题分布的熵是不好进行比较的。因为明显8个状态的优势比较大。求和数目变多了。所以我们应该关注每个状态的混乱度（如果从最初的提出，就是每个状态所占用的平均二进制编码的平均位数）。

$H_r=\frac{1}{n}H(X_n)=-\frac{1}{n}\sum_{x_n}p(x_n)log p(x_n)$

点间互信息：

$I(x,y)=log\frac{p(x,y)}{p(x)p(y)}$
这个是具体两个事件之间的互信息。不是两个随机变量的。在自然语言处理当中。对于词向量{X1,X2}。往往研究的是X1=‘a’ X2='b' 的相互之间的关系。

相对熵（KL散度）：

$\begin{equation} \begin{aligned} D(p||q)=\sum_{x\epsilon X} p(x)log \frac{p(x)}{q(x)}\\ rule: 0 log \frac{0}{q}=0, p log \frac{p}{0}= \infty \end{aligned} \end{equation}$

理解：

相对熵反应了对于一个随机变量，我们猜测的分布和实际的分布的差异。所以可以很直接就能发现，我们可以使用这个相对熵来对概率模型进行评价。

交叉熵:

$H(X,q) = \sum_{x\epsilon X}p(x)log q(x)$

理解：

对于相对熵
$D(p||q)=\sum_{x\epsilon X}p(x)log \frac{p(x)}{q(x)}$
对于这个式子我们进行展开。
$D(p||q)= \sum_{x\epsilon X} p(x) \frac{log p(x)}{log q(x)} = \left [- \sum_{x\epsilon X} p(x)log p(x) \right] - \left[ - \sum_{x\epsilon X} p(x)log q(x) \right] = H(X,p) - H(X,q)$