Deep Anomaly Detection and Search via Reinforcement Learning

In RL, the agent is asked to interact with the environment to deal with a sequential decision-making problem. At each time step $t$, the agent is capable of sensing the state $s_t$ from the environment and then selects an action $a_t$ according to policy $\pi \left(a|s\right)$, given the state $s=s_t$. The chosen action is passed to the environment and executed, which causes a transition to a new state $s_{t+1}$ and a scalar reward $r_t$. The interaction continues until the task terminates. The objective of RL is to train such an agent to maximize the expected discounted cumulative rewards (a.k.a. return) $E_{\pi }\left[{\sum }_t{\gamma }^t{r}_t\right]$, where $\gamma \in (0,1]$ is the discount factor.

The standard RL can be formalized as a Markov decision process (MDP). It can be defined as a 4-tuple $⟨S,A,R,P⟩$, where $S$ denotes state space; $A$ denotes action space; $R$ denotes reward function $S\times A\to R,R(s,a)=E[r_t|s_t=s,a_t=a]$; and $P$ denotes transition function $S\times A\times S\to [0,1]$, $P(s,a,s^{\prime })=p(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$. The whole process can be expressed as a trajectory: $\tau =(s_0,a_0,s_1,a_1...s_T)$, which obeys an implicit probability distribution determined by transition dynamics and policy $\pi$: $p_{\pi }\left(\tau \right)=p\left(s_0\right){\prod }_{t=1}^T\pi \left(a_{t-1}|s_{t-1}\right)p(s_t|s_{t-1},a_{t-1})$. The optimization decision problem can be formalized as:

where $r\left(\tau \right)={\sum }_t{\gamma }^t{r}_t$ is the sum of discounted rewards.

Deep reinforcement learning (DRL) refers to algorithms that combine RL with deep learning. According to the difference in target network, it can be divided into three categories: value-based, policy-based, and actor-critic algorithms.

Value-based methods use the estimated Q-value to select action. DQN Mnih et al. (2013, 2015) is a classical value-based method. It combines deep learning with Q-learning, and uses a neural network to estimate Q-value. Experiments on Atari show that it can achieve human-level performance, which is a great success. After that, there are many works trying to make improvements, including double DQN Mnih et al. (2016), dueling DQN Wang et al. (2016), etc.

Policy-based methods directly model the relationship between state and optimal action. REINFORCE Williams (1992) is a representative of this category, which uses the Monte-Carlo method to sample trajectories and update parameters. Improved methods include adding a baseline to reduce variance.

Actor-critic methods combine the above two categories. They use actor network and critic network to learn policy function and value function respectively, which can effectively reduce variance and speedup training. Actor-critic Konda and Tsitsiklis (1999) is the most basic method, and by adding baseline we can get the A2C method. A3C Mnih et al. (2016) applies parallel training on the basis of A2C. TRPO Schulman et al. (2015) introduces importance sampling and trust domain constraint in policy update. PPO Schulman et al. (2017) substitutes KL-divergence constraint in TRPO with clipping, which effectively improves its performance. The soft actor-critic (SAC) Haarnoja et al. (2018) method effectively improves the robustness of the algorithm by introducing entropy regularization and dueling Q-network. In this paper, we use SAC as the RL algorithm.

Given a training dataset $X=\{x_1,x_2,\cdots ,x_N\}$, AD aims at learning a feature representation mapping function $\tau (\cdot ):X\mapsto Z$ or an anomaly scoring function $\varphi (\cdot ):X\mapsto R$ in a way that anomalies can be easily differentiated in the subspace of $\tau$ or $\varphi$, where $Z\in R^K(K\ll N)$ denotes representation space. Since AD focuses on rare and irregular events, it faces many challenges including unknownness of anomalies, class imbalance, various types of anomalies, etc Pang et al. (2021a). According to the amount of known data, AD can be divided into three categories: supervised, semi-supervised, and unsupervised Ruff et al. (2021). Unsupervised AD is the most studied category, many works have been done in this area, including Isolation Forest Liu et al. (2008), Histogram-based Outlier Score Goldstein and Dengel (2012), One-Class SVM Schölkopf et al. (2001), NCAE Yu et al. (2021b), etc. Most supervised AD methods are classification methods Ruff et al. (2021) including XGBoost Chen and Guestrin (2016), VIME Yoon et al. (2020), etc.

In this paper, we focus on semi-supervised tabular AD problems, where both unlabeled samples and a small portion of the labeled anomalies and labeled normal samples are available during training Ruff et al. (2021). Generally, semi-supervised AD methods can be classified into supervised-based and unsupervised-based categories Görnitz et al. (2013).

On top of the supervised learning paradigm, supervised-based semi-supervised AD methods add a bias term to describe the data characterization based on some assumptions, e.g., the cluster assumption Chapelle et al. (2009), in the loss function Pang et al. (2019). Their performance relies heavily on the consistency between the distribution of datasets and the assumptions. The mentioned DPLAN is this method.

On the other hand, unsupervised-based semi-supervised AD methods extend the unsupervised AD methods by exploiting labeled data as a regularization term in the loss function Görnitz et al. (2013); Ruff et al. (2019). A recent work Chang et al. (2022) extends the explainable $G{A}^{2}M$ model to the AD method with the Partial IDentification (PID) objective Gopalan et al. (2019), and a differentiable AUC loss is added to incorporate labeled data. These methods also exist problems like weak robustness to data contamination, insufficient exploration of unlabeled data, etc.

Figure 1 is an illustration of DADS, which is mainly composed of two parts: a SAC-based agent and an anomaly search environment. To apply RL, we must first transform the training dataset into a data flow environment where key components of RL are clearly defined.

• State space is the whole training dataset $D=\{D^a,D^u\}$, with each $s_t\in D$ sampled at timestep $t$ be a state.

• Action space is a continuous space within range $[0,1]$, with value corresponding to anomaly score of input data.

• Environment has its own inner dataset, and a single piece of data will be sampled as the state in each training step. When receiving the action of the agent, its inner dataset will make adjustments to its inner dataset according to a series of rules and calculate the reward.

• Agent takes the current data as input, uses its inner network to calculate the corresponding action (the anomaly score of the input data), and returns it to the environment.

In the design of the agent, we use the RL algorithm SAC, which adds an extra entropy term to the original target of RL, i.e., maximizing the expected cumulative rewards, and thus its objective function becomes: $J\left(\pi \right)={\sum }_{t=0}^T{E}_{(s_t,a_t)\sim {\tau }_{\pi }}{\gamma }^t[r(s_t,a_t)+\alpha H(\pi (\cdot \mid s_t))]$, where $\pi$ is represented as a policy network, $(s_t,a_t)$ is a state-action pair within trajectory ${\tau }_{\pi }$ generated by policy $\pi$, $H\left(\pi (.\mid s_t)\right)$ is the entropy term which evaluates the uncertainty of policy $\pi$, and $\alpha >0$ is the trade-off coefficient.

To find the optimal policy, SAC uses $\pi \left(\theta \right)$ to approximate policy function, uses $q(s,a;{\varphi }_i),i\in \{1,2\}$ to approximate action-value function, and uses $v(s;\psi )$ and $v(s;\overline{\psi })$ to estimate state-value function. The way of updating each network is listed in Appendix A. After training, we get ${\pi }^{\ast }\left(\theta \right)$. For every single data $s$, ${\pi }^{\ast }(s;\theta )$ is used as anomaly score.

We emphasize that the entropy term of the objective function in SAC is of great help to the anomaly search of DADS, since the agent is encouraged to take different actions and thus discover more possible anomalies. This entropy regularization, together with the sampling function of DADS, contributes to the search mechanism of DADS.

The environment design of DADS is divided into the following three parts.

• Hierarchical datasets tailored for anomaly search: The training dataset is separated into three parts and multi-stage screening is used to search for possible anomalies.

• Ensemble-based sampling function: Ensemble learning is adopted to integrate different unsupervised AD methods.

• Reward function for AD: The agent receives a reward combining both supervised and unsupervised rewards.

As stated above, DADS uses a hierarchical search to find anomalies in the unlabeled dataset, and we believe that such a search mechanism is the key to solving the challenges proposed at the beginning of the paper. To be specific, DADS features in the following three aspects.

• Strong robustness to contamination: When the agent searches for possible anomalies in unlabeled dataset, it is also cleaning it. In addition, the reward function of DADS is designed in a simple way that it does not include any prior assumption of the unlabeled dataset. Considering the above two points, it can be predicted that DADS will be robust to the contamination of unlabeled dataset.

• High search efficiency and accuracy: On one hand, DADS borrows the idea of ensemble learning to improve the accuracy of search. Before a possible anomaly in $A$ is finally added into A, it needs to be classified as an anomaly by the agent for $T{H}_{conf}$ times. Notice that the agent is continuously updated, the $T{H}_{conf}$ times judgment is actually an integration of the results of different agents. On the other hand, DADS combines different unsupervised methods in its sampling function to improve search efficiency, while the entropy term of SAC also plays a role in improving it.

• Nice balance of exploration and exploitation: With the help of RL, the whole training process of DADS integrates exploring unlabeled dataset and exploiting labeled anomalies in a natural way, which solves the exploration-exploitation dilemma automatically.

To make a comprehensive comparison between DADS and other methods, we choose $5$ datasets with single anomaly class and $3$ datasets with multiple anomaly classes. The former $5$ of datasets are used in experiments of scenario $1$, with dimension ranging from $6$ to $36$ and anomaly percentage ranging from $1.2\%$ to $31.6\%$. Detailed information are in Table S3 of Appendix B. To further compare DADS with baselines, scenario $2$ is designed using $3$ datasets with multiple anomaly classes, of which size ranging from thousands to tens of thousands and dimension ranging from $9$ to $561$. Detailed information are in Table S4 of Appendix B. The last column indicates whether the corresponding class is known or not. If the anomaly class is known, it will appear in both anomaly dataset and unlabeled dataset, else it only exists in unlabeled dataset.

The mentioned datasets serve as base pool of our experiments. We set two adjustable parameters, namely anomalies ratio and contamination ratio. Anomalies ratio corresponds to the ratio of known anomalies to total anomalies (in scenario $2$ total anomalies means anomalies of the known anomaly class); contamination ratio corresponds to the percentage of anomalies in unlabeled data.

We stratified split each dataset into training set, validation set and testing set, each accounting for $60\%$, $20\%$, and $20\%$ of the total dataset with $10$ different random seeds. validation set and testing set are fixed after splitting, so the percentage of each class is consistent with original dataset. Training dataset is manually generated according to the above two adjustable parameters: anomalies ratio and contamination ratio, and, as stated before, it is composed of $D^a$ and $D^u$. In particular, DADS will search for optimal training episodes on validation set, SSAD and XGBoost will also tune on validation set. Detailed information are in Appendix B.

We select Area Under Receiver Operating Characteristic Curve (AUC-ROC) as the evaluation metric, which measures the area under ROC curve. The reported AUC-ROC are average results over 10 different random seeds.

We select SSAD Görnitz et al. (2013), Deep SAD Ruff et al. (2019), DevNet Pang et al. (2019), XGBoost Chen and Guestrin (2016), STOC Yoon et al. (2021), DPLAN Pang et al. (2021b), and Isolation Forest Liu et al. (2008) as baselines. SSAD and Deep SAD are all based on SVDD Ruff et al. (2018), which use hypersphere to envelop the anomalies in the embedding space. According to experiments in Deep SAD, SSAD and Deep SAD are both state-of-the-art semi-supervised AD methods. Notice that here we use the improved version of Deep SAD called Hypersphere Classification (HSC) Ruff et al. (2020), which is about $1.5\%$ better than the original Deep SAD. DevNet introduces deviation loss and combines it with supervised loss to train an end-to-end anomaly scoring network. We combine the data-driven STOC method with both Isolation Forest and self-supervised representation learning method GOAD Bergman and Hoshen (2020). We reproduce DPLAN and include it in our baselines, considering that the distance calculation step in DPLAN is time-consuming, we decrease the sampling size from 1000 to 100. Finally, to make a comprehensive comparison, we also consider XGBoost and Isolation Forest, while XGBoost and Isolation Forest are classical supervised and unsupervised methods, respectively.

In this scenario, we use $5$ datasets with single anomaly class to compare DADS with baseline methods. As stated above, there are two adjustable parameters: anomalies ratio and contamination ratio, we will fix one at a time and adjust another. The results of these two groups of settings are as follows. Detailed graphic results are shown in Appendix C, below we only list some processed results.

The above experiments on datasets with single anomaly class shows the advantage of DADS in both the exploration of unlabeled dataset and robustness to contaminated data. For further verification, we conducted similar experiments on datasets with multiple anomaly classes. For each dataset, we set one anomaly as the known anomaly class while leave others as unknown. We believe that the tasks in this scenario will be more difficult and can better show the advantages of DADS. Same as above, detailed results are in Appendix C.

From the results of experiments conducted on two scenarios, we can summarize several empirical results.

• DADS vs. DPLAN: We think it is necessary to make a comprehensive comparison between DADS and DPLAN, since they are all AD methods based on RL. According to the experiment results, DADS outperforms DPLAN in all two scenarios. To be specific, settings 1.1 and 1.2, especially datasets like cardio, satimage2, and multi-har prove the superiority of robustness of DADS to contamination. In settings 1.2 and 2.2, DADS outperforms DPLAN when only small amount of labeled anomalies is known, which should give credit to the SAC algorithm and the search mechanism that avoid the problem of DPLAN that only searches locally. Another advantage of DADS is that it removes the distance-based sampling strategy of DPLAN, thus accelerating training to a large extent.

• DADS vs. unsupervised/supervised/semi-supervised AD methods: According to the experiment results, we can also make a comparison between DADS and different kinds of AD methods. First of all, compared with unsupervised methods like Isolation Forest, STOC+IForest, and STOC+GOAD, DADS has advantages in settings 1.2 and 2.2 since it can search and exploit unknown anomalies.

  Secondly, though supervised methods like XGBoost achieve quite good results in some datasets like annthyroid, it cannot keep the advantage on all datasets, while the performance of DADS is relatively stable across different datasets. When the aomunt of known anomalies is extremely small(e.g. 1%), DADS also performs better than supervised methods, which can be verified in Figures S5 and S7 of Appendix C.

  Lastly, compared with semi-supervised methods like DPLAN, DeepSAD, SSAD and DevNet, DADS outperforms them in all four settings. Figures S4 and 2 of settings 1.1 and 2.1 indicates that DADS is more robust to data contamination, especially when compared with supervised-based methods like DPLAN. In settings 1.2 and 2.2, different from unsupervised-based methods like SSAD and Deep SAD that reach performance plateau prematurely, DADS can maintain synchronous performance growth with the increases of known anomalies, which shows stronger ability in utilizing supervision signals.

To identify to what extent the search mechanism helps, we remove the search mechanism of DADS and leave other components unchanged, that is to say, no anomalies will be found and added into the anomaly dataset $A$. Experiments of settings 2.1 and 2.2 are conducted on original DADS and DADS without search. We plot the result on multi_cardio dataset with line chart, which can demonstrate the advantage of DADS well. For detailed results of experiment, please refer to Tables S7 and  S8 of Appendix D.

The training and inference procedures of ADAS are illustrated in Algorithms S1 and S2.

The experiment results are shown in Figures  S4$\sim$S7.

Tables S7 and  S8 respectively summarize the results of ablation study on settings 2.1 and 2.2.