Four broad approaches to knowledge representation, in increasing expressiveness: 1. SIMPLE RELATIONAL KNOWLEDGE Attributes and values in tables, as in the previous topic. ✔ trivial to store and query ✘ almost no inferential capability 2. INHERITABLE KNOWLEDGE A class hierarchy with property inheritance — semantic nets and frames. ✔ compact: shared properties stored once ✔ inheritance is a genuine inference mechanism ✘ weak at anything other than taxonomic reasoning; cannot express disjunction, negation or quantification cleanly 3. INFERENTIAL KNOWLEDGE Formal logic — propositional and first-order predicate logic — with sound inference procedures. ✔ precise semantics, provable conclusions ✔ can express quantification, negation, disjunction ✘ everything must be certain; hard to represent defaults and likelihood ✘ inference can be intractable or undecidable 4. PROCEDURAL KNOWLEDGE Knowledge encoded as procedures — production rules, or code. IF the patient has a fever AND a rash THEN consider measles with certainty 0.7 ✔ directly executable, and efficient ✔ naturally expresses heuristics and how-to knowledge ✘ knowledge is embedded in control flow, so it is harder to inspect, modify and reuse than declarative knowledge THE DECLARATIVE vs PROCEDURAL TENSION runs through all of KR and gets its own topic in ACtE0904. In one line: DECLARATIVE knowledge says WHAT IS TRUE and is easy to modify and reason about; PROCEDURAL knowledge says HOW TO DO IT and is efficient but opaque.

FIVE STANDARD ISSUES that any representation scheme must address. These are the examinable list. 1. IMPORTANT ATTRIBUTES Are there attributes that occur in so many kinds of object that they deserve special treatment? THE ANSWER: yes — `instance` and `isa`, which support class membership and class inclusion, and hence inheritance. Almost every representation scheme provides them explicitly, because inheritance is the most-used inference. 2. RELATIONSHIPS AMONG ATTRIBUTES Attributes are not independent, and four relationships between them recur: INVERSES if A is the parent of B, then B is the child of A. Store once and derive the other, or store both and risk them disagreeing. EXISTENCE IN AN ISA HIERARCHY attributes themselves form hierarchies: `height` is a kind of `physical measurement`, so a query about measurements should find heights. TECHNIQUES FOR REASONING ABOUT VALUES constraints on values: a height must be positive; an age must be less than the age of a parent. Reasoning uses these to detect errors and to infer bounds. SINGLE-VALUED ATTRIBUTES some attributes take exactly one value — a person has one date of birth. Knowing this permits the system to REPLACE rather than accumulate values, and to detect a contradiction when two are asserted. 3. CHOOSING THE GRANULARITY OF REPRESENTATION At what level of detail should knowledge be represented? THE TRADE-OFF, made concrete: COARSE: spotted(John, Sue) — compact, but you cannot ask what John spotted her WITH, or WHEN FINE: a `spotting` event with agent, object, instrument, time and location slots — answers more questions, and requires far more knowledge to be entered and far more inference to use WORKED: "John spotted Sue." To answer "did John see Sue?" a fine-grained representation must know that spotting is a kind of seeing, so the granularity decision determines what inference rules are needed. THERE IS NO UNIVERSALLY RIGHT LEVEL — it depends on the questions the system must answer, which is why the requirements must precede the ontology. 4. REPRESENTING SETS OF OBJECTS Two ways, with different consequences: EXTENSIONALLY list the members: {Ram, Sita, Gita} INTENSIONALLY give a rule: {x : student(x) ∧ year(x)=3} THE IMPORTANT REASON TO REPRESENT SETS AT ALL: some properties belong to the SET rather than to its members. "There are 26 million people in Nepal" — no individual person has the property of being 26 million. "The average height is 5-6" — no individual is the average. CONFUSING SET PROPERTIES WITH MEMBER PROPERTIES is a real modelling error, and it is the reason inheritance must not pass every property downward. 5. FINDING THE RIGHT STRUCTURES AS NEEDED Given a large knowledge base, how do you find the relevant part? Three sub-problems: · how to select an initial structure to consider — an INDEXING problem · how to fill in the details from the current situation · how to find a BETTER structure if the chosen one turns out not to fit · what to do if no structure fits at all THIS IS THE INFERENTIAL EFFICIENCY PROPERTY from the previous topic, seen as a concrete engineering problem. A knowledge base of a million facts is useless without indexing, however adequate its logic. A SIXTH ISSUE, often listed: HANDLING UNCERTAINTY AND DEFAULTS. Most real knowledge is qualified — "usually", "probably", "unless" — and classical logic has no room for it. The options: DEFAULT REASONING and non-monotonic logic CERTAINTY FACTORS (as in MYCIN) FUZZY LOGIC (degrees of truth, ACtE0905) PROBABILITY and Bayesian networks (later in this section) Of these, probability has the firmest foundations, which is why the field moved toward it.

THE FRAME PROBLEM — the deepest issue in this topic, and worth understanding rather than memorising. When an action occurs, MOST OF THE WORLD DOES NOT CHANGE. Moving a block does not alter the colour of the walls, the day of the week, or the positions of the other blocks. But a logical representation must SAY SO, because nothing is implicit in logic. THE SIZE OF THE PROBLEM: with n facts and m actions, stating what does NOT change requires up to n×m FRAME AXIOMS — statements of the form "if P was true and action A occurs and A is not about P, then P remains true". WORKED: a modest blocks world with 20 facts and 5 actions needs up to 100 frame axioms to say nothing happened, on top of the 5 axioms saying what did. THE BOOKKEEPING DOMINATES THE CONTENT. THE STANDARD RESPONSES: STRIPS-STYLE REPRESENTATION: state only what an action ADDS and DELETES, and assume everything else persists. This is the STRIPS ASSUMPTION, and it is what makes automated planning practical. SUCCESSOR-STATE AXIOMS: for each fluent, state exactly the conditions under which it becomes true or false. NON-MONOTONIC LOGIC: assume persistence by default. RELATED PROBLEMS with the same flavour: THE QUALIFICATION PROBLEM no action's preconditions can be completely enumerated. "Turning the key starts the car" — unless the battery is flat, the tank is empty, the starter has failed, there is a potato in the exhaust… The list has no natural end. THE RAMIFICATION PROBLEM the indirect consequences of an action. Moving a block moves whatever is on it, and stating every such consequence is as hopeless as stating every precondition. WHY THESE MATTER BEYOND AI: they are the reason common-sense reasoning resisted symbolic AI for decades. Humans handle them effortlessly and cannot say how, which is the Moravec paradox from the AI concepts topic appearing in logical form. CHOOSING A REPRESENTATION — the practical decision procedure: WHAT THE KNOWLEDGE IS LIKE USE ───────────────────────────────────────────────────────────── a taxonomy with inherited a semantic net or frames properties procedures and heuristics production rules facts requiring provable propositional or conclusions first-order logic quantified statements over FIRST-ORDER logic many objects (propositional cannot) uncertain or statistical Bayesian networks knowledge vague, graded predicates fuzzy logic ("tall", "warm") knowledge learned from data a learned model — no explicit representation ───────────────────────────────────────────────────────────── AND THE ANSWER MOST REAL SYSTEMS GIVE: SEVERAL AT ONCE. A medical system may hold a disease taxonomy as a hierarchy, its diagnostic knowledge as rules, its uncertainty as probabilities, and its image interpretation as a neural network. THE QUESTION IS NOT "WHICH FORMALISM" BUT "WHICH FORMALISM FOR WHICH KIND OF KNOWLEDGE", and the four properties of the previous topic are the criteria for each choice.