MODULE-3
Decision by Committee: Ensemble Learning: Boosting: Adaboost , Stumping, Bagging: Subagging,
Random Forests, Comparison With Boosting, Different Ways To Combine Classifiers.
Unsupervised Learning: The K-MEANS algorithm : Dealing with Noise ,The k-Means Neural
Network , Normalisation ,A Better Weight Update Rule ,Using Competitive Learning for Clustering
Decision by Committee:
Ensemble Learning
Ensemble learning is a widely used and preferred machine learning technique in which
multiple individual models, often called base models, are combined to produce an effective
optimal prediction model. The Random Forest algorithm is an example of ensemble learning.
Boosting
Boosting is another ensemble procedure for creating a collection of predictors. In other words,
we fit successive trees, usually random samples, and at each step the goal is to resolve the net
error from the previous trees.
If a given input is misclassified by the theory, then its weight is increased so that the upcoming
hypothesis is more likely to classify it correctly by consolidating the whole set eventually
converting weak learners to more powerful models.
Gradient Boosting is an extension of the boosting procedure.
Gradient Boosting = Gradient Descent + Boosting
Advantages of using Gradient Boosting methods
• It supports different loss functions.
• It works well with interactions.
Boosting Algorithm Steps
Train a classifier A1 that best classify the data with respect to accuracy.
Identify the regions where A1 produces error, add weight to them and produce a A2
classifier.
Aggregate those samples for where ‘A1’ gives the different result from ‘A2’ and produce
‘A3’ classifier. Repeat step 2 for a new classifier.
AdaBoost
Boosting is technique of changing weak learner into strong learner . Each. new tree is a fit
on modified version of original dataset .
AdaBoost is the first boosting algorithm, to be adapted in solving practices.
It helps mixing multiple weak classifier into one strong classifier.
AdaBoost
Step 1
Assign equal weights to each data point and apply a decision stump to classify them as ‘+’ (plus)
and ‘-‘ (minus). For distinct attributes, the tree consists only of a single interior node. Now, apply
higher weights to incorrectly predicted three ‘+’(plus) and add another decision stump.
Step 2
The size of three incorrectly predicted + (plus) is much bigger than the rest of the data points.
The second decision stump (D2) will try to predict them correctly.
Now, Vertical plane (D2) has classified three misclassified ‘+’(plus) correctly.
D2 has also caused misclassified reporting to three ‘-‘ (minus)
Step 3
D3 adds higher weights to three ‘-‘ (minus)
A horizontal line is generated to classify ‘+’ (plus) and ‘-‘ (minus) based on higher weight of
misclassified observations.
Step 4
D1,D2 and D3 are combined to form a strong prediction that has a more complex rule than
individual weak learners.
AdaBoost Algorithm
Algorithm Summary:
Stumping:
A decision stump is a simple machine learning model that acts as a one-level decision tree. It makes a
decision based on a single attribute, splitting the input space into two regions using a threshold.
Stumps are extremely weak learners on their own, often giving poor classification performance if used
individually. However, they become powerful when combined using ensemble methods like AdaBoost.
In boosting, multiple stumps are trained sequentially, and each stump focuses on correcting the errors
made by the previous ones. The process begins with all training examples having equal weights. After
each stump is trained, the weights of the misclassified examples are increased, so that the next stump
focuses more on those difficult examples. Over several iterations, the boosted model builds a strong
classifier by combining the outputs of these simple stumps, each weighted according to its accuracy.
Bagging
Bagging, also known as Bootstrap aggregating, is an ensemble learning technique that
helps improve the performance and accuracy of machine learning algorithms. It is used
to deal with the bias-variance trade-offs and reduce the variance of the prediction
model. Bagging avoids data overfitting and is used for both regression and classification
models, specifically decision tree algorithms.
Example:
The Random Forest model uses Bagging, where decision tree models with higher
variance are present. It makes random feature selection to grow trees. Several random
trees make a Random Forest.
Implementation of Bagging
Multiple subsets are created from the original data set with equal tuples,
selecting observations with replacement.
A base model is created on each of these subsets.
Each model is learned in parallel with each training set and independent of each
other.
The final predictions are determined by combining the predictions from all the
models.
Advantages of Bagging
• Bagging minimizes the overfitting of data
• It improves the model’s accuracy
• It deals with higher dimensional data effcienty
Random Forest
Random Forest is a popular ensemble learning algorithm, which is an extension of the vanilla
bagging algorithm.
The first algorithm for random decision forests was created in 1995 by Tin Kam Ho. In this
algorithm, he introduced the idea of random feature selection for a high cardinality of feature
space, which is the key difference between vanilla bagging and random forest.
The algorithm for random forests is similar to that of bagging methods. However, in random
forests, a subset of pre-decided length is formed from original feature space for each of the
bootstrapped dataset.
The feature subset is chosen randomly without replacements. The length of the feature subsets,
ξf , is a hyperparameter.
A decision tree is formed for each dataset and corresponding feature space, leading to a
prediction from each. Final prediction is made following the same rules as of bagging, i.e. taking
mean for regression and mode for classification.
Random Forest, in general, is a good choice when we want a high-performing model with low
variance and low bias. It is particularly useful when we have a large number of strongly correlated
features, as the feature subsampling helps to decorrelate the models. Although, in instances, when
we don’t have a large sample-space or feature-space, or we need to find co-dependencies or
strong interpretation, it is more useful to use a simpler algorithm such as decision tree or support
vector machine. Nevertheless, Random Forest is one of the most powerful machine learning
algorithms we have and it’s been used in several complicated real life problems.
Random Forest is used in the banking and finance industry for tasks such as credit risk analysis,
fraud detection, and loan approval processes.
In e-commerce, it is used for tasks such as customer segmentation, personalized product
recommendations, and fraud detection.
Different Ways To Combine Classifiers.
Ensemble methods are powerful machine learning techniques that combine multiple classifiers to
achieve improved prediction performance compared to individual models. These techniques rely on
the assumption that different classifiers may make different errors, and a combined prediction can
reduce the overall error.
Voting Strategies in Ensemble Methods
Majority Voting
Each classifier votes, and the output class is the one with the most votes.
This is a simple method and effective when classifiers are moderately accurate and diverse.
Weighted Voting
Each classifier is assigned a weight based on its accuracy.
More reliable classifiers have a greater influence on the final decision.
Strict Voting
Some systems only produce output when all or most classifiers agree.
Used to avoid uncertain or contentious outputs.
Probability of Correct Ensemble Prediction
Assuming:
TTT: number of classifiers,
ppp: probability that a classifier gives a correct output.
The probability that the ensemble majority vote is correct is given by the binomial distribution:
∑k=T2+1T(Tk)pk(1−p)T−k\sum_{k=\frac{T}{2}+1}^{T} \binom{T}{k} p^k (1 - p)^{T-k}k=2T+1∑T
(kT)pk(1−p)T−k
If p>0.5p > 0.5p>0.5, and TTT is large, this sum approaches 1.
This explains the strength of ensembles: even if individual classifiers are just slightly better
than random, the ensemble becomes highly accurate.
Median Voting in Regression
In regression, instead of the mean, using the median is often more effective because:
The mean is sensitive to outliers.
The median is more robust and yields stable performance.
This idea leads to robust bagging, where median replaces mean for better resistance to noise.
Mixture of Experts
The Mixture of Experts (MoE) is a more advanced method that combines classifiers based on their
specialization.
Key Ideas:
The system has multiple classifiers (experts).
Gating networks decide how much to trust each expert for a given input.
Outputs from experts are weighted using gates and combined.
The system is organized hierarchically:
At the bottom are experts that receive the input and make predictions.
Gate networks also take the input and decide how much each expert should contribute.
A top-level gate may combine outputs from lower-level gates.
Gate2 combines outputs from Gate1,1 (which selects Expert1 and Expert2) and Gate1,2 (which
selects Expert3 and Expert4).
All use the same input data, and each level decides which expert(s) to trust.
Unsupervised Learning
Unsupervised learning differs fundamentally from supervised learning in that it does not rely on any
form of labelled data or external evaluation criteria. In supervised learning, we typically use a training
set containing input-output pairs and minimize a task-specific error, such as the sum-of-squares
difference between predicted and actual targets. However, in unsupervised learning, no such targets
are available. Instead, the goal is to identify underlying patterns or groupings in the data by examining
the similarities between input samples. This approach is useful in scenarios where labelled data is
unavailable or expensive to obtain and reflects more biologically plausible learning, similar to how
humans often learn without explicit feedback.
The main aim in unsupervised learning is often to cluster data points that are similar in some feature
space. This involves using internal metrics such as Euclidean distance to evaluate similarity and assign
inputs into clusters. These internal, task-independent metrics replace external error measures. If
inputs are close together in the input space, they are assumed to be similar and are grouped
accordingly. To demonstrate how such clustering is achieved, one of the most widely used
unsupervised learning algorithms—the K-Means algorithm—is introduced.
The K-Means Algorithm
The K-Means algorithm can be understood with a simple analogy: imagine tourists trying to follow their tour
guides who are holding umbrellas — only here, the data points (tourists) are stationary, and the guides
(cluster centers) move around to group them. The main idea is to divide a dataset into kkk clusters, where the
number kkk is known beforehand. For example, in a medical dataset where test results belong to three
known diseases, we might want to cluster the data into three groups. Initially, kkk cluster centers are
randomly placed in the data space, and the goal is to move these centers to the 'middle' of their respective
clusters. But since we don't know the cluster locations, we need an algorithm that adjusts these centers by
learning from the data.
To implement this, we need two key components: a distance measure and a mean calculation. Typically,
Euclidean distance is used to evaluate how close a point is to a cluster center. The mean (or centroid) of a set
of points is used to define the cluster's center — assuming the input space is flat, as in Euclidean geometry.
The objective is to minimize the total distance between each data point and its assigned cluster center, which
is equivalent to minimizing the sum-of-squares error.
The process starts by randomly initializing the cluster centers. Each data point is then assigned to the nearest
center based on the chosen distance metric. After assignments, each cluster center is updated to be the mean
of the points assigned to it. This process is repeated iteratively — recomputing assignments and updating
centers — until the centers stop changing significantly, indicating convergence. Computationally, this can be
accelerated using techniques like KD-Trees to reduce distance calculation time.
The algorithm proceeds in three stages: initialization, learning, and usage. During initialization, kkk is
chosen and kkk random cluster centers are selected. During learning, for each iteration, every data point is
assigned to the closest center, and then the centers are updated based on the mean of their assigned points.
This repeats until stability. Finally, in the usage phase, any new (test) data point is classified by assigning it
to the nearest cluster center.
The NumPy implementation follows these steps almost exactly, and we can take advan
tage of the [Link]() function, which returns the index of the minimum value, to find
the closest cluster. The code that computes the distances, finds the nearest cluster centre,
and updates them can then be written as:
🚫 Dealing with Noise
One practical use of clustering is to manage noisy or corrupted data. Clustering can act as a denoising
step by replacing each data point with its corresponding cluster center, smoothing out noise. However,
the standard K-Means algorithm relies on the mean of cluster members, which is highly sensitive to
outliers. This problem can be mitigated by using the median instead of the mean when updating
cluster centers, making the algorithm more robust at the cost of increased computation.
🤖 The K-Means Neural Network
Though not immediately obvious, K-Means can be reformulated as a type of neural network. Each
cluster center can be represented by a neuron in weight space, and the process of assigning a point to
the nearest cluster center can be implemented as a winner-takes-all mechanism in a single-layer
competitive neural network. Here, each neuron competes to "fire" for a given input, and the one whose
weight vector (position in input space) is most similar to the input vector wins and gets updated.
The network is composed of input units connected to a layer of kkk competitive neurons, where each
neuron's activation is simply the inner product of the input vector and the neuron's weight vector. The
weights of the winning neuron are then adjusted toward the input vector, effectively moving the
cluster center toward its assigned points. This formulation allows for on-line learning, where the
weights are updated incrementally for each new input rather than in batch.
🔄 Normalization and Better Weight Updates
A crucial consideration in competitive learning networks is normalization. If the input or weight
vectors are not normalized, a neuron with large weight magnitudes can always dominate, even if it is
not the best match. To ensure fairness in competition, all weight vectors (and often inputs) are
normalized to lie on the unit hypersphere. This allows the dot product to reflect angular similarity
rather than magnitude.
The basic weight update rule, where the winning neuron's weight vector is simply incremented by a
scaled version of the input vector, can cause the weights to grow unboundedly. A better alternative is
the update rule:
Δwij=η(xj−wij)\Delta w_{ij} = \eta (x_j - w_{ij})Δwij=η(xj−wij)
This rule ensures that the weight vector is updated in the direction of the input but remains bounded.
Over time, the weights stabilize to represent the mean direction of the inputs assigned to them.
🌸 Example: The Iris Dataset
To illustrate the K-Means algorithm, Marsland revisits the Iris dataset, which contains measurements
from three species of iris flowers. Even though labels are known, they are not used during
unsupervised training. After clustering, the predicted cluster labels are compared against true class
labels to evaluate performance. Often, there’s a clear one-to-one mapping between clusters and true
classes, though not guaranteed. If more clusters than classes are used, a supervised layer, such as a
perceptron, can map multiple clusters to a single class, thereby improving interpretability and
classification.
🧠 Using Competitive Learning for Clustering
Once trained, competitive learning networks can be used to assign class labels to new data based on
which neuron (cluster center) wins the competition. If labels are available, these can be matched to
clusters post hoc. However, since the learning process is label-free, the order of cluster indices may
not align with class labels. This necessitates matching cluster indices to classes manually or through a
supervised mapping layer.
Additionally, K-Means-based competitive learning can be used to initialize Radial Basis Function (RBF)
networks, where the unsupervised part identifies good positions for RBF centers, and a subsequent
supervised layer handles classification. This hybrid approach combines the strengths of both learning
paradigms and avoids the need for manual cluster-class mapping.