Transcript Using Definite Knowledge

Using Definite Knowledge:
NLP and nl_interface.pl
Notes for Ch.3 of Poole et al.
CSCE 580
Marco Valtorta
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Natural Language Processing (NLP)
with Definite Clause Logic
• nl_interface.pl
• Computational Linguistics is a big field
• Three reasons to study NLP
– Ease of communication with people (infobot)
– Lots of information stored in NL
– Many problems in AI arise in NL
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Syntax, Semantics, Pragmatics
• Imagine finding these sentences at the beginning of
the textbook:
– This book is about computational intelligence.
– Green frogs sleep soundly.
– Colorless green ideas sleep furiously.
• Noam Chomsky
– Time flies like green bananas.
• Robert Oakman
– Sleep ideas green furiously colorless.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Rules and Lists for NL
• A context-free production rule:
– sentence -> noun_phrase, verb_phrase
• A corresponding definite clause:
– sentence(S) <- noun_phrase(N),
verb_phrase(V), append(N,V,S).
– Sentences and phrases are represented as lists,
e.g.:
• Noun_phrase([computer]).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Definite Clause Grammars
• We may do away with explicit appends by using
difference lists.
– This leads to definite clause grammars.
• noun-phrase(T1,T2) is true if T1 – T2 is a noun
phrase. E.g.,
– noun_phrase([the, computer, runs], [runs]).
is true in the normal interpretation, since “the
computer” is a noun phrase.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Examples
• sentence  noun_phrase, verb_phrase
sentence(T0,T2)  noun-phrase(T0,T1) &
verb_phrase(T1,T2).
Read: “There is a sentence between T0 and T2 if
there is a noun phrase between T0 and T1 and there
is a noun phrase between T1 and T2.”
• This reading is consistent with the view of the second
part of a difference list as a pointer to the end of the
list.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
More Examples
• h  a,b,[c,d],e,[f],g
• a, b, e, and g are nonterminal symbols: they get
rewritten
• c, d, and g are terminal symbols.
• h(T0,T6)  a(T0,T6) & b(T1, [c,d|T3]) &
e(T3,[f|T5]) & g(T5,T6).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
More Examples
• noun-phrase(T0,T4)  det(T0,T1) &
modifiers(T1,T2) & noun(T2,T3) & pp(T3,T4).
– “A noun phrase is a determiner followed by
modifiers followed by a noun followed by a
prepositional phrase.”
• det(T,T).
Empty list: determiner is optional!
det([a|T],T).
det([the|T],T).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Building Parse Trees
• Use extra arguments.
• This is done with recursive descent parsers in CSCE
531, where the atoms correspond to Java methods.
• sentence(T0,T2,s(NP,VP)) 
noun_phrase(T0,T1,NP) &
verb_phrase(T1,T2,VP).
• Parse trees do not adequately represent the deep
structure of a sentence.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Enforcing Constraints
• Parameters added to nonterminals enforce constraints
• cf. attribute grammars; these are contextual
grammars!
• nl_numbera.pl is a grammar that enforces
subject-verb number agreement.
• ?sentence([the, student, eats],[],Num,T)
• Num = singular,
T = s(np(definite,[],student,nopp),vp(eat,nonp,nopp)).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
NL Interface to a DB
• The query…
• ?noun_phrase([a, female, student, enrolled, in, a,
computer,science,course])
• …returns C = [course(X), dept(X,comp_science),
enrolled(P,X), student(P), female(P)].
• This is (almost) a Datalog query.
• See nl_interface.pl
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Limitations
• Assumptions of compositionality.
• Ambiguity of NL: need to deal with uncertainty.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Canned Text Output
• A grammar rule can be used “backwards.”
• The “meaning” (parse tree) may be bound, while the
sentence itself is a free variable.
• Example: trans.pl (Figure 3.7) with query…
• ?trans (scheduled(w92,cs422,clock(15,30),
above(csci333)), T, []).
• …produces the answer T = [the, winter, 1992, session,
of, the, advanced, artificial, intelligence, course, is,
scheduled, at, 3, :, 30, pm, in, the, room, above, the,
computer, science, department, office].
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering