Announcements¶

• HW 2 is due today at 8pm

• HW 3 out, due next Friday

• Upcoming office hours:

  • Today: Peer tutor Daniel Cho from 12:30-3:30pm in CCDS 16th floor
  • Today: Abhishek Tiwari from 4-5pm on CCDS 13th floor

• Read Tan, Steinbach, Karpatne, Kumar Chapter 7.3

Lecture 10: Supervised Learning¶

[This lecture is based on Prof. Crovella's CS 506 lecture notes, Pattern Recognition and Machine Learning by Christopher Bishop, and Introduction to Data Mining by Tan, Steinbach, and Kumar.]

10.1 The Supervised Learning Problem¶

Recall that there are, broadly speaking, two kinds of learning algorithms.

• Supervised learning: Data items have labels, and we want to learn a function that correctly assigns labels to new data items.

• Unsupervised learning: Data items do not have labels, and we want to learn a function that extracts important patterns from the data.

We have seen examples of unsupervised learning ($k$-means clustering and heirarchical clustering). Today we'll start talking about supervised learning.

Let's explore in more detail the data science aspects of supervised learning.

The supervised learning problem in general is:

• You are given some example data, which we'll think of abstractly as tuples $\left\{\right(x_i,y_i)|i=1,\dots ,N\}$.

• Your goal is to learn a rule that allows you to predict $y_j$ for some $x_j$ that is not in the example data you were given.

Typically $x$ is a vector.

We use the term "features" to refer to the components of $x$.

The collection $\left\{\right(x_i,y_i)|i=1,\dots ,N\}$ is called the training data.

• If $y$ is a continuous (numeric) value, then the problem is called regression.

  For example, in predicting housing prices, the features $x$ could be a vector containing lot size, square footage, number of bathrooms, etc., and $y$ could be the sale price of the house.

  In the regression case, you will usually be satisfied if your prediction is close to the true $y$ (it doesn't have to be exact to be useful).

• If $y$ is a discrete value (a label, for example) then the problem is called classification.

  For example, in image recognition, the features $x$ could be a vector that represents the pixels of the image, and $y$ could be a label such as "tiger," "tree," etc.

What do we have to assume to make this problem tractable?

We assume two things:

1. There is a set of functions ("rules") that could be used to predict $y_i$ from $x_i$. This allows us to turn the learning problem into one that searches through this set for the "right" function. However, this set is probably very large!

2. The rule for predicting $y_i$ from $x_i$ is the same as the rule for predicting $y_j$ from the new item $x_j$. Speaking probabilistically, we say that $(x_i,y_i)$ and $(x_j,y_j)$ are drawn from the same distribution.

10.2 A Toy Example of Regression¶

In order to explore these ideas a bit, we'll use a toy example of regression.

This is a very artificial example, but it will expose some important wrinkles in the supervised learning problem.

We will consider polynomial curve fitting.

Suppose we are given a training set comprising $N$ observations of a scalar value $x_i$, which we'll collect into the vector $x$.

For each $x_i$ we have a corresponding numeric value $y_i$, and these form $y$.

Here is a plot of the 10 training points:

The way we generated these points was to take $x$ as equal spaced points on the range 0 to 1,

and for each $x_i$, we take $y_i=\sin \left(2\pi x_i\right)$ plus a sample of a Gaussian random variable.

Many data sets are like this!

In many cases, there is some component of $y$ that depends on $x$, and some component that we treat as random, called "noise."

The "noise" component is typically not really random, but rather depends on features that we cannot see.

(Remember, probability is useful for exactly this case.)

Now for this toy example, we "happen" to know that the correct rule to use for prediction is:

and the Gaussian random addition does not depend on $x$ so we cannot hope to predict it.

Let's learn from this data.

We will consider a simple approach based on curve fitting.

The class of models we will consider are polynomials. They are of the form:

where $k$ is the order of the polynomial.

If we are given some $k$, then what we want to learn are the $w_i$s, that is, $w$.

The $w_i$s are the parameters of the model.

Recall that this function $y(x,w)$ is a nonlinear function in $x$ ... but it is linear in $w$. That is, all the $w_i$ terms appear only raised to the first power. For this reason, we can apply a linear model: namely linear regression.

Model Fitting¶

How will we fit our model, that is, learn the best parameters $w$?

We use a objective function to guide our search through the space of model parameters. For linear regression, we want to choose the parameters to minimize the least squares criterion:

This is a nonnegative function which is zero if the polynomial passes through every point exactly.

We often write ${\hat{y}}_n$ for $y(x_n,w)$.

Then:

In other words, the error function $E(\cdot )$ measures the distance or dissimilarity between the data and the predictions.

Finding a $w$ that minimizes $E\left(w\right)$ is a least-squares problem, and we know how to solve for it.

The resulting solution $w^{\ast }$ is the set of parameters that minimizes the error on the training data.

Model Selection¶

So we are done, correct?

Wait ... what about choosing $k$, the order of the polynomial?

The problem of choosing $k$ is called model selection.

That is, a polynomial of order 3 (a cubic) is a different model from a polynomial of order 2 (a quadratic).

Let's look at constant (order 0), linear (order 1), and cubic (order 3) models.

We will fit each one using the least squares criterion:

So it looks like a third-order polynomial ($k$ = 3) is a good fit!

How do we know it's good? Well, the training error $E\left(w\right)$ is small.

But ... can we make the training error smaller?

Yes, we can, if we increase the order of the polynomial.

In fact, we can reduce the error to zero!

By setting $k=9$, we get the following polynomial fit to the data:

So ... is the 9th order polynomial a "better" model for this dataset?

Absolutely not!

Why?

Informally, the model is very "wiggly". It seems unlikely that the real data generation process is governed by this curve.

In other words, we don't expect that, if we had more data from the same source, that this model would do a good job of fitting the additional data.

We want the model to do a good job of predicting on future data. This is called the model's generalization ability.

The 9th degree polynomial would seem to have poor generalization ability.

Let's assess generalization error. For each polynomial (value of $k$) we will use new data, called test data. This is data that was not used to train the model, but comes from the same source.

In our case, we know how the data is generated -- $\sin \left(2\pi x\right)$ plus noise -- so we can easily generate more.

Notice that as we increase the order of the polynomial, the training error always declines.

Eventually, the training error reaches zero.

However, the test error does not -- it reaches its smallest value at $k=3$, a cubic polynomial.

The phenomenon in which training error declines, but testing error does not, is called overfitting.

In a sense we are fitting the training data "too well".

There are two ways to think about overfitting:

1. The number of parameters in the model is too large, compared to the size of the training data. We can see this in the fact that we have only 10 training points, and the 9th order polynomial has 10 coefficents.

2. The model is more complex than the actual phenomenon being modeled. As a result, the model is not just fitting the underlying phenomenon, but also the noise in the data.

These suggest techniques we may use to avoid overfitting:

1. Increase the amount of training data. All else being equal, more training data is always better.

2. Limit the complexity of the model. Model complexity is often controlled via hyperparameters.

More Training Data¶

It's not necessarily true that a order-3 polynomial is best for this problem.

After all, we are fitting to a sine function, whose Taylor series includes polynomials of all orders.

But the higher the order of polynomial we want to fit, the more data we need to avoid overfitting.

Here we use an order-9 polynomial for increasing amounts of training data (N = 15, 50, 200):

We see that with enough training data, the high order polynomial begins to capture the sine wave well.

Parameters and Hyperparameters¶

Many times however, we cannot simply get more training data, or enough training data, to solve the overfitting problem.

In that case, we need to control the complexity of the model.

Notice that model selection problem required us to choose a value $k$ that specifies the order of the polynomial model.

As already mentioned, the values $w_0,w_1,\dots ,w_k$ are called the parameters of the model.

In contrast, $k$ is called a hyperparameter.

A hyperparameter is a parameter that must be set first, before the (regular) parameters can be learned.

Hyperparameters are often used to control model complexity.

Here, the hyperparameter $k$ controls the complexity (the order) of the polynomial model.

So, to avoid overfitting, we need to choose the proper value for the hyperparameter $k$.

We do that by holding out data.

10.3 Holding Out Data¶

The idea behind holding out data is simple.

We want to avoid overfitting, which occurs when a model fails to generalize -- that is, when it has high error on data that it was not trained on.

So: we will hold some data aside, and not use it for training the model, but instead use it for testing generalization ability.

Let's assume that we have 20 data points to work with, stored in arrays x and y.

scikit-learn has some functions that can be helpful.

We will use train_test_split():

Notice that train_test_split() splits the data randomly.

This will be important.

Our strategy will be:

• For each possible value of the hyperparameter $k$:
  • randomly split the data 5 times
  • compute the mean testing and training error over the 5 random splits

What are good possible values for the hyperparameter? It can depend on the problem, and may involve trial and error.

This strategy of trying all possible values of the hyperparameter is called a grid search.

Let's plot the mean for each value of k and its standard error ($\sigma /\sqrt{n}$):

From this plot we can conclude that, for this dataset, a polynomial of degree $k=3$ shows the best generalization ability.

Hold Out Strategies¶

Deciding how much, and which, data to hold out depends on a number of factors.

In general we'd like to give the training stage as much data as possible to work with.

However, the more data we use for training, the less we have for testing -- which can decrease the accuracy of the testing stage.

Furthermore, any single partition of the data can introduce dependencies -- any class that is overrepresented in the training data will be underrepresented in the test data.

There are two ways to address these problems:

• Random subsampling
• Cross-validation

In random subsampling one partitions the data randomly between train and test sets. This is what the function train_test_split() does.

This ensures there is no dependence between the test and train sets.

One needs to perform a reasonable number of random splits - usually five at least.

In cross-validation, the data is partitioned once, and then each partition is used as the test data once.

This ensures that all the data gets equal weight in the training and in the testing.

We divide the data into $k$ "folds".

The value of $k$ can vary up to the size of the dataset.

The larger $k$ we use, the more data is used for training, but the more folds must be evaluated, which increases the time required.

In the extreme case where $k$ is equal to the data size, then each data item is held out by itself; this is called "leave-one-out".

Conclusions¶

We have seen strategies that allow us to learn from data.

The strategies include:

• Define a set of possible models
• Define an error function that tells us when the model is predicting well
• Using the error function, search through the space of models to find the best performer

We've also seen that there are some subtleties to this approach that must be dealt with to avoid problems:

• Simply using the model that has lowest error on the training data will overfit.
• We need to hold out data to assess the generalization ability of each trained model.
• We control model complexity using hyperparameters
• We choose the best hyperparameters based on performance on held out data.

10.4 $k$-means Clustering with Real Data¶

Suppose we have a collection of documents (say, books) and we want to build a model to understand which documents are more (or less) related to each other.

How do we encode categorical or text data in a form usable by linear algebra algorithms? All of the math we've done so far expects inputs to be numbers, not strings.

Here's one idea:

As a "real world" example of $k$-means clustering, we'll use the "20 Newsgroup" data provided as example data in sklearn.

(http://scikit-learn.org/stable/datasets/twenty_newsgroups.html).

Getting to know the Data¶

Let's ask sklearn to calculate the TF-IDF score for each document in this dataset.

We'll talk about the particulars later in the course. For now, consider TF-IDF as a way to identify important words: it increases with the frequency of a word, but is offset by the number of documents a word appears in.

Next, let's look at a picture showing each of the vectors. Black dots denote document-word pairs that are rare (occur near-0 times) whereas brighter colors denote document-word pairs that occur frequently.

We find from this picture that our data is sparse: most words don't occur often in most documents. (Note that we have already removed words like "the" that occur frequently in all documents, using the stop_words command above.)

Selecting the Number of Clusters¶

Let's try several methods to predict the appropriate number of clusters. In the next few diagrams, we will run $k$-means clustering for $k$ between 1 and 10.

Let's first measure the total error of the clustering algorithm. Remember that this is defined as the sum of squared-distances between each point in the dataset and the nearest center.

This error will decrease as $k$ increases, because adding more centers means that the nearest one is even closer than before.

Next, let's use the ground truth labels and measure the Rand Index. Recall that it measures how often the clustering correctly groups the same points together, and correctly keeps apart points with different ground truth labels.

The graph below shows the Adjusted Rand Index, which essentially discounts the number of "correct" clustering decisions that could happen through pure chance alone.

Finally, let's measure the Silhouette Coefficient. This metric does not rely on the ground truth labels. Instead it evaluates how compact the clusters are.

Even though we know the data comes from 3 distinct forums, the Silhouette Coefficient happens to prefer larger choices of $k$. Let's explore the data more closely.

Looking into the clusters¶

Next, let's look at the distance between each pair of documents. The following image is a picture whose pixels correspond to the distance between document $i$ and document $j$, after sorting the documents based on their $k$-means clustering.

You'll see that there are four distinct groups of documents that are slightly closer to each other than to the other documents. Also, the fourth cluster is much smaller than the others.

Let's visualize with Multidimensional Scaling (MDS), which builds a 2-dimensional plot where the distances between points are "close" to their distances in the larger 9409-dimensional space.

Note that MDS is a slow algorithm and we can't do all 1700+ data points quickly, so we will take a random sample.