Emerging Computational Linguistics

In a previous entry, I wrote about the Entailment Challenge. Entailment is a linguistic knowledge concept that concerns two sentences about an event or idea. It is said that sentence A ‘entails’ sentence B when all of the meaning in B is contained in A. Follow this link to see more discussion: Recognizing Entailment.

As part of the Master’s program in Computational Linguistics at the University of Washington, we are preparing for internship appointments in the summer of 2008. As part of that preparation, we were asked to pick a topic that concerns Computational Linguistics and write a short summary of a few papers that covered the topic. This is a PDF of that paper. PreInternship Topic

As part of our NLP statistical processing class in the CLMA program at the University of Washington, we did a comparison of Naive-Bayes learning algorithms. We compared the Bernoulli and Multinomial approaches to this problem and the results are shown in the table below.

This test was run by ‘training’ a classifier on a set of data instances. Each instance has a vector of features. In the Bernoulli case, we treat the features as binary. In the multinomial case, we treat the features as a numeric value from 0 to n where n is the number of instances the given word was found in the instance. Both sets of data have a ‘class’ assigned to them. After we train on the data, we check our system results with the actual class value assigned to each instance. This is where the percent accuracy comes from.

Of course these numbers are from a single test on one set of training and test data, but the fact that the Multinomial results are 91% accurate compared to 88% accurate for the Bernoulli is pretty telling. Also you can see that the elapsed runtime for the test is significantly different as well. The ‘cross_prob_delta’ is a parameter for tweaking the ‘add-one’ smoothing in the training stage.

Bernoull

Cross prob delta	Training Accuracy	Test Accuracy	Wall Clock (seconds)
0.1	0.9303	0.8800	303.23
0.5	0.9103	0.8633	318.10
1.0	0.8970	0.8400	305.45
2.0	0.8796	0.8233	305.56

Multinomial

Cross prob delta	Training Accuracy	Test Accuracy	Wall Clock (seconds)
0.1	0.9570	0.9133	8.33
0.5	0.9503	0.9066	8.50
1.0	0.9448	0.9000	8.29
2.0	0.9400	0.8966	8.26

While we were working on this evaluation, we were brainstorming on other ways to compare the Bernoulli and Multinomial approaches. This is what we came up with.

• Office chair comparison. Put signs on two contestants that are sitting in office chairs. The signs are ‘Bernoulli’ and ‘Multinomial’. The contestants race down the hallway without lifting themselves out of the chair. The first sign to the finish line is the method of choice.
• Date getting comparison. Again, put signs on two contestants. Have them stand back to back in the center of the student lounge and randomly ask girls for dates. The sign that gets the most dates is the method of choice.

All kidding aside, the NLP stats processing class is challenging and fun. We are gaining insight into how these methods can be used for basic classification of data.