MACHINE LEARNING (BITE401L)

Module-1: INTRODUCTION

Dr. B. K. Tripathy
Professor, Higher Academic Grade
School of Computer Science Engineering and Information Systems
VIT, Vellore-632014, Tamil Nadu, India
 BOOKS RECOMMENDED

Text Books:
1. Ethem Alpaydin: Introduction to Machine Learning, Fourth
Edition, MIT press, 2020
2. Shai Shalev Shwartz and Shai Ben David: Understanding
Machine Learning from Theory to Algorithms, Cambridge
University Press, 2015
Reference Books:
3. Tom M. Mitchell: Machine Learning, Indian Edition, McGraw
Hill Education, 2017
4. Oliver Theobald: Machine Learning for Absolute beginners,
Second Edition, copyright by the author, 2017
 SYLLABUS: MODULE-1

• Types of Learning
• Supervised Learning
• Unsupervised Learning
• Semi-supervised Learning
• Reinforcement Learning
• A Formal Model- PAC Learning
 THE HIERARCHY OF TOPICS
• g
It encompasses everything related to the
Computer Science:
design and use of computers

It comprises of methods and systems to extract

Data Science: knowledge and insights from data through the
use of computers

Artificial Encompasses the ability of machines to

Intelligence: perform intelligent and cognitive act or
process of knowing) tasks: Sub-fields are ML,
Knowledge representation, NLP, Perception,
Search and planning
Machine A field that gives computers the ability to
learning: learn without being explicitly programmed
 WHAT IS LEARNING ? - FROM A HUMAN
PERSPECTIVE
 Learning is the ability to improve one’s behaviour with
experience
 With better learning, tasks can be performed more efficiently

Human Learning happens in the following ways :

• Either somebody who is an expert in the subject directly
teaches us
• We build our own notion indirectly based on what we have
learnt from the expert in the past
• We do it ourselves, may be after multiple attempts, some being
unsuccessful
 DEFINITIONS OF LEARNING

• Learning denotes changes in a system that ... enable a system

to do the same task … more efficiently the next time.
-Herbert Alexander Simon
• Learning is constructing or modifying representations of
what is being experienced
- Ryszard Stanisław Michalski
• Learning is making useful changes in our minds
- Marvin Lee Minsky
• IN MACHINE LEARNING IT IS SAID “WHAT TO DO”
BUT NOT TOLD “HOW TO DO” IT HAS TO FIND ITS
OWN MECHANISM
 WHAT IS MACHINE LEARNING?

• Arthur, Samuel (1959-03-03). "Some Studies in Machine

Learning Using the Game of Checkers". IBM Journal 3 (3):
pp.210–229. (Introduction)
• It is a field of study that gives computers the ability
to learn without being explicitly programmed
• A key feature is the concept of self-learning
• Arthur Samuel is responsible for influencing early
Arthur Samuel
research in using transistors for computers at IBM (1901-1990)
• At IBM he made the first checkers program
on IBM's first commercial computer, the IBM 701 in 1952
 WHAT IS MACHINE LEARNING? CONTD…
• Since the days when computers were built, we have
developed several algorithms
• Digital technology has become the main source to store,
process and transform information
• For some works there are no algorithms; like recognizing a
person from its photo, moving effortlessly in a crowded
environment, play chess or drive a car etc.
• In Machine Learning we try to learn such type of things
• We start with a very general model with many parameters.
This general model is supposed to do all sorts of tasks
depending upon how the values of the parameters are set
 WHAT IS MACHINE LEARNING? CONTD…

• Learning corresponds to adjust the values of the parameters

such that the model matches with the data it sees during
training

• Based on the training data the general model through a

particular setting of its parameters becomes specialised to the
particular task that underlies the data

• That version of the model we get after training, that particular

instantiation of the general template becomes the algorithm
for the task
 WHAT IS MACHINE LEARNING? CONTD…

• Today we have many problems for which we lack algorithms

but have data
• We store many of our day to day activities digitally
• Buy a product, visit a web page, write a blog, message
through social media, online questionnaires, book tickets etc.
• We are not producers but also consumers of data
• We want products and services specialized for us
• Machines do their tasks much faster with a higher level of
precision compared to humans
 WHAT IS MACHINE LEARNING? CONTD…

• The fundamental difference between humans and machines

in performing their work is intelligence
• The human brain receives data gathered by the five senses:
vision, hearing, smell, taste, and tactility (the capability of
being felt or touched)
• These gathered data are sent to the human brain via the
neural system for perception and taking action
• Because machines have been originally created to help
humans in their daily lives, it is necessary for the machines to
think, understand to solve problems, and take suitable
decisions akin to humans
 WHAT IS MACHINE LEARNING? CONTD…

• The question of whether a machine can think was first asked

by the British mathematician Alan Turing in 1955, which was
the start of the artificial intelligence history.
• He was the one who proposed a test to measure the
performance of a machine in terms of intelligence.
• Machine Learning is a natural outgrowth of the intersection
of Computer Science and Statistics
• Machine Learning (ML) is a field of artificial intelligence (AI)
that enables software to make decisions and predict
outcomes without requiring explicit coding or programming
 WHAT IS MACHINE LEARNING? CONTD…

• In the world of computer languages, every output by a

computer used to be preceded by an input from the user
• However, with Machine Learning, computer programs can
learn from data and make predictions without being
specifically told how to do so
• The goal of learning is to construct a model that takes the
input and produces the desired result (From a general
model).
• A measure of performance (besides performance of metrics
of speed and memory usage) of a machine learning algorithm
will be the accuracy of results
 BASIC REQUIREMENTS OF ML

• Classical statistics (discipline concerned with the collection,

summary, and analysis of data) is at the heart of machine
learning and many of these algorithms are based on the same
statistical equations we studied in high school.
• Indeed, statistical algorithms were conducted on paper
(started in the 18th century) well before machines over took
on the title of artificial intelligence.
• Computer programming is another indispensable part of
machine learning
• Programming skills are vital to manage data and design
statistical models that run on machines
 WHAT IS ARTIFICIAL INTELLIGENCE?
• What Is Artificial Intelligence ?
• AI is the broad field of computer science that focuses on
creating machines and software that can perform tasks that
require human intelligence.

• It has branches like

• Machine Learning
• Data Learning,
• Robotics
• Natural Language Processing (NLP) and
• Computer Vision
 DIFFERENCE BETWEEN ARTIFICIAL
INTELLIGENCE AND MACHINE LEARNING
• AI encompasses the broader goal of creating intelligent
systems, while
• ML is a specific technique within AI that allows machines to
learn and improve their performance through data-driven
approaches
 DO MACHINES REALLY LEARN?

• A machine can be considered to learn if it is able to gather

experience by doing a certain task and improve its
performance in doing the similar tasks in the future

• When we talk about past experience, it means past data

related to the task.

• This data is an input to the machine from some source

 HOW DO MACHINES LEARN?

• The basic machine learning process can be divided into

three parts
• Data input: Past data or information is utilized as a basis
for future decision-making
• Abstraction: The input data is represented in a
summarized way
• Generalization: The abstracted representation is
generalized to form a framework for making decisions
 MACHINE LEARNING DEFINITION
- T. M. MITCHELL

• A computer program is said to learn from

• experience ‘E’ with respect to
• some class of tasks ‘T’ and
• performance measure ‘P’,
• if its performance at tasks in ‘T’, as measured by ‘P’, improves
with experience E.’
• Experience ‘E’ can also be called as past data,
• The task ‘T’ can be a prediction, classification of data, and
• the measure of ‘P’ can be increase of accuracy in prediction
 USE OF MACHINE LEARNING AND MACHINE
LEARNING MODEL
• What Is the use of Machine Learning?
• ML focuses on enabling computers to access data and learn
patterns to make predictions. ML occurs in everyday use
through email filtering, social media algorithms, voice
recognition, healthcare diagnostics, and plenty of other day-
to-day technology perks.
• What Is a Machine Learning Model?
• A machine learning model is an algorithm trained to pick up
patterns from data to make predictions or decisions based
on that knowledge (a pattern refers to a recognizable
structure or relationship within data)
 HUMAN LEARNING [Link] LEARNING

• As human takes decision based on experience, computers

can make model based on the extracted patterns in the
input data and arrive decision
• The aim of the Machine Learning is to learn a model from
the given data automatically so that it can predict the
unknown data correctly
• The learnt model is equivalent to the human experience
Experience Decisions HUMAN LEARNING
Humans

Database Model
Learning programs MACHINE LEARNING
TRADITIONAL PROGRAMMING vs MACHINE
LEARNING
MACHINE LEARNING ALGORITHMS AND STEPS

• What are Machine Learning Algorithms?

• ML algorithm is enabled through a set of mathematical and
statistical procedures. A ML model learns patterns and makes
predictions from data. ML algorithms are vital in extracting
meaningful information and knowledge from the data
• Step 1: The algorithm takes data that consists of features and
their corresponding labels
• Step 2: The algorithm uses this data to identify underlying
patterns and relationships within the dataset
• Step 3: The derived knowledge in the form of a dataset is used
to make predictions or decisions on new, unseen data
 TRAINING DATASETS

• Datasets are tables of organized data. The rows represent

individual data samples and instances, whereas the columns
represent features or attributes of recurring samples

• Labelled data is a type of data used in supervised learning

tasks where each data sample is associated with a known
output label

• The training dataset trains the machine learning model

• This includes labelled examples and input features that have
a corresponding target
 TESTING DATASETS

• The testing dataset is used to evaluate the performance of

the trained model

• The model evaluates itself based on the testing data

• The model assesses its ability to generalize unseen data and

estimate its performance in real-world scenarios
 TYPES OF MACHINE LEARNING
Four main types of machine learning:
 Supervised learning
 Unsupervised learning
 Semi-supervised learning, and
 Reinforcement learning
 SUPERVISED MACHINE LEARNING

• In supervised machine learning, algorithms are trained using

labelled datasets, where both input and corresponding
output parameters are provided
• The machine learns from these labelled examples and
predicts outputs for new, unseen data based on the patterns
learned during training
• In supervised learning, the target is to infer a function or
mapping from training data that is labeled. (Ex. Interpolation)
• The training data consist of input vector X and output vector Y
of labels or tags.
 SUPERVISED MACHINE LEARNING CONTD…

• A label or tag from vector Y is the explanation of its

respective input example from input vector X
• Together they form a training example
• In other words, training data comprises of training examples
• The output vector Y consists of labels for each training
example present in the training data
• These labels for output vector are provided by the supervisor
• Often, these supervisors are humans, but machines can also
be used for such labeling
 WHY IT IS CALLED SUPERVISED LEARNING?

• Human judgments are more expensive than machines, but

the higher error rates in data labeled by machines suggest
superiority of human judgment
• The manually labeled data is a precious and reliable resource
for supervised learning
• However, in some cases, machines can be used for reliable
labeling
• In supervised learning, the aim is to learn mapping from the
input to an output whose correct values are provided by a
supervisor
 SUPERVISED LEARNING- TRAINING PHASE

• During training an input vector generates a actual output vector

• This actual output vector is compared with the desired output
vector

• If there is a difference between the two vectors, then an error

signal is generated by the network
• This error signal is used for adjustment of parameters until the
output matched the desired output
• It is assumed that correct target output values are known for each
input pattern
SUPERVISED MODEL ARCHITECTURE
SUPERVISED LEARNING- WORK FLOW
DIAGRAM
 AN EXAMPLE

• Suppose we want to predict the market value of a used car

• A supervised algorithm can formulate predictions by analyzing
the relationship between car attributes (year of make, car
brand, mileage etc.) and the selling price of other cars sold
based on historical data
• Given that the supervised algorithm knows the final price of
other cars sold, it can then work backward to determine the
relationship between the characteristics of the car and the value
• After the machine deciphers the rules and patterns of the data,
it creates what is known as a model (An algorithmic equation for
producing an outcome with new data based on the rules
derived from the training data)
 EXAMPLE CONTD…

• Once the model is prepared, it can be applied to new data

and tested for accuracy
• After the model has passed both the training and test data
stages, it is ready to be applied and used in the real world

X
Attribute 1: Year of Y
make
Model Car Price
Attribute 2: Car Brand

Attribute 3: Mileage
 UNSUPERVISED LEARNING

• In unsupervised learning there are no supervisors and we

have only input data
• The aim is to find the regularities in the input
• There is a structure to the input space such that certain
patterns occur more often than others
• We want to see what generally happens and what does not
happen
• Unsupervised machine learning aims to uncover underlying
patterns or groupings in data that haven’t been labelled
• Unsupervised learning is distinguished by the fact that either
the source or destination is unknown.
EXAMPLE OF UNSUPERVISED LEARNING

Interpr- Algorit- Proces-

etation hms sing

Unsupervised Model
Input Data Outputs
Unlabeled
HOW DOES UNSUPERVISED LEARNING WORK?

• Unsupervised machine learning analyzes and clusters

unlabeled input datasets using machine learning algorithms
to identify patterns and relationships
• These hidden patterns are found without any human
intervention
• The data is not labeled with any predefined categories or
outcomes, so the algorithm must find these patterns and
relationships on its own
• This can be a challenging task, but it can also be very
rewarding, as it can reveal insights into the data that would
not be apparent from a labeled dataset
UNSUPERVISED LEARNING- ARCHITECTURE
 UNSUPERVISED LEARNING- TRAINING PHASE

• The input vectors of similar type are grouped without the use of
training data to specify how a member of each group looks or to
which group a member belongs
• In the training process the network receives the input patterns
and organizes these patterns into clusters

(Input) X The Model Y (Actual Output)

• If for a pattern no class could be found then a new class is

formulated
• When a new pattern arrives the ANN gives an output response
indicating the class to which the pattern belongs
 SUPERVISED VS UNSUPERVISED LEARNING
Parameter of Supervised Learning (SL) Unsupervised Learning (UL)
Comparison
Types There are two sorts of issues Clustering and association
that can be solved with SL. i.e. are two sorts of issues that
classification and regression may be solved using UL
Output- Input Output is calculated according Output is independently
Relation to the fed framework, and calculated, and input is
input is analyzed. analyzed only.
Accuracy Very accurate. It can be inaccurate
sometimes.
Time Off-line and input framework Real-time in nature.
analysis takes place.
Analysis The analysis and The analysis ratio is higher
computational complexity but computational
level is high. complexity is lower.
 SEMI-SUPERVISED LEARNING

• Semi-supervised learning is a method of machine learning in

which a small quantity of labeled data is combined with a set of
unlabeled data during training
• It is a type of learning that exists between unsupervised
learning and supervised learning
• Semi-supervised machine learning algorithms are trained on
data that consists of a mixture of labelled and unlabeled
samples.
• Semi-supervised learning is beneficial when obtaining labelled
data is expensive or time-consuming
• Semi-supervised learning bridges the gap between supervised
and unsupervised learning by leveraging both labeled and
unlabeled data
 REINFORCEMENT LEARNING

• It is the most advanced algorithm category under machine

learning (Till 2010)
• Unlike supervised and un-supervised learning, reinforcement
learning continuously improved its model by leveraging
feedback from previous iterations
• Reinforcement learning is a type of learning where an agent
interacts with an environment and receives feedback or
rewards for its actions
• It is very similar, where algorithms are set to train the model
through continuous learning
• A standard reinforcement learning model has measurable
performance criteria where outputs are not tagged, but
graded
SEMI-SUPEVISED LEARNING- ARCHITECTURE
 DIAGRAMATIC REPRESENTATION OF
SUPERVISED AND SEMI-SUPERVISED LEARNING
 REINFORCEMENT LEARNING

• Example: Video game

• As a player progresses through the virtual space of a game, it
learns the value of various actions under different conditions
and becomes more familiar with the field of play
• The learned values inform and influence a payer’s subsequent
behaviour and its performance immediately improves based on
their learning and past experience
• Example: Pac-Man
• One starts with a set of environment states (challenges,
obstacles or pathways), say S
• There may exist a wall to the left, a ghost to the right and a
power pill above- each one representing a different state
 PAC MAN DESCRIPTION

• iconic yellow circle with a mouth—is simply called Pac-Man.

• He’s the star of the game and the piece you control to gobble up dots,
fruits, and occasionally ghosts
• Here’s a breakdown of the key “pieces” in the game:
• Pac-Man: The player-controlled character who eats dots and avoids ghosts.
• Ghosts: The enemies—Blinky (red), Pinky (pink), Inky (cyan), and Clyde
(orange)—each with unique behavior patterns
• Pac-Dots: The small dots scattered throughout the maze that Pac-Man eats
to clear the level.
• Power Pellets: The larger flashing dots that temporarily let Pac-Man eat
the ghosts
• Fruits & Bonus Items: Appear for extra points—cherries, strawberries,
apples, and even bells and keys
 POINT SYSTEM

• Points are collected by eating various items and defeating

enemies as you navigate the maze. Here's how the scoring
works in the classic version
• Basic Point System
• Pac-Dots: 10 points each
• Power Pellets: 50 points each
• Ghosts (after eating a Power Pellet):
• 1st Ghost: 200 points
• 2nd Ghost: 400 points
• 3rd Ghost: 800 points
• 4th Ghost: 1600 points
 REINFORCEMENT LEARNING

• The set of possible actions to respond to these states is

referred to as ‘A’
• Here A = { move left, move right, move up, move down}
• The symbol Q, which is the starting value and initialized to 0
• As Pac-Man explores the space inside the game, two main
things may happen
 Q drops as negative things occur after a given state/action
 Q increases as positive thins occur after a given state/action
• The machine learns to match the action for a given state that
generates or maintains the highest level of Q
 REINFORCEMENT LEARNING

• It learns initially through the process of random movements

(actions) under different conditions (States)
• The machine records the results (rewards/ penalties) and
how the Q level is affected by those values to inform and
optimize its future action
• The idea of interacting with our environment is probably the
first to occur to us when we think about the nature of learning
• Examples:
• When an infant plays, waves arms or looks about , it has no
explicit teacher, but it does have a direct sensorimotor
connection to its environment
 REINFORCEMENT LEARNING- ARCHITECTURE

• A cow calf struggles to its feet minutes after being born. Half
an hour later it is running at 20 miles per hour
• A master chess player makes a move. The choice is informed
both by planning, anticipating possible replies and counter-
replies and by immediate, initiative judgments of the
desirability of particular positions and moves

X
Neural Network W Y (Actual Output)
Input

R (Reinforcement)
Error signal generator
signal
REINFORCEMENT LEARNING- ARCHITECTURE
 SUPERVISED VS REINFORCEMENT LEARNING
Parameters of Supervised Learning Reinforcement Learning
Comparison
Definition/ It is a type of machine learning It is a type of machine learning
Learning policy where the model is trained on a where an agent learns to make
labeled dataset. Each input data decisions by interacting with an
point is paired with the correct environment. The agent receives
output, and the model learns to rewards or penalties based on the
map inputs to outputs based on actions it takes and learns to
these examples. maximize the cumulative reward
over time
Goal The main goal is to learn a function The main goal is to learn a policy
that can accurately predict the that dictates the best action to take
output for new, unseen data in a given state to maximize long-
term rewards
Algorithms Data: Requires a large amount of Data: Does not require labeled
applied/ Process labeled data. data but instead relies on the
agent's interactions with the
environment.
 SUPERVISED VS REINFORCEMENT LEARNING
Parameters of Supervised Learning Reinforcement Learning
Comparison
Algorithms Training: The model is trained Training: The agent learns through
applied/ by minimizing the error trial and error, receiving rewards or
Process between the predicted output penalties, and updates its policy
and the actual labeled output based on these experiences.
using techniques like gradient
descent.
Example Commonly used for Commonly used in robotics, game
Applications: classification (e.g., spam playing (e.g., AlphaGo), and
detection, image recognition) autonomous systems (e.g., self-
and regression (e.g., driving cars).
predicting house prices)
Feedback: The feedback is immediate, as the The feedback is delayed, as the
model can compare its rewards or penalties can occur well
predictions to the known correct after the actions are taken, making it a
outputs more complex learning process.
 REPRESENTATION OF MODELS IN SUPERVISED
LEARNING
• In supervised learning, models can be represented in various
ways, depending on the type of problem being solved and the
algorithm used.
• Here are some common representations of models:
• Linear Models-- Linear Regression, Logistic Regression
• Decision Trees
• Support Vector Machines (SVM)
• Neural Networks
• Ensemble Methods--Random Forest, Gradient Boosting
• K-Nearest Neighbors (KNN)
 REPRESENTATION OF MODELS IN
UNSUPERVISED LEARNING
• In unsupervised learning, models are designed to identify
patterns or structures within unlabeled data.
• Here are some common representations of models in
unsupervised learning:
• Clustering Models-- K-Means Clustering, Hierarchical
Clustering, DBSCAN (Density-Based Spatial Clustering of
Applications with Noise)
• Dimensionality Reduction Models--Principal Component
Analysis (PCA), t-Distributed Stochastic Neighbor Embedding
(t-SNE)
• Association Rule Learning-- Apriori Algorithm, Eclat Algorithm
 REPRESENTATION OF MODELS IN
UNSUPERVISED LEARNING
• Anomaly Detection Models—An anomaly is something that
deviates from what’s normal, expected, or standard
• Examples: Isolation Forest, Auto encoders)
• Generative Models--Gaussian Mixture Models (GMM),
Generative Adversarial Networks (GANs)
 REPRESENTATION OF MODELS IN
REINFORCEMENT LEARNING
• In reinforcement learning (RL), models are represented by
agents that interact with an environment to learn optimal
behaviors through trial and error.
• Here's an overview of common representations in RL:
• Markov Decision Processes (MDP)
• Value-Based Methods
• Deep Q-Networks (DQN)
• Policy-Based Methods
• Actor-Critic Methods
• Model-Based Methods
• Multi-Agent Reinforcement Learning (MARL)
UNSUPERVISED VS REINFORCEMENT LEARNING

Parameters of Unsupervised Learning Reinforcement Learning

Comparison
Definition/ Unsupervised learning is a Reinforcement learning is a type of
Learning policy type of machine learning machine learning where an agent
where the model is trained learns to make decisions by
on unlabeled data. The goal interacting with an environment.
is to find hidden patterns or The agent receives rewards or
intrinsic structures in the penalties based on the actions it
input data. takes and learns to maximize the
cumulative reward over time.
Goal The main goal is to uncover The main goal is to learn a policy
the underlying structure of that dictates the best action to take
the data, such as clustering in a given state to maximize long-
similar data points together term rewards.
or reducing the
dimensionality of the data.
 UNSUPERVISED VS REINFORCEMENT LEARNING
Parameters Unsupervised Learning Reinforcement Learning
of
Comparison
Algorithms Data: Uses unlabeled data, which Data: Does not require labeled data
applied/ means the input data does not have but instead relies on the agent's
Process corresponding output labels. interactions with the environment.
Training: The model identifies Training: The agent learns through
patterns and relationships within trial and error, receiving rewards or
the data without any predefined penalties, and updates its policy
labels or categories. based on these experiences.
Example Commonly used for clustering (e.g., Commonly used in robotics, game
Applications: customer segmentation), playing (e.g., AlphaGo), and
dimensionality reduction (e.g., autonomous systems (e.g., self-
principal component analysis), and driving cars)
anomaly detection (e.g., fraud
detection)
Feedback: There is no explicit feedback The feedback is delayed, as the
provided, as the model is not guided rewards or penalties can occur well
by labeled outputs. after the actions are taken, making it
a more complex learning process.
 SEMI-SUPERVISED VS REINFORCEMENT
LEARNING
Parameters of Semi-Supervised Learning Reinforcement
Comparison Learning
Uses a small amount of labeled data An algorithm with
Definition
bolstering a larger set of unlabeled data a reward system
To counter the disadvantages of To learn a series of
Aim
supervised and unsupervised learning. action
Interaction of
Doesn’t interact Interacts
the agent
Trajectory
Practical Speech analysis, internet content
optimization, motion
application classification
planning
It doesn’t have
Labels It has labels.
labels.
A FEW CHARACTERISTICS OF REINFORCEMENT
LEARNING
• From the examples we have the following observations about
characteristics of Reinforcement Learning
• All of these involve interaction between an active decision-
making agent and its environment
• Within the environment the agent seeks to achieve a goal
despite uncertainty about its environment
• The agent’s actions are permitted to affect the future state of
the environment
• Correct choice requires taking into account indirect, delayed
consequences of actions and it requires foresight and
planning
 HISTORY OF PROBABILITY
• Probability as a scientific theory started in the 17th century
• Two mathematicians, B. Pascal(1623-62) [French
mathematician, physicist, inventor,
philosopher, and Catholic writer]
• In 1642, he started some pioneering work on calculating
machines (called Pascal's calculators and later Pascalines),
establishing him as one of the first two inventors of
the mechanical calculator.
• The other one being P. Fermat (1601-65) [made notable
contributions to analytic geometry, probability, and
optics]
 HISTORY OF PROBABILITY

• Collaborated for sharing the stack in an incomplete gambling

match played by a French gambler (Chevalier De Mere)
• Both these mathematicians gave thought to the gambler
friend in a series of letters which echoed the theory of
probability for the first time
• The first book on probability was written by Dutch scientist C.
Hugens (1629-95) in 1654 dealing with some interesting
problems on the subjects
• Next J. Bernoulli (1654-1705) studied probability for 20 years
 HISTORY OF PROBABILITY
• He defined probability in his book “Arts Conjectundi’, which
was published posthumously by his nephew in 1713. He is the
inventor of ‘Bernoullian trials’
• De Moivre (1667-1754) solved some fresh problems in his
book ‘Doctrine of chances’ published in the year 1718
• The theory of inverse probability is due to T. Bayes (1702-
1761)
• In 1940, John Von Neumann applied the probability theory to
the Economic and Sociological problems
 PROBABILITY DISTRIBUTIONS
• A probability distribution is a mathematical function that
describes the probability of different possible values of a
variable. Probability distributions are often depicted using
graphs or probability tables
• There are two types of probability distributions
• 1. Discrete distributions
• 2. Continuous distributions
• Suppose X is a random variable taking values and the
respective probabilities given by . Then we write their in the
probability distribution form as
 PROBABILITY DISTRIBUTIONS

• Here X is called a discrete random variable

• The probability is a function P: P(U)[0, 1]
• (i)
• (ii)
• Example: Let us consider the tossing a coin
• The random variable X takes two values H or T with
probability ½ for each value. So, the distribution is

X H T
P 1/2 1/2
 EXAMPLE

• Let us consider the tossing of a die. The variable takes 6 values

1, 2, 3, 4, 5 and 6 with probability of 1/6 for each of the
values. So, the probability distribution is:
X 1 2 3 4 5 6
P 1/6 1/6 1/6 1/6 1/6 1/6

• Note: The probability values of the variable values need not

be same as these are in the above two examples
 PROBABILITY COMPUTATION

• An event is any subset of a sample space. The sample space

is the set of all possible outcomes in a random experiment
• For example in the experiment of tossing a coin, . The events
can be {H}, {T}, {H, T}

• The experiments can be of two types

 Deterministic experiment
 Probabilistic (Uncertain) experiment

 In probability theory we are not interested in deterministic

experiments
 PROBABILITY COMPUTATION CONTD…

 Example of deterministic experiments:

 Boyle’s Law (P. V = Constant)
 Charles's Law (V/T = Constant)
• Suppose X is a random event on a sample space U
• A sample space is the set of all possible outcomes in a
random experiment
• A random event is any subset of U
• Then , where n(X) is the number of elements favourable to X.
 PROBABILITY COMPUTATION CONTD…

• Example: Suppose we are considering the tossing of a die

Then
• U = {1, 2, 3, 4, 5, 6}
• X = getting an even number
• Then X =.
• P(X) =
• Suppose Y = The event of getting a number greater than 2. Y =
{3, 4, 5, 6}
• Then
 PROBABILITY COMPUTATION CONTD…

• Suppose we are tossing a pair of dice

• Then U = {(1,1), (1,2), (1,3)……..(6,6)} , |U| = 36
• X be the event that sum of the numbers on the dice is 9
• Then X = {(4, 5), (5,4), (3, 6), (6, 3)}

• So,
• If Y is the event of getting a sum of 7 the
• Y = {(1, 6), (6,1), (2, 5), (5,2), (4,3), (3,4)}
• So,
 PAC LEARNING- A FORMAL MODEL

• In computational learning theory, probably approximately

correct (PAC) learning is a framework for mathematical
analysis of machine learning
• It was proposed in 1984 by Leslie Valiant (1949- )
• He is the 2010 ACM Turing award winner
• Originator of the concept of Bulk Synchronous Parallel (BSP)
• This concept is analogous to the Von Neumann model for a
single computer architecture, BSP has been an influential
model for parallel and distributed computing architectures
 PAC LEARNING- A FORMAL MODEL

• Valliant's 2013 book is Probably Approximately Correct:

Nature's Algorithms for Learning and Prospering in a
Complex World
• Currently the T. Jefferson Coolidge Professor of Computer
Science and Applied Mathematics at Harvard University
• Valiant is world-renowned for his work in Theoretical
Computer Science.
• Among his many contributions to Complexity Theory, he
introduced the notion of #P-completeness ("Sharp-P
completeness")
 PAC LEARNING- A FORMAL MODEL

• Several high-performance parallel programming models are

derived from BSP
• Popular examples are Hadoop, Spark, Giraph, Hama, Beam
and Dask
• Google adopted it for computation at large scale
via MapReduce
• In it he argues, among other things, that evolutionary biology
does not explain the rate at which evolution occurs
 LESLIE VALIANT

• Writing, for example, "The evidence for Darwin's general

schema for evolution being essentially correct is convincing
to the great majority of biologists”
• This author has been to enough natural history museums to
be convinced himself
• All this, however, does not mean the current theory of
evolution is adequately explanatory
• At present the theory of evolution can offer no account of
the rate at which evolution progresses to develop complex
mechanisms or to maintain them in changing environments
 WHAT IS PAC LEARNING?

• It is a theoretical framework introduced by Leslie Valiant in

1984.
• It addresses the problem of learning a function from a set of
samples in a way that is both probably correct and
approximately correct.
• In simpler terms, PAC learning formalizes the conditions
under which a learning algorithm can be expected to
perform well on new, unseen data after being trained on a
finite set of examples
• PAC learning is concerned with the feasibility of learning in a
probabilistic sense.
 WHAT IS PAC LEARNING?

• It asks whether there exists an algorithm that, given enough

examples, will find a hypothesis that is approximately correct
with high probability
• The "probably" aspect refers to the confidence level of the
algorithm, while the "approximately correct" aspect refers to
the accuracy of the hypothesis
 IMPORTANCE OF PAC LEARNING

• PAC learning is important because it provides a rigorous

foundation for understanding the behavior and performance
of learning algorithms.
• It helps determine the conditions under which a learning
algorithm can generalize well from a limited number of
samples, offering insights into the trade-offs between
accuracy, confidence, and sample size
 IMPORTANCE OF PAC LEARNING

• The PAC framework is widely applicable and serves as a

basis for analyzing and designing many machine
learning algorithms
• It offers theoretical guarantees that are crucial for
assessing the reliability and robustness of these
algorithms
• By understanding PAC learning, researchers and
practitioners can develop more efficient and effective
models that are capable of making accurate predictions
on new data
 PAC LEARNING- BASICS

• In this framework, the learner receives samples and must

select a generalization function (called the hypothesis) from a
certain class of possible functions
• The goal is that, with high probability (the "probably" part),
the selected function will have low generalization error (the
"approximately correct" part)
• The learner must be able to learn the concept given any
arbitrary approximation ratio, probability of success,
or distribution of the samples
approximation ratio = our solution :actual solution
 PAC LEARNING- BASICS

• The goal is to obtain an approximation ratio as close to 1 as

possible
• If the problem involves a minimization, the approximation
ratio will be greater than 1
• If it involves a maximization, the approximation ratio will be
less than 1
• An important innovation of the PAC framework is the
introduction of computational complexity theory concepts
to machine learning
 PAC LEARNING- BASICS

• In particular, the learner is expected to find efficient

functions (time and space requirements bounded to
a polynomial of the example size)
• and
• The learner itself must implement an efficient procedure
(requiring an example count bounded to a polynomial of the
concept size, modified by the approximation
and likelihood bounds)
• In PAC learning, error tolerance refers to the ability of
an algorithm to learn when the examples received have been
corrupted in some way
 ERROR TOLERANCE (PAC LEARNING)

• In fact, this is a very common and important issue since in

many applications it is not possible to access noise-free data
• Noise can interfere with the learning process at different
levels
• The algorithm may receive data that have been occasionally
mislabeled, or
• The inputs may have some false information, or the
classification of the examples may have been maliciously
adulterated
 PAC LEARNNG THEORY

• PAC learning defines a mathematical relationship between

the number of training samples, the error rate, and the
probability that the available training data are large enough
to attain the desired error rate
• Usually, we calculate various metrics to estimate its
performance
• One of these metrics is the error rate
• The estimates differ from the actual value due to their
statistical nature
• So, we may ask how many training samples we need to be
confident about our estimates
 PAC LEARNNG THEORY

• The PAC theory is an answer to that

• It’s about finding the relationship between the true error
rate and the number of training samples
• The PAC theory is concerned with the confidence with which
we can say that our estimate is correct
 CORE CONCEPTS OF PAC LEARNING
(SAMPLE COMPLEXITY)

• Sample complexity refers to the number of samples required for a learning

algorithm to achieve a specified level of accuracy and confidence
• In PAC learning, sample complexity is a key measure of the efficiency of a
learning algorithm
• It helps determine how much data is needed to ensure that the learned
hypothesis will be generalized well to unseen instances
• The sample complexity depends on several factors, including the desired
accuracy, confidence level, and the complexity of the hypothesis space
• A higher desired accuracy or confidence level typically requires more
samples
• Similarly, a more complex hypothesis space may require more samples to
ensure that the learned hypothesis is approximately correct
 CORE CONCEPTS OF PAC LEARNING
(HYPOTHESIS SPACE)

• The hypothesis space is the set of all possible hypotheses (or

models) that a learning algorithm can choose from
• In PAC learning, the size and structure of the hypothesis space
play a crucial role in determining the sample complexity and
the generalization ability of the algorithm
• A larger and more complex hypothesis space offers more
flexibility and can potentially lead to more accurate models
• However, it also increases the risk of overfitting, where the
learned hypothesis performs well on the training data but
poorly on new, unseen data
• The challenge in PAC learning is to balance the flexibility of
the hypothesis space with the need to generalize well
 CORE CONCEPTS OF PAC LEARNING
(GENERALIZATION)

• Generalization is the ability of a learning algorithm to

perform well on unseen data.
• In the PAC framework, generalization is quantified by the
probability that the chosen hypothesis will have an error
rate within an acceptable range on new samples.
• Generalization is a fundamental goal of machine learning, as
it determines the practical usefulness of the learned
hypothesis.
• A model that generalizes well can make accurate predictions
on new data, which is essential for real-world applications.
• The PAC framework provides theoretical guarantees on the
generalization ability of learning algorithms, helping to ensure
that the learned hypothesis will perform well on new data
 SOME PREREQUISITES

• Let’s say we have a set D of samples with size m, where

are the features and are the labels
• Then, we have a hypothesis space H, which contains the class
of all possible hypotheses (e.g., linear classifiers) that we’d
like to use to find the mapping between the features and the
labels
• Additionally, the target concept c is the true underlying
function from which we’ve drawn the training samples. In
other words, for any , we have
• The hypotheses that fit the data with zero error are called
consistent with the training data
• We call the set of hypotheses that are consistent with training
data the version space
 HYPOTHESIS IN MACHINE LEARNING

• In the realm of machine learning, a hypothesis serves as an

initial assumption made by ML professionals when
attempting to address a problem
• Machine learning involves conducting experiments based on
past experiences, and these hypotheses are crucial in
formulating potential solutions
• A hypothesis in machine learning is the model’s presumption
regarding the connection between the input features and
the result.
• It is an illustration of the mapping function that the algorithm
is attempting to discover using the training set
 HYPOTHESIS IN MACHINE LEARNING
• To minimize the discrepancy between the expected and actual
outputs (Error), the learning process involves modifying the
weights that parameterize the hypothesis
• The objective is to optimize the model’s parameters to achieve
the best predictive performance on new, unseen data, and a
cost function is used to assess the hypothesis’ accuracy
• In most supervised machine learning algorithms, our main goal
is to find a possible hypothesis from the hypothesis space that
could map out the inputs to the proper outputs
• Hypothesis space is the set of all the possible legal hypothesis
• This is the set from which the machine learning algorithm
would determine the best possible (only one) which would
best describe the target function or the outputs
 HYPOTHESIS IN MACHINE LEARNING

• A hypothesis is a function that best describes the target in

supervised machine learning
• The hypothesis that an algorithm would come up depends
upon the data and also depends upon the restrictions and
bias that we have imposed on the data

• 𝑦 = 𝑚𝑥+c
• The Hypothesis can be calculated as:

• y = range
• m = slope of the lines
• x = domain
• c = intercept
SOME DISTRIBUTION OF DATA
 TEST DATA
• g
 DIVISION OF THE COORDINATES
• g
OUTCOME FROM TEST DATA
ALTERNATE DIVISIONS OF THE COORDINATE
SPACE
 HYPOTHESIS SPACE AND HYPOTHESIS

• The way in which the coordinate would be divided depends

on the data, algorithm and constraints
• All these legal possible ways in which we can divide the
coordinate plane to predict the outcome of the test data
composes of the Hypothesis Space
• Each individual possible way is known as the hypothesis
 PAC LEARNING THEOREM

• It provides formal guarantees about the performance of

learning algorithms
• It states that for a given accuracy (ε) and confidence (δ), there
exists a sample size (m) such that any learning algorithm that
returns a hypothesis consistent with the training samples will,
with probability at least 1-δ, have an error rate less than ε on
unseen data
• Mathematically,
• Here,
• m is the number of samples, ϵ(epsilon) is the error tolerance
• δ (delta) is the confidence level,
• VC(H) is the Vapnik-Chervonenkis dimension of the hypothesis
class H.
 EXPLANATION OF VC(H)

• The VC dimension is a measure of the capacity or complexity of the

hypothesis space
• It quantifies the maximum number of points that can be shattered
(i.e., correctly classified in all possible ways) by the hypotheses in
the space
• A higher VC dimension indicates a more complex hypothesis space,
which may require more samples to ensure good generalization
• The PAC learning theorem provides a powerful tool for analyzing
and designing learning algorithms.
• It helps determine the sample size needed to achieve a desired
level of accuracy and confidence, guiding the development of
efficient and effective models
 SAMPLE COMPLEXITY

• A learning algorithm is considered PAC-learnable if, with

high probability (at least 1−δ), it outputs a hypothesis whose
approximation error is within ϵ of the true concept.
• The guarantee is that the algorithm's performance improves
as the sample size increases.

• The sample complexity formula is a central expression in

PAC learning is given by

Here is the cardinality of the hypothesis space

 COMPUTATION OF SAMPLE COMPLEXITY : EXAMPLE

• Suppose you are given with

• Hypothesis class: A finite hypothesis class H with |H| = 1000
• Error tolerance : (5% error tolerance)
• Confidence level : (99% confidence)
• Find the number of samples required (m) required to
guarantee that the true error of the learned hypothesis is
within with confidence at least
 SOLUTION

• We have the PAC formula

•
• Step 1: Compute . Here, .
So, ln(|H|) = ln=
• =
• = 2.302585093 = 6.9077
• Step 2: Compute . Here . So,
 SOLUTION

• Step 3: Compute m
• Using PAC formula,
• So,
• = 230.258
• As m must be an integer, we have m = 231
 COMPUTATION OF TOTAL NUMBER OF HYPOTHESIS : AN EXAMPLE

• Problem set up:

• Suppose there are two input variables and one output
variable Y
• Further, suppose

• and Y is an binary output variable {0, 1}

• The task is to learn hypothesis h that maps to Y.
• The input space X consists of all possible combinations of
values , i.e. it has 6 pairs of values
 COMPUTATION OF TOTAL NUMBER OF
HYPOTHESIS : AN EXAMPLE
• Hypothesis class:
• Since h maps each input pair( 𝑋 1 , 𝑋 2 ) to a value of Y
independently, the total number of hypothesis is
• The 64 hypotheses maps all possible mappings from the input
space to the output space.