Hello everyone and welcome to our next talk which is mine. 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. So that's enough about me. Let me play my talk back for you.
So, here we go.
I welcome everyone to my talk on calculating concepts very quickly with this library called
Google which is based on... I hear no audio.
Oopsie daisy.
Um, there's no... do you hear audio from the talk?
Okay, well that's the problem I'm trying to...
Uh, sorry about this guys.
Uh, sorry, I don't know what's going on.
Um, I am... I'll apologize.
Key takeaway for this talk is this is a novel way of calculating drift.
Welcome everyone to my talk on calculating concept drift very quickly with this library
called Google which is based on cover trees. My name is Sven Kittel. I am a senior data
scientist at Elastic and my Twitter handle is co-mathematician.
So, the key outline... key takeaway for this talk is this is a novel way of calculating drift.
It's done using a new technique using cover trees.
And because it's so fast, it's log-in time to actually calculate drift for a new sample.
We can use it for on... in new ways that concept drift couldn't have been applied before now.
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.
So, why do we care about data set drifts? Well, our data drifts.
So, I work with malware and there are new malware families coming out every month.
There are new benign pieces, examples of software coming out every month.
Every time that Adobe patches Photoshop, it changes the pattern slightly and it changes
its location slightly in our data set. 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.
Another problem... well, what those do, basically, which gets into the second problem,
they lower the efficacy of our models that we deploy. So, our models expect data in a sort of
the same sort of general location as our training data. 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. 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.
So, one of the methods for dealing with this is you build a dashboard that basically tracks the
error. And when the error gets too high, you discard the model and go on for a new one.
But the problem is, I don't trust VirusTotalLabels, and I don't think anyone really should trust
VirusTotalLabels. And that's the best way we have because of the sheer volume of data
we have to kind of trust VirusTotalLabels. 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.
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? What's going on?
And then additionally, aside from the fact that things are just changing all the time,
our models are also under attack. 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.
They're constantly innovating with a specific goal in mind of bypassing our models.
This may not result be an adversarial example per se from the literature, but it sure
kind of acts like that sometimes. And additionally, we could be under attack via a poisoning system.
Maybe if the detector is fast enough, we can get ahead of those things beforehand.
So here's a trivial example. So we have these two data sets. One is our training data set. That's
we've got 1, 1, 2, 1, 1. And so our training data set has 70% 1s, 20% 2s, and 10% 3s.
And this is what we trained on. Realistically, there's no point in training a machine learning
model on a sequence of numbers, but suppose we do. But then we deploy this model, and we get
this other sequence of data. 2, 2, 1, 2, so on, so on. And when we actually deploy it, we see
data coming over the wire. We have 30% 1s, 60% 2s, and 10% 3s. So that's a little bit different
from our training set. So the real world is different from our training set. So in this case,
this is a... we can model this distribution very easily because it's a discrete space.
There are only three things that our data could be. There's only... it isn't continuous like a lot
of the stuff we have to deal with in data science. So we can actually compute the distribution fairly
easily. And this is a pretty good... we can feel confident in our estimate of the distribution.
We have to do some Bayesian statistics to do this properly,
which we're not getting into this talk. But this is basically how it works. 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. So
this is a sort of a measure of the distance between this distribution and this distribution.
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. So that's the category for 1s over the
1s. Take the log and then multiply it for the category for 1s. And that gives you the first
term. Second term is the same thing for 2s. And the third term is the same thing for 3s.
And then we add those all up and you get the KL divergence between these two distributions is
0.16. So that's all great. But the problem is our data looks like this. And I don't know whether
this has any difference. Are my blue points sampled from the same distribution as my orange
points? I don't know. It's really hard to tell by just looking at this picture.
And now, in this case, they are. So my orange points are sampled from a two-dimensional
Gaussian, two-dimensional normal distribution, where it's just, it's a nice sphere. And they're
both, the covariance matrix is 1, 1. And the covariance matrix with blues is 1, 1. And it
gives you this nice distribution. And it looks okay. Now, what I'm going to do is I'm going to
drift the blues slightly over. And can you tell, is this correct? Well, you know, every single time
that I put a blue, it's right next to some orange points. So this looks like it could be from the
distribution. I can't really tell with my eyes. 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. But if you tell here, that's not going to tell
you much. If I go here, well, oh, I've got some outliers here now. So maybe that will work now.
If I go here, well, this is really distributed. So this center, the center of this distribution
should be around here. And the center for this distribution is around here. So that's really
drifted. But you've got some outliers over here. Now, what happens when there's like millions of
orange points and there's only a few hundred blue points? Well, you might not be able to tell the
difference with that in that case. So, and also like, there's all this, what I've described to
you is kind of a feeling. And to actually get at the math of this thing, I have to like model the
distributions that these came from. And that's quite a hard problem. And especially in high
dimensions. So things get kind of complicated. So the solution to this that I came up with is to
use a cover tree. Now, why do I want to use a cover tree? So the cover tree, basically,
the key takeaway for cover trees is it's a k-nearest neighbors data structure. There are
many like it. There's kd trees, there's b trees, there's kd trees, you know,
there's k-means trees, a whole bunch. 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. There's some caveats to that statement, and mathematically,
it will probably, to properly statement, will take it, take the whole page. 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. And you have to have enough data from that.
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.
There's some caveats, and you can go read their paper if you want on exactly what that means.
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.
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. I can tell
clusters and things. I can infer what clusters are. Let's go build a very simple cover tree
in two-dimensional data. 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.
You know, in this case, it's a circle that covers everything. So, this is the start. And now,
this doesn't help me that much. 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.
So, here's what I do. I shrink my sphere down, add another one, and I cover it again.
You can kind of tell that this object is longer than it is wide. It's kind of,
if you really squint, it's kind of a one-dimensional thing in this direction.
So, that's great. 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. So, here's their children.
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.
At the scale, the top scale, it was too blurry. I could only see a line here. 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. 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, and at every single step of the way, I can make some inferences about
what the shape of my data is. They're very cheap, because it's basically counting.
So how do we build a probability distribution? 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, but I will be at a parent node,
and I have to go to one of its children. So I always have discrete choices, a discrete choice
of where to go. So how does that apply? So here is a very, like, simple cover tree,
and I've colored it by the total, like, the population of this node.
So this color here is the relative population of this node. So about 66% of the data
is underneath this node. About 33% of the data is underneath this node. And you can see that
colors are kind of changing. 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. It doesn't help me make the choices at all steps.
So if I go here, this helps me make my choices. So here, I've got 66% of my data over here, and I've
got 33% of my data over here. And then once I've taken... I have to take one of those two choices.
If I take this choice, I'm now at this node, and I have two choices again. 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. And once I get to this node,
I have a probability of one of going straight down, because I have no other choices.
And every single point, I have a discrete distribution, like we had on page one, which
tells me where I'm going. 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. It's all... it's just counting,
taking logs, and summing things up. So this is my prior distribution. As I said,
we're going to use some Bayesian statistics. And so here is my prior. How... this is built
with my training set. How do I include my test set? 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. So if it was already...
if it was in my training set and didn't get involved in building the tree,
where would have it ended up? So I have a point here. So this is my new point that came over the
wire. 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. So the path for this point goes up this way.
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. And now I can do that again with another point.
Oh yep, cool. I have a posterior... this point's been added, and you can see that the distribution
changes. And then I can add some more points, and I can add some more points. So these are
all my posterior. 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. So this enables me to
sort of quickly make a posterior distribution out of my prior distribution, and everything
is discrete. And then I can take the KL divergence between my posterior discrete distributions and
my prior discrete distributions. So in this case, this one has a probability of 0.33,
and here I have a probability of 0.66. And afterwards, after I've included all my training
set, this is a probability of like 0.4. And this, you know, this is a probability of 0.6,
and this is a probability of 0.4. And those are very different. And I can plug those into the
KL divergence thing and get a positive number for the KL divergence at this node. 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.
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. And so this basically, yeah, does it. 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. And the slide just covers how you do it.
So let's go back to that original test set. 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.
And then I have a small number of points from a test distribution. And in this case, I have
100,000 points from my training distribution and only 500 points from my test distribution.
And these both have a covariance matrix of all ones. So it's actually quite, and it's
20-dimensional. This is actually harder than most datasets. MNIST is about 10-dimensional,
if you really get down to it. If you want to know what that is, you can
contact me on Twitter and ask me why MNIST might be lower dimensional.
And between the training distribution, I build the tree, fix it, and then I make a posterior
distribution for a bunch of test distributions. And I take the KL divergence. And you can see
it's a bit noisy. The reason being is I generate a lot of the exact position of your points. It's
fairly sensitive to these. So this is one of the problems. 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. And I'll get into why I did that afterwards, because honestly,
it came to the drift stuff backwards. But you can see, the further you get, the further you
separate the two distributions, the higher the number gets. So the sanity test, the unit test
of does this work is correct. And I'll have to compare this to other methods.
This takes big O of, sorry, Wasserstein takes big O of N to the fourth.
Wasserstein is the only other drift calculator that I really know
works. And is model independent and doesn't have some funny business with
building an estimated distribution initially. This takes K log N. Another big difference between
Wasserstein is the traditional way of doing Wasserstein requires a relatively equal size
test and training set. You can't have the test set be 0.5% of the training set.
That would just not work so great on the traditional method I know of. And this one,
honestly, it's online. You can do, the test set can be a fraction of the size of the training
set. And because it's online, it can do it in real time. And this is stupidly fast. 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. So that's fast enough that inference
wouldn't be, this would not be the bottleneck. 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.
So we built it so that it can go fast enough to defend. And now here is where the thing originally
came from, and then we backtracked onto Drift. So here's the test set attack. So this was
originally categorized by Ian Goodfellow, and some defenses have been proposed by Nicholas Carlini
and others. So, but here is the gist of the attack. Normal users just query. They don't
care about whether they got a false positive or a false negative, they just keep querying.
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. But a malicious user would be submitting
things with a specific goal in mind. They don't care about what they care deeply what the label
is, and they care deeply about defining a false negative. They want to find a malicious sample
we classify as benign. 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. 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.
And as samples come over the wire, you track it for that user. 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. 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. 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. And the KL divergence rises rapidly. You can see that
that this is in log of scale. So this is literally hundreds of times more KL divergence than the
benign samples. And here, it's the same thing. Hundreds of times more KL divergence than
the benign and the attackers were unsuccessful. Because of this, you can build, you can probably
build a very good online defense of your system against a set attack. 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. But because it's so
bloody fast, it does this really well. And because it's so bloody fast, you can retrofit it.
So here's where I'll talk about some next steps. So as I mentioned previously,
this thing is a bit noisy. There are ways to fix it. 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. There are some tuning systems you can use to really clean up and
de-noise. 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. And there's a couple other little
things like that that still need to be cleaned up before this goes into production. But the
system itself is looking very promising and is honestly the fastest of its kind
that I can see in the world. And that's basically it for Gokul's ability to detect benign test set
and other drift things. The library is at elastic.com, oh sorry, github slash elastic
slash Gokul. It's named after my grandmother because the base algorithm for this thing is
called GRMA. And if you say that while drunk, you can kind of get grandma.
And grandma's a bit too on the nose, so I named it Gokul.
Anyway, well, looking forward to hearing you guys on Twitter
and Twitch and Slack or whatever. So thank you very much and good night.