ML Question Bank CA-II

1. What is PAC learning model?

Probably Approximately Correct (PAC) learning 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.

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.

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 generalize well to unseen instances.

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.

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.

2. Define and explain “Shattering a set of Instances” with suitable example.

Shattering a Set of Instances

In machine learning theory, particularly in PAC (Probably Approximately Correct)

learning, “Shattering” is a concept used to describe how well a hypothesis class
can fit data.
A hypothesis class H is said to shatter a set of instances S if for every possible
labeling (classification) of S, there exists some hypothesis in H that correctly
classifies all the instances in S according to that labeling.
Suppose you have a small dataset S with a few input points. If a hypothesis class
H can correctly learn all possible combinations of labels (e.g., 0s and 1s) for those
input points, then we say that H shatters the set S.
It basically means:
“No matter how you assign labels to the data points, the hypothesis class can
match that labeling exactly.”

Example:
LetÕs consider a simple hypothesis class:
Let H be the set of all linear classifiers in 2D (like straight lines).
Let S = {A, B, C} be three points in a plane that are not in a straight line (they
form a triangle).
There are 2³ = 8 possible labelings (e.g., 000, 001, 010, ..., 111).
If for each labeling, we can draw a line that separates the points according to
their labels, then H (set of linear classifiers) shatters the set S.
In this case, yes — a line can separate three points in 2D in any labeling (if not
collinear).
So the set of 3 non-collinear points is shattered by linear classifiers.
But if you take 4 points in 2D, not all labelings can be separated by a line.
So the hypothesis class of linear classifiers cannot shatter 4 points in general.

Significance of Shattering:
 Shattering is used to define the VC Dimension (Vapnik–Chervonenkis
Dimension) of a hypothesis class.
  The VC Dimension is the size of the largest set that can be shattered by the
hypothesis class.
 It helps in measuring the capacity or complexity of a learning algorithm.

3. What is ensemble learning? Describe in detail the types of ensemble learning.

Ensemble learning is a machine learning technique where multiple models (learners)
are combined to solve the same problem and improve overall performance.
The idea is that a group of weak learners (models that perform slightly better
than random guessing) can be combined to form a strong learner with better
accuracy and robustness.
Why Use Ensemble Learning?
 Reduces the chances of overfitting or underfitting.
 Improves accuracy, stability, and generalization.
 Handles complex data patterns better than a single model.

Types of Ensemble Learning

There are three main types of ensemble learning:

1. Bagging (Bootstrap Aggregating)

 Goal: Reduce variance (i.e., avoid overfitting).
 How it works:
o Create multiple subsets of the training data by random sampling with
replacement.
o Train a separate model (like a decision tree) on each subset.
o Final prediction is made by averaging (for regression) or majority voting
(for classification).
Popular Algorithm: Random Forest

Example: Suppose we have 1000 data points. We create 10 models, each trained on
a random 1000-sample subset (some points may repeat).

2. Boosting
 Goal: Reduce bias and improve predictive accuracy.
 How it works:
o Models are trained sequentially, each new model focuses on correcting
the errors of the previous one.
o Misclassified points are given more weight in the next round.
o Final model combines all weak learners in a weighted manner.
 Popular Algorithms:
 o AdaBoost (Adaptive Boosting)
o Gradient Boosting
o XGBoost
 Example: In AdaBoost, if a data point is misclassified by the first tree, the
next tree gives more importance to that point.

3. Stacking (Stacked Generalization)

 Goal: Combine different types of models to capture a wider variety of
patterns.
 How it works:
o Multiple different base models (e.g., SVM, Decision Tree, KNN) are
trained.
o Their predictions are passed to a meta-model (usually logistic regression
or another classifier), which learns how to best combine their outputs.
 Example: Use SVM, KNN, and Decision Tree as base learners. Then use a
logistic regression model to learn from their outputs.

4. Explain any one ensemble learning algorithm.

Random Forest Algorithm (An Ensemble Learning Technique)
Random Forest is an ensemble learning algorithm that combines the predictions of
multiple decision trees to produce a more accurate and stable result.
It belongs to the Bagging family (Bootstrap Aggregation).

How it Works:
1. Bootstrap Sampling:
o From the original dataset, random subsets are created with
replacement.
o Each subset is used to train a different decision tree.
2. Random Feature Selection:
o When splitting nodes in each tree, only a random subset of features is
considered, which makes each tree slightly different.
3. Training Multiple Trees:
o Many decision trees are trained in parallel, each on a different subset.
4. Prediction:
o For Classification: Each tree votes, and the majority class is the final
output.
o For Regression: The average of all tree predictions is taken.
Example:
LetÕs say we want to classify whether a loan should be approved.
 Features: Income, Credit Score, Age, Loan Amount.
 Random Forest:
o Trains multiple decision trees.
o Each tree sees a different subset of data and features.
o Some trees may focus more on credit score, others on income, etc.
o The majority of trees predicting "Approve" → Final output = Approve.
Advantages:
 High Accuracy: Combines many trees to reduce errors.
 Reduces Overfitting: Trees are less correlated due to randomness.
 Works Well with Large Datasets
 Handles Missing Data

Disadvantages:
 Slower Prediction Time (because many trees are involved).
 Less interpretable than a single decision tree.

Applications:
 Banking (fraud detection)
 Healthcare (disease prediction)
 E-commerce (product recommendation)
 Stock Market (price prediction)
1. Explain the how K-Means Clustering Algorithm works? Explain the elbow
method.

What is K-Means Clustering?

K-Means is an unsupervised learning algorithm used for clustering, where the goal is
to divide data into K distinct clusters based on similarity.

Each cluster has a centroid (center point), and data points are grouped based on the
nearest centroid.

2. Working of K-Means Algorithm

The algorithm works in the following steps:

Step 1: Choose the value of K

 Decide the number of clusters (K) you want to create.

Step 2: Initialize centroids

 Randomly select K points from the dataset as initial centroids.

Step 3: Assign points to nearest centroid

 Calculate the Euclidean distance of each data point to each centroid.

 Assign each point to the nearest centroid.

 This forms K clusters.

Step 4: Update centroids

 For each cluster, calculate the mean of all points in that cluster.

 Move the centroid to this new mean position.

Step 5: Repeat

 Repeat steps 3 and 4 until:

o Centroids do not change (convergence), or

o A maximum number of iterations is reached.

3. Example

LetÕs say we have the following data points (students' scores):

[45, 47, 50, 55, 90, 92, 95]

If we apply K = 2, the algorithm will:

  Group [45, 47, 50, 55] into one cluster (low scorers).

 Group [90, 92, 95] into another cluster (high scorers).

4. Elbow Method

The Elbow Method helps you choose the optimal value of K (number of clusters).

How It Works:

 Run K-Means for different values of K (e.g., from 1 to 10).

 For each K, compute WCSS (Within Cluster Sum of Squares).

 Plot a graph of K vs. WCSS.

Why Use It?

 Avoids overfitting by not choosing too many clusters.

 Ensures clusters are meaningful.

2. What is unsupervised machine learning? Explain with suitable example. What

is clustering?

1. What is Unsupervised Machine Learning?

Unsupervised learning is a type of machine learning where:

The model is not provided with labeled data (no output values).

The goal is to find hidden patterns or structure in the input data.

The algorithm tries to learn the structure of the data by identifying similarities,
differences, or groupings within the data.

Key Features:

 No labels or output values are provided.

 Learns from the input data only.

 Mostly used for exploratory data analysis.

 Common tasks: Clustering, Dimensionality Reduction, Anomaly Detection.

2. Example of Unsupervised Learning

Imagine a company collects customer data with features like:

 Age

 Spending Score

 Annual Income

But there is no label like "Premium Customer" or "Budget Customer."

Using unsupervised learning, the company can:

 Identify groups of similar customers based on their spending habits.

 Use these clusters for targeted marketing or personalized offers.

Algorithm Used: K-Means Clustering (or any clustering technique)

3. What is Clustering?

Clustering is one of the most common tasks in unsupervised learning.

It involves grouping similar data points together into clusters so that:

 Points in the same cluster are more similar to each other.

 Points in different clusters are less similar.

Common Clustering Algorithms:

Algorithm Description

K-Means Divides data into K clusters by minimizing within-cluster distance.

Hierarchical Builds clusters in a tree-like structure (dendrogram).

DBSCAN Groups points based on density, useful for irregular shapes.

Applications of Clustering:

 Customer segmentation in marketing

 Document classification

 Grouping similar products

 Image compression
3. Explain Hierarchical Clustering Technique and its types in detail.

1. What is Hierarchical Clustering?

Hierarchical clustering is an unsupervised machine learning technique used to group

similar data points into clusters, where the clusters are arranged in a tree-like
structure (called a dendrogram).

The process involves either:

Merging smaller clusters into larger ones (bottom-up), or

Dividing a large cluster into smaller ones (top-down).

Unlike K-Means, hierarchical clustering does not require specifying the number of
clusters (K) in advance.

2. Types of Hierarchical Clustering

Hierarchical clustering is of two main types:

A. Agglomerative Hierarchical Clustering (Bottom-Up Approach)

This is the most commonly used type.

Steps:

Start with each data point as an individual cluster.

Find the closest pair of clusters and merge them.

Repeat step 2 until all data points belong to a single cluster (the root).

Key Concept: At each step, the algorithm chooses the nearest clusters based on a
distance metric.

B. Divisive Hierarchical Clustering (Top-Down Approach)

This approach is the opposite of agglomerative.

Steps:

Start with all data points in one big cluster.

Split the cluster into two smaller clusters.

Keep splitting until each data point is its own cluster or a stopping condition is met.
This method is computationally more expensive, and hence less commonly used.

3. Distance Metrics Used in Clustering

To decide which clusters to merge or split, we use linkage criteria:

Linkage Type Description

Single Linkage Minimum distance between any two points in two clusters

Complete Linkage Maximum distance between points in two clusters

Average Linkage Average of all pairwise distances between two clusters

Centroid Linkage Distance between the centroids of two clusters

5. Advantages of Hierarchical Clustering

No need to specify the number of clusters in advance

Can handle non-spherical cluster shapes
Good for small datasets and visualization

6. Disadvantages

Not scalable for large datasets

Once a merge/split is done, it cannot be undone
Sensitive to noise and outliers

7. Applications

 Bioinformatics (gene sequencing)

 Market segmentation

 Social network analysis

 Document or text clustering