Artificial Intelligence

Knowledge Reasoning And Planning

Knowledge Representation Basics

Module 2's states were problem-SPECIFIC (a city name, a board

JrCodex·7 min read

Jr Codex AI Notes

Level: Intermediate Prerequisites: Module 2: Problem Solving by Search Time to complete: ~25 minutes

Table of Contents

  1. What is Knowledge Representation?
  2. Properties of a Good Representation
  3. Semantic Networks
  4. Frames
  5. Ontologies
  6. Representing Knowledge in Code
  7. Summary & Next Steps

1. What is Knowledge Representation?

Knowledge representation (KR) is the study of how to encode facts about the world in a form a computer can store, retrieve, and reason over. Module 2's search problems already used a form of this (states and actions) — this module makes representation itself the focus, enabling much richer reasoning than "which state am I in?"

Why Search States Aren't Enough
─────────────────────────────────────────
  Module 2's states were problem-SPECIFIC (a city name, a board
  position) — useful for search, but not naturally reusable for
  answering general questions like:

  "Is a canary a bird?"
  "Do all birds fly?"
  "If Tweety is a canary, can Tweety fly?"

  This requires representing GENERAL facts and relationships,
  then REASONING over them — the subject of this entire module.
─────────────────────────────────────────

2. Properties of a Good Representation

Four Qualities to Balance
─────────────────────────────────────────
  Representational Adequacy:   can it express everything we
                                  actually need to represent?
  Inferential Adequacy:           can NEW knowledge be derived
                                     from what's already represented?
  Inferential Efficiency:            can that derivation happen
                                        FAST enough to be useful?
  Acquisition Efficiency:               how easily can new
                                           knowledge be ADDED?
─────────────────────────────────────────

These four properties trade off against each other constantly throughout this module — propositional logic (Chapter 2) is inferentially efficient but not very expressive; first-order logic (Chapter 3) is far more expressive but harder to reason over efficiently.

3. Semantic Networks

A semantic network represents knowledge as a graph — nodes are concepts/objects, edges are labeled relationships between them.

A Small Semantic Network
─────────────────────────────────────────
       [Animal]
          │ is-a
       [Bird] ────can────► [Fly]
          │ is-a
      [Canary]
          │ is-a
       [Tweety] ───has-color───► [Yellow]
─────────────────────────────────────────

class SemanticNetwork:
    def __init__(self):
        self.edges = []      # list of (subject, relation, object) triples
 
    def add_fact(self, subject, relation, obj):
        self.edges.append((subject, relation, obj))
 
    def query(self, subject=None, relation=None, obj=None):
        """Find all facts matching the given pattern (None = wildcard)."""
        return [
            (s, r, o) for (s, r, o) in self.edges
            if (subject is None or s == subject)
            and (relation is None or r == relation)
            and (obj is None or o == obj)
        ]
 
net = SemanticNetwork()
net.add_fact("Bird", "is-a", "Animal")
net.add_fact("Bird", "can", "Fly")
net.add_fact("Canary", "is-a", "Bird")
net.add_fact("Tweety", "is-a", "Canary")
net.add_fact("Tweety", "has-color", "Yellow")
 
print(net.query(subject="Tweety"))      # everything directly known about Tweety

The power (and limitation) of a plain semantic network: answering "can Tweety fly?" requires following the is-a chain (Tweety → Canary → Bird → can Fly) — the network itself doesn't automatically do this; Chapter 4's inference techniques are what make this kind of chained reasoning actually work.

def can_fly(network, entity):
    """A simple inheritance-following query — climbs the is-a chain."""
    direct = network.query(subject=entity, relation="can", obj="Fly")
    if direct:
        return True
    parents = network.query(subject=entity, relation="is-a")
    return any(can_fly(network, parent_obj) for (_, _, parent_obj) in parents)
 
print(can_fly(net, "Tweety"))      # True — inherited through Canary → Bird

4. Frames

A frame groups everything known about one concept into a single structure with named slots — closer to an object in OOP (Python Notes, Module 4) than a scattered set of graph edges.

class Frame:
    """A frame represents a concept with named slots and (optionally) a parent frame."""
    def __init__(self, name, parent=None):
        self.name = name
        self.parent = parent
        self.slots = {}
 
    def set_slot(self, slot_name, value):
        self.slots[slot_name] = value
 
    def get_slot(self, slot_name):
        """Look up a slot, INHERITING from the parent frame if not found locally."""
        if slot_name in self.slots:
            return self.slots[slot_name]
        if self.parent:
            return self.parent.get_slot(slot_name)
        return None
 
bird_frame = Frame("Bird")
bird_frame.set_slot("can_fly", True)
bird_frame.set_slot("num_legs", 2)
 
canary_frame = Frame("Canary", parent=bird_frame)
canary_frame.set_slot("color", "yellow")
 
tweety_frame = Frame("Tweety", parent=canary_frame)
tweety_frame.set_slot("name", "Tweety")
 
print(tweety_frame.get_slot("can_fly"))      # True — inherited from Bird
print(tweety_frame.get_slot("color"))          # "yellow" — inherited from Canary
print(tweety_frame.get_slot("name"))             # "Tweety" — defined directly
Frames vs Semantic Networks
─────────────────────────────────────────
  Semantic network:  facts are scattered EDGES in a graph —
                       flexible, but no natural "grouping"

  Frame:                everything about ONE concept lives
                          together in ONE structure, with
                          explicit INHERITANCE from a parent —
                          closer to how OOP classes work
                          (Python Notes, Module 4)
─────────────────────────────────────────

This is directly analogous to class inheritance (Python Notes, Module 4, Chapter 2) — a frame's parent slot lookup is essentially the same mechanism as super() resolving an attribute up the class hierarchy.

5. Ontologies

An ontology is a formal, shared specification of the concepts in a domain and the relationships between them — essentially a rigorously-defined, often large-scale semantic network, designed so multiple systems can share a common, unambiguous understanding.

Why Ontologies Matter
─────────────────────────────────────────
  A semantic network you build yourself (Section 3) might use
  "is-a" while someone else's system uses "subtype_of" for the
  IDENTICAL relationship — nothing forces consistency.

  An ONTOLOGY standardizes this: a shared, formally agreed-upon
  vocabulary and structure, so DIFFERENT systems can exchange
  and combine knowledge without ambiguity.
─────────────────────────────────────────

Real-World Ontology Examples
─────────────────────────────────────────
  WordNet:        a large lexical ontology of English words,
                    organized by meaning and relationship
                    (synonym, hypernym/hyponym — "is-a" chains)
  Medical ontologies (SNOMED CT):  standardized medical terms
                                     and relationships, used across
                                     hospital systems worldwide
  Schema.org:         a web-standard ontology letting websites
                        mark up content (products, events,
                        recipes) so search engines understand it
                        consistently
─────────────────────────────────────────

# A tiny, simplified ontology-style hierarchy — the SAME underlying
# concept as Section 3's semantic network, but with a formal,
# standardized set of relationship types
ontology = SemanticNetwork()
ontology.add_fact("Canary", "subclass_of", "Bird")      # standardized relation name
ontology.add_fact("Bird", "subclass_of", "Animal")
ontology.add_fact("Bird", "has_property", "can_fly")

Ontologies are what make large-scale knowledge sharing between AI systems possible — a modern example is how structured web data (schema.org markup) helps search engines and, increasingly, LLM-based systems (NLP/LLM notes) understand web page content unambiguously.

6. Representing Knowledge in Code

Bringing Sections 3-5 together — a small, unified knowledge base combining semantic-network-style facts with frame-style inheritance:

class KnowledgeBase:
    def __init__(self):
        self.facts = []          # (subject, relation, object) triples
        self.frames = {}           # name -> Frame
 
    def add_fact(self, subject, relation, obj):
        self.facts.append((subject, relation, obj))
 
    def add_frame(self, frame):
        self.frames[frame.name] = frame
 
    def query_facts(self, subject=None, relation=None, obj=None):
        return [
            (s, r, o) for (s, r, o) in self.facts
            if (subject is None or s == subject)
            and (relation is None or r == relation)
            and (obj is None or o == obj)
        ]
 
kb = KnowledgeBase()
kb.add_fact("Canary", "subclass_of", "Bird")
kb.add_fact("Bird", "subclass_of", "Animal")
kb.add_fact("Bird", "can", "fly")
 
kb.add_frame(Frame("Bird"))
kb.frames["Bird"].set_slot("num_legs", 2)
 
print(kb.query_facts(relation="subclass_of"))      # the full class hierarchy
print(kb.frames["Bird"].get_slot("num_legs"))         # 2

This kind of hybrid structure — facts for flexible relationships, frames for grouped, inheritable properties — is a common practical pattern, and sets up exactly the kind of structured knowledge that Chapters 2-4's logic and inference techniques operate over formally.

7. Summary & Next Steps

Key Takeaways

  • Knowledge representation encodes general facts and relationships so a system can reason beyond the problem-specific states used in Module 2's search.
  • A good representation balances expressiveness (representational adequacy), the ability to derive new facts (inferential adequacy), speed of doing so (inferential efficiency), and ease of adding new knowledge (acquisition efficiency).
  • Semantic networks represent knowledge as labeled graph edges; frames group a concept's properties together with explicit inheritance, closely mirroring OOP class hierarchies.
  • Ontologies formalize and standardize these structures so multiple systems can share an unambiguous, consistent understanding of a domain — real examples include WordNet, medical ontologies, and schema.org.

Concept Check

  1. Why couldn't Module 2's search-problem states alone answer a general question like "can a canary fly?"
  2. How does a frame's inheritance mechanism resemble Python's class inheritance?
  3. Why do ontologies matter for letting different systems share knowledge, beyond what a personal semantic network provides?

Next Chapter

→ Chapter 2: Propositional Logic

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index