PadhaikoAll subjects

Machine Learning Fundamentals (part 2: 4.5–4.8)

Artificial Intelligence (ENCT 351)

Open in the Padhaiko app

4.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).

Definition

Entropy, Information Gain, and Gini Impurity

For a dataset with classes where class has proportion :

  1. Shannon Entropy:

if all samples belong to one class (pure); bit for an equal binary split.

  1. 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.

  1. Gini Impurity (used by CART):

Lower Gini means purer subsets.

Support Vector Machines (SVM)

A Support Vector Machine finds the maximum-margin hyperplane separating classes and .

Definition

SVM Margin, Primal Optimization, and Kernels

The training points lying directly on the margin boundaries (, dual variables ) are the support vectors.

Large penalizes margin violations heavily (narrower margin, risk of overfitting); small allows wider margin and more tolerance to outliers.

AspectDecision TreeSupport Vector Machine (SVM)
Decision boundaryAxis-aligned orthogonal splits (piecewise rectangular)Maximum-margin hyperplane (or smooth nonlinear boundary via kernel)
InterpretabilityHigh (explicit IF-THEN rules)Low (especially with RBF kernel)
Feature scaling needed?NoYes (sensitive to feature magnitudes)
High-dimensional dataCan overfit without pruning / ensemblesStrong 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

  1. 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 ).

  1. 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.

  1. 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:

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.

Definition

Markov Decision Process (MDP) and Q-Learning

An RL task is formalized as a Markov Decision Process :

where is the learning rate, balancing exploration vs. exploitation (e.g., -greedy policy).

Comparison of Supervised, Unsupervised, and Reinforcement Learning
AspectSupervisedUnsupervisedReinforcement Learning
Feedback signalExact target labels None (features only)Delayed scalar rewards
GoalPredict outputs accuratelyDiscover clusters, manifolds, structureLearn an optimal policy maximizing return
Data assumptionTypically i.i.d. pairsUnlabelled i.i.d. samples Sequential agent-environment trajectories
ExamplesDecision Tree, SVMt-SNE, -means, PCAQ-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.

Definition

Energy Function, Free Energy, and Energy Score

  1. Energy function : Maps an input–output configuration to a scalar energy (lower energy = higher compatibility / higher plausibility; higher energy = unexpected or anomalous).
  2. Gibbs / Boltzmann distribution: Converts energies into probabilities using temperature :

where is the partition function.

  1. 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

Worked Out Examples

Example 4.4

4.4 (8 marks)

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:

Answer:

bits and bits.

Example 4.5

4.5 (6 marks)

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 :

Answer:

Updated .

Example 4.6

4.6 (6 marks)

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 :

Answer:

and . Since has significantly higher energy (), is flagged as OOD.

Exercises

Exercise: Decision Trees, SVM, t-SNE, RL, and Energy Indicators

Question 1

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:

Answer:

bits and .

Question 2

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:

Answer:

Support vectors anchor the margin, controls error tolerance, and kernels enable nonlinear separation. The margin width is .

Question 3

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.

Answer:

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.

Question 4

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:

Answer:

Semi-supervised learning leverages unlabelled data alongside few labels; RL optimizes long-term reward via interaction. Updated .

Question 5

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

Answer:

Energy indicators measure compatibility for OOD/confidence evaluation. Here and the free energy is .

← Machine Learning Fundamentals (part 1: 4.1–4.4)Neural Networks and Deep Learning Algorithms →