>> So, we saw before when we looked at AND and
OR versus XOR that in the case of AND and OR
we only needed two nodes but in the case of XOR
we needed three. The difference between two and three is not that
big, but it actually does turn out to be big if
you start thinking about having more than simply two attributes. So, let's
look at generalized versions of OR and generalized versions of XOR
and see if we can see how the size of the decision
tree grows differently. So in the case of an n version of OR. That is we have n
attributes as opposed to just two. We might call
that the any function. That is a function were any
of the variables are true then the output is
true. We can see that the decision tree for that
has a very particular and kind of interesting form.
Any ideas Michael about what that decision tree looks like?
>> So, well. So going off of the way you described
OR in the two case. We can start with that. And you.
You pick Pick one of the variables. And if its true
then yeah. Any of them is true since the leaf is true.
>> What happens if its false?
>> Well, then we have to check what everything that's left. [LAUGH]
So then we move on to one of the other attributes like A2.
>> mm hm.
>> And again, if it's
true, it's true and if it's false then we don't know.
>> Look at A3.
>> Good idea.
This could take some time.
>> Yes, oh that was actually an interesting point. Let's
say if there were only three, we would be done. Right?
>> Right.
>> But wait, what if there were five?
>> Then we need one more node.
>> What if there were n?
>> Then we need n minus 4 more nodes.
>> Right, so what you end up with in
this case is a nice little structure around the
decision tree. And how many nodes do we need?
>> Looks like one for each attribute, so that would be n.
>> n nodes, exactly right. So we have a term for this
sort of thing, the size of the decision tree is, in fact, linear.
In n. And that's for any. Now what about an n version of XOR?
>> Mm. So XOR is, if one is true but the other one's not true then it's true.
And if they're both true. Yeah I don't. It's
not clear headed. Generalize that. So why not hmm.
>> So, while the usual general version of this we like
to think of as parity. All parity is a way of counting,
so there's usual two forms of parity that we worry about. Either
even parity or odd parity. So let's pick one, it doesn't matter.
Let's say.
>> Odd.
>> I like that, we'll do odd parity. And all that
works out to be in this case is, if the number
of attributes that are true is an odd number, then the
output of the function is true, otherwise it's false. Got it?
>> Got it.
>> Okay, so, how would we make that decision tree work?
>> Ooh. Well, we got to split on something and there all the same, so let's
split on A1 again.
>> Okay.
So what do we do if A1 is true, versus being false.
>> We don't know much if A1 is true. We have to look at everybody else.
>> Right. So let's look at A2. What if A2 is true versus false?
>> Well if A1 and A2 are true then, then the output is going to be
whatever the parity of all the remaining variables
are. So you still have to do that.
>> Uh-huh, yup. And I'm already running out of room,
so let's pretend there's only three variables. What's the output?
>> [LAUGH] All right, so the far left. Is there's
three trues which is odd so the output is true.
>> Yep.
>> The next leaf over, only two trues. A1 is true, A2 is true,
but A3 is false, so that's two trues which is is even so the answer's false.
>> Um-huh.
>> Is this going to, is this pattern
continuing? Now we've got. No, so then it's
false again because we've got two trues and a false to get to the next leaf.
>> Mm-hm.
>> And we've got one true to get to the
next leaf so that's true. Oh, that looks like XOR.
>> It looks just like XOR. In fact, each
one of these sub trees is kind of a version
of XOR isn't it? Now what we have is, we have to do the same thing on the right.
So we gotta redo A2, and we're going to be in the same
situation before. And we're going to start drawing on top of each other because.
>> [LAUGH]
>> there's just not enough room. Hm, so, what's the answer to the one
on the very right. Where all of them is false. All of them are false.
>> So that's, an even number of trues. Zero is even. So that's false.
Okay, so in the case where only A3 is true, it's true and
we just keep going on and on and on again. Now imagine what would happen, in
fact let me ask you Michael, what would
happen if we had four attributes instead of three.
>> Then we would be really tired of this game.
>> Yes, and I am already tired of this game so the question is, can you.
>> We get a whole another, a whole other level of this tree.
>> Yep. We have the, it just goes on and on and on and nobody
wants to think about it anymore. [LAUGH] So,
how many nodes do you think there are?
>> Well, for three there was one,
two, three, four, five, six, seven. Which seems
suspiciously like one less than the power of two.
>> Mm-hm. And that is exactly right. You need
more or less 2 to the n nodes. Or.
>> 2 to the n, maybe, minus 1.
>> Yeah. So let's just say big O of 2 to the n. Everyone watching this is a
computer scientist to they know what they're doing. Okay
so, you need an exponential therefore, as opposed to linear
number of nodes.
>> Gad.
>> Yeah, so you very, very quickly run
out of room here. You very, very quickly
have a really, really big tree because it's
growing exponentially. So, XOR is an exponential problem and
is also known as hard. Whereas OR, at
least in terms of space that you need, it's
a relatively easy one. This is linear. We
have another name for exponential and that is evil.
Evil, evil, evil. And it's evil because it's a very
difficult problem. There is no clever way to pick the right
attributes in order to give you an answer. You have to
look at every single thing. That's what make this kind of
problem difficult. So, just as a general point, Michael, I
want to make, is that we hope that in our machine
learning problems we're looking at things that are more like any
than we are looking at things that are more like parity.
Because otherwise, we're going to need to ask a lot of questions in order to
answer the, the parity questions. And we can't
be particularly clever about how we do it.
>> Though, if we were kind of clever and added another attribute,
which is like, the sum of all the other attribute values, that
would make it not so bad again. So maybe it's just a,
it's just a kind of, bad way of writing the problem down.
>> Well, you know, what they say about AI
is that the hardest problem is coming up with
a good representation. So what you just did
is, you came up with a better representation,
where you created some new pair, new variable.
Let's call it B, which is just the sum
of all of the As, where we pretend that I don't know,
true is one and false is zero. This is actually a really good
idea. It's also called cheating. [LAUGH] Because you [LAUGH] got to solve the
problem by picking the best representation in the first place. But you know
what? It's a good point, that in order for a machine running
to work, you either need an easy problem or you need to find
a clever way of cheating. So, let's come back and think about that
throughout all the rest of the lessons. What's the best way to cheat?