Recall that a kernel is a way of placing a data space into a higher dimensional vector space so that the intersections of the data space with hyperplanes in the higher dimensional space determine more complicated, curved decision boundaries in the data space. The main example that we looked at was the kernel that sends a two-dimensional data space to a five-dimensional space by sending each point with coordinates to the five-dimensional point with coordinates . If we wanted to give ourselves even more flexibility, we could pick an even higher dimensional kernel, for example by sending the point to the point in a nine-dimensional space.

This week, we’re going to go beyond higher dimensional vector spaces to infinite-dimensional vector spaces. You can see how the nine-dimensional kernel above is an extension of the five-dimensional kernel – we’ve essentially just tacked on four more dimensions at the end. If we keep tacking on more dimensions in this way, we’ll get higher and higher dimensional kernels. If we were to keep doing this “forever”, we would end up with infinitely many dimensions. Note that we can only do this in the abstract. Computers can only deal with finite things, so they can’t store and process computations in infinite dimensional vector spaces. But we’ll pretend for a minute that we can, just to see what happens. Then we’ll translate things back into the finite world.

In this hypothetical infinite-dimensional vector space, we can add vectors the same way that we do with regular vectors, by just adding corresponding coordinates. However, in this case, we have to add infinitely coordinates. Similarly, we can multiply by scalars, by multiplying each of the (infinitely many) coordinates by a given number. We’ll define the infinite polynomial kernel by sending each point to the infinite vector . In particular, every monomial in the variables and , such as or will appear in one of the entries of this kernel, possibly very far down the sequence.

In order to get back to the computational world, we can recover our original five-dimensional kernel by just forgetting all but the first five of the entries. In fact, the original five-dimensional space is contained in this infinite dimensional space. (The original five-dimensional kernel is what we get by projecting the infinite polynomial kernel into this five-dimensional space.)

Now take a deep breath, because we’re going to take this one step further. Consider, for a moment, what a vector is. If you ever took a mathematical linear algebra class, you may remember that vectors are officially defined in terms of their addition and multiplication properties. But I’m going to temporarily ignore that (with apologies to any mathematicians who are reading this.) In the computing world, we usually think of a vector as being a list of numbers. If you’ve read this far, you may be willing to let that list be infinite. But I want you to think of a vector as being a collection of numbers in which each number is assigned to a particular thing. For example, each number in our usual type of vector is assigned to one of the coordinates/features. In one of our infinite vectors, each number is assigned to a spot in our infinitely long list.

But how about this: What would happen if we defined a vector by assigning a number to each point in our (finite dimensional) data space? Such a vector doesn’t pick out a single point in the data space; rather, once you pick this vector, if you point to any point in the data space, the vector tells you a number. Well, actually, we already have a name for that: Something that assigns a number to each point in the data space is a function. In fact, we’ve been looking at functions a lot on this blog, in the form of density functions that define probability distributions. But the point is, we can think of these density functions as vectors in an infinite-dimensional vector space.

How can a function be a vector? Well, we can add two functions by just adding their values at each point. This was the first scheme we discussed for combining distributions in last week’s post on mixture models. The density functions for two vectors (Gaussian blobs) and the result of adding them are shown in the Figure below. We can multiply a function by a number in a similar way,  which would result in making the overall density lighter or darker. In fact, these are both operations that you’ve probably had lots of practice with in algebra class and calculus. So we’re not doing anything new yet, we’re just thinking about things in a different way.

The next step is to define a kernel from our original data space into this infintie dimensional space, and here we have a lot of choices. One of the most common choices is the Gaussian blob function which we’ve seen a few times in past posts. For this kernel, we’ll choose a standard size for the Gaussian blobs, i.e. a fixed value for the deviation . Then we’ll send each data point to the Gaussian function centered at that point. Remember we’re thinking of each of these functions as a vector, so this kernel does what all kernels do: It places each point in our original data space into a higher (in fact, infinite) dimensional vector space.

Now, here’s the problem: In order to bring things back to the computational world, we need to pick out a finite dimensional vector space sitting in this infinite dimensional vector space and “project” the infinite dimensional space into the finite dimensional subspace. We’ll choose a finite-dimensional space by choosing a (finite) number of points in the data space, then taking the vector space spanned by the Gaussian blobs centered at those point. This is the equivalent of the vectors pace defined by the first five coordinates of the infinite polynomial kernel, as above.  The choice of these points is important, but we’ll return to that later. For now, the question is how do we project?

For finite dimensional vectors, the most common way to define a projection is by using the dot product: This is the number that we get by multiplying corresponding coordinates of two vectors, then adding them all together. So, for example the dot product of the three-dimensional vectors and is .

We could do something similar with functions, by multiplying the values that they take on corresponding points in the data set. (In other words, we multiply the two functions together.) But we can’t then add all these numbers together because there are infinitely many of them. Instead, we will take an integral! (Note that I’m glossing over a ton of details here, and I again apologize to any mathematicians who are reading this.) The nice thing here is that if we multiply two Gaussian functions and integrate, the number is equal to a Gaussian function of the distance between the center points. (Though the new Gaussian function will have a different deviation value.)

In other words, the Gaussian kernel transforms the dot product in the infinite dimensional space into the Gaussian function of the distance between points in the data space: If two points in the data space are nearby then the angle between the vectors that represent them in the kernel space will be small. If the points are far apart then the corresponding vectors will be close to “perpendicular”.

The practical part

So, lets review what we have so far: To define an -dimensional Gaussian kernel, we first choose points in the data space. We can then calculate the kernel coordinates of any point in the data space by calculating its distance to each of these chosen data points and taking the Gaussian function of the distances.

To better understand how this kernel works, lets figure out what the intersection of a hyperplane with the data space looks like. (This is what is done with kernels most of the time, anyway.) Recall that a plane is defined by an equation of the form where are the coordinates of the point (in the higher dimensional kernel space) and are parameters that define the hyperplane. If we’re using a Gaussian kernel then, thanks to our version of the dot product, the values measure the distances to our chosen points. The decision boundary is thus the set of points for which the Gaussian function of the distances to these points satisfy this equation.

That’s still pretty hard to unpack, so lets look at an example where each of the values is either 1 or -1. Then near each data point with label , the value will be very close to 1, while the other values will be small, so the sum will be positive. Similarly, near a point with , the sum will be negative. Thus if then the decision boundary will separate the positive points from the negative points. In fact, it will carve out a region reminiscent of the Gaussian balls that define the kernel. One example is indicated on the left in the Figure below, where the colors indicate whether the coefficients are positive or negative. As you can see, the result looks something like a smooth version of the nearest neighbors algorithm.

If we adjust the parameters , this has the effect of changing the sizes of the Gaussian balls around the points, and thus moves the decision boundary towards or away from them, as on the right of the Figure. If a coefficient switches from positive to negative, the decision boundary will move from one side of a point to the other. If we have a labeled data set (which may or may not coincide with the points that define the Gaussian kernel) then training a linear classification algorithm (such as SVM or logistic regression) in the kernel space corresponds to moving this decision boundary around, within the constraints defined above, to maximize how many of the data points are on the correct side.

So, this gives us more flexibility for choosing the decision boundary (or, at least, a different kind of flexibility) but the final result will be very dependent on the vectors that we choose. If we choose too many (such as if we let the points that define the kernel be the same as the data points) then we will risk overfitting, similar to how the nearest neighbor algorithm tends to lead to overfitting. What we really want is a small number of points that are evenly distributed throughout the set, ideally such that each of the points is close to mostly points in the same class.

Finding such a collection of points is a very different problem from what we’ve been focusing on in the posts so far on this blog, and falls under the category of unsupervised learning/descriptive analytics. (In the context of kernels, it can also be thought of as feature selection/engineering.) In the next few posts, we’ll switch gears and start to explore ideas along these lines.

As usual, we will start by considering two-dimensional data so that we can visualize what’s going on. Our two-dimensional data lives in a two-dimensional plane, which we can think of as a piece of paper. A kernel is a way of placing this two dimensional plane into a higher dimensional space, so that it is curved in the higher dimensional space. (In other words, a kernel is a function from the low dimensional space into a higher dimensional space.) So, for example, we might place the plane into three dimensional space so that it curves up along one axis, as in the Figure below. Here, the cross sections of the plane in three-dimensional space are parabolas.

The goal of the kernel is to make it so that two classes of data points that can only be separated by a curved line in the two-dimensional space can be separated by a flat plane in the three-dimensional space. This may seem strange that in order to make data points that follow a curve into data points that follow a line, we make the plane even more curved. But in fact, by adding more dimensions, what we’re doing is adding more flexibility for the lines/planes/hyperplanes to move around in. For example, in the data set shown below on the left, there is clearly no line that separates the two blue points from the two green points. However, when we place this data set in three dimensions using the kernel from the first Figure, the two blue points are lifted up, as on the right, so that there is now another plane (drawn in red) that separates blue from green, shown in the bottom right. This plane intersects the two-dimensional space in a curve shown in the bottom left figure.

In general, what the kernel does is to make it so that any plane in the three-dimensional space intersects the two-dimensional plane that contains our data in a curved line rather than a straight line. If we use a kernel that places the plane in an even higher dimensional space, then the hyperplanes in these higher dimensional spaces will intersect the two-dimensional space in potentially more complicated curves, giving us more flexibility to choose the curve that separates the data.

We can think about this in terms of adjusting/tuning parameters of the separating curve, as we did in the post on general regression. With a line/plane/hyperplane, the number of parameters that you’re allowed to adjust is equal to the number of dimensions plus one. By placing the space containing the data set into a higher dimensional space, we effectively give ourselves more parameters to choose a hyperplane in the higher dimensional space. Because of how this hyperplane intersects the original space, these extra parameters end up determining how the separating shape in the original space containing the data points can curve around the data.

So, the general procedure is to place the labeled data points into a higher dimensional space using a kernel, then run SVM or logistic regression (or any other classification algorithm) on the data in this higher dimensional space. This will (hopefully) give us a hyperplane that separates the two classes in the higher dimensional space. The intersection of this hyperplane with the curved copy of the original data space will determine a curved shape in the original data space that still separates the two classes of points. In fact, we could also run this process with linear regression, and the results would be effectively the same as using a more general form of regression, as in my earlier post.

I think it’s worth going into a bit more technical detail at this point, but if you don’t like equations, feel free to skip to the next paragraph. One of the simplest examples of a kernel is a function that takes each two-dimensional point to the five dimensional point . A hyperplane in the five-dimensional space is determined by an equation of the form , where and are parameters that we allow SVM or logistic regression to choose for us. Note that the , and parts are meant to indicate the third, fourth and fifth coordinates of the five dimensional space. However, if we think of them as products of s, s and s, then they define a curve in the plane, which happens to be the intersection of the hyperplane with the two-dimensional space that contains the data. Thus we can interpret the results of SVM or logistic regression on the higher dimensional space as a curved separating shape in the lower dimensional space. There are many other types of kernels, using more interesting functions, but the basic principle is the same.

Note that in practice, one generally doesn’t need to explicitly calculate the coordinates of the data points in the higher dimensional space when using a kernel. Instead, it’s often possible to make the calculations needed for a given classification algorithm, such as distances and angles in the higher dimensional space, but without calculating the new coordinates. So if we wanted to get really abstract, we could think of a kernel as a new definition of distances and angles, with or without explicitly placing the data into a higher dimensional space. We’ll explore this idea further in later posts.

For now, keep in mind that a kernel is not a silver bullet that will allow you to solve every classification problem without any effort. The more dimensions we put in our kernel, the more flexibility we have, but picking a kernel with more parameters/dimensions will be more computationally expensive. So it’s better to pick the simplest kernel that you can get away with, and this requires having a really good understanding of your data before you even get to the modeling step.

Another reason to try and pick the simplest possible kernel is that, as with general regression, the more flexibility you allow the model, the greater the risk of over fitting. We can always find a kernel in which the two classes of data points are linearly separated, but this may not be the best one to use. Remember that the model that we want is the one that is best at predicting new data points, but not necessarily the best at predicting existing data. As always, one can get a rough idea if a model is over-fit by splitting the initial data into a training and evaluation set. However, in specific situations there may be better ways. In general, the best way to make sure you have a good kernel and a good model is to understand your objective, understand your data, and understand the tools at your disposal.

One way we might do this would be to divide everyone’s salary by $10,000 (in the data set, not in real life!) so that a difference of one spice level would have the same impact on the distance as a difference of $10,000 in salary. This will make our notion of distance a little more reasonable. However, I just chose the number $10,000 based on intuition – it might have been better to scale by a larger number or a smaller number. We really need a more objective way to choose how much to scale each dimension by, and there are a number of possible choices.  But before we look at some of them, lets consider the geometric picture.

Dividing the salary dimension by 10,000 has the effect of shrinking the data set in the direction corresponding to salary. That’s because for two people who have all the same values, but their salaries are different by $10,000, the distance between them will become 1 instead of 10,000. You can see the effect of this on the Voronoi cells for one example below. As expected, this makes a drastic difference in the middle of each picture, where it switches from green to blue depending on how we scale the dimensions.

Scaling the dimensions will have a similar impact on most of the data analysis algorithms that we’re going to look at, though it’s most obvious for Nearest Neighbors. So choosing the right scale for each dimension (i.e. how much to multiply it by) is a vital step in the process of preparing data. One common approach is to scale things so that the possible values for each variable are between 0 and 1. For example, we would divide each person’s spice preference by 5 so the possible choices become 0, .2, .4, .6, .8 and 1, rather than 0,1,2,3,4 and 5. If we were keeping track of people’s ages, we might subtract 18 from each person’s age, then divide by 82 so that someone who is 18 gets the value 0 and someone who is 100 gets the value 1. This leaves out some potential ages, but it seems reasonable that most people who are choosing restaurants would be between the ages of 18 and 100. A slightly more objective approach would be to look at the highest and lowest values for each dimension in our initial data set and scale so that the lowest becomes 0 and the highest becomes 1.

Things get more complicated if we try to do this for annual income. Incomes can range from zero to hundreds of millions (or perhaps more). However, the range in which most people would fall is much much smaller than the entire possible range. So if we have a single person in our data set with an annual income of $100 million, and we divide by this amount, then almost all of the points in our data set will end up between 0 and .001, which will make the income dimension essentially useless.

One way to minimize this issue is to scale by dividing by the variance of the values in a given dimension, rather than the entire range. The variance of a set of numbers measures how spread out they are in a way that takes into account all the numbers, not just the highest and lowest. So, if there are one or two numbers that are much higher or lower than the rest, the variance minimizes the impact that these outliers have on the scaling factor. For a detailed description of variance (and examples), see the wikipedia page for it.

In fact, one could go a step further by noting that the principal components defined in my previous post on PCA are the directions (not necessarily parallel to features) in which the variance of the data set is maximal. If we scale the data along the principle component directions so that each principle component has length one, then the data will be very evenly round. This is a more complicated linear transformation than just scaling individual features, and it leads us in the direction of kernels, a topic I will write about in much greater depth later on.

There are also more interesting ways to measure the “distance” between data points than the standard vector distance (i.e. Euclidean distance.) For example, when comparing customers of an online store, one might define the similarity between two customers as the number of types of items that both customers have bought in common divided by the total number of types of items either of them has bought. This value is equal to one if two customers buy the exact same thing and 0 if they haven’t bought any of the same things. (Also, dividing by the total number of purchases takes into account the fact that some customers buy more than others.) If we define the distance to be one minus the similarity, then two customers with more of the same purchases will be closer to each other than two customers with only a few purchases in common.

For now, though, the key is to note that there are a lot of options and some very important decisions to make, even with an algorithm as simple as Nearest Neighbors clustering. There is no one best way to scale the different dimensions: The best choice for how to normalize your data will depend on the type of data, what you plan to do with it and how you will evaluate the results.