lOMoARcPSD|67953334

CP25C05 AIML unit-2 - aiml unit 2

Aiml (Anna University)

messages.pdf_cover_qr_code_label

messages.studocu_not_sponsored_or_endorsed_by_college
messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Uncertain Knowledge and Reasoning: Overview of uncertainty and basic

probability – Baye’s rule – Bayesian networks – Hidden Markov models –
Kalman filters – Utility Functions – Decision Networks – Sequential
decision problems – Game theory

2.1 Overview of uncertainty and basic probability

Probabilistic reasoning in Artificial Intelligence (AI) is a method that uses probability theory
to manage and model uncertainty in decision-making. Unlike traditional systems that depend
on precise information, it understands that real-world data is often incomplete, unclear or
noisy. By giving probabilities to different possibilities, AI systems can make better decisions,
predict outcomes and solve problems even when things are uncertain. This approach is
important for building smart systems that can work in changing environments and make good
choices in complex situations.

2.1.1 Need for Probabilistic Reasoning in AI

Probabilistic reasoning with artificial intelligence is important to different tasks such as:
 Machine Learning: It helps algorithms learn from incomplete or noisy data, refining
predictions over time.
 Robotics: It enables robots to navigate and interact with dynamic and unpredictable
environments.
 Natural Language Processing: It helps AI understand human language which is
often ambiguous and depends on context.
 Decision Making: It allows AI systems to evaluate different outcomes and make
better decisions by considering the likelihood of various possibilities.
2.1.2 Key Concepts in Probabilistic Reasoning
Probabilistic reasoning helps AI systems make decisions and predictions when they have to
deal with uncertainty. It uses different ideas and models to understand how likely things are
even when we don't have all the answers. Let's see some of the important concepts:
(i) Probability: It is a way to measure how likely something is to happen, typically expressed
as a number between 0 and 1. In AI, we use probabilities to understand and make predictions
when the information we have is uncertain or incomplete.
(ii) Bayes' Theorem: It helps AI systems update their beliefs when they get new information.
It’s like changing our mind about something based on new evidence. This is useful when we
need to adjust our predictions after learning new facts.

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

(iii). Conditional Probability: It is the chance of an event happening, given that something
else has already happened. This helps when the outcome depends on something that
happened before.
(iv). Random Variables: They are values that can change or vary based on uncertainty. In
simple terms, these are the things AI tries to predict or estimate. The possible outcomes of
these variables depend on probability.
2.1.3 Types of Probabilistic Models
There are different models that use these concepts to help AI systems make sense of
uncertainty. Let’s see some of them:
1. Bayesian Networks: They are graphs that show how different variables are
connected with probabilities. Each node represents a variable and the edges show how
they depend on each other. These networks help us understand how one piece of
information can affect another.
2. Markov Models: They predict the future state of a system based only on the present
state with no regard for the past. This is known as the "memoryless" property which
means the future depends only on the current situation not the history that led to it.
3. Hidden Markov Models (HMMs): They extend Markov models by introducing
hidden states that cannot be directly observed. These models help infer the hidden states
based on observable data, using statistical techniques to estimate the likelihood of these
unobservable conditions.
4. Probabilistic Graphical Models: It combine the features of Bayesian networks and
Hidden Markov Models, allowing more complex relationships between variables to be
represented. It provide a framework for managing uncertainty in large systems where
many variables are connected and interact with each other.
5. Markov Decision Processes (MDPs): They are used for decision-making,
particularly in reinforcement learning. It model an agent’s interaction with an
environment where the agent takes actions that affect the state of the environment and
receives rewards or penalties based on those actions.
2.1.4 Techniques in Probabilistic Reasoning
1. Inference: It calculates the probability of an outcome based on known data. Exact
methods like variable elimination and approximate methods like Markov Chain Monte
Carlo (MCMC) are used, depending on the complexity of the system.
2. Learning: It updates the parameters of probabilistic models as new data comes in,
improving predictions. Techniques like maximum likelihood estimation and Bayesian
estimation allow models to adapt and become more accurate over time.

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
3. Decision Making: AI uses probabilistic reasoning to make decisions that maximize
expected rewards. Partially Observable Markov Decision Processes (POMDPs) are used
when some information is hidden.
2.1.5 How Probabilistic Reasoning Enhances AI Systems?
Probabilistic reasoning helps AI systems navigate uncertainty, enabling them to make better
decisions even when information is unclear. Let's see how it works:
1. Quantifying Uncertainty: Probabilistic reasoning turns uncertainty into probabilities.
Instead of a simple “yes” or “no,” it provides a probability, like “there’s a 60% chance of
rain tomorrow.”
2. Reasoning with Evidence: As new information comes in, AI systems update their
predictions. For example, if dark clouds appear, the chance of rain might rise to 80%.
This continuous adjustment helps AI stay accurate.
3. Learning from Past Experiences: AI systems can improve predictions by learning
from historical data. For example, weather predictions become more accurate as the AI
system accounts for past seasonal trends.
4. Effective Decision-Making: It allows AI to make informed decisions by considering
the likelihood of different outcomes. It helps AI weigh possible paths and choose the best
option even when the future is uncertain.
2.1.6 Applications of Probabilistic Reasoning in AI
Probabilistic reasoning is applicable in a variety of domains which includes:
1. Robotics: In robotics, probabilistic reasoning helps with navigation and mapping. For
example, in Simultaneous Localization and Mapping, robots create maps and track their
position in unknown environments.
2. Healthcare: AI systems use probabilistic models to predict disease likelihood and
assist in diagnosis. Bayesian networks can model medical factors like symptoms and test
results to guide decisions.
3. Natural Language Processing: In tasks like speech recognition and translation,
models like Hidden Markov Models (HMMs) help AI understand and process ambiguous
language.
4. Finance: Probabilistic reasoning in finance helps predict market trends and assess
risks. Techniques like Bayesian inference and Monte Carlo simulations model financial
uncertainties for better decision-making.
2.1.7 Advantages of Probabilistic Reasoning
 Flexibility: Probabilistic models can handle different kinds of uncertainty and can be
adapted to work in various fields from healthcare to robotics.
 Robustness: These models remain effective even when the data is noisy or
incomplete, making them reliable in real-world scenarios where perfect data is rarely
available.
 Transparency: It provides a clear framework for understanding and explaining
uncertainty which helps build trust and improve the interpretability of AI decisions.
 Scalability: It can scale to handle large amounts of data and complex systems,
making them suitable for applications like big data analysis and large-scale decision-
making processes.
 Decision Support: These models assist in making informed decisions under
uncertainty by calculating the likelihood of different outcomes, helping AI systems
choose the best course of action based on expected results.

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

2.1.8 Challenges of Probabilistic Reasoning

Despite its various advantages, probabilistic reasoning in AI also has several challenges:
1. Complexity: Some models such as large Bayesian networks can become
computationally expensive, especially as the number of variables grows. This can slow
down processing and limit scalability.
2. Data Quality: Probabilistic models heavily rely on accurate and clean data. If the data
is noisy, incomplete or biased, the model’s predictions can become unreliable, leading to
incorrect conclusions.
3. Interpretability: Understanding how probabilistic models make decisions can be
tough, particularly in complex systems or deep learning models. This makes it harder to
trust and explain AI decisions to non-experts.

2.2 Baye’s Theorem

Bayes’ theorem describes the probability of occurrence of an event related to any condition.
It is also considered for the case of conditional probability. Bayes theorem is also known as
the formula for the probability of “causes”. For example: if we have to calculate the
probability of taking a blue ball from the second bag out of three different bags of balls,
where each bag contains three different colour balls viz. red, blue, black. In this case, the
probability of occurrence of an event is calculated depending on other conditions is known as
conditional probability. In this article, let us discuss the statement and proof for Bayes
theorem, its derivation, formula, and many solved examples.

2.2.1 Bayes Theorem Statement

Let E1, E2,…, En be a set of events associated with a sample space S, where all the events E1,
E2,…, En have nonzero probability of occurrence and they form a partition of S. Let A be any
event associated with S, then according to Bayes theorem,

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Note:

The following terminologies are also used when the Bayes theorem is applied:

Hypotheses: The events E1, E2,… En is called the hypotheses

Priori Probability: The probability P(Ei) is considered as the priori probability of hypothesis
Ei

Posteriori Probability: The probability P(Ei|A) is considered as the posteriori probability of

hypothesis Ei
Bayes’ theorem is also called the formula for the probability of “causes”. Since the Ei‘s are a
partition of the sample space S, one and only one of the events Ei occurs (i.e. one of the
events Ei must occur and the only one can occur). Hence, the above formula gives us the
probability of a particular Ei (i.e. a “Cause”), given that the event A has occurred.

2.2.2 Bayes Theorem Formula

If A and B are two events, then the formula for the Bayes theorem is given by:

Where P(A|B) is the probability of condition when event A is occurring while event B has
already occurred.
Also, get the Bayes Theorem Calculator here.

2.2.3 Bayes Theorem Derivation

Bayes Theorem can be derived for events and random variables separately using the
definition of conditional probability and density.

From the definition of conditional probability, Bayes theorem can be derived for events as
given below:

P(A|B) = P(A ⋂ B)/ P(B), where P(B) ≠ 0

P(B|A) = P(B ⋂ A)/ P(A), where P(A) ≠ 0

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Here, the joint probability P(A ⋂ B) of both events A and B being true such that,

P(B ⋂ A) = P(A ⋂ B)

P(A ⋂ B) = P(A | B) P(B) = P(B | A) P(A)

P(A|B) = [P(B|A) P(A)]/ P(B), where P(B) ≠ 0

Similarly, from the definition of conditional density, Bayes theorem can be derived for two
continuous random variables namely X and Y as given below:

2.2.4 Examples and Solutions

Some illustrations will improve the understanding of the concept.

Example 1:

A bag I contains 4 white and 6 black balls while another Bag II contains 4 white and 3 black
balls. One ball is drawn at random from one of the bags, and it is found to be black. Find the
probability that it was drawn from Bag I.

Solution:

Let E1 be the event of choosing bag I, E2 the event of choosing bag II, and A be the event of
drawing a black ball.

Then,

Also, P(A|E1) = P(drawing a black ball from Bag I) = 6/10 = 3/5

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

P(A|E2) = P(drawing a black ball from Bag II) = 3/7

By using Bayes’ theorem, the probability of drawing a black ball from bag I out of two
bags,

Example 2:

A man is known to speak the truth 2 out of 3 times. He throws a die and reports that the
number obtained is a four. Find the probability that the number obtained is actually a four.

Solution:

Let A be the event that the man reports that number four is obtained.
Let E1 be the event that four is obtained and E2 be its complementary event.
Then, P(E1) = Probability that four occurs = 1/6.
P(E2) = Probability that four does not occur = 1- P(E1) = 1 – (1/6) = 5/6.
Also, P(A|E1)= Probability that man reports four and it is actually a four = 2/3
P(A|E2) = Probability that man reports four and it is not a four = 1/3.
By using Bayes’ theorem, probability that number obtained is actually a four, P(E1|A)
│

2.2.4 Bayes Theorem Applications

One of the many applications of Bayes’ theorem is Bayesian inference, a particular

approach to statistical inference. Bayesian inference has found application in various
activities, including medicine, science, philosophy, engineering, sports, law, etc. For
example, we can use Bayes’ theorem to define the accuracy of medical test results
by considering how likely any given person is to have a disease and the test’s overall
accuracy. Bayes’ theorem relies on consolidating prior probability distributions to

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

generate posterior probabilities. In Bayesian statistical inference, prior probability is

the probability of an event before new data is collected.
2.2.5Practice Problems

Solve the following problems using Bayes Theorem.

1. A bag contains 5 red and 5 black balls. A ball is drawn at random, its colour is noted,
and again the ball is returned to the bag. Also, 2 additional balls of the colour drawn
are put in the bag. After that, the ball is drawn at random from the bag. What is the
probability that the second ball drawn from the bag is red?
2. Of the students in the college, 60% of the students reside in the hostel and 40% of the
students are day scholars. Previous year results report that 30% of all students who
stay in the hostel scored A Grade and 20% of day scholars scored A grade. At the end
of the year, one student is chosen at random and found that he/she has an A grade.
What is the probability that the student is a hosteler?
3. From the pack of 52 cards, one card is lost. From the remaining cards of a pack, two
cards are drawn and both are found to be diamond cards. What is the probability that
the lost card is a diamond?

2.3 Bayesian networks

Bayesian Belief Network (BBN) is a graphical model that represents the probabilistic
relationships among variables. It is used to handle uncertainty and make predictions or
decisions based on probabilities.
 Graphical Representation: Variables are represented as nodes in a directed acyclic
graph (DAG), and their dependencies are shown as edges.
 Conditional Probabilities: Each node's probability depends on its parent nodes,
expressed as

 Probabilistic Model: Built from probability distributions, BBNs apply

probability theory for tasks like prediction and anomaly detection.
Bayesian Belief Networks are valuable tools for understanding and solving problems
involving uncertain events. They are also known as Bayes networks, belief networks,
decision networks, or Bayesian models.
Note: A classifier assigns data in a collection to desired categories.
Consider this example:

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
 In the above figure, we have an alarm 'A' - a node, say installed in a house of a person
'gfg', which rings upon two probabilities i.e burglary 'B' and fire 'F', which are - parent
nodes of the alarm node. The alarm is the parent node of two probabilities P1 calls 'P1'
& P2 calls 'P2' person nodes.
 Upon the instance of burglary and fire, 'P1' and 'P2' call person 'gfg', respectively.
But, there are few drawbacks in this case, as sometimes 'P1' may forget to call the person
'gfg', even after hearing the alarm, as he has a tendency to forget things, quick. Similarly,
'P2', sometimes fails to call the person 'gfg', as he is only able to hear the alarm, from a
certain distance.
2.3.1 Calculating Conditional Probability of Events in a Bayesian Network
Find the probability that 'P1' is true (P1 has called 'gfg'), 'P2' is true (P2 has called
'gfg') when the alarm 'A' rang, but no burglary 'B' and fire 'F' has occurred.
=> P ( P1, P2, A, ~B, ~F) [ where- P1, P2 & A are 'true' events and '~B' & '~F' are
'false' events]
[ Note: The values mentioned below are neither calculated nor computed. They have
observed values ]
Burglary 'B' -
 P (B=T) = 0.001 ('B' is true i.e burglary has occurred)
 P (B=F) = 0.999 ('B' is false i.e burglary has not occurred)
Fire 'F' -
 P (F=T) = 0.002 ('F' is true i.e fire has occurred)
 P (F=F) = 0.998 ('F' is false i.e fire has not occurred)
Alarm 'A' :

B F P (A=T) P (A=F)

T T 0.95 0.05

T F 0.94 0.06

F T 0.29 0.71

F F 0.001 0.999

 The alarm 'A' node can be 'true' or 'false' ( i.e may have rung or may not have
rung). It has two parent nodes burglary 'B' and fire 'F' which can be 'true' or 'false'
(i.e may have occurred or may not have occurred) depending upon different
conditions.
Person 'P1' :

A P (P1=T) P (P1=F)

T 0.95 0.05

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

A P (P1=T) P (P1=F)

F 0.05 0.95

 The person 'P1' node can be 'true' or 'false' (i.e may have called
the person 'gfg' or not) . It has a parent node, the alarm 'A', which
can be 'true' or 'false' (i.e may have rung or may not have rung ,upon
burglary 'B' or fire 'F').
Person 'P2' :
A P (P2=T) P (P2=F)

T 0.80 0.20

F 0.01 0.99

 The person 'P2' node can be 'true' or false' (i.e may have called the
person 'gfg' or not). It has a parent node, the alarm 'A', which can be
'true' or 'false' (i.e may have rung or may not have rung, upon
burglary 'B' or fire 'F').
Solution: Considering the observed probabilistic scan -
With respect to the question — P ( P1, P2, A, ~B, ~F) , we need to get
the probability of 'P1'. We find it with regard to its parent node - alarm
'A'. To get the probability of 'P2', we find it with regard to its parent node
— alarm 'A'.
We find the probability of alarm 'A' node with regard to '~B' & '~F' since
burglary 'B' and fire 'F' are parent nodes of alarm 'A'.
From the observed probabilistic scan, we can deduce -

P ( P1, P2, A, ~B, ~F)

= P (P1/A) * P (P2/A) * P (A/~B~F) * P (~B) * P (~F)
= 0.95 * 0.80 * 0.001 * 0.999 * 0.998
= 0.00075
2.3.2 Basics of Inference in Bayesian Networks
Inference in Bayesian Networks involves answering probabilistic queries about the
network. The most common types of queries are:
 Marginalization: Determining the probability distribution of a subset of
variables, ignoring the values of all other variables.
 Conditional Probability: Computing the probability distribution of a subset of
variables given evidence observed on other variables.

10

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

2.3.3 Methods of Exact Inference

Exact inference in Bayesian Networks is a critical task for probabilistic reasoning under
uncertainty. Techniques like Variable Elimination, the Junction Tree Algorithm, and Belief
Propagation provide powerful tools for conducting this inference, although they can be
computationally intensive for large networks. Understanding these methods enhances one’s
ability to implement and utilize Bayesian Networks in various real-world applications, from
decision support systems to complex predictive modeling.

Amongst the extant exact inference methods developed in the context of Bayesian networks.
These methods operate under the assumptions of the network structure to achieve efficient
probability calculations.
The methods of Exact Inference are:
1. Variable Elimination
2. Junction Tree Algorithm
3. Belief Propagation
[Link] Variable Elimination
Variable Elimination is a popular exact inference technique that systematically sums out the
variables not of interest. The process involves manipulating and combining the network's
CPTs to answer queries efficiently.
Steps:
1. Factorization: Break down the joint probability distribution into a product of factors,
each corresponding to a CPT in the network.
2. Elimination: Sequentially eliminate each non-query, non-evidence variable by
summing over its values. This step reduces the dimensionality of the problem.
3. Normalization: After all eliminations, normalize the resulting distribution to ensure
that it sums to one.
Mathematical Representation:

[Link] Junction Tree Algorithm

The Junction Tree Algorithm, also known as the Clique Tree Algorithm, is a more structured
approach that converts the Bayesian Network into a tree structure called a "junction tree" or
"clique tree," where each node (clique) contains a subset of variables that form a complete
(fully connected) subgraph in the network.
Steps:
1. Triangulation: Modify the network to ensure that every cycle of four or more nodes
has a chord (an edge that is not part of the cycle but connects two nodes of the cycle).
2. Building the Junction Tree: Form cliques of variables and organize them into a tree
structure where each edge represents a conditional independence statement.
3. Message Passing: Perform a two-phase message passing (collecting and distributing)
to propagate information throughout the tree.

11

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

[Link] Belief Propagation

Belief Propagation (BP) is another exact inference method used particularly in networks that
form a tree structure or can be restructured into a tree-like form using the Junction Tree
Algorithm. It involves passing messages between nodes and uses these messages to compute
marginal probabilities at each node.
Steps:
1. Initialization: Each node initializes messages based on its local evidence and
conditional probabilities.
2. Message Passing: Nodes send and receive messages to and from their neighbors.
Each message represents a belief about the state of the sender, conditioned on the
evidence.
3. Belief Update: Each node updates its belief based on the incoming messages and its
initial probability.
Belief Propagation is especially effective in tree-structured networks where messages can be
propagated without loops, ensuring that each node's final belief is computed exactly once all
messages have been passed.

Challenges of Exact Inference

1. Exponential Complexity: Exact approaches like the variable elimination and the
junction tree are computationally complex and increase with a rate that is exponential to
the number of variables in the network. The diversity of the degrees of freedom further
implies that exact inference is not feasible for large networks with a large number of
variables.
2. Memory Requirements: Most exact inference methods involve the computation of a
large table or another structure such as a junction tree which in turn has to be stored in
memory. The use of sparse structures or high-dimensional probability distributions may
make the memory demands impractical in some cases, especially when the number of
variables in the network is large.
3. Loops and Cycles: Local computations can be performed using Bayesian networks
without loops or cycles that cause problems with exact inference algorithms. Variable
elimination can result in suboptimal computations and, in addition, junction tree
algorithms may cause more complicated loops.

2.3.4 Approximate Inference Techniques

Bayesian Networks (BNs) are probabilistic graphical models used to represent uncertain
relationships between variables. While exact inference in BNs provides accurate results, it
becomes computationally infeasible for large-scale networks due to the exponential growth of
computational complexity. As the number of variables and dependencies increases, exact
inference algorithms struggle to efficiently compute probabilities, limiting their practical
utility.

12

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Approximate Inference Techniques

(i)Sampling Methods

Sampling methods are probabilistic techniques used to approximate complex distributions in

Bayesian Networks by generating and analyzing representative samples. Some of the
sampling methods are:
1. Monte Carlo Methods: Monte Carlo methods use random sampling to estimate
numerical results. They are particularly useful for high-dimensional integrals and
summations in Bayesian Networks. By repeatedly sampling from the probability
distributions of interest, these methods provide approximations of desired quantities.
2. Markov Chain Monte Carlo (MCMC): MCMC methods generate samples from a
probability distribution by constructing a Markov chain that has the desired distribution
as its equilibrium distribution. Common MCMC algorithms include the Metropolis-
Hastings algorithm and Gibbs sampling. These methods are powerful for exploring
complex distributions but can be computationally intensive.
3. Gibbs Sampling: Gibbs Sampling is a specific type of MCMC method that iteratively
samples each variable from its conditional distribution given the current values of all
other variables. This technique is effective for high-dimensional spaces and can converge
to the target distribution under appropriate conditions.
Monte Carlo Methods
Monte Carlo methods use random sampling to approximate complex mathematical or
physical systems. The principle is to generate a large number of random samples from a
probability distribution and use these samples to estimate the properties of the distribution.
This process involves the following steps:
1. Define the Problem: Identify the quantity to be estimated (e.g., an integral or a
probability).
2. Generate Random Samples: Use a random number generator to produce samples
from the distribution of interest.
3. Compute the Estimate: Calculate the desired quantity using the generated samples,
often by averaging the results of the sampled data.

(ii)Variational Inference

Variational inference approximates probability distributions through optimization. It turns the

problem of inference into an optimization problem, making it more scalable for large
datasets.
1. Mean-field Approximation: The mean-field approximation simplifies the joint
distribution of the network by assuming that each variable is independent of the others.
This approach reduces computational complexity but may lose accuracy due to the
independence assumption.
2. Structured Variational Methods: Structured variational methods improve on mean-
field approximations by considering dependencies between variables. They provide more

13

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
accurate approximations by incorporating structured dependencies, but at the cost of
increased computational effort.
Variational inference turns the problem of inference into an optimization problem. Instead of
sampling from the posterior distribution, it approximates the distribution by a simpler
distribution and optimizes the parameters of this distribution to be as close as possible to the
true posterior.
The steps involved are:
1. Choose a Family of Distributions: Select a family of distributions parameterized by
variational parameters.
2. Define the Variational Objective: Typically, this is the Evidence Lower Bound
(ELBO), which is optimized to make the approximate distribution close to the true
posterior.
3. Optimize the ELBO: Use gradient descent or other optimization techniques to find
the best parameters.
Mathematically, the ELBO is defined as:

(iii)Loopy Belief Propagation

Loopy belief propagation extends the traditional belief propagation algorithm to networks
with cycles (loops). Although exact convergence is not guaranteed, it often provides good
approximations in practice. It is particularly useful in networks where exact inference is
computationally infeasible.
Let's cover the key methods in detail.
Loopy Belief Propagation (LBP) extends the Belief Propagation algorithm to
Bayesian Networks with cycles (loops).
The algorithm involves the following steps:
1. Initialization: Initialize messages on the edges of the network.
2. Message Passing: Iteratively update messages passed between nodes
based on neighboring messages.
3. Belief Update: Compute the beliefs (marginal probabilities) at each node from
the incoming messages.
Despite its name, LBP does not always converge, especially in networks with many
loops. Convergence issues can arise due to oscillations or divergence in the
message updates. When LBP converges, it often provides good approximations of
marginal probabilities.

2.3.5 Challenges in Approximate Inference

Approximate inference methods face several challenges:

14

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
1. Convergence Issues: Methods like MCMC may require a large number of
iterations to converge, and poor convergence can lead to inaccurate estimates.
2. Complexity and Scalability: While approximate methods are more scalable
than exact inference, they can still become computationally intensive for very
large networks or high-dimensional data.
3. Quality of Approximations: The accuracy of the approximations can vary
significantly depending on the method and the specific characteristics of the
Bayesian Network. Choosing an appropriate method and tuning its parameters is
crucial.
Approximate inference in Bayesian Networks has numerous practical applications
across different domains:
1. Machine Learning: Probabilistic graphical models and latent variable models
often rely on approximate inference for tasks such as clustering, classification,
and regression.
2. Medical Diagnosis: Bayesian Networks model the probabilistic relationships
between symptoms and diseases, aiding in diagnosis and treatment planning
under uncertainty.
3. Robotics: Real-time decision-making and sensor fusion in dynamic
environments leverage approximate inference for efficient and accurate
probabilistic reasoning.
Approximate inference methods are essential for the practical application of
Bayesian Networks in real-world scenarios where exact inference is computationally
prohibitive. By providing scalable and efficient solutions for probabilistic reasoning,
these methods enable the use of Bayesian Networks in various complex and high-
dimensional domains. Despite the challenges, continuous advancements in
approximate inference techniques promise to enhance their accuracy and
applicability, driving further innovations in fields that depend on robust probabilistic
models.

2.4 Hidden Markov Model

To work with sequential data where the actual states are not directly visible, the Hidden
Markov Model (HMM) is a widely used probabilistic model in machine learning. It
assumes that a system moves through hidden states over time, and each hidden state
produces an observable output based on certain probabilities.

15

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
This example shows a Hidden Markov Model where the hidden states are weather conditions
(Rainy, Cloudy, Sunny) and the observations are emotions (Happy, Neutral, Sad).
 The green arrows represent transition probabilities, showing how likely the weather is
to change from one state to another each day.
 Red arrows represent emission probabilities, showing how likely each emotion is
given the current weather.
 Since we only observe the emotions and not the actual weather, the HMM helps infer
the most probable hidden weather pattern behind those observations.
Assumptions of HMM
1. Hidden States
 The actual state of the system is not visible.
 Example: Weather (Sunny/Rainy) is hidden.
2. Observations
 We only see the outcomes produced by the hidden states.
 Example: Friend’s mood (Happy/Sad) is observed.
3. Markov Property
The model assumes the future state depends only on the current state not on the entire history.

Components of a Hidden Markov Model (HMM)

A Hidden Markov Model is defined by

1. Hidden States (N): These are the internal states of the system, which are not directly
observable.
2. Observations (M): These are the visible outputs generated by the hidden states.
3. Initial State Distribution (�π): Represents the probability of starting in each hidden
state.
4. Transition Probabilities (A): Defines the probability of moving from one hidden state to
another.
5. Emission Probabilities (B): Defines the probability of producing a particular observed
output from a given hidden state.
2.4.1 Three Fundamental Problems in Hidden Markov Models (HMMs)
Hidden Markov Models solve three core problems related to sequences of observations
generated by hidden states.

[Link]. Evaluation Problem (Forward Algorithm)

Problem: How to compute the probability of an observation sequence?
Mathematically, given an observation sequence:

16

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

[Link]. Decoding Problem (Viterbi Algorithm)

Problem: How to find the most likely hidden state sequence that explains the
observations?

Mathematically, it finds:

The Viterbi Algorithm efficiently computes this using dynamic programming by keeping
track of the maximum probability path to each state at each time step.

[Link]. Learning Problem (Baum–Welch Algorithm / EM)

Problem: How to train the HMM to fit the observed data?

Here, the goal is to estimate the model parameters that maximize the likelihood of the
observation sequence:

17

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

2.4.2 Applications
 Bioinformatics: Models DNA/protein sequences for gene identification and protein
classification.
 Finance: Capture hidden market states to predict trends and detect bullish/bearish
periods.
 NLP: Perform POS tagging, NER and early machine translation using sequential text
modeling.
 IoT and Cybersecurity: Detect anomalous event sequences in sensors or logs.
 Weather Forecasting: Predict future weather patterns from historical data sequences.
 Activity Recognition in Wearables: Classify activities like walking, running or
sleeping using sensor
2.4.3 Advantages
 Easy to Interpret: Clear probabilistic structure of hidden states and observations.
 Works Well on Small Datasets: Requires less data compared to deep learning
models.
 Fast Inference: Efficient algorithms like Forward and Viterbi enable quick
computation.
 Strong for Anomaly Detection: Can detect unusual sequences effectively.
 Mathematically Elegant: Solid foundation in probability and statistics.
2.4.4Limitations
 Markov Assumption: Only considers the previous state, limiting long-range
dependencies.
 Discrete Hidden States: Struggles with continuous or non-categorical hidden states.
 Difficulty with Complex Sequences: Less effective than RNNs or LSTMs on
complex sequences.
 Limited Long-Term Memory: Cannot remember distant past events effectively.
 Less Accurate for High-Dimensional Inputs: Performance drops with high-
dimensional data.

18

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
2.5 Kalman Filter
What is Kalman Filter (in one sentence) ? The Kalman Filter is an algorithm used for
predicting the state of an object over time, even in the presence of uncertainty and noisy
sensor data.
Common examples of “state” include:
Location (position)
Velocity (speed and direction)
Acceleration
Orientation (angle, heading, rotation)
Temperature, altitude, battery level, etc.
Basically, a Kalman Filter doesn’t care what you’re tracking — as long as it changes over
time in a somewhat predictable way and you can observe it (even imperfectly).

2.5.1 How It Works (in one sentence):

The Kalman Filter works by combining prior knowledge (the prediction) with new, possibly
noisy, sensor measurements to produce a better [Link] Filters use Bayesian
reasoning, let’s firstly take a look at the 1D example.

2.5.2 1D Kalman Filter:

If you’re unfamiliar with probability and Bayes’ Rule, check out this short article on Bayes’ Rule
and Probability.
Now, take a look at the graph below — a Bayesian update in a 1D Kalman Filter — which
visually demonstrates how prior knowledge and new observations combine into a sharper, more
confident estimate.

19

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Prior belief P(x):

This is the estimate of the state before incorporating the new
measurement. It has a certain mean (e.g., from prediction)
and variance (uncertainty).

Measurement likelihood P(z∣x):

This represents the probability of observing measurement z
if the true state were x. It usually has a tighter variance
(assuming sensors are precise).

After the measurement and applying Bayes’ rule, the

Kalman Filter will produce a even tighter new estimate as:

Posterior P(x∣z):
The new estimate that combines both sources of
information.

 The mean shifts to somewhere between the prior

mean and the measurement.

 The variance decreases, because now you

have more information (prediction + measurement).

20

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Why the Posterior Is Narrower (more certain)

One of the most powerful aspects of the Kalman Filter is

how it reduces uncertainty by combining two sources of
information: your prior belief and the measurement.

Kalman filter computes the updated (posterior) variance as:

In other words, the updated belief (posterior) is more

confident — it has less uncertainty than either the
prediction or the measurement alone.

In more extreme case where Prior and Measurement are far

apart. Kalman Filter can still produce a more confident
estimate, as in the graph below:

21

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

The following code demonstrates

 Starts with a very uncertain prior

 Repeatedly: Updates belief using a measurement

 Predicts new state after a motion

You’ll see uncertainty (variance) shrink as it gets more

confident!

22

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

# Measurement update: combine prior estimate with noisy

observation

def update_belief(prior_mean, prior_var, meas_value, meas_var):

combined_mean = (meas_var * prior_mean + prior_var *

meas_value) / (prior_var + meas_var)

combined_var = 1 / (1 / prior_var + 1 / meas_var)

return [combined_mean, combined_var]

# Prediction step: apply control input or expected motion

def predict_state(current_mean, current_var, motion_change,

motion_var):

predicted_mean = current_mean + motion_change

predicted_var = current_var + motion_var

return [predicted_mean, predicted_var]

# Example data

sensor_readings = [5.0, 6.0, 8.0, 9.0] # observed positions

motions_applied = [1.0, 2.0, 2.0, 1.0] # motion per step

sensor_noise = 3.0 # measurement

noise (variance)

motion_uncertainty = 2.0 # motion noise

(variance)

# Initial guess: very uncertain

estimated_position = 0.0

position_uncertainty = 500.0

# Run Kalman Filter steps

23

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

for i in range(len(sensor_readings)):

estimated_position, position_uncertainty = update_belief(

estimated_position, position_uncertainty,

sensor_readings[i], sensor_noise

print("Update:", [estimated_position, position_uncertainty])

estimated_position, position_uncertainty = predict_state(

estimated_position, position_uncertainty,

motions_applied[i], motion_uncertainty

print("Predict:", [estimated_position,

position_uncertainty])

# Final result

print("Final estimate:", [estimated_position,

position_uncertainty])

Utility Functions

A utility function measures a consumer’s preference and

satisfaction with different goods or services. As part of rational
choice theory, it helps economists analyze how consumers make
decisions to maximize satisfaction. Utility functions help inform
economists and businesses in sales, marketing, and product
development. Preferences can be ranked using ordinal utility,
which orders choices from most to least preferred, or cardinal
utility, which assigns numerical values to show the strength of
preferences. Utility functions are mathematically expressed using
formulas that capture these preferences.

24

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
 Utility function measures consumer satisfaction and
preferences for goods and services.
 Ordinal utility ranks choices by preference, while cardinal
utility measures the degree of preference.
 Marginal utility refers to the satisfaction from consuming an
additional unit of a product.
 The law of diminishing marginal utility states that
satisfaction decreases with each additional unit consumed.
- Utility functions help economists and companies
understand consumer behavior and guide product
development.
Exploring the Concept of Utility in Economics
In economics, utility represents the satisfaction or pleasure that
consumers receive for consuming a good or service. Utility
function measures consumers' preferences for a set of goods
and services.

Utility is measured in units called utils—the Spanish word for

useful— but calculating the benefit or satisfaction that consumers
receive is abstract and difficult to pinpoint. As a result,
economists measure utility in terms of revealed preferences by
observing consumers' choices. From there, economists create an
ordering of consumption baskets from the least desired to the
most preferred.
Understanding Ordinal Utility: Ranking Preferences
When economists measure or rank the preferences of
consumers, it is referred to as ordinal utility. In other words, the
order in which consumers choose one product over another can
establish that consumers assign a higher value to the chosen
product. Ordinal utility measures how consumers rank products,
but it does not measure how much more one ranks above the
other.

To better understand ordinal utility, consider the following

example. Three contestants vie for first place in a dance
competition. Contestant A is declared the winner. Contestant B is

25

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
the runner-up, and contestant C is ranked third. Ordinal utility
reveals that the judges preferred contestant A over contestants B
and C and contestant B over C. What ordinal function does not
tell us is to what degree one was preferred over the other.
Cardinal Utility: Assigning Numerical Values to Preferences
Mainly used in microeconomics, cardinal utility assigns a numeric
value to the consumer's preference, indicating the degree to
which one choice ranks above another. Cardinal utility will define
how much more contestant A was preferred over contestants B
and C, and so on.
Marginal Utility: Measuring Satisfaction from Additional Units
When considering utility, it is important to understand the
concepts of total utility and marginal utility. Marginal utility
measures the satisfaction or benefits a person gets
from consuming an additional unit of a product or service. Total
utility measures the satisfaction or benefits a person gets from
the total consumption—including marginal utility—of a product or
service.

If consuming 10 units of a product yields 20 utils, and consuming

one additional unit yields 1 util, the total utility is 21 utils. If
consuming another unit yields 0.5 utils, the total utility would then
become 21.5 utils.

Economists believe that the amount of satisfaction one receives

from each additional unit of consumption diminishes with each
unit consumed. This concept is called the law of diminishing
marginal utility. Diminishing marginal utility doesn't state that
consuming additional units will fail to satisfy the consumer; it
states that the satisfaction from consuming more and more units
is less than the first additional units consumed.

26

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Calculating a Utility Function: Methods and Examples

Example of Utility Function: A Practical Application

Let's say a consumer is shopping for a new car and has
narrowed the choice down to two cars. The cars are nearly
identical, except the second car has enhanced safety features.
As a result, the second car costs $2,000 more than the first car.

The incremental or marginal utility or satisfaction derived from

car two could be represented numerically as the $2,000 price
difference between the two cars. In other words, the consumer is
receiving $2,000 in incremental or marginal utility from car two.

Assume 100,000 consumers prefer car two over car one.

Economists could infer they gained $200 million in total utility
from the additional safety features. Utility is derived from the
consumer's belief that they are likely to have fewer accidents due
to the added safety features of car two.
Pros and Cons of Using Utility Functions
Economists can't assign a true numerical value to a consumer's
level of satisfaction from a preference or choice. Also, pinpointing
the reason for purchase can be difficult; there are usually many
variables to consider.

In the previous example, the two cars were nearly identical. In

reality, there might be several features or differences between
the two cars. As a result, assigning a value to a consumer's
preference can be challenging since one consumer might prefer
the safety features while another might prefer something else.

27

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Despite challenges, tracking utility is useful to economists. It
helps reveal shifts in spending and preferences over time.

Knowing why consumers choose certain products helps both

economists and companies. Executives use utility insights to see
how customers perceive their products.
What Is Utility Function?
Utility describes the benefits gained or satisfaction experienced
with the consumption of goods or services. Utility function
measures the preferences consumers apply to their consumption
of goods and services. For instance, if a customer prefers apples
to oranges no matter the amount consumed, the utility function
could be expressed as U(apples) > U(oranges).
What Is the Difference Between Utility Function and
Marginal Utility?
Utility function ranks consumers' consumption of goods or
services by preference. Marginal utility measures the change in
utility when the rate of consumption changes (i.e., how much
more satisfaction is gained by consuming another unit of a good
or service).
Why Is Utility Function Important?
Economists use utility function to better understand consumer
behaviors, as well as determine how well goods and services
provide satisfaction to consumers.

Utility function can also help analysts determine how to distribute

goods and services to consumers in a way that total utility is
realized.

Companies can use utility function to determine which product(s)

within their product line (or that of a competitor) consumers
prefer. Knowing these preferences can help management teams
enhance product development to assume a competitive
advantage.

28

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
The Bottom Line
Utility measures the satisfaction or benefit a consumer receives
from consuming goods or services. Economists use utility
functions to quantify preferences, helping analyze consumer
behavior and inform rational choice theory. Ordinal utility ranks
preferences without specifying the magnitude of differences,
while cardinal utility assigns numerical values to show how much
more one option is preferred over another. Businesses use these
insights to tailor products and marketing strategies to align with
consumer preferences. Marginal utility illustrates the principle of
diminishing marginal utility, where each extra unit provides less
satisfaction than the previous one.

Decision Networks

Decision networks, also known as influence diagrams, play a

crucial role in artificial intelligence by providing a structured
framework for making decisions under uncertainty. These
graphical representations integrate decision theory and
probability, enabling AI systems to systematically evaluate
various actions and their potential outcomes. In this article, we
will explore the components, structure, and applications of
decision networks in AI.

What is a Decision Network?

Decision networks are graphical models used to represent and
solve decision-making problems. They extend Bayesian
networks by incorporating decision and utility nodes, allowing for
a comprehensive analysis of decision scenarios.
Components of Decision Networks
A decision network consists of three types of nodes:
 Chance Nodes: Represent random variables and their
possible values, capturing the uncertainty in the decision-
making process.

29

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

 Decision Nodes: Represent the choices available to the

decision-maker.

30

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
 Utility Nodes: Represent the utility or value of the outcomes,
helping to evaluate and compare different decision paths.

Example of a Decision Network

Consider a simple medical diagnosis scenario where a doctor needs to
decide whether to order a test for a patient based on the likelihood of a
disease and the cost of the test. The decision network for this scenario
might include:
 Chance Nodes: Disease presence (Yes/No), Test result
(Positive/Negative)
 Decision Node: Order test (Yes/No)
 Utility Node: Overall patient health outcome and cost
The doctor can use the decision network to evaluate the expected utility
of ordering the test versus not ordering it, taking into account the
probabilities of disease presence and test results, and the utility values
associated with different outcomes.

Structure of Decision Networks

The structure of a decision network is typically represented as a directed
acyclic graph (DAG), where:
 Arcs (Edges): Indicate relationships between nodes. Arcs pointing
to chance nodes signify dependencies between random variables,
arcs pointing to decision nodes signify information available at the

31

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
time of decision, and arcs pointing to utility nodes represent factors
influencing the utility.
Representing a Decision Problem with a Decision
Network
To represent a decision problem with a decision network, the primary
step is to construct a graphical model capturing the relationship between
random variables, decision variables, and utility functions. The decision
network consists of nodes representing these elements and directed arcs
depicting dependencies between them.

Arcs in the Graph

 Arcs to Decision Nodes: Represent information available when

the decision is made.
 Arcs to Chance Nodes: Represent probabilistic dependence.
 Arcs to Utility Nodes: Represent what the utility depends on.
How to Structure a Decision Network?
To structure a decision network, follow these key steps:
1. Define Variables and Functions: Identify random variables,
decision variables, and utility functions crucial for the decision
problem.
2. Node Representation: Represent random variables as chance
nodes, decision variables as decision nodes, and utility functions as
utility nodes.
3. Connect Nodes: Use directed arcs to represent dependencies
between variables.
4. Directed Arcs:
 Arcs to decision nodes represent available information.
 Arcs to chance nodes represent probabilistic dependencies.
 Arcs to utility nodes represent utility dependencies.
5. Ensure DAG Structure: Avoid cycles or feedback loops in the arcs
to maintain a directed acyclic graph.
6. Define Domains: Specify the domain for each random variable
and decision variable. Utility nodes do not have domains.

32

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
7. Conditional Probability Distributions: Provide conditional
probability distributions for each random variable given their
parents in the network.
8. Utility Function: Define the utility function mapping the values of
the variables it relies on to a real number representing the decision-
maker's preferences.
Example of Representing a Decision Problem
Consider a simple decision network for deciding whether an agent
should take an umbrella when going out. The agent’s utility depends on
the weather and whether he takes an umbrella. The agent can only
observe the forecast and does not observe the weather directly. The
forecast depends on the weather.

Variables and Domains

 Weather: {norain, rain}

 Forecast: {sunny, rainy, cloudy}
 Umbrella: {take_it, leave_it}

33

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Probabilities

 P(Weather = rain) = 0.3

 P(Forecast | Weather):
Weather Forecast Probability

norain sunny 0.7

norain cloudy 0.2

norain rainy 0.1

rain sunny 0.15

rain cloudy 0.25

rain rainy 0.6

Utility Function
 u(Weather, Umbrella):
Weather Umbrella Utility

norain take_it 20

norain leave_it 100

rain take_it 70

34

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Weather Umbrella Utility

rain leave_it 0

Maximum Expected Utility

MEU, i.e. Maximum Expected Utility, is a basic principle in
decision theory and artificial intelligence. The MEU directs
decision-making by suggesting to choose the option that
maximizes the expected utility. The MEU suggests selecting the
action that is expected to yield the highest utility value while
considering the probabilities of different outcomes.
Assume an action (a), then the formula for the expected utility
(EU) for that specific action is:

Steps to Calculate Expected Utility

1. Specify Actions and States: Define likely actions and

states for the decision network.
2. Allocate Utility Values: Assign utility values to each state-
action pair.
3. Specify Probabilities: Use conditional probability
relationships to specify the probability of each state occurring
given a specific action.

35

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
4. Multiply Utility and Probability: Multiply the utility of each
action by its corresponding probability.
5. Sum Products: Sum the products to find the expected utility
of each action.
6. Repeat: Repeat for all available actions.
7. Select MEU: Choose the action with the highest expected
utility..
No-Forgetting Agent and Decision Network
No-Forgetting Property
A no-forgetting agent remembers previous decisions and
associated information, ensuring coherent decision-making in an
ordered manner.
Characteristics
 Ordered Decisions: Decisions are made in a specific order.
 Memory: Stores information about past decisions.
 Informed Choices: Considers past experiences to inform
future choices.
Structure and Implications
 Ordered Decision Nodes: Arranged in a specific sequence.
 Parent-Child Relationships: Preceding decision nodes are
parents of subsequent nodes.
 Information Flow: Information flows through the network,
influencing subsequent choices.
Evaluating Decision Networks
To ensure optimal functioning, evaluate decision networks using
these steps:
1. Verify Structure: Ensure the network structure accurately
reflects the real-world problem.
2. Sensitivity Analysis: Observe changes in output after
modifying probabilities or utilities.
3. Validate Recommendations: Compare network predictions
with real-world data.
4. Compare Networks: Analyze different decision networks for
the same problem to find the most desirable outcomes.
Applications of Decision Networks in AI
Decision networks are widely used in various AI applications,
including:

36

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
 Medical Diagnosis: Assisting doctors in making diagnostic
and treatment decisions.
 Robotics: Enabling robots to make decisions in uncertain
environments.
 Finance: Helping financial analysts make investment
decisions under uncertainty.
 Game Theory: Analyzing strategic interactions in
competitive environments.
 Operations Research: Optimizing resource allocation and
scheduling decisions.
Advantages of Decision Networks
 Comprehensive Framework: Integrates probability and
utility theory, providing a robust framework for decision-making
under uncertainty.
 Clarity and Visualization: Offers a clear visual
representation of decision problems, making complex
scenarios easier to understand and analyze.
 Optimization: Facilitates the identification of optimal
decision strategies by evaluating expected utilities.
Conclusion
Decision networks are powerful tools in AI, enabling systematic
and informed decision-making in uncertain environments. By
integrating chance, decision, and utility nodes, they provide a
comprehensive framework for evaluating and optimizing decision
strategies. From medical diagnosis to robotics and finance,
decision networks have broad applications, making them an
essential component of modern AI systems.

Sequential decision problems

Sequential decision problems are at the heart of artificial

intelligence (AI) and have become a critical area of study due to
their vast applications in various domains, such as robotics,
finance, healthcare, and autonomous systems. These problems
involve making a sequence of decisions over time, where each
decision can affect future outcomes, leading to a complex

37

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
decision-making process that requires balancing immediate
rewards with long-term benefits.

Introduction to Sequential Decision Problems

Sequential decision problems occur when an agent must make a
series of decisions in an environment, with each decision
affecting not only the immediate outcome but also the future
states of the environment. These decisions are interdependent,
meaning that the optimal decision at any point depends on the
decisions made previously and the potential decisions that will be
made in the future.
A classic example is the process of playing chess, where each
move influences the subsequent moves and the overall outcome
of the game. The challenge in such problems is to devise a
strategy that optimizes a certain objective, such as maximizing
the total reward or minimizing the total cost, over the entire
sequence of decisions.
Five Key Components of Sequential Decision
Problems
1. States: The state represents the current situation of the
environment. It encapsulates all the necessary information to
make a decision. For example, in a game of chess, the state
would include the positions of all the pieces on the board.
2. Actions: Actions are the choices available to the agent at
any given state. Each action leads to a transition from one
state to another. In the chess example, an action would be
moving a piece from one square to another.
3. Transitions: The transition model describes how the state
changes in response to an action. This is often probabilistic in
nature, especially in environments where uncertainty plays a
role.
4. Rewards: The reward function assigns a numerical value to
each state or state-action pair, representing the immediate
benefit of being in that state or taking that action. The objective
is typically to maximize the cumulative reward over time.
5. Policies: A policy is a strategy that defines the action the
agent will take in each state. An optimal policy maximizes the
expected cumulative reward over time.

38

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Types of Sequential Decision Problems

Sequential decision problems can be categorized based on the
environment's characteristics and the information available to the
agent:

1. Markov Decision Processes (MDPs)

MDPs are a fundamental framework for modeling sequential
decision problems where the environment is fully observable, and
the transitions between states are probabilistic. The decision-
making process relies on the Markov property, where the future
state depends only on the current state and action, not on the
history of past states.

2. Partially Observable Markov Decision Processes

(POMDPs)
In many real-world scenarios, the agent does not have complete
information about the current state of the environment. POMDPs
extend MDPs by introducing hidden states and an observation
model, making the decision-making process more complex.

3. Multi-armed Bandits
This is a simpler form of sequential decision problem where the
agent must choose between multiple actions (or arms), each with
an unknown probability distribution of rewards. The challenge is
to balance exploration (trying out different actions) and
exploitation (choosing the action with the highest known reward).

4. Reinforcement Learning
Reinforcement learning (RL) is a popular approach for solving
sequential decision problems where the agent learns an optimal
policy through trial and error, receiving rewards or penalties for its
actions. RL is widely used in AI for tasks such as game playing,
robotic control, and resource management.

Sequential Decision Problem Solving with

Value Iteration in Grid Environments
In this section, we are going to implement sequential decision
making problem using Value Iteration which is a form of dynamic
programming. This problem is modeled as a Markov Decision

39

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Process (MDP) where the system's dynamics are described by
states, actions, and rewards.
Here’s a breakdown of the key components and the technique
used:

1. Sequential Decision Making Problem

The task involves navigating through a grid world, where the goal
is to find an optimal policy that dictates the best action to take in
each state to maximize the cumulative reward. The decision-
making is sequential because each decision (or action) leads to a
new state, and the choice of action at each step depends on the
current state of the environment.

2. Markov Decision Process

1. States: The grid positions, represented as tuples (i, j).

2. Actions: Possible moves (Up, Down, Left, Right) which can
alter the state.
3. Rewards: Specific outcomes defined for reaching the goal,
hitting obstacles, or moving to regular positions.
4. Transitions: The result of taking an action in a state,
leading to a new state.

Implementation

Step 1: Define the Environment and Initialize Parameters

In this step, we define the grid world's size and characteristics,
including the goal state and obstacles. We also set key
parameters like the discount factor and the convergence
threshold.
import numpy as np

# Define the grid world parameters

grid_size = 3
goal_state = (2, 2)
obstacles = [(1, 1)]
gamma = 0.9 # Discount factor
epsilon = 0.01 # Convergence threshold

40

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Step 2: Define Reward Function and Actions
Set up the reward function and the possible actions an agent can
take within the grid.
# Define the reward function
def reward_function(state):
if state == goal_state:
return 1
elif state in obstacles:
return -1
else:
return 0

# Define possible actions and their effects

actions = {
"Up": (-1, 0),
"Down": (1, 0),
"Left": (0, -1),
"Right": (0, 1)
}

Step 3: Initialize Value Function and Policy

Set the initial value function and a random initial policy.
# Initialize value function and policy
V = [Link]((grid_size, grid_size))
policy = [Link](list([Link]()), (grid_size,
grid_size))

Step 4: Implement the Value Iteration Algorithm

def value_iteration(V, policy):
while True:
delta = 0
new_V = [Link](V)

for i in range(grid_size):
for j in range(grid_size):
state = (i, j)
if state == goal_state or state in obstacles:
continue

action_values = []
for action in actions:
next_state = get_next_state(state, action)
reward = reward_function(next_state)
action_value = reward + gamma *
V[next_state]
action_values.append(action_value)

best_action_value = max(action_values)

41

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
new_V[state] = best_action_value
best_action = list([Link]())
[[Link](action_values)]
policy[state] = best_action
delta = max(delta, abs(V[state] -
best_action_value))

V = new_V
if delta < epsilon:
break

return V, policy

V, optimal_policy = value_iteration(V, policy)

Step 5: Visualize the Results

Create a visual representation of the grid world, including the
optimal policy with directional arrows.
import [Link] as plt

fig, ax = [Link]()

# Create a grid
ax.set_xticks([Link](-0.5, grid_size, 1), minor=True)
ax.set_yticks([Link](-0.5, grid_size, 1), minor=True)
[Link](which="minor", color="black", linestyle='-',
linewidth=2)

# Draw obstacles and goal state

for obs in obstacles:
ax.add_patch([Link]((obs[1] - 0.5, obs[0] - 0.5),
1, 1, fill=True, color="red"))
ax.add_patch([Link]((goal_state[1] - 0.5, goal_state[0]
- 0.5), 1, 1, fill=True, color="green"))

# Draw policy arrows

for i in range(grid_size):
for j in range(grid_size):
state = (i, j)
if state == goal_state or state in obstacles:
continue
action = optimal_policy[state]
# Arrow drawing code based on the action

ax.set_aspect('equal')
[Link]()

Step 6: Output the Value Function and Policy

print("Optimal Value Function:")
print(V)

42

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
print("\nOptimal Policy:")
for i in range(grid_size):
print([optimal_policy[(i, j)] for j in range(grid_size)])

Applications of Sequential Decision Problems

1. Robotics: In robotics, sequential decision problems arise in
navigation, path planning, and manipulation tasks. Robots
must make a series of decisions to achieve a goal, such as
reaching a destination or assembling a product, while
accounting for dynamic changes in the environment.
2. Finance: Financial decision-making often involves
sequential decisions, such as portfolio management, where
investors must decide how to allocate assets over time to
maximize returns while managing risks.
3. Healthcare: In healthcare, treatment planning for chronic
diseases can be modeled as a sequential decision problem,
where doctors must choose a series of treatments that
optimize patient outcomes over time.
4. Autonomous Systems: Autonomous vehicles, drones, and
other autonomous systems rely on sequential decision-making
to navigate complex environments, avoid obstacles, and
achieve their objectives.

43

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II

Challenges in Solving Sequential Decision

Problems
 Computational Complexity: As the number of states and
actions increases, the computational complexity of finding an
optimal policy grows exponentially. This is known as the
"curse of dimensionality."
 Uncertainty and Exploration: In many sequential decision
problems, the agent must deal with uncertainty about the
environment and the outcomes of its actions. Balancing
exploration (gathering information) and exploitation (using
known information to make decisions) is a key challenge.
 Scalability: For large-scale problems, traditional methods
may not be feasible. Approximation techniques, such as deep
reinforcement learning, are often used to handle high-
dimensional state and action spaces.
Conclusion
Sequential decision problems are a fundamental aspect of AI,
playing a crucial role in various applications where decision-
making over time is essential. Understanding the structure of
these problems and the methods used to solve them is key to
advancing AI research and developing intelligent systems
capable of making complex, long-term decisions. As AI continues
to evolve, the ability to tackle more sophisticated sequential
decision problems will become increasingly important, driving
innovation in fields ranging from robotics to finance and beyond.
Game theory is basically a branch of mathematics that is used to
typical strategic interaction between different players (agents), all
of which are equally rational, in a context with predefined rules (of
playing or maneuvering) and outcomes. Every player or agent is
a rational entity who is selfish and tries to maximize the reward to
be obtained using a particular strategy. All the players abide by
certain rules in order to receive a predefined playoff- a reward
after a certain outcome. Hence, a GAME can be defined as a set
of players, actions, strategies, and a final playoff for which all the
players are competing.
Game Theory has now become a describing factor for both
Machine Learning algorithms and many daily life situations.
Consider the SVM (Support Vector Machine) for instance.

44

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
According to Game Theory, the SVM is a game between 2
players where one player challenges the other to find the best
hyper-plane after providing the most difficult points for
classification. The final playoff of this game is a solution that will
be a trade-off between the strategic abilities of both players
competing.
Types of Games:
Currently, there are about 5 types of classification of games.
They are as follows:
1. Zero-Sum and Non-Zero Sum Games: In non-zero-sum
games, there are multiple players and all of them have the
option to gain a benefit due to any move by another player. In
zero-sum games, however, if one player earns something, the
other players are bound to lose a key playoff.
2. Simultaneous and Sequential Games: Sequential games
are the more popular games where every player is aware of
the movement of another player. Simultaneous games are
more difficult as in them, the players are involved in a
concurrent game. BOARD GAMES are the perfect example of
sequential games and are also referred to as turn-based or
extensive-form games.
3. Imperfect Information and Perfect Information
Games: In a perfect information game, every player is aware
of the movement of the other player and is also aware of the
various strategies that the other player might be applying to
win the ultimate playoff. In imperfect information games,
however, no player is aware of what the other is up to. CARDS
are an amazing example of Imperfect information games while
CHESS is the perfect example of a Perfect Information game.
4. Asymmetric and Symmetric Games: Asymmetric games
are those win in which each player has a different and usually
conflicting final goal. Symmetric games are those in which all
players have the same ultimate goal but the strategy being
used by each is completely different.
5. Co-operative and Non-Co-operative Games: In non-co-
operative games, every player plays for himself while in co-
operative games, players form alliances in order to achieve the
final goal.

45

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
Nash equilibrium:
Nash equilibrium can be considered the essence of Game
Theory. It is basically a state, a point of equilibrium of
collaboration of multiple players in a game. Nash Equilibrium
guarantees maximum profit to each player.
Let us try to understand this with the help of Generative
Adversarial Networks (GANs).

What is GAN?
It is a combination of two neural networks: the Discriminator and
the Generator. The Generator Neural Network is fed input images
which it analyzes and then produces new sample images, which
are made to represent the actual input images as close as
possible. Once the images have been produced, they are sent to
the Discriminator Neural Network. This neural network judges the
images sent to it and classifies them as generated images and
actual input images. If the image is classified as the original
image, the DNN changes its parameters of judging. If the image
is classified as a generated image, the image is rejected and
returned to the GNN. The GNN then alters its parameters in order
to improve the quality of the image produced.
This is a competitive process which goes on until both neural
networks do not require to make any changes in their parameters
and there can be no further improvement in both neural networks.
This state of no further improvement is known as NASH
EQUILIBRIUM. In other words, GAN is a 2-player competitive
game where both players are continuously optimizing themselves
to find a Nash Equilibrium.

46

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
But how do we know if the game has reached Nash
Equilibrium?
In any game, one of the agents is required to disclose their
strategy in front of the other agents. After the revelation, if none
of the players changes their strategies, it is understood that the
game has reached Nash Equilibrium.
Now that we are aware of the basics of Game Theory, let us try to
understand how Nash Equilibrium is attained in a simultaneous
game. There are many examples but the most famous is the
Prisoner’s Dilemma. There are some more examples such as the
Closed-bag exchange Game, the Friend or For Game, and the
iterated Snowdrift Game.
In all these games, two players are involved and the final playoff
is a result of a decision that has to be made by both players. Both
players have to make a choice between defection and co-
operation. If both players cooperate, the final playoff will turn out
to be positive for both. However, if both defect, the final playoff
will be negative for both players. If there is a combination of one
player defecting and the other co-operating, the final playoff will
be positive for one and negative for another.
Here, Nash Equilibrium plays an important role. Only if both
players jot out a strategy that benefits each other and provide
both with a positive playoff, the solution to this problem will be
optimal.
There are many more real examples and a number of pieces of
code that try to solve this dilemma. The basic essence, however,
is the attainment of the Nash Equilibrium in an uncomfortable
situation.
Where is GAME THEORY now?
Game Theory is increasingly becoming a part of the real-world in
its various applications in areas like public health services, public
safety, and wildlife. Currently, game theory is being used in
adversary training in GANs, multi-agent systems, and imitation
and reinforcement learning. In the case of perfect information and
symmetric games, many Machine Learning and Deep Learning
techniques are applicable. The real challenge lies in the
development of techniques to handle incomplete information
games, such as Poker. The complexity of the game lies in the

47

messages.downloaded_by
 lOMoARcPSD|67953334

CP25C05 Artificial Intelligence and Machine

Learning UNIT-II
fact that there are too many combinations of cards and the
uncertainty of the cards being held by the various players.

48

messages.downloaded_by