Knowledge Representation Fundamentals: Encoding Knowledge

Introduction

Knowledge representation (KR) is the field concerned with how to formally represent knowledge so that it can be used by automated reasoning systems. The fundamental challenge is: how do we encode what we know about the world in a form that machines can reason about? This article explores knowledge representation techniques, formalisms, and applications.

Historical Context

Knowledge representation emerged as a field in the 1970s with work on semantic networks and frames. Early AI systems like MYCIN used rule-based representations. The field has evolved to include description logics, ontologies, and semantic web technologies. Modern knowledge representation combines logical foundations with practical engineering to support large-scale knowledge bases.

Core Concepts

Knowledge vs Data

Data: Raw facts without interpretation

• Example: “John 30 Engineer”

Knowledge: Interpreted, structured information

• Example: “John is a 30-year-old engineer”

Knowledge Representation: Formal encoding of knowledge

Representation Formalisms

Logic-Based: Use formal logic (first-order logic, description logic) Semantic Networks: Graph-based representation Frames: Object-oriented representation Rules: If-then rules Ontologies: Formal specifications of concepts and relationships

Logic-Based Representation

First-Order Logic

Advantages: Expressive, well-understood Disadvantage: Undecidable, can be inefficient

Example:

∀x (Engineer(x) → Employed(x))
∀x (Employed(x) → HasIncome(x))
Engineer(John)

Description Logic

Advantages: Decidable, efficient reasoning Disadvantage: Less expressive than first-order logic

Example:

Engineer ⊆ Employed
Employed ⊆ HasIncome
John : Engineer

Semantic Networks

Structure

Nodes: Concepts or entities Edges: Relationships between concepts

Example:

    Engineer
      ↑ is-a
    John
      ↓ works-for
    Company

Advantages

• Intuitive visual representation
• Efficient for certain queries
• Natural for hierarchical knowledge

Disadvantages

• Limited expressiveness
• Ambiguous semantics
• Difficult to handle complex constraints

Frame-Based Representation

Frames

Definition: Object-oriented representation with slots and values

Structure:

Frame: Engineer
  Slots:
    - name: string
    - salary: number
    - company: Company
    - skills: list of Skill

Advantages: Organized, supports inheritance Disadvantage: Limited reasoning capabilities

Rule-Based Representation

Production Rules

Format: IF condition THEN action

Example:

IF patient has fever AND patient has cough
THEN patient might have flu

Advantages: Intuitive, efficient Disadvantage: Limited expressiveness

Rule Chaining

Forward Chaining: Start with facts, apply rules to derive new facts Backward Chaining: Start with goal, find rules that prove it

Ontologies

Definition

Ontology: Formal specification of concepts, properties, and relationships in a domain

Components:

• Concepts: Classes of entities
• Properties: Attributes and relationships
• Constraints: Rules and restrictions
• Instances: Specific entities

Example: Medical Ontology

Concept: Disease
  Properties: name, symptoms, treatment
  
Concept: Symptom
  Properties: name, severity
  
Relationship: causes (Disease → Symptom)
Relationship: treats (Treatment → Disease)

Instance: Flu
  Type: Disease
  Symptoms: fever, cough
  Treatment: rest, fluids

Ontology Languages

RDF: Resource Description Framework (triples) OWL: Web Ontology Language (description logic) SKOS: Simple Knowledge Organization System

Knowledge Bases

Structure

Terminological Box (TBox): Concepts and relationships Assertional Box (ABox): Facts about individuals

Example:

TBox:
  Engineer ⊆ Employed
  Employed ⊆ Person

ABox:
  John : Engineer
  John works-for Company-A

Reasoning Tasks

Consistency Checking: Is knowledge base consistent? Classification: What concepts does entity belong to? Retrieval: Find entities satisfying conditions Entailment: Does KB entail a statement?

Practical Example: University Domain

Concepts

Person
  ├─ Student
  ├─ Faculty
  └─ Staff

Course
  ├─ Lecture
  └─ Lab

Department

Properties

Person:
  - name: string
  - email: string
  - phone: string

Student:
  - studentID: string
  - major: Department
  - gpa: number

Faculty:
  - facultyID: string
  - department: Department
  - courses: list of Course

Course:
  - courseID: string
  - title: string
  - instructor: Faculty
  - students: list of Student

Relationships

teaches: Faculty → Course
enrolls: Student → Course
works-in: Faculty → Department
offers: Department → Course

Rules

IF Student enrolls in Course
AND Faculty teaches Course
THEN Faculty advises Student

IF Faculty teaches Course
AND Course in Department
THEN Faculty works-in Department

Knowledge Representation Challenges

Expressiveness vs Efficiency

Challenge: More expressive formalisms are harder to reason about Solution: Choose formalism matching problem requirements

Completeness

Challenge: Real-world knowledge is incomplete Solution: Use default reasoning, non-monotonic logic

Consistency

Challenge: Knowledge bases may contain contradictions Solution: Consistency checking, conflict resolution

Scalability

Challenge: Large knowledge bases are hard to manage Solution: Modular ontologies, distributed reasoning

Glossary

Assertion: Fact about specific entity Concept: Class of entities Constraint: Restriction on values Entailment: Logical consequence Frame: Object-oriented representation Ontology: Formal specification of domain Property: Attribute or relationship Reasoning: Deriving new knowledge Semantic Network: Graph-based representation Slot: Attribute in frame

Practice Problems

Problem 1: Represent “All engineers are employed” in first-order logic.

Solution:

∀x (Engineer(x) → Employed(x))

Problem 2: Create a semantic network for a university domain.

Solution:

University
  ├─ has-department → Department
  ├─ has-student → Student
  └─ has-faculty → Faculty

Department
  ├─ offers → Course
  └─ employs → Faculty

Faculty
  ├─ teaches → Course
  └─ advises → Student

Student
  ├─ enrolls-in → Course
  └─ majors-in → Department

Problem 3: Write rules for a medical diagnosis system.

Solution:

IF patient has fever AND patient has cough
THEN patient might have flu

IF patient has fever AND patient has rash
THEN patient might have measles

IF patient has shortness-of-breath AND patient has chest-pain
THEN patient might have heart-disease

Related Resources

• Knowledge Representation: https://en.wikipedia.org/wiki/Knowledge_representation_and_reasoning
• Ontology: https://en.wikipedia.org/wiki/Ontology_(information_science)
• Semantic Networks: https://en.wikipedia.org/wiki/Semantic_network
• Description Logic: https://en.wikipedia.org/wiki/Description_logic
• OWL: https://www.w3.org/OWL/
• RDF: https://www.w3.org/RDF/
• SKOS: https://www.w3.org/2004/02/skos/
• Frames: https://en.wikipedia.org/wiki/Frame_(artificial_intelligence)
• Production Rules: https://en.wikipedia.org/wiki/Production_system
• Expert Systems: https://en.wikipedia.org/wiki/Expert_system
• Semantic Web: https://en.wikipedia.org/wiki/Semantic_Web
• Knowledge Graphs: https://en.wikipedia.org/wiki/Knowledge_graph
• Reasoning: https://en.wikipedia.org/wiki/Automated_reasoning
• Logic Programming: https://en.wikipedia.org/wiki/Logic_programming
• Artificial Intelligence: https://en.wikipedia.org/wiki/Artificial_intelligence

Conclusion

Knowledge representation is fundamental to artificial intelligence and automated reasoning. By formally encoding knowledge, we enable machines to reason about complex domains, answer questions, and solve problems. The choice of representation formalism significantly impacts the efficiency and effectiveness of reasoning.

Understanding knowledge representation is essential for anyone working in AI, knowledge management, or semantic technologies. As knowledge bases grow larger and more complex, effective representation techniques become increasingly important.