记最大熵模型的实现

作者: neroop | 来源:发表于2019-12-14 01:03 被阅读0次

记最大熵模型的实现
最大熵模型详细解析 | 统计学习方法学习笔记 | 数据分析 |
熵
逻辑斯谛回归与最大熵模型
逻辑斯谛回归与最大熵模型
最大熵模型
Day 2080：学习
最大熵模型
改进的迭代尺度法(IIS)详细解析 | 统计学习方法学习笔记 |
统计学习方法7.3 - 7.4笔记

最大熵模型是统计机器学习中常用的判别式模型（Discriminative model），在许多分类任务中都能用到。这里将以文本分类为例，实现模型。

在此之间，先简要了解一下模型原理。

原理介绍

最大熵从字面意思就是可以知道熵值最大，具体是指模型 $p(y|x)$ 满足熵值最大。即（下式条件熵展开）
$\begin{align} p^{\ast} &= \arg\max_p H[p] \\ &= \arg\max_p \sum_x p(x) \sum_y -p(y|x)\log p(y|x) \\ &= \arg\max_p -\sum_{x,y} p(x)p(y|x)\log p(y|x) \end{align}$
在“均衡”的状态下，熵是最大的。这意味着模型不对未知信息做任何先验假设。

当然，不是任意选择一个模型 $p(y|x)$ ，模型是需要满足训练数据的，所以训练数据约束了 $p$ 的选择。那么什么作为约束呢？训练数据的统计信息。利用训练数据的统计量需要与模型的统计量相等作为约束。这里使用“特征” $f_i(x,y)$ 的期望 $E$ 相等作为约束。

不妨设训练数据为观测( $x$ )与标签( $y$ )组成 $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$ 。针对这些数据，定义了一系列的特征函数 $f_i(x,y), i=1,2,3,\dots,k$ 。通常为二值函数如：
$\begin{equation} f_i(x,y) = \begin{cases} 1, & \text{if } x = \text{something and } y = \text{some label} \\ 0, & \text{if others} \end{cases} \end{equation}$
特征在经验分布 $\tilde{p}$ 和模型分布 $p$ 上的期望相等，有：
$\begin{align} E_{\tilde{p}}(f_i) &= E_p (f_i) \label{eq:ep_f} \\ \sum_{x,y} \tilde{p}(x,y)f_i(x,y) &= \sum_{x,y} \tilde{p}(x)p(y|x)f_i(x,y) \end{align}$
式(\ref{eq:ep_f})中 $x$ 的先验 $p(x)$ 以经验分布 $\tilde{p}(x)$ 估计。

最大熵模型可以描述为：
$\begin{align}\label{eq:origin} obj. \quad & p^{\ast} = \arg\max_p H[p] \\ s.t. \quad & E_{\tilde{p}} (f_i) = E_p (f_i) \quad i=1,2,3,\dots,k \\ & \sum_y p(y|x) = 1 \end{align}$
是一个在满足观测数据（训练数据）约束条件下的，熵值最大的模型。式(\ref{eq:origin})称为最大熵模型的原问题（对比后文将要提到的对偶问题）。

对于原问题进行求解是较为困难的，因此通过一定条件（拉格朗日对偶性）进行转换
$\begin{equation} L(w, p) = H[p] - \sum_i w_i(E_{\tilde{p}} (f_i) - E_p (f_i)) - w_0 (\sum_y p(y|x) - 1) \end{equation}$
根据对偶性有
$\begin{equation} \max_p\min_w L(w, p) = \min_w\max_p L(w, p) \end{equation}$
先求解 $\max_p L(w, p)$ ，令其关于 $w$ 的偏导为0， $\frac{\partial}{\partial w} L(w, p) = 0$ ，那么可以得到最大熵模型常见的参数化（参数 $w$ ）表示形式:
$\begin{equation}\label{eq:model_pw} p_w(y|x) = \frac{ \text{exp} \left(\sum_i w_if_i(x, y)\right)}{Z_w(x)} \end{equation}$
其中
$\begin{equation} Z_w(x) = \sum_y \text{exp} \left(\sum_i w_if_i(x, y)\right) \end{equation}$
再求解 $\min_w L(w, p_w)$ ，可以证明对 $\min L$ 的求解等价于 $p_w(y|x)$ 分布的最大似然估计。因此模型的最终求解变成了求解分布 $p(y|x,w)$ （即模型分布）的最大似然估计。
$\begin{equation}\label{eq:max_lik} \arg\max_w \prod_{x, y} p_w(y|x)^{\tilde{p}(x,y)} \iff \arg\max_w \sum_{x,y} \tilde{p}(x,y)\log p_w(y|x) \end{equation}$
最大换个符号就是最小，在将公式(\ref{eq:model_pw})带入有：
$\begin{align}\label{eq:loss} J(w) &= - \sum_{x,y} \tilde{p}(x,y)\log p_w(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \log Z_w(x) - \sum_{x,y} \tilde{p}(x,y)\sum_i w_if_i(x,y) \end{align}$
剩下的就是利用数值优化方法解(\ref{eq:loss})的最小值。涉及到梯度的数值优化算法，需要计算梯度
$\begin{equation}\label{eq:grad} \frac{\partial}{\partial w_i}J(w) = E_{p_w}[f_i] - E_{\tilde{p}}[f_i] \end{equation}$

模型实现

说了这么多，如果省去推导与证明过程，结果还是比较简单的。

模型表示

$p_w(y|x) = \frac{ \text{exp} \left(\sum_i w_if_i(x, y)\right)}{Z_w(x)}$
$Z_w(x) = \sum_y \text{exp} \left(\sum_i w_if_i(x, y)\right)$

参数估计

$J(w) = \sum_{x,y} \tilde{p}(x,y) \log Z_w(x) - \sum_{x,y} \tilde{p}(x,y)\sum_i w_if_i(x,y)$
$\frac{\partial}{\partial w_i}J(w) = E_{p_w}[f_i] - E_{\tilde{p}}[f_i]$

Coding

终于开始编码啦！在实现过程中，最关键部分是特征函数的定义。

以下列文本为例，第一列是类别，第二列是上下文信息。
$\begin{array}{l|l} \text{label} & \text{context} \\ \hline \text{Outdoor} & \text{Sunny Dry}\\ \text{Outdoor} & \text{Sunny Happy Humid}\\ \text{Indoor} & \text{Rainy Sad Dry}\\ \text{Indoor} & \text{Rainy Sad Humid}\\ \text{Indoor} & \text{Rainy Sad Humid} \end{array}$
特征可以使用unigram、bigram、trigram等或其他形式也行，这里假设只使用unigram。

那么上下文集合
$C = \{ \text{Sunny Dry}, \text{Sunny Happy Humid}, \text{Rainy Sad Dry}, \text{Rainy Sad Humid} \}$

上下文的unigram集合
$U = \{\text{Sunny}, \text{Dry}, \text{Happy}, \text{Humid}, \text{Rainy}, \text{Sad}\}$

标签集合
$L = \{\text{Outdoor}, \text{Indoor}\}$

特征函数可以定义为：
$f_{u,l}(x, y)= \begin{cases} 1, \quad & \text{if } u \in x \text{ and } y = l \\ 0, \quad & \text{if others} \end{cases}$
其中 $u \in U \text{ and } l \in L$ ， $(u, l)$ 是从训练数据中获取的，如(Sunny,Outdoor)是一个特征函数，而(Sad,Outdoor)不是。另外，对于训练数据，模型输入变量空间为上下文集合 $x \in C$ ，目标变量空间为标签集合 $y \in L$ 。所以特征矩阵表示为：
$\begin{array}{l|cccccccc} f_{u, l} \text{ \ } (x_i, y_i) & (x_0, y_0) & (x_0, y_1) & (x_1, y_0) & (x_1, y_1) & (x_2, y_0) & (x_2, y_1) & (x_3, y_0) & (x_3, y_1)\\ \hline \text{Sunny,Outdoor} & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ \text{Dry,Outdoor} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \text{Happy,Outdoor} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ \text{Humid,Outdoor} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ \text{Dry,Indoor} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ \text{Humid,Indoor} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \text{Rainy,Indoor} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\ \text{Sad,Indoor} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \end{array}$
可以看到，特征矩阵是十分稀疏的，因此在实现的时候是采用稀疏矩阵来存储。以Python为例，使用scipy.sparse模块。

from scipy.sparse import lil_matrix
# matrix shape: [|F|, |C|*|L|]
F = lil_matrix((len(f), len(x) * len(y)))

除了将训练数据转换成特征矩阵，还需要从中统计得到经验概率分布估计 $\tilde{p}(x,y)$ ，即统计 $(x,y)$ 的频次。
$\tilde{p}(x,y) = \frac{count(x,y)}{N}$
$\tilde{p}(x) = \sum_y \tilde{p}(x,y)$
$N$ 为训练集的总样本数， $count()$ 表示计算频次。如 $\tilde{p}(\text{Sunny Dry},\text{Outdoor}) = \frac{1}{5}$ ， $\tilde{p}(\text{Rainy Sad Humid},\text{Indoor}) = \frac{2}{5}$ 。经验分布同样是稀疏的，所以在存储时也使用稀疏矩阵。

count_xy = lil_matrix((len(x) * len(y), ))
p_tilde_xy = count_xy/N
p_tilde_x = np.sum(p_tilde_xy.reshap([len(x), len(y)]), axis=1)

有了特征矩阵后，其他部分就比较容易实现了，直接套公式即可。
$\tilde{v}_{x,y} = \sum_i w_if_i(x,y)$

# W dense matrix with shape: [1, |F|]
# F sparse matrix with shape: [|F|, |C|*|L|]
# energy shape: [1, |C|*|L|]
v = W * F

计算概率质量函数(PMF, Probability Mass Function)时，可以调整一下公式以便使用scipy的模块的logsumexp方法
$\begin{align} \notag p_w(y|x) &= \exp \log p_w(y|x) \\ \notag &= \exp \log \frac{ \exp(\tilde{v}_{x,y})}{\sum_y \exp(\tilde{v}_{x,y})} \\ \notag &= \exp \left( \tilde{v}_{x,y} - \underset{y}{\text{logsumexp}} (\tilde{v}_{x,y}) \right) \end{align}$

from scipy.special import logsumexp

def pmf():
  size_C, size_L = len(x), len(y)
  # sum_i wi * fi: shape [|C|*|L|, ]
  v = W * F
  # log Z(x) shape: [|C|, 1]
  logZ = logsumexp(v.reshape((size_C, size_L)), axis=-1, keepdims=True)
  # log Z(x) shape: [|C|*|L|, ]
  logZ = np.tile(logZ, (1, size_L)).reshape([-1, ])
  return np.exp(v - logZ)

现在已经有了模型的表示（即PMF），接下来就是进行参数估计了。实现采用scipy.optimize�模块，该模块实现了许多常用的数值优化算法。具体算法选择L-BFGS，其他算法也OK，喜欢的话实现个SGD也行。

import scipy.optimize as optimize

# loss function
# parameters initial value
# gradient function
optimize.fmin_l_bfgs_b(func, init, grad)

上文中提到了，取得模型最大似然值的参数是最优参数，所以需要求解的目标函数为(\ref{eq:loss})

def negative_likelihood():
  size_C, size_L = len(x), len(y)
  v = W * F
  logZ = logsumexp(v.reshape((size_C, size_L)), axis=-1)
  l1 = p_tilde_x * logZ
  l2 = p_tilde_xy * v
  return np.sum(l1) - np.sum(l2)

接下来是梯度函数(\ref{eq:grad})，它是模型分布与经验分布的特征期望差。其中期望分别为：
$E_{p_w}[f_i] = \sum_{x,y}\tilde{p}(x)p_w(y|x)f_i(x,y)$
$E_{\tilde{p}}[f_i] = \sum_{x,y} \tilde{p}(x,y)f_i(x,y)$

def gradient():
  """
  output shape: [|F|, ]
  """
  g = model_expectation() - empirical_expecation()
  return g

def expectation(self):
  size_C, size_L = len(x), len(y)
  px = np.tile(p_tilde_x.reshape([size_C, 1]), (1, size_L)).reshape([-1, ])
  return F * (pmf() * px)

def empirical_expecation():
  return F * p_tilde_xy

目标函数与梯度函数定义好后，代入scipy.optimize.fmin_l_bfgs_b即可求解模型得到最优参数估计 $w^{\ast}$

# shape: [|F|, ]
W_0 = numpy.zeros(len(F))
optimize.fmin_l_bfgs_b(negative_likelihood, W_0, gradient)

记最大熵模型的实现
最大熵模型是统计机器学习中常用的判别式模型（Discriminative model），在许多分类任务中都能用到。...
最大熵模型详细解析 | 统计学习方法学习笔记 | 数据分析 |
本文包括： 1.最大熵模型简介2.最大熵的原理3.最大熵模型的定义4.最大熵模型的学习 1.最大熵模型简介：最大...
熵
一、看文章 “熵”不起：从熵、最大熵原理到最大熵模型（一）“熵”不起：从熵、最大熵原理到最大熵模型（二）“熵”不起...
逻辑斯谛回归与最大熵模型
逻辑斯谛回归与最大熵模型逻辑斯谛回归模型最大熵模型最大熵模型的学习逻辑斯谛回归（logistic regr...
逻辑斯谛回归与最大熵模型
逻辑斯谛回归与最大熵模型首先介绍逻辑斯谛分布：二项逻辑斯谛回归模型：最大熵模型：最大熵原理是概率模型...
最大熵模型
在满足约束条件的模型集合中选取熵最大的模型，即不确定最大熵模型。最大熵模型就是要学习到合适的分布 P(y|x) ,...
Day 2080：学习
#统计学习最大熵模型：由最大熵原理推导而得最大熵原理是概率模型学习的一个准则，它认为所有可能的概率模型中，熵最...
最大熵模型
序本次记录的主要内容有：1、熵的概念2、最大熵模型推导模型属性 ME是经典的分类模型ME是对数线性模型最大熵...
改进的迭代尺度法(IIS)详细解析 | 统计学习方法学习笔记 |
IIS是一种最大熵模型学习的最优化算法。最大熵模型：舟晓南：统计学习方法 - 最大熵模型解析 | 数据分析，机器学...
统计学习方法7.3 - 7.4笔记
7.3 最大熵模型：拉格朗日乘子法最大熵模型：在待选集合C中挑选条件熵最大的条件概率分布（P），并且符合约束条件...