ML 14: Anomaly Detection

Anomaly detection – problem motivation

• Anomaly detection is a reasonably commonly used type of machine learning application
  • Can be thought of as a solution to an unsupervised learning problem
  • But, has aspects of supervised learning
• What is anomaly detection?
  • Imagine you’re an aircraft engine manufacturer
  • As engines roll off your assembly line you’re doing QA
    • Measure some features from engines (e.g. heat generated and vibration)
  • You now have a dataset of x¹ to x^m (i.e. m engines were tested)
  • Say we plot that dataset 
    
  • Next day you have a new engine
    • An anomaly detection method is used to see if the new engine is anomalous (when compared to the previous engines)
  • If the new engine looks like this;
    
    
    • Probably OK – looks like the ones we’ve seen before
  • But if the engine looks like this
    
    
    • Uh oh! – this looks like an anomalous data-point

• More formally
  • We have a dataset which contains normal (data)
    • How we ensure they’re normal is up to us
    • In reality it’s OK if there are a few which aren’t actually normal
  • Using that dataset as a reference point we can see if other examples are anomalous
• How do we do this?
• • First, using our training dataset we build a model 
    • We can access this model using p(x)
      • This asks, “What is the probability that example x is normal” 
  • Having built a model
    • if p(x_test) < ε –> flag this as an anomaly
    • if p(x_test) >= ε –> this is OK
    • ε is some threshold probability value which we define, depending on how sure we need/want to be
  • We expect our model to (graphically) look something like this;
    
    • i.e. this would be our model if we had 2D data
      

Applications

• Fraud detection
  • Users have activity associated with them, such as
    • Length on time on-line
    • Location of login
    • Spending frequency
  • Using this data we can build a model of what normal users’ activity is like
  • What is the probability of “normal” behavior?
  • Identify unusual users by sending their data through the model
    • Flag up anything that looks a bit weird
    • Automatically block cards/transactions
• Manufacturing
  • Already spoke about aircraft engine example
• Monitoring computers in data center
  • If you have many machines in a cluster
  • Computer features of machine
    • x₁ = memory use
    • x₂ = number of disk accesses/sec
    • x₃ = CPU load
  • In addition to the measurable features you can also define your own complex features
    
    • x₄ = CPU load/network traffic
  • If you see an anomalous machine
    • Maybe about to fail
    • Look at replacing bits from it

The Gaussian distribution (optional)

• Also called the normal distribution
• Example
  • Say x (data set) is made up of real numbers
    • Mean is μ
    • Variance is σ²
      • σ is also called the standard deviation – specifies the width of the Gaussian probability
    • The data has a Gaussian distribution
  • Then we can write this ~ N(μ,σ² )
    • ~ means = is distributed as
    • N (should really be “script” N (even curlier!) -> means normal distribution
    • μ, σ² represent the mean and variance, respectively
      • These are the two parameters a Gaussian means
  • Looks like this;
    
  • This specifies the probability of x taking a value
    • As you move away from μ
• Gaussian equation is
  • P(x : μ , σ²) (probability of x, parameterized by the mean and squared variance)
    
• Some examples of Gaussians below
  • Area is always the same (must = 1)
  • But width changes as standard deviation changes

Parameter estimation problem

• What is it?
  • Say we have a data set of m examples
  • Give each example is a real number – we can plot the data on the x axis as shown below 
    
  • Problem is – say you suspect these examples come from a Gaussian
    • Given the dataset can you estimate the distribution?
  • Could be something like this
    
  • Seems like a reasonable fit – data seems like a higher probability of being in the central region, lower probability of being further away
• Estimating μ and σ² 
  • μ = average of examples
  • σ² = standard deviation squared 
    
  • As a side comment
    • These parameters are the maximum likelihood estimation values for μ and σ² 
    • You can also do 1/(m) or 1/(m-1) doesn’t make too much difference
      • Slightly different mathematical problems, but in practice it makes little difference

Anomaly detection algorithm

• Unlabeled training set of m examples
  • Data = {x¹, x², …, x^m }
    
    • Each example is an n-dimensional vector (i.e. a feature vector)
    • We have n features!
  • Model P(x) from the data set
    • What are high probability features and low probability features
    • x is a vector
    • So model p(x) as 
      • = p(x₁; μ₁ , σ₁²) * p(x₂; μ₂ , σ₂²) * … p(x_n ; μ_n , σ_n²)
    • Multiply the probability of each features by each feature
      • We model each of the features by assuming each feature is distributed according to a Gaussian distribution
      •  p(x_i; μ_i , σ_i²)
        • The probability of feature x_i given μ_i and σ_i², using a Gaussian distribution
  • As a side comment
    • Turns out this equation makes an independence assumption for the features, although algorithm works if features are independent or not
      • Don’t worry too much about this, although if you’re features are tightly linked you should be able to do some dimensionality reduction anyway!
  • We can write this chain of multiplication more compactly as follows;
    
    • Capital PI (Π) is the product of a set of values
  • The problem of estimation this distribution is sometimes call the problem of density estimation

Algorithm

• 1 – Chose features
  • Try to come up with features which might help identify something anomalous – may be unusually large or small values
  • More generally, chose features which describe the general properties
  • This is nothing unique to anomaly detection – it’s just the idea of building a sensible feature vector
• 2 – Fit parameters
  • Determine parameters for each of your examples μ_i and σ_i²
    • Fit is a bit misleading, really should just be “Calculate parameters for 1 to n”
  • So you’re calculating standard deviation and mean for each feature 
  • You should of course used some vectorized implementation rather than a loop probably
• 3 – compute p(x)
  • You compute the formula shown (i.e. the formula for the Gaussian probability)
  • If the number is very small, very low chance of it being “normal”

Anomaly detection example

• x₁
  • Mean is about 5
  • Standard deviation looks to be about 2
• x₂
  • Mean is about 3
  • Standard deviation about 1
• So we have the following system
  
• If we plot the Gaussian for x₁ and x₂ we get something like this
  
• If you plot the product of these things you get a surface plot like this
  
  • With this surface plot, the height of the surface is the probability – p(x)
  • We can’t always do surface plots, but for this example it’s quite a nice way to show the probability of a 2D feature vector
• Check if a value is anomalous
  • Set epsilon as some value
  • Say we have two new data points new data-point has the values
    • x¹_test
    • x²_test
  •  We compute 
    • p(x¹_test) = 0.436 >= epsilon (~40% chance it’s normal)
      • Normal
    • p(x²_test) = 0.0021 < epsilon (~0.2% chance it’s normal)
      • Anomalous
  • What this is saying is if you look at the surface plot, all values above a certain height are normal, all the values below that threshold are probably anomalous

Developing and evaluating and anomaly detection system

• Here talk about developing a system for anomaly detection
  • How to evaluate an algorithm
• Previously we spoke about the importance of real-number evaluation
  • Often need to make a lot of choices (e.g. features to use)
    • Easier to evaluate your algorithm if it returns a single number to show if changes you made improved or worsened an algorithm’s performance
  • To develop an anomaly detection system quickly, would be helpful to have a way to evaluate your algorithm
• Assume we have some labeled data
  • So far we’ve been treating anomalous detection with unlabeled data
  • If you have labeled data allows evaluation
    • i.e. if you think something iss anomalous you can be sure if it is or not
• So, taking our engine example
  • You have some labeled data 
    • Data for engines which were non-anomalous -> y = 0
    • Data for engines which were anomalous -> y = 1
  • Training set is the collection of normal examples
    • OK even if we have a few anomalous data examples 
  • Next define
    • Cross validation set
    • Test set
    • For both assume you can include a few examples which have anomalous examples
  • Specific example
    • Engines
      • Have 10 000 good engines
        • OK even if a few bad ones are here…
        • LOTS of y = 0
      • 20 flawed engines 
        • Typically when y = 1 have 2-50 
    • Split into 
      • Training set: 6000 good engines (y = 0)
      • CV set: 2000 good engines, 10 anomalous
        
      • Test set: 2000 good engines, 10 anomalous
      • Ratio is 3:1:1
    • Sometimes we see a different way of splitting
      • Take 6000 good in training
      • Same CV and test set (4000 good in each) different 10 anomalous, 
      • Or even 20 anomalous (same ones)
      • This is bad practice – should use different data in CV and test set
  • Algorithm evaluation
    • Take trainings set { x¹, x², …, x^m }
      • Fit model p(x)
    • On cross validation and test set, test the example x
      • y = 1 if p(x) < epsilon (anomalous)
      • y = 0 if p(x) >= epsilon (normal)
    • Think of algorithm a trying to predict if something is anomalous
      • But you have a label so can check!
      • Makes it look like a supervised learning algorithm
• What’s a good metric to use for evaluation
  • y = 0 is very common
    • So classification would be bad
  • Compute fraction of true positives/false positive/false negative/true negative
  • Compute precision/recall
  • Compute F1-score
• Earlier, also had epsilon (the threshold value)
  • Threshold to show when something is anomalous
  • If you have CV set you can see how varying epsilon effects various evaluation metrics
    • Then pick the value of epsilon which maximizes the score on your CV set
  • Evaluate algorithm using cross validation
  • Do final algorithm evaluation on the test set

Anomaly detection vs. supervised learning

• If we have labeled data, we not use a supervised learning algorithm?
  • Here we’ll try and understand when you should use supervised learning and when anomaly detection would be better

Anomaly detection

• Very small number of positive examples 
  • Save positive examples just for CV and test set
  • Consider using an anomaly detection algorithm
  • Not enough data to “learn” positive examples
• Have a very large number of negative examples
  
  • Use these negative examples for p(x) fitting
  • Only need negative examples for this
• Many “types” of anomalies
  • Hard for an algorithm to learn from positive examples when anomalies may look nothing like one another
    • So anomaly detection doesn’t know what they look like, but knows what they don’t look like
  • When we looked at SPAM email,
    • Many types of SPAM
      
    • For the spam problem, usually enough positive examples
    • So this is why we usually think of SPAM as supervised learning
• Application and why they’re anomaly detection
  • Fraud detection
    • Many ways you may do fraud
    • If you’re a major on line retailer/very subject to attacks, sometimes might shift to supervised learning
  • Manufacturing
    • If you make HUGE volumes maybe have enough positive data -> make supervised
      • Means you make an assumption about the kinds of errors you’re going to see
      • It’s the unknown unknowns we don’t like!
  • Monitoring machines in data

Supervised learning

• Reasonably large number of positive and negative examples
• Have enough positive examples to give your algorithm the opportunity to see what they look like
  • If you expect anomalies to look anomalous in the same way
• Application
  • Email/SPAM classification
  • Weather prediction
  • Cancer classification

Choosing features to use

• One of the things which has a huge effect is which features are used
• Non-Gaussian features
  • Plot a histogram of data to check it has a Gaussian description – nice sanity check
    • Often still works if data is non-Gaussian
    • Use hist command to plot histogram
  • Non-Gaussian data might look like this
    
  • Can play with different transformations of the data to make it look more Gaussian
  • Might take a log transformation of the data
    • i.e. if you have some feature x₁, replace it with log(x₁)
      
      • This looks much more Gaussian
    • Or do log(x₁+c)
      • Play with c to make it look as Gaussian as possible
    • Or do x^1/2
    • Or do x^1/3

Error analysis for anomaly detection

• Good way of coming up with features
• Like supervised learning error analysis procedure
  • Run algorithm on CV set
  • See which one it got wrong
  • Develop new features based on trying to understand why the algorithm got those examples wrong
• Example
  • p(x) large for normal, p(x) small for abnormal
  • e.g.
    
  • Here we have one dimension, and our anomalous value is sort of buried in it (in green – Gaussian superimposed in blue)
    • Look at data – see what went wrong
    • Can looking at that example help develop a new feature (x2) which can help distinguish further anomalous 
• Example – data center monitoring
  • Features
    • x₁ = memory use
    • x₂ = number of disk access/sec
    • x₃ = CPU load
    • x₄ = network traffic
  • We suspect CPU load and network traffic grow linearly with one another
    • If server is serving many users, CPU is high and network is high
    • Fail case is infinite loop, so CPU load grows but network traffic is low
      • New feature – CPU load/network traffic
      • May need to do feature scaling

Multivariate Gaussian distribution

• Is a slightly different technique which can sometimes catch some anomalies which non-multivariate Gaussian distribution anomaly detection fails to
• • Unlabeled data looks like this 
    
  • Say you can fit a Gaussian distribution to CPU load and memory use
  • Lets say in the test set we have an example which looks like an anomaly (e.g. x₁ = 0.4, x₂ = 1.5)
    • Looks like most of data lies in a region far away from this example
      • Here memory use is high and CPU load is low (if we plot x₁ vs. x₂ our green example looks miles away from the others) 
  • Problem is, if we look at each feature individually they may fall within acceptable limits – the issue is we know we shouldn’t don’t get those kinds of values together
    • But individually, they’re both acceptable
      
      
  • This is because our function makes probability prediction in concentric circles around the the means of both
    
    
    • Probability of the two red circled examples is basically the same, even though we can clearly see the green one as an outlier
  • • Doesn’t understand the meaning

Multivariate Gaussian distribution model

• To get around this we develop the multivariate Gaussian distribution
  • Model p(x) all in one go, instead of each feature separately
    • What are the parameters for this new model?
      • μ – which is an n dimensional vector (where n is number of features)
      • Σ – which is an [n x n] matrix – the covariance matrix

• For the sake of completeness, the formula for the multivariate Gaussian distribution is as follows
  
  
  • NB don’t memorize this – you can always look it up
  • What does this mean?
    •  = absolute value of Σ (determinant of sigma)
      • This is a mathematic function of a matrix
      • You can compute it in MATLAB using det(sigma)
• More importantly, what does this p(x) look like?
  • 2D example
    
    • Sigma is sometimes call the identity matrix
      
      • p(x) looks like this
        • For inputs of x₁ and x₂ the height of the surface gives the value of p(x)
  • What happens if we change Sigma?
    
  • So now we change the plot to
    
    • Now the width of the bump decreases and the height increases
  • If we set sigma to be different values this changes the identity matrix and we change the shape of our graph
    
  • Using these values we can, therefore, define the shape of this to better fit the data, rather than assuming symmetry in every dimension
• One of the cool things is you can use it to model correlation between data
  • If you start to change the off-diagonal values in the covariance matrix you can control how well the various dimensions correlation
    
    • So we see here the final example gives a very tall thin distribution, shows a strong positive correlation
    • We can also make the off-diagonal values negative to show a negative correlation
• Hopefully this shows an example of the kinds of distribution you can get by varying sigma 
  • We can, of course, also move the mean (μ) which varies the peak of the distribution

Applying multivariate Gaussian distribution to anomaly detection

• Saw some examples of the kinds of distributions you can model
  • Now let’s take those ideas and look at applying them to different anomaly detection algorithms
• As mentioned, multivariate Gaussian modeling uses the following equation;
  
• Which comes with the parameters μ and Σ
  • Where 
    • μ – the mean (n-dimenisonal vector)
    • Σ – covariance matrix ([nxn] matrix)
• Parameter fitting/estimation problem
  • If you have a set of examples 
    •  {x¹, x², …, x^m }
  • The formula for estimating the parameters is
    
  • 
    
  • Using these two formulas you get the parameters

Anomaly detection algorithm with multivariate Gaussian distribution

• 1) Fit model – take data set and calculate μ and Σ using the formula above
• 2) We’re next given a new example (x_test) – see below
  
  • For it compute p(x) using the following formula for multivariate distribution
    
• 3) Compare the value with ε (threshold probability value)
  • if p(x_test) < ε –> flag this as an anomaly
  • if p(x_test) >= ε –> this is OK
• If you fit a multivariate Gaussian model to our data we build something like this
  
  
• Which means it’s likely to identify the green value as anomalous
  
• Finally, we should mention how multivariate Gaussian relates to our original simple Gaussian model (where each feature is looked at individually)
  • Original model corresponds to multivariate Gaussian where the Gaussians’ contours are axis aligned
  • i.e. the normal Gaussian model is a special case of multivariate Gaussian distribution
    • This can be shown mathematically
    • Has this constraint that the covariance matrix sigma as ZEROs on the non-diagonal values
      
    • If you plug your variance values into the covariance matrix the models are actually identical 

Original model vs. Multivariate Gaussian
Original Gaussian model

• Probably used more often
• There is a need to manually create features to capture anomalies where x₁ and x₂ take unusual combinations of values
  • So need to make extra features
  • Might not be obvious what they should be
    • This is always a risk – where you’re using your own expectation of a problem to “predict” future anomalies
    • Typically, the things that catch you out aren’t going to be the things you though of
      • If you thought of them they’d probably be avoided in the first place
    • Obviously this is a bigger issue, and one which may or may not be relevant depending on your problem space
• Much cheaper computationally
• Scales much better to very large feature vectors
  • Even if n = 100 000 the original model works fine
• Works well even with a small training set
  • e.g. 50, 100
• Because of these factors it’s used more often because it really represents a optimized but axis-symmetric specialization of the general model

Multivariate Gaussian model

• Used less frequently
• Can capture feature correlation
  • So no need to create extra values
• Less computationally efficient
  
  • Must compute inverse of matrix which is [n x n]
  • So lots of features is bad – makes this calculation very expensive
  • So if n = 100 000 not very good
• Needs for m > n 
  • i.e. number of examples must be greater than number of features
  • If this is not true then we have a singular matrix (non-invertible)
  • So should be used only in m >> n
• If you find the matrix is non-invertible, could be for one of two main reasons
  • m < n
    • So use original simple model
  • Redundant features (i.e. linearly dependent)
    • i.e. two features that are the same
    • If this is the case you could use PCA or sanity check your data