advertisement

Ch90 ExtensionsToFOPC

40 %
60 %
advertisement
Information about Ch90 ExtensionsToFOPC
Entertainment

Published on September 17, 2007

Author: CoolDude26

Source: authorstream.com

advertisement

Extensions to FOL:  Extensions to FOL Extensions to FOL:  Extensions to FOL When the form of the statements provides useful information Rule-based systems Frame systems When FOL isn’t enough Default reasoning and circumscription Reasoning with uncertainty Degrees of membership (fuzzy logic) Reasoning about belief What Does  Really Mean?:  What Does  Really Mean? HasChildren  Mother A  B definition of B Raining  Wet A  B A causes B Fever  Infection A  B A is a symptom of B B causes A LikeBig  GetHummer A  B whenever A occurs, B usually does too So how should we reason with these very different things? Rule-Based Systems:  Rule-Based Systems The logic: a  b is equivalent to: a  b So, given: fever  infection fever  infection fever Conclude: infection Given: fever  infection fever  infection infection Conclude: fever But are these two inferences equally useful? An Example for a Design Task: XCON (1982):  An Example for a Design Task: XCON (1982) From XCON (1982): If: the most current active context is distributing massbus devices, and there is a single-port disk drive that has not been assigned to a massbus, and there are no unassigned dual-port disk drives, and the number of devices that each massbus should support is known, and there is a massbus that has been assigned at least one disk drive that should support additional disk drives, and the type of cable needed to connect the disk drive to the previous device on the massbus is known Then: assign the disk drive to the massbus. An Example for a Diagnosis Task: Mycin (1975):  An Example for a Diagnosis Task: Mycin (1975) If: (1) the stain of the ogranism is gram-positive, and (2) the morphology of the organism is coccus, and (3) the growth conformation of the organism is clumps Then: there is suggestive evidence (0.7) that the identity of the organism is staphylococcus. Simple Examples Today:  Simple Examples Today eXpertise2Go: http://www.expertise2go.com/ AcquiredIntelligence: http://www.aiinc.ca/demos/ (whales, graduate school) DecisionScript: http://www.vanguardsw.com/decisionscript/Examples.htm Implementation of Rule-Based Systems:  Implementation of Rule-Based Systems Prolog: The KB: reply(sampcor) :- a, b A query: ?- reply(X) Use backward chaining to answer the question. Expert system shells: Typically combine methods If (1) the suggested technique category is correlation and regression analysis, and (2) one of the values of the desired correlation/regression result is a measure of the degree to which 2 variables move together Then the suggested analysis approach is to calculate a sample correlation coefficient If a  b  reply(sampcor) Expert System Shells :  Expert System Shells Some rules are best used in forward chaining mode. For example, data collection and reasoning from symptoms. Other rules (e.g., how to achieve goals) are best used in backward chaining mode. All these rules may also want to exploit other kinds of knowledge, like default information associated with classes of objects: Inheritance, Again:  Inheritance, Again birds canfly T ISA ISA robins ostriches canfly F Instance-of Instance-of Tweety Richy Scooter is a bird. Can Scooter fly? Inheritance:  Inheritance Objects inherit from their parents: Scooter inherits from Bird the facts that: its birthmode is eggs, and it has two wings Should Scooter inherit from Bird the fact that it can fly? Default Reasoning:  Default Reasoning The importance of default reasoning Default reasoning is nonmonotonic. Techniques for default reasoning Inheritance The closed world assumption Circumscription Maintaining consistency in nonmonotonic reasoning systems Default Reasoning - Examples:  Default Reasoning - Examples Inheritance from superclasses: x bird(x)  canfly(x) UNLESS ostrich(x) The 'normal' case: x bird(x)  canfly(x) UNLESS (broken-wing(x)  sick(x)  in(oil-slick, x)) The closed world assumption: can cats fly? Abduction: infection  fever Given fever, can we conclude infection? Default Reasoning in Nonmonotonic:  Default Reasoning in Nonmonotonic Inference in FOL systems is monotonic: The addition of any new assertion that is consistent with the KB will never cause a formula that was previously true to become false. Default reasoning may be nonmonotonic: Birds can fly. Tweety is a bird.  Tweety can fly. But what if we now learn: Tweety is an ostrich. or Tweety has a broken wing. Implementing Inheritance:  Implementing Inheritance birds canfly T ISA ISA robins ostriches canfly F Instance-of Instance-of Tweety Richy If we implement inheritance procedurally, we don’t have to write the UNLESS clauses. We assume Tweety isn’t an ostrich. The Closed World Assumption:  The Closed World Assumption The CWA: Any ground atomic sentences that are not asserted to be true in the KB can be assumed to be false. We make the closed world assumption for two reasons: We have to. In any complex domain, there may be a huge number of possible facts and there isn’t time to mention each of them explicitly: A database of classes mentions the ones that are offered. An inventory database mentions all the objects on hand. An airline scheduling system assumes that it will be told if the power is out or the terminal has burned down or is held by terrorists or there is a storm. It is consistent with felicitous human communication. Implementing the CWA: Negation as Failure:  Implementing the CWA: Negation as Failure A common way to implement the CWA: Interpret failure to prove p as a proof of p. Example:  hasonhand(x)  uses(x)  mustorder(x) How do we prove  hasonhand(x)? Circumscription:  Circumscription x bird(x)  canfly(x) UNLESS (broken-wing(x)  sick(x)  in(oil-slick, x)) Is different from: x bird(x)  broken-wing(x)   sick(x)   in(oil-slick, x)  canfly(x) Or: x bird(x)  adult(x)  withmother(x) One way to implement this is to create the predicate Abnormal: x bird(x)  canfly(x) UNLESS Abnormal(x) (broken-wing(x)  sick(x)  in(oil-slick, x))  Abnormal(x) Circumscription:  Circumscription Then we circumscribe Abnormal, i.e., we prefer models in which Abnormal is true of the smallest possible number of individuals consistent with the rest of the KB. But what happens if we are told just: bird(Tweety) and then we conclude canfly(Tweety) Then we are told: broken-wing(Tweety) How do we undo the conclusion canfly(Tweety)? Abbott, Babbitt, and Cabot:  Abbott, Babbitt, and Cabot Truth Maintenance Systems:  Truth Maintenance Systems The basic idea: Associate with each assertion one or more justifications. Believe any assertion with at least one valid justification. Each justification is composed of two parts: An IN-list An OUT-list We will define the operation of a TMS that operates as a service to a separate reasoning system. The TMS doesn’t make choices. It is just a bookkeeper. The Structure of a Justification:  The Structure of a Justification Before Alibis:  Before Alibis Abbott’s Situation, with Alibi:  Abbott’s Situation, with Alibi Babbitt’s Situation:  Babbitt’s Situation Cabot’s Situation:  Cabot’s Situation The Big Picture:  The Big Picture New Facts Come In:  New Facts Come In Deciding How to Resolve the Conflict:  Deciding How to Resolve the Conflict Abduction:  Abduction Examples: infection  fever measles  spots raining  wetsidewalks If given: fever, can we conclude infection? spots, can we conclude measles? wetsidewalks, can we conclude raining? Uncertainty and Fuzziness:  Uncertainty and Fuzziness Degrees of truth John is tall. John is very tall. Probability of truth John is in Austin (p = .6) Coin is heads (p = .5) Certainty of belief John is in Austin (c = .2) a wild guess Coin is heads (c = 1) sure it’s 50/50 When Must We Deal with Uncertainty?:  When Must We Deal with Uncertainty? Diagnosis: Observe: spots, fever, headache. What’s wrong with the patient? Observe: clothes are wrinkled and hot. What’s wrong with the dryer? Interpretation: Speech understanding Language understanding Image understanding Data interpretation Planning: If I turn the steering wheel, where will the car go? Probabilistic Reasoning:  Probabilistic Reasoning P(strep) = x (the probability that a random person has strep right now) P(staph) = y (similar) Suppose that we can use the same drug in either case, so we want to know P(strep  staph) = Probabilistic Reasoning:  Probabilistic Reasoning P(strep) = x (the probability that a random person has strep right now) P(staph) = y (similar) Suppose that we can use the same drug in either case, so we want to know P(strep  staph) = P(strep) + P(staph) - P(strep  staph) Probabilistic ReasoningSuppose There are Three Factors:  Probabilistic Reasoning Suppose There are Three Factors P(a  b  c) = P(a) + P(b) + P(c) - P(a  b) - P(a  c) - P(b  c) +P(a  b  c) P(a  b  c) = P(a  b  c) - P(a) - P(b) - P(c) + P(a  b) + P(a  c) + P(b  c) Conditional Probability:  Conditional Probability P(measles  spots) = P(measles | spots) P(spots) definition P(measles  spots) = P(spots | measles) P(measles) P(measles | spots) = P(measles  spots) definition P(spots) P(measles | spots) = P(spots | measles)  P(measles) Bayes Rule P(spots) Examples from Diagnosis and Interpretation:  Examples from Diagnosis and Interpretation P(measles | spots) = P(spots | measles)  P(measles) P(spots) P(word x | sound y) = P(sound y | word x)  P(word x) P(sound y) Word = Argmax(P(sound y | word x)  P(word x)) x Naïve Bayes Classifier:  Naïve Bayes Classifier What if Multiple Observations Are Available? P(measles | spots  fever) = P(spots  fever | measles)  P(measles) P(spots  fever) Assume spots and fever are independent: = P(spots  fever | measles)  P(measles) P(spots  fever) = P(spots|measles)  P(fever | measles)  P(measles) P(spots)  P(fever) Disease = Argmax(P(spots|x)  P(fever |x)  P(x) ) x Not Quite So Naïve Bayes Classifier:  Not Quite So Naïve Bayes Classifier Comparing chicken pox (pox) to measles: P(measles | spots  fever) = P(spots  fever | measles)  P(measles) P(spots  fever) Assume spots and fever are independent given measles or pox and measles and pox are independent: = P(spots|measles)  P(fever | measles)  P(measles) P(spots  fever) = P(spots|measles)  P(fever | measles)  P(measles) P(spots|measles)*P(fever|measles)*P(measles) + P(spots|pox)* P(fever|pox)*P(pox) Disease = Argmax(P(spots|x)  P(fever |x)  P(x) ) x Learning Naïve Bayes Classification:  Learning Naïve Bayes Classification An important aspect of naïve Bayes classification is that a classifier can be learned. Where do numbers like p(spots | measles) come from? Answer: Various ad hoc Approaches:  Various ad hoc Approaches Unfortunately, it often happens that we don’t have all the joint probabilities required to compute true probabilities for our conclusions. So a variety of approximate methods are used. http://www.expertise2go.com/webesie/tutorials/Inference/Confidence1.htm

Add a comment

Related presentations

Related pages

JaideeExpertSystems - Ace Recommendation Platform - 1

Ch90-ExtensionsToFOPC; lecture02 Rule-based expert systems a73 Introduction, or what is knowledge? a73 Rules as a knowledge representation technique a73 ...
Read more

ch14 - Ace Recommendation Platform - 5

5 Office Automation Systems: Computer systems, such as word processing, voice mail, ...
Read more

pols374_intro_lecture - Ace Recommendation Platform - 15

GLOBAL POLITICS introduction to the course thinking/theory and practice " gramsci (1891-1937) told us that “theory” and “practice ...
Read more

560 - Ace Recommendation Platform - 5

5appeared in the early 1970s, were often called “expert systems” because either the domain knowledge they had was a direct encoding of the ...
Read more

003.Ch10-semantic-networks-logical-reasoning-systems - Ace ...

Ch90-ExtensionsToFOPC Extensions to FOL ; ker03a.draft provides knowledge sharing, context reasoning, and privacy protection supports for pervasive context ...
Read more

ch14 - Ace Recommendation Platform - 2

2Knowledge Management in the Organization Information management: The process of systematically and ...
Read more

003.Ch10-semantic-networks-logical-reasoning-systems - Ace ...

Related Contents; 003.Ch10-semantic-networks-logical-reasoning-systems Logical Reasoning Systems Material adopted from slides and notes by Yun Peng, UMBC ...
Read more

Intelligent Agents - University of Texas at Austin

Title: Intelligent Agents Author: Elaine Rich Last modified by: Elaine A. Rich Created Date: 1/19/2004 7:44:10 PM Document presentation format: On-screen Show
Read more