Posts Tagged ‘logic’

How to use Logical Inference and Unification in AI

The previous posts on propositional calculus (or zeroth-order logic) and predicate calculus (first-order logic), build on the final and practical application of these logical systems in artificial intelligence automated reasoning systems. Through logical inference and unification we will take a real world example for a financial advisor decision making system.

We come to the full possession of our power of drawing inferences, the last of our facilities; for it is not so much a natural fight as a long and difficult art.

C. S. Pierce

Logical Inference

Logical inference is a formal theory that infers new correct expressions from a set of true assertions. These new assertions will be consistent with all previous statements and interpretations. Inference rules provide the computational mechanism which we can use the concept that a conclusion “logically follows” from a premise.

A basic example is modus ponens. The inference rule for modus ponens is

If P and P → Q are true, then modus ponens infers Q is also true.

More inference rules like modus tollens, examples can be found at the Wikipedia page here.

Unification

In order to apply these rules of inference we will need to be able to determine when two expressions match. This is trivial in propositional calculus, but the presence of variables in predicate calculus makes it more complicated. Unification is the algorithm that determines what substitutions we can make to predicate calculus expressions in order to make them match.

First we check the initial predicate symbol, then the number of arguments the predicate has, and then the actual arguments for a match. These arguments are either variables or constants, for example,

love(X, Y) and love(eleanor, chidi)
We can list substitutions and unify as {X/eleanor, Y/chidi}.

When unifying we have three rules:

  • a variable can by unified with an atom, variable or term
  • two atoms can by unified if they are identical
  • a term can be unified if the identifiers are the same

Here are some more examples:

p(X,Y) and p(a,Z)
'X' is a variable, and 'a' is an atom.
'X' and 'Z' are variables.
Therefore it unifies with {X/a, Z/Y}.
p(X,X) and p(a,b)
'X' is a variable, but it cannot be substituted by both 'a' and 'b' atoms, therefore it does not unify.
ancestor(X,Y) and ancestor(bill,father(bill))
'ancestor' and 'ancestor' unify and return the empty set {}
'X' and 'bill' unify as {bill/X}
'Y' and father(bill) unifies as {father(bill)/Y}
Therefore it unifies to {bill/X,father(bill)/Y}
ancestor(X,father(X)) and ancestor(david,george)
Assuming that george is the father of david:
'ancestor' and 'ancestor' unify and return the empty set {}
'X' and 'david' unify as {david/X}
father(X) and 'george' unify as {george/father(X)}
Therefore it unifies to {david/X,george/father(X)}

A logic-based financial advisor

This example is part of the exercises found in Lugers text[efn_note](Luger, George F.; Stubblefield, William A, Artificial intelligence: structures and strategies for complex problem solving 1998)[/efn_note].

We are going to build a financial advisor that decides how someone should split their money between investments and savings. Specifically, the advisor should recommend the amount according the the following criteria.

  • Inadequate savings accounts should always make increasing their savings the top priority regardless of their income.
  • Adequate savings and adequate income should consider riskier investments in the stock market.
  • Lower income with an adequate savings may consider splitting their surplus in investments and savings.

From this we can create the first three predicates for our logical system:

1.  savings_account(inadequate) → investment(savings)
2.  savings_account(adequate)⋀income(adequate) → investment(stocks)
3.  savings_account(adequate)⋀income(inadequate) → investment(combination)

We now need to determine when savings and income are considered adequate. To do this we create the function minsavings which takes one argument, the number of dependents, and returns 5000 times that argument. minsavings(X) ≡ 5000 * X. Now we have two more predicates for our logical system.

4.  ∀ X amount_saved(X) ⋀ ∃ Y (dependents(Y) ⋀ greater(X, minsavings(Y))) → savings_account(adequate)
5.  ∀ X amount_saved(X) ⋀ ∃ Y (dependents(Y) ⋀ ¬ greater(X, minsavings(Y))) → savings_account(inadequate)

Similiarily we need a minincome function. We will define this function as minincome(X) ≡ 15000 + (4000 * X). To define an investors income as adequate it must be above this minimum income and also steady. This adds three more predicates to our logical system.

6.  ∀ X earnings(X, steady) ⋀ ∃ Y (dependents(Y) ⋀ greater(X, minincome(Y))) → income(adequate)
7.  ∀ X earnings(X, steady) ⋀ ∃ Y (dependents(Y) ⋀ ¬ greater(X, minincome(Y))) → income(inadequate)
8.  ∀ X earnings(X, unsteady) → income(inadequate)

For our example, Jane Doe has four dependents, a steady income of $30,000 and $15,000 in her savings account. This adds our final three predicate calculus sentences.

9.  amount_savings(15000)
10. earnings(30000,steady)
11. dependents(4)

Now for the fun part! Let’s unify! First we can unify conjunction of 10 and 11 with the first two components of 7.

earnings(30000, steady) ⋀ dependents(4) unifies with:
earnings(X, steady) ⋀ dependents(Y) under substitution {30000/X, 4/Y} yielding:

earnings(30000, steady) ⋀ dependents(4) ¬ greater(30000, minincome(4)) → income(inadequate)

earnings(30000, steady) ⋀ dependents(4) ¬ greater(30000, 31000) → income(inadequate)

All 3 components of the premise are true, therefore by 10, 3, and the mathematical definition of greater their conjunction is true and the entire premise is true. Thus, we can add another premise

12. income(inadequate)
amount_saved(15000) ⋀ dependents(4) unifies with the first two elements of assertion 5 under the substitution {15000/X, 4/Y} yielding:

amount_saved(15000) ⋀ dependents(4) ⋀ ¬ greater(15000, minsavings(4)) → savings_account(inadequate)

amount_saved(15000) ⋀ dependents(4) ⋀ ¬ greater(15000, 20000) → savings_account(inadequate)

Given that all 3 components of the premise are true, we have another premise

13. savings(inadequate)

As a consequence of expressions 13 and 1 and modus pollens,

savings(inadequate) → investment(savings)

Our automated logical reasoning system suggests that Jane Doe’s surplus income goes into her savings account. This example shows how we can automatically reason and draw conclusions by applying these inference rules in a programmatic fashion.

Tags: , , ,
Posted in artificial intelligence | No Comments »

Predicate Calculus: Its Simple Syntax, and Semantics

In my previous post I talked about propositional calculus. Today we will talk about predicate calculus and its syntax and semantics. Predicate calculus builds on this concept by allowing us to describe the relationships in our logical assertions. We could have a statement like “it snowed on Saturday” (it did… it sucks), and represent that as

weather(saturday, snow)

We can now add variables and start to generalize. For example if we use the X as a variable for the day of the week, we can say

weather(X, snow) is true

to say that it snows every day of the week (I hope not!). As usual, we first need to define the words in our language, that is the syntax.

The essential quality of a proof is to compel belief.

Fermat

Predicate Calculus Syntax and Semantics

In predicate calculus we use improper symbols to describe objects and their relationship in the world. These are parentheses “( )”, commas “,”, and periods “.”.

We define the symbols as strings of characters and digits. No spaces or special characters can be used, although the “_” can be used for readability. That is the valid characters used are

  1. All letters, upper- and lowercase.
  2. All digits from 0 to 9.
  3. The underscore, “_”.

And all symbols must start with a letter. Some correct examples are

Name   coffee3   stan_and_kyle   emma   XYZ   likes   partner_of

And some invalid examples are

7John   stan and kyle   ta%ble   ###123   lookout!!!

These symbols can represent variables, constants, functions, or predicates.

Variables are used for the abstract concept of classes. Any symbol beginning with a capital is a variable.

X   Name   Location

Constants are specific objects in the world, and start with a lowercase.

emma   small   pink     
note: true and false are reserved as truth symbols

Functions also start with a lowercase, and are used the map elements in a set. In this writers world, the function

aunt(emma)

evaluates to nancy. Functions also have an arity associated with them. In the previous example the arity would be 1. An example of an arity of 2 could be

loves(nancy, emma)

Another simple example would be

subtract(nine, two)

which evaluates to seven.

A predicate term is a constant, variable, or function expression of a specific arity. We use these terms to describe the problem domain. This leads to another definition, the atomic sentence. It is simply a predicate of N arity followed by N terms in parentheses separated by commas. It is the the most primitive unit of a predicate term. An example of an atomic sentence is

loves(aunt(emma), partner_of(nancy))

Now that we have our basic unit, we can build predicate sentences. First some definitions of symbols

  • ∧ : logical and
  • ∨ : logical or
  • ¬ : logical not
  • → : logical implies
  • ≡ : logical equivalent to
  • ∀ : universal quantifier (reads “sentence is true for all values”)
  • ∃ : existential quantifier (reads “sentence is true for at least one value”)

To end our discussion on syntax I’ll show another example[efn_note](Luger, George F.; Stubblefield, William A, Artificial intelligence: structures and strategies for complex problem solving 1998)[/efn_note].

mother(eve, abel)
mother(eve, cain)
father(adam, abel)
father(adam, cain)

∀ X ∀ Y father(X, Y) ∨ mother(X, Y) → parent(X, Y)
∀ X ∀ Y ∀ Z parent(X, Y) ∧ parent(X, Z) → sibling(Y, Z)

The first 4 lines describe the world. The second two sentences define rules of the world. The first states that for all X’s and all Y’s, if the X is the father of Y or mother of Y, than X is implied to be a parent of Y. The second states that for all X’s, Y’s, and Z’s if a parent of Y is X, and a parent of Z is X, then it is implied that the sibling of Y is Z. If this still confuses you, I encourage you to plug in the variables and see how that looks on paper.

If you want more check out the MIT OpenCourseWare video here!

Tags: ,
Posted in artificial intelligence | No Comments »

Propositional Calculus – A Quick Artificial Intelligence primer

Artificial Intelligence includes much more than machine learning I’ve talked about before here, and here. I thought I’d start talking about this by introducing predicate calculus. Predicate calculus, also known as first-order logic, is the collection of formal systems used in computer science to quantify non-logical objects and expressions. It breaks down artificial intelligence systems to their most atomic states.

Logic is the anatomy of thought.

John Locke

Logic is the beginning of wisdom, not the end.

Spock

A fact can be broken down into propositional expressions. The most traditional example is,

  • Socrates is a human (P)
  • All human are mortal (Q)
  • Therefore Socrates is mortal (P –> Q)

This reads P is true, and Q is true, therefore P implies Q.

Some examples of propositional operators that build our propositional expressions are,

  • ∧ : AND
  • ∨ : OR
  • ¬ : NOT

Let’s do an example. How would we express something like the exclusive-or operator ⊗, using only those operators? We can start by making a truth table of what this should look like.

PQP⊗Q
TTF
TFT
FTT
FFF
Truth table for the exclusive-or

Now an exclusive-or sentence in English should say P or Q, but not P and Q. That expression in our formal propositional style is (P ⋁ Q) ⋀ ¬(P ⋀ Q). But lets check our work with truth tables.

PQP ⋁ Q¬(P ⋀ Q)(P ⋁ Q) ⋀ ¬(P ⋀ Q)
TTTFF
TFTTT
FTTTT
FFFTF
Truth table for (P ⋁ Q) ⋀ ¬(P ⋀ Q)

This truth table evaluates to the same truth values and shows P⊕Q ≡ (P ⋁ Q) ⋀ ¬(P ⋀ Q).

Modus Ponens

We can use truth tables to prove some classic logical arguments. Let’s start wtih modus ponens. Modus ponens states that P is true, therefore Q is true. The “Socrates is a human” predicate above is an example of modus ponens. A truth table for modus ponens would be:

PQP → Q
TTT
TFF
Because we state P to be true, we only need to look at those cases. Interestingly in the case of false statements P implies Q would evaluate to false, showing that false statements imply anything!

The truth tables shows truth values of the if… then statement of P → Q. If the statement was instead,

  • Shakespeare is a human.
  • All humans are men.
  • Therefore Shakespeare is a man.

Note that although Shakespeare could be a man, the logical argument is not sound. Because Q (All humans are men) is false, we cannot state that P implies Q.

Abduction

Abduction is an inference rule that infers P to be true from P → Q. Let’s look again to the P → Q truth table.

PQP → Q
TTT
FTT
This time we consider cases where P → Q is True. We can see that there are instances were P is True and P is False, and we cannot infer that P is true from P → Q.

Abductive reasoning is common in science. Sherlock Holmes, often praised for his deductive skills, often actually uses abductive reasoning to come to his conclusions. As an example look at these two arguments.

  • Organs have been designed to be similar to machines.
  • Machines are a product of intelligent design.
  • Therefore, humans are the product of intelligent design

or,

  • Test mice given water from a new industrial plant get sick.
  • People got sick after the plant was opened.
  • Therefore, the current sickness caused by the new plant.

Modus tollens

Finally let’s look at modus tollens. Modus tollens, or affirming the consequent is the contrapositive of modus ponens. It states Q is false, and P → Q is false, and concludes P is false. The propositional expression is ((P → Q) ⋀ ¬ Q) → ¬ P. This truth table is,

PQP → Q¬ P¬ Q((P → Q) ⋀ ¬ Q)((P → Q) ⋀ ¬ Q) → ¬ P
TFFFTFF
FFTTTTT
Assuming Q is false, P is inferred to also be false, else modus tollens evaluates to false.

Artificial Intelligence starts with these basic concepts. I encourage you to learn more about them and how to build and use truth tables in all your work.

Tags: ,
Posted in artificial intelligence | No Comments »