2.3: A List of Supervised Learning Models

This is based on Sect. 2.1.2 of SD.

We discuss briefly the most popular supervised learning models. Unsupervised learning models will be discussed in later chapters.

1. Multiple Regression

   1. Given a data point x ∈ ℝ^p, it predict an output by a linear relationship: $$ \hat{y} = 
      \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \cdots + \beta_p x_p
      .$$
      The parameters/coefficients β₀, β₁, …, β_p are to be learned from the data. Note: p is the number of features.

   2. The parameters are estimated (learned) by minimizing the lost function defined by the Mean Squared Error (MSE):
      $$\label{02b=02} \text{RSS} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2 = \frac{1}{n} \sum_{i=1}^n \left(y_i - \left(\beta_0 + \sum_{j=1}^p \beta_j x_{ij}\right)\right)^2$$
      Here, n is the size of the training dataset. The notation x_ij: it denotes the j-th feature of the i-th data (or, the j-th component of the vector x_i).

2. Logistic Regression

   1. It is a model that predicts the probability of a categorical outcome (or, a binary outcome if there are only two possible states).

   2. Consider binary outcomes (say, 0 or 1). Given a data point x ∈ ℝ^p, it predicts the probability of the output being 1 by the following formula:
      $$\label{02b=03} p(\mathbf{x}) = P(y=1 \mid \mathbf{x}) = \frac{1}{1 + e^{-(\beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p)}}$$
      Here, {β_i} are the parameters (to be learned from the data). Note that, the function
      $$\label{02b=04} \sigma(z) := \frac{1}{1 + e^{-z}}$$
      is called the sigmoid function. Hence ([02b=03]) can be written as
      $$\label{02b=05} p(\mathbf{x}) = \sigma ( \beta_0 + \underbrace{ \beta_1 x_1 + \cdots + \beta_p x_p }_{:=\mathbf{\beta} \cdot \mathbf{x}} ) = \sigma \left( \mathbf{\beta} \cdot \mathbf{x} + \beta_0 \right) .$$

   3. The parameters are estimated (learned) by minimizing the lost function defined by binary cross-entropy loss (negative log-likelihood):
      $$\label{02b=06} \mathcal{L}(\boldsymbol{\beta}) = - \sum_{i=1}^n \left[ y_i \log \hat{y}_i + (1 - y_i) \log (1 - \hat{y}_i) \right] ,$$
      where

      • y_i ∈ {0, 1} is the observed class label

      • \( \hat{y}_i = \frac{1}{1 + e^{-(\mathbf{\beta} \cdot \mathbf{x}_i + \beta_0)} } \) is the predicted probability for the i-th observation/data point (i.e., ([02b=05]))

      • n is the number of observations.

   4. Remarks: For the case of multiple outcomes, For predicting/modeling the probability of each class c among K classes, one has
      $$\label{02b=07} p(y = c \mid \mathbf{x}) = \frac{ e^{\mathbf{w}_c \cdot \mathbf{x} + b_c} }{ \sum_{k=1}^K e^{\mathbf{w}_k^\top \mathbf{x} + b_k} },$$
      where w_c and b_c are the weight vector and bias for class c, and x is the input feature vector. ([02b=07]), we assume

      The loss function is again the corresponding cross-entropy loss. It measures the dissimilarity between the true distribution and the predicted distribution. It is defined by

      For the entire dataset with N samples, the total loss is averaged or summed over all samples:
      $$\label{02b=08} L = -\frac{1}{n} \sum_{i=1}^n \left( \sum_{c=1}^K y_{i,c} \log \hat{y}_{i,c} \right) .$$
      Here,

      • n is the number of data points

      • the sum in the parenthesis is the cross-entropy of the i-th sample/data point

      • y_i, c is the indicator that sample i belongs to class c, and ŷ_i, c is the predicted softmax probability for class c of the i-th data point.

      This cross-entropy loss encourages the model to assign high probability to the correct class, and is differentiable for various optimization methods.

   5. To motivate the formula in ([02b=07]):

      1. Say, there are K classes.

      2. Given a data point, x, we set
         p(y = c ∣ x) ∝ e^f_c(x).
         This is a natural choice: p(y = c ∣ x) is probability and it has to be positive, so we define it as an exponential function. The exponent, f_c( ⋅ ), depend on the data point/input vector.

      3. Since these are probabilities, we normalize them so that their sum is 1. This normalization is given by
         $$p( y= c \mid \mathbf{x}) \propto e^{f_c (\mathbf{x}) } \rightarrow \frac{ e^{f_c (\mathbf{x}) } }{ \sum_d e^{f_d (\mathbf{x}) } }.$$
         This is same as the softmax function (see DL Notes (OER): Modern Hopfield Networks).

      4. To obtain ([02b=07]), we assume f_c( ⋅ ) is a linear function of the input vector.

3. Support Vector Machine (SVM)

   SVM is designed to find optimal hyperplane in high-dimensional data spaces for classification or regression. We will explore this in more detail in later sections.

4. K-Nearest Neighbors (KNN)

   • Basic idea: Classify or predict a data point based on the labels or values of its K nearest neighbors in the feature/data space. KNN assumes that points close to each other are likely to have similar outcomes (“Birds of a feather flock together”).

   • The Algorithm:

     • Step 1: Calculate distances between the query point x and all points x_i in the dataset.

     • Step 2: Identify the K nearest neighbors by selecting the K points with the smallest distances to the query point.

     • Step 3: Aggregate neighbors’ outputs:

       • For regression:
         $$\label{02b=10} \hat{y}_q = \frac{1}{K} \sum_{i=1}^K y_i$$
         where ŷ_q is the predicted value, and y_i is the value of the i-th nearest neighbor.

       • For classification: One counts how many of the K nearest neighbors belong to each class, and then assigns the query point the class with the most votes (the majority class among the neighbors):
         $$\label{02b=11} \hat{c}_q = \arg\max_{c} \sum_{i=1}^K \mathbf{1}(c_i = c)$$
         where ĉ_q is the predicted class of the query point, c_i is the class label of the i-th nearest neighbor, and 1 is the indicator function counting votes per class. In ([02b=11]): For each class value c, count the number of times it appears among the K-nearest neighbors. Then, output the class value with the highest occurrence (i.e., the highest vote).

   • Note: KNN is non-parametric. KNN does not build an explicit model; it stores training data and uses distance-based lookup for prediction.

   • Choosing the optimal number of neighbors (K)

     • The value of K controls how many neighbors influence the prediction. Selecting the right K is crucial for balancing bias and variance:

       • A small K (e.g., K = 1) can lead to overfitting, being sensitive to noise and outliers.

       • A large K smooths predictions, reducing variance but possibly causing underfitting by ignoring local patterns.

     • Some common strategies to select K include:

       • Elbow Method: Plot error rate (or accuracy) versus K. Choose K at the “elbow” where error stops decreasing significantly.

       • Heuristic rules: Use \( K = \sqrt{n} \) or \( K = \frac{\sqrt{n}}{2} \) as starting points, where n is the number of training samples.

       • Odd values for K in classification tasks to avoid ties.

     • It is important to tune K based on the dataset and task, as there is no universal best value.

   • Approximate Nearest Neighbor (ANN) Search: we will discuss this in a separate note.

5. Naive Bayes (NB)

   Or, Naı̈ve Bayes, with the diaeresis.

   • Model assumption: NB is a probabilistic classifier based on Bayes’ theorem with the naive assumption that all features x_i are conditionally independent given the class c_k.

   • Bayes’ theorem formulation:
     $$\label{02b=12} P(c_k \mid \mathbf{x}) = \frac{P(c_k) \cdot P(\mathbf{x} \mid c_k)}{P(\mathbf{x})}$$
     where:

     • P(c_k ∣ x) is the (posterior) probability of class c_k given features x = (x₁, x₂, …, x_p)

     • P(c_k) is the (prior) probability of class c_k

     • P(x ∣ c_k) is the likelihood of features given the class (conditional probability of observing the input features x given that the instance belongs to class c_k)

     • P(x) is the evidence (constant across classes for given x).

   • Naive conditional independence assumption:
     $$\label{02b=13} P(\mathbf{x} \mid c_k) = \prod_{i=1}^p P(x_i \mid c_k)$$
     Thus,
     $$\label{02b=14} P(c_k \mid \mathbf{x}) \propto P(c_k) \prod_{i=1}^p P(x_i \mid c_k)$$

   • Classification rule: Choose the class ĉ that maximizes ()the posterior probability):
     $$\label{02b=15} \hat{c} = \arg \max_{c_k} P(c_k) \prod_{i=1}^p P(x_i \mid c_k)$$

   • Model components:

     • P(c_k) can be estimated as the relative frequency of class c_k in training data.

     • P(x_i ∣ c_k) is modeled using appropriate probability distributions and depends on the type of features (e.g., Gaussian for continuous, multinomial for counts, Bernoulli for binary).

   • Loss function: Naive Bayes does not explicitly optimize a separate loss function like regression or neural networks. Instead, it is a generative model estimating likelihoods and priors, and classification is performed by maximizing posterior probabilities.

   • Computational advantage: Due to the independence assumption, the model is efficient to train and effective even with limited data, particularly in high-dimensional settings like text classification.

   • Short comings (when using NB in NLP)

     • Independence assumption: Assumes all words are independent (not true).

     • Ignores word order: Loses context by treating text as a bag of words.

     • Misses dependencies: Fails to capture collocations, negation, or co-occurrence patterns.

     • Rare/unseen words: Struggles without smoothing (as it assign zero probabilities to them).

     • Limited semantics: Cannot model sarcasm, irony, or deeper meaning.

     • Bias to frequent words: Common terms may dominate predictions.

     That said, NB is much less costly to run/implement (than the current cost of running LLMs).

   • Key papers:

     Robertson, S. E., & Sparck Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3), 129–146.

     Kononenko, I. (1990). Comparison of inductive and naïve Bayesian learning approaches. In Current trends in knowledge acquisition (pp. 187–200). Amsterdam, The Netherlands: IOS Press.

6. Random Forest (RF)

   • Definition: An ensemble learning method that builds a collection of decision trees (usually M trees) and combines their predictions to improve accuracy and reduce overfitting.

   • Training data notation: Let D_n = {(x_i, y_i)}_i = 1ⁿ be the full training dataset of size n, where x_i is the i-th input vector and y_i are target values. Here, n is the number of training observations.

   • For each tree j = 1, 2, …, M, a randomized decision tree is constructed by:

     • Sampling with replacement (bootstrap sampling) a set D_n^*(Θ_j) of size n from D_n.

     • Selecting a random subset of features at each node split. The number of random features is a hyperparameter.

     • Splitting nodes using a criterion (e.g., Gini impurity or information gain for classification; variance reduction for regression).

     • Growing the tree until stopping criteria (e.g., minimum leaf size) are met.

   • Single tree prediction for input x (regression form):
     $$\label{02b=16} m_n(\mathbf{x}; \Theta_j, D_n) = \frac{1}{N_n(\mathbf{x}; \Theta_j, D_n)} \sum_{i \in A_n(\mathbf{x}; \Theta_j, D_n)} y_i$$
     where:

     • Θ_j represents the randomness parameter associated with the j-th tree in the forest. It captures all the stochastic aspects involved in the construction of that specific tree .

     • A_n(x; Θ_j, D_n) is the leaf containing x in tree j.

     • N_n(x; Θ_j, D_n) is the number of training samples in that leaf.

     • y_i are target outputs of those samples.

   • Ensemble prediction:
     $$\label{02b=17} m_{M,n}(\mathbf{x}) = \frac{1}{M} \sum_{j=1}^M m_n(\mathbf{x}; \Theta_j, D_n)$$
     For classification, this usually corresponds to majority voting on the predicted classes.

   • Loss function: RF does not explicitly optimize a single, global loss function. Each tree minimizes a local impurity measure (e.g., Gini, entropy, variance) at each split. The ensemble reduces variance through averaging of decorrelated trees.

   • Key advantages: (1) Lower overfitting compared to single decision trees. (2) Works well with high-dimensional features. (3) Robust to noise and outliers (averaging reduce both).

   • Key papers:

     Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32.

     Ho, T. K. (1995). Random decision forests. In Proceedings of the Third International Conference on Document Analysis and Recognition (Vol. 1, pp. 278–282). IEEE Computer Society.

     Amit, Y., & Geman, D. (1997). Shape quantization and recognition with randomized trees. Neural Computation, 9(7), 1545–1588.

     Dietterich, T. G. (2000). Ensemble methods in machine learning. In Multiple classifier systems (Lecture Notes in Computer Science, Vol. 1857, pp. 1–15). Springer.

     See also the review:

     Biau, G., & Scornet, E. (2016). A random forest guided tour. TEST, 25(2), 197–227.

7. Extreme Gradient Boosting (XGBoost)

   • XGBoost (eXtreme Gradient Boosting) is an ensemble learning method that builds a sequence of decision trees (base learners) to create a strong predictive model by iteratively correcting errors of previous trees.

   • The prediction for the i-th data point is the sum of the predictions from all K trees:
     $$\label{02b=18} \hat{y}_i = \sum_{k=1}^K f_k(x_i)$$
     where:

     • ŷ_i is the predicted value.

     • K is the total number of trees.

     • f_k represents the function (tree) learned at iteration k.

   • The objective function minimized by XGBoost combines a differentiable loss function l that measures the difference between predicted values ŷ_i and true labels y_i, and a regularization term Ω that penalizes complex tree structures:
     $$\label{02b=19} \mathcal{L}(\theta) = \sum_{i=1}^n l(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega(f_k)$$
     where:

     • n is the number of data points,

     • l is the chosen loss function (e.g., squared error for regression or logistic loss for classification),

     • Ω(f_k) typically includes terms that measure the complexity of tree f_k, such as the number of leaves and leaf weights, helping to prevent overfitting.

   • XGBoost uses a second-order Taylor expansion (using first and second derivatives of the loss with respect to predictions) to approximate the objective function for efficient optimization and to select the best tree splits.

   • Each new tree is trained to fit the negative gradient (pseudo residuals) of the loss function with respect to the current prediction, effectively correcting errors made by the previous ensemble.

   • Regularization parameters, shrinkage (learning rate), and tree pruning are built-in to control model complexity and improve generalization.

   • Trees in XGBoost are grown level-wise (breadth-first), evaluating all possible splits at each depth level and choosing the one that optimizes the objective function.

   • The optimization at each iteration involves solving for the leaf weights that minimize the regularized loss, often using closed-form solutions derived from the Taylor approximation.

   • Key papers:

     Chen, T., & Guestrin, C. (2016). XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 785–794). ACM.

8. NN/DL: We will discuss this in depth in later chapters.

---