放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

最大熵的Java实现

目录

这是一个最大熵的简明Java实现,提供训练与预测接口。训练采用GIS训练算法,附带示例训练集。本文旨在介绍最大熵的原理、分类和实现,不涉及公式推导或其他训练算法,请放心食用。

最大熵理论

简介

最大熵属于辨识模型,能够满足所有已知的约束, 对未知的信息不做任何过分的假设。

什么叫已知的约束?本文不会使用晦涩的术语迷惑你,请看这样一个例子:

你的朋友每天都会“出门”或者“自宅”,这两种活动是同时受“天气”“心情”“湿度”(因为她是女孩子)影响的,我们可以称其为特征。

接下来我们从她的微博历史记录收集到了一些“活动<->特征”的对应例子,比如:

“今天天气真好,我很开心,所以出门逛街了”
“太干燥了,我要睡个美容觉!”
“我的备胎2号又来踩我的微博主页了,气死我了!魔都的雨冷死了,干脆看美剧算了!”
“男神约我逛街,就算天气差,我也要去!”
……

我们从直觉上可以感受到,这是一个……绿茶婊( ̄_ ̄|||) 跑题了……我们从直觉上可以感受到,“天气好”对“出门”是正相关的,“心情好”也是如此,心情差则是负相关,但是这并非绝对的,可能只有在“不干燥”的情况才成立。

最大熵可以将我们的直觉数字化,将其作为一种特征(或称特征函数),并且计算出每一种特征有多重要。约束指的是,预测出的结果的分布都满足对特征统计出的概率,且这些概率均匀分布,最终的结果是,导致系统的熵最大。

最大熵没有假设“天气”与“心情”独立分布,也没有承认“天气”对“心情”有影响,也许它的确有影响,但是最大熵只保证最终结果符合概率约束。

如果你有深厚的数学修养和足够的时间,可以选择阅读附录中的论文与推导过程,在那里你会得到严密的描述与公式推导。

分类

最大熵模型根据样本信息进行概率估计可分为2 种:联合最大熵模型和条件最大熵模型。假设a 是某个事件,b 是事件a 发生的环境(或称上下文),则a 和b 的联合概率记为p(a, b)。一般地,设所有可能发生的事件组成的集合为A,所有环境组成的集合是B,则对任意给定的a∈A, b∈B,求概率p(a, b)须建立联合最大熵模型。若要计算在b 的条件下,事件a 发生的概率,即概率p(a | b),则须建立条件最大熵模型。

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

实现

已经将项目开源在https://github.com/hankcs/MaxEnt ,请检出Java代码后进行下一步。

(PS:主要代码来自“CSDN厚”,请参考Reference)

训练集

假如我们把上文采集到的微博制作成计算机可读的数据集data/train.txt(已经包含在该开源项目中):

Outdoor Sunny Happy
Outdoor Sunny Happy Dry
Outdoor Sunny Happy Humid
Outdoor Sunny Sad Dry
Outdoor Sunny Sad Humid
Outdoor Cloudy Happy Humid
Outdoor Cloudy Happy Humid
Outdoor Cloudy Sad Humid
Outdoor Cloudy Sad Humid
Indoor Rainy Happy Humid
Indoor Rainy Happy Dry
Indoor Rainy Sad Dry
Indoor Rainy Sad Humid
Indoor Cloudy Sad Humid
Indoor Cloudy Sad Humid

我们看到数据最长有4列,每一行第一列表示当天的活动,其余的表示当天的环境。

训练

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

GIS算法

定义λi为特征函数i的拉格朗日乘子,C为每个事件最多有多少个特征,log中的分子与分母分别表示经验分布期望与模型估计期望。

GIS算法用第N次迭代的模型来估算每个特征在训练数据中的分布。如果超过了实际的(分式小于1,log得到负数),就把相应参数变小(加上负数就变小)。否则,将它们变大。当训练样本的特征分布和模型的特征分布相同时,就求得了最优参数。

这个式子用Java描述如下:

        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;
        }

预测

终于到了最激动人心的时刻了,作为备胎2号,你准备明天约她看电影。你从天气预报得知,明天天气晴朗,湿度良好。那么她答应你出门的概率是多大呢?

        String path = "data/train.txt";
        MaxEnt maxEnt = new MaxEnt();
        maxEnt.loadData(path);
        maxEnt.train(200);
        List<String> fieldList = new ArrayList<String>();
        fieldList.add("Sunny"); // 假如天晴
        fieldList.add("Humid"); // 并且湿润
        Pair<String, Double>[] result = maxEnt.predict(fieldList);  // 预测出门和自宅的概率各是多少
        System.out.println(Arrays.toString(result));

输出

[Outdoor=0.9747657631914007, Indoor=0.025234236808599233]

看来出门的概率高达97%。

……

嗯,忘了告诉你了,还要乘上一个她答应你做某事的概率,这个概率大概接近0。为什么?因为你是个码农噗哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈!

"单身狗也是狗,秀恩爱也属于虐狗行为,可以不爱,但请不要伤害。"

Reference

http://www.cnblogs.com/hexinuaa/p/3353479.html

http://blog.csdn.net/nwpuwyk/article/details/37500371

基于最大熵的依存句法分析.pdf

基于最大熵模型的汉语词义消歧与标注方法.pdf

基于最大熵模型的中文名词短语识别_张惠春.pdf

最大熵模型.pdf

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 最大熵的Java实现

分享到:更多 ()

评论 11

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #5

    楼主 你好 计算同一个样本的时候,是不是不同的特征的情况下 计算了多次呀?P(x)里面有交集,那条件熵的P(x)怎么解释?

    刺猬6个月前 (12-15)回复
  2. #4

    楼主,在不?有问题想问一下你。

    杨光1年前 (2016-03-22)回复
  3. #3

    weight怎么没有和f(x,y)相乘呢?看到的只是weight的相加呀

    杨光1年前 (2016-03-22)回复
  4. #2

    楼主,模型计算中modelE除了计算p(y|x),是否还应该计算p(x),我在源码中没有看到,不知道是不是我理解有偏差?

    bevanking2年前 (2015-03-10)回复
    • p(x) = 1.0 / instanceList.size()

      hankcs2年前 (2015-03-13)回复
      • 哦,这个我看到了,这样子计算是否欠妥,是否应该是p(x) = v(x) / instanceList.size(),其中v(x)是x出现的次数

        bevanking2年前 (2015-03-14)回复
        • 我觉得没问题,整体是个累加过程,最外层的循环保证了x每出现一次都会累加一次

          hankcs2年前 (2015-03-14)回复
          • 明白了,非常感谢!

            bevanking2年前 (2015-03-14)
          • 我觉得这里把p(x)设置成均匀分布跟p(x) = v(x) / instanceList.size()还是不一样的吧,虽然整体是累加的,但是两个还是不等价的

            ningyuwhut2年前 (2015-11-28)
          • 不,应该就是这样算的。请参考:http://www.hankcs.com/ml/the-logistic-regression-and-the-maximum-entropy-model.html ,“边缘分布P(X)的经验分布”这一句下面的算式。

            hankcs2年前 (2015-11-28)
  5. #1

    通俗易懂~顶露珠~

    kuakua3年前 (2014-11-25)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机