8.10 Anomaly Detection | Anomaly detection algorithm-- [Machine Learning | Andrew Ng]
 Now that you've seen how the Gaussian or the normal distribution works for a single number, we're ready to build our anomaly detection algorithm. Let's dive in. You have a training set X1 through Xm where here each example X has n features. So each example X is a vector with n numbers. In the case of the airplane engine example, we had two features corresponding to the heat and the vibrations. And so each of these XIs would be a two dimensional vector and n would be equal to two. But for many practical applications, n can be much larger and you might do this with dozens or even hundreds of features. Given this training set, what we would like to do is to carry out density estimation. And all that means is we will build a model or estimate the probability for P of X. What's the probability of any given feature vector? And our model for P of X is going to be as follows. X is a feature vector with values X1, X2, and so on down to Xn. And I'm going to model P of X as the probability of X1 times the probability of X2 times the probability of X3 times the probability of Xn for the n features in the feature vectors. If you've taken an advanced class in probability statistics before, you may recognize that this equation corresponds to assuming that the features X1, X2, and so on up to Xm are statistically independent. But it turns out this algorithm often works fine even if the features are not actually statistically independent. But if you don't understand what I just said, don't worry about it. Understanding statistical independence is not needed to fully complete this class and also be able to very effectively use the Nullary Detection algorithm. Now to fill in this equation a little bit more, we are saying that the probability of all the features of this vector features X is the product of P of X1 and P of X2 and so on up through P of Xn. And in order to model the probability of X1, say the heat feature in this example, we're going to have two parameters mu1 and sigma1 or sigma squared 1. And what that means is we're going to estimate the mean of the feature X1 and also the variance of feature X1 and that will be mu1 and sigma1. To model P of X2, X2 is a totally different feature measuring the vibrations of the airplane engine, we're going to have two different parameters which I'm going to write as mu2 sigma2 squared and it turns out this will correspond to the mean or the average of the vibration feature and the variance of the vibration feature and so on. If you have additional features mu3 sigma3 squared up through mu n and sigma n squared. In case you're wondering why we multiply probabilities, maybe here's one example that could build intuition. Suppose for an aircraft engine there's a one-tenth chance that it is really really hot, unusually hot and maybe there is a one in 20 chance that it vibrates really really hot. Then what is the chance that it runs really really hot and vibrates really really hot? We're saying that the chance of that is one-tenth times one over 20 which is one over 200 so it's really really unlikely to get an engine that both runs really hot and vibrates really hot. It's the product of these two probabilities. Or the chance of both of these things happening we're saying is the product of both of these probabilities. A somewhat more compact way to write this equation up here is to say that this is equal to the product from j equals one through n of p of xj with parameters mu j and sigma squared j. And this symbol here is a lot like the summation symbol except that whereas the summation symbol corresponds to addition, this symbol here corresponds to multiplying these terms over here for j equals one through n. So let's put it all together to see how you can build an anomaly detection system. The first step is to choose features xi that you think might be indicative of anomalous examples. Having come up with the features you want to use, you would then fit the parameters mu one through mu n and sigma squared one through sigma squared n for the n features in your data set. As you might guess, the parameter mu j will be just the average of xj of the feature j of all the examples in your training set and sigma squared j will be the average of the square difference between the j feature and the value mu j that you just computed up here on top. And by the way, if you have a vectorized implementation, you can also compute mu as the average of the training examples as follows where here x and mu are both vectors. And so this would be the vectorized way of computing mu one through mu n all at the same time. And by estimating these parameters on your unlabeled training set, you've now computed all the parameters of your model. Finally, when you are given a new example, x test, or I'm just going to write the new example as x here, what you would do is compute p of x and see if it's large or small. So p of x, as you saw on the last slide, is the product from j equals one through n of the probability of the individual features. So p of xj with parameters mu j and sigma squared j. And if you substitute in the formula for this probability, you end up with this expression, one over root two pi sigma j of e to this expression over here. And so xj are the features. This is a j feature of your new example. Mu j and sigma j are numbers or parameters you had computed in the previous step. And if you compute out this formula, you get some number for p of x. And the final step is to see if p of x is less than epsilon. And if it is, then you flag that it is an anomaly. One intuition behind what this algorithm is doing is that it will tend to flag an example as anomalous if one or more of the features are either very large or very small relative to what it has seen in the training set. So for each of the features xj, you're fitting a Gaussian distribution like this. And so if even one of the features of the new example was way out here, say, then p of xj would be very small. And if just one of the terms in this product is very small, then this overall product, we multiply together will tend to be very small and thus p of x will be small. And what anomaly detection is doing in this algorithm is a systematic way of quantifying whether or not this new example x has any features that are unusually large or unusually small. Now, let's take a look at what all this actually means on one example. Here's a data set with features x1 and x2. And you notice that the features x1 take on a much larger range of values than the features x2. If you were to compute the mean of the features x1, you end up with five, which is why mu one is equal to one. And it turns out that for this data set, if you compute sigma one, it will be equal to about two. And if you were to compute mu two, the average of the features on x2, the average is three. And similarly, its variance or standard deviation is much smaller, which is why sigma two is equal to one. So that corresponds to this Gaussian distribution for x1 and this Gaussian distribution for x2. If you were to actually multiply p of x1 and p of x2, then you end up with this 3D surface plot for p of x, where at any point, the height of this is the product of p of x1 times p of x2 for the corresponding values of x1 and x2. And this signifies that values where p of x is higher are more likely, so values near the middle, kind of here, are more likely, whereas values far out here, like values out here, are much less likely, and have much lower chance. Now let me pick two test examples. The first one here, I'm going to write as x test one, and the second one down here as x test two. And let's see which of these two examples the algorithm will flag as anomalous. I'm going to pick the parameter epsilon to be equal to 0.02. And if you were to compute p of x test one, it turns out to be about 0.04. And this is much bigger than epsilon, and so the algorithm will say, this looks okay, doesn't look like an anomaly. Whereas in contrast, if you were to compute p of x for this point down here, corresponding to x1 equals about 8, and x2 equals about 0.5, kind of down here, then p of x test two is 0.0021. So this is much smaller than epsilon, and so the algorithm will flag this as a likely anomaly. So pretty much as you might hope, it decides that x test one looks pretty normal, whereas x test two, which is much further away than anything you see in the training set, looks like it could be an anomaly. So you've seen the process of how to build an anomaly detection system, but how do you choose the parameter epsilon? And how do you know if your anomaly detection system is working well? In the next video, let's dive a little bit more deeply into the process of developing and evaluating the performance of an anomaly detection system. Let's go on to the next video.
[{"start": 0.0, "end": 7.82, "text": " Now that you've seen how the Gaussian or the normal distribution works for a single number,"}, {"start": 7.82, "end": 10.96, "text": " we're ready to build our anomaly detection algorithm."}, {"start": 10.96, "end": 12.56, "text": " Let's dive in."}, {"start": 12.56, "end": 20.96, "text": " You have a training set X1 through Xm where here each example X has n features."}, {"start": 20.96, "end": 24.92, "text": " So each example X is a vector with n numbers."}, {"start": 24.92, "end": 31.880000000000003, "text": " In the case of the airplane engine example, we had two features corresponding to the heat"}, {"start": 31.880000000000003, "end": 33.2, "text": " and the vibrations."}, {"start": 33.2, "end": 38.980000000000004, "text": " And so each of these XIs would be a two dimensional vector and n would be equal to two."}, {"start": 38.980000000000004, "end": 43.160000000000004, "text": " But for many practical applications, n can be much larger and you might do this with"}, {"start": 43.160000000000004, "end": 46.92, "text": " dozens or even hundreds of features."}, {"start": 46.92, "end": 53.120000000000005, "text": " Given this training set, what we would like to do is to carry out density estimation."}, {"start": 53.12, "end": 60.4, "text": " And all that means is we will build a model or estimate the probability for P of X."}, {"start": 60.4, "end": 66.12, "text": " What's the probability of any given feature vector?"}, {"start": 66.12, "end": 71.28, "text": " And our model for P of X is going to be as follows."}, {"start": 71.28, "end": 79.03999999999999, "text": " X is a feature vector with values X1, X2, and so on down to Xn."}, {"start": 79.04, "end": 87.76, "text": " And I'm going to model P of X as the probability of X1 times the probability of X2 times the"}, {"start": 87.76, "end": 98.2, "text": " probability of X3 times the probability of Xn for the n features in the feature vectors."}, {"start": 98.2, "end": 103.52000000000001, "text": " If you've taken an advanced class in probability statistics before, you may recognize that"}, {"start": 103.52, "end": 110.8, "text": " this equation corresponds to assuming that the features X1, X2, and so on up to Xm are"}, {"start": 110.8, "end": 113.52, "text": " statistically independent."}, {"start": 113.52, "end": 117.8, "text": " But it turns out this algorithm often works fine even if the features are not actually"}, {"start": 117.8, "end": 120.52, "text": " statistically independent."}, {"start": 120.52, "end": 124.19999999999999, "text": " But if you don't understand what I just said, don't worry about it."}, {"start": 124.19999999999999, "end": 129.42, "text": " Understanding statistical independence is not needed to fully complete this class and"}, {"start": 129.42, "end": 134.76, "text": " also be able to very effectively use the Nullary Detection algorithm."}, {"start": 134.76, "end": 140.27999999999997, "text": " Now to fill in this equation a little bit more, we are saying that the probability of"}, {"start": 140.27999999999997, "end": 146.16, "text": " all the features of this vector features X is the product of P of X1 and P of X2 and"}, {"start": 146.16, "end": 149.23999999999998, "text": " so on up through P of Xn."}, {"start": 149.23999999999998, "end": 156.92, "text": " And in order to model the probability of X1, say the heat feature in this example, we're"}, {"start": 156.92, "end": 164.67999999999998, "text": " going to have two parameters mu1 and sigma1 or sigma squared 1."}, {"start": 164.67999999999998, "end": 172.35999999999999, "text": " And what that means is we're going to estimate the mean of the feature X1 and also the variance"}, {"start": 172.35999999999999, "end": 178.0, "text": " of feature X1 and that will be mu1 and sigma1."}, {"start": 178.0, "end": 184.27999999999997, "text": " To model P of X2, X2 is a totally different feature measuring the vibrations of the airplane"}, {"start": 184.28, "end": 192.0, "text": " engine, we're going to have two different parameters which I'm going to write as mu2"}, {"start": 192.0, "end": 197.08, "text": " sigma2 squared and it turns out this will correspond to the mean or the average of the"}, {"start": 197.08, "end": 203.32, "text": " vibration feature and the variance of the vibration feature and so on."}, {"start": 203.32, "end": 213.6, "text": " If you have additional features mu3 sigma3 squared up through mu n and sigma n squared."}, {"start": 213.6, "end": 220.24, "text": " In case you're wondering why we multiply probabilities, maybe here's one example that could build"}, {"start": 220.24, "end": 222.51999999999998, "text": " intuition."}, {"start": 222.51999999999998, "end": 229.48, "text": " Suppose for an aircraft engine there's a one-tenth chance that it is really really hot, unusually"}, {"start": 229.48, "end": 238.35999999999999, "text": " hot and maybe there is a one in 20 chance that it vibrates really really hot."}, {"start": 238.35999999999999, "end": 242.92, "text": " Then what is the chance that it runs really really hot and vibrates really really hot?"}, {"start": 242.92, "end": 250.56, "text": " We're saying that the chance of that is one-tenth times one over 20 which is one over 200 so"}, {"start": 250.56, "end": 256.03999999999996, "text": " it's really really unlikely to get an engine that both runs really hot and vibrates really"}, {"start": 256.03999999999996, "end": 257.03999999999996, "text": " hot."}, {"start": 257.03999999999996, "end": 260.56, "text": " It's the product of these two probabilities."}, {"start": 260.56, "end": 264.8, "text": " Or the chance of both of these things happening we're saying is the product of both of these"}, {"start": 264.8, "end": 267.36, "text": " probabilities."}, {"start": 267.36, "end": 273.2, "text": " A somewhat more compact way to write this equation up here is to say that this is equal"}, {"start": 273.2, "end": 286.16, "text": " to the product from j equals one through n of p of xj with parameters mu j and sigma"}, {"start": 286.16, "end": 289.76, "text": " squared j."}, {"start": 289.76, "end": 296.52000000000004, "text": " And this symbol here is a lot like the summation symbol except that whereas the summation symbol"}, {"start": 296.52, "end": 303.2, "text": " corresponds to addition, this symbol here corresponds to multiplying these terms over"}, {"start": 303.2, "end": 306.88, "text": " here for j equals one through n."}, {"start": 306.88, "end": 313.84, "text": " So let's put it all together to see how you can build an anomaly detection system."}, {"start": 313.84, "end": 320.0, "text": " The first step is to choose features xi that you think might be indicative of anomalous"}, {"start": 320.0, "end": 322.91999999999996, "text": " examples."}, {"start": 322.92, "end": 327.64000000000004, "text": " Having come up with the features you want to use, you would then fit the parameters"}, {"start": 327.64000000000004, "end": 334.48, "text": " mu one through mu n and sigma squared one through sigma squared n for the n features"}, {"start": 334.48, "end": 337.64000000000004, "text": " in your data set."}, {"start": 337.64000000000004, "end": 345.56, "text": " As you might guess, the parameter mu j will be just the average of xj of the feature j"}, {"start": 345.56, "end": 351.64, "text": " of all the examples in your training set and sigma squared j will be the average of the"}, {"start": 351.64, "end": 360.2, "text": " square difference between the j feature and the value mu j that you just computed up here"}, {"start": 360.2, "end": 361.2, "text": " on top."}, {"start": 361.2, "end": 369.96, "text": " And by the way, if you have a vectorized implementation, you can also compute mu as the average of"}, {"start": 369.96, "end": 376.59999999999997, "text": " the training examples as follows where here x and mu are both vectors."}, {"start": 376.6, "end": 382.56, "text": " And so this would be the vectorized way of computing mu one through mu n all at the same"}, {"start": 382.56, "end": 383.56, "text": " time."}, {"start": 383.56, "end": 388.48, "text": " And by estimating these parameters on your unlabeled training set, you've now computed"}, {"start": 388.48, "end": 391.12, "text": " all the parameters of your model."}, {"start": 391.12, "end": 397.28000000000003, "text": " Finally, when you are given a new example, x test, or I'm just going to write the new"}, {"start": 397.28000000000003, "end": 405.20000000000005, "text": " example as x here, what you would do is compute p of x and see if it's large or small."}, {"start": 405.2, "end": 410.88, "text": " So p of x, as you saw on the last slide, is the product from j equals one through n of"}, {"start": 410.88, "end": 413.7, "text": " the probability of the individual features."}, {"start": 413.7, "end": 420.08, "text": " So p of xj with parameters mu j and sigma squared j."}, {"start": 420.08, "end": 427.84, "text": " And if you substitute in the formula for this probability, you end up with this expression,"}, {"start": 427.84, "end": 432.59999999999997, "text": " one over root two pi sigma j of e to this expression over here."}, {"start": 432.6, "end": 436.12, "text": " And so xj are the features."}, {"start": 436.12, "end": 439.24, "text": " This is a j feature of your new example."}, {"start": 439.24, "end": 445.68, "text": " Mu j and sigma j are numbers or parameters you had computed in the previous step."}, {"start": 445.68, "end": 453.52000000000004, "text": " And if you compute out this formula, you get some number for p of x."}, {"start": 453.52000000000004, "end": 458.8, "text": " And the final step is to see if p of x is less than epsilon."}, {"start": 458.8, "end": 463.32, "text": " And if it is, then you flag that it is an anomaly."}, {"start": 463.32, "end": 469.24, "text": " One intuition behind what this algorithm is doing is that it will tend to flag an example"}, {"start": 469.24, "end": 476.68, "text": " as anomalous if one or more of the features are either very large or very small relative"}, {"start": 476.68, "end": 479.90000000000003, "text": " to what it has seen in the training set."}, {"start": 479.90000000000003, "end": 485.24, "text": " So for each of the features xj, you're fitting a Gaussian distribution like this."}, {"start": 485.24, "end": 492.64, "text": " And so if even one of the features of the new example was way out here, say, then p"}, {"start": 492.64, "end": 495.68, "text": " of xj would be very small."}, {"start": 495.68, "end": 501.8, "text": " And if just one of the terms in this product is very small, then this overall product,"}, {"start": 501.8, "end": 508.7, "text": " we multiply together will tend to be very small and thus p of x will be small."}, {"start": 508.7, "end": 516.64, "text": " And what anomaly detection is doing in this algorithm is a systematic way of quantifying"}, {"start": 516.64, "end": 522.16, "text": " whether or not this new example x has any features that are unusually large or unusually"}, {"start": 522.16, "end": 523.16, "text": " small."}, {"start": 523.16, "end": 530.0, "text": " Now, let's take a look at what all this actually means on one example."}, {"start": 530.0, "end": 535.04, "text": " Here's a data set with features x1 and x2."}, {"start": 535.04, "end": 540.36, "text": " And you notice that the features x1 take on a much larger range of values than the features"}, {"start": 540.36, "end": 543.36, "text": " x2."}, {"start": 543.36, "end": 549.16, "text": " If you were to compute the mean of the features x1, you end up with five, which is why mu"}, {"start": 549.16, "end": 550.8399999999999, "text": " one is equal to one."}, {"start": 550.8399999999999, "end": 556.04, "text": " And it turns out that for this data set, if you compute sigma one, it will be equal to"}, {"start": 556.04, "end": 558.04, "text": " about two."}, {"start": 558.04, "end": 564.9599999999999, "text": " And if you were to compute mu two, the average of the features on x2, the average is three."}, {"start": 564.96, "end": 571.1600000000001, "text": " And similarly, its variance or standard deviation is much smaller, which is why sigma two is"}, {"start": 571.1600000000001, "end": 573.12, "text": " equal to one."}, {"start": 573.12, "end": 580.76, "text": " So that corresponds to this Gaussian distribution for x1 and this Gaussian distribution for"}, {"start": 580.76, "end": 583.4000000000001, "text": " x2."}, {"start": 583.4000000000001, "end": 590.32, "text": " If you were to actually multiply p of x1 and p of x2, then you end up with this 3D surface"}, {"start": 590.32, "end": 598.84, "text": " plot for p of x, where at any point, the height of this is the product of p of x1 times p"}, {"start": 598.84, "end": 603.8000000000001, "text": " of x2 for the corresponding values of x1 and x2."}, {"start": 603.8000000000001, "end": 611.48, "text": " And this signifies that values where p of x is higher are more likely, so values near"}, {"start": 611.48, "end": 617.1600000000001, "text": " the middle, kind of here, are more likely, whereas values far out here, like values out"}, {"start": 617.16, "end": 622.7199999999999, "text": " here, are much less likely, and have much lower chance."}, {"start": 622.7199999999999, "end": 625.92, "text": " Now let me pick two test examples."}, {"start": 625.92, "end": 633.0, "text": " The first one here, I'm going to write as x test one, and the second one down here as"}, {"start": 633.0, "end": 634.88, "text": " x test two."}, {"start": 634.88, "end": 640.16, "text": " And let's see which of these two examples the algorithm will flag as anomalous."}, {"start": 640.16, "end": 648.0, "text": " I'm going to pick the parameter epsilon to be equal to 0.02."}, {"start": 648.0, "end": 656.24, "text": " And if you were to compute p of x test one, it turns out to be about 0.04."}, {"start": 656.24, "end": 660.64, "text": " And this is much bigger than epsilon, and so the algorithm will say, this looks okay,"}, {"start": 660.64, "end": 662.8, "text": " doesn't look like an anomaly."}, {"start": 662.8, "end": 669.0799999999999, "text": " Whereas in contrast, if you were to compute p of x for this point down here, corresponding"}, {"start": 669.08, "end": 680.36, "text": " to x1 equals about 8, and x2 equals about 0.5, kind of down here, then p of x test two"}, {"start": 680.36, "end": 681.36, "text": " is 0.0021."}, {"start": 681.36, "end": 688.4000000000001, "text": " So this is much smaller than epsilon, and so the algorithm will flag this as a likely"}, {"start": 688.4000000000001, "end": 689.72, "text": " anomaly."}, {"start": 689.72, "end": 696.1600000000001, "text": " So pretty much as you might hope, it decides that x test one looks pretty normal, whereas"}, {"start": 696.16, "end": 701.28, "text": " x test two, which is much further away than anything you see in the training set, looks"}, {"start": 701.28, "end": 703.9, "text": " like it could be an anomaly."}, {"start": 703.9, "end": 710.12, "text": " So you've seen the process of how to build an anomaly detection system, but how do you"}, {"start": 710.12, "end": 712.16, "text": " choose the parameter epsilon?"}, {"start": 712.16, "end": 716.64, "text": " And how do you know if your anomaly detection system is working well?"}, {"start": 716.64, "end": 721.72, "text": " In the next video, let's dive a little bit more deeply into the process of developing"}, {"start": 721.72, "end": 725.9599999999999, "text": " and evaluating the performance of an anomaly detection system."}, {"start": 725.96, "end": 727.48, "text": " Let's go on to the next video."}]