Oddballness: universal anomaly detection with language models
Filip Graliński Ryszard Staruch Krzysztof Jurkiewicz


§ INTRODUCTION


Not all events with low probability are weird or oddball
when they happen.
For instance, the probability of a specific deal in the game of bridge is
extremely low (p_b = 1/5.36 × 10^28 for each deal).
So every time you are dealt cards in bridge, something unfathomable
happens? Of course not, actually an event of the very low probability p_b
must happen (with the probability 1!).

Another example, imagine two probability distributions:


  
  * D_1 = {p_1 = 1/100, p_2 = 99/100},
  
  * D_2 = {p_1 = 1/100, p_2 = 1/100, … p_100 = 1/100},


Intuitively, p_1 is much more oddball in D_1 than p_1 in D_2.

So, how to measure oddballness? We already know that a low probability is not
enough. Let us start with basic assumptions or axioms of oddballness.
Then we will define oddballness and show their practical usage for
anomaly detection when applied to probability distributions generated
by language models.



§ AXIOMS OF ODDBALLNESS


Let us assume a discrete probability distribution
D = (Ω, Pr), where Ω could be finite or countably infinite.
From now on, for simplicity, we define D just as a multiset of
probabilities:


    D = {p_1, p_2, p_3, …} = {Pr(ω_i) : ω_i ∈Ω}.


We would like to define an oddballness measure[Measure
understood informally, not as defined in measure theory.] for an
outcome (elementary event) of
a given probability p_i within a distribution D:


    ξ_D(p_i), ξ_D : D → [0,1]


Let us define some common-sense axioms for oddballness:


  
  (O0) ξ_D(p_i) ∈ [0,1] – let us assume our measure is
    from 0 to 1,
  
  (O1) ξ_D(0) = 1 – if an impossible event happens, that's
    pretty oddball!
  
  (O2) for any distribution ξ_D(max{p_i}) = 0
    the most likely outcome is not oddball at all,
  
  (O3) p_i = p_j →ξ_D(p_i) = ξ_D(p_j) – all
    we know is a distribution, hence two outcomes of the same probability
    must have the same oddballness (within the same distribution),
  
  (O4) p_i < p_j →ξ_D(p_i) ≥ξ_D(p_j), if
    some outcome is less likely than another outcome, it cannot be less
    oddball,
  
  (O5) (continuity) for any distribution  D = {p_1, p_2,p_3,…},
    the function f(x) = ξ_D_x(x), where
    D_x = {x, p_2 ×1-x/1-p_1, …, p_i ×1-x/1-p_1, …},
    is continuous – if we change the probabilities a little bit, the
    oddballness should not change much.



Note that (O2) implies the following two facts:


  
  (F1) p_i > 0.5 →ξ_D(p_i) = 0, what is more likely
    than 50% is not oddball at all,
  
  (F2) for any distribution
     D={p_1=1/N,…,p_N=1/N}, ξ_D(p_i) = 0 –
     like in the bridge example.




§ ODDBALLNESS MEASURE


Let us a define a measure that fulfils (O0)-(O5). First, let us define
an auxiliary function:


    x^+ = max(0, x)


(In other words, this is the ReLU activation function.)

Now let us assume a probability distribution
D = {p_1, p_2, p_3, …}. Let us define the following
oddballness measure:


    ξ_D(p_i) = ∑_j g((p_j - p_i)^+)/∑_jg(p_j),


where g is any monotonic and continuous function
for which g(0)=0 and g(1)=1.

This measure satisfies the axioms (O0)-(O5).


From now on, we assume the identity function g(x)=x (though, for
instance x^2 or x^3 can be used as well); the oddballness measure
simplifies to:


    ξ_D(p_i) = ∑_j (p_j - p_i)^+.


Let us check this measure for our distributions D_1 and D_2 given
as examples:


  
  * ξ_D_1(p_1) = 0.98,
  
  * ξ_D_1(p_2) = 0,
  
  * ξ_D_2(p_i) = 0,


Consider another example: D_3 = {p_1=0.7, p_2=0.25, p_3=0.05},
then: ξ_D_3(p_1) = 0, ξ_D_3(p_2) = (0.7-0.25)^+ + (0.25-0.25)^+ + (0.05-0.25)^+ = 0.45,
ξ_D_3(p_3) = 0.85.



§ ODDBALLNESS AS A COMPLEMENT OF PROBABILITY OF PROBABILITY


Interestingly, oddballness can be interpreted as the complement of
the probability of a probability. By probability of a
probability p_i with respect to distribution D, or π_D(p_i),
we mean the probability that an event of probability p_i (not
necessarily ω_i) happens, with two extra assumptions:



  * all probabilities smaller than p_i are also summed up,

  * for each event ω_j with probability p_j > p_i, we
  assume that it contains a “subevent” of probability p_i, hence
  for each such event we sum p_i in.


It can be shown that


    π_D(p_i) = 1 - ξ_D(p_i).


Intuitively, it makes sense: An event is oddball if the probability of
any event happening with similar probability is low. See
Figure <ref> for an illustration of the relation between
oddballness and probability of probability.





§ WHAT'S THE PRACTICAL USE?


The oddballness measure can be used to detect anomalies or errors, e.g. in a
text, assuming that we have a good language model. The language model will
give a probability distribution for any word in a text, some words
will be given higher probability (likelihood), some lower. We could mark words
with low probability as suspicious, but sometimes a low-probability
event must occur. For instance, the distribution for the gap in
the sentence:

I was born in …, a small village

should be (for a good language model[For this
example, an encoder-only model trained on the masked language task
should be assumed, for instance RoBERTa <cit.>.]) composed of a large number of names, each with a
rather low probability. Hence, like in the bridge example, we should
be not surprised to see a low-probability event. On the other hand, in the
sentence:

I was born in New …City

any word other than York is pretty unlikely (and
oddball). Therefore, rather than probability, the oddballness
should be used – words with oddballness exceeded some threshold
should be marked as suspicious, they are potential mistakes or
anomalies to be checked by humans. This way, we could devise a grammar
checking/proofreading system that is not trained or fine-tuned in a supervised
manner for the specific task of error detection.

The notion of oddballness might not be that useful in the world before
good language models, when usually only static discrete distributions
were assumed. Language models, even for the same text, can generate
vastly different types of probability distributions for each
position:


  
  * sometimes the model is almost certain and almost all
    probability will be assigned to one token,
  
  * sometimes the model will predict a group of possible tokens
    plus a long tail of less likely tokens,
  
  * and sometimes the model is uncertain and the entropy is high.


In this paper, we focus on applying oddballness to grammatical error
detection (see Section <ref>). Some related (but not
the same) ideas were, however, proposed in the field of log anomaly
detection, as log sequences can be viewed as a modality similar to
natural language. LogBERT by <cit.> was trained on, in a
semi-supervised way, on log sequences. During anomaly detection some
tokens are masked and the probability distribution is obtained from
LogBERT for each of them. If the probability of the actual token is
not one of the K highest-likelihood tokens (K is a hyperparameter),
the token is considered anomalous (we will refer to this method as
topK later). LogGPT by <cit.> is a
similar idea, but applied to an decoder-only GPT-like architecture,
rather than an encoder-only Transformer, but still the same approach
of considering topK prediction is taken for the anomaly detection
itself, though the model is also fine-tuned specifically for anomaly
detection.

In general, there is a vast body of literature on anomaly or outlier
detection (see, for instance: <cit.>,
<cit.>, <cit.>). Oddballness is
different, as it considers only probabilities from a language model
(or any other statistical model) rather than any intrinsic feature of
events in question.



§ EXPERIMENTS WITH ERROR DETECTION





Table <ref> presents the results on the FCE
dataset <cit.>. In each case, using the
oddballness value as the threshold gives better results than using the
probability value. All thresholds were adjusted to maximize the F0.5
score on the development set. The maximum oddballness value from the
GPT2-XL and RoBERTa Large <cit.> models produced the best F0.5 score on the
test set. The result is slightly better than the BiLSTM model by <cit.>,
which was trained specifically to detect errors in texts, while GPT2-XL and RoBERTa
Large are models which were trained, in a self-supervised manner, on the masked token prediction
task. Although results based on the oddballness value are not competitive with
state-of-the-art solutions, it should be noted that the oddballness
technique does not involve any task-specific fine-tuning, except
for single-hyperparameter tuning. Also, the texts were written by CEFR B level
students, indicating that they may not be fully proficient in the
language. This could cause the language model to flag not fluent words
as incorrect and thus predict correct words as erroneous. This may also
explain why the smaller GPT2-small model outperforms the much larger
Mistral 7b model. This study demonstrates that the oddballness measure
can yield superior results compared to using probability values for
anomaly detection.





We also tested the Mistral 7b model for multilingual GED datasets used in
MultiGED-2023 Shared Task <cit.> using the
same approach as in experiments for the FCE dataset. The results in
Table <ref> show that for all languages the
oddballness method outperforms the probability method. We also tested
adding the following prompt before each sentence: "An example of a
grammatically correct text in any language that may be out of context:
<example>" to make probability distribution more smooth. The results
in Table <ref> show that this trick helps in almost
all experiments, but the improvements for the oddballness method are
greater compared to the probability method. Looking at the thresholds
we can also indicate that thresholds for the oddballness value are
more universal compared to the probability thresholds. We also tested the top-K approach. For multilingual GED task it does not provide better results than probability method in any language. The best
solutions for each dataset in the shared task are better compared to
oddballness value results, but again those solutions are trained to
predict incorrect tokens, whereas the oddballness method approach
focus more on predicting spans in texts that are most likely
errorneous without precisely labeling all incorrect tokens.






§ CONCLUSIONS


We have showed that using a new metric for anomalous events,
oddballness, is better than just considering low-likelihood tokens, at
least for grammatical error detection tasks. The method based on
oddballness yields worse results than state-of-the-art models heavily
fine-tuned for the task (<cit.>), but its great advantage is that it can be
used for any language model, without any fine-tuning. This technique
can be applied potentially to anomaly detection in sequences of any
type of data, assuming that a “language” model was pre-trained.
