Nicolas Bailluet

Hélène Le Bouder

David Lubicz

Ransomware Detection Using Markov Chain Models Over File Headers

Keywords: Ransomware, Detection, Malware, Markov Chain, File Header

In this paper, a new approach for the detection of ransomware based on the runtime analysis of their behaviour is presented. The main idea is to get samples by using a mini-filter to intercept write requests, then decide if a sample corresponds to a benign or a malicious write request. To do so, in a learning phase, statistical models of structured file headers are built using Markov chains. Then in a detection phase, a maximum likelihood test is used to decide if a sample provided by a write request is normal or malicious. We introduce new statistical distances between two Markov chains, which are variants of the Kullback-Leibler divergence, which measure the efficiency of a maximum likelihood test to distinguish between two distributions given by Markov chains. This distance and extensive experiments are used to demonstrate the relevance of our method.

Introduction

Ransomware are a family of malware that ask a payment to the legitimate users for accessing their machine or computer files. They are one of the most serious security threats on the Internet. The number of attacks has increased drastically these last years, resulting in huge losses and disruptions. There are two types of ransomware: some prevent the usage of the computer, others encrypt files. In this paper we are interested in the last case called crypto-ransomware. Crypto-ransomware are more and more efficient and easy to operate by malicious individuals and organisations. They are provided as ready-to-use toolkit with robust cryptographic algorithms, embed evasion techniques to defeat intrusion detection and are capable to spread in a network to infect many computers.

In order to mitigate this threat, it is important to be able to detect and stop automatically the malicious activity of ransomware.

In this paper, we present a new method to detect ransomware that belongs to the class of behavioural approach which consists in detecting malign activity : the encryption data, by distinguishing it from normal activity.

In this paper, we explain:

• how to use Markov chains in order to build a statistical model of a normal behaviour by training it with write requests; • how to compute maximum likelihood tests that distinguish samples drew following two distributions well described by Markov chains;

• we report on extensive experiments to demonstrate the relevance of our method.

The main originality of the paper, which is developed in Section 4, is related to the remark that the Kullback-Leibler differential entropy measures the efficiency of the maximum likelihood test to distinguished the distributions given by two Markov chains. Unfortunately, the Kullback-Leibler entropy can not always be computed in our case because the probability of some transition is 0. So we have to tweak a little bit the definition of Kullback-Leibler entropy to obtain a useful criterion. This criterion is then used as an essential tool to conduct our experiment methodology and adjust the parameters of the Markov chain so as to maximise the probability of detection.

The state of the art of countermeasures are described in section 2. In section 3, the basic definition and main theoretical ingredients that are used in the paper, are introduced. Section 4 is devoted to a preliminary analysis of the data. In section 5, we present the results of our first experiments to then refine our approach in Section 6. The Section 7 tests our approach against real-world ransomware-encrypted files. Finally, conclusions are drawn in section 8.

Different surveys have been published on ransomware protections [START_REF] Genc | Next generation cryptographic ransomware[END_REF][START_REF] Al-Rimy | Ransomware threat success factors, taxonomy, and countermeasures: A survey and research directions[END_REF][START_REF] Aurangzeb | Ransomware: a survey and trends[END_REF][START_REF] Moussaileb | Log Analysis for Malicious Software Detection[END_REF]. A first idea to protect data against ransomware attacks is to use data back-up as explained in [START_REF] Castiglione | Dynamic distributed secure storage against ransomware[END_REF][START_REF] Baykara | A novel approach to ransomware: Designing a safe zone system[END_REF] but it is not possible to have at any time an up to date back-up of data and to decide when and which data need to be restored it is necessary to have a mechanism to detect a ransomware attack when it occurs.

The classic detection techniques used for all malware, such as as NIDS (Network Intrusion Detection Systems), can be used for ransomware. Signature based detection remains a valid way to detect an infection. Network traffic is compared to previously well-known malware patterns, called signatures as in [START_REF] Moussaileb | Ransomware network traffic analysis for pre-encryption alert[END_REF][START_REF] Ahmadian | Connection-monitor & connection-breaker: A novel approach for prevention and detection of high survivable ransomwares[END_REF][START_REF] Cabaj | Software-defined networking-based crypto ransomware detection using http traffic characteristics[END_REF][START_REF] Almashhadani | A multi-classifier network-based crypto ransomware detection system: a case study of locky ransomware[END_REF]. The limitation of these techniques is that they are unable to detect new malware, never seen before. This is a serious problem with ransomware because a lot of attacks come from new ransomware.

The detection of specific behaviours of ransomware are used too. Some detection mechanisms specific to ransomware can be to watch how files are touched [START_REF] Moussaileb | Ransomware's early mitigation mechanisms[END_REF] or to detect ransom note writing (Yassine [START_REF] Lemmou | Discriminating unknown software using distance model[END_REF]. Some papers studies the transaction for the ransom payment [START_REF] Akcora | Bitcoinheist: Topological data analysis for ransomware detection on the bitcoin blockchain[END_REF]. But, the most specific behaviour of ransomware is to overwrite files with encrypted data so that these methods still generate a lot of false alarms.

Often ransomware do not come with their own cryptographic libraries and rather rely on the victims own tools. So many protections are based on controlling accesses over the cryptographic tools in Windows [START_REF] Palisse | Ransomware and the legacy crypto api[END_REF][START_REF] Chen | Automatic ransomware detection and analysis based on dynamic api calls flow graph[END_REF]Al-rimy et al., 2018a;[START_REF] Al-Rimy | Crypto-ransomware early detection model using novel incremental bagging with enhanced semirandom subspace selection[END_REF]. One other way to detect ransomware is to have honey pots. These are files that trigger an alarm when they are modified [START_REF] Moore | Detecting ransomware with honeypot techniques[END_REF][START_REF] Patton | Behavior-based ransomware detection using decoy files[END_REF].

Finally there is a family of ransomware detection mechanisms which rely on encryption detection. Indeed encryption produces data which have a pseudorandom distribution, therefore increasing the entropy of the files. There is an important literature about statistical tests of randomness which can be used to detect encrypted data [START_REF] Scaife | CryptoLock (and Drop It): Stopping Ransomware Attacks on User Data[END_REF][START_REF] Continella | ShieldFS: A Self-healing, Ransomware-aware Filesystem[END_REF]Kharraz and Kirda, ;[START_REF] Palisse | Data aware defense (dad): towards a generic and practical ransomware countermeasure[END_REF][START_REF] Kharraz | UNVEIL: A Large-Scale, Automated Approach to Detecting Ransomware[END_REF].

A recent study [START_REF] Pont | Why current statistical approaches to ransomware detection fail[END_REF] explains in detail why the classical statistic tool are not sufficient to detect ransomware. That is why in this paper a new approach is presented.

A drawback of these methods is that randomness behaviour is not a complete characterisation of encrypted streams: compressed data streams which are quite common behave in the same manner. As a consequence, in order to avoid too much false alarms it is necessary to combine detection mechanism based on randomness with other criteria, specific of ransomware malign activity.

Another problem on the statistical level is that we want to distinguish malign activity from normal behaviour. But if we have a clear statistical model for malign activity, namely random data, we do not have its counterpart for normal behaviour. In this situation, the use of classical χ 2 tests [START_REF] Palisse | Data aware defense (dad): towards a generic and practical ransomware countermeasure[END_REF] is awkward to say the least since they are meant to detect improbable events under the hypothesis that the stream of data is random where we actually want to single out improbable events in the case that the stream of data is a normal structured file. This makes it impossible to carry out a precise analysis of the efficiency of the statistical tests that we use for the detection of ransomware and to design the most efficient statistical tests.

In this paper, we present a new method to detect ransomware that belongs to the class of behavioural approach which consists in detecting malign activity by distinguishing it from normal activity. A well suited probe for the kind of malign activity involved by ransomware is provided by write requests which are handled by the kernel and is a mandatory call in order to perform a write access on a hard drive. These requests can be monitored by a specific driver running in kernel land, the operation of which can not be disrupted by the ransomware (which is running in user land).

Whereas most statistical models and machine learning techniques recently implemented focus on neural networks or other modern machine learning methods [START_REF] Lee | Machine learning based file entropy analysis for ransomware detection in backup systems[END_REF], we chose to use Markov chains to model the stream of data. Unlike modern machine learning methods, Markov chains are fairly easy to understand and manipulate. They induce well understood probability distributions and can be used in conjunction with a maximum likelihood test that is known to be the most powerful in a large class of statistical tests. In building the model, we mainly focus on file headers because they produce data stream of very structured data with recurrent patterns which make them very different from a statistical point of view from encrypted data.

Let bit = {0, 1} be an alphabet of cardinal 2 . ∀k ∈ N, let S k be the set of finite sequences of length k with coefficients in bit. The data stream is represented by a probability distribution on S k . This probability distribution can be:

• either the uniform U k distribution which represents encrypted data; • or an unknown distribution D k which represents normal header data.

We suppose that we can obtain samples drawn following the distribution D k (and of course also following the distribution U k ). So, we can obtain information about this distribution. The problems that we want to solve efficiently are:

1. obtain a model of the distribution D k by learning it from samples drawn following D k ; 2. for s a given sample, decide from which distribution D k or U k it comes from.

In order to learn the distribution D k , we use the model provided by Markov chains. It is a fundamental and widely used model in information theory and is particularly well suited to statistically model a data stream. There exists more general definition in the huge literature on the subject (see [START_REF] Ash | Information theory[END_REF] for instance), but we have chosen in this paper to slightly adapt it to our needs. A binary Markov chain X with memory m is a sequence (X i ) i≥0 of random variables with value in S m , the set of states, and such that ∀n ≥ k:

1. P(X n = x n |X n-1 = x n-1 , . . . , X n-k = x n-k ) = P(X n = x n |X n-1 = x n-1 ), 2. P(X n = x n |X n-1 = x n-1 ) does not depend on n.
We suppose moreover that if

x n / ∈ succ(x n-1 ) then P(X n = x n |x n-1 = x n-1 ) = 0.
It is clear that succ maps any element s ∈ S m to the set of its possible successors. If s = s 1 . . . s m ∈ succ(s) then the transition from s to s is labelled by s m ∈ bit.

A binary Markov chain is classically defined by the following data:

• the memory m which is an integer;

• the transition matrix T = t x,y such that, ∀x, y ∈ S m :

t x,y = P(X n = x|X n-1 = y).
• an initial state X 0 which is a random variable with value in S m .

Definition 3.2. An element X k 0 of the Markov chain

(X i ) i≥0 is stable if, ∀k ≥ k 0 : X k+1 = X k .
A Markov chain with memory m verifies the ergodicity and irreducibility condition [START_REF] Ash | Information theory[END_REF]) so that by [START_REF] Ash | Information theory[END_REF] we know that any such Markov chain has a unique stable element. A stable element gives by definition a random variable on S m that we denote by X(m). More generally, it also defines random variable X(k) on S k , ∀k > m, by the induction (1) Because of Definition 3.1, the preceding formula does not depend on n. One has to remark that X(m + 1) allows to recover X(m) using ( 2). But, it means that X(m + 1) allows to recover the transition matrix t x,y , for x ∈ succ(y) using Equation ( 1) with k = m + 1. The distribution X(m + 1) can then be encoded by a function

f X : S m+1 → [0, 1] b 1 . . . b m+1 → P( X(m + 1) = b 1 . . . b m+1 ). (3)
This way of encoding the transition matrix takes O(2 m ) memory bits and is more efficient that storing all the t x,y , ∀x, y ∈ S m (which takes O(2 2m ) memory bits). Finally, we denote by X(m, f X , X 0 ) the Markov chain with memory m, transition matrix encoded by f X and initial state X 0 . From the knowledge of f X , one can recover the stable state X(m) from (2). Then P( X(k 0 ) = s) for k 0 > m is given for s = b 1 . . . b k 0 ∈ S k 0 by 4. In the preceding formula, the first equality is obtained by an inductive application of (1) for k = k 0 , k 0 -1, . . . , m + 1 and the second equality comes from (3).

Modeling data stream using Markov chains

We have a corpus of files with different extensions and we want to model the statistical properties of their header with Markov chains in order to be able to distinguish them from encrypted files. A Markov chain of memory m is used and trained, with the first N bits of each file. In this section, we explain how to train the model, compute the test and assess the efficiency of the test.

P( X(k) = b 1 . . . b k ) = P(X n = b k-m+1 . . . b k |X n-1 = b k-m . . . b k-1 ) • P( X(k -1) = b 1 . . . b k-1 ).
(1)

P( X(m) = b 1 . . . b m ) = P( X(m + 1) = b 1 . . . b m 1) + P( X(m + 1) = b 1 . . . b m 0). (2) P X(k 0 ) = s = P X(m) = b 1 . . . b m k 0 ∏ i=m+1 P (X n = b i-m+1 . . . b i |X n-1 = b i-m . . . b i-1 ) = P X(m) = b 1 . . . b m k 0 ∏ i=m+1 P( X(m + 1) = b i-m . . . b i ) P( X(m) = b i-m . . . b i-1 ) (4)

Training the Model

Let H N be the list of the first N-bit sequences of each file in the corpus. Let X(m, f X , X 0 ) be the Markov chain which represents the best statistical approximation of the sample H N . To define this Markov chain X(m, f X , X 0 ), we have to compute f X (s), ∀s ∈ S m+1 and P(X 0 = s), ∀s ∈ S m . ∀s ∈ S m+1 , let c H N (s) be the occurrence count of s in every sequence of H N . ∀s ∈ S m , let c H N,0 be the number of sequences in H N such as s is the m first bits. Denote by |H N | the number of the list H N i.e the number of files. Finally, let

|H N |(k) = (N -k).
|H N | be the number of sequences of bits of length k in H N . We have:

∀s ∈ S m+1 , f X (s) = c H N (s) |H N |(m+1) , ∀s ∈ S m , P(X 0 = s) = c H N,0 (s) |H N | .
(5) On the other side, let X r (m, f X r , X r 0 ) be the Markov chain with memory m which represents the best statistical approximation of an encrypted file. As the statistical behaviour the encrypted file is indistinguishable from the one of a perfectly random sequence [START_REF] Katz | Introduction to Modern Cryptography (Chapman & Hall/Crc Cryptography and Network Security Series)[END_REF]. Thus:

∀m ∈ S m+1 , f X r (s) = 1 2 m+1 , ∀m ∈ S m , P(X r 0 = s) = 1 2 m . (6)
From ( 5) and ( 6), we obtain Algorithm 1 to compute a Markov chain model of the data stream associated to file headers.

Testing Samples against models

For i ∈ {1, 2}, let X i (m, f X i , X i 0 ) be two Markov chains. Let s ∈ S N be a sample header. We want to decide which of the two trained models X i (m, f X i , X i 0 ) for i = 1, 2 is the more likely to match s. For this we apply the likelihood ratio test.

Definition 4.1. Likelihood Ratio Test for Trained Models. Let s ∈ S k be a sample, we define the likelihood ratio of s with respect to X i (m, f X i , X i 0 ) for output: X(m, f X , X 0 ) a memory m Markov chain.

1 for i ← 1 to |H N | do 2 Let b 1 . . . b N = H N [i]; 3 C H N,0 (b 1 . . . b m ) = C H N,0 (b 1 . . . b m ) + 1; 4 for j ← 1 to N -m do 5 C H N (b j . . . b j+m ) = C H N (b j . . . b j+m ) + 1; 6 end 7 end 8 for s ← S m do 9 P(X 0 = s) ← C H N,0 (s)/|H N |; 10 end 11 for s ← S m+1 do 12 f X (s) ← C H N (s)/|H N |(m + 1); 13 end 14 return X(m, f X , X 0 ); i = 1, 2, two Markov chains, as: Λ s, X 1 (k), X 2 (k) = P X 1 (k) = s P X 2 (k) = s .
The likelihood ratio test then is defined by:

T c, s, X 1 (k), X 2 (k) = 1 if Λ(s, X 1 (k), X 2 (k)) > c 0 otherwise .
Here c is a constant that allows to set the significance level of the test.

The Neyman-Pearson lemma [START_REF] Huber | Minimax tests and the neyman-pearson lemma for capacities[END_REF] states that this likelihood-ratio test is the most powerful test for a given significance level. A variant uses the log-likelihood ratio log Λ(s, X 1 (k), X 2 (k) . The Algorithm 2 uses (4) to compute the likelihood ratio.

Algorithm 2: Algorithm to compute the likelihood ratio input :

• m an integer;

• X i (m, f X i , X i 0 ), for i = 1, 2 two Markov chains; • s = b 1 . . . b k ∈ S k a sample of length k with k ≥ m. output: Λ s, X 1 (k), X 2 (k) the likelihood ratio. 1 Λ ← P(X 1 0 =b 1 ...b m ) P(X 2 0 =b 1 ...b m ) ; 2 for i ← m + 1 to k do 3 for j ← 1 to 2 do 4 P j = f X j (b i-m ...b i ) f X j (b i-m ...b i-1 0)+ f X j (b i-m ...b i-1 1) ; 5 end 6 Λ ← Λ P 1 P 2 ; 7 end 8 return Λ;

Measuring the Relevance of the Test

For k ≥ m an integer, the expected value of log Λ(s, X 1 (k), X 2 (k) , with s drawn from X 1 (k) is (7). It is nothing but the Kullback-Leibler divergence [START_REF] Kullback | On information and sufficiency[END_REF][START_REF] Hershey | Approximating the kullback leibler divergence between gaussian mixture models[END_REF] of X 1 (k) and X 2 (k), denoted by: KL ( X 1 (k)|| X 2 (k) . Thus, the Kullback-Leibler divergence gives an assessment of the distance between the distributions of X 1 (k) and X 2 (k). One has to remark that it is particularly well suited for the likelihood ratio test. The bigger the Kullback-Leibler divergence is, the more the test will be able to successfully distinguish X 1 (k) from X 2 (k).

When a statistical model for a corpus of very structure files is computed, it is not so uncommon that some states of a Markov chain are almost never or never reached. In the case where P X 2 (k) = s = 0, KL ( X 1 (k)|| X 2 (k) is not defined and the computation of the likelihood ratio may fail. Indeed, in the computation of likelihood ratio or in the Kullback-Leibler divergence, there is the following quotient: for k ≥ m and s ∈ S k :

Λ s, X 1 (k), X 2 (k) = P X 1 (k) = s P X 2 (k) = s . Of course if X 2 m, f X 2, X 2 0
is the model corresponding to the random distribution, then, Λ s, X 1 (s), X 2 (s) can always be computed. In this case, we can also compute the Kullback-Leibler divergence. But we would like to be able to compute the divergence between two not random distributions.

Furthermore, it may also happen that P( X 2 (k) = s) is not zero but is very small, which corresponds to very rare states. In this case, the statistics computed during the training phase may happen to be not significant, since they have been computed with a very small sample. It could generate false negative for our test. One of the main point of the present paper is to explain how to deal with this situation by introducing a tweaked Kullback-Leibler divergence and use it to choose the best parameters for our Markov chain model.

First Experiments and Results

In this section, we make a first analysis of our corpus of files.

The given corpus is split into two parts, one is for training while the other is for testing the model. The purpose of this corpus is to make a model of legit and well-structured data that are commonly present on anybody's computer, as well as observing how already-known ransomware encrypt data.

The training corpus is composed of 10134 files with 49 different extensions. The extensions frequencies are shown in Figure 1.

The model is built on file headers analyse. It is possible to group extensions by header format. For example: doc, docx, ppt, pptx, xls, xlsx share the same header format in Microsoft Office suite.

The test corpus is composed of 27 plaintexts files and their associated ciphertexts for different ransomware. The list of ransomware and their specific behaviour is shown on Table 1.

Ransomware name

Behaviour

Table 1: List of of ransomware and their specific behaviour.

For the first experiments, we have trained multiple models on different file formats: jpg, gif, msoffice and pdf. These formats are the most present ones in the corpus. Indeed, we have considered subsets of the training corpus consisting of files with the same extensions because it seems reasonable to suppose that their file headers have the same structure that will be captured by the Markov chain model. We wanted to see how much our approach is sensitive to the type of files of the corpus.

E log Λ(s, X 1 (k), X 2 (k)) = ∑ s∈S k P X 1 (k) = s • log P( X 1 (k) = s P( X 2 (k) = s . ( 7
The parameters for the experiments have been chosen based on the KL-divergence to randomness. We trained multiple models with different parameters m (memory) and N (header length). The parameter N is ranging from 128 to 2048, which seem to be reasonable sizes for file headers. The parameter m is ranging from 4 to 16, a larger value would not be reasonable knowing the number of states in a Markov chain grows exponentially as the memory grows. The results are shown in Table 2.

While the header length N seems to have a significant effect on the divergence for each format, to increase in memory m seems to globally decrease the divergence. Based on those observations and the results in Table 2, we have chosen the following parameters for our experiments: m = 4 and N = 512. Indeed, the choice for m is obvious, we have decided to set N = 512, since it maximizes the divergence for msoffice files.

To ensure the significance of the test, we have recorded the evolution of the KL-divergence while training the Markov chain model. The results are shown in Figure . 2. It is important to take a look at the evolution to ensure that the metric tends to converge to a non-null value. A null value would indicate that the test would be unable to distinguish the trained model from randomness. We can see in Figure 2 that the divergence seems to more or less converge in most cases.

The divergence of msoffice files is really high compared to other format. This is not surprising, this format is known to have a header that leaves small room for randomness. As for jpg and gif files, the divergence is relatively smaller and this is again not surprising because these formats do not have headers as static as msoffice. Finally, the divergence for pdf files seems to be almost zero because the pdf headers are very varying.

The model trained over the whole corpus, without taking into account file extension, seems to converge to a divergence of approximately 0.069.

Test and Results

To test the trained models against randomness, we have created for each format a corpus half composed of randomly generated files and half composed of files that match the format and were not in the original training corpus. We have used the likelihood ratio test (see Definition 4.1) with the constant c = 1. The test is positive if it says that the sample corresponds to a structured header and negative if it says that the sample is random. The results are shown in Table 3. One has to remark that the success rate of positive testcases for gif and pdf is not maximal. By looking at the computation of the likelihood ratio, we figured out the issue is due to rare states and transitions that are not highly present in the original corpus.

Explanation of False Negatives

The results showed that some positive test-cases are categorized as negative by the test. We figured out this behaviour is due to some states that are relatively little present in the original corpus.

Let X(m, f X , X 0 ) be a trained model, we say that b 1 . . . b m ∈ S m is a rare state if (with the notations of Section 4.1):

c H N (b 1 . . . b m ) = c H N (b 1 . . . b m 0) + c H N (b 1 . . . b m 1
) is small compared to the total number of transitions in the corpus. Said in another way, a s ∈ S m is rare if

f X (s0) + f X (s1) < t,
that      c H N (b 1 . . . b m 0) = 0 or c H N (b 1 . . . b m 1) = 0 .
As a result, when such a state is encountered in a testcase and the transition taken is the one of null probability, the numerator of the likelihood ratio becomes zero and eventually the file is categorised as negative.

Since the global number of states is 2 m , we observed this behaviour to be more significant on the results with greater values of m. For instance the proportion of false negative was about 33% for m = 16. The issue is that the test only takes into account the transition probabilities, it does not take into account whether the state's count in the corpus is representative or not compared to other's state counts. For example, it is irrelevant to reject a file only because of one state whose count in the corpus is only 4 while the total number of transitions seen in the corpus is greater than 400000. This means that in this case the decision is taken on little information which only rep-resent 1 100000 of the original corpus, this is like deducing generalities from specific cases.

Refine the Models and Tests

In this section we describe the solutions implemented to overcome the issue of rare states. A modification of the model is introduced to involve applying a threshold to get rid of irrelevant information.

Adding a Threshold

The main idea is to get rid of irrelevant information, by applying a threshold on state probabilities in the trained model X(m, f X , X 0 ). That is to say, for a threshold t ∈ [0, 1], ∀b 1 . . . b m ∈ {0, 1} m , during the learning phase, we set:

f X (b 1 . . . b m+1 ) =    1 2 c H N (b 1 ...b m ) |H N |(m) if c H N (b 1 ...b m ) |H N |(m) < t c H N (b 1 ...b m+1 ) |H N |(m+1)
otherwise .

Intuitively, we remove any information based on rare states, with t a tolerance coefficient. We deduce Algorithm 3 to compute a Markov chain model of a data stream taking into account t.

Algorithm 3: Computation of a Markov chain model of a data stream with threshold input :

• m an integer ;

• H N a list of the first N-bit sequences of each file in the corpus ; • t ∈ [0, 1] a threshold. output: X(m, f X , X 0 ) a memory m Markov chain.

1 for i ← 1 to |H N | do 2 Let b 1 . . . b N = H N [i]; 3 C H N,0 (b 1 . . . b m ) = C H N,0 (b 1 . . . b m ) + 1; 4 for j ← 1 to N -m do 5 C H N (b j . . . b j+m ) = C H N (b j . . . b j+m ) + 1; 6 end 7 end 8 for s ← S m do 9 P(X 0 = s) ← C H N,0 (s)/|H N |; 10 end 11 for s = b 1 . . . b m+1 ← S m+1 do 12 if c H N (b 1 . . . b m )/|H N (m)| < t then 13 f X (s) ← 1/2c H N (b 1 . . . b m )/|H N |(m) 14 else 15 f X (s) ← c H N (s)/|H N |(m + 1); 16 end 17 end 18 return X(m, f X , X 0 );

Threshold Benefits

In other words, once the likelihood ratio is computed, we can distinguish between the transitions which are relevant for the test from those who are not.

Formally, one can define some kind of confidence ratios based on the number of relevant transitions the likelihood ratio is computed with in line 6 of Algorithm 2. For this, let s ∈ S N be a header sample, we want to test this sample for a model

X 1 (m, f X 1 , X 1 0 ) with threshold t against a model X 2 (m, f X 2 , X 2 0 )
with the same threshold t.

We write s = b 1 . . . b N and we introduce:

Γ X 1 ,X 2 ,t (s) = γ X 1 ,t (s) N -m , γ X 2 ,t (s) N -m , with (8). It is clear that Γ X 1 ,X 2 ,t (s)
is the pair of proportions of relevant transitions in the sample s for both models X 1 and X 2 . The higher these values are, the more relevant the test should be. The Algorithm 4 computes the likelihood ratio of a sample s ∈ S k and outputs Γ X 1 ,X 2 ,t (s) taking into account a certain threshold t.

We remark that if we increase t the proportion of relevant transition in the computation of a sample s will decrease but if a sample has only relevant transitions with respect to t, we will be confident that the likelihood ratio is meaningful from a statistical point of view. In order to choose t, we can compute the expectancy, that we denote by E( X,t), that a sample s ∈ S N drawn following the distribution X(N) has only relevant transitions that is:

E( X,t) = ∑ s=b 1 ...b N ∈S N P( X(N) = s)T X(m) (s), (9)
where T X(N) : S N → {0, 1} is the function such that

• T X(N) (s) = 0 for s = b 1 . . . b N if there is a i ∈ {1, . . . , N -m + 1} such that f X (b i . . . b i+m-1 0) + f X (b i . . . b i+m-1 1) < t • and T X(N) (s) = 1 otherwise.
Then one can choose a E( X,t) which give the probability that a test will be relevant which fixes a t.

Results

The same tests as in Section 5.1, have been ran, on the same corpus, with threshold models for pdf and gif formats. The results for the best observed t parameter are shown in Table 4.

The results are optimal for pdf files, the threshold achieves a success rate of 100%. However, it

γ X,t = |{s = b i . . . b i+m-1 ∈ S m , i = 1, . . . , N -m + 1 | f X (s0) + f X (s1) ≥ t}|. ( 8
)
Algorithm 4: Algorithm to compute the likelihood ratio input :

• m an integer; • X i (m, f X i , X i 0 ), for i = 1, 2 two Markov chains; • s = b 1 . . . b k ∈ S k a sample of length k with k ≥ m; • t ∈ [0, 1] a threshold. output: • Λ s, X 1 (k), X 2 (k) the likelihood ratio; • µ 1 , µ 2 ∈ [0, 1] 2 measuring the relevance of the test. 1 Λ ← P(X 1 0 =b 1 ...b m ) P(X 2 0 =b 1 ...b m ) ; 2 n 1 ← 0, n 1 ← 0 ; 3 for i ← m + 1 to k do 4 for j ← 1 to 2 do 5 P j = f X j (b i-m ...b i ) f X j (b i-m ...b i-1 0)+ f X j (b i-m ...b i-1 1) ; 6 if f X j (b i-m . . . b i-1 0) + f X j (b i-m . . . b i-1 1) ≥ t then 7 n j ← n j + 1; 8 end 9 end 10 Λ ← Λ P 1 P 2 ; 11 end 12 return Λ, µ 1 = n 1 /(k -m), µ 2 = n 2 /(k -m) ;
does not work so well for gif files, the threshold does not improve the success rate. This is not surprising because with m = 4, the observed transitions are only distributed over a set of 2 4 = 16 states. This does not allow for a lot of precision in the choice of the threshold since we are basically ignoring a whole state, when m = 4 this represents 1 16 of the et of states.

According to the previous observation, it should be easier to find a good threshold for greater m. Thus, the threshold model has also been tested with different values of m. The results are the best for m = 16 as shown in Table 5.

Experiments on Real-World Ransomware

In this section we show and analyse the results of our tests against files encrypted by real-world ransomware. We used a model trained over the whole corpus for these tests. It is important to precise that the ransomware are active only a short moment, so it is difficult to compare two experimentations paper.

Models and Parameters

As done in section 5, we compared the divergence to randomness for different values of m and N and selected the ones that maximize the metric. The results are shown in Table 6. According to the diver- gence results we have selected the following parameters: m = 8 and N = 512.

Results and Analysis

We have run a test for each ransomware in the corpus, on both encrypted files (we removed the files that were not encrypted by the ransomware) and original files. The results are shown in issues with these two ransomware is that they put a padding of zeroes at the beginning of some encrypted files, since the transition from the all-zero state to itself is quite common in the corpus and can also be an initial state, the model has troubles distinguishing it.

xorist: we believe the issues with this one is due to its ability to conserve more or less the original entropy of encrypted files, thus it does not fit into our model of encrypted data based on randomness.

As we can see, the main issue is that some ransomware encryption techniques do not fit into our model of encrypted data. A possible way to solve these issues would be to train a model over a large number of files encrypted with those ransomware and then perform a test against these newly trained models. However, this would ruin the preventive aspect of this approach since these specific ransomware would have to be known before being detectable.

Conclusion and Future Works

We have introduced a new countermeasure based on Markov Chains to detect ransomware based on their encryption behaviour. We also define a metric associated to our models to give an idea on how well the test should work. Considering ransomware use semantically secure encryption schemes, we represent encrypted data by a complete randomn Markov chain model and are able to distinguish the structured files from random data. According to our observations we have refined our approach and models to fix potential issues and get better results. Finally, we have proved our approach to be applicable to real-world cases by successfully distinguishing structured files from files encrypted with known ransomware whose encryption schemes fit into our models.

While the results are quite encouraging, there are still some points to be dealt with more in depth. We have mentioned that all the metrics do not take into account the initial state probabilities, defining new metrics to fix this issue would help getting a more precise idea on the significance of the tests. Finally, all tests on ransomware were made on small corpora, running a full benchmark on thousands of files would be needed to ensure the reliability of the approach. One limitation of this work is that it cannot detect a ransomware which do not encrypt header of files. This countermeasure is not enough on her own. But it's a pertinent additional tool to complete other implemented countermeasures against ransomware. In the fight against ransomware, more indicators we have, better is the detection. Moreover, the Markov chain models have a low cost in terms of computing. So they can be deployed in the kernel to stop malicious processes without slowing down too much the computer.

Algorithm 1 :

 1 Algorithm to compute a Markov chain model of a data stream input :• m an integer ;• H N a list of the first N-bit sequences of each file in the corpus.

Figure 1 :

 1 Figure 1: Number of files by extension in the training corpus.

  Evolution of the divergence for pdf files Figure 2: Evolution of the divergence for different file formats (m = 4, N = 512) Format # true positive # true negative # false negative # false positive

  )

	Extension	avi c crt csv dbase3 doc docx dwf eps f fits fm gif gls gz hlp html java jpg key kml kmz log mp3 pdf pem png pps ppt zip xml xlsx xls wp unk txt troff tmp text tex sys swf sql sgml rtf py pub ps pptx
		0	500	1000	1500	2000	2500
				Number of files

Table 2 :

 2 for a t > 0 small. If s ∈ S m is a rare state it may happen KL-divergence for different choices of parameters m (memory) and N (header length), and for different file formats

	m	N		128	256		512		1024		2048
			msoffice	0.25	msoffice	0.30	msoffice	0.39	msoffice	0.25	msoffice	0.14
	4		jpeg gif		0.13 0.11	jpeg gif	0.12 0.12	jpeg gif	0.10 0.09	jpeg gif	0.09 0.06	jpeg gif	0.11 0.04
					0.01	pdf	0.01	pdf	0.02	pdf	0.02	pdf	0.03
			msoffice	0.32	msoffice	0.32	msoffice	0.38	msoffice	0.23	msoffice	0.13
	8		jpeg gif		0.11 0.09	jpeg gif	0.08 0.10	jpeg gif	0.08 0.08	jpeg gif	0.09 0.06	jpeg gif	0.11 0.04
			pdf		0.01	pdf	0.02	pdf	0.02	pdf	0.02	pdf	0.03
			msoffice	0.29	msoffice	0.32	msoffice	0.33	msoffice	0.17	msoffice	0.09
	16		jpeg gif		0.05 0.06	jpeg gif	0.03 0.06	jpeg gif	0.03 0.05	jpeg gif	0.04 0.04	jpeg gif	0.06 0.02
			pdf		0.00005	pdf	0.0003	pdf	0.0004	pdf	0.0004	pdf	0.0002
		0.42
		0.41
	Divergence to randomness	0.37 0.38 0.39 0.40
		0.36
		0.35
		0	200	400	600 Number of file processed 800 1000 1200 1400

Table 3 :

 3 First results of tests against randomness for multiple file formats

	Accuracy

Table 4 :

 4 Results of tests with thresholded models against randomness for pdf and gif files (m = 4, N = 512)

	Format t	# true positive # true negative # false negative # false positive Accuracy
	pdf	0.05 330	330	0	0	1.00
	gif	0.05 142	150	8	0	0.97
	Format t	# true positive # true negative # false negative # false positive Accuracy
	pdf	0.0005 330	330	0	0	1.00
	gif	0.05	149	150	1	0	0.99

Table 5 :

 5 Results of tests with thresholded models against randomness for pdf and gif files (m = 16, N = 512)

Table 6 :

 6 Divergence to randomness (whole corpus) for different parameters m and N

	m	N	128	256	512	1024	2048
	4		0.044 0.057 0.069 0.049 0.035
	8		0.074 0.074 0.084 0.060 0.045
	16		0.055 0.062 0.067 0.040 0.025

Table 7

 7

	. The tested

Table 7 :

 7 Results with a model trained over the whole corpus tested against ransomware encrypted files (m = 8, N = 512)

Acknowledgments The authors would like to thank Jean-Louis Lanet and Aurélien Palisse for their for their helpful comments and discussions.


Snehil Dahiya

Shalini Sharma

Dhruv Sahnan

Vasu Goel

Emilie Chouzenoux
email: emilie.chouzenoux@centralesupelec.fr

Víctor Elvira

Angshul Majumdar

Anil Bandhakavi

Tanmoy Chakraborty
email: tanmoy@iiitd.ac.invictor.elvira@ed.ac.uk

Would Your Tweet Invoke Hate on the Fly? Forecasting Hate Intensity of Reply Threads on Twitter

Keywords: Computing methodologies → Machine learning algorithms, • Information systems → Social tagging systems, • Humancentered computing → Social network analysis Hate speech, Signal processing, State-space model, Time series forecasting

Curbing hate speech is undoubtedly a major challenge for online microblogging platforms like Twitter. While there have been studies around hate speech detection, it is not clear how hate speech finds its way into an online discussion. It is important for a content moderator to not only identify which tweet is hateful, but also to predict which tweet will be responsible for accumulating hate speech. This would help in prioritizing tweets that need constant monitoring. Our analysis reveals that for hate speech to manifest in an ongoing discussion, the source tweet may not necessarily be hateful; rather, there are plenty of such non-hateful tweets which gradually invoke hateful replies, resulting in the entire reply threads becoming provocative.

In this paper, we define a novel problemgiven a source tweet and a few of its initial replies, the task is to forecast the hate intensity of upcoming replies. To this end, we curate a novel dataset constituting ∼ 4.5𝑘 contemporary tweets and their entire reply threads. Our preliminary analysis confirms that the evolution patterns along time of hate intensity among reply threads have highly diverse patterns, and there is no significant correlation between the hate intensity of the source tweets and that of their reply threads. We employ seven state-of-the-art dynamic models (either statistical signal processing or deep learning based) and show that they fail badly to forecast the hate intensity. We then propose DESSERT, a novel deep state-space model that leverages the function approximation capability of deep neural networks with the capacity to quantify the uncertainty of statistical signal processing models. Exhaustive experiments and ablation study show that DESSERT outperforms all the baselines substantially. Further, its deployment in an advanced AI platform designed to monitor real-world problematic hateful content has improved the aggregated insights extracted for countering the spread of online harms.

T.

INTRODUCTION

Online discussion forums such as Twitter, and Reddit, provide users with the opportunity to express their opinion freely and that too, anonymously. Although freedom of speech enables users to seek, express and impart information about ideas and opinions, its misuse often leads to social instability both online and offline, resulting in cyber-crimes such as hate speech and cyberbullying. Hate speech is highly subjective -its nature varies across demography; its effect varies across religion, identity and social groups. Therefore, most of the hate speech detection models which leverage hand-crafted lexicons in one form or the other, often struggle to generalize. Recently, there has been a growing body of research in detection and characterizing online hate speech and modeling its spread [START_REF] Fortuna | A survey on automatic detection of hate speech in text[END_REF].

Although hate speech detection is highly pertinent towards the broader goal of sanitizing online content, it is often observed that a non-hate (benign) post, over the time, evolves as a source of provocative discussion, fostering the generation of hateful or offensive posts. For example, Figure 1(a) shows a (partial) reply thread along with the hate intensity (defined in Section 3.2) of each reply. As observed, although the source tweet is less hate intensive and is not detected as hate speech by the hate speech classifier, the replies generated under this tweet are highly hateful. Figure 1(b) shows the hate intensity profile of the entire reply thread of the previous example -it does not follow any particular pattern. None of the hate speech detection models would be able to predict that such a benign online post would ever invoke hatred in near future. This calls for an early prediction model to forecast whether a tweet will invoke hate speech.

Hate intensity profiles of reply threads are diverse. We formally pose the problem as follows: given a tweet (and the initial history of its reply thread), we aim to forecast the hate intensity that its upcoming replies will express. To this end, we curate entire reply threads of ∼ 4.5𝑘 tweets; the average length of a thread is ∼ 200. We quantify the hate intensity of a reply thread by leveraging a hate speech classifier and a benchmark hate lexicon. We observe that the hate intensity profiles of reply threads are non-uniform, exhibiting diverse patterns (c.f. Figure 1(b)). Moreover, the hate intensity of reply threads is not correlated with that of the source tweet (c.f. Figure 1(c)), indicating that identifying hateful source tweet may not be enough to predict the upcoming toxicity of a reply thread. It is also uncertain which quarter of reply threads is more prone to hate speech (c.f. Figure 5 in the Appendix).

Limitations of state-of-the-art methods. One can readily map this into a dynamical modeling problem -given an ordered sequence of data points representing hate intensity of current reply thread of a source tweet, the aim is to predict the hate intensity of the upcoming replies. One can borrow two off-the-shelf approaches to address this problem. First is the classical signal processing models like auto-regressive moving average (ARMA) and its variants (ARIMA, ARIMAX, etc.) or its state-space counterparts. The problem with such models is that one needs to apriori specify the underlying dynamical function; this is not possible for the current problem. The second approach is to use deep learning models such as recurrent neural networks (such as LSTM and GRU) and generative adversarial network (GAN). These techniques do not require specification of the underlying function; they can learn it from the data. However, the problem with them is that they cannot quantify the uncertainty about the prediction -which the signal processing models can.

Our proposed approach: DESSERT. In this work, we propose to keep the best of both worlds mentioned above -the function approximation ability of neural networks and the uncertainty quantification capability of state-space models. We propose DESSERT1 , a deep blind state-space model. Here 'blind' means that we do not need to specify the underlying dynamical model / function; we learn it from the data. However, learning one operator for the state-evolution and one operator for the observation limits the function approximation capability of the blind state-space model. Moreover, by making the model deep, we aim to better capture the non-linearity dynamics of online interactions.

Experimental results. We perform an exhaustive evaluation of DESSERT with seven state-of-the-art baselines (borrowed from both classical signal processing and deep learning domains) on our curated dataset. We observe that DESSERT outperforms all the baselines across four evaluation metrics (both correlation-based and error-based). DESSERT achieves 0.67 Pearson's 𝑟 and 31.08 Mean Absolute Percentage Error (MAPE), which is significantly better than the best baseline [START_REF] Koochali | Probabilistic forecasting of sensory data with generative adversarial networksforgan[END_REF] (𝑟 = 0.557, MAPE=43.47). We also present a detailed ablation study of DESSERT. We further dig deeper into the results to explain how the models respond to reply threads -(i) whose source tweets are originated from across demography, (ii) whose source tweets are posted by different types of users, (iii) whose source tweets are of different types (hate, fake, controversial and others), and (iv) with different thread length. Unlike other baselines, DESSERT also outputs a confidence score with each prediction, which a content moderator may use to prioritize the tweets that need constant inspection.

Real-world deployment. DESSERT has been deployed in an advanced AI platform at Logically2 designed to monitor real-world problematic hateful content in large volumes of social media data. It has been tested by integrating into proprietary and custom pipelines that extract insights and intelligence to counter the spread of online harms. We observe that DESSERT offers complementary insights and has significant potential to improve the overall accuracy of the pipelines in detecting patterns and extracting insights concerning hate speech on real-world online content.

In particular, our contributions are five-fold: ▲ Novel problem definition. To our knowledge, we are the first to address the problem of forecasting hate intensity of upcoming reply threads of tweets. ▲ Novel model. Our proposed model, DESSERT leverages the advantages of classical signal processing and recently proposed deep learning techniques. ▲ New dataset: Our curated dataset consists of contemporary tweets and the entire reply threads on diverse topics that are posted across demography. ▲ Exhaustive results. DESSERT outperforms seven state-of-the-art baselines with significant margin. ▲ System deployment. DESSERT has been extensively tested and deployed by Logically in an advanced AI platform for detecting real-world problematic hateful content to extract insights for countering the spread of online harms (see Appendix).

Reproducibility. We present detailed hyper-parameter configurations in the Appendix. Source codes and datasets are available at https://github.com/LCS2-IIITD/DESSERt_KDD21.

RELATED WORK

We discuss the literature survey into three parts -hate speech detection, other studies related to hate speech, and some of the studies on time-series modeling which are pertinent to our paper. We also present how our method is different from existing studies.

Hate speech detection. Initial studies on hate speech detection [START_REF] Davidson | Automated Hate Speech Detection and the Problem of Offensive Language[END_REF] made use of n-gram based Logistic Regression and SVM; later Badjatiya et al. [START_REF] Badjatiya | Deep Learning for Hate Speech Detection in Tweets[END_REF] extended their work to LSTM. In last two years, bigger datasets [START_REF] Founta | Large Scale Crowdsourcing and Characterization of Twitter Abusive Behavior[END_REF] and BERT-based models have shown to perform better [START_REF] Mozafari | A BERT-Based Transfer Learning Approach for Hate Speech Detection in Online Social Media[END_REF]. In addition, Gomez et al. [START_REF] Gomez | Exploring Hate Speech Detection in Multimodal Publications[END_REF] explored the impact of multi-modality for hate detection. Over time, the focus also shifted from English datasets to diverse regional languages like Indonesian [START_REF] Okky | Multi-label Hate Speech and Abusive Language Detection in Indonesian Twitter[END_REF], Vietnamese [START_REF] Do | Hate Speech Detection on Vietnamese Social Media Text using the Bidirectional-LSTM Model[END_REF], Urdu [START_REF] Rizwan | Hate-Speech and Offensive Language Detection in Roman Urdu[END_REF], etc. In order to make the results of automatic hate speech classification explainable, Mathew et al. [START_REF] Mathew | HateXplain: A Benchmark Dataset for Explainable Hate Speech Detection[END_REF] proposed to capture words and phrases contributing to hate class. Poletto et al. [START_REF] Poletto | Resources and benchmark corpora for hate speech detection: a systematic review[END_REF] presented a comprehensive comparative study of various hate detection models. Note, in this work, we do not propose a new hate detection model, rather we leverage the existing state of art hate classifiers [START_REF] Davidson | Automated Hate Speech Detection and the Problem of Offensive Language[END_REF][START_REF] Founta | Large Scale Crowdsourcing and Characterization of Twitter Abusive Behavior[END_REF] for measuring hate intensity of a post.

Other studies on hate speech. Apart from the task of hate speech detection, hateful content has also been studied for analysing user characteristics and countering hateful information. Ribeiro et al. [START_REF] Ribeiro | Characterizing and Detecting Hateful Users on Twitter[END_REF] performed various statistical analysis to characterise hateful users on Twitter. Meanwhile, similar studies have been conducted on platforms like Gab [START_REF] Zannettou | What is Gab: A Bastion of Free Speech or an Alt-Right Echo Chamber[END_REF], BitChute [START_REF] Trujillo | What is BitChute? Characterizing The[END_REF], etc. To further study the dynamics of hate speech diffusion, Bagavathi et al. [START_REF] Bagavathi | Examining Untempered Social Media: Analyzing Cascades of Polarized Conversations[END_REF] performed exploratory analysis comparing hateful and non-hateful information cascades on Gab. We recently proposed a prediction model for hate speech diffusion on Twitter using exogenous signals [START_REF] Masud | Hate is the New Infodemic: A Topic-aware Modeling of Hate Speech Diffusion on Twitter[END_REF]. There have been studies around automatic hate countering on Facebook [START_REF] Mivskolci | Countering Hate Speech on Facebook: The Case of the Roma Minority in Slovakia[END_REF] and Twitter [START_REF] Mathew | Interaction Dynamics between Hate and Counter Users on Twitter[END_REF]. The benchmark datasets [START_REF] Chung | CONAN -COunter NArratives through Nichesourcing: a Multilingual Dataset of Responses to Fight Online Hate Speech[END_REF] and strategies [START_REF] Sinem Tekirouglu | Generating Counter Narratives against Online Hate Speech: Data and Strategies[END_REF] can be employed to build generative models that can act as first line of defence in countering hateful content [START_REF] Qian | A Benchmark Dataset for Learning to Intervene in Online Hate Speech[END_REF].

Time-series modeling. The classical techniques like ARMA [START_REF] Rojas | Soft-computing techniques and ARMA model for time series prediction[END_REF] and its variants (ARIMA, SARIMA) have shown outstanding performance in modeling time-series signals. These models are dependent on the assumption of data being linear and stationary, neither of which hold for real-time scenarios. They are collectively known as the Box-Jenkins method [START_REF] Box | Intervention analysis with applications to economic and environmental problems[END_REF]. Another alternate approach is the state-space model (SSM). Kalman filter is one such model widely used to forecast time-series signals when the model is linear, and the noise is modeled as Gaussian. Real application such as ours are even challenging for SSM as it requires prior knowledge of the state and observation parameters. Real-time streaming data is highly volatile; therefore, it becomes difficult to assume the model parameters in advance. The inability of signal processing techniques helped machine learning approaches gain popularity. These approaches can successfully address the learning-based system [START_REF] Hiransha | NSE stock market prediction using deep-learning models[END_REF] with no prior assumptions on the model parameters. One of its variant, RNNs are designed explicitly to address time-series signals. However, the performance of RNN degrades when the sequences grows longer due to long-term dependencies. To overcome this, Long Short Term Memory (LSTM) [START_REF] Elsworth | Time series forecasting using LSTM networks: A symbolic approach[END_REF] came into existence. LSTM still could not model the long-term dependencies well. These limitations paved the path for 1D CNN [START_REF] Mehtab | Robust Analysis of Stock Price Time Series Using CNN and LSTM-Based Deep Learning Models[END_REF]. The neural network approaches do not require specifications and prior knowledge of the model parameters. However, they do not provide any confidence score on the point estimate. Most of the research in time-series forecasting does not discuss the confidence score associated with the prediction. In recent years, its necessity has become prominent and has been considered crucial in addressing challenging applications [START_REF] Wesley | A simple baseline for bayesian uncertainty in deep learning[END_REF]. Several recent studies of time-series modeling capture the underlying non-linearity into the models [START_REF] Salinas | DeepAR: Probabilistic forecasting with autoregressive recurrent networks[END_REF].

Differences with the existing studies. Our work proposes a novel learning-based approach to bridge the gap between the state-space models and neural network approaches. Our proposed approach, DESSERT is a learning-based approach to model timeseries signals using deep state-space. DESSERT needs no structural details of model parameters and can model confidence score associated with the next timestamp prediction, thereby keeping both worlds' best.

PRELIMINARIES 3.1 Problem formulation

Given a tweet 𝜏 and its reply thread till 𝑡, denoted by R 𝜏 1,𝑡 = ⟨𝑟 𝜏 1 , 𝑟 𝜏 2 , . . . , 𝑟 𝜏 𝑡 ⟩, where 𝑟 𝜏 𝑡 denotes a reply tweet at time 𝑡, we aim to predict the intensity of hatred H (.) that the upcoming chunks of replies (each chunk with size Δ time window) will express, i.e., H R 𝜏 𝑡 +1,𝑡 +Δ ,. . ., H R 𝜏 𝑡 +(𝑛-1)Δ,𝑡 +𝑛Δ . Here, 𝑡 denotes an integer index associated to 𝑡-th reply in the sequence, not the actual (continuous) time. A reply chunk is a set of Δ consecutive replies to a source tweet 𝜏. This problem can be readily mapped to a classical time-series prediction problem as follows. We break R 𝜏 1,𝑡 into a sequence of chunks each with size Δ and calculate the hate intensity per window, i.e., H R 𝜏 1,Δ , H R 𝜏 Δ+1,2Δ , . . ., H R 𝜏 𝑡 -Δ,𝑡 . This constitutes the training data points. We then aim to predict the hate intensity of the next chunks of replies.

Quantifying hate intensity

In order to quantify H R 𝜏 𝑘,𝑘+Δ , the hate intensity of a chunk of replies posted between 𝑘 and 𝑘 + Δ, with 1 ≤ 𝑘 ≤ 𝑡 -Δ, we rely on two scores: a model-dependent score, and a lexicon-based score.

• Hate speech classifier: We employ a state-of-the-art hate speech classifier C which takes a reply 𝑟 and classifies it into hate speech with a score C(𝑟 ), indicating the probability of reply being a hate speech. We consider C(𝑟 ) in calculating H R 𝜏 𝑘,𝑘+Δ . • Lexical hate score: Wiegand et al. [START_REF] Wiegand | Inducing a Lexicon of Abusive Words -a Feature-Based Approach[END_REF] proposed a domainindependent hate lexicon with 2, 895 hate words. They also assigned hate score to each word in the lexicon. Given a reply 𝑟 , we check the presence of such hate words and sum up their hate scores to obtain a model-independent lexicon-based hate score per reply, denoted by L (𝑟 ).

The hate intensity of a reply 𝑟 is measured as,

H (𝑟 ) = 𝑤 C(𝑟 ) + (1 -𝑤)L (𝑟 ), (1)
where 𝑤 (0 ≤ 𝑤 ≤ 1) adjusts the weights of two components.

The hate intensity of a chunk of replies is measured by the sum of hate intensity of all the replies in that chunk, i.e.,

H R 𝜏 𝑘,𝑘+Δ = 𝑟 ∈R 𝜏 𝑘,𝑘+Δ H (𝑟 ) = 𝑤 𝑟 ∈R 𝜏 𝑘,𝑘+Δ C (𝑟 ) +(1-𝑤) 𝑟 ∈R 𝜏 𝑘,𝑘+Δ L (𝑟 ) . (2)
Note that 0 ≤ H R 𝜏 𝑘,𝑘+Δ ≤ ∞. Section 7.2 will show the results with different hate speech classifiers C, and varying 𝑤. For the chunks of replies till 𝑡 in the training set, we measure the hate

intensity of each chunk, H R 𝜏 1,Δ , H R 𝜏 Δ+1,2Δ , . . ., H R 𝜏 𝑡 -Δ,𝑡 .

Feature extraction from a reply chunk

In the training set, from a given chunk R 𝜏 𝑘,𝑘+Δ , we measure the hate intensity score of its constituent replies, i.e., H 𝑟 𝜏 𝑘 ), H 𝑟 𝜏 𝑘+1 ), . . ., H 𝑟 𝜏 𝑘+Δ ). From this, we extract five quantities, namely: (i) sum of hate intensities, H R 𝜏 𝑘,𝑘+Δ , (ii) hate intensity of the first reply for the chunk, H 𝑟 𝜏 𝑘 , (iii) hate intensity of the last reply for the chunk,

H 𝑟 𝜏 𝑘+Δ , (iv) max hate intensity, H R 𝜏 𝑘,𝑘+Δ max = max 𝑟 ∈R 𝜏 𝑘,𝑘+Δ H (𝑟 ), (v) min hate intensity, H R 𝜏 𝑘,𝑖+Δ min = min 𝑟 ∈R 𝜏 𝑘,𝑘+Δ H (𝑟 ).
This results in a 5-dimensional observed feature vector associated to R 𝜏 𝑘,𝑘+Δ :

x 𝑘 = H R 𝜏 𝑘,𝑘+Δ , H 𝑟 𝜏 𝑘 , H 𝑟 𝜏 𝑘+Δ , H R 𝜏 𝑘,𝑖+Δ max , H R 𝜏 𝑘,𝑖+Δ min .
The training set is formed by (x 𝑘 ) 1≤𝑘 ≤𝐾 where each x 𝑘 ∈ R 5 , and 𝐾 = 𝑡 -Δ is the number of chunks in the training set.

PROPOSED MODEL: DESSERT

Our objective is to predict the hate intensity of a reply thread for a given source tweet. We formulate this problem as a dynamical modeling problem. Off-the-shelf approaches to address such problems like ARMA, its variants, and state-space models, are proposed either in classical signal processing or in machine learning, namely RNN and its variants like LSTM and GRU. The disadvantage of signal processing approaches is that the underlying dynamical evolution function needs to be specified. This may be inappropriate in a typical scenario such as ours as the underlying evolution function is non-stationary and highly volatile in nature. On the other hand, machine learning approaches learn the underlying function from the data [START_REF] Hammer | On the approximation capability of recurrent neural networks[END_REF]. However, the shortcoming of off-the-shelf RNNs is that unlike state-space models, they cannot predict the confidence score around the estimate. The confidence score is highly relevant to our problem as based on this, the online content moderators may decide which thread to inspect manually.

To overcome the limitations of both, we propose DESSERT, a Deep State-Space (DSS) model. DESSERT is built on the advantages of both schools of methods. First, unlike the standard state-space model where the state evolution and the observation operators are supposed to be known apriori, we will learn it from the data. Second, in order to handle non-linearity, we introduce multiple layers of learnable parameters for both the observation and the state evolution. DESSERT keeps the ability of function approximation of neural networks (since it learns the parameters from the data) and the capacity to model uncertainty from classical state-space models. The schematic diagram of DESSERT is shown in Figure 2 4.1 Basis architecture

We consider (x 𝑘 ) 1≤𝑘 ≤𝐾 the observed time-ordered sequence vector of size 𝑁 𝑥 , (z 𝑘 ) 1≤𝑘 ≤𝐾 is the latent state-space vector of size 𝑁 𝑧 that we want to infer, and (v 𝑘 ) 1≤𝑘 ≤𝐾 models the noise. As explained in Section 3.3, we consider 𝑁 𝑥 = 5 features. Moreover, we consider the possibility of a multivariate hidden feature space, i.e., 𝑁 𝑧 can be greater than 1. The original linear state-space model is given by,

z 𝑘 = Az 𝑘-1 + v 1,𝑘 , x 𝑘 = Hz 𝑘 + v 2,𝑘 , (3)
where the matrices, A and H, are the learnable parameters. When A and H are known, the solution is the celebrated Kalman filter. When the parameters are unknown, the solution to the blind Kalman filtering problem has been recently investigated in [START_REF] Sharma | Blind Kalman Filtering for Short-term Load Forecasting[END_REF]. A limitation of this aforementioned work is that it cannot handle non-linearity in the dynamical system. In this present study, we propose to account for the non-linearity by introducing multiple layers (3 layers in our case) in the model. The DSS model is given as follows. For every

𝑘 ∈ {1, . . . , 𝐾 }, z 𝑘 = A 0 A 1 A 2 z 𝑘-1 + v 1,𝑘 , x 𝑘 = H 0 H 1 H 2 z 𝑘 + v 2,𝑘 , (4)
where A 0 , A 1 , A 2 and H 0 , H 1 , H 2 can be understood as latent factors for the state matrix A and the observation matrix H, respectively. Process noise (v 1,𝑘 ) 1≤𝑘 ≤𝐾 is zero-mean Gaussian with covariance matrix Q, and the observation noise (v 2,𝑘 ) 1≤𝑘 ≤𝐾 is zeromean Gaussian with covariance matrix R. Then Equation 4 describes a first-order Markovian multi-linear Gaussian model, where (z 𝑘 ) 1≤𝑘 ≤𝐾 is the sequence of 𝐾 unknown states, which can be seen as learned features for describing the data. The goal is the joint inference from the observed sequence

(x 𝑘 ) 1≤𝑘 ≤𝐾 of the fac- tors A 0 ∈ R 𝑁 𝑧 ×𝑁 𝑧 , A 1 ∈ R 𝑁 𝑧 ×𝑁 𝑧 , A 2 ∈ R 𝑁 𝑧 ×𝑁 𝑧 , H 0 ∈ R 𝑁 𝑥 ×𝑁 𝑧 , H 1 ∈ R 𝑁 𝑧 ×𝑁 𝑧 , H 2 ∈ R 𝑁 𝑧 ×𝑁 𝑧 and of the hidden state sequence (z 𝑘 ) 1≤𝑘 ≤𝐾 .
This problem can be considered as blind filtering inference where both the estimated series and model parameters are unknown initially, and will be learnt and estimated from the data. The model is expected to understand trends and update its parameters for every chunk from the data. This can be done following an expectationmajorization algorithm [START_REF] Särkkä | Bayesian filtering and smoothing[END_REF]. The problem is solved in an alternating manner where we alternate between (i) the estimation of the state, considering operators A 0 , A 1 , A 2 , H 0 , H 1 , H 2 being fixed, and (ii) the update of the parameters, assuming fixed state. Both steps are elaborated below.

State update

This is the first step where we consider the parameters A 0 , A 1 , A 2 , H 0 , H 1 , H 2 to be fixed and known, and the goal is to infer the latent (

) 5
where z𝑘 ∈ R 𝑁 𝑧 and P 𝑘 ∈ R 𝑁 𝑧 ×𝑁 𝑧 are the mean and covariance, respectively, of the filtering distribution. For every 𝑘 ∈ {1, . . . , 𝐾 }, z𝑘 and P 𝑘 can be computed by means of the Kalman filter recursions as follows: For 𝑘 = 1, . . . , 𝐾 Predict state:

z - 𝑘 = A 0 A 1 A 2 z𝑘-1 , P - 𝑘 = A 0 A 1 A 2 P 𝑘-1 (A 0 A 1 A 2 ) ⊤ + Q. (6)
Update state:

           y 𝑘 = x 𝑘 -H 0 H 1 H 2 𝑧 - 𝑘 , S 𝑘 = H 0 H 1 H 2 P - 𝑘 (H 0 H 1 H 2 ) ⊤ + R, K 𝑘 = P - 𝑘 (H 0 H 1 H 2 ) ⊤ S -1 𝑘 , z𝑘 = z - 𝑘 + K 𝑘 y 𝑘 , P 𝑘 = P - 𝑘 -K 𝑘 S 𝑘 K ⊤ 𝑘 . (7)
The Rauch-Tung-Striebel (RTS) smoother [START_REF] Särkkä | Bayesian filtering and smoothing[END_REF] makes a backward recursion on the data which makes use of the filtering distributions computed by the Kalman filter to obtain the smoothing distribution 𝑝 (z 𝑘 |x 1...𝐾 ). Below, we summarize the RTS recursions: For 𝑘 = 𝐾, . . . , 1 Backward Recursion (Bayesian Smoothing):

           z - 𝑘+1 = A 0 A 1 A 2 z𝑘 , P - 𝑘+1 = A 0 A 1 A 2 P 𝑘 (A 0 A 1 A 2 ) ⊤ + Q, G 𝑘 = P 𝑘 (A 0 A 1 A 2 ) ⊤ (P - 𝑘+1 ) -1 , z 𝑠 𝑘 = z 𝑘 + G 𝑘 [z 𝑠 𝑘+1 -z - 𝑘+1 ], P 𝑠 𝑘 = P 𝑘 + G 𝑘 (P 𝑠 𝑘+1 -P - 𝑘+1 )G ⊤ 𝑘 . (8)
As a result, the smoothing distribution at each time 𝑘 is a multivariate Gaussian with closed-form given by, 𝑝 (z 𝑘 |x 1...𝐾 ) = N (z 𝑘 ; z 𝑠 𝑘 , P 𝑠 𝑘 ).

Parameter updates

The training procedure of DESSERT requires an alternating iteration of Kalman filter/smoother, considering parameters to be known and fixed initially (E-step), followed by the model/state parameters estimation assuming latent states to be fixed (M-step) [START_REF] Särkkä | Bayesian filtering and smoothing[END_REF]. It starts with an initialization stage A

[0]

0 , A [0] 1 , A [0]
2 and

H [0] 0 , H [0] 1 , H [0]
2 . For every iteration 𝑖, it runs the RTS scheme, presented in Section 4.2, then computes the updates A

[𝑖+1] 0 , A [𝑖+1] 1 , A [𝑖+1] 2 and H [𝑖+1] 0 , H [𝑖+1] 1 , H [𝑖+1] 2 ,
given their estimates at previous EM iteration, i.e., A

[𝑖 ] 0 , A [𝑖 ] 1 , A [𝑖 ] 2 and H [𝑖 ] 0 , H [𝑖 ] 1 , H [𝑖 ]
2 . This amounts to maximizing this lower bound, so as to increase the marginal log-likelihood of these six deep latent factors, given the observed data. Let us introduce some useful quantities, defined from the RTS recursion:

𝚺 [𝑖 ] = 1 𝐾 𝐾 𝑘=1 P 𝑠 𝑘 + z 𝑠 𝑘 (z 𝑠 𝑘 ) ⊤ ; 𝚽 [𝑖 ] = 1 𝐾 𝐾 𝑘=1 P 𝑠 𝑘-1 + z 𝑠 𝑘-1 (z 𝑠 𝑘-1 ) ⊤ , B [𝑖 ] = 1 𝐾 𝐾 𝑘=1 x 𝑘 (z 𝑠 𝑘 ) ⊤ ; D [𝑖 ] = 1 𝐾 𝐾 𝑘=1 P 𝑠 𝑘 G ⊤ 𝑘-1 + z 𝑠 𝑘 (z 𝑠 𝑘-1 ) ⊤ , (9)
𝚪 [𝑖 ] = 1 𝐾 𝐾 𝑘=1 x 𝑘 x ⊤ 𝑘 .
Then, the computation of

A [𝑖+1] 0 , A [𝑖+1] 1 , A [𝑖+1] 2
and

H [𝑖+1] 0 , H [𝑖+1] 1 , H [𝑖+1] 2
amounts to solving the following subproblems (see Appendix B for detailed derivations):

A [𝑖+1] 0 = argmin A 0 K 2 tr Q -1 𝚺 [i] -D [i] (A 0 A [i] 1 A [i] 2 ) ⊤ -A 0 A [𝑖 ] 1 A [𝑖 ] 2 (D [𝑖 ] ) ⊤ + A 0 A [𝑖 ] 1 A [𝑖 ] 2 𝚽 [𝑖 ] (A 0 A [𝑖 ] 1 A [𝑖 ] 2 ) ⊤ , A [𝑖+1] 1 = argmin A 1 K 2 tr Q -1 𝚺 [i] -D [i] (A [i+1] 0 A 1 A [i] 2 ) ⊤ -A [𝑖+1] 0 A 1 A [𝑖 ] 2 (D [𝑖 ] ) ⊤ + A [𝑖+1] 0 A 1 A [𝑖 ] 2 𝚽 [𝑖 ] (A [𝑖+1] 0 A 1 A [𝑖 ] 2 ) ⊤ , A [𝑖+1] 2 = argmin A 2 K 2 tr Q -1 𝚺 [i] -D [i] (A [i+1] 0 A [i+1] 1 A 2 ) ⊤ -A [𝑖+1] 0 A [𝑖+1] 1 A 2 (D [𝑖 ] ) ⊤ + A [𝑖+1] 0 A [𝑖+1] 1 A 2 𝚽 [𝑖 ] (A [𝑖+1] 0 A [𝑖+1] 1 A 2 ) ⊤ .
And,

H [𝑖+1] 0 = argmin H 0 K 2 tr R -1 𝚪 [i] -B [i] (H 0 H [i] 1 H [i] 2 ) ⊤ -H 0 H [𝑖 ] 1 H [𝑖 ] 2 (B [𝑖 ] ) ⊤ + H 0 H [𝑖 ]
1 H

[𝑖 ]

2 𝚺 [𝑖 ] (H 0 H

[𝑖 ]

1 H

[𝑖 ]

2 ) ⊤ ,

H [𝑖+1] 1 = argmin H 1 K 2 tr R -1 𝚪 [i] -B [i] (H [i+1] 0 H 1 H [i] 2 ) ⊤ -H [𝑖+1] 0 H 1 H [𝑖 ] 2 (B [𝑖 ] ) ⊤ + H [𝑖+1] 0 H 1 H [𝑖 ] 2 𝚺 [𝑖 ] (H [𝑖+1] 0 H 1 H [𝑖 ] 2 ) ⊤ , H [𝑖+1] 2 = argmin H 2 K 2 tr R -1 (𝚪 [i] -B [i] (H [i+1] 0 H [i+1] 1 H 2 ) ⊤ -H [𝑖+1] 0 H [𝑖+1] 1 H 2 (B [𝑖 ] ) ⊤ + H [𝑖+1] 0 H [𝑖+1] 1 H 2 𝚺 [𝑖 ] (H [𝑖+1] 0 H [𝑖+1] 1 H 2 ) ⊤ .
where tr(•) denotes the trace operator, Q is covariance matrix for the process noise, and R is the covariance matrix for the observation noise.

Due to the quadratic form of the above problems, the update of each deep factor takes a closed form:

A [𝑖+1] 0 = D [𝑖 ] (A [𝑖 ] 2 ) ⊤ (A [𝑖 ] 1 ) ⊤ A [𝑖 ] 1 A [𝑖 ] 2 Φ [𝑖 ] (A [𝑖 ] 2 ) ⊤ (A [𝑖 ] 1 ) ⊤ -1 , A [𝑖+1] 1 = (A [𝑖+1] 0 ) ⊤ Q -1 A [𝑖+1] 0 -1 (A [𝑖+1] 0 ) ⊤ Q -1 D [𝑖 ] (A [𝑖 ] 2 ) ⊤ A [𝑖 ] 2 𝚽 [𝑖 ] (A [𝑖 ] 2 ) ⊤ -1 , A [𝑖+1] 2 = (A [𝑖+1] 1 ) ⊤ (A [𝑖+1] 0 ) ⊤ Q -1 A [𝑖+1] 0 A [𝑖+1] 1 -1 (A [𝑖+1] 1 ) ⊤ (A [𝑖+1] 0 ) ⊤ Q -1 D [𝑖 ] (𝚽 [𝑖 ] ) -1 .
And,

H [𝑖+1] 0 = B [𝑖 ] (H [𝑖 ] 2 ) ⊤ H [𝑖 ] 1 ) ⊤ (H [𝑖 ] 1 H [𝑖 ] 2 𝚺 [𝑖 ] (H [𝑖 ] 2 ) ⊤ (H [𝑖 ] 1 ) ⊤ -1 , H [𝑖+1] 1 = (H [𝑖+1] 0 ) ⊤ R -1 H [𝑖+1] 0 -1 (H [𝑖+1] 0 ) ⊤ R -1 B [𝑖 ] (H [𝑖 ] 2 ) ⊤ H [𝑖 ] 2 𝚺 [𝑖 ] (H [𝑖 ] 2 ) ⊤ -1 , H [𝑖+1] 2 = (H [𝑖+1] 1 ) ⊤ (H [𝑖+1] 0 ) ⊤ R -1 H [𝑖+1] 0 H [𝑖+1] 1 -1 (H [𝑖+1] 1 ) ⊤ (H [𝑖+1] 0 ) ⊤ R -1 B [𝑖 ] (𝚺 [𝑖 ] ] ) -1 .

On the fly training

A limitation of the EM strategy is that it requires reprocessing the full dataset to compute the updates for the state and observation model parameters. On top of being computationally cumbersome, this strategy implicitly assumes the static values of these parameters over time during the processing of the whole sequence which may not be a well-suited practice due to the lack of stationarity in the data. Indeed, tweeter trends are expected to evolve over time. Moreover, in real-time applications, users may want rapid feedback on the hate intensity evolution. We thus propose here a strategy to make DESSERT suitable for online training, reminiscent of recent implementations of stochastic majorization-minimization algorithms [START_REF] Chouzenoux | A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation[END_REF]. We set a window (or mini-batch) size 𝛼 ≥ 1. At each time step 𝑘, the static parameters are estimated using the last 𝛼 observations contained in the set X 𝑘 = {x 𝑗 } 𝑘 𝑗=𝑘-𝛼+1 . In particular, we run RTS only on the recent 𝛼 observed data; then we update the parameters using the smoothing results. This sliding-window strategy presents two advantages. First, introducing 𝛼 leads to faster processing. Second, it also allows better modeling of piece-wise linear processes that vary faster. The price to pay is that a smaller number of observations also limits the estimation capabilities. For initializing the RTS iterations, we use a warm start strategy. We set the parameters to their last updated values for the next timestamp. We initialize the mean and covariance of the state at 𝑘 -𝛼 + 1 using the smoothing results from the last update of the parameters in this window. Note that if 𝛼 = 𝐾, the algorithm goes back to the original offline version.

Forecasting

As explained in Section 4.1, we proceed in a sliding window fashion. For each particular observed window X 𝑘 , the training of DESSERT allows to extract features and finds the update for parameters by iterating alternatively EM steps. After stabilization of the EM iterations (for this task, 10 iterations were sufficient for the EM to reach convergence), we can then use the output to predict the hate intensity of upcoming chunk of replies. More precisely, for every 𝑘 ∈ {0, . . . , 𝐾 -𝛼 }, we apply DESSERT on {x 𝑗 } 𝑘 𝑘 ≤ 𝑗 ≤𝑘+𝛼 which provides the estimate,

x 𝑘+𝛼+1 = H 0 H 1 H 2 z - 𝑘+𝛼 , (10)
associated with a covariance matrix S 𝑘+𝛼 , for the immediate next reply chunk indexed by 𝑘 + 𝛼 + 1. Note that although DESSERT will perform the prediction on the whole 5-dimensional vector, we will particularly be interested in the ability of our model to perform prediction on a single entry of the vector of interest, i.e., the overall hate intensity of the chunk H R 𝜏 𝑘,𝑘+Δ .

Model confidence

Due to the probabilistic approach in Kalman filter, our DESSERT model can estimate the confidence score associated with the prediction. DESSERT indeed provides distribution of the next observation conditioned to the previously seen data, which is also called predictive distribution of the observation. Such probabilistic validation allows to quantify how much the model is (un)certain while predicting the next chunk hate intensity. Let us express, for every chunk index 𝑘, the distribution of the forecasted x 𝑘 given the past observations:

𝑝 ( x 𝑘 |x 1:𝑘-1 ) = N x 𝑘 ; H 0 H 1 H 2 z - 𝑘 , S 𝑘 , (11)
where andz - 𝑘 , P 𝑘 are byproducts of the Kalman filter, defined in Section 4.2 (see [START_REF] Elvira | Adapting the Number of Particles in Sequential Monte Carlo Methods through an Online Scheme for Convergence Assessment[END_REF] for more details about the predictive distribution of the observations). In our case, we would like to quantify our confidence score about the prediction given by the model for the hate intensity. More precisely, we focus on forecasting the sum of hate intensity, as defined in Section 3.3, for the next chunk of replies, i.e., predicting the first entry of x 𝑘 , denoted by x 𝑘 [0]. The value of the first row/column of S 𝑘 , denoted by S 𝑘 [0, 0], gives us the uncertainty quantification about such prediction. Unless otherwise stated, DESSERT puts 95% of confidence on x 𝑘 [0] to belong to the interval

S 𝑘 = H 0 H 1 H 2 ((A 1 A 2 A 3 )P 𝑘-1 (A 1 A 2 A 3 ) ⊤ + Q) + R,
[H 0 H 1 H 2 z - 𝑘 ] [0] ± S 𝑘 [0, 0]
. We can even go further in the analysis. For instance, we can define the confidence score about an increase of the hate intensity as:

𝑝 𝑘 = ∫ +∞ x 𝑘 [0] N 𝑦; H 0 H 1 H 2 z - 𝑘 [0], S 𝑘 [0, 0] 𝑑𝑦 (12) = 1 -CDF( x 𝑘 [0]| H 0 H 1 H 2 z - 𝑘 [0], S 𝑘 [0, 0]), ( 13
)
where CDF denotes the cumulative distribution function for the multivariate Gaussian model. Equation 12quantifies the probability that the hate intensity will grow in the next time step. Once we have determined 𝑝 𝑘 for every chunk index 𝑘, we can validate the method by using the standard cross-entropy loss as:

log-loss = 1 𝐾 𝐾 𝑘=1 -𝐿 𝑘 [𝑖] log( 𝑝 𝑘 ) , (14)
where 𝐿 𝑘 ∈ {0, 1} represents the ground-truth at time 𝑘 for increase (i.e., 𝐿 𝑘 = 1) /decrease (i.e., 𝐿 𝑘 = 0) of x 𝑘 [0] from 𝑘 -1 to 𝑘.

Time complexity

£ Training. Let us express the complexity for training DESSERT in a given window of length 𝛼. To this aim, we rely on the complexity analysis for Kalman-based approaches available in [START_REF] Montella | The Kalman filter and related algorithms: A literature review[END_REF], which leads to a complexity of O (𝛼𝑁 2.376

𝑧

). £ Testing. The testing phase just amounts to evaluating the multi-linear equation (Equation 10). This has complexity of O (𝑁 𝑥 𝑁 2 𝑧 ) for each chunk. It can be reduced to O (𝑁 2 𝑧 ) if we want to forecast only one feature (which is the case in our setting, i.e., only the overall hate intensity).

DATASET DESCRIPTION

For our problem setting, we require reply threads of tweets. Since existing Twitter API does not provide the entire reply thread of a tweet, we first identified source tweets and systematically scraped timelines of users who replied to these tweets. To identify the source tweets, we searched with hashtags related to 2020 US presidential elections (e.g., #MagaTerrorists, #StopTheSteal), COVID-19 (e.g., #ChinaVirus, #TrumpVirus), the Brexit referendum in the UK (e.g., #brexitshambles, #stopbrexit), and other political issues in the US, the UK and India (e.g., #BorisResign, #ToryCovidCatastrophe, #CAA, #NRC). We focused on the US and the UK more to avoid tweets in regional/code-mixed languages. The data collection was carried out during October 2020 to January 2021. The complete dataset contains 4, 533 reply threads. In the Appendix, Figures 6(a) and 6(b) show the length distribution of reply threads and the distribution of the number of unique users involved in reply threads, respectively. The average thread length is 213, and the average number of unique users per thread is 187.

In Section 7.2, we study how the hate intensity of reply threads varies across different types of source tweets such as hate, fake, and controversial (these labels were provided by Logically's content moderators). Each reply thread is split into two parts: first 70% replies are used for training and remaining 30% for forecasting.

BASELINE METHODS

To the best of our knowledge, there is no prior work on forecasting hate intensity of a reply threads on Twitter. We, therefore, consider statistical and deep learning based time-series and temporal pattern modeling approaches.

ARIMA. It is one of the classical time-series prediction models based on auto regressive integrated moving average. LSTM. We use a stacked 2-layer LSTM with 50 cells each. We use a dense layer with ReLU activation for final prediction [START_REF] Elsworth | Time series forecasting using LSTM networks: A symbolic approach[END_REF]. CNN. We use a 1D Convolutional layer with 64 filters and a kernel size of 2. This is followed by a max-pooling layer which feeds result into a fully-connected layer with ReLU activation for final prediction [START_REF] Mehtab | Robust Analysis of Stock Price Time Series Using CNN and LSTM-Based Deep Learning Models[END_REF]. N-Beats. It uses the idea that the base architecture should be simple and generic, yet expressive (deep). It does not rely on time-series specific feature engineering or input scaling [START_REF] Boris N Oreshkin | N-BEATS: Neural basis expansion analysis for interpretable time series forecasting[END_REF].

DeepAR. It aims to produce probabilistic forecasts specifically on a large number of related time series [START_REF] Salinas | DeepAR: Probabilistic forecasting with autoregressive recurrent networks[END_REF].

TFT. Temporal Fusion Transformers is an attention-based architecture which combines high-performance multi-horizon forecasting with interpretable insights into temporal dynamics [START_REF] Lim | Temporal Fusion Transformers for Interpretable Multi-horizon Time Series Forecasting[END_REF].

ForGAN. It utilizes conditional generative adversarial network to learn the data generating distribution and compute probabilistic forecasts [START_REF] Koochali | Probabilistic forecasting of sensory data with generative adversarial networksforgan[END_REF].

EXPERIMENTAL RESULTS

For comparison, we use one correlation-based metric (higher is better) -Pearson correlation coefficient (𝑟 ), and three metrics for error calculation (lower is better) -Root mean square error (RMSE), Mean Absolute Percentage Error (MAPE) and Symmetric Mean Absolute Percentage Error (SMAPE). Default setup. Unless otherwise mentioned, we consider the following setup as default: 𝑤 = 0.5, Δ = 10, 𝛼 = 20, 𝑁 𝑧 = 5, 𝑁 𝑥 =5 and DESSERT with 3 layers, and hyperparameters Q = 𝜎 2 𝑄 I, R = 𝜎 2 𝑅 I, P 0 = 𝜎 2 𝑃 I, with (𝜎 𝑄 , 𝜎 𝑅 , 𝜎 𝑃 ) = (10 -5 , 10 -1 , 10 -1 ), 𝑧 0 = 0 (I : identity matrix), and the hate speech classifier C by Founta et al. [START_REF] Antigoni | A Unified Deep Learning Architecture for Abuse Detection[END_REF].

Overall performance

Table 1 shows the performance of the competing models. Clearly, DESSERT outperforms all the baselines with a significant margin. DESSERT (3 layers) achieves 0.113 points gain in Pearson's 𝑟 , 0.065 points drop in RMSE, and 12.39% and 4.57% drop in MAPE and SMAPE respectively compared to ForGAN (the best baseline). Among the baselines, ARIMA and LSTM/CNN perform the worst.

An advantage of DESSERT over other deep learning based baselines is that it estimates a confidence score along with the prediction (which statistical signal processing models also produce). As discussed earlier in Section 4.6, DESSERT helps to estimate the probabilistic validation. One can estimate the (un)certainty of the prediction of an increase/decrease of the hate intensity, from the log-loss value (Equation 14). Smaller is the loss, more accurate is the model for its prediction of an increase/decrease of hate intensity. This information helps the practitioners to understand the impact, in terms of hate causality, for a given thread. For instance, in our dataset, the log-loss associated to a thread (i.e., 'Hate' category, c.f. Section 7.2) is 2.51, meaning that the consequences of this category of thread is highly predictable. It is expected as 'Hate' content will tend to generate more hateful reactions. In contrast, the broader category 'Others', corresponding to another thread, seems more difficult to assess, having a log-loss of 5.38.

Detailed analysis

Further, we delve deeper into the results of DESSERT and the best baseline (ForGAN) to understand how they generalize. Results across demography. Figure 3(a) shows how DESSERT and ForGAN perform on the reply threads of the source tweets originated from different countries -the US, the UK, and others (India, Brazil, Australia). DESSERT is consistent across geographic locations.

Types of Source tweets. The content moderation team at Logically further annotated 1830 randomly selected source tweets into 'fake' (518), 'hate' (582), 'controversial' (550) and 'others' (180). We aim to understand how the models perform for different types of source tweets. Once again, DESSERT shows steady performance across different types (c.f. Figure 3(b)). Types of source users. One may wonder if the prestige of online users drives the toxicity of the reply thread. To check this, we divide the reply threads into five equal bins based on the follower count of the users who posted the source tweets. Figure 3(c) shows that unlike ForGAN, DESSERT is agnostic to types of the source users. Length of reply threads. One may wonder how the forecasting varies with the overall length of the reply threads. Here, we divide the reply threads into five equal bins based on the length of the threads. Figure 3(d) shows that although ForGAN improves with the increase of length, DESSERT remains highly consistent. Foreseeability & early prediction. So far, we have considered reply tweets till 𝑡 and reported the prediction for the immediate reply thread, i.e., R 𝜏 𝑡,𝑡 +Δ . Here, we are interested to check that with the same training data, how far the models can predict. We further allow the models to predict for R 𝜏 𝑡 +(𝑛-1)Δ,𝑡 +𝑛Δ , with 𝑛 = 1, 3, 5, 7. Also, it captures how early our model can predict. Figure 3(e) shows that DESSERT does not deteriorate much even at 𝑛 = 7. Hate speech classifier. To compute hate intensity, we have used a hate speech classifier C in Equation 1. Here, we check how the models respond if we change C. We replace our default C [START_REF] Founta | Large Scale Crowdsourcing and Characterization of Twitter Abusive Behavior[END_REF] by the hate speech detection method proposed by Davidson et al. [START_REF] Davidson | Automated Hate Speech Detection and the Problem of Offensive Language[END_REF] and observe that DESSERT still outperforms ForGAN (Figure 3(f)). Varying 𝑤. In Eq. 1, the weight 𝑤 balances the effect of the hate speech classifier and the lexicon to measure hate intensity. Figure 3(g) shows that DESSERT's accuracy does not depend much on 𝑤. Varying Δ. Figure 3(h) shows that with the increase of chunk size Δ, both ForGAN and DESSERT improve.

Ablation study

Varying layers. Table 1 shows that DESSERT performs the best with three layers. Varying 𝛼. In DESSERT, the parameter 𝛼 indicated how much historical data we consider for prediction. As expected, Figure 4(a) shows that increasing 𝛼 results in better prediction. Changing training size. We experiment with three different sizes of the training set -50%, 60% and 70%.

CONCLUSION

In this paper, we attempted to predict the hate intensity of upcoming replies for a source tweet. We employed a series of timeseries forecasting models and showed that they do not perform well on the dataset we curated. We further proposed DESSERT, a deep state-space model that significantly outperforms all the baselines. Detailed study further brought out how DESSERT generalizes w.r.t. several decision choices. Further, DESSERT has been deployed in Logically's advanced AI platform for monitoring online problematic hateful content and recommend countermeasures to minimise its reach and reduce the damage (see Appendix). In future, we intend to capture user metadata and graph-level signals to enhance the accuracy.

(Appendix / Supplementary Material)

A ADDITIONAL RESULTS

Figure 6 shows the distribution of the reply thread length and the number of unique users per reply thread. Figure 5 shows that there is not single quarter of the threads which is most hateful across all the threads. This indicates that the forecasting is not straightforward, and there is no underlying function which models the hate intensity pattern. Figure 7 shows the detailed analysis of the results in terms of Pearson's 𝑟 . Figure 8 shows the ablation results in terms of Pearson's 𝑟 . DeepAR. We use the default implementation for this model, with 2 RNN layers having LSTM cells with the hidden recurrent size as 10. We set 𝑙𝑜𝑔_𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙, 𝑙𝑜𝑔_𝑣𝑎𝑙_𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙, 𝑤𝑒𝑖𝑔ℎ𝑡𝑑𝑒𝑐𝑎𝑦 to 10, 1, 0.01 respectively. We run the trainer for a maximum of 200 epochs on a batch size of 16. TFT. We use the default implementation, with the number of LSTM layers set to 2 and the hidden size of the network set to 8. We set the 𝑙𝑜𝑔_𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙, 𝑙𝑜𝑔_𝑣𝑎𝑙_𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 and 𝑤𝑒𝑖𝑔ℎ𝑡𝑑𝑒𝑐𝑎𝑦 to 10, 1, 0.01 respectively. The model runs for a maximum of 200 epochs.

ForGAN. We use the default architecture, with LSTM layers of sizes 8 and 64 for the RNN based generator and discriminator, respectively. The model runs for a maximum of 800 epochs. DESSERT. Thanks to our warm start strategy, the initialisation of hyper-parameters A 2 with uniform independent entries in [0, 1]. All results are averaged over a set of four random initializations. Moreover, we empirically tuned hyper-parameters 𝜎 𝑄 , 𝜎 𝑅 , 𝜎 𝑃 , 𝑁 𝑧 , 𝑁 𝑥 and window size 𝛼 to 10 -5 , 10 -1 , 10 -1 , 5, 5, 20 respectively.

D DEPLOYMENT DETAILS

Logically's advanced AI platform is a real-world system that can ingest and analyse data from millions of media sources as well as social media posts. Proprietary models and custom pipelines in the platform harness state-of-the-art machine learning and NLP to identify and analyse online problematic harmful content at-scale. Built on cutting-edge, secure and highly scalable cloud infrastructure, the platform brings together Logically's capabilities in granular analysis, classification and detection of damaging harmful content, its origins and impact. It also provides access to a diverse set of stakeholders in different market segments, a suite of countermeasures to tackle identified problematic content by leveraging in-house expert analysts in fact-checking and OSINT research.

The technology side of the platform is uniquely developed by implementing state-of-the-art in AI research and industry best practices in software architecture and engineering. In order to achieve high-quality analytical throughput on large volumes of data, the platform leverages cutting-edge cloud technologies such as Kubernetes, which works with a range of container tools including Docker to make software applications highly scalable. On the other hand, the platform applies state-of-the-art AI research to customise and iteratively evolve its methodologies for effective modelling of heterogeneous (articles, social media posts, multimedia) data sources to build reliable AI models that can augment its expert intelligence network of editors, fact checkers, content moderators and OSINT analysts.

Deployment of multiple AI models is possible in the platform as it implements micro services architecture to empower a range of products built by Logically with AI-based insights through an ensemble of REST based machine learning services. This feature of the platform offered the flexibility to integrate DESSERT as a REST micro-service to evaluate its hate speech intensity annotations alongside the company's proprietary models and custom pipelines for problematic hateful content analysis. Further, the evaluation revealed that the intensity scores from DESSERT offer additional knowledge to the proprietary models for ranking and prioritization of high risk online harms for enforcement of countermeasures to minimize their impact and damage. We plan to further test DESSERT extensively on multiple heterogeneous social media data streams ingested by the platform to understand its abilities to generalise in accurately and reliably detecting hate speech patterns. Also we intend to evaluate DESSERT and its future enhanced versions in the AI platform to extract insights to better detect custom online harms across domains such as health, finance and geopolitics.

Figure 1 :

 1 Figure 1: (a) An example reply thread with the hate intensity per reply (within brackets). (b) Hate intensity profile of three example reply threads, one of which is (a). We observe that that the hate intensity of reply threads does not follow any particular pattern. (c) Scatter plot of hate intensity of the source tweets and their corresponding reply threads, indicating they are uncorrelated (Pearson's 𝑟 =0.11).

Figure 2 :

 2 Figure 2: Schematic diagram of DESSERT where x 𝑘 represents the input (ordered sequence of vectors), z 𝑘-1 represents the hidden state-space vector (i.e. feature) for previous timestamp. A 0 , A 1 , A 2 , H 0 , H 1 , H 2 are the learnable parameters, and z 𝑘 represents the hidden state-space vector for current timestamp.

Figure 3 :

 3 Figure 3: Performance (MAPE) of DESSERT and ForGAN w.r.t (a) demography, (b) types of source tweets, (c) types of source users, (d) length of reply threads, (e) foreseeability, (f) hate speech classifiers (Founta et al. [13] and Davidson et al. [7]), (g) weight 𝑤, and (h) chunk size Δ. See the Appendix for the correlation-based (Pearson's 𝑟 ) performance.

  Fig. 4(b) shows that unlike ForGAN, DESSERT remains effective with varying training size.

Figure 4 :

 4 Figure 4: Model ablation w.r.t. (a) 𝛼 and (b) training size.

Figure 5 :

 5 Figure 5: Heat map showing the hate intensity per quarter of the reply threads (sorted by the hate intensity of the source tweets). We divide each reply thread into four equal quarters and measure hate intensity per quarter. It indicates that there is no single quarter which is always more hateful than the others across reply threads.

Figure 6 :

 6 Figure 6: Distribution of (a) the length of reply threads and (b) the number of unique users involved in reply threads.

Figure 7 :

 7 Figure 7: Performance (Pearson's 𝑟 ) of DESSERT and ForGAN w.r.t (a) demography, (b) types of source tweets, (c) types of source users, (d) length of reply threads, (e) foreseeability, (f) hate speech classifiers (Founta et al. [13] and Davidson et al. [7]), (g) weight 𝑤, and (h) chunk size Δ.

Figure 8 :

 8 Figure 8: Model ablation w.r.t. (a) 𝛼 and (b) training size.

  required for the very first chunk of the training set, i.e., for 𝑘 = 𝑡 = 0. In practice, we initialized A

Table 1 :

 1 Overall performance (↓: lower value is better).

	Model	𝑟	RMSE ↓ MAPE (%) ↓ SMAPE (%) ↓
	ARIMA	0.138	0.584	70.17	54.73
	LSTM	0.331	0.515	76.53	46.34
	CNN	0.251	0.454	54.68	43.40
	N-Beats	0.322	0.388	47.25	39.94
	DeepAR	0.308	0.386	48.95	38.56
	TFT	0.511	0.413	45.88	40.39
	ForGAN	0.557	0.397	43.47	38.58
	DESSERT (1 layer)	0.671	0.342	32.28	35.28
	DESSERT (2 layers) 0.665	0.394	32.69	35.66
	DESSERT (3 layers) 0.670	0.332	31.08	34.01

DEep State-SpacE model for hate intensity prediction of Reply Threads.

https://www.logically.ai (see Appendix for more details about Logically).

B EXPECTATION-MINIMIZATION

The training of DESSERT requires the estimation of the matrices A 0 , A 1 , A 2 and H 0 , H 1 , H 2 jointly with the state. This problem can be solved efficiently using an expectation-maximization (EM) algorithm [START_REF] Särkkä | Bayesian filtering and smoothing[END_REF], that alternates classic Kalman filtering/smoothing and the update of matrix parameters, with the aim of reaching the maximum likelihood (ML) estimator of those parameters. With the proposed DESSERT model in Eq. 4, the EM consists in searching for

The EM algorithm is a type of majorization-minimization [START_REF] Chouzenoux | A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation[END_REF] approach. It allows to compute a lower bound 𝑄 of the marginal likelihood, satisfying that, for any A 0 , A 1 , A 2 , and

), where Θ [𝑖 ] gathers the outputs of the RTS smoother at previous EM iterate 𝑖, listed in Equation 9. The application of [START_REF] Särkkä | Bayesian filtering and smoothing[END_REF]Theo.12.4] to our DESSERT model in Equation 4and the cancellation of constant terms, leads to the function

The proposed update in Section 4.3 amounts to maximizing Q (•, Θ [𝑖 ] ), for 𝑖 = 1, 2, . . ., using a coordinate descent algorithm, i.e.,

)

2 , Θ [𝑖 ] )

which leads to the six sub-problems provided in Section 4.3. This procedure is theoretically sound (see [START_REF] Chouzenoux | GraphEM: EM algorithm for blind Kalman filtering under graphical sparsity constraints[END_REF][START_REF] Särkkä | Bayesian filtering and smoothing[END_REF] for more details). In particular, it is guaranteed to yield a monotonic increase of the marginal log-likelihood function 𝜑 𝐾 and convergence to a stationary point of it.

C HYPER-PARAMETERS

ARIMA. We use the python library pmdarima. For the hyperparameters (𝑠𝑡𝑎𝑟𝑡_𝑝, 𝑠𝑡𝑎𝑟𝑡_𝑞, 𝑚𝑎𝑥_𝑝, 𝑚𝑎𝑥_𝑞, 𝑚, 𝑠𝑡𝑎𝑟𝑡_𝑃, 𝑑 and 𝐷), we set them to 0, 0, 5, 5, 12, 0, 𝑓 𝑎𝑙𝑠𝑒, 0 and 1 respectively. The non-seasonal version of ARIMA works best for our task. LSTM. We use a stacked LSTM with 2 layers, each with 50 units followed by a dense layer for final prediction. We use ReLU for activation in both layers. The model is trained on a batch size 16 for 100 epochs. We add an early stopping layer to avoid overfitting. CNN. We use a CNN with 1-D convolutional layer of filter size 64 and kernel size of 2. We pass it through a max-pooling 1D layer of pool size 2. We train the model on a batch size of 16 for 100 epochs.

To avoid overfitting, we use early stopping. N-Beats. We use the default implementation and run the model in the interpretable mode, with the 3 blocks per stack, 3 fullyconnected layers per block of width chosen from [START_REF] Rizwan | Hate-Speech and Offensive Language Detection in Roman Urdu[END_REF]512] (whichever works best). We set 𝑙𝑜𝑔_𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙, 𝑙𝑜𝑔_𝑣𝑎𝑙_𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙, 𝑤𝑒𝑖𝑔ℎ𝑡𝑑𝑒𝑐𝑎𝑦 to 10, 1, 0.01 respectively. We run the trainer for a maximum of 100 epochs on a batch size of 16.