First, let me quickly review the idea behind a neural network: We start with a collection of neurons, each of which takes a collection of input values and uses them to calculate a single output value. Then we hook them all together, so that the inputs to each neuron are attached to either the outputs of other neurons or to coordinates/features of a data point that is fed into the network.

When you input a data point into neural network, the outputs of the first level of neurons are calculated, then they feed into the later neurons and so on until all the neurons have set their outputs based (directly or indirectly) on the input data. Abstractly, we can think of each neuron in a neural network representing an “idea”. The output of the neuron should be a value close to 1 if that “idea” is present in a given input data point, and close to 0 otherwise. The earlier neurons will represent relatively simple, low-level ideas, while the later neurons represent higher level, more abstract ideas that are combinations of the ideas defined by the earlier neurons. This perspective is kind of hard to grasp in general, but it starts to make sense in more specific contexts, such as analyzing pictures.

If we’re making a neural network to analyze images, then the input to the neural network will be a vector like we saw in the post on digital images: each dimension will represent how light one of the pixels is (or one of its RGB values if it’s a color image, but for simplicity lets stick to grey-scale). We saw that when we encoded images as vectors this way, vectors that were nearby in the data space corresponded to images that matched up very closely. We can use this fact to understand how the neurons in a neural network respond to an image.

The standard way for a neuron to compute its output is to take a weighted sum of its input values, then apply a function with a steep drop-off that that sends all values below some threshold to values near 0, and all valued above that threshold to values near 1. By a weighted sum, I mean that each input is multiplied by a preset value (or, rather, a value that is set during the training phase), then the results are all added together. These preset values define a vector with the same number of features/dimensions as vector defined by the input values, and this weighted sum is essentially a dot product of the two vectors.

If you don’t remember what a dot product is, don’t worry – all you need to know is that (under the appropriate assumptions that I’ll gloss over) the resulting value is higher when the two vectors are closer together, and goes to zero as the vectors move farther apart. (Gory details: The dot product of two unit vectors is the cosine of the angle between them, and cosine is close to one for small angles, then goes to zero as the angle increases, up to a right angle.)

So, for the neurons that get their input directly from each incoming data point, we can interpret this as follows: The fixed vector of weights defines an image. The neuron calculates its output by comparing the input image to this fixed image, and if these images are reasonably close, its output is close to 1. Otherwise, it’s close to 0.

If we want these front-line neurons to encode basic, low-level ideas, then we probably don’t want them to do this with the whole image. Instead, we can have each of these neurons hooked up to the pixels that form a small rectangle somewhere in the image, and each one will check whether the part of the image in that rectangle matches some fixed image (that was “learned” during the training process.) So, for example, if the fixed image looks like an eye, as in the Figure on the right, then the neuron will output a value close to 1 if there is a similar looking eye in its particular rectangle. There might be another neuron that checks if the image in the rectangle looks like a hand (or a paw?) and so on.

But here’s the problem: Since each neuron is hooked up to a particular rectangle of pixels, what happens if there’s an eye in the picture just a little bit to the left of the rectangle that our neuron is looking at (such as on the right side of the Figure)? Well, its rectangle will only see part of the eye, which won’t match very well. (The dot product only works well if the images match up pixel-to-pixel.) So we need another neuron to be in charge of checking whether the rectangle just to the left of the first neuron’s rectangle has an eye in it. In fact, we would need to fill the whole image with rectangles like this, and have a separate neuron for each of them.

But this introduces two new problems: First, we no longer have a single neuron representing a single “idea” – we have thousands of neurons representing the same idea, which means we need a much larger neural network to encode a relatively small number of ideas.

Second, remember that the weights used by each neuron come from a training process in which data is fed into the network, and the output is compared to a desired value. When the output is different from the desired value, the weights are changed in a way so that the output will be closer to correct next time. Because of the way that dot products work, this means that the first level of neurons will try to adjust their weights to match the data points that come in during the training phase. In order for one of our neurons that’s watching a particular rectangle to end up with weights that define the image of an eye, you need to have lots of input images with an eye in that particular rectangle. In order for the trained neural network to recognize an eye in a future image, there must have been a training image with an eye in the exact same spot.

A convolutional neural network attempts to fix these two issues by allowing a single neuron to watch many different rectangles in each incoming image. In other words, for each of the incoming rectangles, a convolutional neuron will calculate a dot product between its fixed vector and the vector defined by this rectangle, then it will combine all the values in some way, such as by adding them together or taking a maximum.

Lets say we have a convolutional neuron that takes the maximum over all these rectangles and whose fixed vector defines the image of an eye. Then the output from this neuron will be close to 1 whenever there is an image resembling an eye (at the correct scale) anywhere in the picture. So this neuron captures the low-level idea of “an eye” in a much more useful way than a standard neuron.

Things get slightly more complex during the training process, but recall that the standard way of training a neural network is mostly agnostic to how the neurons calculate their output values. In particular, you only need to be able to determine what changes to the weights in the neuron will improve the orverall score for any given input vector. This is slightly more complex for a convolutional neuron than for a standard neuron, but once you get it right, the first layer of neurons in a convolutional neural network will begin adapting themselves to small images that commonly appear anywhere in the input images that you use to train the network.

Recall that in a classification problem, you’re given a training set consisting of data points with labels (we’ll call the labels A and B) and an evaluation set of data points without labels. The problem is to assign labels to the points in the evaluation set. If someone else (such as the Kaggle organizers) happens to know what the labels on the evaluation data points should be, they can calculate the accuracy of your answers by taking the number of correct labels and dividing it by the number of points in the evaluation set. So, if you got them all correct, the accuracy is 1. If you guessed at random, you would expect the accuracy to be around 0.5. (And if you get anything below 0.5, then you probably did something very very wrong.) There are some issues with this method of scoring, such as that if 90% of the evaluation points are supposed to have the same label, then you can get 90% accuracy by guessing that label for all the evaluation points. As it turns out, the ROC score fixes this issue, though there are also other reasons to use it.

Sometimes, in addition to labels for each point, your classification algorithm can also give you some measure of “confidence” in the predicted label. For example, the logistic regression algorithm technically doesn’t assign labels to data points – it assigns values from 0 to 1. We can interpret data points with low values as being likely in class A, and high values as likely in class B (assuming we set up the training algorithm that way). In particular, the lower the value, the farther it is from the decision boundary on the A side, so the more “confident” we can be in that label. Similarly, higher values are deeper into the B side of the decision boundary, so we can confidently assign label B. However, values near 0.5 are right near the decision boundary, so even a little bit of noise could have pushed them into the wrong class.

You can do something similar with random forests as well: For each point in the evaluation set, take the number of decision trees in the forest that assign label B to the point, then divide by the total number of trees. You can use this number the same way as the number from logistic regression: if most of the trees agree on the label, then the resulting low or high value tells you to have high confidence in label A or B, respectively.

Given all the scores of this form for the points in the evaluation set, you could then classify each of the evaluation points by assigning class A to all the points with value less than 0.5, and class B to all the points with value about 0.5, then calculate the accuracy. But this essentially throws away the “confidence” information. Precision/recall and the AUC/ROC score are two ways of using the confidence information in evaluating how well the points were classified.

To understand the ROC curve, imagine that instead of handing all your labels in to the Kaggle judge at the same time, you were asked to tell the judge which data points you think have label A, one at a time, starting with the ones you’re most confident in. Moreover, you have to keep going until you run out of data points, which means you even have to include on this list the points that you think should have label B. But the points that you predict label B for will go at the end: high confidence that a point has label B counts as (very) low confidence that it has label A. So if you had a value from 0 to 1 for each point, e.g. from your logistic regression or random forest algorithm, you would start with the point with the lowest score, then the next lowest scoring point and so on. (Equivalently, you could switch the roles of A and B, and start with the highest scoring points.)

As you’re reciting this list of points, the judge (who knows the correct answers) keeps track as follows: They start by placing the tip of a pen at the top-left corner of a grid of squares. Each time you name a data point that really has label A, they move the pen to the right one square, drawing a horizontal line. Every time you name a B data point, they move the pen down one square, drawing a vertical line. The resulting path might look something like the one in the Figure below.

During this process, the total number of times they move their pen to the right is the number of evaluation data points that really have label A (let a be this number), and the number of times they move it down is the total number of points that really have label B (call this b.) So no matter what order you name the points in, their pen will go right a total of a times and down a total of b times, ending up at the opposite corner of a rectangle with dimensions a x b. The resulting curve splits this rectangle into two pieces and the “area under the curve” is the area of the lower piece, shown in blue on the right above. We want the ROC score to go from 0 to 1, just like accuracy, so the ROC score is the area of this lower piece divided by the total area of the rectangle.

But what does this number mean? Well, the best you could do would be to name all the points that actually have label A first. As you’re doing this, the judge’s pen moves across the top of the rectangle. When it gets to the upper right hand corner, you have to keep naming points, so the pen moves down the right side of the triangle as you name all the B points. In this case, the area below the curve is the entire rectangle, so the ROC score is 1. On the other hand, if you were unfortunate enough to name all the B points first, the resulting curve would follow the left and bottom sides, for a score of 0.

Now the hard question: What would we expect the ROC score to be if we named points at random? Or put more precisely, what would the average ROC score be over all the different possible orders that we could name the points in? Rather than trying to work out all the possible orders and calculating the average, there’s a symmetry argument that will give us the answer: For any given order, if we were to name the evaluation points in the exact opposite order, the resulting ROC curve would be the result of rotating the original curve by 180 degrees. This rotation swaps the above and below regions, so the sum of the areas under the two curves is equal to the area of the rectangle. The average of the two areas is therefore half the area of the rectangle and the average score is 0.5. Every possible order of the data points falls into a unique pair with average score 0.5, so the overall average of all the scores is also 0.5. (This is true no matter how many points are in classes A and B.)

In other words, the expected score for a random order is 0.5, the same as the accuracy. Note that this is the same score we would get if we replaced the ROC curve with a straight line between opposite corners. This is important for understanding how the ROC curve behaves if you have multiple points with the same confidence score. For example, lets say that you have three points that get a score of 0.2 from logistic regression, and it happens that two of these really have label A, while the third has label B.

If you were to randomly choose an order to name them in, the point with label B could come first, second or third, and each of these possibilities would lead to a different final ROC score. However, you can apply a symmetry argument similar to the one above to see that the average score between these three possibilities is the same as the score you would get by drawing a diagonal line over two squares and down one.

So in general, when there are multiple points with the same confidence value, the convention is to draw the ROC curve with a diagonal line that goes across by the number of actual A labels and down by the number of B labels in the set. So, for example, if you gave all the points in the evaluation set a score of 0.5, the ROC curve would just be a diagonal line between opposite corners of the rectangle and the ROC score would be 0.5. On the other hand, if you gave some of the points label 0 and the rest label 1, then the ROC curve would consist of two diagonal lines that meet at a point whose coordinates correspond to how many points you labeled correctly.

With a little work (that I’ll let you figure out yourself), you can show that the ROC score in this case is equal to the number you get by calculating the correctly labeled A points divided by the total number of A points, then calculating the number of correctly labeled B points divided by the total number of B points, and averaging these two numbers. This isn’t exactly the accuracy, as defined above – it’s more like a weighted accuracy that takes into account the size of each class. In fact, it’s better than accuracy because it solves the problem that I mentioned at the top of the post: If you have an evaluation set with 90% of the points labeled A, and you guess label A for all of them, while the accuracy would be 90%, this “weighted” accuracy defined by the ROC score would be 0.5, the same as random guessing since the ROC curve would be just a diagonal line.

In fact this brings up an interesting point: The ROC score when we assign all points a confidence score of 0.5, or when we assign them all 0, or for that matter if we assign them all the same number, no matter what that number is. More generally, since the ROC is determined entirely by the order of the points, it doesn’t matter if the confidence scores run from 0 to 1, or -3 to 5, or any other scale.

So, now that we understand the ROC score, what about precision and recall? It turns out these two measures are essentially a way of describing a single point on the ROC curve. Imagine if, instead of asking you to name evaluation points one at a time, the judge asked you to provide a single set of points, of any size you choose, with points that you think should have label A. This list doesn’t need to contain all the point you think have label A, but it shouldn’t contain any points that you think have label B.

The recall of the list you provide is the number of points on you list that really have label A divided by the total number of points in the evaluation set that really have label A. The precision of your list is the number of points on you list that really have label A divided by the total number of points in the set you provided. Notice that the only difference between these two values is the denominator (the value that you divide by), and both recall and precision take values between 0 and 1.

But to really understand what these values mean, we should consider how they’re related for different sets of points. You already have an order on the evaluation points defined by your confidence score, so why not play the precision/recall game once with the first point in the confidence ordering, then a second time with the first two points, then again with the first three points and so on. What happens to the precision and recall as you do this?

Well, as you get farther along the list, you will (at least occasionally) add more points that really have label A, so the numerator in both recall and precision goes up or stays the same. As the list gets bigger, the denominator in the recall stays the same, so the recall will go up each time you add another point with label A to the list and stay the same when you add a B point. On the other hand, the denominator on the precision goes up by one each time you add a point to the list. So, the precision will go up when you add an A-labeled point, and will go down whenever you accidentally add a B-labeled point.

In fact, it turns out you can read the precision and recall off of the ROC curve. At each point that you stop on while drawing the ROC curve, recall is how far to the right the pen is divided by the total width of the rectangle. Precision, on the other hand, is a bit tricky to read: Given a point on the ROC line, draw a diagonal line up and to the right at a 45 degree angle until it hits the left edge and the top edge of the rectangle, as in the Figure below. (You may have to extend these edges down and to the right, respectively.)  The distance from the point on the ROC curve to the bottom left endpoint of this line segment, divided by the total length of the line segment is the precision. (I’ll again leave it to the reader to work out why this is true.)

The goal of the precision/recall game is to make both precision and recall simultaneously as high as possible. However, unlike the ROC score where you get a well defined score, with precision and recall, there may not be a single pair. For example, you might get 90% precision with 20% recall, but only 70% precision with 90% recall. Which of those precision/recall pairs is better/more important depends on the application.

Lets start off with an example: Imagine you’re designing a robot with a solar powered battery charger. Whenever the robot’s battery is low, you want it to stop whatever it’s doing and find a sunny spot to recharge its batteries. How would you design this part of the robot’s behavior?

There are obviously many different possibilities and I’m going to describe one that will foreshadow later ideas in the post. But first note why this counts as optimization: The collection of possible options is all the places that the robot can stop. The measure that we’re trying to maximize is the amount of sun light in the location.

We’ll put four light sensors on our robot, one at each corner of its square base. So, if the robot is in a patch of shade, but one of its sides is closer to the edge of the shade, the light sensors on that side of the robot would read a slightly higher level of light, as on the left in the Figure below. Since the robot will want to move out of the shade, whenever one of its light sensors reads a higher level of light than the others, the robot should move in direction of that sensor. If it ever gets to a spot where all four sensors are reading the same level of light, it will stop, since it has no reason to pick any one particular direction.

A similar problem would be to design a robot that tries to find the highest altitude in a hilly terrain, as on the right of the Figure. In fact, from an abstract perspective, if we imagine plotting the light level as a function, these two problems are essentially the same: the highest level of light would be the highest point on the hill defined by the function.  If the robot is on the slope of a hill, then the altitude sensor that reads the highest altitude would be on the side of the robot that points up the hill. So in order to move up the hill, the robot should always move towards the sensor that reads the highest altitude/light level.

Each of these two robots is mimicking an algorithm called gradient descent, which gets its name from a mathematical tool called the gradient that you might have learned about in multi-variable Calculus. Given a two-dimensional function, the gradient defines a vector that points in the direction in which the “hill” is steepest. Technically, the robots are mimicking gradient ascent since they’re trying to go up instead of down – In principle, gradient descent and gradient ascent are both the same thing, but people usually refer to it as gradient descent because it’s traditional to try to minimize a function (such as some sort of cost).

The gradient descent algorithm works the same way these robots do: Given a function, start at some initial point and figure out in which direction the function is “steepest”. Then move the point in that direction and repeat the process. Eventually (if you set things up correctly) you’ll get to a point where the function is close to flat. When that happens, you stop and choose whatever point you ended at.

Before we get into how this applies to data analysis, there are a few things I should point out: First, as we’ve noted, either of our two robots will stop when all four sensors read the same. For the hill-climber, this means that it’s on a horizontal patch of ground – if it’s lucky, this will be at the top of the highest hill. (As a side note: If you took calculus, you may recall that maximum and minimum points of a function occur when the derivative/slope is zero/horizontal. With the robots, this is the same idea but in two dimensions instead of one. In fact, you calculate the gradient by combining two (partial) derivatives.)

Second, note that if there are multiple hill tops in the terrain, or multiple light spots surrounded by shade, as in the Figure below, then our robot could easily end up stuck in a spot that is not the overall best, but is better than any of the nearby spots. If our robots had cameras and could get a view of the distant terrain, they might be able to figure this out and move to a better spot, but in actual gradient descent problems, that usually isn’t a possibility. Optimization problems in which there is exactly one maximum (or minimum if that’s your thing) are called convex problems, and these tend to be very easy to solve. In particular, gradient descent will always lead you to the solution to a convex problem, and in some cases you can avoid gradient descent all together and calculate the solution directly. (More on that later.)

Third, note that while our robots are moving around in a two-dimensional landscape, the gradient is defined for as many variables as we want, and we can carry out gradient descent for any function of any number of variables. (It’s just harder to visualize.)

But why would we want to? This blog isn’t about designing solar powered robots; it’s about data analysis, and the optimization problems that we’ve discussed in past posts seem very different. For example, in regression, we want to choose a probability distribution that maximizes the total value of all the points in our data set. This differs from the robots in two ways: First, we’re calculating the values of a whole set of points instead of just one. Second, we’re moving the function (i.e. the probability distribution) around while leaving the points fixed. Most of the other types of optimization had a similar feel.

This is where the magic of configuration spaces comes in. Recall that a configuration space is a way of thinking about all possible configurations of a complicated system as a single object/space, in which each configuration corresponds to a single point in the space. In the configuration spaces post, we mostly thought about abstract configuration spaces that we could only implicitly study by taking data samples. But there are also very simple, concrete configurations spaces.

For example, consider the configuration space of all lines in the plane. Every line is defined by a slope and a y-intercept. That’s two numbers, which we can think of as coordinates defining a point in the plane. In other words, the configuration space of lines in the plane is itself a plane. (Technically this leaves out vertical lines, but lets not worry about that right now.)

Each line also defines a probability distribution concentrated along the line. In the post on linear regression, I described how we can calculate the likelihood of each probability distribution by adding up the values of the data points with respect to the distribution. We can think of this as a function on the two-dimensional plane of probability distributions concentrated along lines.

Recall that the regression line is simply the line for which the corresponding probability distribution has the highest likelihood calculated in this way. From the perspective of configuration spaces, this line is a point where the expectation function – a function on the plane like the light level or the elevation that our robots were interested in – is maximal. So by calculating the gradients of this function and carrying out gradient descent, one can find the best regression line the same way the robots found their ideal spots.

As it turns out, though, linear regression is a convex problem; there’s always a single local maximum. Moreover, the equation for the expectation, and the resulting equation for the gradient are simple enough that this maximum point can be calculated directly, without bothering with the repeated process that gradient descent requires. However, many of the other optimization problems that come up in data analysis – notably linear regression, and expectation maximization – require proper gradient descent.

So gradient descent (on configuration spaces) ends up playing a very large role in data analysis. In fact, now that you know what to look for, you can go back through the earlier entries on this blog, and see if you can spot all the places where gradient descent was hiding in the background. (I haven’t done this myself, but I bet it’s in most of them.)

But first, I should explain where the term tree in decision tree comes from, which I didn’t want to try and squeeze into the last (already long) post. You can think of the decision tree algorithm in terms of a flow chart: You ask the first question, then depending on the answer you either move down and left or down and right to a different second question, as in the Figure on the right. Each question defines a place where two “branches” form a fork and the resulting diagram looks like the roots of a tree. (Maybe it should be drawn upside down so it looks like the branches of a tree…) For a given point, if we follow each sequence of answers down to the end of the branch, the color at the tip of the root tells us the final answer for how we should classify it.

As I described last time, the key to a good decision tree is the choice of questions, i.e. which dimension/feature we ask about, and the choice of threshold, i.e. where we make the cutoff between a yes answer and a no answer. There isn’t a standard way to determine this, but the rough idea is that the new regions defined by each question should have either a lot more greens than blues or a lot more blues than greens. That way, we’re probably making progress towards cutting the data space into regions of all blue or all green.

One common way to make this precise is by calculating the entropy of the regions. When you read the word entropy, you may think of something along the lines of disorder, and way we are using it here is related to this. Roughly speaking, the entropy measures how hard it will be for us to correctly predict the color of a data point based solely on the fact that it is in a given region. To calculate the entropy of a region, we’ll first find the proportion of green data points to the total number of data points. For example, if there are 10 data points and three of them are green then the proportion is .3. We then feed this number into the entropy function, which is shown in the figure on the left. The function takes the value 0 when the proportion is either 0 or 1, i.e. all the points in the region are the same color, so we can very easily predict what color any one of them will be. When the proportion is .5, the entropy function is at its maximum, so there are the same number of green and blue data points and there is no good way to make a prediction: For either choice, we will be wrong half the time.

Note that the entropy function is symmetric if we interchange 0 and 1, so it will give us the same answer if we use the proportion of blue data points instead of the proportion of green data points. If we have more than two classes, then the entropy calculation is a little more complicated, but lets not go into that now.

As we see, the entropy measures the extent to which there are more blues than greens or more greens than blues, taking on smaller values as we get closer to either all green or all blue. Going back to decision trees, the goal should be to choose our dimensions/features and thresholds so that the entropy in each of the resulting regions is as low as possible. In practice, it is common to measure the change in entropy from the original region to each of the new regions that result from the cut, rather than the absolute entropy. For each fork in the decision tree, we can then search over all the dimensions/features and all the possible cutoffs, and choose the dimension and cutoff that causes that largest drop in entropy. The algorithm stops when there are no new questions that will cause the entropy of the final regions to decrease. In particular, this will be the case if each of the final regions contains all blue data points or all green data points. (Though that’s not the only situation in which the algorithm will stop.)

This is an example of what’s called a greedy algorithm: At each step, the algorithm makes the decision that will maximize its immediate reward, i.e. the drop in entropy. However, as we all know, making the decisions that maximize immediate rewards do not always pay off in the long run. And indeed, this is often the case with decision trees. Ideally, we would be able to devise a strategy for choosing questions that isn’t too greedy, but is still self serving enough to come up with a good final solution.

In fact, there is another related problem: If we keep asking questions until each region is all green or all blue then we will be at a severe risk of overfitting since, as we saw last time, each of the final regions may only contain one or two data points. This is reminiscent of the nearest neighbors classification algorithm, in which we formed a Voronoi cell around each individual data point (and which we fixed by switching to the K-nearest neighbors algorithm.) For decision trees, we might be able to fix this if we stop asking questions before we get all the way to cells with all blue and all green, but then we have to decide what the stopping point is – if we stop too early then our model may be too simple to capture the structure of the data. (We may end up with underfitting!)

Random forests are the most common way to deal with these two issues. The idea behind a random forest is to generate a large number of decision trees, but to modify the way we construct the trees in two ways: First, rather than always selecting the question and the threshold that maximally reduces the entropy, or however we select them (which would produce the same tree over and over),  we add an element or randomness to the process. For example, we might randomly select which dimension/feature each question will be about, but then we will still choose a threshold that maximizes the drop in entropy, over all the possible thresholds for that one dimension. (Update:) Another way to add randomness is a proceedure called bootstrapping or bagging, in which we train the decision trees on subsets sampled from the original data set.

Second, we will limit how deep each of the resulting trees is allowed to go, for example by placing a limit on the total number of questions each tree is allowed to ask. This means that each individual tree may not divide the data space up enough to get a consistently good answer.  But the hope is that the combined information of all the trees will lead to an accurate distribution. But this raises the question: How do we combine the trees?

The standard way to combine the trees is through a voting process, reminiscent of the method for multi-class classification: Given a new data point, we will run it through each decision tree in the forest and record how many trees vote for it to be a blue point and how many vote for it to be a green point. Whichever color gets the most votes, that’s the decision that the random forest makes. As usual, we will want to understand how this affects the probability distribution that is implicit in the final classification algorithm. An example with a random forest consisting of two decision trees is shown in the Figure below.

The distributions defined by two decision trees are shown on the left and middle. The final distribution, shown on the right, comes from super-imposing the decision boundaries of the two individual trees. Each region in the resulting distribution is colored green if it is contained in green regions in both of the original two trees. It’s colored blue if it is contained in two blue regions, and grey if it is in one of each. These grey regions are ties – If I had combined three trees instead of two, there wouldn’t have been any ties, but it also would have been a lot harder to see what was going on.

In practice, most random forests combine much larger numbers of individual decision trees and operate on much higher dimensional data sets. However, the process is essentially the same: The regions in the final model/distribution come from superimposing the decision boundaries from the individual trees. We have to be careful about the curse of dimensionality of course, for example by making sure that the total number of questions among all the trees is much larger than the number of dimensions in the data space. You can kind of see in the example that the resulting distribution looks slightly more rounded than the original. In fact, it’s again reminiscent of K nearest neighbors clustering, where we ended up cutting the data space into many more regions, but used a criteria for coloring the regions that looked farther afield, and thus smoothed out some of the artifacts of noisy data. A random forest does something very similar.

So, a random forest gives us another way to combine a number of simple models/distributions into a single more sophisticated one. As with neural networks, the random forest combines the decision boundaries of all the simple models. However, there is a big difference in training: In neural networks, the simple models are all trained simultaneously, taking into account the way that they will be combined by later. A random forest, on the other hand, trains each decision tree independently.

There are tradeoffs between the two methods, and it’s tempting to assume that the more sophisticated method will always win. However, as it turns out, random forests are a very popular method because in practice, they work very well a lot of the time, and the small improvements that might come from switching to a more complicated method such as a neural network are not worth the potential head aches that come along with them.

The idea behind a decision tree is very simple, and can be compared to a game of 20 questions. Lets go back to our original classification example: Someone who is new to town has asked you for a restaurant recommendation and you want to use information about them to decide which restaurant to suggest. In 20 questions, we can ask the person yes/no questions, such as Do you like spicy food? Are you willing to spend more than $15? Are you in a hurry? The answer to each question should both give us a better idea of the best answer, and can also be used to determine what the next question will be. In other words, if they answer yes to the first question then the second question might be different than if they had answered no. At some point, we will get to the point where asking more questions won’t narrow things down any more, and at that point we make the best guess based on what we’ve learned.

So, how do we translate this into an algorithm? First, we will translate each yes/no question that we might ask into a number on a scale. For example, instead of asking whether the person likes spicy food, you could record their preferred spice level, say on a scale from 0 to 5. Then the original question becomes something like Is your preferred spice level greater than 2? Other questions might be What is your lunch budget? How much time do you have? The answer to each of these questions is on a number scale, and can be converted into one of the original yes/no questions by picking a specific cut off and asking whether the number is higher or lower than that cutoff. But here’s the important question: How do we decide which questions to ask, which cutoffs to pick, and what the final answer will be?

Following the theme of this blog, we’ll look for answers by translating the problem into geometry. We’ll start by asking a number of people who have tried some nearby restaurants to rate themselves on these different scales, then ask them what their favorite was. We can then think of each person’s responses as the coordinates of a data point, which we will draw in the data space, choosing the color of the point based on their favorite restaurant. If we were to do this with two questions, we would have two-dimensional data, which might look like the data points on the left in the Figure below. (There are only two colors, so this town only has two restaurants.)

Like the other classification algorithms that we’ve looked at, the decision tree algorithm will divide data the space into a number of regions and then color each region blue or green. To decide if a new person would like a given restaurant, the algorithm just needs to determine whether their data point is in a blue region or a green region. Before we try to understand how it decides the color of each region, we need to figure out what the regions look like and we’ll do this by figuring out when two data points will end up in the same region.

This is pretty straightforward: two data points will end up in the same region if they give the same answers to all the questions. We already know what the coordinates of the new point are. We ask the point questions by checking whether a certain feature/coordinate is greater than or equal to a certain value. Lets go one question at a time, and to make things simple, sticking with our two-dimensional data for now. If the first question is about the y-coordinate, then it divides the data into two sets: all those with y-coordinate above the threshold and all those below.

The decision boundary is the set of all points whose y-coordinates are exactly equal to the threshold, i.e. a horizontal line like the one shown on the left in the Figure above. One region is all the points above this line and the other is all the points below. If the question was about the x-coordinate, we would have a similar picture, but with a vertical line instead of a horizontal line. Notice that for the horizontal line that we chose, there are mostly (though not all) blue points above the line and mostly green below. So the line does a good job of narrowing things down, but to narrow it down completely, we’ll need to ask more questions.

On to the second question. Remember that this one will depend on the answer to the first question, so the set of points above the first decision boundary will be asked one question and the points below the decision boundary might be asked a different one. The question that we ask the lower region will divide it along a second horizontal or vertical line and a second vertical or horizontal line will divide the upper region, as on the right in the picture above. These questions happen to be about the x-axis, producing vertical decision boundaries, and note that the upper vertical line is different from the lower one.

The third round of questions allows us to divide each of the resulting four regions along a horizontal or vertical line and so on. In this case, three of the regions are already completely blue or completely green, so we don’t need to ask any more questions. The upper left region, however, has one blue point and one green, so we can ask it one more question, dividing it into two regions for a total of five, as on the left in the Figure below. In general, though, we may need to ask more questions. (And unlike in the game, we’re allowed to go past 20.)

Once we’ve determined all the questions, we need to color each region either green or blue. Again, this is pretty straightforward: Each region contains some number of blue and green points from the original data set, and we’ll color the region based on whichever color is more common. This is reminiscent of how we colored the regions in KNN, though the shapes of the regions determined by KNN are very different. In this example, each region is all green or all blue, but depending on the particular algorithm you use to construct your decision tree, this may not be the case. In theory, there may be some regions with an equal number of each color, but as I hinted at above, one generally chooses the decision boundaries so that each region has either mostly blue or mostly green data points.

As usual, it is much harder to visualize the regions defined by a decision tree for higher dimensional data, but we can use what we know about the two-dimensional case to get a rough idea. The decision boundaries in higher dimensions will be planes (in three dimensions) or hyperplanes (in four or more dimensions.) They will be “horizontal” and “vertical”, in some sense, so they will cut the data space into regions that are cubes (in three dimensions) or higher dimensional cubes in general.

This picture is reminiscent of the picture from the hierarchical approach to multi-class classification I discussed a few weeks ago. In fact, they’re essentially the same, but with two important differences: First, the decision boundaries in the multi-class classification scheme were allowed to be more complicated than just vertical and horizontal lines/planes/hyperplanes. There are versions of the decision trees algorithm that use general regression at each each step, creating more interesting decision boundaries, but from what I can tell, these are less commonly used. (If you happen to know this isn’t the case, please leave a comment below!) In particular, one of the main appeals of the constrained type of decision tree described above is that they can be expressed as a number of very simple rules that can be understood by a person.

The second difference is that each of the final regions in the multi-class schemes ended up with a different label. In the decision tree, however, we’ll usually have multiple regions with the same class. This allows the algorithm to define more sophisticated distributions, somewhat reminiscent of the way that we saw neural networks combining simple distributions. However, in the case of the decision tree, the combination is all done at once, rather than incrementally by the later layers of neurons.

Also, you may have noticed that I’ve been rather vague about exactly how we choose each question in the tree. That’s because there isn’t a single methods that is well agreed upon, and in fact, there are a number of very different criteria that have been proposed. There’s a good reason for this, but this post is already long enough, so it will have to wait until next week.

In the last two posts, I described how a single neuron in a neural network encodes a single, usually simple, classifier algorithm, then how multiple neurons can be linked together to combine the models from these classifiers into geometrically more complex shapes. In particular, the second of these posts explained the evaluation phase of a general neural network. In this week’s post, I’ll explain how our understanding of the evaluation phase can be used to explain the training phase of the a general network, through an algorithm called back propagation.

We’ll start with the simple neural network from last week’s post with three neurons shown below. Recall that each of the first two neurons defines a line that divides the two-dimensional data space into two regions. Together, these two neurons divide the plane into four regions and the third neuron determines which of these four regions get labeled 0 or 1.

As I described in the first post on neural networks, we can train a neural network one point at a time by a method very similar to the maximum likelihood estimation that we used for regression: For each new data point, we evaluate it using the neural network. If the answer that we get isn’t correct, then we determine how to adjust the parameters to make it closer. We then adjust the parameters accordingly and repeat for the next data point.

For a single neuron, with a logistic distribution, this is very straightforward: The decision boundary is a line, plane or hyperplane that separates the data space into two sides with the different labels. As in the first post, if a data point is on the wrong side then we move the decision boundary towards the point, in the hope of eventually moving it so that the point is on the correct side. If the a data point is on the correct side then we move the decision boundary away from it in order to increase the margin of error in the final distribution. This behavior was determined by the slope (or technically, the gradient) of the distribution at the data point, which told us which direction would increase or decrease the value.

For the distribution defined by a general neural network, we can think of the final distribution as a composition of functions, in the sense of calculus. From this perspective, the chain rule (or rather the multi-dimensional chain rule that one usually sees in Calculus 3) allows you to calculate the gradient of the final distribution in terms of the distributions defined by the individual neurons. This is how most neural networks determine how to adjust the parameters of each neuron, a procedure called back propagation.

For the example neural network above, lets see what would happen when a point is misclassified. In the last post, we considered parameters on the neural network that produced decision boundaries on the first two neurons making the four regions shown on the left below. If we choose a decision boundary on the third neuron as on the right, then the final distribution will be the one shown in the center.

The black point shown in the middle picture is misclassified, so if it shows up during the training phase, we will need to adjust the parameters. The first two neurons both see the point as being on the wrong side of their decision boundaries, so each of these decision boundaries gets moved towards the point, as indicated by the arrows in the middle picture. The last neuron also sees the point as being on the wrong side, so it also moves its decision boundary towards the point, as on the right. If the data point were white, it would have exactly the opposite effect on all three neurons.

To understand what adjusting this last neuron does to the final distribution, recall that the upper region in the middle picture, which appears to be white, is actually a very light shade of gray. Moving the decision boundary on the right towards the upper right corner has the effect of making this region slightly darker. Thus if there are enough black data points in this region, the final neuron will eventually switch the region to black, while white data points in one of the other corners may switch a different region to white.

So this neural network learns in two ways: The first two neurons try to find the decision boundaries that will split the data space into the best four regions. Then the third neuron tries to choose the shades for the four regions that best match the data.

In more complex neural networks with more layers of neurons, the neurons in the first layer will still determine the regions, while the later neurons will determine different ways to combine them. At first it may seem strange that we would need more than one layer to choose the regions, but remember that each of these later neurons is very restricted in the ways that it can combine the regions, the same way the initial neurons are restricted to linear decision boundaries.

Experts often think of it as having each neuron record a single concept. The early neurons record very primitive, very specific concepts. Then later neurons combine these specific concepts into more general concepts. For example, in the neural network that google research recently announced for image processing, we would expect the first layer of neurons to correspond to very basic (and very common) shapes. Later neurons record how these shapes can be combined into specific objects from specific directions, such as a tabby cat’s ear from the front, or a tabby cat’s ear from the side, and so on. (Cat pictures seem to be pretty popular these days.) Then a later neuron might combine the neurons corresponding to different parts of a tabby cat from different angles, to record a picture of a single tabby cat in one particular position (probably sleeping) from one particular angle. Then a later neuron might combine all the earlier neurons for different angles of a tabby to record the concept of a tabby cat. A later neuron might combine the neurons for all different types of cats and so on. (Of course, google’s neural network may combine specific concepts/pictures in a completely different way, but you get the idea.)

The more layers of neurons you have, the more complex the final “concepts” recorded by the network can be. However, one issue with early neural networks was that as you add layers, the back propogation method does not adjust the early layers as much. In other words, the regions defined by the first layer of neurons tend to stay put, while the later neurons attempt to make up for this by switching the shades of the poorly chosen regions back and forth.

The recent resurgence of interest in neural networks (or deep learning, a slightly broader area in which neural networks are a major part) has been partially fueled by more sophisticated training techniques that, when combined with back propagation, ensure that the early neurons are properly trained. (Another major factor in the resurgence of neural networks is the availability of computing power, which makes it possible to cycle through the training data more times with back propagation, which also greatly improves the final result.) However, a discussion of these methods will have to wait for a far future post. Instead, in the next few weeks I plan to discuss some other algorithms that combine simple models/distributions to make more complex ones.

The rough idea that I alluded to last time was that we will form a neural network by connecting the outputs of some neurons to the inputs of others. An example of this is shown in the Figure below. To keep things simple, we will have each neuron use a logistic model/distribution on a two-dimensional data space, and we’ll assume that the parameters for each distribution are chosen at random. Once we’ve chosen the models, we classify a new data point as follows: We first feed the coordinates of the new data point into each of the two neurons on the left. Each neuron uses its stored logistic distribution to assign a value between 0 and 1 to that data point. These two values are then fed to the neuron on the right, which interprets them as coordinates in some other two-dimensional space. This neuron outputs the value of its own stored distribution for that new point and this value is the output of the whole network.

We would like to understand what’s going on from the geometric perspective, but in order to make things easier to see (and to draw), we will temporarily replace the logistic distribution in each of the two neurons with a distribution that is equal to exactly 1 on one side of a line (the decision boundary) and exactly zero on the other side. (This is sometimes called a step function.) The first two Neurons take their input directly from the original input, so they both define distributions on the “same” two dimensional data space. On the left in the Figure below, I’ve drawn the two distributions superimposed on each other, one in green and one in blue. The region where they are both zero is colored black. The region where only one of them is 1 is colored green or blue, respectively, and the region where they’re both equal to 1 is colored aqua blue (which is what you get when you combine green and blue in the RGB color scheme.)

The neuron on the right also keeps track of a distribution on a two-dimensional space, but this space is different from the data space that the first two neurons are interested in. As described above, the coordinates in the data space record the outputs of the first two neurons, so if you feed a given data point into the neural network, the coordinates that the neuron on the right sees describe which of the colored regions the data point lives in. The way that the colored regions correspond to coordinates is shown on the right side of the Figure. So, for example, if a data point is anywhere in the green region then the third neuron will see it as being in the upper left corner.

This is somewhat reminiscent of the way we used kernels: In order to create more complicated decision boundaries from linear classifiers, we transformed the initial data into a new coordinate system. The difference here is that the transformation defined by a neural network is not necessarily into a higher dimensional vector space. In fact, it’s much more common to actually decrease the dimension of the data space with neural networks.

To see how this can give us a more complicated decision boundary, lets look at the possible decision boundaries for the third neuron and what they do to the distribution defined by the entire network. Some examples are shown below. In each case, the model used by the final neuron (shown on the right of each example) determines which of the four points will trigger an output of 0 or 1. From the above interpretation, we see that it’s really selecting which of the regions defined by the first two neurons get those labels (shown on the left of each example). The top right and bottom left examples are not particularly interesting: they’re just the linear models defined by the first two neurons. The interesting ones are the top left and bottom right, both of which are not linear.

So, somewhat like a kernel, the neural network allows us to define more complicated distributions than just ones with lines/planes/hyperplanes as their decision boundaries. However, while a kernel turns a single linear distribution into a more complicated shape, a neural network combines a number of simple models/distributions, in this case the linear models defined by the first two neurons.

Note that the pictures really only show approximations of the final distributions that the network can determine, since we have a logistic distribution from each neuron, rather than a step distribution. The actual distribution has a smooth transition, which is roughly the result of blurring one of the distributions shown here. If we have more coordinates in our initial input and/or more neurons in the first layer (i.e. the neurons that get input directly from the data rather than from other neurons) then this will correspond to having higher dimensional distributions, with planes or hyperplanes as the decision boundaries. These will cut the initial higher dimensional data space into a number of regions, and the final neuron will select which regions correspond to 1s and which correspond to 0s. For example, if we have three neurons in our initial layer then the final neuron will have three dimensions of input and will have a collection of regions to choose from like the ones shown in the Figure below. The corresponding points in the three-dimensional vector space that the final neuron sees are shown on the right.

However, as long as we only have one layer of neurons, the final neuron will still be very limited in how it combines the regions that they define. The real power of neural networks comes from adding more layers in order to get more complicated patterns. For example, in the network drawn below (in which everything is two-dimensional), each of the neurons in the second layer can pick one of the distributions that the final neuron in the original network was allowed to (the ones shown in the third Figure). Then the very last neuron combines these second layer distributions to determine the network’s final answer. For example, you should see if you can work out how to choose distributions on the final three neurons that will pick out the blue and green regions (but not the black and aqua regions). Note that, as in the network below, while each neuron has a single output, this output can feed into the inputs of more than one other neuron.

So from this discussion, we start to see how to create interesting distributions by having layers of neurons, with each successive layer feeding into later layers. However, we’re also allowed to have more complicated networks, where connections can skip between layers, or there may not even be a well defined sense of layers at all. A few people have even developed schemes for having loops of neurons which feed back into each other, though this gets complicated and usually isn’t necessary. In any type of network, the connections between neurons determine what kinds of final distributions the neural network is capable of creating. The more neurons we have, the more complicated the distribution is allowed to be, and (repeating a common theme on this blog) the greater the risk of over-fitting. Larger networks are also more computationally expensive, though this seem to be less of an issue with modern computers. Designing a neural network that is both complicated enough to correctly model the data, but simple enough to avoid over-fitting is a combination of art and science.

But, of course, the real work of the neural network, namely finding a distribution that fits a given data set, is not done by designing the connections between the nodes: It’s done in the training phase, where each neuron in the network “learns” its distribution. I described a rough framework for this in the last post, but a more detailed discussion will have to wait for next week.

First, we should note that in most classification algorithms, there are essentially two modes of operation: training and evaluation. In the training phase, we choose the parameters for the model/distribution, for example by finding the plane that best separates the two classes of data points in SVM or logistic regression. In the evaluation phase, we examine new (unlabeled) data points and predict which class they are in. In past posts, I didn’t define these two phases, but they were implicit in the conversation. When considering neural networks, however, it will help to be very explicit about the difference between training and evaluation. In particular, we will start by understanding how a neuron behaves in the evaluation phase, then use what we know about the evaluation phases when we examine the training phase.

A single neuron in a neural network can be thought of as a box with a number of inputs and one output, as in the Figure on the right. It reads in the numbers from the inputs on the left, then uses them to calculate a number for the output on the right. (In a neural network, the input values may come from other neurons and the output will be attached to the inputs of other neurons, but that’s for next time.) The output value will usually be between 0 and 1, though this is not entirely necessary. If we think of the input values as coordinates of a point, then we can think of the output value as the value of a probability distribution (or rather a probability density function) at that point.

In other words, the neuron will keep track of some model/probability distribution, such as the kind that we used for regression. After we set the input values to the coordinates at a certain point, the neuron looks up the value of the distribution at that point (i.e. how dark the distribution cloud is) and outputs that value. Note that this is not exactly how ANNs were originally defined and understood. However, going from the original definition to this viewpoint requires a lot of technical details that I don’t want to go into.

Like the distributions that we saw in regression and generalized regression, the model/distribution that the neuron keeps track of will be defined by some number of parameters.  In general, this distribution could be fairly complicated, but for the basic neural network, it’s a simple linear model defined by the distance to a line/plane/hyperplane. In fact, the traditional neuron model is the the logistic distribution used in logistic regression, where the points on one side of the line/plane/hyperplane take values close to one, and the points on the other side take values close to zero.

So we haven’t done anything new yet; we’ve just introduced new terminology for describing classification algorithms. What makes neural networks powerful is the way that they allow you to combine the models/distributions in the different neurons. But in order to combine the neurons, we need a general way to go about the training phase of the classifiers. With SVM and logistic regression, we trained the model on all the data points at once. In SVM, that meant looking at all the data points in order to find a decision boundary that is as far from the two classes as possible. For logistic regression, that meant choosing a distribution that minimized the difference between the class values of the points and the values in the distribution. Both of these training phases are specifically designed for the particular model/distribution. For neural networks, we will need a single training process that can work for any model.

There are a number of possible ways to train an artificial neural network, but I will describe one that is particularly simple and (from what I can tell) one of the earliest developed methods. For our training phase, we will only be able to ask the model two things: 1) What is the output for a given point? 2) How can we adjust the parameters of the model to most efficiently increase or decrease the output for that point?

The first question is just the evaluation phase. (That’s why we discussed the evaluation phase first.) The second question is a bit tricky, but we can see how it works with the logistic function. In the Figure below, we have three different logistic functions, evaluated at the same point. It may look like we’re moving the point right and left, but we’re not – it’s only moving relative the logistic curve. If we push the logistic curve to the right (as on the left side of the Figure), the point moves down. If we push the logistic curve to the left (as on the right side of the Figure), it moves up. This has to do with the fact that the slope of the logistic curve is positive, and can all be worked out with a bit of calculus.

For higher dimensional distributions such as the higher dimensional logistic distribution, we have to use a concept from multi-variable calculus called a gradient, rather than a slope, but the idea is the same: The gradient tells us what direction to adjust the parameters of the model in order to increase or decrease the output returned by the neuron at a given point.

To use this in the training phase of the neuron, we will assume that each data point in the training set is assigned a label of either 0 or 1 (green or blue.) We will have the neuron evaluate the first data point and compare its prediction (which will be a value between 0 and 1) to the actual label. If the prediction is correct, then we move on to the next point. But if it’s incorrect (which will always be the case if we use a logistic model, since it only takes values between 0 and 1, but not exactly 0 or 1), we will want the value to be either higher or lower, so we ask the neuron how to adjust the parameters to increase or decrease the value of the model at that point, respectively. We then make these adjustments to the parameters and move on to the next data point.

We can think about this in terms of having the data points push on the the decision boundary, similar to my description of logistic regression: With the logistic distribution, the decision boundary is the line/plane/hyperplane between the points where the distribution is greater than 1/2 and the points where it’s less than 1/2. If a point labeled 1 is on the side of the decision boundary that’s greater than 1/2 then it’s on the correct side, so it pushes the line/plane/hyperplane away to increase the margin for error. But if it’s on the wrong side then it pulls the decision boundary towards itself, in the hopes of ending up on the correct side. (However, to allow for noise in the data, we won’t necessarily move the decision boundary all the way to the correct side of the data point.)

Each time we evaluate a single data point and adjust the parameters, the distribution associated to the neuron should get a little better. Once we make it through the entire data set, we can then improve it further by repeating the process a few more times. After enough runs, we will usually get to the point where, since the model cannot fit all the data points with 100% accuracy, the data points will start to push the model back and forth, and things stop getting better. So a common practice is to slow down the rate at which the neuron adjusts its parameters each time we run through the entire data set, in the hope of settling into a good compromise.

Note that for a single neuron, this approach to training is not as effective as other methods such as logistic regression. With logistic regression, we calculate which direction to adjust the parameters to improve the overall scores of all the data points simultaneously. This makes it possible to guarantee that the distribution we find is a close to the best possible distribution. With the training process for Neural networks, we don’t have such a guarantee since we only look at a single data point at a time. However, this turns out to be a better process for neural networks with multiple neurons because among the distributions that can be defined by a network, there often will not be a single best distribution. But to see what I mean by this, you’ll have to wait for the next post.

The process for turning a binary classifier into a multi-class classifier is kind of like a game of twenty questions. However, rather than being allowed to ask any yes/no question, you can only ask questions of the form “Is this data point more likely to be in class A or in class B?” This is a problem because if the data point isn’t in either of class A or class B, then you will still get an answer – it just may be meaningless.

So for example, one scheme you might try is to run your binary classifier for every possible pair of classes and treat it as an election – whichever class gets the most votes wins. If you have three classes of data (red, blue and green) you would train one binary classifier for each pair of classes: 1) red vs. blue, 2) blue vs.green and 3) red vs. green. If you use a linear classifier like SVM or logistic regression, then this will determine three different lines/planes/hyperplanes (depending on the dimension of the data). We will call these lines/planes/hyperplanes the decision boundaries.

When new data point comes in, you check which side of each decision boundary it is on and see which class is most popular: If a new data point is on the green side of both the red vs. green and the blue vs. green hyperplanes then you classify it as green. In this case, the red vs. blue classifier is meaningless, but that’s OK because we ignore that one anyway. If we use a non-linear classifier or run our linear classifier through a kernel then the decision boundaries will be curved shapes rather than flat lines/planes/hyperplanes, but we can combine them the same way.

This scheme is called All vs. All (AVA). The problem is that there will usually be regions in the vector space of all data points in which the three different classifiers will produce a three-way tie. A good way to think about this is to visualize the two-dimensional case with three classes (such as our red, green and blue). An example is shown on the left in the Figure below. The grey region in the figure is the problematic area, where any data point would be on the red side of the red vs. blue line, on the blue side of the blue vs. green line and on the green side of the red vs. green line. This grey region won’t exist if the three lines meet at a single point, but that is unlikely to happen. But because the three instances of the binary classifier are independent, and all are affected by noise, there is bound to be some grey region.

One way to get rid of the grey region is to use a classifier that includes a measure of confidence. For example, logistic regression doesn’t just give us a decision boundary that separates the two classes – it gives us a probability density function, which was represented in my earlier post as a slow transition from green to blue. The shade of green or blue at any given point can be thought of as indicating how confident the algorithm is that a given point is in one class or the other. So, rather than just adding the number of votes for each class, we can add up the confidence values. Since these can be any values, rather then just ones and zeros, it will be much less likely to get a tie. The resulting algorithm will give us an answer at every point except for the points in the three curves where we switch from one color to another. In our red/green/blue example, this will look like the right side of the Figure above. (The pictures are hand drawn, so they are not 100% accurate, but they should give you the basic idea.)

Another popular scheme is to set up for each class a classifier that compares it to all the other classes at once. For our red, green and blue classes, we would train one classifier for each of: 1) red vs. (green or blue), 2) green vs. (red or blue) and 3) blue vs. (red or green). In other words, the first classifier would predict whether a given point is more likely to be in the red class, or in one of the blue or green classes, and similarly for the second and third classifier. We then choose a class for any new data point based on whichever class wins its own election. This scheme is call One vs. All (OVA).

With this scheme, there are two possible things that can go wrong: For a new data point, there may be two or more classes that win their own election (i.e. are determined to be more likely than the rest). Or, there may be no data points for which an individual class wins an election. You can get a rough idea of this from the left side of the Figure below. The grey regions on the outside are the areas where two different classes win their own elections. The grey triangle in the middle is where no class wins. This problem can again be minimized by using a classifier that includes a confidence value, as indicated on the right of the figure.

From the picture, it looks like there isn’t a big difference between the OVA and AVA results, particularly when a confidence value is included. All the methods certainly agree in the regions closest to the different classes of data, which is what we would expect, since there is an obvious answer in these areas. They mostly disagree in the regions between the data sets, where we wouldn’t expect as many new data points to appear. In particular, if the data is determined by well separated probability distributions then the different methods will usually give us the same answer, since most of the new data points will fall near the center of the appropriate class and away from the decision boundaries. However, if the models defined by the individual classifiers are inaccurate or if the different classes of data points are not well separated, AVA and OVA may give you very different results, and which one works better will depend on the situation.

A third scheme for combining binary classifiers uses something more like the usual strategy for a twenty questions game. The idea is to start with very general questions and then slowly narrow down the results. For example, if someone is thinking of a number between 1 and 100 and you want to figure out what it is with twenty yes/no questions, your first question souldn’t be “Is the number 1?”. Instead, you would ask whether or not the number was greater than 50. If the answer is no, then you would ask whether or not the number is greater than 25, and so on. In other words, you try to cut the possibilities in half with each question.

We can do the same thing with binary classifiers: If we have a large number of classes, we can divide them into two sets of classes, say A and B. Then we can divide the classes in A into two smaller sets of classes, divide B into two smaller sets of classes and so on. To run our multi-class classification, we would first train a binary classifier to determine whether a new data point is in some class in A, or in some class in B. (So, this step wouldn’t determine which class in A the data point is in, just whether or not it’s on one of them.) We then train a second binary classifier to determine which of the two subsets of A a point is in, and a third classifier to determine which of the subsets of B a point is in. We continue all the way down, until we get to classifiers that distinguish individual classes. This is called hierarchical classification because the different steps in the scheme form a sort of hierarchy from the first question (the CEO) to the second level questions (the vice-presidents) and down to the final questions (the mailroom clerks) that distinguish individual classes. The resulting structure, if you do this with a linear classifier, is indicated in the figure below. (Note that this is closely related to a method call decision trees, which I’ll discuss in a later post.)

In the Figure, set A consists of the three classes (purple, red and orange) in the upper right and set B consists of the three classes (blue, green and yellow) in the lower left. In the second and third steps, we separate the purple class off from set A, then separate the green class off from B. Then in the final two steps, we separate red from orange and yellow from blue.

This last scheme has the advantage that even without using a confidence indicator from the binary classifier, it always gives you a well defined answer for every new data point (as long as it isn’t right in one of the decision boundaries.) In other words, the hierarchical classification scheme does not produce any grey regions. The tricky thing is that how you choose to construct the hierarchy can have a big impact on how effective the final classifier is. In particular, you want to make sure that each of your initial sets A or B combines classes that are naturally close together in the space containing the data points. Otherwise, there may not be a hyperplane that separates A from B. Of course, we can always use a kernel to separate them, but as a rule of thumb it’s better to arrange things so that you can use the simplest possible kernel.

So, repeating a common theme on this blog, there is no silver bullet (or free lunch) when it comes to choosing a scheme for combining binary classifiers. The best way to make the right decision is to use a combination of experience with the type of data your working on and an understanding of the structure of the data, based on experimentation, visualization and other types of exploratory techniques. Otherwise, since you can’t actually see the data and the model in the same way that I’ve drawn the above examples, it can be very difficult to tell when a model or classification scheme is really effective or just deceptive garbage.

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.