Knowledge representation (KR) is about organising what an agent knows — categories, objects, properties, defaults and rules — so that inference is efficient. Expert systems were AI's first big commercial success, and today's knowledge graphs are their descendants.

Main representation schemes

Inheritance with exceptions

Python

# a semantic network as (subject, relation, object) triples
TRIPLES = [
    ("Bird", "is-a", "Animal"), ("Animal", "breathes", True),
    ("Bird", "can-fly", True), ("Bird", "has", "feathers"),
    ("Penguin", "is-a", "Bird"), ("Penguin", "can-fly", False),     # an exception overrides the default
    ("Tweety", "instance-of", "Bird"), ("Pingu", "instance-of", "Penguin"),
]

def lookup(entity, attribute):
    node = entity
    while node:
        for s, r, o in TRIPLES:
            if s == node and r == attribute:
                return o                           # the most specific value wins
        parents = [o for s, r, o in TRIPLES if s == node and r in ("is-a", "instance-of")]
        node = parents[0] if parents else None     # climb the is-a hierarchy
    return None

print(lookup("Tweety", "can-fly"), lookup("Pingu", "can-fly"))     # True False
print(lookup("Pingu", "has"), lookup("Pingu", "breathes"))         # feathers True ← inherited from Bird and Animal

This is default (non-monotonic) reasoning: birds fly unless we learn otherwise. Classical logic is monotonic — adding facts never removes conclusions — so defaults need special logics (default logic, circumscription) or the inheritance trick above.

Expert systems

Component	Role
Knowledge base	Domain rules and facts captured from human experts
Inference engine	Applies the rules (forward or backward chaining) to the case at hand
Working memory	Facts about the current case (symptoms, test results)
Explanation facility	Answers why a question is asked and how a conclusion was reached
Knowledge-acquisition interface	Lets experts and engineers add and edit rules

Python

RULES = [
    ("R1", {"fever", "cough"}, "flu-suspected"),
    ("R2", {"flu-suspected", "short-of-breath"}, "refer-to-doctor"),
    ("R3", {"sneezing", "itchy-eyes"}, "allergy-suspected"),
]

def diagnose(symptoms):
    facts, how = set(symptoms), {}
    changed = True
    while changed:                                  # forward chaining until nothing new fires
        changed = False
        for name, conditions, conclusion in RULES:
            if conditions <= facts and conclusion not in facts:
                facts.add(conclusion)
                how[conclusion] = f"{name}: {' + '.join(sorted(conditions))}"
                changed = True
    return how

result = diagnose({"fever", "cough", "short-of-breath"})
print(list(result))                         # ['flu-suspected', 'refer-to-doctor']
print(result["refer-to-doctor"])            # R2: flu-suspected + short-of-breath ← the "how" explanation

System	Domain	Note
DENDRAL (1965)	Inferring molecular structure from mass spectra	First expert system
MYCIN (1970s)	Diagnosing blood infections, recommending antibiotics	Hundreds of backward-chaining rules with certainty factors; matched specialists but was never used clinically
XCON / R1 (1980)	Configuring DEC VAX computers	Saved DEC an estimated $40M a year; grew to thousands of rules

Hard problems in KR

Problem	Description
Frame problem	Representing what does not change when an action happens without writing an axiom for every unaffected fact
Qualification problem	Listing every precondition of an action is impossible (the car starts… unless the battery is dead, the tank empty, a potato in the exhaust…)
Closed-world assumption	Databases and Prolog treat anything not known to be true as false — convenient, but not valid for open worlds like the web
Common sense	Vast everyday knowledge (water is wet, people have one mother) that is hard to write down — the target of projects like Cyc

Compare semantic networks and frames.

What are the components of an expert system?