Supervised Learning Models and Algorithms

Supervised learning is a machine learning paradigm where models learn from labeled data to make predictions. The goal is to build a classifier that can learn to predict an outcome variable y from input features x.

Types of Predictive Models

Types of Machine Learning Models

Generative models first learn how the data is generated by estimating $P(x|y)$, then use Bayes' rule to estimate $P(y|x)$.

Core Concepts in Supervised Learning

• Hypothesis ($h_\theta$): This is the chosen model. For a given input $x^{(i)}$, the model's prediction is $h_\theta(x^{(i)})$.
• Loss Function ($L$): A function that quantifies the difference between a predicted value $z$ and the real data value $y$.

  Squared Loss	Logistic Loss	Hinge Loss	Cross-entropy Loss
  $\frac{1}{2}(y-z)^2$	$\log(1+\exp(-yz))$	$\max(0,1-yz)$	$-[y \log(z)+(1-y) \log(1-z)]$
  Used in Linear Regression	Used in Logistic Regression	Used in SVM	Used in Neural Networks

• Cost Function ($J(\theta)$): Commonly used to assess model performance, defined as the sum of loss over all training examples: $$J (\theta) = \sum_ {i = 1} ^ {m} L \left(h _ {\theta} \left(x ^ {(i)}\right), y ^ {(i)}\right)$$
• Gradient Descent: An optimization algorithm to minimize the cost function. With learning rate $\alpha$, the update rule is: $$\theta \longleftarrow \theta - \alpha \nabla J (\theta)$$

  Stochastic Gradient Descent (SGD) updates parameters based on each training example. Batch Gradient Descent updates based on a batch of training examples.

• Likelihood ($L(\theta)$): Used to find optimal parameters $\theta$ by maximizing the likelihood of the model given the parameters. The optimal $\theta$ is found by: $$\theta^ {\mathrm {o p t}} = \underset {\theta} {\arg \max } L (\theta)$$ In practice, the log-likelihood $\ell (\theta) = \log (L(\theta))$ is often optimized for simplicity.
• Newton's Algorithm: A numerical method to find $\theta$ where $\ell'(\theta) = 0$. The update rule is: $$\theta \leftarrow \theta - \frac {\ell^ {\prime} (\theta)}{\ell^ {\prime \prime} (\theta)}$$ The multidimensional generalization (Newton-Raphson method) uses: $$\theta \leftarrow \theta - \left(\nabla_ {\theta} ^ {2} \ell (\theta)\right) ^ {- 1} \nabla_ {\theta} \ell (\theta)$$

Regression Models

Regression models predict continuous outcome variables.

Linear Regression

Assumes the outcome $y$ given $x$ and $\theta$ follows a Normal distribution: $y|x;\theta \sim \mathcal{N}(\mu ,\sigma^2)$.

• Normal Equations: For a design matrix $X$, the $\theta$ that minimizes the cost function has a closed-form solution: $$\theta = (X^T X)^{-1} X^T y$$
• LMS Algorithm (Widrow-Hoff): An iterative update rule for a training set of $m$ data points with learning rate $\alpha$: $$\forall j, \quad \theta_j \leftarrow \theta_j + \alpha \sum_{i=1}^{m} \left[ y^{(i)} - h_\theta(x^{(i)}) \right] x_j^{(i)}$$ This is a special case of gradient ascent.
• Locally Weighted Regression (LWR): A variant where each training example is weighted in the cost function by $w^{(i)}(x)$, defined as: $$w^{(i)}(x) = \exp \left(- \frac{(x^{(i)} - x)^2}{2 \tau^2}\right)$$ where $\tau$ is a parameter.

Classification Models

Classification models predict categorical outcome variables.

Logistic Regression

Used for binary classification; assumes $y|x;\theta \sim \mathrm{Bernoulli}(\phi)$.

• Sigmoid Function ($g$): Also known as the logistic function, it maps any real-valued number to a value between 0 and 1: $$\forall z \in \mathbb{R}, \quad g(z) = \frac{1}{1 + e^{-z}} \in ]0,1[$$
• Hypothesis: The probability of $y=1$ given $x$ and $\theta$ is: $$\phi = p(y = 1 | x; \theta) = \frac{1}{1 + \exp(-\theta^T x)} = g(\theta^T x)$$

  There is no closed-form solution for logistic regression, requiring iterative optimization methods like gradient descent.

Softmax Regression

A generalization of logistic regression for more than two outcome classes, also called multiclass logistic regression. By convention, $\theta_K = 0$. The Bernoulli parameter $\phi_i$ for each class $i$ is: $$\phi_i = \frac{\exp(\theta_i^T x)}{\sum_{j=1}^{K} \exp(\theta_j^T x)}$$

Generalized Linear Models (GLMs)

GLMs provide a flexible way to model response variables that follow various distributions, not just the normal distribution, by relating the linear predictor to the response variable via a link function.

Exponential Family Distributions

A class of distributions belonging to the exponential family can be written as: $$p(y; \eta) = b(y) \exp(\eta T(y) - a(\eta))$$ Where:

• $\eta$: Natural parameter (canonical parameter or link function).
• $T(y)$: Sufficient statistic (often $T(y) = y$).
• $a(\eta)$: Log-partition function.
• $b(y)$: Base measure.

The term $\exp(-a(\eta))$ acts as a normalization constant ensuring probabilities sum to one.

Common Exponential Distributions

Assumptions of GLMs

GLMs aim to predict a random variable $y$ as a function of $x \in \mathbb{R}^{n+1}$ based on three key assumptions:

1. $y | x; \theta \sim \operatorname {ExpFamily}(\eta)$ (The conditional distribution of $y$ given $x$ belongs to the Exponential Family).
2. $h_\theta(x) = E[y | x; \theta]$ (The model predicts the expected value of $y$).
3. $\eta = \theta^T x$ (The natural parameter is a linear function of the input features).

Ordinary Least Squares (Linear Regression) and Logistic Regression are special cases of Generalized Linear Models.

Support Vector Machines (SVMs)

The goal of SVMs is to find an optimal hyperplane that maximizes the minimum distance to the closest training examples from any class (the margin).

Optimal Margin Classifier

The optimal margin classifier $h(x)$ is given by:

Where $(w,b) \in \mathbb{R}^n \times \mathbb{R}$ are the parameters obtained by solving the following optimization problem:

The decision boundary is defined by $w^T x - b = 0$.

Hinge Loss

The hinge loss function, specific to SVMs, is defined as:

Kernel Function

Given a feature mapping $\phi$, the kernel $K$ is defined as the inner product of the mapped features:

A commonly used kernel is the Gaussian kernel: $K(x,z) = \exp \left(-\frac{||x - z||^2}{2\sigma^2}\right)$.

The "kernel trick" allows us to compute the cost function using the kernel $K(x,z)$ without explicitly knowing the often complex feature mapping $\phi$. This is crucial for handling non-linear separability by mapping data into higher-dimensional spaces.

Lagrangian

The Lagrangian $\mathcal{L}(w,b)$ is used in optimization with constraints:

The coefficients $\beta_i$ are known as Lagrange multipliers.

Generative Learning Algorithms

Generative models learn the joint probability distribution $P(x,y)$ or $P(x|y)$ and $P(y)$, which then allows them to infer $P(y|x)$ using Bayes' rule.

Gaussian Discriminant Analysis (GDA)

GDA assumes specific distributions for $y$ and $x|y$.

• Setting:
  • $y \sim \operatorname {Bernoulli} (\phi)$
  • $x \mid y = 0 \sim \mathcal {N} \left(\mu_ {0}, \Sigma\right)$
  • $x \mid y = 1 \sim \mathcal {N} \left(\mu_ {1}, \Sigma\right)$
• Estimation: Parameters are found by maximizing the likelihood.

  $\phi$	$\mu_j (j=0,1)$	$\Sigma$
  $\frac{1}{m}\sum_{i=1}^{m}1\{y^{(i)}=1\}$	$\frac{\sum_{i=1}^{m}1\{y^{(i)}=j\}x^{(i)}}{\sum_{i=1}^{m}1\{y^{(i)}=j\}}$	$\frac{1}{m}\sum_{i=1}^{m}(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

Naive Bayes

A generative model that simplifies the estimation by assuming feature independence.

• Assumption: Features $x_1, x_2, \dots$ are conditionally independent given $y$: $$P (x | y) = P \left(x _ {1}, x _ {2}, \dots | y\right) = \prod_ {i = 1} ^ {n} P \left(x _ {i} | y\right)$$
• Solutions: Maximizing the log-likelihood yields the following estimations for $k \in \{0,1\}$ and feature value $l \in [1,L]$: $$P (y = k) = \frac {1}{m} \times \# \{j | y ^ {(j)} = k \}$$ $$P (x _ {i} = l | y = k) = \frac {\# \{j | y ^ {(j)} = k \text { and } x _ {i} ^ {(j)} = l \}}{\# \{j | y ^ {(j)} = k \}}$$

  Naive Bayes is widely used in text classification and spam detection due to its simplicity and effectiveness.

Tree-Based Methods

These methods can be used for both regression and classification problems.

• CART (Classification and Regression Trees): Commonly known as decision trees, these are binary trees. They are highly interpretable.
• Random Forest: A tree-based ensemble method that builds a large number of decision trees from randomly selected subsets of features and data. It typically offers good performance but is less interpretable than single decision trees.

Boosting Methods

Boosting combines several "weak learners" to form a stronger learner.

K-Nearest Neighbors (K-NN)

The $k$-NN algorithm is a non-parametric approach where the response of a new data point is determined by the majority class (for classification) or the average (for regression) of its $k$ closest neighbors in the training set.

The choice of $k$ influences the model's bias and variance:

• A higher $k$ leads to higher bias (smoother decision boundaries, less sensitive to noise).
• A lower $k$ leads to higher variance (more complex decision boundaries, more sensitive to noise).

Learning Theory

Learning theory provides theoretical foundations for understanding how and why algorithms learn effectively.

• Union Bound: For $k$ events $A_1, \dots, A_k$, the probability of at least one event occurring is bounded: $$P \left(\bigcup_{i=1}^k A_i\right) \le \sum_{i=1}^k P(A_i)$$
• Hoeffding Inequality (Chernoff Bound): For $m$ i.i.d. Bernoulli variables $Z_1, \dots, Z_m$ with mean $\phi$, and sample mean $\widehat{\phi}$, for any $\gamma > 0$: $$P \left(\left| \phi - \widehat {\phi} \right| > \gamma\right) \leqslant 2 \exp \left(- 2 \gamma^ {2} m\right)$$
• Training Error ($\widehat{\epsilon}(h)$): Also known as empirical risk or empirical error, it measures the proportion of mistakes a classifier $h$ makes on the training set: $$\widehat {\epsilon} (h) = \frac {1}{m} \sum_ {i = 1} ^ {m} 1 _ {\{h (x ^ {(i)}) \neq y ^ {(i)} \}}$$
• Probably Approximately Correct (PAC): A framework for analyzing the theoretical learnability of a concept. Its assumptions are:
  • Training and test sets follow the same distribution.
  • Training examples are drawn independently.
• Shattering: A set of classifiers $\mathcal{H}$ shatters a set of data points $S = \{x^{(1)},\dots,x^{(d)}\}$ if it can perfectly classify any possible labeling of these points: $$\exists h \in \mathcal {H}, \quad \forall i \in [ 1, d ], \quad h (x ^ {(i)}) = y ^ {(i)}$$
• Upper Bound Theorem: For a finite hypothesis class $\mathcal{H}$ of size $k$, with probability at least $1-\delta$, the true error $\epsilon(\widehat{h})$ of the learned hypothesis $\widehat{h}$ is bounded by: $$\epsilon (\widehat {h}) \leqslant \left(\min _{h \in \mathcal {H}} \epsilon (h)\right) + 2 \sqrt {\frac {1}{2 m} \log \left(\frac {2 k}{\delta}\right)}$$
• VC Dimension (Vapnik-Chervonenkis Dimension): For an infinite hypothesis class $\mathcal{H}$, $VC(\mathcal{H})$ is the size of the largest set that can be shattered by $\mathcal{H}$.

  For example, the VC dimension of linear classifiers in 2 dimensions is 3.

• Vapnik's Theorem: For a hypothesis class $\mathcal{H}$ with VC dimension $d$ and $m$ training examples, with probability at least $1-\delta$: $$\epsilon (\widehat {h}) \leqslant \left(\min _ {h \in \mathcal {H}} \epsilon (h)\right) + O \left(\sqrt {\frac {d}{m} \log \left(\frac {m}{d}\right) + \frac {1}{m} \log \left(\frac {1}{\delta}\right)}\right)$$ This theorem provides a generalization bound for infinite hypothesis classes.

Key Takeaways

• Supervised learning involves building models to predict outcomes from labeled data.
• Models are categorized as regression (continuous outcomes) or classification (categorical outcomes), and as discriminative or generative.
• Fundamental concepts include hypothesis, loss functions, cost functions, and optimization algorithms like gradient descent and Newton's method.
• Popular algorithms include Linear Regression, Logistic Regression, SVMs, GDA, Naive Bayes, Decision Trees, Random Forests, and K-NN.
• Generalized Linear Models offer a unifying framework for various exponential family distributions.
• Learning theory provides bounds and insights into model generalization through concepts like PAC learning, shattering, and VC dimension.