AI Village - Calculating Drift, Fast with Goko
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Cattell, Sven (comathematician)
Normally concept or dataset drift is unquantifiable in practice. The only ways to calculate it are with optimal transport techniques that take O(n^4). The proxies some ML practitioners use are unreliable when applied to security. This talk presents a way to calculate a concept drift number that takes O(log n). It is faster than most inference, so can be put inline in an ML pipeline. Also, as the structure used to calculate the drift is so cheap we can apply it per-user as an extremely effective defense against attacks.
 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 I welcome everyone to my talk on calculating concepts very quickly with this library called Google which is based on coverings I hear no audio I hear no audio oopsie-daisy um there's no do you hear audio from the top okay well that's the problem I'm trying to sorry about this guys sorry I don't know what's going on okay I am up, I'll apologize. Key takeaway for this talk is this is a novel way of calculating drift. It is done using new techniques using cover trees. Because it is so fast, it is log n. So, this is what we call the Key Takeaway for this talk. This is a novel way of calculating drift. It is done using new techniques using cover trees. And because it's so fast, it's log n time to actually calculate a drift for a new sample, we can use it for on in new ways that the concept drift couldn't have been applied before now. We're going to go with 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 of 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 changes the way the malware data is distributed slightly. Another problem, well what those do basically, which gets into the second problem, is 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 models view of the world at a certain day and then we're view training it and we're testing it on essentially future data. So it doesn't have a perspective for the, you know, if it's trained in March, it doesn't have its perspective, 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 virus data labels and I don't think anyone really should trust virus data labels and that's the best way we have because of the sheer volume of data we have to try to trust virus data labels. For other things, I wouldn't trust early labels on data because we have to move very quickly and sometimes with whiteness and stuff 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 in 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 so that 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 spam 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 could get ahead of those things beforehand. So here's a trivial example. So we have these two data sets and one is our training data set. So we've got one, one, two, one, one and so our training data set has 70% ones, 20% twos and 10% threes. And this is what we train 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, two, two, one, two, so on and when we actually deploy it we see data coming over the wire. We have 30% one, 60% twos and 10% threes. That's a little bit different from our training set. So the real world is different from our training set. So in this case we can model this distribution very easily because it's a discrete space. There are only three things that our data could be. 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 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 Kublack lecture 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 0.7 times log of 0.7 over 0.3. So that's the category for ones. Over the categories of ones take the log and then multiply it for the category for ones. And that gives you the first term. The second term is the same thing for twos and the third term is the same thing for threes. And then you add those all up and you get the kale 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 nice sphere. And they're both, they're 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. And 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 is, it's right next to some orange points so this looks like it could be from the same 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 and then I'm out of distribution. If you tell here, that's not going to tell you much. If I go here, well I've got some outliers here now so maybe that will work now. If I go here, well this is really distributed so 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 this all, what I've described to you is kind of a feeling and actually get it 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. 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, there is K-means trees a whole bunch. And the cover tree has this wonderful thing where in 2016 Mario Maggiani and Wending Lao proved that it can arbitrarily well approximate the underlying distribution of the data. There's some caveats to that statement and mathematically to probably statement we'll take the whole page but basically the core 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 up. 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 M but we want to divide and conquer so it takes log of M. 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 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. Now I divide and conquer their stuff and I can kind of tell that each of their children have four and if I 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 got a nice shape, square shape and so there's four children and the reason 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 like conforming to your data nicely and like at every single step of the way I can make some inferences about what the shape of my data is that are 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 a parent node and I have to go to one of its children. So I always have a discrete choice of where to go. So how does that apply? So here is a very simple coverage and I've colored it by the total population of this node. 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. You can see that the 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 choice, it doesn't help me make the choices at all the 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 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. This is basically a point one probability of taking this path and this is a point nine probability of taking this path. Once I get to this node I have a probability of one of going straight down because I have no other choices. Every single point I have a discrete distribution like we had on page one which tells me where I'm going. Because my tree is geometrically motivated, these choices which are all discrete and easy to compute and easy to count and easy to track off, now I can compute the K-L divergence because it's trivial. It's just counting and taking logs and summing things up. So this is my prior distribution. As I said we're going to use some Bayesian statistics. So here is my prior. This is built of 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 be long in this tree. So if it was already 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 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 travel list distribution and get a posterior one that includes the new information that I got. There is a new point over here. And now I can do that again with another point. Oh yep cool. I have a posterior, a distant point that'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 Kale 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 have included all my training set this is a probability of like 0.4 and this is a probability of 0.6 and this is a probability of 0.4. And there's a very different and I can plug those into the Kale divergence thing and get a positive number for the Kale divergence at this node and then I can do it for this node and this node and this node and get all the Kale divergences and add them up. And then I can get the total Kale 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 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 sample that was centered 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 1s so it's actually quite 20 dimensional. This is actually harder than most data sets because MNIST is about 10 dimensional if you really get down to it. 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 Kale 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 you. 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 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 N, sorry, Vashistine takes big O of N to the fourth. Vashistine is the only other drift calculator that I'm really, no, 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 Vashistine is the traditional way of doing Vashistine requires a relatively equal sized 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. And this one, honestly, it's online. You can do the test that 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 open source, Ember malware data set. You build a reasonable couple of 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 distribute, 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 on to drift. So here's the test set attack. So this was originally categorized by Ian Goodfellow. And there's some defenses have been proposed by Nicholas Carlini and others. So but here's the just of the attack. Normal users just query. They don't care about whether they got a false positive or false negative. They just keep querying. And for us, we think of a normal user as being like an enterprise user trying to fit in and figure out whether all the reports coming over the wire of like new binaries are malicious or benign or they'd be submitting every single binary that they see on their network to a service or 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 it's actually malicious and bypasses our model and then we can and then they deploy it as far as much as possible. So if you apply this to 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 kale 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 misclassified sample and then when they find one, there's an exploration phase. And the kale divergence rises rapidly. You can see that also that this is in log scale, so this is literally hundreds of times more kale divergence than the benign samples. And here, it's the same thing, hundreds of times more kale divergence than the benign and the attacker is around successful. Because of this, 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 denoise. There's also some interesting waking functions you can do inside the tree because there will be some noise from like an overactive leaf node might end up just building a very high kale divergence for that 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. It's honestly the fastest of its kind that I can see in the world. And that's basically it for Gokul's ability to detect test set attacks and other drift things. The library is at elastic.com, 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, oh too on the nose, 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.
 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 I welcome everyone to my  talk on calculating concepts very quickly with this library called  Google which is based on coverings I hear no audio I hear no audio  oopsie-daisy  um there's no do you hear audio from the top  okay well that's the problem I'm trying to  sorry about this guys  sorry I don't know what's going on  okay  I am up, I'll apologize.  Key takeaway for this talk is this is a novel way of calculating drift.  It is done using new techniques using cover trees.  Because it is so fast, it is log n.  So, this is what we call the Key Takeaway for this talk.  This is a novel way of calculating drift.  It is done using new techniques using cover trees.  And because it's so fast, it's log n time to actually calculate a drift for a new sample,  we can use it for on in new ways that the concept drift couldn't have been applied before  now.  We're going to go with 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 of 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 changes the way the malware data is  distributed slightly.  Another problem, well what those do basically, which gets into the second problem, is 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 models view of the world at  a certain day and then we're view training it and we're testing it on essentially future  data.  So it doesn't have a perspective for the, you know, if it's trained in March, it doesn't  have its perspective, 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 virus data labels and I don't think anyone really should  trust virus data labels and that's the best way we have because of the sheer volume of  data we have to try to trust virus data labels.  For other things, I wouldn't trust early labels on data because we have to move very quickly  and sometimes with whiteness and stuff 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 in 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 so that 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 spam 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 could get ahead of those things beforehand.  So here's a trivial example.  So we have these two data sets and one is our training data set.  So we've got one, one, two, one, one and so our training data set has 70% ones, 20%  twos and 10% threes.  And this is what we train 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, two, two, one, two,  so on and when we actually deploy it we see data coming over the wire.  We have 30% one, 60% twos and 10% threes.  That's a little bit different from our training set.  So the real world is different from our training set.  So in this case we can model this distribution very easily because it's a discrete space.  There are only three things that our data could be.  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 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 Kublack lecture  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  0.7 times log of 0.7 over 0.3.  So that's the category for ones.  Over the categories of ones take the log and then multiply it for the category for  ones.  And that gives you the first term.  The second term is the same thing for twos and the third term is the same thing for threes.  And then you add those all up and you get the kale 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 nice sphere.  And they're both, they're 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.  And 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 is, it's right next to some orange  points so this looks like it could be from the same 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 and then I'm out  of distribution.  If you tell here, that's not going to tell you much.  If I go here, well I've got some outliers here now so maybe that will work now.  If I go here, well this is really distributed so 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 this all, what I've described to you is kind of a feeling and actually get  it 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.  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, there is K-means trees a whole bunch.  And the cover tree has this wonderful thing where in 2016 Mario Maggiani and Wending Lao  proved that it can arbitrarily well approximate the underlying distribution of the data.  There's some caveats to that statement and mathematically to probably statement we'll  take the whole page but basically the core 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 up.  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 M but we want to divide and conquer so it  takes log of M. 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 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.  Now I divide and conquer their stuff and I can kind of tell that each of their children  have four and if I 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 got a nice shape, square shape and so there's four children and the reason  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 like conforming to your data nicely and like at every single step of the way I can  make some inferences about what the shape of my data is that are 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 a parent node and I have to go to one of its children.  So I always have a discrete choice of where to go.  So how does that apply?  So here is a very simple coverage and I've colored it by the total population of this  node.  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.  You can see that the 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 choice, it doesn't help me make the choices at all the 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 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.  This is basically a point one probability of taking this path and this is a point nine  probability of taking this path.  Once I get to this node I have a probability of one of going straight down because I have  no other choices.  Every single point I have a discrete distribution like we had on page one which tells me where  I'm going.  Because my tree is geometrically motivated, these choices which are all discrete and  easy to compute and easy to count and easy to track off, now I can compute the K-L divergence  because it's trivial.  It's just counting and taking logs and summing things up.  So this is my prior distribution.  As I said we're going to use some Bayesian statistics.  So here is my prior.  This is built of 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  be long in this tree.  So if it was already 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 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 travel list distribution  and get a posterior one that includes the new information that I got.  There is a new point over here.  And now I can do that again with another point.  Oh yep cool.  I have a posterior, a distant point that'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 Kale 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 have included all my training set this is a probability of like  0.4 and this is a probability of 0.6 and this is a probability of 0.4.  And there's a very different and I can plug those into the Kale divergence thing and get  a positive number for the Kale divergence at this node and then I can do it for this  node and this node and this node and get all the Kale divergences and add them up.  And then I can get the total Kale 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  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 sample that was centered 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 1s so it's actually quite 20 dimensional.  This is actually harder than most data sets because MNIST is about 10 dimensional if you  really get down to it.  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 Kale 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 you.  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 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 N, sorry, Vashistine takes big O of N to the fourth.  Vashistine is the only other drift calculator that I'm really, no, 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 Vashistine is the traditional way of  doing Vashistine requires a relatively equal sized 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.  And this one, honestly, it's online.  You can do the test that 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 open source, Ember malware data set.  You build a reasonable couple of 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 distribute, 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 on to drift.  So here's the test set attack.  So this was originally categorized by Ian Goodfellow.  And there's some defenses have been proposed by Nicholas Carlini and others.  So but here's the just of the attack.  Normal users just query.  They don't care about whether they got a false positive or false negative.  They just keep querying.  And for us, we think of a normal user as being like an enterprise user trying to fit  in and figure out whether all the reports coming over the wire of like new binaries are malicious  or benign or they'd be submitting every single binary that they see on their network to a  service or 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 it's actually malicious and bypasses our model and then  we can and then they deploy it as far as much as possible.  So if you apply this to 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 kale 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 misclassified sample and then when they find one, there's an exploration phase.  And the kale divergence rises rapidly.  You can see that also that this is in log scale, so this is literally hundreds of times  more kale divergence than the benign samples.  And here, it's the same thing, hundreds of times more kale divergence than the benign  and the attacker is around successful.  Because of this, 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 denoise.  There's also some interesting waking functions you can do inside the tree because there will  be some noise from like an overactive leaf node might end up just building a very high  kale divergence for that 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.  It's honestly the fastest of its kind that I can see in the world.  And that's basically it for Gokul's ability to detect test set attacks and other drift  things.  The library is at elastic.com, 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, oh too on the nose, 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.
DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_0_779.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_780_827.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_828_1259.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_1260_1835.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_1836_1883.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_1884_1931.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_1932_3155.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_3156_3503.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_3504_3551.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_3552_3599.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_3600_4031.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_4032_4763.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_4764_5471.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_5472_5891.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_5892_6719.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_6720_6767.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_6768_10883.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_10884_12935.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_12936_14291.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_14292_15395.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_15396_15587.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_15588_16019.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_16020_17123.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_17124_17231.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_17232_19619.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_19620_20495.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_20496_20795.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_20796_21059.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_21060_21203.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_21204_22043.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_22044_22667.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_22668_23567.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_23568_28955.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_28956_29843.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_29844_30395.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_30396_33095.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_33096_35435.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_35436_35603.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_35604_37775.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_37776_43043.png DEF_CON_Safe_Mode_AI_Village_-_comathematician_-_H_-F-eCJHSw9s_43044_43052.png