BHAD: Explainable unsupervised anomaly detection using Bayesian histograms

Speaker 1 [00:02]

Thank you very much. So yeah, it's a pleasure to be here. My name is Alexander Vosserlein, the lead data scientist of the advanced analytics team of Allianz Germany. And the topic of my talk is about explainable unsupervised anomaly detection using Bayesian histograms. So let me briefly sketch the agenda. I will give you a quick introduction to what is anomaly detection, what is the definition of an outlier, and then give you a little bit of a technical background regarding the model that we proposed, and then also show you a Python implementation, a BHAD package that we have come up with, and then show you some benchmarking, some predictive performances, how the model is doing, and finally give you an outlook and a quick summary. so what is an outlier or an anomaly so depending on really where and what kind of literature or domain of research you're looking at you might find yeah different definitions if you stick let's say with the statistics definition there's a relatively commonly used definition due to hawkins which says that an outlier is an observation which deviates so much from the other observations. As to row suspicions that it was generated by a different mechanism and this already suggests that there is some sort of data generating process. This is very much statistics based so really normal data objects somehow follow that generating mechanism whereas abnormal or deviating objects somehow deviate in some statistical sense from this data generating process. So there are many industrial applications obviously to anomaly detection and outlier detection. For example, fault detection, quality control and predictive maintenance or weblog analytics when you think of looking for unusual patterns in weblogs. Also in medical for example, imaging diagnostics to give an example or in finance so banking insurance for example very very common application is obviously fraud detection in particular for also important for alliance and in natural science for example earth science application sea surface temperature anomalies and so forth. So you can somehow classify the different approaches that are out there in the literature around certain, let's say, categories. One would be if the method you are using is probabilistic in nature or non-probabilistic. On the other hand, it's about the way you Use supervision in your data. So is it an unsupervised semi supervised or even let's say some sort of imbalanced supervised learning problem Or something, you know in between like a pew learning Problem, is it an ensemble that you are using or is it a single model? then the how do you measure let's say deviations or For example, do you use the distances between observations in the feature space or do you use some notion of density? So number of points in different regions of the feature space and of course what kind of data you're looking at. So do you look at a let's say cross-sectional data set or do you have spatial data where you have an index that has a higher dimension? Is it an ordered problem or even a graph problem? So, yeah, very much jumping into the algorithm, so Bayesian Histogram Anomaly Detector, give you a brief motivation around why we have come up with this approach. At Allianz, we were facing, let's say, the challenge that in a corporate insurance context, we wanted to deploy on a global scale really for different countries a fraud predictive model and at that time in that business we didn't have any let's say established business process in place so there were no labels at all so this called somehow for an unsupervised approach and you know it's very common practice in particular if you focus on an unsupervised approach that you should consider an ensemble for this for this task and for any black box models in particular when it's unsupervised and even more complicated when it's an ensemble explainability is very tricky and it's very crucial of course in particular in practical applications when you when you think of personal data so the user wants always a reason why a certain score is like it is. So for this reason we were looking somehow for a sort of a surrogate model, a proxy model that somehow can explain we can use on behalf of the actual ensemble and therefore we wanted to have a model that's predictive on the one hand but on the other side is really locally or globally explainable. And so the model that we are looking at is, as the title already suggests, is a probabilistic model, a Bayesian model, so let's dive right in. So let's assume we have observations which are independently and identically distributed from an unknown continuous distribution, and we somehow want to estimate that distribution and we discretize the support of the random variable Y so we bin it in some sense and for the simplicity we assume that the node locations are known at the moment so this can very easily then motivated in something that we call a piecewise constant data model. So we essentially have to face with certain unknown parameters. So you have those bin probabilities that we denoted by pi, this vector pi. And as I think all of you might know, in a histogram context it's very crucial, so to say, the number of bins, which is a very crucial parameter, that have to somehow in a statistical sense take care of. So this is also part of our estimation. So we really on the fly also estimate the unknown parameter and through the spinning this somehow implies that we map the continuous variable yi to a one-hot vector and this can be perceived as a categorical distribution. So the categorical distribution is very much you know known to be part of the exponential family so there exists a conjugate prior and this will be used subsequently. So a very crucial part as I as I said is here really this parameter k so the integer parameter the number of bins because this very much controls the complexity and the fit of this whole density estimate. And we use an informative prior that was proposed by Skargel 2013. And you can see from the form of this prior that it depends on a hyperparameter, so there's some sort of hierarchy here in place. hyperparameter gamma controls really the complexity and we also put prior on that parameter and this is an uninformative prior that restricts gamma to the range of 0 and 1 and because this has the form of a geometric series this controls so to say the convergent convergence of this geometric series and yeah we will use this subsequently then the parameters pi which are the bin probabilities we simply use a Jeffries prior that can be shown to be a Dirichlet prior with hyperparameters alpha 1 over 2 and we integrate these parameters out because essentially we are facing we want to somehow derive the posterior of the number of bins in order to estimate the number of bins and therefore we have to integrate all the parameter vector pi this can be done analytically because it's a conjugate model and we integrate all this hyper parameter gamma numerically which can be done for example by by importance sampling, or numerically by, let's say, a Simpson's rule, or things like that. So, just wanted to show you what's the form of this informative prior for the number of bins, and you can see it's highly informative because it somehow restricts the number of bins in a sense that we impose something like OChem's razor, saying that, let's say, simpler models are preferred over complex models. And this is some sort of regularization that we impose here by this prior. To give you a simple example, how does that work? So how does the estimation process of the number of bins work? We used a relatively famous example from Larry Wasserman, man which he termed the Bart Simpson density and yeah you can see from the form of this density why this somehow has some resemblance. So under the hood it's mainly a Gaussian mixture model a five component Gaussian mixture model and it's straightforward to to take some random draws from this so we take some random draws from this estimate so to say the number of bins and then compute the histogram and on the right hand side you can see the posterior mass function of the number of bins alongside with the credible interval 95 percent highest posterior density interval and what we term here as k-hat base is the maximum a posteriori estimate and for comparison we show some other let's say frequentest estimates. So in order to somehow have this a little bit more condensed we did a little Monte Carlo experiment and we're repeating this whole process that I just described so taking random draws computing the number of bins for yeah 100 times or so and doing this also with different sample sizes to really you know see a little bit desensitivity regarding the sample size, and I'm computing the mean integrated squared error between the true density, which we know, obviously, which is a Gaussian mixture model, and the estimated densities, and you can see that from the figures that, so the red one is the base estimate, so this performs quite decent, I would say. And when you aggregate everything over the different sample sizes, which we term here aggregated mice, then this is very close to Scott's rule, which is a little bit better here. So this seems to work. So actually we want to do anomaly detection, so how can we go there? For innovation context, obviously we need the posterior predictive distribution for a new data point and this is again straightforward to calculate because again we are in some sort of multinomial Dirichlet conjugacy and we can calculate that more or less by hand. So this has the form of a categorical distribution and this is really the probability of a new data point being in the S bin, so to say. So it's very simple to compute. And using this posterior predictive distribution as a score, we somehow arrive at the anomaly score, which is simply, we take that as the geometric mean of the posterior predictive distribution and using a log scale for let's say numerical reasons this we arrive at a simple arithmetic mean as you can see and so this very much simplifies many things for us first of all the computation because it's a simple arithmetic mean so it's linear the complexity is n times m where m is so to say the number of bins yeah and also allows some sort of explainability obviously because low scores mean being outlierish and vice versa. So we can simply look at the different components of the sum and see what makes the most contribution. That's a little bit the idea. And to a quick summary of the algorithm of the BHAD, so overall features, upper case D, we compute the posterior mass function of the number of pins per feature and then compute the maximum or posterior estimate. on that, compute the sufficient statistics, which are simple counts, compute the posterior predictive probabilities based on that, do that for all features, and then finally compute the score. So it's very simple to compute. And so there is a package available, BHAD, which is available on PyPy. So this very much follows well-known scikit-learn API. alongside the outlier mixin template and You can use everything that you can use with standard outlier mixin Classes, so for example, you can use pipe Lines and things like that. So for example here we use First discretize the continuous features in case of categorical features. This obviously will be skipped and Then compute DBHAD and compute or predict so to say some scores coming to the model explainability as I already mentioned through the linearity you can very easily calculate or come up with some sort of local explainability and for this we have an explainer module in place which allows the user to do that and for on an individual level so So really on an observational level, you simply build the rank series of the different log posterior predictive values and take, so to say, record the feature names and the corresponding ranks and take this then as an explanation. And on a global level, you can very simply average that. So you take the average rank and then transform this to a unit interval on a global level. And you can visualize that in the usual form that everyone knows from global feature importances. So on the very top you have the most important feature and at the bottom the least important one. So coming to the model benchmarking, we calculated a couple of different models to compare BHAD with. So, we took, for example, an isolation forest, one-class support vector machines, average K and Ns, angle-based outlier detector, then two deep learning models, so a vanilla Gaussian VEA and a VEA with a Dirichlet process prior, so the stick-breaking VEA, a local outlier factor, and then two very simple models, which is the empirical CDF, a histogram-based outlier detection, which, as the name suggests, is very, very similar to the one that we are using, but on a purely frequentist basis and doesn't obviously give straightforward inference regarding this crucial parameter of number of bins. And then an ensemble, so a full ensemble, taking the minimum rank of these scores and a boosted ensemble. I'm presenting here evidence for simulated data as well as two commonly known benchmark data sets. So for the simulated data, we simply took random draws from a 30-variate two-component student team mixture. Two components, because on the one hand, we have, so to say, the inliers, the outliers and through the mixture approach we have the latent assignments and so we can mimic a little bit the situation in a binary classification task and use the standard instruments that we would use in our supervised context and in order to really control a little bit for the uncertainty due to train and test split we do some Monte Carlo kind of averaging for different train and test splits, let's say 100 times, and you average the F1 scores. And the other two data sets, so the PIN digits, handwritten PIN digits classification data set, and the Wisconsin breast cancer data sets, which we simply, so we take one class, downsample that class, and the other classes are, so to say, inliers. This is also a common approach, so to say, in the outlier literature. and um here in red you can see that um the bhid does a quite um yeah favorable job i would say um so it is um here for the simulated it's among the top four and for the other one it's among the top three so um again while having really local explainability um Finally, we wanted to show how associated are those different candidate models. When you think of an ensemble, for example, you want to take an ensemble out of all these candidate models and it's interesting to see how correlated are the different candidates because if they were not correlated at all, then it doesn't make sense to use that as a proxy model. And you can see a BHAD here in the third column from the left-hand side. It's very much correlated with those candidates that we just showed. And even, I mean, obviously with, let's say, the histogram-based in the top row and the empirical CDF, CDF, which is somehow to be assumed because they both estimate the density in some sense, but also with more complex models, like, for example, in the top row, the Diraclay process, VEA, which is a completely different approach to ours. It's a deep learning approach, and yeah. But even with such an approach, has a very high Spearman's rank correlation, So, this can be taken as some sort of justification to take this as a proxy model. So, to sum up, I've just introduced BHAD. BHAD automatically determines the optimal number of bins. Allows also using mixed data. It has competitive performance compared to state of the art methods. It allows local and global model extendability due to the linearity in sample size. And there is a Python implementation, bhad, which can be used via PyPy. And one of the, let's say on a discussion basis, one of the current assumptions is that the node positions are known, which is obviously some sort of simplification, and that they are equally spaced. And this might lead to some potential inefficiencies because imagine, for example, you have a high-density region, and this high-density region, you assign too low a number of bins, so you kind of over-smooth that region. And on the other hand, you might have, let's say, a low-density region, and you assign too many bins, so you introduce way too much variance, so you somehow overfit that region. So this is something that is future work, definitely. There are many approaches that you can apply. For example, Bayesian blocks, which is a commonly known method for this kind of problem. So this is really up to future work. So this was it.

Speaker 2 [23:47]

Thank you very much for this very thorough and nicely explained talk. There are three questions. How weak does it scale in the number of features?

Speaker 1 [24:01]

The number of features you could see is, so to say, just the sum over those spins. So, let me go back. There you go. So, if you have continuous data, then so to say the features are the different bins. So the number of bins equals the number of features on a continuous level, however if you have categorical data then the different levels are so to say your different features and as you can see they are in some sense linear here.

Speaker 2 [24:55]

Okay, thank you another the problem with anomaly detection is often putting it into practice with a low amount of false positives How are you using this method at Allianz? Yes, it's a secret

Speaker 1 [25:10]

Important question. Critical, yes. Obviously, I mean, it's an unsupervised method. On simulated data, the world is always beautiful somehow. yeah that was let's say a first approach that we used in Allianz for that and you know over time we collected labels and we switched into a pure learning approach actually now because we gathered positives and so we could switch to a pure learning approach and finally to an imbalanced supervised approach

Speaker 2 [25:46]

Thank you. Did I understand this correct, that PHAD considers each feature dimension individually, or does it also take into account unusual combinations of features? Yes.

Speaker 1 [25:57]

Yes, that's correct. It's another simplification of course, makes computation easier and also introduces of course this linearity. Without this linearity you have a problem with the local explainability of course. That's a simplification but it works quite well so far and on the benefit of having this local explainability.

Speaker 2 [26:19]

And the last one, can you explain BHAD in a short sentence for a not statistical person? That would be nice.

Speaker 1 [26:27]

But that's mean.

Speaker 2 [26:31]

Same question.

Speaker 1 [26:32]

I would say you simply count the number of observations that have a certain value in

Speaker 2 [26:33]

Yes, yes.

Speaker 1 [26:55]

a certain bin. You probably have to define what a bin is, but it's a simple count method under the hood.

Speaker 2 [27:02]

You count the important ones

Speaker 1 [27:04]

I'm not yes. Yes. I mean Yeah, it's a it's a directly approach. So yeah the sufficient statistic is that

Speaker 2 [27:14]

Obviously.

Speaker 1 [27:15]

Ha, ha, ha, ha, ha.

Speaker 2 [27:16]

Thank you very much unless there are no other questions, let's thank all the speakers again