A complete tutorial on knowledge representation issues, mapping, all major approaches, and fundamental representation problems — with worked examples and diagrams
A calculator can multiply 7,463 × 9,821 faster than any human — yet it knows nothing about why you need that product. A chess program can evaluate millions of positions per second — yet it has no idea that chess is a game. Knowledge is what distinguishes intelligent behaviour from mere computation. To build systems that reason, plan, and explain, we must first answer a deceptively difficult question: how do we represent what a system "knows" in a form a computer can use?
This question drives the field of Knowledge Representation and Reasoning (KR&R) — one of the oldest and most fundamental sub-fields of AI. Without good knowledge representation, expert systems cannot diagnose diseases, natural language systems cannot understand sentences, and planning systems cannot schedule factories.
Not all knowledge is the same. AI systems must handle several distinct categories, each requiring different representational tools. This classification is a commonly tested definition.
| Type | Description | Example (Medical Domain) | Representation |
|---|---|---|---|
| Declarative | Facts about the world — "what is" | "Fever is a symptom of infection" | Logic, frames, semantic networks |
| Procedural | How to do something — step-by-step | "To diagnose: first take temperature, then..." | Production rules, scripts |
| Heuristic | Rules of thumb — expert shortcuts | "If patient is elderly, suspect pneumonia first" | IF-THEN rules, weighted rules |
| Meta-knowledge | Knowledge about knowledge itself | "Blood culture results are more reliable than symptoms alone" | Confidence weights, certainty factors |
| Structural | How concepts relate to each other | "Pneumonia is a subtype of lung disease" | Ontologies, class hierarchies |
| Common-sense | Implicit world knowledge humans take for granted | "A dead patient cannot be treated" | Difficult — requires large ontologies (CYC) |
Proposed by Brian Cantwell Smith (1985): "Any mechanically embodied intelligent process will be comprised of structural ingredients that: (a) we as external observers naturally take to represent a propositional account of the domain the overall process is engaged in, and (b) that independent of such external semantic attribution, play a formal but causal and essential role in engendering the behaviour that constitutes the intelligence."
In plain terms: for a machine to behave intelligently, there must be internal structures we can interpret as representing knowledge about the world, and these structures must causally drive the intelligent behaviour. Intelligence requires explicit knowledge — not just programmed responses.
We use a simplified medical diagnosis domain throughout. A doctor must diagnose a patient's illness from symptoms and tests. This domain is rich enough to illustrate all KR approaches yet compact enough for worked examples.
| Entity | Known Facts |
|---|---|
| Patient: John | Age 45, male, smoker. Symptoms: fever (38.5°C), cough (productive), chest pain, shortness of breath. Duration: 3 days. |
| Test Results | WBC count: 14,000 (high). Chest X-ray: consolidation in right lower lobe. Sputum culture: Streptococcus pneumoniae. |
| Target Diagnosis | Bacterial pneumonia (community-acquired). Treatment: amoxicillin 500mg × 7 days. |
| Challenge | How do we encode the doctor's expertise so a computer can replicate this reasoning — and explain it? |
Each KR approach in Sections 3–4 will represent the same knowledge about this patient in a different formalism. Compare how each handles the same facts differently.
Building a usable knowledge representation system requires tackling five fundamental issues. These issues motivate every design decision in every KR formalism we study.
Every KR system must navigate a fundamental trade-off: expressiveness vs. computational tractability. More expressive languages (full first-order logic) can represent anything — but reasoning may be undecidable or impractically slow. Weaker languages (propositional logic) support fast, complete reasoning — but cannot express many real-world facts. This trade-off shapes every KR decision in this unit.
Building on the types of knowledge from Section 1, we now ask: how do we translate knowledge about the world into a form a computer can manipulate? This is the problem of representational mapping — choosing a formal structure that faithfully mirrors the relevant aspects of the world while remaining computationally tractable.
A knowledge representation is not just a storage format. It is a surrogate for the real world: a substitute for things and relationships that lets the system reason about them without direct access to reality. Every design choice for this surrogate has profound consequences for what the system can and cannot know.
A representational mapping is a correspondence between:
The mapping must preserve the relevant structure: if "A is related to B" in the real world, the representing structure must capture this relationship so that any conclusion the system draws about the representing world corresponds to a true conclusion about the real world.
Not every formal language makes a good KR language. A good KR language needs four properties, defined by Brachman & Levesque (1985). These appear frequently in exam questions.
| Property | Definition | Implication if Missing |
|---|---|---|
| Representational Adequacy | Can represent all the knowledge needed for the task | Some facts cannot be stored — system gives wrong or no answers |
| Inferential Adequacy | Reasoning can derive all entailed conclusions | Valid conclusions are missed (incomplete reasoner) |
| Inferential Efficiency | Reasoning is computationally tractable in practice | System is too slow to use — answers arrive hours/days later |
| Acquisitional Efficiency | New knowledge can be added easily without side effects | Knowledge base becomes unmaintainable — expert time consumed |
Every KR scheme makes implicit ontological commitments — assumptions about the kinds of things that exist in the world. Choosing a representation is choosing what kinds of entities you believe the world contains.
| Language | Ontological Commitment — What Exists | Example Entities |
|---|---|---|
| Propositional Logic | Facts — true or false propositions | JohnHasFever, IsPneumonia |
| First-Order Logic | Objects, their properties, and relations between them | John, Pneumonia, hasFever(John) |
| Higher-Order Logic | Objects + relations + relations over relations | Believes(Doctor, Diagnosis(John, Pneumonia)) |
| Probabilistic Logic | Objects + degrees of belief (probabilities) | P(Pneumonia | Fever, Cough) = 0.72 |
| Temporal Logic | Objects + facts + time — things can change | HasFever(John, t) ∧ t > Day3 → WorseSituation |
Davis, Shrobe & Szolovits (1993) identified five roles that any KR scheme plays simultaneously. Understanding these roles explains why KR is hard — a design choice that helps one role often hurts another.
A representational mapping is only useful if it is semantically faithful — conclusions drawn in the formal system must correspond to true conclusions in the real world. A system that concludes "John has malaria" because the formal encoding was wrong is worse than useless. This faithfulness requirement is why knowledge engineering (building knowledge bases) is more art than science.
Logic was the first formal language proposed for AI knowledge representation, and it remains the gold standard for precision and rigour. A logical knowledge base is a set of sentences in a formal language; a logical inference procedure derives new sentences guaranteed to be true whenever the premises are. Logic gives us both expressiveness (what can be said) and soundness (what can safely be derived).
Two levels of logic dominate AI: Propositional Logic (simple but limited) and First-Order Predicate Logic (powerful and expressive). We also touch on Horn Clauses — the efficient subset used in Prolog and expert systems.
Propositional logic deals with propositions — statements that are either true or false. Complex statements are built from atomic propositions using connectives: ¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (iff).
A model is a truth-value assignment to all propositions. A sentence is valid if true in all models, satisfiable if true in some model, and unsatisfiable if true in no model.
-- Facts about John (given) --
HasFever -- John has fever
HasCough -- John has cough
HasChestPain -- John has chest pain
XRayPositive -- consolidation on X-ray
-- Rules (domain knowledge) --
HasFever ∧ HasCough ∧ XRayPositive → SuspectPneumonia
SuspectPneumonia ∧ HasChestPain → DiagnosePneumonia
DiagnosePneumonia → TreatWithAntibiotics| Step | From | Rule Applied | Derived |
|---|---|---|---|
| 1 | HasFever ∧ HasCough ∧ XRayPositive | Rule 1 | SuspectPneumonia ✓ |
| 2 | SuspectPneumonia ∧ HasChestPain | Rule 2 | DiagnosePneumonia ✓ |
| 3 | DiagnosePneumonia | Rule 3 | TreatWithAntibiotics ✓ |
This knowledge base only works for John specifically. To represent the same rules for patient Mary, we need entirely new propositions: MaryHasFever, MaryHasCough, etc. With 1,000 patients, the KB grows 1,000×. There is no way to express "for all patients..." — we need First-Order Logic.
FOL extends propositional logic with objects (constants, variables), predicates (relations over objects), functions, and quantifiers (∀ universal, ∃ existential). These additions make FOL dramatically more expressive — capable of representing most human knowledge.
-- Object sorts (types) --
Patient(john) -- john is a patient
Disease(pneumonia) -- pneumonia is a disease
Symptom(fever) -- fever is a symptom
Drug(amoxicillin) -- amoxicillin is a drugHasSymptom(john, fever)
HasSymptom(john, cough)
HasSymptom(john, chest_pain)
TestResult(john, xray, positive)
Age(john, 45)
Smoker(john)-- Rule 1: Pneumonia diagnostic criteria --
∀x [Patient(x) ∧ HasSymptom(x, fever) ∧ HasSymptom(x, cough)
∧ TestResult(x, xray, positive)
→ SuspectDisease(x, pneumonia)]
-- Rule 2: Confirm diagnosis with chest pain --
∀x [SuspectDisease(x, pneumonia) ∧ HasSymptom(x, chest_pain)
→ Diagnosis(x, pneumonia)]
-- Rule 3: Treatment protocol --
∀x ∀d [Diagnosis(x, d) ∧ BacterialDisease(d)
→ Prescribe(x, amoxicillin)]
-- Fact: pneumonia is bacterial --
BacterialDisease(pneumonia)
-- Rule 4: Elderly patients need extra care (quantified!) --
∀x [Patient(x) ∧ Age(x, ?a) ∧ ?a > 65 ∧ Diagnosis(x, pneumonia)
→ HighRisk(x)]Applying Rule 1 with x = john: the system unifies the variable x with the constant john, checks all conditions against the KB, and derives SuspectDisease(john, pneumonia). This works for ANY patient — Mary, Bob, Alice — using the same rules.
One FOL rule handles all patients. Add 1,000 patients — the rules stay exactly the same. The KB grows only with new patient facts, not new rules. Quantification is the key power of FOL.
| Feature | Propositional Logic | First-Order Logic (FOL) |
|---|---|---|
| Variables | ❌ None — only named propositions | ✅ Variables ranging over objects |
| Quantifiers | ❌ None | ✅ ∀ and ∃ |
| Objects & relations | ❌ No objects — only truth values | ✅ Objects, predicates, functions |
| Expressiveness | Limited — grows linearly with domain | High — one rule covers all objects |
| Decidability | ✅ Decidable (exponential) | ❌ Semi-decidable (can loop forever) |
| Inference speed | Fast (SAT solvers, resolution) | Slower (unification, theorem proving) |
| Practical use | Hardware verification, simple rule engines | Expert systems, ontologies, Prolog, OWL |
A Horn clause is a disjunction of literals with at most one positive literal. Equivalently: B₁ ∧ B₂ ∧ … ∧ Bₙ → H — a conjunction of conditions implies a single head. Horn clauses are a proper subset of FOL that supports efficient reasoning via SLD resolution (used in Prolog).
Advantages: linear-time inference (vs. exponential for full FOL); complete for Horn theories; forms the basis of Prolog and Datalog. Limitation: cannot express disjunctions in the head (you cannot say "diagnosis is either X or Y").
-- Horn clause knowledge base for medical diagnosis --
% Facts (unit clauses — head only)
patient(john).
has_symptom(john, fever).
has_symptom(john, cough).
test_positive(john, xray).
bacterial_disease(pneumonia).
% Rules (definite clauses — body → head)
suspect_pneumonia(X) :-
patient(X),
has_symptom(X, fever),
has_symptom(X, cough),
test_positive(X, xray).
diagnose(X, pneumonia) :-
suspect_pneumonia(X).
prescribe(X, amoxicillin) :-
diagnose(X, D),
bacterial_disease(D).
% Query: ?- prescribe(john, What).
% Answer: What = amoxicillin ✓ChronicCough(x) → HasDisease(x, pneumonia) ∨ HasDisease(x, tb). This is a common exam question — remember "at most one positive literal in the head."Logic is precise but verbose — representing a doctor's knowledge about pneumonia in FOL requires dozens of atomic sentences for what a physician grasps intuitively as a unified concept. Structured representations package related knowledge into coherent units that mirror how humans organise knowledge: as networks of related concepts, as stereotyped descriptions, or as templated event sequences.
The four major structured approaches are: Semantic Networks, Frames, Production Rules (IF-THEN), and Scripts. Each offers a different trade-off between expressiveness, naturalness, and computational efficiency.
A semantic network is a directed graph where:
Key relationship types: is-a (class membership — John is-a Patient), kind-of / a-kind-of (AKO) (class hierarchy — Pneumonia kind-of Lung-Disease), has-property, part-of. Inheritance propagates properties along is-a and AKO links.
Inheritance is the key power of semantic networks. John's diagnosis of Pneumonia automatically grants him all properties of Pneumonia (treatment: antibiotics), Lung Disease (organ: lung), and Infectious Disease (cause: pathogen) — without stating each property individually. This dramatically reduces redundancy. But inheritance can be problematic when exceptions exist: "Tweety is a Bird; Birds fly; Tweety is a Penguin; Penguins don't fly." Which rule wins? This is the famous multiple inheritance problem.
A frame is a data structure (like a record or class) that collects all knowledge about a concept or object into a single unit. Each frame has slots (attributes) and fillers (values). Slot values can be: specific values, pointers to other frames, default values (assumed unless overridden), or procedural attachments (code to run when the slot is accessed).
Frames introduced the ideas of inheritance, default values, and procedural attachment that later became core object-oriented programming (OOP) concepts.
FRAME: Disease
name: [STRING]
category: [STRING]
treatment: [Frame: Drug]
severity: default: "moderate"
is-a: Medical-ConditionFRAME: Pneumonia
is-a: Disease, LungDisease, InfectiousDisease
name: "Pneumonia"
symptoms: [fever, productive-cough, chest-pain, dyspnea]
diagnostic-criteria:
- HasSymptom(fever) ∧ HasSymptom(cough)
- XRayResult(consolidation)
treatment: amoxicillin-500mg -- overrides Disease default
duration: default: "7 days"
severity: "moderate-to-severe" -- overrides Disease default
when-filled(diagnosis):
-- procedural attachment: run when diagnosis slot is filled
→ GeneratePrescription(treatment, duration)FRAME: John-Patient
is-a: Patient
name: "John Smith"
age: 45
smoker: true
symptoms: [fever(38.5°C), productive-cough, chest-pain]
test-results: [xray: consolidation, WBC: 14000]
diagnosis: Pneumonia -- filled by inference; triggers procedural attachment
prescription: amoxicillin-500mg × 7 days -- generated automaticallyWhen diagnosis = Pneumonia is filled in John's frame: (1) John inherits all Pneumonia slot values. (2) Default values ("7 days", "moderate") are used unless explicitly overridden. (3) The procedural attachment when-filled(diagnosis) automatically triggers GeneratePrescription — producing the prescription without additional rules.
A production rule is an IF-THEN pair: IF <condition> THEN <action>. A production system has three components: a set of production rules (knowledge base), a working memory (current state), and an inference engine (selects and fires rules).
Production rules directly model human expert decision-making and are the basis of most clinical decision support systems, credit scoring systems, and early expert systems like MYCIN.
MYCIN (1976) was the first successful medical expert system, diagnosing bacterial infections. It used production rules with certainty factors (CF) to handle uncertainty. CF ranges from −1 (definitely false) to +1 (definitely true).
-- Rule 1: Suspect bacterial pneumonia --
IF the patient has fever (temp > 38°C)
AND the patient has productive cough
AND chest X-ray shows consolidation
THEN suspect bacterial pneumonia [CF = 0.8]
-- Rule 2: Raise confidence with positive culture --
IF suspect bacterial pneumonia
AND sputum culture positive for Streptococcus pneumoniae
THEN diagnose community-acquired pneumonia [CF = 0.95]
-- Rule 3: Select antibiotic --
IF diagnose community-acquired pneumonia
AND patient is NOT penicillin-allergic
THEN prescribe amoxicillin 500mg three times daily [CF = 0.9]
-- Rule 4: Age-based risk flag --
IF patient age > 65
AND diagnose community-acquired pneumonia
THEN flag as HIGH RISK — consider hospitalisation [CF = 0.85]| Step | Working Memory Contains | Rule Fired | New Fact Added |
|---|---|---|---|
| Init | Fever(38.5°C), ProductiveCough, XRay(+), Culture(S.pneumoniae), Age(45) | — | — |
| 1 | Above facts match Rule 1 conditions | Rule 1 | SuspectBacterialPneumonia [CF=0.8] |
| 2 | SuspectPneumonia + Culture match Rule 2 | Rule 2 | DiagnoseCAP [CF=0.95] |
| 3 | DiagnoseCAP + no allergy match Rule 3 | Rule 3 | PrescribeAmoxicillin [CF=0.9] ✓ |
A script is a structured representation of a stereotyped sequence of events — a template for typical situations. Scripts capture procedural knowledge about how common events typically unfold. They have four components:
| Component | Content |
|---|---|
| Script Name | MEDICAL-CONSULTATION |
| Entry Conditions | Patient is unwell. Patient has appointment. Doctor is available. |
| Roles | Patient (p), Doctor (d), Nurse (n), Receptionist (r) |
| Props | Waiting room, examination table, stethoscope, blood pressure cuff, prescription pad, medical records |
| Scene 1: Arrival | p arrives at clinic → r checks in p → n takes vitals (temp, BP, pulse) → p waits in waiting room |
| Scene 2: Consultation | n calls p → p enters examination room → d greets p → d asks about symptoms → p describes symptoms → d examines p (auscultation, palpation) |
| Scene 3: Diagnosis | d orders tests (X-ray, blood work) → d reviews results → d formulates diagnosis → d explains diagnosis to p |
| Scene 4: Treatment | d writes prescription → d gives follow-up instructions → p leaves clinic → p fills prescription at pharmacy |
| Exit Conditions | Patient has prescription. Patient understands treatment plan. |
| Expected Outcomes | Patient recovers. Condition is monitored. Follow-up scheduled if needed. |
Scripts allow an AI system to fill in missing information. If a story says "John went to the doctor and got amoxicillin," a script-based system knows John probably had to check in, wait, be examined, and receive a diagnosis — even though none of this is stated. Scripts power natural language understanding of stories and are the basis of modern frame-based NLU systems.
| Approach | Structure | Strengths | Weaknesses | Best For |
|---|---|---|---|---|
| Propositional Logic | Truth-valued propositions | Decidable; fast; sound & complete | No variables; no quantifiers; exponential growth | Simple boolean reasoning, hardware verification |
| First-Order Logic (FOL) | Objects + predicates + quantifiers | Highly expressive; sound; general | Semi-decidable; slow; verbose | Expert systems, ontologies, theorem proving |
| Horn Clauses / Prolog | Definite clauses — body → head | Efficient SLD resolution; Prolog | No disjunctive heads; limited negation | Logic programming, Datalog databases |
| Semantic Networks | Nodes + labelled arcs + inheritance | Natural; visual; inheritance | Ambiguous semantics; multiple inheritance issues | Taxonomies, NLU, knowledge graphs |
| Frames | Slots + fillers + inheritance + procedures | Default values; procedural attachment; OOP-like | Complex interaction of defaults; not formal | Expert systems, object modelling, planning |
| Production Rules | IF condition THEN action | Natural expert knowledge; modular; explainable | Conflict resolution needed; no structure between rules | Expert systems (MYCIN), decision support |
| Scripts | Stereotyped event sequences | Captures procedural knowledge; enables inference | Rigid; hard to handle deviations; difficult to build | NLU story understanding, dialogue systems |
Building a working knowledge representation system is hard — much harder than picking a formalism and writing down facts. Fundamental problems arise that no current KR approach fully solves. These issues are not bugs in specific systems; they are deep conceptual challenges inherent to representing a complex, changing, and incompletely known world in a finite, static formal language.
This section covers the six most important issues: the expressiveness–tractability trade-off, completeness and consistency, uncertainty and vagueness, the Frame Problem, the Qualification and Ramification Problems, and the knowledge acquisition bottleneck.
The most fundamental issue in KR is a tension between two desirable but conflicting goals. This trade-off is the most frequently examined issue in KR courses.
There is no KR language that is simultaneously fully expressive (can represent all human knowledge), computationally efficient (answers queries in polynomial time), and complete (derives all valid conclusions). Every practical KR system makes a deliberate trade-off. Description Logics (the basis of OWL — Web Ontology Language) are the current best balance for ontology engineering.
Completeness: A KB is complete if it contains all relevant facts about the domain — no true fact is missing. Real-world KBs are almost never complete (we don't know everything).
Consistency: A KB is consistent if no contradiction can be derived — no statement and its negation are both entailed. Inconsistent KBs are dangerous: from a contradiction, everything is provable (ex falso quodlibet).
Closed World Assumption (CWA): Anything not in the KB is assumed false. Databases use CWA. Simple but dangerous — absence of evidence treated as evidence of absence.
Open World Assumption (OWA): Anything not in the KB is simply unknown. Web ontologies (OWL) use OWA. More faithful to reality but requires explicit negation to say something is false.
The KB contains: Allergy(John, penicillin) but does NOT contain Allergy(John, amoxicillin).
| Assumption | Query: Is John allergic to amoxicillin? | Consequence |
|---|---|---|
| CWA (Database) | "NO — not in the KB, therefore false" | System confidently prescribes amoxicillin — possibly dangerous! |
| OWA (Ontology) | "UNKNOWN — not stated either way" | System asks doctor to verify before prescribing — safer! |
Medical KBs should use OWA: a missing allergy record does not mean no allergy — it may mean the allergy was never tested or recorded.
Real-world knowledge is rarely certain. A doctor doesn't know that a patient has pneumonia — they have a degree of belief based on incomplete evidence. Classic logic is bivalent (true or false). Two main approaches handle uncertainty in KR:
| Approach | Representation | Example | Used In |
|---|---|---|---|
| Certainty Factors (CF) | Weight from −1 to +1 attached to rules | IF fever AND cough THEN pneumonia [CF=0.8] | MYCIN, early expert systems |
| Bayesian Networks | Conditional probability distributions | P(Pneumonia | Fever=T, Cough=T) = 0.72 | Medical diagnosis, spam filters, NLP |
| Fuzzy Logic | Truth values in [0,1]; linguistic variables | Temperature is "HIGH" with degree 0.85 | Control systems, washing machines |
| Dempster-Shafer Theory | Belief functions over sets of hypotheses | Belief({pneumonia, bronchitis}) = 0.6 | Decision support under ignorance |
The Frame Problem asks: when an agent takes an action, which facts about the world remain true (the "frame") and which change? In formal terms: how do we efficiently represent non-change without explicitly listing all unchanged facts after every action?
Naïve solution: add an axiom of persistence for every fact and every action. With F facts and A actions, this requires F×A frame axioms — exponentially expensive and impossible to maintain.
State before action: John has Fever, Cough, Chest-Pain, Diagnosis=Pneumonia.
Action: Prescribe(John, amoxicillin)
Question: What is true after the action?
| Fact | After Prescribing? | How do we know? |
|---|---|---|
| HasFever(John) | Still true (immediately) | Frame axiom: Prescribe doesn't change fever |
| HasCough(John) | Still true (immediately) | Frame axiom: Prescribe doesn't change cough |
| Diagnosis(John, Pneumonia) | Still true | Frame axiom: Prescribe doesn't change diagnosis |
| Prescription(John, amoxicillin) | Now true (NEW) | Effect axiom: Prescribe creates this fact |
| Age(John, 45) | Still true | Frame axiom: Prescribe doesn't change age |
| Smoker(John) | Still true | Frame axiom: Prescribe doesn't change smoking |
For one action and six facts, we need five explicit frame axioms. With 1,000 facts and 100 actions, we need 100,000 frame axioms. This is the Frame Problem.
Successor-State Axioms (Reiter, 1991): Instead of frame axioms, write one axiom per fluent: "Fact F is true after action A if: A causes F, OR F was already true and A doesn't change F." This collapses exponentially many axioms into one per fact.
Default Persistence: Assume all facts persist unless explicitly changed — "what was true remains true unless otherwise stated" (the STRIPS assumption used in planning).
The Qualification Problem asks: how many conditions must be listed before an action is guaranteed to achieve its effect? Practically — how complete must the precondition list of an action be?
Example: "Prescribing amoxicillin cures bacterial pneumonia." Qualifications needed: the patient is not allergic, the bacteria are not resistant, the patient actually takes the medication, the dosage is correct, the patient doesn't have an interfering condition… The list is potentially infinite. We can never fully qualify an action.
The Ramification Problem asks: how do we represent all the indirect consequences of an action? When an action changes something, it may trigger cascading changes that are hard to enumerate.
Example: Prescribing amoxicillin → patient buys medicine → patient spends money → patient's bank balance changes → patient has less money for food → … The chain of indirect consequences can be infinite and unpredictable.
| Problem | Core Question | Challenge | Partial Solution |
|---|---|---|---|
| Frame Problem | What stays the same after an action? | Exponential frame axioms | Successor-state axioms; STRIPS default |
| Qualification Problem | What must be true for an action to work? | Infinite preconditions | Default logic; closed world for preconditions |
| Ramification Problem | What changes indirectly? | Infinite ripple effects | Causal theories; ontological modularisation |
Even if we choose the perfect KR formalism, we still need to fill the knowledge base with knowledge. This turns out to be the single hardest practical challenge in AI: the knowledge acquisition bottleneck.
The process of extracting knowledge from human experts and encoding it into a formal KB is: slow (experts communicate poorly in formal terms), expensive (expert time costs money), incomplete (experts cannot articulate all their knowledge), and inconsistent (different experts contradict each other).
Studies show that building a medical expert system requires years of collaboration between knowledge engineers and domain experts. Experts know things they cannot articulate — this tacit knowledge is the hardest to capture.
Knowledge Elicitation: Interview domain experts. Use protocol analysis (think-aloud), structured interviews, cases and repertory grids. Challenge: experts cannot fully articulate tacit knowledge.
Knowledge Analysis: Organise raw information into concepts, relations, and rules. Identify inconsistencies. Challenge: different experts disagree; elicited knowledge is ambiguous.
Knowledge Encoding: Translate analysed knowledge into the chosen KR formalism. Challenge: knowledge does not fit cleanly into any single formalism; lossy translation.
Knowledge Validation: Test the KB against known cases. Identify missing rules and incorrect encodings. Challenge: errors may not surface until rare edge cases; validation requires more expert time.
Knowledge Maintenance: Update the KB as the domain changes (new drugs, new diseases, changed protocols). Challenge: changes may invalidate many existing rules; no version control for knowledge.
The knowledge acquisition bottleneck drove the AI community toward machine learning: rather than manually encoding knowledge, learn it automatically from data. Large language models (GPT-4, Claude) learn vast amounts of implicit world knowledge from text corpora — effectively automating much of the knowledge acquisition process. However, learned knowledge is less transparent, harder to verify, and may contain errors — trading the encoding problem for a verification problem.
| Issue | Definition | Impact | Key Solution Strategies |
|---|---|---|---|
| Expressiveness vs. Tractability | More expressive → slower reasoning | Cannot represent all knowledge efficiently | Description Logics, Horn clauses for efficiency |
| Completeness | KB may be missing facts | System gives wrong answers on unknown facts | CWA vs. OWA; explicit negation |
| Consistency | KB may contain contradictions | Any conclusion derivable — system useless | Truth maintenance systems; paraconsistent logic |
| Uncertainty | Knowledge is often probabilistic | Binary T/F fails on real evidence | Certainty factors, Bayesian networks, fuzzy logic |
| Frame Problem | What stays same after action? | Exponential axiom count | Successor-state axioms; STRIPS |
| Qualification Problem | Preconditions may be infinite | Actions may fail unexpectedly | Default logic; assume normal conditions |
| Ramification Problem | Indirect effects may be infinite | Cannot predict all consequences | Causal models; modular ontologies |
| Knowledge Acquisition | Encoding expert knowledge is hard | KBs are incomplete, inconsistent, expensive | Machine learning; crowdsourcing; ontology reuse |
This section consolidates every definition, comparison, and issue from Unit III into a single revision reference. Work through all tables carefully — the most commonly tested items are marked with a ★.
| Term | Definition | Exam Tip |
|---|---|---|
| Knowledge Representation | A formal language + inference procedure for encoding and reasoning about domain knowledge | Always mention: syntax, semantics, reasoning procedure |
| KR Hypothesis | Intelligent behaviour requires internal structures that represent propositional knowledge and causally drive behaviour (B.C. Smith, 1985) | Quote the key phrase: "structural ingredients that represent…" |
| Ontological Commitment | The assumptions a KR language makes about what kinds of things exist in the world | Every language makes different commitments — give examples |
| Representational Mapping | A structure-preserving correspondence from the real world to formal symbols | Must be faithful: conclusions in formal world = true in real world |
| CWA vs. OWA | CWA: what's not stated is false. OWA: what's not stated is unknown | Databases use CWA; OWL ontologies use OWA |
| Frame Problem | How to represent what does NOT change after an action without listing all unchanged facts | McCarthy & Hayes 1969; solution = successor-state axioms |
| Qualification Problem | How many preconditions must be listed for an action to guarantee its effect? | List is potentially infinite; use default logic as solution |
| Ramification Problem | How to represent all indirect consequences of an action | Different from Frame Problem — it's about what DOES change indirectly |
| KA Bottleneck | The practical difficulty of extracting, encoding, and maintaining expert knowledge in a KB | Tacit knowledge = hardest to capture; ML is the modern partial solution |
| Approach | Year / Author | Core Structure | Key Strength | Key Weakness | Example System |
|---|---|---|---|---|---|
| Propositional Logic | Boole 1847 | Truth-valued propositions + connectives | Decidable; fast; sound & complete | No variables, quantifiers, or objects | SAT solvers, hardware verification |
| First-Order Logic (FOL) | Frege 1879 | Objects + predicates + ∀/∃ + functions | Highly expressive; general-purpose | Semi-decidable; slow on large KBs | Cyc, theorem provers, Prolog |
| Horn Clauses | Horn 1951 / Kowalski 1974 | Definite clauses Body → Head | Polynomial inference (SLD) | No disjunctive head; limited negation | Prolog, Datalog |
| Semantic Networks | Quillian 1966 | Nodes (concepts) + labelled arcs | Natural; visual; inheritance | Ambiguous semantics; multiple inheritance | WordNet, ConceptNet, Knowledge Graphs |
| Frames | Minsky 1975 | Slots + fillers + default + procedures | Default values; procedural attachment | Informal; complex default interactions | FRL, KRL; basis of OOP |
| Production Rules | Newell & Simon 1972 | IF condition THEN action | Natural expert encoding; modular | Rule interaction; conflict resolution | MYCIN, CLIPS, Drools |
| Scripts | Schank & Abelson 1977 | Stereotyped event sequences with roles | Procedural + causal structure; NLU | Rigid; hard to handle novel situations | SAM, PAM (story understanding) |
| Issue | One-Line Definition | Classic Example | Solution Approach |
|---|---|---|---|
| Expressiveness–Tractability | More expressive = slower reasoning | FOL: expressive but semi-decidable | Description Logics (OWL) |
| Completeness | Missing facts cause wrong answers | Absent allergy record ≠ no allergy | Open World Assumption |
| Consistency | Contradictions make KB useless | Drug A cures and harms pneumonia | Truth Maintenance Systems |
| Uncertainty | Knowledge is probabilistic, not binary | "Possibly pneumonia" (CF=0.8) | Certainty factors, Bayesian nets |
| Frame Problem | What persists after an action? | After prescribing, age still same | Successor-state axioms; STRIPS |
| Qualification Problem | How many preconditions does an action need? | Drug works IF not allergic AND not resistant AND… | Default normal conditions |
| Ramification Problem | What are all indirect effects? | Prescription → purchase → bank balance changes | Causal theories, modular ontology |
| KA Bottleneck | Getting expert knowledge in is very hard | Expert cannot articulate tacit knowledge | Machine learning; ontology reuse |
Mistake 1: Confusing the Frame Problem (what stays the same?) with the Ramification Problem (what changes indirectly?). They are different aspects of the action-effects problem.
Mistake 2: Saying propositional logic is "complete" without qualification — it is complete for propositional reasoning, but cannot express FOL statements at all (no variables, no quantifiers).
Mistake 3: Saying Horn clauses are the same as FOL — they are a proper SUBSET of FOL. The key restriction: at most ONE positive literal in the head. Disjunctive conclusions cannot be expressed.
Mistake 4: Confusing semantic networks and frames — semantic networks show relationships between concepts; frames package all slot-value knowledge about a single concept. Frames evolved from semantic networks.
Mistake 5: Saying the knowledge acquisition bottleneck is about encoding speed — it is fundamentally about tacit knowledge that experts cannot articulate, making it impossible to elicit, not merely slow to encode.
Mistake 6: Forgetting CWA vs. OWA — databases (SQL) use CWA; ontologies (OWL, SPARQL) use OWA. This difference is commonly tested and has real-world safety consequences.
| Question Pattern | Required Approach | Key Terms to Use |
|---|---|---|
| "What is knowledge representation?" | Define KR + give the 5 roles (surrogate, ontological commitment, etc.) + KR hypothesis | Formal language, inference, surrogate, Brian Smith |
| "Compare approaches to KR" | Use the master comparison table; highlight expressiveness, strengths, weaknesses, example systems | Logic, frames, semantic networks, production rules, scripts |
| "Explain the Frame Problem with an example" | Define the problem → give action example → show exponential frame axioms → explain successor-state solution | Non-change, frame axioms, persistence, STRIPS |
| "Represent X in [formalism]" | Give concrete syntax for the chosen formalism applied to the given domain | Use correct notation; show both facts and rules |
| "What are issues in KR?" | List and explain all 8 issues; give one example for each | Expressiveness, tractability, completeness, uncertainty, Frame, Qualification, Ramification, KA bottleneck |
| "CWA vs OWA — when to use each?" | Define both; give database vs ontology example; explain safety implications | Closed world, open world, absence of evidence |