Recently, a wide variety of machine learning methods have been brought to bear on forecasting and anomaly detection in numerical time series, including Arima models [7], neural networks [11, 6] and statistical methods  [12, 8]. These methods can often be made to accommodate categorical data through one-hot encoding, but in the authors’ experience quality of models in this family rapidly degrades as the fraction of the series’ variables that are categorical increases. The field in which anomaly detection in categorical time series is most developed in is intrusion detection in network security and fraud detection [9, 4]. The authors in [9] utilize a transformer architecture for fraud detection inspired by an analogy between finite sequences of discrete variables and words in the domain of Natural Language Processing (NLP).

In this paper, we formalize and extend the analogy of multivariate categorical time series to classical concepts in NLP in a way well-suited to anomaly detection in multivariate time series arising from telemetry streams. We design, implement and test three anomaly detection and root cause investigation models based on this analogy. One benefit of our formalization over methods in the current literature is its explainability in terms of an easy ranking of the variables in order of their apparent contribution to a suspected anomaly. A second benefit is that current categorical time series anomaly detection algorithms in the literature are focused on settings with relatively few sensors, and our framework enables construction of models managing large sensor sets, as demonstrated by our results in Section 8.

The remainder of the paper up to the conclusion is organized as follows. In Section 2 we develop the NLP analogy for categorical time series. In Sections 4, 5 and 6 we present and test three anomaly detection and root cause identification models based on this analogy. Sections 7 and 8 respectively contain a description of our test data and the models’ performances on it.

In the models we demonstrate, the score $as(x_{t})$ is always a sum of word-based anomaly scores for each word in the sentence $x_{t}$. Since every two sensors’ vocabularies are disjoint, words are associated with unique sensors. Also, every sentence contains exactly one word from every sensor’s vocabulary. Therefore, at any given time, sensors can be ranked according to the magnitude of the contribution of the words associated with them. Additionally, for a set of (possibly non-consecutive) times $\{t_{1},t_{2},\ldots,t_{M}\}$ during which an anomaly is suspected, we define the suspect score of sensor $s$ over those times as the sum of its words’ contribution to $as(x_{t})$ over all times $t\in\{t_{1},t_{2},\ldots,t_{M}\}$. We denote the sensor-specific score over these times as $score(s)$. This score ranks sensors by their apparent contribution to a suspected anomaly over a time period. This highly interpretable ranking offers a valuable degree explainability for users interested in root cause analysis.

For the model of Section 4, $as(x_{t})$ is calculated only from $x_{t}$, but the models of Sections 5 and 6 rely on a “next sentence forecast” framework. For both of these models, we fix a lookback length, $N$. At time $t$, the input is a sequence of consecutive sentences from the inference series $TS$, $(x_{t-N},x_{t-N+1}\ldots,x_{t-1})$, and the output is a forecast, $\hat{x}_{t}$ for sentence $x_{t}$.

The models are trained on nominal data, so $\hat{x}_{t}$ is a forecast for $x_{t}$ under nominal conditions as characterized by the training sentences from $TS_{tr}$. Therefore, in each model, a numerical measure of the difference between $\hat{x}_{t}$ and $x_{t}$ serves as the anomaly score $as(x_{t})$.

Arbitrarily order the vocabulary $V=(w_{1},w_{2},\ldots,w_{m})$ and the sentences $S=(s_{1},s_{2},\ldots,s_{n})$ of the training corpus. The term frequency of word $i$ in sentence $j$, $TF(i,j)$, is the number of times that $w_{i}$ occurs in $s_{j}$. For the inverse document frequency of word $i$, we use the formula $IDF(i)=\log\frac{n+2}{f_{i}+1}$, where $n$ is the total number of sentences, and $f_{i}$ is the number of sentences containing word $i$. The term frequency matrix for the corpus is the matrix $W$ whose entry in position $(i,j)$ is $W(i,j)=TF(i,j)\cdot IDF(i).$ This formula gives all unknown_word and unknown_letter tokens IDF weight $\log(n+2),$ which is larger than all other “true” words but can be modified as described Section 8. Column $j$ of $W$ is a kind of $m$ dimensional representation of the sentence $s_{j}$.

Next, fix a dimension $k\leq\operatorname{rank}(W)$ for a subspace onto which the sentences are to be projected and construct the full singular value decomposition,

Let $U$ be the $m\times k$ matrix consisting of the first $k$ columns of $U_{0}$, $\Sigma$ be the $k\times k$ matrix consisting of the first $k$ rows and columns of $\Sigma_{0}$ and $V$ be the $k\times n$ matrix consisting of the first $k$ rows of $V_{0}$. There are two key observations.

Observation 1 is the Eckart-Young-Mirsky Theorem [2]. The proof of Observation 2 relies heavily on the fact that $U^{T}U=I$ because $U_{0}$ is orthogonal, as well as the fact that $\dim(\operatorname{col}(W^{\prime}))=k=\dim(\operatorname{col}(U))$.

Observations 1 and 2 provide the optimal $k-$dimensional subspace to project onto in the sense of minimizing the average distance between $x_{t}$ and $P(x_{t})$ for all columns of $W$. The average is minimized not just over projections onto $\operatorname{col}(W^{\prime})$ but over all possible projections onto all possible $k-$dimensional subapaces of $\mathbb{R}^{m}$. This justifies the interpretation of $P(x)$ as a kind of optimally in-family $k-$dimensional reconstruction of the $m-$dimensional sentence represented by $x$. Therefore, for an arbitrary sentence, $x$, we define its anomaly score by,

The decomposition of $as(x)$ in terms of individual word contributions on the right of Equation 2 lets us define the individual sensor scores $score(s)$ for root cause investigation with the method described in Section 3.1.

The transformer model was first introduced by Vaswani et al. [13] for the purpose of language translation using an encoder-decoder architecture. We repurpose the encoder portion of this model to perform both encoding and decoding in the same layer. For this conversion, the attention mechanism was modified to perform two types of attention: self-attention and causal attention.

The right side of Figure 3 describes the architecture of each transformer block. From the bottom, we transform the sequence of sentences into an embedding vector which represents each word. The words are then added with another embedding vector called positional embedding. This embedding is the same size as the input embedding and it is designed to carry information about the position of each word of the sentence. Once the data passes through the embedding layer, the transformer block splits the embedded data based on the number heads used for each block. The number of heads and the embedding dimension are tunable hyperparameters, constant for each transformer block. The number of transformer blocks in the full model is also a tunable hyperparameter.

The attention mechanism shown in Figure 3 is composed of two different mechanisms: a self-attention mechanism and a causal attention mechanism. The self-attention is used only on the unmasked words to build a rich representation of the words by looking at future words, as well as previous words. On the other hand, the structure of the causal attention used on the masked words ensures no valuable information is transmitted from future masked words. This causal attention forces the model to build a representation of the masked words based only on the previous words. Researchers He et. al [5] have shown that this type of dual attention mechanism outperforms transformer baseline architecture in machine translation tasks. This architecture also reduces the number of hyperparameters by more than half by implementing both tasks in a single block.

As shown on the left side of Figure 3, the output dimension of each transformer block is the same as that of the input embedding. This output embedding is then linearly transformed into the dimension of size of the vocabulary. The layer has a softmax activation because the target is the one-hot-encoding of each word in the input. The output is finally filtered only to pass positions of the masked sentence on to the cross-entropy loss, but this is not shown in the figure. In practice, we compute the loss on each sensor’s vocabulary independently instead of computing the overall loss. We then average the sensor-specific losses to obtain the total loss. This technique comes from Padhi et. al [6], where researchers implement a global vocabulary and local vocabulary to compute the cross-entropy loss for each categorical column in their dataset.

The trained model generates next sentences based on nominal characteristics exhibited by the training data, so a measure of the difference between the forecast $\hat{x}_{t}$ and the actual $x_{t}$ is used as the anomaly score at time $t$. For this, we used the Levenshtein distance, which is the number of changes required to convert the predicted word to the truth word. The Levenshtein scores are then added together across words of the sentence to arrive at $as(x_{t})$, as shown in Equation 3, where $w$ is the actual word, $\hat{w}$ is the model’s predicted word and $lev(w,\hat{w})$ is the Levenshtein distance between $w$ and $\hat{w}$.

Anomaly score $as(x_{t})$ is used to flag anomalous times using the threshold method of Section 3. Since words are associated with unique sensors, Equation 3 allows us define the individual sensor scores $score(s)$ for root cause investigation with the method described in Section 3.1.

While existing NLP algorithms could be used to obtain vector representations of words arising from a categorical time series in an unsupervised manner, our situation is different from classical NLP because words in a sentence here have no naturally preferred ordering. We work around this difference by using a trainable entity embedding layer placed before a deep neural network as introduced in [3]. The full model is trained on the task of masked word modeling, and the activations of the trained embedding layer are used as the vector representations.

While more sophisticated architectures could certainly provide performance gains, for demonstration purposes, we used a simple three-layer feed-forward network after the embedding layer. Each training sample consists of an input sentence with a randomly selected word masked to the value $0$, and the target is the one-hot encoding of the masked word. As shown in Figure 4, the words in each sentence are first integer encoded with strictly positive integers so that the embedding can accommodate the $0$-value mask. This has the further benefit that in downstream tasks, the vector representation corresponding to the value $0$ can be used for unknown word tokens’ representations. Once the model is fully trained, the learned parameter matrix of the embedding layer is used as a lookup table for the dense embeddings of the words.

The vector representations of the previous section can be used to fuel most any machine learning model, but we again demonstrate their use on anomaly detection by next sentence forecasting described in Section 3.2. To demonstrate their “out-of-the-box” applicability to downstream tasks, we used a simple LSTM-based model with two LSTM layers followed by a dense layer with softmax activation to make the final forecasting.

The words in each sentence $x_{i}$ of an input sequence $(x_{t-N},x_{t-N+1}\ldots,x_{t-1})$ are each embedded according to the embeddings learned above. The resulting 2-dimensional representation of $x_{i}$ is flattened to $1$-dimensional representation $\overline{x}_{i}$ and the sequence $(\overline{x}_{t-N},\overline{x}_{t-N+1}\ldots,\overline{x}_{t-1})$ is the model’s input. Each sentence has exactly one word for each sensor, so the target sentence $x_{t}$ can be encoded in a kind of “multi-hot” fashion, consisting of a vector of length equal to the total number of words in the full vocabulary with a “1” in the position of every word occurring in the target sentence. The model is trained on the cross entropy loss.

For anomaly scoring during inference, we first translate the model’s forecast at time $t$ back into sentence form. Words in each sentence correspond exactly with the sensors of the time series, so as in Section 5.4 we use the sum of the Levenshtein distances between the forecasted word for each sensor and the the actual word for that sensor observed in sentence $x_{t}$ as the anomaly score $as(x_{t})$. Since $as(x_{t})$ is the sum of word-based contributions, we are able to define the individual sensor scores $score(s)$ for root cause investigation with the method described in Section 3.1.