Natural Language Processing - Class 9

Problem with CFGs.

Grammars over-generate: admit "I liked her" but also "me liked she".
Cannot deal with agreement (person and number).
No notion of common-sense restrictions: "the table liked the man".
CFGs too limited for natural language (maybe): cannot generate the language AnBnCn which seem to occur: "Robin and Sandy loved and hated Pat and Kim, respectively".
Agreement could be solved in CFG (sing-NP, sing-3rd-NP...) but much easier with more powerful grammatical formalism.

More on that point:

talked about equivalence classes: not very much so - for example:
```
the dog runs
the dogs run
```
not all phrases are structured from adjacent constituents:
```
Write everything down that she tells you
```
CFG not intuitive: Missing the point of process phrase vs. subject phrase forces the distinction for v.similar classes like plural and singular nouns. Also, if this distinction is ok then should be also defined for determiners etc. In languages like Hebrew: more - adjective agrees also, definiteness, gender and number.

Linguistic Methods to solve this problem:

transformational grammar

- write everything that she tells you down  ->
- write everything down that she tells you

Phrase Structure based formalism.

Phrase Structure formalism: Account for all sentences by the same set of rules. Although number of equivalence classes is very large, the various subsets of the classes need to be distinguished only for some purposes: for other they can be treated as a single larger class.

Use: description structures: ((cat noun)
                              (number singular))

Description refers not only to the lists of attributes but also to the operation on them.

An Example: (from Unification, Martin Kay in Computational Linguistics and Formal Semantics, ed. M.Rosner, R.Johnson).

meet a person you don't know how he looks like
needs a description
refer to some attributes according to the vast of people possibly around: the more descriptions, the more distinctive the description is.

((height 5ft10inch)
 (beard yes)
 (suit ((color blue)
        (stripes yes))))

Structure: (attribute value) pairs.
Value can be: 1. an atom 2. a description

Describe me: that is - describe the suit.. embedded description.
A value (a v) is unique:
- unique suit - can be refered to as "the suit"

Defines a partial function on description:

a function: F(beard)=yes only
partial: F(x) for most x is not defined.

Scene of descriptions:
Suppose you were late and ask the bystander if saw anyone waiting, he gives the description:

((age 45)
 (beard yes)
 (suit ((fabric tweed))))

This is not helpful: now contradictions, only beard is common.
If you then find out it was me, then you know a broader picture of my description:

((height 5ft10inch)
 (beard yes)
 (suit ((color blue)
        (stripes yes)
        (fabric tweed)))
 (age 45))

This description is a combination of the (a v) sets, eliminating repetitions. This process is called unification.

In the case of a description like

((age 45)
 (height 6ft2ins))

Unification would fail.

To sum:

description are always partial: new pairs can always be added.
descriptions are related through compatibility.
compatibile descriptions can be combined - or unified, to yield a generally more complete (and less partial) description of either of the originals.

Grammar Rules

(cat s) ->  ((cat np)          ((cat vp)
	       (number ?n)         (number ?n)
               (person ?p))        (person ?p))

FDs for "the dog runs" "the dogs run"
Add a notion of a name of an FD:

allow ((cat s)
        (subj ?subj)
        (pred ?pred)) ---> ?subj is the name of the np description, 
 			   ?pred of the vp description.

Unification grammars and Logic Programming

Initially, Prolog was designed to deal with Natural Language. Define Parsing as deduction:

;;;; Code from Paradigms of AI Programming
;;;; Copyright (c) 1991 Peter Norvig

  (<- (S ?s)
      (NP ?np)
      (VP ?vp)
      (concat ?np ?vp ?s))

(<- (concat () ?l ?l))
(<- (concat (?x ?a) ?b (?x ?c)) (concat ?a ?b ?c))

We see in this example how

Variables stand for lists of words.
Very inefficient: blindly generate all possible nps then all possible vps, then test if there are words in common with input (in concat).

More efficient:

  (<- (S ?s)
      (concat ?np ?vp ?s)
      (np ?np)
      (vp ?vp))

Make only n+1 blind guesses.

Would be better to have NP and Concat work together. In Lisp, would use multiple values: NP returns success or failure and the list of remaining words.
In Prolog, use additional arguments to relations:

  (<- (S ?s0 ?s2)
      (NP ?s0 ?s1)
      (VP ?s1 ?s2))

"The string from s0 to s2 is a sentence, if there is an s1 such that the string from s0 to s1 is a noun phrase and the string from s1 to s2 is a verb phrase."

(?- (S (The boy ate the apple) ()))

?s0 = (The boy ate the apple)
?s1 =         (ate the apple)
?s2 =                      ()

Other reading (difference lists):
"Is the list ?s0 minus the list ?s1 a noun phrase?"
Could have an explicit call to concat for difference lists:

(<- (S ?s-in ?s-rem)
    (NP ?np-in ?np-rem)
    (VP ?vp-in ?vp-rem)
    (concat ?np-in ?np-rem ?vp-in ?vp-rem ?s-in ?s-rem))

(<- (concat ?a ?b ?b ?c ?a ?c))

[ie, (a-b)+(b-c) = (a-c)]

Expressing agreement with Unification

(<- (S ?s0 ?s2)
    (NP ?agr ?s0 ?s1)
    (VP ?agr ?s1 ?s2))

(<- (NP 3sg (he . ?s) ?s))
(<- (NP ~3sg (they . ?s) ?s))

(<- (VP 3sg (sleeps . ?s) ?s))
(<- (VP ~3sg (sleep . ?s) ?s))

- Test:
(?- (S (he sleeps) ()))
Yes.

(?- (S (He sleep) ()))
No.

- Allow for common nouns:

(<- (NP ?agr ?s0 ?s2)
    (Det ?agr ?s0 ?s1)
    (N ?agr ?s1 ?s2))

(<- (Det ?any (the . ?s) ?s))
(<- (N 3sg (boy . ?s) ?s))
(<- (N 3sg (girl . ?s) ?s))

- Generate all possible legal sentences:

(?- (S ?words ()))
?words = (he sleeps);
?words = (they sleep);
?words = (the boy sleeps);
?words = (the girl sleeps);
No.

Adding semantic interpretation

Add another argument to each predicate to build up the semantics.
Get a real parser not only a recognizer.

(<- (S (?pred ?subj) ?s0 ?s2)
    (NP ?agr ?subj ?s0 ?s1)
    (VP ?agr ?pred ?s1 ?s2))

(<- (NP 3sg (the male) (he . ?s) ?s))
(<- (NP ~3sg (some objects) (they . ?s) ?s))

(<- (NP ?agr (?det ?n) ?s0 ?s2)
    (Det ?agr ?det ?s0 ?s1)
    (N ?agr ?n ?s1 ?s2))

(<- (VP 3sg sleep (sleeps . ?s) ?s))
(<- (VP ~3sg sleep (sleep . ?s) ?s))

(<- (Det ?any the (the . ?s) ?s))

(<- (N 3sg (young male human) (boy . ?s) ?s))
(<- (N 3sg (young female human) (girl . ?s) ?s))

Notes on semantic representation for entities (nouns) and predicates (verbs):

Driven by needs of application (level of distinction required).
Should be unambiguous (orange fruit != orange color).
Should express generalities (sleeps and sleep should be related).

This grammar builds a semantic rep. but no syntactic tree.
If tree is needed, add another argument to the predicates:

(<- (S (?pred ?subj) (s ?np ?vp) ?s0 ?s2)
    (NP ?agr ?subj ?np ?s0 ?s1)
    (VP ?agr ?pred ?vp ?s1 ?s2))

(<- (NP 3sg (the male) (np he) (he . ?s) ?s))
(<- (NP ~3sg (some objects) (np they) (they . ?s) ?s))

(<- (NP ?agr (?det ?n) (np ?det-syn ?n-syn) ?s0 ?s2)
    (Det ?agr ?det ?det-syn ?s0 ?s1)
    (N ?agr ?n ?s1 ?n-syn ?s2))

(<- (VP 3sg sleep (vp sleeps) (sleeps . ?s) ?s))
(<- (VP ~3sg sleep (vp sleep) (sleep . ?s) ?s))

(<- (Det ?any the (det the) (the . ?s) ?s))

(<- (N 3sg (young male human) (n boy) (boy . ?s) ?s))
(<- (N 3sg (young female human) (n girl) (girl . ?s) ?s))

- Can be used to enumerate all syntax/semantics/sentence triplets:

;; Parsing
> (?- (S ?sem ?syn (He sleeps) ()))
?SEM = (SLEEP (THE MALE))
?SYN = (S (NP HE) (VP SLEEPS)).

;; Generating
> (?- (S (sleep (the male)) ? ?words ()))
?WORDS = (HE SLEEPS).

;; Enumerating
> (?- (S ?sem ?syn ?words ()))
?SEM = (SLEEP (THE MALE))
?SYN = (S (NP HE) (VP SLEEPS))
?WORDS = (HE SLEEPS);

?SEM = (SLEEP (SOME OBJECTS))
?SYN = (S (NP THEY) (VP SLEEP))
?WORDS = (THEY SLEEP);

?SEM = (SLEEP (THE (YOUNG MALE HUMAN)))
?SYN = (S (NP (DET THE) (N BOY)) (VP SLEEP))
?WORDS = (THE BOY SLEEPS);

?SEM = (SLEEP (THE (YOUNG FEMALE HUMAN)))
?SYN = (S (NP (DET THE) (N GIRL)) (VP SLEEP))
?WORDS = (THE GIRL SLEEPS);

No.

Cleaning up: Definite Clause Grammars (DCGs)

Problem of adding more and more arguments of different types (syntax, semantics, agreement, in/out strings).
define a new language.
DCG clauses have main functor --> and compile into straight Prolog clauses.
Implement as a macro.


(rule (S) --> (NP) (VP))

expands into:


(<- (S ?s0 ?s2)
    (NP ?s0 ?s1)
    (VP ?s1 ?s2))

Make it data-driven to allow for other types of rules as well:

(defmacro rule (head &optional (arrow ':-) &body body)
  "Expand one of several types of logic rules into pure Prolog."
  ;; Dispatch on the arrow (data-driven)
  (funcall (get arrow 'rule-function) head body))

(setf (get ':- 'rule-function)
      #'(lambda (head body) '(<- ,head .,body)))

(rule head :- body) expands into (<- head body)

2 more features of DCGs: add arbitrary Prolog calls In Prolog:

s(Sem) --> np(Subj), vp(Pred),
                        {combine(Subj,Pred,Sem)}.

In Lisp notation:

  (rule (S ?sem) --> (NP ?subj) (VP ?pred)
        (:test (combine ?subj ?pred ?sem)))

- Add individual words on the right-hand side:
In Prolog: verb --> [sleeps]. In Lisp notation:

(rule (NP (the male) 3sg) --> (:word he))
                    (rule (VP sleeps 3sg) --> (:word sleeps))

- Add 2 utilities to deal with these 2 features:

  (defun dcg-normal-goal-p (x) (or (starts-with x :test) (eq x '!)))
  (defun dcg-word-list-p (x) (starts-with x :word))

- The --> translator:

  (setf (get '--> 'rule-function) 'make-dcg)

  (defun make-dcg (head body) 
    (let ((n (count-if (complement #'dcg-normal-goal-p) body)))
      `(<- (,@head ?s0 ,(symbol '?s n))
	   .,(make-dcg-body body 0))))

  (defun make-dcg-body (body n)
    "Make the body of a Definite Clause Grammar (DCG) clause.
    Add ?string-in and -out variables to each constituent.
    Goals like (:test goal) are ordinary Prolog goals,
    and goals like (:word hello) are literal words to be parsed."
    (if (null body)
	nil
      (let ((goal (first body)))
        (cond
	 ((eq goal '!) (cons '! (make-dcg-body (rest body) n)))
	 ((dcg-normal-goal-p goal)
	  (append (rest goal)
		  (make-dcg-body (rest body) n)))
	 ((dcg-word-list-p goal)
	  (cons
	   `(= ,(symbol '?s n)
	       (,@(rest goal) .,(symbol '?s (+ n 1))))
	   (make-dcg-body (rest body) (+ n 1))))
	 (t (cons
	     (append goal
		     (list (symbol '?s n)
			   (symbol '?s (+ n 1))))
	     (make-dcg-body (rest body) (+ n 1))))))))

The same simple grammar in DCG format:

(rule (S (?pred ?subj)) -->
  (NP ?agr ?subj)
  (VP ?agr ?pred))
(rule (NP ?agr (?det ?n)) -->
  (Det ?agr ?det)
  (N ?agr ?n))
(rule (NP 3sg (the male))          --> (:word he))
(rule (NP ~3sg (some objects))     --> (:word they))
(rule (VP 3sg sleep)               --> (:word sleeps))
(rule (VP ~3sg sleep)              --> (:word sleep))
(rule (Det ?any the)               --> (:word the))
(rule (N 3sg (young male human))   --> (:word boy))
(rule (N 3sg (young female human)) --> (:word girl))

Extend the grammar: Dealing with Transitive Verbs

Allow for transitive and intransitive verbs (with/without objects). Prevent sentences like: "* The boy meets."
How to deal with semantic interpretation of transitive verbs?

  "Terry kisses Jean" ---> (kiss Terry Jean)

What should be the interpretation of the VP (kisses Jean)?
Model of NP VP sentence is that VP's interpretation is a predicate applied to the subject. Use lambda abstraction:

  "kisses Jean" ---> (lambda (x) (kiss x Jean))

When applied to interpretation of Terry, obtain as desired:

  "Terry kisses Jean" ---> ((lambda (x) (kiss x Jean)) Terry) 
                           === (kiss Terry Jean)

The simplification is not performed automatically by Prolog.
Need to encode it (called beta-reduction in Lambda-calculus, funcall in Lisp)

  (<- (funcall (lambda (?x) ?body) ?x ?body))

Then write sentence rule as:

  (rule (S ?sem) -->
    (NP ?agr ?subj)
    (VP ?agr ?pred)
    (:test (funcall ?pred ?subj ?sem)))

Alternatively, we can compile the call to funcall. Instead of using a lambda representation for the semantics of VP, represent it as 2 arguments: input and output. ?subj is the input parameter that gets bound from above (top-down) and ?pred, which is the body of the lambda expression and gets bound from below, and uses ?subj as a term.

  (rule (S ?pred) -->
    (NP ?agr ?subj)
    (VP ?agr ?subj ?pred))

Read as:
"To parse a sentence, parse a noun phrase followed by a verb phrase. If they have different agreement features then fail, but otherwise, insert the interpretation of the noun phrase, ?subj, into the proper spot in the interpretation of the verb phrase, ?pred, and return ?pred as the final interpretation of the sentence."

Complete grammar with transitive/intransitive verabs:

(rule (S ?pred) -->
  (NP ?agr ?subj)
  (VP ?agr ?subj ?pred))

(rule (VP ?agr ?subj ?pred) -->
  (Verb/tr ?agr ?subj ?pred ?obj)
  (NP ?any-agr ?obj))

(rule (VP ?agr ?subj ?pred) -->
  (Verb/intr ?agr ?subj ?pred))

(rule (Verb/tr ~3sg ?x (kiss ?x ?y) ?y) --> (:word kiss))
(rule (Verb/tr 3sg ?x (kiss ?x ?y) ?y) --> (:word kisses))
(rule (Verb/tr ?any  ?x (kiss ?x ?y) ?y) --> (:word kissed))

(rule (Verb/intr ~3sg ?x (sleep ?x)) --> (:word sleep))
(rule (Verb/intr 3sg ?x (sleep ?x)) --> (:word sleeps))
(rule (Verb/intr ?any  ?x (sleep ?x)) --> (:word slept))

(rule (NP ?agr ?sem) -->
  (Name ?agr ?sem))

(rule (NP ?agr (?det-sem ?noun-sem)) -->
  (Det ?agr ?det-sem)
  (Noun ?agr ?noun-sem))

(rule (Name 3sg Terry) --> (:word Terry))
(rule (Name 3sg Jean)  --> (:word Jean))

(rule (Noun 3sg (young male human))           --> (:word boy))
(rule (Noun 3sg (young female human))         --> (:word girl))
(rule (Noun ~3sg (group (young male human)))   --> (:word boys))
(rule (Noun ~3sg (group (young female human))) --> (:word girls))

(rule (Det ?any the)  --> (:word the))
(rule (Det 3sg a) --> (:word a))

Examples of parsing:

> (?- (S ?sem (The boys kiss a girl) ()))
?SEM = (KISS (THE (GROUP (YOUNG MALE HUMAN)))
             (A (YOUNG FEMALE HUMAN))).

> (?- (S ?sem (The girls kissed the girls) ()))
?SEM = (KISS (THE (GROUP (YOUNG FEMALE HUMAN)))
             (THE (GROUP (YOUNG FEMALE HUMAN)))).

> (?- (S ?sem (Terry kissed the girl) ()))
?SEM = (KISS TERRY (THE (YOUNG FEMALE HUMAN))).

> (?- (S ?sem (The girls kisses the boys) ()))
No.

> (?- (S ?sem (Terry kissed a girls) ()))
No.

> (?- (S ?sem (Terry sleeps Jean) ()))
No.

Extend the grammar: Dealing with Quantification.

One of the most important/complex issue in NL.

- (?- (S ?sem (The girls kissed the girls) ()))
?SEM = (KISS (THE (GROUP (YOUNG FEMALE HUMAN)))
             (THE (GROUP (YOUNG FEMALE HUMAN)))).

- In fact, the sentence is ambiguous and has several possible interpretations.

 forall x, forall y, girl(x) and girl(y) ==> kiss(x,y)
 forall x, forall y, girl(x) and girl(y) and x != y ==> kiss(x,y)
 forall x, exist y, exist z, girl(x) and girl(y) and girl(z) ==> kiss(x,y) and kiss(z,x)
 forall x, exist y, girl(x) and girl(y) ==> kiss(x,y) or kiss(y,x)

In English:

 Every girl kisses every other girl.
 Every girl kisses every other girl but not herself.
 Every girl kisses and is kissed by at least one other girl (but not
 necessarily all of them).
 Every girl is on at least one kissing.

The current representation is ambiguous.
Do NOT want to choose one representation over the other arbitrarily.
Best strategy: keep a concise form of interpretation, from which all possible unambiguous interpretations can be computed when needed.

- The problem:
"Every picture paints a story" now gets (paints (every picture) (a story))
Ambiguous between:

  forall x, picture(x) ==> exist y, story(y) and paint(x,y)
  exist y, story(y) and forall x, picture(x) ==> paint(x,y)
 
  For each picture there is a story that it paints.
  There is a single picture that all pictures paint.

Intended interpretation is probably the first one (several stories).

  "Every US citizen has a president."

Intended interpretation is probably the second one (single president).

First exercise: always produce the first interpretation.
Lisp notation:

  (all ?x (-> (picture ?x) (exists ?y (and (story ?y) (paint ?x ?y)))))

Where do the "all" and "every" come from?
Must come from the determiners.
Then, "all" is followed by "->" and "exist" by "and".

  (rule (Det ?any ?x ?p ?q (the ?x (and ?p ?q)))    --> (:word the))
  (rule (Det 3sg  ?x ?p ?q (exists ?x (and ?p ?q))) --> (:word a))
  (rule (Det 3sg  ?x ?p ?q (all    ?x (-> ?p ?q)))  --> (:word every))

Same principle as in the VP interpretation: the variables ?p and ?q come from above (they are in-variables). They are holes to be filled by the rest of the sentence: ?p will be filled by a noun, ?q by a predicate.

Note phenomenon: Quantifier RAISING.
In previous grammar, verb was HEAD of sentence. Here determiner of subject guides whole interpretation.

?x is not a hole in the interpretation. It plays a very different role. At the end of the parse, ?x is not filled, it remains unbound. But it is used in the body of ?p and ?q. It is called a METAVARIABLE because it is a variable in our semantic language, not a variable in the Prolog implementation. Just happens that Prolog variables can be used to encode metavariables.

Trace of interpretation:

  Every     = (all ?x (-> ?p1 ?q1))
  picture   = (picture ?x)
  paints    = (paint ?x ?y)
  a         = (exists ?y (and ?p2 ?q2))
  story     = (story ?y)

  Every picture  = (all ?x (-> (picture ?x) ?q1))
  a story        = (exits ?y (and (story ?y) ?q2))
  paints a story = (exits ?y (and (story ?y) (paint ?x ?y)))

- The NP predicate:
now has 4 arguments: agreement, metavariable ?x, a predicate that will be supplied externally by the verb, last argument is interpretation of the NP as a whole.

  (rule (NP ?agr ?x ?pred ?name) -->
    (Name ?agr ?name))

  ;(rule (NP ?agr ?x ?pred ?np) -->
  ;  (Det ?agr ?x ?noun ?pred ?np)
  ;  (Noun ?agr ?x ?noun))

Add processing for simple relative clauses:
Important, this is the first recursive rule - which means we can now generate an infinite language.
Only relative clauses of the form: "the boy that paints a picture" ie, "det N that VP". (not of the form "the picture that the boy paints.")

  (rule (NP ?agr ?x ?pred ?np) -->
    (Det ?agr ?x ?noun&rel ?pred ?np)
    (Noun ?agr ?x ?noun)
    (rel-clause ?agr ?x ?noun ?noun&rel))

  (rule (rel-clause ?agr ?x ?np ?np) --> )
  (rule (rel-clause ?agr ?x ?np (and ?np ?rel)) -->
    (:word that)
    (VP ?agr ?x ?rel))

Parameters to the rel-clause:
agreement features of head noun and meta-variable representing head noun. The last 2 arguments are an accumulator for predication on the head noun metavariable: arg 3 is predications so far, arg 4 is predications including that of the relative clause.
First rule is in case there is no rel-clause: what gets out is what gets in. Second rule adds one predication to the NP.

- Verbs remain unchanged.
- VP and S almost unchanged, except for call to NP that has right parameters.

Examples of output:

Every picture paints a story.
(ALL ?3 (-> (PICTURE ?3)
            (EXISTS ?14 (AND (STORY ?14) (PAINT ?3 ?14)))))

Every boy that paints a picture sleeps.
(ALL ?3 (-> (AND (AND (YOUNG ?3) (MALE ?3) (HUMAN ?3))
                 (EXISTS ?19 (AND (PICTURE ?19)
                                  (PAINT ?3 ?19))))
            (SLEEP ?3)))

Every boy that sleeps paints a picture.
(ALL ?3 (-> (AND (AND (YOUNG ?3) (MALE ?3) (HUMAN ?3))
                 (SLEEP ?3))
            (EXISTS ?22 (AND (PICTURE ?22) (PAINT ?3 ?22)))))

Every boy that paints a picture that sells 
paints a picture that stinks.
(ALL ?3 (-> (AND (AND (YOUNG ?3) (MALE ?3) (HUMAN ?3))
                 (EXISTS ?19 (AND (AND (PICTURE ?19) (SELLS ?19))
                                  (PAINT ?3 ?19))))
            (EXISTS ?39 (AND (AND (PICTURE ?39) (STINKS ?39))
                             (PAINT ?3 ?39)))))

Example of grammar:

(rule (Det ?any ?x ?p ?q (the ?x (and ?p ?q)))    --> (:word the))
(rule (Det 3sg  ?x ?p ?q (exists ?x (and ?p ?q))) --> (:word a))
(rule (Det 3sg  ?x ?p ?q (all    ?x (-> ?p ?q)))  --> (:word every))

(rule (Noun 3sg ?x (picture ?x)) --> (:word picture))
(rule (Noun 3sg ?x (story ?x)) --> (:word story))
(rule (Noun 3sg ?x (and (young ?x) (male ?x) (human ?x))) -->
  (:word boy))

(rule (NP ?agr ?name ?pred ?pred) -->
  (Name ?agr ?name))

(rule (NP ?agr ?x ?pred ?np) -->
  (Det ?agr ?x ?noun&rel ?pred ?np)
  (Noun ?agr ?x ?noun)
  (rel-clause ?agr ?x ?noun ?noun&rel))

(rule (rel-clause ?agr ?x ?np ?np) --> )
(rule (rel-clause ?agr ?x ?np (and ?np ?rel)) -->
  (:word that)
  (VP ?agr ?x ?rel))

(rule (Verb/tr ~3sg ?x ?y (paint ?x ?y)) --> (:word paint))
(rule (Verb/tr 3sg  ?x ?y (paint ?x ?y)) --> (:word paints))
(rule (Verb/tr ?any ?x ?y (paint ?x ?y)) --> (:word painted))

(rule (Verb/intr ~3sg ?x (sleep ?x)) --> (:word sleep))
(rule (Verb/intr 3sg  ?x (sleep ?x)) --> (:word sleeps))
(rule (Verb/intr ?any ?x (sleep ?x)) --> (:word slept))

(rule (Verb/intr 3sg  ?x (sells ?x)) --> (:word sells))
(rule (Verb/intr 3sg  ?x (stinks ?x)) --> (:word stinks))

(rule (VP ?agr ?x ?vp) -->
  (Verb/tr ?agr ?x ?obj ?verb)
  (NP ?any-agr ?obj ?verb ?vp))

(rule (VP ?agr ?x ?vp) -->
  (Verb/intr ?agr ?x ?vp))

(rule (S ?np) -->
  (NP ?agr ?x ?vp ?np)
  (VP ?agr ?x ?vp))

Preserving Quantifier Scope

Instead of deciding arbitrarily which interpretation/scoping to give to a quantified sentence, produce a compact representation of the multiple interpretations without committing to one. Then another module will choose the appropriate scoping.

- "Every man loves a woman."
(all ?m (-> (man ?m) (exists ?w) (and (woman ?w) (loves ?m ?w))))
(exists ?w (and (woman ?w) (all ?m (-> (man ?m) (loves ?m ?w)))))
What should be a good representation for the 2 possible readings?

(and (all ?m (man ?m))
     (exists ?w (woman ?w))
     (loves ?m ?w))

- Example of grammar:

(rule (S (and ?np ?vp)) -->
  (NP ?agr ?x ?np)
  (VP ?agr ?x ?vp))

(rule (VP ?agr ?x (and ?verb ?obj)) -->
  (Verb/tr ?agr ?x ?o ?verb)
  (NP ?any-agr ?o ?obj))

(rule (VP ?agr ?x ?verb) -->
  (Verb/intr ?agr ?x ?verb))

(rule (NP ?agr ?name t) -->
  (Name ?agr ?name))

(rule (NP ?agr ?x ?det) -->
  (Det ?agr ?x (and ?noun ?rel) ?det)
  (Noun ?agr ?x ?noun)
  (rel-clause ?agr ?x ?rel))

(rule (rel-clause ?agr ?x t) --> )
(rule (rel-clause ?agr ?x ?rel) -->
  (:word that)
  (VP ?agr ?x ?rel))

(rule (Name 3sg Terry)                     --> (:word Terry))
(rule (Name 3sg Jean)                      --> (:word Jean))
(rule (Det 3sg  ?x ?restr (all ?x ?restr)) --> (:word every))
(rule (Noun 3sg ?x (man ?x))               --> (:word man))
(rule (Verb/tr 3sg ?x ?y (love ?x ?y))     --> (:word loves))
(rule (Verb/intr 3sg ?x (lives ?x))        --> (:word lives))
(rule (Det 3sg  ?x ?res (exists ?x ?res))  --> (:word a))
(rule (Noun 3sg ?x (woman ?x))             --> (:word woman))

Example of output:

(and (all ?4 (and (man ?4) t))
     (and (love ?4 ?12) (exists ?12 (and (woman ?12) t))))

Need to reprocess to remove t and simplify ands.

For any question, contact me: yaeln@cs.bgu.ac.il
Back to course homepage

Last modified March 26, 2000