Semantic networks & inheritance — COMP 456

Knowledge as a graph

Predicate calculus can say anything, but it gives you no structure for free — every fact is an isolated sentence. A semantic network trades some of that generality for organisation: knowledge is a labeled, directed graph where nodes are concepts (or individuals) and labeled arcs are relations between them. The two arcs that carry the most weight are is-a (subclass) and instance-of (membership), because together they build a class hierarchy.

The payoff of the hierarchy is inheritance. Collins and Quillian (1969) ran reaction-time experiments and found that people store a property at its highest appropriate level: "has feathers" and "can fly" live on the bird node, not duplicated onto canary, robin, sparrow. To answer "does a canary fly?" you walk up the is-a chain from canary until you find a node that knows about flying. Their data showed retrieval time grows with the number of levels you climb — direct evidence that the brain (and a sensible KB) does not duplicate inherited facts.

Exceptions live locally

Real categories have exceptions: birds fly, but penguins and ostriches do not. The rule is store the exception with the individual, overriding the inherited default. A lookup stops at the first node that asserts the property, so a local flies = False on penguin short-circuits the inherited flies = True on bird. This is exactly the most-specific-wins principle you will meet again as conflict resolution in production systems and as method override in object-oriented programming.

Worked example

Model an is-a chain canary → bird → animal plus penguin → bird, with flies = True on bird and a local override flies = False on penguin. The lookup get_prop(node, prop) climbs the chain and returns the first node that defines the property:

get_prop('canary', 'flies') climbs canary → bird, finds flies = True on bird → inherited.
get_prop('penguin', 'flies') finds flies = False directly on penguin → local override, never reaches bird.

This is the whole mechanism: store once, inherit down, override locally.

Read the arcs upward and you have the lookup: <em>does a canary fly?</em> climbs <code>canary → bird</code> and stops at the first node that knows about flying. <em>Does a penguin fly?</em> never leaves <code>penguin</code> — the local <code>False</code> answers first. The property is written once and the exception is written once, and no node repeats what its parent already says.