Why NLP is hard and how progress is made

Take four ordinary words, I made her duck, and look for every meaning they can carry. The lecture asks for at least five and leaves the answers to you. Before reading on, try it honestly: how many can you find? Most people stop at two and are surprised that the sentence keeps going.

The five meanings are not the lesson. The lesson is where each one comes from. Jurafsky and Martin use this sentence because every reading is produced by one decision at one linguistic level, and those levels are exactly the ones you met in part 3. That is what makes ambiguity the central problem of the field rather than a party trick.

Work through what flips. The word duck can be a noun (the bird) or a verb (to lower your head), and her can be a dative pronoun (for her) or a possessive (her duck). Both are lexical ambiguities of part of speech. The word make keeps its part of speech but not its meaning: it can mean create or cook, which is a lexical ambiguity of sense, and choosing the right one is Word sense disambiguation. The cause and transform readings are not two further senses of make. They come from the frame the verb takes: the sentence as a whole can be built in three shapes, make with a single object (her duck as one noun phrase), make with two objects (her and duck, one turned into the other), or make with an object and a bare verb (her then duck as an action). That is syntactic ambiguity, a question of syntax rather than of any single word.

One level is still missing, and it only appears when the sentence is spoken. In speech the first word could have been eye and the second could have been maid. Jurafsky and Martin call this an even deeper kind of ambiguity, because it sits below the words themselves, at the level of phonetics. A speech recogniser must settle it before any of the other decisions can even begin. Toggle the cycler to "heard, not read" to see it.

This table is the sentence Jurafsky and Martin build their whole book on: most or all tasks in speech and language processing can be viewed as resolving ambiguity at one of these levels. Part-of-speech tagging decides whether duck is a noun or a verb, word sense disambiguation decides what make means, and probabilistic parsing decides whether her and duck group together. Every one of those tasks has its own chapter later in the course, and each one is answering a question this four-word sentence raises.

If the duck sentence felt contrived, here is one nobody would blink at: I saw the man with a telescope. Who has the telescope? Read it once and you will have decided without noticing. Read it again and the other answer is just as available.

The phrase with a telescope is a prepositional phrase, and a prepositional phrase has to attach to something. Attach it inside the noun phrase, [the man [with a telescope]], and the man has the telescope. Attach it to the verb phrase, [saw [the man] [with a telescope]], and the telescope is the instrument of seeing: I used it. This is prepositional phrase attachment, one of the two common kinds of syntactic ambiguity in English text (the other is coordination ambiguity, as in old men and women), and the point is that both parses are fully grammatical. The grammar licenses both; only context, plausibility or statistics can choose. A third reading hides in the first word: saw can also be the present tense of the verb to saw, so I am cutting the man with a telescope, a lexical ambiguity stacked on top of the syntactic one.

Jurafsky and Martin treat this under structural ambiguity in their parsing chapter: it occurs when the grammar can assign more than one parse to a sentence, and attachment ambiguity is one of the two common forms, the other being coordination ambiguity. Their own example is Groucho Marx's I shot an elephant in my pajamas, where in my pajamas can attach to the shooting or to the elephant. They call ambiguity the most serious problem faced by syntactic parsers, because a grammar big enough to cover real English assigns a naturally occurring sentence not two parses but many, most of them grammatical yet semantically unreasonable. Parsing is therefore never just recognising structure; it is choosing among structures.

Crash blossoms: ambiguity in the wild

Ambiguity is not a classroom invention, and the six headlines stamped "100% REAL" in the lecture prove it: every one really ran in a news outlet. Headlines drop articles, auxiliaries and the copula to save space, which strips away exactly the cues a reader uses to settle part of speech and attachment. The result is a headline that admits an unintended reading, and copy editors have a name for it: a Crash blossom.

The name comes from the first line on the slide. In August 2009 the site Japan Today ran the headline Violinist Linked to JAL Crash Blossoms about Diana Yukawa, whose father died in the 1985 Japan Airlines crash and whose career was flourishing. Editors on the Testy Copy Editors forum read it as a species called crash blossoms and, in the thread that followed, proposed "crash blossom" as the general term for a headline that leads the reader down the garden path. Ben Zimmer picked the story up on Language Log that month and then in his New York Times On Language column in January 2010, which is what made the word stick.

Look at the last column and you will see the same three kinds of ambiguity as the duck sentence, just without the helpful function words. Strikes, blossoms and shooting are part-of-speech flips; holds up, try and cut in half are sense flips; 7 foot doctors is a bracketing flip. Notice also that one choice forces others: once strikes is a verb, idle must be an adjective, and once it is a noun, idle must be a verb. Ambiguities are not independent, which is why parsers resolve them jointly rather than word by word.

Suppose ambiguity were solved. Would language understanding be easy? No, and there are six more reasons, each a different way real text refuses to behave like the tidy sentences of a grammar book. Take them one at a time, and for each one ask which NLP subproblem it defeats, because that subproblem is a research area with its own benchmarks.

Non-standard text

Guys plz d/l the lettr Ive written 2 Jeff Gaspin is perfectly readable to a human and almost useless to a model trained on edited prose. Five of its tokens are misspelt, abbreviated or numerals standing in for words. This is non-standard language, and it defeats normalisation: the step that is supposed to map surface forms to the vocabulary the model knows. For a KFUPM student the sharper version is diglossia. Farghaly and Shaalan describe Arabic as a language where Modern Standard Arabic is the formal written variety while everyday speech is Gulf, Egyptian or Levantine dialect. Text messages and social media carry that dialect into writing, and Darwish describes how it often arrives as Arabizi (Latin letters and digits standing in for Arabic sounds, as in 3ala for على), so a system trained on newswire MSA meets a different language on the phone.

Segmentation

The slide shows the New York-New Haven Railroad tokenized two ways. The naive split, on spaces alone, gives the | New | York-New | Haven | Railroad, gluing York to the wrong New. The right split, the | New York | - | New Haven | Railroad, needs to know that New York and New Haven are each one name. This is a Segmentation problem and it defeats Tokenization and named entity recognition together. Jurafsky and Martin note in their tokenization chapter that keeping a multiword expression such as New York as one token requires a multiword expression dictionary, so tokenization is tied to recognising names and to morphology. Arabic makes segmentation unavoidable rather than occasional: the preposition b (by, with) and the conjunction w (and) are clitics written attached to the following word, so وبالقلم is one orthographic word that a tokenizer must cut into w + b + al + qalam, four units, before anything else can run.

Idioms

Dark horse, get cold feet, lose face, throw in the towel. An Idiom is a multiword expression whose meaning is not built from its parts: no towel is thrown, no feet get cold. This defeats compositional semantics, the assumption that the meaning of a phrase is assembled from the meanings of its words, and it wrecks machine translation that translates word by word. Arabic has its own stock: على عيني is literally "on my eye" and means "gladly, of course".

Neologisms

Unfriend, Retweet, Malware, Webinar. Each of these entered everyday use, or in the case of unfriend returned to it with a new sense, only when a product or a threat made it necessary. A Neologism defeats any system with a closed vocabulary, which treats it as an out-of-vocabulary token and learns nothing. Vocabulary is open: new words arrive faster than lexicons can be updated. This is the motivation for the subword tokenization of lecture 2, where byte-pair encoding lets a model build unfriend from smaller, frequent pieces (ideally un plus friend) without ever having seen the whole word. Arabic coins verbs from loanwords the same way: speakers say سيّف, "to save" a file, forcing an English root into an Arabic verb pattern.

World knowledge

Mary and Sue are sisters. Mary and Sue are mothers. Same shape, same syntax, same plural predicate. Yet the first means sisters of each other and the second cannot mean mothers of each other. Nothing in the sentence tells you that; you know it because you know how sisterhood and motherhood work. This is world knowledge, and the subproblem it defeats is commonsense reasoning. It is the same in every language, which is why there is no Arabic column to add.

Tricky entity names

Where is A Bug's Life playing, Let It Be was recorded, a mutation on the for gene. A Named entity is supposed to be a proper name, but these names are made of ordinary words: an article, a pronoun, a preposition. Named entity recognition has to decide that for is a gene and Let It Be is a record without any lexical clue. In English the capital letters help a little. Arabic has no capital letters at all, so every person, place and organisation name looks like a common word. Farghaly and Shaalan list the missing capital letters among the central challenges for Arabic named entity recognition.

The lecture closes the list with "But that's what makes it fun!" and for a PhD student that line is literal. Each card is a research community: text normalisation, tokenization and segmentation, multiword expressions, open-vocabulary modelling, commonsense reasoning and named entity recognition all have their own shared tasks and leaderboards, and Arabic versions of most of them are still open.

Go back to Mary and Sue are mothers and ask what a system would need to read it correctly. It needs the syntax of a plural predicate, which is knowledge of language. It needs to know that motherhood is not reciprocal between two women, which is knowledge about the world. And it needs some procedure that brings the two together on this sentence, a way to combine knowledge sources. Those are exactly the three tools the lecture says progress requires.

The third tool is the interesting one, because it is where the four approaches of slide 15 come from. Each approach is one answer to how knowledge sources get combined. Rule-based NLP encodes linguistic knowledge by hand and combines it by the order in which rules fire. Machine learning based NLP learns the linguistic knowledge from annotated data and lets a classifier weigh it. End-to-end deep learning learns everything, including whatever world knowledge the text happens to contain, from raw input inside one network. A hybrid approach mixes them, typically rules where knowledge is crisp and models where it is statistical.

The second half of slide 24 says where the models, algorithms and theories come from: computer science, mathematics and linguistics. Slide 5 drew NLP where artificial intelligence, computer science and linguistics meet; slide 24 keeps computer science and linguistics but puts mathematics where artificial intelligence was. Jurafsky and Martin open their overview of the field with the same sentence, that the models are all drawn from the standard toolkits of computer science, mathematics and linguistics. Computer science supplies state space search, classifiers and dynamic programming. Mathematics supplies probability and linear algebra. Linguistics supplies the levels of part 3 and the categories, such as noun phrase and prepositional phrase, that the algorithms operate on.

The textbook behind the slides

The lecture credits its material mainly to Jurafsky and Martin, Speech and Language Processing. That is right; the duck sentence, the toolkit sentence and the whole shape of this lecture come from its first chapter. The edition details on the slide are not right.