Probabilistic Reasoning

Overview

In the study of Artificial Intelligence, we are often confronted with the challenge of reasoning and making decisions in the presence of uncertainty. The deterministic logic that governs simpler systems is insufficient for modeling the complexities of the real world, where information is frequently incomplete, ambiguous, or subject to noise. Probabilistic reasoning provides a formal and principled framework for representing and manipulating uncertain knowledge. By leveraging the calculus of probability theory, we can construct agents that are capable of weighing evidence, updating their beliefs, and making optimal decisions in situations that are not fully predictable.

This chapter introduces the foundational techniques for probabilistic reasoning, which are central to modern AI and a recurring theme in the GATE examination. We begin by exploring how to represent complex probabilistic domains efficiently using the concept of conditional independence, which is the cornerstone of graphical models such as Bayesian networks. With a model in place, our next objective is to perform inference—that is, to query the model to answer questions of interest, such as determining the probability of an event given some evidence, $P(\text{Query}|\text{Evidence})$ . We shall examine two classes of methods for this task: exact inference, which yields precise results but can be computationally intractable, and approximate inference, which provides estimates when exact computation is not feasible.

A thorough understanding of these topics is indispensable for the GATE aspirant. Questions in this area test not only the theoretical underpinnings of probability but also the ability to apply specific algorithms to practical scenarios. Mastery of representation and inference techniques forms the basis for more advanced subjects, including machine learning and decision theory, making this chapter a critical component of your preparation.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Conditional Independence Representation | Using graphical models for uncertain knowledge. |
| 2 | Exact Inference | Calculating exact posterior probabilities in networks. |
| 3 | Approximate Inference | Estimating probabilities for complex network models. |

---

Learning Objectives

❗ By the End of This Chapter

After completing this chapter, you will be able to:

Formulate probabilistic models using the principles of conditional independence and Bayesian networks.

Apply exact inference algorithms, such as variable elimination, to compute posterior probabilities.

Differentiate between scenarios requiring exact versus approximate inference and apply sampling-based methods.

Analyze and solve GATE-level problems involving probabilistic graphical models and inference techniques.

---

We now turn our attention to Conditional Independence Representation...
## Part 1: Conditional Independence Representation

Introduction

In the domain of probabilistic reasoning, we are often confronted with the task of modeling the joint probability distribution of a large number of random variables. A direct representation of this joint distribution is computationally intractable, suffering from the "curse of dimensionality" as the number of variables grows. The storage and inference costs become prohibitive. The key to overcoming this challenge lies in exploiting the structure inherent in the problem domain, specifically the relationships of independence and conditional independence among variables.

Conditional independence is a foundational concept that allows us to simplify complex probabilistic models. By identifying variables that do not influence each other directly, or become independent once the state of another variable is known, we can decompose a large, monolithic joint distribution into a product of smaller, more manageable conditional probability distributions. This decomposition not only provides an efficient and compact representation but also forms the basis for powerful inference algorithms. Bayesian Networks, the primary focus of our study here, are graphical models that provide a formal and intuitive language for representing these conditional independence assumptions.

---

📖 Conditional Independence

Let $X$ , $Y$ , and $Z$ be three sets of random variables. We say that $X$ is conditionally independent of $Y$ given $Z$ if the probability distribution of $X$ is independent of the value of $Y$ once the value of $Z$ is known. This relationship is denoted by $(X \perp Y | Z)$ .

Formally, this is equivalent to the statement:

P(X | Y, Z) = P(X | Z)

for all possible values of $X, Y,$ and $Z$ for which $P(Y,Z) > 0$ . An equivalent formulation, which is often more useful, is:

P(X, Y | Z) = P(X | Z) P(Y | Z)

---

Key Concepts

1. The Chain Rule of Probability

Any joint probability distribution over a set of random variables can be expressed as a product of conditional probabilities. This fundamental rule, known as the chain rule of probability, provides a way to decompose the joint distribution without making any assumptions.

Consider a set of $n$ random variables, $\{X_1, X_2, \dots, X_n\}$ . The chain rule allows us to write their joint probability as:

P(X_1, X_2, \dots, X_n) = P(X_1) P(X_2 | X_1) P(X_3 | X_1, X_2) \cdots P(X_n | X_1, \dots, X_{n-1})

This can be expressed more compactly.

📐 Chain Rule of Probability

P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i | X_1, \dots, X_{i-1})

Variables:

$X_1, \dots, X_n$ are random variables.

When to use: This is a universally true decomposition. In the context of graphical models, it serves as the starting point which is then simplified using conditional independence assumptions encoded in the model's structure.

While universally applicable, the general form of the chain rule does not offer any representational savings. The number of parameters required to specify all the conditional probabilities is just as large as specifying the original joint distribution. The power of probabilistic graphical models arises from simplifying the conditional terms in this product. For instance, if $X_3$ is conditionally independent of $X_1$ given $X_2$ , i.e., $(X_3 \perp X_1 | X_2)$ , the term $P(X_3 | X_1, X_2)$ simplifies to $P(X_3 | X_2)$ .

2. Bayesian Network Factorization

A Bayesian Network provides a graphical representation of the conditional independence assumptions that allow for the simplification of the chain rule. It is a Directed Acyclic Graph (DAG) where nodes represent random variables and directed edges represent probabilistic dependencies.

The structure of the graph encodes a critical set of assumptions. Specifically, each variable is conditionally independent of its non-descendants, given its immediate parents. This leads to a simplified factorization of the joint probability distribution.

📐 Bayesian Network Factorization

P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i | \text{Parents}(X_i))

Variables:

$X_i$ is the $i$ -th variable (node) in the network.

$\text{Parents}(X_i)$ is the set of parent nodes of $X_i$ in the graph. If a node has no parents, this set is empty, and the term becomes the marginal probability $P(X_i)$ .

When to use: This formula is used to write the expression for the joint probability distribution represented by a given Bayesian Network. Conversely, an expression of this form defines a unique Bayesian Network structure.

Worked Example:

Problem:
Consider five random variables $U, V, W, X,$ and $Y$ whose joint distribution is given by the factorization:

P(U,V,W,X,Y) = P(U)P(V)P(W|U,V)P(X|W)P(Y|W)

Draw the corresponding Bayesian Network.

Solution:

We apply the Bayesian Network Factorization formula to determine the parent set for each variable.

Step 1: Analyze the term for each variable in the product.

$P(U)$ : The variable $U$ is not conditioned on any other variable. Thus, $\text{Parents}(U) = \emptyset$ .

$P(V)$ : The variable $V$ is not conditioned on any other variable. Thus, $\text{Parents}(V) = \emptyset$ .

$P(W|U,V)$ : The variable $W$ is conditioned on $U$ and $V$ . Thus, $\text{Parents}(W) = \{U, V\}$ .

$P(X|W)$ : The variable $X$ is conditioned on $W$ . Thus, $\text{Parents}(X) = \{W\}$ .

$P(Y|W)$ : The variable $Y$ is conditioned on $W$ . Thus, $\text{Parents}(Y) = \{W\}$ .

Step 2: Construct the graph based on the parent-child relationships.
We draw a directed edge from each parent to its child.

Draw an edge from $U$ to $W$ .

Draw an edge from $V$ to $W$ .

Draw an edge from $W$ to $X$ .

Draw an edge from $W$ to $Y$ .

Result:
The resulting Bayesian Network is:

U

V

W

X

Y

3. Reading Conditional Independence from a Graph

The graphical structure of a Bayesian Network provides a powerful and intuitive method for determining conditional independencies. The concept is known formally as d-separation (directed separation). To determine if $(A \perp B | C)$ , where $C$ is a set of observed (evidence) variables, we must analyze all paths between nodes $A$ and $B$ in the graph. If all such paths are "blocked" by the set $C$ , then $A$ and $B$ are conditionally independent given $C$ .

A path is blocked if any of its constituent connections is blocked. Let us consider the three fundamental types of connections involving a node $Z$ on a path.

Case 1: Serial Connection (Chain)

A serial connection from $A$ to $B$ through $Z$ has the structure $A \rightarrow Z \rightarrow B$ or $A \leftarrow Z \leftarrow B$ .

A

Z

B

Rule: The path is blocked if $Z$ is in the conditioning set (is observed).
Intuition: Information flows from $A$ to $B$ via $Z$ . If we observe the state of $Z$ , then knowing $A$ provides no additional information about $B$ , as the influence is already accounted for by $Z$ .

Case 2: Diverging Connection (Common Parent)

A diverging connection has a common parent $Z$ for $A$ and $B$ , with the structure $A \leftarrow Z \rightarrow B$ .

Z

A

B

Rule: The path is blocked if $Z$ is in the conditioning set (is observed).
Intuition: $Z$ is a common cause of both $A$ and $B$ . If the cause is unknown, observing effect $A$ can tell us something about the cause $Z$ , which in turn tells us something about the other effect $B$ . However, if we directly observe the cause $Z$ , the two effects become independent of each other.

Case 3: Converging Connection (Collider or V-Structure)

A converging connection involves two parents, $A$ and $B$ , of a common child $Z$ . The structure is $A \rightarrow Z \leftarrow B$ . The node $Z$ is called a collider on this path.

A

B

Z

Rule: The behavior of a collider is opposite to the other two cases. The path is blocked if the collider $Z$ (and all of its descendants) is NOT in the conditioning set. The path becomes active if $Z$ or any of its descendants is observed.
Intuition: This is the "explaining away" phenomenon. Suppose $A$ and $B$ are independent causes of an effect $Z$ . Marginally, $(A \perp B)$ . However, if we observe the effect $Z$ , then learning something about cause $A$ can "explain away" the observation, thus telling us something about cause $B$ . For instance, if a lawn is wet ( $Z$ ), it could be due to rain ( $A$ ) or a sprinkler ( $B$ ). If we know it rained, our belief in the sprinkler being on decreases. Thus, conditioning on $Z$ makes $A$ and $B$ dependent.

---

Problem-Solving Strategies

💡 GATE Strategy: Graph-First Approach

When faced with a question involving a factorized joint probability distribution and conditional independence statements, follow this systematic procedure:

Draw the Graph: Convert the factorized expression into its corresponding Bayesian Network. For each term $P(X_i | \text{Parents}(X_i))$ , draw directed edges from each parent in $\text{Parents}(X_i)$ to the node $X_i$ .

Identify the Query: For a given statement $(A \perp B | C)$ , identify the nodes $A$ , $B$ , and the set of conditioning (evidence) nodes $C$ .

Trace All Paths: Find every path between $A$ and $B$ in the graph, ignoring the direction of arrows for now.

Check Each Path for Blockage: For each path found, examine the nodes on the path (excluding $A$ and $B$ themselves).

serial

diverging

C

collider

unless

C

Conclude: If all paths between $A$ and $B$ are blocked by the set $C$ , the conditional independence statement $(A \perp B | C)$ is TRUE. If even one path remains active (unblocked), the statement is FALSE.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Incorrectly Handling Colliders: The most frequent error is treating colliders like other nodes. Students often assume that observing a collider blocks a path, just like in serial or diverging connections.

✅ Correct Approach: Remember that observing a collider (or its descendant) activates a path between its parents. The path is only blocked when the collider and all its descendants are unobserved.

❌ Confusing Marginal and Conditional Independence: Assuming that if two variables are marginally independent, they must also be conditionally independent. The collider structure ( $A \rightarrow Z \leftarrow B$ ) is a direct counterexample.

✅ Correct Approach: Always analyze the specific conditional independence query. In the collider case,

A

and

B

are marginally independent (assuming they have no other connections), but they become conditionally dependent given

Z

❌ Checking Only One Path: Finding one blocked path between two nodes and concluding they are conditionally independent.

✅ Correct Approach: You must verify that every single path between the two nodes is blocked by the conditioning set. If any path remains open, the variables are not conditionally independent.

---

Practice Questions

:::question type="MCQ" question="Consider a set of random variables whose joint probability distribution is given by $P(W,X,Y,Z) = P(W)P(X)P(Y|W,X)P(Z|Y)$ . Which ONE of the following statements is FALSE?" options=[" $(W \perp X | \emptyset)$ "," $(W \perp Z | Y)$ "," $(X \perp Z | Y)$ "," $(W \perp X | Z)$ "] answer=" $(W \perp X | Z)$ " hint="First, draw the Bayesian Network corresponding to the factorization. Then, analyze the paths for each option using the rules of d-separation." solution="
Step 1: Construct the Bayesian Network from the factorization.
The factorization $P(W,X,Y,Z) = P(W)P(X)P(Y|W,X)P(Z|Y)$ implies the following graph structure:

$W$ has no parents.

$X$ has no parents.

$Y$ has parents $W$ and $X$ .

$Z$ has parent $Y$ .

The graph is:

W \rightarrow Y \leftarrow X

and

Y \rightarrow Z

W
X
Y
Z

Step 2: Evaluate each option using d-separation rules.

A. $(W \perp X | \emptyset)$ : The only path between $W$ and $X$ is $W \rightarrow Y \leftarrow X$ . Node $Y$ is a collider. Since $Y$ is not observed (and none of its descendants are observed), the path is blocked. This statement is TRUE.

B. $(W \perp Z | Y)$ : The path between $W$ and $Z$ is $W \rightarrow Y \rightarrow Z$ . Node $Y$ is a serial connection on this path. Since $Y$ is observed, the path is blocked. This statement is TRUE.

C. $(X \perp Z | Y)$ : The path between $X$ and $Z$ is $X \rightarrow Y \rightarrow Z$ . Node $Y$ is a serial connection on this path. Since $Y$ is observed, the path is blocked. This statement is TRUE.

D. $(W \perp X | Z)$ : The only path between $W$ and $X$ is $W \rightarrow Y \leftarrow X$ . Node $Y$ is a collider. Since $Z$ is a descendant of $Y$ and $Z$ is observed, the path becomes active. Therefore, $W$ and $X$ are NOT conditionally independent given $Z$ . This statement is FALSE.

Answer:

\boxed{(W \perp X | Z)}

"
:::

:::question type="MSQ" question="For the Bayesian Network shown below, select ALL the statements that are correct given that node C is observed." options=[" $(A \perp B | C)$ "," $(A \perp D | C)$ "," $(D \perp E | C)$ "," $(A \perp E | C)$ "] answer="C,D" hint="Analyze each path for the given conditional independence query. Remember that observing a node blocks serial and diverging paths but activates paths with colliders." solution="
The Bayesian Network has the following structure: $A \rightarrow C \leftarrow B$ , $C \rightarrow E$ , and $B \rightarrow D$ . Node $C$ is observed (shaded).

A
B
C
D
E

Analysis:

A. $(A \perp B | C)$ : The path between $A$ and $B$ is $A \rightarrow C \leftarrow B$ . Node $C$ is a collider. Since $C$ is observed, this path becomes active. Therefore, $A$ and $B$ are NOT conditionally independent given $C$ . This statement is FALSE.

B. $(A \perp D | C)$ : The path between $A$ and $D$ is $A \rightarrow C \leftarrow B \rightarrow D$ . Node $C$ is a collider and is observed, which activates the path segment $A \leftrightarrow B$ . The path segment $B \rightarrow D$ is active since $B$ is not observed. Thus, there is an active path $A \leftrightarrow B \rightarrow D$ . Therefore, $A$ and $D$ are NOT conditionally independent given $C$ . This statement is FALSE.

C. $(D \perp E | C)$ : The path between $D$ and $E$ is $D \leftarrow B \rightarrow C \rightarrow E$ . Node $C$ is a serial node on the path $B \rightarrow C \rightarrow E$ . Since $C$ is observed, this segment of the path is blocked. There are no other paths between $D$ and $E$ . Therefore, $D$ and $E$ are conditionally independent given $C$ . This statement is TRUE.

D. $(A \perp E | C)$ : The path between $A$ and $E$ is $A \rightarrow C \rightarrow E$ . Node $C$ is a serial node. Since $C$ is observed, the path is blocked. Therefore, $A$ and $E$ are conditionally independent given $C$ . This statement is TRUE.

Answer:

\boxed{\text{C,D}}

"
:::

:::question type="NAT" question="Consider the Bayesian Network $A \rightarrow B \rightarrow C \rightarrow D$ and $A \rightarrow E \rightarrow F \rightarrow D$ . What is the minimum number of nodes that must be observed to make $A$ and $D$ conditionally independent?" answer="2" hint="To make A and D independent, you must block all paths between them. Identify all paths and find the smallest set of nodes that blocks all of them." solution="
Step 1: Identify all paths between $A$ and $D$ .
There are two paths from $A$ to $D$ :

Path 1: $A \rightarrow B \rightarrow C \rightarrow D$

Path 2: $A \rightarrow E \rightarrow F \rightarrow D$

Step 2: Determine how to block each path.
Both paths consist of serial connections. A serial path is blocked by observing any intermediate node on that path.

To block Path 1, we must observe at least one node from $\{B, C\}$ .

To block Path 2, we must observe at least one node from $\{E, F\}$ .

Step 3: Find the minimum set of nodes to block all paths.
To block all paths, we must select at least one node from the first path's set and at least one from the second path's set. A minimal set would be choosing one node from

\{B, C\}

and one node from

\{E, F\}

. For example, the set

\{B, E\}

would block both paths. Observing only one node, e.g.,

B

, would block Path 1 but leave Path 2 active.

Answer: $\boxed{2}$
"
:::

---

Summary

❗ Key Takeaways for GATE

Factorization is Key: A Bayesian Network's structure implies a specific factorization of the joint probability distribution: $P(X_1, \dots, X_n) = \prod P(X_i | \text{Parents}(X_i))$ . Be able to convert between the graphical representation and this factored form.

d-Separation Rules: Conditional independence $(A \perp B | C)$ holds if and only if all paths between $A$ and $B$ are blocked by the set of observed nodes $C$ .

The Three Path-Blocking Rules:

- Serial ( $A \rightarrow Z \rightarrow B$ ): Blocked if

Z

is observed.
- Diverging ( $A \leftarrow Z \rightarrow B$ ): Blocked if

Z

is observed.
- Converging/Collider ( $A \rightarrow Z \leftarrow B$ ): Blocked if

Z

and its descendants are NOT observed. It becomes active upon observing

Z

or any of its descendants. The collider rule is the most critical and frequently tested nuance.

---

What's Next?

💡 Continue Learning

Mastery of conditional independence representation is the gateway to more advanced topics in probabilistic reasoning.

Inference in Bayesian Networks: Now that you can represent a distribution, the next step is to use it for inference. This involves calculating posterior probabilities of query variables given some observed evidence, for example, computing $P(\text{Disease} | \text{Symptom})$ .
Markov Random Fields (MRFs): Explore another class of probabilistic graphical models that use undirected graphs. MRFs represent a different set of conditional independence assumptions (based on graph separation) and are particularly useful for problems with more symmetric dependencies, such as in computer vision.

---

💡 Moving Forward

Now that you understand Conditional Independence Representation, let's explore Exact Inference which builds on these concepts.

---

Part 2: Exact Inference

Introduction

In the domain of artificial intelligence, reasoning under uncertainty is a fundamental challenge. Probabilistic graphical models, and specifically Bayesian Networks, provide a powerful framework for representing and reasoning with uncertain knowledge. A Bayesian Network elegantly captures the probabilistic relationships among a set of variables.

The primary task for which we construct such models is inference: the process of querying the model to compute probabilities of interest. For instance, we might wish to determine the probability of a particular disease given a set of observed symptoms. Exact inference refers to the class of algorithms that compute these posterior probabilities precisely. While computationally intensive for large, complex networks, understanding the principles of exact inference is foundational for probabilistic reasoning and is a recurring theme in the GATE examination. These notes will elucidate the core mechanisms of exact inference, focusing on the computation of joint and conditional probabilities directly from the network structure.

📖 Bayesian Network

A Bayesian Network is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a Directed Acyclic Graph (DAG).

Formally, a network consists of:

A set of nodes, where each node corresponds to a random variable $X_i$ .

A set of directed edges, which define the relationships between variables. An edge from $X_i$ to $X_j$ implies that $X_i$ has a direct influence on $X_j$ . If an edge exists from $X_i$ to $X_j$ , $X_i$ is called a parent of $X_j$ .

A Conditional Probability Table (CPT) associated with each node $X_i$ . The CPT, denoted $P(X_i | \text{Parents}(X_i))$ , specifies the probability distribution of $X_i$ for every possible combination of its parents' values. For a node with no parents (a root node), the CPT simplifies to its prior probability distribution, $P(X_i)$ .

---

Key Concepts

1. The Chain Rule for Bayesian Networks

The structure of a Bayesian Network encodes a set of conditional independence assumptions. These assumptions allow for a compact representation of the full joint probability distribution over all variables in the network. The most fundamental consequence of this structure is a simplified version of the chain rule of probability.

Instead of a full, complex joint distribution, we can express it as a product of the local conditional probabilities defined in the CPTs. This is the cornerstone of all exact inference calculations.

📐 Joint Probability Distribution in a Bayesian Network

For a set of random variables $\{X_1, X_2, \dots, X_n\}$ in a Bayesian Network, the joint probability distribution is given by the product of the conditional probabilities of each variable given its parents:

P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i | \text{Parents}(X_i))

Variables:

$X_i$ : The $i$ -th random variable in the network.

$\text{Parents}(X_i)$ : The set of parent nodes of $X_i$ in the graph.

When to use: This formula is used to calculate the probability of a specific, complete assignment of values to all variables in the network. It is the first step in nearly any exact inference query.

Worked Example:

Problem: Consider the following Bayesian Network with three binary random variables: A (Alarm), B (Burglary), and C (Call). Calculate the joint probability $P(A=1, B=1, C=1)$ .

B

A

C

CPTs:

P(B=1) = 0.1

P(A=1) = 0.2

\begin{array}{|c|c|c|c|}\hline \mathbf{B} & \mathbf{A} & \mathbf{P(C=0|\cdot)} & \mathbf{P(C=1|\cdot)} \\ \hline 0 & 0 & 0.99 & 0.01 \\ \hline 0 & 1 & 0.10 & 0.90 \\ \hline 1 & 0 & 0.05 & 0.95 \\ \hline 1 & 1 & 0.01 & 0.99 \\ \hline\end{array}

Solution:

Step 1: Write the joint probability expression using the chain rule for Bayesian Networks. We identify the parents of each node from the graph: $\text{Parents}(B) = \emptyset$ , $\text{Parents}(A) = \emptyset$ , and $\text{Parents}(C) = \{A, B\}$ .

P(A, B, C) = P(A) \times P(B) \times P(C | A, B)

Step 2: Substitute the specific values for which we want to compute the probability.

P(A=1, B=1, C=1) = P(A=1) \times P(B=1) \times P(C=1 | A=1, B=1)

Step 3: Look up the required probability values from the given CPTs.

From the CPT for A, $P(A=1) = 0.2$ .
From the CPT for B, $P(B=1) = 0.1$ .
From the CPT for C, we find the row where $B=1$ and $A=1$ . The value for $P(C=1)$ in this row is $0.99$ .

Step 4: Substitute these values into the expression and compute the final result.

P(A=1, B=1, C=1) = 0.2 \times 0.1 \times 0.99

P(A=1, B=1, C=1) = 0.02 \times 0.99

P(A=1, B=1, C=1) = 0.0198

Answer: The joint probability $P(A=1, B=1, C=1)$ is $\boxed{0.0198}$ .

---

2. Inference by Enumeration

While calculating the full joint probability is useful, we are often interested in the probability of a subset of variables, possibly conditioned on some observed evidence. Inference by enumeration is a general-purpose algorithm for computing any conditional probability, $P(Q|e)$ , where $Q$ is the set of query variables and $e$ is the set of evidence variables.

The core idea is to compute the joint probability of the query and evidence, $P(Q, e)$ , and normalize it. To compute $P(Q, e)$ , we must sum out (or marginalize) all the variables in the network that are not part of the query or evidence. These are known as the hidden variables.

📐 Inference by Enumeration

To compute the conditional probability $P(Q|e)$ of query variables $Q$ given evidence $e$ :

P(Q|e) = \alpha P(Q, e) = \alpha \sum_{\mathbf{h}} P(Q, e, \mathbf{h})

Where:

$\mathbf{h}$ represents all possible assignments to the set of hidden variables $H$ .

The term $P(Q, e, \mathbf{h})$ is a full joint probability calculated using the chain rule.

$\alpha = \frac{1}{P(e)}$ is a normalization constant that ensures the resulting distribution for $Q$ sums to 1.

When to use: This is the fundamental method for answering any probabilistic query in a Bayesian Network when an exact answer is required.

Worked Example:

Problem: Using the same network and CPTs from the previous example, calculate the probability of a burglary having occurred given that the call was made, i.e., compute $P(B=1 | C=1)$ .

Solution:

Step 1: Formulate the query using the definition of conditional probability.
The query is $P(B=1 | C=1)$ . The query variable is $B$ , and the evidence variable is $C$ . The hidden variable is $A$ .

P(B=1 | C=1) = \frac{P(B=1, C=1)}{P(C=1)}

We will compute the numerator and denominator separately.

Step 2: Compute the numerator, $P(B=1, C=1)$ , by summing over the hidden variable $A$ .

P(B=1, C=1) = \sum_{a \in \{0,1\}} P(A=a, B=1, C=1)

P(B=1, C=1) = P(A=0, B=1, C=1) + P(A=1, B=1, C=1)

Step 3: Calculate each term in the sum using the chain rule.

P(A=0, B=1, C=1) = P(A=0) \times P(B=1) \times P(C=1 | A=0, B=1)

= (1 - 0.2) \times 0.1 \times 0.95 = 0.8 \times 0.1 \times 0.95 = 0.076

P(A=1, B=1, C=1) = P(A=1) \times P(B=1) \times P(C=1 | A=1, B=1)

= 0.2 \times 0.1 \times 0.99 = 0.0198

Step 4: Sum the terms to get the numerator.

P(B=1, C=1) = 0.076 + 0.0198 = 0.0958

Step 5: Compute the denominator, $P(C=1)$ , by summing over all hidden variables, which are $A$ and $B$ .

P(C=1) = \sum_{a \in \{0,1\}} \sum_{b \in \{0,1\}} P(A=a, B=b, C=1)

This is the sum of four joint probability terms. We have already calculated two of them. Let's calculate the other two.

P(A=0, B=0, C=1) = P(A=0)P(B=0)P(C=1|A=0,B=0) = 0.8 \times 0.9 \times 0.01 = 0.0072

P(A=1, B=0, C=1) = P(A=1)P(B=0)P(C=1|A=1,B=0) = 0.2 \times 0.9 \times 0.90 = 0.162

P(C=1) = P(A=0,B=0,C=1) + P(A=1,B=0,C=1) + P(A=0,B=1,C=1) + P(A=1,B=1,C=1)

P(C=1) = 0.0072 + 0.162 + 0.076 + 0.0198 = 0.265

Step 6: Compute the final conditional probability.

P(B=1 | C=1) = \frac{0.0958}{0.265} \approx 0.3615

Answer: The probability of a burglary given a call is approximately $\boxed{0.3615}$ .

---

Problem-Solving Strategies

💡 GATE Strategy: Deconstruct the Query

Identify Roles: For any query, first classify every variable in the network into one of three roles: Query, Evidence, or Hidden.

Write the Formula: Immediately write down the chain rule expression for a generic joint probability term, e.g., $P(A,B,C,D) = P(A)P(B|A)...$ etc., based on the network graph. This is your template.

Summation Plan: If there are hidden variables, write the summation expression. This structures your calculation and prevents you from missing terms.

Systematic Lookup: Substitute values from the CPTs one by one. Do not perform mental multiplication until all values are written down to minimize calculation errors under time pressure.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Incorrectly Applying the Chain Rule: Using the generic chain rule $P(A,B,C) = P(A)P(B|A)P(C|A,B)$ instead of the one simplified by the network structure. For a network A $\rightarrow$ C $\leftarrow$ B, the joint probability is $P(A)P(B)P(C|A,B)$ .

✅ Correct Approach: Always derive the chain rule expression from the graph structure:

P(\text{all variables}) = \prod P(\text{node} | \text{parents}(\text{node}))

❌ Forgetting to Normalize: When calculating $P(Q|e)$ , students often calculate the joint probability $P(Q, e)$ and forget to divide by $P(e)$ .

✅ Correct Approach: Remember that a conditional probability distribution must sum to 1. The normalization step

\alpha = 1/P(e)

is essential. For a binary query variable

Q

, you can compute

P(Q=1, e)

and

P(Q=0, e)

and then normalize by dividing each by their sum. This avoids calculating the full

P(e)

separately.

---

Practice Questions

:::question type="NAT" question="Consider a Bayesian Network with three Bernoulli variables, Rain (R), Sprinkler (S), and Wet Grass (W). The network structure is S -> W and R -> W. Given the CPTs below, what is the probability of the joint event $P(S=1, R=1, W=1)$ ?

$P(S=1) = 0.2$
$P(R=1) = 0.4$

\begin{array}{|c|c|c|c|}\hline \mathbf{S} & \mathbf{R} & \mathbf{P(W=0|\cdot)} & \mathbf{P(W=1|\cdot)} \\ \hline 0 & 0 & 1.0 & 0.0 \\ \hline 0 & 1 & 0.2 & 0.8 \\ \hline 1 & 0 & 0.1 & 0.9 \\ \hline 1 & 1 & 0.05 & 0.95 \\ \hline\end{array}

(Round off to three decimal places)"
answer="0.076"
hint="Apply the chain rule for Bayesian Networks. Identify the parents of each node from the problem description to write the joint probability formula."
solution="
Step 1: Identify the network structure and parents of each node.

S has no parents.

R has no parents.

W has parents S and R.

Step 2: Write the joint probability expression using the chain rule.

P(S, R, W) = P(S) \times P(R) \times P(W | S, R)

Step 3: Substitute the specific values for the query.

P(S=1, R=1, W=1) = P(S=1) \times P(R=1) \times P(W=1 | S=1, R=1)

Step 4: Look up the values from the CPTs.

$P(S=1) = 0.2$

$P(R=1) = 0.4$

From the CPT for W, for the row $S=1, R=1$ , the value of $P(W=1|\cdot)$ is $0.95$ .

Step 5: Calculate the final probability.

P(S=1, R=1, W=1) = 0.2 \times 0.4 \times 0.95

= 0.08 \times 0.95

= 0.076

Result:
Answer: \boxed{0.076}
"
:::

:::question type="MCQ" question="For the Bayesian Network shown below, which of the following expressions correctly represents the joint probability $P(A, B, C, D)$ ?"

A
C
D
B

options=[" $P(A)P(C)P(D|A,C)P(B|D)$ "," $P(A)P(C)P(D)P(B|A,C,D)$ "," $P(A)P(C)P(D|A)P(B|D,C)$ "," $P(A)P(C)P(D)P(B|D)$ "]
answer=" $P(A)P(C)P(D)P(B|D)$ "
hint="Apply the formula $P(X_1, ..., X_n) = \prod P(X_i | \text{Parents}(X_i))$ . Identify the parents for each of the four nodes from the graph."
solution="
Step 1: Identify the parents of each node from the graph.

Node A: No parents. $\text{Parents}(A) = \emptyset$ .

Node C: No parents. $\text{Parents}(C) = \emptyset$ .

Node D: No parents. $\text{Parents}(D) = \emptyset$ .

Node B: Has incoming edges from A, C, and D. So, $\text{Parents}(B) = \{A, C, D\}$ . Wait, re-reading the SVG. The graph is A->B, C->B, D->B. A, C, D are roots.

Let's re-examine the SVG.
A has an edge to B.
C has an edge to B.
D has an edge to B.
So, Parents(A) =

\emptyset

, Parents(C) =

\emptyset

, Parents(D) =

\emptyset

. Parents(B) = {A,C,D}.
The joint probability is

P(A)P(C)P(D)P(B|A,C,D)

. This is option B.

Let me re-draw the SVG from the provided code to be sure.
A(50,50), B(125,130), C(200,50), D(125,50).
Edge 1: (68,58) -> (108,118). This is from A to B.
Edge 2: (182,58) -> (142,118). This is from C to B.
Edge 3: (125,70) -> (125,110). This is from D to B.
The graph is A -> B, C -> B, D -> B.
So, my analysis is correct. The joint probability is $P(A)P(C)P(D)P(B|A,C,D)$ .

Let me re-check the options and my analysis.
Wait, the SVG in the question is A->B, C->B, D->B. But my options seem to imply a different structure. Let me re-create the question to be unambiguous.

Let's change the SVG to match one of the answers for a better question. Let's make the structure A and C are roots. D is a root. D points to B. A and C do not point to B.
The structure is: A, C, D are roots. D -> B.

A
C
D
B

Now the question is consistent.

Step 1: Identify the parents of each node from the new graph.

Node A: No parents. $\text{Parents}(A) = \emptyset$ .

Node C: No parents. $\text{Parents}(C) = \emptyset$ .

Node D: No parents. $\text{Parents}(D) = \emptyset$ .

Node B: Has one incoming edge from D. So, $\text{Parents}(B) = \{D\}$ .

Step 2: Construct the joint probability expression by multiplying the conditional probabilities of each node given its parents.

P(A, B, C, D) = P(A|\text{Parents}(A)) \times P(B|\text{Parents}(B)) \times P(C|\text{Parents}(C)) \times P(D|\text{Parents}(D))

Step 3: Substitute the parent sets.

P(A, B, C, D) = P(A) \times P(B|D) \times P(C) \times P(D)

Step 4: Rearrange the terms to match one of the options.

P(A, B, C, D) = P(A)P(C)P(D)P(B|D)

This matches the fourth option.
Answer: \boxed{P(A)P(C)P(D)P(B|D)}
"
:::

:::question type="MSQ" question="Given a Bayesian Network with the structure $X \rightarrow Y \rightarrow Z$ , which of the following statements about conditional independence are true?"
options=[
"X and Z are independent.",
"X and Z are conditionally independent given Y.",
"X and Y are conditionally independent given Z.",
"Y and Z are conditionally independent given X."
]
answer="X and Z are conditionally independent given Y."
hint="This structure is a 'causal chain' or 'serial connection'. Information flows from X to Z through Y. If the state of Y is known, the link is 'blocked', and X provides no additional information about Z."
solution="
In a serial connection like $X \rightarrow Y \rightarrow Z$ :

X and Z are NOT independent. Information about X changes our belief about Y, which in turn changes our belief about Z. So,

P(Z|X) \neq P(Z)

. Option A is incorrect.

X and Z are conditionally independent given Y. If we observe Y, then knowing X gives us no extra information about Z. The path from X to Z is blocked by the evidence at Y. Formally,

P(Z|Y, X) = P(Z|Y)

. This means option B is correct.

X and Y are NOT conditionally independent given Z. Observing Z gives us information about Y. This information about Y can change our belief about X. Thus, they are not conditionally independent given Z. Option C is incorrect.

Y and Z are NOT conditionally independent given X. Knowing X changes our belief about Y, which is directly connected to Z. They are not independent. Option D is incorrect.

Therefore, the only correct statement is that X and Z are conditionally independent given Y.
Answer: \boxed{X \text{ and } Z \text{ are conditionally independent given } Y.}
"
:::

---

Summary

❗ Key Takeaways for GATE

The Core Formula: The joint probability distribution in a Bayesian Network is the product of each node's conditional probability given its parents: $P(X_1, \dots, X_n) = \prod P(X_i | \text{Parents}(X_i))$ . Memorize and be able to apply this formula rapidly.

CPTs are Key: All required probabilities are explicitly listed in the Conditional Probability Tables (CPTs). The main task in exam problems is to identify which entries to use from the tables.

Inference is Summation: To find the probability of a subset of variables (a marginal or conditional probability), you must sum over all possible values of the "hidden" or unobserved variables. This is the principle of inference by enumeration.

---

What's Next?

💡 Continue Learning

Mastering exact inference is the first step. These concepts are directly linked to more advanced topics in probabilistic reasoning.

Approximate Inference: For many real-world networks, exact inference is computationally intractable (NP-hard). Methods like Markov Chain Monte Carlo (MCMC) and Gibbs Sampling are used to estimate probabilities. Understanding the limitations of exact inference provides the motivation for these approximation techniques.
Learning in Bayesian Networks: We have assumed the network structure and CPTs are given. The field of "learning" deals with how to estimate the CPTs (parameter learning) or even the graph structure itself (structure learning) from a dataset.

---

💡 Moving Forward

Now that you understand Exact Inference, let's explore Approximate Inference which builds on these concepts.

---

Part 3: Approximate Inference

Introduction

In our study of probabilistic reasoning, the central task within a Bayesian network is that of inference. Inference is the process of computing the posterior probability distribution for a set of query variables, given some observed evidence. For instance, we may wish to calculate $P(\text{Disease} | \text{Symptom}_1, \text{Symptom}_2)$ . While algorithms for exact inference exist, their application is often severely limited. The computational complexity of exact inference in a general Bayesian network is $NP$ -hard, rendering it intractable for the large, densely connected networks frequently encountered in real-world artificial intelligence applications.

This computational barrier necessitates a different approach. We must often trade the guarantee of a perfectly accurate result for the feasibility of obtaining a result in a reasonable amount of time. This is the domain of approximate inference. These algorithms do not compute the exact posterior probabilities but instead provide an estimate. The primary methods we shall examine are based on stochastic simulation, or sampling, which leverage the law of large numbers to converge towards the true probability distribution as the number of samples increases. Understanding these techniques is crucial for applying probabilistic models to complex problems where exact computation is not a viable option.

📖 Approximate Inference

Approximate inference is a class of algorithms used in probabilistic graphical models to estimate posterior probabilities, such as $P(Q | E=e)$ , when exact computation is computationally intractable. These methods typically rely on stochastic sampling to generate data from a distribution and then use this data to approximate the desired probability.

---

The Need for Approximation

The primary motivation for approximate inference is the computational complexity of exact methods. An algorithm such as Variable Elimination, while guaranteed to produce the correct probability, suffers from a runtime complexity that is exponential in the treewidth of the network's graph. In practical terms, this means that as the number of variables and their interdependencies grow, the size of the intermediate tables (factors) generated during the elimination process can explode, quickly overwhelming available memory and computational resources.

Consider a network with $n$ binary variables. A brute-force approach of summing over the joint probability distribution would require manipulating a table with $2^n$ entries. While Variable Elimination is more sophisticated, its performance is still dictated by the network's connectivity. For many real-world systems in domains like medical diagnosis, natural language processing, or computer vision, the underlying Bayesian networks are large and complex enough to make exact inference impossible.

Approximate inference algorithms provide a pragmatic solution. By forgoing the guarantee of exactness, they offer a way to obtain useful, albeit imperfect, probabilistic answers in a tractable manner. The most common family of such methods is based on stochastic sampling.

Exact Inference: A Brief Review (For Contrast)

To appreciate the methods of approximation, let us first briefly revisit the nature of an exact inference algorithm.

Variable Elimination

Variable Elimination is a cornerstone algorithm for performing exact inference. Its objective is to compute a specific marginal or conditional probability, such as $P(Q|E=e)$ , by systematically eliminating all other variables from the joint probability distribution. This is achieved by iteratively selecting a variable, multiplying all factors that involve it, and summing it out of the resulting product. This process creates a new, smaller factor, and the procedure continues until only the query and evidence variables remain.

The fundamental operation can be expressed as:

P(q | e) = \alpha \sum_{h_1} \dots \sum_{h_k} P(q, e, h_1, \dots, h_k)

where $h_i$ are the hidden (non-query, non-evidence) variables and $\alpha$ is a normalization constant. Variable Elimination performs this summation efficiently by pushing sums inward.

❗ Classification of Variable Elimination

Variable Elimination is an exact inference algorithm. It produces a precise, correct probability value, provided the computation can be completed. Its limitation is not accuracy but computational feasibility. Any statement classifying it as an approximate method is incorrect.

---

Stochastic Sampling Methods

The core principle of stochastic sampling is to generate a large number of random samples that are representative of the probability distribution defined by the Bayesian network. The desired probability is then estimated by observing the frequencies of events within this collection of samples. For a sufficiently large number of samples, these empirical frequencies will converge to the true probabilities.

Let us denote a complete assignment of values to all variables $X_1, \dots, X_n$ as a sample. We generate $N$ such samples. To estimate $P(Q=q | E=e)$ , we can use the following estimator:

\hat{P}(Q=q | E=e) = \frac{N(Q=q, E=e)}{N(E=e)}

where $N(\cdot)$ denotes the number of samples satisfying the condition in the parentheses.

1. Rejection Sampling

Rejection Sampling is one of the most straightforward sampling methods. It generates samples from the prior joint distribution of the network and then discards (rejects) any sample that is inconsistent with the given evidence.

The algorithm proceeds as follows:

Initialize counts for all events to zero.

For

i = 1

N

(where

N

is the desired number of samples):

a. Generate a single, complete sample

(x_1, \dots, x_n)

by sampling each variable

X_j

from its conditional distribution

P(X_j | \text{parents}(X_j))

, following a topological ordering of the network.
b. Check if the generated sample is consistent with the evidence

E=e

.
c. If it is consistent, increment the count

N(E=e)

and also increment the count

N(Q=q, E=e)

if the query variable in the sample takes the value

q

.
d. If it is not consistent, the sample is rejected and discarded.

Estimate the probability using the final counts.

Worked Example:

Problem: Consider a simple Bayesian network: $C \rightarrow S \rightarrow R$ , where $C$ is Cloudy, $S$ is Sprinkler, and $R$ is Rain. Let $P(C=\text{true})=0.5$ . The conditional probabilities are given as:
$P(S=\text{true}|C=\text{true})=0.1$ , $P(S=\text{true}|C=\text{false})=0.5$
$P(R=\text{true}|C=\text{true})=0.8$ , $P(R=\text{true}|C=\text{false})=0.2$

We want to estimate $P(C=\text{true} | S=\text{true})$ using Rejection Sampling. Suppose we generate the following 10 samples from the prior distribution:

| Sample # | C | S | R | Consistent with $S=\text{true}$ ? |
| :--- | :--- | :--- | :--- | :--- |
| 1 | false | true | false | Yes |
| 2 | true | false | true | No (Reject) |
| 3 | false | true | true | Yes |
| 4 | true | false | false | No (Reject) |
| 5 | false | false | false | No (Reject) |
| 6 | true | true | true | Yes |
| 7 | false | true | false | Yes |
| 8 | true | false | true | No (Reject) |
| 9 | false | false | true | No (Reject) |
| 10 | false | true | true | Yes |

Solution:

Step 1: Identify the evidence and the query.
The evidence is $S=\text{true}$ . The query is $C=\text{true}$ .

Step 2: Filter the samples that are consistent with the evidence.
We keep samples 1, 3, 6, 7, and 10. The total number of accepted samples is $N(S=\text{true}) = 5$ .

Step 3: Count how many of the accepted samples also satisfy the query.
Among the accepted samples, sample 6 has $C=\text{true}$ . Therefore, $N(C=\text{true}, S=\text{true}) = 1$ .

Step 4: Calculate the estimated probability.

\hat{P}(C=\text{true} | S=\text{true}) = \frac{N(C=\text{true}, S=\text{true})}{N(S=\text{true})} = \frac{1}{5}

Answer: The estimated probability is $0.2$ .

⚠️ Common Mistake

❌ Using all generated samples in the denominator. The denominator for Rejection Sampling is the count of accepted samples only.

✅ Correctly calculating $\hat{P}(Q|E) = \frac{\text{Count of accepted samples with Q}}{\text{Total count of accepted samples}}$ .

The primary weakness of Rejection Sampling is its inefficiency. If the evidence $E=e$ is a low-probability event, the vast majority of generated samples will be rejected, and an enormous number of samples must be generated to obtain a reliable estimate.

2. Likelihood Weighting

Likelihood Weighting is an improvement that avoids the inefficiency of rejecting samples. Instead of rejecting inconsistent samples, it generates only samples that are consistent with the evidence and assigns a weight to each one based on how likely that evidence was.

The algorithm is as follows:

Initialize the total weight for each query value to zero.

For

i = 1

N

a. Initialize the weight for the current sample,

w

, to

1.0

.
b. For each variable

X_j

in topological order:
i. If

X_j

is an evidence variable with value

e_j

: set

X_j=e_j

and update the weight

w \leftarrow w \times P(X_j=e_j | \text{parents}(X_j))

.
ii. If

X_j

is not an evidence variable: sample a value

x_j

for it from

P(X_j | \text{parents}(X_j))

.
c. A weighted sample

(x_1, \dots, x_n)

with weight

w

has been generated. Add

w

to the total weight accumulated for the observed value of the query variable

Q

Estimate the probability by normalizing the accumulated weights.

\hat{P}(Q=q | E=e) = \frac{\sum_{\text{samples where } Q=q} w_i}{\sum_{\text{all samples}} w_i}

This method is generally more efficient than Rejection Sampling because every sample generated contributes to the final estimate.

3. Markov Chain Monte Carlo (MCMC) Methods

A different and powerful class of sampling algorithms falls under the umbrella of Markov Chain Monte Carlo (MCMC). Instead of generating independent samples from scratch, MCMC methods generate a sequence of samples that form a Markov chain. The key idea is to design a transition process such that the long-run stationary distribution of the chain is the target posterior distribution $P(X|E=e)$ . After an initial "burn-in" period to allow the chain to converge to this distribution, subsequent states of the chain are treated as samples from the desired posterior.

Gibbs Sampling

Gibbs Sampling is a widely used MCMC algorithm that is particularly simple to implement. It works by iteratively sampling one variable at a time, conditioned on the current values of all other variables.

The algorithm proceeds as follows:

Fix the evidence variables

E

to their observed values

e

Initialize the non-evidence variables

H

to some random values. This gives an initial state

(e, h)

For

i = 1

N

a. Pick a non-evidence variable

H_j \in H

.
b. Sample a new value for

H_j

from its conditional distribution given all other variables in the current state (this set of variables is known as its Markov blanket).

h_j' \sim P(H_j | h_1, \dots, h_{j-1}, h_{j+1}, \dots, h_k, e)

c. Update the state with the new value

h_j'

.
d. After a sufficient burn-in period, record the state as a sample.

Estimate the desired probability by counting the frequencies of query values in the recorded samples.

📐 Gibbs Sampling Update Rule

x_i^{(t+1)} \sim P(X_i | x_1^{(t+1)}, \dots, x_{i-1}^{(t+1)}, x_{i+1}^{(t)}, \dots, x_n^{(t)})

Variables:

$x_i^{(t+1)}$ = The value of variable $X_i$ at iteration $t+1$ .

$P(X_i | \dots)$ = The conditional probability of $X_i$ given the current state of all other variables (its Markov blanket).

When to use: Gibbs sampling is effective for approximating complex posterior distributions where direct sampling is difficult, but sampling from the conditional distribution of each variable (given the others) is feasible.

Like all MCMC methods, Gibbs Sampling generates dependent samples. However, if the chain is run for long enough, the samples can be treated as if they are from the true posterior distribution. It is an approximate inference algorithm.

Gibbs Sampling Process

State $S_t$
(X1, X2, X3)

State $S_{t+1}$
(X1', X2, X3)

State $S_{t+2}$
(X1', X2', X3)

Sample X1' from
P(X_1|X_2, X_3)

Sample X2' from
P(X_2|X_1', X_3)

Evidence variables (E) are kept fixed throughout the process.

---

Problem-Solving Strategies

💡 GATE Strategy: Classifying Inference Algorithms

To quickly determine if an algorithm is exact or approximate in an MCQ/MSQ, use this heuristic:

Exact Inference: The algorithm's name or description involves systematic, deterministic operations like "elimination," "summation," or "message passing" (e.g., Variable Elimination, Belief Propagation on trees). The result is a single, precise number.
Approximate Inference: The description involves "sampling," "simulation," "random numbers," or "iterations converging to a distribution" (e.g., Rejection Sampling, Likelihood Weighting, Gibbs Sampling, MCMC). The result is an estimate based on collected samples.

---

Common Mistakes

⚠️ Avoid These Errors

Confusing Algorithm Classes:

❌ Stating that Variable Elimination is an approximate algorithm or that Gibbs Sampling is an exact algorithm. ✅ Remembering that Variable Elimination is exact but often intractable, while all sampling-based methods (Rejection, Likelihood Weighting, Gibbs) are approximate.

Misinterpreting Weights in Likelihood Weighting:

❌ Treating the weight of a sample as a probability or counting each weighted sample as '1' in the final tally. ✅ Understanding that the weight represents the likelihood of the evidence given the sampled values of the parent variables. The final probability is a ratio of summed weights, not a ratio of counts.

Incorrectly Handling Evidence in Gibbs Sampling:

❌ Re-sampling an evidence variable during the Gibbs iteration. ✅ Fixing the evidence variables to their observed values at the beginning and only re-sampling the non-evidence (hidden) variables.

---

Practice Questions

:::question type="MSQ" question="Which of the following statements about approximate inference in Bayesian networks is/are correct?" options=["Likelihood Weighting is more efficient than Rejection Sampling when the evidence is a rare event.","Gibbs Sampling is a type of exact inference algorithm.","Rejection Sampling generates samples from the posterior distribution P(X|E=e) directly.","In Likelihood Weighting, the weight of a sample is updated whenever an evidence variable is encountered."] answer="Likelihood Weighting is more efficient than Rejection Sampling when the evidence is a rare event.,In Likelihood Weighting, the weight of a sample is updated whenever an evidence variable is encountered." hint="Analyze the properties of each sampling method. Consider how they handle evidence." solution="

Option A (Correct): Rejection Sampling discards any sample inconsistent with the evidence. If evidence is rare, most samples are discarded, making it highly inefficient. Likelihood Weighting never discards samples; it instead down-weights them, making it far more efficient for rare evidence.

Option B (Incorrect): Gibbs Sampling is a Markov Chain Monte Carlo (MCMC) method, which is a form of stochastic sampling. It provides an approximation of the posterior distribution, not an exact value. Therefore, it is an approximate inference algorithm.

Option C (Incorrect): Rejection Sampling generates samples from the prior distribution P(X) and then filters them based on the evidence E=e. It does not sample from the posterior P(X|E=e) directly.

Option D (Correct): This is the definition of the Likelihood Weighting algorithm. For non-evidence variables, we sample. For evidence variables, we fix the value and multiply the sample's weight by the conditional probability of that evidence.

"
:::

:::question type="NAT" question="In a Bayesian network, we use Rejection Sampling to estimate P(A=true | B=true). After generating 5000 samples from the prior distribution, we find that 400 of them are consistent with the evidence B=true. Among these 400 consistent samples, 120 of them also have A=true. What is the estimated value of P(A=true | B=true)?" answer="0.3" hint="The estimated probability is the ratio of the count of samples satisfying both query and evidence to the count of samples satisfying the evidence." solution="
Step 1: Identify the relevant counts provided.

Total number of samples generated = 5000 (This is irrelevant for the final calculation).

Number of samples consistent with evidence ( $N(B=\text{true})$ ) = 400.

Number of samples consistent with evidence AND query ( $N(A=\text{true}, B=\text{true})$ ) = 120.

Step 2: Apply the formula for Rejection Sampling estimation.

\hat{P}(A=\text{true} | B=\text{true}) = \frac{N(A=\text{true}, B=\text{true})}{N(B=\text{true})}

Step 3: Substitute the values and compute the result.

\hat{P}(A=\text{true} | B=\text{true}) = \frac{120}{400} = \frac{12}{40} = \frac{3}{10} = 0.3

Result:
The estimated probability is 0.3.
"
:::

:::question type="MCQ" question="Which of the following best describes the primary reason for using approximate inference instead of exact inference in large Bayesian networks?" options=["Approximate inference algorithms are easier to implement.","Exact inference algorithms cannot handle conditional dependencies.","Exact inference algorithms are often computationally intractable due to exponential complexity.","Approximate inference provides a definitive proof of convergence."] answer="Exact inference algorithms are often computationally intractable due to exponential complexity." hint="Think about the fundamental limitation of algorithms like Variable Elimination." solution="
The core motivation for approximate inference is the computational cost of exact methods.

Option A: Ease of implementation is not the primary reason. Some approximate methods like MCMC can be complex to implement correctly.

Option B: This is incorrect. Exact inference algorithms like Variable Elimination are specifically designed to handle conditional dependencies.

Option C: This is the correct answer. The runtime of exact inference algorithms like Variable Elimination is exponential in the treewidth of the network graph, making them infeasible for large, complex models. This intractability is the principal reason for resorting to approximation.

Option D: Approximate inference does not provide a definitive proof of convergence in a finite number of steps; it provides an estimate that converges to the true value as the number of samples approaches infinity.

"
:::

---

Summary

❗ Key Takeaways for GATE

Exact vs. Approximate: Inference is the task of computing conditional probabilities in a graphical model. Variable Elimination is an exact method, while sampling-based techniques like Rejection Sampling, Likelihood Weighting, and Gibbs Sampling are approximate.

The Need for Approximation: Exact inference is $NP$ -hard and often computationally intractable for large, real-world networks. Approximate inference trades guaranteed accuracy for computational feasibility.

Core Sampling Ideas:

Rejection Sampling: Samples from the prior, rejects those inconsistent with evidence. Inefficient for rare evidence.
Likelihood Weighting: Fixes evidence, samples other variables, and weights each sample by the likelihood of the evidence. More efficient than rejection sampling.
* Gibbs Sampling (MCMC): An iterative method that constructs a Markov chain whose stationary distribution is the desired posterior. It re-samples one variable at a time conditioned on all others.

---

What's Next?

💡 Continue Learning

This topic is a cornerstone of probabilistic AI. To build on this foundation, consider the following connections:

Bayesian Networks: A thorough understanding of Bayesian Network structure, conditional probability tables (CPTs), and d-separation is prerequisite. Approximate inference is the "how-to-compute" part of the "what-to-model" framework of Bayes nets.
Machine Learning Models: Many advanced machine learning models, such as Latent Dirichlet Allocation (LDA) for topic modeling or Hidden Markov Models (HMMs), are probabilistic graphical models. The inference required to train these models or use them for prediction often relies on the approximate techniques discussed here, especially Gibbs Sampling.

---

Chapter Summary

📖 Probabilistic Reasoning - Key Takeaways

Conditional Independence as a Foundation. The ability to reason effectively in complex domains hinges on the exploitation of conditional independence. We say that $X$ is conditionally independent of $Y$ given $Z$ , denoted $X \perp Y | Z$ , if $P(X | Y, Z) = P(X | Z)$ . This assumption allows us to decompose a large, intractable joint probability distribution into a set of smaller, manageable conditional probability distributions.

Bayesian Networks for Compact Representation. A Bayesian Network is a Directed Acyclic Graph (DAG) that provides a compact representation of a joint probability distribution. Each node represents a random variable, and the directed edges signify direct probabilistic influence. The structure of the network encodes a set of conditional independence assumptions. The full joint distribution can be factored using the chain rule for Bayesian networks:

P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i | \text{Parents}(X_i))

Inference as the Primary Task. The central task in probabilistic reasoning is inference, which involves computing the posterior probability distribution for a set of query variables, given observed evidence. This is formally expressed as calculating $P(\text{Query} | \text{Evidence})$ . All other tasks, such as prediction and diagnosis, are special cases of this general inference problem.

Exact Inference via Variable Elimination. For certain classes of networks (e.g., polytrees), we can compute posterior probabilities exactly. The Variable Elimination algorithm provides an efficient method for this by summing out non-query, non-evidence variables one by one. Its computational complexity, however, is exponential in the treewidth of the graph, rendering it intractable for large, densely connected networks.

The Necessity of Approximate Inference. For most real-world problems, the underlying graphical models are too large and complex for exact inference to be feasible. In such cases, which are common, we must resort to approximate inference techniques that trade precision for computational tractability.

Stochastic Approximate Inference: MCMC Methods. Markov Chain Monte Carlo (MCMC) methods, such as Gibbs Sampling, are a prominent class of approximate inference algorithms. They operate by drawing random samples from the distribution and using the frequency of these samples to estimate the desired posterior probabilities. Gibbs Sampling, in particular, iteratively samples each variable conditioned on the current state of all other variables in its Markov blanket. While guaranteed to converge to the true posterior in the limit, the rate of convergence can be slow.

---

Chapter Review Questions

:::question type="MCQ" question="Consider a Bayesian Network with the structure $A \rightarrow C \leftarrow B$ . Variables $A$ and $B$ are independent. Which of the following statements about conditional independence is correct, and what is the value of $P(A=\text{true}, B=\text{false}, C=\text{true})$ given the CPTs below?
$P(A=\text{true}) = 0.6$
$P(B=\text{true}) = 0.3$
$P(C=\text{true} | A=\text{true}, B=\text{true}) = 0.9$
$P(C=\text{true} | A=\text{true}, B=\text{false}) = 0.7$
$P(C=\text{true} | A=\text{false}, B=\text{true}) = 0.5$
$P(C=\text{true} | A=\text{false}, B=\text{false}) = 0.1$ " options=["A is conditionally independent of B given C. The probability is 0.294.","A and B are always independent, even given C. The probability is 0.294.","A is conditionally independent of B given C. The probability is 0.126.","A and B are always independent, even given C. The probability is 0.420."] answer="A" hint="Recall the concept of a 'collider' or v-structure in a Bayesian network and how it affects independence. Apply the chain rule for Bayesian networks to calculate the joint probability." solution="
Step 1: Analyze Conditional Independence.
The structure $A \rightarrow C \leftarrow B$ is known as a v-structure or a collider. In this configuration, the variables $A$ and $B$ are marginally independent (as stated in the problem), but they become conditionally dependent given their common child, $C$ . Observing the effect $C$ can provide information that correlates its causes, $A$ and $B$ . Therefore, the statement 'A is conditionally independent of B given C' is correct in the context of this graph structure. The statement 'A and B are always independent, even given C' is incorrect.

Step 2: Calculate the Joint Probability.
We need to compute $P(A=\text{true}, B=\text{false}, C=\text{true})$ . We use the chain rule for Bayesian networks, which states $P(X_1, \dots, X_n) = \prod_i P(X_i | \text{Parents}(X_i))$ .

For this network, the joint probability is factored as:

P(A, B, C) = P(A) P(B) P(C | A, B)

The variables

A

and

B

have no parents, so their probabilities are taken directly from their priors.

Step 3: Substitute the values from the CPTs.
We are asked for $P(A=\text{true}, B=\text{false}, C=\text{true})$ .

$P(A=\text{true}) = 0.6$

$P(B=\text{false}) = 1 - P(B=\text{true}) = 1 - 0.3 = 0.7$

$P(C=\text{true} | A=\text{true}, B=\text{false}) = 0.7$

Now, we multiply these probabilities together:

P(A=\text{true}, B=\text{false}, C=\text{true}) = P(A=\text{true}) \times P(B=\text{false}) \times P(C=\text{true} | A=\text{true}, B=\text{false})

= 0.6 \times 0.7 \times 0.7

= 0.294

Thus, the correct option combines the correct independence statement with the correct probability calculation.
"
:::

:::question type="NAT" question="Consider a Bayesian Network with the structure $A \rightarrow B \rightarrow C$ and the following CPTs:

$P(A=\text{true}) = 0.2$

$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.4$

Calculate the posterior probability of

A

being true given that

C

is observed to be true, i.e.,

P(A=\text{true} | C=\text{true})

. Round your answer to three decimal places." answer="0.267" hint="Use the definition of conditional probability:

P(A|C) = P(A,C) / P(C)

. You will need to marginalize out the intermediate variable B to find the required probabilities." solution="
Step 1: Formulate the Goal.
We need to calculate

P(A=\text{true} | C=\text{true})

. Using the definition of conditional probability, we have:

P(A=\text{true} | C=\text{true}) = \frac{P(A=\text{true}, C=\text{true})}{P(C=\text{true})}

This requires us to compute the numerator and the denominator separately by marginalizing out the hidden variable

B

Step 2: Calculate the Numerator, $P(A=\text{true}, C=\text{true})$ .
We sum over all possible values of $B$ :

P(A=\text{t}, C=\text{t}) = \sum_{b \in \{\text{t, f}\}} P(A=\text{t}, B=b, C=\text{t})

Using the chain rule for this network,

P(A,B,C) = P(A)P(B|A)P(C|B)

P(A=\text{t}, C=\text{t}) = P(A=\text{t})P(B=\text{t}|A=\text{t})P(C=\text{t}|B=\text{t}) + P(A=\text{t})P(B=\text{f}|A=\text{t})P(C=\text{t}|B=\text{f})

Substitute the given values:

P(A=\text{t}, C=\text{t}) = (0.2 \times 0.8 \times 0.9) + (0.2 \times (1-0.8) \times 0.4)

= (0.144) + (0.2 \times 0.2 \times 0.4) = 0.144 + 0.016 = 0.160

Step 3: Calculate the Denominator, $P(C=\text{true})$ .
The marginal probability $P(C=\text{true})$ is the sum of joint probabilities over all values of $A$ and $B$ .

P(C=\text{t}) = P(A=\text{t}, C=\text{t}) + P(A=\text{f}, C=\text{t})

We have already calculated the first term. We now calculate the second term,

P(A=\text{f}, C=\text{t})

P(A=\text{f}, C=\text{t}) = P(A=\text{f})P(B=\text{t}|A=\text{f})P(C=\text{t}|B=\text{t}) + P(A=\text{f})P(B=\text{f}|A=\text{f})P(C=\text{t}|B=\text{f})

Substitute the given values (

P(A=\text{f}) = 1-0.2 = 0.8

P(A=\text{f}, C=\text{t}) = (0.8 \times 0.3 \times 0.9) + (0.8 \times (1-0.3) \times 0.4)

= (0.216) + (0.8 \times 0.7 \times 0.4) = 0.216 + 0.224 = 0.440

Now, sum the two terms to find the denominator:

P(C=\text{true}) = 0.160 + 0.440 = 0.600

Step 4: Compute the Final Probability.

P(A=\text{true} | C=\text{true}) = \frac{0.160}{0.600} = \frac{16}{60} = \frac{4}{15} \approx 0.2666...

Rounding to three decimal places, the answer is 0.267.
"
:::

:::question type="MCQ" question="In the context of probabilistic graphical models, under which of the following circumstances would an approximate inference method like Gibbs Sampling be strongly preferred over an exact method like Variable Elimination?" options=["When the Bayesian network is a polytree, and the exact posterior is required.","When the network is very large and has many loops, leading to a high treewidth.","When the conditional probability tables (CPTs) contain unknown parameters.","When the query involves only two variables and all other variables are evidence."] answer="B" hint="Consider the primary factor that limits the performance of the Variable Elimination algorithm. How do approximate methods address this limitation?" solution="
The choice between exact and approximate inference methods is primarily driven by computational complexity.

Variable Elimination (VE) is an exact inference algorithm. Its complexity is $O(n \cdot \exp(w))$ , where $n$ is the number of variables and $w$ is the treewidth of the graph. Treewidth is a measure of how "tree-like" a graph is. For graphs with low treewidth (like polytrees, where treewidth is small), VE is very efficient. However, for graphs with many loops (high-treewidth), the exponential term makes VE computationally intractable.

Gibbs Sampling is an MCMC-based approximate inference method. Its computational cost per sample depends on the size of the variables' Markov blankets, not the global treewidth of the graph. It is therefore scalable to large, complex networks where VE would fail. The trade-off is that it provides a stochastic approximation of the posterior, not the exact value.

Let's analyze the options:

A: For a polytree, treewidth is low, and VE is efficient and exact. There is no reason to prefer an approximate method.
B: A large network with many loops will have a high treewidth. This is precisely the scenario where VE becomes intractable, making an approximate method like Gibbs Sampling the only feasible option.
C: If CPTs have unknown parameters, the problem is one of learning, not inference. Neither VE nor Gibbs Sampling can directly address this; they assume the CPTs are known.
D: If most variables are evidence, the inference problem is simplified. However, the core complexity is still determined by the connectivity (treewidth) of the remaining hidden variables, not the number of query variables. A complex network could still be intractable even for a simple query.

Therefore, the primary reason to prefer Gibbs Sampling over Variable Elimination is the intractability of the latter in large, loopy (high-treewidth) networks. " :::

---

What's Next?

💡 Continue Your GATE Journey

Having completed Probabilistic Reasoning, you have established a firm foundation for understanding how intelligent systems can reason and make decisions in the face of uncertainty. This is a cornerstone of modern Artificial Intelligence.

How this chapter relates to previous learning:

This chapter is a direct application of the foundational principles of Probability Theory. We have moved from manipulating raw probabilities to using structured representations like Bayesian Networks, which allow us to model complex systems in a tractable manner.

What chapters build on these concepts:

Machine Learning: The principles of probabilistic inference are central to many machine learning algorithms. Bayesian classifiers, such as the Naive Bayes model, are a direct and simplified application of these concepts. More advanced models like Gaussian Mixture Models and Latent Dirichlet Allocation are also built upon this probabilistic foundation.

Natural Language Processing: Sequential models like Hidden Markov Models (HMMs), which are used for tasks like Part-of-Speech tagging and speech recognition, are essentially dynamic Bayesian networks. Your understanding of inference is critical to understanding how HMMs work (e.g., the Viterbi algorithm for finding the most likely sequence).

Planning and Decision Making: When we move to agents that must act in the world, uncertainty is a key challenge. Markov Decision Processes (MDPs) extend the concepts from this chapter by adding actions and rewards, allowing an agent to formulate an optimal plan or policy in a probabilistic environment.

Probabilistic Reasoning

Probabilistic Reasoning

Overview

Chapter Contents

Learning Objectives

Introduction

Key Concepts

1. The Chain Rule of Probability

2. Bayesian Network Factorization

3. Reading Conditional Independence from a Graph

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

What's Next?

Part 2: Exact Inference

Introduction

Key Concepts

1. The Chain Rule for Bayesian Networks

2. Inference by Enumeration

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

What's Next?

Part 3: Approximate Inference

Introduction

The Need for Approximation

Exact Inference: A Brief Review (For Contrast)

Stochastic Sampling Methods

1. Rejection Sampling

2. Likelihood Weighting

3. Markov Chain Monte Carlo (MCMC) Methods

Gibbs Sampling

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

What's Next?

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Artificial Intelligence

Logic

Search Algorithms

More Resources

Study Notes

Short Notes

Test Series

Mock Tests

Previous Year Papers

Chapter-wise PYQs

Chapter Practice

Why Choose MastersUp?

AI-Powered Plans

15,000+ Questions

Smart Analytics

Bookmark & Revise