1
00:00:00,650 --> 00:00:02,020
Let's conclude and

2
00:00:02,020 --> 00:00:05,570
kind of create an overview of what
can be learned about decision trees.

3
00:00:05,570 --> 00:00:09,580
Decision trees are really the single
most popular datamining or

4
00:00:09,580 --> 00:00:10,840
machine learning tool.

5
00:00:10,840 --> 00:00:14,080
The reason why decision trees are so,
so popular is the following.

6
00:00:14,080 --> 00:00:18,590
First, it is very easy to understand
the structure of the decision tree, right?

7
00:00:18,590 --> 00:00:22,040
It's even, in a sense,
easy to explain to someone, why did we,

8
00:00:22,040 --> 00:00:24,330
why the tree made a given decision, right.

9
00:00:24,330 --> 00:00:26,190
We can show them a series of speeds and

10
00:00:26,190 --> 00:00:30,650
say, because of these conditions, this is
the classification that has been made.

11
00:00:30,650 --> 00:00:34,890
Decision trees are also very easy to
implement, both at the training stage,

12
00:00:34,890 --> 00:00:39,322
is not that complicated, and also once we
have the tree it's very easy to use it,

13
00:00:39,322 --> 00:00:41,080
for classification.

14
00:00:41,080 --> 00:00:43,980
So, trees are also easy to use.

15
00:00:43,980 --> 00:00:48,266
Another thing that is important is [SOUND]
that they are computationally also very

16
00:00:48,266 --> 00:00:50,860
cheap, in a sense that
classification is easy.

17
00:00:50,860 --> 00:00:55,510
One caveat with, decision trees is
that it's very easy to overfit.

18
00:00:55,510 --> 00:00:59,860
So it's very easy to create complicated
trees that, that are very deep and

19
00:00:59,860 --> 00:01:04,140
become too intricate and don't
generalize well to unseen data set, and

20
00:01:04,140 --> 00:01:07,850
what is also nice about decision trees
is that they can do both classification,

21
00:01:07,850 --> 00:01:08,970
as well as regression.

22
00:01:08,970 --> 00:01:15,000
So, decision trees have many good,
the, ex, eg, properties.

23
00:01:15,000 --> 00:01:17,950
Another thing that decision
trees are very useful for,

24
00:01:17,950 --> 00:01:20,620
is what is called learning ensembles,
right?

25
00:01:20,620 --> 00:01:25,640
Many times it turns out that it is better
to build multiple decision trees, latch,

26
00:01:25,640 --> 00:01:30,730
let each of the individual decision trees,
create its own prediction, and then, for

27
00:01:30,730 --> 00:01:33,770
example, use these predictions as votes,
or

28
00:01:33,770 --> 00:01:36,590
you average them together,
to make the final prediction.

29
00:01:36,590 --> 00:01:40,670
So, this is what it means, that you
learn an ensemble of decision trees, and

30
00:01:40,670 --> 00:01:45,420
then you kind of take, take the individual
predictions, average them up or

31
00:01:45,420 --> 00:01:48,110
somehow aggregate them,
to make the final prediction.

32
00:01:48,110 --> 00:01:52,520
So one method that,
that does this, is called bagging.

33
00:01:52,520 --> 00:01:57,070
The idea here is that we want to learn
multiple trees over independent samples of

34
00:01:57,070 --> 00:02:00,230
the training data, and
then prediction from each tree,

35
00:02:01,310 --> 00:02:05,590
is considered to be average predictions
from all the trees that we have, and

36
00:02:05,590 --> 00:02:07,400
make the final prediction.

37
00:02:07,400 --> 00:02:11,530
It turns out that in practice this kind
of bagging approaches work much better,

38
00:02:11,530 --> 00:02:15,340
especially if the classification or
the prediction task is very hard.

39
00:02:15,340 --> 00:02:17,680
So, the idea is very simple, right?

40
00:02:17,680 --> 00:02:20,920
We will have our, initial data set,

41
00:02:20,920 --> 00:02:25,830
we will create,
many random samples out of it.

42
00:02:25,830 --> 00:02:30,790
right, let's call them D star 1,
D star 2, this can simply be.

43
00:02:30,790 --> 00:02:33,540
When we are sampling from D,
we did a replacement.

44
00:02:33,540 --> 00:02:37,240
This will give us a new set of,
training data sets, and for

45
00:02:37,240 --> 00:02:42,004
each of these, we'll then train
a separate tree, tree 1, tree 2,

46
00:02:42,004 --> 00:02:45,990
tree 3, and
then when a new example x comes in,

47
00:02:45,990 --> 00:02:51,250
we, we make each of the trees to,
to give a, to give a prediction.

48
00:02:51,250 --> 00:02:54,310
And, and then we take the,
let's say the majority vote or

49
00:02:54,310 --> 00:02:58,600
the average, to come out,
with a final prediction.

50
00:02:58,600 --> 00:03:01,950
So that is basically this,
the whole idea of bagging.

51
00:03:01,950 --> 00:03:05,460
There are a few interesting things
how we could, how we could use

52
00:03:05,460 --> 00:03:09,510
our PLANET infrastructure that we,
that we just talked about to do bagging.

53
00:03:09,510 --> 00:03:11,320
So let's look at this.

54
00:03:11,320 --> 00:03:16,030
The idea is that here, right the tree
induction be, be, begin at the root, and

55
00:03:16,030 --> 00:03:21,740
that all, all the trees are of the bagged
are pushed into MapReduce queue and

56
00:03:21,740 --> 00:03:26,010
then all the controller kind of has to
do is to do the tree induction over,

57
00:03:26,010 --> 00:03:29,170
over a given, dataset of samples, right.

58
00:03:29,170 --> 00:03:32,650
One thing that we need to discuss when
the data said this star is very huge,

59
00:03:32,650 --> 00:03:34,930
how do we create subsamples of it?

60
00:03:34,930 --> 00:03:38,030
Here basically the idea is to use,
hashing.

61
00:03:38,030 --> 00:03:40,570
Right?
So the idea is that I can take training

62
00:03:40,570 --> 00:03:45,940
records, and I can, use hashing,
I can use multiple hash functions.

63
00:03:45,940 --> 00:03:51,900
And for every hash function, I, this
creates me a separate, different subsets,

64
00:03:51,900 --> 00:03:56,880
of data, where the idea is that the
records of hash into a particular range,

65
00:03:56,880 --> 00:03:59,010
we use them to learn the tree.

66
00:03:59,010 --> 00:04:01,610
right?
This means that this way the sample,

67
00:04:01,610 --> 00:04:05,410
the same sample, is used for
all nodes in a given tree.

68
00:04:05,410 --> 00:04:10,140
And, no, the way I define right now is
that this is sampling without replacement.

69
00:04:10,140 --> 00:04:14,400
What we, what we want to do in bagging
is to use sampling with replacement.

70
00:04:14,400 --> 00:04:18,890
So, the way we can do this is by using,
multiple hash functions.

71
00:04:20,120 --> 00:04:24,780
To contin, to end our discussion of
decision trees and of the machine learning

72
00:04:24,780 --> 00:04:31,430
topics, I want to also briefly compare the
support vector machines and decision trees

73
00:04:31,430 --> 00:04:36,850
in which of these two methods should,
methods should be used in a given case.

74
00:04:36,850 --> 00:04:39,760
So support vector machines
are generally used for

75
00:04:39,760 --> 00:04:44,670
classification, meaning, usually, binary
classification is the most common case.

76
00:04:44,670 --> 00:04:47,700
They are used for real value,
valued features, right,

77
00:04:47,700 --> 00:04:51,470
because we think about the decision
boundary in this Euclidean space.

78
00:04:51,470 --> 00:04:53,400
So they are not, for example, used for,

79
00:04:53,400 --> 00:04:58,710
for categorical features like, colors,
or, weather types or something, right?

80
00:04:58,710 --> 00:05:01,740
SVMs are also very good
when we have hundreds, or

81
00:05:01,740 --> 00:05:03,650
hundreds of thousands of features, right?

82
00:05:03,650 --> 00:05:05,150
When you have lots and lots of features.

83
00:05:05,150 --> 00:05:08,930
So, for example, for text,
the the SVMs are really great.

84
00:05:08,930 --> 00:05:12,770
They also work really well when we have
sparse feature sets, what this means is

85
00:05:12,770 --> 00:05:17,205
that, most of our feature vector or
most of ours features take value 0.

86
00:05:18,480 --> 00:05:22,700
And, what is nice about SVMs is, that they
have a very simple decision boundary.

87
00:05:22,700 --> 00:05:26,000
The, what we talked about is
a simple linear decision boundary,

88
00:05:26,000 --> 00:05:28,990
which means, it's very hard to overfit.

89
00:05:28,990 --> 00:05:31,120
So, example applications for

90
00:05:31,120 --> 00:05:35,050
support vector machines are like text
classifications, spam detection, exa,

91
00:05:35,050 --> 00:05:41,380
cases in computer vision when, where
we are doing, classification and so on.

92
00:05:41,380 --> 00:05:44,230
On the other hand, decision trees are for

93
00:05:44,230 --> 00:05:49,650
much in some sense more, comp, building
much more complicated decision boundaries.

94
00:05:49,650 --> 00:05:54,010
So, decision trees, are both used for
regression and classification,

95
00:05:55,520 --> 00:05:59,806
having up to let's say ten different
classes if we talk about classification.

96
00:05:59,806 --> 00:06:03,856
Decision trees can handle both real
valued and categorical feature,

97
00:06:03,856 --> 00:06:07,968
the most serious limitation of decision
trees is that they can handle,

98
00:06:07,968 --> 00:06:11,848
only hundreds of features, right,
and only dense features, right?

99
00:06:11,848 --> 00:06:16,213
So, when we think about decision trees,
we think that maybe we have ten, or 20, or

100
00:06:16,213 --> 00:06:18,095
100 different features, and for

101
00:06:18,095 --> 00:06:22,142
every training example all these
features are, are filled in, right?

102
00:06:22,142 --> 00:06:26,881
And SVM,s sorry,
decision trees allow us to come up with,

103
00:06:26,881 --> 00:06:30,810
complicated decision boundaries,
this is good.

104
00:06:30,810 --> 00:06:34,650
On the other hand, we have to be
very careful because otherwise,

105
00:06:34,650 --> 00:06:38,755
we will overfit to the data, and so we
need to do what is called early stopping.

106
00:06:38,755 --> 00:06:42,750
Are, some applications for
decision trees, will for

107
00:06:42,750 --> 00:06:47,386
example be using will be user profile,
classification, where you can have user,

108
00:06:47,386 --> 00:06:49,920
we describe each user with a small
set of features, and now we,

109
00:06:49,920 --> 00:06:54,290
we would ex, want to classify these
users maybe as fraudulent, or not, and

110
00:06:54,290 --> 00:07:00,080
this would be an example for
application for decision trees.

111
00:07:00,080 --> 00:07:01,190
Another application would be, for

112
00:07:01,190 --> 00:07:05,470
example, predicting the, what is called on
the web, page bounce prediction, right?

113
00:07:05,470 --> 00:07:08,110
Whether a person land,
coming to a given page,

114
00:07:08,110 --> 00:07:12,740
are they just going to leave the page or
are they going to make the next, click.

115
00:07:12,740 --> 00:07:16,736
In this case again, we could describe
every person with a small feature vector,

116
00:07:16,736 --> 00:07:18,397
and, make the prediction.