Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 46 ยท Logic and Knowledge Representation

Knowledge Representation, Semantic Networks and Frames

Learn how AI stores knowledge: semantic networks, frames with slots and inheritance, ontologies and production rules, with runnable Python for each.

A reasoning program is only as good as what it knows, and how it stores that knowledge decides what it can do with it quickly. Knowledge representation is the part of AI that studies how to write facts about the world in a form a program can search, combine and extend. First-order logic (see First-Order Logic) is the most expressive option, but it is not always the most convenient one. People also draw boxes and arrows, fill in forms and write "if ... then ..." rules. Classical AI turned each of these habits into a formal scheme.

This lesson covers four of them: semantic networks, frames, ontologies and production rules. You will build the first two as small Python programs, see how inheritance and defaults make them compact, and learn where each scheme runs out of steam. The last of the four, rules, gets a lesson of its own: Rule-Based and Expert Systems.

What a good representation must do

A representation language is judged on a few properties:

  • Representational adequacy: it can express everything the domain needs.
  • Inferential adequacy: it can derive new knowledge from what is stored.
  • Inferential efficiency: it can derive it fast enough, by guiding the search.
  • Acquisitional efficiency: knowledge can be added without rewriting the whole system.

No scheme wins on all four. Logic is adequate but can be slow; frames and networks are fast for the questions they were designed for, but clumsy for others. Good engineers pick the scheme that matches the questions the program must answer.

Semantic networks

A semantic network is a graph. Nodes are concepts or individuals, and labelled edges are relations between them. Two relations do most of the work:

  • is-a links a class to a more general class ("canary is-a bird") or an individual to its class ("Tweety is-a canary").
  • has (or any property edge) attaches a fact to a node ("bird has wings").

The key idea is property inheritance: if you ask what Tweety can do, you start at the Tweety node and walk up the is-a edges, collecting every property on the way.

graph TD
    A["animal"] -->|has| B["skin"]
    C["bird"] -->|is-a| A
    C -->|has| D["wings"]
    C -->|can| E["fly"]
    F["canary"] -->|is-a| C
    F -->|color| G["yellow"]
    H["penguin"] -->|is-a| C
    H -->|can| I["not fly"]
    J["Tweety"] -->|is-a| F

Ask Tweety "can you fly?" and the answer is found two steps up, on bird. Ask a penguin and the nearer, more specific edge wins.

The code below stores the network as triples (node, relation, value) and answers questions by walking up is-a. It returns the first answer found, so a specific fact overrides a general one. That is called default reasoning with exceptions, and the penguin shows why it matters.

Python A semantic network with inheritance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tweety inherits wings from bird and skin from animal, even though neither fact was written next to Tweety. Pingu hits the more specific penguin cannot fly before it reaches bird can fly, so the exception wins.

Semantic networks are easy to draw and to explain, and they were the basis of early natural-language systems. They have weaknesses too: edges have no fixed meaning (is-a can mean "is a member of" or "is a subclass of"), negation and quantifiers ("all", "some") are awkward, and large networks become tangled. Modern knowledge graphs are the descendants of semantic networks, with strict schemas added.

Frames

A frame (introduced by Marvin Minsky in the 1970s) bundles everything about one kind of thing into a structured record. A frame has a name and a set of slots. Each slot holds:

  • a value (the colour of this car is red),
  • a default (cars normally have four wheels),
  • a type restriction (the number of doors is an integer from 1 to 5), and sometimes
  • an attached procedure, a demon, that runs when the slot is read (if-needed) or written (if-added).

Frames are organised in the same is-a hierarchy as semantic networks, and a child frame inherits slots from its parent. Frames that describe a class are generic; frames that describe one individual are instances.

Concept Frame view
Class Generic frame with default slot values
Object Instance frame that fills or overrides slots
Inheritance Look up the parent chain when a slot is empty
Computed value if-needed demon calculates it on demand
Consistency check if-added demon validates a new value

If this sounds like object-oriented programming, that is no coincidence: classes with attributes, inheritance and methods were strongly influenced by frame systems. The difference is the focus. A frame system is a knowledge base you query and reason over, not just a way to organise program code.

Python Frames with defaults and demons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The demon wheels_total_cost is defined once on vehicle, but it is evaluated against whichever frame asked, so the bike (2 wheels) and the sedan (4 wheels) get different answers. That is the "computed slot" idea in a few lines.

Frames, scripts and the frame problem

Do not confuse the frame of knowledge representation with the frame problem from planning (the difficulty of stating what does not change after an action, covered in Classical Planning). The words share a root but are unrelated. A related notion is a script, a frame for a stereotyped sequence of events such as "eating at a restaurant" (enter, order, eat, pay, leave), which lets a program fill in unstated steps when it reads a story.

Ontologies

An ontology is an agreed, formal vocabulary for a domain: the concepts, their properties and the relations that may hold between them. Semantic networks and frames show how to store facts; an ontology says what the vocabulary is, so that different programs and different organisations mean the same thing by "Customer", "Drug" or "Gene".

An ontology usually contains:

  • Classes (concepts) arranged in a subclass hierarchy,
  • Properties (attributes and relations) with their allowed domains and ranges,
  • Individuals (instances), and
  • Axioms (rules such as "every Person has exactly one birth date").

Web standards such as RDF (facts as subject-predicate-object triples) and OWL (a logic-based language for ontologies) are built for this. A description logic, the family behind OWL, is a carefully limited fragment of first-order logic chosen so that reasoning stays decidable. A reasoner can then check that an ontology is consistent and infer, for example, that a Triangle that is also a Shape with 3 sides must belong to Polygon.

A tiny triple store already shows the flavour. The query code below asks a question that crosses two relations, which is exactly the kind of chaining that makes triples useful.

Python A triple store with a transitive rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Nothing in the data says "Rex is an Animal". It follows from two subclassOf triples, the same way a reasoner infers it from an ontology. Real knowledge graphs hold billions of such triples and are queried with languages such as SPARQL.

Choosing a scheme

Scheme Best for Watch out for
Semantic network Quick sketches, inheritance questions Vague edge meanings, no quantifiers
Frames Structured objects with defaults and procedures Exceptions can make inheritance confusing
Production rules Advice, diagnosis, configuration Rule interactions grow hard to maintain
Logic Exact reasoning and proofs Can be slow, needs precise axioms
Ontology Sharing a vocabulary between systems Agreeing on the model is the hard part

Tip: Start with the questions the program must answer, then pick the representation. If every question is "what properties does X have?", frames or a knowledge graph are enough. If you need to prove things, use logic.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a semantic network, how does Tweety learn that it has wings when only bird has wings is stored?

    The program walks up the is-a edges (Tweety, canary, bird) and collects the properties it finds on each node.
  2. 2. What is a slot demon (if-needed procedure) in a frame system?

    Demons are procedures attached to slots. An if-needed demon calculates a value on demand, an if-added demon runs when a value is stored.
  3. 3. What does an ontology add on top of a plain knowledge base?

    An ontology fixes the meaning of the terms so different systems can exchange and reason about the same facts.
  4. 4. A penguin frame says cannot fly while its parent bird says can fly. Which answer does the lookup return for a penguin?

    Lookup starts at the instance and goes up the chain, stopping at the first frame that has an answer, so specific facts override defaults.

Summary

  • Knowledge representation is about storing facts so that a program can answer questions quickly and extend them easily.
  • Semantic networks are graphs of concepts with is-a and property edges, and inheritance gives answers for free.
  • Frames bundle slots, defaults, type checks and demons, and organise into inheritance hierarchies much like classes.
  • Specific facts override general defaults, which gives a simple form of default reasoning with exceptions.
  • Ontologies fix the vocabulary of a domain; RDF triples and description logics are the standard tools.
  • Pick the representation that matches the questions you must answer.

Next: Rule-Based and Expert Systems.