信息论模型

信息论从另外一个角度解释了许多机器学习的问题

  • 是不确定性的度量,类别不均匀程度的度量
  • 最大熵是一种状态的平衡分布,可看作一种自然法则
  • 互信息是随机变量相关性的度量

信息熵与最大熵

信息量是信息多少的度量:

$$ I(x_k) = \log \frac 1 {p_k} = - \log p_k $$

其中,$X = {x_k,| k = 0, \pm1,…,\pm N},\;p_k=P(X=x_k),\; 0\lt p_k \lt 1,\; \sum_{k=-N}^N p_k = 1 $

信息量性质:概率越小的事件,信息量越大

信息熵是信息量在全部数值域上的概率平均值:

  • 离散熵
    $$ H(X) = E[I(x_k)] = \sum_{k=-N}^N p_kI(x_k) = - \sum_{k=-N}^N p_k \log p_k $$

  • 微分熵
    $$ h(X) = - \int_{-\infty}^{\infty} p_X(x) \log p_X(x) dx = - E[\log p_X(x)]$$
    微分熵不是严格意义的信息熵,但是它用于衡量熵差时是有意义的。

从离散熵推导微分熵

离散熵性质

$$ 0 \le H(X) \le \log(2N+1) $$

其中 $2N+1$ 是总的离散值的数目,当且仅当对于某一 $k$ 概率 $p_k=1$ 时,不确定性为 $0$。当且仅当所有 $k$ 概率 $p_k= 1/(2N+1)$ 时,不确定性最大。

微分熵性质

  • 平移不变:
    $$ h(X+c) = h(X) $$
  • 尺度变化:
    $$ h(cX) = h(X) + log|c| \\ h(AX) = h(X) + log|det(A)| $$
    其中,$c$ 为常数,$A$ 为矩阵,$det(A)$ 是矩阵 $A$ 的行列式

定义:当根据不完整的信息作为依据进行推断时,应该由满足分布限制条件的具有最大熵的概率分布推得。

$$ \begin{align} & \;\; h(X) = - \int_{-\infty}^{\infty} p_X(x) \log p_X(x) dx \nonumber
\\ s.t. & \;\; p_X(x) \ge 0 \nonumber
\\ & \;\; \int_{-\infty}^{\infty} p_X(x)dx = 1 \nonumber
\\ & \;\; \int_{-\infty}^{\infty} p_X(x)g_i(x)dx = \alpha_i (i=1,2,…,m)\nonumber \end{align} $$

最大熵原理:学习概率模型时,在所有可能的概率模型中,熵最大的模型是最好的模型。

  • 在完全无约束的条件下,均匀分布的熵最大
  • 若已知均值和方差,高斯分布的微分熵最大


熵与互信息

条件熵

联合熵

互信息

互信息是信息熵与条件熵的差,其中熵可以是离散熵和微分熵。互信息等于信息增益,意义是给定一个随机变量 $X$ 后,$Y$ 所减少的不确定性。

互信息越大,说明两个变量越相关,给定一个变量后,另外一个变量减少的不确定性越大,剩余的不确定性越小。

互信息的性质

  • 非负性: 互信息 $I(X;Y)$ 总是非负的,即 $I(X;Y) \ge 0 $
  • 对称性: $I(X;Y) = I(Y;X)$
  • 不变性: 在随机变量的可逆交换下互信息是不变的,$u =f(x);\;v=g(y);\; I(X;Y) = I(U;V)$

互信息与熵的关系

熵的意义

相对熵

相对熵是衡量两个分布的平均信息差异,对于两个完全相同的分布,它们的相对熵为 $0$,相对熵越大,两个分布的差异越大。

$$ D_{p_x||q_x} = \int_{-\infty}^{+\infty} p_x(x) \log \left(\frac {p_x(x)} {q_x(x)} \right) = E \left[\log \left(\frac {p_x(x)} {q_x(x)} \right) \right] $$

相对熵性质

  • 非负性: $D_{p_x||q_x} \ge 0$
  • 不变性: 考虑可逆变换 $y=f(x)$,那么 $D_{p_x||q_x} = D_{p_y||q_y}$

互信息其实也是一种相对熵: $I(X;Y) = D_{p_{x,y}||p_xp_y}$

$$ I(X;Y) = \iint_{-\infty}^{\infty} p(x,y)\log \left(\frac {p_{x,y}(x,y)} {p_x(x)p_y(y)} \right) dxdy $$

最大熵模型

根据条件熵:

$$ H(Y|X) = -\sum_{x, y} P(x) P(y|x) \log P(y|x) = -\sum_{x, y} \tilde P(x) P(y|x) \log P(y|x)$$

其中 $\tilde P(x) = \frac {number\; of\; x} {number\;of\;all}$ 表示的是经验概率。

我们用特征函数 $f(x,y)$ 描述输入 $x$ 与输出 $y$ 之间的某一个事实,只有 $0$ 和 $1$ 两种值,最大熵模型根据最大熵原理在这样的特征限制下选择最优的概率分布。


理解最大熵模型里的特征函数

假设我们需要来判断 字是量词还是动词,目前有下面的训练数据集:

$$ (x_1,y_1) = (\text{一打火柴},\text{量词}) \\
(x_2,y_2) = (\text{三打啤酒},\text{量词}) \\
(x_3,y_3) = (\text{五打袋子},\text{量词}) \\
(x_4,y_4) = (\text{打电话},\text{动词}) \\
(x_5,y_5) = (\text{打篮球},\text{动词}) $$

通过观察我们可以发现打前面为数字时,打为量词,如果打后面跟着的是名词 ,则打为动词,我们用特征函数来表示为:

$$ f_1(x,y)=
\begin{cases}
1 & \quad \text{“打”的前面为数字} \\
0 & \quad \text{否则} \\
\end{cases}
\\f_2(x,y)=
\begin{cases}
1 & \quad \text{“打”的后面为名词} \\
0 & \quad \text{否则} \\
\end{cases}
$$

有了特征函数之后,我们将现有的数据代入这两个特征函数即有:

$$f_1(x_1,y_1) = f_1(x_2,y_2) = f_1(x_3,y_3) = 1,f_1(x_4,y_4) = f_1(x_5,y_5) = 0 \\
f_2(x_1,y_1) = f_2(x_2,y_2) = f_2(x_3,y_3) = 0,f_2(x_4,y_4) = f_2(x_5,y_5) = 1
$$


特征函数 $f(x,y)$ 关于经验分布 $\tilde P(x)$ 的期望值用 $E_{\tilde p}(f)$ 来表示:

$$ E_{\tilde p} (f) = \sum_{x, y} \tilde P(x,y) f(x,y) $$

特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 与经验分布 $\tilde P(x)$ 的期望值用 $E_p(f)$ 表示:

$$ E_p (f) = \sum_{x, y} \tilde P(x) P(y|x) f(x,y) $$

需要注意的是上式中的 $p(x,y)$ 是未知的。并且我们建模的目标是 $p(y|x)$,因此我们利用贝叶斯定理得到 $p(x,y)=p(x)p(y|x)$。此时,$p(x)$ 也还是未知,我们可以使用经验分布对 $p(x)$ 进行近似。

如果模型能够获取训练数据中的信息,那么可以假设这两个期望值相等,即:

$$ \sum_{x, y} \tilde P(x,y) f(x,y) = \sum_{x, y} \tilde P(x) P(y|x) f(x,y) $$

已知特征函数和约束条件,我们采用条件熵将熵的概念应用到条件分布上面去,就有了最大熵模型。

最大熵模型

中心极限定理:在适当的条件下,大量相互独立的随机变量均值经过适当标准化后收敛于正态分布,这组定理是数理统计学和误差分析的理论基础,指出了大量随机变量之和近似服从正态分布的条件。
所以根据微分熵最大等价于正态分布,我们认为,熵最大的模型就是最好的模型。

假设的模型 $P$ 有许多,它们组成一个模型空间 $\mathcal{P}$,而满足一系列特征函数期望构成的等式的概率分布构成了 $\mathcal{P}$ 的一个子集

$$ \mathcal{C}=\lbrace p \in \mathcal{P} | E_{\tilde{P}}(f_i)=E_{P}(f_i),i=1,2,…,n\rbrace $$

熵就是评估该空间中某个模型的指标,定义在条件概率分布 $P(Y|X)$ 上的条件熵为:

$$ H(P)=-\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$$

模型集合中条件熵 $H(P)$ 最大的模型成为最大熵模型,即最大熵模型 $p^*$ 就是:

$$ p^* = \arg\max_{p\in\mathcal{C}}H(p)$$

最大熵模型的直观理解:

  • 最大熵原理是统计学习的一般原理,将它应用到分类就得到了最大熵模型
  • 假设分类模型是一个条件概率分布 $P(Y|X)$,$X$ 表示输入,$Y$ 表示输出。这个模型表示的是对于给定的输入 $X$,以条件概率 $P(Y|X)$ 输出 $Y$
  • 给定一个训练数据集 $T$,我们的目标就是利用最大熵原理选择最好的分类模型

这个模型表示的是对于给定的输入 $X$,以条件概率 $P(Y|X)$ 输出 $Y$。


参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] 李航,《统计学习方法》,清华大学出版社