Advertisement
English transcript
ANNOUNCER: The following program is brought to you by Caltech.
YASER ABU-MOSTAFA: Welcome to machine learning, and welcome to our online
audience as well.
Let me start with an outline of the course, and then go into the material
of today's lecture.
As you see from the outline, the topics are given colors, and that
designates their main content, whether it's mathematical or practical.
Machine learning is a very broad subject.
It goes from very abstract theory to extreme practice as in rules of thumb.
And the inclusion of a topic in the course depends on the relevance to
machine learning.
So some mathematics is useful because it gives you the conceptual framework,
and then some practical aspects are useful because they give you the way
to deal with real learning systems.
Now if you look at the topics, these are not meant to be separate topics
for each lecture.
They just highlight the main content of those lectures.
But there is a story line that goes through it, and let me tell you what
the story line is like.
It starts here with: what is learning?
Can we learn?
How to do it?
How to do it well?
And then the take-home lessons.
There is a logical dependency that goes through the course, and there's
one exception to that logical dependency.
One lecture, which is the third one, doesn't really belong here.
It's a practical topic, and the reason I included it early on is because I
needed to give you some tools to play around with, to test the
theoretical and conceptual aspects.
If I waited until it belonged normally, which is to the second aspect of the
linear models which is down there, the beginning of the course would be
just too theoretical for people's taste.
And as you see, if you look at the colors, it is mostly red in the
beginning and mostly blue in the end.
So it starts building the concepts and the theory.
And then it goes on to the practical aspects.
Now, let me start today's lecture.
And the subject of the lecture is the learning problem.
It's an introduction to what learning is.
And I will draw your attention to one aspect of this slide,
which is this part.
That's the logo of the course.
And believe it or not, this is not artwork.
This is actually a technical figure that will come up
in one of the lectures.
I'm not going to tell you which one.
So you can wait in anticipation until it comes up, but this will actually be
a scientific figure that we will talk about.
Now when we move to today's lecture, I'm going to talk
today about the following.
Machine learning is a very broad subject, and I'm going to start with
one example that captures the essence of machine learning.
It's a fun example about movies that everybody watches.
And then after that, I'm going to abstract from the learning problem,
the practical learning problem, aspects that are common to all
learning situations that you're going to face.
And in abstracting them, we'll have the mathematical formalization of the
learning problem.
And then we will get our first algorithm for machine learning today.
It's a very simple algorithm, but it will fix the idea about what is the
role of an algorithm in this case.
And we will survey the types of learning, so that we know which part we
are emphasizing in this course, and which parts are nearby.
And I will end up with a puzzle, a very interesting puzzle, and it's
a puzzle in more ways than one, as you will see.
OK, so let me start with an example.
The example of machine learning that I'm going to start with is how
a viewer would rate a movie.
Now that is an interesting problem, and it's interesting for us because we
watch movies, and very interesting for a company that rents out movies.
And indeed, a company which is Netflix wanted to improve the in-house system
by a mere 10%.
So they make recommendations when you log in, they recommend movies that
they think you will like, so they think that you'll rate them highly.
And they had a system, and they wanted to improve the system.
So how much is a 10% improvement in performance worth to the company?
It was actually $1 million that was paid out to the first group that
actually managed to get the 10% improvement.
So you ask yourself, 10% improvement in something like that, why should
that be worth a million dollars?
It's because, if the recommendations that the movie company makes are spot
on, you will pay more attention to the recommendation, you are likely to rent
the movies that they recommend, and they will make lots of money-- much
more than the million dollars they promised.
And this is very typical in machine learning.
For example, machine learning has applications in financial forecasting.
You can imagine that the minutest improvement in financial forecasting
can make a lot of money.
So the fact that you can actually push the system to be better using machine
learning is a very attractive aspect of the technique in a wide spectrum of
applications.
So what did these guys do?
They gave the data, and people started working on the problem using different
algorithms, until someone managed to get the prize.
Now if you look at the problem of rating a movie, it captures the
essence of machine learning, and the essence has three components.
If you find these three components in a problem you have in your field, then
you know that machine learning is ready as an application tool.
What are the three?
The first one is that a pattern exists.
If a pattern didn't exist, there would be nothing to look for.
So what is the pattern here?
There is no question that the way a person rates a movie is related to how
they rated other movies, and is also related to how other
people rated that movie.
We know that much.
So there is a pattern to be discovered.
However, we cannot really pin it down mathematically.
I cannot ask you to write a 17th-order polynomial that captures how people
rate movies.
So the fact that there is a pattern, and that we cannot pin it down
mathematically, is the reason why we are going for machine learning.
For "learning from data".
We couldn't write down the system on our own, so we're going to depend on
data in order to be able to find the system.
There is a missing component which is very important.
If you don't have that, you are out of luck.
We have to have data. We are learning from data.
So if someone knocks on my door with an interesting machine learning
application, and they tell me how exciting it is, and how great the
application would be, and how much money they would make, the first
question I ask, what data do you have?
If you data, we are in business.
If you don't, you are out of luck.
If you have these three components, you are ready to
apply machine learning.
Now let me give you a solution to the movie rating, in order to start
getting a feel for it.
So here is a system.
Let me start to focus on part of it.
We are going to describe a viewer as a vector of factors, a profile if
you will.
So if you look here for example, the first one would be comedy content.
Does the movie have a lot of comedy?
From a viewer point of view, do they like comedies?
Here, do they like action?
Do they prefer blockbusters, or do they like fringe movies?
And you can go on all the way, even to asking yourself whether you like the
lead actor or not.
Now you go to the content of the movie itself, and you get the
corresponding part.
Does the movie have comedy?
Does it have action?
Is it a blockbuster?
And so on.
Now you compare the two, and you realize that if there is a match--
let's say you hate comedy and the movie has a lot of comedy--
then the chances are you're not going to like it.
But if there is a match between so many coordinates, and the
number of factors here could be really like 300 factors.
Then the chances are you'll like the movie.
And if there's a mismatch, the chances are you're not
going to like the movie.
So what do you do,
you match the movie and the viewer factors, and then you add the
contributions of them.
And then as a result of that, you get the predicted rating.
This is all good except for one problem, which is this is really not
machine learning.
In order to produce this thing, you have to watch the movie, and analyze
the content.
You have to interview the viewer, and ask about their taste.
And then after that, you combine them and try to get
a prediction for the rating.
Now the idea of machine learning is that you don't have to do any of that.
All you do is sit down and sip on your tea, while the machine is doing
something to come up with this figure on its own.
So let's look at the learning approach.
So in the learning approach, we know that the viewer will be a vector of
different factors, and different components for every factor.
So this vector will be different from one viewer to another.
For example, one viewer will have a big blue content here, and one of them
will have a small blue content, depending on their taste.
And then, there is the movie.
And a particular movie will have different contents that correspond to those.
And the way we said we are computing the rating, is by simply taking these
and combining them and getting the rating.
Now what machine learning will do is reverse-engineer that process.
It starts from the rating, and then tries to find out what factors would be
consistent with that rating.
So think of it this way.
You start, let's say, with completely random factors.
So you take these guys, just random numbers from beginning to end, and
these guys, random numbers from beginning to end.
For every user and every movie, that's your starting point.
Obviously, there is no chance in the world that when you get the inner
product between these factors that are random, that you'll get anything that
looks like the rating that actually took place, right?
But what you do is you take a rating that actually happened, and then you
start nudging the factors ever so slightly toward that rating.
Make the direction of the inner product get closer to the rating.
Now it looks like a hopeless thing. I start with so many factors, they are
all random, and I'm trying to make them match a rating.
What are the chances?
Well the point is that you are going to do this not for one rating, but for
a 100 million ratings.
And you keep cycling through the 100 million, over
and over and over.
And eventually, lo and behold, you find that the factors now are
meaningful in terms of the ratings.
And if you get a user, a viewer here, that didn't watch a movie, and you get
the vector that resulted from that learning process, and you get the
movie vector that resulted from that process, and you do the inner product,
lo and behold, you get a rating which is actually consistent with how that
viewer rates the movie.
That's the idea.
Now this actually, the solution I described, is one of the winning
solutions in the competition that I mentioned.
So this is for real, this actually can be used.
Now with this example in mind, let's actually go to the
components of learning.
So now I would like to abstract from the learning problems that I see, what
are the mathematical components that make up the learning problem?
And I'm going to use a metaphor.
I'm going to use a metaphor now from another application domain, which
is a financial application.
So the metaphor we are going to use is credit approval.
You apply for a credit card, and the bank wants to decide whether it's
a good idea to extend a credit card for you or not.
From the bank's point of view, if they're going to make
money, they are happy.
If they are going to lose money, they are not happy.
That's the only criterion they have.
Now, very much like we didn't have a magic formula for deciding how
a viewer will rate a movie, the bank doesn't have a magic formula for
deciding whether a person is creditworthy or not.
What they're going to do, they're going to rely on historical records of
previous customers, and how their credit behavior turned out, and then
try to reverse-engineer the system, and when they get the system frozen,
they're going to apply it to a future customer.
That's the deal.
What are the components here?
Let's look at it.
First, you have the applicant information.
And the applicant information-- you look at this, and you can see that
there is the age, the gender, how much money you make, how much money you
owe, and all kinds of fields that are believed to be related to the
creditworthiness.
Again, pretty much like we did in the movie example, there is no question
that these fields are related to the creditworthiness.
They don't necessarily uniquely determine it, but they are related.
And the bank doesn't want a sure bet. They want to get the credit decision
as reliable as possible.
So they want to use that pattern, in order to be able to come up with
a good decision.
And they take this input, and they want to approve the credit or deny it.
So let's formalize this.
First, we are going to have an input.
And the input is called x. Surprise, surprise!
And that input happens to be the customer application.
So we can think of it as a d-dimensional vector, the first
component is the salary, years in residence, outstanding debt, whatever
the components are.
You put it as a vector, and that becomes the input.
Then we get the output y. The output y is simply the decision, either to
extend credit or not to extend credit, +1 and -1.
And being a good or bad customer, that is from the bank's point of view.
Now we have after that, the target function.
The target function is a function from a domain X, which is the
set of all of these x's.
So it is the set of vectors of d dimensions.
So it's a d-dimensional Euclidean space, in this case.
And then the Y is the set of y's.
Well, that's an easy one because y can only be +1 or -1,
accept or deny.
And therefore this is just a binary co-domain.
And this target function is the ideal credit approval formula, which we
don't know.
In all of our endeavors in machine learning, the target function is
unknown to us.
If it were known, nobody needs learning.
We just go ahead and implement it.
But we need to learn it because it is unknown to us.
So what are we going to do to learn it?
We are going to use data, examples.
So the data in this case is based on previous customer application records.
The input, which is the information in their applications, and the output,
which is how they turned out in hindsight.
This is not a question of prediction at the time they applied, but after
five years, they turned out to be a great customer.
So the bank says, if someone has these attributes again, let's approve
credit because these guys tend to make us money.
And this one made us lose a lot of money, so let's deny it, and so on.
And the historical records-- there are plenty of historical records.
All of this makes sense when you're talking about having 100,000 of
those guys.
Then you pretty much say, I will capture what the essence of that
function is.
So this is the data, and then you use the data, which is the historical
records, in order to get the hypothesis.
The hypothesis is the formal name we're going to call the formula we get
to approximate the target function.
So the hypothesis lives in the same world as the target function, and if
you look at the value of g, it supposedly approximates f.
While f is unknown to us, g is very much known--
actually we created it-- and the hope is that it does approximate f well.
That's the goal of learning.
So this notation will be our notation for the rest of the course, so get
used to it.
The target function is always f, the hypothesis we produce, which we'll
refer to as the final hypothesis will be called g, the data will always have
that notation-- there are capital N points, which are the data set.
And the output is always y.
So this is the formula to be used.
Now, let's put it in a diagram in order to analyze it a little bit more.
If you look at the diagram here, here is the target
function and it is unknown--
that is the ideal approval which we will never know, but that's what we're
hoping to get to approximate.
And we don't see it.
We see it only through the eyes of the training examples.
This is our vehicle of understanding what the target function is.
Otherwise the target function is a mysterious quantity for us.
And eventually, we would like to produce the final hypothesis.
The final hypothesis is the formula the bank is going to use in order to
approve or deny credit, with the hope that g hopefully approximates that f.
Now what connects those two guys?
This will be the learning algorithm.
So the learning algorithm takes the examples, and will produce the final
hypothesis, as we described in the example of the movie rating.
Now there is another component that goes into the learning algorithm.
So what the learning algorithm does, it creates the formula from a preset
model of formulas, a set of candidate formulas, if you will.
And these we are going to call the hypothesis set, a set of hypotheses
from which we are going to pick one hypothesis.
So from this H comes a bunch of small h's, which are functions that can be
candidates for being the credit approval.
And one of them will be picked by the learning algorithm, which happens to
be g, hopefully approximating f.
Now if you look at this part of the chain, from the target function to the
training to the learning algorithm to the final hypothesis, this is very
natural, and nobody will object to that.
But why do we have this hypothesis set?
Why not let the algorithm pick from anything?
Just create the formula, without being restricted to a particular set of
formulas H.
There are two reasons, and I want to explain them.
One of them is that there is no downside for including a hypothesis
set in the formalization.
And there is an upside.
So let me describe why there is no downside, and then describe why there
is an upside.
There is no downside for the simple reason that, from a practical point of
view, that's what you do.
You want to learn, you say I'm going to use a linear formula.
I'm going to use a neural network.
I'm going to use a support vector machine.
So you are already dictating a set of hypotheses.
If you happen to be a brave soul, and you don't want to restrict yourself at
all, very well, then your hypothesis set is the set of all possible
hypotheses.
Right?
So there is no loss of generality in putting it.
So there is no downside.
The upside is not obvious here, but it will become obvious as we go through
the theory.
The hypothesis set will play a pivotal role in the theory of learning.
It will tell us: can we learn, and how well we learn, and whatnot.
Therefore having it as an explicit component in the problem statement
will make the theory go through.
So that's why we have this figure.
Now, let me focus on the solution components of that figure.
What do I mean by the solution components?
If you look at this, the first part, which is the target-- let me try to
expand it--
so the target function is not under your control.
Someone knocks on my door and says: I want to approve credit.
That's the target function, I have no control over that.
And by the way, here are the historical records.
I have no control over that, so they give me the data.
And would you please hand me the final hypothesis?
That is what I'm going to give them at the end, before I receive my check.
So all of that is completely dictated.
Now let's look at the other part. The learning algorithm, and the hypothesis
set that we talked about, are your solution tools.
These are things you choose, in order to solve the problem.
And I would like to take a little bit of a look into what they look like,
and give you an example of them, so that you have a complete chain for
the entire figure in your mind.
From the target function, to the data set, to the learning algorithm,
hypothesis set, and the final hypothesis.
So, here is the hypothesis set.
We chose the notation H for the set, and the element will be given the
symbol small h.
So h is a function, pretty much like the final hypothesis g.
g is just one of them that you h
…
YASER ABU-MOSTAFA: Welcome to machine learning, and welcome to our online
audience as well.
Let me start with an outline of the course, and then go into the material
of today's lecture.
As you see from the outline, the topics are given colors, and that
designates their main content, whether it's mathematical or practical.
Machine learning is a very broad subject.
It goes from very abstract theory to extreme practice as in rules of thumb.
And the inclusion of a topic in the course depends on the relevance to
machine learning.
So some mathematics is useful because it gives you the conceptual framework,
and then some practical aspects are useful because they give you the way
to deal with real learning systems.
Now if you look at the topics, these are not meant to be separate topics
for each lecture.
They just highlight the main content of those lectures.
But there is a story line that goes through it, and let me tell you what
the story line is like.
It starts here with: what is learning?
Can we learn?
How to do it?
How to do it well?
And then the take-home lessons.
There is a logical dependency that goes through the course, and there's
one exception to that logical dependency.
One lecture, which is the third one, doesn't really belong here.
It's a practical topic, and the reason I included it early on is because I
needed to give you some tools to play around with, to test the
theoretical and conceptual aspects.
If I waited until it belonged normally, which is to the second aspect of the
linear models which is down there, the beginning of the course would be
just too theoretical for people's taste.
And as you see, if you look at the colors, it is mostly red in the
beginning and mostly blue in the end.
So it starts building the concepts and the theory.
And then it goes on to the practical aspects.
Now, let me start today's lecture.
And the subject of the lecture is the learning problem.
It's an introduction to what learning is.
And I will draw your attention to one aspect of this slide,
which is this part.
That's the logo of the course.
And believe it or not, this is not artwork.
This is actually a technical figure that will come up
in one of the lectures.
I'm not going to tell you which one.
So you can wait in anticipation until it comes up, but this will actually be
a scientific figure that we will talk about.
Now when we move to today's lecture, I'm going to talk
today about the following.
Machine learning is a very broad subject, and I'm going to start with
one example that captures the essence of machine learning.
It's a fun example about movies that everybody watches.
And then after that, I'm going to abstract from the learning problem,
the practical learning problem, aspects that are common to all
learning situations that you're going to face.
And in abstracting them, we'll have the mathematical formalization of the
learning problem.
And then we will get our first algorithm for machine learning today.
It's a very simple algorithm, but it will fix the idea about what is the
role of an algorithm in this case.
And we will survey the types of learning, so that we know which part we
are emphasizing in this course, and which parts are nearby.
And I will end up with a puzzle, a very interesting puzzle, and it's
a puzzle in more ways than one, as you will see.
OK, so let me start with an example.
The example of machine learning that I'm going to start with is how
a viewer would rate a movie.
Now that is an interesting problem, and it's interesting for us because we
watch movies, and very interesting for a company that rents out movies.
And indeed, a company which is Netflix wanted to improve the in-house system
by a mere 10%.
So they make recommendations when you log in, they recommend movies that
they think you will like, so they think that you'll rate them highly.
And they had a system, and they wanted to improve the system.
So how much is a 10% improvement in performance worth to the company?
It was actually $1 million that was paid out to the first group that
actually managed to get the 10% improvement.
So you ask yourself, 10% improvement in something like that, why should
that be worth a million dollars?
It's because, if the recommendations that the movie company makes are spot
on, you will pay more attention to the recommendation, you are likely to rent
the movies that they recommend, and they will make lots of money-- much
more than the million dollars they promised.
And this is very typical in machine learning.
For example, machine learning has applications in financial forecasting.
You can imagine that the minutest improvement in financial forecasting
can make a lot of money.
So the fact that you can actually push the system to be better using machine
learning is a very attractive aspect of the technique in a wide spectrum of
applications.
So what did these guys do?
They gave the data, and people started working on the problem using different
algorithms, until someone managed to get the prize.
Now if you look at the problem of rating a movie, it captures the
essence of machine learning, and the essence has three components.
If you find these three components in a problem you have in your field, then
you know that machine learning is ready as an application tool.
What are the three?
The first one is that a pattern exists.
If a pattern didn't exist, there would be nothing to look for.
So what is the pattern here?
There is no question that the way a person rates a movie is related to how
they rated other movies, and is also related to how other
people rated that movie.
We know that much.
So there is a pattern to be discovered.
However, we cannot really pin it down mathematically.
I cannot ask you to write a 17th-order polynomial that captures how people
rate movies.
So the fact that there is a pattern, and that we cannot pin it down
mathematically, is the reason why we are going for machine learning.
For "learning from data".
We couldn't write down the system on our own, so we're going to depend on
data in order to be able to find the system.
There is a missing component which is very important.
If you don't have that, you are out of luck.
We have to have data. We are learning from data.
So if someone knocks on my door with an interesting machine learning
application, and they tell me how exciting it is, and how great the
application would be, and how much money they would make, the first
question I ask, what data do you have?
If you data, we are in business.
If you don't, you are out of luck.
If you have these three components, you are ready to
apply machine learning.
Now let me give you a solution to the movie rating, in order to start
getting a feel for it.
So here is a system.
Let me start to focus on part of it.
We are going to describe a viewer as a vector of factors, a profile if
you will.
So if you look here for example, the first one would be comedy content.
Does the movie have a lot of comedy?
From a viewer point of view, do they like comedies?
Here, do they like action?
Do they prefer blockbusters, or do they like fringe movies?
And you can go on all the way, even to asking yourself whether you like the
lead actor or not.
Now you go to the content of the movie itself, and you get the
corresponding part.
Does the movie have comedy?
Does it have action?
Is it a blockbuster?
And so on.
Now you compare the two, and you realize that if there is a match--
let's say you hate comedy and the movie has a lot of comedy--
then the chances are you're not going to like it.
But if there is a match between so many coordinates, and the
number of factors here could be really like 300 factors.
Then the chances are you'll like the movie.
And if there's a mismatch, the chances are you're not
going to like the movie.
So what do you do,
you match the movie and the viewer factors, and then you add the
contributions of them.
And then as a result of that, you get the predicted rating.
This is all good except for one problem, which is this is really not
machine learning.
In order to produce this thing, you have to watch the movie, and analyze
the content.
You have to interview the viewer, and ask about their taste.
And then after that, you combine them and try to get
a prediction for the rating.
Now the idea of machine learning is that you don't have to do any of that.
All you do is sit down and sip on your tea, while the machine is doing
something to come up with this figure on its own.
So let's look at the learning approach.
So in the learning approach, we know that the viewer will be a vector of
different factors, and different components for every factor.
So this vector will be different from one viewer to another.
For example, one viewer will have a big blue content here, and one of them
will have a small blue content, depending on their taste.
And then, there is the movie.
And a particular movie will have different contents that correspond to those.
And the way we said we are computing the rating, is by simply taking these
and combining them and getting the rating.
Now what machine learning will do is reverse-engineer that process.
It starts from the rating, and then tries to find out what factors would be
consistent with that rating.
So think of it this way.
You start, let's say, with completely random factors.
So you take these guys, just random numbers from beginning to end, and
these guys, random numbers from beginning to end.
For every user and every movie, that's your starting point.
Obviously, there is no chance in the world that when you get the inner
product between these factors that are random, that you'll get anything that
looks like the rating that actually took place, right?
But what you do is you take a rating that actually happened, and then you
start nudging the factors ever so slightly toward that rating.
Make the direction of the inner product get closer to the rating.
Now it looks like a hopeless thing. I start with so many factors, they are
all random, and I'm trying to make them match a rating.
What are the chances?
Well the point is that you are going to do this not for one rating, but for
a 100 million ratings.
And you keep cycling through the 100 million, over
and over and over.
And eventually, lo and behold, you find that the factors now are
meaningful in terms of the ratings.
And if you get a user, a viewer here, that didn't watch a movie, and you get
the vector that resulted from that learning process, and you get the
movie vector that resulted from that process, and you do the inner product,
lo and behold, you get a rating which is actually consistent with how that
viewer rates the movie.
That's the idea.
Now this actually, the solution I described, is one of the winning
solutions in the competition that I mentioned.
So this is for real, this actually can be used.
Now with this example in mind, let's actually go to the
components of learning.
So now I would like to abstract from the learning problems that I see, what
are the mathematical components that make up the learning problem?
And I'm going to use a metaphor.
I'm going to use a metaphor now from another application domain, which
is a financial application.
So the metaphor we are going to use is credit approval.
You apply for a credit card, and the bank wants to decide whether it's
a good idea to extend a credit card for you or not.
From the bank's point of view, if they're going to make
money, they are happy.
If they are going to lose money, they are not happy.
That's the only criterion they have.
Now, very much like we didn't have a magic formula for deciding how
a viewer will rate a movie, the bank doesn't have a magic formula for
deciding whether a person is creditworthy or not.
What they're going to do, they're going to rely on historical records of
previous customers, and how their credit behavior turned out, and then
try to reverse-engineer the system, and when they get the system frozen,
they're going to apply it to a future customer.
That's the deal.
What are the components here?
Let's look at it.
First, you have the applicant information.
And the applicant information-- you look at this, and you can see that
there is the age, the gender, how much money you make, how much money you
owe, and all kinds of fields that are believed to be related to the
creditworthiness.
Again, pretty much like we did in the movie example, there is no question
that these fields are related to the creditworthiness.
They don't necessarily uniquely determine it, but they are related.
And the bank doesn't want a sure bet. They want to get the credit decision
as reliable as possible.
So they want to use that pattern, in order to be able to come up with
a good decision.
And they take this input, and they want to approve the credit or deny it.
So let's formalize this.
First, we are going to have an input.
And the input is called x. Surprise, surprise!
And that input happens to be the customer application.
So we can think of it as a d-dimensional vector, the first
component is the salary, years in residence, outstanding debt, whatever
the components are.
You put it as a vector, and that becomes the input.
Then we get the output y. The output y is simply the decision, either to
extend credit or not to extend credit, +1 and -1.
And being a good or bad customer, that is from the bank's point of view.
Now we have after that, the target function.
The target function is a function from a domain X, which is the
set of all of these x's.
So it is the set of vectors of d dimensions.
So it's a d-dimensional Euclidean space, in this case.
And then the Y is the set of y's.
Well, that's an easy one because y can only be +1 or -1,
accept or deny.
And therefore this is just a binary co-domain.
And this target function is the ideal credit approval formula, which we
don't know.
In all of our endeavors in machine learning, the target function is
unknown to us.
If it were known, nobody needs learning.
We just go ahead and implement it.
But we need to learn it because it is unknown to us.
So what are we going to do to learn it?
We are going to use data, examples.
So the data in this case is based on previous customer application records.
The input, which is the information in their applications, and the output,
which is how they turned out in hindsight.
This is not a question of prediction at the time they applied, but after
five years, they turned out to be a great customer.
So the bank says, if someone has these attributes again, let's approve
credit because these guys tend to make us money.
And this one made us lose a lot of money, so let's deny it, and so on.
And the historical records-- there are plenty of historical records.
All of this makes sense when you're talking about having 100,000 of
those guys.
Then you pretty much say, I will capture what the essence of that
function is.
So this is the data, and then you use the data, which is the historical
records, in order to get the hypothesis.
The hypothesis is the formal name we're going to call the formula we get
to approximate the target function.
So the hypothesis lives in the same world as the target function, and if
you look at the value of g, it supposedly approximates f.
While f is unknown to us, g is very much known--
actually we created it-- and the hope is that it does approximate f well.
That's the goal of learning.
So this notation will be our notation for the rest of the course, so get
used to it.
The target function is always f, the hypothesis we produce, which we'll
refer to as the final hypothesis will be called g, the data will always have
that notation-- there are capital N points, which are the data set.
And the output is always y.
So this is the formula to be used.
Now, let's put it in a diagram in order to analyze it a little bit more.
If you look at the diagram here, here is the target
function and it is unknown--
that is the ideal approval which we will never know, but that's what we're
hoping to get to approximate.
And we don't see it.
We see it only through the eyes of the training examples.
This is our vehicle of understanding what the target function is.
Otherwise the target function is a mysterious quantity for us.
And eventually, we would like to produce the final hypothesis.
The final hypothesis is the formula the bank is going to use in order to
approve or deny credit, with the hope that g hopefully approximates that f.
Now what connects those two guys?
This will be the learning algorithm.
So the learning algorithm takes the examples, and will produce the final
hypothesis, as we described in the example of the movie rating.
Now there is another component that goes into the learning algorithm.
So what the learning algorithm does, it creates the formula from a preset
model of formulas, a set of candidate formulas, if you will.
And these we are going to call the hypothesis set, a set of hypotheses
from which we are going to pick one hypothesis.
So from this H comes a bunch of small h's, which are functions that can be
candidates for being the credit approval.
And one of them will be picked by the learning algorithm, which happens to
be g, hopefully approximating f.
Now if you look at this part of the chain, from the target function to the
training to the learning algorithm to the final hypothesis, this is very
natural, and nobody will object to that.
But why do we have this hypothesis set?
Why not let the algorithm pick from anything?
Just create the formula, without being restricted to a particular set of
formulas H.
There are two reasons, and I want to explain them.
One of them is that there is no downside for including a hypothesis
set in the formalization.
And there is an upside.
So let me describe why there is no downside, and then describe why there
is an upside.
There is no downside for the simple reason that, from a practical point of
view, that's what you do.
You want to learn, you say I'm going to use a linear formula.
I'm going to use a neural network.
I'm going to use a support vector machine.
So you are already dictating a set of hypotheses.
If you happen to be a brave soul, and you don't want to restrict yourself at
all, very well, then your hypothesis set is the set of all possible
hypotheses.
Right?
So there is no loss of generality in putting it.
So there is no downside.
The upside is not obvious here, but it will become obvious as we go through
the theory.
The hypothesis set will play a pivotal role in the theory of learning.
It will tell us: can we learn, and how well we learn, and whatnot.
Therefore having it as an explicit component in the problem statement
will make the theory go through.
So that's why we have this figure.
Now, let me focus on the solution components of that figure.
What do I mean by the solution components?
If you look at this, the first part, which is the target-- let me try to
expand it--
so the target function is not under your control.
Someone knocks on my door and says: I want to approve credit.
That's the target function, I have no control over that.
And by the way, here are the historical records.
I have no control over that, so they give me the data.
And would you please hand me the final hypothesis?
That is what I'm going to give them at the end, before I receive my check.
So all of that is completely dictated.
Now let's look at the other part. The learning algorithm, and the hypothesis
set that we talked about, are your solution tools.
These are things you choose, in order to solve the problem.
And I would like to take a little bit of a look into what they look like,
and give you an example of them, so that you have a complete chain for
the entire figure in your mind.
From the target function, to the data set, to the learning algorithm,
hypothesis set, and the final hypothesis.
So, here is the hypothesis set.
We chose the notation H for the set, and the element will be given the
symbol small h.
So h is a function, pretty much like the final hypothesis g.
g is just one of them that you h
…