Click here to Skip to main content
15,861,168 members
Articles / Artificial Intelligence / Machine Learning
Article

Maximum Entropy Modeling Using SharpEntropy

Rate me:
Please Sign up or sign in to vote.
4.84/5 (42 votes)
9 May 200612 min read 200K   6.4K   109   53
Presents a Maximum Entropy modeling library, and discusses its usage, with the aid of two examples: a simple example of predicting outcomes, and an English language tokenizer.

Overview

This article presents a maximum entropy modeling library called SharpEntropy, and discusses its usage, first by way of a simple example of predicting outcomes, and secondly, by presenting a way of splitting English sentences into constituent tokens (useful for natural language processing). Please note that because most of the code is a conversion based on original Java libraries published under the LGPL license, the source code available for download with this article is also released under the LGPL license. This means, it can freely be used in software that is released under any sort of license, but if you make changes to the library itself and those changes are not for your private use, you must release the source code to those changes.

A second article, Statistical parsing of English sentences, shows how SharpEntropy can be used to perform sophisticated natural language processing tasks. A small additional library, SharpEntropySqlite, downloadable with this article, provides a simple means of storing maximum entropy models created by SharpEntropy in a Sqlite database.

Introduction

SharpEntropy is a C# port of the MaxEnt toolkit available from SourceForge. MaxEnt is a mature library written in Java, originally created by Jason Baldridge, Tom Morton, and Gann Bierner. SharpEntropy is based upon the latest version (2.3.0) of the MaxEnt toolkit, released in August 2004.

Maximum entropy modeling is a general-purpose machine learning technique originally developed for statistical physics, but which has been employed in a wide variety of fields, including computer vision and natural language processing. It can be usefully applied whenever there is a complex process whose internals are unknown but which must be modeled by the computer. Like any statistical modeling technique, it relies on the existence of a data sample that shows, for given sets of input, what output the process generates. This sample is analysed, and from it, a model is generated, encapsulating all the rules about the process that could be inferred from the sample. This model is then used to predict the output of the process, when supplied with sets of input not found in the sample data.

What technique should be used to generate the model from the sample data? The maximum entropy method follows the principle of “maximizing entropy” – that is, it chooses the model that takes account of all the facts available in the sample data but otherwise preserves as much uncertainty as possible. The principle could be stated as: "Don’t assume anything about your probability distribution other than what you have observed".

The more mathematically inclined may wish to follow some of the references at the end of the article to find out more about the maximum entropy method.

A Simple Example

Suppose you wish to predict whether on a given day, a certain man will leave the house with his umbrella or not. The first thing you do is gather some sample data by observing over a number of days what the man does:

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

After five days, you realise that there may be an additional factor at work: whether the man is late in the morning or not. So, you collect some more sample data:

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

Each of these rows of data represents a training event. Each training event has an outcome (in this example, either "Umbrella" or "No_Umbrella"), and a context, which consists of one or more predicates ("Cold", "Dry" etc.). The context is the combination of predicates that lead to the outcome of the event. Note that the order of the predicates is not significant.

The training data for our simple umbrella example can be found in the file named data.txt in the same folder as the SimpleExample executable. This is a text file with one training event per line. In each line, the contextual predicates and the outcome are separated by single spaces (the outcome is always assumed to be the last string on the line). This training data format is chosen because the SharpEntropy library already has a class called SharpEntropy.IO.PlainTextByLineDataReader that can read text files delimited in this way. The following code, taken from the source of the SimpleExample application, shows how this training data file can be loaded and used to generate a maximum entropy model:

C#
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);

The GisTrainer class trains a maximum entropy model using the GIS (Generalized Iterative Scaling) method. There are a number of other methods for training MaxEnt models, many of which outperform GIS. Currently, however, GIS is the only method that the Java MaxEnt library supports, and therefore the only method whose algorithm was converted for use in SharpEntropy. The trainer class expects to be fed with a stream of events provided by a class that implements the ITrainingEventReader interface. The PlainTextByLineDataReader and BasicEventReader classes together provide the means to supply this stream of events from the delimited text file, whose path is stored in the string variable trainingDataFile.

The result is an instance of the GisModel class, the only class currently coded that implements the IMaximumEntropyModel interface. Once the model has been trained, it can be used to predict future outcomes. The SimpleExample application lets you choose a combination of predicates using dropdown lists:

SimpleExample application user interface

When the Take Umbrella? button is clicked, the chosen features are added to an array of strings and passed into the Evaluate method of the GisModel object:

C#
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");
}

The Evaluate method returns an array of doubles containing the probabilities for all the possible outcomes. Together, these probabilities will always add up to 1. In this simple example, there are only two possible outcomes, Umbrella and No_Umbrella, so it is easy enough to just display the probability of taking the umbrella. The IMaximumEntropyModel interface contains a number of other useful methods for making sense of the results of a prediction, the details of which can be found in the NDoc-generated library help file. The reason why there is an overloaded version of the Evaluate method that takes in an array of doubles as a parameter, is that in more complicated scenarios, where the Evaluate method may be called many hundreds or thousands of times, performance is improved by continually recycling an array of doubles that is already pre-sized to match the number of possible outcomes. That array of doubles can then be passed, if required, to the GetBestOutcome method, to obtain the name of the most likely outcome, or to the GetAllOutcomes method, which will return a formatted string, listing all the possible outcomes, together with their probabilities.

Reading and Writing Models

In the simple example above, the model is built from the training data, each time it is run. This is acceptable with such a small training data set, but in a real world application, the training data file is likely to be much, much larger, and it would be unrealistic to require the overhead of rebuilding a model from training data at application load time in this way. Instead, the model would be built once, saved to persistent storage, and then read back from storage when needed. The SharpEntropy library provides three file formats in the SharpEntropy.IO namespace that may be used to store the model, and three sets of Reader and Writer classes to access the three formats:

  • Plain text format (PlainTextGisModelReader and PlainTextGisModelWriter). This format has the twin advantages that it is (more or less) human readable, so you can check the results of the data training, and it is compatible with the plain text model files generated by the Java MaxEnt library. It produces large file sizes, and would normally be used only during development, not in production.
  • "Java compatible" binary format (JavaBinaryGisModelReader and JavaBinaryGisModelWriter). The file sizes are smaller than plain text, but the binary files are interoperable with the Java MaxEnt library. This results in some performance sacrifices, caused by the need to reverse the byte order of data items (the Java library preferring Big-Endian data formats) and the fact that the MaxEnt format is less than optimal.
  • Binary format (BinaryGisModelReader and BinaryGisModelWriter). This is the format you would normally choose. The files produced are slightly smaller than the Java compatible format, and they are faster to read in.

The code to write a model to one of these file formats, and to read it back, is simple:

C#
//write a model to disk
string modelDataFile = @"C:\model.nbin";
SharpEntropy.IO.BinaryGisModelWriter writer = 
          new SharpEntropy.IO.BinaryGisModelWriter();
writer.Persist(model, modelDataFile);
C#
//read a model in from disk
SharpEntropy.IO.BinaryGisModelReader reader = 
       new SharpEntropy.IO.BinaryGisModelReader(modelDataFile);
SharpEntropy.IMaximumEntropyModel model = new SharpEntropy.GisModel(reader);

It is possible to implement new formats, and depending on the similarity of your chosen format to the existing ones, it may be useful to implement the IGisModelReader interface or to inherit from the GisModelReader and GisModelWriter classes. I have working implementations of Reader/Writer pairs that use SQL Server and Sqlite as backing stores. You can download the Sqlite implementation from the link at the top of the article. However, I am still looking for an optimally efficient read-only file format.

A More Complex Example - Tokenizing English Sentences

The Java MaxEnt library is used by another LGPL-licensed open source Java library, called OpenNLP, which provides a number of natural language processing tools based on maximum entropy models. A C# port of the OpenNLP library is available in my second article, Statistical parsing of English sentences, but to provide a more complex SharpEntropy example, as well as to give a flavor of the OpenNLP code, here is a small application to tokenize English sentences, based on a MaxEnt model created by the Java OpenNLP team.

English Tokenizer application user interface

Tokenizing occurs in the MaxentTokenizer.Tokenize method:

C#
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));
}

It first splits the input at each whitespace character into candidate tokens. Each candidate token is then examined, and if it is less than two characters long, or consists only of alphanumeric characters, then it is accepted as a token. Otherwise, each character position in the candidate token is examined in turn to see if it should be split into more than one token at that position. This is done by building up a set of predicates related to the possible split position in the GenerateContext method. Various features, such as the characters before and after the split, whether the characters on each side are letters or numbers, and so on, are used to generate this set of predicates. This set of predicates is then evaluated against the MaxEnt model. The model has two possible outcomes, "T" for a split, and "F" for a non-split, so if the best outcome is "T", then the characters to the left of the split position are separated off into a new token.

The sample application simply allows you to type in an input sentence, tokenizes it, and lists the resulting tokens, each on a separate line, in a read-only textbox.

A Sqlite Model Reader/Writer

SharpEntropy, like its Java original, holds all of the maximum entropy model data in memory at once, and complex models (such as those used by OpenNLP) may easily consume hundreds of MB. I have been looking into the possibility of keeping most of the model in permanent storage and only accessing it when necessary. An early result of this is the SharpEntropySqlite library, which stores model data in a Sqlite database, and only accesses it on demand when the GIS model is queried. The ADO.NET Sqlite provider used by this library is the public domain one created by Robert Simpson and available on SourceForge.

Notes On The Java Conversion

Lastly, I thought it may be interesting to provide some explanation of how the SharpEntropy library developed. I do not have a mathematical background, and my interest lies largely in the possibility of using maximum entropy for practical purposes, including statistical natural language processing.

Though I started off with a copy of the MaxEnt source code and Microsoft's Java Language Conversion Assistant (JLCA), the SharpEntropy code has subsequently been through many iterations to reach its current state. I have endeavored to make the Java origins of the code as unnoticeable as possible, rather than having the library resemble Java written in a foreign language. Some of the major phases of coding I went through (some revisited iteratively) were:

  • Conversion with the JLCA, and fixing of errors in the generated code. The result of this phase was compilable C# code with a heavy Java flavour. The MaxEnt library uses the open source Trove collections library to handle many of the MaxEnt model data structures, so this phase also involved dutifully converting a large chunk of Trove into C# as well.
  • Removal of Java-like constructs from the code and replacing them with C# versions, particularly where the C# version is known to be more efficient. Some Java-like remnants remain, but hopefully they are few in number.
  • Changing a large number of identifiers in the code, ranging all the way from variables with unclear names to classes and files, particularly those with endings that clash with .NET framework conventions (EventStream, for example).
  • Running FxCop and fixing as many of the issues raised as possible.
  • Tuning for performance. I did a lot of work trying to reduce SharpEntropy's memory footprint. My optimizations have now been back-ported into the Java MaxEnt library.

References

History

  • Third version (3rd May 2006). Added .NET 2.0 versions of the code, plus Sqlite Model Reader/Writer.
  • Second version (16th November 2005). Added links to OpenNLP article; minor edits to the text.
  • Initial version (24th July 2005).

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
United Kingdom United Kingdom
Richard Northedge is a senior developer with a UK Microsoft Gold Partner company. He has a postgraduate degree in English Literature, has been programming professionally since 1998 and has been an MCSD since 2000.

Comments and Discussions

 
QuestionA Simple Example Pin
Member 126640899-Jun-21 2:09
Member 126640899-Jun-21 2:09 
Questionfeature types Pin
rezamin11-Jun-11 0:11
rezamin11-Jun-11 0:11 
GeneralReading Large Model file from disk cause error Pin
adzy24-May-11 21:36
adzy24-May-11 21:36 
Questiontraining data for word tokenize? Pin
vuhong17-May-11 23:45
vuhong17-May-11 23:45 
GeneralMy vote of 5 Pin
peterkm6-Aug-10 1:30
professionalpeterkm6-Aug-10 1:30 
QuestionOn maxentropy model Pin
janapatisiva10-Jan-10 19:17
janapatisiva10-Jan-10 19:17 
GeneralThank you!!! Pin
Phan Dung13-Aug-09 7:28
Phan Dung13-Aug-09 7:28 
QuestionNERC Pin
gcurkov6-Aug-09 19:55
gcurkov6-Aug-09 19:55 
Questionkey not found in dictionary Pin
zink204018-Jan-09 19:46
zink204018-Jan-09 19:46 
AnswerRe: key not found in dictionary Pin
Richard Northedge20-Jan-09 9:26
Richard Northedge20-Jan-09 9:26 
AnswerRe: key not found in dictionary Pin
zink204021-Jan-09 1:57
zink204021-Jan-09 1:57 
GeneralRe: key not found in dictionary Pin
Richard Northedge21-Jan-09 8:57
Richard Northedge21-Jan-09 8:57 
GeneralRe: key not found in dictionary Pin
zink204021-Jan-09 17:28
zink204021-Jan-09 17:28 
GeneralRe: key not found in dictionary Pin
Richard Northedge22-Jan-09 8:58
Richard Northedge22-Jan-09 8:58 
So, reading between the lines, if you're using the SimpleExample code, that uses the GisTrainer class as the IGisModelReader implementation. If you're using that, then I can see where the issue could be, because the implementation of GetPredicateData in the GisTrainer class has the line:

PatternedPredicate predicate = (PatternedPredicate)mPredicates[predicateLabel];


which would fail if there wasn't a predicate with the predicateLabel passed in. That does count as a minor bug in the GisTrainer code, but the reason it hasn't turned up before now is that you shouldn't be using the GisTrainer for a real implementation - it's really not a good idea to train the model each time your code runs. You need to review the section of my article with the heading "Reading and Writing Models". There I explain how you would train your data and save it to a model on disk, and then load the model from disk when you need to do the evaluation.

Richard
GeneralRe: key not found in dictionary Pin
zink204023-Jan-09 2:35
zink204023-Jan-09 2:35 
QuestionParse Tree Pin
prethum30-Oct-08 9:52
prethum30-Oct-08 9:52 
AnswerRe: Parse Tree Pin
Richard Northedge1-Nov-08 6:19
Richard Northedge1-Nov-08 6:19 
GeneralObserved Expectation Pin
Hasan147921-Sep-08 4:31
Hasan147921-Sep-08 4:31 
GeneralRe: Observed Expectation Pin
Richard Northedge23-Sep-08 10:43
Richard Northedge23-Sep-08 10:43 
GeneralWhere do I get the description of all the token type symbols Pin
Van P. Nguyen21-Mar-08 6:21
Van P. Nguyen21-Mar-08 6:21 
GeneralRe: Where do I get the description of all the token type symbols Pin
Richard Northedge21-Mar-08 10:01
Richard Northedge21-Mar-08 10:01 
GeneralRe: Where do I get the description of all the token type symbols Pin
Van P. Nguyen22-Mar-08 5:55
Van P. Nguyen22-Mar-08 5:55 
GeneralGrouping NNPS Pin
ambatisreedhar5-Feb-08 22:31
ambatisreedhar5-Feb-08 22:31 
GeneralRe: Grouping NNPS Pin
Richard Northedge12-Feb-08 8:28
Richard Northedge12-Feb-08 8:28 
Questionplzzz i need help..help me please Pin
Sabrysoft23-Nov-07 14:36
Sabrysoft23-Nov-07 14:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.