DOC PREVIEW
UMBC CMCS 471 - Knowledge Representation

This preview shows page 1-2-14-15-30-31 out of 31 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Knowledge RepresentationIntroductionProduction Systems (forward-chaining version)Three Basic Components of PSSlide 5Slide 6Basic Inference ProcedureConflict Resolution StrategiesSlide 10Slide 11Default ReasoningSlide 13Other IssuesComparing PS and FOLSemantic NetworksSlide 17Slide 18Nodes and ArcsReificationInference by associationISA hierarchyIndividuals and ClassesInference by InheritanceMultiple inheritanceNixon DiamondSlide 27Exceptions in ISA hierarchyFrom Semantic Nets to FramesFacetsSlide 31Slide 321Knowledge Knowledge RepresentationRepresentationChapter 102Introduction•Real knowledge representation and reasoning systems come in several major varieties.•They all based on FOL but departing from it in different ways•They differ in their intended use, degree of formal semantics, expressive power, practical considerations, features, limitations, etc.•Some major families of reasoning systems are–Theorem provers–Logic programming languages–Rule-based or production systems–Semantic networks–Frame-based representation languages –Description logics–Databases (deductive, relational, object-oriented, etc.)–Constraint reasoning systems–Truth maintenance systems3Production Systems (forward-chaining version) •The notion of a “production system” was invented in 1943 by Post to describe re-write rules for symbol strings•Used as the basis for many rule-based expert systems •Most widely used KB formulation in practice•A production is a rule of the form:C1, C2, … Cn => A1 A2 …AmLeft hand side (LHS)Conditions/antecedentsRight hand side (RHS)Conclusion/consequenceCondition which musthold before the rulecan be appliedActions to be performedor conclusions to be drawnwhen the rule is applied4Three Basic Components of PS•Rule Base–Unordered set of user-defined "if-then" rules.–Form of rules: if P1, ..., Pm then A1, ..., An –the Pi’s are conditions (often facts) that determine when rule is applicable. –Actions can add or delete facts from the Working Memory.–Example rule (in CLIPS format) (defrule determine-gas-level (working-state engine does-not-start)(rotation-state engine rotates) (maintenance-state engine recent) => (assert (repair "Add gas.")))5•Working Memory (WM) –A set of "facts“, represented as literals, defining what are known to be true about the world –Often in the form of “flat tuples” (similar to predicates with out functional terms), e.g., (age Fred 45)–WM initially contains case specific data (not those facts that are always true in the world)–Inference may add/delete fact from WM–WM will be cleared when a case is finished6•Inference Engine –Procedure for inferring changes (additions and deletions) to Working Memory.–Can be both forward and backward chaining–Usually a cycle of three phases: match, conflict resolution, and action, (in that order)7Basic Inference ProcedureWhile changes are made to Working Memory do: •Match the current WM with the rule-base –Construct the Conflict Set -- the set of all possible (rule, facts) pairs where rule is from the rule-base, facts from WM that unify with the conditional part (i.e., LHS) of the rule.•Conflict Resolution: Instead of trying all applicable rules in the Conflict set, select one from the Conflict Set for execution. (depth-first)•Action/fire: Execute the actions associated with the conclusion part of the selected rule, after making variable substitutions determined by unification during match phase•Stop when conflict resolution fails to returns any (rule, facts) pair9Conflict Resolution Strategies•Refraction–A rule can only be used once with the same set of facts in WM. This strategy prevents firing a single rule with the same facts over and over again (avoiding loops)•Recency–Use rules that match the facts that were added most recently to WM, providing a kind of "focus of attention" strategy.•Specificity–Use the most specific rule, –If one rule's LHS is a superset of the LHS of a second rule, then the first one is more specific–If one rule's LHS implies the LHS of a second rule, then the first one is more specific•Explicit priorities–E.g., select rules by their pre-defined order/priority•Precedence of strategies10•Example–R1: P(x) => Q(x); R2: Q(y) => S(y); WM = {P(a), P(b)}conflict set: {(R1, P(a)), (R1, P(b))}by order: apply R1 on P(a); {Q(a), P(a), P(b)} conflict set: {(R2, Q(a)), (R1, P(a)), (R1, P(b))}by recency: apply R2 on Q(a) {S(a), Q(a), P(a), P(b)}conflict set: {(R2, Q(a)), (R1, P(a)), (R1, P(b))}by refraction, apply R1 on P(b): {Q(b), S(a), Q(a), P(a), P(b)}conflict set: {(R2, Q(b)), (R2, Q(a)), (R1, P(a)), (R1, P(b))}by recency, apply R2 on P(b): {S(b), Q(b), S(a), Q(a), P(a), P(b)}11•Specificity P(x), Q(x) => R(x) is more specific than P(x) => S(x)R1: bird(x) => fly(x) WM={bird(tweedy), penguin(tweedy)} R2: penguin(z) => bird(z)R3: penguin(y) => ~fly(y)R3 is more specific than R1 because according to R2, penguin(x) implies bird(x)12Default Reasoning•Definition–Reasoning that draws a plausible inference on the basis of less than conclusive evidence in the absence of information to the contrary–If WM = {bird(tweedy)}, then by default, we can conclude that fly(tweedy)–When also know that penguin(tweedy), then we should change the conclusion to ~fly(tweedy)–Bird(x) => fly(x) is a default rule (true in general, in most cases, almost but not necessarily always)•Default reasoning is thus non-monotonic–A logic is monotonic if true sentences remain to be true after new sentences are added into the system–FOL is monotonic13Default Reasoning•Formal study of default reasons: –default logic (Reiter), nonmonotonic logic (McDermott), circumscription (McCarthy)–one conclusion: default reasoning is totally undecidable•Production system can handle simple default reasoning–By specificity: default rules are often less specific–By rule priority: put default rules at the bottom of the rule base–Retract default conclusion (e.g., fly(tweedy)) is complicated14Other Issues•PS can work in backward chaining mode–Match RHS with the goal statement to generate subgoals–Mycin: an expert system for diagnosing blood infectious diseases•Expert system sell–A rule-based system with empty rule base–Contains data structure, inference procedures, AND user interface to help encode domain knowledge–Emycin


View Full Document

UMBC CMCS 471 - Knowledge Representation

Download Knowledge Representation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Knowledge Representation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Knowledge Representation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?