Chapter 24

Natural Language Processing

Natural language processing (NLP)
• NLP is the discipline of building machines that can manipulate human
language or data in the way that it is written, spoken, and organized.
• NLP is about making computers understand and work with human
language, like how we speak or write.
• There are three primary reasons for computers to do NLP:
• To communicate with humans using
• Speech
• Natural language rather than a formal language such as first-order predicate calculus.
• To learn.
• Writing a lot of knowledge using natural language.
• To advance the scientific understanding of languages and language use,
using
• the tools of AI in conjunction with linguistics, cognitive psychology, and neuroscience.

Dr. Husne Ara Chowdhury 2

Language Models
• Problems of NLP:
• Language judgments vary from person to person and time to time.
• Natural language is ambiguous
• The mapping from symbols to objects is not formally defined.

• A language model is defined as a probability distribution describing

the likelihood of any string.
• “Do I dare disturb the universe?” has a reasonable probability as a string of
English,
• But “Universe dare the I disturb do?” is extremely unlikely
• With a language model, we can
• predict what words are likely to come next in a text to complete the message.
• compute which alterations to a text would make it more probable suggesting
spelling or grammar corrections.
• compute the most probable translation of a sentence.
Dr. Husne Ara Chowdhury 3
N-gram word models
• In natural each word is dependent on previous words.

• It captures all possible interactions between words.

• But with a vocabulary of 100,000 words and a sentence length of 40, this model would have
10200 parameters to estimate.
• Markov chain model considers only the dependence between n adjacent words known as an
n-gram model.
• with special cases “unigram” for 1-gram, “bigram” for 2-gram, and “trigram” for 3-gram.
• In an n-gram model, the probability of each word is dependent only on the n−1 previous words; that is:

• N-gram models work well for

• Classifying newspaper sections,
• Spam detection
• Sentiment analysis and
• Author attribution.
Dr. Husne Ara Chowdhury 4
Part-of-speech (POS) tagging

Dr. Husne Ara Chowdhury 5

Part-of-speech (POS) tagging
• The task of assigning a part of speech to each word in a sentence is called POS
tagging.
• From the start , it took a person with great qualities to succeed
IN DT NN , PRP VBD DT NN IN JJ NNS TO VB
• One common model for POS tagging is the hidden Markov model (HMM).
• Ex. the evidence consisted of observations of a person carrying an umbrella (or not), and
the hidden state was rain (or not) in the outside world.
• For POS tagging, the evidence is the sequence of words, W1:N, and the hidden states are
the lexical categories, C1:N.
• if we apply the Viterbi algorithm to find the most probable sequence of hidden states
(tags), accuracy usually around 97%
• To create an HMM for POS tagging, we need
• Transition model, P(Ct |Ct−1)
• P(Ct =VB|Ct−1 =MD)=0.8 means given a modal verb (such as would), the
expected following word to be a verb (such as think) with probability 0.8.
• Sensor model, P(Wt |Ct).
• P(Wt =would |Ct =MD)=0.1 means choosing a modal verb, we will choose would 10%
of the time.
Dr. Husne Ara Chowdhury 6
• A weakness of HMM models
• everything about language are expressed in terms of the transition and
sensor models.
• Long-range dependencies can be problematic and sometimes need
help understanding the context of a word in a sentence entirely.
• Logistic Regression can solve these problems and provides
higher accuracy.

Dr. Husne Ara Chowdhury 7

Grammar
• A grammar is a set of rules that defines the tree structure of
allowable phrases.
• A language is the set of sentences that follow grammar rules.
• Natural languages do not work exactly like the formal language of
FOL.
• Probabilistic context free grammar, or PCFG
• assigns a probability to each string, and
• “context-free” means that any rule can be used in any context:
• the rules for a noun phrase at the beginning of a sentence are the same as for
another noun phrase later in the sentence, and
• if the same phrase occurs in two locations, it must have the same probability each
time.
• Adjs → Adjective [0.80]
| Adjective Adjs [0.20]
• means that the syntactic category Adjs can be either a single Adjective, with
probability 0.80, or of an Adjective followed by a string that constitutes an
Adjs, with probability 0.20
Dr. Husne Ara Chowdhury 8
Grammar ℰ0

Dr. Husne Ara Chowdhury 9

Lexicon for Grammar

Dr. Husne Ara Chowdhury 10

Parsing
• Parsing is the process of analyzing a string of words to uncover
its phrase structure, according to the rules of a grammar.
• Have the students in section 2 of Computer Science 101 take the
exam.
• Have the students in section 2 of Computer Science 101 taken the
exam?
• Dynamic programming: every time we analyze a substring,
store the results so we won’t have to reanalyze it later.
• For example, once we discover that “the students in section 2 of
Computer Science 101” is an NP, we can record that result in a data
structure known as a chart.
• An algorithm that does this is called a chart parser

Dr. Husne Ara Chowdhury 11

Parsing
• Parsing the string “The wumpus is dead” using Grammar ℰ0
• Using A* Algorithm

Dr. Husne Ara Chowdhury 12

Algorithms for Parsing
• A probabilistic version of a bottom-up chart parsing algorithm called the
CYK algorithm:
• Space Complexity: O(n2m)
n is the number of words in the sentence, and m is
• Time Complexity: O(n3m). the number of nonterminal symbols in the grammar
• A ∗ algorithm: we don’t have to search the entire state space, and we are
guaranteed that the first parse found will be the most probable.
• Complexity: O(n)
• Parse tree for the sentence “Every wumpus
smells”
• probability of whole tree is
0.9×0.25×0.05×0.15×0.40×0.10=0.0000675.
• Linear form as [S [NP [Article every][Noun
wumpus]][VP [Verb smells]]].

Dr. Husne Ara Chowdhury 13

• Beam search:
• we consider only the b most probable alternative [Link] highest
probability
• parser can operate in O(n) time and still finds the best parse most of
the time.
• A beam search parser with b = 1 is called a deterministic parser
• Shift-reduce parsing:
• we go through the sentence word by word,
• choosing at each point whether to shift the word onto a stack of constituents,
• or to reduce the top constituent(s) on the stack according to a grammar rule.

Dr. Husne Ara Chowdhury 14

Dependency parsing

Dr. Husne Ara Chowdhury 15

Learning a parser from examples
• To apply supervised learning, we need input/output pairs of
sentences and their parse trees.
• Ex. Penn Treebank
• Given a treebank, we can create a PCFG just by
• S → NP VP [0.6].
• The phrase “the good and the bad” is parsed as
• NP → Article Noun Conjunction Article Noun
• NP → NP Conjunction NP.
• Unsupervised parsing: we learn a new grammar using a corpus
of sentences without trees.
• Semisupervised parsing: we start with a small number of trees
as data to build an initial grammar, then add a large number of
unparsed sentences to improve the grammar.
Dr. Husne Ara Chowdhury 16
Augmented Grammars
• “I ate a banana” is fine
• “Me ate a banana” is ungrammatical
• “I ate a bandanna” is unlikely
• A category like Pronoun that has been augmented with features like
“subjective case, first person singular” is called a subcategory.
• Augmented grammar
• “I” represented as NP(Sbj,1S,Speaker), which means.....
• “me” would be represented as NP(Obj,1S,Speaker)
• A lexicalized PCFG is a type of augmented grammar that allows us to assign
probabilities based on properties of the words in a phrase other than just the syntactic
categories. Ex.

Dr. Husne Ara Chowdhury 17

Augmented Grammars
• Part of an augmented grammar that handles case agreement,
subject–verb agreement, and head words.

Dr. Husne Ara Chowdhury 18

Augmented Grammars
• S(v) → NP(Sbj,pn,n) VP(pn, v) [P5(n, v)].
• This rule says that when an NP is followed by a VP they can form an S,
• but only if the NP has the subjective (Sbj) case and
• the person and number (pn) of the NP and VP are identical. (in agreement.)
• Pronoun(Sbj,1S,I) → I [0.005] which says that “I” is a Pronoun in the subjective
case, first-person singular, with head “I.
• A grammar for arithmetic expressions, augmented with semantics (Next slide).

Dr. Husne Ara Chowdhury 19

Semantic interpretation

Dr. Husne Ara Chowdhury 20

Semantic interpretation

Dr. Husne Ara Chowdhury 21

Learning semantic grammars
• The Penn Treebank does not include semantic representations
-just syntactic trees.
• A system that learns a grammar for a question-answering
• Sentence: What states border Texas?
• Logical Form: λ[Link](x)∧λ[Link](x,Texas)
• A limitation of these systems is that
• The training data includes logical forms.
• These are expensive to create,
• Requiring human annotators with specialized expertise
• Not everyone understands the subtleties of lambda calculus and
predicate logic.

Dr. Husne Ara Chowdhury 22

Complications of Real Natural Language
• The grammar of real English is endlessly complex:
• Quantification: “Every agent feels a breeze.”
• The sentence has only one syntactic parse.
• But it is semantically ambiguous: is there one breeze that is felt by all
the agents, or does each agent feel a separate personal breeze?
• Pragmatics:“I am in Boston today,”
• “I” would be represented by Speaker
• Another part of pragmatics is interpreting the speaker’s intent
• speech act: a statement, a promise, a warning, a command, and so on.
• Long-distance dependencies: “she didn’t hear or even see him”.
• Time and tense: “Ali loves Bo” and “Ali loved Bo.”
• English uses verb tenses (past, present, and future) to indicate the
relative time of an event.

Dr. Husne Ara Chowdhury 23

Complications of Real Natural Language
• Ambiguity:
• Lexical ambiguity is when a word has more than one meaning: “back”
can be an adverb (go back), an adjective (back door), a noun (the back
of the room), a verb (back a candidate).
• Syntactic ambiguity refers to a phrase that has multiple parses: “I
smelled a wumpus in 2,2” has two parses: one where the prepositional
phrase “in 2,2” modifies the noun and one where it modifies the verb.
• The syntactic ambiguity leads to a semantic ambiguity, because one
parse means that the wumpus is in 2,2 and the other means that a
stench is in 2,2. In this case, getting the wrong interpretation could be a
deadly mistake.

Dr. Husne Ara Chowdhury 24

Natural Language Tasks
• Speech recognition
• Text-to-speech synthesis
• Machine translation
• Information extraction:
• process of acquiring knowledge
• Information retrieval:
• task of finding documents that are relevant and important for a given query
• Question Answering

Dr. Husne Ara Chowdhury 25