Stanford CS230 | Autumn 2025 | Lecture 2: Supervised, Self-Supervised, & Weakly Supervised Learning

This lecture teaches decision trees, one of the most practical and understandable models in machine learning. A decision tree predicts an outcome by asking a sequence of simple questions about input features, like walking through a flowchart. You start at the root node, follow branches based on yes/no answers or threshold checks, and finish at a leaf node that outputs the prediction. The big idea is to choose questions that best separate the data into groups that are as pure as possible. Purity means that the examples in a group mostly share the same label, which makes the final decision more certain.

The lecture explains how trees choose the best questions using a concept called information gain, which is based on entropy. Entropy measures disorder: a mixed group of labels has high entropy, while a group where nearly all labels agree has low entropy. Information gain is the reduction in entropy after splitting on a feature. The model compares all possible splits and chooses the one that most reduces entropy, leading to more homogeneous child groups. A clear classroom example shows that splitting students by 'submitting assignments' better separates pass vs. fail than splitting by 'attending lectures.'

Two kinds of trees are covered: classification trees for categorical outcomes (like yes/no or types) and regression trees for continuous outcomes (like prices). The learning process, called recursive partitioning, keeps splitting the data into smaller subsets that are more uniform. This continues until stopping criteria are met, such as a maximum depth or a minimum number of samples in a leaf. These rules help control the complexity of the tree and reduce overfitting.

The lecture highlights strong advantages of trees: they are highly interpretable, handle both numerical and categorical data, and naturally capture non-linear relationships without feature scaling. However, it also addresses notable weaknesses: trees can overfit, can become complex and deep, and can be sensitive to small changes in data, producing different structures each time. To address these, pruning and constraints are recommended. Pruning removes weak branches that do not improve accuracy, and constraints limit depth or leaf size to keep the model simpler and more generalizable.

Beyond single trees, the lecture introduces ensemble methods that build on them. Random forests train many trees on different random samples and features, then average their predictions, making the final model more stable and accurate. Gradient boosting builds trees one after another, with each new tree focusing on fixing the errors the earlier trees made. Both methods often outperform a single tree when accuracy and robustness are priorities.

The target audience includes beginners and practitioners who want a clear and practical model they can explain to teammates or stakeholders. You should be comfortable with basic machine learning ideas like features and labels, but you do not need to know advanced math. After this lecture, you will be able to describe the structure of a decision tree, explain entropy and information gain in simple terms, understand the training process, and apply methods to prevent overfitting. You will also know when to choose a decision tree and when to use ensemble variants such as random forests or gradient boosting.

The lecture is structured from basic definitions and parts of a tree, to how trees choose splits, to learning via recursive partitioning, to advantages and disadvantages, and finally to practical fixes and ensemble improvements. Real-world examples (vision and glasses, student performance, ad clicks, house prices, healthcare, loans, and marketing) ground the theory in familiar contexts. The focus throughout is on clarity, interpretability, and practical decision-making about when and how to use tree-based models.

Overall Architecture and Learning Process

1. Data and Features: A decision tree starts with a dataset of examples. Each example has input features (things you know) and a target (the thing you want to predict). Features can be numbers (like age or income) or categories (like city or color). The target can be a class (for classification) or a number (for regression).

2. Nodes and Splits: The tree’s structure is made of nodes connected by branches. The root node holds all training data. At any decision node, the model tests one feature with a simple question. For numerical features, a question might be “is feature ≤ threshold?” For categorical features, a question might be “is feature in this set of categories?” Each answer sends the data down a different branch.

3. Entropy and Purity Intuition: Entropy is a measure of disorder in labels inside a node. If a node contains a mix of many classes, its entropy is high. If a node contains mostly the same class, its entropy is low. The goal of splitting is to reduce entropy by creating child nodes that are more uniform (homogeneous) in their labels. Lower entropy means more confident predictions.

4. Information Gain as Split Score: Information gain measures how much the entropy drops after you split. The algorithm tests many candidate splits and picks the one with the largest information gain. This is repeated at each node to grow the tree in a way that makes leaves as pure as possible. High information gain means the split creates clean, easy-to-predict groups.

5. Recursive Partitioning: Training is a loop. Start at the root with all data. Search for the best split by evaluating each feature (and possible thresholds for numeric features). Make the best split. Then, repeat the same process inside each child node on its local subset of data. Continue until stopping criteria are met. This is called recursive partitioning because you keep dividing the dataset into parts.

6. Leaf Predictions: In classification trees, a leaf typically predicts the majority class among the training samples in that leaf. In regression trees, a leaf predicts the average (or median) of the target values in that leaf. The leaf also sometimes stores the distribution of classes or the variance of targets, which can be used to estimate uncertainty.

7. Stopping Criteria: To avoid infinite growth and to control complexity, the tree stops growing when one or more rules are met. Common stopping rules include: maximum depth (do not grow beyond D levels), minimum samples per split (need at least N samples to attempt a split), and minimum samples per leaf (each leaf must hold at least L samples). Another stopping condition is when a node is already “pure enough,” meaning further splits do not significantly improve purity.

8. Overfitting Risk and Why It Happens: If you let a tree grow without limits, it can create tiny leaves that perfectly match quirks in the training data. This can include noise or rare patterns that do not repeat in new data. Such a tree memorizes rather than learns. As a result, it may perform poorly on the test set, even if it performs perfectly on the training set.

9. Pruning to Simplify: Pruning cuts back a grown tree to make it simpler and less likely to overfit. A simple approach is to evaluate branches on a validation set and remove those that do not help predictive performance. After pruning, the tree has fewer nodes, clearer rules, and better generalization. Pruning can be done in stages, checking each cut’s effect on accuracy.

10. Setting Constraints (Pre-Pruning): Instead of growing a big tree and cutting it back later, you can prevent overgrowth from the start. Set a maximum depth limit so the tree cannot ask too many questions. Set minimum samples per leaf to prevent tiny, fragile leaves. Set minimum samples per split to ensure splits are based on enough data. These constraints act like guardrails.

11. Handling Numerical vs. Categorical Features: For numerical features, the training algorithm typically tries several thresholds (like 20, 21, 22) to find the best cut. For categorical features, it can either check single categories or small groups (for example, city in {A, B}). The key is to evaluate how each candidate split changes entropy and information gain. Trees naturally handle both types without scaling.

12. Non-Linear Relationships: Trees form piecewise rules that change from branch to branch. This means the decision boundary can twist and turn to match complex patterns. For example, one branch might learn rules for young users and another for older users. No special math is required, because the structure does the shaping.

13. Model Instability (High Variance): A slight shuffle or a small data change can alter which split wins at the root. That early change cascades, producing a very different tree. This is called high variance. It makes single trees sensitive to the exact training sample. It’s one reason ensembles are so useful.

14. Random Forests (Variance Reduction by Averaging): A random forest makes many decision trees, each trained on a different random subset of the data (sampling with replacement) and often a random subset of features at each split. Because each tree sees a slightly different view, their errors are less correlated. The forest combines their outputs by averaging (regression) or majority vote (classification). This averaging reduces variance and improves robustness and accuracy over a single tree.

15. Gradient Boosting (Sequential Error Fixing): Gradient boosting builds trees one after the other. The first tree makes an initial set of predictions. The next tree focuses on the errors left by the first, and so on, gradually improving. The final prediction is a sum of the contributions of many small trees. This method is very powerful but requires care to avoid overfitting by controlling learning rate, tree depth, and number of trees.

16. Training Flow Step-by-Step (Single Tree):

• Step 1: Gather and clean your dataset with features and a target.
• Step 2: Choose whether you are doing classification or regression.
• Step 3: At the root, evaluate all features (and thresholds for numeric features) to compute information gain for each split.
• Step 4: Pick the split with the highest information gain and partition the data.
• Step 5: Recurse into each child node and repeat the process, respecting stopping criteria.
• Step 6: Assign predictions at leaves (majority class or average value).
• Step 7: Evaluate the tree on validation or test data.
• Step 8: If needed, prune or adjust constraints and retrain.

1. Evaluation and Monitoring: For classification trees, measure accuracy or other metrics (like precision/recall if you care about specific errors). For regression trees, check mean absolute error or mean squared error. Compare training vs. validation performance to spot overfitting. Keep an eye on leaf sizes and depth to ensure the model stays reasonable.

2. Debugging and Interpretability: When a prediction looks wrong, trace the path of conditions that led to the leaf. See which condition seems off or too strict. You can adjust constraints to encourage broader, more stable splits. Visualization helps explain choices to stakeholders and to discover data issues.

3. Practical Constraints Tuning: Start with a moderate max depth (for example, 4–8), a minimum samples per leaf (for example, 10–50 depending on dataset size), and a minimum samples per split slightly larger than the leaf size. If the model overfits, increase constraints (shallower depth, larger leaves). If it underfits, relax them (allow deeper trees). Use validation data to choose what works best.

4. Real-World Examples and Fit: Trees work well when rules are meaningful and the audience needs explanations. In healthcare, a tree can mirror clinical logic. In finance, it can outline why a loan looks risky. In marketing, it can show how user behaviors flow into an ad click. The structure directly supports compliance and audits.

5. Deployment Considerations: A trained tree is fast at inference because it only evaluates a handful of conditions per sample. It fits well into low-latency systems. Logging which path was taken can help with monitoring and fairness checks. Because trees are simple, they are easy to export and reproduce.

6. Limitations to Remember: Trees can still be too simple if you force them to be shallow, leading to underfitting. Without care, they can be too complex, leading to overfitting. They can be unstable across different samples. Using pruning, constraints, and possibly ensembles addresses these limits.

7. Ensembles in Practice: Random forests are great general-purpose models when you want strong accuracy without heavy tuning. Gradient boosting can achieve even higher accuracy, especially with careful settings. Both retain some interpretability through feature importance, though individual decisions are less transparent than a single tree. When full path-level explanations are required, a single pruned tree is best.

8. Summary of Data Flow: Input features enter at the root. A feature test sends the sample left or right. This repeats until a leaf returns the prediction. During training, the choice of each test is guided by information gain to make child nodes more pure. During inference, only one path is followed, making predictions fast and simple.

9. Tips and Warnings:

• Tip: Begin with a single interpretable tree to learn about the data, then consider ensembles for accuracy.
• Tip: Use clear stopping criteria from the start to avoid deep, brittle trees.
• Tip: Validate splits with cross-validation if dataset is small.
• Warning: Do not trust high training accuracy without checking test performance.
• Warning: A single top split can change with small data changes; consider forests for stability.
• Tip: Keep track of which features appear near the root; they often carry the most signal.

1. No Heavy Preprocessing Needed: Unlike models that need scaling or encoding in a specific way, trees can naturally handle different types of inputs. This reduces engineering time. However, ensure consistent and clean feature definitions. Good data hygiene still matters a lot.

2. Why Entropy and Information Gain Matter Conceptually: Even without exact formulas, the idea is straightforward. You want splits that make the children more certain than the parent. The bigger the drop in confusion, the better the question. This principle guides the entire learning process and explains why certain everyday questions (like 'did the student submit assignments?') are so powerful.

3. Choosing Between Trees and Ensembles: Use a single tree for maximum explainability and speed of understanding. Move to random forests when you need better accuracy and stability without giving up too much interpretability. Use gradient boosting when you need top performance and can spend time tuning and monitoring. Always validate to ensure you are not overfitting.

Decision trees turn data into a set of simple, readable rules that guide predictions from a root question to a leaf decision. They choose each question by maximizing information gain, which reflects how much a split reduces entropy, or confusion, in the labels. This recursive partitioning process continues until stopping criteria are met, producing a structure that is easy to visualize and explain. Trees handle both numerical and categorical features and naturally capture non-linear relationships, making them strong, practical baselines.

However, single trees can overfit by growing too deep and memorizing noise, and they can be unstable, with small data changes leading to very different structures. Pruning and constraints (like maximum depth and minimum samples per leaf) simplify trees and improve generalization. When accuracy and robustness are critical, ensemble methods shine: random forests reduce variance by averaging many diverse trees, and gradient boosting drives accuracy by sequentially fixing errors. Both approaches often outperform a single tree while preserving some interpretability through feature importance.

To practice, start by training a small classification tree on a simple dataset and visualize its structure. Experiment with splits that seem intuitive vs. those that actually give higher information gain. Then add constraints and compare validation performance before and after pruning. Finally, build a random forest and a gradient boosting model on the same task to feel the gains in stability and accuracy.

Next steps include learning more about model evaluation for different goals (like precision/recall in imbalanced classification), exploring fairness and bias checks along decision paths, and studying advanced tree ensembles. Consider scaling to larger datasets and monitoring model drift in production. The core message to remember is this: pick clear, high-information questions, prevent overfitting with sensible limits, and use ensembles when you need extra power. With these principles, tree-based methods become reliable tools for both understanding your data and making strong predictions.