KNOWLEDGE REPRESENTATION (KR) is concerned with how to encode knowledge about the world in a form a computer can use to solve problems. THE CENTRAL DISTINCTION — two levels, and the mappings between them: FACTS the truths in the world we want to represent — what is actually the case REPRESENTATIONS the formal structures in which facts are encoded, and which the program manipulates THE TWO ARE NOT THE SAME THING, and the whole subject exists because moving between them is lossy and difficult. THE MAPPINGS: REPRESENTATION MAPPING from facts to representations FORWARD MAPPING the same direction, going from the world into the formalism BACKWARD MAPPING from representations back to facts THE FUNDAMENTAL DIAGRAM: ┌──────────────┐ representation ┌──────────────────┐ │ FACTS │ ─────mapping──────▶ │ INTERNAL │ │ (the world) │ ◀────────────────── │ REPRESENTATIONS │ └──────┬───────┘ backward mapping └────────┬─────────┘ │ │ reasoning in computer programs the world manipulate these │ │ ▼ ▼ ┌──────────────┐ ┌──────────────────┐ │ NEW FACTS │ ◀────────────────── │ NEW │ │ │ backward mapping │ REPRESENTATIONS │ └──────────────┘ └──────────────────┘ READ THE DIAGRAM AS A REQUIREMENT: the program manipulates representations, producing new representations; the backward mapping must turn those into facts that are ACTUALLY TRUE in the world. If the mapping and the manipulation do not correspond, the program reasons validly and concludes falsehoods. THE THREE THINGS THAT CAN GO WRONG: 1. THE FORWARD MAPPING LOSES INFORMATION. Natural language is richer than any formalism, so some of the fact does not survive encoding. 2. THE BACKWARD MAPPING IS NOT WELL DEFINED. Several facts may map to the same representation, so the representation cannot be decoded uniquely. 3. THE MAPPINGS ARE NOT INVERSES. This is the interesting case, and the standard illustration: THE CLASSIC EXAMPLE — the mapping is many-to-one and lossy: FACT "All dogs have tails" REPRESENTATION ∀x dog(x) → hastail(x) Now apply a valid inference to conclude hastail(fido) BACKWARD MAPPING "Fido has a tail" That worked. But consider: FACT "Spot is a dog" and "All dogs are mammals" REPRESENTATION dog(Spot), ∀x dog(x) → mammal(x) VALID INFERENCE mammal(Spot) Also fine. THE PROBLEM ARISES WITH FACTS THAT RESIST ENCODING: FACT "The dog is probably in the garden" There is no straightforward first-order sentence for "probably", so the encoder must either drop the qualification — asserting something stronger than the fact — or move to a formalism with probabilities. ENCODING A FACT MORE STRONGLY THAN IT IS TRUE IS THE COMMONEST KR ERROR, and it produces confident wrong conclusions rather than honest uncertainty. KNOWLEDGE vs DATA — a distinction worth being able to state: DATA raw facts and figures, with no interpretation INFORMATION data with context and meaning KNOWLEDGE information plus the ability to USE it — relationships, rules and the capacity to infer new information from it A database stores data; a knowledge base stores knowledge, and the difference is that a knowledge base can answer questions nobody explicitly stored an answer to.

A GOOD KNOWLEDGE REPRESENTATION SYSTEM must have four properties. These are the standard exam enumeration. 1. REPRESENTATIONAL ADEQUACY The ability to represent ALL THE KINDS OF KNOWLEDGE needed in the domain. WHERE IT FAILS: propositional logic cannot express "every student has a supervisor" without one sentence per student; it lacks the machinery for quantification, so it is representationally inadequate for that knowledge. 2. INFERENTIAL ADEQUACY The ability to MANIPULATE the representational structures to derive new structures corresponding to new knowledge inferred from old. WHERE IT FAILS: a semantic net is good at inheritance and poor at expressing "either A or B but not both", so it cannot infer what a logic could. 3. INFERENTIAL EFFICIENCY The ability to incorporate into the knowledge structure additional information (GUIDES, or metadata) that can be used to FOCUS the inference mechanism in the most promising directions. THIS IS THE PRACTICAL PROPERTY: a formalism in which every query requires searching the whole knowledge base is inferentially adequate and useless. Indexing, ordering and relevance information are what make it usable. 4. ACQUISITIONAL EFFICIENCY The ability to ACQUIRE NEW KNOWLEDGE easily, ideally automatically rather than by human intervention. WHERE IT FAILS: this is the KNOWLEDGE ACQUISITION BOTTLENECK that ended the expert-system boom — hand-encoding knowledge is so laborious that systems could not be kept current, which the AI history topic identified as a cause of the second AI winter. THE UNCOMFORTABLE FACT: NO SINGLE SYSTEM OPTIMISES ALL FOUR. A more expressive formalism (better representational and inferential adequacy) is harder to reason with efficiently and harder to populate. This is the same EXPRESSIVENESS-versus-TRACTABILITY trade-off met in the agent structure topic's atomic/factored/structured progression, and it recurs through the whole of knowledge representation. THE PRACTICAL CONSEQUENCE: real systems use SEVERAL representations together — a taxonomy for inheritance, rules for procedures, probabilities for uncertainty — chosen per kind of knowledge rather than one formalism for everything. KINDS OF KNOWLEDGE that must be represented, because the list tells you what a formalism has to cope with: DECLARATIVE facts about the world: "Kathmandu is the capital of Nepal" PROCEDURAL how to do things: the steps to solve a quadratic META-KNOWLEDGE knowledge about knowledge: which rules are reliable, what the system does not know HEURISTIC rules of thumb from experience, not guaranteed correct STRUCTURAL relationships between concepts: taxonomies, part-whole hierarchies RELATIONAL simple facts linking entities ALSO: TACIT knowledge — what an expert knows but cannot articulate — which is precisely what cannot be captured declaratively, and is why knowledge acquisition needs the elicitation techniques of the software requirements unit rather than an interview.

THE SIMPLEST REPRESENTATION — a TABLE of attributes: Player Height Weight Bats-Throws ──────────────────────────────────────────── Hank Aaron 6-0 180 Right-Right Willie Mays 5-10 170 Right-Right Babe Ruth 6-2 215 Left-Left Ty Cobb 6-1 175 Left-Right ──────────────────────────────────────────── · WEAK INFERENTIAL CAPABILITY: it can answer "who weighs most" only if a program is written to scan the column. Nothing is inferred; everything is looked up. · but it PROVIDES THE KNOWLEDGE ON WHICH more powerful mechanisms operate, which is why it is where a knowledge base starts. INHERITABLE KNOWLEDGE — the first genuinely inferential step. Organise knowledge into a CLASS HIERARCHY (an ISA hierarchy) and allow properties to be INHERITED down it. Each node is an object or a class; each arc is a relation. Person ├── isa ── Adult-Male │ ├── isa ── Baseball-Player │ │ ├── instance ── Chicago-Cubs │ │ └── instance ── Pee-Wee-Reese │ └── height: 5-10 └── handed: Right PROPERTY VALUES are attached where they are most general: Person.handed = Right (the default) Adult-Male.height = 5-10 (a default average) Baseball-Player.batting-average = 0.252 Pee-Wee-Reese.batting-average = 0.309 (overrides) THE INHERITANCE ALGORITHM — worth knowing precisely: To retrieve a value for attribute A of an instance object O: 1. Find O in the knowledge base. 2. If there is a value for attribute A, report it. 3. Otherwise, see if there is a value for the attribute `instance`. If not, fail. 4. Otherwise, move to that node and go to step 2. 5. Repeat, following `isa` links, until a value is found or the hierarchy is exhausted. WORKED: what is Pee-Wee-Reese's height? Reese has no `height` → follow `instance` to Baseball-Player → no `height` → follow `isa` to Adult-Male → height = 5-10. ANSWER: 5-10, INFERRED rather than stored. A KNOWLEDGE BASE OF n OBJECTS EACH WITH m ATTRIBUTES WOULD NEED n×m STORED VALUES; inheritance stores the shared ones once. For 1,000 baseball players sharing 20 class-level properties, that is 20,000 values replaced by 20. DEFAULT REASONING AND ITS PROBLEM — the honest complication: Inheritance gives DEFAULTS, which can be overridden. That is what makes it useful ("birds fly" with penguins as an exception) and what makes it NON-MONOTONIC: adding the fact that Tweety is a penguin RETRACTS the previously derived conclusion that Tweety flies. CLASSICAL LOGIC IS MONOTONIC — adding premises never invalidates a conclusion — so default inheritance is not expressible in ordinary first-order logic, and needs non-monotonic formalisms. THE MULTIPLE-INHERITANCE PROBLEM: if Nixon is both a Quaker (pacifist by default) and a Republican (not pacifist by default), inheritance gives contradictory answers depending on which link is followed. This is the NIXON DIAMOND, and there is no purely syntactic resolution — the system must be told which default has priority. THE PROGRESSION OF THIS SECTION, stated once so the later topics have a frame: relational tables → inheritable hierarchies (semantic nets, frames) → propositional logic → first-order logic → probabilistic representations (Bayes, belief networks) Each step adds expressiveness and costs tractability, which is the trade-off the four properties above make explicit.