Knowledge Representation: Schemas, Semantic Networks, Frames, Logic, and Issues

TAKEAWAYS:

• Knowledge representation (KR) is the process of encoding facts, rules, and relationships in a form AI systems can process (e.g., semantic networks, frames, or logic).
• Semantic networks use nodes (concepts) and edges (relationships) to model hierarchical or associative knowledge (e.g., "Dog → Animal → Mammal").
• Frames organize knowledge into templates with slots, values, and default rules (e.g., a "Car" frame with slots for "make," "model," and "fuel_type").
• Predicate calculus (first-order logic) represents statements as predicates (e.g., Parent(X, Y)) and uses inference rules to derive new knowledge.
• Common issues in KR include ambiguity, redundancy, and scalability, solved by normalization, ontologies, or modular designs.
• Real-world systems like eSewa’s transaction validation and Pathao’s route optimization rely on KR to structure and retrieve dynamic knowledge efficiently.

1. Introduction to Knowledge Representation

Knowledge representation (KR) is the foundation of AI systems that need to reason, learn, or make decisions. It involves encoding human-like knowledge into a structured format that computers can manipulate. Without effective KR, AI lacks the ability to understand context, infer new facts, or adapt to new information.

Why Represent Knowledge?

AI systems must:

• Store facts (e.g., "Nepal’s capital is Kathmandu").
• Apply rules (e.g., "If temperature > 30°C, then suggest AC").
• Infer new knowledge (e.g., "If X is a mammal and Y is a mammal, then X and Y share DNA").
• Handle uncertainty (e.g., "There’s a 70% chance of rain today").

2. Representation Schemes

Different KR schemes suit different tasks. Below are the most common ones, with visual examples and trade-offs.

2.1 Semantic Networks

Semantic networks represent knowledge as nodes (concepts) connected by edges (relationships). They excel at modeling hierarchical or associative knowledge.

Key Components:

• Nodes: Entities (e.g., "Person," "City").
• Edges: Relationships (e.g., "is-a," "has-part," "lives-in").
• Arcs: Directed edges with labels (e.g., → for "is-a," --> for "has").

Example: Family Tree

graph TD
    A["John"] -->|"is-a"| B["Person"]
    B -->|"is-a"| C["Human"]
    C -->|"is-a"| D["Animal"]
    A -->|"has-child"| E["Alice"]
    E -->|"lives-in"| F["Kathmandu"]
    F -->|"is-a"| G["City"]

Worked Example: Daraz’s Product Hierarchy Daraz uses semantic networks to categorize products. For instance:

• Electronics → Smartphone → iPhone 15 → has-specification["6GB RAM"] This allows quick retrieval of products under "Smartphones" or filtering by specs.

Advantages:

• Intuitive for humans (mirrors how we think).
• Supports inheritance (e.g., "Bird" inherits "can-fly" from "Animal").
• Easy to visualize and extend.

Disadvantages:

• Can become complex or cyclic (e.g., "A → B → A").
• Struggles with numerical or procedural knowledge.

2.2 Frames

Frames are data structures that organize knowledge into templates with slots, fillers (values), and default rules. They are useful for modeling stereotypical objects (e.g., "Car," "University").

Structure of a Frame:

graph TD
    A["Car"] --> B["Slots"]
    B --> C["make: Toyota"]
    B --> D["model: Corolla"]
    B --> E["fuel_type: Hybrid"]
    B --> F["default_speed: 120 km/h"]
    B --> G["methods: start_engine(), stop_engine()"]

Example: University Frame

graph TD
    A["University"] --> B["Slots"]
    B --> C["name: TU"]
    B --> D["location: Kathmandu"]
    B --> E["departments: [CS, EE, Medicine]"]
    B --> F["default_fee: 50,000 NPR"]
    B --> G["methods: enroll_student(), issue_certificate()"]

Worked Example: NTC’s Network Node Frame NTC’s network management system might use frames to represent routers:

Router["R1"]
  - location: "Kathmandu Data Center"
  - connected_to: ["R2", "R3"]
  - default_gateway: "192.168.1.1"
  - methods: [ping(), configure(), monitor_traffic()]

This allows quick lookup of connected nodes or traffic patterns.

Advantages:

• Modular and reusable (e.g., a "Person" frame can be inherited by "Student").
• Supports default values and methods (e.g., "Car" defaults to "4 wheels").
• Good for structured data (e.g., databases, expert systems).

Disadvantages:

• Overhead in defining slots and inheritance.
• Hard to represent vague or probabilistic knowledge.

2.3 Predicate Calculus (First-Order Logic)

Predicate calculus is a formal language for representing knowledge using predicates, quantifiers, and logical operators. It is the backbone of symbolic AI and expert systems.

Syntax:

• Predicates: Relations (e.g., Parent(X, Y), Student(X, "TU")).
• Quantifiers: ∀ (for all), ∃ (there exists).
• Connectives: ∧ (and), ∨ (or), → (implies), ¬ (not).

Example Statements:

1. Parent(john, alice) → "John is the parent of Alice."
2. ∀x (Student(x, "TU") → Enrolled(x)) → "All TU students are enrolled."
3. ∃y (Doctor(y) ∧ Treats(y, "COVID-19")) → "There exists a doctor who treats COVID-19."

Worked Example: Loan Eligibility (NMB Bank) A bank might represent loan eligibility as:

∀x (∃y (Salary(y, x) ≥ 50000) ∧ ∃z (CreditScore(z, x) ≥ 700) → EligibleForLoan(x))

Translation: "If a person’s salary is ≥ 50,000 NPR AND their credit score is ≥ 700, then they are eligible for a loan."

Advantages:

• Precise and unambiguous (mathematically sound).
• Supports complex reasoning (e.g., proofs, deductions).
• Used in theorem provers and expert systems.

Disadvantages:

• Verbose for large knowledge bases.
• Struggles with uncertainty or vague concepts (e.g., "tall," "expensive").

2.4 Comparison of Representation Schemes

3. Knowledge Representation Issues

No KR scheme is perfect. Common issues include:

3.1 Ambiguity

• Problem: Same representation can mean different things (e.g., "Bank" could mean financial institution or riverside).
• Solution: Use ontologies (formal definitions of terms) or contextual constraints.

3.2 Redundancy

• Problem: Same knowledge is stored multiple times (e.g., repeating "Kathmandu is the capital" in multiple frames).
• Solution: Normalization (store facts once and reference them).

3.3 Scalability

• Problem: Large knowledge bases become slow or unwieldy (e.g., a semantic network with 10,000 nodes).
• Solution: Modular design (split into smaller ontologies) or distributed KR (e.g., graph databases).

3.4 Dynamic Knowledge

• Problem: Real-world knowledge changes (e.g., a product’s price updates daily).
• Solution: Incremental updates (e.g., frames with versioning) or rule-based systems.

4. Solutions to Common Issues

5. Real-World Applications

In the Real World

1. eSewa’s Transaction Validation

   • Idea Used: Predicate Calculus + Frames
   • How: eSewa’s system uses rules like:

     ∀x (User(x) ∧ Balance(x) ≥ Amount ∧ Transaction(x, y, Amount) → Approve(x))
     

     This ensures transactions are only approved if the user has sufficient balance. Frames store user details (e.g., User["Alice"] → balance: 1000).

2. Pathao’s Route Optimization

   • Idea Used: Semantic Networks + Graph Theory
   • How: Pathao models cities, roads, and traffic as a semantic network:

     Kathmandu -->[road]--> Lalitpur -->[road]--> Bhaktapur
     

     Then applies shortest-path algorithms (e.g., Dijkstra’s) to suggest routes dynamically.

3. NEPSE’s Stock Market Analysis

   • Idea Used: Frames + Temporal Logic
   • How: Stocks are represented as frames with slots for price, volume, and trends. Temporal logic tracks changes over time (e.g., "If price > 50-day avg, then Buy signal").

6. Worked Example: Representing a Library System

Scenario: Represent a library’s books, authors, and loans using frames and semantic networks.

Step 1: Define Frames

graph TD
    A["Book"] --> B["Slots"]
    B --> C["title: The Hobbit"]
    B --> D["author: J.R.R. Tolkien"]
    B --> E["published_year: 1937"]
    B --> F["available: true"]
    B --> G["methods: check_out(), return()"]

graph TD
    A["Author"] --> B["Slots"]
    B --> C["name: J.R.R. Tolkien"]
    B --> D["nationality: British"]
    B --> E["books: [The Hobbit, Lord of the Rings]"]

Step 2: Semantic Network for Relationships

graph TD
    A["The Hobbit"] -->|"authored-by"| B["J.R.R. Tolkien"]
    B -->|"is-a"| C["Author"]
    A -->|"published-in"| D["1937"]
    A -->|"located-in"| E["TU Library"]
    E -->|"is-a"| F["Library"]

Step 3: Loan Logic (Predicate Calculus)

∀x (Book(x) ∧ Available(x) ∧ ∃y (User(y) ∧ CheckOut(x, y)) → UpdateStatus(x, "CheckedOut"))

Translation: "If a book is available and a user checks it out, update its status to 'CheckedOut.'"

7. Exam Tip

• Focus on definitions: Know the exact definitions of semantic networks, frames, and predicate calculus (e.g., "A semantic network is a directed graph where nodes represent concepts and edges represent relationships").
• Draw diagrams: Always include visuals for semantic networks, frames, or predicate logic statements. Partial marks are lost without diagrams.
• Compare schemes: Be ready to compare two schemes (e.g., "Why use frames over semantic networks for a university database?").
• Apply to real-world: Link examples to Nepali companies (e.g., Daraz, NTC) or global apps (e.g., WhatsApp’s message routing).
• Address issues: For questions on KR issues, name the issue, explain it, and propose a solution (e.g., "Ambiguity can be solved using ontologies like WordNet").
• Show inference: If asked about reasoning, write a predicate calculus statement and derive a new fact (e.g., from Parent(X, Y) and Grandparent(Z, X), infer Grandparent(Z, Y)).

Example Exam Answer Structure: Q: Define knowledge representation system. How can you represent knowledge using semantic network? Illustrate with an example. A: A knowledge representation system (KRS) is a framework that encodes human-like knowledge into a structured format (e.g., frames, logic, or networks) so AI systems can process, reason, and retrieve it.

Semantic Networks represent knowledge as nodes (concepts) connected by labeled edges (relationships). For example:

graph TD
    A["Dog"] -->|"is-a"| B["Animal"]
    B -->|"is-a"| C["Mammal"]
    A -->|"has-part"| D["Tail"]
    D -->|"is-a"| E["BodyPart"]

Here, "Dog" is connected to "Animal" via the is-a relationship, showing inheritance. The edge "has-part" links "Dog" to "Tail," modeling composition.

Real-World Tie: Pathao’s route planner uses semantic networks to model cities (Kathmandu → Lalitpur) and traffic rules (road → speed_limit), enabling efficient pathfinding.