Mixture of hyperspheres for novelty detection

The main task in machine learning problems is to find the optimal parameter \(\theta \) of the model given a training set D. In probabilistic perspective, it is described as a maximization of log likelihood function. However, estimating parameters using maximum-likelihood principle is very hard if there are some missing data or latent variables (i.e., cannot be observed). The expectation maximization principle [11], for short EM, was proposed to overcome this obstacle. EM is an iterative method, in which each iteration consists of expectation step (E-step) followed by the maximization step (M-step). The basic idea of EM is described as follows.

Let \(\left\{ x_{n}\right\} _{n=1}^{N}\) be the observed data and \(\left\{ z_{n}\right\} _{n=1}^{N}\) the latent variables; the log likelihood function is given as follows:As can be seen, the log cannot be pushed inside the sum; hence it is hard to find the maximum of \(l\left( \theta \right) \). Instead of finding maximum likelihood, EM involves the complete data log likelihood as follows:In the E-step, the expected complete data log likelihood \(Q\left( \theta ,\theta ^{t-1}\right) \) is computed by formulation as follows:Then, in the M-step, \(\theta ^{t}\) is found by optimizing the Q function w.r.t \(\theta \)

Given the training set \(D=\left\{ \left( x_{n},y_{n}\right) \right\} _{n=1}^{N}\) where \(x_{n}\in \mathbb {R}^{d}\) and \(y_{n}\in \left\{ -1;1\right\} ,\,n=1,\ldots ,N\) including normal (labeled by 1) and abnormal (labeled by \(-1)\) observations. To find the domain of novelty, weighted SVDD [26] learns an optimal hypersphere which encloses all normal observations with tolerances. Each observation \(x_{n}\) is associated with a weight \(C\lambda _{n}\) and a smaller value for the weight implies that the correspondent observation is allowed to have a bigger error. The optimization problem of weighted SVDD is defined as follows:where \(R,\,c\) are the radius and center of the optimal hypersphere, respectively.

It follows that the error at the observation \(x_{n}\) is given asand the optimization problem in Eq. (1) can be rewritten as follows:

Let us denote the latent variable which specifies the expert of \(x_{n}\) by \(z_{n}\in \left\{ 0;1\right\} ^{m}\). The latent variable \(z_{n}\), a bit pattern of size m where only its jth component is 1 and others are 0, means that the jth expert (i.e., the jth SVDD) is used to classify the observation \(x_{n}\). The graphical model of mSVDD is shown in Fig. 1.

In mSVDD, we describe normal data using a set of m hyperspheres denoted by \(\mathbb {S}_{j}\left( c_{j},R_{j}\right) ,\,j=1,\ldots ,m\). Given the jth hypersphere and the observation \(x_{n}\), the conditional probability to classify \(x_{n}\) w.r.t the jth hypersphere is given as follows:where \(s\left( x\right) =\frac{1}{1+e^{-x}}\) is the sigmoid function and \(\theta \) is the model parameter.

Intuitively, \(p\left( \text {normal}\mid x_{n},\mathbb {S}_{j}\right) \) is exactly \(\frac{1}{2}\) if \(x_{n}\) locates at the boundary of the hypersphere \(\mathbb {S}_{j}\) and increases to 1 when \(x_{n}\) resides inside the hypersphere or decreases from 0 when \(x_{n}\) resides outside the hypersphere and moves apart from it. Because it is difficult to handle the log of \(s\left( x\right) =\frac{1}{1+e^{-x}}\) , we approximate \(s\left( x\right) \) as follows:To visually see how tight the approximation is, we plot the above two functions on the same coordinate when \(\delta =1\). As can be seen in Fig. 2, the blue line (presenting function \(\frac{1}{1+e^{-x}}\)) is close to the green line (presenting function \(e^{-\text {max}\left\{ 0;\delta -x\right\} }\)). Therefore, the function \(e^{-\text {max}\left\{ 0;\delta -x\right\} }\) is a good approximation of the sigmoid function \(s\left( x\right) \).

The marginal likelihood is given as: \(p\left( Y|X,\theta \right) =\prod _{n=1}^{N}p\left( y_{n}\mid x_{n},\theta \right) \), where \(X=\left[ x_{n}\right] _{n=1}^{N}\in \mathbb {R}^{d\times N}\), \(Y=\left[ y_{n}\right] _{n=1}^{N}\in \mathbb {R}^{N}\), and \(\theta =\left( \theta _{1},\theta _{2},\ldots ,\theta _{m}\right) \) encompass the parameters of all experts.

To take into account both the general and empirical risks, the following optimization problem is proposed:In the optimization problem as shown in Eq. (4), we minimize \(\sum _{j=1}^{m}R_{j}^{2}\) to maximize the generalization capacity of the model. In the meanwhile, we maximize the log marginal likelihood to boost the fit of the model to the observed data X. The trade-off parameter C is used to control the proportion of the first and second quantities or to govern the balance between overfitting and underfitting.

To efficiently solve the optimization problem in Eq. (4), we make use of EM principle by iteratively performing two steps: E-step and M-step.

We start with the number of hyperspheres \(m=m_{\text {max}}\) and make use of the criterion \(\alpha _{j}^{(t+1)}<\lambda \), where \(\lambda >0\) is a threshold, for decision to eliminate the jth hypersphere. The small value for the mixing proportion \(\alpha _{j}^{(t+1)}\) of the jth hypersphere implies that \(\tau _{j}^{(t)}\) is too small as compared to others. The quantity \(\tau _{j}^{(t)}=\sum _{n=1}^{N}p(z_{n}^{j}=1\mid x_{n},y_{n}=1,\theta ^{(t)})\) is interpreted as the sum of the relevance levels of observations to the jth hypersphere and its small value implies that this hypersphere is redundant and has a too small radius.

In mSVDD, a natural way to classify a new observation x is to examine whether it belongs to at least one of m hyperspheres. The decision function is given as follows:where \(R_{j},\,c_{j}\) are radius and center of the \(j^{th}\) hypersphere, respectively.

The above decision function can be regarded as a hard way to decide the normality or abnormality. To take advantage of the probabilistic perspective of mSVDD, we propose a probabilistic approach to make a decision. This approach decides an observation x as a normal data point if more than k experts (e.g., \(k=0.8m\)) classify it as normal data with a confidence level over \(\rho \), that iswhere the second case means that x is classified as normal if there are more than k experts that predict it as normal with a confidence level over \(\rho \).

According to Eq. (7), M-step requires the solutions of m weighted SVDD problems, each of which requires training the whole training set. It is also noteworthy that the variable \(\tau _{jn}^{(t)}\) governs the influence of data point \(x_{n}\) to the jth hypersphere. A large value of \(\tau _{jn}^{(t)}\) highly affects the determination of the jth hypersphere and vice versa, and a small value of \(\tau _{jn}^{(t)}\) slightly affects the determination of the jth hypersphere. Therefore, the data point \(x_{n}\) with a small value of \(\tau _{jn}^{(t)}\) can be eliminated when training the jth hypersphere without possibly changing the learning performance. In return, the training time of a mixture of SVDDs would be improved because training each SVDD now possibly involves a small subset of the training set. To realize this idea, we define the parameter \(\mu \in \left( 0,1\right) \) as a threshold to eliminate data point \(x_{n}\) in the determination of the jth hypersphere (i.e., \(\tau _{jn}^{(t)}<\mu \)).

We establish the experiments over five datasets.¹

The statistics of the experimental datasets is given in Table 1. To form the imbalanced datasets, we choose a class as the positive class and randomly select the negative data samples from the remaining classes such that the proportion of positive and negative data samples is 10 : 1. We make a comparison of our proposed mSVDD with ball vector machine (BVM) [22], core vector machine (CVM) [23] and support vector data description (SVDD) [21]. All codes are implemented in C/C++. All experiments are run on the computer with core I3 2.3GHz and 16GB in RAM.

We do experiments to investigate the performance of our proposed mSVDD in the input space compared with BVM, CVM and SVDD in the feature space with RBF kernel, named KBVM, KCVM, and KSVDD, respectively. To prove the necessity of mSVDD, we also compare mSVDD with CVM using the linear kernel (i.e., LCVM). We wish to validate that with mixture model dataset, a single hypersphere offered by LCVM cannot be sufficiently robust to classify it. We apply fivefold cross-validation to select the trade-off parameter C for KBVM, LCVM, KCVM, KSVDD, mSVDD and the kernel width parameter \(\gamma \) for KBVM, KCVM and KSVDD. The considered ranges are \(C\in \left\{ 2^{-3},2^{-1},\ldots ,2^{29},2^{31}\right\} \) and \(\gamma \in \left\{ 2^{-3},2^{-1},\ldots ,2^{29},2^{31}\right\} \). With mSVDD and LCVM, the linear kernel given by \(K\left( x,x'\right) =\left\langle x,x'\right\rangle \) is used, whereas with kernel versions, the RBF kernel given by \(K\left( x,x'\right) =e^{-\gamma \Vert x-x'\Vert ^{2}}\) is employed. It is certainly true that the computation cost of the linear kernel is much lower than that of the RBF kernel. We fix \(\delta =0\) in all experiments; then in Sect. 5.4 we will investigate the behavior of mSVDD when \(\delta \) is varied. We repeat each experiment five times and compute the means of the corresponding measures. We report training times (cf. Table 5 and Fig. 3a), the one-class accuracy (cf. Table 2 and Fig. 3b), the negative prediction values (NPVs) (cf. Table 3 and Fig. 3c) and \(F_{1}\) score (cf. Table 4 and Fig. 3d) corresponding to the optimal values of C, \(\gamma \).

In addition, the one-class accuracy is computed by \(acc=\frac{\%TP+\%TN}{2}=\frac{acc^{+}+acc^{-}}{2}\). This measure is appropriate for one-class classification, since it is required to achieve high values for both \(acc^{+}\) and \(acc^{-}\) to produce a high one-class accuracy. The negative prediction values (NPVs) are computed by \(NPV=\frac{TN}{TN+FN}\). This formulation indicates that a less number of false negative (FN) produces a higher value of NPV. \(F_{1}\) score is the harmonic mean of precision and recall and is computed by \(F_{1}=\frac{2.precision.recall}{precision+recall}\) where \(precision=\frac{TP}{TP+FP}\) and \(recall=\frac{TP}{TP+FN}\). \(F_{1}\) score can be rewritten as \(F_{1}=\frac{2.TP}{2.TP+FP+FN}\) which shows that a higher value of \(F_{1}\) score is caused by a less number for both false negative and false positive.

To visually support the above reason, we design experiments on 2-D datasets as displayed in Figs. 4 and 5. In Fig. 4, mSVDD recommends two hyperspheres in the input space to approximate two contours formed by a single hypersphere in the feature space. In Fig. 5, mSVDD offers three simple hyperspheres which can be visually seen to sufficiently simulate the set of contours formed by a single hypersphere in the feature space. The results of LCVM in all cases are worse, because it learns a single hypersphere in the input space which cannot sufficiently represent the contours formed by a single hypersphere in the feature space.

We empirically compare mSVDD with its two variations which are approximate approach (amSVDD) and probability approach (pmSVDD). In amSVDD, we use the threshold \(\mu =0.8\) to eliminate data points for reducing training size in each SVDD problem. Our pmSVDD applies probability perspective and allows experts to vote when predicting new data. We set the parameter k to 2 and the parameter \(\rho \) to 0.8. Tables 6, 7 and Fig. 6 summarize the performance measures of mSVDD, amSVDD, and pmSVDD. The results show that pmSVDD achieves higher accuracies on all datasets, except mushroom, in comparison to mSVDD. This demonstrates that the probability approach really improves mSVDD by allowing a voting scheme and using probabilistic perspective. For amSVDD, its training time is usually less than others in all datasets, except a9a. Obviously, it comes from the reasonable reduction in training size of each SVDD problem at each step. This allows amSVDD to run faster than others while still preserving the accuracy.

To analyze how parameter \(\delta \) affects the one-class accuracy and negative prediction value, we conduct the experiment where \(\delta \) is varied and other parameters are kept fixed. As observed from Tables 8 and 9, when \(\delta \) is varied in ascending order, the accuracy at first increases to its peak and then gradually decreases. This fact may be partially explained as \(\delta \) is altered and also changes the probability function of the observed data to classify them with respect to a particular hypersphere. When \(\delta \) decreases, the component hypersphere tends to absorb more data outside it and, consequently, the hypersphere becomes bigger. Therefore, some abnormal data points can be misclassified. Reversely, the component hypersphere tends to be smaller and would not give a very high probability to data located inside the hypersphere and near the boundary. This prevents the model from misclassifying abnormal data points, but have the side effect of increasing the misclassification of normal data.

To visually manifest the above reason, we also provide simulation study on \(2-D\) datasets, as displayed in Fig. 7. When we set \(\delta =-0.5\) and start with 3 hyperspheres, the hyperspheres tend to become bigger; as a result, two of them overlap each other. In the meanwhile, we increase \(\delta \) to 1 and get a better solution which induces \(90~\%\) one-class accuracy. However, if we continue to increase \(\delta \) to 12, the hypersphere is too small to describe normal data and, thus, the one-class accuracy declines to \(88.75~\%\).