I want to introduce a new kind of a hypothesis space,

namely the hypothesis space of decision lists.

Decision lists are just like decision trees,

except that they're trivially branching,

meaning they're extremely unbalanced.

So, you basically have a set of decision nodes,

and they have one, they're binary,

they have one decision branch

where you all directly have a terminal node, yes or no,

and then you have the next one,

and so essentially you basically have lists here,

trees that are essentially lists, hence the name.

To compensate for that,

we actually allow not only literals of attributes in the nodes,

but we allow conjunctions of literals.

Different class of functions,

seems a little bit easier to represent,

maybe that's a good subclass.

Actually, it's easy to convince yourselves

that it's actually not a smaller subclass,

it's not a subclass, it's equivalent to decision trees.

You can think of this as every node here as an or,

because it allows you to go into two directions,

and every node here is a conjunction,

so we have a disjunction of conjunctions,

so that's a disjunctive normal form,

which allows us to do any old Boolean function.

We haven't restricted at all.

But we can actually,

we can now in this format,

we can just say, well,

we're going to restrict the number of conjunctions

to get a restricted case.

In the limit, we're getting everything,

but we have these small sets here.

We have a sublanguage.

Let's just define a little bit of vocabulary.

We're going to define a set KDL,

which is the decision lists of size K,

where we say K is the number of conjunctions in them,

allowed in them, so that's KDL.

And of course, this list here is in 2DL,

because we have one of those here having two conjuncts.

And there's 3DL, 17DL, and so on,

they get fatter and fatter.

And then we observe, of course,

that KDL contains the analogous KDT,

which is the decision trees that have depth K.

And you can see how you would do that, right?

Because you can always pull back every branch here of the KDT