Ensemble Algorithms

Ensemble algorithms started in the previous session and this one finishes them. The whole idea fits in one sentence: instead of using a single classification algorithm or model for the final prediction, we use a group of classification algorithms and combine their outputs. We first revisit why that helps, then look at the four ways to combine results, then study two bagging-based algorithms in detail - bagged decision trees and random forest - and end with a detour into adversarial robustness, which is where bagging-based models get interesting in practice.

10.1 The Big Idea Behind Ensembles

10.1.1 One Model or a Group of Models

The standard pipeline until now looks like this: take a dataset $D$, train one classifier on it (say a decision tree, DT), test it, and read off the final prediction. An ensemble flips this picture. The same dataset is passed not to one algorithm but to a group of classification algorithms or models. Each model makes its own prediction, and at the end we combine those results into a single final answer. The combine step is the heart of every ensemble — nothing else distinguishes an ensemble from a plain classifier.

Name the pieces with a compact notation, because every ensemble in this lecture is a filling of the same skeleton. Suppose we have $k$ base classifiers $C_1,C_2,\dots ,C_k$. Given a test sample $x$, each classifier returns its own prediction $C_i(x)$, and the ensemble's final prediction is:

$$C^{\ast }(x)=\text{combine}(C_1(x),C_2(x),\dots ,C_k(x))$$

The function $\text{combine}$ is where the ensemble actually lives. Two ensembles that use the same $k$ classifiers but different combine rules are, for practical purposes, different algorithms — which is why the lecture spends so much time on combination techniques before touching any specific algorithm.

Picture the structure as a short factory line: the dataset $D$ sits on the left; arrows fan out from it into $C_1,C_2,\dots ,C_k$; and a single arrow leaves the fan on the right, labeled "combined prediction $C^{\ast }(x)$". The fan of models is only the machinery; the final arrow is what actually decides.

10.1.2 Why Combining Works: The Wisdom of the Crowd

The statistical justification is simple: the wisdom of the crowd beats one intelligent classifier. We deliberately force multiple classifiers to make independent errors, and when their results are combined, the overall error drops below what any single model achieves. The reasoning is the same one behind a famous game show called KBC (Kaun Banega Crorepati), where a contestant stuck on a question has two lifelines: phone a friend, or take an audience poll. Phone a friend is one expert — you are betting on a single classifier. The audience poll is a group of people, each voting on the correct answer. Statistically, the audience poll outperforms phone a friend: collective intelligence of a group beats a single expert, even a good one. So an ensemble does nothing exotic — it just applies the same crowd logic to classifiers.

The analogy's honest boundary: the audience only beats the friend when the voters are independent of each other and each voter is at least a little better than a coin flip. If every audience member simply copies the same smart friend, the crowd collapses into one opinion repeated many times, and the vote adds nothing. The same is true of classifiers, and this exact point returns in the bagged decision tree section.

The professor's claim about the scale of the effect: "let's suppose you have 25 classification models, each of them generating an error of 0.35. If you combine them in a particular way, overall error will be reduced to 0.06." The combination scheme matters — the number 0.06 comes from combining in a particular way, not from any arbitrary merge. The standard treatment works this example in full, and it is worth seeing the machinery, because the "particular way" turns out to be nothing exotic: majority voting plus independent errors.

Two conditions make the arithmetic work, and both matter for every ensemble we build later:

1. The errors must be independent. If the 25 models are identical, they make the same mistakes on the same samples, the vote changes nothing, and the ensemble error stays at 0.35.
2. Each model must beat random guessing ($ϵ<0.5$). Below 0.5 the vote helps; above 0.5 the crowd is systematically wrong and the ensemble is worse than its members.

In practice, perfect independence is impossible — models trained on the same data share mistakes — but even partly independent classifiers improve on a single model, which is why ensembles are everywhere in modern machine learning.

Real-world: game shows like KBC have used the audience poll as a lifeline for decades precisely because crowds are more reliable than individuals; the same principle underlies modern ensembles — from random forests in fraud detection to the committees of models behind search results and streaming recommendations.

10.1.3 The Two Design Choices in Every Ensemble

Every ensemble algorithm in the literature differs along exactly two axes: which classification algorithm you use, and how you combine the results. Different ensemble structures come with their own rules and properties for these two parameters. The session covers four ways of combining results (committee, weighted average, predictors of predictor, and mixture of experts), then two concrete algorithms: bagged decision trees and random forest, and closes by pointing at a boosting algorithm as homework. There are more combining techniques in the literature, but for this course these four are enough.

Why only two axes? Look back at the skeleton from Section 10.1.1: the models in the middle (the "which algorithm" choice) and the combine function at the end (the "how to combine" choice) are the only two places where an ensemble author has freedom. Everything else — how many models, how the training data is shared between them, whether they run in parallel — is detail that ultimately belongs to one of the two axes.

The next section works through the four ways to combine the models' outputs.

10.2 Four Ways to Combine Model Results

10.2.1 Committee: Majority Voting and Simple Averaging

A committee is the simplest aggregation. The analogy the professor uses is how a government gets elected: each person living in a constituency gets one vote, and the candidate with the majority of votes becomes the representative. It also works like passing a bill in parliament: the bill is put on the table, every MP votes, and if a majority of MPs say yes the bill passes; if a majority say no it is rejected. In a committee of five members, each member has exactly one vote, everyone votes, and the decision backed by the majority wins.

In classification problems the committee rule is majority voting: each classifier votes for a class and the class with the most votes is the final answer. Written with the skeleton from Section 10.1.1, the committee's combine function is:

$$C^{\ast }(x)=\arg \underset{y}{\max }\sum _{i=1}^k\mathbb{I}(C_i(x)=y)$$

where $x$ is the test sample, $C_i(x)$ is the class predicted by classifier $i$, $y$ runs over the candidate classes, and $\mathbb{I}(\cdot )$ is an indicator that is 1 when the condition inside is true and 0 otherwise. In words: for each class, count how many classifiers voted for it, and pick the class with the highest count. Every classifier's vote counts exactly once — that equal weight is the defining property of the committee.

In regression problems there are no classes to vote for, so you just aggregate the results with an unweighted average. If the three results are $R_1$, $R_2$, and $R_3$, you add them and divide by three:

$$Y=\frac{R_1+R_2+R_3}{3}$$

where $R_1,R_2,R_3$ are the predictions of the three models and $Y$ is the combined prediction. The professor's verbal description: "let's suppose three results are R1, R2 and R3. You can just add them and divide by three. So unweighted average you have done here."

10.2.2 Weighted Average

The weighted average relaxes the equal-vote rule: instead of giving each vote the same weight, we give higher weightage to some votes and lower weightage to others. The professor's everyday analogy: in a committee of five people with committee voting, each person gets one vote and every vote weighs the same; in a weighted average over the same five people, votes weigh differently — a more senior person gets more weight, a more junior person gets less, or a person with higher educational qualification gets more weight and a person with lower qualification gets less.

Applied to classifiers: train multiple classification algorithms or models, then decide weights based on accuracy or error. Give higher weightage to a model with higher accuracy and lower weightage to a model with higher error. Formally, the final classification is a weighted sum of the individual predictions:

$$Y=\sum _{i=1}^k{\alpha }_i{\hat{y}}_i$$

where $k$ is the number of classifiers, ${\hat{y}}_i$ is the prediction of the $i$-th classification algorithm, and ${\alpha }_i$ is the weight (alpha, as the session calls it) you assign to that algorithm — a higher number for a classifier you trust more, a lower number for one you trust less. When the weights are all equal, ${\alpha }_i=1/k$ for every $i$, the weighted average collapses back into the committee's unweighted average — so the committee is the weighted average with equal weights. The professor's guidance on choosing weights: the weight ${\alpha }_i$ can be directly proportional to accuracy, inversely proportional to variance, or inversely proportional to error — "higher the error, lower the weight of the classification algorithm; higher the classification accuracy, higher the weight of the classification model."

The standard treatment of ensemble methods uses exactly this idea — combine the base classifiers by voting, "or by weighting each prediction with the accuracy of the base classifier." The professor's version generalizes the accuracy rule: accuracy is one reasonable basis for the weights, but variance and error work just as well, and the meaning is the same — models you trust more get more say.

10.2.3 Predictors of Predictor

Predictors of predictor (reviewed from the earlier session) does not use the raw predictions directly. Suppose the original dataset was used to train three models: a DT model, an SVM model, and a rule-based classification model. Given a test sample, DT predicts some ${\hat{y}}_1$, SVM predicts ${\hat{y}}_2$, and the rule-based model predicts ${\hat{y}}_3$. Committee would combine these three values directly, either by majority voting or with a weighted average putting alphas on them. Predictors of predictor instead treats each prediction as a tuple — a feature vector — and trains a brand new model on those tuples. That second-level model produces the final prediction $Y$. In other words, you learn a predictor on top of the predictions: the predictions become the input data for a final model. This structure is called predictors of predictor (a stacking-style meta-model, standard in the literature under different names).

The two-level flow is a flow of two stages. Stage one: the original dataset $D$ with attributes $A_1,A_2,\dots$ trains the three base models. Stage two: the base models' predictions on every training sample are collected into a new table — each row is a tuple $({\hat{y}}_1,{\hat{y}}_2,{\hat{y}}_3)$, and the true class of that sample becomes the label of the row. A second-level model (a meta-model) is trained on this new table, and that meta-model's output on a fresh tuple is the final prediction $Y$.

The literature calls this structure stacking (or stacked generalization), and it is widely supported in practice — for example, the combination of base models into a stacking meta-model is the standard way ensemble "voting" operators work in data mining tools. The key difference from a committee: the combination rule is not fixed in advance by the designer; it is learned from data.

10.2.4 Mixture of Experts

The fourth combining technique partitions the data instead of the predictions. Take a big dataset, projected into a 2D space. Instead of building one classification model for the whole space, partition the space into multiple parts and build a separate model inside each part: a DT model for one region, an SVM model for another region, a rule-based classification model for a third. When a test sample arrives, only the model of its region is invoked — a sample in region one triggers only the DT, a sample in region two triggers only the SVM, and so on. The complete vector space is divided into parts, and inside each part we can use one or many classification algorithms. Mixture of experts is divide-and-conquer on the input space rather than on the output votes.

Picture the input space as a flat map with the two attributes as the horizontal and vertical axes. Instead of one expert covering the whole map, draw boundaries that cut the map into three territories, and write a different expert's name in each territory: DT on the left block, SVM on the middle block, rules on the right block. A test point lands in exactly one territory, and only that territory's expert decides — no votes, no weights, no meta-model.

Why is partitioning the input space a valid combining method? Because a single model must draw one boundary through the entire space, but different regions of the space often need different boundary shapes. Where the data is cleanly separable by a line, a linear model wins; where it is tangled, a tree wins. Partitioning lets each region use the model best suited to it — an explicit "divide and conquer" that a committee can only approximate through voting.

10.2.5 How the Four Methods Compare

The committee is the fastest to build and explain, and its equal-weight rule is the safest default when model qualities are unknown. Weighted average is the committee with trust levels: it pays off when you have a reliable accuracy, variance, or error estimate per model. Predictors of predictor is the most powerful of the three prediction-level methods, because the combination rule is learned instead of designed — at the cost of a second training stage and the risk that the meta-model overfits the small tuple dataset. Mixture of experts is the outlier: it is the right tool when different parts of the input space genuinely need different models, and it needs a way to draw the region boundaries in the first place.

10.3 The Philosophy of Bagging and Boosting

10.3.1 Bagging's Philosophy

Every ensemble algorithm is built on a philosophy, and the philosophy is fixed for each class of algorithm. The philosophy of bagging-based algorithms is to reduce overfitting issues in the model, and the tool for that is playing around with the bias-variance trade-off. That is the entire idea behind bagging. This philosophy is shared by every concrete bagging example — bagged DT, bagged SVM, random forest, and many more — with only minor changes here and there. Once the philosophy is clear, every bagging algorithm makes sense on its own.

The standard treatment confirms the same story: bagging improves generalization error by reducing the variance of the base classifiers. One practical consequence follows immediately — bagging pays off most when the base classifier is unstable, meaning small changes in the training data produce noticeably different models. Decision trees, rule-based classifiers, and neural networks are the classic unstable models; each bootstrap subset gives them a genuinely different shape, and averaging those shapes stabilizes the result. If the base model is already stable — barely changing when the data changes — bagging has little variance left to remove, and it can even make things slightly worse, because each member now trains on less data than it would have seen alone.

The everyday picture: imagine a teacher who marks each student with a single essay. One essay can be a fluke — the student memorized one good paragraph. Bagging is the teacher who asks for many short essays on random subsets of the syllabus; no single essay can carry the grade, so the final judgement is a more stable picture of the student's real ability. The analogy's boundary: if every "essay" is actually the same essay (models that are perfectly correlated), asking for more of them changes nothing.

10.3.2 Boosting's Philosophy

Boosting starts from the opposite promise: given a group of weak classifiers, combine them in such a fashion that the final result is a highly complex, highly accurate, highly performant classification model. The initial models are weak classifiers, and the combination turns them into one sophisticated, complex classifier. AdaBoost, gradient boost, histogram boost, and the rest all work on this single philosophy, with only tunable differences between them. So the mental map is: bagging fights overfitting through the bias-variance trade-off; boosting builds strength from weakness.

Where bagging asks many models to vote on equal footing, boosting builds its model in a chain: train a weak classifier, look at which samples it got wrong, give those samples more importance, train the next weak classifier on the reweighted data, and repeat. Each new member is forced to specialize on the mistakes of its predecessors, and the final prediction is a weighted combination of all the chain's members. The "weak classifiers" of the philosophy are models that are only slightly better than random guessing — each one alone is nearly useless, which is precisely why the promise is striking: a pile of nearly useless models becomes one sophisticated, complex, highly accurate classifier.

The one-sentence rule for choosing: bagging is the tool when the model is too unstable and overfits (high variance); boosting is the tool when the individual models are too weak and underfit (high bias).

10.4 Bias, Variance, and the Error Curve

10.4.1 Train Error and Test Error

To see what bagging is really doing, we need the two error definitions. You partition the dataset into training data and test data. Train error is what you get when you build the model on the training data and then test it also on the training data. Test error is what you get when you train on the training data but test on the test data. Everything seen until now in the course is test error. Test error matters because you do not want to overlearn: you want to know how the model performs on a sample that is not already in the dataset, on unseen samples, and only test data can tell you that.

Concretely: split a dataset of 1000 samples into 800 training and 200 test samples. A model trained on the 800 might classify 780 of them correctly — train error 20/800 = 2.5%. Tested on the 200 held-out samples it might get 176 right — test error 24/200 = 12%. The 12% figure is the number that matters, because the test samples were not available while the model was being built; a new customer, a new email, a new file behaves like a test sample, not like a training sample.

10.4.2 Model Complexity and the Two Curves

Plot model complexity on the x-axis and error on the y-axis. Model complexity means how strong the model is — whether it can only draw a linear boundary, or a quadratic one, or an even more complex function. For decision trees, complexity is controlled by the height of the tree. If the maximum height is one, the model has essentially no complexity: you must decide the class using a single attribute, so the best boundary you can draw is a straight line parallel to either the x-axis or the y-axis — that is a decision stump. If there is no limit on the height, the tree can split on many features and is a highly complex model.

The train error curve: at very low complexity the train error is very high, and as complexity increases the train error keeps decreasing until it becomes parallel to the complexity axis — it flattens out near zero. The test error curve: it starts very high at low complexity, decreases as complexity increases, and then rises again — a U shape. The gap between the two curves is the story of the next two zones.

Picture the graph: horizontal axis is model complexity (left = simple, right = complex), vertical axis is error (low at the bottom, high at the top). The train curve comes down from the top-left and runs flat along the bottom — a simple model cannot fit even the training data, a complex one fits it almost perfectly. The test curve descends from the top-left, reaches a low valley in the middle, and climbs back up on the right. The point where the test curve is lowest is the sweet spot of the whole lecture: enough complexity to learn the real pattern, not so much that the model chases noise.

10.4.3 The High-Bias Zone

The left part of the test error curve is the high bias zone. Bias comes from the model choice: under the sun there are thousands of classification algorithms, and for each one you can raise or lower the complexity by tuning parameters — a DT with maximum height one, or a DT with height 500. If you choose a very simple model, the model cannot learn the data. "Not understanding the data" means the model produces high train error and high test error at the same time — both curves sit high. That failure mode is called high bias. You can fix high bias by increasing the model complexity or by changing the classification algorithm altogether.

In the left zone the two curves sit close together, both high. The model is failing because it is not strong enough — a decision stump trying to separate a pattern that needs two or three attributes cannot do it, no matter how the data is sampled. The failure is a design failure: the model simply does not have the expressive power. Because both errors are high together, no amount of extra data fixes the problem — a wrong model trained on more data is still the wrong model.

10.4.4 The High-Variance Zone

The right part of the curve is the high variance zone: train error is very low but test error is very high. This happens because at high complexity the model learns the minute details of the dataset — even the noise. Tested back on the training data the error is almost zero, but the test partition contains samples drawn from a slightly different distribution, so the same model fails there. The professor's plain-language definition of variance: if your model is too dependent on the training data, then changing the training data changes the performance drastically — the error swings up or down. High variance is exactly this: change the dataset a little and the classification performance changes a lot.

In the right zone the two curves are far apart: train error near zero (the model aces the homework), test error high (the model fails the unseen problems). The model has learned the class boundaries plus every random wiggle of the training samples. The wiggles do not exist in the test data, so the model's elaborate boundary is wrong there. The professor's plain-language definition of variance captures the diagnosis directly: if the training data were swapped for a slightly different sample, this model would redraw its boundary drastically — the model is hostage to its training data.

10.4.5 Where Bagging Lands

In the ideal world the model sits in the middle of the curve — not in the high bias zone, not in the high variance zone. Bagging fixes exactly this part. Bagging-based models never have high variance, and they will not have high bias either: the structure of bagging forces the model to the middle, away from both extremes. This is the core claim to remember: bagging is designed to reduce high bias and high variance in the system.

The standard treatment sharpens the claim in one detail worth knowing: bagging's main weapon is variance reduction. A bagged model averages many slightly different models, and averaging cuts the fluctuation that defines variance. The bias side of the trade-off is largely untouched — bagging does not make the base model stronger — which is why the professor also says bagging-based models "will not have high bias": the base trees are already complex enough to be past the high-bias zone, so the ensemble inherits their strength while removing their instability. (The professor's claim that bagging directly reduces high bias too is the subject of the homework question in Section 10.5.3 — the class is expected to reason it through.)

10.4.6 The Bias-Variance-Noise Decomposition

The two-zone story has a formal backbone. The standard treatment decomposes the expected error of a model into three parts:

$$\text{expected error}=\text{bias}+\text{variance}+\text{noise}$$

where bias is the systematic error built into the model choice (the error that remains even with infinite training data), variance is the fluctuation caused by changing the training sample, and noise is the irreducible error in the problem itself — samples with identical attribute values but different class labels, which no model can ever predict perfectly.

The standard intuition is a projectile fired at a target: the bias is how far the average landing spot sits from the target (the launcher's fixed angle), the variance is how much the landing spot scatters around that average (the varying force applied), and the noise is the target itself moving. A model with high bias hits consistently far from the target; a model with high variance sprays shots everywhere; even the best aim cannot hit a moving target reliably.

Map the decomposition onto the curve from Section 10.4.2: at the left edge the bias term dominates (both errors high, close together); at the right edge the variance term dominates (train near zero, test high); in the middle the two terms balance, which is exactly where the test error is lowest. Bagging's claim, in the language of the decomposition, is that averaging many unstable models shrinks the variance term while leaving bias and noise unchanged — the ensemble lands in the middle of the curve.

10.5 Bagging: Bootstrap Aggregation

10.5.1 Step One: Bootstrapping

Bagging has two steps, and its name spells them out: bootstrap aggregation. The first step is bootstrapping. Given the dataset $D$ with $T$ tuples, generate many subsets $D_1,D_2,\dots ,D_t$ of $D$ by random sampling with replacement. Each subset $D_i$ holds $K$ tuples, a smaller number than the full dataset:

$$D_i\subset D,|D_i|=K,K<T=|D|$$

The professor's description: "initially you have a data set D with T tuples. You generated many subsets of D which is D1, D2, D3 to Dt, by doing random sampling with replacement." The inequality $K<T$ is the point: each model will see a subset, not the whole dataset. Generating these subsets is the bootstrapping step. The number of subsets you generate equals the number of classification models you plan to build — if you want 100 models, you generate 100 subsets.

The letter $T$ is the session's notation for the total number of tuples in $D$. Textbooks often use $N$ for this count; here we keep $T$ to match the lecture. The subscript count $t$ (in $D_t$) is the number of subsets, which equals the number of models — do not confuse the total count $T$ with the number of subsets $t$.

A note on the standard convention: the classical bootstrap (as in the standard treatment and in the reference text's bagging algorithm) draws bootstrap samples of the same size as the original dataset, with replacement, so a subset can be exactly as large as $D$ while still omitting about $1-1/e\approx 0.632$ of the distinct tuples on average. The professor's version draws strictly smaller subsets ($K<T$); the mechanism and the lesson — duplicates allowed, some tuples missing, no model sees all of $D$ — are identical either way.

10.5.2 Step Two: Aggregation

The second step is aggregation (also called bagging). For each subset $D_i$, build a classification model $M_i$ — for example, a DT model on $D_1$, another DT on $D_2$, and so on. Then combine the results at the end by majority voting over the committee. So every bagging-based model looks the same: dataset $D$, subsets $D_i$, one model per subset, majority vote at the end. Whether it is random forest, bagged DT, or bagged SVM, the structure is fixed; the only thing that varies is the base algorithm and small details. A concrete default: for random forest the default number of DT models is 100, so you generate 100 subsets and train 100 decision trees on them. In scikit-learn that parameter is called the number of estimators — the number of classification models you want to train, 100 DTs by default, so 100 subsets of $D$.

The aggregation step is why the method has "aggregation" in its name: the individual models are deliberately trained in isolation, and only at prediction time are they brought together by the vote.

10.5.3 Why Bagging Lowers Variance

Recall the variance definition: if you change the dataset, the performance fluctuates. Bagging lowers variance through bootstrapping. Because no model ever sees the complete dataset, no model can overlearn the data or learn the very minute details and noise from it: each subset is derived from $D$ with $K<T$, so the full dataset is never exposed to any single classification model, and that is how the overall variance in the system drops. A student's answer along exactly these lines was confirmed in class — not exposing the complete data to any one algorithm is the accepted explanation for variance reduction.

The statistical view agrees and makes the mechanism precise: when you average $k$ predictions whose fluctuations are largely independent, the fluctuations of the average shrink. If each of $k$ models has variance ${\sigma }^2$, the average has variance about ${\sigma }^2/k$ — more models, steadier answer. Bootstrapping is what makes the models' fluctuations different from each other: different subsets, different trees, different mistakes — and differences between mistakes is precisely what the average needs to cancel them.

The professor's framing: "Bagging models will force your model to be here, not on the extremes," pointing at the middle of the bias-variance curve.

10.5.4 Bootstrapping vs. Cross Validation

A student asked how bootstrapping differs from cross validation, and argued that in some sense they are almost the same — the structures do look similar. The professor held the thought, then corrected it in detail.

The follow-up point is important: the professor explicitly ties the difference to random sampling of tuples and attributes, which cross validation does not do — the attribute part is exactly the step that will distinguish random forest from bagged DT.

The "almost the same" impression comes from the shared gesture of splitting the data into overlapping pieces; the difference is what the pieces are for — one error estimate versus a family of models.

10.5.5 Everyday Analogies

A student asked for a real-life example, and the professor gave two. The first: suppose you have had chest pain for the last 15 days. You go to a doctor who asks for an angiography; the angiography shows multiple blockages, and the doctor proposes open heart surgery. Not confident, you take a second opinion: the second doctor says three arteries have about 80% blockage each and you do not need open heart surgery — two or three stents will do. Still unsatisfied, you visit a third doctor, who also recommends three stents instead of surgery. Now you have three opinions: two say stents, one says open heart surgery. You do a majority vote and get the operation done accordingly. That is exactly bagging: two models predict the same thing, one differs, and the majority decides the final prediction.

The second analogy: choosing a masters program. You have multiple options — a BITS degree, an IIT degree, an IIT degree option, and so on. Many seniors tell you their experience at BITS was good, so you go with BITS. You choose bagging in everyday life every time you let the majority of advisors guide a decision.

10.6 Bagged Decision Trees

10.6.1 How Bagged DT Works

Bagged DT is a DT-based bagging algorithm available in scikit-learn. The first step is bagging, where data points are randomly sampled with replacement to generate multiple bags. Then a DT-based model is trained on each bag — this is the aggregation phase, and the name bagged DT means all the models are decision trees, nothing else. Finally, the results are combined by majority voting to produce the prediction. The flow: dataset $D$ → subsets $D_1,D_2,\dots$ → one DT per subset → majority vote → final prediction.

The structure is the exact bagging skeleton from Section 10.5 with the base algorithm fixed to decision trees. Because every member is a DT, the committee's vote is a vote among trees — and the value of the vote depends entirely on how different those trees are, which is the subject of Section 10.6.3.

The number of bags is a tunable: like random forest, the parameter is the number of estimators, which the professor believes defaults to 100 (with some uncertainty). It is a tunable either way — you can make it 10, 100, or 500.

10.6.2 The Memorization Effect and Tuning a DT

The positive side of bagged DT: it is better than a single DT because it reduces the memorization effect of DT models. Memorization is what happens when you have very few tuples and the DT model learns even those — it rote-learns everything. A rote-learning model is not what we want; we want a generalized model, meaning less specificity and higher generalization performance: the model should not learn minute details or noises. Even if accuracy is high, a model that does not generalize well will not be selected. The professor's tuning walkthrough uses the scikit-learn tunables of a DT: one of the parameters is the minimum number of tuples at each leaf node. A leaf node holds the class label, and the tunable decides the minimum number of samples required to create one. With the default of one, a prediction can rest on a single sample — that sample might be noise, so the model has overlearned. By setting the minimum to five, a leaf node is only created when you have the same label for five samples, which pushes the model toward generalization. The same effect can be tuned with the maximum number of leaf nodes. One more parameter, max_features, was mentioned in class with the answer "max features equals to none," deferred for later — it is exactly the attribute-sampling idea that powers random forest.

The professor's vocabulary correction is worth keeping straight: the bad behavior is the memorization effect (rote-learning the few training tuples), and the desired alternative is a generalized model — immunity to minute details and noise.

10.6.3 The Fundamental Problem with Bagged DT

Bagged DT has a fundamental issue: the upper structure of all the DT models remains the same. The reasoning goes through how trees are built. Suppose there are three attributes and we build a DT using entropy as the feature selector: compute the entropy of all three features, pick the highest, then the second highest, then the third, and the tree is built. Now start from the full dataset $D$ (100 samples) and a subset $D_i$ (say 90 samples). The attribute entropies are estimators that work on a greedy strategy: instead of 50 samples you now have 47 samples, but the majority of the samples is still there, so the entropy of each attribute barely changes. If the entropies barely change, the same attribute $A_1$ still has the highest entropy, you choose the same attribute at the root, and the upper part of the tree stays identical across every bagged DT.

And that is why bagged DT is a bad choice for a bagging-based model: the trees are not independent, the ensemble does not get diversity, and the benefit of combining is largely lost. The fix is the subject of the next section: randomize the attribute choice, not just the tuples.

The mechanism, spelled out. Every tree is built by the same greedy rule: at the root, compute entropy over the whole attribute set and pick the attribute with the highest value. A bootstrap subset of 90 samples drawn from 100 keeps the large majority of each class — so the per-class proportions, and with them the entropy values, stay close to the full dataset's. The greedy rule picks the same root attribute in almost every bagged tree, then the same second attribute, and so on: the trees share their entire upper structure and differ only in deep, low-level splits. Visually, lay the trees side by side: the top two or three levels are identical copies.

The ensemble of Section 10.1 worked because independent errors cancel; identical upper structure means the errors are correlated — the trees tend to fail on the same samples, and the majority vote of nearly-identical trees is nearly a single tree. Bagging on trees is not wasted (it still reduces variance from the lower levels), but it falls far short of its potential, which is why the professor calls bagged DT a bad choice among bagging models.

10.6.4 Student Questions and Answers

10.7 Random Forest

10.7.1 Random Sampling of Tuples and Attributes

Random forest fixes the bagged DT problem with one small change. Bagged DT randomizes the tuples; random forest randomizes the tuples and the attributes. If we want the tree structure to change between subsets, random sampling must be done on attributes as well. With three attributes $A_1,A_2,A_3$, a given subset might take only two attributes, say $A_1$ and $A_2$. Then even if $A_3$ has the highest entropy, it cannot be chosen, so the structure of that tree changes. The next subset takes two different attributes, and so on. Random forest is essentially bagged DT — the same bagging structure — with the single modification that the bagging step does random sampling of tuples as well as attributes. This also closes the loop on the earlier cross-validation comparison: bagging does random sampling of tuples and attributes, which cross validation does not do.

Trace the difference on the entropy story of Section 10.6.3. Bagged DT fails because the greedy rule always sees the same three attributes and always picks the best one — $A_1$ at the root, every time. Random forest removes the choice: a subset that drew the attributes $\{A_1,A_2\}$ cannot even see $A_3$, so the root must come from $A_1$ or $A_2$ — a different tree shape than the subset that drew $\{A_2,A_3\}$, whose root comes from those two. The attribute randomization forces the trees to differ, and differing trees make different mistakes, which is exactly the independence the vote needs.

10.7.2 Structure and Parameters

Concretely, random forest is an ensemble algorithm: roughly 100 decision trees, each built from a random sub-selection of tuples and attributes, each subset trained on DT only, and the final result combined by majority voting. The number of trees is controlled by the number of estimators parameter (default 100 in scikit-learn's RandomForestClassifier). By randomizing both dimensions, random forest reduces the learning of noise and improves the generalization performance of the classification model.

Picture the structure: a forest — the name is literal. One hundred trees stand side by side, and no two are built from the same combination of tuples and attributes; each tree was grown on its own random view of the data. At prediction time the sample runs through all 100 trees, each tree votes, and the majority class wins. The default of 100 trees means 100 bootstrap subsets of the data and 100 independent (or nearly so) decision trees.

The two randomization dimensions do different jobs: tuple randomization keeps any single tree from memorizing the whole dataset, and attribute randomization keeps the trees from copying each other's structure. Both together give the vote what it needs — many trees whose errors do not align.

10.7.3 Properties of Bagging-Based Models

The properties of bagging-based models in general: they have higher generalization performance and perform better than normal (single) classifiers; they have overall low complexity; they are more robust to noise; and they are more robust to adversarial attacks. That last property is where the session turns next — what it means for a model to be attacked, and how the robustness of bagging-based models matters in practice.

Each property follows from the machinery already built:

• Higher generalization, better than a single classifier: the vote averages away individual trees' mistakes; as long as the trees are diverse and better than random, the ensemble error is below the average member error (the 0.06-vs-0.35 arithmetic of Section 10.1).
• Overall low complexity: no single tree needs to be elaborate — the ensemble does not rely on one deep, fragile tree but on the combined opinion of many simpler ones.
• More robust to noise: noise is memorized only when a single model can chase it; with every tree restricted to a random view of the data, no tree can chase the same noise in the same way, and the vote washes it out.
• More robust to adversarial attacks: a single model has one known boundary that an attacker can probe; a forest presents many randomized boundaries, so a small crafted change to one sample is far less likely to flip a whole forest's vote. This is precisely the claim the next section examines in detail.

10.7.4 Random Forest vs. Bagged DT

The one-sentence rule: when the base model is a decision tree, always prefer random forest — it is bagged DT with the one change that fixes bagged DT's core flaw, at essentially no extra cost.

10.8 Adversarial Robustness and Threat Modeling

10.8.1 The Malware Detection Setup

The detour starts with a concrete system: a malware detection system, which is essentially an antivirus. You give it a test file, and the model tells you whether the file contains malicious software — a malicious sample — or is benign, a good file. It is a binary classification problem. Suppose we choose a decision tree-based model. The dataset $D$ holds many samples, malicious and benign, described by multiple attributes $A_1,A_2,A_3$ in the hypothetical example. Using entropy, attribute $A_1$ scores highest and is chosen first, then the second, then the third, and a tree is built with these rules:

• If $A_1>10$: if $A_2>15$, the sample is malware; otherwise it is benign.
• If $A_1<10$ and $A_3=5$, the sample is malicious; otherwise it is benign.

The model is deployed at the customer end and gives about 99% accuracy. So far everything looks good.

Picture the deployed system: a user drops a file into the scanner, the file is measured on attributes $A_1,A_2,A_3$ (say, sizes of code sections and an API-call count), and the tree walks from the root $A_1>10$ down to a leaf that says "malware" or "benign." The tree is simple, interpretable, and 99% accurate on the samples it was tested on. Nothing in the standard evaluation — accuracy on a test set — has raised any alarm.

10.8.2 The Worked Evasion Walkthrough

Now consider the scenario from the perspective of a bad guy — a malware designer who wants to evade the detection system, fool it, and force a misclassification so that his malicious file is not detected as malware. There are two parties here, and they are playing a game: the malware designers and the anti-malware community. The anti-malware community builds the DT model; the malware community tries to fool it.

Assume the tree is known to the malware designer as well. A test sample arrives with the values $A_1=11$, $A_2=16$, $A_3=0$. Walking the tree: $A_1=11>10$, so we take the first path; $A_2=16>15$, so the model classifies the sample as malware. From the designer's perspective that is exactly wrong — he wants his sample to be classified as benign. His move is to modify the value of $A_2$ from 16 to 14. Now the path changes: $A_1=11>10$ still holds, but $A_2=14$ is not greater than 15, so the model predicts benign. One attribute value, changed by two units, flips the classification from malware to benign.

This is an adversarial attack on the malware detection system, and it is a general problem: any classification model — spam detection, malware detection, image classification, object detection, any domain — faces a two-party game. One party wants the model to perform well; the other party modifies samples in very small fashions to force misclassification. Real-world: think of the spam detector in Gmail. If an attacker understands the spam detector, he can modify one or two words in an email so that a spam email is classified as genuine — it is hard, but it can be done.

Why are trees so easy to attack in this way? A tree's decision boundary is made of axis-parallel thresholds — straight lines parallel to the axes of the attribute space. Crossing a single threshold (16 → 14 across the $A_2=15$ line) flips the outcome, and the attacker knows exactly which line to cross because the thresholds sit in plain sight. More complex models (deep networks, forests) have smoother, harder-to-read boundaries — the flip is still possible, but finding the right tiny change takes real work, which is part of why bagging-based models are credited with stronger adversarial robustness.

10.8.3 Why Accuracy Alone Is Not Enough

The lesson is direct: a model at 95% or 99% accuracy is not automatically ready for the customer end. The bad guy will break the model if he can, and a broken model is doomed. Before deploying, you must check the model's adversarial robustness — how well the model can protect itself, how well it performs when it is under attack. Adversarial robustness is significant for any classification model, whether it is a DT, an SVM, or a bagging-based model, and in any domain. It is a heavily researched, very hot area right now. Studying it properly means studying the broad domain of threat modeling of adversarial attacks, which examines attacks in a structured way — the four tuples below.

10.8.4 Threat Modeling: The Four Tuples

Threat modeling studies this domain in a very structured way, and it depends on four tuples:

1. What is the goal of the adversary (the attacker)?
2. What knowledge does the adversary have about the target system?
3. What capabilities does the adversary have?
4. What perturbations or modifications can the adversary make?

Each tuple has its own subdivisions, detailed next.

Think of the four tuples as the four questions a security review must answer before it can say anything useful about a system: what does the attacker want, what does he know, what can he do, and how much may he change? Change any one answer and the threat picture changes — an attacker who knows the tree (tuple 2) can stage the two-unit attack of Section 10.8.2; an attacker who does not know the tree must probe it blindly, a much harder game.

10.8.5 Attacker Goals

An attacker can have many goals; three are listed in the session. First, break the integrity of the system — an integrity attack: take a malicious sample and modify its feature vector, modify the sample a bit, so that it fools the detection system. Second, an availability attack: modify some sample so that the availability of the classification model goes down — the model becomes less available or less usable. Third, a privacy attack: steal information from the target system — about the sample, about the model, or about the data. These are possible goals; many more exist beyond the three listed.

• Integrity attack: the goal is to make the system accept the wrong answer — the malware walkthrough is the canonical example: malicious file in, benign verdict out. The system still works for everyone else; it has just been fooled.
• Availability attack: the goal is to make the system stop working or stop being usable — for example, flooding a detector with crafted samples that slow it down, or poisoning its training so its decisions become useless and it has to be taken offline.
• Privacy attack: the goal is to extract information the system was not meant to give away — the data used to train the model, the model's internals, or information about individual samples (such as the membership of a particular file or user in the training data).

10.8.6 Attacker Knowledge: White Box, Black Box, Gray Box

The second tuple is what the attacker knows about the target system, and it is defined on four sub-items: whether he knows the dataset the defender used (the complete dataset, a partial dataset, how many test samples, and so on), the feature vector (which features the model uses), the classification algorithm (which algorithm the antivirus uses), and the architecture of the classifier. These four give the box taxonomy:

• White box scenario: all four parameters are known to the attacker.
• Black box scenario: none of the four parameters is known.
• Gray box scenario: some partial parameters are known.

Depending on the attacker's knowledge, the attack scenarios differ.

The box taxonomy is a spectrum of knowledge, and each level changes the attack game. In the white box setting the attacker holds the full blueprint — dataset, features, algorithm, architecture — and can compute exactly where the boundaries sit, as in the Section 10.8.2 walkthrough, where the attacker simply read the tree. In the black box setting the attacker only has an oracle: submit a file, read the verdict, and reverse-engineer the boundary by trial and error — slower, noisier, but still feasible. The gray box sits in between: maybe the attacker knows the feature vector (the numbers a file is measured on) but not the algorithm, or knows the algorithm class but not its trained parameters. The right defense strategy depends on which box the realistic attacker occupies — assuming the worst case (white box) is the safe default in security practice.

10.8.7 Attacker Capabilities: Evasion and Poisoning

The third tuple is what the attacker can actually do. Capabilities include reading or modifying test samples, reading or modifying training samples, and reading or modifying the feature vector. Two attacks follow directly:

• Evasion attack: the attacker has the capability to modify test samples so that they force misclassification in the classification model. The malware walkthrough above is exactly an evasion attack — the test sample's $A_2$ was changed from 16 to 14.
• Poisoning attack: the attacker has the capability to modify training samples — the very samples used to build the classification model. This is the other very popular attack.

Evasion is an attack on the model's output; poisoning is an attack on the model's memory of the world. An evasion attack changes what the deployed model sees; a poisoning attack changes what it believes.

10.8.8 Perturbation Limitations

The fourth tuple bounds the modifications. Perturbation limitations describe what modifications the attacker can make: in an evasion attack, the modification is limited to test samples. There is also a cost associated with each modification made to a test or training sample, so the attacker tries to minimize the number of modifications, and various constraints can be placed on the perturbations. Real-world: this is why the tiny two-unit change in the malware example matters — small, cheap, hard-to-detect modifications are the realistic threat model.

Every modification has a budget. The attacker does not want to rewrite the whole file — a file that looks radically different from any known malware might be flagged for other reasons, and a modification that is too large is expensive to produce at scale. So the realistic attacker changes as little as possible: two units of one attribute, one word of an email, a few pixels of an image. The defender's constraints work in the opposite direction — bounding the perturbation (saying "only changes smaller than a threshold may not fool the model") is a standard way to define what "robust" even means, and enforcing detection of unusual modifications is a standard defense.

10.8.9 Why This Matters Now

Put the four tuples together and you have the complete picture of adversarial robustness, one of the hottest topics in classification algorithms today. The professor's advice to students: read about adversarial robustness and threat modeling of adversarial attacks — it is very hot and very relevant these days, and if you are choosing a thesis topic for the next semester or the one after, choose something from this domain rather than building a classification model, which has become routine. Also relevant: bagging-based models were earlier credited with being more robust to adversarial attacks than single models, so this area is where the ensemble ideas of the session connect to current research.

The four tuples compose into a single threat picture: who (goal) × what they know (knowledge) × what they can touch (capabilities) × how much they may change (perturbations). Any real system can be described by one cell of this table, and the session's malware walkthrough is one specific cell — a white-box attacker with test-sample modification rights and a two-unit budget. The same vocabulary is the language of current research papers, which is why the professor points students at the domain: the four-tuple framing is both the course summary and the research frontier.

Exam Guidance Summary

Homework From This Session

• Explain how the bagging structure reduces high bias. This is the open question from class: the full dataset is never exposed to any one model, so how does a group of data-restricted models avoid the underlearning that defines the high bias zone? Think it through — the professor will ask questions in class, and the resolution is expected in the next session.
• Read boosting. The next session continues with a new category of algorithms built on the boosting philosophy: AdaBoost, gradient boosting, and histogram boosting. Boosting is the designated homework topic.

Schedule and Assessment

• Quiz 2 has been announced and will come later this month, around the 20th of April, in the last roughly ten days of the month; the assignment will come around the same time. The exact date was not fixed in the session.
• The professor intends to ask questions from the homework in class, so the homework items above are worth preparing.

What to Focus On

Key Industry Applications

• Game-show lifelines (KBC, Kaun Banega Crorepati): the audience poll beats phone a friend — the same crowd logic used by ensembles. A single expert is one classifier; a crowd of voters is a committee, and decades of game-show history confirm the crowd's reliability.
• Antivirus and malware detection: real antivirus products are binary classifiers under constant attack. Evasion attacks modify one feature value to flip predictions, as in the $A_2:16\to 14$ example — a reminder that a deployed detector must be evaluated under attack, not just on test accuracy.
• Gmail's spam detector: an attacker who understands the spam detector can modify one or two words so that a spam email is classified as genuine — hard, but possible; the same perturbation logic as the malware walkthrough, in a consumer-facing setting.
• Image classification and object detection: these face the same two-party adversarial game as malware detection — tiny pixel-level modifications crafted to make a classifier misread an image, an active research area behind every deployed vision system.
• scikit-learn tooling: the tunables discussed in this session are all exposed in scikit-learn — min_samples_leaf and max_leaf_nodes on decision trees, max_features (set to none in the class discussion), and n_estimators on RandomForestClassifier and the bagging models (BaggingClassifier, default 10 estimators; RandomForestClassifier, default 100).
• Threat modeling of adversarial attacks: attacker goal, knowledge, capability, and perturbation limitations (white box / black box / gray box) form a structured vocabulary used by security teams and research papers alike — and the professor recommends this domain as a thesis direction: it is heavily researched and more interesting than yet another classification model.