Knowledge Representation & Reasoning: Frames, Scripts, Semantic Nets, Logic

Core Concepts & Representations

1. First-Order Predicate Logic (FoPL)

FoPL extends propositional logic by introducing predicates, quantifiers (∀, ∃), and variables to represent complex relationships.

How it works

• Predicates: Functions that return true/false (e.g., Chases(Traffic, Driver)).
• Quantifiers:
  • Universal (∀): "For all" (e.g., ∀x (Driver(x) → Honks(x))).
  • Existential (∃): "There exists" (e.g., ∃x (Traffic(x) ∧ Frustrated(x))).
• Variables: Placeholders for objects (e.g., x, y).

Worked Example: Traffic & Drivers

Facts:

1. Every traffic chases a driver: ∀x (Traffic(x) → ∃y (Driver(y) ∧ Chases(x, y)))
2. Drivers who horn are smart: ∀x (Horns(x) → Smart(x))
3. No traffic catches a smart driver: ∀x (Smart(x) → ¬∃y (Traffic(y) ∧ Catches(y, x)))
4. Traffic that chases but doesn’t catch is frustrated: ∀x ∀y (Chases(x, y) ∧ ¬Catches(x, y) → Frustrated(x))

Inference:

• If Traffic(T1) and Chases(T1, D1) and ¬Catches(T1, D1), then Frustrated(T1).
• If Horns(D2), then Smart(D2), so ¬∃x (Traffic(x) ∧ Catches(x, D2)).

Real-World Tie-In: eSewa’s Fraud Detection

eSewa uses FoPL-like rules to flag suspicious transactions:

• ∀x (Transaction(x) ∧ HighRisk(x) → Block(x))
• ∀x (User(x) ∧ ¬Verified(x) → HighRisk(Transaction(x))) If a user is unverified (¬Verified(U1)) and makes a transaction (Transaction(T1)), eSewa blocks it (Block(T1)).

2. Frames: Structured Knowledge Representation

Frames organize knowledge into slots (attributes) and default values for objects.

Definition

A frame is a data structure representing a stereotyped situation (e.g., a person, a car, a restaurant).

• Slots: Attributes (e.g., name, age, department).
• Slot fillers: Values (e.g., Ram for name).
• Default values: Assumed if unspecified (e.g., gender: male).
• If-needed/if-added: Rules for dynamic updates.

Example: Employee Frame

classDiagram
    class Employee {
        +name: string
        +age: int
        +gender: string
        +department: string
        +salary: float
        +is_active: boolean
    }
    class Department {
        +name: string
        +employees: int
    }
    Employee "1" --> "1" Department : belongs_to

Knowledge Base:

Frame: Employee
    Slot: name = "Ram"
    Slot: age = 27
    Slot: gender = male
    Slot: department = HR
    Slot: salary = 50000
    Default: is_active = true
    If-needed: salary = (age * 2000) + 10000

Advantages/Disadvantages

Real-World Tie-In: Khalti’s User Profiles

Khalti stores user data in frame-like structures:

• Slot: user_id, balance, transaction_history, kyc_verified.
• Default: kyc_verified = false (until user submits documents).
• If-added: If kyc_verified = true, unlock loan_eligibility.

3. Scripts: Event Sequences

Scripts represent procedural knowledge—sequences of actions for common scenarios (e.g., "going to a restaurant").

Structure

1. Roles: Participants (e.g., customer, waiter).
2. Props: Objects involved (e.g., menu, bill).
3. Scenes: Sub-events (e.g., ordering, paying).
4. Result: Outcome (e.g., satisfied/unsatisfied).

Example: Restaurant Script

flowchart LR
    A["Arrive"] --> B["Find Table"]
    B --> C["Waiter Approaches"]
    C --> D["Customer Orders"]
    D --> E["Waiter Takes Order"]
    E --> F["Food Served"]
    F --> G["Customer Pays"]
    G --> H["Receive Bill"]
    H --> I["Leave"]

Knowledge Base:

Script: RestaurantVisit
    Roles: customer, waiter, chef
    Props: menu, order, bill, food
    Scenes:
        1. Customer enters → Waiter greets
        2. Customer orders → Waiter notes order
        3. Chef prepares → Food served
        4. Customer pays → Bill given
    Result: satisfied if food is good

Real-World Tie-In: Daraz’s Order Fulfillment

Daraz uses script-like workflows for order processing:

1. Scene 1: User places order (Props: product, address, payment).
2. Scene 2: Warehouse picks item (Roles: picker, scanner).
3. Scene 3: Courier delivers (Props: tracking ID).
4. Result: OrderStatus = "Delivered" or Failed.

4. Semantic Networks

Semantic networks represent knowledge as nodes (concepts) and edges (relationships).

Components

• Nodes: Objects, actions, or properties (e.g., Ram, student).
• Edges: Relationships (e.g., IS-A, HAS, DOES).
• Inheritance: IS-A links (e.g., Student IS-A Person).

Example: University Hierarchy

Knowledge Base:

Node: Subash
    IS-A: Student
    HAS: hair
    DOES: study
Node: Student
    IS-A: Person
    HAS: ID
    DOES: attend_class

Inference Example

Question: Does Subash have an ID? Trace:

1. Subash IS-A Student (from edge).
2. Student HAS ID (inherited from Student node). Answer: Yes.

Real-World Tie-In: Ncell’s Customer Support

Ncell’s chatbot uses semantic networks to resolve queries:

• Node: Customer
  • HAS: subscription_plan, balance
  • DOES: call, roam
• Node: SubscriptionPlan
  • IS-A: Plan
  • HAS: data_limit, validity
• Inference: If Customer(C1) DOES roam and Plan(P1) HAS roaming_disabled, then Block(C1).

5. Bayesian Networks for Uncertain Knowledge

Bayesian networks represent probabilistic relationships between variables.

Structure

• Nodes: Random variables (e.g., A, B, C).
• Edges: Conditional dependencies.
• CPDs (Conditional Probability Tables): Probabilities for each node given its parents.

Example: CD Size Prediction

Variables:

• A: CD type (Standard/Extended).
• B: Length (120mm/130mm).
• C: Width (120mm/130mm).

CPD for B given A:

Question: What is P(B=130mm | A=Standard)? Answer: Directly from CPD: 0.3.

Joint Probability Example

Given:

• P(A=Standard) = 0.6, P(A=Extended) = 0.4.
• P(B=120|A=Standard) = 0.7, P(B=130|A=Standard) = 0.3.
• P(C=120|B=120) = 0.8, P(C=130|B=130) = 0.9.

Find: P(B=130mm) (marginal probability). Solution:

P(B=130) = P(B=130|A=Standard)*P(A=Standard) + P(B=130|A=Extended)*P(A=Extended)
         = (0.3 * 0.6) + (0.8 * 0.4)
         = 0.18 + 0.32
         = 0.5

Real-World Tie-In: NEPSE Stock Predictions

NEPSE uses Bayesian networks to predict stock prices:

• Nodes:
  • A: Market sentiment (Positive/Negative).
  • B: Trading volume (High/Low).
  • C: Stock price (Rise/Fall).
• Edge: A → C (sentiment affects price).
• CPD: If A=Positive, P(C=Rise) = 0.85.

In the Real World

1. eSewa’s Fraud Rules

   • Uses FoPL-like constraints to block transactions: ∀x (Transaction(x) ∧ UnverifiedUser(x) → Block(x)).
   • Example: If User(U1) has ¬Verified(U1) and makes Transaction(T1), eSewa flags it.

2. Khalti’s KYC Verification

   • Frame-based: User profile has slots like kyc_status, documents_submitted.
   • Default: kyc_status = "Pending" until documents are uploaded.

3. Daraz’s Order Fulfillment Script

   • Script: PlaceOrder → PickItem → Ship → Deliver.
   • If ShippingFailed, trigger RefundCustomer.

4. Ncell’s Chatbot Semantic Network

   • Nodes: Customer, Plan, Roaming.
   • Edge: Customer HAS Plan → If Plan has roaming_disabled, block calls.

5. NTC’s Traffic Prediction

   • Bayesian network with nodes:
     • A: Weather (Rainy/Sunny).
     • B: Time (Peak/Off-peak).
     • C: Traffic (Congested/Smooth).
   • CPD: If A=Rainy and B=Peak, P(C=Congested) = 0.9.

Exam Tip

1. FoPL Questions:

   • Always translate English sentences into logical expressions step-by-step.
   • Use quantifiers (∀/∃) for "all" and "some."
   • For inference, apply resolution rules or modus ponens.

2. Frames/Scripts:

   • Define slots clearly (e.g., name, age for an Employee).
   • For scripts, list scenes in order (e.g., Arrive → Order → Pay).
   • Justify inheritance (e.g., HR inherits from Department).

3. Semantic Networks:

   • Draw IS-A and HAS relationships.
   • For inference, follow edges (e.g., Subash IS-A Student → Student HAS ID).

4. Bayesian Networks:

   • Identify parents/children in the graph.
   • For marginal probabilities, use law of total probability.
   • For conditional probabilities, read from CPD tables.

5. Common Pitfalls:

   • FoPL: Forgetting quantifiers or misplacing them.
   • Frames: Not defining defaults or if-needed rules.
   • Bayesian: Confusing joint vs. conditional probabilities.

Visual Summary