SWRules

CS 9010: Semantic Web: 

CS 9010: Semantic Web Inference and Rules Paula Matuszek Spring, 2006

Beyond Ontologies: 

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?

The Restaurant Recommender: 

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?"

Relevant Ontologies: 

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?

Restaurant Ontology for Zagat:: 

Restaurant Ontology for Zagat: Classes Cuisine Afghan African American … Neighborhood Abington Ambler … Feature All you can eat Boat Docking Facilities … Properties described Décor Price Ratings Address Reservations? Parking? Dress Liquor license

What’s missing?: 

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?

Other Possibly Relevant Facts: 

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.

Now Is That All?: 

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.

We Need Rules!: 

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

But Wait, There’s More!: 

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.

So Where Are We?: 

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.

And Then Magic Happens?: 

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.

Rule-Based Systems (RBS): 

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

Messy, Messy: 

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

Start at the End: 

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.

Efficiency, Please: 

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.

Horn Logic: 

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.

Rules and Reality: 

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.

Monotonic Reasoning: 

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.

Monotonic Rules 2: 

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)

Rules Syntax 3: 

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

Inference in a Monotonic System: 

Inference in a Monotonic System Our inference engine will use a proof system (forward-chaining, 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.

Why Logic?: 

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.

Other Rule Formulations: 

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 rule-based systems.

Non-Monotonic Rules: 

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.

Non-Monotonic Inference: Retractions: 

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.

Non-Monotonic Rules: Contradictions: 

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

KB vs Inference: 

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.

Some Well-Known (and Available) Inference Engines: 

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-by-failure. 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.

RuleML: 

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.

Backup Slides: 

Backup Slides

Rules Syntax in Predicate Logic: 

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.

Rule Syntax 2: 

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)

Rules Syntax 3: 

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.

Predicate Rules Semantics: 

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