So I've tried to convince you that learning is just essentially curve fitting.

And that kind of sounds like a geometric problem or something like this.

I would like to now come up, use a different example where we're really fitting some kind of a function to examples,

but which is much less geometric.

And what I want to do is I want to look at learning decision trees.

Because that actually allows me to make a couple of points that are important and actually carry over to the rest.

So look at the following situation.

You want to go to a restaurant and this is a US example.

And what you do is you don't pick out your own table, but you actually wait to be seated.

And then sometimes the people there tell you, we don't have a table.

Now there's the question and then they usually say, well, maybe you want to take a seat at the bar and have something to drink first,

and then you can wait until a table becomes free.

Now the question is you look around and you take a decision whether you want to go to the next restaurant

or whether you want to wait for the table or you're not that hungry after all or those kind of things.

So will I wait for a table?

And I have here 12 examples and all of those are characterized by a couple of attributes.

And the attributes are, do I have an alternative?

Is this the only restaurant that I can afford in town?

Does it have a bar?

Because waiting at the bar is much nicer than waiting outside.

Is it a Friday?

Am I hungry?

How many people are in the restaurant?

How many patrons are there?

How expensive is the restaurant?

Does it rain?

Do I have a reservation?

What's the type?

And what's the estimation of the maître who tells you, I should have a table in 30 minutes or something like this.

So that kind of describes the situation broadly.

And we have the decision whether we'll wait.

Right here, if we have an alternative and it's only 10 minute wait and I'm hungry and it's an expensive restaurant but it doesn't rain, then I'll wait.

If it's more than an hour and a burger restaurant, I'm not going to wait.

No way.

Right?

And so on.

Okay, now this is our set of examples and we want to find a function that will make predictions.

We want to find a function that is consistent with all of those.

And since we are interested in a Boolean result of the function, we're probably not going to take a polynomial.

So we're not in the kind of red-blue-green curve situation.

And the functions I'm going to look at that is what is called a decision tree.

You pick out one of the attributes and depending on what the values are, you make decisions.

If there is, if there are no patrons, I won't wait in this example.

Okay?

If there are some patrons, I will wait.

If it's full, then I'll look at what is the estimate.

And depending on that, if it's up to 10 minutes, I will always wait.

If it's greater than 60 minutes, I'll never wait and then I'll look at whether there's alternates or if I'm hungry and so on.

And eventually, I go through all the, I go through sufficiently many attributes and in the end, I'll make a decision.

Anybody of you red-green blind?