Juan Vazquez-Rodriguez

Grégoire Lefebvre

Julien Cumin

James L Crowley

ACCOMMODATING MISSING MODALITIES IN TIME-CONTINUOUS MULTIMODAL EMOTION RECOGNITION AUTHOR VERSION

Keywords: Affective Computing, Multimodal Emotion Recognition, Machine Learning, Transformers

Decades of research indicate that emotion recognition is more effective when drawing information from multiple modalities. But what if some modalities are sometimes missing? To address this problem, we propose a novel Transformer-based architecture for recognizing valence and arousal in a timecontinuous manner even with missing input modalities. We use a coupling of cross-attention and self-attention mechanisms to emphasize relationships between modalities during time and enhance the learning process on weak salient inputs. Experimental results on the Ulm-TSST dataset show that our model exhibits an improvement of the concordance correlation coefficient evaluation of 37% when predicting arousal values and 30% when predicting valence values, compared to a latefusion baseline approach.

Introduction

Technologies for automatic emotion recognition have been shown valuable for interpersonal communications [START_REF] Zenonos | HealthyOffice: Mood recognition at work using smartphones and wearable sensors[END_REF], health and wellness concerns [START_REF] Zenonos | HealthyOffice: Mood recognition at work using smartphones and wearable sensors[END_REF] and stress management [START_REF] Nunez | Effect on Social Connectedness and Stress Levels by Using a Huggable Interface in Remote Communication[END_REF], for example. People express emotions in both verbal and nonverbal manners. Facial expressions, pitch intensity or cardiac rhythms are examples of non-verbal communication.

Using multiple modalities for emotion recognition is advantageous since modalities may be complementary, and should thus improve the performance of the model when used together [START_REF] Ouzar | Video-Based Multimodal Spontaneous Emotion Recognition Using Facial Expressions and Physiological Signals[END_REF]. However, in real-world scenarios, there might be cases where a modality might not be available. If for example, the modalities consist of video, audio, and physiological signals, the camera field of view might be obstructed, the microphone can be too far away, or the physiological sensor might be on a wearable device that is not currently worn. Therefore, we need a model capable of handling missing modalities.

In this work, we extend a multimodal Transformer [START_REF] Gabeur | Multi-modal Transformer for Video Retrieval[END_REF] as an encoder to obtain representations from the different modalities and a Transformer decoder [START_REF] Vaswani | Attention is All you Need[END_REF] to process those representations and make predictions. A Transformer-based approach will continue to work in the case of missing modalities, although the performance often decreases [START_REF] Ma | Are Multimodal Transformers Robust to Missing Modality?[END_REF]. We investigated a learning strategy to improve performance by eliminating the most important modalities during part of the training, so that the model is forced to learn from the less informative ones, that nevertheless may carry valuable features. This has two desirable effects. First, the model improves its performance, by training the model to draw information from all modalities rather than focusing on the most important ones. Second, the model becomes less sensitive to missing modalities, as it learns to handle the case where a modality is not present.

A critical aspect of multimodal emotion recognition is modeling the complementarity of information from different modalities. In other words, the model should be capable of weighing the different modalities according to their importance. We then present a novel approach of using the encoder-decoder attention (cross-attention) of the Transformer decoder to weigh the representations generated by the encoder, making this weighting scheme focus on choosing between modalities rather than paying attention to information from different time-steps. In addition, our Transformer decoder is auto-regressive, meaning that it takes into account past predicted values when doing the current inference, which is important when performing timecontinuous predictions.

The main contributions of this research are: 1. we extend a multimodal Transformer-based architecture to perform timecontinuous value-continuous multimodal emotion recognition, 2. we present a novel approach using cross-attention from the Transformer decoder to weigh the importance of different modalities, 3. and we develop a learning strategy to improve the performance of the model when a modality is missing.

2 Related Work

Time-Continous Multimodal Emotion Recognition

Several works address the problem of time-continuous multimodal emotion recognition. Traditionally, Long Short Term Memory -Recurrent Neural Networks (LSTM-RNN) have been employed to model the temporal relations of the inputs and to consider past predictions when predicting the current time-step [START_REF] Christ | The MuSe 2022 Multimodal Sentiment Analysis Challenge: Humor, Emotional Reactions, and Stress[END_REF]. Recently, employing Transformer-based approaches [START_REF] Huang | Multimodal Transformer Fusion for Continuous Emotion Recognition[END_REF][START_REF] Zhang | Continuous Emotion Recognition using Visual-audio-linguistic Information: A Technical Report for ABAW3[END_REF][START_REF] Chen | Transformer Encoder With Multi-Modal Multi-Head Attention for Continuous Affect Recognition[END_REF] has gained popularity in addressing this task. Some works rely on LSTM-RNNs to complement the attention mechanisms from the Transformer to model the temporal information better [START_REF] Huang | Multimodal Transformer Fusion for Continuous Emotion Recognition[END_REF], while other works use a pure attentionbased approach [START_REF] Zhang | Continuous Emotion Recognition using Visual-audio-linguistic Information: A Technical Report for ABAW3[END_REF][START_REF] Chen | Transformer Encoder With Multi-Modal Multi-Head Attention for Continuous Affect Recognition[END_REF].

To fuse information from different modalities, some authors use late-fusion combining the outputs of single modality models [START_REF] Liu | Improving Dimensional Emotion Recognition via Featurewise Fusion[END_REF], while others employ early-fusion by combining the input features before feeding them into the model [START_REF] Karas | Time-Continuous Audiovisual Fusion with Recurrence vs Attention for In-The-Wild Affect Recognition[END_REF]. Some approaches that use Transformer-based techniques have presented more elaborate solutions to aggregate multimodal information. Cross-modal attention [START_REF] Tsai | Multimodal Transformer for Unaligned Multimodal Language Sequences[END_REF] can be used to incorporate information from different modalities [START_REF] Huang | Multimodal Transformer Fusion for Continuous Emotion Recognition[END_REF][START_REF] Karas | Time-Continuous Audiovisual Fusion with Recurrence vs Attention for In-The-Wild Affect Recognition[END_REF]. Different from this, Zhang et al. [START_REF] Zhang | Continuous Emotion Recognition using Visual-audio-linguistic Information: A Technical Report for ABAW3[END_REF] group the query vectors from each modality to form a single query vector and do the same for the key and value vectors. Then, they employ the grouped vectors to perform a modified version of the scaled dot-product attention described in the original Transformer paper [START_REF] Vaswani | Attention is All you Need[END_REF]. Chen et al. [START_REF] Chen | Transformer Encoder With Multi-Modal Multi-Head Attention for Continuous Affect Recognition[END_REF] and He et al. [START_REF] He | Multimodal Temporal Attention in Sentiment Analysis[END_REF] model temporal information using a standard Transformer approach and they model intermodal information through a multimodal attention mechanism.

A disadvantage of these approaches is that, at some point, the features coming from the different modalities are concatenated. This requires that all the modalities need to be present, thus breaking the approach if a modality is missing. Some authors have worked on addressing this situation, and we review some of these works below.

Handling Missing Modalities

There are three main types of approaches to handle missing modalities [START_REF] Zhao | Missing Modality Imagination Network for Emotion Recognition with Uncertain Missing Modalities[END_REF]: 1. learning a joint representation from the different modalities, so only one modality could be used at test time, 2. generating the missing modalities from the available ones, and 3. hiding some modalities during training.

For the first type, an example is the work of Pham et al. [START_REF] Pham | Found in Translation: Learning Robust Joint Representations by Cyclic Translations between Modalities[END_REF], where a joint representation is learned by encoding the text into a representation (the joint representation) and generating the other modalities from this representation. At test time, only the text input is needed. For the second type, we have the work of Mittal et al. [START_REF] Mittal | M3ER: Multiplicative Multimodal Emotion Recognition using Facial, Textual, and Speech Cues[END_REF], where the model generates replacement features using a learned linear transformation that converts features from the available modalities into features of the missing one. For the third type, an example is the work of Neverova et al. [START_REF] Neverova | ModDrop: Adaptive Multi-Modal Gesture Recognition[END_REF], where a carefully designed network is designed so it can still work even with missing modalities. Then, at train time, some modalities are dropped randomly to make the model robust to missing modalities.

Although these approaches make the model robust to missing modalities, a disadvantage of the first type of approach is that it cannot take advantage of using all modalities if they are present at test time. For the second type of approach, a drawback is that there is no guarantee that the generated representation accurately resembles the missing one. And to implement the third type of approach, the architecture should be capable of working with missing modalities. On the contrary, if a Transformer-based approach is used, there is no need to generate the missing modality representations, or do modifications to the architecture so it can work with modalities absent. In this case, the attention mechanisms simply do not attend to the missing modalities, and it is capable of attending to all of them if they are present.

For the reasons stated in the previous paragraph, many works that use the third type of approach to handle missing modalities use a Transformer-based model. Some examples include the work of Goncalves and Busso [START_REF] Goncalves | AuxFormer: Robust Approach to Audiovisual Emotion Recognition[END_REF], and the work of Parthasarathy and Sundaram [START_REF] Parthasarathy | Training Strategies to Handle Missing Modalities for Audio-Visual Expression Recognition[END_REF], where they use a crossmodality Transformer to combine audio and visual modalities, improving the robustness of the model to missing modalities by eliminating a modality during training. A disadvantage of using a cross-modality Transformer is that expanding the approach to use more modalities is not straightforward. To overcome this problem, a Multimodal Transformer [START_REF] Gabeur | Multi-modal Transformer for Video Retrieval[END_REF] can be employed, like in the work of Ma et al. [START_REF] Ma | Are Multimodal Transformers Robust to Missing Modality?[END_REF], where robustness to missing modalities is increased using a multitasking approach.

The Transformer-based models are well suited to model long and short temporal relations of the inputs and to model the cross-modality dependencies. Nevertheless, in the reviewed Transformer-based approaches, the attention layers have to model the temporal and the intermodal dependencies at the same time. We argue that it can be advantageous to attend only to the cross-modal dependencies when aggregating the multimodal information. In addition, the reviewed approaches do not explicitly consider past predictions when making the current prediction, which we believe is beneficial.

Our approach is a Transformer-based approach that uses a Multimodal Transformer as encoder, making it suitable for any number of modalities. We also use the novel idea of using the cross-attention from a Transformer decoder [START_REF] Vaswani | Attention is All you Need[END_REF] to weigh the information from the different modalities. The decoder uses only the information of each modality at the current prediction time-step, relieving it from modeling the temporal information, which is done by the encoder. In addition, we explicitly use past predictions to make the current one by employing an auto-regressive approach. To handle missing modalities, we use the approach of hiding some modalities at train time, but different from the state of the art, we employ a technique to find and then hide the important modalities.

Approach

In this section, we provide a detailed explanation of our approach to perform multimodal time-continuous valuecontinuous emotion recognition. Our objective is to predict values of arousal and valence. We start this section by explaining our encoder that generates multimodal representations. Then we explain our decoder that predicts the values of arousal and valence from those representations. Finally, we describe the loss that we use to train our model.

Transformer Encoder

r 1 1 r 1 2 r 1 T ... f 1 1 f 1 2 f 1 T e 1 e 1 ... e 1 + + + p 1 p 2 ... p T + + + TCN 1 a 1 1 a 1 2 a 1 T x 1 1 x 1 2 x 1 T ... ... ... ... ... ... r M 1 r M 2 r M T ... Encoder Outputs f M 1 f M 2 f M T
e M e M e M ...

Modality Encodings

+ + + p 1 p 2 p T ... Positional Encodings + + + TCN M a M 1 a M 2 a M T x M 1 x M 2 x M T ...

Input Features

Figure 1: MultiModal Transformer Encoder (MMTE).

MultiModal Tranformer Encoder (MMTE)

We depict our MultiModal Transformer Encoder (MMTE) in Figure 1. Our MMTE is based on the work by Gabeur et al. [START_REF] Gabeur | Multi-modal Transformer for Video Retrieval[END_REF].

The inputs for our encoder are features extracted from raw data from the different modalities. We discuss the features we use in Section 6.

The first step in our MMTE architecture is to process each modality individually using a Temporal Convolutional Network (TCN) [START_REF] Shaojie Bai | An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling[END_REF] to model local temporal information, similarly to [START_REF] Chen | Transformer Encoder With Multi-Modal Multi-Head Attention for Continuous Affect Recognition[END_REF]. Our model learns a different TCN for each modality. We define x m t ∈ R dmodality as the feature corresponding to modality m at time-step t. If we denote [x m 1 , . . . , x m T ] as the sequence with length T of features corresponding to modality m, then during this step we have:

[a m 1 , . . . , a m T ] = TCN m ([x m 1 , . . . , x m T ]), (1)
where a m t ∈ R dmodel . For all modalities, the TCN output will have a common size d model .

The next step is to add positional encodings that allow the Transformer to take into account the actual order of the sequence [START_REF] Vaswani | Attention is All you Need[END_REF]. If the sequence of positional encodings is P = [p 1 , . . . , p T ], with p t ∈ R dmodel , then the output of this step is

[a m 1 + p 1 , . . . , a m T + p T ]. (2)
The elements of P are parameters that are learned during the training of the whole architecture.

The Transformer also needs to differentiate each modality to process cross-modality information. To do this, we follow the original multimodal Transformer from Gabeur et al., and add modality encodings. Similar to positional encodings, these modality encodings are learned during training. For each modality m, an encoding e m ∈ R dmodel is added to the input. The output of this step is then

[a m 1 + p 1 + e m , . . . , a m T + p T + e m ]. (3)
We then concatenate the sequences from all modalities to have a single sequence. If we define the input corresponding to Encoder Outputs

r 1 1 r 1 2 r 1 t r 1 T ... ... ... r M 1 r M 2 r M t r M T ... ... ... ŷ1 ŷ2 ŷt

Emotion Predictions

Emotion Regression Network (ERN) Fully-Connected (FC)

d 1 d 2 d t ... Output Features h ′′ 0 h ′′ 1 h ′′ t-1

Transformer Decoder

Layer (TDL)

Nx H ′′ t Feed-Forward Network (FFN)
Fully-Connected (FC)

H ′ t Multi-Head Cross-Attention (MHCA)
Multi-Head Attention (MHA)

Ht K V Q Multi-Head Self-Attention (MHSA)
Multi-Head Attention (MHA)

It K V Q i0 i1 it-1 p ′ 1 p ′ 2 p ′ T ... Positional Encodings + + + d 0 d 1 d t-1 ...

Input Features

Figure 2: Auto-regressive MultiModal Transformer Decoder (AMMTD). Decoder when predicting the emotion value at time t. N x means that there are N stacked TDL layers. modality m at time-step t as f m t = a m t + p t , +e m , and if we have M modalities, the concatenated input sequence is then

[f 1 1 , . . . , f 1 T , . . . , f M 1 , . . . , f M T ]. (4)
We process this sequence using a Transformer encoder. The output representations r m t of the Transformer are given by [r 1 1 , . . . , r 1 T , . . . , r M 1 , . . . , r

M T ] = Transformer Encoder([f 1 1 , . . . , f 1 T , . . . , f M 1 , . . . , f M T ]). (5)
Following [START_REF] Chen | Transformer Encoder With Multi-Modal Multi-Head Attention for Continuous Affect Recognition[END_REF], we employ a bidirectional attention mask in the Transformer encoder. When processing a specific time-step, this mask hides the inputs that are farther than mask_length positions in the future and in the past. This allows the model to concentrate on recent information, and not to worry about information too far in time that probably does not influence the current emotional state. Note that we are not hiding complete modalities, therefore this technique is not intended to make the model robust to missing modalities.

Auto-regressive MultiModal Transformer Decoder (AMMTD)

One of the contributions of this paper is to develop a decoder that predicts emotion from the multimodal representations given by the encoder. To do this, we design an Autoregressive MultiModal Transformer Decoder (AMMTD). This decoder has two important characteristics: first, it takes previous predictions into account to determine the current emotion; second, it aggregates the representations of the different modalities, giving more weight to the more important ones.

A Transformer Decoder Layer (TDL) [START_REF] Vaswani | Attention is All you Need[END_REF] is composed of a Multi-Head Self-Attention module (MHSA), followed by a Multi-Head Cross-Attention module (MHCA), and followed by a fully-connected Feed-Forward Network (FFN). Residual connections are used around each of these three components. The Multi-Head Attention (MHA) mechanism in MHSA and MHCA projects a query vector q from a given position to a key vector k from another position to determine the attention (i.e. the weight) given to a value v associated with the position of k. The final value is the weighted sum of the v vectors from the different positions. We denote the MHA mechanism as

MHA(Q, K, V ), (6)
where the three parameters Q, K, and V indicate the sequence used as query, key, and value, respectively. More details about MHA can be found in the original Transformer paper [START_REF] Vaswani | Attention is All you Need[END_REF].

Our
d i ∈ R dmodel . Then, the decoder input is [d 0 , d 1 , . . . , d t-1 ], (7)
where d 0 ∈ R dmodel is a randomly initialized vector.

As for our encoder, we learn positional encodings p ′ t ∈ R dmodel for our decoder and add them to the inputs before feeding them to the TDL stack. Thus, when performing the prediction at time-step t, the input sequence I t = [i 0 , i 1 , . . . , i t-1 ] with I t ∈ R t×dmodel becomes

I t = [d 0 + p ′ 0 , d 1 + p ′ 1 , . . . , d t-1 + p ′ t-1 ]. (8)
Inside the TDL, the features are first processed by the MHSA module. This module uses self-attention to integrate information from its own inputs. This means that the query, key, and value for the MHSA all come from the input sequence.

To preserve the auto-regressive property, we make sure that a given input at a certain time-step can only attend inputs from past time-steps. Using Expression 6, the sequence of features

H t = [h 0 , h 1 , . . . , h t-1
] with H t ∈ R t×dmodel at the output of the MHSA module is

H t = MHA(I t , I t , I t ). (9)
The sequence of features H t is then processed with the MHCA module, which is used to incorporate information from the input modalities. Specifically, the MHCA module attends to the outputs of the encoder. This means that the query comes from the output sequence of the MHSA, and the key and value come from the output of the encoder. If we are predicting the emotion value at time-step t, the MHCA attends only to the outputs of each modality corresponding to this time step. The output sequence of the MHCA, H ′ t ∈ R t×dmodel , using the output of the encoder from Equation 5and the output of the MHSA from Equation 9, is

H ′ t = MHA([h 0 , h 1 , . . . , h t-1 ], [r 1 t , . . . , r M t ], [r 1 t , . . . , r M t ]), (10)
Note that we force the model to only attend to the encoder outputs at time t instead of attending to all encoder outputs (or other outputs around t) because we want that the MHCA focuses only on finding the best weighting between the different modalities. We want to avoid the MHCA having to weigh which other time-steps in the different modalities might be important. Moreover, this restricts the information flow between modalities, which has been demonstrated to be beneficial [START_REF] Nagrani | Attention Bottlenecks for Multimodal Fusion[END_REF], because it forces the shared representation to condense the most significant information.

The final step in the TDL is processing each feature of the sequence H ′ t through a fully connected feed-forward network (FFN), applied independently to each position:

H ′′ t = FFN(H ′ t ). (11)
If the TDL stack has more than one layer, the sequence from Equation 11becomes the input of the next layer. Concretely, the new layer implements Equations 9, 10, and 11 using as input I t = H ′′ t . For the last TLD layer, the sequence in Equation 11is the newly generated sequence [d 1 , . . . , d t ] that will be used as input for the decoder to predict the emotion value for the next time-step, thus if

H ′′ t = [h ′′ 0 , h ′′ 1 , . . . , h ′′ t-1 ], then d i = h ′′ i-1 with i ∈ [1, t].
Once the complete output sequence D = [d 1 , . . . , d T ] has been generated, the final step is to process it with the Emotion Regression Network (ERN). As shown in Figure 2, our ERN is a Fully Connected (FC) layer that independently processes each element of the sequence D to predict the emotion values for each time-step, producing the predicted sequence [ŷ 1 , . . . , ŷT ].

Loss Function

As suggested in previous works that address the problem of recognizing emotion in a time-continuous manner [START_REF] Christ | The MuSe 2022 Multimodal Sentiment Analysis Challenge: Humor, Emotional Reactions, and Stress[END_REF][START_REF] Liu | Improving Dimensional Emotion Recognition via Featurewise Fusion[END_REF][START_REF] He | Multimodal Temporal Attention in Sentiment Analysis[END_REF], we use the concordance correlation coefficient (CCC) [START_REF] Lin | A concordance correlation coefficient to evaluate reproducibility[END_REF] as the loss to train our model. Specifically, the loss is

L = 1 -CCC CCC = 2ρσ ŷ σ y σ 2 ŷ + σ 2 y + (µ ŷ -µ y ) 2 , ( 12
)
where ρ is the Pearson correlation coefficient between the predicted values ŷ and the ground-truth values y. σ denotes the standard deviation and µ denotes the average of either the predicted or the ground-truth values.

Handling Missing Modalities

We now describe another contribution of our paper, which is our approach to deal with missing modalities. In our case, a missing modality means that the modality is completely absent, thus the input sequence defined in Expression 4 is built with the remaining modalities. By construction, our model will not break in the case a modality is missing. The attention mechanisms in our Transformer-based approach can accommodate missing modalities as explained below. In the case of the MMTE, if a modality is not present, the Tranformer encoder will simply attend to the remaining modalities. Similarly, in the AMMTD, the cross-modal attention will be able to attend to the remaining representations without the need to generate a replacement for the missing ones.

Even if our approach is capable to continue working in the case of missing modalities, its performance may be degraded.

To increase the robustness of the model to missing modalities, we perform an optimized training that we describe below.

First, we identify the most important modalities. To do this, we first train our model in a standard way, then test it without one modality at a time. We can then identify in which cases the performance is reduced more, meaning that the missing modalities in those cases should be important. Next, we retrain the model, without the important modalities a part of the time. Specifically, for each batch, we randomly select to eliminate the important modality i with probability ρ i eliminate , and to keep all modalities with probability ρ none = 1-n i=1 ρ i eliminate , where n is the number of important modalities.

Our reasoning behind this training strategy is that by hiding the important modalities, the model is forced to learn from the remaining ones, thus making the model more robust when those important modalities are missing. Moreover, we believe that this training strategy should lead to better results in general, even without missing modalities, as more information will be incorporated from all the modalities, rather than just relying on the important ones.

Experimental Setup

We test our model on the task of recognizing time-continuous values of arousal and valence. In this section, we describe the dataset, features, and parameters of our model for these experiments.

Dataset

To evaluate our model, we use the Ulm-Trier Social Stress Test dataset (Ulm-TSST), which was presented for the Muse 2021 Challenge [START_REF] Stappen | The MuSe 2021 Multimodal Sentiment Analysis Challenge: Sentiment, Emotion, Physiological-Emotion, and Stress[END_REF][START_REF] Stappen | MuSe 2021 Challenge: Multimodal Emotion, Sentiment, Physiological-Emotion, and Stress Detection[END_REF]. This is a multimodal dataset, where participants were recorded in a stressful situation emulating a job interview, following the TSST protocol [START_REF] Kirschbaum | The 'Trier Social Stress Test'-a tool for investigating psychobiological stress responses in a laboratory setting[END_REF]. Each participant gave a 5 minutes speech supervised by two interviewers, who did not intervene during that time. Besides audio and video, the following physiological signals are collected: Electrocardiogram (ECG), Respiration (RESP), and heart rate (BPM). A transcription of the speech is also provided.

The data set was annotated by 3 raters giving continuous values of arousal and valence in the range [-1, 1]. The annotations are done in a time-continuous fashion every 0.5s. To aggregate the valence annotations from the 3 raters, Rater Aligned Annotation Weighting (RAAW) [START_REF] Stappen | MuSe-Toolbox: The Multimodal Sentiment Analysis Continuous Annotation Fusion and Discrete Class Transformation Toolbox[END_REF] is used. For arousal, the annotations corresponding to the lowest inter-rater agreement are discarded, and replaced by the subject's Electrodermal Activity (EDA) signal recorded during the session. The authors of the dataset do this because EDA has been demonstrated to be a good indicator of arousal [START_REF] Baird | A Physiologically-Adapted Gold Standard for Arousal during Stress[END_REF]. Like it was done for valence, RAAW is used to aggregate the annotations from the two remaining raters and the EDA signal.

The dataset includes 69 samples, each being a 5-minute presentation given by a subject. In the original dataset, 41 samples are used as train set, 14 as validation set, and 14 as test set. Since annotations are not provided for the test set, we randomly pick 4 samples from the validation set and 6 from the train set to form a new test set with 10 samples. In summary, we have 35 samples in the train set, 10 in the validation set, and 10 in the test set.

Input Features

We use audio, video, and physiological signals as input modalities, with features directly provided in Ulm-TSST. All features are aligned with annotations; that is, they are sampled at a rate of 2 Hz. For audio, we use extended Geneva Minimalistic Acoustic Parameter Set (eGeMAPS) features. For video, we use Facial Action Units (FAU) intensity. For physiological signals, the features are the concatenation of the values of ECG, RESP, and BPM. We selected these features by running some experiments in the baseline model provided by the authors of the Ulm-TSST dataset and selecting the features that lead to good performance.

Model Hyperparameters and Training

We optimize the hyperparameters of our model using the Ray Tune Framework [START_REF] Liaw | Tune: A Research Platform for Distributed Model Selection and Training[END_REF] During training, we segment each 5-minute sample into smaller samples, as suggested by Christ et al. [START_REF] Christ | The MuSe 2022 Multimodal Sentiment Analysis Challenge: Humor, Emotional Reactions, and Stress[END_REF]. Searching across different options, we found that segments of 125 seconds (250 time-steps) with a hop size of 25 seconds (50 time-steps) work well in our experimental protocol.

We train our model with a batch size of 64 for a maximum of 100 epochs. We start with a learning rate of 0.0001, and halve it if the metric does not improve for 5 epochs on the validation set, and we early-stop the training if there is not improvement for 15 epochs. We use Adam optimizer with B 1 = 0.9 and B 2 = 0.999. We use a dropout rate of 0.2 throughout all the model.

Experiments

This section presents and discusses the experimental results. For each experiment, we obtain 30 results by training the model with 30 different initialization seeds, reporting the average of those results. We use the Holm-Bonferroni method to assert statistically significant difference in the comparisons in Section 6.1. For other results, we do a t-test using a threshold of p-value < 0.05 to assert statistical significance, using a one-sided t-test to state that a result is significantly better than another, and a two-sided t-test to check for statistical difference. We use as metric the Root-Mean-Square Error (RMSE) and the Concordance Correlation Coefficient (CCC) [START_REF] Lin | A concordance correlation coefficient to evaluate reproducibility[END_REF] between ground truths and predicted values.

Performance with all Modalities Present

We present in Table 1 the performance of our model, along with baseline approaches, when all modalities are present. Approach N o 1 corresponds to the baseline model developed for the Muse 2022 Challenge [START_REF] Christ | The MuSe 2022 Multimodal Sentiment Analysis Challenge: Humor, Emotional Reactions, and Stress[END_REF], where the Ulm-TSST dataset was presented. We use the provided code 1 and the original hyperparameters to evaluate this model with the same features we employ, using our partition of the Ulm-TSST dataset. This approach is based on Long Short-Term Memory (LSTM) networks and uses late-fusion to aggregate the different modalities. Approach N o 2 corresponds to a model where instead of using our AMMTD to process the representations from the MMTE, it uses directly the ERN. Recall that the ERN is a FC network that performs regression of the emotion values. Similarly, approach N o 3 uses an LSTM to process the outputs of the MMTE. The LSTM has 4 layers, with a hidden dimension of 32. We used a grid search to tune this LSTM. For both approaches N o 2 and 3, the input is the concatenation of all modalities per time-step. The last two entries in Table 1 correspond to the approach presented in this paper. Approach N o 4 is our model trained in a standard way, i.e. with all modalities present during training. Approach N o 5 is our model trained with our optimized training strategy as presented in Sections 4 and 6.2, i.e. hiding some modalities during training.

In Figure 3, we present an example of the predictions of our model when using the optimized training strategy. For the same sample, we present the results when predicting arousal, Fig. 3(a), and valence, Fig. 3(b). As observed, the real valence values tend to be flat and have less variability than the arousal values, which we noted is a common occurrence in the dataset.

Comparison to the LSTM-based baseline model

If we compare our approach with standard training (approach N o 4 in Table 1) with the LSTM baseline (approach N o 1), we can see that in all metrics except for valence RMSE, our model performs better than the LSTM baseline, demonstrating that in general, our Tranformer-based approach is well suited for this task.

Comparison with other predictors

To test our idea of using cross-attention to weigh the input modalities and an auto-regressive approach to incorporate past predictions, we compare our approach with standard training (approach N o 4), with approaches N o 2 and N o 3 in Table 1, that use the ERN and an LSTM respectively instead of our AMMTD. The results show that our AMMTD module increases the performance in most of the metrics, demonstrating the effectiveness of our ideas of using cross-attention and auto-regression. The performance of our approach is statistically significantly better for all the metrics except for valence RSME, where although our approach outperforms both baselines, the improvement is not statistically significant.

In general, the baseline models perform well in terms of the RMSE metric when predicting valence, but our model performs better in terms of the CCC metric. We hypothesize that this behavior is produced because the simpler architecture of the baselines is good enough to predict flat sequences of valence values that are close enough to the flat ground-truth. On the other hand, those approaches fail to predict the small changes in the valence values, penalizing the CCC score.

Comparison with our optimized training strategy

The results presented in entries N o 4 and N o 5 in Table 1 show that our optimized training approach, designed to improve the handling of missing modalities, also has the desirable effect of increasing the performance of the model when all modalities are present. For example, arousal RMSE decreases from 0.2948 to 0.2869 and valence CCC increases from 0.1502 to 0.1656. As we expected, the model seems to learn to use more information from the weak modalities, improving the overall performance.

Accommodating Missing Modalities

We present in Table 2 the results of experiments we conducted when a modality is missing. 2, we see that there is no significant performance degradation when the audio or physiological modalities are missing. For example, when audio is missing, RMSE goes from 0.2948 to 0.2926, and CCC goes from 0.3578 to 0.3589. These differences are not statistically significant, as indicated by the checkmark ( ). We also see that performance drops significantly when the video modality is missing, with RMSE increasing from 0.2948 to 0.3252 and CCC decreasing from 0.3578 to 0.2713. These results confirm that our model continues to accurately predict arousal when a modality is missing, although performance is reduced in some cases.

For valence, we see that there is no significant performance degradation when physiological signals are missing, with RMSE going from 0.1796 to 0.1808 and CCC going from 0.1502 to 0.1486. On the contrary, the model performance drops significantly when the audio or video modalities are missing. For example, RMSE increases from 0.1796 to 0.2533 when the audio modality is missing and increases to 0.2170 when the video modality is missing. Much like for arousal, these results show that our model continues to estimate valence when a modality is missing, albeit with a drop in performance.

With these results, we can identify the most important modalities for our model, by identifying the modalities that when missing, induce a significant drop in performance. When predicting arousal, the most important modality is video, and for valence the most important modalities are audio and video.

Models tend to rely heavily on the important modalities, even though other modalities may carry useful features for recog-nizing emotions. To improve this, we apply our optimized training strategy of hiding important modalities during parts of the training, forcing the model to rely on other modalities. Specifically, we use the strategy described in Section 4, eliminating the video modality with probability ρ video eliminate = 0.25, and maintaining all modalities with probability ρ none = 0.75 when training for arousal prediction. For valence, we use ρ audio eliminate = 0.333, ρ video eliminate = 0.333 and ρ none = 0.334. These probabilities were found empirically by testing several configurations and keeping the best ones for the validation set.

We see in Table 2 that our optimized training strategy improves all results when any modality is missing. For example, when the physiological signals are missing, CCC improves from 0.3539 to 0.3571 when predicting arousal and from 0.1486 to 0.1637 when predicting valence. Notably, the improvement is statistically significant, as indicated by the double dagger ( ‡), in all cases when the important modalities are missing, except for RMSE when predicting arousal with the video modality missing. In addition, the performance of the model improves even when all modalities are present. For instance, RMSE decreases from 0.2948 to 2869 for arousal and from 0.1796 to 0.1739 for valence. This shows that our optimized training strategy works well, making our model less reliant on the important modalities and using more information from the other ones. This strategy improves the performance of our approach not only when a modality is missing, but also when all modalities are present.

In this work, we presented a novel Transformer-based architecture with the coupling of self-and cross-attention mechanisms for emotion recognition from multimodal signals. We experimentally showed, using the Ulm-TSST dataset, that our proposal can competitively recognize emotional valence and arousal. In addition, we demonstrated that our optimized learning strategy improves performance. Consequently, our architecture is capable of reaching high performances for emotion recognition even with missing modalities.

Future works include investigating new ways to pre-train multimodal models with contrastive learning strategies. Metric learning between different signals, sharing the same semantic meaning, could positively influence the whole system to build strong correlations between input sequences produced at different moments in time. Moreover, learning similarities between signals even when some modalities are missing may help to better understand how pretraining on Transformerbased models behave for multimodal emotion recognition.

Ethical Impact Statement

We consider two main issues: privacy and harmful applications. First, regarding privacy, knowing the emotional state of a person leads to privacy concerns since it is evident that the emotional state is a private matter. Therefore, privacy should be guaranteed. There might be cases that people involved might agree to share this private information, as in the case of people participating in the dataset that we use. That is why we adhere to the dataset usage agreement. In the general case, to avoid privacy concerns, we think the emotional record of a person should be treated at the same level of privacy that medical records are treated.

The second issue has to do with potentially harmful applications. Although in this work we do not develop an application that uses the emotional state of a person as input, we are aware that bad actors may use emotion recognition techniques in unethical ways. For example, knowing the emotional state of a person can be used to manipulate their behavior. Direct control of this is out of our hands, and therefore, we think the affective computing community should pressure governmental entities for laws and ways to control these types of applications.

  based on the validation set. Our model is parameterized as follows: we use a TCN with 6 layers and a kernel of size 9, with ReLU activation function. We have a model dimension of d model = 64. In the Transformer encoder and the TDL, we use the GELU activation function. The size of the FFN inside the Transformers is d model × 4 = 256. We use a Transformer encoder with 2 attention heads and 2 layers. Our decoder is composed of a single TDL with one head. The FC layer in the ERN has a single hidden layer of d model /2 = 32, with ReLU activation function. The bidirectional attention mask for the Transformer encoder has a mask_length of 50 seconds (100 time-steps).

Figure 3 :

 3 Figure 3: Example of an output of our model with optimized training compared with the ground-truth, when predicting arousal (a) and valence (b) for the same sample.

  AMMTD architecture is depicted in Figure2. It is composed of a stack of TDL followed by an Emotion Regression Network (ERN). The MHSA module in the TDL uses selfattention to attend to previous predictions. To do this, we use auto-regression, meaning that the previously generated outputs are used as inputs to the decoder. Note that we cannot use the output of the ERN, i.

e. the predicted emotion values ŷ, since we are predicting continuous outputs. Instead, we use the features generated by the top TDL. When predicting the emotion value at time-step t, the TDL stack should have generated a sequence [d 1 , . . . , d t-1 ] with

Table 1 :

 1 Comparison of our results with the baselines. The best result is in bold, the second best is underlined. The standard deviation is in parentheses. (•), ( †), ( ‡) indicate that our results are statistically significantly different than the late-fusion, MMTE+FC, and MMTE+LSTM baselines, respectively. (↓) and (↑) indicate that a lower and a higher score is desirable respectively.

	Arousal	Valence

Table 2 :

 2 Summary of results when modalities are missing, for standard training and our optimized training strategy. We use bold font to indicate that the result is better than its counterpart trained in a different fashion, and if it is statistically significantly better we indicate this with the symbol ( ‡). We use a checkmark ( ) to indicate that a result obtained with a modality missing is not statistically significantly different than the result obtained with all the modalities.

			All Modalities	Missing Audio	Missing Video	Missing Physio
		Training Mode RMSE↓ CCC↑	RMSE↓	CCC↑	RMSE↓	CCC↑	RMSE↓	CCC↑
	AROUSAL	Standard Optimized	0.2948 0.2869 ‡ 0.3703 0.3578	0.2926 0.2850 ‡ 0.3644 0.3589	0.3252 0.3249	0.2713 0.2984 ‡	0.2920 0.2878	0.3539 0.3571
	VALENCE	Standard Optimized	0.1796 0.1739 ‡ 0.1656 ‡ 0.2052 ‡ 0.1502 0.2533	0.0738 0.1170 ‡ 0.1809 ‡ 0.1676 ‡ 0.1746 ‡ 0.1637 ‡ 0.2170 0.1564 0.1808 0.1486

First, we analyze the case where we are predicting arousal with the model trained in a standard way. In Table

Acknowledgements: This work has been partially supported by the MIAI Multidisciplinary AI Institute at the Univ. Grenoble Alpes: (MIAI@Grenoble Alpes -ANR-19-P3IA-0003).


Éric Fusy
email: eric.fusy@univ-eiffel.fr

Gregory Kucherov
email: gregory.kucherov@univ-eiffel.fr

Count-min sketch with variable number of hash functions: an experimental study

Conservative Count-Min, a stronger version of the popular Count-Min sketch [Cormode, Muthukrishnan 2005], is an onlinemaintained hashing-based sketch summarizing element frequency information of a stream. Although several works attempted to analyze the error of conservative Count-Min, its behavior remains poorly understood. In [Fusy, Kucherov 2022], we demonstrated that under the uniform distribution of input elements, the error of conservative Count-Min follows two distinct regimes depending on its load factor. In this work, we present a series of results providing new insights into the behavior of conservative Count-Min. Our contribution is twofold. On one hand, we provide a detailed experimental analysis of Count-Min sketch in different regimes and under several representative probability distributions of input elements. On the other hand, we demonstrate improvements that can be made by assigning a variable number of hash functions to different elements. This includes, in particular, reduced space of the data structure while still supporting a small error.

Introduction

In most general terms, Count-Min sketch is a data structure for representing an associative array of numbers indexed by elements (keys) drawn from a large universe, where the array is provided through a stream of (key,value) updates so that the current value associated to a key is the sum of all previous updates of this key. Perhaps the most common setting for applying Count-Min, that we focus on in this paper, is the counting setting where all update values are +1. In this case, the value of a key is its count telling how many times this key has appeared in the stream. In other words, Count-Min can be seen as representing a multiset, that is a mapping of a subset of keys to non-negative integers. With this latter interpretation in mind, each update will be called insertion. The main supported query of Count-Min is retrieving the count of a given key, and the returned estimate may not be exact, but can only overestimate the true count.

The counting version of Count-Min is applied to different practical problems related to data stream mining and data summarization. One example is tracking frequent items (heavy hitters) in streams [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF][START_REF] Charikar | Finding frequent items in data streams[END_REF][START_REF] Cormode | Finding frequent items in data streams[END_REF]. It occurs in network traffic monitoring [START_REF] Estan | New directions in traffic measurement and accounting[END_REF], optimization of cache usage [START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF]. It also occurs in non-streaming big data applications, e.g. in bioinformatics [START_REF] Mohamadi | ntCard: a streaming algorithm for cardinality estimation in genomics data[END_REF][START_REF] Behera | KmerEstimate: A streaming algorithm for estimating k-mer counts with optimal space usage[END_REF][START_REF] Shibuya | Set-Min sketch: a probabilistic map for power-law distributions with application to k-mer annotation[END_REF].

Count-Min relies on hash functions but, unlike classic hash tables, does not store elements but only count information (hence the term sketch). It was proposed in [START_REF] Cormode | An improved data stream summary: the countmin sketch and its applications[END_REF], however a very similar data structure was proposed earlier in [START_REF] Cohen | Spectral Bloom filters[END_REF] under the name Spectral Bloom filter. The latter, in turn, is closely related to Counting Bloom filters [START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF]. In this work, we adopt the definition of [START_REF] Cohen | Spectral Bloom filters[END_REF] but still call it Count-Min to be consistent with the name commonly adopted in the literature. A survey on Count-Min can be found e.g. in [START_REF] Cormode | Count-Min sketch[END_REF].

In this paper, we study a stronger version of Count-Min called conservative. This modification of Count-Min was introduced in [START_REF] Estan | New directions in traffic measurement and accounting[END_REF] under the name conservative update, see [START_REF] Cormode | Count-Min sketch[END_REF]. It was also discussed in [START_REF] Cohen | Spectral Bloom filters[END_REF] under the name minimal increase. Conservative Count-Min provides strictly tighter count estimates using the same memory and thus strictly outperforms the original version. The price to pay is the impossibility to deal with deletions (negative updates), whereas the original Count-Min can handle deletions as well, provided that the cumulative counts remain non-negative (condition known as strict turnstile model [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF]).

Analysis of error of conservative Count-Min is a difficult problem having direct consequences on practical applications. Below in Section 2.2 we survey known related results in more details. In our previous work [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF], we approached this problem through the relationship with random hypergraphs. We proved, in particular, that if the elements represented in the data structure are uniformly distributed in the input, the error follows two different regimes depending on the peelability property of the underlying hash hypergraph. While properties of random hypergraphs have been known to be crucially related to some data structures (see Section 2.3), this had not been known for Count-Min.

Starting out from these results, in this paper we extend and strengthen this analysis in several ways, providing experimental demonstrations in support of our claims. Our first goal is to provide a fine analysis of the "anatomy" of conservative Count-Min, describing its behavior in different regimes. Our main novel contribution is the demonstration that assigning different number of hash functions to different elements can significantly improve the error, and, as a consequence, lead to memory saving. Another major extension concerns the probability distribution of input elements: here we study non-uniform distributions as well, in particular step distribution and Zipf's distribution, and analyze the behavior of Count-Min for these distributions. This analysis is important not only because non-uniform distributions commonly occur in practice, but also because this provides important insights for the heavy hitters problem [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF][START_REF] Charikar | Finding frequent items in data streams[END_REF][START_REF] Cormode | Finding frequent items in data streams[END_REF]). In particular, we consider the "small memory regime" (supercritical, in our terminology) when the number of distinct represented elements is considerably larger than the size of the data structure, and analyse conditions under which most frequent elements are evaluated with negligible error. This has direct applications to the frequent elements problem.

2 Background and related work

Conservative Count-Min: definitions

A Count-Min sketch is a counter array A of size n together with a set of hash functions mapping elements (keys) of a given universe U to [1..n]. In this work, each element e ∈ U can in general be assigned a different number k e of hash functions. Hash functions are assumed fully random, therefore we assume w.l.o.g. that an element e is assigned hash functions h 1 , . . . , h ke .

At initialization, counters A[i] are set to 0. When processing an insertion of an input element e, basic Count-Min increments by In both versions, the estimate of the number of occurrences of a queried element e is computed by c(e) = min 1≤i≤ke {A[h i (e)]}. It is easily seen that for any input sequence of elements, the estimate computed by original Count-Min is greater than or equal to the one computed by the conservative version.

1 each counter A[h i (e)], 1 ≤ i ≤ k e .
In this work, we study the conservative version of Count-Min. Let H denote a selection of hash functions H = {h 1 , h 2 , . . .}. Consider an input sequence I of N insertions and let E be the set of distinct elements in I. The relative error of an element e is defined by err (e) = (c(e) -occ(e))/occ(e), where occ(e) is the number of occurrences of e in the input. The combined error is an average error over all elements in I weighted by the number of occurrences, i.e. We assume that I is an i.i.d. random sequence drawn from a probability distribution on a set of elements E ⊆ U . A key parameter is the size of E relative to the size n of A. By analogy to hash tables, λ = |E|/n is called the load factor, or simply the load.

Analysis of conservative Count-Min: prior works

Motivated by applications to traffic monitoring, [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] was probably the first work devoted to the analysis of conservative Count-Min in the counting setting. Their model assumed that all n k counter combinations are equally likely, where k hash functions are applied to each element. This implies the regime when |E| n. The focus of [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] was on the analysis of the growth rate of counters, i.e. the average number of counter increments per insertion, using a technique based on Markov chains and differential equations. Another approach proposed in [START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF] simulates a conservative Count-Min sketch by a hierarchy of ordinary Bloom filters. Obtained error bounds are expressed via a recursive relation based on false positive rates of corresponding Bloom filters.

Recent works [START_REF] Ben Mazziane | Analyzing count min sketch with conservative updates[END_REF][START_REF] Ben Mazziane | A Formal Analysis of the Count-Min Sketch with Conservative Updates[END_REF] propose an analytical approach for computing error bounds depending on element probabilities assumed independent but not necessarily uniform, in particular leading to improved precision bounds for detecting heavy hitters. However the efficiency of this technique is more limited when all element probabilities are small. In particular, if the input distribution is uniform, their approach does not bring out any improvement over the general bounds known for original Count-Min.

In our recent work [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF], we proposed an analysis of conservative Count-Min based on its relationship with random hypergraphs. We summarize the main results of this work below in Section 2.4.

Hash hypergraph

Many hashing-based data structures are naturally associated with hash hypergraphs so that hypergraph properties are directly related to the proper functioning of the data structure. This is the case with Cuckoo hashing [START_REF] Pagh | Cuckoo hashing[END_REF] and Cuckoo filters [START_REF] Fan | Cuckoo filter: Practically better than Bloom[END_REF], Minimal Perfect Hash Functions and Static Functions [START_REF] Majewski | A family of perfect hashing methods[END_REF], Invertible Bloom Lookup Tables [START_REF] Goodrich | Invertible Bloom lookup tables[END_REF], and some others. [START_REF] Walzer | Random hypergraphs for hashing-based data structures[END_REF] provides an extended study of relationships between hash hypergraphs and some of those data structures.

A Count-Min sketch is associated with a hash hypergraph H = (V, E) where V = {1..n} and E = {{h 1 (e), ...h ke (e)}} over all distinct input elements e. We use notation H n,m for hypergraphs with n vertices and m edges, and H k n,m for k-uniform such hypergraphs, where all edges have cardinality k. In the latter case, since our hash functions are assumed fully random, a hash hypergraph is a k-uniform Erdős-Rényi random hypergraph.

As inserted elements are assumed to be drawn from a random distribution, it is convenient to look at the functioning of a Count-Min sketch as a stochastic process on the associated hash hypergraph [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF]. Each vertex holds a counter initially set to zero, and therefore each edge is associated with a set of counters held by corresponding vertices. Inserting an element consists in incrementing the minimal counters of the corresponding edge, and retrieving the estimate of an element returns the minimum value among the counters of the corresponding edge. From now on in our presentation, we will interchangeably speak of distinct elements and edges of the associated hash hypergraph, as well as of counters and vertices. Thus, we will call the vertex value the value of the corresponding counter, and the edge value the estimate of the corresponding element. Also, we will speak about the load of a hypergraph understood as the density |E|/|V |.

Hypergraph peelability and phase transition of error

A hypergraph H = (V, E) is called peelable if iterating the following step starting from H results in the empty graph: if the graph has a vertex of degree 1 or 0, delete this vertex together with the incident edge (if any). As many other properties of random hypergraphs, peelability undergoes a phase transition. Consider the Erdős-Rényi k-uniform hypergraph model where graphs are drawn from H k n,m uniformly at random. It is shown in [START_REF] Molloy | Cores in random hypergraphs and Boolean formulas[END_REF] that a phase transition occurs at a (computable) peelability threshold λ k : a random graph from H k n,λn is with high probability (w.h.p.) peelable if λ < λ k , and w.h.p. non-peelable if λ > λ k . The first values are λ 2 = 0.5, λ 3 ≈ 0.818, λ 4 ≈ 0.772, etc., λ 3 being the largest. Note that the case k = 2 makes an exception to peelability: for λ < λ 2 , a negligible fraction of vertices remain after peeling.

Peelability is known to be directly relevant to certain constructions of Minimal Perfect Hash Functions [START_REF] Majewski | A family of perfect hashing methods[END_REF] as well as to the proper functioning of Invertible Bloom filters [START_REF] Goodrich | Invertible Bloom lookup tables[END_REF]. In [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF], we proved that it is relevant to Count-Min as well.

Theorem 1 ([21]

). Consider a conservative Count-Min where each element is hashed using k random hash functions. Assume that the input I of length N is drawn from a uniform distribution on a set E ⊆ U of elements and let λ = |E|/n, where n is the number of counters. If λ < λ k , then for a randomly chosen element e, the relative error err (e) is o(1) w.h.p. when both n and N/n grow.

In the complementary regime λ > λ k , we showed in [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF], under some additional assumptions, that err is Θ(1). Thus, the peelability threshold for random hash hypergraphs corresponds to phase transition in the error produced by conservative Count-Min for uniform distribution of input. We call regimes λ < λ k and λ > λ k subcritical and supercritical, respectively.

Variable number of hash functions: mixed hypergraphs

The best peelability threshold λ 3 ≈ 0.818 can be improved in at least two different ways. One way is to use a carefully defined class of hash functions which replace uniform sampling of k-edges by a specific non-uniform sampling. Thus, [START_REF] Dietzfelbinger | Dense peelable random uniform hypergraphs[END_REF] showed that the peelability threshold can be increased to ≈ 0.918 for k = 3 and up to ≈ 0.999 for larger k's if a special class of hypergraphs is used.

Another somewhat surprising idea, that we apply in this paper, is to apply a different number of hash functions to differents elements, that is to consider nonuniform hypergraphs. Following [START_REF] Dietzfelbinger | Tight thresholds for cuckoo hashing via XORSAT[END_REF], [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF] showed that non-uniform hypergraphs may have a larger peelability threshold than uniform ones. More precisely, [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF] showed that mixed hypergraphs with two types of edges of different cardinalities, each constituting a constant fraction of all edges, may have a larger peelability threshold: for example, hypergraphs with a fraction of ≈ 0.887 of edges of cardinality 3 and the remaining edges of cardinality 21 have the peelability threshold ≈ 0.920, larger than the best threshold 0.818 achieved by uniform hypergraphs. We adopt the notation of [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF] for mixed hypergraphs: by writing k = (k 1 , k 2 ) we express that the hypergraph contains edges of cardinality k 1 and k 2 , and k = (k 1 , k 2 ; α) specifies in addition that the fraction of k 1 -edges is α.

The idea of using different number of hash functions for different elements has also appeared in data structures design. [START_REF] Bruck | Weighted Bloom filter[END_REF] proposed weighted Bloom filters which apply a different number of hash functions depending on the frequency with which elements are queried and on probabilities for elements to belong to the set. It is shown that this leads to a reduced false positive probability, where the latter is defined to be weighted by query frequencies. This idea was further refined in [START_REF] Wang | Improved weighted Bloom filter and space lower bound analysis of algorithms for approximated membership querying[END_REF], and then further in [START_REF] Bercea | Daisy Bloom filters[END_REF], under the name Daisy Bloom filter.

Results

Uniform distribution

We start with the case where input elements are uniformly distributed, i.e. edges of the associated hash hypergraph have equal probabilities to be processed for updates.

Subcritical regime. Theorem 1 in conjunction with the results of Section 2.5 leads to the assumption that using a different number of hash functions for different elements one could "extend" the regime of o(1) error of Count-Min sketch, which can be made into a rigorous statement (for simplicity we only give it with two different edge cardinalities).

Theorem 2. Consider a conservative Count-Min with n counters. Assume that the input of length N is drawn from a uniform distribution on E ⊆ U and let λ < λ k . Assume further that elements of E are hashed according to a mixed hypergraph model k = (k 1 , k 2 ; α). Let c k be the peelability ratio associated to k. Then, when λ < c k , the relative error err (e) of a randomly chosen key e is o(1) w.h.p., as both n and N/n grow.

The proof can be found in the full version [START_REF] Fusy | Count-min sketch with variable number of hash functions: an experimental study[END_REF]. Figure 1 shows the average relative error as a function of the load factor for three types of hypergraphs: 2-uniform, 3-uniform and mixed hypergraph where a 0.885 fraction of edges are of cardinality 3 and the remaining ones are of cardinality 14. 2-uniform and 3-uniform hypergraphs illustrate phase transitions at load factors approaching respectively 0.5 and ≈ 0.818, peelability thresholds for 2-uniform and 3-uniform hypergraphs respectively. It is clearly seen that the phase transition for the mixed hypergraphs occurs at a larger value approaching ≈ 0.898 which is the peelability threshold for this class of hypergraphs [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF].

While this result follows by combining results of [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF] and [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF], it has not been observed earlier and has an important practical consequence: using a variable number of hash functions in Count-Min sketch allows one to increase the load factor while keeping negligibly small error. In particular, for the same input, this leads to space saving compared to the uniform case.

Note that parameters k = (3, 14; 0.885) are borrowed from [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF] in order to make sure that the phase transition corresponds to the peelability threshold obtained in [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF]. In practice, "simpler" parameters can be chosen, for example we found that k = (2, 5; 0.5) produces essentially the same curve as k = (3, 14; 0.885) (data not shown). Supercritical regime. When the load factor becomes large (supercritical regime), the situation changes drastically. When the load factor just surpasses the threshold, some edges are still evaluated with small or zero error, whereas for the other edges, the error becomes large. This "intermediate regime" has been illustrated in [START_REF] Fusy | Phase transition in count approximation by Count-Min sketch with conservative updates[END_REF]. When the load factor goes even larger, the multi-level pattern of edge values disappears and all edge values become concentrated around the same value. We call this phenomenon saturation. For example, for k = 3 saturation Fig. 1: err for small λ = m/n, for uniform distribution and different types of hypergraphs: 2-uniform, 3-uniform and (3,14)-mixed with a fraction of 0.885 of 3-edges (parameters borrowed from [START_REF] Rink | Mixed hypergraphs for linear-time construction of denser hashing-based data structures[END_REF]). Data obtained for n = 1000. The input size in each experiment is 5, 000 times the number of edges. Each average is taken over 10 random hypergraphs. occurs at around λ = 6 (data not shown). Under this regime, the hash hypergraph is dense enough so that its specific topology is likely to be irrelevant and the largest counter level "percolates" into all vertex counters. In other words, all counters grow at the same rate, without any of them "lagging behind" because of particular graph structural patterns (such as edges containing leaf vertices).

Step distribution

In this section, we focus on the simplest non-uniform distribution -step distribution -in order to examine the behavior of Count-Min sketch in presence of elements with different frequencies. Our model is as follows. We assume that input elements are classified into two groups that we call hot and cold, where a hot element has a larger appearance probability than a cold one. Note that we assume that we have a prior knowledge on whether a given element belongs to hot or cold ones. This setting is similar to the one studied for Bloom filters augmented with prior membership and query probabilities [START_REF] Bercea | Daisy Bloom filters[END_REF]. Note that our definition of err assumes that the query probability of an element and its appearance probability in the input are equal.

We assume that the load factors of hot and cold elements are λ h and λ c respectively. That is, there are λ h n hot and λ c n cold edges in the hash hypergraph. G > 1, called gap factor, denotes the ratio between probabilities of a hot and a cold element respectively. Let p h (resp. p c ) denote the probability for an input element to be hot (resp. cold). Then p h /p c = Gλ h /λ c , and since p h + p c = 1, we have

p h = Gλ h λ c + Gλ h , p c = λ c λ c + Gλ h .
For example, if there are 10 times more distinct cold elements than hot ones (λ h /λ c = 0.1) but each hot element is 10 times more frequent than a cold one (G = 10), than we have about the same fraction of hot and cold elements in the input (p h = p c = 0.5).

In the rest of this section, we will be interested in the combined error of hot elements alone, denoted errhot. If E h ⊆ E is the subset of hot elements, and N h is the total number of occurrences of hot elements in the input, then errhot is defined by

errhot = 1 N h e∈E h occ(e) • err (e) = 1 N h e∈E h (c(e) -occ(e)).
"Interaction" of hot and cold elements. A partition of elements into hot and cold induces the partition of the underlying hash hypergraph into two subgraphs that we call hot and cold subgraphs respectively. Since hot elements have larger counts, one might speculate that counters associated with hot edges are larger than counts of cold elements and therefore are not incremented by those. Then, errhot is entirely defined by the hot subgraph, considered under the uniform distribution of elements. In particular, errhot as a function of λ h should behave the same way as err for the uniform distribution (see Section 3.1). This conjecture, however, is not true in general. One reason is that there is a positive probability that all nodes of a cold edge are incident to hot edges as well. As a consequence, "hot counters" (i.e. those incident to hot edges) gain an additional increment due to cold edges, and the latter contribute to the overestimate of hot edge counts. Figure 2a illustrates this point. It shows, for k = 3, errhot as a function of λ h in presence of cold elements with λ c = 5, for the gap value G = 20. For the purpose of comparison, the orange curve shows the error for the uniform distribution (as in Figure 1), that is the error that hot elements would have if cold elements were not there. We clearly observe the contribution of cold elements to the error, even in the load interval below the peelability threshold. Figure 2b illustrates that when the gap becomes larger (here, G = 50), the contribution of cold elements diminishes and the curve approaches the one of the uniform distribution. A larger gap leads to larger values of hot elements and, as a consequence, to a smaller relative impact of cold ones.

Another reason for which the above conjecture may not hold is the following: even if the number of hot elements is very small but the gap factor is not large enough, the cold edges may cause the counters to become large if λ c is large enough, in particular in the saturation regime described in Section 3.1. As a consequence, the "background level" of counters created by cold edges may be larger than true counts of hot edges, causing their overestimates. As an example, consider again the configuration with k = 3 and λ c = 5. The cold elements taken alone would have an error of about 6 on average (≈ 6.25, to be precise, data not shown) which means an about 7× overestimate. Since the graph is saturated in this regime (see Section 3.1), this means that most of the counters will be about 7 times larger than counts of cold edges. Now, if a hot element is only 5 times more frequent than a cold one, those will be about 1.4× overestimated, i.e. will have an error of about 0.4, This situation is illustrated in Figure 2c.

Mixed hypergraphs. The analysis above shows that in presence of a "background" formed by large number of cold elements, the error of hot elements starts growing for much smaller load factors than without cold elements, even if the latter are much less frequent than the former. Inspired by results of Section 3.1, one may ask if the interval of negligible error can be extended by employing the idea of variable number of hash functions. Note that here this idea applies more naturally by assigning a different number of hash functions to hot and cold elements.

Fig. 3: errhot as a function of λ h for k = 3, λ c = 5 and G = 20 (same as in Figure 2a) vs. k = (2, 5) for hot and cold elements respectively Figure 3 illustrates that this is indeed possible by assigning a smaller number of hash functions to hot elements and a larger number to cold ones. It is clearly seen that the interval supporting close-to-zero errors is extended. This happens because when the hot subgraph is not too dense, increasing the cardinality of cold edges leads to a higher probability that at least one of the vertices of such an edge is not incident to a hot edge. As a consequence, this element does not affect the error of hot edges. For the same reason, decreasing the cardinality of hot edges (here, from 3 to 2) improves the error, as this increases the fraction of vertices non-incident to hot edges.

Saturation in supercritical regime. In Section 3.1 we discussed the saturation regime occurring for large load values: when the load grows sufficiently large, i.e. the hash hypergraph becomes sufficiently dense, all counters reach the same level, erasing distinctions between edges. In this regime, assuming a fixed load (graph density) and the uniform distribution of input, the edge value depends only on input size and not on the graph structure (with high probability).

It is an interesting, natural and practically important question whether this saturation phenomenon holds for non-uniform distributions as well, as it is directly related to the capacity of distinguishing elements of different frequency. A full and precise answer to this question is not within the scope of this work. We believe that the answer is positive at least when the distribution is piecewise uniform, when edges are partitioned into several classes and are equiprobable within each class, provided that each class takes a linear fraction of all elements.

Here we illustrate this thesis with the step distribution. One can observe that in all configurations, values of hot and cold edges converge, which is a demonstration of the saturation phenomenon. Interestingly, the "convergence speed" heavily depends on the configuration: the convergence is "slower" for uniform configurations, whereas in the mixed configuration, it occurs right after the small error regime for hot edges.

Zipf 's distribution

Power law distributions are omnipresent in practical applications. The simplest of those is Zipf's distribution which is often used as a test case for different algorithms including Count-Min sketches [START_REF] Cormode | Summarizing and mining skewed data streams[END_REF][START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF][START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF][START_REF] Chen | Precise error estimation for sketchbased flow measurement[END_REF][START_REF] Ben Mazziane | Analyzing count min sketch with conservative updates[END_REF]. Under Zipf's distribution, element probabilities in descending order are proportional to 1/i β , where i is the rank of the key and β ≥ 0 is the skewness parameter. Note that for β = 0, Zipf's distribution reduces to the uniform one.

Zipf's distribution is an important test case for our study as well, as it forces several (few) most frequent elements to have very large counts and a large number of elements (heavy tail ) to have small counts whose values decrease only polynomially on the element rank and are therefore of the same order of magnitude. Bianchi et al. [5, Fig. 1] observed that for Zipf's distribution in the supercritical regime, the estimates follow the "waterfall-type behavior": the most frequent elements have essentially exact estimates whereas the other elements have all about the same estimate regardless of their frequency. Figure 5 illustrates this phenomenon for different skewness values. The waterfall-type behavior for Zipf's distribution is well explained by the analysis we developed in the previous sections. The "waterfall pool level" of values (called error floor in [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF]) is the effect of saturation formed by heavy tail elements. The few "exceptionally frequent" elements are too few to affect the saturation level (their number is n), they turn out to constitute "peaks" above the level and are thus estimated without error. Naturally, smaller skewness values make the distribution less steep and reduce the number of "exceptionally frequent" elements. For example, according to Figure 5, for λ = 5 and k = 2, about 50 most frequent elements are evaluated without error for β = 0.7, about 40 for β = 0.5 and only 5 for β = 0.3.

Following our results from previous sections, we studied whether using a variable number of hash functions can extend the range of frequent elements estimated with small error. We found that for moderate loads λ, this is possible indeed. More specifically, using a variable number of hash functions can lead to a sharper "break point" compared to the constant number of hash functions, see Figure 5. As a result, although the "waterfall pool level" may be higher, a larger range of most frequent elements are evaluated with small error. This observation matches the phenomenon illustrated earlier in Figure 4. Due to space limitation, we refer to the full version [START_REF] Fusy | Count-min sketch with variable number of hash functions: an experimental study[END_REF] for the data illustrating this point.

Conclusions

In this paper, we presented a series of experimental results providing new insights into the behavior of conservative Count-Min sketch. Some of them have direct applications to practical usage of this data structure. Main results can be summarized as follows.

-For the uniform distribution of input elements, assigning a different number of hash functions to different elements extends the subcritical regime (range of load factors λ) that supports asymptotically vanishing relative error. This immediately implies space saving for Count-Min configurations verifying this regime. For non-uniform distributions, variable number of hash functions allows extending the regime of negligible error for most frequent elements, -Under "sufficiently uniform distributions", including uniform and step distributions, a Count-Min sketch reaches a saturation regime when λ becomes sufficiently large. In this regime, counters become concentrated around the same value and elements with different frequency become indistinguishable, -Frequent elements that can be estimated with small error can be seen as those which surpass the saturation level formed by the majority of other elements. For example, in case of Zipf's distribution, those elements are a few "exceptionally frequent elements", whereas the saturation is insured by the heavy-tail elements. Applying a variable number of hash functions can increase the number of those elements for moderate loads λ.

Many of those results lack a precise mathematical analysis. Perhaps the most relevant to practical usage of Count-Min is the question of saturation level ("waterfall pool level"), as it provides a lower bound to the frequency of elements that will be estimated with small error, which in turn is a fundamental information for heavy-hitter type of applications. Bianchi et al. [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] observed that in the case of non-uniform distribution of input elements, the "waterfall pool level" is upper-bounded by the saturation level for the uniform distribution of input. This latter is computed in [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] using a method based on Markov chains and differential equations. We believe that this method can be extended to the case of mixed graphs as well and leave it for future work. However, providing an analysis for more complex distributions including Zipf's distribution is an open problem.

  e) -occ(e)).

= 5 Fig. 2 :

 52 Fig. 2: errhot for k = 3 depending on λ h , in presence of cold elements with λ c = 5 (blue curves) and without any cold elements (orange curve).

Fig. 4 :

 4 Fig. 4: Convergence of average estimates of hot and cold elements for 2-uniform (4a), 3-uniform (4b) and (2,5)-mixed (4c) hypergraphs. x-axis shows the total load λ = λ h + λ c with λ h = 0.1 • λ and λ c = 0.9 • λ and G = 10 in all cases.

Figure 4

 4 Figure 4 illustrates the saturation phenomenon by showing average values of hot and cold edges (G = 10) with three different configurations: 2-uniform, 3-uniform, and (2,5)-mixed. Note that the x-axis shows here the total load λ = λ h + λ c , where λ h = 0.1 • λ and λ c = 0.9 • λ. That is, the number of both hot and cold edges grows linearly when the total number of edges grows.One can observe that in all configurations, values of hot and cold edges converge, which is a demonstration of the saturation phenomenon. Interestingly, the "convergence speed" heavily depends on the configuration: the convergence is "slower" for uniform configurations, whereas in the mixed configuration, it occurs right after the small error regime for hot edges.

3 Fig. 5 :

 35 Fig. 5: Exact (blue) and estimated (orange) edge values for Zipf's distribution as a function on the element frequency rank, plotted in double log scale. All plots obtained for n = 1000, λ = 5, k = 2, and the input size 50 • 10 6 . Estimates are averaged over 10 hash function draws.

  The conservative version of Count-Min increments by 1 only the smallest of all A[h i (e)]. That is, A[h i (e)] is incremented by 1 if and only if A[h i (e)] = min 1≤j≤ke {A[h j (e)]} and is left unchanged otherwise.