MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

UNIT 4
1. Describe about Probability Learning an Approximately Correct Hypothesis in
detail.
A. Definition: "Probability Learning an Approximately Correct Hypothesis" refers to a
specific learning model called the Probably Approximately Correct (PAC) learning
model. This model provides a framework for understanding how machine learning
algorithms work, the number of training examples required, and the computational
resources needed to learn different classes of target functions. The PAC learning model is
primarily concerned with learning boolean-valued concepts from noise-free training data,
but it can be extended to real-valued target functions and noisy data scenarios.

Problem Setting:

• In the PAC learning model, you have a set of all possible instances (X) over
which target functions can be defined. For instance, this could represent all people
described by attributes like age and height.
• You have a set of target concepts (C) that you want to learn. Each concept
corresponds to a subset of instances and is represented as a boolean-valued
function.
• Training examples are generated by drawing instances at random from a
probability distribution (D) that represents how instances are generated.

Learning Process:
• You use a learner (L) to learn a hypothesis (h) from a set of possible hypotheses
(H). The hypothesis is the learner's estimate of the target concept.
• The learner observes a sequence of training examples and must output a
hypothesis h that approximates the target concept.
• The learner's performance is evaluated based on how well the hypothesis h
generalizes to new instances drawn from the same probability distribution D.

Error of a Hypothesis:
• The true error (errorv) of a hypothesis h is the probability that h will misclassify
an instance drawn at random according to D. This is the true measure of how well
h approximates the actual target concept.

PAC Learnability:
• A class of target concepts (C) is considered PAC-learnable if, for any target
concept in C, any instance distribution D, any desired error rate (ε), and any
allowable probability of failure (δ), the learner L will, with probability at least (1 -
δ), output a hypothesis h such that errorv(h) ≤ ε.

1
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

• PAC-learnability sets a high standard for the learner, demanding that it produce
approximately correct hypotheses with high probability and do so efficiently in
terms of computation.

Complexity Analysis:
• To show that a class C is PAC-learnable, you typically demonstrate that each
target concept in C can be learned from a polynomial number of training
examples, and that the computational effort per example is also polynomially
bounded.
• The PAC model provides insights into the complexity of learning problems and
how generalization accuracy improves with more training examples.
Lifting Assumptions:
• The standard PAC definition assumes that the learner's hypothesis space H
contains a hypothesis with arbitrarily small error for every target concept in C,
which may be a restrictive assumption.
• The model can be extended to scenarios where the learner makes no prior
assumptions about the target concept's form.

In summary, the PAC learning model addresses the problem of learning concepts and
hypotheses accurately from limited training data, providing a rigorous framework for
evaluating the quality of learned hypotheses. It combines considerations of sample size,
learner performance, and computational efficiency.

2. Describe about Error of a Hypothesis and PAC Learnability in detail.

A.
Error of a Hypothesis:

The "error of a hypothesis" (errorv) is a fundamental concept in machine learning,

particularly in the context of Probably Approximately Correct (PAC) learning. It measures
how well a hypothesis approximates the actual target concept in the presence of uncertainty.
The error of a hypothesis is defined as the probability that the hypothesis will misclassify
an instance drawn randomly from a given probability distribution (D).

Here's a more detailed explanation of the error of a hypothesis:

Probability Distribution (D): In the context of machine learning, D represents the

probability distribution over the set of all possible instances (X). It describes how instances
are generated or sampled. For instance, D could be a distribution that describes how
people's attributes (e.g., age, height) vary in the population.
Hypothesis (h): A hypothesis is the learner's approximation of the target concept. It's a rule
or function that assigns a binary classification (e.g., 0 or 1) to instances. Hypotheses are
used to make predictions about the classification of new, unseen instances.

2
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

True Error (errorv(h)): The true error of a hypothesis h, denoted as errorv(h), measures
the probability that h will misclassify an instance drawn randomly according to D. In other
words, it quantifies the chance that h will make a classification error when applied to new,
randomly sampled instances.

Mathematically, errorv(h) can be defined as follows:

errorv(h) = Pr[x ∼ D](h(x) ≠ c(x))

Pr[x ∼ D] represents the probability that an instance x is drawn randomly from the
distribution D.
h(x) is the classification assigned by the hypothesis h to the instance x.
c(x) is the true classification (or label) of instance x based on the target concept.
The goal of a learning algorithm is to find a hypothesis h with a low true error, which means
it approximates the target concept accurately.

PAC Learnability:

PAC Learning Model: Probably Approximately Correct (PAC) learning is a theoretical

framework for studying machine learning algorithms. It addresses the question of how well
a learner can approximate a target concept from a finite set of training examples.

PAC Learnability: A class of target concepts (C) is considered PAC-learnable if, for any
target concept in C, any instance distribution D, any desired error rate (ε), and any
allowable probability of failure (δ), the learner can, with high probability (1 - δ), output a
hypothesis h such that the true error (errorv(h)) is less than or equal to ε.

In other words, PAC-learnability sets a high standard for machine learning algorithms,
demanding that they satisfy two key conditions:

High Probability Guarantee: The algorithm should, with high confidence (1 - δ), produce
a hypothesis with true error (errorv) close to the desired error rate (ε).

Efficiency: The algorithm should perform this learning process efficiently, with a
computational complexity that is polynomial in various parameters like ε, δ, the instance
space size, and the complexity of the concept class.
PAC learnability is used to analyze and characterize the effectiveness of machine learning
algorithms in various learning scenarios. It provides a formal framework for assessing how
well a learner can generalize from training data to unseen instances. The concept of PAC
learnability helps us understand the trade-offs between the number of training examples,
the accuracy of hypotheses, and computational resources in the learning process.

3
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

3. Describe about Sample Complexity for Finite Hypothesis Spaces and Agnostic
Learning and Inconsistent Hypotheses.
A.
Sample Complexity for Finite Hypothesis Spaces:
Sample complexity in the context of machine learning refers to the number of training
examples required for a learner to reliably learn a target concept or hypothesis.

A key result in the study of sample complexity is derived from Equation (7.2), which
provides a general bound on the sample complexity for a wide range of learners,
particularly consistent learners.
In Equation (7.2), the sample complexity (number of training examples, denoted as "m")
is estimated as a function of the acceptable error rate (E), the acceptable probability of
failure (δ), the size of the hypothesis space (|H|), and the natural logarithm (ln). This
equation tells us how many training examples are needed for a consistent learner to ensure,
with probability (1 - δ), that every hypothesis in its hypothesis space, having zero training
error, will have a true error of at most E.

Agnostic Learning and Inconsistent Hypotheses:

Agnostic learning is a learning scenario where the learner does not make any prior
assumptions about whether the target concept is representable within the hypothesis space
(H). In agnostic learning, the goal is to find the best hypothesis within H based on the
available training data, even if none of the hypotheses in H can perfectly fit the target
concept.
In such cases, a learner aims to minimize training error, and this learner is often called an
"agnostic learner." When we use agnostic learning, Equation (7.2) can be generalized to
consider the minimum training error among hypotheses in H rather than insisting on a zero
training error.

The extension of Equation (7.2) provides a way to estimate the sample complexity needed
for the agnostic learner to ensure that the best hypothesis it finds, which may have non-
zero training error, has an acceptable true error with high probability. This number of
4
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

training examples grows with the square of the desired error threshold (E) and depends
logarithmically on the size of the hypothesis space (H) and the acceptable probability of
failure (δ).
"inconsistent hypotheses" refer to those hypotheses within the hypothesis space (H) that
do not perfectly fit or "match" the provided training data.
In the context of agnostic learning, where the learner doesn't assume that the target concept
can be perfectly represented within the hypothesis space, the learner considers hypotheses
that may have nonzero training error. These hypotheses are termed "inconsistent" because
they misclassify some of the training examples, reflecting the imperfections in modeling
the target concept.
The key idea here is to find the hypothesis within H that minimizes the training error (the
fraction of training examples misclassified) while acknowledging that perfect consistency
with the training data may not be achievable due to the limitations of the hypothesis space.

4. Describe about Agnostic Learning and Inconsistent Hypotheses with respect to

Sample Complexity for Finite Hypothesis Spaces.
A. Same as Q3

5. Describe about PAC - Learnable for Conjunctions of Boolean Literals.

A.
Conjunctions of boolean literals are PAC-learnable. PAC-learnability, which stands for
"Probably Approximately Correct" learnability, is a framework for machine learning that
deals with the number of training examples required to learn a target concept with a
specified level of confidence. Specifically, PAC-learnability focuses on the trade-off
between the number of training examples, the acceptable error rate, and the desired
confidence level.

In the case of conjunctions of boolean literals, this class of target concepts consists of
logical combinations of boolean variables and their negations. For instance, a target
concept could be "Old AND -Tall," which is a conjunction of the boolean variables "Old"
and "-Tall."

To determine if this class of target concepts is PAC-learnable, we can use Equation (7.2) to
calculate the sample complexity. The sample complexity tells us the number of random
training examples required to ensure that any consistent learner will, with a specified
probability, learn a hypothesis with a maximum error rate no greater than 'E.'

5
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

The key factor in calculating the sample complexity is the size of the hypothesis space (H),
which represents the set of all possible hypotheses that the learner can consider. For
conjunctions of boolean literals, the size of H is 3^n, where 'n' is the number of boolean
variables involved in the conjunction. This is because there are three possibilities for each
variable in any hypothesis: include the variable as a literal, include its negation as a literal,
or ignore it. With 'n' variables, there are 3^n distinct hypotheses.

Substituting the size of H into Equation (7.2), we can calculate the sample complexity for
this concept class. This sample complexity is polynomial in 'n' (the number of literals), '1/ε'
(the desired confidence level), and '1/δ' (the probability of failure), and it is independent of
the size of the concept (c).

In practical terms, this means that conjunctions of boolean literals can be learned efficiently
with a polynomial number of training examples. One specific algorithm that can be used
for this purpose is the FIND-S algorithm, which is known for its efficiency and
effectiveness in learning these kinds of target concepts.

In summary, PAC-learnability ensures that conjunctions of boolean literals can be learned

from data with high confidence by using a reasonable number of training examples, and
the FIND-S algorithm is a suitable choice for this learning task.

6. Describe about PAC -learnability of boolean conjunctions.

A.
PAC-learnability, which stands for "Probably Approximately Correct" learnability, is a
framework for machine learning that focuses on the trade-off between the number of
training examples, the acceptable error rate, and the desired confidence level. Specifically,
it deals with the question of how many training examples are needed to learn a target
concept accurately with a specified level of confidence. In this context, let's explore the
PAC-learnability of boolean conjunctions.

Boolean conjunctions are logical combinations of boolean literals, which can include
boolean variables and their negations. For instance, a boolean conjunction could be "Old
AND -Tall," indicating that an instance (a person, in this example) is classified as positive
if they are old and not tall.

To determine whether boolean conjunctions are PAC-learnable, we can use Equation (7.2)
to compute the sample complexity. Sample complexity refers to the number of random
training examples required to ensure that any consistent learner, with a specified level of
confidence, will learn a hypothesis with an acceptable error rate.

6
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

The key factor in calculating the sample complexity is the size of the hypothesis space (H).
In the case of boolean conjunctions, the hypothesis space H is determined by the number
of boolean variables involved in the conjunction. Specifically, H has a size of 3^n, where
'n' is the number of boolean variables in the conjunction. This is because there are three
possibilities for each variable in any hypothesis: include the variable as a literal, include its
negation as a literal, or ignore it. With 'n' variables, there are 3^n distinct hypotheses in H.

By plugging the size of H into Equation (7.2), we can compute the sample complexity. The
result is a polynomial function of 'n' (the number of literals in the boolean conjunction),
'1/ε' (the desired confidence level), and '1/δ' (the probability of failure). Notably, the sample
complexity does not depend on the size of the concept (c), which makes it computationally
feasible.

This means that boolean conjunctions are PAC-learnable, and it is possible to learn them
efficiently with a reasonable number of training examples while achieving a high level of
confidence in the learned hypotheses. Furthermore, the FIND-S algorithm is one of the
suitable algorithms to accomplish this task.

7. Describe about PAC - learnability of Unbaised Learners and K-term DNF and K-
CNF concepts
A.
PAC-learnability of Unbiased Learners:
Unbiased learners are those learners that don't make any prior assumptions about the nature
of the target concept. Instead, they consider all possible concepts that can be defined within
the given set of instances. This means they need to use a hypothesis space (H) that is as
broad as the set of all possible target concepts (C), essentially the power set of the set of
instances (X). The power set contains all possible subsets of X, which results in an
extremely large number of concepts.
For example, if there are 'n' boolean features defining instances in X, there are 2^n possible
instances. Therefore, there are 2^(2^n) distinct concepts that could be considered. These
concepts can be very complex and numerous because there are so many possible
combinations.

Using the sample complexity formula (Equation 7.2), we can compute the number of
training examples required to learn such an unbiased class of target concepts under the PAC
model. When we plug in the size of the hypothesis space (|H| = 2^(2^n)), we find that the
sample complexity grows exponentially with 'n'. In simpler terms, the number of training
7
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

examples needed increases very quickly as the number of boolean features in the instances
(n) grows.

This demonstrates that the unbiased concept class, despite its large representational
capacity, is not PAC-learnable within polynomial bounds due to its exponential sample
complexity.

PAC-learnability of K-term DNF and K-CNF Concepts:

The concept classes of k-term DNF (Disjunctive Normal Form) and k-CNF (Conjunctive
Normal Form) expressions involve logical combinations of boolean attributes using "OR"
and "AND" operators. While k-term DNF expressions are limited to k terms, k-CNF
expressions involve k sub-expressions. Equivalently, k-term DNF expressions can be seen
as a special case of k-CNF expressions.

K-term DNF expressions: The sample complexity of k-term DNF expressions, as

determined by Equation (7.2), is polynomial in various factors such as 1/ε (the inverse of
acceptable error), 1/δ (the confidence level), the number of attributes (n), and the number
of terms (k). However, despite having polynomial sample complexity, learning these
expressions has computational complexity that is not polynomial. In fact, it's
computationally hard and not solvable in polynomial time unless certain complexity theory
conjectures are resolved (i.e., unless RP = NP).

K-CNF expressions: The concept class of k-CNF expressions, which is more expressive
and general than k-term DNF expressions, is interestingly PAC-learnable. Despite being
more expressive, k-CNF expressions have both polynomial sample complexity and
polynomial computational complexity per example, making them efficiently learnable.

This contrast shows that while k-term DNF expressions are not efficiently PAC-learnable
due to their computational complexity, there exists a larger concept class, k-CNF
expressions, that is both efficiently learnable and more expressive. The PAC-learnability
of k-CNF, despite its expressiveness, highlights the intriguing nature of computational
learning theory.

8. Describe about PAC - learnability of K-term DNF and K-CNF concepts and
Unbaised Learners
A. Same as Q7

9. Describe about Sample Complexity for Infinite Hypothesis Space.

A.
Sample complexity for infinite hypothesis spaces is an essential concept in machine
learning. It deals with how many training examples are needed to learn a target concept
when the hypothesis space (the set of possible hypotheses or models) is infinite, and we

8
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

want to achieve a certain level of confidence and accuracy. In other words, it quantifies the
amount of data required for learning in cases where there are countless possible hypotheses.

Infinite Hypothesis Spaces: The material mentions scenarios where the hypothesis space
is effectively infinite. This situation can arise in machine learning, particularly when
working with complex models like neural networks that have numerous parameters. In
such cases, the traditional methods for estimating sample complexity, which rely on finite
hypothesis spaces, are not directly applicable.

VC-Dimension: To address the challenge of infinite hypothesis spaces, the concept of VC-
dimension is introduced. It is a measure of the expressive power of the hypothesis space
and can help in estimating sample complexity even when dealing with infinite hypotheses.
The material demonstrates the use of VC-dimension to bound the sample complexity in
these scenarios.

Sample Complexity Bounds: The material likely provides insights into how VC-
dimension-based estimates help in determining the number of training examples (sample
complexity) required to learn effectively in the presence of infinite hypothesis spaces. It
might explain how the VC-dimension can be used as a more realistic and practical measure
for sample complexity in such settings.

Trade-off between Complexity and Data: It's essential to understand the trade-off
between the complexity of the model (often related to the VC-dimension) and the amount
of training data needed. The material may discuss how models with higher VC-dimension
(more complex) require more data to achieve accurate learning, highlighting the
importance of finding the right balance.

10. Describe about the Vapnik-chervonenkis Dimension and VC dimension for neural
networks.
A.
Vapnik-chervonenkis Dimension:

The Vapnik-Chervonenkis (VC) Dimension is a concept in machine learning and statistics

that measures the capacity or expressive power of a hypothesis space, which is a set of
possible models or classifiers. Named after Vladimir Vapnik and Alexey Chervonenkis,
this dimension quantifies the ability of a hypothesis space to represent different patterns or
dichotomies in a dataset.

The VC dimension is defined for a specific hypothesis space H over an instance space X.
The VC dimension, denoted as VC(H), is the size of the largest finite subset of X that can
be shattered by H. An instance space is "shattered" if the hypothesis space can realize every
possible way of dividing or classifying the instances in that subset. In other words, it
measures how well the hypothesis space can fit or capture diverse patterns in the data.

9
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

If there is no finite subset of X that can be shattered by H, the VC dimension is considered

infinite (VC(H) = ∞). The VC dimension is a useful concept for understanding the
complexity and flexibility of a hypothesis space. A higher VC dimension implies a more
expressive hypothesis space that can potentially represent a larger variety of patterns.

The definition also provides a bound on the VC dimension: for any finite hypothesis space
H, VC(H) is less than or equal to the logarithm base 2 of the cardinality of H (VC(H) ≤
log2|H|). This bound ensures that the VC dimension does not grow too rapidly with the size
of the hypothesis space.

The concept is illustrated through examples in the given context, such as the VC dimension
for intervals on the real number line, linear decision surfaces in the plane, and conjunctions
of boolean literals. These examples demonstrate how to determine the VC dimension by
finding the largest shattered subset of instances in each hypothesis space.

VC dimension for neural networks:

The Vapnik-Chervonenkis (VC) Dimension for neural networks is discussed with a focus
on layered directed acyclic graphs, specifically those resembling feedforward neural
networks trained using the backpropagation procedure. The VC Dimension is a measure of
the capacity or expressive power of a hypothesis space, and in the case of neural networks,
it helps quantify the complexity of the network's structure.

The discussion introduces the concept of the VC dimension for layered directed acyclic
networks, which are common representations of feedforward neural networks. The VC
dimension is derived based on the structure of the network and the VC dimension of its
individual units or nodes. The theorem presented provides a bound on the VC dimension
of the network's composition, considering the VC dimension of the primitive units from
which the network is constructed.

Network Structure and Composition:

The neural network is represented as a layered directed acyclic graph. The graph has input
nodes, internal nodes (representing hidden layers), and one output node. Each internal unit
implements a boolean-valued function from a function class C, with at most r inputs.

G-Composition of C:

The G-composition of C represents the hypothesis space of the network G. It includes all
functions that can be implemented by the network G when individual units take functions
from C.

VC Dimension Bounds:

10
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

The VC dimension of the G-composition of C is bounded based on the VC dimension d of

C and the structure of G. The bound is given by VC(CG)≤2dslog(e), where s is the number
of internal nodes, and e is the base of the natural logarithm.

Application to Perceptron Networks:

When considering acyclic layered networks with perceptrons as individual nodes, the VC
dimension of a single perceptron with r inputs is r+1. The overall VC dimension of the
network is then bound using the theorem, providing a method to estimate the VC dimension
of such networks.

Limitations in the Context of Backpropagation:

The analysis focuses on networks of perceptrons, and while it is noted that the VC
dimension of sigmoid units is at least as great as that of perceptrons, the application to
networks trained with backpropagation is limited.
The analysis doesn't fully capture the inductive bias introduced by backpropagation, which
favors networks with small weights.

11. State and explain about k-Nearest neighbor learning and Distance-Weighted Nearest
Neighbor Algorithms.
A.
k-Nearest Neighbor Learning:

k-Nearest Neighbor Learning:

Algorithm Description: k-Nearest Neighbor (k-NN) is an instance-based learning

algorithm for both discrete and real-valued target functions.
Instance Representation: Instances are represented as points in an n-dimensional space
R^n described by feature vectors.
Distance Measure: Euclidean distance is commonly used to measure the distance between
instances.

Discrete-Valued Target Functions: For discrete-valued targets, the algorithm estimates

the target for a new instance x based on the most common value among the k nearest
training examples to x.

11
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

Hypothesis Space: No explicit general hypothesis is formed. The algorithm dynamically

computes classifications for new instances based on the closest training examples.
Example: For k=1, the algorithm assigns the target value of the nearest neighbor to the
new instance.

Distance-Weighted Nearest Neighbor Algorithm:

Objective: The Distance-Weighted Nearest Neighbor Algorithm is a refinement of the k-

Nearest Neighbor (k-NN) algorithm, aiming to give greater weight to closer neighbors in
the classification process.

Weighting Scheme: The contribution of each of the k neighbors is weighted based on its
distance to the query point x. Closer neighbors receive higher weights.

Discrete-Valued Target Functions: For discrete-valued targets, the vote of each neighbor
is weighted according to the inverse square of its distance from x.

Weighted Classification: The final classification is determined by summing the weighted

votes and assigning the majority classification among the neighbors.

Handling Exact Matches: If x exactly matches a training instance xi, the target value is
assigned to be f(xi), handling cases where the denominator is zero.

Real-Valued Target Functions: For real-valued targets, a similar weighting scheme is

applied. The contribution of each neighbor is weighted by wi as defined in Equation (8.3).

12
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

Normalization: The denominator in the weighting equation normalizes the contributions

of the various weights, ensuring that the classifier behaves appropriately even when all
f(xi) values are constant.

Global and Local Methods: The algorithm can be implemented as a global or local
method.

- Global Method (Shepard's Method): Considering all training examples, it allows

every training example to influence the classification of x.
- Local Method: Considers only the k nearest neighbors for classification, enhancing
computational efficiency.

12. Describe about k-Nearest neighbor learning and Distance-Weighted Nearest

Neighbor Algorithms.
A. Same as Q11

13. Describe about Locally Weighted Regression.

A.

13
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

• Error criteria:

14. Write about Locally Weighted Regression.

A. Same as Q13

14
MVGR COLLEGE OF ENGINEERING MACHINE LEARNING

15. Describe about Radial Basis Functions.

A.

16. Write about Radial Basis Functions.

A. Same as Q15

15