Unsupervised Dictionary Learning for Anomaly Detection

2020·Arxiv

Abstract

Abstract

We investigate the possibilities of employing dictionary learning to address the requirements of most anomaly detection applications, such as absence of supervision, online formulations, low false positive rates. We present new results of our recent semi-supervised online algorithm, TODDLeR, on a anti-money laundering application. We also introduce a novel unsupervised method of using the performance of the learning algorithm as indication of the nature of the samples.

1 Introduction

It is often the case in anomaly detection applications that not all types of anomalies are known in advance and new ones must be identified on the run. Supervised methods fall short of this requirement. We present two approaches on using the dictionary learning (DL) framework for anomaly detection. The first, a semi-supervised online solution that allows for discovering of new, unseen types of anomalies is presented in Section 2. Previous tests showed the method is suited for malware identifica-tion [5] in large datasets of file descriptions. The second is an empirical take on the unsupervised problem, created with the application of fraud detection in mind and is detailed in Section 3. More on the motivation and specifics of the application, in particular on anti-money laundering, can be found in [6] and [1]. While the two approaches address slightly different settings, we are motivated in presenting them together by their common novelty in approaching the anomaly detection problem by dictionary learning.

Consider the dictionary learning problem

where are the N samples, is the dictionary and the sparse representation, with at most s nonzero elements.

2 Semi-supervised Anomaly Detection

Semi-supervised DL algorithms usually start with an offline pretraining stage where a classification algorithm is used to train a dictionary on labeled data. This dictionary is then used unsupervised to classify and learn from incoming signals in an online fashion.

Label Consistent K-SVD (LC-KSVD) [7] extends the DL objective to include a linear classifier W and a second labelconsistent dictionary A that groups atoms to represent only a particular signal class.

Here H and Q are indicator matrices of the labels and, respectively, the atoms allocated for representing each signal class. Due to the properties of the Frobenius norm, the (2) objective can be rewritten as the plain DL problem.

Anomaly detection implies large sets of data where only a few of the items are anomalous. Thus classic DL solutions can not cope with the large signals set and we have to approach the problem online. RLS-DLA [10] is an online recursive algorithm drawing its inspiration from MOD [4] that fixes the signals and the representations and updates the dictionary through least squares (LS). RLS-DLA applies the same technique in the online setting. Let us note the following fixed matrices

such that the LS at time t is written as . When a new signal y arrives at time t + 1, RLS-DLA performs dictionary update by solving

After a few algebraic manipulations, the update can be rewritten as

where and is a forgetting factor that controls the reliance on past estimations and is usually set around 0.95.

TODDLeR [5] further extends the online objective to include the classification ingredients from LC-KSVD

where we also added two regularization constraints on the linear classifier and the label consistent dictionary such that the existing model absorbs the new information given by signal y but also maintains its existing properties. Unlike competing online algorithms [8, 11], TODDLeR updates the dictionary with all samples that it sees no matter the classification confidence level. The robustness of the existing model is maintained by mediating the rate of change through the two extra regularization in (7) that lead to minimizing the following functions after the classification and dictionary update. Note, however, that since we are in the online, unsupervised stage, labels h are now estimated, not ground truth labels.

Looking at f and g as generalized Tikhonov regularization, we proposed and showed in [5] that good choices for and are

3 Unsupervised Anomaly Detection

In absence of labels, some other knowledge must be sought that informs DL on the nature of the signals. In the following experiments we seek for such clues in the learning process itself. The scheme involves progressively filtering out signals that, according to some criteria, appear less likely to be anomalies. Let A denote the set of potential anomalies, at first containing all the samples. At each iteration the signals not satisfying the criteria are eliminated from the set.

Our first proposal seeks to overspecialize the dictionary in representing the normal samples. We train a new dictionary, , on the set A at each iteration and join these dictionaries together. Given that in most applications normal signals outnumber anomalies, it is to be expected that in the first DL iterations the dictionary is more able to represent normal samples. Mean representation error obtained after a few rounds of DL can therefore offer some indication on how well the dictionary performs in representing anomalies, and can in turn be used to determine the signal class. Algorithm 1 details the above steps.

The dictionary can, however, overspecialize in representing some anomalies as well, which will then be excluded from A. Therefore, a criteria that minimizes the number of false negatives is also needed. We turn to the measure of atom popularity for the task. The approach requires that the number of anomalies in the dataset, , is known, which is reasonably common in practice. Provided the dictionary has learned to represent both the features of normal signals and those of anomalies, it is expected that some dictionary atoms will specialize in describing anomalies. As a result, those atoms will be used in the representations of at most samples. We refer to popularity of an atom j as the number of signals that are represented using that atom and compute the measure as [3].

In our second solution, we restrict the set A of potential anomalies to signals represented by atoms with popularity , namely . Atoms that describe rare but otherwise normal features will also meet the criteria, therefore filtering out signals using the above atom popularity threshold is a cautious way of reducing the set of potential anomalies: it minimizes false negatives, but may result in fairly large number of false positives. Unlike the previous method, a new dictionary is learned at each step. The iterative process can be stopped when .

Figure 1: Unsupervised DL with error threshold

4 Results

We test the above methods on a financial fraud database consisting of credit card transaction information developed at the Université Libre de Bruxelles [2]. The database is extremely unbalanced (0.17% anomalies) and for the purpose of this study we work on a subset where the normal samples outnumber anomalies by a factor of 100 when testing the online method (TODDLeR) and 10 for the unsupervised methods.

We first run TODDLeR on a dataset of N = 39754 samples with 29 features, which have been previously normalized. The best performance, 98.86% classification accuracy, is obtained when the Tikhonov regularization factors are set . This setting also has a good false positive count of 83.

Our second test involves unsupervised experiments on a dataset of N = 5412 samples. At each step, we perform 20 iterations of DL (AK-SVD). Sparse coding is done via OMP [9] with sparsity set to s = 5. Figure 1 shows the evolution of false positives and false negatives when filtering samples based on the error criteria. Filtering with popularity threshold alone correctly labels 32% of signals as normal samples, while keeping false negatives to 0 after 60 iterations. Clearly, performance depends on the number of atoms representing other uncommon signal attributes. A preliminary step of dictionary size adjustment can help ensure that a proper number of atoms is available to represent all sample features. This empirical approach can be extended to other means of characterizing the learning process (such as atom coefficients magnitude, or the evolution of these measures as learning progresses etc) that can be informative of the nature of the signals or their occurrence rate.

5 Conclusion

The paper shows current work state on the problem of applying DL to anomaly detection. It tackles the main issues arising in these applications, namely the need for lightweight, online algorithms, with little or no supervision.

Acknowledgements

This work was supported by BRD Groupe Societe Generale through DataScience Research Fellowships of 2019. P. Irofti was also supported by a grant of Romanian Ministry of Research and Innovation CCCDI-UEFISCDI. project no. 17PC-CDI/2018, and A. B˘altoiu by the Operational Programme Human Capital of the Ministry of European Funds through the Financial Agreement 51675/09.07.2019, SMIS code 125125.

References

[1] Andra Baltoiu, Andrei Patrascu, and Paul Irofti. Community-level anomaly detection for anti-money laundering. arXiv preprint arXiv:1910.11313, 2019.

[2] Fabrizio Carcillo, Yann-Aël Le Borgne, Olivier Cae- len, Yacine Kessaci, Frédéric Oblé, and Gianluca Bontempi. Combining unsupervised and supervised learning in credit card fraud detection. Information Sciences, 05 2019.

[3] B. Dumitrescu and P. Irofti. Dictionary Learning Algorithms and Applications. Springer, 2018.

[4] K. Engan, S.O. Aase, and J.H. Husoy. Method of optimal directions for frame design. In IEEE Int. Conf. Acoustics Speech Signal Proc., volume 5, pages 2443–2446, 1999.

[5] Paul Irofti and Andra B˘altoiu. Malware identification with dictionary learning. In 2019 27th European Signal Processing Conference (EUSIPCO), pages 1–5. IEEE, 2019.

[6] Paul Irofti, Andrei Patrascu, and Andra Baltoiu. Fraud detection in networks: State-of-the-art. arXiv preprint arXiv:1910.11299, 2019.

[7] Z. Jiang, Z. Lin, and L.S. Davis. Learning A Discrim- inative Dictionary for Sparse Coding via Label Consistent K-SVD. In IEEE Conf. Computer Vision and Pattern Recognition, pages 1697–1704, 2011.

[8] S. Matiz and K.E. Barner. Label consistent recursive least squares dictionary learning for image classification. In 2016 IEEE International Conference on Image Processing (ICIP), pages 1888–1892. IEEE, 2016.

[9] Y.C. Pati, R. Rezaiifar, and P.S. Krishnaprasad. Orthog- onal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In 27th Asilomar Conf. Signals Systems Computers, volume 1, pages 40–44, Nov. 1993.

[10] K. Skretting and K. Engan. Recursive least squares dic- tionary learning. IEEE Trans. Signal Proc., 58(4):2121– 2130, 2010.

[11] G. Zhang, Z. Jiang, and L.S. Davis. Online semi-supervised discriminative dictionary learning for sparse representation. In Asian conference on computer vision, pages 259–273. Springer, 2012.