Machine Learning Fundamentals (part 2: 4.5–4.8)
Open in the Padhaiko app4.5 Supervised learning algorithm: Decision tree and support vector machine
In supervised learning, the algorithm learns a mapping from labelled examples .
Decision Trees
A decision tree predicts by testing attributes sequentially from the root node down internal decision nodes (each testing one attribute) along branches (attribute outcomes) to leaf nodes (class labels or continuous values).
Entropy, Information Gain, and Gini Impurity
For a dataset with classes where class has proportion :
- Shannon Entropy:
if all samples belong to one class (pure); bit for an equal binary split.
- Information Gain (used by ID3 / C4.5): Expected entropy reduction after splitting on attribute :
At each node, choose the attribute with the highest Information Gain.
- Gini Impurity (used by CART):
Lower Gini means purer subsets.
- Overfitting and pruning: Deep trees memorize noise. Prevent overfitting via pre-pruning (max depth, min samples per leaf) or post-pruning (grow full tree, then collapse branches that fail to improve validation accuracy), or combine many trees into Random Forests / Gradient Boosted Trees.
Support Vector Machines (SVM)
A Support Vector Machine finds the maximum-margin hyperplane separating classes and .
SVM Margin, Primal Optimization, and Kernels
- Functional and geometric margin: For linearly separable points with , the distance between the two canonical supporting hyperplanes () is the margin:
- Hard-margin SVM primal: Maximizing equals solving the convex quadratic program:
The training points lying directly on the margin boundaries (, dual variables ) are the support vectors.
- Soft-margin SVM (non-separable data): Adds slack variables and penalty :
Large penalizes margin violations heavily (narrower margin, risk of overfitting); small allows wider margin and more tolerance to outliers.
- Kernel trick: For nonlinear boundaries, replace dot products in the dual form with a kernel function without explicitly computing high-dimensional :
- Polynomial kernel:
- RBF (Gaussian) kernel:
| Aspect | Decision Tree | Support Vector Machine (SVM) |
|---|---|---|
| Decision boundary | Axis-aligned orthogonal splits (piecewise rectangular) | Maximum-margin hyperplane (or smooth nonlinear boundary via kernel) |
| Interpretability | High (explicit IF-THEN rules) | Low (especially with RBF kernel) |
| Feature scaling needed? | No | Yes (sensitive to feature magnitudes) |
| High-dimensional data | Can overfit without pruning / ensembles | Strong generalization via margin maximization |
4.6 Unsupervised learning algorithm: t-SNE
Unsupervised learning finds hidden structure (clusters, manifolds, low-dimensional embeddings) in unlabelled data .
t-SNE (t-Distributed Stochastic Neighbor Embedding) (van der Maaten & Hinton, 2008) is a nonlinear dimensionality reduction method built mainly for visualizing high-dimensional data in 2D or 3D while preserving local neighbourhood structure.
How t-SNE Works
- High-dimensional similarities ( and ): Model the probability that point picks as its neighbour under a Gaussian centered at :
The bandwidth is tuned automatically to match a user-chosen perplexity (effective number of nearest neighbours, typically ).
- Low-dimensional similarities (): Use a heavy-tailed Student's -distribution with 1 degree of freedom (Cauchy distribution) in the 2D/3D map :
Heavy tails prevent the crowding problem—moderately distant high-dimensional points can sit farther apart in 2D without crushing clusters together.
- Objective (KL divergence minimization): Optimize via gradient descent to minimize:
4.7 Semi supervised and reinforcement learning
Semi-Supervised Learning
When labelled examples are expensive (e.g., medical scans, speech transcripts) but unlabelled data is abundant, semi-supervised learning combines a small labelled set with a large unlabelled set under structural assumptions (smoothness, cluster assumption, manifold assumption).
Common techniques:
- Self-training (pseudo-labelling): Train a model on , predict on , add high-confidence predictions as pseudo-labels, and retrain iteratively.
- Consistency regularization: Require predictions on and a perturbed/augmented to agree.
- Graph-based label propagation: Connect nearby points in a similarity graph and propagate known labels across dense regions.
Reinforcement Learning (RL)
In Reinforcement Learning, an agent interacts sequentially with an environment to maximize expected cumulative discounted return, learning from scalar reward signals rather than labelled answers.
Markov Decision Process (MDP) and Q-Learning
An RL task is formalized as a Markov Decision Process :
- States () and Actions ().
- Transition probability: .
- Reward function: .
- Discount factor: , trading off immediate vs. future rewards in the return .
- Bellman Optimality Equation for action-value :
- Q-Learning update (model-free off-policy TD control):
where is the learning rate, balancing exploration vs. exploitation (e.g., -greedy policy).
| Aspect | Supervised | Unsupervised | Reinforcement Learning |
|---|---|---|---|
| Feedback signal | Exact target labels | None (features only) | Delayed scalar rewards |
| Goal | Predict outputs accurately | Discover clusters, manifolds, structure | Learn an optimal policy maximizing return |
| Data assumption | Typically i.i.d. pairs | Unlabelled i.i.d. samples | Sequential agent-environment trajectories |
| Examples | Decision Tree, SVM | t-SNE, -means, PCA | Q-Learning, Policy Gradient |
4.8 Model evaluation: Energy-based indicators
Evaluating ML models requires checking both predictive accuracy (via confusion matrix metrics like Accuracy, Precision, Recall, , ROC-AUC, or RMSE/MAE) and uncertainty / energy-based indicators that measure how compatible an input–output pair is with the learned data distribution.
Energy Function, Free Energy, and Energy Score
- Energy function : Maps an input–output configuration to a scalar energy (lower energy = higher compatibility / higher plausibility; higher energy = unexpected or anomalous).
- Gibbs / Boltzmann distribution: Converts energies into probabilities using temperature :
where is the partition function.
- Helmholtz Free Energy Score (for classification / OOD evaluation): Given a neural classifier with class logits (where ), the energy indicator of input is:
Why Energy-Based Indicators Are Used in Model Evaluation
- Out-of-Distribution (OOD) and anomaly detection: Unlike raw softmax confidence (which can be overconfident far from training data), the free energy score rises sharply for unfamiliar inputs because all logits remain small, cleanly separating in-distribution (ID, low energy) from out-of-distribution (OOD, high energy) samples using AUROC / FPR@95.
- Calibration and likelihood scoring: Negative log-likelihood (), cross-entropy, and perplexity () evaluate probabilistic calibration directly from the energy surface.
- Model selection indicators: AIC () and BIC () balance log-likelihood fit against parameter count , penalizing overly complex models.
Worked Out Examples
4.4
In a dataset of examples ( Positive, Negative), attribute Outlook has three values: Sunny (), Overcast (), and Rain (). Compute the parent entropy and the Information Gain .
Parent entropy for ( total):
Entropy of each child subset:
- Sunny (): .
- Overcast (): (pure!).
- Rain (): .
Weighted child entropy and Information Gain:
bits and bits.
4.5
An agent in state takes action , receives immediate reward , and lands in state where the current Q-table values are and . Given current , learning rate , and discount factor , compute the updated .
Identify maximum next-state Q-value:
Compute TD target and TD error:
Update :
Updated .
4.6
A 2-class classifier produces logits for an in-distribution sample and for an unfamiliar out-of-distribution sample . With temperature , compute the free energy score for both inputs and state which is flagged as OOD.
Energy score for :
Energy score for :
and . Since has significantly higher energy (), is flagged as OOD.
Exercises
Exercise: Decision Trees, SVM, t-SNE, RL, and Energy Indicators
A node in a binary decision tree holds positive and negative examples. Compute both its Shannon Entropy and its Gini Impurity .
Class proportions: and .
Shannon Entropy:
Gini Impurity:
bits and .
Explain the role of support vectors, slack parameter , and the kernel trick in Support Vector Machines. If an SVM hyperplane is with canonical margin planes , calculate the geometric margin width .
Concepts: Support vectors are the boundary points with that uniquely define and . Parameter trades margin width against classification errors in soft-margin SVMs. The kernel trick computes inner products implicitly to handle nonlinear boundaries.
Geometric margin width: Here , so . Thus:
Support vectors anchor the margin, controls error tolerance, and kernels enable nonlinear separation. The margin width is .
Explain how t-SNE constructs high-dimensional and low-dimensional similarity distributions, why it uses a Student's -distribution in the output space, and two cautions when interpreting t-SNE plots.
Mechanism: t-SNE converts high-dimensional pairwise distances into Gaussian conditional probabilities (controlled by perplexity) and low-dimensional distances into heavy-tailed Student's (1-dof / Cauchy) probabilities , minimizing .
Why Student's & cautions: The heavy tail prevents the crowding problem by allowing moderate distances in high-D to spread comfortably in 2D. Cautions: (1) inter-cluster distances and cluster sizes are not meaningful globally, and (2) results depend on perplexity and random seed.
t-SNE minimizes between high-D Gaussians and low-D Student- distributions to avoid crowding; global inter-cluster distances and cluster sizes should not be over-interpreted.
Distinguish between semi-supervised learning and reinforcement learning. Also perform one Q-learning update when , reward , , , and .
Comparison: Semi-supervised learning uses a small labelled dataset plus many unlabelled samples (e.g., pseudo-labelling) for static prediction; reinforcement learning learns sequential actions from scalar rewards in an MDP.
Q-learning update:
Semi-supervised learning leverages unlabelled data alongside few labels; RL optimizes long-term reward via interaction. Updated .
What are energy-based indicators in model evaluation? For two classes with energies and at temperature , find the Boltzmann probability and the free energy score .
Concept: Energy-based indicators score input compatibility (lower energy = closer to training distribution) and are used to evaluate calibration, anomaly/OOD detection, and likelihood quality.
Boltzmann probability ():
Free energy score: The partition sum is , so
Energy indicators measure compatibility for OOD/confidence evaluation. Here and the free energy is .