最大熵源码解读

先简要介绍一下最大熵，主要的参考资料是：

• 《自然语言处理的最大熵模型》常宝宝
• 《统计自然语言处理》第二章
• 《条件随机场综述》韩雪东
• 《Classical Probabilistic Models and Conditional Random Fields》 Roman Klinger

一个问题

假设已知随机变量X的一些特征，需要求解X的概率分布，怎么求解？X的概率分布长什么样子？

最大熵原理的思想就是：

在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的分布

什么是熵值最大？如何衡量熵值？

可参考《统计自然语言处理》第二章

1. 我们不是对随机变量\(X\)一无所知，而是知道一些特征

2. 选择那些符合特征的 概率分布，这个选择的过程，相当于最大熵模型的训练过程

3. 将 符合特征的概率分布 并且 熵值 最大的概率分布，作为最终结果

   ​

   这些特征相当于约束条件，即：需要选择符合这些特征的 概率分布。那如何衡量一个概率分布是否符合特征呢？

   这就要靠收集的样本数据了。

   把样本数据拿过来，对每个特征\(f_j\)计算数学期望 \(E^~_{p}f_j\)，这个数学期望称为：经验期望。

   待求解的概率分布\(X\)的数学期望，应该等于 经验期望----约束条件

   待求解的概率分布\(X\) 熵值最大----通过GIS算法迭代选取----熵值最大

经过证明，符合上述约束条件且熵值最大的概率分布可写成如下形式：

\[p(x)=\pi*\prod_{j=1}^{k}\alpha_j^{f_j(x)}\]

至于如何证明的，感兴趣的就去找相关参考文献吧。

特征函数\(f_j(x)\)是个二值函数，因此从上式可看出：要想知道 \(p(x)\)， 求出参数 \(\alpha_j\)即可（特征\(f_j(x)\)的权重）。而 \(\alpha_j\)可使用GIS算法迭代求解出来。

本文以和记录最大熵模型的源码实现细节。

整理好的训练样本 train.txt 如下：

Outdoor Sunny HappyOutdoor Sunny Happy DryOutdoor Sunny Happy HumidIndoor Rainy Happy DryIndoor Rainy Sad Dry....

第一列代表事件，比如 在家、外出，用论文中的集合A表示。

其他列代表环境(上下文)，用论文中的集合B表示。

Feature类代表特征，是个二值函数，封装了某事件对应的一个环境。一个事件，可对应多个环境。

/**     * 特征(二值函数)     */    class Feature    {        /**         * 事件，如Outdoor         */        String label;        /**         * 事件发生的环境，如Sunny         */        String value;

一个Instance对象代表一个观测实例。封装了一个事件及触发该事件的上下文环境，一个事件可由多个环境触发，故上下文环境用ArrayList保存。一个Instance对象相当于训练样本train.txt中的一行。

/**     * 一个观测实例，包含事件和时间发生的环境     */    class Instance    {        /**         * 事件（类别），如Outdoor         */        String label;        /**         * 事件发生的环境集合，如[Sunny, Happy]         */        List
    
      fieldList = new ArrayList
     
      ();
     
    

训练的目的：

训练的目的其实是计算出一组最优的拉格朗日乘子，对应表示每个特征函数有多重要。

这里的拉格朗日乘子，就是代码中的 weight[] 数组保存。

/**     * 训练模型     * @param maxIt 最大迭代次数     */    public void train(int maxIt)    {        int size = featureList.size();        weight = new double[size];               // 特征权重 (训练之后得到的模型)

计算经验期望

根据《自然语言处理的最大熵模型》论文，对于第 j 个特征而言，经验期望的计算公式如下：

\[E^{''}f_j=\Sigma_{i=1}^{N}{\frac{1}{N}}f(a_i,b_i)\]

经验期望 相当于 约束条件，代码实现如下：

for (int i = 0; i < size; ++i)        {        /**         * 特征i的经验期望 = 1/N*\Sigma_{j=1}^{N}(f_i(a_j, b_j))         * N = instanceList.size()         * \Sigma_{j=1}^{N}f(_i(a_j,b_j)) = featureCountList.get(i)         */            empiricalE[i] = (double) featureCountList.get(i) / instanceList.size();        }

经验期望计算出来后，保存起来就可以了，不需要重复计算。

计算模型期望

模型期望的计算公式可参考《自然语言处理的最大熵模型》论文的第五小节。需要说明一下的是：代码实现中，求解的是条件分布的最大熵。

本文实现的最大熵模型属于条件最大熵模型。

训练过程如下：

for (int i = 0; i < maxIt; ++i)        {            computeModeE(modelE);            for (int w = 0; w < weight.length; w++)            {                lastWeight[w] = weight[w];                weight[w] += 1.0 / C * Math.log(empiricalE[w] / modelE[w]);            }            if (checkConvergence(lastWeight, weight)) break;        }

• maxIt 是迭代次数

• computeModeE(modelE);计算模型期望

• 接下来的for循环更新权重

• checkConvergence(lastWeight, weight)检查是否收敛以停止迭代

  ​

具体的实现细节不说了（大概了解一下，等以后碰到了再深入研究一下）。整个最大熵JAVA实现的流程是：

根据训练样本：

Outdoor Sunny Happy

Outdoor Sunny Happy Dry

Outdoor Sunny Happy Humid

Indoor Rainy Happy Dry

Indoor Rainy Sad Dry

统计出 Outdoor 有多少次、Indoor 有多少次、在Sunny的条件下Outdoor又有多少次、在Rainy的条件下Indoor又有多少次……然后再根据论文中的公式，计算条件概率、联合概率、经验期望、模型期望啊……各种数据。然后再根据论文中的GIS算法来迭代，求解权重\(\alpha_j\)，最终将得到的权重保存下来weight[]数组，就是模型了，然后再拿它来进行预测。

public Pair
    
     [] predict(List
     
       fieldList)    {        double[] prob = calProb(fieldList);
     
    

计算一个新样本的预测的概率：计算 calProb(fieldList)

public double[] calProb(List
    
      fieldList)    {        //....            for (String field : fieldList)            {                Feature feature = new Feature(labels.get(i), field);                int index = featureList.indexOf(feature);                if (index != -1)                    weightSum += weight[index];            }    //....    p[i] = Math.exp(weightSum);
    

weightSum += weight[index]使用weight数组（保存的特征的权重）进行预测。

总结

有时候理论看多了，每次看到书上说：训练模型、用什么EM算法、迭代算法…求解代价函数的最优值、计算出模型的参数、使用模型参数对新样本预测……这些概念的时候，觉得挺抽象的。而看一个具体的实例，就能知道怎么从训练样本数据如何 转化成 论文中说的 各种需要的数据，模型的参数又是如何 用代码实现计算得到的，又是如何存储的……其实是如何把数学公式转化成编程语言，然后放在计算机上运行吧。

原文：https://www.cnblogs.com/hapjin/p/9093545.html