Knowledge Representation: Semantic Networks, Frames, Ontologies and Knowledge Graphs

An agent's intelligence depends not only on its reasoning algorithm but on how its knowledge is represented. The same fact can be easy or impossible to use depending on its form. Today we survey the major representation schemes and connect them to the knowledge graphs that power today's search engines and assistants.

What a representation must do#

A good knowledge representation (KR) scheme should offer:

• Representational adequacy — it can express what we need.
• Inferential adequacy — it supports deriving new knowledge.
• Inferential efficiency — inference is fast enough to be useful.
• Acquisitional efficiency — knowledge can be added easily.

There is an unavoidable tension: the more expressive a language, the harder inference becomes. Full first-order logic is expressive but undecidable; simple databases are fast but inflexible.

Categories and objects#

Much of human knowledge is organised in categories (Dog, Mammal, Animal) with inheritance: properties of a category are inherited by its members and subcategories. In FOL we might write:

Taxonomies of this kind exist in biology, medicine (SNOMED CT has hundreds of thousands of concepts) and library science.

Semantic networks#

A semantic network represents knowledge as a graph: nodes are concepts or objects, and labelled edges are relations such as is-a, part-of or has-colour. For example: Tweety —is-a→ Bird —is-a→ Animal, Bird —can→ Fly.

Semantic networks make inheritance natural: to find whether Tweety can fly, follow is-a links upward. They also support default reasoning: Penguin —can→ ¬Fly overrides the inherited default because it is more specific.

Frames#

Marvin Minsky's frames (1974) organise knowledge into structured records with slots and fillers, much like objects in object-oriented programming:

Frame: Lecture
  is-a:        Event
  location:    <Room>          default: Main Building
  lecturer:    <Person>
  duration:    default 90 minutes
  if-needed:   compute end_time from start_time + duration

Slots can have defaults, constraints and attached procedures ("demons") that run when values are needed or changed. Frames influenced OOP and modern schema design.

Description logics and OWL#

Description logics (DLs) are decidable fragments of FOL designed for defining and reasoning about categories. A DL definition looks like:

DL reasoners answer questions such as subsumption (is every Parent a Person?) and classification (place a new concept correctly in the hierarchy). The Web Ontology Language OWL, a W3C standard, is based on description logics and underlies biomedical ontologies such as the Gene Ontology.

Knowledge graphs#

A knowledge graph stores facts as triples $(\text{subject}, \text{predicate}, \text{object})$:

(Dhaka, capitalOf, Bangladesh)
(AUST, locatedIn, Dhaka)
(Janin_A_Apurba, alumnusOf, AUST)

The RDF standard encodes triples; SPARQL queries them. Large public knowledge graphs such as Wikidata contain over a hundred million items. Search engines use knowledge graphs to answer factual queries directly.

triples = {
    ("Dhaka", "capitalOf", "Bangladesh"),
    ("AUST", "locatedIn", "Dhaka"),
    ("Bangladesh", "locatedIn", "SouthAsia"),
}

def located_in(x, triples):
    """Transitive closure of 'locatedIn' and 'capitalOf' treated as containment."""
    found, frontier = set(), {x}
    while frontier:
        nxt = {o for (s, p, o) in triples if s in frontier and p in {"locatedIn", "capitalOf"}}
        frontier = nxt - found
        found |= nxt
    return found

print(located_in("AUST", triples))   # {'Dhaka', 'Bangladesh', 'SouthAsia'}

Knowledge graph embeddings#

Modern ML represents entities and relations as vectors. The TransE model, for example, learns embeddings such that $\mathbf{e}_{\text{head}} + \mathbf{r} \approx \mathbf{e}_{\text{tail}}$ for true triples. This enables link prediction — inferring missing facts — and bridges symbolic knowledge with neural learning.

Reasoning with defaults and change#

Real knowledge is messy. Two classic difficulties:

• Non-monotonic reasoning — conclusions may be withdrawn given new information ("Tweety flies" until we learn Tweety is a penguin). Circumscription and default logic formalise this.
• The frame problem — when an action occurs, how do we avoid stating everything that did not change? Successor-state axioms offer a solution in the situation calculus.