Foundations of Machine Learning

Machine learning allows computers to learn from experience rather than explicit developer rules. Formally, a program learns from experience $E$ with respect to a class of tasks $T$ and performance measure $P$, if its performance at tasks in $T$, as measured by $P$, improves with experience $E$.

Taxonomy of Machine Learning Systems

Algorithms are structured by their learning feedback:

1. Supervised Learning: trained on labeled data $(x_i, y_i)$ to map inputs to continuous (regression) or discrete (classification) targets.
2. Unsupervised: identifies patterns in unlabeled data (e.g., clustering).
3. Semi-Supervised: combines few labeled and many unlabeled samples.
4. Reinforcement: learns optimal actions via environment rewards.

Mathematical Formulation: ERM

Learning is formulated as empirical risk minimization. Given a hypothesis space $\mathcal{H}$ and a loss function $L(y, h(x))$, we solve for a hypothesis $\hat{h} \in \mathcal{H}$ that minimizes the average loss over the training set:

$\hat{h} = \arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^{n} L(y_i, h(x_i))$

Generalization and the Bias-Variance Trade-off

A model’s generalization error on unseen data is decomposed into three components:

• Bias: error due to overly simplistic assumptions, causing underfitting.
• Variance: error due to high sensitivity to small training set fluctuations, causing overfitting.
• Irreducible Noise: inherent variance in the data distribution.

Generalization is evaluated by training parameters on a training set and testing performance on an independent test set.

Example: Train-Test Splitting

The following example demonstrates splitting data and verifying shapes to ensure proper evaluation setup:

import numpy as np
from sklearn.model_selection import train_test_split

# Generate synthetic dataset
X = np.random.rand(100, 2)
y = np.random.randint(0, 2, size=100)

# 80/20 train-test split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

print(f"Train features shape: {X_train.shape}")
print(f"Test features shape: {X_test.shape}")

Train features shape: (80, 2)
Test features shape: (20, 2)

Exercise

Validate your understanding of generalization error trade-offs:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

Model Evaluation Metrics

Evaluating model performance requires task-specific metrics. Accuracy is misleading on imbalanced datasets: if a rare disease affects 1% of the population, a dummy classifier predicting “healthy” achieves 99% accuracy. Generalization error must be measured on independent data to evaluate utility.

Classification Metrics and Confusion Matrix

Binary classification performance is tabulated in a Confusion Matrix:

In this disease-screening example with 200 samples:

• Precision: positive prediction accuracy. Out of 90 predicted positive cases, 80 were correct. $\text{Precision} = \frac{\text{TP}}{\text{TP} + \text{FP}} = \frac{80}{80 + 10} \approx 0.889$
• Recall (Sensitivity): detection rate of actual positives. Out of 100 actual diseased patients, 80 were detected. $\text{Recall} = \frac{\text{TP}}{\text{TP} + \text{FN}} = \frac{80}{80 + 20} = 0.800$
• F1 Score: harmonic mean of precision and recall, penalizing extreme values. $F_1 = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} = 2 \times \frac{0.889 \times 0.8}{0.889 + 0.8} \approx 0.842$

ROC Curve and AUC

The ROC curve plots True Positive Rate (Recall) against False Positive Rate ($\text{FPR} = \frac{\text{FP}}{\text{TN} + \text{FP}}$) across decision thresholds. The Area Under the Curve (AUC) ranges from $0.5$ (random) to $1.0$ (perfect).

import os
import matplotlib.pyplot as plt
plt.figure(figsize=(5, 3.5))
plt.plot([0, 1], [0, 1], 'k--', label='Random (AUC=0.5)')
plt.plot([0, 0.25, 1], [0, 0.75, 1], 'b-', label='Model (AUC=0.75)')
plt.xlabel('FPR')
plt.ylabel('TPR')
plt.title('ROC Curve')
plt.legend()
plt.tight_layout()
plt.savefig(os.environ["LIBREUNI_OUTPUT"], format="svg")

Regression Metrics

While classification relies on counting correct assignments, regression predicts continuous values. Typical metrics include Mean Squared Error (MSE), Root Mean Squared Error (RMSE), and Mean Absolute Error (MAE).

A normalized evaluation metric is the Coefficient of Determination ($R^2$). The total variance in the data is captured by the Total Sum of Squares (SST). The variance explained by the model is the Sum of Squares due to Regression (SSR), and the unexplained variance is the Sum of Squared Errors (SSE).

$\text{SST} = \sum_{i=1}^n (y_i - \bar{y})^2$ $\text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2$ $\text{SSR} = \sum_{i=1}^n (\hat{y}_i - \bar{y})^2$

The $R^2$ score represents the proportion of variance explained by the model:

$R^2 = 1 - \frac{\text{SSE}}{\text{SST}}$

Validation Methods

Proper validation is crucial for an iterative ML workflow to prevent overfitting and ensure model generalization.

• Train-test split: Uses a portion of data for training and a held-out test set purely for final evaluation.
• Train-val-test split: Introduces a validation set. The training set updates model parameters, the validation set is used for evaluation and hyperparameter tuning, and the test set is reserved exclusively for final evaluation.
• Stratification: When splitting non-representative training data (especially imbalanced classification datasets), stratification ensures the class distribution in all splits mirrors the original dataset.

Cross-Validation

• Cross-validation (CV): Splits the training data into $k$ folds. The model trains on $k-1$ folds and validates on the remaining one, rotating iteratively. This provides a more robust estimate of performance than a single validation set.
• Leave-one-out cross-validation (LOO CV): An extreme form of CV where $k$ equals the number of samples ($N$). The model trains on $N-1$ samples and is validated on the single remaining point. While computationally expensive, it maximizes training data usage and provides unbiased performance estimates.

Example: Calculating Metrics

The following example demonstrates calculating classification metrics using a confusion matrix in scikit-learn:

from sklearn.metrics import precision_score, recall_score, f1_score

# Ground truth and predictions
y_true = [1, 0, 1, 1, 0, 1, 0, 0, 1, 0]
y_pred = [1, 0, 1, 0, 0, 1, 1, 0, 1, 0]

precision = precision_score(y_true, y_pred)
recall = recall_score(y_true, y_pred)
f1 = f1_score(y_true, y_pred)

print(f"Precision: {precision:.2f}")
print(f"Recall: {recall:.2f}")
print(f"F1 Score: {f1:.2f}")

Precision: 0.80
Recall: 0.80
F1 Score: 0.80

Exercise

Validate your knowledge of classification metric trade-offs:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Feature Engineering

Preprocessing transforms raw data into numerical matrices optimized for training.

Handling Missing Data and Outliers

Real-world datasets are rarely perfect. Data may be missing due to sensor failures, non-responses, or unrecorded events.

• Imputation: Replaces missing values using training statistics (e.g., mean, median, mode) or algorithms (e.g., kNN imputation).
• Removal: Dropping rows or irrelevant columns with too many missing values.

Handling Outliers

Outliers are extreme values that can significantly skew statistical measures and models like Linear Regression. Depending on the context, we can:

• Keep: If the outliers represent genuine, important anomalies (e.g., fraud detection).
• Delete: If the outliers are clearly errors or irrelevant.
• Impute: Treat outliers as missing data and impute a central value.
• Transform: Apply mathematical transformations to reduce their impact.

Boxplots are visual tools commonly used to identify outliers. They display the interquartile range (IQR) of data, with points falling outside $1.5 \times \text{IQR}$ typically flagged as outliers.

Skewed Data and Transformations

When data is highly skewed (e.g., income distribution with a long right tail), it can negatively impact model performance. We apply transformations to make the distribution more Gaussian-like:

• Logarithmic Transformation: $x' = \log(x)$ (useful for right-skewed data).
• Square Root Transformation: $x' = \sqrt{x}$.
• Box-Cox Transformation: A parameterized family of power transformations.

Handling String and Text Data

Models require numerical inputs. Categorical and textual data must be encoded:

• Ordinal Encoding: Maps categories to ordered integers (e.g., “Low”, “Medium”, “High” to 1, 2, 3).
• One-Hot Encoding: Creates separate binary columns for each category, preventing the model from assuming a false ordinal relationship between nominal categories (e.g., colors).
• Bag of Words (BoW): For free-text data, BoW creates a vocabulary of all unique words and represents each document as a vector indicating the frequency of each word.

Feature Scaling

Disparate scales bias distance-based models (KNN, SVM). We scale features via:

1. Min-Max Scaling: maps to $[0, 1]$: $x_{\text{scaled}} = \frac{x - x_{\text{min}}}{x_{\text{max}} - x_{\text{min}}}$.
2. Standardization: centers by mean and variance: $x_{\text{scaled}} = \frac{x - \mu}{\sigma}$.

Feature Selection and Correlation

Linear relationships are analyzed using a Correlation Matrix of Pearson coefficients in the range $[-1, 1]$. Below is an example mapping features from a real estate dataset:

The diagonal $1.00$ represents self-correlation. The coefficient $0.85$ indicates a strong positive relationship between size and bedrooms, while $-0.60$ shows a negative relationship with center distance (further houses tend to be smaller).

import os, pandas as pd, numpy as np, matplotlib.pyplot as plt
d = pd.DataFrame(np.random.randn(50, 3), columns=list('ABC'))
d['B'] = d['A'] * 0.7 + np.random.randn(50) * 0.3
plt.figure(figsize=(3.5, 2.8))
plt.imshow(d.corr(), cmap='coolwarm', vmin=-1, vmax=1)
plt.colorbar()
plt.xticks(range(3), d.columns)
plt.yticks(range(3), d.columns)
plt.tight_layout()
plt.savefig(os.environ["LIBREUNI_OUTPUT"], format="svg")

Example: Scaling and Encoding

The following example demonstrates categorical one-hot encoding and standardization:

import pandas as pd
from sklearn.preprocessing import StandardScaler, OneHotEncoder

df = pd.DataFrame({'Income': [50000, 120000, 30000], 'City': ['Paris', 'Berlin', 'Paris']})
scaled = StandardScaler().fit_transform(df[['Income']])
encoded = OneHotEncoder(sparse_output=False).fit_transform(df[['City']])

print("Scaled Income:", scaled.flatten().round(2))
print("Encoded City Categories:\n", encoded)

Scaled Income: [-0.46  1.39 -0.93]
Encoded City Categories:
[[0. 1.]
[1. 0.]
[0. 1.]]

Exercise

Evaluate your understanding of data preprocessing constraints:

Data Leakage

Preprocessing parameters must fit only on training data. Fitting on all data leaks test set statistics, inflating validation scores.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Machine Learning Workflows

Machine learning development is an iterative lifecycle accommodating data variability.

Lifecycle Architecture

The development lifecycle consists of sequential phases and feedback loops:

skinparam backgroundColor transparent
start
:Data Collection;
repeat
:Exploratory Data Analysis (EDA);
:Data Preprocessing & Cleaning;
:Model Training & Selection;
backward:Refine Features or Architecture;
repeat while (Meets Performance Goal?) is (no) not (yes)
:Final Validation;
:Model Deployment;
stop

Three Core Workflows

Developing machine learning systems involves three distinct architectural flows depending on the operational stage:

1. The Experimental Flow (Exploration & Prototyping)

Focused on data discovery. Data scientists work in interactive environments (e.g., notebooks) to query raw sources, perform Exploratory Data Analysis (EDA) to locate distributions and outliers, engineer prototype features, and evaluate baseline hypotheses.

2. The Production Pipeline (Continuous Training)

Focused on automation and scalability. Notebook experiments are codified into structured, reproducible pipelines:

1. Validation: load and validate incoming data schemas.
2. Preprocessing: fit and execute transformations.
3. Training: automate hyperparameter search.
4. Registry: evaluate targets and register valid binaries.

3. The Inference Flow (Batch vs. Real-time)

Deployment layouts depend on latency and throughput constraints:

• Batch: offline, scheduled predictions on large datasets, maximizing throughput.
• Real-time: on-demand predictions (e.g., via APIs) with minimal latency (under 100ms).

Example: Chaining Workflows via Pipelines

Scikit-learn Pipeline objects bundle preprocessing steps and estimators, preventing data leakage during validation:

import numpy as np
import pandas as pd
from sklearn.pipeline import Pipeline
from sklearn.impute import SimpleImputer
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression

df = pd.DataFrame({'x': [1.0, np.nan, 3.0, 4.0, 5.0]})
y = np.array([0, 0, 1, 1, 1])

# Chain imputation, scaling, and classifier
pipeline = Pipeline([
  ('imputer', SimpleImputer(strategy='median')),
  ('scaler', StandardScaler()),
  ('classifier', LogisticRegression())
])

pipeline.fit(df, y)
pred = pipeline.predict(df)
print("Predictions:", pred)
print("Pipeline steps:", [name for name, _ in pipeline.steps])

Predictions: [0 0 1 1 1]
Pipeline steps: ['imputer', 'scaler', 'classifier']

Exercise

Test your understanding of ML pipeline architectures:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Linear Regression and the Normal Equation

Linear Regression models a continuous target $y$ as a linear combination of input features $x$:

$\hat{y} = \theta^T \mathbf{x}$ where $\theta$ is the model parameter vector (including the intercept or bias $\theta_0$), and $\mathbf{x}$ is the observation vector containing the features (with $x_0 = 1$).

Simple vs. Multiple Linear Regression

• Simple Linear Regression: Models the relationship between a single feature $x_1$ and the target $y$. The equation simplifies to finding the best line with a specific slope ($\theta_1$) and intercept ($\theta_0$): $\hat{y} = \theta_0 + \theta_1 x_1$
• Multiple Linear Regression: Extends the concept to multiple features, where each feature gets its own weight (slope) in a multidimensional space.

Polynomial Regression

If the data is more complex than a simple straight line, we can still use linear models to fit nonlinear data. By adding powers of each feature as new features, we can train a linear model on this extended set of features. This is called Polynomial Regression. Despite fitting a curve to the data, it is still considered a linear model because the prediction is still a linear combination of the (now polynomial) features.

Parameter Estimation: Ordinary Least Squares

To train the model, we find parameters $\theta$ that minimize the Mean Squared Error (MSE) over the dataset:

$\text{MSE}(X, h_{\theta}) = \frac{1}{m} \sum_{i=1}^{m} (\theta^T \mathbf{x}^{(i)} - y^{(i)})^2$

The Closed-Form Normal Equation

To minimize the cost function, we solve analytically using the Normal Equation:

$\hat{\theta} = (X^T X)^{-1} X^T y$

• $X$: The design matrix of shape $(m, n+1)$ containing all features.
• $y$: The target vector of shape $(m, 1)$.

Multicollinearity and SVD

If the matrix $X^T X$ is singular (non-invertible) due to redundant, highly correlated features, standard inversion fails. Solvers compute the pseudo-inverse $X^+$ using Singular Value Decomposition (SVD) for stability.

Computational Complexity

Computing $(X^T X)^{-1}$ requires inverting an $(n+1) \times (n+1)$ matrix. The computational complexity is between $O(n^{2.4})$ and $O(n^3)$, making the Normal Equation expensive when the number of features is large.

Example: Computing the Normal Equation

The following example demonstrates computing model coefficients using the Normal Equation:

import numpy as np

# Generate synthetic linear data with random Gaussian noise
np.random.seed(42)
X = 2 * np.random.rand(5, 1)
y = 4 + 3 * X + np.random.randn(5, 1)

# Add bias column (x0 = 1) to build design matrix X_b
X_b = np.c_[np.ones((5, 1)), X]

# Solve analytically via normal equation: theta = (X^T * X)^(-1) * X^T * y
theta_best = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y)
print("Estimated coefficients [bias, weight]:")
print(theta_best.flatten())

Estimated coefficients [bias, weight]:
[3.9877443  3.40798606]

Exercise

Test your understanding of the analytical parameter estimation limits:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

Logistic Regression and Probability Estimation

Logistic Regression is a classifier that computes a weighted sum of inputs and maps the output to a probability between $0$ and $1$.

Probabilistic Formulation: The Sigmoid Function

The model feeds its linear output into the Sigmoid Function $\sigma(t)$:

$\hat{p} = \sigma(\theta^T \mathbf{x}) = \frac{1}{1 + e^{-\theta^T \mathbf{x}}}$

The prediction rule for binary classes is:

$\hat{y} = \begin{cases} 1 & \text{if } \hat{p} \ge 0.5 \\ 0 & \text{if } \hat{p} < 0.5 \end{cases}$

The prediction decision boundary is linear where $\theta^T \mathbf{x} = 0$.

import os
import numpy as np
import matplotlib.pyplot as plt
t = np.linspace(-6, 6, 200)
sig = 1 / (1 + np.exp(-t))
plt.figure(figsize=(5, 3.5))
plt.plot(t, sig, "b-", linewidth=2, label=r"$\sigma(t) = \frac{1}{1 + e^{-t}}$")
plt.axhline(y=0.5, color="gray", linestyle="--")
plt.axvline(x=0, color="gray", linestyle="--")
plt.title("Sigmoid Curve")
plt.grid(True, alpha=0.3)
plt.legend()
plt.tight_layout()
plt.savefig(os.environ["LIBREUNI_OUTPUT"], format="svg")

Parameter Optimization: Log Loss

To optimize parameters $\theta$, we minimize the convex Log Loss (binary cross-entropy):

$J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(\hat{p}^{(i)}) + (1 - y^{(i)}) \log(1 - \hat{p}^{(i)}) \right]$

It penalizes confident incorrect predictions with infinite cost (if $y=1$ and $\hat{p} \to 0$, then $-\log(\hat{p}) \to \infty$).

Multiclass Classification Strategies

While Logistic Regression is inherently a binary classifier, it can be extended to handle multiple classes (e.g., classifying images of digits 0-9) using specific strategies:

• One-vs-Rest (OVR) (also called One-vs-All): Trains $N$ separate binary classifiers for an $N$-class problem. Each classifier is trained to distinguish one specific class from all the rest combined. During prediction, the classifier that outputs the highest probability wins. This is the default approach in most ML libraries for logistic regression.
• One-vs-One (OVO): Trains a binary classifier for every possible pair of classes, resulting in $\frac{N \times (N-1)}{2}$ classifiers. For a new data point, all classifiers are run, and the class that wins the most duels is selected. OVO is particularly useful for algorithms that scale poorly with dataset size (like SVMs), because each classifier is only trained on the subset of data belonging to the two classes.

Alternatively, Softmax Regression (Multinomial Logistic Regression) generalizes Logistic Regression to natively support multiple classes by normalizing raw logits into a direct probability distribution across all classes without training multiple binary models.

Example: Logistic Regression Inference

The following example demonstrates calculating predictions using a trained Logistic Regression classifier:

import numpy as np
from sklearn.linear_model import LogisticRegression

# Create toy dataset
X = np.array([[1], [2], [3], [4], [5]])
y = np.array([0, 0, 0, 1, 1])

# Train model
clf = LogisticRegression()
clf.fit(X, y)

# Predict probabilities and classes
test_val = np.array([[3.5]])
prob = clf.predict_proba(test_val)
pred = clf.predict(test_val)

print(f"Probabilities [0, 1]: {prob[0].round(4)}")
print(f"Class: {pred[0]}")

Probabilities [0, 1]: [0.3235 0.6765]
Class: 1

Exercise

Test your knowledge of the Logistic Regression model boundary behavior:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Regularization Theory

Regularization restricts model complexity to prevent overfitting. It penalizes large model weights during training, forcing parameters to stay small.

Regularized Linear Regression Models

Three common regularized versions of linear regression modify the MSE cost function:

1. Ridge Regression (L2 Regularization)

Ridge Regression adds a penalty equal to the sum of squared weights to the cost function:

$J(\theta) = \text{MSE}(\theta) + \alpha \frac{1}{2} \sum_{i=1}^{n} \theta_i^2$

The hyperparameter $\alpha$ controls regularization strength. If $\alpha = 0$, it behaves like Ordinary Least Squares. Note that the bias term $\theta_0$ is not regularized.

2. Lasso Regression (L1 Regularization)

Lasso adds a penalty equal to the sum of absolute weights:

$J(\theta) = \text{MSE}(\theta) + \alpha \sum_{i=1}^{n} |\theta_i|$

Lasso regression performs feature selection by forcing less important feature weights to exactly $0$.

Geometric Intuition

L1 forms a diamond constraint boundary that tends to intersect coordinate axes at their corners, yielding sparse weights. L2 forms a spherical boundary, shrinking weights toward zero without setting them exactly to zero.

3. Elastic Net

Elastic Net combines Ridge and Lasso regularizations, controlled by a mix ratio $r$:

$J(\theta) = \text{MSE}(\theta) + r \alpha \sum_{i=1}^{n} |\theta_i| + (1 - r) \alpha \frac{1}{2} \sum_{i=1}^{n} \theta_i^2$

It acts as a compromise, stabilizing selection when features are highly correlated.

Example: Parameter Sparsity

The following example demonstrates how Lasso regularizes weights to zero compared to Ridge:

import numpy as np
from sklearn.linear_model import Ridge, Lasso

# Small continuous dataset for regression
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([2.1, 4.0, 5.9])

# Ridge Regression (L2 regularization) shrinks weights close to zero
ridge = Ridge(alpha=1.0)
ridge.fit(X, y)

# Lasso Regression (L1 regularization) can shrink weights exactly to zero
lasso = Lasso(alpha=1.0)
lasso.fit(X, y)

print(f"Ridge weights: {ridge.coef_}")
print(f"Lasso weights: {lasso.coef_}")

Ridge weights: [0.44303797 0.44303797]
Lasso weights: [0.8 0. ]

Exercise

Test your understanding of regularized cost functions:

Early Stopping

Early stopping is a regularization technique where validation error is monitored during iterative training. We stop training as soon as the validation error reaches a minimum and starts to increase.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Naive Bayes Classifier

Naive Bayes is a probabilistic classifier based on Bayes’ Theorem. It assumes conditional independence between features given the class.

Probabilistic Foundation: Bayes’ Theorem

We predict the class probability $P(C_k | \mathbf{x})$ for an input feature vector $\mathbf{x} = [x_1, x_2, \dots, x_d]^T$ using:

$P(C_k | \mathbf{x}) = \frac{P(\mathbf{x} | C_k) P(C_k)}{P(\mathbf{x})}$

The Conditional Independence Assumption

Estimating $P(\mathbf{x} | C_k)$ directly requires massive datasets. The Naive Bayes classifier assumes that features are conditionally independent given the class:

$P(\mathbf{x} | C_k) = \prod_{j=1}^{d} P(x_j | C_k)$

Thus, the classification rule predicts the class that maximizes the numerator:

$\hat{y} = \arg\max_{k} P(C_k) \prod_{j=1}^{d} P(x_j | C_k)$

The “Naive” Limitation

Features are rarely independent in practice, making the model “naive” (e.g., “machine” and “learning” are highly correlated), but it performs remarkably well on tasks like spam filtering.

Generative vs. Discriminative

Naive Bayes is a generative model because it models the joint distribution $P(\mathbf{x}, C_k) = P(\mathbf{x} | C_k) P(C_k)$, unlike discriminative models (e.g., Logistic Regression) which model $P(C_k | \mathbf{x})$ directly.

Laplace Smoothing

If a feature value $x_j$ never occurs with class $C_k$ in training, the probability $P(x_j | C_k)$ is $0$. Since we multiply feature probabilities, this zeroes out the entire class probability. We prevent this using Laplace Smoothing:

$P(x_j = v | C_k) = \frac{count(x_j = v, C_k) + \alpha}{count(C_k) + \alpha \cdot N_j}$

where $N_j$ is the number of possible values for $x_j$, and $\alpha$ is the smoothing parameter.

Example: Classification with Gaussian Naive Bayes

The following example demonstrates training a Gaussian Naive Bayes model on continuous features:

import numpy as np
from sklearn.naive_bayes import GaussianNB

# Continuous features: [height, weight]
X = np.array([[180, 80], [160, 55], [175, 75], [150, 50]])
y = np.array([0, 1, 0, 1]) # 0: Male, 1: Female

model = GaussianNB()
model.fit(X, y)

# Classify unknown sample
sample = [[165, 60]]
prob = model.predict_proba(sample)
print(f"Probabilities [Male, Female]: {prob[0]}")

Probabilities [Male, Female]: [0.00392348 0.99607652]

Exercise

Test your understanding of the independence assumption:

Prior Probabilities

Priors $P(C_k)$ reflect baseline class rates, acting as regularizers that bias predictions toward dominant classes.

References & Further Reading

• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

k-Nearest Neighbors (kNN) is a non-parametric, instance-based learning algorithm. Unlike parametric models such as linear regression or logistic regression, kNN does not explicitly learn a mapping function from the training data during a training phase. Instead, it memorizes the training dataset and performs classification or regression on the fly when a new data point is presented. Because the computational work is deferred until the prediction phase, kNN is often referred to as a “lazy learning” algorithm.

The core principle of kNN is that similar data points exist in close proximity. To classify a new, unseen data point, the algorithm identifies the $k$ training examples that are closest to it in the feature space and assigns a label based on the majority class among those neighbors.

Classification of New Data Points

The kNN algorithm for classification follows these steps:

1. Calculate Distances: Compute the distance between the new data point and all points in the training dataset.
2. Identify Nearest Neighbors: Select the $k$ training points with the smallest calculated distances.
3. Determine the Majority Class: Count the class labels among the $k$ nearest neighbors. The new data point is assigned the class that appears most frequently (majority vote). In the case of a tie, the algorithm may resolve it randomly or weight the votes by the inverse of their distances.

Distance Metrics

The choice of distance metric fundamentally defines what it means for two data points to be “close.” Depending on the data type and dimensionality, different metrics are appropriate.

Euclidean Distance

The most common distance metric for continuous variables is the Euclidean distance, which represents the straight-line distance between two points in Euclidean space. For two vectors $\mathbf{x} = (x_1, x_2, \dots, x_n)$ and $\mathbf{y} = (y_1, y_2, \dots, y_n)$, the Euclidean distance is defined as:

$d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$

Manhattan Distance

Manhattan distance (also known as $L_1$ norm or city block distance) calculates the distance between two points by summing the absolute differences of their Cartesian coordinates. It is often preferred in high-dimensional spaces because it is less susceptible to the curse of dimensionality than Euclidean distance.

$d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} |x_i - y_i|$

Minkowski Distance

Minkowski distance is a generalized metric that encompasses both Euclidean and Manhattan distances. It introduces a parameter $p$:

$d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}}$

When $p=1$, it is equivalent to the Manhattan distance, and when $p=2$, it reduces to the Euclidean distance.

The Hyperparameter $k$

The parameter $k$ represents the number of nearest neighbors considered during the voting process. It is a crucial hyperparameter that dictates the complexity and generalization capability of the model.

Impact of $k$

• Small $k$ (e.g., $k=1$): The model is highly sensitive to noise in the training data. The decision boundary becomes complex and jagged, leading to low bias but high variance (overfitting). With $k=1$, a new data point is assigned the exact class of its single closest neighbor.
• Large $k$: The voting process incorporates a broader region of the feature space, resulting in smoother, more robust decision boundaries. However, if $k$ is too large, the model may suffer from high bias (underfitting), as it risks simply predicting the majority class of the entire dataset regardless of the specific input location.

Even or Odd $k$

In binary classification problems (where there are only two possible classes), it is critical to choose an odd value for $k$. If an even $k$ is selected, there is a possibility of a tie in the majority voting process. An odd $k$ inherently prevents tied votes, ensuring a definitive class assignment for every new data point. For multi-class problems, ties can still occur with an odd $k$, but they are significantly less frequent.

The Importance of Scaling

kNN is highly sensitive to the scale of the features. Because the algorithm relies entirely on distance calculations, features with larger ranges will disproportionately influence the final distance metric.

Consider a dataset with two features: age (ranging from 18 to 80 years) and income (ranging from $20,000 to $150,000). If the Euclidean distance is calculated without scaling, the income feature will completely dominate the distance computation, rendering the age feature effectively irrelevant.

To prevent this, it is mandatory to normalize or standardize the data before applying kNN.

• Min-Max Scaling (Normalization): Rescales features to a fixed range, typically $[0, 1]$.
• Standardization (Z-score scaling): Transforms features to have a mean of 0 and a standard deviation of 1.

By ensuring all features contribute equally to the distance calculation, scaling significantly improves the performance and reliability of the kNN algorithm.

Exercise

Evaluate your understanding of kNN properties:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Support Vector Machines

A Support Vector Machine (SVM) is a supervised algorithm that finds the decision boundary (hyperplane) that maximizes the margin between classes.

Margin Maximization and Slack Variables

In linear classification, we find a hyperplane $w^T x + b = 0$ that separates classes.

Primal Optimization Problem (Soft Margin)

To allow for noise and misclassifications, we introduce slack variables $\xi_i \ge 0$. The objective minimizes:

$\min_{w, b, \xi} \frac{1}{2} ||w||^2 + C \sum_{i=1}^{m} \xi_i$

subject to:

$y^{(i)} (w^T x^{(i)} + b) \ge 1 - \xi_i \quad \text{and} \quad \xi_i \ge 0$

The parameter $C$ controls the trade-off: a small $C$ allows more margin violations (regularized), while a large $C$ forces a hard margin (sensitive to noise).

The Dual Formulation and the Kernel Trick

By reformulating the optimization problem using Lagrange multipliers, we express the decision function using inner products of training instances:

$h(x) = \sum_{i=1}^{m} \alpha_i y^{(i)} (x^{(i)} \cdot x) + b$

The coefficients $\alpha_i$ are non-zero only for instances on the margin boundaries. These are the Support Vectors that determine the decision boundary.

The Kernel Trick

The kernel trick replaces the dot product with a kernel function $K(x^{(i)}, x^{(j)})$, avoiding mapping data to high-dimensional spaces explicitly.

• Polynomial Kernel: $K(x, z) = (\gamma x^T z + r)^d$
• Radial Basis Function (RBF) Kernel: $K(x, z) = \exp(-\gamma ||x - z||^2)$

The parameter $\gamma$ controls the RBF width: a larger $\gamma$ makes the boundary narrower and more irregular, fitting specific instances.

Example: Non-Linear Kernel SVM

The following example demonstrates training an SVM with an RBF kernel:

import numpy as np
from sklearn.svm import SVC

# Non-linear XOR problem dataset
X = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
y = np.array([0, 0, 1, 1])

# Radial Basis Function (RBF) kernel SVM handles non-linear boundaries
clf = SVC(kernel='rbf', C=10.0, gamma=1.0)
clf.fit(X, y)

print(f"Predictions: {clf.predict(X)}")
print(f"Number of Support Vectors per class: {clf.n_support_}")

Predictions: [0 0 1 1]
Number of Support Vectors per class: [2 2]

Exercise

Test your understanding of SVM margin constraints:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

Decision Trees and the CART Algorithm

Decision Trees are non-parametric models that recursively partition the feature space, predicting targets using simple hierarchical decision rules.

Recursive Induction: The CART Algorithm

The CART algorithm builds binary trees by searching for a feature $k$ and threshold $t_k$ that minimize the weighted impurity of child nodes.

$J(k, t_k) = \frac{m_{\text{left}}}{m} I_{\text{left}} + \frac{m_{\text{right}}}{m} I_{\text{right}}$

where $I$ represents the impurity of a node, and $m$ is the number of samples.

Split Selection Logic

The CART algorithm is greedy: it searches for the best split at the current step rather than evaluating combinations globally. It does not guarantee finding the globally optimal tree.

Impurity Measures

• Gini Impurity: Probability of a random element being misclassified. $G = 1 - \sum_{i=1}^{C} p_i^2$
• Entropy: Quantifies node disorder or uncertainty. $H = -\sum_{i=1}^{C} p_i \log_2(p_i)$

For regression trees, CART minimizes Mean Squared Error (MSE), and leaves predict the average target value.

Regularization

Without constraints, decision trees grow until leaves are pure, causing overfitting. We regularize using stopping hyperparameters:

• max_depth: Limits depth.
• min_samples_split: Minimum samples required to split a node.
• min_samples_leaf: Minimum samples a leaf must contain.

skinparam backgroundColor transparent
rectangle "Is Feature X <= 2.5?" as Root
rectangle "Leaf: Class A" as Left
rectangle "Leaf: Class B" as Right
Root --> Left : Yes
Root --> Right : No

Example: Computing Impurity

The following example demonstrates calculating Gini impurity and Information Gain:

import numpy as np

# Calculate Gini Impurity: 1 - sum(p_i^2) for class probabilities p_i
def gini(labels):
  _, counts = np.unique(labels, return_counts=True)
  probs = counts / len(labels)
  return 1 - np.sum(probs**2)

# Unsplit parent node containing mixed classes
parent = [0, 0, 1, 1, 1, 1]

# Left and right child nodes after split
left = [0, 0]
right = [1, 1, 1, 1]

print(f"Parent Gini: {gini(parent):.4f}")
print(f"Left Child Gini: {gini(left):.4f}")
print(f"Right Child Gini: {gini(right):.4f}")

Parent Gini: 0.4444
Left Child Gini: 0.0000
Right Child Gini: 0.0000

Exercise

Test your understanding of Decision Tree scaling requirements:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Ensemble Learning and Random Forests

Ensemble methods combine predictions from multiple base models to build a stronger predictor with improved generalization.

Voting Classifiers

Ensemble models aggregate individual predictions using different consensus rules:

• Hard Voting: predicts the class that receives the absolute majority of votes from the base estimators.
• Soft Voting: averages the predicted class probabilities across all estimators, prioritizing confident predictions. This requires all estimators to support probability calculation.

Bagging and Pasting

Rather than using diverse algorithms, we can train multiple instances of the same base algorithm on different random subsets of the training set to construct homogeneous ensembles:

• Bagging (Bootstrap Aggregating): sampling is performed with replacement, allowing the same data point to be selected multiple times across different subsets.
• Pasting: sampling is performed without replacement, ensuring each subset contains unique data points.

Out-of-Bag (OOB) Evaluation

With bagging, statistical probability dictates that about 37% of the training instances are never sampled for any single estimator. These are known as Out-of-Bag (OOB) instances. Evaluating the ensemble’s performance on these OOB instances provides an unbiased validation score without requiring a separate validation dataset.

Random Forests

A Random Forest is an ensemble of decision trees trained via bagging. Tree splits are evaluated on random feature subsets to reduce estimator correlation and variance.

Example: Ensemble Voting Classifier

The following example demonstrates building a Voting Classifier:

from sklearn.ensemble import VotingClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=100, noise=0.30, random_state=42)

log_clf = LogisticRegression()
tree_clf = DecisionTreeClassifier()

voting_clf = VotingClassifier(
  estimators=[('lr', log_clf), ('dt', tree_clf)],
  voting='soft'
)
voting_clf.fit(X, y)
print(f"Ensemble score: {voting_clf.score(X, y):.2f}")

Ensemble score: 0.94

Exercise

Test your understanding of bootstrap aggregation:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

Gradient Boosting Systems

Boosting methods train predictors sequentially, with each model attempting to correct its predecessor’s errors.

AdaBoost (Adaptive Boosting)

AdaBoost focuses on misclassified instances by adjusting their weights:

1. Initialize all instance weights to $w^{(i)} = 1/m$.
2. Train a base predictor and calculate its weighted error rate $r_j$.
3. Compute the predictor weight $\alpha_j = \eta \log((1-r_j)/r_j)$, where $\eta$ is the learning rate.
4. Update instance weights: increase weights for misclassified instances and decrease them for correctly classified instances.
5. Normalize weights and repeat.

Gradient Boosting

Unlike AdaBoost, Gradient Boosting trains models on the residual errors of the previous predictor.

For regression with squared error loss, the target for predictor $h_t(x)$ is the residual:

$r_t^{(i)} = y^{(i)} - \sum_{k=1}^{t-1} \eta h_k(x^{(i)})$

The final prediction aggregates all estimators:

$\hat{y}^{(i)} = \sum_{t=1}^{T} \eta h_t(x^{(i)})$

In classification, Gradient Boosting fits new trees to minimize the pseudo-residuals of the loss function, which are the negative gradients of the loss.

Histogram-Based Gradient Boosting

Modern implementations (like XGBoost, LightGBM, and scikit-learn’s HistGradientBoostingRegressor) bin continuous features into integer bins (e.g., 256 bins). This reduces the computational complexity of finding splits from $O(300 \times n \log n)$ to $O(300 \times n \text{ bins})$, speeding up training on large datasets.

Example: Residual Learning

The following example demonstrates fitting successive decision trees to residual errors:

import numpy as np
from sklearn.tree import DecisionTreeRegressor

# Target function: quadratic with noise
X = np.random.rand(50, 1) - 0.5
y = 3*X[:, 0]**2 + 0.05 * np.random.randn(50)

# Model 1
tree_reg1 = DecisionTreeRegressor(max_depth=2)
tree_reg1.fit(X, y)

# Train on residuals
y2 = y - tree_reg1.predict(X)
tree_reg2 = DecisionTreeRegressor(max_depth=2)
tree_reg2.fit(X, y2)

# Combined prediction
sample = [[0.2]]
pred = tree_reg1.predict(sample) + tree_reg2.predict(sample)
print(f"Gradient Boosted prediction: {pred[0]:.4f}")

Gradient Boosted prediction: ...

Exercise

Test your understanding of the boosting process:

Shrinkage and Estimator Limits

In gradient boosting, learning rate $\eta$ is also known as shrinkage. A low learning rate (e.g., $\eta = 0.01$) paired with more trees allows the model to converge smoothly, increasing generalization performance on tabular data.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

High-dimensional spaces suffer from the Curse of Dimensionality: points are sparse, distances become uniform, and models overfit. Dimensionality reduction compresses features, removes redundancies, and enables visualization. Principal Component Analysis (PCA) projects data onto a lower-dimensional subspace while maximizing variance preservation.

Matrix Factorization: SVD

PCA identifies the axis that accounts for the largest amount of variance in the training set. It finds principal components using Singular Value Decomposition (SVD), which decomposes the centered design matrix $X$ into three matrices:

$X = U \Sigma V^T$

The matrix $V$ contains the unit vectors that define the principal components:

$V = [\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n]$

To project the training set down to $d$ dimensions, we multiply the design matrix by the matrix $V_d$ containing the first $d$ principal components:

$X_{d\text{-proj}} = X V_d$

The Eigendecomposition Approach

Alternatively, PCA can be computed by performing an eigendecomposition on the Sample Covariance Matrix of the centered data. The covariance matrix $C$ captures the variance and correlation of features:

$C = \frac{1}{m-1} X^T X$

By solving the characteristic equation, we decompose $C$ into its eigenvalues ($\lambda$) and eigenvectors ($\mathbf{v}$):

$C \mathbf{v} = \lambda \mathbf{v}$

• The Eigenvectors represent the directions of the principal components (equivalent to the columns of $V$ from SVD). They are orthogonal to each other.
• The Eigenvalues represent the magnitude of variance captured along each corresponding principal component.

The Trace of the covariance matrix (the sum of its diagonal elements) is equal to the total variance in the dataset. Consequently, the sum of all eigenvalues is also equal to the total variance, allowing us to compute the proportion of variance captured by any single principal component $i$ as $\frac{\lambda_i}{\sum \lambda}$.

Explained Variance Ratio

The explained variance ratio indicates the proportion of the dataset’s variance that lies along each principal component. We use it to choose the number of dimensions $d$ that preserve a target percentage of variance (e.g., 95%).

Incremental PCA

For large datasets that do not fit in memory, we use Incremental PCA (IPCA). The algorithm splits the training set into mini-batches and feeds them one by one, enabling dimensionality reduction on out-of-core data.

Example: Computing PCA

The following example demonstrates projecting data using PCA and calculating the explained variance ratio:

import numpy as np
from sklearn.decomposition import PCA

# Synthetic 3D dataset
X = np.random.randn(10, 3)

# Project to 2D
pca = PCA(n_components=2)
X_2d = pca.fit_transform(X)

print(f"Reduced shape: {X_2d.shape}")
print(f"Explained variance ratio: {pca.explained_variance_ratio_}")

Reduced shape: (10, 2)
Explained variance ratio: [...]

Exercise

Evaluate your understanding of PCA projection logic:

Choosing the Number of Components

Instead of selecting an arbitrary number of dimensions, we look at the cumulative explained variance plot. We choose the number of principal components that capture a target percentage (typically 95%) of the total variance. This ensures that we discard noise while preserving the essential geometric structure of the original data.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Clustering Algorithms

Clustering partitions unlabeled data into groups (clusters) of similar instances.

Centroid-Based: K-Means

K-Means partitions data into $K$ clusters by minimizing the Within-Cluster Sum of Squares (Inertia):

$J = \sum_{j=1}^{K} \sum_{x \in C_j} ||x - \mu_j||^2$

Lloyd’s Algorithm

1. Initialize $K$ centroids $\mu_j$ randomly (or using K-Means++).
2. Assign each instance to its closest centroid: $c^{(i)} = \arg\min_j ||x^{(i)} - \mu_j||^2$.
3. Update centroids: $\mu_j = \frac{1}{|C_j|} \sum_{x \in C_j} x$.
4. Repeat steps 2-3 until convergence.

K-Means++ initialization spreads centroids far apart during initialization, reducing the risk of converging to sub-optimal local minima.

Density-Based: DBSCAN

DBSCAN groups points based on local density, classifying them into three categories:

• Core Points: At least MinPts neighbors within a radius of $\epsilon$.
• Border Points: Not core points, but within $\epsilon$ of a core point.
• Noise Points: Neither core nor border points.

DBSCAN detects the number of clusters automatically and handles outliers effectively by marking them as noise.

Hierarchical (Agglomerative) Clustering

Agglomerative clustering is a “bottom-up” approach. It begins by treating every single data point as its own cluster. It then iteratively merges the closest pairs of clusters until all points are merged into a single root cluster.

• Dendrogram: This merging process is visualized as a tree-like diagram called a dendrogram. By analyzing the vertical height of the branches in the dendrogram, one can decide on an optimal number of clusters by cutting the tree horizontally.
• WCSS: Within-Cluster Sum of Squares can also be used as a metric to evaluate cluster cohesion.

Linkage Criteria

The decision of which clusters to merge depends on the defined distance (linkage) between clusters:

• Single Linkage: The distance between two clusters is defined by their two closest members.
• Complete Linkage: The distance is defined by their two furthest members.
• Average Linkage: The average distance between all points in the two clusters.
• Ward’s Linkage: Merges clusters in a way that minimizes the total variance within all clusters.

Probabilistic: Gaussian Mixture Models

Gaussian Mixture Models (GMM) represent clusters as covariance ellipsoids rather than spheres, allowing for varying cluster shapes. GMM uses the Expectation-Maximization (EM) algorithm to assign “soft clustering” probabilities.

Example: Comparing Algorithms

The following example demonstrates clustering using scikit-learn:

from sklearn.cluster import KMeans, DBSCAN
from sklearn.datasets import make_moons

# Synthetic crescent-shaped data
X, _ = make_moons(n_samples=100, noise=0.05, random_state=42)

# K-Means (spherical clusters, K centroids)
kmeans = KMeans(n_clusters=2, n_init='auto')

# DBSCAN (density-based clusters)
dbscan = DBSCAN(eps=0.3, min_samples=5)

# Predict cluster labels
print(f"K-Means cluster labels: {set(kmeans.fit_predict(X))}")
print(f"DBSCAN cluster labels: {set(dbscan.fit_predict(X))}")

K-Means cluster labels: {0, 1}
DBSCAN cluster labels: {0, 1}

Exercise

Test your understanding of clustering paradigms:

Selecting the Number of Clusters

Choosing the parameter $K$ in K-Means is challenging. We use two main validation methods:

• The Elbow Method: Plotting inertia vs. $K$ and finding the point where the rate of decrease drops.
• Silhouette Analysis: Computing the average silhouette coefficient for all points. A higher average coefficient indicates well-defined, dense clusters.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Optimization

Training models requires finding parameters $\theta$ that minimize a cost function $J(\theta)$ by updating them iteratively.

Stochastic Gradient Descent (SGD)

SGD updates parameters using the gradient calculated from a single random instance (or a mini-batch) at each step:

$\theta \leftarrow \theta - \eta \nabla_{\theta} J(\theta; x^{(i)}, y^{(i)})$

While computationally efficient, SGD’s updates can oscillate, slowing convergence.

Momentum and Nesterov Accelerated Gradient

Momentum accelerates SGD by adding a fraction $\beta$ of the previous update vector $m$, acting like a physical ball rolling down a hill:

$m \leftarrow \beta m + \eta \nabla_{\theta} J(\theta)$ $\theta \leftarrow \theta - m$

NAG calculates the gradient ahead of the current position ($J(\theta - \beta m)$) to stabilize convergence.

Adaptive Learning Rates

Adaptive algorithms adjust the learning rate per parameter based on historical gradients:

• RMSProp: Decays past squared gradients to focus on recent updates. $s \leftarrow \beta s + (1 - \beta) (\nabla_{\theta} J(\theta))^2$ $\theta \leftarrow \theta - \frac{\eta}{\sqrt{s + \epsilon}} \nabla_{\theta} J(\theta)$
• Adam (Adaptive Moment Estimation): Tracks first (mean) and second (variance) moments of the gradients: $m \leftarrow \beta_1 m + (1 - \beta_1) \nabla_{\theta} J(\theta)$ $s \leftarrow \beta_2 s + (1 - \beta_2) (\nabla_{\theta} J(\theta))^2$

Bias correction is applied: $\hat{m} = m/(1-\beta_1^t)$ and $\hat{s} = s/(1-\beta_2^t)$.

AdamW (Weight Decay)

AdamW improves on Adam by applying weight decay directly to the parameters rather than incorporating it into the gradient update step.

Example: Optimizing Parameters

The following example demonstrates parameter optimization using Adam in PyTorch:

import torch

# Start parameter with gradient tracking
w = torch.tensor([5.0], requires_grad=True)

# Adam optimizer with learning rate of 0.1
optimizer = torch.optim.Adam([w], lr=0.1)

# Minimize w^2 over 5 iterations
for _ in range(5):
  optimizer.zero_grad() # Reset gradients
  loss = w ** 2         # Compute loss
  loss.backward()       # Backprop
  optimizer.step()      # Update w
  print(f"w: {w.item():.4f}")

w: 4.9000
w: 4.8001
w: 4.7003
w: 4.6009
w: 4.5019

Exercise

Test your understanding of adaptive optimization updates:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

Neural Networks Foundations

Artificial Neural Networks (ANNs) are computational models inspired by biological neural networks, structured as layers of interconnected nodes.

The Perceptron

The Perceptron is the simplest ANN architecture, computing a weighted sum of inputs plus a bias, and applying a step function:

$\hat{y} = \text{step}(z) = \text{step}(w^T x + b)$

A single Perceptron is a linear classifier, meaning it cannot solve non-linearly separable problems (like the XOR problem).

Multilayer Perceptron (MLP)

An MLP consists of an input layer, one or more hidden layers, and an output layer. Hidden layers allow the model to learn non-linear representations.

Forward Propagation

For layer $l$, the activations $a^{(l)}$ are computed using the weight matrix $W^{(l)}$ and bias vector $b^{(l)}$:

$z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)}$ $a^{(l)} = \phi(z^{(l)})$

where $\phi$ is the activation function.

Activation Functions

Non-linear activation functions prevent stacked layers from collapsing into a single linear model:

• Sigmoid: $\sigma(z) = 1 / (1 + e^{-z})$, squashing outputs to $(0, 1)$.
• Tanh: $\tanh(z) = (e^z - e^{-z}) / (e^z + e^{-z})$, squashing to $(-1, 1)$.
• ReLU: $\text{ReLU}(z) = \max(0, z)$, preventing vanishing gradients.
• ELU: $\text{ELU}(z) = \max(\alpha(e^z - 1), z)$, preventing dying neurons with small negative values.

Backpropagation

Backpropagation trains networks by computing the gradient of the loss function with respect to the weights using the chain rule of calculus, working backward from the output layer:

$\frac{\partial L}{\partial W^{(l)}} = \frac{\partial L}{\partial z^{(l)}} (a^{(l-1)})^T$

The error term $\delta^{(l)} = \frac{\partial L}{\partial z^{(l)}}$ is computed recursively from the output error using matrix multiplications.

Example: Forward Pass Calculations

The following example demonstrates calculating the forward pass of a single neuron using NumPy:

import numpy as np

# Inputs, weights, and bias
x = np.array([1.5, 2.0])
w = np.array([0.8, -0.5])
b = -0.2

# Linear output
z = np.dot(w, x) + b

# ReLU activation
activation = max(0, z)
print(f"Pre-activation z: {z:.2f}")
print(f"Activation output: {activation:.2f}")

Pre-activation z: 0.00
Activation output: 0.00

Exercise

Test your understanding of activation functions:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Convolutional Neural Networks

Convolutional Neural Networks (CNNs) are specialized neural architectures designed to process grid-structured data, such as images, by exploiting spatial hierarchies.

Convolutional Layers

Unlike fully connected layers where neurons connect to all inputs, convolutional layers connect only to a local receptive field.

Filters and Feature Maps

A layer applies learnable filters (kernels). As a filter slides, it computes dot products, producing a feature map.

Output Dimension Formula

Given input height $H_{\text{in}}$, filter size $F$, padding $P$, and stride $S$, the output height $H_{\text{out}}$ is:

$H_{\text{out}} = \lfloor \frac{H_{\text{in}} - F + 2P}{S} \rfloor + 1$

• Padding ($P$): Adding zero-pixels around the border to preserve spatial dimensions.
• Stride ($S$): The step size of the filter as it slides across the input.

Translation Invariance

CNNs build translation invariance: if a pattern (like a cat’s ear) is learned in one part of the image, the convolutional filters can recognize it anywhere else. This parameter sharing significantly reduces model parameter counts compared to MLPs.

Pooling Layers

Pooling layers reduce the spatial size of feature maps to decrease parameter counts and build translation invariance.

• Max Pooling: Extracts the maximum value from each receptive patch.
• Average Pooling: Computes the average value of each patch.

ResNet and Residual Connections

Deep CNNs suffer from vanishing gradients. ResNet resolves this using Residual Connections (skip connections) that bypass layers:

$a^{(l)} = \phi(W^{(l)} a^{(l-1)} + b^{(l)} + a^{(l-1)})$

This allows gradients to flow directly backward, enabling the training of deep networks.

Example: Output Shapes

The following example calculates the output dimensions of a convolutional layer:

import math

# Formula for calculating the output dimension of a convolutional layer
def get_output_dim(dim_in, filter_size, padding, stride):
  return math.floor((dim_in - filter_size + 2 * padding) / stride) + 1

# Standard input: 32x32 spatial dimensions, 5x5 filter, padding of 2, stride of 1
out_w = get_output_dim(dim_in=32, filter_size=5, padding=2, stride=1)
print(f"Output width: {out_w}")

Output width: 32

Exercise

Test your understanding of CNN operations:

Receptive Fields and Hierarchies

Early layers detect simple edges, while deeper layers combine these features to recognize complex shapes and objects, building a hierarchical spatial representation.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.

Natural Language Processing

Natural Language Processing (NLP) focuses on translating text sequences into mathematical representations that algorithms can learn from.

Statistical Representation: TF-IDF

TF-IDF (Term Frequency-Inverse Document Frequency) measures how important a word is to a document in a corpus:

$\text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \log\left(\frac{|D|}{1 + |\{d \in D : t \in d\}|}\right)$

While effective for classification, TF-IDF ignores word order and semantic similarity.

Sequence Modeling: RNNs and Attention

To handle sequential context, Recurrent Neural Networks (RNNs) maintain a hidden state vector $h_t$ that updates at each step:

$h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b_h)$

The Bottleneck of RNNs

RNNs struggle with long-term dependencies because gradients vanish over long sequence lengths. While LSTM (Long Short-Term Memory) and GRU (Gated Recurrent Unit) architectures use gating mechanisms to help, they still process tokens sequentially, which limits parallel training.

Self-Attention and the Transformer

The Transformer architecture replaces recurrent loops with Self-Attention. For queries $Q$, keys $K$, and values $V$, attention weights are computed in parallel:

$\text{Attention}(Q, K, V) = \text{Softmax}\left(\frac{Q K^T}{\sqrt{d_k}}\right) V$

where $d_k$ is the dimension of the key vectors. This allows the model to capture relationships between words regardless of their distance in the sequence. Positional encodings are added to the input embeddings to represent sequence order. Transformers process the entire sequence in parallel via multi-head attention, capturing complex relationships between distant words. This represents a significant advancement over sequential RNN processing.

Example: TF-IDF Vectorization

The following example demonstrates tokenizing and vectorizing text using TF-IDF:

from sklearn.feature_extraction.text import TfidfVectorizer

corpus = [
  "Machine learning learns from data.",
  "Data science uses machine learning."
]

vectorizer = TfidfVectorizer()
tfidf_matrix = vectorizer.fit_transform(corpus)

print("Vocabulary:")
print(vectorizer.get_feature_names_out())
print("TF-IDF shape:")
print(tfidf_matrix.shape)

Vocabulary:
['data' 'learning' 'learns' 'machine' 'science' 'uses']
TF-IDF shape:
(2, 6)

Exercise

Validate your understanding of text vectorization properties:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Machine Learning Operations (MLOps)

MLOps standardizes the automation, deployment, and monitoring of production ML systems.

Model Decay and Drift

Unlike traditional software, ML models decay in production as real-world data distributions drift:

• Data Drift: statistical properties of inputs change ($P(X_{\text{prod}}) \neq P(X_{\text{train}})$) due to demographic or environment shifts.
• Concept Drift: relationships between inputs and targets change ($P(Y|X_{\text{prod}}) \neq P(Y|X_{\text{train}})$) due to structural changes (e.g., macroeconomics).

MLOps Core Architecture

Production MLOps pipelines introduce Continuous Training (CT) alongside CI/CD:

skinparam backgroundColor transparent
rectangle "Feature Store" as Data
rectangle "CT Pipeline" as CT
rectangle "Model Registry" as Registry
rectangle "Production API" as Prod
rectangle "Drift Monitor" as Mon
Data --> CT : training data
CT --> Registry : registers binary
Registry --> Prod : rolls out model
Prod --> Mon : logs inference
Mon --> Data : triggers CT on drift

Core Components

• Feature Store: stores standardized features for training/inference, preventing serve skew.
• Model Registry: catalogs model binaries, metadata, and version tags.
• Metadata Store: logs hyperparameters and evaluation histories.
• Data Versioning (DVC): tracks datasets using git-like hashes.

MLOps Maturity Levels

• Level 0: manual training and deployment. No automated tracking.
• Level 1: automated model retraining (CT) triggered by drift.
• Level 2: automated CI/CD pipelines deploy both code and retraining steps.

Example: Simulating Drift Detection

The following example demonstrates a basic drift detection agent comparing production feature means with the training baseline:

import numpy as np

train_mean, train_std = 50.0, 5.0
np.random.seed(42)
prod_data = np.random.normal(loc=52.5, scale=5.0, size=100)
prod_mean = np.mean(prod_data)
deviation = abs(prod_mean - train_mean) / train_std

print(f"Production Mean: {prod_mean:.2f}")
print(f"Deviation (in STDs): {deviation:.2f}")

if deviation > 0.4:
  print("ALERT: Statistical data drift detected! Trigger retraining.")
else:
  print("Status: Stable")

Production Mean: 52.34
Deviation (in STDs): 0.47
ALERT: Statistical data drift detected! Trigger retraining.

Exercise

Test your understanding of concept and data drift mechanisms:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Recommender Systems

Recommender systems suggest items to users based on historical interaction patterns and profile attributes.

Collaborative Filtering

Collaborative filtering recommends items based on the behavior of similar users.

Cosine Similarity

We measure the similarity between user rating vectors $\mathbf{u}$ and $\mathbf{v}$ via:

$\text{Sim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{||\mathbf{u}|| ||\mathbf{v}||}$

Predictions are weighted averages of ratings from similar users.

Matrix Factorization (Latent Factor Models)

Matrix Factorization decomposes the sparse user-item rating matrix $R$ of shape $(m, n)$ into two lower-rank matrices: $P$ of shape $(m, k)$ and $Q$ of shape $(n, k)$, representing user and item latent factor embeddings:

$R \approx P Q^T$

We find matrices $P$ and $Q$ by minimizing the squared error over observed ratings, applying regularization to prevent overfitting:

$\min_{P, Q} \sum_{(u,i) \in K} (r_{ui} - (\mu + b_u + b_i + \mathbf{p}_u^T \mathbf{q}_i))^2 + \lambda (||\mathbf{p}_u||^2 + ||\mathbf{q}_i||^2)$

where $K$ is the set of user-item pairs with observed ratings, $\mu$ is the global average rating, and $b_u, b_i$ are user and item bias parameters. Biases isolate systematic offsets (e.g., users who always rate critically, or items that are universally liked).

Cold Start Problem

Latent factor models struggle when a new user or item joins because interaction data is missing. Hybrid systems mitigate this by utilizing content metadata (e.g., genre, age).

Example: Computing Embedding Similarity

The following example demonstrates calculating the cosine similarity between item latent embeddings:

import numpy as np

# Latent factor vectors for two items (rank k=3)
q_a = np.array([0.9, -0.1, 0.2])
q_b = np.array([0.8, 0.0, 0.3])

# Cosine similarity
similarity = np.dot(q_a, q_b) / (np.linalg.norm(q_a) * np.linalg.norm(q_b))
print(f"Embedding Similarity: {similarity:.4f}")

Embedding Similarity: 0.9880

Exercise

Test your understanding of matrix factorization limits:

Regularization

The L2 regularizer parameter $\lambda$ prevents user/item embedding parameters from growing too large during updates, mitigating overfitting.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.
• Smola, A., & Vishwanathan, S. V. N. (2008). An Introduction to Machine Learning. Cambridge University Press.

Reinforcement Learning and Q-Learning

Reinforcement Learning (RL) is a paradigm where an agent learns to make sequences of decisions in an environment to maximize its cumulative long-term reward.

Markov Decision Processes (MDP)

An MDP provides a formal mathematical framework for modeling decision-making under uncertainty, defined by:

• States ($S$): The set of all possible environmental states.
• Actions ($A$): The set of actions available to the agent.
• Transition Probability $P(s' | s, a)$: The probability of transition to state $s'$ given action $a$ in state $s$.
• Reward Function $R(s, a, s')$: The immediate reward received after transitioning.

The Bellman Optimality Equation

The objective is to find a policy $\pi(s)$ that maximizes the expected discounted return $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$, where $\gamma \in [0, 1)$ is the discount factor.

The optimal action-value function $Q^*(s, a)$ satisfies the Bellman Optimality Equation:

$Q^*(s, a) = \sum_{s'} P(s' | s, a) \left[ R(s, a, s') + \gamma \max_{a'} Q^*(s', a') \right]$

Q-Learning (Model-Free Control)

When transition probabilities $P(s'|s,a)$ are unknown, the agent learns $Q$-values through experience using temporal difference updates:

$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$

where $\alpha$ is the learning rate, and $r$ is the immediate reward.

Deep Q-Networks (DQN)

In large state spaces, we replace the lookup table $Q(s, a)$ with a neural network $Q(s, a; \theta)$ parameterized by weights $\theta$. We train the network by minimizing the loss against a target value:

$y = r + \gamma \max_{a'} Q(s', a'; \theta^{-})$

where $\theta^{-}$ represents the weights of a separate target network updated periodically to stabilize training. We use an Experience Replay Buffer to store state transitions, breaking sample correlation and stabilizing updates.

Example: Q-Learning Update Step

The following example demonstrates a single Q-learning update step:

# Hyperparameters
alpha = 0.1
gamma = 0.9

q_value = 2.0
reward = 1.0
max_future_q = 3.0

# Temporal difference update
td_target = reward + gamma * max_future_q
new_q = q_value + alpha * (td_target - q_value)

print(f"Updated Q-value: {new_q:.4f}")

Updated Q-value: 2.1700

Exercise

Test your understanding of the discount factor parameter:

Dimensional Complexity

Tabular Q-learning is limited to small discrete environments. Continuous, high-dimensional spaces require deep neural network function approximators (DQNs).

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.

Ethics in Machine Learning

As machine learning systems are increasingly deployed to automate high-stakes decisions, it is critical to address algorithmic bias and ensure fairness.

Sources of Algorithmic Bias

Algorithmic bias arises at multiple pipeline stages:

• Historical Bias: training data reflects existing systemic human prejudices.
• Representation Bias: sample underrepresents demographics, raising error rates for minorities.
• Measurement Bias: collected features are noisy, poor proxies of the target task.

Mathematical Definitions of Fairness

Fairness is defined mathematically, but different metrics are often mutually exclusive. Let $A$ be a sensitive attribute (e.g., race, gender), $X$ be the remaining features, $Y$ be the true label, and $\hat{Y} = f(X)$ be the model prediction.

1. Demographic Parity (Statistical Parity)

The likelihood of receiving a positive prediction is independent of the sensitive attribute:

$P(\hat{Y} = 1 | A = 0) = P(\hat{Y} = 1 | A = 1)$

2. Equal Opportunity

The true positive rate (recall) is equal across all demographic groups:

$P(\hat{Y} = 1 | A = 0, Y = 1) = P(\hat{Y} = 1 | A = 1, Y = 1)$

3. Predictive Parity

The precision (positive predictive value) is equal across all demographic groups:

$P(Y = 1 | A = 0, \hat{Y} = 1) = P(Y = 1 | A = 1, \hat{Y} = 1)$

These definitions are mathematically incompatible if the base rates differ between demographic groups, meaning a model cannot satisfy all of them simultaneously unless it makes perfect predictions.

Example: Evaluating Fairness

The following example calculates demographic parity difference between two groups:

import numpy as np

# sensitive attribute (0: Group A, 1: Group B)
sensitive = np.array([0, 0, 0, 0, 1, 1, 1, 1])
# model predictions
predictions = np.array([1, 0, 1, 0, 1, 1, 1, 0])

prob_a = np.mean(predictions[sensitive == 0])
prob_b = np.mean(predictions[sensitive == 1])

print(f"Positive selection rate Group A: {prob_a:.2f}")
print(f"Positive selection rate Group B: {prob_b:.2f}")
print(f"Demographic Parity Difference: {abs(prob_a - prob_b):.2f}")

Positive selection rate Group A: 0.50
Positive selection rate Group B: 0.75
Demographic Parity Difference: 0.25

Exercise

Test your understanding of mathematical fairness constraints:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.