Machine Learning Algorithms 1: Supervised Learning

Supervised learning is a paradigm in machine learning where the model learns from data that has been manually labeled with the correct output. The primary goal is to learn a mapping function that can accurately predict the output for new, unseen data.

This process involves a training phase where the model is fed both input features and their corresponding correct labels. The model adjusts its internal parameters to minimize the difference between its predictions and the actual labels.

Supervised learning tasks are typically categorized into two main types:

Regression: Predicting a continuous numerical value (e.g., predicting the price of a house).
Classification: Predicting a discrete class label (e.g., classifying an email as "spam" or "not spam").

Common Algorithms

This document covers the theory, mathematics, and practical considerations for the following foundational supervised learning algorithms:

Linear Regression
Logistic Regression
Regularized Regression
Support Vector Machines (SVM)
k-Nearest Neighbors (k-NN)
Naive Bayes
Decision Trees
Gaussian Processes

Note: Powerful techniques like Random Forest, Gradient Boosting Machines, and Extra Trees are also supervised learning algorithms, but they are covered in detail in the Ensemble Methods document due to their nature of combining multiple models.

Linear Regression

Linear regression is a fundamental statistical method that models the relationship between a dependent variable and one or more independent variables using a linear approach. It forms the foundation for many machine learning algorithms and statistical techniques.

Mathematical Framework

Simple & Multiple Linear Regression

The relationship is modeled as: y = β₀ + β₁x₁ + ... + βₚxₚ + ε

In matrix notation: Y = Xβ + ε

Y: Target vector
X: Design matrix (features)
β: Parameter vector (coefficients)
ε: Error vector

Cost Function (Mean Squared Error)

The objective is to minimize the sum of squared residuals (the difference between actual and predicted values): J(β) = (1/2n) Σ(yᵢ - ŷᵢ)²

Solution Methods

Normal Equation (Closed-Form Solution): A direct analytical solution for the optimal parameters. It is efficient for smaller datasets. β̂ = (XᵀX)⁻¹XᵀY
Gradient Descent: An iterative optimization algorithm used when the normal equation is computationally expensive (i.e., for large datasets). The parameters are updated in the opposite direction of the cost function's gradient. β⁽ᵗ⁺¹⁾ = β⁽ᵗ⁾ - α∇β J(β⁽ᵗ⁾)

Assumptions

Linearity: The relationship between features and the target is linear.
Independence: Observations are independent of each other.
Homoscedasticity: The variance of the error terms is constant across all levels of the independent variables.
Normality: The error terms are normally distributed.
No Multicollinearity: The independent variables are not highly correlated with each other.

Advantages

Simplicity and Interpretability: Easy to understand, and coefficients provide a clear interpretation of feature importance.
Fast Computation: An analytical solution (Normal Equation) is available.
Baseline Model: Serves as an excellent starting point for regression tasks.

Limitations

Underlying Assumptions: Performance suffers if the assumptions are violated.
Overfitting: Can overfit with a high number of features. Regularization is needed to address this.
Sensitivity to Outliers: The model can be heavily influenced by extreme values.

Use Cases

Economics: Forecasting demand, modeling prices.
Finance: Assessing risk, predicting returns.
Healthcare: Analyzing dose-response relationships.

Logistic Regression

Logistic regression is a statistical method used for binary and multiclass classification problems. It models the probability that an instance belongs to a particular class using the logistic (sigmoid) function.

Mathematical Framework

Sigmoid Function

The core of the model is the sigmoid function, which maps any real-valued number into a value between 0 and 1. σ(z) = 1 / (1 + e⁻ᶻ)

Probability Model

The probability of an instance belonging to class 1 is modeled as: P(Y = 1|x) = σ(βᵀx)

The log-odds (logit) of this probability is a linear function of the features, which is why it is considered a linear model for classification. log(P/(1-P)) = βᵀx

Cost Function (Log-Loss)

Parameters are estimated by maximizing the likelihood of the observed data. This is equivalent to minimizing the negative log-likelihood, often called the Log-Loss or Cross-Entropy Loss: J(β) = -Σ [yᵢ log(pᵢ) + (1-yᵢ) log(1-pᵢ)]

This cost function is convex, ensuring that optimization algorithms like gradient descent can find the global minimum.

Advantages

Probabilistic Output: Provides well-calibrated probability estimates for each class.
Interpretability: The model's coefficients can be interpreted as the change in the log-odds of the outcome for a one-unit change in the feature.
Efficiency: It is computationally inexpensive to train and predict.

Limitations

Linear Decision Boundary: It assumes that the data is linearly separable, which may not be true for complex datasets.
Feature Independence: The "naive" assumption of independence between features may not hold.
Multicollinearity: Can be sensitive to highly correlated features, leading to unstable coefficient estimates.

Use Cases

Medical Diagnosis: Predicting the likelihood of a disease based on symptoms.
Finance: Detecting fraudulent transactions or approving credit.
Marketing: Predicting whether a customer will click on an ad (click-through rate).

Regularized Regression

Regularized regression methods are extensions of linear regression that add a penalty term to the cost function to prevent overfitting, handle multicollinearity, and perform feature selection, especially when the number of features is large.

Mathematical Framework

The general objective is to minimize: Cost = ||y - Xβ||₂² + λR(β)

||y - Xβ||₂²: The standard least squares term.
R(β): The regularization penalty function.
λ: The regularization parameter that controls the trade-off between fitting the data and penalizing model complexity.

Ridge Regression (L2 Regularization)

Penalty: R(β) = ||β||₂² = Σβⱼ²
Effect: Shrinks the coefficients of correlated predictors towards each other. It keeps all features but reduces their magnitude. It is particularly useful for dealing with multicollinearity.
Solution: Has a closed-form solution: β̂_Ridge = (XᵀX + λI)⁻¹Xᵀy

Lasso Regression (L1 Regularization)

Penalty: R(β) = ||β||₁ = Σ|βⱼ|
Effect: Can shrink some coefficients to exactly zero, effectively performing automatic feature selection. This results in a sparse and more interpretable model.
Solution: No closed-form solution exists due to the non-differentiable nature of the L1 norm. It is solved using iterative optimization algorithms like coordinate descent.

Elastic Net

Penalty: A linear combination of L1 and L2 penalties: λ[α||β||₁ + (1-α)||β||₂²]
Effect: Combines the properties of both Ridge and Lasso. It can select groups of correlated variables (a weakness of Lasso, which might select only one) and also provides a sparse solution.
Use Case: Effective when there are multiple correlated features and a sparse solution is desired.

When to Use Each Method

Ridge: Use when you have many features, most of which are expected to be relevant, and multicollinearity is present.
Lasso: Use when you have a large number of features and expect that only a subset of them are important (feature selection).
Elastic Net: Use as a default when dealing with high-dimensional data containing correlated features.

Support Vector Machines (SVM)

Support Vector Machines are powerful supervised learning algorithms used for classification and regression tasks. The core idea is to find an optimal hyperplane that separates data points of different classes with the maximum possible margin.

Mathematical Framework

Margin Maximization

For a linearly separable dataset, SVM finds the hyperplane wᵀx + b = 0 that maximizes the geometric margin, which is the distance between the hyperplane and the nearest data point from either class. This is equivalent to minimizing (1/2)||w||₂² subject to yᵢ(wᵀxᵢ + b) ≥ 1.

Support Vectors

The data points that lie closest to the hyperplane are called support vectors. These are the critical elements of the dataset, as they define the margin. The optimal hyperplane is determined only by these support vectors.

Soft Margin SVM

To handle data that is not perfectly separable, the soft margin formulation introduces slack variables ξᵢ that allow some data points to be on the wrong side of the margin or even the hyperplane. The optimization problem becomes a trade-off between maximizing the margin and minimizing the classification error, controlled by a regularization parameter C.

The Kernel Trick

For non-linearly separable data, SVMs use the kernel trick to map the original data into a higher-dimensional space where it becomes linearly separable. The decision function is computed using inner products in this high-dimensional space, which can be calculated efficiently by a kernel function K(xᵢ, xⱼ).

Common Kernels:

Linear: K(xᵢ, xⱼ) = xᵢᵀxⱼ
Polynomial: K(xᵢ, xⱼ) = (γxᵢᵀxⱼ + r)ᵈ
Radial Basis Function (RBF/Gaussian): K(xᵢ, xⱼ) = exp(-γ||xᵢ - xⱼ||₂²) (Most popular choice)

Advantages

High-Dimensional Data: Very effective in high-dimensional spaces, especially when the number of dimensions is greater than the number of samples.
Memory Efficiency: The model is defined only by the support vectors, making it memory efficient.
Versatility: Different kernel functions can be specified for the decision function, allowing for great flexibility.

Limitations

Scalability: Does not scale well to very large datasets, as the training time complexity is between O(n²) and O(n³).
No Probabilistic Output: The basic SVM does not directly provide probability estimates.
Parameter Sensitivity: Performance is highly dependent on the choice of the regularization parameter C and the kernel parameters (like γ for RBF).

k-Nearest Neighbors (k-NN)

k-Nearest Neighbors is a simple, non-parametric, instance-based learning algorithm. It makes no assumptions about the underlying data distribution and is considered a "lazy learning" algorithm because it does not have a dedicated training phase. Instead, it stores all training data and makes predictions by finding the k most similar training examples (neighbors) for a new, unseen data point.

Mathematical Framework

Prediction Process

Calculate Distances: For a new data point x_q, calculate the distance to all points in the training set. A common choice is the Euclidean distance: d(x_q, xᵢ) = √(Σ(x_qʲ - xᵢʲ)²)
Find k-Nearest Neighbors: Identify the k training points that are closest to x_q.
Make a Prediction:
- Classification: Assign the class label that is most frequent among the k neighbors (majority vote).
- Regression: Predict the average of the target values of the k neighbors.

Choosing the value of k

The choice of k is critical and represents a bias-variance trade-off:

Small k: Low bias, high variance. The model is very flexible and can be sensitive to noise (overfitting).
Large k: High bias, low variance. The decision boundary is smoother, but the model may fail to capture local patterns (underfitting).

k is a hyperparameter that is typically chosen using cross-validation.

Advantages

Simplicity: Easy to understand and implement.
No Training Phase: New data can be added easily without retraining the entire model.
Non-parametric: Makes no assumptions about the data distribution, allowing it to capture complex decision boundaries.

Limitations

Computational Cost: Prediction is slow for large datasets, as it requires calculating distances to all training points.
Curse of Dimensionality: Performance degrades in high-dimensional spaces because the concept of "distance" becomes less meaningful.
Sensitivity to Feature Scaling: Features with larger scales can dominate the distance calculation, so standardization is crucial.
Memory Intensive: Requires storing the entire training dataset.

Naive Bayes Classification

Naive Bayes is a family of probabilistic classifiers based on applying Bayes' theorem with a "naive" assumption of conditional independence between every pair of features. Despite this strong assumption, it performs surprisingly well in many real-world applications, especially text classification.

Mathematical Framework

Bayes' Theorem

The foundation of the classifier is Bayes' theorem: P(y | x) = (P(x | y) * P(y)) / P(x)

P(y | x): Posterior probability of class y given features x.
P(x | y): Likelihood of features x given class y.
P(y): Prior probability of class y.
P(x): Evidence probability of features x.

Naive Independence Assumption

The key assumption is that all features are conditionally independent given the class: P(x₁, ..., xₚ | y) = Π P(xᵢ | y)

This simplifies the decision rule to: ŷ = argmax_y [log P(y) + Σ log P(xᵢ | y)]

The model learns the prior probabilities P(y) and the conditional probabilities P(xᵢ | y) from the training data.

Variants

The way P(xᵢ | y) is calculated depends on the type of data:

Gaussian Naive Bayes: Assumes that features follow a Gaussian (normal) distribution. Used for continuous data.
Multinomial Naive Bayes: Used for discrete counts (e.g., word counts in text classification).
Bernoulli Naive Bayes: Used for binary features (e.g., whether a word is present or not).

Advantages

Efficiency: Extremely fast for both training and prediction.
Scalability: Scales linearly with the number of features and data points.
Performance with Small Data: Performs well even with small amounts of training data.
Handles High Dimensions: Works well for high-dimensional data like text.

Limitations

Strong Independence Assumption: The conditional independence assumption is rarely true in the real world, which can lead to suboptimal performance if features are highly correlated.
Zero-Frequency Problem: If a categorical feature in the test set was not observed in the training set for a particular class, the model will assign it a zero probability. This is handled by using smoothing techniques like Laplace smoothing.

Decision Trees

Decision trees are non-parametric supervised learning algorithms that create a model to predict a target value by learning simple, hierarchical decision rules inferred from data features. They produce a tree-like structure where each internal node represents a test on a feature, each branch represents the outcome of the test, and each leaf node represents a class label (in classification) or a continuous value (in regression).

Mathematical Framework

Tree Construction (Recursive Splitting)

The tree is built using a recursive partitioning algorithm. Starting with the entire dataset at the root, the algorithm selects the best feature and split point to divide the data into two or more subsets. This process is repeated for each subset until a stopping criterion is met.

Splitting Criteria

The "best" split is chosen by maximizing an impurity reduction metric.

For Classification:
- Gini Impurity: Measures the frequency at which any element from the set would be incorrectly labeled if it were randomly labeled according to the distribution of labels in the subset. A Gini score of 0 indicates perfect purity. Gini(S) = 1 - Σ pᵢ²
- Entropy & Information Gain: Entropy measures the level of disorder or uncertainty. The algorithm chooses the split that results in the highest Information Gain, which is the reduction in entropy. Entropy(S) = -Σ pᵢ log₂(pᵢ)
For Regression:
- Variance Reduction: The algorithm chooses the split that minimizes the weighted average variance of the child nodes. This is equivalent to maximizing the reduction in the sum of squared errors (SSE).

Pruning

A fully grown decision tree is likely to overfit the training data. Pruning is a technique to reduce the size of the tree by removing sections that provide little predictive power.

Pre-pruning (Early Stopping): Stops the tree from growing once it reaches a certain depth, a minimum number of samples per leaf, etc.
Post-pruning (Cost-Complexity Pruning): Grows the full tree and then removes branches, trading off complexity against training set accuracy.

Advantages

Interpretability: The tree structure is easy to visualize and understand, making it a "white-box" model.
Handles Mixed Data: Can handle both numerical and categorical data without extensive preprocessing.
Non-parametric: Makes no assumptions about the data distribution.

Limitations

Overfitting: Prone to creating overly complex trees that do not generalize well.
Instability: Small variations in the data can result in a completely different tree being generated.
Bias: Tends to be biased towards features with more levels.

Gaussian Processes

Gaussian Processes (GPs) are a non-parametric, Bayesian approach to supervised learning. Instead of learning the parameters of a specific function, GPs define a probability distribution over a collection of functions. This probabilistic framework makes them exceptionally powerful for tasks where quantifying uncertainty is as important as the prediction itself.

Mathematical Framework

Definition

A Gaussian Process is a collection of random variables, any finite number of which have a joint Gaussian distribution. A GP is fully specified by its mean function μ(x) and its covariance function (or kernel) k(x, x'). f(x) ~ GP(μ(x), k(x, x'))

The kernel function k(x, x') is the key component. It defines the similarity between data points, and the choice of kernel embeds assumptions about the function being modeled (e.g., smoothness, periodicity).

Radial Basis Function (RBF) Kernel: A common choice that assumes the function is infinitely smooth. k(x, x') = σ² exp(-||x - x'||²/(2ℓ²))

Regression

Given training data D = {(xᵢ, yᵢ)}, a GP model can make predictions for new inputs x*. The model assumes that the observed target values and the function values at the new inputs are jointly Gaussian. By conditioning this joint distribution on the observed data, we obtain a posterior distribution for the function values at the new inputs.

This posterior is also a Gaussian distribution with a predictive mean and variance:

Predictive Mean: The best estimate for the function's value.
Predictive Variance: A measure of uncertainty in the prediction. The variance is typically low near observed data points and high in regions far from them.

Hyperparameter Optimization

The kernel function has its own parameters (e.g., the length-scale ℓ and signal variance σ² in the RBF kernel). These are learned by maximizing the log marginal likelihood of the training data, often using gradient-based optimization.

Advantages

Uncertainty Quantification: Provides well-calibrated confidence intervals around predictions.
Flexibility: The choice of kernel allows for modeling a wide variety of functions.
Works with Small Data: Can perform well on small datasets where other complex models might overfit.

Limitations

Scalability: The computational complexity of standard GP regression is O(n³), making it intractable for large datasets (n > ~10,000).
Kernel Selection: The performance is highly dependent on the choice of the kernel and its parameters.
High-Dimensional Inputs: Can struggle with the curse of dimensionality.

Use Cases

Bayesian Optimization: Finding the maximum of an expensive-to-evaluate function.
Robotics and Control: Modeling system dynamics with uncertainty.
Geostatistics: Spatial data modeling (Kriging).