Perfection in NLP

Is there perfection in NLP? Let's take, for example, part of speech analysis. For many texts such as the one you are reading, the POS is easily discernible. Occasionally there will be some odd usage that is hard to classify but for the most part it is clear what the part of speech is. There are basically 60 or so parts of speech in English that are worth tracking. University of Pennsylvania's Treebank has around 110 with some being odd combinations of part of speech.

However you run into trouble with text messages and forum postings:

"C U L8r"
"That show was def"
"Another Halo Game? Interesting."

You have further trouble when you look at these musical lyrics (from Weird Al):

"What y'all wanna do?
Wanna be hackers? Code crackers? Slackers
Wastin' time with all the chatroom yakkers?
9 to 5, chillin' at Hewlett Packard?
Workin' at a desk with a dumb little placard?
Yeah, payin' the bills with my mad programming skills
Defraggin' my hard drive for thrills
I got me a hundred gigabytes of RAM
I never feed trolls and I don't read spam"

Those aren't so bad but now try to deconstruct "Welcome to the Terrordome":

"I got so much trouble on my mind
I refuse to lose
Here's your ticket
Hear the drummer get wicked
The crew to you to push the back to black
Attack so I sat and japped
Then slapped the mac
Now Im ready to mike it
(you know I like it) huh
Hear my favoritism roll oh
Never be a brother like to go solo
Lazer, anastasia, maze ya
Ways to blaze your brain and train ya
The way I'm livin, forgiven
What Im givin up"

OK so is it cheap racial demagoguery or social conscience writ large? The fact is that it makes sense to some people who can decode it. However from a machine learning point of view its a mess! And yet here we have written communication. It represents the problem of attaining perfection. I will say that I had as much trouble understanding what Chuck D was saying in the above lyrics as I did reading a macro economics text book. However the more I knew the more both made sense. The start, of course, is knowing where to begin and with just a simple part of speech analysis I think it is asking a lot of machines, heck people even, to get anywhere with text they don't understand. I'm reminded of the Chinese Room Argument.

We all know that these are the challenges. There is no arguing that language captured in text runs a huge spectrum of quality and consistency. The fact is that people who probably would score poorly in POS identification for the most part (guilty as charged here) we still manage to understand what we are reading and have the ability to associate information, spot entities of particular types and generally get by. Sometimes we miss things that are communicated via sarcasm - like that girl I was staring at who said "why don't you just take a picture." I didn't realize she wasn't serious... Sheesh.

Great so lets assume that we accept these problems and decide to identify POS anyway. We would like a measure of how "good" the system is and typically this means taking some text that is "regular" without any weird word plays, lyrics, noise or any other nonsense. I have three text files I use often for this purpose. One is a very dry description of plant maintenance. The other is a post game report on a Red Sox win (oh shut up they were losers all my life, let me enjoy the recent string of wins.) Finally I have a review of the Halo 3 game. I have this one because it is full of weird made up grammar. Gamers and programmers seem to prefer to invent POS for things instead of using "standard English." You know what I mean. "Spreadsheet these numbers for me." If you don't see the made up usage in the previous sentence you need to check out this blog.

I definitely suggest using multiple documents in different voices. Include a lot of things you are interested in - especially if you do entity extraction. If you are interested in people then a sports report is great because multiple people get mention in each post-game report. Find things that interest you and your work and begin there. Keep it short. Creating a reference file is a tedious process and long documents are hard to do because the tedium is a killer. At least for me. Maybe there is a way to make it fun. Maybe I should use Penthouse Forum articles instead.

The next problem is that the words internal to words that are co-located generally aren't their normal part of speech. "Welcome to the Learn to Fly Website!" "Fly" is part of a proper noun so is it a verb? The hell it is. That co-location is a noun. On a token by token basis MAYBE that word is a verb but together with it's neighboring tokens it is part of a noun.

So when do you test for part of speech, before determining co-locations or after? You probably want to do BOTH. However anything prior to determining co-locations is for debugging purposes only. You need to know what is going into your process for determining co-locations. Corrections here are important. For analytical purposes however you will score your POS after the co-locations are figured out.

Here is the rub. Your co-locations might not be correct. Some will be good, some will not. So how do you separate this problem from POS analysis? In my opinion you take the output and put one token or co-location per line along with the part of speech and as you score you check for the word count. If they match then you compare from the output to your idealized reference set. If they don't then you keep reading until the counts match. Each mismatch is a bad co-location. Keep score of good versus bad co locations separately and if its bad don't bother checking the part of speech. Just don't count it. In my opinion this produces the most even and fairest analysis.

Keep track of the types of POS you are using and the number right and wrong for each one. It isn't hard to calculate the f-measure for each part of speech but you need a statistically significant number of examples in order to get a reasonable number. There are a number of problems with F-Measure so its not really clear that it is helpful as a measure here. A pure % right calculation is also of questionable utility. However they will do for a start. I have friends working on a new measure that should help in this analysis.

As for the problematic cases such as lyrics and text captured from forums I suggest giving a hand at trying to determine the collocations and part of speech by hand first. Then try your process for POS prediction and see how it does. You will find a number of issues. How do you score where someone has inadvertently or deliberately used bad diction? In this article the author talks about the "Obama Affect" when I am pretty certain he meant the "Obama Effect." If we discount bad spelling, diction and grammar in text then how can we measure how accurate we are in modes of communication totally defined by this such as SMS messages? I think we can't do this kind of discounting. We have to pick, if not a POS, at least a role that the token is performing. Even a smiley face has a role, be it decorative or meaningful at a meta level.

Do Illiterate People get the Full Effect of Alphabet Soup?

The title comes from a George Carlin joke and in reverence I've used it as a very appropriate title for today's entry.

From the people I spoke with at Text Analytics Summit 2008 it seems that every one gets recall and precsions, some get f-measure and few if any get any other measurement for analyzing the quality of analytics from products. This seems weird to me. First off the f-measure is pretty easy to get. What I find more difficult are defining recall and preceision. In fact it is questions of how to measure those that generally screw people up the most.

Recall: To simplify this consider that a document is full of entities. You have a conceptual set of relevent entities. It is important to make sure that when you go through the document you only find the ones that are actually relevent. For example if you were looking for Populated Place names (PPLs) then you would want to throw out anything that is a personification or adjective. "I'm going to Washington" would be good but "Washington was urged to sign the Kyoto Agreement" would not be. In the second case the entity Washington is the administation of the United States government. So assuming you have identified all of these then the next task is to sum them up. The sum of every hit that you get as a result that matches (with perfect registration) is compared against the total relevent entities and that is your recall. So if there are 10 PPLs and you get 6 of them then your recall is 0.6.

Precision: This is really simple. Take the number of relevent hits you have an divide by all the hits you have. So if you have 6 relevent hits but your total hits are 12 then your precision is 0.5.

Registration: This is where people cheat and fudge numbers. You have to show the instance of the term that was hit to know if you got it right. In the Washington example above if both of those sentences were in the target document then you'd want to know WHICH Washington was picked up. What cheaters will do is note how many Washingtons are relevent and then count the number of hits without checking registration so if there is a false positive it will look like a true positive. Another cheat I've seen is to take any hits on Washington and flatten them - ignoring the counts and just counting that as a true positive. These are real life examples and show you can't just trust the vendor.

So don't let someone scam you with their recall and precision numbers. Ask how they were derived. Don't just accept them as given. Once you have recall and precision then there are two ways you can calculate the f-measure:

1) Unweighted

2RP
---
R+P

2) Weighted
2RPb
----
R+Pb

With the weighted version you put in a value for b between 0.5 and 1.5 and it shifts from prefering recall to prefering precision. It depends on the individual needs on the analysis you are doing.

The point of this post is that you need to know what goes into making an accurate calculation of f-measure. The fact is that if you have someone doing it for you they have to really understand recall and precision. If you take shortcuts you reduce the benefit of the analysis to the point where you start promoting systems that just don't work. If you rely upon the vendor they are likely to sell you a pack of lies. The best approach is to be knowlege able about how to do the measurement and do it yourself or find someone who is skilled at doing it. In the end the security and comfort you get from validating the f-measure will keep you from losing sleep.

Correctness and Utility

A theme I've been working on the past few months is about the interplay of correctness and utility. At times there is a tradeoff between the two concepts and I think they deserve discussion. Generally speaking in computer science terms, corretness applies to the amount an algorithm of implemented software compares to a specification. Given a specification for addition, an algorithm that takes 2 and 2 and produces a value of 4 is deemed "correct." What a lot of people have tried in the past with machine learning is to impose a correct model of language on a system and then shoe horned the data into that model. While the results work reasonably well for white papers, they don't for the 99.9% of all other inputs.

The reason for this is because language itself is not correct. In almost all documents, this one included, you will find spelling mistakes, bad diction, bad grammer, neologisms, double negatives, sarcasm, run-on sentences and so many other ills. T33n SMS Sp3@k... You name it, we manage to communicate in spite of the rules of standard language. In fact at times we invent grammer, words and turn things on their ear to communicate more specifically and with more impact than if we had just made statements in standard correct English. Take a look at advertising, literature or even the script they handed Frank Oz when he took on the part of Yoda.

So even if I spell something wrong or perhaps use awkward phrasing can you still make utility out of what I write? Can you still find the essencial meaning of my text? We all know this is essencial for data mining, text analytics and machine learning. We have to overcome human weakness in the way that humans do. We have to be flexible. We have to value utility over correctness because what we have to work with is, itself, not correct.

This leads to another thought which I won't expand upon much here but requires it's own series of articles. When you score a system for its quality of analytics it would be a huge mistake to spare it from having made a mistake due to the text itself being incorrect. The reason why is we need to accept the fact that text will always have mistakes in it. While it is understandable why your system did not get 100% it would be important to rate a system that did get the right relationship more highly.

I'll be writing more of my concepts on quality of analytics as time goes on.