Reinforcement Learning (RL)
Reinforcement Learning (RL) is a type of machine learning where an agent learns to
make decisions by interacting with an environment.
The agent receives feedback in the form of rewards or penalties based on the actions
it takes.
The goal of the agent is to maximize cumulative reward over time by learning the
best actions through trial and error.
Key Components of Reinforcement Learning
1. Agent
o The learner or decision-maker that interacts with the environment.
2. Environment
o The external system the agent interacts with. It provides feedback based on the
agent's actions.
3. State
o A representation of the current situation of the environment. The agent
perceives the environment through states.
4. Action
o The set of all possible moves the agent can make in the environment.
5. Reward
o Feedback from the environment based on the agent's actions. Positive rewards
incentivize desirable actions, while negative rewards (penalties) discourage
undesirable actions.
6. Policy
o A strategy used by the agent to determine the next action based on the current
state. It can be deterministic (fixed actions) or stochastic (probabilistic
choices).
7. Value Function
o A function that estimates the expected cumulative reward of states or state-
action pairs, helping the agent make decisions that maximize long-term rewards.
The Learning Process
1. Exploration
o The agent tries different actions to discover their effects and gather information
about the environment.
2. Exploitation
o The agent uses its knowledge to choose actions that it believes will maximize
the reward.
3. Balance
o Effective RL requires balancing exploration and exploitation to ensure the
agent learns the optimal policy.
Algorithms in Reinforcement Learning
1. Q-Learning
o A model-free algorithm where the agent learns a value function Q(s,a), which
represents the expected utility of taking action a in state s and following the
optimal policy thereafter.
2. SARSA (State-Action-Reward-State-Action)
o Similar to Q-Learning, but updates the Q-value based on the action actually
taken, considering the policy followed by the agent.
Getting Lost Example: Reinforcement Learning in a Maze
To understand how an RL agent learns to navigate an environment, let’s consider a robot
trying to escape a maze.
Scenario: Robot Navigating a Maze
1. Environment:
o The maze is a grid-based structure with walls, open paths, and an exit.
o The robot starts at a random position and must reach the exit.
2. State:
o The robot's current position in the maze, represented as coordinates (x,y)(x,
y)(x,y).
3. Actions:
o The robot can move up, down, left, or right.
4. Rewards:
o +10 points for reaching the exit.
o -1 point for every move to encourage efficiency.
o -5 points for hitting a wall (to discourage unnecessary moves).
Applications of Reinforcement Learning
Reinforcement learning enables intelligent systems to improve through experience. Some key
applications include:
1. Game Playing
o RL agents have achieved superhuman performance in games like Chess, Go,
and video games (e.g., AlphaGo, OpenAI Five).
2. Robotics
o Training robots for complex tasks like walking, grasping objects, and
navigating environments.
3. Autonomous Vehicles
o Teaching self-driving cars to navigate safely in various traffic conditions.
4. Healthcare
o Optimizing treatment strategies, personalized medicine, and managing
clinical trials.
5. Finance
o Used in algorithmic trading, portfolio management, and risk assessment to
make smarter financial decisions.
Sampling
Sampling is a technique used to select a subset of data from a larger population. It allows for
analysis and inference without examining the entire dataset.
1. Probability Sampling
Every member of the population has a known, non-zero chance of being selected.
Examples:
Simple Random Sampling: Every member has an equal chance of selection.
Systematic Sampling: Selects every k-th member after a random start.
Stratified Sampling: Divides the population into groups (strata) and samples
proportionally.
Cluster Sampling: Divides the population into clusters and randomly selects entire
clusters.
2. Non-Probability Sampling
Not every member has a known or equal chance of selection.
Examples:
Convenience Sampling: Based on ease of access.
Judgmental (Purposive) Sampling: Selected based on researcher’s judgment.
Quota Sampling: Ensures representation by meeting specific quotas.
Snowball Sampling: Current subjects recruit future subjects from their
acquaintances.
Markov Chain Monte Carlo (MCMC) Methods
MCMC methods are a class of algorithms used to sample from complex probability
distributions, especially when direct sampling is difficult. These methods are commonly used
in Bayesian statistics, computational physics, and high-dimensional integrals.
Key Concepts of MCMC Methods
1. Markov Chain
o A sequence of random variables where the next state depends only on the
current state (Markov property).
o Over time, the chain converges to a stationary distribution.
2. Monte Carlo
o A technique that uses random sampling to estimate numerical results.
o In MCMC, Monte Carlo methods generate samples from the probability
distribution.
Proposal Distribution in MCMC
A proposal distribution is a fundamental component in Markov Chain Monte Carlo (MCMC)
methods. It is used to generate new candidate samples from a target probability
distribution, especially when direct sampling is not feasible.
Denoted as q(x′∣x), where x′ is the proposed new state given the current state x.
The proposed state x' is accepted or rejected based on a criterion that ensures the
sequence of samples converges to the target distribution π(x).
Common MCMC Algorithms
1. Metropolis-Hastings Algorithm
Description:
o Proposes new states and accepts or rejects them based on the acceptance ratio.
o Widely used due to its simplicity and flexibility.
Process:
1. Start at an initial state x₀.
2. Generate a candidate state x′ from the proposal distribution q(x′∣x).
3. Compute the acceptance probability:
4. Accept x' with probability α, otherwise, remain at x.
Use Case:
o General-purpose algorithm, works for various probability distributions.
2. Gibbs Sampling
Description:
o Instead of proposing an entire new state, samples each variable one at a time,
conditional on the other variables.
o Efficient when conditional distributions are easy to sample from.
Process:
1. Initialize all variables.
2. Sample each variable xi from its conditional distribution:
3. Repeat until convergence.
Use Case:
o Effective for Bayesian networks and hierarchical models.
o Used in statistical inference and latent variable models.
How MCMC Works
1. Initialization
o Start with an initial state (or set of states) from the target distribution.
2. Iteration
o Propose a new state using a proposal distribution.
o Accept or reject the new state based on a criterion (e.g., Metropolis-Hastings
algorithm).
3. Convergence
o After many iterations, the distribution of the states will approximate the
target distribution.
Applications of MCMC
1. Bayesian Inference
o Estimating posterior distributions of parameters when the likelihood and
prior are known.
o Useful for hierarchical models and complex data structures.
2. Statistical Physics
o Simulating the behavior of physical systems at the atomic or molecular level.
o Estimating properties like magnetization or phase transitions.
3. Machine Learning
o Training models with complex likelihood functions.
o Used in Bayesian neural networks and other probabilistic models.
4. Ecology and Evolutionary Biology
o Estimating parameters of population dynamics models.
o Studying the evolution of traits under different selection pressures.
Markov Random Fields (MRFs) / Markov Networks
Markov Random Fields (MRFs) are probabilistic graphical models that represent
dependencies among a set of random variables using an undirected graph.
Useful when dependencies are symmetrical or the exact direction of influence is unclear.
Unlike Bayesian Networks, MRFs use undirected edges to capture relationships.
Components of Markov Random Fields
1. Nodes (Vertices)
o Represent random variables in the model.
o Can represent observed data or hidden variables.
2. Edges (Links)
o Undirected edges indicate direct dependencies between variables.
o Capture bidirectional (symmetric) relationships.
3. Clique Potentials (Factors)
o Potential functions (ψ) define local dependencies within cliques (fully
connected subgraphs).
o Help determine the joint probability distribution over the graph.
Applications of MRFs
Image Processing → Image segmentation, denoising, and restoration.
Natural Language Processing → Part-of-speech tagging, named entity recognition.
Computer Vision → Object recognition, scene labeling.
Bioinformatics → Modeling spatial dependencies in protein structures.
Hidden Markov Models (HMMs)
A Hidden Markov Model (HMM) is a statistical model that describes the probabilistic
relationship between a sequence of observations and a sequence of hidden states.
Used when the underlying system generating the observations is unknown (hidden).
Helps predict future observations or classify sequences based on the hidden process.
Components of HMM
1. Hidden States
o The underlying variables that generate observations.
o Not directly observable but inferred from observations.
2. Observations
o The measurable variables affected by hidden states.
3. Transition Probabilities (A)
o The probability of moving from one hidden state to another.
o Forms a transition matrix.
4. Emission Probabilities (B)
o The probability of observing a certain output given a hidden state.
o Forms an emission matrix.
5. Initial State Distribution (π)
o The probabilities of starting in each hidden state.
HMM Algorithm Steps
Step 1: Define State Space & Observation Space
State Space → Set of all possible hidden states.
Observation Space → Set of all possible observations.
Step 2: Define Initial State Distribution (π)
Assign probabilities to starting in each hidden state.
Step 3: Define Transition Probabilities (A)
Construct transition matrix, which represents probabilities of state changes.
Step 4: Define Emission Probabilities (B)
Construct emission matrix, which represents probabilities of observations given
states.
Step 5: Train the Model
Use Baum-Welch or Forward-Backward Algorithm to estimate parameters
iteratively.
Step 6: Decode the Most Likely Sequence of Hidden States
Use Viterbi Algorithm to find the most probable sequence of hidden states.
Useful for prediction, classification, and pattern detection.
Step 7: Evaluate the Model
Use accuracy, precision, recall, and F1-score for performance evaluation.
Applications of HMMs
Speech Recognition → Recognizing phonemes in audio signals.
Natural Language Processing (NLP) → Part-of-speech tagging, named entity
recognition.
Bioinformatics → DNA sequence analysis, gene prediction.
Financial Modeling → Predicting stock market trends.
Activity Recognition → Tracking human motion in sensor-based applications.
Tracking Methods in Machine Learning
Tracking methods, commonly used in object tracking, help locate and follow an object's
position over time in a sequence of frames or images.
Used in computer vision, robotics, surveillance, and augmented reality.
1. Kalman Filter
The Kalman filter is an optimal estimator for linear systems with Gaussian noise. It
recursively processes noisy measurements to estimate the system’s state accurately.
Components
1. State Vector (xₜ): Represents the system's state at time t.
2. State Transition Model (A): Defines how the state evolves over time.
3. Measurement Model (H): Links the state to observations.
4. Covariance Matrices (Q, R): Represent uncertainty.
o Q : Process noise covariance.
o R : Measurement noise covariance.
Kalman Filter Algorithm:
Applications of Kalman Filter
Navigation Systems: GPS, Inertial Navigation Systems.
Robotics & Control Systems: Aerospace, autonomous vehicles.
Economics & Finance: Estimating trends & cycles.
2. Particle Filter (Sequential Monte Carlo - SMC)
The Particle Filter is used for non-linear and non-Gaussian systems.
It represents the posterior distribution using random samples (particles) with weights.
Components
1. Particles: A set of random samples representing possible states.
2. Weights: Importance weights indicating the likelihood of each particle given
observations.
Particle Filter Algorithm:
Step 1: Initialization
Generate an initial set of particles from the prior distribution.
Initialize weights.
Step 2: Prediction
Propagate particles using the state transition model.
Step 3: Update
Update weights based on measurement likelihood.
Normalize weights.
Step 4: Resampling
Resample particles based on weights to prevent degeneracy.
Applications of Particle Filter
Robotics: Localization & Mapping (SLAM).
Computer Vision: Object tracking in videos.
Finance: Stochastic volatility models.
Comparison: Kalman Filter vs. Particle Filter
Feature Kalman Filter Particle Filter
Assumptions Linear dynamics, Gaussian noise Non-linear, Non-Gaussian
Computational Cost Efficient More intensive
Accuracy Optimal for linear models Handles complex systems
Applications Navigation, Robotics, Finance SLAM, Object Tracking, Finance