最大熵的Java实现

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

最大熵理论

简介

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

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

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

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

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

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

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

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

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

分类

最大熵模型根据样本信息进行概率估计可分为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));

输出

  1. [Outdoor=0.9747657631914007, Indoor=0.025234236808599233]

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

转自:http://www.hankcs.com/nlp/maximum-entropy-java-implementation.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

【接上篇】从白富美相亲看特征预处理与选择(下)

作者:龙心尘 &&寒小阳 出处: http://blog.csdn.net/han_xiaoyang/article/details/50503115 ...

3364
来自专栏新智元

【虫二】的人工智能

艺术创作一直是人类精神活动的最高级形式,自古以来,人们认为只有人类的智慧才能真正领悟艺术作品的深远意境和奥妙神韵,玄而又玄的艺术风格更是只可意会,不可言传。近些...

38611
来自专栏PPV课数据科学社区

【学习】R语言与机器学习(分类算法)logistic回归

由于我们在前面已经讨论过了神经网络的分类问题,如今再从最优化的角度来讨论logistic回归就显得有些不合适了。Logistic回归问题的最优化问题可以表述为:...

2884
来自专栏鹅厂优文

游戏人工智能 读书笔记 (六) AI算法简介——演化算法

Chapter 2.8 Hybrid Algorithm: Neuroevolution

2799
来自专栏大数据挖掘DT机器学习

R语言实现混合模型

普通的线性回归只包含两项影响因素,即固定效应(fixed-effect)和噪声(noise)。噪声是我们模型中没有考虑的随机因素。而固定效应是那些可预测因素,而...

8976
来自专栏专知

【干货荟萃】机器学习&深度学习知识资料大全集(二)(论文/教程/代码/书籍/数据/课程等)

【导读】转载来自ty4z2008(GItHub)整理的机器学习&深度学习知识资料大全荟萃,包含各种论文、代码、视频、书籍、文章、数据等等。是学习机器学习和深度学...

46412
来自专栏大数据挖掘DT机器学习

R语言与机器学习(分类算法)logistic回归

由于我们在前面已经讨论过了神经网络的分类问题,如今再从最优化的角度来讨论logistic回归就显得有些不合适了。Logistic回归问题的最优化问题可以表述为:...

7234
来自专栏量化投资与机器学习

【年度系列】监督学习标签在股市中的应用(代码+书籍)

由于低信噪比和非平稳的价格分布,预测未来股票价格走势是一件十分困难的事。现在流行的机器学习算法通常会给你带来不怎么满意的结果。

1926
来自专栏AI2ML人工智能to机器学习

一步一步走向锥规划 - LP

一般来说凸优化(Convex Optimization, CO)中最一般的是锥规划 (Cone Programming, CP) 问题, 前面我们介绍了最简单...

1022
来自专栏机器学习、深度学习

人群运动--Scene-Independent Group Profiling in Crowd

Scene-Independent Group Profiling in Crowd CVPR2014 http://www.ee.cuhk.edu.hk/...

2289

扫码关注云+社区

领取腾讯云代金券