UNIT – V

Reinforcement Learning – Overview – Getting Lost Example Markov Chain Monte Carlo
Methods – Sampling – Proposal Distribution – Markov Chain Monte Carlo – Graphical
Models – Bayesian Networks – Markov Random Fields – Hidden Markov Models –
Tracking Methods.

REINFORCEMENT LEARNING
Reinforcement Learning (RL) is a branch of machine learning that focuses on how agents
can learn to make decisions through trial and error to maximize cumulative rewards. RL allows
machines to learn by interacting with an environment and receiving feedback based on their
actions. This feedback comes in the form of rewards or penalties.

Reinforcement Learning revolves around the idea that an agent (the learner or decision-maker)
interacts with an environment to achieve a goal. The agent performs actions and receives
feedback to optimize its decision-making over time.
• Agent: The decision-maker that performs actions.
• Environment: The world or system in which the agent operates.
• State: The situation or condition the agent is currently in.
• Action: The possible moves or decisions the agent can make.
• Reward: The feedback or result from the environment based on the agent’s action.

How Reinforcement Learning Works?

The RL process involves an agent performing actions in an environment, receiving rewards or
penalties based on those actions, and adjusting its behavior accordingly. This loop helps the
agent improve its decision-making over time to maximize the cumulative reward.
Here’s a breakdown of RL components:
• Policy: A strategy that the agent uses to determine the next action based on the
current state.
• Reward Function: A function that provides feedback on the actions taken, guiding
the agent towards its goal.
 • Value Function: Estimates the future cumulative rewards the agent will receive
from a given state.
• Model of the Environment: A representation of the environment that predicts
future states and rewards, aiding in planning.

Reinforcement Learning Example: Navigating a Maze

Imagine a robot navigating a maze to reach a diamond while avoiding fire hazards. The goal is
to find the optimal path with the least number of hazards while maximizing the reward:
• Each time the robot moves correctly, it receives a reward.
• If the robot takes the wrong path, it loses points.
The robot learns by exploring different paths in the maze. By trying various moves, it evaluates
the rewards and penalties for each path. Over time, the robot determines the best route by
selecting the actions that lead to the highest cumulative reward.

The robot’s learning process can be summarized as follows:

1. Exploration: The robot starts by exploring all possible paths in the maze, taking
different actions at each step (e.g., move left, right, up, or down).
2. Feedback: After each move, the robot receives feedback from the environment:
• A positive reward for moving closer to the diamond.
• A penalty for moving into a fire hazard.
3. Adjusting Behavior: Based on this feedback, the robot adjusts its behavior to
maximize the cumulative reward, favoring paths that avoid hazards and bring it
closer to the diamond.
4. Optimal Path: Eventually, the robot discovers the optimal path with the least
number of hazards and the highest reward by selecting the right actions based on
past experiences.

Application of Reinforcement Learning

1. Robotics: RL is used to automate tasks in structured environments such as
manufacturing, where robots learn to optimize movements and improve efficiency.
 2. Game Playing: Advanced RL algorithms have been used to develop strategies for
complex games like chess, Go, and video games, outperforming human players in
many instances.
3. Industrial Control: RL helps in real-time adjustments and optimization of
industrial operations, such as refining processes in the oil and gas industry.
4. Personalized Training Systems: RL enables the customization of instructional
content based on an individual’s learning patterns, improving engagement and
effectiveness.
Advantages of Reinforcement Learning
• Solving Complex Problems: RL is capable of solving highly complex problems
that cannot be addressed by conventional techniques.
• Error Correction: The model continuously learns from its environment and can
correct errors that occur during the training process.
• Direct Interaction with the Environment: RL agents learn from real-time
interactions with their environment, allowing adaptive learning.
• Handling Non-Deterministic Environments: RL is effective in environments
where outcomes are uncertain or change over time, making it highly useful for real-
world applications.

Disadvantages of Reinforcement Learning

• Not Suitable for Simple Problems: RL is often an overkill for straightforward
tasks where simpler algorithms would be more efficient.
• High Computational Requirements: Training RL models requires a significant
amount of data and computational power, making it resource-intensive.
• Dependency on Reward Function: The effectiveness of RL depends heavily on the
design of the reward function. Poorly designed rewards can lead to suboptimal or
undesired behaviors.
• Difficulty in Debugging and Interpretation: Understanding why an RL agent
makes certain decisions can be challenging, making debugging and troubleshooting
complex

GETTING LOST EXAMPLE- MARKOV CHAIN MONTE CARLO

METHODS
A classic example of a Markov Chain Monte Carlo (MCMC) application is simulating the
movement of a "getting lost" person in a city. Imagine a person walking randomly, with a certain
probability of moving in each direction, representing a Markov chain. MCMC algorithms, like
Metropolis-Hastings, can then be used to explore this chain and understand the likely path of the
person, or even estimate the probability of them eventually reaching a specific location.

1. The Markov Chain:

• States:
Each location in the city (e.g., streets, intersections) can be considered a state in the Markov
chain.
• Transitions:
The probability of moving from one location to another (e.g., walking to the next street)
defines the transition probabilities of the Markov chain.
• Independence:
The next location depends only on the current location, not the entire previous path (the
Markov property).
2. MCMC Algorithms:
Metropolis-Hastings:
This is a common MCMC algorithm that can be used to sample from the probability
distribution of the person's location.
• Steps:
o Start with an initial location.
o Propose a new location based on the current location (e.g., by moving randomly in
one of the four cardinal directions).
o Calculate the acceptance probability of the proposed new location. This probability
depends on the likelihood (probability) of the person being at that location.
o If the acceptance probability is high enough (or always accepted if the proposed
move improves the likelihood), move to the new location. Otherwise, stay in the
current location.
o Repeat these steps many times to explore the probability distribution of the person's
location.
3. Applying MCMC to "Getting Lost":
• Exploring the City:
By running the MCMC algorithm, you can simulate the person's movement over time,
essentially creating a "walk" through the city.
• Estimating Likelihoods:
You can use the MCMC samples to estimate the probability of the person being at any
particular location after a certain number of steps.
• Finding Paths:
You can analyze the MCMC samples to understand the most likely paths the person might
take, or even the probability of them reaching a specific destination (e.g., a store, their
home).
In essence, MCMC methods allow you to explore and understand the probabilistic behavior of a
system (like a "getting lost" person) that can be modeled as a Markov chain. This is useful for
various applications, including understanding complex systems, optimizing paths, and predicting
future states.

SAMPLING

• When we have a big dataset and excited to get started with analyzing it and building your
machine learning model. Our machine gives an “out of memory” error while trying to load
the dataset.
• It’s happened to us most of the time when we have big dataset. Big dataset is one of the
biggest hurdles we face in data science — dealing with massive amounts of data on
computationally limited machines (of course we can resolve it with additional resource
power).
• So how can we overcome this problem? Is there a way to pick a subset of the data and
analyze that — and that can be a good representation of the entire dataset? Here comes the
statistical approach to deal with bigger dataset called “Sampling”.
• “Sampling is a method that allows us to get information about the population based
on the statistics from a subset of the population (sample), without having to
investigate every individual”
• Example: When you conduct research about a group of people, it’s rarely possible to
collect data from every person in that group. Instead, you select a sample. The sample is
the group of individuals who will actually participate in the research.

Steps involved in sampling framework:

Step 1: The first stage in the sampling process is to clearly define the target population.

Step 2: Sampling Frame — It is a list of items or people forming a population from which the
sample is taken.

Step3: Generally, probability sampling methods are used.

Step 4: Sample Size — It is the number of individuals or items to be taken in a sample that
would be enough to make inferences about the population with the desired level of accuracy and
precision. Larger the sample size, more accurate our inference about the population would be.

Step 5: Once the target population, sampling frame, sampling technique, and sample size have
been established, the next step is to collect data from the sample.

• Probability Sampling: In probability sampling, every element of the population has

an equal chance of being selected. Probability sampling gives us the best chance to
create a sample that is truly representative of the population

• Non-Probability Sampling: In non-probability sampling, all elements do not have

an equal chance of being selected. Consequently, there is a significant risk of ending
up with a non-representative sample which does not produce generalizable results

1. Probability Sampling (Everyone has a known chance of being selected)

• Simple Random Sampling: Everyone has an equal chance (like picking names from a
hat).
• Systematic Sampling: Pick every 5th, 10th, or 20th person from a list.
• Stratified Sampling: Divide people into groups (like by age or gender) and randomly
pick from each group.
• Cluster Sampling: Divide the population into clusters (like cities) and randomly select
whole clusters.
2. Non-Probability Sampling (Not everyone has a chance; selection is based on other factors)

• Convenience Sampling: Pick whoever is easiest to reach (like asking your friends).
• Judgmental Sampling: You choose who you think is best to include.
• Snowball Sampling: Existing participants refer new participants (good for finding rare
groups).
• Quota Sampling: You pick people to meet a set number for each group (like 50 men and
50 women).

PROPOSAL DISTRIBUTION
A proposal distribution (denoted q(x′∣x)) is a probability distribution used to propose a new
state x′ given the current state x in the Markov chain. The choice of proposal distribution directly
impacts the efficiency and convergence of MCMC algorithms.
Example Robot Exploring a Maze

Imagine you have a robot in a maze. The robot is trying to find the best path to the goal, but it
doesn’t know the full layout of the maze. It can only try different moves and learn if they’re
good or bad over time.

The Goal: The robot wants to find the most likely paths (according to some hidden rules, like
shortest path or least danger). But it can’t sample these good paths directly — the maze is too
complex.

What Does the robot do?

Instead of guessing perfectly:

1. It uses a proposal distribution — this is like the robot saying:

“Let me randomly propose a move, like ‘turn left’ or ‘move forward 2 steps’ based on my
current location.”

2. It tries the move and checks:

“Is this move likely to help me get to the goal?”

3. If the move looks promising (based on some probability), it accepts it. If not, it rejects it
and stays in place (or tries another).
How This Connects to ML:

• The maze is like the complex target probability distribution — we don’t know its full
shape.
• The robot’s random move is like sampling from the proposal distribution — a simple
way to suggest new positions (or parameter values).
• The accept/reject step helps the robot eventually explore the most important areas of
the maze — just like in MCMC, we sample more from the “important” regions of the
target distribution.

MARKOV CHAIN MONTE CARLO

Markov Chain Monte Carlo (MCMC) is a powerful technique used in statistics and various
scientific fields to sample from complex probability distributions. It is particularly useful when
directly sampling from the distribution is difficult or impossible. Here is a breakdown of the
name:

• Monte Carlo: This refers to a general approach using randomness to solve problems,
drawing inspiration from the element of chance involved in casino games.
• Markov Chain: This is a sequence of random events where the probability of the next
event depends only on the current event, not the history leading up to it.

MCMC combines constructing a Markov chain and recording samples from the chain. The chain
is designed to spend more time in regions with higher probability according to the target
distribution. Then, by recording states from the chain after it has ‘warmed up’ and reached a
stable state, you effectively get samples from the target distribution.
 So, we accept it with probability α<1

Why Accept Worse States at All?

Accepting worse states occasionally helps the algorithm:

• Escape local maxima

• Explore the entire space
• Ensure convergence to the true target distribution
• The goal is to sample from the entire target distribution, not just find its maximum.
Accepting worse states occasionally allows the chain to explore low-probability regions
and later return to higher ones — which is important for accurate sampling.

The min(1, ...) part ensures that the acceptance probability α\alphaα is always between 0 and 1,
which is required because:

• A probability cannot exceed 1.

 • We want to accept better states with full certainty (i.e., probability = 1).
• We want to accept worse states only with a chance less than 1.
• If the min(1, ...) part of the Metropolis-Hastings acceptance formula were removed, and
the acceptance probability were allowed to exceed 1, you would break the algorithm and
violate the balance and the resulting samples would not reflect the target distribution .
That means your entire MCMC sampling process could give incorrect, biased results.

How Is Markov Chain Monte Carlo Used In Machine Learning?

MCMC plays a crucial role in various aspects of machine learning, particularly when dealing
with complex probabilistic models or situations where direct sampling is difficult. Here are some
key ways it’s utilised:

• Bayesian Inference: Machine learning often involves estimating unknown parameters in

models based on observed data. In the Bayesian framework, these parameters are treated
as random variables with prior probability distributions. MCMC helps sample from the
posterior distribution, which combines the prior information with the likelihood of the
data, allowing for a better understanding of the parameter uncertainties and making
predictions with appropriate confidence intervals.
• Model Selection: When choosing between different models, MCMC can be used to
compare their posterior probabilities by integrating over the parameter space. This helps
identify the model that best fits the data and accounts for the model’s complexity.
• Latent Variable Models: These models involve hidden variables that are not directly
observed but influence the observed data. MCMC is used to infer the posterior
distribution of these latent variables, providing insights into the underlying structure of
the data. This is crucial in techniques like dimensionality reduction and topic modelling.
• Variational Inference (VI): While not directly using Markov Chain Monte Carlo, some
machine learning algorithms like Variational Inference (VI) borrow ideas from MCMC.
VI approximates the posterior distribution through an optimisation process inspired by
MCMC, making it applicable when exact MCMC sampling might be computationally
expensive.
• Deep Learning: Markov Chain Monte Carlo can be integrated with deep learning
techniques, particularly in Bayesian deep learning, where MCMC helps sample from the
posterior distribution of the network weights, enabling learning and uncertainty
quantification.

What Are Some Common Applications of Markov Chain Monte Carlo In AI?

Markov Chain Monte Carlo finds several applications in various aspects of artificial intelligence
(AI), particularly when dealing with complex probabilistic models or situations where direct
sampling is impractical. Here are some common areas where MCMC plays a significant role:
 • Uncertainty Quantification: MCMC allows AI models, especially Bayesian neural
networks, to capture the uncertainty associated with their predictions. By generating
samples from the posterior distribution of model parameters, MCMC provides confidence
intervals and probabilistic forecasts. This enhances the reliability and decision-making
capabilities of AI systems in crucial areas like finance, healthcare and autonomous
systems.
• Generative Modelling: MCMC algorithms like Gibbs sampling can be used in
generative models like Variational Autoencoders (VAEs) and Generative Adversarial
Networks (GANs). These models aim to learn the underlying distribution of data and
generate new data samples. MCMC helps sample from the latent space of the model,
leading to the creation of realistic and diverse data for various applications like image
generation, text synthesis and drug discovery

Advantages Of MCMC:

• Handles Complex Distributions: MCMC excels at sampling from intricate probability

distributions, even when direct sampling is impossible or inefficient. This makes it
invaluable for various applications in statistics, machine learning, and scientific
simulations.
• No Analytical Solutions Required: Unlike some methods that require deriving
analytical solutions, MCMC can operate even when such solutions are unavailable. This
provides a flexible and robust approach when dealing with challenging problems.
• Provides Uncertainty Quantification: MCMC enables the generation of samples from
the posterior distribution, allowing for the estimation of uncertainty associated with
parameters or predictions. This is crucial for building reliable and interpretable models in
various AI applications.
• Widely Applicable: MCMC finds use in diverse fields like Bayesian inference, machine
learning, physics, economics, and finance. Its versatility makes it a powerful tool for
tackling problems across various domains.
• Relatively Easy Implementation: Compared to some other advanced statistical
techniques, MCMC algorithms can be relatively straightforward to implement, especially
with readily available software libraries.

Disadvantages Of MCMC:

• Computational Cost: MCMC simulations can be computationally expensive, especially

when dealing with high-dimensional distributions or requiring high accuracy. This can
limit its applicability in situations with limited computational resources.
• Convergence Issues: Ensuring proper convergence of the Markov chain to the target
distribution is crucial. This can be challenging and requires careful monitoring and
diagnostics to avoid obtaining biased results.
• Sensitivity To Starting Point: The initial state of the Markov chain can impact the
convergence process. Choosing an inappropriate starting point can lead to slow
convergence or even getting stuck in irrelevant regions of the distribution.
 • Difficulties In Assessing Convergence: Evaluating the convergence of the Markov
chain can be complex and subjective. Different tests and diagnostics are available but
they might not always provide a definitive answer and require careful interpretation.
• Not Always The Best Option: Depending on the specific problem and available
resources, other methods like gradient-based optimisation might be more efficient or
suitable alternatives to MCMC.

GIBBS SAMPLING
Gibbs sampling is a Markov Chain Monte Carlo (MCMC) method used in machine learning to
generate samples from a joint probability distribution, especially when direct sampling is
difficult. It works by iteratively sampling one variable at a time, given the current values of all
other variables, and repeating this process until a stable distribution of samples is achieved.

Example Imagine you and your friend are sharing a cake, but the size each of you takes
depends on the other person’s slice:

• If your friend takes a big piece, you take a small one.

• If your friend takes a small piece, you take a bigger one.

But you don't decide together. Instead:

1. You guess a slice size for your friend.

2. Based on that, you choose your own slice.
3. Then your friend updates their guess based on your slice.
4. You go back and forth, adjusting your slices.

Over time, this back-and-forth settles into a stable pattern — that’s the balance, or the true
joint distribution of cake slices.

Real Life Gibbs Sampling

Cake slices Variables
Taking turns Sampling conditionals
Adjusting based on the other Sampling one variable at a time
Balanced cake sharing Converged joint distribution

How it Works:
1. Start with an initial value for each variable.
2. Iterate: For each variable:
 o Sample a new value for the variable, given the current values of all other
variables.
o This sampling is done from the conditional distribution of that variable, given the
others.
3. Repeat: steps 2 until a stable distribution of samples is achieved.
4. Burn-in and Thinning: Initial samples are often discarded (burn-in) to ensure they are
representative of the target distribution. Samples are then thinned (every n-th sample is
kept) to reduce autocorrelation.
Why is it Useful?
• Handles Complex Distributions:
Gibbs sampling is particularly useful when dealing with high-dimensional or complex
probability distributions where direct sampling is computationally infeasible.
• Bayesian Inference:
It's a powerful tool for Bayesian inference, allowing us to draw samples from the posterior
distribution of parameters.
• Latent Variable Models:
Gibbs sampling is used in training models with latent variables, like Restricted Boltzmann
Machines (RBMs).

Examples in Machine Learning:

• Restricted Boltzmann Machines (RBMs):
Gibbs sampling is used to train RBMs by iteratively sampling between visible and hidden
layers.
• Bayesian Networks:
Gibbs sampling is well-suited for sampling from the posterior distribution of Bayesian
networks.
• Topic Modeling:
It's used in topic modeling algorithms to infer the underlying topics in a collection of
documents.
GRAPHICAL MODELS – BAYESIAN NETWORKS – MARKOV
RANDOM FIELDS

Graphical models in machine learning use graphs to represent the relationships between variables
and their dependencies, providing a visual and structured way to model complex systems. These
models are broadly categorized into Bayesian networks (directed) and Markov random fields
(undirected). They are useful for tasks like prediction, inference, and decision-making by
capturing probabilistic dependencies and allowing efficient computation.

• Nodes: Represent random variables or hypotheses in the model.

• Edges: Represent relationships between variables, indicating direct influence or
conditional independence.
• Directed vs. Undirected: Directed models (like Bayesian networks) use arrows to
show the direction of influence, while undirected models (like Markov networks) use
lines to indicate pairwise dependencies.

Types of Graphical Models

There are two main types:

a. Bayesian Networks (Directed Graphical Models)

• Use directed edges (arrows).

• Represent causal or sequential relationships.
• Each node is conditionally independent of its non-descendants, given its parents.

Example: Imagine you're modeling the likelihood of someone getting the flu.

Weather → Has Flu → Misses Work

• If it’s cold (Weather), you might get the flu.

• If you have the flu, you’re more likely to miss work.

This network tells us:

• Flu depends on Weather.

• Missing Work depends on Flu.

b. Markov Random Fields (Undirected Graphical Models)

• Use undirected edges.

• Represent mutual dependencies, not necessarily causal.
• Focus on the concept of cliques (fully connected subsets) and Markov properties.
Example:
Variables:

• Fever (F)
• Cough (C)
• Fatigue (T)
• Flu (U)

We’ll assume these variables are connected like this:

F
/ \
U — C
\ /
T
This is an undirected graph, meaning:

• Fever (F) is related to Flu (U)

• Flu (U) is related to Cough (C) and Fatigue (T)
• Cough and Fatigue are also related

Why Use Graphical Models?

• Efficient inference in large systems (e.g., variable elimination, belief propagation).

• Modular representation: easier to design and debug.
• Interpretability: visualize dependencies clearly.
• Combines domain knowledge with data-driven learning.

Applications

• Natural language processing (e.g., parsing, POS tagging).

• Computer vision (e.g., object recognition, segmentation).
• Bioinformatics (e.g., gene expression analysis).
• Robotics (e.g., sensor fusion, localization).

Advantages:

• Intuitive Visualization: Graphical models provide a clear and visual representation of

complex relationships.
• Efficient Inference: They allow for efficient probabilistic inference, making it possible to
compute probabilities of events given observed data.
• Modularity: Complex systems can be built by combining simpler parts, and the graph
structure allows for efficient implementation of algorithms.

HIDDEN MARKOV MODEL

• When working with sequences of data, we often face situations where we can’t directly
see the important factors that influence the datasets.
• Hidden Markov Models (HMM) help solve this problem by predicting these hidden
factors based on the observable data
• It is an statistical model that is used to describe the probabilistic relationship between a
sequence of observations and a sequence of hidden states. It is often used in situations
where the underlying system that generates the observations is unknown or hidden,
hence it has the name “Hidden Markov Model.”
• A Hidden Markov Model (HMM) is a statistical model often used in machine learning,
natural language processing (NLP), speech recognition, and bioinformatics, especially
when dealing with sequential or time-series data.
• The relationship between the hidden states and the observations is modeled using a
probability distribution.
• An HMM consists of two types of variables: hidden states and observations.

1. Hidden Variable (a.k.a. Hidden State)

• This is the real cause or situation you're trying to figure out.

• It’s not directly visible or measurable.
• You can only guess it based on what you observe.

Example:
If you’re trying to guess the weather:

• Weather (Sunny or Rainy) is the hidden variable — you can’t see it directly.

2. Observed Variable (a.k.a. Observation)

• This is what you can see or measure.

• It's influenced or caused by the hidden variable.

Example:
If you see your friend:
 • Carrying an umbrella or not is the observed variable — it's what you actually see

Concept Example

Hidden Variable Weather (Rainy/Sunny)

Observed Variable Umbrella (Yes/No)

The relationship between the hidden states and the observations is modeled using a probability
distribution. The Hidden Markov Model (HMM) is the relationship between the hidden states
and the observations using two sets of probabilities: the transition probabilities and the
emission probabilities.

1. Transition Probabilities

These describe the probability of moving from one hidden state to another.

Example:
Let’s say the hidden states are:

• Sunny
• Rainy

Then:

• P(Rainy tomorrow∣Sunny today)=0.3

• P(Sunny tomorrow∣Sunny today)=0.7

2. Emission Probabilities

These describe the probability of seeing an observation given a hidden state.

Example:
You don’t see the weather, but you see your friend:

• Carrying an umbrella
• Not carrying an umbrella

Then:

• P(Umbrella∣Rainy)=0.9
• P (Umbrella∣Sunny)=0.2

These tell you how likely each observation is, depending on the hidden state.
Hidden Markov Model Algorithm
The Hidden Markov Model (HMM) algorithm can be implemented using the following steps:
• Step 1: Define the state space and observation space: The state space is the set of
all possible hidden states, and the observation space is the set of all possible
observations.
• Step 2: Define the initial state distribution: This is the probability distribution
over the initial state.
• Step 3: Define the state transition probabilities: These are the probabilities of
transitioning from one state to another. This forms the transition matrix, which
describes the probability of moving from one state to another.
• Step 4: Define the observation likelihoods: These are the probabilities of
generating each observation from each state. This forms the emission matrix, which
describes the probability of generating each observation from each state.
• Step 5: Train the model: The parameters of the state transition probabilities and
the observation likelihoods are estimated using the Baum-Welch algorithm, or the
forward-backward algorithm. This is done by iteratively updating the parameters
until convergence.
• Step 6: Decode the most likely sequence of hidden states: Given the observed
data, the Viterbi algorithm is used to compute the most likely sequence of hidden
states. This can be used to predict future observations, classify sequences, or detect
patterns in sequential data.
• Step 7: Evaluate the model: The performance of the HMM can be evaluated using
various metrics, such as accuracy, precision, recall, or F1 score.

ML Applications of HMM

Field How HMM Helps

Speech Recognition Models how phonemes (hidden) produce sounds (observed)
NLP Tags parts of speech (hidden) from words (observed)
Bioinformatics Finds genes in DNA sequences
Finance Predicts market trends from past price movements
Activity Recognition Determines what someone is doing from motion data
FORWARD ALGORITHM

The Forward Algorithm is used to compute the probability of an observed sequence given an
HMM. Instead of checking all possible hidden state sequences (which is computationally
expensive), it efficiently sums over them using dynamic programming.

Example:

You’re a detective.
Each day, someone tells you what they did (like “walk”, “shop”, or “clean”) — but you don’t
know the weather that day (Sunny or Rainy).
You want to figure out:
How likely is it that this person did those things, based on what you know about the
weather?

You Have a Model (HMM)

You know:

• How likely it is to start with Sunny or Rainy

• How likely the weather changes each day (Sunny → Rainy, Rainy → Sunny, etc.)
• What people usually do when it’s Sunny or Rainy (like walking more on Sunny days)

This information is your Hidden Markov Model (HMM).

The Observations

Let’s say you observe:

Day 1: walk
Day 2: shop
Day 3: clean

You want to know:

How likely is it that this sequence (walk, shop, clean) could happen?

But you don’t know the weather on any day. That’s what’s “hidden.”

What’s the Problem?

There are many possible weather combinations:

• Sunny → Sunny → Rainy

• Rainy → Sunny → Sunny
 • … and more

Checking all of them takes too long if the sequence is long.

What Does the Forward Algorithm Do?

It solves this by:

• Starting with Day 1: “If it was Sunny, how likely was 'walk'? If it was Rainy, how likely
was 'walk'?”
• Then moving to Day 2: “If yesterday was Sunny, how likely is today Sunny or Rainy, and
how likely is 'shop'?”
• It builds up the total probability step by step for each day.
• At the end, it adds everything up to find the total chance of the full observation (walk,
shop, clean).

In Short: The Forward Algorithm is a step-by-step way to add up all the possible hidden
weather paths that could explain what you saw, without checking every single path one by
one.

Steps of the Forward Algorithm :

Let:

• N = number of hidden states (like Sunny, Rainy)

• T = number of observations (like walk, shop, clean)
• A[i][j] = probability of moving from state i to state j
• B[j][O_t] = probability of observing O_t in state j
• π[j] = initial probability of starting in state j
• α[t][j] = total probability of being in state j at time t (after observing up to time t)

Step 1: Initialization (t = 1)

For each state j:

α[1][j] = π[j] × B[j][O₁]

(Start in state j and observe the first symbol)

Step 2: Recursion (t = 2 to T)

For each time t and each state j:

α[t][j] = Σ (α[t-1][i] × A[i][j]) × B[j][O_t]

(Sum over all paths to state j, then multiply by chance of observing O_t in state j)

Step 3: Termination

At the final time step T, add up all the final probabilities:

P(O | model) = Σ α[T][j]

(The total probability of the observed sequence)

In Simple Words:

• Start with: "How likely is the first observation in each state?"

• Then, for each day:
o "How likely is it that I got to this state from previous states?"
o "How likely is today’s observation in this state?"
• Finally, add up the results from all final states.

VITERBI ALGORITHM

The Viterbi Algorithm is a dynamic programming algorithm used to find the most probable
sequence of hidden states (called the Viterbi path) in a Hidden Markov Model (HMM), given
a sequence of observations.

The Viterbi Algorithm is used in Hidden Markov Models (HMMs) to solve the decoding
problem, which means:

Given a sequence of observations, what is the most likely sequence of hidden states that
generated it?

Why Do We Need It?

In an HMM, multiple hidden states can produce the same observation. This creates ambiguity
about which state produced the observation. So, the problem becomes:

Given a sequence of observations, which hidden state sequence is the most likely sequence
that generated these observations?

Example of Ambiguity:

Imagine a weather model with two hidden states:

 • Sunny
• Rainy

Now, consider the observation sequence:

• Walk, Walk, Shop

Both Sunny and Rainy could produce similar sequences of observations:

• Sunny could produce "Walk, Walk, Shop" because people tend to walk or shop on sunny
days.
• Rainy could also produce "Walk, Walk, Shop" because people might walk quickly or
shop to avoid the rain.

But the probability of being in Sunny or Rainy at each time step, and the transition
probabilities between states, are different.

So, even though both states can result in similar observations, we need to figure out which state
sequence (Sunny-Rainy or Rainy-Sunny, etc.) is more probable over the entire observation
sequence.

How the Viterbi Algorithm Helps:

• The Viterbi Algorithm helps by finding the most probable sequence of hidden states
(even if some states can produce similar observations) by considering:
o Transition probabilities (probability of moving from one state to another)
o Emission probabilities (probability of an observation occurring given a state)

Thus, it takes into account both the likelihood of observations given states and the likelihood
of state transitions.

What It Does:

• The algorithm efficiently searches for the most probable path (sequence of states)
through a trellis (a time vs. state graph), using dynamic programming.
• It avoids recalculating the same probabilities repeatedly by:
1. Storing the maximum probability of reaching each state at each time.
2. Keeping track of the path that led to that max probability.

Steps of the Viterbi Algorithm

Let’s say:
 • You observe: Walk, Shop, Clean
• The hidden states could be: Sunny and Rainy
• You have some data:
o Probability of starting in each state (Sunny or Rainy)
o Probability of going from one state to another
o Probability of each activity happening in each state

Step 1: Start with the first observation

For each state:

• Multiply:
o The probability of starting in that state
o By the probability of that state producing the first observation

Save that value — it tells us how likely it is to start in that state and see the first observation.

Step 2: Move through the rest of the observations

For each new observation and each state:

• For each possible previous state:

o Multiply:
▪ The probability of being in the previous state
▪ By the probability of moving to the current state
▪ By the probability of the current observation in the current state
• Choose the highest of those possibilities — that’s the best path to the current state at this
time step
• Remember which previous state gave that max value (this is used to trace back the best
path)

Step 3: Finish (last observation)

• Look at the last step and pick the state with the highest probability
• That state is the last step in the best path

Step 4: Trace back the best path

• Use the remembered “best previous states” from each step to trace back and find the full
sequence of states

You now have:

• The most likely sequence of hidden states (like: Sunny → Sunny → Rainy)
• The probability of that sequence
BAUM–WELCH ALGORITHM
The Baum-Welch algorithm, also known as the forward-backward algorithm, is a special case of
the Expectation-Maximization (EM) algorithm used to train Hidden Markov Models (HMMs). It
iteratively refines the HMM parameters by maximizing the likelihood of observed data given the
model. The algorithm alternates between an E-step (expectation) and an M-step (maximization)
to estimate the model's parameters, such as transition and emission probabilities.

Example:
Scenario: Imagine a simple HMM where the weather (Sunny or Rainy) is hidden, and we can
only observe whether someone is carrying an umbrella or not.

Model:
• Hidden States: Sunny (S), Rainy (R)
• Observations: Umbrella (U), No Umbrella (N)
• Initial State Probabilities: π = (π_S, π_R)
• Transition Matrix: A = [[p(S|S), p(R|S)], [p(S|R), p(R|R)]]
• Emission Matrix: B = [[p(U|S), p(N|S)], [p(U|R), p(N|R)]]
Baum-Welch Algorithm Steps:
1. 1. Initialization:
Start with random guesses for π, A, and B.
2. 2. E-Step (Expectation):
• Use the forward and backward algorithms (a part of the forward-backward
algorithm) to calculate the probability of each hidden state sequence given the
observed umbrella/no umbrella sequence.
•Specifically, the forward algorithm computes the probability of observing the data
up to a given time step, given a hidden state at that time. The backward algorithm
calculates the probability of observing the data from a given time step to the end,
given a hidden state at that time.
3. 3. M-Step (Maximization):
• Update the HMM parameters (π, A, and B) based on the calculated probabilities
from the E-step.
• For example, the new initial state probabilities are calculated as the sum of the
forward and backward probabilities at time t=0, normalized by the sum of all
forward-backward probabilities.
4. 4. Iteration:
Repeat the E-step and M-step until the model parameters converge (the changes in
parameter values become negligible).
Example with Data:

Let's say we observe the sequence: Umbrella, No Umbrella, Umbrella.

• E-step:
The forward and backward algorithms would compute the probabilities of different hidden
state sequences (e.g., S, S, S; S, R, S; etc.) given the observation sequence.
• M-step:
Based on these probabilities, the algorithm would estimate the new values for π, A, and B,
for example, it might estimate that the probability of starting in the Sunny state is higher
(π_S).
In essence, the Baum-Welch algorithm learns how to best map the hidden state transitions and
observations to the observed data by iteratively refining the HMM parameters.

COMPARISON OF THE FORWARD, VITERBI, AND BAUM-WELCH ALGORITHMS

IN THE CONTEXT OF HIDDEN MARKOV MODELS:

Aspect Forward Algorithm Viterbi Algorithm Baum-Welch Algorithm

Purpose Compute the Find the most likely Train HMM parameters to
probability of an sequence of hidden maximize the likelihood of the
observation sequence states (decoding) observations
given the model
Stage Evaluation Decoding Learning (Training)
Output Probability of the Most probable hidden Updated transition and emission
observed sequence state sequence probabilities
Method Dynamic Dynamic Expectation-Maximization
programming programming (taking (EM) using Forward-Backward
(summing over paths) max over paths) steps
Dependency Uses only model Uses model Uses both Forward and
parameters and parameters and builds Backward algorithms for
observations on forward-like probability estimates
recursion
Example "What is the "What is the most "Given many sequences like
Use likelihood of seeing likely weather pattern ‘sunny, cloudy, sunny’, what are
the sequence ‘sunny, behind ‘sunny, the most likely
cloudy, sunny’?" cloudy, sunny’?" transition/emission
probabilities?"
TRACKING METHODS

In machine learning and robotics, tracking methods are used to estimate the state of a system
over time, especially when that state is partially observed and noisy. Common applications
include:

• Object tracking in videos

• Navigation systems (e.g., GPS)
• Sensor fusion
• Autonomous vehicles

Two popular tracking techniques are the Kalman Filter and the Particle Filter.

KALMAN FILTER

The Kalman Filter is a mathematical algorithm used to track or estimate the state of
something over time, especially when the data is noisy or uncertain. Works best for linear systems
with Gaussian noise.

How It Works:

The Kalman Filter estimates the current state of a system using a two-step process:

1. Prediction Step:
o Predict the current state from the previous state using a motion model.
o Predict the current uncertainty (covariance) as well.
2. Update Step:
o Get a new observation (measurement).
o Combine prediction and observation using a weighted average, giving more
weight to the more certain information.
o Update the estimate and reduce uncertainty.
Example: Let’s say you're tracking a car using a GPS. The GPS gives noisy data. The Kalman
Filter helps you:

1. Predict where the car should be based on its last known position and speed.
2. Update that guess using the new (noisy) GPS reading.
3. Combine both in a smart way to get a better estimate of the car's actual location.

It repeats this process every time new data comes in.

Goal of Kalman Filter: To predict the next state of a system (like the position of a car), and
then update the prediction using noisy measurements (like GPS data), in the smartest possible
way.

STEP 1:

STEP 2:
STEP 3:

STEP 4:

STEP 5:
 Step What It Does Why It Matters
1. Predict state Guess where the system is going Keeps track of motion or change
2. Predict uncertainty Guess how confident we are Helps know how reliable the guess is
3. Kalman Gain Balance between prediction and data Chooses what to trust more
4. Update state Correct the guess with real data Improves accuracy
5. Update uncertainty Recalculate confidence after update Gets more certain over time (ideally)

Pros:

• Computationally efficient (only uses matrix operations).

• Works well for Gaussian, linear problems.

Cons:

• Not suitable for non-linear systems or non-Gaussian noise.

PARTICLE FILTER

• A Particle Filter is a probabilistic algorithm used to estimate the state of a system over
time by representing it with a set of many random samples (called particles) and
updating them based on new data.
• Each particle is like a possible guess of the true state, and the algorithm uses a weighting
and resampling process to keep the best guesses and discard the bad ones.
• The Particle Filter is a method that uses lots of random guesses (called particles) to
figure out where the robot might be — and then keeps the best guesses. Designed for
non-linear and non-Gaussian systems.

Example: You're tracking where a robot is in a room. But you don’t know exactly where it is —
you only have a noisy sensor (like a blurry camera or weak GPS).

You want to figure out:

“Where is the robot right now?”

How it works:

1. Initialization – Start with 1000 random guesses of where the robot might be (particles).
2. Prediction – Move each guess based on the robot’s movement (e.g., it moved forward).
3. Update (Weighting) – Check how well each guess matches the new sensor reading.
o If it matches well, it gets a high weight.
o If not, low weight.
4. Resample – Keep only the best guesses (high weights) and throw away the bad ones.
o Make new guesses based on the best ones.
Repeat this every time the robot moves and sends a new sensor reading.

Term What it means in particle filter

Particle A possible guess of the true state
Weight Confidence in that guess (based on sensor)
Resampling Keeping better guesses, dropping bad ones
Iteration Repeat for every new observation

Pros:

• Works well with complex, non-linear systems.

• Can approximate any distribution.

Cons:

• Computationally expensive.
• Requires many particles for accurate estimates.

KALMAN FILTER VS PARTICLE FILTER

Feature Kalman Filter Particle Filter
Basic idea One smart prediction + Many random guesses weighted
correction and updated
Model assumption Linear motion and Gaussian Can handle non-linear motion and
noise any noise
State representation A single mean and uncertainty A set of particles (many possible
(matrix) states)
Noise handling Assumes noise is normal (bell Handles any type of noise
curve)
Accuracy Very accurate for simple systems Very accurate for complex and
noisy systems
Computation Fast, efficient Slower, needs more processing
(many particles)
Flexibility Low (works best when High (can work in messy, real-
assumptions are true) world problems)
Memory use Low (just matrices) High (stores lots of particles)
Resilience to non- Poor Excellent
linearity
Example use GPS + speed tracking in cars, Robot navigation, visual tracking
radar in video