NLP Notes

http://www.cs.columbia.edu/~mcollins/notes-spring2013.html

Intro

Michael Collins - Columbia, MIT.

http://www.cs.columbia.edu/~mcollins/notes-spring2013.html

What is NLP

Using a computer for understanding and/or generating language.

• Translation
• Information extraction
• Summarization
• Dialogue systems (allows user to interact with a system using natural language)
• Tagging
  • part-of-speech tagging
  • named entity recognition
• Parsing

Why is NLP hard

• Ambiguity
  • Sentences are ambiguous (I saw her duck with a telescope)
  • Sounds/acoustic are ambiguous ("recognize speech" vs "wreck a nice beach")
  • Words are ambiguous
  • Anaphora - resolving a pronoun to an entity

Syllabus

• Language modeling
• Tagging, Hidden Markov Models
• Statistical parsing
• Machine translation
• Log-linear models, discriminative methods
• Semi-supervised and unsupervised learning for NLP

Pre-reqs

• Basic linear algebra
• Probability
• Algorithms
• Programming skillz

Resources http://www.cs.columbia.edu/~mcollins

Week 1 : The Language Modeling Problem

Introduction to the Language Modeling Problem : 1

• The language modeling problem
• Trigram models
• Evaluating language models: perplexity
• Estimation techniques
  • Linear interpolation
  • Discounting methods

Assume we have:

• some (finite) set V of vocabulary. While it is finite, it may be quite large
• an infinite set of strings V' composed of words from V followed by a symbol to indicate an end. These are sentences.
• a training sample of example sentences (this set might be very large, over a billion words, possibly hundreds of billions)

We need to "learn" a probability distribution p so that Σ p(x) = 1, p(x) >= 0 for all x ∈ V' . A good language model will assign high probability to a sentence that is likely to exist in the language and low probability to one that is not.

Introduction to the Language Modeling Problem : 2

A naive estimate is simply to assign the probability relative to the number of times it is seen in the training set. Obviously deficient - but a starting point.

Markov Processes : 1

Review of Bayesian statistics.

The Markov assumption says that an event is conditioned only on the previous event. In reality, it is often dependent on all events, but often the previous event has the greatest weight.

Markov Processes : 2

Markov can consider any N events. Introduction to Markov through Bayesian probability.

Trigram Language Models

For every trigram (three words, or possibly start symbols) we know the probability of the third word given the previous two. This uses a Markov process.

We can use this to compute the probability of a sentence by finding the product of all trigrams in that sentence.

The independence assumption is often violated, but it's decent simple model. This model is tremendously useful for being very simple.

Evaluating Language Models : Perplexity

Σ log p(s_i) where s_i is all the sentences in the example data: I'm not sure what this means!!!!

Perplexity = 2^-l where l = (1/M) * Σ log p(s_i) and M is the total number of words in the test data the log is base 2. Lower perplexity is better.

The naive model where every trigram/word is given equal probability we get l = log (1/N) and Perplexity = N. So perplexity is important in relevance to the size of the vocabulary.

Claude Shannon conducted experiments on entropy of English.

Week 1: Parameter Estimation in Language Models

Linear Interpolation : 1

Sparse Data Problem

For a set of vocabulary, the number of trigrams grows very quickly and it becomes unrealistic to train on any significant portion of possible trigrams. For |v| = 20,000 there are over 8E12 trigrams.

Bias-Variance Trade off

A trigram model is powerful, but needs a lot of data, a unigram model is much less powerful, but needs only a fraction of the data.

Linear Interpolation : 2

q(w_i | w_i-2 , w_i-1 ) = λ₁ X qML(w_i | w_i-2 , w_i-1 ) + λ₂ X qML(w_i | w_i-1 ) + λ₃ X qML(w_i )

Where λ₁ + λ₂ + λ₃ = 1 and all values are >= 0

Choose λ₁, λ₂, λ₃ to maximize: L(λ₁, λ₂, λ₃) = ∑ c' (w₁ , w₂ , w₃ ) log q(w₁ | w₂ , w₃ ) where c' represents the validation data.

In theory, the λs shouldn't vary, but in practice, it can be useful to have them vary based on the trigram and bigram count from the training data. The term for this is 'partition' (each data range is a partition).

Discounting Methods : 1

Count^*(x) = Count(x) - D where D is the discount rate (something like 0.5)

We now have a 'missing probability mass'

α(w_i-1 ) = 1 - ∑ Count^*(w_i-1, w ) / Count(w_i-1 )

which we divide among all words in the V.

Α (w_i-1</sub ) = {w : Count(w_i-1, w ) > 0 } and qBO( w_i | w_i-1 ) = Count^*(w_i-1, w ) / Count(w_i-1 )

Β (w_i-1 ) = {w : Count(w_i-1, w ) = 0 } and 'qBO( w_i | w_i-1 ) = α(w_i-1 ) * qML(w_i) / ∑w ∈ Β(w_i-1 ) qML(w)

Discounting Methods : 2

We can extend this to a trigram model. Exercise left to reader. The process becomes recursive.

Week 2 : Tagging Problems and Hidden Markov Models

The Tagging Problem

• Parts of Speech tagging (PoS)
• Named Entity Recognition

Assume we have a training set - such as the Wall Street Journal Tree Bank.

Constraints are local or contextual. A local constraint means that a word is more likely type A than B purely because that statement is more often true. Contextual uses the surrounding words.

Generative Models for Supervised Learning

Given x⁽ⁱ⁾ and y⁽ⁱ⁾ for i = 1...m. Each x⁽ⁱ⁾ is an input (sentence) and each y⁽ⁱ⁾ is a label (set).

Conditional Model

For each word, look up which label is most likely or p(x|y)

Generative Model

p(x,y) = p(y) p(x|y)

Hidden Markov Models, Basic Definitions

A generative model. I was disappointed by this lecture - he went into a lot of math (that wasn't very useful) with almost no explanation of what HMMs are.

Parameter Estimation in HMMs

Smoothing, blah blah blah...

Split the training set into all words occurring more than X (say, 5) and all words occurring less than X - these are high and low frequency sets. The low frequency words are then mapped to a set of descriptive words (firstCap, firstWord, noCpas, etc).

The Viterbi Algorithm for HMMs (1)

π(k,u,v) = max r(y₁...y_k-2 , u, v)

Where k is the length of the sub-set (3 for a trigram), u and v are both in the tag set.

The Viterbi Algorithm for HMMs (2)

Use recursion...wow...this really needed 24 minutes. Annnnnnd - it's not even efficient.

π(k, u, v) = max[w ∈ S] ( π(k-1, w,u) * q(v|w, u) * e(x_k | v))

Then we use "backpointers" which is just memoization.

The Viterbi Algorithm for HMMs (3)

-sigh- that was so disappointing.

Week 3 - Parsing and context-free grammars

Introduction to the Parsing Problem : 1

Input is a sentence and output is a parse tree. We will treat it as a supervised machine learning problem.

Penn WSJ Treebank. 50,000 hand-annotated sentence trees.

Introduction to the Parsing Problem : 2

Word order can be easily manipulated in trees.

Context-Free Grammars : 1

G = (N, Σ, R, S)

• N is a set of non-terminal symbols
• Σ is a set of terminal symbols
• R is a set of rules of the form X →Y₁Y₂...Y_n for n ≥ 0 , X ∈ N, Y_i ∈ (N ∪ Σ)
• S ∈ N is a distinguished start symbol

This describes a tree. Σ is the leaves and R is the branching rules.

Left-Most Derivation. A way of iterating over possible structure. Start with the start symbol then recursively replace the left most non terminal with a rule. When the same string can be generated through two different paths, that is ambiguity.

Context-Free Grammars : 2

Ambiguity exists. "She announced a program to promote safety in trucks and vans" has over 14 interpretations.

A Simple grammar for English : 1 - 4

A lot of rules and terms.

I am going to continue to modify this from the next 3 lectures, so some of the following material is located in those lectures

• NN: single noun
• NNS: plural noun
• NNP: proper noun
• DT: derterminer (the, a some, every)
• JJ: adjective (fast, idealistic, red)
• NP: Noun phrase
  • → NBAR
  • → DT NBAR
  • → NP CC NP
• NBAR: This is an intermediate category.
  • → NN
  • → NN NBAR (car factory)
  • → JJ NBAR
  • → NBAR NBAR
  • → NBAR PP
  • → NBAR CC NBAR
• IN: preposition (in, under, of, on, with, as) there are about 100 prepositions in English
• PP: Preposition phrase
  • → IN NP
• Vi: Intransitive verb (sleeps, walks, laughs)
• Vt: Transitive verb (sees, saw, likes)
• Vd: Ditransitive verg (gave)
• V[5]: said, reported
• V[6]: told, informed
• V[7]: bet
• VP: verb phrase
  • → Vi
  • → Vt NP
  • → Vd NP NP
  • → VP PP
  • → V[5] SBAR
  • → V[6] NP SBAR
  • → V[7] NP NP SBAR
  • → VP CC VP
• S: sentence
  • → NP VP
  • → S CC S
• COMP: complementizer (that)
• SBAR:
  • → COMP S
  • → SBAR CC SBAR
• Coordinator (and, or, but)

Stuff We Missed

Agreement - the subject and the verb need to agree (the dogs laugh vs the dog laughs).

Wh-movement: "The dog the cat liked", liked is vt and matched "the dog" which has been moved to the beginning.

Active vs passive

• The dog saw the cat
• The cat was seen by the dog

Examples of Ambiguity

Duck can be a singular noun (NN) or transitive verb (Vi).

There is a preference for prepositions to modify the most recent verb.

Week 3 - Probabilistic Context-Free Grammers (CFGs)

Basics of PCFGs : 1

Give a probability to each rule so that every parse tree can be given a probability and the most likely can be identified.

I'm not going to write out the formula, but just multiply all the probabilities together to get the probability of a tree.

τ(s) is the set of all parse trees.

Basics of PCFGs : 2

Treebanks

• Penn WSJ Treebank

q_ML(α → Β) = Count(α → Β) / Count(α)

A technical point is that the the distribution of all possible parse trees must sum to 1. The obvious part of this is a grammar with no possible parsetrees is invalid. But also a grammar that divides too quickly will also not yield a valid distribution.

The CKY Parsing Algorithm : 1

Rules take the form (Chomsky Normal Form)

• X → Y₁ Y₂
• X → terminal

If the real grammar has rules with more than one symbol on the right, it is simply broken out into multiple levels with special symbols to represent them and probabilities of 100%.

The CKY Parsing Algorithm : 2

π[i, j, X] = most probable tree with root rule X spanning i to j inclusive.

Our goal is to find the highest π[1,n,S]

Recursive algorithm.

Base Case: π[i,i,X] = q(X → w_i</sub)

• • Or, the probability that X goes to that terminal (word)
  • If q(X → w_{i</sub) is not defined in the grammar, it is 0}

Recursion Case: π(i, j, X) = max( q(X → Y Z) * &pi(i, s, Y) * π(x+1, j, Z)) for s in range (i, j-1)

The CKY Parsing Algorithm : 3

Proof...boring!

Complexity is O(w³ * NT³) where w is the number of words in the sentence and NT is the number of non-terminals in the grammar. Not great, but better than brute force.

Weaknesses of PCFGs

Initial accuracy (in early 90s) was about 72%. Modern parsers are around 92%.

There is a strong independence assumption - that each word is independent from every other word, depending only upon the part of speech.

PCFGs have trouble attaching things that appear close together in the sentence. This is close attachment preference and PCFGs have a lot of trouble with it. Often the close attachment and non close attachment will have the same rule sets in a different order, rendering the exact same probabilities.

Lexicalized PCFGs

Lexicalization of a Treebank

For each rule in a CFG, denote one of the children as the "head". The head value propagates up the tree and we multiply our non-terminals by our vocabulary. The idea is that the "head" is the focus of each sub-tree and the one that propagates all the way to the top is the "most important word in the sentence".

Lexicalized PCFGs : Basic Definition

Review: CFG in Chomsky Normal form is G = (N, Σ, R, S) where:

• N is a set of non-terminal symbols
• Σ is a set of verminal symbols
• R is a set of rules taking one of two forms
  • X → Y₁ Y₂ with X, Y₁, Y₂ ∈ N
  • X → Y with X ∈ N and Y ∈ Σ
• S ∈ N is a distinguished start symbol

Lexicalization changes R to:

• X(h) → Y₁(h) Y₂(w) with X, Y₁, Y₂ ∈ N
• X(h) → Y₁(w) Y₂(h) with X, Y₁, Y₂ ∈ N
• X(h) → h with X ∈ N and h ∈ Σ

When applying our algorithm, only n²*|N|³ rules can be applicable. So our complexity only increases to O(n⁵*|N|³).

Parameter Estimation in Lexicalized PCFGs : 1

Not really sure...may have to come back to this one.

Parameter Estimation in Lexicalized PCFGs : 2

q(S(saw) →₂ NP(man) VP(saw)) = q(S →₂ NP VP | S,saw) * q(man|S →₂ NP VP,saw)

q(S →₂ NP VP | S,saw) = λ₁ * q_ML(S →₂ NP VP | S,saw) + λ₂ * q_ML(S →₂ NP VP | S)

The first segment uses the lexical information, and the second portion uses just the CFG probability.

q(man | S →₂ NP VP,saw) = λ₃ * q_ML(man | S →₂ NP VP,saw) + λ₄ * q_ML(man | S →₂ NP VP) + λ₅ * q_ML(man | NP)

Evaluation of Lexicalized PCFGs : 1

Recall vs. Precision. We can get as high as 92%.

Week 5 - Introduction to Machine Translation

Challenges in MT

• Lexical Ambiguity
  • book a flight
  • read a book
• Differing word order
  • English: subject-verb-object
  • Japanese: subject-object-verb
• Syntactic structure is not preserved
• Syntactic ambiguity

Classical Approaches to MT : 1

The classical approach was ruled based. Direct Machine Translation. Translation is word-by-word using a bilingual dictionary and then reordered to fit the target language.

I'll summarize about 15 slides - this is very complex and doesn't work well.

Next they tried "Transfer-Based Approaches". One approach is to build the parse tree, transform the parse tree into the target language and translate the words. The steps are analysis-transfer-generation.

Classical Approaches to MT : 2

Interlingua-Based translation. Analysis-Generation. Analyze the source into a language-independent representation. Generate the target from the meaning representation. This only needs two rule sets for each language, not O(n²) rules. But what does a language-independent representation look like? Nearly impossible to define.

Introduction to Statistical MT

Parallel corpora: sentence pairs in two languages

I love this - in 1949 Warren Weaver suggested statistical cryptanalysis techniques could be used for translation.

• p(e) : the language mode (the probability of sentence e existing in the language)
• p(f | e) : the probability of f given e - the probability that a french sentence translates to the English one

p(e|f) = p(e,f) / p(f) = [p(e)p(f|e)] / [Σ_ep(e)p(f|e)]

Which gives us the same answer as (though it is not mathematically equivalent) argmax_ep(e|f) = argmax_ep(e)p(f|e)

Though we are trying to solve for p(e|f), but changing it to p(e)p(f|e) we have the entire p(e) language model to draw on, which makes us far more likely to produce valid sentences.

Week 5 - The IBM Translation Models

IBM Model 1 : 1

The IBM model uses alignments. Each word aligns either with a word in the translation sentence or null (0). An alignment is just a sequence of number mapping the word from the target to the objective (double check that it might be reversed - in the example the mapping is F to E).

Define models for p(a|e,m) and p(f|a,e,m) giving us

 p(f,a|e,m) = p(a|e,m)p(f|a,e,m)

and

 p(f|e,m) = Σa∈A p(a|e,m)p(f|a,e,m)

Where A is the set of all possible alignments.

Given an English and French sentence, we can find the most probable alignment:

 p(a|f,e,m) = p(f,a|e,m) / Σa∈A

Although the original models were design for translation, they are now primarily used to find alignment.

IBM Model 2

Adds a "distortion" parameter by including the length of the sentences in the baysian probabilities.

The EM Algorithm for IBM Model 2 : 1

Challenge: We do not have alignments on our training data.

Probabilities are just ratios from training data (as always).

The EM Algorithm for IBM Model 2 : 2

The algorithm is iterative. We start with random values or a guess and then refine the estimate over several iterations.

The EM Algorithm for IBM Model 2 : 3

The math is very complex looking.

The core idea is that we iterate, using q and t to calculate δ then we recompute q and t using our δ values. Iterate.

The EM Algorithm for IBM Model 2 : 4

More stuff I don't care about.

Week 6 - Decoding of Phrase-Based Translation Models

I'm skipping week 6 for now because I don't care about translation.

Definition of the Decoding Problem : 1

A phrase is a set of words. Again, we use ratio-probabilities.

Week 7 - Log Linear Models

Two Example Problems

What is the probability of word w given the previous n words. We've done this with trigrams, but they have many weaknesses. We can try to take more aspects into account by increasing the dimensions of the linear interpolation, but it becomes unwieldy.

We've looked POS tagging and used hidden markov models to handle this. Again, we could take more data into account but it also grows hard to incorporate all the data in a meaningful way.

Features in Log-Linear Models : 1

General problem:

• Input domain x (possibly infinite)
• Finite label set y
• Find p(y|x)

Define features with boolean values and then a vector of the features. There is no harm in having a very large number of features.

Features in Log-Linear Models : 2

Example Feature

f(x,y) = 1 if current word ends in 'ing' and y = VBG

Where y is the part of speech and x is the context.

Definition of Log-Linear Models : 1

For a feature vector we will also have a parameter vector that scores each feature.

Σ v_kf_k(x,y)

f(x,y) gets a different score for each y. Higher scores mean higher probabilities.

p(y | x;v) = (e^v*f(x,y)) / Σ_y'∈Y e^v*f(x,y')

He's reading "p(y|x;v)" as "probability of y given x under v" and I'm not sure what that means.

Also, apparently this is important

• p(y|x;v) > 0
• Σ p(y|x;v) = 1

Definition of Log-Linear Models : 2

It's called the log-linear model because the log of the probability produces a linear component.

Parameter Estimation in Log-Linear Models : 1

v_ML = argmax_v∈R^M L(v)

L(v) = Σ_i log p(yⁱ | xⁱ; v) = Σ_i v * f( xⁱ, yⁱ) - Σ_i log Σ_{y' ∈ Y} e^{v * f(xi, y')}

L(v) is concave, which makes the solution possible (feasible). It is a smooth hill with no local optima except for the global optima. We can solve this with gradient descent.

...lots of math later...

dL(v)/dv_k = Σ_i f_k(xⁱ, yⁱ) - Σ_i Σ_{y' ∈ Y} f_k(xⁱ, y') p(y' | xⁱ; v)

Parameter Estimation in Log-Linear Models : 2

Don't do this by hand or write code to do it. Many packages exist to handle this for you.

Smoothing/Regularization in Log-linear Models

L(v) = Σ_i log p(yⁱ | xⁱ; v) = Σ_i v * f( xⁱ, yⁱ) - Σ_i log Σ_{y' ∈ Y} e^{v * f(xi, y')} - (λ / 2) Σ v²_k

dL(v)/dv_k = Σ_i f_k(xⁱ, yⁱ) - Σ_i Σ_{y' ∈ Y} f_k(xⁱ, y') p(y' | xⁱ; v) - λ v_k

see last parameter on each

Log-linear Models for tagging (MEMMs)

Recap of the Tagging Problem

Parts-of-speech, named entity recognition.

Independence Assumptions in Log-linear taggers

Iterate over EVERY POSSIBLE COMBINATION and compute their likelyhood.

Features in Log-Linear taggers

• previous 2 tags
• words in the input sentence
• index of word

We can now use spelling features (prefix/suffix). Sequences - both word and tag.

Parameters in Log-linear Models

Lots of review.

The Viterbi Algorithm for Log-linear Taggers

Assumes just the previous two tags matter. Still not impressed.

An Example Application

Labeling lines in an FAQ as part of head, question or answer. Because a 'word' is an entire line, most other methods are very poorly suited.

Week 8 - Log-Linear for History-based Parsing

Conditional History-based Models

nothing useful