Intelligent Systems Lecture Notes

21 September 2011 • Knowledge Bases

---

Outline

• Propositional definite clauses.
  • Atoms and rules.
• Knowledge representation.
  • Knowledge bases, local and global semantics.

Where Should I Go?

Should I Make That Loan?

How Should I Decide?

Remember This?

what color is(x)
  if is color(x, y) return y

what color is(x)
  if is made of(x, y) and is color(y, z)
    return z

what color is(x)
  return "don't know"

is color("snow", "white")
is made of("grass", "vegetation")
is color("vegetation", "green")

what color is("snow") → "white"
what color is("grass") → "green"
what color is ("mud") → "don't know"

Propositional Definite Clauses

• A propositional definite clause (PDC) is a sentence of the form

  atom [ \(\leftarrow\) atom ( \(\wedge\) atom)* ]

• An propositional atom is a lower-case variable in various forms.

  snowIsWhite
  snow-is-white
  snow_is_white
  snowiswhite
  a b c

PDC Examples

• PDC: atom [ \(\leftarrow\) atom ( \(\wedge\) atom)* ]

  snowiswhite
  grassisvegetation
  dogissmelly \(\leftarrow\) dogiswet
  a \(\leftarrow\) b \(\wedge\) c \(\wedge\) d

• \(\leftarrow\) is pronounced “when”; \(\wedge\) is pronounced “and” (sometimes “conjunct”).

  a \(\leftarrow\) b \(\wedge\) c: “a when b and c”
  dogissmelly \(\leftarrow\) dogiswet: “dog is smelly when dog is wet”

Clause Observations

• Various forms of “proposition” will be dropped unless needed.
• A definite clause with an ← in it is a rule.

  

• The atom to the left of ← is the head.
• The expression to the right of ← is the body.

Knowledge Bases

• A propositional knowledge base (KB) is a definite-clause set.

  snowiswhite
  skyisblue
  grassisvegetation
  vegetationisgreen
  grassisgreen \(\leftarrow\)
     grassisvegetation \(\wedge\) vegetationisgreen

• Conventionally, atoms appear before clauses.

Knowledge-Base Semantics

• What does the previous knowledge-base example mean? How is it interpreted?
• Answering these questions requires defining the knowledge-base semantics.
• Knowledge-base semantics has two parts:
  1. A local semantics describing the knowledge base itself.
  2. A global semantics connecting a knowledge base to the world.

Semantic Observations

• Local semantics applies uniformly to any knowledge base.
  • The same local semantics applies to any knowledge base.
  • Local semantics is independent of global semantics.
• Each global semantics applies to individual knowledge bases.
  • A knowledge base may have many global semantics, or none.

Local Atom Semantics

• An atom in a knowledge base is a boolean value.
  • snowiswhite is either true or false.
• An atom’s actual value is not defined by the local semantics.
  • That’s the job of the global semantics.
• Once set, an atom’s value is fixed (it’s constant).

Local Clause Semantics

• A rule in a knowledge base is a boolean value.
• A rule’s value is determined by its head and body values.

  a \(\leftarrow\) b t t t t t f f f t f t f

  a ∧ b t t t t f f f f t f f f

Rule Observations

a ← b t t t t t f f f t f t f

A false body doesn’t imply anything about the head. If the dog’s not wet, it may or may not smell.

• A rule’s false only when a true body implies a false head.
  • If a dog’s wet, but it doesn’t smell, then what’s the point?

Local Semantics Observations

• There is no implied relation between definite clauses in a knowledge base.
• A knowledge base has no value, boolean or otherwise.
  • A knowledge base cannot be true or false.,
  • It may, however, have subjective value measures relative to the world.

Global Semantics

• Global semantics connects a knowledge base with the world.
  • Or it explains how a KB connects with the world.
• The global semantics has two jobs:
  1. Assign values to atoms in the knowledge base.
  2. Determine the atoms’ meaning.

Interpretation

• An interpretation \(I\) is a mapping assigning boolean values to atoms.

  \(I\): {	snowiswhite	:	true
  	skyisblue	:	false
  	grassisvegetation	:	true
  	vegetationisgreen	:	true }

  \(I\): {	snowiswhite	:	true
  	grassisvegetation	:	true
  	vegetationisgreen	:	true }

  \(I\): {	snowiswhite, grassisvegetation,
  	vegetationisgreen }

Interpretation Observations

• It is helpful to think of unassigned atoms as being undefined rather than false.
  • Although false is the usual interpretation.
• It isn't necessary to assign values to all atoms in a knowledge base.
• There are other mechanisms by which atoms are assigned values.
  • The result, however, will be a modified interpretation.

Meaning and Atoms

• Computers don't need to know what atoms mean.
  • Although it would be nice.
• Humans do need to know.
  • Understand the knowledge base world model.
  • Setting up sensible interpretations.
  • Understand the answers and reasoning behind the answers.

Establishing Meaning

• The atoms’ meaning is established informally, or semiformally.
  • A reader's knowledge of the world modeled and the atoms used.
  • Documentation provided with the knowledge base.
• An ontology is a formal attempt to establish meaning.
  • It's early days for ontologies.

Knowledge-Base Models

• A knowledge base models a piece of the world, known as the domain.
  • The domain doesn't have to be real.
• Atoms represent states in the domain.

  snowiswhite
  grassisvegetation
  

• Rules represent relations between atoms.

  grassisgreen \(\leftarrow\)
     grassisvegetation \(\wedge\) vegetationisgreen

Tic-Tac-Toe KB Model

xincell00 xincell01 \(\vdots\) xincell21 xincell22	oincell00 oincell01 \(\vdots\) oincell21 oincell22
xwins \(\leftarrow\)   xincell00 \(\wedge\) xincell01 \(\wedge\) xincell02 xwins \(\leftarrow\)   xincell00 \(\wedge\) xincell10 \(\wedge\) xincell20 \(\vdots\)

Tic-Tac-Toe Interpretation Example

• \(I\): { xincell10, oincell21 }

Summary

• A definite clause knowledge base models a domain.
  • Atoms are states; rules are relations.
• An interpretation for a knowledge base assigns values to atoms.

References

• The Language of First-Order Logic (Chapter 2) and Expressing Knowledge (Chapter 3) of Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque from Morgan Kaufmann, 2004.
• From Logic-Based Chaining to Production Systems (Chapter 6) in Intelligent Systems by Robert Schalkoff from Jones and Bartlett, 2011.

Credits

• Consumer Decision Making Process (Kotler) by Peter Morville under a Creative Commons BY NC license.
• Risks to creditor confidence and mitigating balance sheet characteristics by Bank of England under a Creative Commons BY ND license.
• Management Decision Making Tool by Ron Bieber under a Creative Commons BY NC ND license.

---

This page last modified on 2011 September 15.