Logical Aspects of Inference

We’ll be talking about Inference in Cyc.  Inference is the mechanism we use to conclude new facts from other existing facts and rules in the system.  We’ll be talking about it in four sections and the first section will be about the logical aspects of inference.

Inference uses Deduction: Rules

  “Rules” are very general statements in a formal logical language, such as this formula, under “Rules,” which essentially says that everyone loves their mother. If ?MOTHER is the mother of some ?PERSON, then that ?PERSON loves that ?MOTHER.  It’s a conditional statement.  It’s general -- it doesn’t apply to one specific thing and it quantifies over objects in the world.  As such it usually has variables (i.e. “?PERSON”) in it and there are usually multiple literals, or statements, that are connected together by logical connectives (i.e. “implies”).

Rules tend to be the complicated logical statements.  The other statements in the system can be colloquially described as “facts.”

Inference uses Deduction: Facts

  “Facts” tend to be about some very specific thing in the world -- unlike rules which are general.  They tend to be ground, meaning that they don’t have any variables in them, because they’re talking about some specific case, they’re not quantifying over the world.

Facts are also atomic, which has to do with it being a single statement, like “the mother of Hamlet is Gertrude.”  It is the application of a predicate, #$mother, to arguments, #$Hamlet and #$Gertrude.  So the rule from the previous slide would not be atomic because there are two literals connected together by a logical connective to say that if this (a person has a mother) were the case, then this (a person loves their mother) would be the case.  So something is “atomic” if there is no conditional aspect to it, if it’s just a single statement.

“Facts” are more formally called ground atomic formulas because they are formulas that are both ground and atomic.

Inference uses Deduction: Non-atomic terms, Predicates, and Functions

A “non-atomic” term would be a functional term, something like (#$BabyFn #$Jaguar).  Let’s say you had a function called #$BabyFn that applies to any animal type and you can use it to denote the baby forms of any animal.  So you could denote a baby cat, a baby whale, or a baby jaguar.

There is a distinction between predicates and functions in logic.  Predicates are statements about the truth of something -- it is either true or it’s not.  In the case of (#$mother #$Hamlet #$Gertrude), it’s stating “it is true that the mother of Hamlet is Gertrude.”  Functions denote a new term that you’re talking about.  The application of #$BabyFn to #$Jaguar does not say “it is true that BabyFn of Jaguar.”  That doesn’t make any sense.  The application of #$BabyFn to #$Jaguar allows you to denote a new concept, that of “Baby Jaguar.”  Functions and predicates can both be used to make what Cyc calls “formulas.”

Inference uses Deduction: Formulas and Logic

  A formula is just an operator applied to arguments.  In that sense, logical connectives like #$implies, #$and, and #$or are also operators.  So the previous example of a rule is a formula as well. The operator #$implies takes two formulas as arguments and maks a larger formula.  This is what a logical connective is -- it is something that connects formulas into more complex formulas.

The basis for inference in Cyc is just performing the standard logical deductions or syllogisms that you learn in logic classes: All men are mortal.  Socrates is a man.  Therefore, Socrates is mortal.  This is just to point out that the basis of our system is not Bayesian Reasoning or fuzzy logic or something like that.  For every inference step we make, we actually have a logically-sound proof behind it that you can look at to see “X is true specifically because I did a deduction and Y and Z are the two things which together allow me to conclude it.”  This will be important later, when we describe how we perform truth maintenance in our system.

Inference uses Deduction: Rules + Facts

  Our system uses logical deduction as the basis for inference.  This can be tersely summarized as the application of rules plus facts to conclude some new facts.

An example of a fact is “the mother of Hamlet is Gertrude.”  You can use this fact plus the rule from previous slides to perform a logical deduction.  This deductive inference would be that because of this rule (everyone loves their mother) and this fact (the mother of Hamlet is Gertrude) you can logically conclude that Hamlet loves Gertrude.

The Resolution Principle

Let’s talk in a little more detail about how we perform these logical deductions.  The specific method that we use is the “Resolution Principle.” The Resolution Principle is a very standard logical mechanism for connecting two logical statements to come up with a third one.  The algorithm that embodies the resolution principle can be tersely summarized as “Unify, Substitute, and Merge,” in that order.  I’ll describe each of these steps in this next example.

Assume for a moment that I have a question that I’m asking the system: “Who is it that Hamlet both knows and loves?”  I want the system to try and prove what answers for “Who?” are in our system.  So, given that the formula on the left of the slide is the query that I’m asking, and we have the rule on the right of the slide in our system (which says that everyone loves their mother), then one way of concluding who someone loves would be if you know who their mother is.

The Resolution Principle: Unify

  I can use the query and the rule to perform one logical deductive step: I can prove an answer for your query if I can prove an answer for something else because of some rule in the system.  In effect, an application of the Resolution Principle allows you to take one logical formula and use it in concert with the thing you’re trying to prove to help you turn it into something else you should try and prove.  This can either be more complicated or less complicated than what you start with.  I’ll talk about the ramifications of both of those options later.  For now, let’s look at how we would perform this one step in this case.

The act of combining the query and the rule to help answer part of the query is one deductive step.  The following is how we apply the resolution principle to this situation.  The key is to identify one particular literal which is common between the two.  In this case, we have the literal “Who does Hamlet love?” and a rule that would allow us to conclude who everyone loves.  “Who does Hamlet love?” would be called the “pivot literal” in the query and “Person loves its mother” would be called the “pivot literal” in the rule because these are the literals around which the whole step pivots.  So we identify that we are going to try and prove this literal, (#$loves #$Hamlet ?WHO), using the rule on the right of the slide.

The Resolution Principle: Unify

  Se we have decided to see if we can prove the loves part, the third line of the query, using the third line of the rule.  We can do it by unifying the “loves” from the query with the “loves” from the rule.  The unification step is attempting to identify a way of making the two “loves” literals exactly the same.  This is the essence of Unification.  We’re trying to come up with a recipe for how to make both of these actually exactly the same.  That recipe is referred to as the “Most General Unifier.”  This is a recipe for substituting one thing for another such that if you did the substitution, then you would actually have the exact same thing.  So, in this case, we can get the literals to be exactly the same with this proviso: if #$Hamlet is matched up with ?PERSON and ?WHO is matched up with ?MOTHER.  It’s called the Most General Unifier because we make the most conservative recipe possible -- we’re not committing to anything more than we have to in order to get these things to match and that makes it most general.

So once we’ve identified the Most General Unifier, the most general recipe for making them the same, we’ve completed the unifying step.

The Resolution Principle: Substitute

  Given the Most General Unifier, we can apply this recipe to both of them to perform the Substitution step.  We apply this recipe to one literal in order to get it to be the same as the other.  If I substitute into the rule, #$Hamlet for ?PERSON and ?WHO for ?MOTHER, I’ll then have something in which the third line of both the query and the rule exactly match.  We also apply the Most General Unifier to the rest of the query and the rule.  This is a simple unification, but it is common in the inference that Cyc normally does.

The Resolution Principle: Merge

  The final step is the Merge step, where we then take the remaining pieces of both and merge them together into something like what you see at the bottom of the slide.  The loves part disappears because that’s the thing that actually got proved in this step.  The result of the merge is a combination of the two substituted pieces together.  So, we start out with “Who does Hamlet know and love?” and using this rule, “Everyone loves their mother,” we can turn our original query into “Who does Hamlet know? And is that person Hamlet’s mother?”  If I were to find an answer for the new, merged question, then because of the rule, it would be an answer for the query.

So what results is a new thing, shown at the bottom of the slide, that we try and prove.  It indicates that any answer for the formula, because of the rule on the right of the slide, would be an answer for the query on the left of the slide.

The Resolution Principle using a fact

 
So, the act of inference is taking things that you're trying to prove and applying things you already know in order to find different things to prove.  Hopefully these things you are trying to prove eventually reduce down to something like “true” which is patently true already and does not need to be proven.  Therefore, the path of how you got there would provide one complete logical proof of an answer.

Let’s look at another example of the Resolution Principle -- one that uses a fact instead of a rule.  Let’s say that we actually have “Hamlet loves Ophelia” as a fact instead of a rule.  We’re still asking “Who does Hamlet know and love?”  I can use the fact “Hamlet loves Ophelia” to resolve against the loves literal in the query.  In this case, the Most General Unifier would be simpler.  It would just be matching ?WHO with #$Ophelia.  All that would be left to prove is if Hamlet knows Ophelia, so down below we have a very simple statement.  This would usually be proved using some other knowledge, for example Ophelia is Hamlet’s friend and everyone knows their friends, or something like that.  With this, I could reduce the formula (#$knows #$Hamlet #$Ophelia) down to #$True.  There would be nothing left to prove.  It would be like there being an empty degenerate (#$and) in the query, which is equivalent to #$True.

This example shows that the use of a fact strictly simplifies a proof, while the use of a rule usually leaves a proof at least as complicated and sometimes more complicated (if it has more conditions in the antecedent) than the original.

Resolving to #$True

  Let me say more about proving “True.”  Once you arrive at #$True as the final thing to prove, you can realize that #$True is true, so you’ve actually finally proved it -- you’ve reached the end.

This leaves you with one complete deductive proof such that you can walk backwards and say “What did I use in each step along the way?” and collect up the formulas that you used along the way to make each step.  By collecting all of the Most General Unifiers involved in the proof, you can see things like “what did this variable ?WHO get bound to?  Oh, it eventually got bound to #$Ophelia here.”  So this kind of information keeps getting passed up to the top and eventually out the top will bubble an answer.  “Here is one answer for what you asked for and the path all the way down has each step along the way -- the intermediate steps (Most General Unifiers) and how you proved them, and what you used to justify this answer.”

Next we’ll be talking about how we actually algorithmically perform all of these resolution steps.  We just described logically how Cyc performs inference and in the next lesson we’re going to describe in more detail the mechanism that we use to perform these logical deductions.

Summary
  • Inference uses Deduction
    • Facts + Rules => New Fact
    • Rules vs. Facts
    • Predicates vs. Functions
  • Inference uses Resolution
    • The Resolution Principle: Unify,
    • Substitute, Merge
    • Resolving to #$True

This concludes the lesson on the logical aspects of Inference.