Créer une présentation
Télécharger la présentation

Télécharger la présentation
## DCP 1172 Introduction to Artificial Intelligence

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**DCP 1172Introduction to Artificial Intelligence**Chang-Sheng Chen Topics Covered: Introduction to Nonmonotonic Logic**Monotonic logic**• Standard logic is monotonic: • onceyou prove something is true, it is true forever • Monotonic Logic is not a good fit to reality • If the wallet is in the purse, and the purse in is the car, we can conclude that the wallet is in the car • But what if we take the purse out of the car? DCP 1172, Ch. 6**Monotonic Logic**• Given a collection of facts D that entail some sentence s (s is a logical conclusion of D): • for any collection of facts D’ such that DÍ D’ , D’ also entails s. • in other words: s is also a logical conclusion of any superset of D. DCP 1172, Ch. 6**Nonmonotonic Logic**• In a nonmonotonic system: • the addition of new facts can reduce the set of logical conclusions. • S is a conclusion of D, but is not necessarily a conclusion of D+newfact. • Humans use nonmonotonic reasoning constantly! DCP 1172, Ch. 6**What is “Non-monotonic Logic” ?**• To understand what nonmonotonic logic means simple consider a standard example: "all birds fly", "Tweety is a bird", "Does Tweet fly?". • The obvious answer is yes, • however what if later you learned that Tweety had a broken wing, then the answer becomes no, • then what if you learned that tweet was an airplane pilot, or had a jet pack, the answer can change again. • The important point is that as new information is added the answers change DCP 1172, Ch. 6**Nonmonotonic logic**• Facts and rules can be changed at any time • such facts and rules are said to be dynamic • Prolog uses nonmonotonic logic • assert(...) adds a fact or rule • retract(...) removes a fact or rule • assert and retract are said to be extralogical predicates DCP 1172, Ch. 6**Intelligent Reasoning**• One of the characteristics associated with intelligent systems is adaptability - the ability to deal with a changing environment. • Adaptation requires that a system be capable of adding and retracting beliefs as new information is available. • This requires nonmonotonic reasoning. DCP 1172, Ch. 6**Uncertainty**• Another characteristic of intelligent systems is the ability to reason under conditions of uncertainty. • Another way of saying this: the ability to reason with an incomplete set of facts. DCP 1172, Ch. 6**Can we implement inheritance using predicate logic?**• Pat is a Bat. • Bats are Mammals. • Bats can fly. • Bats have 2 legs. • Mammals cannot fly. • Mammals have 4 legs. • How many legs does Pat have? DCP 1172, Ch. 6**Inheritance**• Reasoning about inheritance of properties from one class to another: Bird(x) Flies(x) • Clearly this is not a good rule, since we know there are exceptions. Bird(x) Ù Normal(x) Flies(x) • This provides for exceptions, although we must define the conditions that imply Normal(x). DCP 1172, Ch. 6**Normal(x)**• Assuming we know that: Ostrich(x) Bird(x) ~Flies(x) • we can derive: Ostrich(x) ~Normal(x) • So an ostrich is not a normal bird. • But what about all the the other things that are birds? DCP 1172, Ch. 6**Assumptions and Defaults**• If there is no reason to believe otherwise, assume that Normal(x) is TRUE. • The default is that everything is normal. • Now we only need to supply additional information for exceptions. DCP 1172, Ch. 6**How to specify defaults**• A number of formal systems have been developed to handle defaults. • Nonmonotonic logics formalize unsound but reasonable patterns of reasoning with uncertain, incomplete and inconsistent information • Default Logic: New rule of inference • Abduction: New interpretation of implication. DCP 1172, Ch. 6**And More Logics To Think About!**• Modal logic is useful for modeling reasoning about knowledge, actions, time or obligations. • Epistemic logics apply the techniques of modal logic to reasoning about knowledge. • Both individual and group knowledge is studied. The study of epistemic logic is relevant to communication protocols and cooperation. • Deontic logic formalizes normative modalities. • Deontic logic can be applied to representation of normative (e.g. legal) knowledge. DCP 1172, Ch. 6**Default Reasoning with Nonmonotonic Logic**• Predicate logic with an extension: • a modal operator M which means is “consistent with everything we know”. • Example: x,y: Related(x,y) Ù M GetAlong(x,y) WillDefend (x,y) DCP 1172, Ch. 6**Default Logic**• New rule of inference: A : B C • If A is true and it is consistent to assume B, then C is true. • Same idea, but now used as a rule of inference. The new rule extends the knowledge base to a set of plausible extensions, any new statement that is true in all extensions is added. DCP 1172, Ch. 6**Inheritance with Default Logic**• Support for inheritance using Default Logic: Mammal(x) : Legs(x,4) Legs(x,4) • In the absence of contradictory information, we can assume anything that is a mammal has 4 legs. (also need a rule stating that nothing can have 2 different numbers of legs!) DCP 1172, Ch. 6**Abduction**• Deduction (演繹): Given A(x) B(x) and A(x), we assume that B(x) is true. • Similar to forward reasoning • [Cf.] reasoning from the general to the particular (or from cause to effect) • Abduction: Given A(x) B(x) and B(x), we assume that A(x) is true. • Similar to backward reasoning DCP 1172, Ch. 6**Inheritance Diagrams**• The book shows how we can also express default reasoning using diagrams. Flying Things Normal Facts Default Ostriches Birds Default Fred Tweety DCP 1172, Ch. 6**A Problem with NML**• x: Republican(x) Ù M ~ Pacifist(x) ~ Pacifist(x) • x: Quaker(x) Ù M Pacifist(x) Pacifist(x) • Republican(Dick) • Quaker(Dick) DCP 1172, Ch. 6**Pacifists**Republicans Quakers Nixon Not quite this easy • Assuming we have some mechanism for representing defaults, there can still be problems: • Is Nixon a pacifist? DCP 1172, Ch. 6**Nixon Dilemma**• In general we must be prepared to deal with multiple, possibly conflicting consequences of a set of facts. • One simple idea - rank all the assumptions and use rank to determine which to believe. DCP 1172, Ch. 6**Other approaches to handling conflicting assumptions.**• Minimalist Reasoning • Assume that there are fewer true statements that false statements in the world. • Find the smallest interpretation that satisfies all the statements we know to be true. • Closed World Assumption: the only objects that satisfy a predicate are those that must. • forces positive assertions to take priority over negative assertions DCP 1172, Ch. 6**Closed world assumption**• If we are told nothing about Tweety, other than Tweety is a bird, • we assume that Tweety's feet are not in concrete, or Tweety's wings are not broken, this is the closed world assumption. • Humans regularly make assumptions and when new evidence appears those assumptions can be changed, causing a different answer, thus behaving nonmonotonicaly. DCP 1172, Ch. 6**Using Probabilities**• Probabilities can also be used determine which defaults apply when contradictions arise. • Label each fact with a probability of being true. • There is a big split in the A.I. community over whether symbolic methods or numeric methods are best for handling these types of issues. DCP 1172, Ch. 6**Summary - Nonmonotonic logic vs. Probabilty**• Nonmonotonic logic systems may miss the importance of probability. • Probabilistic reasoners can also represent uncertainty, and in a different (probabilistic) way. • These systems exhibit a different set of properties, with which nonmonotonic logic can not effectively deal with. DCP 1172, Ch. 6**Nonmonotonic vs. Classical logic**• Nonmonotonic logic does not have many essential properties of classical first order logic, specifically semi-decidability. • In classical logic, it is possible for a system to halt (be stuck in an infinite loop) trying to prove the negation of something for which there is insufficient information. • In nonmonotonic default logic, rather than return with no answer, the process returns with a wrong (default answer). DCP 1172, Ch. 6**Summary - Nonmonotonic vs. Classical logic**• First order logic although descriptively universal, is not effective at handling large classes of problems. • If computers are going to handle common sense we need to be able to have some form of default reasoning. • Nonmonotonic logic can be used in many domains where classical logic falls short: • such as in the areas of default diagnosis, diagnosis, action, and temporal logic. DCP 1172, Ch. 6