In this video, we'll talk about

the normal equation, which for

some linear regression problems, will

give us a much better way

to solve for the optimal value

of the parameters theta.

Concretely, so far the

algorithm that we've been using

for linear regression is gradient

descent where in order

to minimize the cost function

J of Theta, we would take

this iterative algorithm that takes

many steps, multiple iterations of

gradient descent to converge

to the global minimum.

In contrast, the normal equation

would give us a method to

solve for theta analytically, so

that rather than needing to run

this iterative algorithm, we can

instead just solve for the

optimal value for theta

all at one go, so that in

basically one step you get

to the optimal value right there.

It turns out the normal equation

that has some advantages and

some disadvantages, but before

we get to that and talk about

when you should use it, let's

get some intuition about what this method does.

For this week's planetary example, let's

imagine, let's take a

very simplified cost function

J of Theta, that's just the

function of a real number Theta.

So, for now, imagine that Theta

is just a scalar value or that Theta is just a row value.

It's just a number, rather than a vector.

Imagine that we have a cost function J that's a quadratic function of this real value

parameter Theta, so J of Theta looks like that.

Well, how do you minimize a quadratic function?

For those of you that know a little bit of calculus,

you may know that the way to

minimize a function is to

take derivatives and to

set derivatives equal to zero.

So, you take the derivative of J with respect to the parameter of Theta.

You get some formula which I am not going to derive,

you set that derivative

equal to zero, and this

allows you to solve for

the value of Theda that minimizes J of Theta.

That was a simpler case

of when data was just real number.

In the problem that we are interested in, Theta is

no longer just a real number,

but, instead, is this

n+1-dimensional parameter vector, and,

a cost function J is

a function of this vector

value or Theta 0 through

Theta m. And, a cost

function looks like this, some square cost function on the right.

How do we minimize this cost function J?

Calculus actually tells us

that, if you, that

one way to do so, is

to take the partial derivative of J, with respect to every parameter of Theta J in turn, and then, to set

all of these to 0.

If you do that, and you

solve for the values of

Theta 0, Theta 1,

up to Theta N, then,

this would give you that values

of Theta to minimize the cost

function J. Where, if

you actually work through the

calculus and work through

the solution to the parameters

Theta 0 through Theta N, the

derivation ends up being somewhat involved.

And, what I am going

to do in this video,

is actually to not go

through the derivation, which is kind

of long and kind of involved, but

what I want to do is just

tell you what you need to know

in order to implement this process

so you can solve for the

values of the thetas that

corresponds to where the

partial derivatives is equal to zero.

Or alternatively, or equivalently,

the values of Theta is that

minimize the cost function J of Theta.

I realize that some of

the comments I made that made

more sense only to those

of you that are normally familiar with calculus.

So, but if you don't

know, if you're less familiar

with calculus, don't worry about it.

I'm just going to tell you what

you need to know in order to

implement this algorithm and get it to work.

For the example that I

want to use as a running

example let's say that

I have m = 4 training examples.

In order to implement this normal

equation at big, what I'm going to do is the following.

I'm going to take my

data set, so here are my four training examples.

In this case let's assume that,

you know, these four examples is all the data I have.

What I am going to do is take

my data set and add

an extra column that corresponds

to my extra feature, x0,

that is always takes

on this value of 1.

What I'm going to do is

I'm then going to construct

a matrix called X that's

a matrix are basically contains all

of the features from my

training data, so completely

here is my here are

all my features and we're

going to take all those numbers and

put them into this matrix "X", okay?

So just, you know, copy

the data over one column

at a time and then I am going to do something similar for y's.

I am going to take the

values that I'm trying to

predict and construct now

a vector, like so

and call that a vector y.

So X is going to be a

m by (n+1) - dimensional matrix, and

Y is going to be

a m-dimensional vector

where m is the number of training examples

and n is, n is

a number of features, n+1, because of

this extra feature X0 that I had.

Finally if you take

your matrix X and you take

your vector Y, and if you

just compute this, and set

theta to be equal to

X transpose X inverse times

X transpose Y, this would

give you the value of theta

that minimizes your cost function.

There was a lot

that happened on the slides and

I work through it using one specific example of one dataset.

Let me just write this

out in a slightly more general form

and then let me just, and later on in

this video let me explain this equation a little bit more.

It is not yet entirely clear how to do this.

In a general case, let us

say we have M training examples

so X1, Y1 up to

Xn, Yn and n features.

So, each of the training example

x(i) may looks like a vector

like this, that is a n+1 dimensional feature vector.

The way I'm going to construct the

matrix "X", this is

also called the design matrix

is as follows.

Each training example gives

me a feature vector like this.

say, sort of n+1 dimensional vector.

The way I am going to construct my

design matrix x is only construct the matrix like this.

and what I'm going to

do is take the first

training example, so that's

a vector, take its transpose

so it ends up being this,

you know, long flat thing and

make x1 transpose the first row of my design matrix.

Then I am going to take my

second training example, x2, take

the transpose of that and

put that as the second row

of x and so on,

down until my last training example.

Take the transpose of that,

and that's my last row of

my matrix X. And, so,

that makes my matrix X, an

M by N +1

dimensional matrix.

As a concrete example, let's

say I have only one

feature, really, only one

feature other than X zero,

which is always equal to 1.

So if my feature vectors

X-i are equal to this

1, which is X-0, then

some real feature, like maybe the

size of the house, then my

design matrix, X, would be equal to this.

For the first row, I'm going

to basically take this and take its transpose.

So, I'm going to end up with 1, and then X-1-1.

For the second row, we're going to end

up with 1 and then

X-1-2 and so

on down to 1, and

then X-1-M.

And thus, this will be

a m by 2-dimensional matrix.

So, that's how to construct

the matrix X. And, the

vector Y--sometimes I might

write an arrow on top to

denote that it is a vector,

but very often I'll just write this as Y, either way.

The vector Y is obtained by

taking all all the labels,

all the correct prices of

houses in my training set, and

just stacking them up into

an M-dimensional vector, and

that's Y. Finally, having

constructed the matrix X

and the vector Y, we then

just compute theta as X'(1/X)

x X'Y. I just

want to make

I just want to make sure that this equation makes sense to you

and that you know how to implement it.

So, you know, concretely, what is this X'(1/X)?

Well, X'(1/X) is the

inverse of the matrix X'X.

Concretely, if you were

to say set A to

be equal to X' x

X, so X' is a

matrix, X' x X

gives you another matrix, and we

call that matrix A. Then, you

know, X'(1/X) is just

you take this matrix A and you invert it, right!

This gives, let's say 1/A.

And so that's how you compute this thing.

You compute X'X and then you compute its inverse.

We haven't yet talked about Octave.

We'll do so in the later

set of videos, but in the

Octave programming language or a

similar view, and also the

matlab programming language is very similar.

The command to compute this quantity,

X transpose X inverse times

X transpose Y, is as follows.

In Octave X prime is

the notation that you use to denote X transpose.

And so, this expression that's

boxed in red, that's computing

X transpose times X.

pinv is a function for

computing the inverse of

a matrix, so this computes

X transpose X inverse,

and then you multiply that by

X transpose, and you multiply

that by Y. So you

end computing that formula

which I didn't prove,

but it is possible to

show mathematically even though I'm

not going to do so

here, that this formula gives you

the optimal value of theta

in the sense that if you set theta equal

to this, that's the value

of theta that minimizes the

cost function J of theta

for the new regression.

One last detail in the earlier video.

I talked about the feature

skill and the idea of

getting features to be

on similar ranges of

Scales of similar ranges of values of each other.

If you are using this normal

equation method then feature

scaling isn't actually necessary

and is actually okay if,

say, some feature X one

is between zero and one,

and some feature X two is

between ranges from zero to

one thousand and some feature

x three ranges from zero

to ten to the

minus five and if

you are using the normal equation method

this is okay and there is

no need to do features

scaling, although of course

if you are using gradient descent,

then, features scaling is still important.

Finally, where should you use the gradient descent

and when should you use the normal equation method.

Here are some of the their advantages and disadvantages.

Let's say you have m training

examples and n features.

One disadvantage of gradient descent

is that, you need to choose the learning rate Alpha.

And, often, this means running

it few times with different learning

rate alphas and then seeing what works best.

And so that is sort of extra work and extra hassle.

Another disadvantage with gradient descent

is it needs many more iterations.

So, depending on the details,

that could make it slower, although

there's more to the story as we'll see in a second.

As for the normal equation, you don't need to choose any learning rate alpha.

So that, you know, makes it really convenient, makes it simple to implement.

You just run it and it usually just works.

And you don't need to

iterate, so, you don't need

to plot J of Theta or

check the convergence or take all those extra steps.

So far, the balance seems to

favor normal the normal equation.

Here are some disadvantages of

the normal equation, and some advantages of gradient descent.

Gradient descent works pretty well,

even when you have a very large number of features.

So, even if you

have millions of features you

can run gradient descent and it will be reasonably efficient.

It will do something reasonable.

In contrast to normal equation, In, in

order to solve for the parameters

data, we need to solve for this term.

We need to compute this term, X transpose, X inverse.

This matrix X transpose X.

That's an n by n matrix, if you have n features.

Because, if you look

at the dimensions of

X transpose the dimension of

X, you multiply, figure out what

the dimension of the product

is, the matrix X transpose

X is an n by n matrix where

n is the number of features, and

for almost computed implementations

the cost of inverting

the matrix, rose roughly as

the cube of the dimension of the matrix.

So, computing this inverse costs,

roughly order, and cube time.

Sometimes, it's slightly faster than

N cube but, it's, you know, close enough for our purposes.

So if n the number of features is very large,

then computing this

quantity can be slow and

the normal equation method can actually be much slower.

So if n is

large then I might

usually use gradient descent because

we don't want to pay this all in q time.

But, if n is relatively small,

then the normal equation might give you a better way to solve the parameters.

What does small and large mean?

Well, if n is on

the order of a hundred, then

inverting a hundred-by-hundred matrix is

no problem by modern computing standards.

If n is a thousand, I would still use the normal equation method.

Inverting a thousand-by-thousand matrix is

actually really fast on a modern computer.

If n is ten thousand, then I might start to wonder.

Inverting a ten-thousand- by-ten-thousand matrix

starts to get kind of slow,

and I might then start to

maybe lean in the

direction of gradient descent, but maybe not quite.

n equals ten thousand, you can

sort of convert a ten-thousand-by-ten-thousand matrix.

But if it gets much bigger than that, then, I would probably use gradient descent.

So, if n equals ten

to the sixth with a million

features, then inverting a

million-by-million matrix is going

to be very expensive, and

I would definitely favor gradient descent if you have that many features.

So exactly how large

set of features has to be

before you convert a gradient descent, it's hard to give a strict number.

But, for me, it is usually

around ten thousand that I might

start to consider switching over

to gradient descents or maybe,

some other algorithms that we'll talk about later in this class.

To summarize, so long

as the number of features is

not too large, the normal equation

gives us a great alternative method to solve for the parameter theta.

Concretely, so long as

the number of features is less

than 1000, you know, I would

use, I would usually is used

in normal equation method rather than, gradient descent.

To preview some ideas that

we'll talk about later in this

course, as we get

to the more complex learning algorithm, for

example, when we talk about

classification algorithm, like a logistic regression algorithm,

We'll see that those algorithm

actually...

The normal equation method actually do not work

for those more sophisticated

learning algorithms, and, we

will have to resort to gradient descent for those algorithms.

So, gradient descent is a very useful algorithm to know.

The linear regression will have

a large number of features and

for some of the other algorithms

that we'll see in

this course, because, for them, the normal

equation method just doesn't apply and doesn't work.

But for this specific model of

linear regression, the normal equation

can give you a alternative

that can be much faster, than gradient descent.

So, depending on the detail of your algortithm,

depending of the detail of the problems and

how many features that you have,

both of these algorithms are well worth knowing about.

Normal Equation

Aprendizagem Automática

Conheça os instrutores