1
00:00:01,470 --> 00:00:06,270
Hello everyone and welcome to our next talk which is mine.

2
00:00:06,510 --> 00:00:23,670
To introduce myself, which is wrong, I did a postdoc in machine learning after getting my PhD in algebraic topology with some of the people who did some of the math behind the concepts in this talk and I've just extended it for this thing.

3
00:00:23,670 --> 00:00:27,750
So that's enough about me.

4
00:00:28,070 --> 00:00:30,810
Let me play my talk back for you.

5
00:00:32,490 --> 00:00:34,530
So, here we go.

6
00:00:34,530 --> 00:00:42,610
I welcome everyone to my talk on calculating concepts very quickly with this library called Google which is based on... I

7
00:00:59,530 --> 00:01:01,730
hear no audio.

8
00:01:05,790 --> 00:01:06,930
Oopsie daisy.

9
00:01:28,690 --> 00:01:31,430
Um, there's no... do you hear audio from the talk?

10
00:01:38,900 --> 00:01:41,260
Okay, well that's the problem I'm trying to...

11
00:02:02,030 --> 00:02:04,050
Uh, sorry about this guys.

12
00:02:22,810 --> 00:02:27,950
Uh, sorry, I don't know what's going on.

13
00:03:18,250 --> 00:03:23,590
Um, I am... I'll apologize.

14
00:03:34,220 --> 00:03:39,140
Key takeaway for this talk is this is a novel way of calculating drift.

15
00:03:39,980 --> 00:03:47,160
Welcome everyone to my talk on calculating concept drift very quickly with this library called Google which is based on cover trees.

16
00:03:47,260 --> 00:03:48,560
My name is Sven Kittel.

17
00:03:48,560 --> 00:03:53,940
I am a senior data scientist at Elastic and my Twitter handle is co-mathematician.

18
00:03:54,480 --> 00:04:01,660
So, the key outline... key takeaway for this talk is this is a novel way of calculating drift.

19
00:04:01,660 --> 00:04:05,970
It's done using a new technique using cover trees.

20
00:04:06,800 --> 00:04:13,600
And because it's so fast, it's log-in time to actually calculate drift for a new sample.

21
00:04:13,600 --> 00:04:19,460
We can use it for on... in new ways that concept drift couldn't have been applied before now.

22
00:04:19,660 --> 00:04:28,360
So, we're going to go over the objective, why we care about concept drift, mathematically how it's done, then a couple results, and then finishing up with next steps.

23
00:04:28,860 --> 00:04:31,180
So, why do we care about data set drifts?

24
00:04:31,180 --> 00:04:33,780
Well, our data drifts.

25
00:04:35,300 --> 00:04:41,040
So, I work with malware and there are new malware families coming out every month.

26
00:04:41,040 --> 00:04:45,300
There are new benign pieces, examples of software coming out every month.

27
00:04:45,300 --> 00:04:52,140
Every time that Adobe patches Photoshop, it changes the pattern slightly and it changes its location slightly in our data set.

28
00:04:52,300 --> 00:05:00,880
Every single time a new piece of malware comes up, it's a new... it changes the way our... the malware data is distributed slightly.

29
00:05:01,500 --> 00:05:11,060
Another problem... well, what those do, basically, which gets into the second problem, they lower the efficacy of our models that we deploy.

30
00:05:11,700 --> 00:05:18,640
So, our models expect data in a sort of the same sort of general location as our training data.

31
00:05:18,640 --> 00:05:29,640
And every time we deploy, we are kind of fixing our model's view of the world at a certain day, and then we're training it and we're testing it on essentially future data.

32
00:05:29,760 --> 00:05:40,800
So, it doesn't have a perspective for the... if it's trained in March, it doesn't have... it might not work very well at the end... data coming in at the end of April.

33
00:05:41,800 --> 00:05:47,280
So, one of the methods for dealing with this is you build a dashboard that basically tracks the error.

34
00:05:49,020 --> 00:05:53,340
And when the error gets too high, you discard the model and go on for a new one.

35
00:05:53,340 --> 00:05:59,940
But the problem is, I don't trust VirusTotalLabels, and I don't think anyone really should trust VirusTotalLabels.

36
00:05:59,940 --> 00:06:06,000
And that's the best way we have because of the sheer volume of data we have to kind of trust VirusTotalLabels.

37
00:06:06,220 --> 00:06:16,660
So, and for other things, I wouldn't trust early labels on data because we have to move very quickly and sometimes with whitelisting and stuff.

38
00:06:18,380 --> 00:06:28,620
And , you know, well, and sometimes we only get like a label when our customer complains and we'd rather get ahead of that and figure out like, hey, where's the drift happening?

39
00:06:28,680 --> 00:06:29,920
What's going on?

40
00:06:29,920 --> 00:06:36,400
And then additionally, aside from the fact that things are just changing all the time, our models are also under attack.

41
00:06:36,400 --> 00:06:50,920
People are trying to bypass them by doing new and weird things to their data, like packing a spam filter and seeing if that works, or like posting a different pattern to see if that works, to see if they can get past like the Facebook spam filter.

42
00:06:50,920 --> 00:06:56,020
They're constantly innovating with a specific goal in mind of bypassing our models.

43
00:06:56,540 --> 00:07:04,300
This may not result be an adversarial example per se from the literature, but it sure kind of acts like that sometimes.

44
00:07:04,400 --> 00:07:08,500
And additionally, we could be under attack via a poisoning system.

45
00:07:09,420 --> 00:07:14,760
Maybe if the detector is fast enough, we can get ahead of those things beforehand.

46
00:07:15,640 --> 00:07:18,040
So here's a trivial example.

47
00:07:18,680 --> 00:07:20,460
So we have these two data sets.

48
00:07:20,460 --> 00:07:21,760
One is our training data set.

49
00:07:21,760 --> 00:07:24,540
That's we've got 1, 1, 2, 1, 1.

50
00:07:24,540 --> 00:07:29,500
And so our training data set has 70% 1s, 20% 2s, and 10% 3s.

51
00:07:29,900 --> 00:07:32,140
And this is what we trained on.

52
00:07:32,680 --> 00:07:40,040
Realistically, there's no point in training a machine learning model on a sequence of numbers, but suppose we do.

53
00:07:41,080 --> 00:07:44,220
But then we deploy this model, and we get this other sequence of data.

54
00:07:44,220 --> 00:07:46,380
2, 2, 1, 2, so on, so on.

55
00:07:46,520 --> 00:07:50,440
And when we actually deploy it, we see data coming over the wire.

56
00:07:50,440 --> 00:07:53,420
We have 30% 1s, 60% 2s, and 10% 3s.

57
00:07:53,420 --> 00:07:55,400
So that's a little bit different from our training set.

58
00:07:55,400 --> 00:07:59,480
So the real world is different from our training set.

59
00:08:00,000 --> 00:08:06,240
So in this case, this is a... we can model this distribution very easily because it's a discrete space.

60
00:08:06,240 --> 00:08:09,520
There are only three things that our data could be.

61
00:08:09,700 --> 00:08:14,840
There's only... it isn't continuous like a lot of the stuff we have to deal with in data science.

62
00:08:15,040 --> 00:08:18,100
So we can actually compute the distribution fairly easily.

63
00:08:18,100 --> 00:08:22,980
And this is a pretty good... we can feel confident in our estimate of the distribution.

64
00:08:23,180 --> 00:08:29,800
We have to do some Bayesian statistics to do this properly, which we're not getting into this talk.

65
00:08:29,800 --> 00:08:33,880
But this is basically how it works.

66
00:08:34,000 --> 00:08:48,480
And then once we have like a concept of our training distribution, and our real world distribution, or our test distribution, as I'll be calling it today, we can take the Kublai-Klepch divergence.

67
00:08:48,520 --> 00:08:55,930
So this is a sort of a measure of the distance between this distribution and this distribution.

68
00:08:56,200 --> 00:09:08,260
And it's very easy to calculate on this categorical discrete data because it's just going to be, well, 0.7 times log of 0.7 over 0.3.

69
00:09:08,260 --> 00:09:12,040
So that's the category for 1s over the 1s.

70
00:09:12,560 --> 00:09:15,220
Take the log and then multiply it for the category for 1s.

71
00:09:15,220 --> 00:09:16,700
And that gives you the first term.

72
00:09:16,700 --> 00:09:18,740
Second term is the same thing for 2s.

73
00:09:18,740 --> 00:09:21,140
And the third term is the same thing for 3s.

74
00:09:21,240 --> 00:09:27,480
And then we add those all up and you get the KL divergence between these two distributions is 0.16.

75
00:09:28,780 --> 00:09:30,080
So that's all great.

76
00:09:30,080 --> 00:09:32,540
But the problem is our data looks like this.

77
00:09:32,640 --> 00:09:37,580
And I don't know whether this has any difference.

78
00:09:37,580 --> 00:09:43,000
Are my blue points sampled from the same distribution as my orange points?

79
00:09:43,120 --> 00:09:44,680
I don't know.

80
00:09:44,940 --> 00:09:48,020
It's really hard to tell by just looking at this picture.

81
00:09:48,600 --> 00:09:51,140
And now, in this case, they are.

82
00:09:51,140 --> 00:10:01,640
So my orange points are sampled from a two-dimensional Gaussian, two-dimensional normal distribution, where it's just, it's a nice sphere.

83
00:10:01,640 --> 00:10:06,100
And they're both, the covariance matrix is 1, 1.

84
00:10:06,100 --> 00:10:08,000
And the covariance matrix with blues is 1, 1.

85
00:10:08,000 --> 00:10:09,440
And it gives you this nice distribution.

86
00:10:09,440 --> 00:10:11,120
And it looks okay.

87
00:10:11,540 --> 00:10:15,360
Now, what I'm going to do is I'm going to drift the blues slightly over.

88
00:10:15,540 --> 00:10:17,480
And can you tell, is this correct?

89
00:10:17,480 --> 00:10:21,940
Well, you know, every single time that I put a blue, it's right next to some orange points.

90
00:10:21,940 --> 00:10:24,380
So this looks like it could be from the distribution.

91
00:10:25,120 --> 00:10:26,800
I can't really tell with my eyes.

92
00:10:26,800 --> 00:10:36,700
And one of the techniques we might do is like, oh, well, let me take the k-nearest neighbors and see if the distance from my k-nearest neighbors over time goes up, then I'm out of distribution.

93
00:10:36,700 --> 00:10:40,000
But if you tell here, that's not going to tell you much.

94
00:10:40,780 --> 00:10:43,940
If I go here, well, oh, I've got some outliers here now.

95
00:10:43,940 --> 00:10:46,000
So maybe that will work now.

96
00:10:46,060 --> 00:10:48,080
If I go here, well, this is really distributed.

97
00:10:48,080 --> 00:10:51,300
So this center, the center of this distribution should be around here.

98
00:10:51,300 --> 00:10:53,100
And the center for this distribution is around here.

99
00:10:53,100 --> 00:10:54,760
So that's really drifted.

100
00:10:54,760 --> 00:10:56,780
But you've got some outliers over here.

101
00:10:56,780 --> 00:11:02,460
Now, what happens when there's like millions of orange points and there's only a few hundred blue points?

102
00:11:02,460 --> 00:11:05,440
Well, you might not be able to tell the difference with that in that case.

103
00:11:05,860 --> 00:11:11,080
So, and also like, there's all this, what I've described to you is kind of a feeling.

104
00:11:11,080 --> 00:11:15,780
And to actually get at the math of this thing, I have to like model the distributions that these came from.

105
00:11:15,780 --> 00:11:17,620
And that's quite a hard problem.

106
00:11:17,680 --> 00:11:20,160
And especially in high dimensions.

107
00:11:20,160 --> 00:11:22,280
So things get kind of complicated.

108
00:11:22,280 --> 00:11:26,500
So the solution to this that I came up with is to use a cover tree.

109
00:11:26,520 --> 00:11:29,160
Now, why do I want to use a cover tree?

110
00:11:29,640 --> 00:11:36,200
So the cover tree, basically, the key takeaway for cover trees is it's a k-nearest neighbors data structure.

111
00:11:36,200 --> 00:11:37,320
There are many like it.

112
00:11:37,320 --> 00:11:49,700
There's kd trees, there's b trees, there's kd trees, you know, there's k-means trees, a whole bunch.

113
00:11:50,140 --> 00:12:03,820
And, well, the cover tree has this wonderful thing where in 2016, Mario Maggiorni and Wenjing Lau proved that it can arbitrarily well approximate the underlying distribution of the data.

114
00:12:04,560 --> 00:12:10,520
There's some caveats to that statement, and mathematically, it will probably, to properly statement, will take it, take the whole page.

115
00:12:10,520 --> 00:12:18,860
But basically, the whole concept of their proof is for a nice data set, and to know what a nice data set is, you need to know what a low dimensional manifold is.

116
00:12:19,360 --> 00:12:21,600
And you have to have enough data from that.

117
00:12:22,000 --> 00:12:33,260
But for a nice data set, which most of our data sets are pretty nice, sort of, kind of, a cover tree will arbitrarily well approximate the underlying distribution of the data.

118
00:12:34,460 --> 00:12:39,160
There's some caveats, and you can go read their paper if you want on exactly what that means.

119
00:12:39,160 --> 00:12:52,500
But for us, what this means is, if I use a cover tree to build a model of my data for k-nearest neighbors, I can take k-nearest neighbors, or I can just fiddle around with the properties of the cover tree to, like, get information about my data set.

120
00:12:53,420 --> 00:13:01,560
So, I can tell things like the local dimensionality, I can tell things like how things glue together, and I can tell, like, sort of, the shape of my data fairly well.

121
00:13:01,560 --> 00:13:02,980
I can tell clusters and things.

122
00:13:02,980 --> 00:13:05,600
I can infer what clusters are.

123
00:13:05,680 --> 00:13:08,780
Let's go build a very simple cover tree in two-dimensional data.

124
00:13:08,820 --> 00:13:17,900
So, here's a, you know, infinity sign, a bow tie, whatever you want to call it, and I start my cover tree by picking a point at random and then building a sphere.

125
00:13:18,080 --> 00:13:21,340
You know, in this case, it's a circle that covers everything.

126
00:13:21,340 --> 00:13:22,740
So, this is the start.

127
00:13:22,740 --> 00:13:24,540
And now, this doesn't help me that much.

128
00:13:24,540 --> 00:13:38,880
I haven't split up my data geometrically to, like, divide and conquer the k-nearest neighbors structure, because the naive way would take a linear time, big O of n, but we want to divide and conquer, so it takes log of n.

129
00:13:38,880 --> 00:13:40,120
So, here's what I do.

130
00:13:40,120 --> 00:13:43,640
I shrink my sphere down, add another one, and I cover it again.

131
00:13:43,760 --> 00:13:48,480
You can kind of tell that this object is longer than it is wide.

132
00:13:48,500 --> 00:13:53,460
It's kind of, if you really squint, it's kind of a one-dimensional thing in this direction.

133
00:13:55,100 --> 00:13:56,080
So, that's great.

134
00:13:56,080 --> 00:14:08,020
But now, if I go, okay, well, I'm going to split it up further, so really divide and conquer, and I, so I've got these two nodes, and they're both children of the previous node on the previous slide, and I'm going to build their children.

135
00:14:08,260 --> 00:14:10,220
So, here's their children.

136
00:14:10,880 --> 00:14:23,580
So, I divide and conquer their stuff, and I can kind of tell that each of their children have four, and if I, if you squint a little bit, it's kind of square-shaped in this dimension.

137
00:14:23,740 --> 00:14:27,360
At the scale, the top scale, it was too blurry.

138
00:14:27,360 --> 00:14:28,500
I could only see a line here.

139
00:14:28,500 --> 00:14:41,360
At the scale, I can kind of see that it's up in, it's got a nice shape, square shape, and so there's four children, and the reason, you know, that that dimensionality is relevant to the number of children you have.

140
00:14:41,540 --> 00:14:57,980
And then I can go further, and you know, it's got some more, it's kind of split up nicely, and I've got like a one-dimensional object here again, because all these children are kind of one-dimensional-ish, and I can split up some more, and you can see that it's kind of conforming to your data nicely,

141
00:14:57,980 --> 00:15:03,480
and at every single step of the way, I can make some inferences about what the shape of my data is.

142
00:15:03,480 --> 00:15:06,380
They're very cheap, because it's basically counting.

143
00:15:06,980 --> 00:15:10,140
So how do we build a probability distribution?

144
00:15:10,200 --> 00:15:31,460
So on slide two, we built a very simple probability distribution, where I had a discrete space, and now I've got a tree, and essentially, when I have a tree, at every single node, I can either go left, or right, or down, or you know, in this case, my number of children I have is variable,

145
00:15:31,460 --> 00:15:35,320
but I will be at a parent node, and I have to go to one of its children.

146
00:15:35,320 --> 00:15:41,620
So I always have discrete choices, a discrete choice of where to go.

147
00:15:42,320 --> 00:15:43,800
So how does that apply?

148
00:15:44,320 --> 00:15:54,840
So here is a very, like, simple cover tree, and I've colored it by the total, like, the population of this node.

149
00:15:55,900 --> 00:15:59,800
So this color here is the relative population of this node.

150
00:15:59,860 --> 00:16:06,000
So about 66% of the data is underneath this node.

151
00:16:06,500 --> 00:16:10,220
About 33% of the data is underneath this node.

152
00:16:10,220 --> 00:16:12,620
And you can see that colors are kind of changing.

153
00:16:12,620 --> 00:16:19,820
I get a kind of a picture of how dense my data is, but that doesn't help me, because I need to make choices.

154
00:16:19,820 --> 00:16:22,680
It doesn't help me make the choices at all steps.

155
00:16:22,800 --> 00:16:26,500
So if I go here, this helps me make my choices.

156
00:16:27,040 --> 00:16:35,840
So here, I've got 66% of my data over here, and I've got 33% of my data over here.

157
00:16:35,840 --> 00:16:38,840
And then once I've taken... I have to take one of those two choices.

158
00:16:38,840 --> 00:16:44,380
If I take this choice, I'm now at this node, and I have two choices again.

159
00:16:44,380 --> 00:16:57,100
And the relative probability of taking this choice versus this one... Well, this is basically a 0.1 probability of taking this path, and this is a 0.9 probability of taking this path.

160
00:16:57,160 --> 00:17:03,400
And once I get to this node, I have a probability of one of going straight down, because I have no other choices.

161
00:17:03,400 --> 00:17:11,840
And every single point, I have a discrete distribution, like we had on page one, which tells me where I'm going.

162
00:17:11,840 --> 00:17:26,100
And because my tree is geometrically motivated, these choices, which were all discrete and easy to compute, and easy to count, and easy to keep track of, now I can compute the KL divergence, because it's trivial.

163
00:17:26,100 --> 00:17:29,880
It's all... it's just counting, taking logs, and summing things up.

164
00:17:30,960 --> 00:17:33,960
So this is my prior distribution.

165
00:17:33,960 --> 00:17:36,220
As I said, we're going to use some Bayesian statistics.

166
00:17:36,220 --> 00:17:37,920
And so here is my prior.

167
00:17:38,280 --> 00:17:40,500
How... this is built with my training set.

168
00:17:40,500 --> 00:17:43,080
How do I include my test set?

169
00:17:44,120 --> 00:17:51,980
So when I see a piece of data coming over the wire, I can make an inference of where it should belong in this tree.

170
00:17:52,020 --> 00:17:54,200
So if it was already...

171
00:17:54,200 --> 00:17:59,920
if it was in my training set and didn't get involved in building the tree, where would have it ended up?

172
00:18:00,060 --> 00:18:01,760
So I have a point here.

173
00:18:01,760 --> 00:18:04,140
So this is my new point that came over the wire.

174
00:18:04,140 --> 00:18:13,120
And I queried and said, oh well, this point is covered by this parent, and it's covered by that parent, and that parent, and all the way up.

175
00:18:13,180 --> 00:18:17,460
So the path for this point goes up this way.

176
00:18:17,460 --> 00:18:28,480
And now for each of those elements in those paths, I can increment my probabilistic distribution and get a posterior one that involves... that includes the new information that I got, that there's a new point over here.

177
00:18:28,840 --> 00:18:31,320
And now I can do that again with another point.

178
00:18:31,320 --> 00:18:32,420
Oh yep, cool.

179
00:18:32,420 --> 00:18:37,000
I have a posterior... this point's been added, and you can see that the distribution changes.

180
00:18:37,180 --> 00:18:40,320
And then I can add some more points, and I can add some more points.

181
00:18:40,320 --> 00:18:42,500
So these are all my posterior.

182
00:18:42,500 --> 00:18:51,120
And I can update my original thing by taking the path of each of the points and updating all the little discrete distributions that I have.

183
00:18:51,320 --> 00:19:02,600
So this enables me to sort of quickly make a posterior distribution out of my prior distribution, and everything is discrete.

184
00:19:02,600 --> 00:19:10,140
And then I can take the KL divergence between my posterior discrete distributions and my prior discrete distributions.

185
00:19:10,140 --> 00:19:17,800
So in this case, this one has a probability of 0.33, and here I have a probability of 0.66.

186
00:19:17,920 --> 00:19:24,660
And afterwards, after I've included all my training set, this is a probability of like 0.4.

187
00:19:24,660 --> 00:19:29,020
And this, you know, this is a probability of 0.6, and this is a probability of 0.4.

188
00:19:29,020 --> 00:19:30,900
And those are very different.

189
00:19:30,900 --> 00:19:36,280
And I can plug those into the KL divergence thing and get a positive number for the KL divergence at this node.

190
00:19:36,280 --> 00:19:42,220
And then I can do it for this node, and this node, and this node, and get all the KL divergences and add them up.

191
00:19:42,220 --> 00:19:54,680
And then I can get the total KL divergence with respect to my original tree of the posterior distribution with respect to the prior distribution, which is really useful.

192
00:19:54,680 --> 00:19:57,400
And so this basically, yeah, does it.

193
00:19:57,700 --> 00:20:10,220
And the code for doing this enables you to do it very quickly, because it's basically just counting a couple logs and some other statistical equations.

194
00:20:11,060 --> 00:20:15,680
And the slide just covers how you do it.

195
00:20:16,260 --> 00:20:21,480
So let's go back to that original test set.

196
00:20:21,480 --> 00:20:36,280
So I've got basically a blown up version of those slides of the Gaussian distributions where I had them, where a large number of points from my training distribution, which was a single Gaussian sampled at the center of the thing.

197
00:20:36,280 --> 00:20:40,440
And then I have a small number of points from a test distribution.

198
00:20:41,120 --> 00:20:48,300
And in this case, I have 100,000 points from my training distribution and only 500 points from my test distribution.

199
00:20:48,300 --> 00:20:54,340
And these both have a covariance matrix of all ones.

200
00:20:54,340 --> 00:20:57,860
So it's actually quite, and it's 20-dimensional.

201
00:20:57,880 --> 00:21:01,220
This is actually harder than most datasets.

202
00:21:01,680 --> 00:21:05,880
MNIST is about 10-dimensional, if you really get down to it.

203
00:21:05,880 --> 00:21:12,260
If you want to know what that is, you can contact me on Twitter and ask me why MNIST might be lower dimensional.

204
00:21:15,140 --> 00:21:23,780
And between the training distribution, I build the tree, fix it, and then I make a posterior distribution for a bunch of test distributions.

205
00:21:23,800 --> 00:21:26,260
And I take the KL divergence.

206
00:21:26,380 --> 00:21:28,300
And you can see it's a bit noisy.

207
00:21:28,480 --> 00:21:33,540
The reason being is I generate a lot of the exact position of your points.

208
00:21:33,540 --> 00:21:35,200
It's fairly sensitive to these.

209
00:21:35,340 --> 00:21:36,760
So this is one of the problems.

210
00:21:36,760 --> 00:21:45,980
And one of the things I'll talk about at the end is like, there are ways to normalize this and resolve this, because I've designed it for speed, not really for accuracy.

211
00:21:46,140 --> 00:21:51,460
And I'll get into why I did that afterwards, because honestly, it came to the drift stuff backwards.

212
00:21:51,620 --> 00:21:59,040
But you can see, the further you get, the further you separate the two distributions, the higher the number gets.

213
00:21:59,040 --> 00:22:03,200
So the sanity test, the unit test of does this work is correct.

214
00:22:04,860 --> 00:22:07,160
And I'll have to compare this to other methods.

215
00:22:07,860 --> 00:22:12,940
This takes big O of, sorry, Wasserstein takes big O of N to the fourth.

216
00:22:13,440 --> 00:22:19,960
Wasserstein is the only other drift calculator that I really know works.

217
00:22:20,740 --> 00:22:28,240
And is model independent and doesn't have some funny business with building an estimated distribution initially.

218
00:22:29,780 --> 00:22:33,500
This takes K log N.

219
00:22:33,500 --> 00:22:41,020
Another big difference between Wasserstein is the traditional way of doing Wasserstein requires a relatively equal size test and training set.

220
00:22:41,840 --> 00:22:46,160
You can't have the test set be 0.5% of the training set.

221
00:22:46,720 --> 00:22:51,620
That would just not work so great on the traditional method I know of.

222
00:22:51,740 --> 00:22:54,800
And this one, honestly, it's online.

223
00:22:54,800 --> 00:22:58,800
You can do, the test set can be a fraction of the size of the training set.

224
00:22:58,800 --> 00:23:02,240
And because it's online, it can do it in real time.

225
00:23:02,620 --> 00:23:05,360
And this is stupidly fast.

226
00:23:05,360 --> 00:23:18,100
You can track for the Ember open source, Ember malware data set, you build a reasonable couple tree, you can track 16,000 new samples per second on my laptop.

227
00:23:18,500 --> 00:23:24,160
So that's fast enough that inference wouldn't be, this would not be the bottleneck.

228
00:23:24,160 --> 00:23:32,640
Inference would be the bottleneck if you would build a cloud distribution, a cloud model, and put this as a guard in front of that cloud model.

229
00:23:33,820 --> 00:23:37,800
So we built it so that it can go fast enough to defend.

230
00:23:38,660 --> 00:23:44,420
And now here is where the thing originally came from, and then we backtracked onto Drift.

231
00:23:44,480 --> 00:23:46,780
So here's the test set attack.

232
00:23:47,400 --> 00:23:59,740
So this was originally categorized by Ian Goodfellow, and some defenses have been proposed by Nicholas Carlini and others.

233
00:24:01,540 --> 00:24:05,160
So, but here is the gist of the attack.

234
00:24:05,160 --> 00:24:06,720
Normal users just query.

235
00:24:06,720 --> 00:24:10,840
They don't care about whether they got a false positive or a false negative, they just keep querying.

236
00:24:11,820 --> 00:24:36,160
And for us, we think of a normal user as being like an enterprise user, trying to figure out whether all the reports coming over the wire of new binaries are malicious or benign, or they'd be submitting every single binary that they see on their network to a service that will tell them whether it was malicious or benign for an ADV product.

237
00:24:37,600 --> 00:24:43,640
But a malicious user would be submitting things with a specific goal in mind.

238
00:24:43,640 --> 00:24:51,620
They don't care about what they care deeply what the label is, and they care deeply about defining a false negative.

239
00:24:51,620 --> 00:24:54,780
They want to find a malicious sample we classify as benign.

240
00:24:54,780 --> 00:25:09,340
So what they'll do is they'll try a bunch of stuff until they find something that is misclassified as benign and is actually malicious and bypasses our model, and then they deploy it as far as much as possible.

241
00:25:09,700 --> 00:25:20,420
So if you do, if you apply this to, you know, the fast drift calculators to that, you can attach a little drift calculator to each user.

242
00:25:20,560 --> 00:25:25,720
And as samples come over the wire, you track it for that user.

243
00:25:26,440 --> 00:25:35,020
And if the user starts exploiting something, they're going to get a very boring distribution where it's just one point repeated over and over again.

244
00:25:37,420 --> 00:25:47,620
And you spike your distribution, your KL divergence spikes up and then becomes very normal because it's essentially you're tracing the same path over and over and over again.

245
00:25:49,160 --> 00:25:59,040
And you can see that there's an exploration phase where the malicious users try to look for a benign misclassified sample, and when they find one, there's an exploitation phase.

246
00:25:59,040 --> 00:26:01,480
And the KL divergence rises rapidly.

247
00:26:01,480 --> 00:26:06,280
You can see that that this is in log of scale.

248
00:26:06,280 --> 00:26:11,220
So this is literally hundreds of times more KL divergence than the benign samples.

249
00:26:11,220 --> 00:26:13,380
And here, it's the same thing.

250
00:26:13,380 --> 00:26:19,640
Hundreds of times more KL divergence than the benign and the attackers were unsuccessful.

251
00:26:20,780 --> 00:26:30,460
Because of this, you can build, you can probably build a very good online defense of your system against a set attack.

252
00:26:32,900 --> 00:26:46,560
And here's where basically the system was originally built sort of with this mind and other attacks in mind, because I'm more interested in defending my models than calculating drift.

253
00:26:47,340 --> 00:26:50,420
But because it's so bloody fast, it does this really well.

254
00:26:50,420 --> 00:26:53,220
And because it's so bloody fast, you can retrofit it.

255
00:26:53,220 --> 00:26:59,160
So here's where I'll talk about some next steps.

256
00:26:59,180 --> 00:27:02,740
So as I mentioned previously, this thing is a bit noisy.

257
00:27:02,740 --> 00:27:04,500
There are ways to fix it.

258
00:27:04,500 --> 00:27:14,940
In this case, window sizes and some tuning things that I didn't go into in these slides because I've already got 20 minutes.

259
00:27:15,060 --> 00:27:20,940
There are some tuning systems you can use to really clean up and de-noise.

260
00:27:20,940 --> 00:27:39,880
There's also some interesting waking functions you can do inside the tree because there's some noise from an overactive leaf node might end up just building a very high KL divergence for just that one node and it throws everything off.

261
00:27:40,300 --> 00:27:44,980
And there's a couple other little things like that that still need to be cleaned up before this goes into production.

262
00:27:45,000 --> 00:27:54,440
But the system itself is looking very promising and is honestly the fastest of its kind that I can see in the world.

263
00:27:55,900 --> 00:28:09,180
And that's basically it for Gokul's ability to detect benign test set and other drift things.

264
00:28:09,180 --> 00:28:15,540
The library is at elastic.com, oh sorry, github slash elastic slash Gokul.

265
00:28:15,880 --> 00:28:22,180
It's named after my grandmother because the base algorithm for this thing is called GRMA.

266
00:28:22,180 --> 00:28:24,820
And if you say that while drunk, you can kind of get grandma.

267
00:28:25,160 --> 00:28:30,940
And grandma's a bit too on the nose, so I named it Gokul.

268
00:28:32,680 --> 00:28:38,640
Anyway, well, looking forward to hearing you guys on Twitter and Twitch and Slack or whatever.

269
00:28:38,980 --> 00:28:40,980
So thank you very much and good night.