Probabilistic Reasoning & Semantic Networks: Bayesian Nets, Graphical Models & Knowledge Representation

Core Concepts

1. Probabilistic Reasoning: Why Logic Fails

Traditional AI uses Boolean logic (true/false), but real-world data is uncertain. Probabilistic reasoning quantifies uncertainty using probabilities (0 to 1) and conditional probabilities $P(A|B)$ ("probability of A given B").

Example in Nepal:

• eSewa’s "Is this transaction fraudulent?" system doesn’t wait for 100% certainty. It uses probabilities like:
  • $P(\text{Fraud}|\text{High\_Amount}\wedge \text{Unusual\_Location})=0.85$
  • $P(\text{Fraud}|\text{Normal\_Amount}\wedge \text{Regular\_User})=0.01$

Visual: This is a naive Bayes classifier (a simple probabilistic model).

2. Semantic Networks: Representing Knowledge as Graphs

Semantic networks store facts as nodes (concepts) and edges (relationships). They answer queries by traversing the graph.

Example: Facts:

• Ram is a person.
• Persons are humans.
• Humans have noses.
• Ram weighs 60 kg.
• Ram’s weight < Sita’s weight.

Semantic Network:

graph TD
    Ram["Ram"] -->|"is-a"| Person["Person"]
    Person -->|"is-a"| Human["Human"]
    Human -->|"has"| Nose["Nose"]
    Ram -->|"has-weight"| Weight_Ram["60 kg"]
    Weight_Ram -->|"<"| Weight_Sita["Sita's weight"]

Query: "Does Ram have a nose?" Answer: Traverse Ram → Person → Human → Nose. Yes.

Real-world use in Nepal:

• NTC’s traffic route optimization uses semantic networks to represent:
  • Roads as nodes, traffic rules as edges.
  • Query: "Is there a shorter route from Kathmandu to Pokhara avoiding tolls?"
  • Answer: Traverse the graph while avoiding "toll" edges.

3. Bayesian Networks: Probabilistic Graphical Models

Bayesian networks (BNs) are directed acyclic graphs (DAGs) where:

• Nodes = random variables (e.g., Rain, Slippery).
• Edges = conditional dependencies.
• Each node has a conditional probability table (CPT).

Example: Given:

• $P(\text{Cloudy})=0.5$
• $P(\text{Rain}|\text{Cloudy}\wedge \text{Winter})=0.3$
• $P(\text{Winter})=0.4$

Bayesian Network:

graph TD
    Winter["Winter"] -->|"0.4"| Rain["Rain"]
    Cloudy["Cloudy"] -->|"0.5"| Rain
    Rain -->|"0.3"| Umbrella["Take Umbrella"]

Query: "What’s $P(\text{Rain})$?" Solution: Use the law of total probability: $$P(\text{Rain})=P(\text{Rain}|\text{Cloudy})\cdot P(\text{Cloudy})+P(\text{Rain}|\neg \text{Cloudy})\cdot P(\neg \text{Cloudy})$$ Assume:

• $P(\text{Rain}|\text{Cloudy})=0.7$
• $P(\text{Rain}|\neg \text{Cloudy})=0.1$ Then: $$P(\text{Rain})=0.7\times 0.5+0.1\times 0.5=0.35+0.05=0.4$$

Real-world use:

• Khalti’s fraud detection uses BNs to model:
  • Nodes: High_Transaction, New_Device, Fraud.
  • Edge: High_Transaction → Fraud with $P(\text{Fraud}|\text{High\_Transaction})=0.6$.

4. Markov Networks: Undirected Probabilistic Graphs

Unlike BNs (directed), Markov networks have undirected edges and use clique potentials (probabilities for groups of nodes).

Example: Modeling student performance in TU exams:

• Nodes: Study_Hours, Sleep, Exam_Score.
• Edges: Study_Hours ↔ Exam_Score, Sleep ↔ Exam_Score.
• CPT for Exam_Score depends on both Study_Hours and Sleep.

Graph:

graph TD
    Study["Study Hours"] --|""|-- Score["Exam Score"]
    Sleep["Sleep"] --|""|-- Score

Query: "What’s the probability of scoring >80 if you study 10 hours but sleep 5 hours?" Solution: Use the Markov property: The score depends only on its neighbors (Study_Hours, Sleep), not on other variables.

5. Inference in Probabilistic Models

Two key methods:

1. Exact Inference (for small networks):
   • Enumeration of all possibilities (brute-force).
   • Variable elimination: Remove variables one by one.
2. Approximate Inference (for large networks):
   • Loopy Belief Propagation (LBP).
   • Markov Chain Monte Carlo (MCMC).

Worked Example: Exact Inference Given the BN:

graph TD
    A["A"] --> B["B"]
    B --> C["C"]

CPTs:

• $P(A=\text{True})=0.5$
• $P(B=\text{True}|A=\text{True})=0.8$, $P(B=\text{True}|A=\text{False})=0.3$
• $P(C=\text{True}|B=\text{True})=0.9$, $P(C=\text{True}|B=\text{False})=0.2$

Query: $P(C=\text{True})$ Solution: Use the law of total probability: $$P(C)=P(C|B=\text{True})\cdot P(B=\text{True})+P(C|B=\text{False})\cdot P(B=\text{False})$$ First, compute $P(B)$: $$P(B=\text{True})=P(B|A=\text{True})\cdot P(A)+P(B|A=\text{False})\cdot P(A)$$ $$P(B=\text{True})=0.8\times 0.5+0.3\times 0.5=0.4+0.15=0.55$$ Then: $$P(C=\text{True})=0.9\times 0.55+0.2\times (1-0.55)=0.495+0.09=0.585$$

6. Semantic Networks vs. Bayesian Networks

7. Learning Probabilistic Models

From data, we learn the structure and parameters of a BN:

1. Structure Learning:
   • Score-based methods: Score each possible DAG using data (e.g., Bayesian Dirichlet equivalent uniform).
   • Constraint-based methods: Use conditional independence tests (e.g., PC algorithm).
2. Parameter Learning:
   • Maximum Likelihood Estimation (MLE): For a binary node $X$ with parent $Y$, estimate $P(X|Y)$ from data.
   • Bayesian Estimation: Use priors to avoid overfitting.

Example: Learning $P(\text{Rain}|\text{Cloudy})$ Data:

MLE estimate: $$P(\text{Rain}|\text{Cloudy})=\frac{\text{Count}(\text{Rain}\wedge \text{Cloudy})}{\text{Count}(\text{Cloudy})}=\frac{3}{4}=0.75$$

8. Applications in Nepal

9. Limitations and Challenges

• Curse of Dimensionality: Probabilities become unreliable with many variables.
• Data Hunger: Requires large datasets for accurate parameter learning.
• Computational Cost: Exact inference is NP-hard for large BNs.
• Assumption of Conditional Independence: BNs assume variables are independent given their parents (often unrealistic).

Example of Failure:

• A BN modeling student performance might assume Sleep and Study_Hours are independent given Exam_Score, but in reality, they might interact (e.g., studying late reduces sleep, which hurts performance).

In the Real World

1. Khalti’s Fraud Detection

   • Model: Bayesian Network with nodes like Transaction_Amount, Device_Type, Location, and Fraud.
   • How it works: For a transaction of ₹50,000 from a new device in Kathmandu at 3 AM, the system computes: $$P(\text{Fraud}|\text{High\_Amount}\wedge \text{New\_Device}\wedge \text{Unusual\_Time})=0.92$$
   • Outcome: Blocks the transaction and asks for OTP verification.

2. NTC’s Traffic Management

   • Model: Markov Network where roads are nodes and traffic rules are edges.
   • How it works: If Ringroad is congested (probability >0.8), the system reroutes buses via Swoyambhu Marg with probability 0.65.
   • Outcome: Reduces average wait time by 20%.

3. Ncell’s Network Optimization

   • Model: Hidden Markov Model (HMM) to predict signal drops.
   • How it works: If $P(\text{Signal\_Drop}|\text{High\_Usage}\wedge \text{Rainy\_Day})=0.7$, the system preemptively increases tower power in that area.
   • Outcome: Reduces call drops by 30% during monsoon.

Exam Tip

What Examiners Look For

1. Semantic Networks:

   • Draw the graph correctly (nodes = concepts, edges = relationships).
   • Label edges with relationship types (is-a, has-a, <).
   • Answer queries by traversing the graph (show steps).

2. Bayesian Networks:

   • Define CPTs clearly (show tables for binary variables).
   • Use probability rules (chain rule, law of total probability) to compute queries.
   • For inference, show all intermediate steps (don’t skip calculations).

3. Comparisons:

   • Contrast semantic networks (logic) vs. Bayesian networks (probabilities).
   • Explain when to use exact vs. approximate inference.

4. Real-world Tie-ins:

   • Link examples to Nepali companies (eSewa, Khalti, NTC).
   • Use small numbers (e.g., $P(A)=0.5$, $P(B|A)=0.8$) for calculations.

Common Mistakes to Avoid

• Forgetting conditional probabilities: Always use $P(A|B)$, not $P(A)$.
• Incorrect graph structure: Ensure edges represent causal dependencies.
• Skipping normalization: Probabilities must sum to 1.
• Overcomplicating: Stick to binary or small discrete variables in exams.

Sample Exam Question & Answer

Question: Construct a Bayesian network for the following facts:

• $P(\text{Cloudy})=0.4$
• $P(\text{Rain}|\text{Cloudy})=0.7$, $P(\text{Rain}|\neg \text{Cloudy})=0.1$
• $P(\text{Slippery}|\text{Rain})=0.9$, $P(\text{Slippery}|\neg \text{Rain})=0.2$ Compute $P(\text{Slippery})$.

Answer:

1. Bayesian Network:

   graph TD
       Cloudy["Cloudy"] --> Rain["Rain"]
       Rain --> Slippery["Slippery"]

2. Compute $P(\text{Rain})$: $$P(\text{Rain})=P(\text{Rain}|\text{Cloudy})\cdot P(\text{Cloudy})+P(\text{Rain}|\neg \text{Cloudy})\cdot P(\neg \text{Cloudy})$$ $$P(\text{Rain})=0.7\times 0.4+0.1\times 0.6=0.28+0.06=0.34$$
3. Compute $P(\text{Slippery})$: $$P(\text{Slippery})=P(\text{Slippery}|\text{Rain})\cdot P(\text{Rain})+P(\text{Slippery}|\neg \text{Rain})\cdot P(\neg \text{Rain})$$ [ P(\text{Slippery}) = 0.9 \times 0.34 + 0.2 \times (1 - 0.34) = 0.306 + 0.132 = 0.438

---