Skip to content

Knowledge Representation

Knowledge Representation (KR) is one of the central problems in artificial intelligence: how to encode real-world knowledge in a form that computers can understand and reason about. An effective KR scheme must balance expressiveness (the ability to represent complex knowledge), reasoning efficiency (the ability to perform inferences efficiently), and acquirability (the ease of obtaining and maintaining knowledge).

From early semantic networks and frames to modern knowledge graphs and ontologies, and on to knowledge-enhanced methods integrated with large language models, KR technology has evolved from purely symbolic approaches toward hybrid paradigms. These notes cover semantic networks, ontologies, knowledge graphs, rule engines, knowledge graph embeddings, and KG+LLM fusion.

1. Why Knowledge Representation Matters

Challenge Description
Diversity of knowledge Facts, rules, hierarchical relationships, uncertain knowledge
Need for reasoning Deriving new knowledge from existing knowledge
Ambiguity resolution The same word can have different meanings in different contexts (e.g., "Apple" as a fruit vs. a company)
Common-sense reasoning Knowledge that is "obvious" to humans is far from trivial for machines
Interpretability Symbolic knowledge representations are inherently interpretable

KR Hypothesis: Any intelligent system requires some form of knowledge representation and performs reasoning based on it.

2. Semantic Networks and Frames

2.1 Semantic Networks

A semantic network represents concepts as nodes and relationships between concepts as directed edges.

[Animal]  --is-a--> [LivingThing]
[Dog]     --is-a--> [Animal]
[Dog]     --has-->   [FourLegs]
[Dog]     --can-->   [Bark]

Core relation types:

Relation Meaning Example
is-a Class membership (inheritance) Dog is-a Animal
has-a Part-whole Car has-a Engine
instance-of Instantiation Fido instance-of Dog
can Capability Bird can Fly

Inheritance mechanism: Subclasses automatically inherit attributes from their parent classes. "Dog is-a Animal" and "Animal has Metabolism" together imply "Dog has Metabolism."

2.2 Frames

Frames, proposed by Minsky in 1974, provide a structured knowledge representation:

Frame: Dog
  is-a: Animal
  legs: 4
  sound: Bark
  default-color: Brown (can be overridden by specific instances)
  • Slot: An attribute name, such as legs or sound
  • Facet: Constraints or metadata about an attribute, such as default values, types, or ranges
  • Inheritance: Child frames inherit slot values from parent frames

Semantic Networks vs. Frames vs. Object-Oriented Programming

The concept of frames directly influenced the "class-attribute-inheritance" mechanism in object-oriented programming. All three are essentially hierarchical approaches to organizing knowledge.

3. Ontology

3.1 What Is an Ontology?

In AI, an ontology is a formal specification of the concepts, relationships, and constraints within a particular domain.

\[ \text{Ontology} = \langle C, R, A, I \rangle \]

where \(C\) is the set of concepts, \(R\) the set of relations, \(A\) the set of axioms, and \(I\) the set of instances.

3.2 Description Logic (DL)

Description logic provides the mathematical foundation for ontologies and offers decidable reasoning mechanisms.

Constructor Syntax Semantics
Concept intersection \(C \sqcap D\) \(C^I \cap D^I\)
Concept union \(C \sqcup D\) \(C^I \cup D^I\)
Existential quantification \(\exists R.C\) There exists an \(R\)-successor that belongs to \(C\)
Universal quantification \(\forall R.C\) All \(R\)-successors belong to \(C\)
Concept negation \(\neg C\) \(\Delta^I \setminus C^I\)

Examples:

  • "People who have children" = \(\text{Person} \sqcap \exists \text{hasChild}.\top\)
  • "Parents all of whose children are doctors" = \(\text{Person} \sqcap \forall \text{hasChild}.\text{Doctor}\)

3.3 OWL (Web Ontology Language)

OWL is the W3C-recommended language for describing ontologies, based on description logic:

OWL Sub-language Corresponding DL Reasoning Complexity
OWL Lite \(\mathcal{SHIF}(D)\) EXPTIME
OWL DL \(\mathcal{SHOIN}(D)\) NEXPTIME
OWL Full Unrestricted Undecidable

4. Knowledge Graphs

4.1 Basic Concepts

A Knowledge Graph (KG) stores structured knowledge as triples (subject, predicate, object):

\[ (\text{Albert Einstein}, \text{bornIn}, \text{Ulm}) \]

RDF (Resource Description Framework): The W3C standard format for representing triples.

Component Example
Subject dbr:Albert_Einstein
Predicate dbo:birthPlace
Object dbr:Ulm

4.2 SPARQL Queries

SELECT ?person ?birthPlace WHERE {
    ?person rdf:type dbo:Scientist .
    ?person dbo:birthPlace ?birthPlace .
    ?birthPlace dbo:country dbr:Germany .
}

4.3 Knowledge Graph Construction Pipeline

Raw Text → Named Entity Recognition (NER) → Relation Extraction (RE) → Entity Linking (EL) → Knowledge Fusion → Knowledge Graph
Step Task Typical Methods
Entity extraction Identify entities in text BiLSTM-CRF, BERT-NER
Relation extraction Determine relationships between entities Distant supervision, GPT prompting
Entity linking Link mentioned entities to KG nodes Candidate generation + ranking
Knowledge fusion Merge knowledge from different sources Entity alignment, conflict resolution

Major knowledge graphs:

Knowledge Graph Scale Characteristics
Wikidata ~100B triples Open, community-maintained
DBpedia ~3B triples Extracted from Wikipedia
YAGO ~120M triples High precision, spatiotemporal info
Google KG Non-public Search engine backend
ConceptNet ~21M triples Common-sense knowledge

5. Rule Engines

5.1 Production Rules

Production systems represent knowledge using IF-THEN rules:

IF patient.temperature > 38.5°C AND patient.hasCough = true
THEN suspect respiratory_infection (confidence = 0.8)

5.2 Reasoning Directions

Reasoning Mode Description Suitable Scenarios
Forward chaining Start from known facts, apply rules to derive new facts Data-driven, monitoring/alerting
Backward chaining Start from a goal, search backward for supporting facts Goal-driven, diagnostic systems

Forward chaining example (the Rete algorithm enables efficient matching):

Facts: {temperature=39, cough=yes, age=65}
Rule 1: temperature > 38.5 AND cough = yes → respiratory_infection
Rule 2: respiratory_infection AND age > 60 → high_risk_patient
→ Inferred: {respiratory_infection, high_risk_patient}

6. Knowledge Graph Reasoning

6.1 Embedding Methods

Knowledge Graph Embeddings map entities and relations to low-dimensional vector spaces for link prediction and completion.

Model Scoring Function Characteristics
TransE \(\|\mathbf{h} + \mathbf{r} - \mathbf{t}\|\) Simple and efficient; struggles with one-to-many relations
TransR \(\|\mathbf{M}_r \mathbf{h} + \mathbf{r} - \mathbf{M}_r \mathbf{t}\|\) Relation-specific projection
DistMult \(\langle \mathbf{h}, \mathbf{r}, \mathbf{t} \rangle\) Bilinear model; handles only symmetric relations
ComplEx \(\text{Re}(\langle \mathbf{h}, \mathbf{r}, \bar{\mathbf{t}} \rangle)\) Complex-valued space; handles asymmetric relations
RotatE \(\|\mathbf{h} \circ \mathbf{r} - \mathbf{t}\|\) Rotation-based; models diverse relation patterns

Training objective: Maximize the scores of positive triples and minimize the scores of negative triples (contrastive learning).

6.2 Rule-Based Reasoning

  • Path Ranking Algorithm (PRA): Discovers inference paths between relations
  • Inductive Logic Programming (ILP): Learns logical rules from data
  • AnyBURL: An efficient rule-based KG reasoning system

7. Knowledge Graphs + LLMs

7.1 Knowledge Graphs in RAG

Traditional RAG (Retrieval-Augmented Generation) relies on unstructured text retrieval. Incorporating knowledge graphs into RAG can:

  • Provide structured context to reduce hallucinations
  • Support multi-hop reasoning (reasoning along graph paths)
  • Enhance entity disambiguation capabilities

GraphRAG Architecture:

User Question → Entity Recognition → Subgraph Retrieval → Subgraph Serialization → LLM Answer Generation

7.2 Knowledge-Enhanced Generation

Approach Description
KG-grounded generation Inject KG triples as prompt context for the LLM
KG-guided retrieval Use KG structure to guide document retrieval
LLM-augmented KG Use LLMs to assist in KG construction and completion
Neuro-symbolic reasoning Combine LLM language capabilities with KG reasoning capabilities

7.3 Challenges and Outlook

Challenge Description
Knowledge freshness KG updates lag behind the real world
Scale and efficiency Real-time querying and reasoning over large-scale KGs
Knowledge conflicts Inconsistencies between KG knowledge and LLM parametric knowledge
Incompleteness Existing KGs are far from covering all knowledge
Multimodal knowledge Unified representation of text, images, tables, and other modalities

Emerging Trends

Knowledge representation is moving from purely symbolic approaches toward neuro-symbolic integration (Neuro-Symbolic AI): using neural networks for perception and language understanding, and symbolic systems for precise reasoning and knowledge management. This integration is considered one of the key pathways toward more capable AI.

References

  • Brachman & Levesque, Knowledge Representation and Reasoning
  • Hogan et al., "Knowledge Graphs" (ACM Computing Surveys, 2021)
  • Pan et al., "Unifying Large Language Models and Knowledge Graphs: A Roadmap" (2024)
  • W3C OWL 2 Web Ontology Language
  • Stanford Protege

评论 #