Data Sets as Random Samples

There are two general modes when analyzing data sets:

1. To deeply understand the peculiarities of a single dataset and say something meaningful about just that dataset.
2. Using a dataset to extrapolate to additional data.

For example, when rolling out the Covid-19 Vaccine, you might use some randomized controlled trial to say something about the population at hand.

For example, for the COVID-19 Vaccine, of the 21,720 people who received the vaccine, 8 people got covid more than 7 days after the second dose. In comparison, of the 21,728 participants who received a placebo, 162 people got covid. We would like to take this data and generalize it throughout the population.

We’ll start off with the assumption that data points are random samples from some underlying population. There’s a lot of things to be careful of when assuming this in the real world, but we’ll assume all our samples follow this rule.

Another example might be classifying spam, from an intiial labeled dataset. We learn an algorithm on the dataset, and then let it out in the wild, to have it label more things as spam.

Binary Classification

There are many types of learning problems, but we’ll focus on Binary Classification problems, which involve the following.

1. Data points correspond to points in $d$-dimensional Euclidean space ${\mathbb{R}}^d$. For the spam problem, this would be $d$ different words that we’re keeping track of.
2. There is a “ground truth” function $f:{\mathbb{R}}^d\to \{0,1\}$ specifying the correct classification of each datapoint (i.e. there is a mapping of every datapoint to true or false, and this never changes). The function f is unknown and is what we want to learn.
3. There is an unknown distribution $D$ on ${\mathbb{R}}^d$. We can simplify $D$ as the uniform distribution over a very large finite subset of $R^d$ (like all emails with at most 10,000 unique characters).

Here’s the problem solved by a learning algorithm:

Input: $n$ data points $x_1,\dots ,x_n\in {\mathbb{R}}^d$, with each $x_i$ drawn i.i.d from the distribution $D$, with a corresponding $f(x_1),\dots ,f(x_n)\in \{0,1\}$. The $x_i$ constitute the training data, where $f(x_i)$ is labeled as either true or false.

Output: The responsibility of the learning algorithm is to create a prediction function $g:{\mathbb{R}}^d\to \{0,1\}$.

Success criterion: the prediction function $g$ should be as close as possible to $f$. It would look something like this, where we want our function $g$ to match the line drawn here, $f$.

There are two more critical aspects of the learning problem:

1. The amount of data. The more data you have, the closer you are to learning about the ground truth function $f$.
2. The number of possible functions that might be the truth. The fewer functions that you’re trying to distinguish between, the easier the learning problem.

Training Error and Generalization

The goodness of a prediction function $g$ can be assessed with the generalization error, the probability that g disagrees with the ground truth $f$ on the label of a random sample.

$$generalizationerror(g)=P{r}_{x\sim D}[g(x)\ne f(x)]$$

We can’t calculate the generalization error of a prediction function, because we don’t know $f$ nor the distribution $D$. We do know $n$ points, and their ground truth labels, so we can grade $g$ based on that. This is called the training error of $g$:

$$trainingerror(g)=\frac{1}{n}\ast [numberof{x}_i^{\prime }swithg(x_i)\ne f(x_i)]$$

For any prediction function, its expected training error over the random sample is its generalization error. However, we don’t know if the training error of $g$ ona random sample is likely to be close to its generalization error – we don’t have enough data.

This can be phrased as “does g generalize?” and it depends on the algorithm and the size of the data.

For example, if a learning algorithm outputs a prediction function $g$ with generalization error much higher than its training error, it has overfit the training data. When a prediction function overfits its training data, it doesn’t say anything meaningful about the data.

Analysis: The Well-Separated Finite Case

Let’s start off with a simpler version of the learning problem with two assumptions:

1. (Finite) The ground truth function $f$ belongs to a known set $\{f_1,\dots ,f_h\}$ of $h$ different functions. That is, there are only $h$ different possibilites for what $f$ might be, and we know the options up front.

2. (Well-separated) No function (other than $f$) is extremely close to $f$, meaning that every candidate $f_j\ne f$ has generalization error of at least $e$.

PAC Guarantees: The Finite Case

Suppose we loosen the second argument, that there are no functions close to $f$, the ground truth function. We now might output this other function $f^{\prime }$, but if it’s similar enough to $f$, it should be fine. We can use the same logic, with the stipulation that the output of the learning function has a generalization error less than $e$.

$$n\ge \frac{1}{e}(\ln h+\ln \frac{1}{\sigma })$$

This is a PAC guarantee, which is “probably approximately correct”.

PAC Guarantees: Linear Classifiers

Now we loosen the first assumption, but with a caveat – that the ground truth function $f$ has some structure. If $f$ is unrestricted, from ${\mathbb{R}}^d$ to $\{0,1\}$, then the unseen points could be anything, and the learning algorithm could not meaningfully say anything about it.

Computational Considerations

The learning algorithm can be implemented in a few ways. If there are a finite number of candidates, then exhaustive search works. But for infinitely many linear classifiers, that won’t work.

One way is to use linear programming, or to use iterative methods like stochastic gradient descent, perceptron, etc.

Non-Zero Training Error and the ERM Algorithm

If the ground truth is not a linear function, we have to extend the learning algorithm somehow.