Sunday, March 8, 2009

Measuring NLP is like Marksmanship

There is an interesting correlation between shooting and NLP improvement - both require mathematical analysis in order to be improved upon. In the case of marksmanship the emphasis is the removal of bias. In NLP the emphasis is the harmonic improvement of recall and precision.

Recall in entity extraction is the finding of correct items in a category. In other aspects of NLP it is the correct networking of terms. In marksmanship one could say that recall is putting the bullet into the X ring - though you still score for being close. Hence the emphasis is really not about hitting the target (it is rare to not hit the target) but more the quality of the hit.

Just for fun lets look at some numbers. These numbers came from my shooting at 100 yards without a brace using a carbine. 2 shots were "flyers" as in totally off the paper. Those are in the 2nd quadrant. I list the quadrants as 1st (upper left), 2nd (upper right), 3rd (lower right) and 4th (lower left). The numbers show I am biased up a bit. This is actually not too unexpected as I know that with the trajectory of the bullets I use and the range to the target they are still rising to their apogee. From the numbers I see I am shooting a little to the right as well.

The other number of value is my average score. I got an 8.88 which means my shots were with the same space as a cantaloupe. Ideally I'd like to be hitting something the size of a baseball. That would probably happen if I used a brace.

Marksmen use other measures as well. Grouping is important. In NLP that would be analogous to clustering.

The point I am trying to make is that the marksman uses a lot more numbers to refine his process. Why aren't we doing the same with NLP? My first forays into the world of marksmanship were without knowledge of the math behind the shooting and when I had groups the size of a medium pizza at 100 yards I wanted to improve my skill. All of these numbers help me to diagnose a wide range or problems. I learned I was able to tell where my problems were (breathing, stance, grip, trigger pull, etc.)

We seem to have a lack of these controls in NLP at the moment. I have been an advocate of using f-measure in the development arena early on so that algorithmic changes can be evaluated. I am also an advocate of having a running f-measure as one trains an entity extraction system. However, this is just a first step. I now advocate that we start to develop better controls through stronger math to help the scientist, developer or trainer to better understand their NLP system and make corrections.

This with have further benefits when the system in question is being automatically trained by another software system. Automating the process would require a strong understanding but would have the advantage of removing random bias that humans tend to add to training.

Target Scoring         
March 8th, 2008
1st Quad
0 7 8 9 10 X Total Score Avg. Score
0 0 4 5 2 0 11 97 8.82
2nd Quad
0 7 8 9 10 X
2 1 2 4 0 1 10 79 7.90
3rd Quad
0 7 8 9 10 X
0 0 2 1 4 0 7 65 9.29
4th Quad
0 7 8 9 10 X
0 0 0 1 1 0 2 19 9.50
Totals 2 1 8 11 7 Bias Up 12 260 8.88
Bias Left -4

Wednesday, February 4, 2009

Open Source Text Analytics

Seth Grimes has a new article up worth reading. My friend Bill Day pointed this one out to me this morning. It is a great read for those looking to delve into data mining using open source tools. He is quite honest saying up front that these lack a bit of polish and that of course is to be expected. That said - the price can't be beat!

Give them a look!

Pete

Tuesday, November 18, 2008

Can you use adjectives to infer nouns in entity extraction?

I will limit this case to location extraction since this is a common case and one where I seem to find a lot of confusion. To give away the punch line the definitive answer is no, you can't use adjectives. The full answer though is more subtle than that. Read on, read on.

The use of adjectives for entity extraction looking for locations has many flaws. Semantically, a location can only be a noun. The theory is that in a sentence such as "The ship was beached along the Boston Coastline" that the word Boston is the location. Boston in this context is an adjective. There are two cases where this is provably bad and incorrect and one case where it just simply is misleading.

Case 1: Location Name has Multiple Meanings:

There are location names that are perfectly valid that have additional common meaning. Bad, Iran or Train, Germany or Hit, Iraq or Car, Romania are just 4 examples of hundreds worldwide. If we take the adjective case then when we find "train station" or "bad karma" or "I'd hit that" (ok that's a predicate, you got me - I just wanted to use that phrase!) or "car wash" then we can infer locations. This is clearly absurd. For names like Boston that seem to be unique we find that they have additional meaning. Boston is a transliteral variant of the Uzbek word Baystan. What it means I have no clue.

Case 2: Adjective looks like a location but isn't

There are many of these. Boston cream pie, Boston Bruins, Boston Marathon, New York minute, etc. No discussion really needed here.

Case 3: Adjective is sort of a location but is misleading

Boston Marathon also falls in this example. The Boston Marathon does indeed terminate in Boston. In fact less than 5% of the race is in the city of Boston. The other 95+% runs through many places. Along the way you find another misleading place called Boston College at the top of Heartbreak Hill. The problem there is that Boston College is not in Boston. It is in Chestnut Hill.

Further, these types can be used as locations. Ex. I am going to the Boston Marathon or I am heading to Boston City Hall. They are destination - but they are more specific than just the city.

What is the correct method of dealing with these cases? A good semantic system not only is aware of the parts of speech of individual words, it recognizes important co-locations of words. So instead of seeing:

The: Determiner
Boston: Adjective
Coastline: noun
is: predicate
beautiful: modifier
.: end of sentence

It would see

The: determiner
Boston Coastline: noun
is: predicate
beautiful: modifier
.: end of sentence

In an ideal solution Boston Coastline would then be in your gazetteer with correct coordinate representation. While the software I work on does not handle linear or polygonal targets and could not represent even a bounding box for this type of target today it would not be terribly difficult to implement. It is a simple matter of programming. Entity extraction software that correctly groups terms like "Boston Coastline" are advanced. That is what our software does. That is a significant problem to solve. Once done it is simply a matter of having a properly populated gazetteer and an ability to distinguish in the database between point and area features.

Finally a good semantic solution looks not only look at the words but how they are used in context.

I like to travel to Train, Germany.

vs.

I like to train in Germany.

In the first case we definitely are talking about Train as a noun and location. In the second case it is a predicate and not a location. Imagine further that this is all caps data and it becomes an even more difficult problem.

So avoid the trap of thinking that placename lables are useful without having an understanding of their groupings, parts of speech and context.

Monday, August 18, 2008

Getting rid of Google from news posts

I just noticed that google was very prominent in the news bar at the left. However the articles weren't very relevent to data mining, text analytics, unstructured data analytics or robotics. So I tried to add "-google" to the list. Guess what - no joy. Then I changed the query to the company I work for "digital reasoning systems" and guess what, Google comes up! Then I tried "Kiva Systems" and they come up again. Put in robotics and they go away. Put in an excluder for any term in the headline of one of the returned results and it goes away. Google is cheating on their own system to make it so you can't exlude news about their company even thought it is irrelevent! They also have decided to associate themselves with two unrealated companies. I don't know but it smells dishonest to me. Maybe someone can explain to me why these searches come up with Goodle so prominantly.

Startup Kiva's New (Robotic) Approach to Order Fulfillment - Brightcove

Startup Kiva's New (Robotic) Approach to Order Fulfillment - Brightcove

The Kiva CEO talks about warehouse automation. Its a very interesting interview. I didn't get to meet him when I visited Kiva but perhaps on my next visit. The video nicely shows the drive units at work. While they look small and weak, trust me, they will take your leg in second if you wander onto their pathways! There are safety devices of course but I'm not willing to trust life and limb to them! I love these systems.

One other thing you get to see is the software they use to help the robots get organized. The whole system isn't shown and I don't think you could casually show it in such an interview. I really enjoyed using it and it clearly has evovled nicely.

Thursday, August 14, 2008

Punctual Punctuation

I've been looking at the output of a text processor/pos tagger and noticed that there is a whole class of error I haven't been looking for but should and that is punctuation. It makes a big difference when predicting the start and end of a sentence on the tagging of POS. Especially with words that may be nouns or verbs depending on their context.

Mainly the biggest problem i see is in the handling of the period which for Americans at least appears as the decimal separator for numbers, in abbreviations and at the end of sentences. So it becomes important to discover these three cases accurately. I noticed in some cases that decimal was being concatenated with the prior word (clearly a bug with differentiating abbreviations from words!)

I believe I will treat this kind of error in the same class as lemma error in that the POS prediction is discounted and error is attributed to form. I've been working with this kind of measurement for a long time and I'm surprised I hadn't noticed this class of error before. However it is good to see it now and incorporate it into my methodology.

Monday, August 4, 2008

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.