Towards a Hierarchical Bayesian Model of Multi-View Anomaly Detection

1 Introduction

Anomaly Detection (AD) is a fundamental task with broad applications, such as in clinical diagnosis, fraud transaction detection and cybersecurity [Chandola et al., 2009]. Traditional detectors only examine a single view 1 of instances and cannot discover multi-view anomalies, i.e., instances that exhibit inconsistent behaviors across different views. One example is in web image analysis, an image can be described its category such as car or animal (view 1) and its web page such as cars.com or animals.com (view 2). If an image is assigned to the animal group in view 1 but car group in view 2, then it is natural to consider this image anomalous [Marcos Alvarez et al., 2013]. Other examples can be found in digit recognition

1 A view is a set of features that often have similar semantics, e.g., a webpage can be described by one view of its content and another view of its hyperlinks [Xu et al., 2013].

[Li et al., 2018b] and movie recommendation on MovieLens dataset [Gao et al., 2011]. How to effectively leverage multiple views to detect anomaly is an interesting and significant topic, often referred to as multi-view anomaly detection.

In the literature, a number of multi-view anomaly detectors have been developed. Some of them try to find samples that have inconsistent cross-view cluster membership. HOrizontal Anomaly Detection (HOAD) [Gao et al., 2011] pioneers this branch of methods. In HOAD, the author first constructs a combined similarity graph based on the similarity matrices, and computes the key eigenvectors of the graph Laplacian of the combined matrix. Then anomalies are identified by computing cosine distance between the components of these eigenvectors. This idea is further studied by [Marcos Alvarez et al., 2013] and [Liu and Lam, 2012] for different application tasks. Another successful group of methods is developed from a perspective of data representation [Li et al., 2015; Zhao and Fu, 2015; Li et al., 2018a]. The intuition in these works is that a normal sample usually serves as a good contributor in representing the other normal samples while the outliers do not. Low-rank matrix recovery is the technique which can exploit the intrinsic structure of data and explore the representation relationship of samples. Therefore, by calculating the representation coefficients in low-rank matrix recovery, the multi-view outliers can be identified. In addition, [Iwata and Yamada, 2016] utilizes a sophisticated statistical machine learning algorithm to detect anomalies. They design a probabilistic latent variable model to infer the consistent or inconsistent characteristics of multiple views for each object.

We note that above detection methods are unsupervised and transductive. In some applications, however, one can often get plenty of labeled normal data (e.g., one can collect or simulate normal network traffic data for a certain period of time). In these cases, it is natural to hypothesize these data will enable the detector to better capture normal behavior than unlabeled data. In addition, when an unseen testing instance arrives, above methods have to add it to the existing training set and rerun the detection algorithm (e.g., clustering or matrix factorization), which often causes inefficiency.

To lift above limitations, in this paper we propose a novel Bayesian model for semi-supervised multi-view anomaly detection. To be specific, we first present a generative model for normal data, assuming that different views of a normal instance are generated from a single latent factor through different projection matrices; and the views are independent conditioned on the factor [Blum and Mitchell, 1998; Dasgupta et al., 2002]. Then we build a hierarchical Bayesian model, by first assigning priors on model parameters and then assigning priors over the priors. In particular, we assign the automatic relevance determination (ARD) prior [Neal, 2012] on the projection matrices to sparsify their columns for automatically determining the dimension of latent factor; we also place Student's t distributions on the latent factor prior and the likelihood to improve robustness of the estimator [Archambeau et al., 2006; Gai et al., 2008]. Finally, we employ variational inference to derive an analytical approximation to the posterior probability (of unobserved variables and parameters) of model. To detect multi-view anomalies, we propose to measure the outlier score by calculating the value of log marginal distribution of multiple observed views.

The contributions of this paper are summarized as: 1) To the best of our knowledge, this paper is the first attempt to detect multi-view outliers under semi-supervised scenario via a Bayesian model of inductive learning. 2) In theory, we proves the proposed estimator approaches the true model at a rate of O( ∑v dvm0 log(∑v dv N) N ), and under mild conditions we derive a first sample complexity of O( 1 ϵ2 γ 2 (V 2 lnV +ln 1δ )) for a multi-view anomaly detector to achieve detection rate ϵ. 3) we experimentally evaluates the proposed method on both synthetic and real-life multi-view data. The competing results demonstrate the effectiveness of our model.

The rest of this paper is organized as follows. In Section II, we introduce basic notations; in Section III, we present the proposed Bayesian multi-view anomaly detection model; in Section IV, we theoretically analyze the model; in Section V, we show experimental results and discussions; in Section VI, we conclude the study.

2 Preliminaries and Problem Setup

Before going further, we explain some preliminary knowledge and notational conventions used throughout the paper.

To clarify, in anomaly detection applications, the term semi-supervised detection has been widely used to describe the scenario in which AD methods only incorporate the use of labeled normal samples to learn a model that compactly characterizes the "normal" class [Chalapathy and Chawla, 2019; Akcay et al., 2018; Chandola et al., 2009; Blanchard et al.,

2010; Mu˜noz-Mar´ı et al., 2010; Song et al., 2017]. However, there are a few works [Das et al., 2016; Siddiqui et al., 2018; G¨ornitz et al., 2013] having investigated the general semisupervised setting where one also utilizes unlabelled data. In this work, we stick to the first AD setting.

Following the definition used in [Li et al., 2018a], there are three kinds of outliers in multi-view setting. As shown in Figure 1, Class-outlier is an outlier that exhibits inconsistent characteristics (e.g. cluster membership) across different views. Attribute-outlier is an outlier that exhibits consistent abnormal behaviours in each view. Class-Attribute-outlier is an outlier that exhibits class outlier characteristics in some views while shows attribute outlier properties in the other views. Suppose we are given a data set D which consists of N instances, denoted by n = 1, 2, ...,N, described by V views with each view v = 1, 2, ..., V . The feature representation of instance n under view v is xvn ∈ Rdv , where dv is the dimensionality of view v. Xv = [xv1 , xv2 , ..., xvN ] ∈Rdv×N is sample set observed in view v. In this way, the whole data set is denoted as D = {X1 ,X2 , ...,XV }. Then, the multiview anomaly detector computes an anomaly score for each instance and compares it to a threshold ˆ τζ for finding the outlier in multi-view setting.

3 BayesianMuli-ViewAnomaly Detector

In this section, we illustrate the proposed probabilistic model together with its estimation and the outlier score calculation.

3.1 Generative Process

To link the multiple views x1 , x2 , ..., and xV together, we introduce a common latent variable z. The intuition here is that: generally, an normal instance can be sufficiently described by a single view for learning tasks. Therefore, it is reasonable to suppose that these different views share some common features or latent structure, then the problem is how to build a framework to learn these common structure or the correspondence between observed views and the unobserved space. To explore it, we proposed a probabilistic model which describes the generative process of multi-view instances whose views are linked via a single, reduced-dimensionality latent variable space. Specifically, We assume x1 , x2 , ..., and xV are generated from z by first choosing a value for the latent variable z and then sampling observed variables conditioned on this latent value. The d1 , d2 , ..., dV -dimensional observed vectors x1n , x2n , ..., xVn are defined by a linear transformation governed by the matrix Wv ∈ Rdv ×m of the latent vector z ∈ Rm plus a projection noise ϵv ∈ Rdv , so that

where µv ∈ Rdv is the data offset.

3.2 Model Specification

In the following, we introduce the probabilistic formulation, assign prior distribution on latent variables and parameters in Eq. (1), and assign priors on the priors. Specifically, we define Student's-t prior distribution over the latent variable z

In Eq. (2), we adopt Student's-t distribution's equivalent form according to [Liu and Rubin, 1995; Archambeau et al., 2006]. u > 0 is a latent scale variable. Its Gamma prior p(u) and the associated Gaussian condition p(z|u) are defined as:

Similarly, noise ϵv is a dv dimensional zero-mean Student's-t variable with precision Ψv and degree of freedom ν

By the property of affine transformation of random variable, combining (1), (2), (3) and (4) gives the conditional distributions of observed variables xv

Next, we place priors on parameters Wv, µv and Ψv. Let wvi ∈Rm be the ith row of Wv, we first employ ARD prior onWv to automatically sparsify its columns

Then we parameterize the distributions over µv and Ψv by defining

where W(Ψv|K-1 v , νv) ∝ |Ψv| (νv-dv-1) 2 exp(- 1 2 T r(KvΨv )) denotes Wishart distribution. Finally, we complete the specification of priors (ν,αv) over prior distributions of variables u and wvi respectively

where αv controls the magnitude of Wv. If certain αvj is large, the jth column of Wv will tend to take value zero and become little importance.

The graphical representation of Bayesian model over a data set of N instances is illustrated by Figure 2 in which arrows represent conditional dependencies between random variables. Since we have no further knowledge about the hyperparameters of priors, we choose broad ones by setting aα = bα = βv = 10-3 , Kv = 10-3 Idv , νv = dv + 1, aν = 2 and bν = 0.1, m = min{dv - 1; v = 1, . . . , V }.

3.3 Model Inference

The goal of model inference is to learn posterior distributions of latent variables and parameters. Based on Figure 2, the joint probability of data set D, latent components Z = {z1, . . . , zN}, U = {u1, . . . , uN}, and parameters Θ = {{Wv, αv, µv, Ψv}Vv=1 , ν} can be written as

It is analytically intractable to derive the posterior distribution p(Z,U,Θ|D) from Eq. (10) directly. Therefore, we adopt variational inference for approxiamting the posterior by a facterized distribution

The distribution q is found by maximizing the lower bound

Since log p(D) is constant, maximizing the low bound is equivalent to minimizing the KL divergence between q(Z,U,Θ) and p(Z,U,Θ|D). By substituting factor distributions in Eq. (11) into (12) and dissecting out the dependence on one of the factors ql(Ωl), we have following result

where Ω = {{zn, un}Nn=1 , {Wv , {αvj }mj=1 , µv , Ψv}Vv=1 , ν} refers all latent components and parameters of model, E·[·] represents an expectation w.r.t. distribution qk(Ωk) for all k ̸= l. Combining (13), (10) with the distributions defined in section 3.2, we obtain the following factor distributions

where M,:i is the ith column of matrix M, 〈·〉 denotes the expectation, and we use Stirling's approximation Γ(x) ∼ √2π exp(-x)xx- 12 for log (Γ(ν/2)) when deriving the factor q(ν). The equations (14-24) represent a set of consistency conditions for the maximum of the lower bound subject to the factorization constraint. We can find an optimal solution by first initializing all qk(Ωk) properly and then cycling through the factors and re-estimating each distribution in turn using the updated moments of other factors. We monitor the convergence of optimization by evaluating the lower bound.

3.4 Outlier Score Measurement

The distribution p(x1 , ..., xV ) of V -view observed variable (x1 , ..., xV ) is expressed, from the sum and product rules of probability, in the form

by integrating out z and u, it gives a Student's-t distribution for p(x1 , ..., xV ), where

and Λ(W,Ψ) is a ∑v dv -by-∑v dv precision matrix

From Eq. (12), we know that the log marginal likelihood can be approximated by the evidence lower bound (ELBO).

Through maximizing the ELBO, we find an optimum estimate of the data distribution. According to theorem 1 in section 4.1, this estimated distribution is close to the real model distribution with theoretical guarantee. Since all parameters of estimated data distribution are learned on the normal sample, thus it reasonably concludes that normal instance will have bigger value in Eq. (25). By this insight, we formulate the outlier score s(xi) of an instance xi = [x1i ; x2i ; . . . ; xVi ] as the negative unscaled Student's-t density

Conceptually, a negative outlier score measures the probability that the sample is generated from the multi-view distribution defined by normal data, therefore bigger value in Eq. (28) means this sample is less likely to be the normal class.

4 Theoretical Analysis

In this section, we show theoretical analysis for the proposed model (Due to space limitation, detailed proofs are omitted).

4.1 Consistency of the Bayesian Estimator

Let XNV := {{xvn }Vv=1 }Nn=1 be a sample of i.i.d multi-view random variables collected from distribution p0. We consider statistical models Mm = {pθm |θm ∈ Θm} with the countable collection {Mm|1 ≤ m ≤ min{dv ; v = 1, . . . , V }}, where Θm is the parameter set associated with m latent components model. Let F +(Θm) be the set of all possible distributions over Θm. Now we assume that there exists a true modelMm0 that contains the true data distribution pθ∗m0 (i.e., there exists m0 and θ∗m0 ∈ Θm0 satisfying p0 = pθ∗m0 ).

Assumption 1. There exists g(N) for which there is a distribution ρm0,N,V ∈ F +(Θm0 ) such that

where πm0 (·) on θm0 ∈ Θm0 is a prior over model Mm0 . Theorem 1. Given assumption 1, for any α ∈ (0, 1), if there exists a true model Mm0 such that p0 = pW∗m0 and the coefficients of W∗m0 = [W∗ 1,m0 ; W∗ 2,m0 ; . . . ;W∗V,m0 ] ∈ R∑ dv ×m0 are bounded, then

where ˆπm α,N,V (Wm|XNV ) is the approximate posterior distribution derived by variational inference.

From Eq. 31, we see that, in expectation w.r.t the random variables XNV under distribution pW∗m0 , the average αRenyi loss (Dα) [Van Erven and Harremos, 2014; Ch´eriefAbdellatif, 2018] between a distribution in the selected model and the true distribution over ˆπm α,N,V (Wm|XNV ) goes to zero as n → +∞. This shows the Bayesian estimator of our model is consistent.

Algorithm 1 Compute Optimal Threshold

Input: Data {X , X ′ }, Swapping Rate γ, Detection Rate ζ Output: Detection Threshold ˆ τζ

• 1: Generate mixture set X γ via swapping views randomly.
• 2: Compute anomaly scores for all points in X and X γ via Eq. (28), and denote them as S and S γ respectively.
• 3: Calculate empirical CDF ˆ Fa.
• 4: Optimize threshold by

4.2 Sample Complexity of Multi-ViewDetector

Let {X,X ′ } be two "clean" nominal sets (both containing k i.i.d. multi-view draws from p0). We take X as training input. For X ′ , given a swapping rate γ, we use it to generate a 'mixture' dataset X γ . In this case, the mixture data X γ can be approximately treated as k points drawn from a mixture distribution pγ , which generates a multi-view outlier and nominal point with probability 2γ and 1-2γ respectively. Our multi-view semi-supervised anomaly detector is trained on X and assigns anomaly scores to all data points in X and X γ . Intuitively, an ideal detector would rate all alien data points higher than all nominals (higher score means more anomalous). The key challenge in practice is to select a threshold for anomaly score that gives the guarantee on achieving the desired outlier detection rate. Motivated by [Liu et al., 2018], our approach to obtaining a theoretical guarantee is based on considering the cumulative distribution function (CDF) over anomaly scores.

Let ˆ F and ˆ Fγ be the empirical CDFs of anomaly scores of samples from p0 and pγ respectively. The empirical CDF for an abnormal sample can be derived as ˆ Fa(s(x)) = ( ˆ Fγ(s(x))-(1-2γ) ˆ F(s(x)))/2γ. With sufficient data and knowledge of γ, empirical CDFs ˆ F, ˆ Fγ and ˆ Fa will convergence to the ground truth F, Fγ and Fa. After deriving Fa, a detector can achieve an outlier detection rate of ζ by selecting an anomaly score threshold τζ that is the 1-ζ quantile of Fa and raises an alarm on the testing point whose anomaly score is greater than τζ. Alg. 1 summarizes the steps for finding a reasonable threshold achieving the desired outlier detection.

Theorem 2. Let X and X ′ be the nominal data sets containing k i.i.d V-view instances drawn from distribution p0. Given a swapping rate γ, let X γ be the mixture set generated from X ′ over the randomness of view selecting and view swapping. For any ϵ ∈ (0, ζ) and δ ∈ (0, 1), if

where 1 g(δ,V ) = 1δ ∑V˜ V =2 V ! ˜ V !(V -˜ V )! ⌊ ˜ V ! e ⌋, ⌊·⌋ is the floor function, and e is Euler's Number, then with probability at least 1 - δ, Algorithm 1 will output a threshold ˆ τζ that achieves an multi-view outlier detection rate of at least 1- η, where η = 1 - ζ + ϵ.

Theorem 2 provides a value for the sample size k that guarantees at least ζ - ϵ fraction of outliers in the test points

(c) Class-Attribute Outlier

Figure 3: The variation curves of AUC W.R.T outlier ratio.

will be detected (an additional error term ϵ is introduced here because of the finite sample size). By using Stirling's formula for approximating factorials (e.g. ˜ V !, (V - ˜ V )!), above guarantee is approximately polynomial since k grows as O( 1 ϵ2 γ 2 (V 2 lnV +ln 1δ )). We believe theorem 2 is the first PAC-style guarantee for multi-view anomaly detection.

5 Experimental Evaluations

We now show the effectiveness of proposed method on public Outlier Detection Datasets (ODDS) 2 , WebKB dataset 3 and MovieLens dataset 4 . We compared the proposed model with representative and cutting edge multi-view anomaly detectors: HOrizontal Anomaly Detection (HOAD) [Gao et al., 2011], Affinity Propagation (AP) [Marcos Alvarez et al., 2013], Probabilistic Latent Variable Model (PLVM) [Iwata and Yamada, 2016] and Latent Discriminant Subspace Representation (LDSR) [Li et al., 2018a]. For AD problems, the most widely used performance evaluation metrics are ROC curve and AUC score.

5.1 Evaluation on Synthetic Multi-View Settings

We employ 9 data sets, namely thyroid, annthyroid, forestcover, vowels, pima, vertebral, lympho, wine and glass, which are obtained from the ODDS library [Rayana, 2016]. We generate multiple views by randomly splitting the features, where each feature can belong to only one view. To generate three types of multi-view outliers, we follow the strategy in previous works (e.g. [Li et al., 2018a]) for fair comparison. After the outlier generation stage, we equivalently split all normal instances into two parts, and use one of them as the training set to train the proposed model. Then we verify the outlier detection performance on the test set which consists of the remaining normal data and generated outliers.

2 http://odds.cs.stonybrook.edu

3 http://lig-membres.imag.fr/grimal/data.html

4 https://grouplens.org/datasets/movielens/latest

On each dataset, we repeat the random outlier generation procedure 20 times and at each time, we perturb 2.5% of the data in that procedure. We average their performance and report AUC results (mean ± standard deviation) in Table 1. From table 1, we can observe that the proposed method consistently outperforms all competing counterparts on almost nine data sets for all kinds of multi-view outliers. The superiority of proposed method is expected, because it uses the semi-supervised anomaly detection technique, which can maximally capture the nature and property of normal instances. This, in turn, can help the learned model to better distinguish whether the test instance is normal or not, thus improving the detection performance.

To investigate how the number of outliers affects the performance of different models, we experiment on data corrupted by progressively higher percentages of outliers. The Figure 3 shows the variation of AUCs on data set pima with outlier ratio of 2%, 5%, 10%, 15%, 20%, 25% and 30% for three types of outliers. We see that, in general, as the anomaly rate increases, the performance decreases. And the proposed method is comparatively robust and outperforms other compared ones with all outlier ratio settings.

5.2 Evaluation on Real WorldMulti-ViewData

Further, we compare them on the WebKB dataset [Blum and Mitchell, 1998] which has been widely used for evaluating multi-view learning algorithms [Guo, 2013; Li et al., 2014]. We use its Cornell subset in our experiment. It contains 195 webpages over 5 labels. Each webpage is described by four views: content, inbound link, outbound link and cites. Figure 4 shows the ROC curves of all compared methods on the WebKB dataset with outlier ratio of 5% (left) and 10% (right). We can observe that clearly, our approach achieves higher AUC than its competitors, which demonstrates the strength of our Bayesian detector.

To present the qualitative analysis of Bayesian model in detecting inconsistency between users' rating behavior and movie genre, we apply the proposed model to MovieLens small dataset which contains 100,836 ratings over 9,742

movies by 610 users. We sample 1000 movies, and perform our model to calculate anomalous scores for them. Table 2 lists some movies high and low anomalous scores. Movie 'spirited away' is categorized into animation and fantasy genre, but it receives most of ratings from users that watch and tag action-thriller movies. In other words, it exhibits inconsistent behavior between genre view and rating view, and thus has a high anomalous score. Contrarily, low anomalous score movies, e.g. sacrifice, do not show view inconsistency.

6 Conclusion

In this paper, we offer a novel hierarchical Bayesian model to find multi-view outliers under a semi-supervised detection scenario via inductive learning. We prove our Bayesian estimator is consistent and derive a sample complexity for the detector. In experiment, we show the proposed model consistently outperforms state-of-the-art multi-view anomaly detectors across both synthetic and real-world multi-view data.