Note
This personal note is written after studying the opening course on the coursera website, Machine Learning by Andrew NG . And images, audios of this note all comes from the opening course.
01_large-margin-classification
01_optimization-objective
By now, you’ve seen a range of difference learning algorithms. With supervised learning, the performance
of many supervised learning algorithms will be pretty similar, and what matters less often will be whether you use learning algorithm a or learning algorithm b, but what matters more will often be things like the amount of data you create these algorithms on, as well as your skill in applying these algorithms. Things like your choice of the features you design to give to the learning algorithms, and how you choose the colorization parameter, and things like that.
But, there’s one more algorithm that is very powerful and is very widely used both within industry and academia, and that’s called the Support Vector Machine. And compared to both logistic regression and neural networks, the Support Vector Machine, or SVM sometimes gives a cleaner, and sometimes more powerful way of learning complex non-linear functions. And so let’s take the next videos to talk about that. Later in this course, I will do a quick survey of a range of different supervisory algorithms just as a very briefly describe them. But the support vector machine, given its popularity and how powerful it is, this will be the last of the supervisory algorithms that I’ll spend a significant amount of time on in this course as with our development other learning algorithms, we’re gonna start by talking about the optimization objective. So, let’s get started on this algorithm.
In order to describe the support vector machine, I’m actually going to start with logistic regression, and show how we can modify it a bit, and get what is essentially the support vector machine. So in logistic regression, we have our familiar form of the hypothesis there and the sigmoid activation function shown on the right.
And in order to explain some of the math, I’m going to use z to denote theta transpose axiom. Now let’s think about what we would like logistic regression to do. If we have an example with y equals one and by this I mean an example in either the training set or the test set or the cross-validation set, but when y is equal to one then we’re sort of hoping that h of x will be close to one. Right, we’re hoping to correctly classify that example. And what having x subscript 1, what that means is that theta transpose x must be must larger than 0. So there’s greater than, greater than sign that means much, much greater than 0. And that’s because it is z, the theta of transpose x is when z is much bigger than 0 is far to the right of the sphere. That the outputs of logistic progression becomes close to one. Conversely, if we have an example where y is equal to zero, then what we’re hoping for is that the hypothesis will output a value close to zero. And that corresponds to theta transpose x of z being much less than zero because that corresponds to a hypothesis of putting a value close to zero.
If you look at the cost function of logistic regression, what you’ll find is that each example (x,y) contributes a term like this to the overall cost function, right? So for the overall cost function, we will also have a sum over all the chain examples and the 1 over m term, that this expression here, that’s the term that a single
training example contributes to the overall objective function so we can just rush them. Now if I take the definition for the fall of my hypothesis and plug it in over here, then what I get is that each training example contributes this term, ignoring the one over M but it contributes that term to my overall cost function for logistic regression. Now let’s consider two cases of when y is equal to one and when y is equal to zero. In the first case, let’s suppose that y is equal to 1. In that case, only this first term in the objective matters, because this one minus y term would be equal to zero if y is equal to one. So when y is equal to one, when in our example x comma y, when y is equal to 1 what we get is this term.. Minus log one over one, plus E to the negative Z where as similar to the last line I’m using Z to denote data transposed X and of course in a cost I should have this minus line that we just had if Y is equal to one so that’s equal to one I just simplify in a way in the expression that I have written down here. And if we plot this function as a function of z, what you find is that you get this curve shown on the lower left of the slide.
And thus, we also see that when z is equal to large, that is, when theta transpose x is large, that corresponds to a value of z that gives us a fairly small value, a very, very small contribution to the consumption. And this kinda explains why, when logistic regression sees a positive example, with y=1, it tries to set theta transport x to be very large because that corresponds to this term, in the cross function, being small.
Now, to fill the support vector machine, here’s what we’re going to do. We’re gonna take this cross function, this minus log 1 over 1 plus e to negative z, and modify it a little bit. Let me take this point 1 over here, and let me draw the cross functions you’re going to use. The new pass functions can be flat from here on out, and then we draw something that grows as a straight line, similar to logistic regression. But this is going to be a straight line at this portion. So the curve that I just drew in magenta, and the curve I just drew purple and magenta, so if it’s pretty close approximation to the cross function used by logistic regression. Except it is now made up of two line segments, there’s this flat portion on the right, and then there’s this straight line portion on the left. And don’t worry too much about the slope of the straight line portion. It doesn’t matter that much. But that’s the new cost function we’re going to use for when y is equal to one, and you can imagine it should do something pretty similar to logistic regression.
But turns out, that this will give the support vector machine computational advantages and give us, later on, an easier optimization problem that would be easier for software to solve. We just talked about the case of y equals one. The other case is if y is equal to zero. In that case, if you look at the cost, then only the second term will apply because the first term goes away, right? If y is equal to zero, then you have a zero here, so you’re left only with the second term of the expression above. And so the cost of an example, or the contribution of the cost function, is going to be given by this term over here. And if you plot that as a function of z, to have pure z on the horizontal axis, you end up with this one. And for the support vector machine, once again, we’re going to replace this blue line with something similar and at the same time we replace it with a new cost, this flat out here, this 0 out here. And that then grows as a straight line, like so.
So let me give these two functions names. This function on the left below I’m going to call cost subscript 1 of z $cost_1(z)$, and this function of the right I’m gonna call cost subscript 0 of z $cost_0(z)$. And the subscript just refers to the cost corresponding to when y is equal to 1, versus when y Is equal to zero.
Armed with these definitions, we’re now ready to build a support vector machine.
Here’s the cost function, j of theta, that we have for logistic regression. In case this equation looks a bit unfamiliar, it’s because previously we had a minus sign outside, but here what I did was I instead moved the minus signs inside these expressions, so it just makes it look a little different. For the support vector machine what we’re going to do is essentially take this and replace this with cost1 of z, that is cost1 of theta transpose x. And we’re going to take this and replace it with cost0 of z, that is cost0 of theta transpose x. Where the cost one function is what we had on the previous slide that looks like this. And the cost zero function, again what we had on the previous slide, and it looks like this.
So what we have for the support vector machine is a minimization problem of one over M, the sum of Y I times cost one, theta transpose X I, plus one minus Y I times cause zero of theta transpose X I, and then plus my usual regularization parameter. Like so.
Now, by convention, for the support of vector machine, we’re actually write things slightly different. We re-parameterize this just very slightly differently. First, we’re going to get rid of the 1 over m terms, and this just this happens to be a slightly different convention that people use for support vector machines compared to or just a progression. But here’s what I mean. You’re one way to do this, we’re just gonna get rid of these one over m terms and this should give you me the same optimal value of beta right? Because one over m is just as constant so whether I solved this minimization problem with one over n in front or not. I should end up with the same optimal value for theta.
Here’s what I mean, to give you an example, suppose I had a minimization problem $min_u(u-5)^2+1$. Well, the minimum of this happens to be $u=5$. Now if I were to take this objective function and multiply it by 10. So here my minimization problem is min over U, 10 U minus five squared plus 10 ( $min_u10[(u-5)^2+1]$ ). Well the value of U that minimizes this is still U equals five right? So multiply something that you’re minimizing over, by some constant, 10 in this case, it does not change the value of U that gives us, that minimizes this function. So the same way, what I’ve done is by crossing out the M is all I’m doing is multiplying my objective function by some constant M and it doesn’t change the value of theta. That achieves the minimum.
The second bit of notational change, which is just, again, the more standard convention when using SVMs instead of logistic regression, is the following. So for logistic regression, we add two terms to the objective function. The first is this term, which is the cost that comes from the training set and the second is this row, which is the regularization term. And what we had was we had a, we control the trade-off between these by saying, what we want is A plus, and then my regularization parameter lambda. And then times some other term B, where I guess I’m using your A to denote this first term, and I’m using B to denote the second term, maybe without the lambda. And instead of prioritizing this as A plus lambda B, and so what we did was by setting different values for this regularization parameter lambda, we could trade off the relative weight between how much we wanted the training set well, that is, minimizing A, versus how much we care about keeping the values of the parameter small, so that will be, the parameter is B for the support vector machine, just by convention, we’re going to use a different parameter. So instead of using lambda here to control the relative waiting between the first and second terms. We’re instead going to use a different parameter which by convention is called C and is set to minimize $C \times a + B$. So for logistic regression, if we set a very large value of lambda, that means you will give B a very high weight. Here is that if we set C to be a very small value, then that responds to giving B a much larger rate than C, than A. So this is just a different way of controlling the trade off, it’s just a different way of prioritizing how much we care about optimizing the first term, versus how much we care about optimizing the second term. And if you want you can think of this as the parameter C playing a role similar to 1 over lambda. And it’s not that it’s two equations or these two expressions will be equal. This equals 1 over lambda, that’s not the case. It’s rather that if C is equal to 1 over lambda, then these two optimization objectives should give you the same value, the same optimal value for theta. so we just filling that in I’m gonna cross out lambda here and write in the constant C there. So that gives us our overall optimization objective function for the support vector machine. And if you minimize that function, then what you have is the parameters learned by the SVM.
**Finally unlike logistic regression, the support vector machine doesn’t output the probability is that what we have is we have this cost function, that we minimize to get the parameter’s data, and what a support vector machine does is it just makes a prediction of y being equal to one or zero, directly. So the hypothesis will predict one if theta transpose x is greater or equal to zero, and it will predict zero otherwise and so having learned the parameters theta, this is the form of the hypothesis for the support vector machine. So that was a mathematical definition of what a support vector machine does. **
In the next few videos, let’s try to get back to intuition about what this optimization objective leads to and whether the source of the hypotheses SVM will learn and we’ll also talk about how to modify this just a little bit to the complex nonlinear functions.
summary
Optimization Objective
The Support Vector Machine (SVM) is yet another type of supervised machine learning algorithm. It is sometimes cleaner and more powerful.
Recall that in logistic regression, we use the following rules:
if y=1, then $h_\theta(x) \approx 1$ and $\Theta^Tx \gg 0$
if y=0, then $h_\theta(x) \approx 0$ and $\Theta^Tx \ll 0$
Recall the cost function for (unregularized) logistic regression:
$$\begin{align*}J(\theta) & = \frac{1}{m}\sum_{i=1}^m -y^{(i)} \log(h_\theta(x^{(i)})) - (1 - y^{(i)})\log(1 - h_\theta(x^{(i)}))\ & = \frac{1}{m}\sum_{i=1}^m -y^{(i)} \log\Big(\dfrac{1}{1 + e^{-\theta^Tx^{(i)}}}\Big) - (1 - y^{(i)})\log\Big(1 - \dfrac{1}{1 + e^{-\theta^Tx^{(i)}}}\Big)\end{align*}$$
To make a support vector machine, we will modify the first term of the cost function $-\log(h_{\theta}(x)) = -\log\Big(\dfrac{1}{1 + e^{-\theta^Tx}}\Big)$ so that when $θ^Tx$ (from now on, we shall refer to this as z) is greater than 1, it outputs 0. Furthermore, for values of z less than 1, we shall use a straight decreasing line instead of the sigmoid curve.(In the literature, this is called a hinge loss ( https://en.wikipedia.org/wiki/Hinge_loss) function.)
Similarly, we modify the second term of the cost function $$-\log(1 - h_{\theta(x)}) = -\log\Big(1 - \dfrac{1}{1 + e^{-\theta^Tx}}\Big)$$ so that when z is less than -1, it outputs 0. We also modify it so that for values of z greater than -1, we use a straight increasing line instead of the sigmoid curve.
We shall denote these as $\text{cost}1(z)$ and $\text{cost}0(z)$ (respectively, note that $\text{cost}_1(z)$ is the cost for classifying when y=1, and $\text{cost}_0(z)$ is the cost for classifying when y=0), and we may define them as follows (where k is an arbitrary constant defining the magnitude of the slope of the line):
$$z = \theta^Tx$$
$$\text{cost}_0(z) = \max(0, k(1+z))$$
$$\text{cost}_1(z) = \max(0, k(1-z))$$
Recall the full cost function from (regularized) logistic regression:
$$J(\theta) = \frac{1}{m} \sum{i=1}^m y^{(i)}(-\log(h_\theta(x^{(i)}))) + (1 - y^{(i)})(-\log(1 - h_\theta(x^{(i)}))) + \dfrac{\lambda}{2m}\sum{j=1}^n \Theta^2_j$$
Note that the negative sign has been distributed into the sum in the above equation.
We may transform this into the cost function for support vector machines by substituting $\text{cost}0(z)$ and $\text{cost}1(z)$:
$$J(\theta) = \frac{1}{m} \sum{i=1}^m y^{(i)} \ \text{cost}_1(\theta^Tx^{(i)}) + (1 - y^{(i)}) \ \text{cost}_0(\theta^Tx^{(i)}) + \dfrac{\lambda}{2m}\sum{j=1}^n \Theta^2_j$$
We can optimize this a bit by multiplying this by m (thus removing the m factor in the denominators). Note that this does not affect our optimization, since we’re simply multiplying our cost function by a positive constant (for example, minimizing $$(u-5)^2 + 1$$ gives us 5; multiplying it by 10 to make it $$10(u-5)^2 + 10$$ still gives us 5 when minimized).
$$J(\theta) = \sum_{i=1}^m y^{(i)} \ \text{cost}1(\theta^Tx^{(i)}) + (1 - y^{(i)}) \ \text{cost}0(\theta^Tx^{(i)}) + \dfrac{\lambda}{2}\sum{j=1}^n \Theta^2_j$$
Furthermore, convention dictates that we regularize using a factor C, instead of λ, like so:
$$J(\theta) = C\sum_{i=1}^m y^{(i)} \ \text{cost}_1(\theta^Tx^{(i)}) + (1 - y^{(i)}) \ \text{cost}_0(\theta^Tx^{(i)}) + \dfrac{1}{2}\sum{j=1}^n \Theta^2_j$$
This is equivalent to multiplying the equation by $C = \dfrac{1}{\lambda}$, and thus results in the same values when optimized. Now, when we wish to regularize more (that is, reduce overfitting), we decrease C, and when we wish to regularize less (that is, reduce underfitting), we increase C.
Finally, note that the hypothesis of the Support Vector Machine is not interpreted as the probability of y being 1 or 0 (as it is for the hypothesis of logistic regression). Instead, it outputs either 1 or 0. (In technical terms, it is a discriminant function.)
$$h_\theta(x) =\begin{cases} 1 & \text{if} \ \Theta^Tx \geq 0 \ 0 & \text{otherwise}\end{cases}$$
02_large-margin-intuition
Sometimes people talk about support vector machines, as large margin classifiers, in this video I’d like to tell you what that means, and this will also give us a useful picture of what an SVM hypothesis may look like.
Here’s my cost function for the support vector machine where here on the left I’ve plotted my cost 1 of z function that I used for positive examples and on the right I’ve plotted my zero of ‘Z’ function, where I have ‘Z’ here on the horizontal axis.
Now, let’s think about what it takes to make these cost functions small. If you have a positive example, so if y is equal to 1, then cost 1 of Z is zero only when Z is greater than or equal to 1. So in other words, if you have a positive example, we really want theta transpose x to be greater than or equal to 1 and conversely if y is equal to zero, look this cost zero of z function, then it’s only in this region where z is less than equal to 1 we have the cost is zero as z is equals to zero, and this is an interesting property of the support vector machine right, which is that, if you have a positive example so if y is equal to one, then all we really need is that theta transpose x is greater than equal to zero.And that would mean that we classify correctly because if theta transpose x is greater than zero our hypothesis will predict zero. And similarly, if you have a negative example, then really all you want is that theta transpose x is less than zero and that will make sure we got the example right. But the support vector machine wants a bit more than that. It says, you know, don’t just barely get the example right. So then don’t just have it just a little bit bigger than zero. What i really want is for this to be quite a lot bigger than zero say maybe bit greater or equal to one and I want this to be much less than zero. Maybe I want it less than or equal to -1. And so this builds in an extra safety factor or safety margin factor into the support vector machine.
Logistic regression does something similar too of course, but let’s see what happens or let’s see what the consequences of this are, in the context of the support vector machine. Concretely, what I’d like to do next is consider a case case where we set this constant C to be a very large value, so let’s imagine we set C to a very large value, may be a hundred thousand, some huge number. Let’s see what the support vector machine will do. If C is very, very large, then when minimizing this optimization objective, we’re going to be highly motivated to choose a value, so that this first term is equal to zero. So let’s try to understand the optimization problem in the context of, what would it take to make this first term in the objective equal to zero, because you know, maybe we’ll set C to some huge constant, and this will hope, this should give us additional intuition about what sort of hypotheses a support vector machine learns. So we saw already that whenever you have a training example with a label of y=1 if you want to make that first term zero, what you need is is to find a value of theta so that theta transpose $x^{(i)}$ is greater than or equal to 1. And similarly, whenever we have an example, with label zero, in order to make sure that the cost, cost zero of Z, in order to make sure that cost is zero we need that theta transpose $x^{(i)}$ is less than or equal to -1.
So, if we think of our optimization problem as now, really choosing parameters and show that this first term is equal to zero, what we’re left with is the following optimization problem. We’re going to minimize that first term zero, so C times zero, because we’re going to choose parameters so that’s equal to zero, plus one half and then you know that second term and this first term is ‘C’ times zero, so let’s just cross that out because I know that’s going to be zero. And this will be subject to the constraint that theta transpose $x^{(i)}$ is greater than or equal to one, if $y^{(i)}$ Is equal to one and theta transpose $x^{(i)}$ is less than or equal to minus one whenever you have a negative example and it turns out that when you solve this optimization problem, when you minimize this as a function of the parameters theta you get a very interesting decision boundary.
$$
\min_\limits{\theta}C\sum_\limits{i=1}^{m}\left[y^{(i)}{\cos}t_{1}\left(\theta^{T}x^{(i)}\right)+\left(1-y^{(i)}\right){\cos}t\left(\theta^{T}x^{(i)}\right)\right]+\frac{1}{2}\sum_\limits{i=1}^{n}\theta^{2}_{j}
$$
Concretely, if you look at a data set like this with positive and negative examples, this data is linearly separable and by that, I mean that there exists, you know, a straight line, although there is many a different straight lines, they can separate the positive and negative examples perfectly. For example, here is one green decision boundary that separates the positive and negative examples, but somehow that doesn’t look like a very natural one, right?
Or by drawing an even worse one, you know here’s another magenta decision boundary that separates the positive and negative examples but just barely. But neither of those seem like particularly good choices. The Support Vector Machines will instead choose this decision boundary, which I’m drawing in black. And that seems like a much better decision boundary than either of the ones that I drew in magenta or in green. The black line seems like a more robust separator, it does a better job of separating the positive and negative examples. And mathematically, what that does is, this black decision boundary has a larger distance. That distance is called the margin, when I draw up this two extra blue lines, we see that the black decision boundary has some larger minimum distance from any of my training examples, whereas the magenta and the green lines they come awfully close to the training examples. and then that seems to do a less a good job separating the positive and negative classes than my black line. And so this distance is called the margin of the support vector machine and this gives the SVM a certain robustness, because it tries to separate the data with as a large margin as possible. So the support vector machine is sometimes also called a large margin classifier and this is actually a consequence of the optimization problem we wrote down on the previous slide.
I know that you might be wondering how is it that the optimization problem I wrote down in the previous slide, how does that lead to this large margin classifier. I know I haven’t explained that yet. And in the next video I’m going to sketch a little bit of the intuition about why that optimization problem gives us this large margin classifier. But this is a useful feature to keep in mind if you are trying to understand what are the sorts of hypothesis that an SVM will choose. That is, trying to separate the positive and negative examples with as big a margin as possible.
$$
\min_\limits{\theta}C\sum_\limits{i=1}^{m}\left[y^{(i)}{\cos}t_{1}\left(\theta^{T}x^{(i)}\right)+\left(1-y^{(i)}\right){\cos}t\left(\theta^{T}x^{(i)}\right)\right]+\frac{1}{2}\sum_\limits{i=1}^{n}\theta^{2}_{j} \
\min_\limits{\theta} \frac{1}{2}\sum\limits_{j=1}^{n} s.t. \cases{\theta^Tx \ge 1 & if y=1, then left term is 0 \\theta^Tx \le 0 & if y=-1, then left term is 0}
$$
outliers
I want to say one last thing about large margin classifiers in this intuition, so we wrote out this large margin classification setting in the case of when C, that regularization concept, was very large, I think I set that to a hundred thousand or something. So given a dataset like this, maybe we’ll choose that decision boundary that separate the positive and negative examples on large margin. (personal note : In order to minimize the cost function as possible as the classifier, SVM , can, it need to choose a proper $\theta$ to make the left term equal to 0 when C is a pretty large constant)
Now, the SVM is actually slightly more sophisticated than this large margin view might suggest. And in particular, if all you’re doing is use a large margin classifier then your learning algorithms can be sensitive to outliers, so lets just add an extra positive example like that shown on the screen. If he had one example then it seems as if to separate data with a large margin, maybe I’ll end up learning a decision boundary like that, right? that is the magenta line and it’s really not clear that based on the single outlier based on a single example and it’s really not clear that it’s actually a good idea to change my decision boundary from the black one over to the magenta one. So, if C, if the regularization parameter C were very large, then this is actually what SVM will do, it will change the decision boundary from the black to the magenta one but if C were reasonably small if you were to use the C, not too large then you still end up with this black decision boundary.
And of course if the data were not linearly separable so if you had some positive examples in here, or if you had some negative examples in here then the SVM will also do the right thing. And so this picture of a large margin classifier that’s really, that’s really the picture that gives better intuition only for the case of when the regulations parameter C is very large, and just to remind you this corresponds C plays a role similar to one over Lambda, where Lambda is the regularization parameter we had previously. And so it’s only of one over Lambda is very large or equivalently if Lambda is very small that you end up with things like this Magenta decision boundary, but in practice when applying support vector machines, when C is not very very large like that, it can do a better job ignoring the few outliers like here. And also do fine and do reasonable things even if your data is not linearly separable. But when we talk about bias and variance in the context of support vector machines which will do a little bit later, hopefully all of of this trade-offs involving the regularization parameter will become clearer at that time. So I hope that gives some intuition about how this support vector machine functions as a large margin classifier that tries to separate the data with a large margin, technically this picture of this view is true only when the parameter C is very large, which is a useful way to think about support vector machines. There was one missing step in this video which is, why is it that the optimization problem we wrote down on these slides, how does that actually lead to the large margin classifier, I didn’t do that in this video, in the next video I will sketch a little bit more of the math behind that to explain that separate reasoning of how the optimization problem we wrote out results in a large margin classifier.
summary
A useful way to think about Support Vector Machines is to think of them as Large Margin Classifiers .
If y=1, we want $\Theta^Tx \geq 1$ (not just ≥0)
If y=0, we want $\Theta^Tx \leq -1$ (not just <0)
Now when we set our constant C to a very large value (e.g. 100,000), our optimizing function will constrain Θ such that the equation A (the summation of the cost of each example) equals 0. We impose the following constraints on Θ:
$$\Theta^Tx \geq 1 \text{ if y=1 and } \Theta^Tx \leq -1 \text{ if y=0 .}$$
If C is very large, we must choose Θ parameters such that:
$$\sum_{i=1}^m y^{(i)}\text{cost}_1(\Theta^Tx) + (1 - y^{(i)})\text{cost}0(\Theta^Tx) = 0$$
This reduces our cost function to:
$$ \begin{align*} J(\theta) = C \cdot 0 + \dfrac{1}{2}\sum{j=1}^n \Theta^2_j \newline = \dfrac{1}{2}\sum_{j=1}^n \Theta^2_j \end{align*}$$
Recall the decision boundary from logistic regression (the line separating the positive and negative examples). In SVMs, the decision boundary has the special property that it is as far away as possible from both the positive and the negative examples.
The distance of the decision boundary to the nearest example is called the margin . Since SVMs maximize this margin, it is often called a Large Margin Classifier.
The SVM will separate the negative and positive examples by a large margin .
This large margin is only achieved when C is very large .
Data is linearly separable when a straight line can separate the positive and negative examples.
If we have outlier examples that we don’t want to affect the decision boundary, then we can reduce C.
Increasing and decreasing C is similar to respectively decreasing and increasing $λ$, and can simplify our decision boundary.
03_mathematics-behind-large-margin-classification
In this video, I’d like to tell you a bit about the math behind large margin classification. This video is optional, so please feel free to skip it. It may also give you better intuition about how the optimization problem of the support vex machine, how that leads to large margin classifiers. In order to get started, let me first remind you of a couple of properties of what vector inner products look like.
Let’s say I have two vectors U and V, that look like this. So both two dimensional vectors. Then let’s see what U transpose V looks like. And U transpose V is also called the inner products between the vectors U and V. Use a two dimensional vector, so I can on plot it on this figure. So let’s say that’s the vector U. And what I mean by that is if on the horizontal axis that value takes whatever value U1 is and on the vertical axis the height of that is whatever U2 is the second component of the vector U. Now, one quantity that will be nice to have is the norm of the vector U. So, these are, you know, double bars on the left and right that denotes the norm or length of U. So this just means; really the euclidean length of the vector U. And this is Pythagoras theorem is just equal to U1 squared plus U2 squared square root, right? And this is the length of the vector U. That’s a real number. Just say you know, what is the length of this, what is the length of this vector down here. What is the length of this arrow that I just drew, is the normal view? Now let’s go back and look at the vector V because we want to compute the inner product. So V will be some other vector with, you know, some value V1, V2. And so, the vector V will look like that, towards V like so. Now let’s go back and look at how to compute the inner product between U and V. Here’s how you can do it. Let me take the vector V and project it down onto the vector U. So I’m going to take a orthogonal projection or a 90 degree projection, and project it down onto U like so. And what I’m going to do measure length of this red line that I just drew here. So, I’m going to call the length of that red line P. So, P is the length or is the magnitude of the projection of the vector V onto the vector U. Let me just write that down. So, P is the length of the projection of the vector V onto the vector U. And it is possible to show that unit product U transpose V, that this is going to be equal to P times the norm or the length of the vector U. So, this is one way to compute the inner product. And if you actually do the geometry figure out what P is and figure out what the norm of U is. This should give you the same way, the same answer as the other way of computing unit product. Right. Which is if you take U transpose V then U transposes this U1 U2, its a one by two matrix, 1 times V. And so this should actually give you U1, V1 plus U2, V2. And so the theorem of linear algebra that these two formulas give you the same answer. And by the way, U transpose V is also equal to V transpose U. So if you were to do the same process in reverse, instead of projecting V onto U, you could project U onto V. Then, you know, do the same process, but with the rows of U and V reversed. And you would actually, you should actually get the same number whatever that number is. And just to clarify what’s going on in this equation the norm of U is a real number and P is also a real number. And so U transpose V is the regular multiplication as two real numbers of the length of P times the normal view.
Just one last detail, which is if you look at the norm of P, P is actually signed so to the right. And it can either be positive or negative. So let me say what I mean by that, if U is a vector that looks like this and V is a vector that looks like this. So if the angle between U and V is greater than ninety degrees. Then if I project V onto U, what I get is a projection it looks like this and so that length P. And in this case, I will still have that U transpose V is equal to P times the norm of U. Except in this example P will be negative. So, you know, in inner products if the angle between U and V is less than ninety degrees, then P is the positive length for that red line whereas if the angle of this angle of here is greater than 90 degrees then P here will be negative of the length of the super line of that little line segment right over there. So the inner product between two vectors can also be negative if the angle between them is greater than 90 degrees. So that’s how vector inner products work. We’re going to use these properties of vector inner product to try to understand the support vector machine optimization objective over there.
Here is the optimization objective for the support vector machine that we worked out earlier. Just for the purpose of this slide I am going to make one simplification or once just to make the objective easy to analyze and what I’m going to do is ignore the indeceptrums.
So, we’ll just ignore theta 0 and set that to be equal to 0. To make things easier to plot, I’m also going to set N the number of features to be equal to 2. So, we have only 2 features, X1 and X2. Now, let’s look at the objective function. The optimization objective of the SVM. What we have only two features. When N is equal to 2. This can be written, one half of theta one squared plus theta two squared. Because we only have two parameters, theta one and theta two. What I’m going to do is rewrite this a bit. I’m going to write this as one half of theta one squared plus theta two squared and the square root squared. And the reason I can do that, is because for any number, you know, W, right, the square roots of W and then squared, that’s just equal to W. So square roots and squared should give you the same thing. What you may notice is that this term inside is that’s equal to the norm or the length of the vector theta and what I mean by that is that if we write out the vector theta like this, as you know theta one, theta two. Then this term that I’ve just underlined in red, that’s exactly the length, or the norm, of the vector theta. We are calling the definition of the norm of the vector that we have on the previous line. And in fact this is actually equal to the length of the vector theta, whether you write it as theta zero, theta 1, theta 2. That is, if theta zero is equal to zero, as I assume here. Or just the length of theta 1, theta 2; but for this line I am going to ignore theta 0. So let me just, you know, treat theta as this, let me just write theta, the normal theta as this theta 1, theta 2 only, but the math works out either way, whether we include theta zero here or not. So it’s not going to matter for the rest of our derivation. And so finally this means that my optimization objective is equal to one half of the norm of theta squared. Support vector machine is doing in the optimization objective is it’s minimizing the squared norm of the square length of the parameter vector theta.
Now what I’d like to do is look at these terms, theta transpose X and understand better what they’re doing. So given the parameter vector theta and given and example x, what is this is equal to? And on the previous slide, we figured out what U transpose V looks like, with different vectors U and V. And so we’re going to take those definitions, you know, with theta and X(i) playing the roles of U and V. And let’s see what that picture looks like. So, let’s say I plot.
Let’s say I look at just a single training example. Let’s say I have a positive example the drawing was across there and let’s say that is my example X(i), what that really means is plotted on the horizontal axis some value X(i) 1 and on the vertical axis X(i) 2. That’s how I plot my training examples. And although we haven’t been really thinking of this as a vector, what this really is, this is a vector from the origin from 0, 0 out to the location of this training example. And now let’s say we have a parameter vector and I’m going to plot that as vector, as well. What I mean by that is if I plot theta 1 here and theta 2 there so what is the inner product theta transpose X(i). While using our earlier method, the way we compute that is we take my example and project it onto my parameter vector theta. And then I’m going to look at the length of this segment that I’m coloring in, in red. And I’m going to call that P superscript I to denote that this is a projection of the i-th training example onto the parameter vector theta. And so what we have is that theta transpose X(i) is equal to following what we have on the previous slide, this is going to be equal to P times the length of the norm of the vector theta. And this is of course also equal to theta 1 x1 plus theta 2 x2. So each of these is, you know, an equally valid way of computing the inner product between theta and X(i). Okay. So where does this leave us? **What this means is that, this constrains that theta transpose X(i) be greater than or equal to one or less than minus one. What this means is that it can replace the use of constraints that P(i) times X be greater than or equal to one. Because theta transpose X(i) is equal to P(i) times the norm of theta. **
So writing that into our optimization objective. This is what we get where I have, instead of theta transpose X(i), I now have this P(i) times the norm of theta. And just to remind you we worked out earlier too that this optimization objective can be written as one half times the norm of theta squared. So, now let’s consider the training example that we have at the bottom and for now, continuing to use the simplification that theta 0 is equal to 0. Let’s see what decision boundary the support vector machine will choose. Here’s one option, let’s say the support vector machine were to choose this decision boundary. This is not a very good choice because it has very small margins. This decision boundary comes very close to the training examples. Let’s see why the support vector machine will not do this. For this choice of parameters it’s possible to show that the parameter vector theta is actually at 90 degrees to the decision boundary. And so, that green decision boundary corresponds to a parameter vector theta that points in that direction. And by the way, the simplification that theta 0 equals 0 that just means that the decision boundary must pass through the origin, (0,0) over there.
So now, let’s look at what this implies for the optimization objective. Let’s say that this example here. Let’s say that’s my first example, you know, X1. If we look at the projection of this example onto my parameters theta. That’s the projection. And so that little red line segment. That is equal to P1. And that is going to be pretty small, right. And similarly, if this example here, if this happens to be X2, that’s my second example. Then, if I look at the projection of this this example onto theta. You know. Then, let me draw this one in magenta. This little magenta line segment, that’s going to be P2. That’s the projection of the second example onto my, onto the direction of my parameter vector theta which goes like this. And so, this little projection line segment is getting pretty small. P2 will actually be a negative number, right so P2 is in the opposite direction. This vector has greater than 90 degree angle with my parameter vector theta, it’s going to be less than 0. And so what we’re finding is that these terms P(i) are going to be pretty small numbers. So if we look at the optimization objective and see, well, for positive examples we need P(i) times the norm of theta to be bigger than either one. But if P(i) over here, if P1 over here is pretty small, that means that we need the norm of theta to be pretty large, right? If P1 of theta is small and we want P1 you know times in all of theta to be bigger than either one, well the only way for that to be true for the profit that these two numbers to be large if P1 is small, as we said we want the norm of theta to be large. And similarly for our negative example, we need P2 times the norm of theta to be less than or equal to minus one. And we saw in this example already that P2 is going pretty small negative number, and so the only way for that to happen as well is for the norm of theta to be large, but what we are doing in the optimization objective is we are trying to find a setting of parameters where the norm of theta is small, and so you know, so this doesn’t seem like such a good direction for the parameter vector and theta.
In contrast, just look at a different decision boundary. Here, let’s say, this SVM chooses that decision boundary. Now the is going to be very different. If that is the decision boundary, here is the corresponding direction for theta. So, with the direction boundary you know, that vertical line that corresponds to it is possible to show using linear algebra that the way to get that green decision boundary is have the vector of theta be at 90 degrees to it, and now if you look at the projection of your data onto the vector x, lets say its before this example is my example of x1. So when I project this on to x, or onto theta, what I find is that this is P1. That length there is P1. The other example, that example is and I do the same projection and what I find is that this length here is a P2 really that is going to be less than 0. And you notice that now P1 and P2, these lengths of the projections are going to be much bigger, and so if we still need to enforce these constraints that P1 of the norm of theta is phase number one because P1 is so much bigger now. The normal can be smaller. And so, what this means is that by choosing the decision boundary shown on the right instead of on the left, the SVM can make the norm of the parameters theta much smaller. So, if we can make the norm of theta smaller and therefore make the squared norm of theta smaller, which is why the SVM would choose this hypothesis on the right instead. And this is how the SVM gives rise to this large margin certification effect.
Mainly, if you look at this green line, if you look at this green hypothesis we want the projections of my positive and negative examples onto theta to be large, and the only way for that to hold true this is if surrounding the green line. There’s this large margin, there’s this large gap that separates positive and negative examples is really the magnitude of this gap. The magnitude of this margin is exactly the values of P1, P2, P3 and so on. And so by making the margin large, by these tyros P1, P2, P3 and so on.
that’s the SVM can end up with a smaller value for the norm of theta which is what it is trying to do in the objective. And this is why this machine ends up with enlarge margin classifiers because it’s trying to maximize the norm of these P1 which is the distance from the training examples to the decision boundary.
Finally, we did this whole derivation using this simplification that the parameter theta 0 must be equal to 0. The effect of that as I mentioned briefly, is that if theta 0 is equal to 0 what that means is that we are entertaining decision boundaries that pass through the origins of decision boundaries pass through the origin like that, if you allow theta zero to be non 0 then what that means is that you entertain the decision boundaries that did not cross through the origin, like that one I just drew. And I’m not going to do the full derivation that. It turns out that this same large margin proof works in pretty much in exactly the same way. And there’s a generalization of this argument that we just went through them long ago through that shows that even when theta 0 is non 0, what the SVM is trying to do when you have this optimization objective. Which again corresponds to the case of when C is very large. But it is possible to show that, you know, when theta is not equal to 0 this support vector machine is still finding is really trying to find the large margin separator that between the positive and negative examples. So that explains how this support vector machine is a large margin classifier. In the next video we will start to talk about how to take some of these SVM ideas and start to apply them to build a complex nonlinear classifiers.
summary
Vector Inner Product
Say we have two vectors, u and v:
$$\begin{align*} u = \begin{bmatrix} u_1 \newline u_2 \end{bmatrix} & v = \begin{bmatrix} v_1 \newline v_2 \end{bmatrix} \end{align*}$$
The length of vector v is denoted $||v||$, and it describes the line on a graph from origin (0,0) to $(v_1,v_2)$.
The length of vector v can be calculated with $\sqrt{v_1^2 + v_2^2}$ by the Pythagorean theorem.
The projection of vector v onto vector u is found by taking a right angle from u to the end of v, creating a right triangle.
p= length of projection of v onto the vector u.
$$u^Tv= p \cdot ||u||$$
Note that $u^Tv = ||u|| \cdot ||v|| \cos \theta$ where θ is the angle between u and v. Also, $p = ||v|| \cos \theta$. If you substitute p for $||v|| \cos \theta$, you get $u^Tv= p \cdot ||u||$.
So the product $u^Tv$ is equal to the length of the projection times the length of vector u.
In our example, since u and v are vectors of the same length, $u^Tv = v^Tu$.
$$u^Tv = v^Tu = p \cdot ||u|| = u_1v_1 + u_2v_2$$
If the angle between the lines for v and u is greater than 90 degrees , then the projection p will be negative .
$$\begin{align*}&\min_\Theta \dfrac{1}{2}\sum_{j=1}^n \Theta_j^2 \newline&= \dfrac{1}{2}(\Theta_1^2 + \Theta_2^2 + \dots + \Theta_n^2) \newline&= \dfrac{1}{2}(\sqrt{\Theta_1^2 + \Theta_2^2 + \dots + \Theta_n^2})^2 \newline&= \dfrac{1}{2}||\Theta ||^2 \newline\end{align*}$$
We can use the same rules to rewrite $\Theta^Tx^{(i)}$:
$$\Theta^Tx^{(i)} = p^{(i)} \cdot ||\Theta || = \Theta_1x_1^{(i)} + \Theta_2x_2^{(i)} + \dots + \Theta_n x_n^{(i)}$$
So we now have a new optimization objective by substituting $p^{(i)} \cdot ||\Theta ||$ in for $\Theta^Tx^{(i)}$:
If y=1, we want $p^{(i)} \cdot ||\Theta || \geq 1$
If y=0, we want $p^{(i)} \cdot ||\Theta || \leq -1$
The reason this causes a “large margin” is because: the vector for Θ is perpendicular to the decision boundary. In order for our optimization objective (above) to hold true, we need the absolute value of our projections $p^{(i)}$ to be as large as possible.
If $\Theta_0 =0$, then all our decision boundaries will intersect (0,0). If $\Theta_0 \neq 0$, the support vector machine will still find a large margin for the decision boundary.
02_kernels
01_kernels-i
In this video, I’d like to start adapting support vector machines in order to develop complex nonlinear classifiers. The main technique for doing that is something called kernels. Let’s see what this kernels are and how to use them.
If you have a training set that looks like this, and you want to find a nonlinear decision boundary to distinguish the positive and negative examples, maybe a decision boundary that looks like that. One way to do so is to come up with a set of complex polynomial features, right? So, set of features that looks like this, so that you end up with a hypothesis X that predicts 1 if you know that theta 0 and plus theta 1 X1 plus dot dot dot all those polynomial features is greater than 0, and predict 0, otherwise.
$$
h(\theta)=\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_1x_2+\theta_4x_1^2+\theta_5x_2^2+\cdots
$$
And another way of writing this, to introduce a level of new notation that I’ll use later, is that we can think of a hypothesis as computing a decision boundary using this. So, theta 0 plus theta 1 f1 plus theta 2, f2 plus theta 3, f3 plus and so on.
$$
h(\theta)=\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3+\theta_4f_4+\cdots
$$
Where I’m going to use this new denotation f1, f2, f3 and so on to denote these new sort of features that I’m computing, so f1 is just X1, f2 is equal to X2, f3 is equal to this one here.
$$
f_1=x_1,f_2=x_2,f_3=x_1x_2,f_4=x_1^2,f_5=x_2^2,\cdots
$$
we seen previously that coming up with these high order polynomials is one way to come up with lots more features, the question is, is there a different choice of features or is there better sort of features than this high order polynomials because you know it’s not clear that this high order polynomial is what we want, and what we talked about computer vision talk about when the input is an image with lots of pixels. We also saw how using high order polynomials becomes very computationally expensive because there are a lot of these higher order polynomial terms. So, is there a different or a better choice of the features that we can use to plug into this sort of hypothesis form.
So, here is one idea for how to define new features f1, f2, f3. On this line I am going to define only three new features, but for real problems we can get to define a much larger number. But here’s what I’m going to do in this phase of features X1, X2, and I’m going to leave X0 out of this, the interceptor X0, but in this phase X1 X2, I’m going to just, you know, manually pick a few points, and then call these points l1, we are going to pick a different point, let’s call that l2 and let’s pick the third one and call this one l3, and for now let’s just say that I’m going to choose these three points manually. I’m going to call these three points landmarks, so line landmark one, two, three.
What I’m going to do is define my new features as follows, given an example X, let me define my first feature f1 to be some measure of the similarity between my training example X and my first landmark and this specific formula that I’m going to use to measure similarity is going to be this $f_i = similarity(x^{(1)}, l^{(1)}) = e^{(-\frac{||x^{(1)}-l^{(1)}||^2}{2δ^2})}$. So, depending on whether or not you watched the previous optional video, this notation, you know, this is the length of the vector W (=$x^{(1)}-l^{(1)}$). And so, this thing here, this $||x-l^{(1)}||^2$, this is actually just the euclidean distance squared, is the euclidean distance between the point x and the landmark l1. We will see more about this later. But that’s my first feature, and my second feature f2 is going to be, you know, similarity function that measures how similar X is to l2 and the game is going to be defined as the following function. This is E to the minus of the square of the euclidean distance between X and the second landmark, that is what the enumerator is and then divided by 2 sigma squared and similarly f3 is, you know, similarity between X and l3, which is equal to, again, similar formula. And what this similarity function is, the mathematical term for this, is that this is going to be a kernel function. And the specific kernel I’m using here, this is actually called a Gaussian kernel. And so this formula, this particular choice of similarity function is called a Gaussian kernel.
But the way the terminology goes is that, you know, in the abstract these different similarity functions are called kernels and we can have different similarity functions and the specific example I’m giving here is called the Gaussian kernel. We’ll see other examples of other kernels. But for now just think of these as similarity functions. And so, instead of writing similarity between X and l, sometimes we also write this a kernel denoted you know, lower case k between x and one of my landmarks all right. So let’s see what this kernel actually do and why these sorts of similarity functions, why these expressions might make sense.
So let’s take my first landmark. My landmark l1, which is one of those points I chose on my figure just now. So the similarity of the kernel between x and l1 is given by this expression. Just to make sure, you know, we are on the same page about what the numerator term is, the numerator can also be written as a sum from j equals 1 through N on sort of the distance. So this is the component wise distance between the vector X and the vector l. And again for the purpose of these slides I’m ignoring X0. So just ignoring the intercept term X0, which is always equal to 1. So, you know, this is how you compute the kernel with similarity between X and a landmark. So let’s see what this function does. Suppose X is close to one of the landmarks. Then this euclidean distance formula and the numerator will be close to 0, right. So, that is this term here, the distance was great, the distance using X and 0 will be close to zero, and so f1, this is a simple feature, will be approximately E to the minus 0 and then the numerator squared over 2 is equal to squared so that E to the 0, E to minus 0, E to 0 is going to be close to one. And I’ll put the approximation symbol here because the distance may not be exactly 0, but if X is closer to landmark this term will be close to 0 and so f1 would be close 1. Conversely, if X is far from 01 then this first feature f1 will be E to the minus of some large number squared, divided divided by two sigma squared and E to the minus of a large number is going to be close to 0. So what these features do is they measure how similar X is from one of your landmarks and the feature f is going to be close to one when X is close to your landmark and is going to be 0 or close to zero when X is far from your landmark.
Each of these landmarks. On the previous line, I drew three landmarks, l1, l2, l3. Each of these landmarks, defines a new feature f1, f2 and f3. That is, given the the training example X, we can now compute three new features: f1, f2, and f3, given, you know, the three landmarks that I wrote just now.
But first, let’s look at this exponentiation function, let’s look at this similarity function and plot in some figures and just, you know, understand better what this really looks like. For this example, let’s say I have two features X1 and X2. And let’s say my first landmark, l1 is at a location, $\begin{bmatrix}3\5\end{bmatrix}$. So and let’s say I set sigma squared equals one for now. If I plot what this feature looks like, what I get is this figure. So the vertical axis, the height of the surface is the value of f1 and down here on the horizontal axis are, if I have some training example, and there is x1 and there is x2. Given a certain training example, the training example here which shows the value of x1 and x2 at a height above the surface, shows the corresponding value of f1 and down below this is the same figure I had showed, using a quantifiable plot, with x1 on horizontal axis, x2 on horizontal axis and so, this figure on the bottom is just a contour plot of the 3D surface. You notice that when X is equal to 3 5 exactly, then we the f1 takes on the value 1, because that’s at the maximum and X moves away as X goes further away then this feature takes on values that are close to 0. And so, this is really a feature, f1 measures, you know, how close X is to the first landmark and if varies between 0 and one depending on how close X is to the first landmark l1. Now the other was due on this slide is show the effects of varying this parameter sigma squared. So, sigma squared is the parameter of the Gaussian kernel and as you vary it, you get slightly different effects. Let’s set sigma squared to be equal to 0.5 and see what we get. We set sigma square to 0.5, what you find is that the kernel looks similar, except for the width of the bump becomes narrower. The contours shrink a bit too. So if sigma squared equals to 0.5 then as you start from X equals $\begin{bmatrix}3\5\end{bmatrix}$ and as you move away, then the feature f1 falls to zero much more rapidly and conversely, if you has increase since where three in that case and as I move away from, you know l. So this point here is really l, right, that’s l1 is at location $\begin{bmatrix}3\5\end{bmatrix}$, right. So it’s shown up here. And if sigma squared is large, then as you move away from l1, the value of the feature falls away much more slowly.
So, given this definition of the features, let’s see what source of hypothesis we can learn. Given the training example X, we are going to compute these features f1, f2, f3 and a hypothesis is going to predict one when theta 0 plus theta 1 f1 plus theta 2 f2, and so on is greater than or equal to 0. For this particular example, let’s say that I’ve already found a learning algorithm and let’s say that, you know, somehow I ended up with these values of the parameter. So if theta 0 equals minus 0.5, theta 1 equals 1, theta 2 equals 1, and theta 3 equals 0 And what I want to do is consider what happens if we have a training example that takes has location at this magenta dot, right where I just drew this dot over here. So let’s say I have a training example X, what would my hypothesis predict? Well, If I look at this formula. Because my training example X is close to l1, we have that f1 is going to be close to 1 the because my training example X is far from l2 and l3 I have that, you know, f2 would be close to 0 and f3 will be close to 0. So, if I look at that formula, I have theta 0 plus theta 1 times 1 plus theta 2 times some value. Not exactly 0, but let’s say close to 0. Then plus theta 3 times something close to 0. And this is going to be equal to plugging in these values now. So, that gives minus 0.5 plus 1 times 1 which is 1, and so on. Which is equal to 0.5 which is greater than or equal to 0. So, at this point, we’re going to predict Y equals 1, because that’s greater than or equal to zero.
$$
h_θ(x) = θ_0+θ_1f_1+θ_2f_2+θ_3f_3=-0.5+11+10+00=0.5≥0
$$
Now let’s take a different point. Now lets’ say I take a different point, I’m going to draw this one in a different color, **in cyan*** say, for a point out there, if that were my training example X, then if you make a similar computation, you find that f1, f2, f3 are all going to be close to 0. And so, we have theta 0 plus theta1, f1, plus so on and this will be about equal to minus 0.5, because theta 0 is minus 0.5 and f1, f2, f3 are all zero. So this will be minus 0.5, this is less than zero. And so, at this point out there, we’re going to predict Y equals zero.
$$
h_θ(x) = θ_0+θ_1f_1+θ_2f_2+θ_3f_3=-0.5+10+10+0*0=-0.5<0
$$
And if you do this yourself for a range of different points, be sure to convince yourself that if you have a training example that’s close to L2, say, then at this point we’ll also predict Y equals one. And in fact, what you end up doing is, you know, if you look around this boundary, this space, what we’ll find is that for points near l1 and l2 we end up predicting positive. And for points far away from l1 and l2, that’s for points far away from these two landmarks, we end up predicting that the class is equal to 0. As so, what we end up doing,is that the decision boundary of this hypothesis would end up looking something like this where inside this red decision boundary would predict Y equals 1 and outside we predict Y equals 0. And so this is how with this definition of the landmarks and of the kernel function. We can learn pretty complex non-linear decision boundary, like what I just drew where we predict positive when we’re close to either one of the two landmarks. And we predict negative when we’re very far away from any of the landmarks. And so this is part of the idea of kernels of and how we use them with the support vector machine, **which is that we define these extra features using landmarks and similarity functions to learn more complex nonlinear classifiers. So hopefully that gives you a sense of the idea of kernels and how we could use it to define new features for the Support Vector Machine. **
But there are a couple of questions that we haven’t answered yet. One is, how do we get these landmarks? How do we choose these landmarks? And another is, what other similarity functions, if any, can we use other than the one we talked about, which is called the Gaussian kernel. In the next video we give answers to these questions and put everything together to show how support vector machines with kernels can be a powerful way to learn complex nonlinear functions.
summary
Kernels allow us to make complex, non-linear classifiers using Support Vector Machines.
Given x, compute new feature depending on proximity to landmarks $l^{(1)},\ l^{(2)},\ l^{(3)}$.
To do this, we find the “similarity” of x and some landmark $l^{(i)}$:
$$f_i = similarity(x, l^{(i)}) = \exp(-\dfrac{||x - l^{(i)}||^2}{2\sigma^2})$$
This “similarity” function is called a Gaussian Kernel . It is a specific example of a kernel.
The similarity function can also be written as follows:
$$f_i = similarity(x, l^{(i)}) = \exp(-\dfrac{\sum^n_{j=1}(x_j-l_j^{(i)})^2}{2\sigma^2})$$
There are a couple properties of the similarity function:
If $x \approx l^{(i)}$, then $f_i = \exp(-\dfrac{\approx 0^2}{2\sigma^2}) \approx 1$
If x is far from $l^{(i)}$, then $f_i = \exp(-\dfrac{(large\ number)^2}{2\sigma^2}) \approx 0$
In other words, if x and the landmark are close, then the similarity will be close to 1, and if x and the landmark are far away from each other, the similarity will be close to 0.
Each landmark gives us the features in our hypothesis:
$$\begin{align*}l^{(1)} \rightarrow f_1 \newline l^{(2)} \rightarrow f_2 \newline l^{(3)} \rightarrow f_3 \newline\dots \newline h_\Theta(x) = \Theta_1f_1 + \Theta_2f_2 + \Theta_3f_3 + \dots\end{align*}$$
$\sigma^2$ is a parameter of the Gaussian Kernel, and it can be modified to increase or decrease the drop-off of our feature $f_i$. Combined with looking at the values inside Θ, we can choose these landmarks to get the general shape of the decision boundary.
02_kernels-ii
In the last video, we started to talk about the kernels idea and how it can be used to define new features for the support vector machine. In this video, I’d like to throw in some of the missing details and, also, say a few words about how to use these ideas in practice. Such as, how they pertain to, for example, the bias variance trade-off in support vector machines.
In the last video, I talked about the process of picking a few landmarks. You know, l1, l2, l3 and that allowed us to define the similarity function also called the kernel or in this example if you have this similarity function this is a Gaussian kernel. And that allowed us to build this form of a hypothesis function.
where do we get these landmarks from
Where do we get l1, l2, l3 from? And it seems, also, that for complex learning problems, maybe we want a lot more landmarks than just three of them that we might choose by hand. So in practice this is how the landmarks are chosen which is that given the machine learning problem. We have some data set of some some positive and negative examples. So, this is the idea here which is that we’re gonna take the examples and for every training example that we have, we are just going to call it. We’re just going to put landmarks as exactly the same locations as the training examples. So if I have one training example if that is x1, well then I’m going to choose this is my first landmark to be at exactly the same location as my first training example. And if I have a different training example x2. Well we’re going to set the second landmark to be the location of my second training example.
On the figure on the right, I used red and blue dots just as illustration, the color of this figure, the color of the dots on the figure on the right is not significant. But what I’m going to end up with using this method is I’m going to end up with m landmarks of l1, l2 down to l(m) if I have m training examples with one landmark per location of my per location of each of my training examples. And this is nice because it is saying that my features are basically going to measure how close an example is to one of the things I saw in my training set. So, just to write this outline a little more concretely, given m training examples, I’m going to choose the the location of my landmarks to be exactly near the locations of my m training examples.
When you are given example x, and in this example x can be something in the training set, it can be something in the cross validation set, or it can be something in the test set. Given an example x we are going to compute, you know, these features as so f1, f2, and so on. Where l1 is actually equal to x1 and so on. And these then give me a feature vector. So let me write f as the feature vector. I’m going to take these f1, f2 and so on, and just group them into feature vector. Take those down to fm. And, you know, just by convention. If we want, we can add an extra feature f0, which is always equal to 1. So this plays a role similar to what we had previously. For x0, which was our interceptor. So, for example, if we have a training example x(i), y(i), the features we would compute for this training example will be as follows: given x(i), we will then map it to, you know, f1(i). Which is the similarity. I’m going to abbreviate as SIM instead of writing out the whole word similarity, right? And f2(i) equals the similarity between x(i) and l2, and so on, down to fm(i) equals the similarity between x(i) and l(m). And somewhere in the middle. Somewhere in this list, you know, at the i-th component, I will actually have one feature component which is f subscript i(i), which is going to be the similarity between x and l(i). Where l(i) is equal to x(i), and so you know f(i) is just going to be the similarity between x and itself. And if you’re using the Gaussian kernel this is actually e to the minus 0 over 2 sigma squared and so, this will be equal to 1 and that’s okay. So one of my features for this training example is going to be equal to 1. And then similar to what I have above. I can take all of these m features and group them into a feature vector. So instead of representing my example, using, you know, x(i) which is this what R(n) plus one dimensional vector. Depending on whether you can set terms, is either R(n) or R(n) plus 1. We can now instead represent my training example using this feature vector f. I am going to write this f superscript i. Which is going to be taking all of these things and stacking them into a vector. So, $f_1^{(i)}$ down to $f_m^{(i)}$ and if you want and well, usually we’ll also add this $f_0^{(i)}$ , where $f_0^{(i)}$ is equal to 1.
And so this vector here gives me my new feature vector with which to represent my training example. So given these kernels and similarity functions, here’s how we use a simple vector machine. If you already have a learning set of parameters theta, then if you given a value of x and you want to make a prediction. What we do is we compute the features f, which is now an $R^{m}$ plus 1 dimensional feature vector. And we have m here because we have m training examples and thus m landmarks and what we do is we predict 1 if theta transpose f is greater than or equal to 0. Right.
So, if theta transpose f, of course, that’s just equal to theta 0, f0 plus theta 1, f1 plus dot dot dot, plus theta m f(m). And so my parameter vector theta is also now going to be an m plus 1 dimensional vector. And we have m here because where the number of landmarks is equal to the training set size. So m was the training set size and now, the parameter vector theta is going to be m plus one dimensional. So that’s how you make a prediction if you already have a setting for the parameter’s theta.
How do you get the parameter’s theta? Well you do that using the SVM learning algorithm, and specifically what you do is you would solve this minimization problem. You’ve minimized the parameter’s theta of C times this cost function which we had before. Only now, instead of looking there instead of making predictions using theta transpose x(i) using our original features, x(i). Instead we’ve taken the features x(i) and replace them with a new features so we are using theta transpose f(i) to make a prediction on the i’th training examples and we see that, you know, in both places here and it’s by solving this minimization problem that you get the parameters for your Support Vector Machine.
$$
minJ(θ)=min C[\sum_{i=1}^{m} y^{(i)}Cost_1(θ^Tf^{(i)}) + (1-y^{(i)})Cost_0(θ^Tf^{(i)}) ] + \frac{1}{2}\sum_{j=1}^{n}θ_j^2
$$
And one last detail is because this optimization problem we really have n equals m features. That is here. The number of features we have. Really, the effective number of features we have is dimension of f. So that n is actually going to be equal to m. So, if you want to, you can think of this as a sum, this really is a sum from j equals 1 through m. And then one way to think about this, is you can think of it as n being equal to m, because if f isn’t a new feature, then we have m plus 1 features, with the plus 1 coming from the interceptor. And here, we still do sum from j equal 1 through n, because similar to our earlier videos on regularization, we still do not regularize the parameter theta zero, which is why this is a sum for j equals 1 through m instead of j equals zero though m. So that’s the support vector machine learning algorithm. That’s one sort of, mathematical detail aside that I should mention, which is that in the way the support vector machine is implemented, this last term is actually done a little bit differently. So you don’t really need to know about this last detail in order to use support vector machines, and in fact the equations that are written down here should give you all the intuitions that should need. But in the way the support vector machine is implemented, you know, that term, the sum of j of theta j squared right? Another way to write this is this can be written as theta transpose theta if we ignore the parameter theta 0. So theta 1 down to theta m. Ignoring theta 0. Then this sum of j of theta j squared that this can also be written theta transpose theta.
SVM thetas
And what most support vector machine implementations do is actually replace this theta transpose theta, will instead, theta transpose times some matrix inside, that depends on the kernel you use, times theta. And so this gives us a slightly different distance metric. We’ll use a slightly different measure instead of minimizing exactly the norm of theta squared means that minimize something slightly similar to it. That’s like a rescale version of the parameter vector theta that depends on the kernel. But this is kind of a mathematical detail. That allows the support vector machine software to run much more efficiently. And the reason the support vector machine does this is with this modification. It allows it to scale to much bigger training sets.
Because for example, if you have a training set with 10,000 training examples. Then, you know, the way we define landmarks, we end up with 10,000 landmarks. And so theta becomes 10,000 dimensional. And maybe that works, but when m becomes really, really big then solving for all of these parameters, you know, if m were 50,000 or a 100,000 then solving for all of these parameters can become expensive for the support vector machine optimization software, thus solving the minimization problem that I drew here. So kind of as mathematical detail, which again you really don’t need to know about. It actually modifies that last term a little bit to optimize something slightly different than just minimizing the norm squared of theta squared, of theta. But if you want, you can feel free to think of this as an kind of an implementational detail that does change the objective a bit, but is done primarily for reasons of computational efficiency, so usually you don’t really have to worry about this.
**And by the way, in case your wondering why we don’t apply the kernel’s idea to other algorithms as well like logistic regression, it turns out that if you want, you can actually apply the kernel’s idea and define the source of features using landmarks and so on for logistic regression. But the computational tricks that apply for support vector machines don’t generalize well to other algorithms like logistic regression. And so, using kernels with logistic regression is going too very slow, whereas, because of computational tricks, like that embodied and how it modifies this and the details of how the support vector machine software is implemented, support vector machines and kernels tend go particularly well together. Whereas, logistic regression and kernels, you know, you can do it, but this would run very slowly. And it won’t be able to take advantage of advanced optimization techniques that people have figured out for the particular case of running a support vector machine with a kernel.But all this pertains only to how you actually implement software to minimize the cost function. **
I will say more about that in the next video, but you really don’t need to know about how to write software to minimize this cost function because you can find very good off the shelf software for doing so. And just as, you know, I wouldn’t recommend writing code to invert a matrix or to compute a square root, I actually do not recommend writing software to minimize this cost function yourself, but instead to use off the shelf software packages that people have developed and so those software packages already embody these numerical optimization tricks, so you don’t really have to worry about them.
SVM regularization parameters
But one other thing that is worth knowing about is when you’re applying a support vector machine, how do you choose the parameters of the support vector machine?
And the last thing I want to do in this video is say a little word about the bias and variance trade offs when using a support vector machine. When using an SVM, one of the things you need to choose is the parameter C which was in the optimization objective, and you recall that C played a role similar to 1 over lambda, where lambda was the regularization parameter we had for logistic regression. So, if you have a large value of C, this corresponds to what we have back in logistic regression, of a small value of lambda meaning of not using much regularization. And if you do that, you tend to have a hypothesis with lower bias and higher variance. Whereas if you use a smaller value of C then this corresponds to when we are using logistic regression with a large value of lambda and that corresponds to a hypothesis with higher bias and lower variance. And so, hypothesis with large C has a higher variance, and is more prone to overfitting, whereas hypothesis with small C has higher bias and is thus more prone to underfitting. So this parameter C is one of the parameters we need to choose. The other one is the parameter sigma squared, which appeared in the Gaussian kernel. So if the Gaussian kernel sigma squared is large, then in the similarity function, which was this you know E to the minus x minus landmark varies squared over 2 sigma squared. In this one of the example; If I have only one feature, x1, if I have a landmark there at that location, if sigma squared is large, then, you know, the Gaussian kernel would tend to fall off relatively slowly and so this would be my feature f(i), and so this would be smoother function that varies more smoothly, and so this will give you a hypothesis with higher bias and lower variance, because the Gaussian kernel that falls off smoothly, you tend to get a hypothesis that varies slowly, or varies smoothly as you change the input x. Whereas in contrast, if sigma squared was small and if that’s my landmark given my 1 feature x1, you know, my Gaussian kernel, my similarity function, will vary more abruptly. And in both cases I’d pick out 1, and so if sigma squared is small, then my features vary less smoothly. So if it’s just higher slopes or higher derivatives here. And using this, you end up fitting hypotheses of lower bias and you can have higher variance. And if you look at this week’s points exercise, you actually get to play around with some of these ideas yourself and see these effects yourself. So, that was the support vector machine with kernels algorithm. And hopefully this discussion of bias and variance will give you some sense of how you can expect this algorithm to behave as well.
summary
One way to get the landmarks is to put them in the exact same locations as all the training examples. This gives us m landmarks, with one landmark per training example.
Given example x:
$f_1 = similarity(x,l^{(1)}), f_2 = similarity(x,l^{(2)}), f_3 = similarity(x,l^{(3)})$, and so on.
This gives us a “feature vector,” $f_{(i)}$ of all our features for example $x_{(i)}$. We may also set $f_0 = 1$ to correspond with $Θ0$. Thus given training example $x{(i)}$:
$$x^{(i)} \rightarrow \begin{bmatrix}f_1^{(i)} = similarity(x^{(i)}, l^{(1)}) \ f_2^{(i)} = similarity(x^{(i)}, l^{(2)}) \ \vdots \ f_m^{(i)} = similarity(x^{(i)}, l^{(m)}) \ \end{bmatrix}$$
Now to get the parameters Θ we can use the SVM minimization algorithm but with $f^{(i)}$ substituted in for $x^{(i)}$:
$$\min_{\Theta} C \sum_{i=1}^m y^{(i)}\text{cost}_1(\Theta^Tf^{(i)}) + (1 - y^{(i)})\text{cost}0(\theta^Tf^{(i)}) + \dfrac{1}{2}\sum{j=1}^n \Theta^2_j$$
Using kernels to generate f(i) is not exclusive to SVMs and may also be applied to logistic regression. However, because of computational optimizations on SVMs, kernels combined with SVMs is much faster than with other algorithms, so kernels are almost always found combined only with SVMs.
Choosing SVM Parameters
Choosing C (recall that $C = \dfrac{1}{\lambda}$
If C is large, then we get higher variance/lower bias
If C is small, then we get lower variance/higher bias
The other parameter we must choose is $σ^2$ from the Gaussian Kernel function:
With a large $σ^2$, the features fi vary more smoothly, causing higher bias and lower variance.
With a small $σ^2$, the features fi vary less smoothly, causing lower bias and higher variance.
Using An SVM
There are lots of good SVM libraries already written. A. Ng often uses ‘liblinear’ and ‘libsvm’. In practical application, you should use one of these libraries rather than rewrite the functions.
In practical application, the choices you do need to make are:
Choice of parameter C
Choice of kernel (similarity function)
No kernel (“linear” kernel) – gives standard linear classifier
Choose when n is large and when m is small
Gaussian Kernel (above) – need to choose $σ^2$
Choose when n is small and m is large
The library may ask you to provide the kernel function.
Note: do perform feature scaling before using the Gaussian Kernel.
Note: not all similarity functions are valid kernels. They must satisfy “Mercer’s Theorem” which guarantees that the SVM package’s optimizations run correctly and do not diverge.
You want to train C and the parameters for the kernel function using the training and cross-validation datasets.
Multi-class Classification
Many SVM libraries have multi-class classification built-in.
You can use the one-vs-all method just like we did for logistic regression, where $$y \in {1,2,3,\dots,K}$$ with $$\Theta^{(1)}, \Theta^{(2)}, \dots,\Theta{(K)}$$. We pick class i with the largest $$(\Theta^{(i)})^Tx$$.
Logistic Regression vs. SVMs
If n is large (relative to m), then use logistic regression, or SVM without a kernel (the “linear kernel”)
If n is small and m is intermediate, then use SVM with a Gaussian Kernel
If n is small and m is large, then manually create/add more features, then use logistic regression or SVM without a kernel.
In the first case, we don’t have enough examples to need a complicated polynomial hypothesis. In the second example, we have enough examples that we may need a complex non-linear hypothesis. In the last case, we want to increase our features so that logistic regression becomes applicable.
Note : a neural network is likely to work well for any of these situations, but may be slower to train.
Additional references
“An Idiot’s Guide to Support Vector Machines”: http://web.mit.edu/6.034/wwwbob/svm-notes-long-08.pdf
03_svms-in-practice
So far we’ve been talking about SVMs in a fairly abstract level. In this video I’d like to talk about what you actually need to do in order to run or to use an SVM.
The support vector machine algorithm poses a particular optimization problem. But as I briefly mentioned in an earlier video, I really do not recommend writing your own software to solve for the parameter’s theta yourself. So just as today, very few of us, or maybe almost essentially none of us would think of writing code ourselves to invert a matrix or take a square root of a number, and so on. We just, you know, call some library function to do that. In the same way, the software for solving the SVM optimization problem is very complex, and there have been researchers that have been doing essentially numerical optimization research for many years. So you come up with good software libraries and good software packages to do this. And then strongly recommend just using one of the highly optimized software libraries rather than trying to implement something yourself. And there are lots of good software libraries out there. The two that I happen to use the most often are the linear SVM but there are really lots of good software libraries for doing this that you know, you can link to many of the major programming languages that you may be using to code up learning algorithm.
Even though you shouldn’t be writing your own SVM optimization software, there are a few things you need to do, though.
linear kernel
First is to come up with with some choice of the parameter’s C. We talked a little bit of the bias/variance properties of this in the earlier video. Second, you also need to choose the kernel or the similarity function that you want to use. So one choice might be if we decide not to use any kernel. And the idea of no kernel is also called a linear kernel. So if someone says, I use an SVM with a linear kernel, what that means is you know, they use an SVM without using without using a kernel and it was a version of the SVM that just uses theta transpose X, right, that predicts 1 theta 0 plus theta 1 X1 plus so on plus theta N, X N is greater than equals 0. This term linear kernel, you can think of this as you know this is the version of the SVM that just gives you a standard linear classifier. So that would be one reasonable choice for some problems, and you know, there would be many software libraries, like linear, was one example, out of many, one example of a software library that can train an SVM without using a kernel, also called a linear kernel. So, why would you want to do this? If you have a large number of features, if N is large, and M the number of training examples is small, then you know you have a huge number of features that if X, this is an X is an Rn, Rn +1. So if you have a huge number of features already, with a small training set, you know, maybe you want to just fit a linear decision boundary and not try to fit a very complicated nonlinear function, because might not have enough data. And you might risk overfitting, if you’re trying to fit a very complicated function in a very high dimensional feature space, but if your training set sample is small. So this would be one reasonable setting where you might decide to just not use a kernel, or equivalents to use what’s called a linear kernel.
Gaussian kernel
A second choice for the kernel that you might make, is this Gaussian kernel, and this is what we had previously. And if you do this, then the other choice you need to make is to choose this parameter sigma squared when we also talk a little bit about the bias variance tradeoffs of how, if sigma squared is large, then you tend to have a higher bias, lower variance classifier, but if sigma squared is small, then you have a higher variance, lower bias classifier. So when would you choose a Gaussian kernel? Well, if your omission of features X, I mean Rn, and if N is small, and, ideally, you know, if n is large, right, so that’s if, you know, we have say, a two-dimensional training set, like the example I drew earlier. So n is equal to 2, but we have a pretty large training set. So, you know, I’ve drawn in a fairly large number of training examples, then maybe you want to use a kernel to fit a more complex nonlinear decision boundary, and the Gaussian kernel would be a fine way to do this.
I’ll say more towards the end of the video, a little bit more about when you might choose a linear kernel, a Gaussian kernel and so on. But if concretely, if you decide to use a Gaussian kernel, then here’s what you need to do. Depending on what support vector machine software package you use, it may ask you to implement a kernel function, or to implement the similarity function.
So if you’re using an octave or MATLAB implementation of an SVM, it may ask you to provide a function to compute a particular feature of the kernel. So this is really computing f subscript i for one particular value of i, where f here is just a single real number, so maybe I should move this better written f(i), but what you need to do is to write a kernel function that takes this input, you know, a training example or a test example whatever it takes in some vector X and takes as input one of the landmarks and but only I’ve come down X1 and X2 here, because the landmarks are really training examples as well.
But what you need to do is write software that takes this input, you know, X1, X2 and computes this sort of similarity function between them and return a real number. And so what some support vector machine packages do is expect you to provide this kernel function that take this input you know, X1, X2 and returns a real number. And then it will take it from there and it will automatically generate all the features, and so automatically take X and map it to f1, f2, down to f(m) using this function that you write, and generate all the features and train the support vector machine from there. But sometimes you do need to provide this function yourself. Other if you are using the Gaussian kernel, some SVM implementations will also include the Gaussian kernel and a few other kernels as well, since the Gaussian kernel is probably the most common kernel. Gaussian and linear kernels are really the two most popular kernels by far. Just one implementational note. If you have features of very different scales, it is important to perform feature scaling before using the Gaussian kernel. And here’s why. If you imagine the computing the norm between X and l, right, so this term here, and the numerator term over there. What this is doing, the norm between X and l, that’s really saying, you know, let’s compute the vector V, which is equal to X minus l. And then let’s compute the norm does vector V, which is the difference between X. So the norm of V is really equal to V1 squared plus V2 squared plus dot dot dot, plus Vn squared. Because here X is in Rn, or Rn plus 1, but I’m going to ignore, you know, X0. So, let’s pretend X is an Rn, square on the left side is what makes this correct. So this is equal to that, right? And so written differently, this is going to be X1 minus l1 squared, plus x2 minus l2 squared, plus dot dot dot plus Xn minus ln squared. And now if your features take on very different ranges of value. So take a housing prediction, for example, if your data is some data about houses. And if X is in the range of thousands of square feet, for the first feature, X1. But if your second feature, X2 is the number of bedrooms. So if this is in the range of one to five bedrooms, then X1 minus l1 is going to be huge. This could be like a thousand squared, whereas X2 minus l2 is going to be much smaller and if that’s the case, then in this term, those distances will be almost essentially dominated by the sizes of the houses and the number of bathrooms would be largely ignored. As so as, to avoid this in order to make a machine work well, do perform future scaling. And that will sure that the SVM gives, you know, comparable amount of attention to all of your different features, and not just to in this example to size of houses were big movement here the features.
When you try a support vector machines chances are by far the two most common kernels you use will be the linear kernel, meaning no kernel, or the Gaussian kernel that we talked about. And just one note of warning which is that not all similarity functions you might come up with are valid kernels. And the Gaussian kernel and the linear kernel and other kernels that you sometimes others will use, all of them need to satisfy a technical condition. It’s called Mercer’s Theorem and the reason you need to this is because support vector machine algorithms or implementations of the SVM have lots of clever numerical optimization tricks.
In order to solve for the parameter’s theta efficiently and in the original design envisaged, those are decision made to restrict our attention only to kernels that satisfy this technical condition called Mercer’s Theorem. And what that does is, that makes sure that all of these SVM packages, all of these SVM software packages can use the large class of optimizations and get the parameter theta very quickly. So, what most people end up doing is using either the linear or Gaussian kernel, but there are a few other kernels that also satisfy Mercer’s theorem and that you may run across other people using, although I personally end up using other kernels you know, very, very rarely, if at all.
Other choices of kernel
Just to mention some of the other kernels that you may run across. One is the polynomial kernel. And for that the similarity between X and l is defined as, there are a lot of options, you can take X transpose l squared. So, here’s one measure of how similar X and l are. If X and l are very close with each other, then the inner product will tend to be large. And so, you know, this is a slightly unusual kernel. That is not used that often, but you may run across some people using it. This is one version of a polynomial kernel. Another is X transpose l cubed. These are all examples of the polynomial kernel. X transpose l plus 1 cubed. X transpose l plus maybe a number different then one 5 and, you know, to the power of 4 and so the polynomial kernel actually has two parameters. One is, what number do you add over here? It could be 0. This is really plus 0 over there, as well as what’s the degree of the polynomial over there. So the degree power and these numbers. And the more general form of the polynomial kernel is X transpose l, plus some constant and then to some degree in the X1 and so both of these are parameters for the polynomial kernel. So the polynomial kernel almost always or usually performs worse. And the Gaussian kernel does not use that much, but this is just something that you may run across. Usually it is used only for data where X and l are all strictly non negative, and so that ensures that these inner products are never negative. And this captures the intuition that X and l are very similar to each other, then maybe the inter product between them will be large. They have some other properties as well but people tend not to use it much.
And then, depending on what you’re doing, there are other, sort of more esoteric kernels as well, that you may come across. You know, there’s a string kernel, this is sometimes used if your input data is text strings or other types of strings. There are things like the chi-square kernel, the histogram intersection kernel, and so on. There are sort of more esoteric kernels that you can use to measure similarity between different objects. So for example, if you’re trying to do some sort of text classification problem, where the input x is a string then maybe we want to find the similarity between two strings using the string kernel, but I personally you know end up very rarely, if at all, using these more esoteric kernels.
I think I might have use the chi-square kernel, may be once in my life and the histogram kernel, may be once or twice in my life. I’ve actually never used the string kernel myself. But in case you’ve run across this in other applications. You know, if you do a quick web search we do a quick Google search or quick Bing search you should have found definitions that these are the kernels as well.
Two last details
Multi-class classification
So just two last details I want to talk about in this video. One in multiclass classification. So, you have four classes or more generally 3 classes output some appropriate decision boundary between your multiple classes. Most SVM, many SVM packages already have built-in multiclass classification functionality. So if your using a pattern like that, you just use the both that functionality and that should work fine. Otherwise, one way to do this is to use the one versus all method that we talked about when we are developing logistic regression. So what you do is you trade kSVM’s if you have k classes, one to distinguish each of the classes from the rest. And this would give you k parameter vectors, so this will give you, upi lmpw. theta 1, which is trying to distinguish class y equals one from all of the other classes, then you get the second parameter, vector theta 2, which is what you get when you, you know, have y equals 2 as the positive class and all the others as negative class and so on up to a parameter vector theta k, which is the parameter vector for distinguishing the final class key from anything else, and then lastly, this is exactly the same as the one versus all method we have for logistic regression. Where we you just predict the class i with the largest theta transpose X. So let’s multiclass classification designate. For the more common cases that there is a good chance that whatever software package you use, you know, there will be a reasonable chance that are already have built in multiclass classification functionality, and so you don’t need to worry about this result. Finally, we developed support vector machines starting off with logistic regression and then modifying the cost function a little bit. ****
logistic regression vs. SVMs
The last thing we want to do in this video is, just say a little bit about. when you will use one of these two algorithms, so let’s say n is the number of features and m is the number of training examples. So, when should we use one algorithm versus the other? Well, if n is larger relative to your training set size, so for example, if you take a business with a number of features this is much larger than m and this might be, for example, if you have a text classification problem, where you know, the dimension of the feature vector is I don’t know, maybe, 10 thousand. And if your training set size is maybe 10 you know, maybe, up to 1000. So, imagine a spam classification problem, where email spam, where you have 10,000 features corresponding to 10,000 words but you have, you know, maybe 10 training examples or maybe up to 1,000 examples. So if n is large relative to m, then what I would usually do is use logistic regression or use it as the m without a kernel or use it with a linear kernel. Because, if you have so many features with smaller training sets, you know, a linear function will probably do fine, and you don’t have really enough data to fit a very complicated nonlinear function. Now if is n is small and m is intermediate what I mean by this is n is maybe anywhere from 1 - 1000, 1 would be very small. But maybe up to 1000 features and if the number of training examples is maybe anywhere from 10, you know, 10 to maybe up to 10,000 examples. Maybe up to 50,000 examples. If m is pretty big like maybe 10,000 but not a million. Right? So if m is an intermediate size then often an SVM with a linear kernel will work well. We talked about this early as well, with the one concrete example, this would be if you have a two dimensional training set. So, if n is equal to 2 where you have, you know, drawing in a pretty large number of training examples. So Gaussian kernel will do a pretty good job separating positive and negative classes. One third setting that’s of interest is if n is small but m is large. So if n is you know, again maybe 1 to 1000, could be larger. But if m was, maybe 50,000 and greater to millions. So, 50,000, a 100,000, million, trillion. You have very very large training set sizes, right. So if this is the case, then a SVM of the Gaussian Kernel will be somewhat slow to run. Today’s SVM packages, if you’re using a Gaussian Kernel, tend to struggle a bit. If you have, you know, maybe 50 thousands okay, but if you have a million training examples, maybe or even a 100,000 with a massive value of m. Today’s SVM packages are very good, but they can still struggle a little bit when you have a massive, massive trainings that size when using a Gaussian Kernel. So in that case, what I would usually do is try to just manually create have more features and then use logistic regression or an SVM without the Kernel. And in case you look at this slide and you see logistic regression or SVM without a kernel. In both of these places, I kind of paired them together. There’s a reason for that, is that logistic regression and SVM without the kernel, those are really pretty similar algorithms and, you know, either logistic regression or SVM without a kernel will usually do pretty similar things and give pretty similar performance, but depending on your implementational details, one may be more efficient than the other. But, where one of these algorithms applies, logistic regression where SVM without a kernel, the other one is to likely to work pretty well as well. But along with the power of the SVM is when you use different kernels to learn complex nonlinear functions. And this regime, you know, when you have maybe up to 10,000 examples, maybe up to 50,000. And your number of features, this is reasonably large. That’s a very common regime and maybe that’s a regime where a support vector machine with a kernel kernel will shine. You can do things that are much harder to do that will need logistic regression.
And finally, where do neural networks fit in? Well for all of these problems, for all of these different regimes, a well designed neural network is likely to work well as well. The one disadvantage, or the one reason that might not sometimes use the neural network is that, for some of these problems, the neural network might be slow to train. But if you have a very good SVM implementation package, that could run faster, quite a bit faster than your neural network. And, although we didn’t show this earlier, it turns out that the optimization problem that the SVM has is a convex optimization problem and so the good SVM optimization software packages will always find the global minimum or something close to it. And so for the SVM you don’t need to worry about local optima. In practice local optima aren’t a huge problem for neural networks but they all solve, so this is one less thing to worry about if you’re using an SVM. And depending on your problem, the neural network may be slower, especially in this sort of regime than the SVM.
In case the guidelines they gave here, seem a little bit vague and if you’re looking at some problems, you know, the guidelines are a bit vague, I’m still not entirely sure, should I use this algorithm or that algorithm, that’s actually okay. When I face a machine learning problem, you know, sometimes its actually just not clear whether that’s the best algorithm to use, but as you saw in the earlier videos, really, you know, the algorithm does matter, but what often matters even more is things like, how much data do you have. And how skilled are you, how good are you at doing error analysis and debugging learning algorithms, figuring out how to design new features and figuring out what other features to give you learning algorithms and so on. And often those things will matter more than what you are using logistic regression or an SVM. But having said that, the SVM is still widely perceived as one of the most powerful learning algorithms, and there is this regime of when there’s a very effective way to learn complex non linear functions. And so I actually, together with logistic regressions, neural networks, SVM’s, using those to speed learning algorithms you’re I think very well positioned to build state of the art you know, machine learning systems for a wide region for applications and this is another very powerful tool to have in your arsenal. One that is used all over the place in Silicon Valley, or in industry and in the Academia, to build many high performance machine learning system.
