Our next application of nonlinear least squares is nonlinear model fitting.
Um, and so we'll just look at what happens when the parameters,
uh, enter the model in a non-affine way.
When they're entered in an affine way,
you have just linear least squares and we already know how to do that.
So nonlinear model fitting looks like this.
Um, we have our predictor, uh,
that's our- our model or predictor f hat of x_i,
that is going to be, uh,
the ith feature vector.
Um, and then the parameter Theta,
that's what we seek to choose.
And then this is the prediction.
So this is really, uh,
y hat i, right?
And this is the sum of the squares of the errors, prediction errors, right?
So now the difference here,
um, is that, um,
we are not assuming, uh, that,
f hat, um, depends in an affine way on Theta.
Um, now, in the linear in the parameters model, it looks like this.
And this is exactly- this is the- this is the general case of what it
would be if f hat was a linear function of Theta.
That's called the linear in parameters
model because it's a linear function of the parameters.
Of course, it's not necessarily a linear function of x and usually is not.
Um, but it's a linear function of the parameters.
Um, so here we're gonna allow this f hat,
uh, to be a nonlinear function of the- of the model parameters.
Um, and we'll see that there's lots of examples where that can be helpful.
[NOISE] It can also improve interpretability, things like that.
And we're gonna minimize over the,
uh, this- the model parameters Theta.
So we'll look at a quick example.
Uh, so we have some data and, er,
for some reason we believe that it has the form of a decaying sinusoid.
Okay, so, we're gonna write it this way.
It's Theta 1 times exp Theta 2 x.
Uh, Theta 2 gives you the decay rate if it's negative or positive, the growth rate.
And then, uh, cosine term,
cosine Theta 3 x,
uh, plus Theta 4.
Uh, Theta 3 is essentially the frequency of the sinusoid.
And Theta 4 gives you the offset or phase for that.
So- so that's it- that's- that's it- a model that's parameterized by four parameters.
And then your job is to,
given some data points,
uh, which you can see on this plot are the little green circles.
Um, given the data points,
your job is to choose Theta 1, Theta 2, Theta 3,
Theta 4, uh, to fit,
uh, to- to get a good fit with your data.
Um, now, that ends up with a,
uh, a nonlinear least squares problem,
because you end up with this objective.
You sum over all of your data points.
Um, this thing, of course,
that's y hat- that's y hat,
er, i, like that.
Um, and you can see that it doesn't- it's not linear.
Well, actually I should say one thing.
It is linear in Theta 1.
So we could solve for Theta 1 by our least squares problem,
but, you know, not Theta 2,
Theta 3, and Theta 4.
Okay, um, so this,
I would say thing- things like this are- are quite, you know,
this is easily done,
um, by using Levenberg–Marquardt.
And in fact, I believe the fit that we're showing there is one
computed from these data points, uh, using Levenberg–Marquardt.
And you can see it gets- it fits a decaying sinusoid like quite nicely.
Okay. Um, the next, uh,
example of this is something called orthogonal distance regression.
So, um, let's remember that when you actually normally fit a function,
what happens is you'd have a curve like this.
That's your- that's your approximation and you have
a data point like this or like that, something like that.
Um, what we- what we measure their is the vertical distance
between your data point and- and the- and the value of the model here.
That's- that's the traditional thing.
If you look at, uh,
if you look at traditional model fitting, you do that.
You- you have the- it's the vertical distance between- the vertical distance
between the data point and the- and the, uh, function value.
Um, and in some cases you literally wanna fit a curve.
And if you're fitting a curve, not a function,
I mean if you think of it as a curve not a function,
then basically what it does is you- what you
really should do is look at the actual distance to the curve.
Now the distance to the curve is defined as the closest point
on the- distance of the closest point on the curve to you.
Um, and so that means that instead of penalizing
the vertical distance like this we're actually if the curve looks like that,
we're actually gonna penalize you for being away from the curve.
So that's it. Um, this would be as it is.
In- in this case, you're not really thinking of this as a function,
you're thinking of it more as a relation or a curve.
Um, this picture, uh,
shows you, you know,
how you would do that, uh,
what the picture is, uh, for that.
Um, and, you know,
it's similar to but slightly different from,
um, the, uh, it's slightly different from normal fitting.
Um, actually, the main point here is that you're allowed, uh,
when you have a data point,
you're allowed not to associate it with the same value of x.
You're actually allowed to mess with
the x and- and- and compare it to a slightly different one.
So actually sometimes people call this an error,
error in the features model because we're all also- what
we're giving ourselves license to do is to actually,
uh, change the value of x associated with- with the,
uh, a data point.
So that looks like this.
Um, so we'll write it out as a nonlinear least squares problem.
What we'll do is [NOISE] we'll take the,
uh, difference in- in- in the y's,
but we're gonna evaluate it at a u_i.
U_i is gonna be a variable.
Like I said, we don't actually- if you spit u_i- if you insist u_i equals x_i,
we're back where we were before.
Um, but we're gonna do is we're actually gonna allow you to mess with that,
and then we're actually gonna penalize you for, um,
for basically moving, choosing an x that- sorry,
an x value called u_i which is not the same as the given x value, x_i.
Um, and that if you look at this- this case in, well, in 1d,
you get- you kinda get the idea, uh,
that the- the distance to the curve here is two things.
It's the vertical distance which were kind of,
that- that- that's the one that we're- that's this term, right?
And then there's this term, right?
Here, uh, u and x are,
uh, scalars, so it's just the absolute value.
So it's the square root of the sum of the squares,
and the distance squared is the sum of the squares.
Um, so here what we're gonna do- this is- we're gonna optimize in this problem over,
uh, the following variables, Theta,
those are the- the model parameters and u_i.
So by the way, even in this case,
if Theta enters, uh,
linearly into f hat,
so it's a linear in the parameters model.
Even in this case, this is a-
a nonlinear least squares problem because we also have u_i's there,
uh, which we're allowed to mess with.
Okay. So that is, um,
this is- this is a,
um, a- this is called orthogonal distance regression.
I guess it's called orthogonal because you associate with each point,
um, a- a point on the curve,
on the- on- on- on the graph of the function,
um, and the tangent to the function
there is orthogonal to the- to the deviation from that point to,
um, to- to the given data point.
So that's why it's called orthogonal distance regression.
But you'll hear this and you'll see this in- in a bunch of applications.
The next topic is nonlinear least squares classification.
So let's see how this works.
Uh, well, recall that in a linear least squares classifier,
what we do is we, uh- first,
we fit by least squares,
uh, and f Tilde of x.
Uh, that's simply a- a regression or
a- a- a- a model prediction that predicts the real number,
uh, that should be a sub- ideally close to minus 1 or plus 1.
That's the idea. Now, then of course, we're not allowed,
if someone says for this- for this feature vector,
do you think it's true or false?
You're not allowed to say it's 0.6 or something,
or- or partly true or something like that.
Um, what you'll do instead is we'll take the sign of that.
So that's- that- that's the actual,
uh- that's the actual predictor.
Um, okay.
And this is- we just use,
uh, ordinary least squares to do this.
Now, a nonlinear least squares classifier, uh, does this.
It starts with the following observation.
If- we're going to work directly with the sign, right.
In- in- in- in least squares classification,
we don't use- we don't use the sign at all.
That's a post-process, right?
We simply use least squares,
which you know how to do, we fit it,
and then we take the sign,
and actually, the weird part is that it kinda works pretty well, often, but- okay.
Here we're going to take into effect-
into account the fact that we're gonna use the sign.
So let's see how this works.
Um, sine of f hat of x_i has only two values,
plus or minus 1, y_i has only two values, plus or minus 1.
So if I subtract them,
you either get zero,
if they agree, or you get,
uh, minus, you get plus 2 or minus 2.
And those are the two cases when it doesn't agree.
Now, when you square plus 2 or minus 2, uh, you get 4.
So it turns out the sum over the data of sign f Tilde
of x_i minus y_i squared is actually four times the number of errors.
So now what we're gonna do,
we're gonna directly- well,
not directly, not quite.
We're going to attempt to minimize that,
because we really would like to pick
parameters for which our model makes as few errors as possible.
Okay. So let's try that.
Um, oh, one minor problem.
Sine of f Tilde of x is discontinuous and so it's not differentiable, right?
Because the sine function,
you know, goes like this.
It's gonna- it's gonna- it's gonna jump at 0.
Now, in this case,
it's where f Tilde e of x is 0.
Actually, interestingly, it's gonna jump- f Tilde of x equals 0 is sort
of- some people call that the confusion point because in a classifier,
you know, f Tilde of x equals 0 means,
I don't know, it could be minus 1 or plus 1.
You know, f Tilde equals 0.3 means,
okay, I think f hat should be 1.
Minus 0.3 means f hat should probably be minus 1.
But zero means like, I don't know.
I don't know. So it's a decision and at that de- at that confusion point,
I should say, it's actually not as a big jump, it's non-differentiable.
So what we do instead is you just
simply replace sign with a differentiable approximation of it.
Uh, for example, a sigmoid function,
which I'll show you, uh, shortly.
And then you just use, uh, Levenberg–Marquardt to minimize this.
It's a- it's a non- it's just fine.
It's a nonlinear least squares problem.
Okay. So here's a sigmoid function.
Uh, you'll probably see this in a whole bunch of different things,
but that's- that's it.
And the idea is, you know,
here's the sign function, right?
And the sigmoid function is like a smooth approximation of it. So that's the idea.
So we just have a- we just have a sigmoid function,
uh, in there, like that,
and that's- that's- that's what we're gonna do.
Okay. Uh, so this actually works, actually shockingly well.
So, uh, we'll go back to the MNIST,
uh, handwritten digit dataset.
The very- very famous dataset these days or
not anymore because people have moved on with much bigger ones,
CIFAR, and stuff like that.
Okay. So, um- but the feature vector here,
x is a 493 vector of pixel intensities,
I think, including one that's constant, right? So that's it.
And we're gonna make a nonlinear least squares 10-way multi, uh- multi-class classifier.
So, um- and, uh,
when we do this,
I mean you get down to 7.5 error,
uh, on- on- on this.
So, um- so the- the,
the Boolean classifiers are- are computed by solving this nonlinear,
uh, least squares problem, right?
Which says- which says minimize this.
And we take phi to be a sigmoid here.
Um, here, we add regularization, and sure enough,
as Lambda gets, uh, bigger,
we actually improve, uh,
on our test error.
And so we should take Lambda somewhere in this region right here, right?
So we could take it to be,
I don't know, 0.3, 0.5.
I don't know, something like that.
Some- somewhere- somewhere in that- in that- in that range.
Um, so that's how that works.
Um, okay.
We're gonna take that same problem
and we're going to do a little bit of feature engineering.
We're gonna do profoundly stupid feature engineering,
which is we're gonna generate 5,000 random features,
which is you take a linear- you take random linear combinations,
then you take the sine or something.
No, uh, sorry.
Positive part, right?
And that's just our- I mean, you could do way,
way better if you sort of did handcrafted features.
But this is just to show you what happens if you just do some feature engineering.
The test set error, in this case,
drops to two percent.
Um, by the way, that's the performance of human beings on recognizing digits.
In other words, if you simply take those digits,
show them to a person, and they're like, yeah, sure.
You say- usually, this would be like an undergrad or something like that and we'd
force them to do it or something in a class and be- and that'll be part of the class,
is- is you have to look at, you know,
300 digits and type in whether it's 0 to 9.
That's it. Um, when you do that,
uh, that- the test set error drops.
For- for people, sorry, for people,
they get an error rate that's about 2%.
Um, so about 1 in 50, you know,
some of these things are written- these handwritten things
are written pretty poorly, right?
Um, and sometimes, you would look at it and you'd say,
that is a 7,
and then- but the data would say that's a 9,
or at least that person thought they were writing a 9.
You know, it looks like a 7, but it's a 9.
Um, so- all right.
So that means that just, you know,
using pretty much the material of this book and class,
um, you match human performance.
Um, it's actually really kind of a stunning thing to think about briefly,
because you- if you think about like how dumb what's happening is,
but you understand all the moving parts, it's just pixels.
Um, the algorithm you put together,
which would be Levenberg–Marquardt on this thing,
it, uh- it doesn't- it- it knows- it's profoundly stupid.
It does not know what integers are.
It knows nothing.
Um, and yet here it is,
classifying- classifying digits, um,
just as well as people are.
Um, now, if you do more feature engineering,
you can easily beat,
uh, human performance substantially,
which starts getting weird and creepy if you think about it.
Now, I should also add that, you know,
with a- I mean, there's other methods.
Uh, this is an ideal problem for these, uh,
classifiers- classifiers called neural networks,
and they- they can easily get superhuman performance on them.
It's like just e- easily.
Um, I should add that you can actually minimize,
uh- you can fit neural networks,
you know, using, uh, Levenberg–Marquardt.
Now, anyway, uh, so this shows you that just,
you know, putting together some bits and pieces from this course,
you actually get to maybe not the state of the art,
but you're not too far behind and at least it demystifies how all these things work.
Um, this is kinda how they all work.
If you go and look at, uh,
how these are actually done on your internships or whatever, uh,
you'll- you'll see that it's very similar to the stuff we've been talking about.