记最大熵模型的实现

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

最大熵模型是统计机器学习中常用的判别式模型（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)

记最大熵模型的实现

原理介绍

模型实现

模型表示

参数估计

Coding

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读