One thing we looked at in more detail was the hypothesis space of decision trees in

which you can learn, just like in any other hypothesis space.

So we had a running example which was, will we wait for a table in a restaurant that is

characterized by 10 attributes and what we want to learn is the target, whether we want

to wait or not. Not quite neural networks yet, but we can learn a lot from looking at

these examples. So we have a classification problem where we classify the situations into

the good or the bad. We'll wait or we won't wait. Generally, if we want to learn a function

that is discrete valued, in this case it's Boolean, so it is discrete value, then we talk

of classification problems. And this is what the functions look like. We take decisions

based on attributes and these attributes will have a couple of values, so we get a finitely

branching tree and on the leaves we have the decisions. We talked about the expressiveness

of this, which essentially is how big is the hypothesis space and we saw that the hypothesis

space is huge, it's 2 to the 2 to the n. And of course, as always, we take the upper brackets,

which makes it worse. And we looked at an algorithm which we call decision tree learning

which is relatively simple, which is just pick an attribute, if we have this attribute

and look at the subsets for each value. If I have a subset that's homogenous, that's

the other, but it's better to explain it that way, right? We have a situation where we have

a distribution of trues and falses, if we split that into subsets with respect to the

patrons attribute, we get here two homogenous subsets, for those I can make a decision,

divides into these two decisions and we have a non-homogenous subset with patrons where

we just have to recursively do the same. That's what this recursive algorithm does, it chooses

an attribute, if I have homogeneity, then I'm forced into a decision, if I have no information,

then I'll just take the mode, so the most frequently attained value there and otherwise

I recurse. The question here is which attributes to choose and there is actually indeed a very

important decision to make here in the sense that we, depending on how we choose, we get

huge trees or small trees. Small trees typically generalize better and that's something we'll

look to, that's why I'm going over the algorithm now.