Knowledge Representation: Logics, Frames, Scripts & State Spaces

TAKEAWAYS:

• Knowledge representation is the bridge between raw data and AI reasoning, using structures like predicates, frames, and graphs to model facts and relationships.
• Logical representations (propositional, first-order) enable formal reasoning but struggle with uncertainty and large-scale knowledge.
• Semantic networks and frames organize knowledge hierarchically (e.g., Animal → Dog → Labrador) for efficient inheritance and querying.
• Scripts model sequences of events (e.g., "restaurant visit") while state spaces represent all possible configurations of a problem (e.g., chessboard positions).
• Constraint satisfaction problems (CSPs) use variables and domains to solve puzzles like scheduling or Sudoku.
• Real-world AI (e.g., eSewa’s transaction rules, Pathao’s route planning) relies on these representations to automate decisions.

Core Concepts: What Is Knowledge Representation?

Knowledge representation (KR) is how we encode information so that an AI agent can:

1. Store facts (e.g., "Ram is a student").
2. Infer new facts (e.g., "Ram must pay tuition").
3. Act based on those facts (e.g., "Send a reminder").

Without KR, AI is just a calculator—KR gives it common sense.

Why Does KR Matter?

• Efficiency: A well-structured knowledge base avoids redundant computations.
• Scalability: Hierarchies (e.g., Vehicle → Car → Tesla) let AI reuse information.
• Reasoning: Logical rules (e.g., "If X then Y") enable problem-solving.

1. Logical Representations: Rules and Predicates

Logics are the mathematical backbone of AI reasoning. They let us define facts and rules precisely.

A. Propositional Logic

• Atoms: Simple statements like Raining, TrafficJam.
• Connectives: ¬ (not), ∧ (and), ∨ (or), → (implies).
• Example: Raining → TrafficJam means "If it rains, there will be a traffic jam."

Worked Example: eSewa Transaction Rules Suppose eSewa’s logic for a successful payment is:

(ConnectedToInternet ∧ ValidUser ∧ SufficientBalance) → PaymentSuccess

If all three atoms are true, the payment goes through.

B. First-Order Logic (FOL)

Extends propositional logic with:

• Predicates: Likes(X, Y) = "X likes Y".
• Quantifiers: ∀ (for all), ∃ (there exists).
• Example: ∀x (Student(x) → PaysTuition(x)) = "All students pay tuition."

Worked Example: NEPSE Stock Rules NEPSE’s trading system might use FOL to enforce:

∀s (Listed(s) ∧ HighVolume(s) → AlertTrader(s))

= "Alert traders if a listed stock has high volume."

C. Resolution: How AI "Proves" Things

Resolution is a method to derive new facts from a knowledge base. Steps:

1. Convert all statements to clauses (disjunctions of literals).
   • AvaLikes(Fruit) → AvaLikes(X) ∨ ¬Fruit(X)
2. Apply modus ponens: If P → Q and P are true, then Q is true.
3. Repeat until the goal is found or all possibilities are exhausted.

Worked Example: Proving "Ava Likes Watermelon" Knowledge Base:

1. AvaLikes(X) ∨ ¬Fruit(X) (Ava likes all fruits)
2. Fruit(Apple) ∧ Fruit(Watermelon) (Apple and watermelon are fruits)
3. AvaEats(X) → AvaLikes(X) (If Ava eats X, she likes X)

Goal: Prove AvaLikes(Watermelon) Resolution Steps:

1. From KB2: Fruit(Watermelon) is true.
2. Substitute into KB1: AvaLikes(Watermelon) ∨ ¬Fruit(Watermelon) → AvaLikes(Watermelon) ∨ False → AvaLikes(Watermelon). Conclusion: Ava likes watermelon!

2. Semantic Networks: Nodes and Arcs

Semantic networks represent knowledge as nodes (concepts) connected by arcs (relationships). Example:

Doctor ---(is-a)---> Person
Doctor ---(treats)---> Patient

Types of Arcs:

Worked Example: Pathao’s Route Planning Pathao’s AI uses semantic networks to model:

Kathmandu ---(connected-by)---> Road1 ---(has-speed-limit)---> 60km/h
Road1 ---(leads-to)---> Destination

This helps it avoid congested roads by querying relationships.

3. Frames: Slots and Defaults

Frames are templates for objects with:

• Slots: Attributes (e.g., color, size).
• Default values: Assumed if not specified.
• Facets: Constraints (e.g., color ∈ {red, green, blue}).

Example: A Car Frame

classDiagram
    class Car {
        +make: string
        +model: string
        +color: string [default: "red"]
        +topSpeed: number [range: 0-300]
        +isElectric: boolean [default: false]
    }

Worked Example: Daraz’s Product Catalog Daraz uses frames to store product details:

Frame: Laptop
  Slots:
    - brand: "Dell"
    - ram: 16GB [default: 8GB]
    - price: 89999 [currency: NPR]
    - inStock: true

Inheritance in Frames

Frames can inherit slots from parent frames. Example:

Frame: Vehicle
  Slots: wheels: 4, color: "black"

Frame: Car extends Vehicle
  Slots: topSpeed: 200

Here, Car inherits wheels and color from Vehicle.

4. Scripts: Sequences of Events

Scripts represent stereotypical sequences of actions (e.g., "going to a restaurant"). Structure:

1. Props: Objects involved (e.g., menu, bill).
2. Roles: Participants (e.g., customer, waiter).
3. Scenes: Ordered steps.
   • Enter: Customer walks in.
   • Order: Customer gives menu to waiter.
   • Serve: Waiter brings food.
   • Pay: Customer pays bill.

Worked Example: eSewa Transaction Script

Script: OnlinePayment
  Props: phone, internet, bankAccount
  Roles: user, eSewaServer, bank
  Scenes:
    1. User opens eSewa app.
    2. User enters amount and selects bank.
    3. eSewaServer requests bank for verification.
    4. Bank approves/declines transaction.
    5. User receives confirmation.

5. State Spaces: All Possible Worlds

A state space represents all possible configurations of a problem, with states (configurations) and operators (actions that change states). Example: Chess has ~10⁴³ possible states!

Components:

• Initial State: Starting configuration.
• Goal State: Desired configuration.
• Operators: Legal moves (e.g., in chess: movePawn, castle).

Worked Example: Kathmandu Traffic Routes Imagine modeling traffic as a state space:

• States: Positions of all vehicles on a road.
• Operators: moveCar, changeLane, stopAtSignal.
• Goal: Minimize travel time from A to B.

6. Constraint Satisfaction Problems (CSPs)

CSPs solve problems by assigning values to variables under constraints. Example: Scheduling exams so no student has overlapping classes.

Components:

Worked Example: NTC’s Internet Slot Allocation NTC must assign internet slots to users without overloading servers.

• Variables: User1_slot, User2_slot, ...
• Domains: Morning, Afternoon, Evening
• Constraints:
  • User1_slot ≠ User2_slot (no overlap)
  • Total_users_in_slot ≤ ServerCapacity

7. Issues in Knowledge Representation

No representation is perfect. Common challenges:

In the Real World

AI systems in Nepal and globally rely on these representations daily:

1. eSewa’s Transaction Logic

   • What it uses: Propositional logic for rules like (Connected ∧ ValidUser ∧ SufficientBalance) → Success.
   • How: Encodes every step of a payment as a logical clause to ensure fraud detection and smooth processing.

2. Pathao’s Route Planning

   • What it uses: Semantic networks for roads, constraints for traffic, and state spaces for possible paths.
   • How: Models Kathmandu’s roads as nodes, traffic rules as arcs, and dynamically updates routes based on real-time data.

3. NEPSE’s Trading System

   • What it uses: First-order logic for stock rules (e.g., ∀s (HighVolume(s) → AlertTrader(s))) and CSPs for order matching.
   • How: Ensures no two buyers/sellers get the same stock at conflicting prices.

4. Khalti’s Fraud Detection

   • What it uses: Frames for user profiles (e.g., User {name, transactionHistory, riskScore}) and scripts for transaction flows.
   • How: Flags unusual patterns (e.g., sudden large transactions) by comparing against default user behaviors.

5. NTC’s Network Management

   • What it uses: CSPs to allocate bandwidth and state spaces to model network states.
   • How: Prevents overload by assigning slots dynamically, like a traffic cop for data packets.

Visualizing Knowledge Representation

1. Game Tree: Minimax Algorithm (Chess)

flowchart TD
    A["Root: White to move"] --> B["Move 1: e4"]
    B --> C["Black responds: e5"]
    C --> D["White: Nf3"]
    D --> E["Black: Nc6"]
    D --> F["Black: Bc5"]
    E --> G["Game continues..."]
    F --> H["Game continues..."]

Explored Path: White plays e4, Black responds e5, and White moves Nf3. The tree grows as the game progresses.

2. Neural Network Layers (Simplified)

Real Picture: A labelled diagram showing input neurons, hidden layers with weights, and output neurons. (Image: BrunelloN, CC BY-SA 4.0, via Wikimedia Commons)

3. Decision Tree for Loan Approval (Bank)

Worked Example: Nabil Bank Loan

• Input: Income = 60k, Credit Score = 650.
• Path:
  1. Income > 50k? → Yes.
  2. Credit Score > 700? → No.
  3. Check Collateral? → If Yes, loan approved; else denied.

4. State Space: 8-Puzzle (Sliding Tiles)

Real Picture:

Comparison Table: Knowledge Representations

Exam Tip: How to Score Full Marks

1. Define Clearly: Always start with precise definitions. For example:

   "A frame is a data structure that represents stereotypical objects with slots (attributes) and facets (constraints), enabling inheritance and default values."

2. Use Diagrams: Draw one diagram per question if asked to represent knowledge. For example:

   • For scripts, show scenes as arrows.
   • For semantic networks, label nodes and arcs.
   • For state spaces, mark initial, goal, and explored states.

3. Show Step-by-Step Reasoning: For resolution or CSPs, write each inference or assignment explicitly. Examiners reward clarity.

4. Relate to Real World: Mention one Nepalese example (e.g., eSewa, Pathao) per concept. For instance:

   "Like Pathao’s route planner, semantic networks help AI navigate relationships between roads and traffic rules."

5. Highlight Trade-offs: Compare representations by listing advantages and disadvantages in a table (as shown above).

6. Practice Past Questions:

   • For script representation, expect questions like "Represent ‘buying groceries’ as a script."
   • For resolution, expect proofs like "Show that ‘Ava likes watermelon’ using the given KB."
   • For CSPs, expect problems like "Schedule exams for 3 classes with no overlaps."

Common Pitfalls to Avoid

• Overcomplicating Logics: Stick to propositional or first-order logic unless the question specifies otherwise.
• Ignoring Constraints in CSPs: Always list variables, domains, and constraints explicitly.
• Assuming Inheritance: In frames, not all slots are inherited—only those not overridden.
• Missing the Goal State: In state spaces, always identify the goal before searching.

Summary Checklist

Before the exam, ensure you can: ✅ Define logical representations, semantic networks, frames, scripts, and state spaces. ✅ Draw a semantic network for a given scenario (e.g., "family relationships"). ✅ Write a frame for an object (e.g., "Laptop") with slots and defaults. ✅ Represent a script (e.g., "restaurant visit") with props, roles, and scenes. ✅ Solve a resolution problem step-by-step. ✅ Model a CSP (e.g., "schedule 3 exams") with variables, domains, and constraints. ✅ Explain one real-world application (e.g., Pathao uses semantic networks).