最大熵源码解读
最大熵源码解读先简要介绍一下最大熵,主要的参考资料是:
一个问题假设已知随机变量X的一些特征,需要求解X的概率分布,怎么求解?X的概率分布长什么样子? 最大熵原理的思想就是:
什么是熵值最大?如何衡量熵值? 可参考《统计自然语言处理》第二章
? 这些特征相当于约束条件,即:需要选择符合这些特征的 概率分布。那如何衡量一个概率分布是否符合特征呢? 这就要靠收集的样本数据了。 把样本数据拿过来,对每个特征(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算法迭代求解出来。 本文以最大熵的JAVA实现和最大熵模型.pdf 论文记录最大熵模型的源码实现细节。 整理好的训练样本 train.txt 如下: Outdoor Sunny Happy Outdoor Sunny Happy Dry Outdoor Sunny Happy Humid Indoor Rainy Happy Dry Indoor 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<String> fieldList = new ArrayList<String>(); 训练的目的:
这里的拉格朗日乘子,就是代码中的 weight[] 数组保存。 /** * 训练模型 * @param maxIt 最大迭代次数 */ public void train(int maxIt) { int size = featureList.size(); weight = new double[size]; // 特征权重 (训练之后得到的模型) 计算经验期望根据《自然语言处理的最大熵模型》论文,对于第 j 个特征而言,经验期望的计算公式如下: 经验期望 相当于 约束条件,代码实现如下: 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; }
? 具体的实现细节不说了(大概了解一下,等以后碰到了再深入研究一下)。整个最大熵JAVA实现的流程是: 根据训练样本:
统计出 Outdoor 有多少次、Indoor 有多少次、在Sunny的条件下Outdoor又有多少次、在Rainy的条件下Indoor又有多少次……然后再根据论文中的公式,计算条件概率、联合概率、经验期望、模型期望啊……各种数据。然后再根据论文中的GIS算法来迭代,求解权重(alpha_j),最终将得到的权重保存下来 public Pair<String,Double>[] predict(List<String> fieldList) { double[] prob = calProb(fieldList); 计算一个新样本的预测的概率:计算 public double[] calProb(List<String> fieldList) { //.... for (String field : fieldList) { Feature feature = new Feature(labels.get(i),field); int index = featureList.indexOf(feature); if (index != -1) weightSum += weight[index]; }
总结有时候理论看多了,每次看到书上说:训练模型、用什么EM算法、迭代算法…求解代价函数的最优值、计算出模型的参数、使用模型参数对新样本预测……这些概念的时候,觉得挺抽象的。而看一个具体的实例,就能知道怎么从训练样本数据如何 转化成 论文中说的 各种需要的数据,模型的参数又是如何 用代码实现计算得到的,又是如何存储的……其实是如何把数学公式转化成编程语言,然后放在计算机上运行吧。 最大熵JAVA实现github (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |