Supervised Learning: Function Approximation

From Programming to Learning

In traditional programming, a developer writes explicit rules to transform input data into a desired output. Machine learning turns this on its head: we provide the algorithm with examples of data and the corresponding desired outputs, and the algorithm's job is to learn the rules itself. This learned set of rules is our "model" or "program."

Let's begin by watching a short segment from a lecture by Kilian Weinberger at Cornell University, which illustrates this fundamental distinction.

This training/testing paradigm is the cornerstone of supervised learning. Let's formalize the setup.

The Formal Setup of Supervised Learning

In supervised learning, we start with a dataset, which we'll denote as $\mathcal{D}$. This dataset consists of $n$ pairs of observations:

• Each $x_i$ is an input or feature vector from an input space $\mathcal{X}$. For example, $\mathcal{X}$ could be ${\mathbb{R}}^d$, representing a vector with $d$ numerical features (like a patient's age, height, and blood pressure).
• Each $y_i$ is the corresponding output or label from an output space $\mathcal{Y}$. The nature of $\mathcal{Y}$ defines the type of problem:
  • Regression: $\mathcal{Y}$ is a set of continuous values (e.g., $\mathbb{R}$ for predicting house prices).
  • Classification: $\mathcal{Y}$ is a discrete set of categories (e.g., $\{0,1\}$ for spam detection, or $\{\text{cat},\text{dog},\text{bird}\}$ for image classification).

The most crucial assumption in this framework is that our data points $(x_i,y_i)$ are independent and identically distributed (i.i.d.) samples drawn from a true, but unknown, joint probability distribution $P(X,Y)$. This distribution represents the underlying process generating the data—the "real world" we are trying to model. The data we have, $\mathcal{D}$, is our training sample from this world. Our goal is to perform well on future samples from this same world, which we can call the test distribution.

To solidify these initial concepts, let's return to the Cornell lecture video.

The Goal: Minimizing Risk

Our objective is to use the training data $\mathcal{D}$ to find a function, $h:\mathcal{X}\to \mathcal{Y}$, called a hypothesis or predictor, that makes accurate predictions on new, unseen data drawn from $P(X,Y)$.

To formalize "accurate," we first need to define a loss function, $\mathcal{L}(y_{pred},y_{true})$, which quantifies the penalty for a single incorrect prediction. For example, in regression, a common choice is the squared error: $\mathcal{L}(\hat{y},y)=(\hat{y}-y{)}^2$, where $\hat{y}=h(x)$ is our prediction.

While the loss tells us how we did on one example, we need a way to evaluate the hypothesis $h$ as a whole. The ultimate measure of a hypothesis's quality is its risk, also known as the generalization error. The risk $R(h)$ is the expected loss over the true data-generating distribution $P(X,Y)$.

This is our gold standard for evaluation. It measures the average performance of our hypothesis on all possible data, weighted by its probability of occurrence.

The following video from a Bloomberg lecture series on Statistical Learning Theory provides an excellent walkthrough of these ideas.

The Optimal Predictor: The Bayes Function

If we knew the true distribution $P(X,Y)$, what would be the best possible hypothesis? This is the Bayes predictor, denoted $f^{\ast }$. It is the function that minimizes the risk over the space of all possible functions.

The risk of this optimal function, $R(f^{\ast })$, is called the Bayes risk. It represents the irreducible error for the problem—the error that remains even with a perfect model, due to inherent randomness or noise in the data-generating process itself.

For a given loss function, the form of the Bayes predictor is often intuitive. For squared error loss in regression, $f^{\ast }(x)$ turns out to be the conditional expectation of the output given the input, $f^{\ast }(x)=\mathbb{E}[Y|X=x]$. This is a powerful result that connects the statistical properties of the data to the optimal prediction strategy.

Let's watch the next segment of the Bloomberg video to see this explained.

This formally frames our goal: supervised learning is a function approximation problem where we try to find a hypothesis $h$ that is a good approximation of the unknown Bayes predictor $f^{\ast }$.

The Method: Empirical Risk Minimization

There's a major challenge: we cannot calculate the true risk $R(h)$ because we do not know the true distribution $P(X,Y)$.

Instead, we can use our training data $\mathcal{D}$ to compute an approximation called the empirical risk, $R_n(h)$. This is simply the average loss of our hypothesis on the training data.

The Law of Large Numbers tells us that for any fixed hypothesis $h$, as our sample size $n$ grows, the empirical risk converges to the true risk ($R_n(h)\to R(h)$). This suggests a natural learning strategy: Empirical Risk Minimization (ERM). We can try to find the hypothesis $\hat{f}$ that minimizes the empirical risk on our training data.

However, naively minimizing the training error can be a trap. If we search for a function in a too-large, unrestricted space, we can easily find a hypothesis that perfectly "memorizes" the training data but fails spectacularly on new data. This phenomenon is called overfitting.

The solution is to not search over all possible functions, but to restrict our search to a predefined set of functions called the hypothesis space, denoted by a script $\mathcal{F}$. This could be the set of all linear functions, all polynomials up to degree 3, or all neural networks with a specific architecture. By choosing $\mathcal{F}$, we embed our assumptions about the problem's structure, aiming for functions that generalize well. This leads to the principle of Constrained Empirical Risk Minimization.

The following video segments will guide you through the introduction of empirical risk, the problem of overfitting, and the solution of using a constrained hypothesis space.

A Deeper Look: The Sources of Error

We can now see that the total error of our final learned function, ${\hat{f}}_n$, comes from two distinct sources. Let's formalize this.

1. Approximation Error (or Bias): This error arises from our choice of hypothesis space $\mathcal{F}$. Even the best possible function within our chosen space, $f_{\mathcal{F}}=\arg {\min }_{h\in \mathcal{F}}R(h)$, might still be a poor approximation of the true Bayes predictor $f^{\ast }$. If $\mathcal{F}$ is too simple (e.g., trying to model a complex, non-linear phenomenon with only linear functions), our approximation error will be high.

2. Estimation Error (or Variance): This error arises from the fact that we are working with a finite training sample ${\mathcal{D}}_n$, not the full distribution $P(X,Y)$. Our algorithm finds ${\hat{f}}_n\in \mathcal{F}$ by minimizing the empirical risk, not the true risk. The difference between the performance of ${\hat{f}}_n$ and the best-in-class function $f_{\mathcal{F}}$ is the estimation error. This error is due to the "noise" and randomness in our specific, finite sample.

The diagram below visualizes this decomposition.

Understanding this trade-off is fundamental to machine learning. A very complex hypothesis space (like a very deep neural network) might have low approximation error but can suffer from high estimation error, as it might overfit the limited training data. A simple hypothesis space (like a linear model) may have low estimation error but suffer from high approximation error.

For a more detailed, mathematical treatment of these foundational concepts, you can refer to Chapter 3 of the Statistical Machine Learning notes by Louis Aslett. The sections on the problem setting, loss functions, and generalisation error are particularly relevant.

Conclusion

In this lesson, we have constructed the formal framework for supervised learning. We've moved from a general idea of "learning from examples" to a precise mathematical problem of function approximation.

Key Takeaways:

• Formal Problem: Supervised learning aims to find a function $h$ (hypothesis) that approximates an unknown target function, using a finite dataset $\mathcal{D}$ of $(x,y)$ pairs.
• Underlying Distribution: We assume the data is sampled i.i.d. from a true but unknown probability distribution $P(X,Y)$. This is our "test distribution."
• Goal (Risk): The ultimate goal is to find a hypothesis that minimizes the risk—the expected loss on unseen data from $P(X,Y)$. The theoretical minimum risk is the Bayes risk, achieved by the Bayes predictor.
• Method (Empirical Risk): Since we cannot compute the true risk, we minimize the empirical risk—the average loss on our training data.
• The Trade-off (Hypothesis Space): To avoid overfitting, we constrain our search to a hypothesis space $\mathcal{F}$. This introduces a fundamental trade-off between approximation error (how well $\mathcal{F}$ can model the true function) and estimation error (how well we can find the best function in $\mathcal{F}$ with finite data).

In our next lesson, we will dive deeper into this trade-off by exploring the bias-variance decomposition. This will provide a powerful and concrete lens through which to analyze model complexity, overfitting, and underfitting, building directly on the foundational concepts of approximation and estimation error we established today.