Introduction to AI - Week 7

Natural Language Understanding - Parsing

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.)

Lexicon

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

• The effective dosage varies considerably. [Hodges, p.78]

Example of Parsing (Cont'd)

• The effective dosage varies considerably. [Hodges, p.78]

Example of Parsing (Cont'd)

• The effective dosage varies considerably. [Hodges, p.78]

Example of Parsing (Cont'd)

• The effective dosage varies considerably. [Hodges, p.78]

Natural Language Understanding - Parsing

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

Parse the Following Sentence

• The man must be rich or young and good-looking. [Hodges, p.78]

Parse the Following Sentence (Cont'd)

Parse the Following Sentence (Cont'd)

Semantics

1. Parsing

Semantics (Cont'd)

2. Semantic Interpretation

Semantics (Cont'd)

Semantics (Cont'd)

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

• Understanding
• Question answering
• Summarisation
• Translation to other languages

Pragmatics

Assume a system that should automatically perform hotel bookings.

• Costumer: Is the double room for £ 22 available on 9 November?
• Computer: No.

• Computer: No, but I can offer you our suite, which is normally £ 50 for only £ 25 on 9 November. It's a real treat and unbeatably competitive.

Natural Language Understanding
Syntax, Semantics, Pragmatics

• Syntactic analysis: "Boy the go the to store." rejected as syntactically incorrect.
• Semantic analysis: "Colourless green ideas sleep furiously." rejected as semantically anomalous.
• Pragmatic analysis: "Do you know the time?", answer: "Yes, I do." pragmatically incorrect, since it disregards the intension of the request.

Knowledge Representation
in First-Order Logic

Examples:

(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)]

Read:

logic	|	&	->	~	FORALL	EXISTS
--------	-------------	-------------
nat. lang.	or	and	implies	not	forall	exists

Properties of First-Order Logic:

• very expressive as well as unambiguous syntax and semantics
• no generally efficient procedure for processing knowledge

How to translate?

• Sam is a tall man.
  man(sam)  &  tall(sam)
• Every human is mortal.
  FORALL  x. human(x) -> mortal(x)
• Some girl is happy.
  EXISTS  x. girl(x) & happy(x)

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

Encode

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

Examples

• If Sam loves everybody then Sam loves himself.
  (FORALL  x. Loves(sam,x)) -> Loves(sam,sam)
• If God was not created by anything then it is false that God created everything. (~EXISTS  x.  Created(x, god))  ->  (~FORALL  y.  Created( god,y))

• If only doctors or hospital administrators are eligible and Mrs Miller is eligible then Mrs Miller is a doctor or a hospital administrator.

  (	(FORALL  x.  Eligible(x)  ->  Doc(x) |  Admin(x)))  &  Eligible( MrsMiller))
  ->	( Doctor( MrsMiller) |  Admin( MrsMiller))

Example (Cont'd)

• You may fool all the people some of the time; you can even fool some of the people all the time; but you can't fool all of the people all the time. [Abraham Lincoln] Use P(x) standing for "x is a person", T(y) for "y is a moment of time", and Fool(x,y) for "x can be fooled at y."

(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)

• There are times when you may fool all the people.
  EXISTS  y.  T(y) &  (FORALL  x.  P(x) ->  Fool(x,y))
• You may fool any person some of the time.
  FORALL  x.  P(x) -> (EXISTS  y.  T(y) &  Fool(x,y))

Problem

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

• Thinking always begins with suggestive but imperfect plans and images; these are progressively replaced by better - but usually still imperfect - ideas. (Minsky)

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

• Typically birds can fly.
• Typically humans have two legs.
• The typical height of an adult male is 180cm.
• The typical maximal temperature of a November day is 12 ^oC.

Defaults

• Typically elephants are grey.
• Clyde is an elephant.
• Clyde is white. I.e., Clyde is an exception with respect to colour, but inherits the other properties of elephants.

Defaults (Cont'd)

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

The net can be read:

• Typically elephants are grey.
• Clyde is an elephant.
• Clyde is white.

Multiple Inheritance

Assume knowledge:

• Nixon is a Quaker.
• Quakers are typically pacifists.
• Nixon is a Republican.
• Republicans are typically not pacifists.

Non-monotonic Reasoning

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)

Thus

Non-monotonic Reasoning (Cont'd)

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.

Example

What follows?

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

How to formalise?

Formalisation

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)
good_student(david)
party_person(david)

Summary

• Natural Language:
  • Very powerful representation formalism.
  • Ambiguity in representation.
  • Difficult to parse.
  • Difficult to find semantics.
  • Pragmatics important in application.

• Logic:
  • Clear syntax and semantics.
  • Easy to parse.
  • Restricted expressive power (e.g., no defaults).
  • No account of pragmatics.

Summary (Cont'd)

• Semantic Nets/Defaults:
  • Structured Representation.
  • Semantic status may be unclear.
  • Efficient reasoning possible (depending on exact format).
  • Default values and non-monotonic reasoning.

There is no single best knowledge representation formalism.