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)