Planning and Machine Learning

PLANNING AND MACHINE LEARNING

Reasoning is the act of deriving a conclusion from certain premises using a given methodology.

Reasoning is a process of thinking; reasoning is logically arguing; reasoning is drawing inference.

When a system is required to do something, that it has not been explicitly told how to do, it must reason. It must figure out what it needs to know from what it already knows.

Many types of Reasoning have long been identified and recognized, but many questions regarding their logical and computational properties still remain controversial.

The popular methods of Reasoning include abduction, induction, model-based, explanation and confirmation. All of them are intimately related to problems of belief revision and theory development, knowledge assimilation, discovery and learning.

1. Reasoning

Any  knowledge system  to  do  something,  if  it  has  not been  explicitly  told

how to do it then it must reason.

The system must figure out what it needs to know from what it already knows. Example

If we know : Robins are birds. All birds have wings. Then if we ask : Do robins have wings?

Some reasoning (although very simple) has to go on answering  the question.

 1.1 Definitions :

Reasoning is the act of deriving a conclusion from certain premises using a given methodology.

Any knowledge system must reason, if it is required to do something which has not been told explicitly .

For reasoning, the system must find out what it needs to know from what it already knows.

Example :

If we know :                                  Robins are birds.

All birds have wings

Then if we ask:                             Do robins have wings?

To answer this question - some reasoning must go.

areas:

Mathematical Reasoning – axioms, definitions, theorems, proofs

Logical Reasoning – deductive, inductive, abductive

Non-Logical Reasoning – linguistic , language

These three areas of reasoning, are in every human being, but the ability level depends on education, environment and genetics.

The IQ (Intelligence quotient) is the summation of mathematical reasoning skill and the logical reasoning.

The EQ (Emotional Quotient) depends mostly on non-logical reasoning capabilities.

Note : The Logical Reasoning is of our concern in AI

Logical Reasoning

Logic is a  language  for  reasoning. It  is  a  collection of rules called Logic arguments, we use when doing logical reasoning.

Logic reasoning is the process of drawing conclusions from premises using rules of inference.

The study of logic is divided into formal and informal logic. The formal logic is sometimes called symbolic logic.

Formal system consists of two components, a formal language plus a set of inference rules. The formal system has axioms.

Axiom is a sentence that is always true within the system.

Sentences are derived using the system's axioms and rules of derivation are called theorems.

Formal Logic

The Formal logic is the study of inference with purely formal content, ie. where content is made explicit.

Examples - Propositional logic and Predicate logic.

Here the logical arguments are a set of rules for manipulating symbols. The rules are of two types

◊ Syntax rules                         : say how to build meaningful expressions.

Inference rules : say how to obtain true formulas from other true formulas.

Logic also needs semantics, which says how to assign meaning to expressions.

Informal Logic

The Informal logic is the study of natural language arguments.

The analysis of the argument structures in ordinary language is part of informal logic.

The focus lies in distinguishing good arguments (valid) from bad arguments or fallacies (invalid).

■                Formal Systems

Formal systems can have following three properties :

‡ Consistency : System's      theorems do not contradict.

‡ Soundness : System's rules  of  derivation       will  never  infer anything false, so long    as start is with only      true premises.

Completeness : There are no true sentences in the system that cannot be proved using the derivation rules of the system.

System Elements

Formal systems consist of following elements :

A finite set of symbols for constructing formulae.

A grammar, is a way of constructing well-formed formulae (wff).

A set of axioms; each axiom has to be a wff.

A set of inference rules.

A set of theorems.

A well-formed formulae, wff, is any string generated by a grammar. e.g., the sequence of symbols ((α → β ) → (¬ β → ¬ α )) is a WFF because it is grammatically correct in propositional logic.

■ Formal Language

A formal language may be viewed as being analogous to a  collection of words or a collection of sentences.

In computer science, a formal language is defined by precise mathematical or machine process able formulas.

A formal language L is characterized as a set F of finite-length sequences of elements drawn from a specified finite set A of symbols.

Mathematically, it is an unordered pair L = { A, F }

If  A is words

then the set A is called alphabet of L, and the elements of F are called words.

‡ If A is sentence

then the set A is called the lexicon or vocabulary of F, and the elements of F are then called sentences.

‡ The mathematical theory that treats formal languages in general is known as formal language theory.

Uncertainty in Reasoning

■ The world is an uncertain place; often the Knowledge is imperfect which causes uncertainty. Therefore reasoning must be able to operate under uncertainty.

■ AI systems must have ability to reason under conditions of uncertainty.

Monotonic Logic

Formal logic is a set of rules for making deductions that seem self evident. A Mathematical logic formalizes such deductions with rules precise enough to program a computer to decide if an argument is valid, representing objects and relationships symbolically.

Examples

Predicate logic and the inferences we perform on it.

All humans are mortal. Socrates is a human. Therefore Socrates is mortal.

In monotonic reasoning if we enlarge at set of axioms we cannot retract any existing assertions or axioms.

Most formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. In other words, a logic is monotonic if the truth of a proposition does not change when new information (axioms) are added. The traditional logic is monotonic.

‡ In mid 1970s, Marvin Minsky and John McCarthy pointed out that pure classical logic is not adequate to represent the commonsense nature of human reasoning. The reason is, the human reasoning is non-monotonic in nature. This means, we reach to conclusions from certain premises that we would not reach if certain other sentences are included in our premises.

‡        The non-monotonic human reasoning is caused by the fact that our knowledge about the world is always incomplete and therefore we are fo ed to reason in the absence of complete information. Therefore we often revise our conclusions, when new information becomes available.

Thus, the need for non-monotonic reasoning in AI was recognized, and several formalizations of non-monotonic reasoning.

Only the non-monotonic logic reasoning is presented in next few slides.

Non-Monotonic Logic

Inadequacy of monotonic logic for reasoning is said in the previous slide. A monotonic logic cannot handle :

Reasoning by default : because consequences may be derived only because of lack of evidence of the contrary.

Abductive reasoning : because consequences are only deduced as most likely explanations.

Belief revision : because new knowledge may contradict old beliefs.

A non-monotonic logic is a formal logic whose consequence relation is not monotonic. A logic is non-monotonic if the truth of a proposition may change when new information (axioms) are added.

‡ Allows a statement to be retracted.

‡ Used to formalize plausible (believable) reasoning.

Example 1 :

Birds typically fly.

Tweety is a bird.

--------------------------

Tweety (presumably) flies.

‡  Conclusion of non-monotonic argument may not be correct.

Example-2 : (Ref. Example-1)

If Tweety is a penguin, it is incorrect to conclude that Tweety flies. (Incorrect because, in example-1, default rules were applied when case-specific information was not available.)

All non-monotonic reasoning are concerned with consistency. Inconsistency is resolved, by removing the relevant conclusion(s)

derived by default rules, as shown in the example below.

Example -3 :

The truth value (true or false), of propositions such as "Tweety is a bird" accepts default that is normally true, such as "Birds typically fly". Conclusions derived was "Tweety flies". When an inconsistency is recognized, only the truth value of the last type is changed.

2. Different Methods of Reasoning

Mostly three kinds of logical reasoning: Deduction, Induction, Abduction.

Deduction

Example: "When it rains, the grass gets wet. It rains. Thus, the grass is wet."

This means in determining the conclusion; it is using rule and its precondition to make a conclusion.

Applying a general principle to a special case.

Using theory to make predictions

Usage: Inference engines, Theorem provers, Planning.

Induction

Example: "The grass has been wet every time it has rained. Thus, when it rains, the grass gets wet."

This means in determining the rule; it is learning the rule after numerous examples of conclusion following the precondition.

Deriving a general principle from special cases

From observations to generalizations to knowledge

Usage: Neural nets, Bayesian nets, Pattern recognition

■                Abduction

.

Example: "When it rains, the grass gets wet. The grass is wet, it must have rained."

Means determining the precondition; it is using the conclusion and the rule to support that the precondition could explain the conclusion.

Guessing that some general principle can relate a given pattern of cases

Extract hypotheses to form a tentative theory

Usage: Knowledge discovery, Statistical methods,  Data mining.

Analogy

Example: "An atom, with its nucleus and electrons, is like the solar system, with its sun and planets."

Means analogous; it is illustration of an idea by means of a more familiar idea that is similar to it in some significant features. and thus said to be analogous to it.

finding a common pattern in different cases

usage: Matching labels, Matching sub-graphs, Matching transformations.

Note: Deductive reasoning and Inductive reasoning are the two most commonly used explicit methods of reasoning to reach a conclusion.

More about different methods of Reasoning

■                Deduction Example

Reason from facts and general principles to other facts.

Guarantees that the conclusion is true.

Modus Ponens : a valid form of argument affirming the antecedent.

If it is rainy, John carries an umbrella

It is rainy / John carries an umbrella.

◊ If p then q

p/q

Modus Tollens : a valid form of argument denying the consequent.

If it is rainy, John carries an umbrella

John does not carry an umbrella / It is not rainy

◊ If p then q

not q / not p

Induction Example

Reasoning from many instances to all instances.

‡ Good Movie 

Fact : You have liked all movies starring Mery.

Inference     You will like her next movie.

‡                       Birds    

Facts:          Woodpeckers, swifts, eagles, finches have four toes on each foot.

Inductive Inference         All birds have 4 toes on each foot.

(Note: partridges have only 3).

‡                       Objects 

Facts : Cars, bottles, blocks fall if not held up.

Inductive Inference         If not supported, an object will fall.

(Note: an unsupported helium balloon will rise.)

‡                       Medicine        

Noted : People who had cowpox did not get smallpox.

Induction : Cowpox prevents smallpox.

Problem : Sometime inference is correct, sometimes not correct.

Advantage : Inductive inference may be useful even if not correct. It generates a proposition which may be validated deductively.

Abduction Example

Common form of human reasoning– "Inference to the best explanation".

In Abductive reasoning you make an assumption which, if true, together with your general knowledge, will explain the facts.

‡  Dating

Fact:           Mary asks John to a party.

Abductive Inferences : Mary likes John.

John is Mary's last choice.

Mary wants to make someone else jealous.

‡                       Smoking house        

Fact:           A  large  amount  of  black  smoke  is  coming from a home.

Abduction1:         the house is on fire.

Abduction2:         bad cook.

‡                       Diagnosis                

Facts:          A  thirteen  year-old  boy  has  a  sharp  pain in his right side, a fever, and a high white blood count.

Abductive : inference     Appendicitis.

Problem:          Not always correct; many explanations possible.

Advantage :      Understandable conclusions.

Analogy Example

Analogical Reasoning yields conjectures, possibilities.

If A is like B in some ways, then infer A is like B in other ways.

‡ Atom and Solar System

Statements:                              An atom, with its nucleus and electrons, is like the

solar system, with its sun and planets.

Inferences:                                Electrons travel around the nucleus.

Orbits are ci                                                     ular.

Orbits are all in one plane.

Electrons have little people living on them.

Idea:                                         Transfer information from known (sou  e)

to unknown (target).

‡ Sun and Girl

Statement:                                She is like the sun to me.

Inferences:                                She lights up my life.

She gives me warmth.

?                                               She is gaseous.

?                                               She is spherical.

‡                     Sale man Logic

Statement:                                John has a fancy car and a pretty girlfriend.

Inferences:                                If Peter buys a fancy car,

Then Peter will have a pretty girlfriend.

Problems :                     Few analogical inferences are correct

Advantage :  Suggests novel possibilities. Helps to organize information.

 3. Sou es of Uncertainty in Reasoning

In many problem domains it is not possible to create complete, consistent models of the world. Therefore agents (and people) must act in uncertain worlds (which the real world is). We want an agent to make rational decisions even when there is not enough information to prove that an action will work.

Uncertainty is omnipresent because of

Incompleteness

Incorrectness

Uncertainty in Data or Expert Knowledge

Data derived from defaults/assumptions

Inconsistency between knowledge from different experts.

“Best Guesses”

Uncertainty in Knowledge Representation

Restricted model of the real system.

Limited expressiveness of the representation mechanism.

Uncertainty in Rules or Inference Process

Incomplete because too many conditions to be explicitly enumerated

Incomplete because some conditions are unknown

Conflict Resolution

4. Reasoning and KR

To certain extent, the reasoning depends on the way the knowledge is represented or chosen.

A good knowledge representation scheme allows easy, natural and plausible (credible) reasoning.

Reasoning methods are broadly identified as :

Formal reasoning: Using basic rules of inference with logic knowledge representations.

Procedural reasoning:    Uses procedures that specify how to perhaps solve sub problems.

Reasoning by analogy : This is as Human do, but more difficult for AI systems.

Generalization and abstraction: This is also as Human do; are basically learning and understanding methods.

Meta-level reasoning : Uses knowledge about what we know and ordering them as per importance.

Note : What ever may be the reasoning method, the AI model must be able to reason under conditions of uncertainty mentioned before.

5. Approaches to Reasoning

There are three different approaches to reasoning under uncertainties.

Symbolic reasoning

Statistical reasoning

Fuzzy logic reasoning

The first two approaches are presented in the subsequent slides.