Henry 10: Shakespeare's history plays have a new marketing department

Shakespeare's (English) history plays are too confusing for today's audiences. The problem, according to the new marketing director, is largely a matter of inconsistent branding. From a branding perspective, this list has a number of obvious problems:

• King John
• Edward III
• Richard II
• Henry IV, Part 1
• Henry IV, Part 2
• Henry V
• Henry VI, Part 1
• Henry VI, Part 2
• Henry VI, Part 3
• Richard III
• Henry VIII

For a start, is the product called "Henry" or not? Far too many different names. And they're all kings, right, so why is only John called out as such? Also, some of these guys sound like sequels or minor revisions, not full fledged new kings, which is going to affect sales. Let's get this sorted out by regularizing the names and choosing a natural and consistent numbering scheme. 

• Henry I
• Henry 2
• Henry 3.0
• Henry 3.1
• Henry 95
• Henry NT 4.0
• Henry 98
• Henry 2000
• Henry XP
• Henry 7
• Henry Fundamentals for Legacy PCs
• Henry Vista
• Henry 8
• Henry 10

Error Analysis of the Week: Ratnaparkhi on POS tagging

This is the first of a planned series of posts showcasing good error analysis for NLP. This is motivated by a conversation with Lori Levin about "linguists who improve your score".  It is intended as a positive response to the common lament that linguistics is getting squeezed out of modern NLP. I think that error analysis is an undervalued skill, and that this is an area where trained linguists can make an especially useful contribution. 

The plan is that the series will cover several different areas of computational linguistics, and perhaps also be useful to NLP researchers seeking to deepen their understanding of how language works. The coverage is necessarily going to be sparse. For a more thorough introduction to linguistic concepts, aimed at an NLP audience, I recommend Emily Bender's Linguistic Fundamentals for Natural Language Processing. For a general audience introduction to the ways computers can do things to language, I self-servingly recommend Dickinson, Brew and Meurers' Language and Computers.

We start with part-of-speech tagging, which might seem to be an easy case (it isn't!). Modern statistical NLP relies on linguistically annotated corpora, which are used to train and test machine learning models. The shallowest layer of linguistic annotation assigns parts of speech, such as noun and verb, to each word of each sentence. You probably learned something about parts of speech at school, but as with many things, the devil is in the detail. For some languages it is unclear that even the distinction between nouns and verbs makes sense. So it should be no surprise that when the annotators working to build the famous Penn Treebank decided to assign parts of speech, they ran into not only detailed technical issues but also genuine scientific concerns. 

The treebank annotators were by no means the first to label corpora with parts of speech. They chose to use a smaller set of part-of-speech tags than had been used in previous projects, including 36 POS tags and 12 other tags (for punctuation, currency symbols and the like).  Previous projects had used much richer tag sets. The reasons for the Penn Treebank design are outlined in a journal article by Santorini et al. The process that the treebank annotators used to produce the final corpus was an initial automated annotation using a computer program, followed by careful correction by human analysts.  As we will see, this gave rise to interesting patterns of error.

The analysis that we will focus on is part of a paper by Adwait Ratnaparkhi, who was a student at Penn, and had the benefit of insider access to the treebank annotators. The primary concern of the paper is a so-called maximum entropy model, which is shown to produce what was then state-of-the-art performance. The claim of the paper is that the maximum entropy framework succeeds because of its flexibility and ability to design and use linguistically informed features. Since the paper was written in 1996, and statistical NLP has progressed since then,  it should surprise no-one that its raw performance is lower than that achieved by the latest systems. However,  the paper does include an exemplary error analysis: one that could usefully be emulated in present day papers.

Error analysis

The point of error analysis is to understand the behaviour of the system with which one is working. Sometimes this leads directly to improvements in the system, but sometimes it instead identifies errors that are likely to be hard or impossible to fix. In either case the analysis is useful, because it helps to direct effort toward changes that might be useful and away from ones that will not be.

By the numbers, part of speech taggers are pretty good. Ratnaparkhi's, system got nearly 97% of the tags right. It does much better on words that it has seen in the training set than on words it has never seen before.

	Correct	Fraction	Mistakes
sentence	3,804/8,000	0.476	4,196
token	185942/192,826	0.963	6,884
known	180,676/186719	0.968	6,043
unknown	5,266/6,107	0.862	841

The counts for Ratnaparkhi's system are reconstructed from what is in the paper, which only gives percentages.

There's also a more detailed error analysis, indicating which words caused problems.

Word	Correct	Prediction	Frequency
about	RB	IN	393
that	DT	IN	389
more	RBR	JJR	221
up	IN	RB	187
that	WDT	IN	184
as	RB	IN	176
up	IN	RP	176
more	JJR	RBR	175
that	IN	WDT	159
about	IN	RB	144
that	IN	DT	127
out	RP	IN	126
that	IN	WDT	123
much	JJ	RB	118
yen	NN	NNS	117
chief	NN	JJ	116
up	RP	RB	114
ago	IN	RB	112
much	RB	JJ	111
out	IN	RP	109

These numbers matter because of their general trend. If we could fix the top two categories without breaking anything else, we would have removed more than 10% of the system's errors. They also matter because of the linguistic patterns. RB(R) (adverb) JJ(R) (adjective) and IN (preposition) parts-of-speech  seem to be tricky. But why, and what can be done about it?

Rich Features

A potential advantage of Ratnaparkhi's technique is that he has more options in choosing features than are available in (say) the Hidden Markov Model taggers that were current at the time he was writing. So, what is a feature then? Basically, anything that is measurable on the history up to the point where a decision needs to be made. In Ratnaparkhi's case, the history consists of the word for which the decision is needed, the previous two part of speech tags, the two previous words, and the two following words. A feature is a predicate that relates a particular choice of tag (\(t_i\)) to properties of the history. We call them rich features, because they can refer to any measurable property of the history.

The history is \( h_i = \{ w_i, w_{i+1},w_{i+2},w_{i-1},w_{i-2}, t_{i-1},t_{i-2}\}\) and predicates are defined over \((h_i, t_i)\). There are lots of potentially active features, because the words and tags can be filled in in many different ways, so the standard way of defining which features are used is to create templates, then automate the process of generating actual features from the templates. The standard templates used by Ratnaparkhi were the following:

Condition	Feature
\(w_i\) is not rare	\(w_i = X  \; \& \;  t_i = T\)
\(w_i\) is rare	Prefixes: \(w_i[:n] = X  \; \& \;  t_i = T\) where \(n \in 1..4\) Suffixes: \(w_i[-n:] = X  \; \& \;  t_i = T\) where \(n \in 1..4\) Number: \(w_i\) contains number \( \& \;  t_i = T\) Uppercase: \(w_i\) contains uppercase letter  \( \& \;  t_i = T\) Hyphen: \(w_i\) contains hyphen  \( \& \;  t_i = T\)
\( \forall w_i \)	\(t_{i-1} = X \;  \& \;  t_i = T\) \(t_{i-1} = X\;   \&\;  t_{i-2} = Y\;   \& \;  t_i = T\) \(w_{i-2} = X \;  \& \;  t_i = T\) \(w_{i-1} = X \;  \& \;  t_i = T\) \(w_{i+1} = X \;  \& \;  t_i = T\) \(w_{i+2} = X \;  \& \;  t_i = T\)

These templates, taken together, can be filled in for each of the positions in the training corpus. They are sufficient to get the performance reported in the paper. But it is plausible that there might be other, more specialised features that will improve performance on particular words or in particular situations.

Ratnaparkhi's hypothesis was that specialised features would help. The first step in testing this hypothesis was to make precise the notion of "specialised feature", which required examination of the errors that the system was making, and decisions about what kinds of specialised feature to try. For this, the breakdown by words was useful.

The specialised features were similar to the original ones, but they mention specific words. They are not derived from templates, but selected on the basis of the word-by-word error analysis. For example:

\(w_i = "about"  \; \& \;  t_i = "IN" \& t_{i-2} = "DT" \& t_{i-1} = "NNS" \)

Features like this were made for 50 "difficult" words, and the experiment re-run. Unfortunately, this did not improve performance. At this point, Ratnaparkhi did something truly exemplary: realizing that the "correct" answers in the gold standard might not actually be correct, he went back and looked at the identities of the annotators, and discovered that, for example, the ratio of about/IN to about/RB changes when the annotator changes.  This should not have happened, because the tagging guidelines are supposed to be written in such a way as to ensure that annotators are interchangeable. But of course they are not, and what we have is prima facie evidence that in the case of words like "about", the gold standard is almost certainly inconsistent. If different choices had been made about which annotator did what, the corpus would be different.

System 1.5: the dialog system thats expects the expected unexpected, but does the conventional thing.

A while ago, Jon Oberlander wrote a squib for Computational Linguistics called "Do the Right Thing ... but Expect the Unexpected", in which he argued that when people speak, they often succeed in choosing what to say in accordance with the maxim to do the right thing, which in this case means to produce the utterance that the listener will find easiest to interpret and make sense. But they also sometimes fail, and the article points out that reasonable generation algorithms may well also do the wrong (i.e. unexpected) thing, and that this is no surprise.

In the intervening years, things have happened, some of them expected, some of them unexpected. Among them was the invention, by Donald Rumsfeld, of a useful meme for dichotomization. He split the unknowns of a situation  into the "known unknowns" and the "unknown unknowns".  This also works for the "unexpected": we have the "expected unexpected" and the "unexpected unexpected".  Both of these turn up in information seeking natural language dialog systems. The expected exchanges of such a dialog systems are things like a question-answer pair. The "expected unexpected" are the points at which knowledge gaps and other misfires result in the need for dialog moves, such as the initiators for clarification sub-dialogs, that are there in order to fix difficulties and get the system and its interlocutor out of the ditch next to the royal road of goal-directed dialog and onto the smooth well-maintained tarmac. The "unexpected unexpected" is when something happens that leads the system to believe that its interlocutor is off in the next field climbing a tree, talking to a cow or even climbing a cow and talking to a tree. The system has no conventional moves for getting things back on track.

At this point the system may fall into the temptation that it ought to engage in sophisticated reasoning in order to work out what the appropriate repair is, by, for example, recruiting extra knowledge from somewhere until it can work out that its interlocutor is after all doing something rational. This is going to take work, which is scary. What is even more scary, this work is like the effortful, rational, slow work that Daniel Kahneman calls "System 2". Kahneman points out that System 2 thought comes less naturally than System 1 thought, which is more automatic. I think that modern dialog systems, especially the ones that work by reinforcement learning, are basically operating in a way that mirrors system 1, choosing dialog moves that, from experience, tend to work out well in moving the interaction along. They actually do a bit more than this, because they can often tell when the dialog is in a ditch, and get it out. Their remedies (such as clarification requests) are conventional, stereotyped and maybe under-informed, but they are a bit flexible, and they usually work in handling the expected unexpected. Maybe they are something like "System 1.5", with a bit of flexibility, but not enough to handle the cases where the dialog seems to be off in the next field.  I doubt that there is any hope of learning System 2 thought by reinforcement learning over dialog traces.

That's OK, because there are two quite distinct reasons why the system might think the dialog is off in the next field. Either the situation will become sensible when the system manages to find the chain of reasoning that will allow it to understand that the interlocutor is acting reasonable, or, perhaps just as likely, the interlocutor really is up a cow, talking to tree, and no amount of inference will get the
dialog back where it needs to be. This interlocutor is beyond the pale, and the best that they can expect is kindness (which co-incidentally, Don Rumsfeld ... hmm,  let's leave that thought unfinished).

So, if I ever get to design  a dialog system, it will be called System 1.5, and it will adopt the Rumsfeldian philosophy of expecting the expected unexpected, then doing the conventional thing.

Dennis Mehay

Has submitted his Ph.D dissertation and graduated. Well done!

One for negation experts

Northern Ireland expert Denis Murray, on BBC, talking with an interviewer about the Queen’s historic meeting with Martin McGuinness.

Interviewer: Would you say that until recently something like this would have been unthinkable?

Murray: I’d say more than that, until two years ago it was not even thinkable.

It’s pretty clear that Murray felt he was adding information. But why does “not even thinkable” mean more than “unthinkable”.

I believe he took the interviewer’s “unthinkable” to mean “you can (indeed must) think it, but you really should not do it”, and augmented by using “thinkable” to imply that “nobody would even have thought of it, or have needed to judge that it was a bad idea”

Samasource

Samasource:

'via Blog this'

In his IJCNLP keynote address, among many other things,
Matt Lease mentioned a crowdsourcing service that is more focused on ethics than many
others. If I do crowdsourcing, I would like to consider using this.

Please call me, Ishmael
In my quest for the white wael
I lost your voicemael

How to master and command the eRiots.

The Dear knows that the Napoleonic era has much to teach us, especially on penal policy. In responding to the British consumer-oriented flash mob eRiots and eRobberies [1] we should  follow the policies that Jack Aubrey, MP, would suggest.

Captain Aubrey highly values social order, but tempers his opinions with as much compassion as his situation allows.

He would be reserved in his use of eFlogging, and that only in cases of drunkenness (by naval standards), sodomy and damaging the paintwork. He would certainly withdraw grog from repeat offenders, and would perhaps allow the use of an ePillory and/or eStocks. Mutineers and murderers could expect no mercy, but thieves would not be hanged. Instead they would either be ePressed into the eNavy or subjected to eTransportation to eBotany eBay.

Dr. Maturin was unavailable for comment, having been distracted by a piece of nondescript wildlife.

[1] US and EU Patents Applied for: Communication apparatus and coordination method for transgressive social communication among the yoof

New Job

I just moved to the Educational Testing Service, to work on their cRater project, which is like the famous eRater essay-grading project, except with more semantics, and for short answers instead of essays. I THINK the c stands for content, but it could stand for "constructed response", which is a psychometrics and educational testing thing. Learning fast, having fun, working with a great group of people. Note that the cRater link describes cRater as it was in 2004, not as it is now.

"You can observe a lot by just watching" Yogi Berra

While it isn't always easy, I can usually tell where people were raised as well as where they were born. Koreans raised in Los Angeles have a style completely different from those born in Seoul; the English, en masse, look different from the Scots, and it just takes one look at those wacky triangular eyeglasses for me to know that a young lady is either French or getting that way. In the same way, just by looking, I can pretty much diagnose the families waiting for the Newark to Gatwick flight. Here's one, prematurely greying father with John Lennon glasses, slightly older  mother with shoulder length hair, three blond boys with backpacks and crew cuts. I'm like, O.K. , he's British, she's American, all three boys born in the USA. Or, Asian looking father, fiftyish, no mother in the party, two young teen daughters, one classically Eurasian looking, the other blonder. Sure, I can do that: he's born in Hong Kong, but doesn't speak Cantonese well, one kid born in Shanghai, the other in canoe transit up the Amazon. Same father, I think, but the first girl's mother is definitely working as a dogcatcher in Evansville, Indiana, and the second one's mother once had that unfortunate accident with a hairnet and an avocado. Could these be the same person? Very likely, but I'm not infallible, while I know for sure that the father is part-time seal tamer and computer science professor, I can't be be sure whether he's a bigamist. It's just a matter of assessing the evidence.

I can also tell what language people speak, because the patterns of vowels and consonants shape the face. Turkish oral surgeons spend 47% of their time unsticking the tongue tip from the roof of the mouth. "Who put the gluten in this agglutinative language?", they cry. And did you know that Mick Jagger was raised Basque? His English accent is a fake: he stole it from a classmate at LSE, using 1960s recording technology and a hypnopaedic pillow. You don't get those lips from an Indo-European language, let me tell ya! Angela Lansbury is Swedish, and Dick van Dyke really is a cockney. As a young man Rex Harrison sang Wagner's Parsifal with Maria Callas in the Italian premiere at La Scala: the My Fair Lady thing is a front. Not many know that, but you can see all this in their faces.

Just by looking, I can tell whether your dog will develop cataracts (and whether your cat will develop doggeracts, should you care). Show me your friend's wardrobe, and I can predict the mean rainfall over the Andes for the next two weeks. Two glances inside your purse and I can diagnose your psychological problems to eight decimal places AND predict your fashion preferences. Just from your diet, I can tell you not only your height, weight and hat size but your views on a wide range of social issues and the three last digits of your social security number. If you were raised by wolves, I can tell. If you were kept locked in a cupboard by your neglectful parents, I will spot it, and be able to offer career advice, speech therapy and a range of inexpensive  after-care options. If your father married his half sister and you were raised by a vengeful dwarf in the forest, I will know, and be the first to offer you a place to lay your sword. And advise you on whether the local fire brigade is any use for your unknowingly genetically suspect purpose. But I'm not special, I think most people could do that, just by looking.

Tag clouds

How to do comparisons between machine learning schemes

Nice paper comparing 16 model selection and weighting schemes. Includes 58 benchmark datasets. The data analysis was done in the following way - for each dataset, rank the schemes. Then average the ranks. - use the Friedman test to test whether ranks are all equal ( - if ranks are not all equal, use the Nemenyi test (covered in papers by Demsar, Garcia et al  http://jmlr.csail.mit.edu/papers/volume9/garcia08a/ Ying Yang, Geoffrey I. Webb, Jesús Cerquides, Kevin B. Korb, Janice R. Boughton, Kai Ming Ting: To Select or To Weigh: A Comparative Study of Linear Combination Schemes for SuperParent-One-Dependence Estimators. IEEE Trans. Knowl. Data Eng. 19(12): 1652-1665 (2007), ISSN: 1041-4347 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.8561

What probability is about

Just as formal logic is a tool for capturing intuitions about effective ways of reasoning probability is a tool for capturing effective ways of reasoning about uncertainty.  In logic, we are taught to proceed from premises to conclusions. We conclude  that "If every CSE graduate takes the exit exam  before graduating and Emily is a CSE graduate, then Emily must have taken the exam" because this matches the Modus ponens pattern .  The good thing about this is that if we trust Modus ponens and we believe that we have correctly mapped the English description of the conclusion onto the terms of the formula, we know that the argument is valid. Notice that this claim of validity is not affected by the truth or falsity of the premises. Even if Emily never was a CSE student, or even if some CSE students are in fact able to weasel out of taking the exit exam, the argument is still OK. Not, however, especially useful as a way of working out stuff about Emily: if we aren't sure about the assumptions, we can't be sure about the conclusion either. Aristotle hit on the idea of laying out a taxonomy of plausible ways of reasoning, then thinking, in the abstract, about which of these patterns of reasoning actually deliver valid arguments. This is a wonderful idea, because you can rely on the insights about the patterns of reasoning without having to be concerned about the truth or falsity of particular facts.

In the same way that logic is the study of patterns of true/false reasoning, probability is the study of patterns of reasoning in the face of uncertainty.

Why statisticians shouldn't write movie titles

Never Give a Sucker an Asymptotically Even Flip
The Variational Enigma
The Fisher King
Independence Day
Return to Monte Casino
The Man Who Measured the Bank at Monte Carlo
Between 99 and 103 Dalmatians
8.5 +/- 0.2
The Metropolis Method (void where prohibited by law)
Improper Priors go wild on Cancun

War reporting

Yesterday Wikileaks   posted a shocking video taken from an Apache helicopter in Iraq. It

Julian Assange, who founded Wikileaks, was interviewed about this. . He feels that the soldiers in the helicopter obviously committed a war crime, and that

Plain speaker's guide to "any more" and "anymore:

First here's a rephrasing of what Huddleston and Pullum's epic Cambridge Grammar of English says about "any more" and similar adverbs. The main discussion is on p 710 and following, with other bits on 823 and 831

1. They are polarity sensitive: this means that there is a difference in acceptability between "She isn't here any more" and "She is here any more". For many speakers, the first is OK, the second not.


2. The difference between "any more" and "anymore" is a British/American spelling difference.


3. You can line up "anymore" with "still" and "no longer". They differ in how they work with negation.

My own impressions follow. Most speakers can say :

"She is still here" (i.e. she is here and has been for a while)
"She is still not here" (i.e. we are waiting, and she still hasn't arrived),
"She is not here anymore" ,"She is no longer here" (in both cases, she was here, but now isn't)

Many speakers find: "She is not still here","She is here anymore" awkward. For the first one the intended meaning is the same as the one expressed by "She is no longer here". Some speakers, including me, blow a fuse when confronted with the second one, and don't even understand what it means. For others, "anymore" can be used anywhere that "nowadays" is, with much the same meaning, so "She is here anymore" could be used (if you are, say, in a bar) when the person in question used to avoid the bar but now hangs out there on a regular basis. Similarly "Ice cream is cheap anymore" works for many people, but in my natural dialects, I  would have to either turn it round and say "Ice cream isn't expensive anymore" or punt and say "Ice cream is cheap nowadays".

Unfortunately, linguists have taken to confusing themselves and others by talking about "positive anymore".  If they had called it "nowadays anymore" there would have  been no trouble. These adverbs are neither positive nor negative, just a little fussy about what kind of sentences they like to be wrapped up in. The "nowadays" translation helped me, and is from John Lawler. As he says

Apparently, for users of positive "anymore", "nowadays" doesn't
cut it anymore. Anymore, they use "anymore" instead. Or perhaps
only in certain speech contexts; the definitive sociolinguistic
study remains to be done.

I guess I can forgive him for using the term "positive", because he puts it in quotes and gives an amusing example.

By the way, in Columbus, Ohio. ice cream really is cheap and good at Graeter's and  Jeni's . No ice creams were consumed in the creation of this post, but several area shops are on high alert.

Facebook's de facto terms of use

If you are thinking of collecting and distributing data from social media sites, you should read
Pete Warden's account of how Facebook responded to his activities.. Facebook appears to be keen to exert more control than one would think they are entitled to, and certainly more than is convenient for academics. Nobody knows how this would play out in court… Twitter is looking better than ever as a data source.

Genuinely funny April Fool article

This one actually made me laugh:


A would-be saboteur arrested today at the Large Hadron Collider in Switzerland made the bizarre claim that he was from the future. Eloi Cole, a strangely dressed young man, said that he had travelled back in time to prevent the LHC from destroying the world.

The LHC successfully collided particles at record force earlier this week, a milestone Mr Cole was attempting to disrupt by stopping supplies of Mountain Dew to the experiment's vending machines.


http://crave.cnet.co.uk/gadgets/0,39029552,49305387,00.htm?s_cid=33

Environmentally concerned spouse

"It felt so good to throw away that Martha Stewart dishwasher liquid"

Context: in our machine, Martha Stewart's green dishwasher liquid may be green, but isn't effective for washing.

SPLPAC

The Society for the Promotion of Long Prepositions,Adverbs and Conjunctions wishes, henceforward, to exist, notwithstanding its lack of positive ontological status heretofore. Moreover. it regrets and plans to remedy its previous delinquencies in this area, but nevertheless accepts that its existence may not continue for long. Contrariwise, it sees itself as a lexical mayfly skittering over the surface of the language, and is OK with that. Anyone know where the nectar is?