Introduction to AI - Week 7

Representation II

Natural Language Understanding - Parsing

Sentences are parsed according to rules, which form a grammar. A simple subset of English grammar is:
  1. S-> NP VP
    (A sentence is a noun phrase followed by a verb phrase.)
  2. NP-> N
    (A noun phrase is a noun.)
  3. NP-> DET N
    (A noun phrase is a determiner (article) followed by a noun.)
  4. VP-> V
    (A verb phrase is a verb.)
  5. VP-> V NP
    (A verb phrase is a verb followed by a noun phrase.)
  6. PP-> PROP NP
    (A propositional phrase is a proposition followed by a noun phrase.)


In addition to the grammatical rules, we need a lexicon which contains the terminal symbols for our grammar. A small subset is:
  1. DET-> a
    ("a" is a determiner.)
  2. DET-> the
    ("the" is a determiner.)
  3. N-> man
    ("man" is a noun.)
  4. N-> woman
    ("woman" is a noun.)
  5. V-> saw
    ("saw" is a verb.)

Example of Parsing

Example of Parsing (Cont'd)

Example of Parsing (Cont'd)

Example of Parsing (Cont'd)

Natural Language Understanding - Parsing

Meaning depends on parsing:
John saw the boy in the park with a telescope
-------- ------------- -------------

John saw the boy in the park with a dog

  John saw the boy in the park with a statue
-------- ------------- -------------

Parse the Following Sentence

Find two reading and focus on the main difference.

Parse the Following Sentence (Cont'd)

Parse the Following Sentence (Cont'd)


Tarzan kissed Jane

1. Parsing

Semantics (Cont'd)

Tarzan kissed Jane

2. Semantic Interpretation

Semantics (Cont'd)

3. Contextual/world knowledge interpretation

Semantics (Cont'd)

The semantic analysis of a piece of text is essential for a good performance with various tasks such as:


Pragmatics is the study of ways in which language is used and its effects on the listener.

Assume a system that should automatically perform hotel bookings.

The answer "No" is syntactically and (let's assume so) semantically correct, but does not fulfil the intention the computer should have, namely to sell. A better answer would be

Natural Language Understanding
Syntax, Semantics, Pragmatics


Knowledge Representation
in First-Order Logic

 (a) man(Pat)  (d) man(Jan)  |  woman(Jan)
 (b) married(Pat,Jan)  (e) FORALL  x. EXISTS  y. [person(x) ->  has_mother(x,y)]
 (c) FORALL  x. FORALL  y. [[married(x,y) &  man(x)] -> ~ man(y)]
 logic   |    &    ->   ~  FORALL  EXISTS
-------- ------------- -------------
 nat. lang.  or  and  implies  not  forall  exists

Properties of First-Order Logic:

raining  ->  street_wet
-------- ------------- -------------

raining  ->  street_wet
-------- ------------- -------------

How to translate?

Larger sentences are parsed and decomposed into smaller parts which can be translated piecewise.


If the Millennium Dome is at least as high as the Royal Albert Hall, then every concert hall which is at least as high as the Millennium Dome is at least as high as the Royal Albert Hall.

 Higher(Millenium-Dome,Royal-Albert-Hall) -> 
  (FORALL  x. (  (Concert-Hall(x) & Higher(x,Millenium-Dome))
    -> Higher(x,Royal-Albert-Hall)))


Translate to first-order logic:

Example (Cont'd)

Translate to first-order logic:

(EXISTS  y.  T(y) &  (FORALL  x.  P(x) ->  Fool(x,y))) & 
(EXISTS  x.  P(x) &  (FORALL  y.  T(y) ->  Fool(x,y))) & 
(~(FORALL  x.  P(x) ->  (FORALL  y.  T(y) ->  Fool(x,y))))

Example (Cont'd)

Note there is an ambiguity in the sentence:
You may fool all the people some of the time.
There are two possible ways to interpret it:


How to formalise Mickey is a big mouse?
mouse(mickey) &  big(mickey)

How to formalise Jumbo is a little elephant?
elephant(jumbo) &  little(jumbo)

BUT: A big mouse is smaller than a little elephant.
More sophisticated representation necessary.

Default Values

Use default value when no concrete information is available
default value = typical value (not average value)


Slots can be overridden, hence they can be taken to represent properties that follow only typically.

The net above can be read:

Defaults (Cont'd)

Slots can be overridden, hence they can be taken to represent properties that follow typically only.

The net can be read:

What should be derivable?

Multiple Inheritance

Nixon Diamond

Assume knowledge:

What to conclude?
* "Nixon is a pacifist." or
* "Nixon is not a pacifist."?

Non-monotonic Reasoning

In the light of default values a fundamental property of standard logic does not hold any more, monotonicity.

Monotonicity means: If a statement A can be concluded from a set of facts set, then A can also be concluded from any larger set which contains set as a subset.

(Formally: set |= A then set union  set' |= A.)

This is no longer the case for defaults.

Non-monotonic Reasoning (Cont'd)

Assume knowledge:
 FORALL  x.  Bird(x) ->  Can_Fly(x)
-------- ------------- -------------
This is not correct, however. If we learn in addition that Tweety is a penguin, we don't want to conclude any longer that Tweety can fly.


 FORALL  x.  Bird(x) unless abnormal Bird(x) ->  Can_Fly(x)
-------- ------------- -------------
is a better form of reasoning (default reasoning).
We would also have FORALL  x. Penguin(x) ->  abnormal Bird(x)
With the additional knowledge Penguin(Tweety) it is not possible to derive Can_Fly(Tweety) any more.

Non-monotonic Reasoning (Cont'd)

 FORALL  x.  P(x) unless abnormal P(x) ->  Q(x)
 abnormal P(c) cannot be derived
-------- ------------- -------------

Question: How to derive that P(c) is not abnormal.
Use negation as failure as in Prolog, that is, in the example, if it is not possible to derive that Tweety is a penguin, then assume that it is not a penguin, then assume that Tweety is a "normal" bird, then conclude that Tweety can fly.


Represent: "A good student of whom nothing is known to the contrary will study hard. A party person of whom nothing else is known to the contrary will not study hard. A good student who studies hard will graduate. David is a good student."

What follows?

What follows, when we learn in addition:
"David is a party person."

How to formalise?


FORALL  x.  good_student(x) &  unless abnormal study_hard(x) ->  graduates(x)
FORALL  y.  party_person(y) &  unless abnormal not study_hard(x) ->  not graduates(x)


Summary (Cont'd)

There is no single best knowledge representation formalism.

© Manfred Kerber, 2004, Introduction to AI
The URL of this page is
URL of module