The Probabilistic View of Machine Learning

I like to think of machine learning as pattern matching, where we find a function that maps input to an output. The probabilistic interpretation generalizes this notion to a probability distribution over the output given the input.

Given a dataset $D = \{(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n})\}$ with inputs $x$ and outputs $y$, we aim to find a probability distribution $p(x, y)$ that "best" describes the dataset, i.e. maximizes the likelihood of the data under some assumptions.

The "best" probabilistic model depends on our modeling goals and assumptions about the data. We can classify the methods in two ways:

1. Based on What You Model: A discriminative approach, as the name suggests, discriminates between classes, which makes it a good tool for classification tasks. We model the conditional distribution $p(y \mid x)$. This is the most common approach to machine learning in practice, and some examples include Logistic Regression, Neural Networks, and Decision Trees. A generative approach is more nuanced, as we are trying to create a "blueprint" of our data. Building on the "blueprint" analogy, if the final result of the "blueprint" is the observed sample $(x, y)$, our blueprint is then the joint distribution $p(x, y)$. Some of the most common generative models are Naive Bayes and Gaussian Mixture Models [2].
2. Based on How You Estimate the Distribution: We assume that the distribution has a parametric form $p(x, y; \theta)$, where $\theta$ is the parameter vector, and fit $\theta$ via Maximum Likelihood Estimation (MLE) or Bayesian inference. I like to think of this as a "knobs" approach, where we are looking for the best $\theta$ to fit the data. Examples include Logistic Regression, Neural Networks, and Naive Bayes. There are other ways to estimate a distribution (non-parametric methods like Decision Trees, for example), but the main focus here is on parametric likelihood. So, with a high-level understanding of the problem setup, let's dive deeper into the details of some of the most common machine learning algorithms.

We start with the classic logistic regression algorithm which is a classification model (seriously the real hard problem in machine learning is naming stuff). Logistic regression is a discriminative model that uses a parametric approach to model the conditional distribution $p(y \mid x; \theta)$, making it a good starting point.

Given a dataset $D = \{(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n})\}$ where $y_i \in \{0, 1\}$, the logistic regression algorithm models the log odds of the output as a linear combination of the input features.

Following from the definition above, we have:

where $\theta$ is the parameter vector that we want to learn.

Taking the exponential of both sides, we get:

Since the labels are binary, we know that $p(y = 1 \mid x; \theta) = 1- p(y = 0 \mid x; \theta)$. So, we can rewrite the above equation as:

Solving for $p(y = 1 \mid x; \theta)$, we get:

where $\sigma(z) = \frac{1}{1 + e^{-z}}$ is the sigmoid function which maps any real value to a probability between 0 and 1.

Next, we find the $\theta$ that maximizes the likelihood of the data, $\theta^* = \argmax_{\theta} \mathcal L(\theta)$, where the likelihood function is given by:

Substituting the sigmoid function, we get:

Maximizing the likelihood function over the data is equivalent to minimizing the negative log of the likelihood function,

To find the parameter vector $\theta$ that minimizes the negative log-likelihood of the data, we use gradient descent because no closed-form solution exists. Intuitively, gradient descent looks for the direction in which the loss decreases fastest and takes a small step in that direction. The gradient points in the direction of steepest ascent, so we step along the negative gradient, repeating the update rule $\theta \leftarrow \theta - \eta \nabla \ell(\theta)$ until the gradient is (close to) zero, where $\eta$ is the learning rate.

To make this easier to work with, we start by taking the derivative of the negative log-likelihood for a single data point:

A quick note on the derivative of the sigmoid function:

Using this, the derivative for a single data point simplifies to:

So over all the data points, we have:

Because $\ell(\theta)$ is convex, gradient descent with a suitable learning rate converges to a global minimum, with no local minima to get stuck in.[3]

With logistic regression we focus on binary classification, now we generalize the idea to multi-class classification.

Given a dataset $D = \{(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n})\}$ where $y_i \in \{1, 2, ..., k\}$, similar to the binary case, we model the log-odds of the output as a linear combination of the input features, however, this time we have $k$ classes. We model the conditional probability of each class, and choose one class $C$ as the reference class such that $\theta_C = 0$. Next, we know that the sum of the probabilities of all the classes must be 1, so we have:

Now, we can rewrite the log-odds of the output as a linear combination of the input features, for all $c \neq C$:

Exponentiating both sides, we get:

Substituting equation 2.2 into equation 2.1 and factoring out $p(y = C \mid x; \theta)$, we get:

Substituting equation 2.3 back into equation 2.2, we get:

Since we have $\theta_C = 0$, we can simplify the above equation to:

which is the softmax function.

Similar to logistic regression, we can use gradient descent to find the parameter vector $\theta$ that minimizes the negative log-likelihood of the data. However, the likelihood function is a bit more complicated:

where $1\{y_i = c\}$ is the indicator function that is 1 if $y_i = c$ and 0 otherwise.

Taking the negative log of the likelihood function, we get:

Since a closed-form solution is not possible, we use gradient descent once again, with the same update rule $\theta \leftarrow \theta - \eta \nabla \ell(\theta)$. Again, to make this easier to work with, we take the derivative of the negative log-likelihood with respect to a single weight vector $\theta_c$ for a single example,

Using

and the fact that exactly one indicator is 1, the gradient for a single example is:

Summing over all examples, the gradient with respect to $\theta_c$ is:

1. On the importance of the i.i.d. assumption in statistical learning
2. Generative model
3. Prove that the cost function is convex