使用 SharpEntropy 进行最大熵建模
4.84/5 (38投票s)
2005年7月24日
12分钟阅读
210507
6407
介绍了一个最大熵建模库，并结合两个示例讨论了其用法：一个预测结果的简单示例，以及一个英语分词器。
- 下载源代码文件（.NET 1.0）- 415 Kb
- 下载演示项目（.NET 1.0）- 494 Kb
- 下载源代码文件（.NET 2.0）- 418 Kb
- 下载演示项目（.NET 2.0）- 485 Kb
- 下载 Sqlite 模型读写器（.NET 2.0）- 273 Kb
概述
本文介绍了一个名为 SharpEntropy 的最大熵建模库，并讨论了它的用法。首先通过一个预测结果的简单示例，然后展示了一种将英语句子分割成组成标记（对自然语言处理很有用）的方法。请注意，由于大部分代码是基于在 LGPL 许可证下发布的原始 Java 库的转换，本文提供的源代码也遵循 LGPL 许可证。这意味着，它可以自由地用于任何许可证下的软件，但如果您修改了库本身并且这些修改不是为了您私人使用，您必须公开这些修改的源代码。
另一篇文章 英语句子统计解析 展示了 SharpEntropy 如何用于执行复杂的自然语言处理任务。本文提供了一个小的附加库 SharpEntropySqlite，它可以方便地将 SharpEntropy 创建的最大熵模型存储在 Sqlite 数据库中。
引言
SharpEntropy 是 MaxEnt 工具包的 C# 移植版本，该工具包可从 SourceForge 获取。MaxEnt 是一个成熟的 Java 库，最初由 Jason Baldridge、Tom Morton 和 Gann Bierner 创建。SharpEntropy 基于 MaxEnt 工具包的最新版本（2.3.0），该版本于 2004 年 8 月发布。
最大熵建模是一种通用的机器学习技术，最初为统计物理学而开发，但已广泛应用于计算机视觉和自然语言处理等领域。当存在一个内部未知但必须由计算机建模的复杂过程时，它可以被有效应用。与任何统计建模技术一样，它依赖于数据样本的存在，该样本显示了给定输入集下过程生成的输出。对该样本进行分析，并从中生成一个模型，该模型封装了从样本中推断出的关于该过程的所有规则。然后，当提供样本数据中不存在的输入集时，该模型将用于预测该过程的输出。
应该使用哪种技术从样本数据生成模型？最大熵方法遵循“最大化熵”原则——即，它选择一个模型，该模型考虑了样本数据中所有可用事实，但除此之外，保留尽可能多的不确定性。该原则可以表述为：“除了您已观察到的内容外，不要对您的概率分布做任何假设”。
数学能力较强的读者可以参考文章末尾的一些参考文献，以了解更多关于最大熵方法的信息。
一个简单示例
假设您想预测某人是否会在特定一天带伞出门。首先，您需要通过观察多天的男人行为来收集一些样本数据。
Day 1 Warm Dry No_Umbrella
Day 2 Cold Dry No_Umbrella
Day 3 Cold Rainy Umbrella
Day 4 Cold Dry Umbrella
Day 5 Warm Dry No_Umbrella
经过五天后，您意识到可能还有一个额外因素在起作用：这个人早上是否迟到了。因此，您收集了更多样本数据。
Day 6 Cold Dry Early Umbrella
Day 7 Cold Rainy Early Umbrella
Day 8 Cold Dry Late No_Umbrella
Day 9 Warm Rainy Late No_Umbrella
Day 10 Warm Dry Late No_Umbrella
这些数据行中的每一行都代表一个训练事件。每个训练事件都有一个结果（在本例中是“Umbrella”或“No_Umbrella”），以及一个上下文，它由一个或多个谓词（“Cold”、“Dry”等）组成。上下文是导致事件结果的谓词组合。请注意，谓词的顺序并不重要。
我们简单的雨伞示例的训练数据可以在 SimpleExample 可执行文件同文件夹下的名为 data.txt 的文件中找到。这是一个文本文件，每行一个训练事件。在每一行中，上下文谓词和结果由单个空格分隔（结果始终假定为行中的最后一个字符串）。选择此训练数据格式是因为 SharpEntropy 库中已有一个名为 SharpEntropy.IO.PlainTextByLineDataReader 的类，它可以读取以这种方式分隔的文本文件。以下代码摘自 SimpleExample 应用程序的源代码，展示了如何加载此训练数据文件并用于生成最大熵模型。
System.IO.StreamReader trainingStreamReader =
new System.IO.StreamReader(trainingDataFile);
SharpEntropy.ITrainingEventReader eventReader =
new SharpEntropy.BasicEventReader(new
SharpEntropy.PlainTextByLineDataReader(trainingStreamReader));
SharpEntropy.GisTrainer trainer = new SharpEntropy.GisTrainer();
trainer.TrainModel(eventReader);
mModel = new SharpEntropy.GisModel(trainer);
GisTrainer 类使用 GIS（广义迭代尺度）方法训练最大熵模型。有许多其他方法可以训练 MaxEnt 模型，其中许多方法的性能优于 GIS。然而，目前 GIS 是 Java MaxEnt 库唯一支持的方法，因此也是唯一将其算法转换为 SharpEntropy 使用的方法。训练器类期望接收由实现 ITrainingEventReader 接口的类提供的事件流。PlainTextByLineDataReader 和 BasicEventReader 类共同提供了从定界文本文件中提供此事件流的手段，该文件的路径存储在字符串变量 trainingDataFile 中。
结果是 GisModel 类的一个实例，这是目前唯一实现了 IMaximumEntropyModel 接口的类。模型训练完成后，就可以用于预测未来的结果。SimpleExample 应用程序允许您通过下拉列表选择谓词组合。
当单击“Take Umbrella?”按钮时，所选特征将被添加到字符串数组中，并传递给 GisModel 对象的 Evaluate 方法。
private void btnOutcome_Click(object sender, System.EventArgs e)
{
ArrayList context = new ArrayList();
if (cboTemperature.Text != "Unknown")
{
context.Add(cboTemperature.Text);
}
if (cboPrecipitation.Text != "Unknown")
{
context.Add(cboPrecipitation.Text);
}
if (cboTiming.Text != "Unknown")
{
context.Add(cboTiming.Text);
}
double[] probabilities = mModel.Evaluate((string[])
context.ToArray(typeof(string)));
lblOutcome.Text = probabilities[mUmbrellaOutcomeId].ToString("N5");
}
Evaluate 方法返回一个包含所有可能结果概率的 double 数组。这些概率加起来总是等于 1。在这个简单的例子中，只有两种可能的结果，“Umbrella”和“No_Umbrella”，所以只显示带伞的概率就足够了。IMaximumEntropyModel 接口包含许多其他有用的方法，用于理解预测结果，更多详细信息可以在 NDoc 生成的库帮助文件中找到。Evaluate 方法有一个接受 double 数组作为参数的重载版本的原因是，在更复杂的情况下，当 Evaluate 方法可能被调用数百甚至数千次时，通过不断地循环使用一个已预先分配好大小以匹配可能结果数量的 double 数组，可以提高性能。然后，如果需要，可以将该 double 数组传递给 GetBestOutcome 方法以获取最可能结果的名称，或者传递给 GetAllOutcomes 方法，该方法将返回一个格式化字符串，列出所有可能的结果及其概率。
读写模型
在上面的简单示例中，每次运行都会从训练数据中构建模型。对于如此小的数据集来说，这是可以接受的，但在实际应用中，训练数据文件可能会大得多，并且在应用程序加载时需要从头开始重建模型，这在开销上是不现实的。相反，模型将构建一次，保存到持久存储中，然后在需要时从存储中读回。SharpEntropy 库在 SharpEntropy.IO 命名空间中提供了三种可以用来存储模型的格式，以及三组 Reader 和 Writer 类来访问这三种格式。
- 纯文本格式（
PlainTextGisModelReader和PlainTextGisModelWriter）。这种格式具有双重优点：它（或多或少）是人类可读的，因此您可以检查数据训练的结果，并且它与 Java MaxEnt 库生成的纯文本模型文件兼容。它产生的文件大小较大，通常仅在开发过程中使用，而不是在生产环境中使用。 - “Java 兼容”二进制格式（
JavaBinaryGisModelReader和JavaBinaryGisModelWriter）。文件大小比纯文本格式小，但二进制文件与 Java MaxEnt 库是互操作的。这会导致一些性能损失，原因在于需要反转数据项的字节顺序（Java 库偏好大端数据格式），并且 MaxEnt 格式的效率不高。 - 二进制格式（
BinaryGisModelReader和BinaryGisModelWriter）。这是您通常会选择的格式。生成的文件比 Java 兼容格式稍小，并且读取速度更快。
将模型写入其中一种文件格式并读回的代码很简单。
//write a model to disk
string modelDataFile = @"C:\model.nbin";
SharpEntropy.IO.BinaryGisModelWriter writer =
new SharpEntropy.IO.BinaryGisModelWriter();
writer.Persist(model, modelDataFile);//read a model in from disk
SharpEntropy.IO.BinaryGisModelReader reader =
new SharpEntropy.IO.BinaryGisModelReader(modelDataFile);
SharpEntropy.IMaximumEntropyModel model = new SharpEntropy.GisModel(reader);
可以实现新的格式，并且根据您选择的格式与现有格式的相似性，实现 IGisModelReader 接口或继承 GisModelReader 和 GisModelWriter 类可能会很有用。我已经实现了使用 SQL Server 和 Sqlite 作为后备存储的 Reader/Writer 对的可用实现。您可以从文章顶部的链接下载 Sqlite 实现。然而，我仍在寻找一种最优效的只读文件格式。
更复杂的示例 - 对英语句子进行分词
Java MaxEnt 库被另一个 LGPL 许可的开源 Java 库 OpenNLP（OpenNLP）使用，该库提供了许多基于最大熵模型的自然语言处理工具。OpenNLP 库的 C# 移植版本在我的第二篇文章 英语句子统计解析 中提供，但为了提供一个更复杂的 SharpEntropy 示例，以及让您了解 OpenNLP 的代码风格，这里有一个基于 Java OpenNLP 团队创建的最大熵模型来分词英语句子的简单应用程序。
分词发生在 MaxentTokenizer.Tokenize 方法中。
public string[] Tokenize(string input)
{
ArrayList tokens = new ArrayList();
string[] candidateTokens = input.Split(mWhitespaceChars);
foreach (string candidateToken in candidateTokens)
{
if (candidateToken.Length < 2)
{
tokens.Add(candidateToken);
}
else if (mAlphaNumericRegex.IsMatch(candidateToken))
{
tokens.Add(candidateToken);
}
else
{
int startPos = 0;
int endPos = candidateToken.Length;
for (int currentPos = startPos + 1;
currentPos < endPos; currentPos++)
{
double[] probabilities =
mModel.Evaluate(GenerateContext(candidateToken,
currentPos));
string bestOutcome = mModel.GetBestOutcome(probabilities);
if (bestOutcome == "T")
{
tokens.Add(candidateToken.Substring(startPos,
currentPos - startPos));
startPos = currentPos;
}
}
tokens.Add(candidateToken.Substring(startPos,
endPos - startPos));
}
}
return (string[])tokens.ToArray(typeof(string));
}
它首先在每个空格字符处将输入分割成候选标记。然后检查每个候选标记，如果它小于两个字符长，或者只包含字母数字字符，则将其接受为一个标记。否则，将逐个检查候选标记中的每个字符位置，看它是否应该被分割成多个标记。这是通过在 GenerateContext 方法中构建一组与可能的分割位置相关的谓词来实现的。各种特征，例如分割前后的字符，两侧字符是字母还是数字，等等，都被用来生成这组谓词。然后，这组谓词会根据最大熵模型进行评估。模型有两个可能的结果，“T”表示分割，“F”表示不分割，因此如果最佳结果是“T”，则分割位置左侧的字符将分离出来形成一个新标记。
示例应用程序允许您输入一个输入句子，对其进行分词，并将结果标记逐行显示在一个只读文本框中。
Sqlite 模型读写器
SharpEntropy 和其 Java 原版一样，将所有最大熵模型数据一次性保存在内存中，而复杂的模型（例如 OpenNLP 使用的模型）很容易消耗数百 MB。我一直在研究将大部分模型保存在永久存储中，仅在需要时访问的可能性。这是 SharpEntropySqlite 库的一个早期成果，它将模型数据存储在 Sqlite 数据库中，并且仅在查询 GIS 模型时按需访问。该库使用的 ADO.NET Sqlite 提供程序是 Robert Simpson 创建的公共领域提供程序，可在 SourceForge 上找到。
关于 Java 转换的说明
最后，我认为提供一些关于 SharpEntropy 库如何开发的解释可能会很有趣。我没有数学背景，我的兴趣主要在于使用最大熵进行实际应用的潜力，包括统计自然语言处理。
尽管我一开始使用的是 MaxEnt 源代码和微软的 Java Language Conversion Assistant (JLCA)，但 SharpEntropy 代码随后经过了多次迭代才达到现在的状态。我努力使 Java 的代码起源尽可能不显眼，而不是让库看起来像用外语写的 Java。我经历的一些主要编码阶段（有些是反复进行的）是：
- 使用 JLCA 进行转换，并修复生成的代码中的错误。此阶段的结果是可编译的 C# 代码，但带有浓厚的 Java 风格。MaxEnt 库使用开源的 Trove 集合库来处理许多 MaxEnt 模型数据结构，因此此阶段还包括将 Trove 的大部分内容仔细地转换为 C#。
- 从代码中移除类 Java 的结构，并用 C# 版本替换它们，尤其是在 C# 版本已知更有效的情况下。仍然存在一些类 Java 的残余，但希望它们数量不多。
- 更改代码中的大量标识符，从名称不清晰的变量到类和文件，特别是那些名称后缀与 .NET 框架约定冲突的（例如
EventStream）。 - 运行 FxCop 并尽可能修复提出的问题。
- 性能调优。我做了大量工作来尝试减小 SharpEntropy 的内存占用。我的优化现在已向后移植到 Java MaxEnt 库。
参考文献
- “OpenNLP MaxEnt 主页” - 托管在 SourceForge 上的 Java MaxEnt 项目的主页。
- “最大熵建模” - 一个有用的网页，链接到网络上的最大熵资源。
- “简要 MaxEnt 教程” - 超链接教程，介绍最大熵建模，并附带数学公式！
- “MaxEnt 阅读清单” - 一篇关于最大熵文章的参考文献。
- 英语句子统计解析 - 后续文章，展示了如何使用 SharpEntropy 进行自然语言处理任务。
历史
- 第三版（2006 年 5 月 3 日）。添加了代码的 .NET 2.0 版本，以及 Sqlite 模型读写器。
- 第二版（2005 年 11 月 16 日）。添加了 OpenNLP 文章的链接；对文本进行了少量编辑。
- 初始版本（2005 年 7 月 24 日）。