Transcript CS 8520: Artificial Intelligence

CS 9010: Semantic Web
Inference and Rules
Paula Matuszek
Spring, 2006
CSC 9010 Spring, 2006. Paula Matuszek
1
Beyond Ontologies
• With ontologies we can represent a lot of
knowledge about the world:
–
–
–
–
Classes of objects
Instances of those classes
Properties of those classes, including
Relationships among those classes:
• Subclass (often called a specialization hierarchy)
• Components (often called an aggregation hierarchy)
• Any other binary relationships we care to define
• Is this enough?
CSC 9010 Spring, 2006. Paula Matuszek
2
The Restaurant Recommender
• Consider what happens when a friend says
to you "We're trying to decide where to go
for dinner tomorrow; any ideas?"
CSC 9010 Spring, 2006. Paula Matuszek
3
Relevant Ontologies
• There is a LOT of information available
online about restaurants. Consider, for
instance, zagat.com. If this were a semantic
web page, what might the ontology include?
CSC 9010 Spring, 2006. Paula Matuszek
4
CSC 9010 Spring, 2006. Paula Matuszek
5
Restaurant Ontology for Zagat:
Classes
• Cuisine
–
–
–
–
Afghan
African
American
…
• Neighborhood
– Abington
– Ambler
– …
• Feature
– All you can eat
– Boat Docking Facilities
– …
CSC 9010 Spring, 2006. Paula Matuszek
Properties described
• Décor
• Price
• Ratings
• Address
• Reservations?
• Parking?
• Dress
• Liquor license
6
What’s missing?
• This gives a lot of information, but it’s
generally not what mostly went into where
your friend should eat tomorrow. What else
was there?
CSC 9010 Spring, 2006. Paula Matuszek
7
Other Possibly Relevant Facts
• These could all be expressed fairly readily in a
description logic, with a little bit of creativity in
what we consider an “object”.
–
–
–
–
–
–
–
Tomorrow is Valentine's Day.
Going to a nice restaurant is a special thing.
Restaurants have limited capacities.
Your friend hates waiting.
Your friend doesn't like Italian food.
Your friend lives in Cherry Hill
Your friend works in King of Prussia.
• Mostly not a restaurant ontology, but an ontology.
CSC 9010 Spring, 2006. Paula Matuszek
8
Now Is That All?
• How about:
– Couples do special things on Valentine's Day.
– If a restaurant serves mixed drinks it's a nice
restaurant.
– If the average cost of a meal for two people at a
restaurant is >$50, it’s a nice restaurant.
– If a site has a limited capacity and many people
go there, it will be crowded.
– Going to a crowded restaurant involves either
making a reservation or waiting a long time.
CSC 9010 Spring, 2006. Paula Matuszek
9
We Need Rules!
• These are all general pieces of knowledge
about eating at restaurants and about people,
but they are hard to capture in the
framework of a classes/properties structure.
• Several kinds here:
– Rules that allow us to infer properties:
• Nice restaurant
– Rules that give information about situations
• Waiting time, couples on Valentine’s Day
CSC 9010 Spring, 2006. Paula Matuszek
10
But Wait, There’s More!
• Now we have knowledge about restaurants
and about your friend, but there’s also
knowledge about making recommendations,
meta-knowledge about our process here
– Recommend restaurants that don't involve too
much travel.
– Recommend restaurants that are new or have
recently changed ownership/chef/style.
– Recommend restaurants that your friend might
not have thought of.
– Recommend restaurants that you like.
CSC 9010 Spring, 2006. Paula Matuszek
11
So Where Are We?
• Our recommender clearly has several
components:
– Gather information about restaurants. Ideally
we have a nicely tagged site where we can
simply find it based on our restaurant ontology.
– Gather information about the individual’s
preferences, based on another ontology.
– Consult a generic “common sense” ontology for
date-related information such as Feb 14 =
Valentine’s Day.
CSC 9010 Spring, 2006. Paula Matuszek
12
And Then Magic Happens?
• And then what actually happens is inference.
– If it’s Valentine’s Day, then couples will do special
things.
– If couples do special things, then they will go to nice
restaurants.
– If couples go to nice restaurants, then the restaurants
will be crowded.
– If a restaurant is crowded and it does not take
reservations, the wait will be long.
– If a restaurant is crowded and it does take reservations,
the wait will not be long.
– My friend should go to a nice restaurant which takes
reservations or should not go to a nice restaurant.
CSC 9010 Spring, 2006. Paula Matuszek
13
Rule-Based Systems (RBS)
• The knowledge we have been using can be captured in
rules.
• Rules in knowledge representation have a typical form of
– IF left-hand-side or LHS or Premises or Body
– THEN right-hand-side or RHS or Head
• The LHS has a condition or set of conditions to be met
• The RHS is the action to be taken if those conditions are
met.
• In a subset of RBS the RHS is always an additional fact to
be asserted. These are known as deductive systems; the
rule can be interpreted as “if the LHS is true, so is the
RHS.” (This is the subset mostly discussed in the text.)
CSC 9010 Spring, 2006. Paula Matuszek
14
Messy, Messy
• What we are doing here is forward chaining: working forward
from existing facts to new things we can assert until we get to the
one we want.
• If we have many rules with similar LHS conditions, this is very
inefficient.
–
–
–
–
–
–
–
If couples go to nice restaurants then they will spend a lot of money
If couples go to NRs then they will be well-dressed.
If couples go to NRs then they will spend at least two hours.
If couples go to NRs then they will have a good time.
If couples go to restaurants then they will eat.
If couples go to restaurants then they will spend money.
…
• Also known as data-driven inference
CSC 9010 Spring, 2006. Paula Matuszek
15
Start at the End
• Suppose we start at the other end?
• My friend doesn’t like waiting
– Restaurant takes reservations or isn’t “nice”
• Restaurant takes reservations.
• This allows us to ignore all the things we know about eating at
nice restaurants except the one that affects our current
problem.
• This is backward chaining: We maintain a tree of possibilities
until we can ground out a reasoning chain at a fact.
• Also known as goal-driven inference
• If there is more than one way to get to a conclusion (meaning
usually that more than one rule has the same RHS) then we
may do a lot of backtracking and it’s just as messy.
CSC 9010 Spring, 2006. Paula Matuszek
16
Efficiency, Please
• We can view our restaurant
recommendation as an attempt to prove that
a specific restaurant is a good
recommendation.
• Much of the work in both defining OWL
and defining rule languages which can sit
on top of OWL has been focused on
supporting efficient proof system
• Description Logics have (Owl DL and OWL
Lite) have efficient proof systems.
CSC 9010 Spring, 2006. Paula Matuszek
17
Horn Logic
• Another subset of predicate logic with an efficient
proof system is Horn Logic
• In a Horn system
– The LHS is a series of facts connected by AND
– The RHS is a single fact.
• You cannot say, for instance, that
– If Person(X) Then Man(X) OR Woman(X)
• With this restriction we can do inference using a
very efficient procedure called resolution.
• The basic idea of resolution is assert the negative
of the RHS and try to derive a contradiction to
what we know is true. If we can find one then the
RHS must be true.
CSC 9010 Spring, 2006. Paula Matuszek
18
Rules and Reality
• Predicate Logic as a knowledge representation makes
some assumptions:
– The fact base (the collection of things we know to be true) is
monotonic.
• Once something is asserted to be true it remains true. We never retract
something.
• Once something is asserted to be true we cannot assert its
contradiction. We can’t have both A and Not(A) in the fact base.
– Everything is either true or not true. We don’t have a maybe.
– We also don’t have an unknown. If we can’t prove it true, it’s
false. This is known as the closed world assumption, and it
gives us negation by failure.
CSC 9010 Spring, 2006. Paula Matuszek
19
Monotonic Reasoning
• Consider the rule: If the date is Feb 14 and a
restaurant is expensive, then it is a suitable
restaurant.
– Date(Feb 14), RestaurantCost (X) >$50  Suitable(X).
• Rules have several ingredients:
–
–
–
–
Variables are placeholders for values: X
Constants denote fixed values: $50
Predicates relate objects: RestaurantCost
Function symbols return a value for certain arguments:
date.
CSC 9010 Spring, 2006. Paula Matuszek
20
Monotonic Rules 2
Date(Feb 14), RestaurantCost (X) >$50 
Suitable(X).
• LHS has the form B1, … Bn  A, where
– B1 – Bn and A are atomic formulas
– The commas are conjunctions: ANDs
• The rule applies to any instance which can
match to X: it is implicitly universally
quantified (ie, we assume for all X)
CSC 9010 Spring, 2006. Paula Matuszek
21
Rules Syntax 3
• Facts are atomic formulas with no variables.
RestaurantCost(McDonald’s, $5) is a fact.
• Goals: what we are trying to make true or
find out. Typically phrased as a query which
we want to prove to be true.
– Suitable(McDonald’s): Prove that McDonald’s
is a suitable restaurant (or that it isn’t)
– Suitable(X). Prove that there exists a suitable
restaurant. More usefully, instantiate X to a
suitable restaurant (and tell us what it is!)
CSC 9010 Spring, 2006. Paula Matuszek
22
Inference in a Monotonic System
• Our inference engine will use a proof system (forwardchaining, backward-chaining, resolution…) to
– Try possible instantiations of variables in the LHS based on
what instances are in the knowledge base
– Apply any relevant rules in the knowledge base
– Assert additional facts with those instantiated variables
• Until
– We find an instantiation that allows us to prove our goal
or
– We try all possible combinations of instantiations and fail.
CSC 9010 Spring, 2006. Paula Matuszek
23
Why Logic?
• Advantages of Logic as a knowledge
representation include
– High expressive power, well-known
– Well-understood formal semantics
– Proof systems exist for deriving sound and complete
conclusions. Some are even efficient.
• Disadvantages include
– The restrictions it imposes are hard to handle in the real
world
– While it’s well known and well-understood by
logicians, it’s not a very natural representation for most
human experts.
CSC 9010 Spring, 2006. Paula Matuszek
24
Other Rule Formulations
• There are a variety of other rule formulations
which are less restrictive then predicate logic.
• Pattern is still
– If LHS Then RHS.
• LHS may be clauses connected by OR instead of
AND, may include tests or actions which interact
with the environment instead of the fact base
• RHS may include actions which interact with the
environment and may also include retractions as
well as assertions.
• Generically called production systems or just rulebased systems.
CSC 9010 Spring, 2006. Paula Matuszek
25
Non-Monotonic Rules
• We said that in predicate logic the knowledge base
is monotonic.
– Once something is asserted to be true it remains true.
We never retract something.
– Once something is asserted to be true we cannot assert
its contradiction. We can’t have both A and Not(A) in
the knowledge base.
• So there are two ways to have a non-monotonic
system:
– Allow retractions
– Allow contradictory rules in the same knowledge base.
CSC 9010 Spring, 2006. Paula Matuszek
26
Non-Monotonic Inference: Retractions
• In a non-monotonic system a rule may retract a fact. Why?
– Things change over the course of our inference.
• Restaurant has a special Valentine’s Day Reservations Only policy
– Default reasoning
• Your friend is going out with coworkers
• This introduces a number of complications:
– For a reasoning chain ABC if we assert A, then we can conclude B
and then C. If we then retract A, we no longer have support for B or C.
Handling this general situation is called truth maintenance.
– In a monotonic system, the order in which we apply rules can’t affect the
outcome, only the efficiency. This is not true in a non-monotonic
system; therefore the choice of which applicable rule to use becomes
important. This is the issue of conflict resolution. It can be resolved by a
general CR strategy (depth first, breadth first, most complex first…) or
by explicit rule weights.
CSC 9010 Spring, 2006. Paula Matuszek
27
Non-Monotonic Rules: Contradictions
• We can also get non-monotonicity because we allow
contradictory rules in the same knowledge base.
– If a restaurant is >$50, don’t recommend it to students.
– If a restaurant is >$50, recommend it on special occasions.
• Often the contradiction is indirect, with two different paths of
inference leading to contradictory conclusions.
• Can be very difficult to spot as you develop rules!
• Often indicates insufficiently well-defined rules, such as missing
conditions.
– If RestCost(X) > $50, CanAfford(Y, X) recommend(X).
• Also a conflict resolution issue.
– Find a difference inference chain without contradiction
– Priorities on rules
CSC 9010 Spring, 2006. Paula Matuszek
28
KB vs Inference
• There is a distinction in Rule-Based Systems
between the knowledge being captured, or the
knowledge base (KB), and the process of using
those rules, or inference. The program which
implements the latter is called an inference engine.
• Difference inference engines can be used over the
same KB, and different KBs can be used with the
same inference engine.
• Not all inference engines can be used with all KB
formats; an engine that assumes monotonicity
cannot be use with a KB which includes
retractions, for instance.
CSC 9010 Spring, 2006. Paula Matuszek
29
Some Well-Known (and Available) Inference Engines
• CLIPS: Forward-chaining rule system originally
developed for NASA, implemented in C. CLIPS supports
non-monotonic rules, but assumes negation-by-failure. It
uses an inference engine based on the Rete algorithm.
JESS: Reimplementation of CLIPS in Java. Over the
years it has acquired quite a few extensions over CLIPS.
• Prolog: a logic programming language; backward
chaining, based on resolution as an inference engine,
supports non-monotonic rules, also assumes negation-byfailure.
• There are plugins for all of these for Protégé. More
inference plugins can be found at the Protégé wiki’s library
of plugins by topic.
CSC 9010 Spring, 2006. Paula Matuszek
30
RuleML
• RuleML is an initiative to standardize rules for the
semantic web
• Would allow inference about web pages to be
shared just as content is
• Based on XML and RDF
– XML format and emphasis on order of elements
– RDF-like role tags in which order is irrelevant
• Includes support for non-monotonic rules which
have a priority tag, such as <stronger>
• There’s a protégé plugin for converting
taxonomies into ruleML.
CSC 9010 Spring, 2006. Paula Matuszek
31
Backup Slides
CSC 9010 Spring, 2006. Paula Matuszek
32
Rules Syntax in Predicate Logic
• Consider the rule: If the date is Feb 14 and a
restaurant is expensive, then it is a suitable
restaurant.
– Date(Feb 14), RestaurantCost (X) >$50  Suitable(X).
• Rules have several ingredients:
–
–
–
–
Variables are placeholders for values: X
Constants denote fixed values: $50
Predicates relate objects: RestaurantCost
Function symbols return a value for certain arguments:
date.
CSC 9010 Spring, 2006. Paula Matuszek
33
Rule Syntax 2
Date(Feb 14), RestaurantCost (X) >$50 
Suitable(X).
• LHS has the form B1, … Bn  A, where
– B1 – Bn and A are atomic formulas
– The commas are conjunctions: ANDs
• The rule applies to any instance which can
match to X: it is implicitly universally
quantified (ie, we assume for all X)
CSC 9010 Spring, 2006. Paula Matuszek
34
Rules Syntax 3
• Facts are atomic formulas with no variables.
RestaurantCost(McDonald’s, $5) is a fact.
• Logic Programs are finite sets of facts and
rules. If P is a set of facts and rules, pl(P) is
the set of all predicate logic interpretations
of these rules.
• Goals: what we are trying to make true or
find out. Typically phrased as a query which
we want to prove to be true.
CSC 9010 Spring, 2006. Paula Matuszek
35
Predicate Rules Semantics
• Domain: non-empty set of objects about
which to make statements
• Elements of domain
• Concrete function on domain for every
domain symbol
• Concrete relation on domain for every
predicate
• Ground and parameterized witnesses
CSC 9010 Spring, 2006. Paula Matuszek
36