Transcript Natural Language Processing

Natural Language Processing
What’s the problem?
Input?
Output?
1
Example Applications
Enables great user interfaces!
Spelling and grammar checkers.
Http://www.askjeeves.com/
Document understanding on the WWW.
Spoken language control systems: banking,
shopping
Classification systems for messages, articles.
Machine translation tools.
2
NLP Problem Areas
Phonology and phonetics: structure of sounds.
Morphology: structure of words
Syntactic interpretation (parsing): create a
parse tree of a sentence.
Semantic interpretation: translate a sentence
into the representation language.
Pragmatic interpretation: incorporate current
situation into account.
Disambiguation: there may be several
interpretations. Choose the most probable
3
Some Difficult Examples
From the newspapers:
Squad helps dog bite victim.
Helicopter powered by human flies.
Levy won’t hurt the poor.
Once-sagging cloth diaper industry saved by full
dumps.
Ambiguities:
Lexical: meanings of ‘hot’, ‘back’.
Syntactic: I heard the music in my room.
Referential: The cat ate the mouse. It was ugly.
4
Parsing
Context-free grammars:
EXPR
EXPR
EXPR
EXPR
->
->
->
->
NUMBER
VARIABLE
(EXPR + EXPR)
(EXPR * EXPR)
(2 + X) * (17 + Y) is in the grammar.
(2 + (X)) is not.
Why do we call them context-free?
5
Using CFG’s for Parsing
Can natural language syntax be captured using
a context-free grammar?
Yes, no, sort of, for the most part, maybe.
Words:
nouns, adjectives, verbs, adverbs.
Determiners: the, a, this, that
Quantifiers: all, some, none
Prepositions: in, onto, by, through
Connectives: and, or, but, while.
Words combine together into phrases: NP, VP
6
An Example Grammar
S -> NP VP
VP -> V NP
NP -> NAME
NP -> ART N
ART -> a | the
V -> ate | saw
N -> cat | mouse
NAME -> Sue | Tom
7
Example Parse
The mouse saw Sue.
8
Try at Home
The Sue saw.
9
Also works...
The student like exam
I is a man
A girls like pizza
Sue sighed the pizza.
The basic word categories are not capturing
everything…
10
Grammars with Features
We add features to constituents:
AGR: number-person combination, (3s, 1p)
VFORM: verb form (go, goes, gone, going)
SUBCAT: restrictions on complements
None (sleep)
NP (find)
NP-NP (give)
Now every constituent has a set of features:
(NP (AGR 1p) (ROOT cat))
11
Grammar rules with Features
(S (AGR (? a)) -> (NP (AGR (? a)))
(VP (AGR (? a)))
(VP (AGR (? a)) (VFORM (? vf))) -->
(V (AGR (? a))
(VFORM (? vf)) (SUBCAT non))
dog: (N (AGR 3s) (ROOT dog))
dogs: (N (AGR 3p) (ROOT dog))
barks: (V (AGR 3s) (VFORM pres)
(SUBCAT none) (ROOT bark))
12
Semantic Interpretation
Our goal: to translate sentences into a logical
form.
But: sentences convey more than true/false:
It will rain in Seattle tomorrow.
Will it rain in Seattle tomorrow?
A sentence can be analyzed by:
propositional content, and
speech act: tell, ask, request, deny, suggest
13
Propositional Content
We develop a logic-like language for
representing propositional content:
Word-sense ambiguity
Scope ambiguity
Proper names --> objects (John, Alon)
Nouns --> unary predicates (woman, house)
Verbs -->
transitive: binary predicates (find, go)
intransitive: unary predicates (laugh, cry)
Quantifiers: most, some
14
Syntactic
category
Name
N
V(intransitive)
V(transitive)
V(stative)
Conj
ART
Quant
Adj
P
Examples
Logical
construct
John, TheTimes Constants
Man, house
Unary predicate
Laugh
Unary predicate
Find
Binary predicate
Believe, know Modal operator
And, but
Logical operator
The, a, this
Quantifiers
All, every, some Quantifiers
Red, heavy
Unary pred
In, on, above
Binary pred 15
Examples
(MOST x1: (laugh x1) (happy x1))
(Believe john (kill June Mary))
(Every b1: (boy b1)
(A d1 : (dog d1) (loves b1 d1)))
Semantic interpretation can be done with
feature grammars (see book).
16
Disambiguating Word Senses
Use type hierarchies:
The ruler likes the house.
Object
Animate
Person
Ruling person
Cat
Inanimate
Tool
Dwelling
Ruler tool hammer
house
Only allow patterns: (Likes Animate object)
17
Speech Acts
What do you mean when you say:
Do you know the time?
Context
Speaker knows time
Speaker doesn’t know
Speaker believes
hearer knows time
request
request
Speaker believes
hearer doesn’t know
offer
wasting time
Speaker doesn’t know
if hearer knows time
yes-no question
or cond offer
Y/N question or
18
request
Natural Language Summary
Parsing:
context free grammars with features.
Semantic interpretation:
Translate sentences into logic-like language
Use additional domain knowledge for word-sense
disambiguation.
Use context to disambiguate references.
Use context to analyze which speech act is meant.
19