Part 2 & 3 - Bayesian Linear Regression

Given a training set $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^{N}$, where $\mathbf{x}_i$ are free variables (features, covariates, domain points, explanatory variables, etc.) and $y_i$ are the target variables, dependant on $\mathbf{x}_i$ (dependent variables, labels, responses, etc.), the goal of supervised machine learning is to identify an algorithm to predict the label $y$ for a new (yet unseen) input $\mathbf{x}$. In other words, learning a model from label data and predicting outputs of new data based on the learned model.w

However, this task is impossible if there is no information about the mechanism relating $\mathbf{x}$ and $y$. Thus, we may assume that $\mathbf{x}$ and $y$ are related via a function $y = \tilde{f}(\mathbf{x})$.

Thus, the goal is to find the best possible approximation of $\tilde{f}(\mathbf{x})$, $f(\mathbf{x})$ (prediction model), and predict the outcome $y$ for $\mathbf{x}$ as $\hat{y} = f(\mathbf{x})$.

Again, in more general temrs, we want to identify a predictive algorithm that minimizes the error in the prediction of a new label $y$ for an unobserved input $\mathbf{x}$ (generalization loss).

As we discussed last time, we have two main approaches, the frequentist and the Bayesian approach. We will rephrase the supervised machine learning problem as a Bayesian inference problem.

From learning, we know that we need to treat $\mathbf{x}$ and $y$ as random variables. Thus, our objective is predict $y$ given the (random) observation of $\mathbf{x}$ under the assumption that the joint distribution $p(\mathbf{x}, y)$ is known.

We define the loss function $\ell(y, \hat{y})$ as the cost (loss or risk) incurred when the correct value is $y$ while the estimated value is $\hat{y}$. For example, the quadratic loss function is defined as,

We say there is a optimal prediction $\hat{y}^{\star}(\mathbf{x})$ that minimizes the generalization loss (or, generalization error),

The solution is “simply”,

Thus, the optimal prediction is a function of $p(y \mid \mathbf{x})$ and the loss function $\ell(y, \hat{y})$.

For the loss function, $\ell(y, \hat{y}) = (y - \hat{y})^2$,

i.e., the optimal prediction is the conditional mean of $y$ given $\mathbf{x}$.

However, in most scenarios, the joint distribution $p(\mathbf{x}, y)$ is unknown.

Finally, let’s restate the supervised machine learning problem as an inference problem.

The goal is to obtain a predictor $\hat{y}(\mathbf{x})$ that performs close to optimal predictor $\hat{y}^{\star}(\mathbf{x})$ based only on the training set $\mathcal{D}$ (without knowledge of $p(\mathbf{x}, y)$). Where closeness is measured as,

where $L_p(\hat{y})$ is the generalization loss of the trained predictor $\hat{y}(\mathbf{x})$ and $L_p(\hat{y}^{\star})$ is the minimum generalization loss (optimal predictor).

Our training data points $(\mathbf{x}_i, \mathsf{y}_i) \in \mathcal{D}$ are i.i.d random variables drawn from a true (but unknown) distribution $p(\mathbf{x}, y)$,

Since $p(\mathbf{x}, y)$ is unknown, we cannot find the optimal predictor via,

The solution however, is to separate learning inference. If we can learn an approximation of $p(y \mid \mathbf{x})$ based on $\mathcal{D}(p_{\mathcal{D}}(y \mid \mathbf{x}))$, and use it in,

we can obtain,

Further, we can perform direct inference via empirical risk minimization (ERM). If we directly learn an approximation of the optimal decision rule ($\hat{y}_{\mathcal{D}}(\cdot)$) by minimizing an empirical estimate of the generalization loss,

But, how do we learn an approximation of $p_{\mathcal{D}}(y \mid \mathbf{x})$ of $p(\mathsf{y} \mid \mathbf{x})$ based on $\mathcal{D}$? If we can select a family of parametric probabilistic models (i.e., hypothesis classes), we can learn the model parameters to fit $\mathcal{D}$.

In linear regression, we are interested in values of a fucntion $y(\mathbf{x}): \mathbb{R}^d \to \mathbb{R}$, where $\mathbf{x} = (x_1, \ldots, x_d)^T$. We have some observations of this mapping, precisely $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^{N}$.

Thus, the goal is to predict $y$ for a new input $\mathbf{x}$, i.e., learn an accurate prediction function $\hat{y}(\mathbf{x})$ (also called regression function) from $\mathcal{D}$. Further, in linear regression, we assume that the relationship between $\mathbf{x}$ and $y$ is linear,

We can extend this to a setting where we allow linear combinations of fixed nonlinear functions of the input variables,

where $\phi_j(\mathbf{x})$ are basis functions, $w_0$ is called the bias (allows for any fixed offset). Further, conveniently, we define the dummy basis function $\phi_0(\mathbf{x}) \coloneqq 1$ so that,

where $\mathbf{w} = (w_0, w_1, \ldots, w_{M-1})^T$ and $\boldsymbol{\phi}(\mathbf{x}) = (\phi_0(\mathbf{x}), \phi_1(\mathbf{x}), \ldots, \phi_{M-1}(\mathbf{x}))^T$.

We can (again) further extend our framework by expressing our uncertainty over the value of $\mu(\mathbf{x}, \mathbf{w})$ as,

Thus, given $\mathbf{x}$, $y$ can be modeled by a probabilistic model,

or, equivalently,

where $\boldsymbol{\theta} = (\mathbf{w}, \beta)$.

In discriminative models, our posterior (predictive) distribution $p(y \mid \mathbf{x})$ is assumed to belong to a hypothesis class parameterized by $\boldsymbol{\theta}$, i.e., $p(y \mid \mathbf{x}, \boldsymbol{\theta})$. We learn the parameters $\boldsymbol{\theta}$ directly from the training data $\mathcal{D}$.

Thus, once the model is learned, we can compute,

In generative models, we see the models $p(\mathbf{x}, y)$ as being part of a parametric family $p(\mathbf{x}, y \mid \boldsymbol{\theta})$. This means we from these models, can find $p(\mathbf{x})$.

This is the generative ascpet of these models. We have the capacity to generate a realization of $\mathbf{x}$ by using the marginal $p(\mathbf{x} \mid \boldsymbol{\theta})$. Thus, once the model is learned, we can obtain $p(y \mid \mathbf{x}, \boldsymbol{\theta})$ via Bayes’ theorem and computing,

From what we have seen so far, we have stated that our models can be from a hypothesis class $p(y \mid \mathbf{x}, \boldsymbol{\theta}) = \mathcal{N}(\mu(\mathbf{x}, \mathbf{w}), \beta^{-1})$. For example, this can define the polynomial degree $M$ (i.e., edfines the capacity of the class).

While a specific model $p(y \mid \mathbf{x}, \boldsymbol{\theta})$ is defined by the selection of the parameters $\boldsymbol{\theta} = (\mathbf{w}, \beta)$ (learned from $\mathcal{D}$).

As we discussed in the last part, one approach is Maximum Likelihood (ML) learning. Select $\boldsymbol{\theta}$ such that $\mathcal{D}$ has maximum probability of being observed,

We know that maximizing the likelihood is equivalent to maximizing the log-likelihood 11since $\log(\cdot)$ is a monotonic function and does not change the location of the maximum,

The ML criterion (cross-entropy or log-loss) is then,

where $L_p(\hat{y}^{\star})$ is generalization loss of the optimal predictor (minimum loss achievable), $L_p(\mathbf{w}^{\star})$ is the generalization loss for optimal $\mathbf{w}$ for the given hypothesis class (e.g., fixing $M$).

The bias (approximation error) is caused by our choice of the hypothesis class (model misspecification) and the estimation error (generalization gap) is caused byt the fact that $N$ is not large enough.

We can divide our available data into three sets.

• Training set $\mathcal{D}$ to fit the model parameters.

• Validation set $\mathcal{V}$ to choose hypothesis class via evaluation of approximation of the generalization error,

for the selected hypothesis class, retrain $\mathbf{w}$ based on $\mathcal{D} \cup \mathcal{V}$.

• Test set $\mathcal{T}$ to produce the estimate generalization error obtained with the final model.

However, there is a pitfall with this approach, parts of the available data are not used for training! Validation is suitable when we have plently of data. However, when data is scarce, we can use cross-validation (CV) techniques.

1. Randomly partition data points into $k$ partitions (folds)

2. For each $\kappa \in \{1, \ldots, k\}$, train model over all other $k -1$ partitions.

3. Compute generalization error on the $\kappa$-th partition,

4. Generalization error estimated as average over all partitions.

5. Choose hypothesis class that minimizes the estimate of the generalization error in Step 4.

In the Bayesian approach, we instead treat the parameters $\mathbf{w}$ as unknown random variables (instead of unknown but deterministic quantities). MAP enables a finer control of the bias and estimation error.

The key idea is to leverage prior information available on the behavior of parameters in the absence, or presence, of overfitting.

or, equivalently,

If $\beta$ is a known constant,

Assuming $\mathbf{w} \sim \mathcal{N}(0, \alpha^{-1} \mathbf{I})$, i.e., $p(\mathbf{w}) = \mathcal{N}(\mathbf{w} \mid 0, \alpha^{-1} \mathbf{I}) = \left(\frac{\alpha}{2 \pi}\right)^{(M + 1) / 2} \exp \left(- \frac{\alpha}{2} \mathbf{w}^T \mathbf{w} \right)$,

Thus, consider $p(\mathbf{w} \mid \hat{y}_{\mathcal{D}}, x_{\mathcal{D}}, \beta)$. Due to conjugate Gaussian prior distribution, the posterior also Gaussian,

where,

We assume $\mathbf{w} \sim \mathcal{N}(0, \alpha^{-1} \mathbf{I})$,

Applying Bayes’,

• $p(\mathbf{w})$ is our knowledge about $\mathbf{w}$ before observing any data.

• $p(y_{\mathcal{D}} \mid \mathbf{w})$ is how likely the observed data is for a particular parameter value.

• $p(\mathbf{w} \mid y_{\mathcal{D}})$ knowledge about $\mathbf{w}$ from the observed data and the model.

In this part, we have seen that the frequentist approach, aims at identifying a specific value for $\boldsymbol{\theta}$ of a probabilistic model to derive a predictor,

• ML: Chooses $\boldsymbol{\theta}$ that maximizes probability of training data.

• MAP: Includes also prior information about parameter vector. In contrast, the Bayesian approach assumes that $\boldsymbol{\theta}$ is jointly distributed with data $\Rightarrow$ Does not commit to a single value of $\boldsymbol{\theta}$ but considers explanations provided by all possible values of $\boldsymbol{\theta}$, each weighted according to data-dependent belief.

Bayesian Linear Regression Model,

where $\mathbf{w} \sim p(\mathbf{w})$

Probabilistic Model,

Thus, the end goal is making predictions of $y$ for new values of $\mathbf{x}$ $\Rightarrow$ We can directly evalute the posterior distribution $p(y \mid y_{\mathcal{D}}, x_{\mathcal{D}}, \mathbf{x}, \beta)$. A fully Bayesian solution returns the entire posterior $p(y \mid \mathcal{D}, \mathbf{x}, \beta)$ $\Rightarrow$ which provides more information about unobserved label $y$.

Finally, one last note on predictive distribution. We obtain,

With the Bayesian approach, $p(y \mid \mathbf{x}, \mathbf{w}, \beta)$ is associated with each value of $\mathbf{w}$ weighted by the posterior belief,

Computing $p(\mathbf{w} \mid \mathcal{D}, \beta)$ and $p(y \mid \mathcal{D}, \mathbf{x}, \beta)$ is difficult.

For our Bayesian linear regression problem with $\mathbf{w} \sim \mathcal{N}(0, \alpha^{-1} \mathbf{I})$,

where $\mathbf{m}_N$ and $\mathbf{S}_N$ are defined as before.

Thus, we can obtain,

where,