\section{Acknowledgments}
The research leading to these results has received funding from H2020 Grant Agreement 826266: COADAPT.
This work is also supported by the Bayerisches Wissenschaftsforum (BayWISS) and the German Academic Exchange Service (DAAD).

\newpage
\bibliographystyle{IEEEbib}

\section{Introduction}\label{sec:introduction}
\begin{figure*}[t]
    \centering
    \includegraphics[width=\textwidth]{figures/emotion_tasks_distinction.jpeg}
    \caption{This figure explains and differentiates the concepts of \textit{Emotion State, Emotion Lexicon, and Emotion Carriers}. In the first example the emotional state 'sad' is directly described by the emotion lexicon using the word 'sad', whereas the second example does not use emotion lexicon to describe the emotional state 'excited', it is rather implicit and can be explained using emotion carriers.}
    \label{fig:emotion_tasks}
\end{figure*}
People express and communicate emotions consciously as well as subconsciously.
This is done by modifying the manner of speaking, the content of a conversation or written text, facial expressions, gestures, or even the way of walking. The combination of these signals, especially speech and text, has successfully been used to determine the emotional state of a person making a statement or telling a narrative~\cite{montacie2018vocalic,poria_review_affective_fusion_2017}. Most of the emotion research in affective computing aims at categorical or continuous recognition of emotions.
However, these tasks are not necessarily able to provide an explanation for the emotional state.
Tammewar \emph{et al.} defined the linguistic {\em carrier} of emotions and evaluated an annotation protocol in the context of PNs \cite{tammewar2020annotation}.
Detecting the fragments from the narratives that best explain the emotional state of the narrator would provide deeper emotion analysis that has potential benefits in the context of mental well-being applications, to analyze a user's Personal Narratives (PN).
This application of EC is described in \cite{tammewar2020emotion}.
A conversational agent, as part of a mental well-being application, uses previously extracted ECs, from the dialogue with the user, and generates a tailored response.
A deeper analysis of the the perceived emotion may help to ask better questions and get more information from the user.
This additional information in turn may help to better understand a user's emotional state through a conversation and makes showing empathy towards the user easier.

A previous analysis on how different fragments of PNs help explain the current mental state of the narrator in terms of valence  can be found in \cite{tammewar_modeling_2019}.
Not only fragments containing emotion words but also events ({\emph ``high school exam''}), people ({\emph ``grandpa''}), and actions ({\emph ``made me choose''}) were proven to be useful to predict the valence.
Following up on this analysis, \emph{Emotion Carriers (EC)} for PNs can be defined as the concepts that best explain and carry the emotional state of the narrator \cite{tammewar2020annotation}.
ECs thus include not only explicitly emotionally charged words, such as {\emph ``happy''}, but also mentions of people, places, objects, predicates, and events that carry an emotional weight within the context of a narrative.
They performed the annotation of German PNs from the Ulm State-of-Mind in Speech (USoMs) corpus \cite{rathner2018state} with the emotion carriers \cite{tammewar2020annotation}. In Figure~\ref{fig:emotion_tasks}, we explain and differentiate the three different emotion concepts: \textit{Emotion State, Emotion Lexicon}, and \textit{Emotion carriers}.

Further work on the automatic detection of emotion carriers from transcriptions of spoken PNs, can be found in \cite{tammewar2020emotion}.
However, relying only on lexical features leaves out the possibility of the same lexical content conveying different things based on acoustic context.

Ivanov \emph{et al.} showed that there is a relationship between meaning-bearing parts of utterances and their acoustic properties \cite{ivanov_acu_sem_2010}.
Following up on that research, we have found evidence supporting distinct prosodic profiles for emotion {\em vs} non-emotion carriers:
\figurename~\ref{fig:ec_spectrum} compares the spectrograms of two occurrences of the phrase {\emph ``vor die Wahl gestellt''; ``made me choose''}; while (a) was annotated as an emotion carrier, (b) was not.
The strong rise in fundamental frequency (f0), as well as the strong fluctuations at the beginning of \figurename~ \ref{fig:ec_spectrum}a, indicates emotional speech \cite{paeschke_f0_emo_1999}.
In contrast, the same phrase that was not marked as an EC has a very flat f0 contour (\emph{cf.} \figurename~\ref{fig:ec_spectrum}b).
While the figure provides only anecdotal and motivational evidence, in this paper we provide ample evidence of the complementarity of acoustic and lexical information.

Our contributions are:
\begin{itemize}
    \item evidence for the acoustic discriminability of EC
    \item word-level acoustic embeddings using a modified ResNet architecture and transfer learning from EmoDB
    \item analysis of early and late fusion of textual and acoustic embeddings
    \item rule-based late fusion based on posterior probabilities leveraging the strength of the lexical system

\begin{figure*}[htb]
\begin{minipage}{0.5\linewidth}\label{fig:res_a}
  \centering
  \centerline{\includegraphics[width=8.0cm]{figures/emo_spectrum_marked_f0.png}}
  \centerline{(a) emotion carrier}\medskip
\end{minipage}
\begin{minipage}{0.5\linewidth}\label{fig:res_b}
  \centering
  \centerline{\includegraphics[width=8.0cm]{figures/non_emo_spectrum_marked_f0.png}}
  \centerline{(b) non emotion carrier}\medskip
\end{minipage}
\caption{
Spectrograms with \textit{f0}-contour of the phrase: ``\textbf{vor die Wahl gestellt},''(Translation: ``made me choose'').
(a) was marked as an EC, showing signs of emotional speech and the voice cracking in the center part whereas (b) was taken from the same recording session, but was not marked as EC.
While this is an anecdotal example, statistical analysis revealed significant differences in f0, energy, and shimmer on nouns marked as EC when comparing them with all other nouns in the dataset.
}
\label{fig:ec_spectrum}
\end{figure*}

\end{itemize}
\section{Related Work}
\label{sec:relatedwork}
A related concept to EC are \emph{affective events} (AE)
~\cite{ding2016acquiring}.
Affective events are a predefined set of events that have a stereotipycally (w/o specific context) positive or negative impact on the people who experience the event.
In the set of AEs, an event is a tuple of subject, verb and object and the polarity is provided to the entire tuple, while ECs could be any entity or event, with no strict restriction on the syntactic categories, that carry the emotional state of the narrator.
AEs are closely linked to the satisfaction or violation of human needs ~\cite{ding_affective_event_2018}.
While this can be true for EC, it is not a necessity, as EC can be identified in personal narratives, where only the recollection of events leads to the current emotional state.
Identifying what moves or creates an emotional reaction in a personal narrative can for example help a personalized mental health application ask questions about what is important w.r.t. the emotional state of the narrator.

To our knowledge, there is no prior work on merging acoustic and lexical features for  detecting AE.

Relevant techniques for utilizing multiple modalities can be found in the related field of Speech Emotion Recognition (SER), where the use of multiple modalities is common \cite{pepino_fusion_2020,georgiou_deep_2019,hazarika_conversational_2018,meng_speech_2019}.
Most research on Emotion Recognition (ER) is focused on classifying the emotion of a writer or narrator into discrete values such as fear, anger, or joy.
This is usually done on an utterance, dialogue, or narrative level \cite{schuller_ser_2018}.

The SER task is concerned with the direct classification of a persons' emotional state whereas EC detection is looking for events, entities, and people that explain the subject's current emotional state.
ECs are the linguistic {\em vehicles} of emotions and provide insights into the entities, people, and events that explain the narrators' emotional state.
Related work focusing on acoustic cues in meaning structures can be found in \cite{ivanov_acu_sem_2010} where the authors found a relationship between acoustics and meaning.
Nastase \emph{et al.} studied the relation between words that express emotions and the way they sound.
The study found statistical evidence that phonetic features are useful in determining if words express the same emotion \cite{nastase_happy_2007}.
Batliner \emph{et al.} used word-level emotional labels and tried classifying emotional state of children on word and turn level, using acoustic features as well as a combination of lexical and acoustic features \cite{batliner_combining_2006}.
Huang \emph{et al.} combine word-level acoustic embeddings with Word2Vec for utterance-level emotion recognition \cite{huang2018ser}

Current fusion approaches for multi-modal emotion recognition essentially follow a similar approach.
The first step is finding appropriate intermediate representations, usually produced by using some kind of encoder neural network, and then, depending on the problem, train a classifier applying different fusion strategies \cite{pepino_fusion_2020,georgiou_deep_2019,hazarika_conversational_2018,meng_speech_2019}.
For example, Pepino \emph{et al.} use CNNs to extract sentence-level embeddings from pre-trained word embeddings and utterance-level embeddings using a CNN on handcrafted acoustic features comparing different fusion approaches \cite{pepino_fusion_2020}.

\section{Data}\label{sec:data}

All experiments presented to detect EC and analyses in this paper were conducted using the dataset and annotations described in \cite{tammewar2020annotation}.
The dataset is based on the USoMs corpus described in the Interspeech 2018 ComParE paralingiustics challenge \cite{schuller_interspeech_2018}.
The USoMs dataset consists of spoken PNs collected from 100 participants; audio data was converted to 16\,kHz mono, and a noise profile was removed where necessary.
Manual transcriptions were obtained from a professional transcription service (verbatim approach \cite{dresing_2011}), with a vocabulary of 6438 words.
The data of 66 participants (239 PNs) was annotated with the ECs by four annotators, selecting emotion-carrying text spans using the transcript only \cite{tammewar2020annotation}.
ECs are annotated with the inside–outside (IO) scheme which is common in natural language processing.
Words that belong to a text span marked as EC are annotated as \textit{I} others as \textit{O}.
The resulting dataset is heavily imbalanced with only 6.6\,\% of tokens marked as EC.

Accurate time alignment of text to audio was produced by forced alignment (FA) using a speaker-adaptive HMM-GMM (Hidden Markov Model, Gaussian Mixture Model) automatic speech recognition system (ASR) based on \cite{milde_tuda_2018}.
Missing entries in the pronunciation lexicon were generated using a grapheme-to-phoneme tool \cite{bisani_g2p_joint_seq_mod_2008} where necessary.

Before running any classification and fusion experiments for the detection of EC, we performed an in-depth feature analysis.
We focused on prosodic word-level features of nouns marked as EC, as only they were labeled in a significant number of cases being an EC ($N=15600$, of which 2019 were EC nouns).
While Fig.~\ref{fig:ec_spectrum} provides anecdotal evidence only, we could identify significant differences between the nouns marked as EC and those that were not.
F0, energy, and HNR (Harmonic to Noise Ratio) were extracted using Praat with the Parselmouth library and Jitter and Shimmer were calculated based on the extracted f0 using the method described in \cite{farrus_using_jitter_2009}.
Our analysis revealed significant differences on a word-level for mean f0 (and its derivatives), mean energy (and its derivatives) as well as shimmer using an independent two-sample t-test ($p=0.05$).

\section{Method}
We follow the approach of finding representations for EC from different feature spaces.
As EC are a word-, and phrase-level concept, we try to find appropriate representations from the linguistic and acoustic input feature space.
The representations are then used in uni-modal experiments as well as multi-modal fusion experiments for EC recognition.

\begin{figure*}[t]
    \centering
    \includegraphics[width=\linewidth]{figures/Comments_Tobi_MERGE_ResNet_LF.png}
    \caption{
    Overview of the neural network architecture used in the experiments.
    The left part shows the ResNet classifier containing the audio embedding layer which is used to extract word-based acoustic embeddings (WAE) for each word.
    The central part contains the sequence tagging (ST) architecture that can operate using either word-based textual embeddings (WTE), WAE, or a combination of WTE and WAE in an early fusion (EF) approach.
    The right part of the figure is depicting the late fusion (LF) and decision level fusion (DLF) systems. Inputs for the LF are taken after the fully connected layer in the ResNet and the ST, using only WTE as inputs, as logits (A1, T1) and for DLF after the Softmax layer (A2, T2) returning normalized probabilities.
    }
    \label{fig:architecture}
\end{figure*}

\subsection{Word-based textual embeddings (WTE)}
For word-based textual embeddings, we use 100-dimensional pre-trained GloVe word embeddings trained on the German Twitter corpus \cite{pennington_glove_2014}.
A total of 656 (10.2\%) words were not present in the pre-trained embeddings.
The word-embeddings where fine-tuned on the actual task inside the cross-validation loops.

\subsection{Word-based acoustic embeddings (WAE)}

The previously performed feature analysis revealed differences between EC and non EC with respect to handcrafted acoustic features.
This motivated us to use embeddings based on convolutional neural networks (CNN) and handcrafted acoustic features as described in \cite{pepino_fusion_2020}.
Our early stage experiments failed to produce good results on an utterance level with the German EmoDB dataset \cite{burkhardt_emodb_2005} on the speech emotion recognition (SER) task.

The failure to produce good results with CNNs and handcrafted acoustic features led us to explore other network architectures and input features.
We decided to use a ResNet architecture which was successfully applied to a number of speech applications such as speaker recognition, and SER and has been shown to produce good embeddings \cite{Chung_2018_voxceleb, tang_2018_resnet_ser}.
ResNets are fully convolutional neural networks (FCN) and can handle inputs of different sizes (or lengths, respectively) due to a global pooling layer at the end of the convolutional part of the neural network.
The network we use is very similar to the one described in \cite{he_resnet_2016} and consists of 18 convolutional blocks (ResNet18).
Its architecture was adapted by removing the initial max-pooling layer to keep more features prior to the residual blocks as the expected inputs are already relatively small.
The dimensionality of the embedding layer was reduced from 1000 to 512 and the final classification layer was altered to match the number of classes (2).

As acoustic input features for the ResNet, we extract 40-dimensional Mel-frequency cepstrum coefficients (MFCC) with a window length of 0.025\,s, a frameshift of 0.01\,s, along with 1st and 2nd order moments, stacking them to a tensor with three dimensions (frequency x time x moments) and apply z-score normalization.
Those acoustic input features are then used to train the acoustic only classifier and to extract neural acoustic word embeddings from the trained acoustic encoder.
The word-based acoustic contexts are extracted using the aforementioned FAs.

The network was pre-trained on short utterances from the German EmoDB corpus to differentiate between neutral and emotional speech \cite{burkhardt_emodb_2005}.
This is done to learn filters that are already primed to extract features from speech that are important to classify emotional speech.
Both pre-training and training were done using stochastic gradient descent with a cross entropy loss function.
To overcome the class imbalance problem, an oversampling strategy was applied as it had proven to be the best performing technique in our experiments.

To obtain word-based acoustic embeddings (WAE), we froze to resulting model to act as an acoustic word encoder.
We feed the word-based acoustic context to the model and extract WAE from the embedding layer of the model.

\subsection{Sequence Tagging}
\label{sec:sequence_tagging}
We model the task of detecting emotion carriers as a binary sequence labeling problem using both modalities, with targets encoded as \textit{I} if the token is part of an EC and \textit{O} otherwise.
For this task, we adopt a bidirectional Long Short-Term Memory (LSTM) neural network with an attention-based sequence tagging (\textbf{ST}) architecture previously used for labeling candidates for emphasis in written text \cite{shirani2019learning}.\footnote{Implementation: \url{https://tinyurl.com/seqtagging}}
An overview of the architecture is located in the central part of Fig.~\ref{fig:architecture}.

\subsection{Fusion}
There are two main challenges in combining multiple modalities: How to combine features of different dimensionality and valuation, and at which stage to combine the streams.
In general, three different kinds of approaches can be differentiated: early, late, and decision-level fusion.
\subsubsection{Early and late fusion}
In early fusion (EF), features for each modality are extracted separately, i.e.~each modality represents a view of the same concept.
The resulting feature vectors are then combined, e.g.~by concatenation or stacking, and then treated as a single input channel.
In late fusion (LF), each modality has its own model and is often trained independently.
The outputs of those classifiers are used as input to another classifier that combines them for an overall best prediction.
EF as used in this paper can be found at the center of Figure~\ref{fig:architecture} and the LF approach can be found at the top right.

\subsubsection{Decision Level Fusion}\label{sc:DLF}

In our experiments the sequence tagger using WTE is trained as a regression problem with the Kullback–Leibler (KL) divergence, predicting the probability of a token being an emotion carrier.
For this, the best decision threshold was experimentally found to be $p_{db}=0.15$ for lexical features only.
This motivated us to explore a rather heuristic late fusion approach: a \textit{rule-based cascaded classifier based on posterior probabilities.}
Applying a similar technique to the normalized probabilities in the output of the ResNet classifier, we can find a decision threshold and then merge the decisions, defining decision states around these thresholds.
This way it is possible to leverage long-range lexical information as well as local acoustic information.

We define the lexical-based ST model to be the primary model and the ResNet classifier to be the disambiguator, leveraging local acoustic information.
In our merging approach, we define an $\epsilon$ parameter that indicates how certain a classifier is with the decision if a token is an EC.
The decision boundary (DB) is defined by setting a probability value $p_{db}$.

We only consider the probability for the EC to determine certainty.
If the normalized probability of a token being an EC $p_{ec}$ is within the epsilon interval $(p_{db} \pm \epsilon)$ the classifier is considered to be uncertain regarding a positive decision of a token being an EC.
$p_{ec} > p_{db} + \epsilon$ is considered to be certain.
Those certainty indicators are computed for both models separately.
Merging is then done by checking certainty indicators:
If the lexical model is certain, the token is considered to be an EC.
If the lexical model is uncertain and the acoustic model is certain, the token is also considered as an EC.
In all other cases, the token is not considered as an EC.
We call this heuristic \textit{decision level fusion} (DLF).

\section{Experiments}\label{sec:experiments}

Results for single modality, fusion experiments, and baselines, are reported in Tab.~\ref{tbl:results}.
As this is an information retrieval task, we report metrics for class \textit{I} in this unbalanced task.
The equal priors baseline constitutes random guessing with no knowledge about the actual class distribution with $p_{I}=p_{O}=0.5$, resembling a fair coin toss whereas the class priors baselines resembles a heavily biased coin with $p_{I}=0.066$ and $p_{O}=0.934$.
\subsection{Training Details}
All experiments were performed using five-fold cross-validation with consistent folds across all experiments.
The folds were split by speaker to ensure no speaker in the test set was present in the training set and hyper-parameters were tuned on separate development folds, as is common when working with acoustic data and small datasets.
Tab.~\ref{tbl:results} contains results for single modality classification using a ResNet classifier as well as ST using either WTE or WAE as inputs.
We report one result for an EF experiment concatenating WTE and WAE to a single word vector as well as a logit-based LF experiment combining the ResNet classifier and the ST using WTE as inputs only.
Lastly, we show our overall best results, obtained with DLF and oracle results.
Oracle results are obtained by a fictitious fusion of classifiers, which is considered to be right, if at least one of the contributing classifiers (ResNet18 and ST WTE), predicted the correct label.
Details of the proposed neural network architectures can be found in Fig.~\ref{fig:architecture}.
\subsection{Results}

Direct word-level EC detection using only MFCC features (ResNet18) improved results compared to both random baseline classifiers using class priors for both actual class priors in the dataset as well as equal class priors.
It can therefore be assumed that useful representations can be extracted from the embedding layer of the ResNet classifier.
The analysis of the word-based acoustic embeddings produced by the ResNet system also looked promising.
Fig.~\ref{fig:ec_tsne} contains a t-distributed Stochastic Neighbor Embedding (t-SNE) plot of embeddings marked as EC vs. embeddings not marked as EC.
The plot shows that there is potential to differentiate EC from non-EC tokens in this low-dimensional projection.

While we achieved good results with the ST using WTE only, results for the WAE failed to perform better than the ResNet classifier that solely relied on local acoustic information.
It barely improved results compared to the random classifiers' expected baseline precision.
We, therefore, decided to not use the ST with WAE in late fusion experiments and rather use the ResNet classifier in LF.

The EF experiment combining WAE and WTE performed worse than WTE alone as described in this paper and only slightly improved previous WTE only results \cite{tammewar2020emotion}.
The LF experiment using logit outputs from the ResNet classifier and the ST using WTE improved the ST using WTE only in terms of recall, but lowered the precision which lead to overall worse results w.r.t. F1-I.
Experiments with Logistic Regression to model the probability of a word being an EC using the logit outputs of the ST using WTE and the ResNet classifier did not improve over the LF experiment with the FCNN.

Unfortunately, the experiments using the standard EF and LF approaches couldn't improve over the already strong textual system (ST WTE).
However as shown in Fig.~\ref{fig:ec_spectrum} and the feature analysis, there definitely is evidence that acoustic information can help with the detection of EC.
Our experiments with the word-level ResNet classifier could not completely convince but still beat all statistical baselines as a stand-alone system.
Lastly oracle results presented in Tab.~\ref{tbl:results} show that the combination of the ResNet classifier and the ST using WTE has a lot of room for improvements still.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.8\linewidth]{figures/TP_anspannung_tsne.png}
\caption{t-SNE plot for the word-based acoustic embeddings of the German word "Anspannung" (English: tension). Red dots represent tokens marked as EC while blue are non EC.}
\label{fig:ec_tsne}
\end{figure}

This led us to explore the rather heuristic decision level fusion (DLF) approach described in ~\ref{sc:DLF} and yielded the best overall results.
The decision boundary was tuned for the ResNet classifier only since the ST using WTE was already trained using KL divergence with a tuned decision boundary at $p_{db}=0.15$.
The DB for the ResNet classifier was determined using 5-fold cross-validation.
Results are reported in Tab.~\ref{tbl:results} (DLF).
The decision boundary for certainty of the ResNet classifier was found to be $p_{DB}=0.75$ with $\epsilon=0.05$.

\begin{table}
\centering
\caption{Precision, Recall and F1 scores for class \textit{I} of
EC detection.
We report results for different models trained using combinations of modalities (acoustics and lexical) with early (EF), late (LF) and decision level late fusion (DLF) using posterior probabilities.
For LF, only the best performing experiment using a fully connected neural network (FCNN) is shown.
Baseline results are included for equal priors with $p_{I}=p_{O}=0.5$ representing a fair coin toss and class priors with $p_{I}=0.066$ and $p_{O}=0.934$.
The results are in the format: \textit{mean(std)}; computed over the five folds.}
\setlength\tabcolsep{7 pt}
\label{tbl:results}
\scalebox{0.86}{\begin{tabular}{|l|c|c|c|c|}
\hline
 \textbf{Model} & \textbf{Features}  & \textbf{Prec-I}  & \textbf{Recall-I}  & \textbf{F1-I}  \\
\hline
Baseline & equal priors & 6.6  & 50.0  &  0.12 \\
\hline
Baseline & class priors & 6.6  & 6.6  & 0.07 \\
\hline
ResNet18 & MFCCs & 19.4 (5.3) & 64.6 (14.6)  & 0.29 (0.05) \\
\hline
ST &  WAE & ~7.6 (2.3) & 40.3 (9.0) & 0.13 (0.03) \\
\hline
ST & WTE & 37.9 (6.9) & 46.7 (6.4) & 0.41 (0.03) \\
\hline\hline
ST EF & WTE, WAE &  35.3 (6.4) & 44.3 (5.9) & 0.39 (0.04) \\
\hline\hline
FCNN LF &  logits      &   25.6 (3.6)      & 52.5 (9.2)            & 0.34 (0.01)          \\
\hline\hline
\textbf{DLF}  & \textbf{post. prob.} & \textbf{42.3 (5.3)}  & \textbf{51.2 (6.4)}  & \textbf{0.46 (0.05)}  \\
\hline\hline
Oracle & - & 70.6 (6.1) & 67.4 (4.6) & 0.69 (0.03) \\
\hline
\end{tabular}}
\end{table}
\section{Discussion and Conclusion}\label{sc:discussion}

With a strong lexical baseline and the promising results from previous work, we were convinced that ordinary fusion strategies would help to improve our results.
The high recall on the acoustic ResNet18 system was encouraging.
However, the results for EF and LF experiments suggest that simply adding the acoustic representations, extracted from the ResNet, adds a lot of entropy that the system in its current architecture can't handle, yielding worse accuracy than the textual system.

The analysis of the extracted representations and our knowledge about the existence of acoustic cues led us to explore heuristic ways to combine the modalities.
The final DLF experiments show that the accuracy of the lexical model with its knowledge about context and content of a narrative could be improved by relying on local acoustic information in case of uncertainty.

The task of detecting EC is an important step towards a deeper understanding and better modeling of a person's emotional state; ECs can also benefit natural language understanding tasks such as dialog modeling.
Combining acoustic and lexical modalities yields higher accuracy than the uni-modal approaches to this difficult task if done the right way.
We could show that local acoustic information alone is not reliable to detect EC but helps to improve results when combined with a text-based system that captures long-range semantic relations.

The research on acoustic cues of emotion carriers is still in the initial stage.
In future work, we will look into more effective word-level acoustic representations that can be used in typical fusion approaches.


\section{\uppercase{Introduction}}
\label{sec:introduction}

Learned Data Structures is a  novel area at the crossroad of Classic Data Structures and Machine Learning. They have been initially proposed by Kraska et. al. \cite{Kraska18} and have had a rapid growth
\cite{Ferragina:2020book}. Moreover, now the area  has been extended to include also Learned  Algorithms \cite{Mitz20}.
The theme common to those new approaches to Data Structures Design and Engineering is that a query to a data structure is either intermixed with or preceded by a query to a Classifier \cite{duda20} or a Regression Model~\cite{FreedmanStat}, those two being the learned part of the data structure.  To date,
	Learned Indexes have been the most studied, e.g.,  \cite{amato2021learned,Ferragina:2020pgm,FERRAGINA21,Kipf20,Kraska18,Mailtry21,Marcus20,Markus20b}. Rank/select data structures have also received some attention \cite{Boffa21}.

	Bloom Filters \cite{Bloom70}, which are the object of this study, have also been considered,  as we detail next. Historically, they have been designed to be a data structure able to solve the Approximate Membership  Problem in small space (see Section \ref{sec:ASM}). Due to their fundamental nature and pervasive use, many variants and alternatives have been proposed. A good review in the domain of Internet applications is provided in \cite{Broder2005}.

	Kraska et al. \cite{Kraska18} have proposed a learned version of such a filter, in which a query to the data structure is preceded by a query to a suitably trained  binary classifier. The intent is to reduce space and reject time. Mitzenmacher \cite{Mitz18}  has provided a model for those filters, together with a very informative mathematical analysis of their pros/cons and even an alternative proposal. Additional Learned Bloom Filters have been proposed  recently \cite{Dai,Kraskap}. It is worth pointing out that, although they differ in architecture, each of those proposals has a classifier as its central part.

	Somewhat puzzling is that, although the classifier is the novel part of this new family of Filters and it is accounted for in theoretical studies \cite{Mitz18}, not much attention is given to which classifier to use in practical settings. Kraska et al. use  a Neural Network, while Dai and Shrivastava and Vaidya et al. use Random  Forests. Those choices are only informally motivated, giving no evidence of superiority with respect to other possible ones, via a comparative analysis.
	Therefore, the important problem of how to choose  a specific classifier in conjunction with  a specific filter has not been addressed so far,  even in one application domain.

     Such a State of the Art is problematic, both methodologically and practically. Here we propose the first, although initial, study that considers the choice of the classifier within Learned Filters. Since our study is of a fundamental nature, we consider only basic versions of the Filters and six generic, if not textbook, classifier paradigms.
     The intent is to characterize how different classifiers affect different performance parameters of the Learned Filter.  The application domain is the one of malicious URL determination, as in previous work. \rev{As per literature standard, our datasets are real and fall within the  data size used by Dai and Shrivastava}. However, even so, Random Forest classifiers do not seem to be competitive in our setting, needing bigger datasets. Indeed, for the continuation of this work, we plan to consider much larger datasets and include also Random Forests. Additional application domains will also be considered.

     Our results provide a confirmation of some expected behaviours, like that more complex classifiers tend to yield larger space reduction when used within a learned Bloom Filter, but also some counterintuitive perspectives, including that simple linear classifiers might represent very competitive alternatives to their bigger counterparts, sometimes even better. These results make more sense if we consider that  in a learned Bloom Filter classifiers come up with one or two classic Bloom Filters, calibrated in turn on the classifier performance, and accordingly it is their synergy that determines the overall space reduction, not just the classifier itself. Finally, a relevant note is also that in our experiments linear classifiers allow two orders of magnitude faster reject times.

\section{Approximate Set Membership Problem: Definitions and Key Parameters}\label{sec:ASM}
\paragraph{{\bf Definition}.} Given $S\subset U$ and $x\in U$, where $U$ is the universe of keys, the \textit{set membership} problem consists in finding a data structure able to determine if $x \in S$. The \textit{approximate
set membership} instead allows for a fraction $\epsilon$ of \textit{false positives}, that is elements in $U \setminus S$ considered as members of $S$. No \textit{false negatives} are allowed.  That is,  elements in $S$ considered as non-members.\\

\paragraph{\textbf{A  Paradigmatic Example}. } Assume that a set of URLs is given. They can be \emph{malicious}, i.e.,  websites hosting
unsolicited content (spam, phishing, drive-by downloads, etc.), or luring unsuspecting users to become victims of scams (monetary loss, theft of private information, and malware installation), or otherwise labeled as \emph{benign}. The aim is to design a time efficient data structure that takes small space and that ``rejects'' benign URL quickly, as they do not belong to the malicious set. On occasions, we may have false positives.

\paragraph{\bf Key Parameters of the Filter.} The reject time, taken as the expected time to reject a  non-member of the set; the space taken by the data structure, since the cardinality of $S$ may be very large; the false positive rate $\epsilon$. Quite remarkably, Bloom provided two data structures to solve the posed problem, linking the three key parameters in trade-off bounds. The most space-efficient of those data structures goes under the name of Bloom Filter and it is outlined next, together with two of its learned versions.

\subsection{Basic Classic and Learned Bloom Filters}\label{sub:BFs}

\paragraph{\bf Classic.}
Letting $|S|=n$, a Bloom Filter (BF) is made up by a bit array $\textit{\textbf{v}}$ of size $m$, whose elements are all initialized to $0$. It uses $k$  hash functions $h_j: U \longrightarrow \{0, 1, \ldots, m-1\}$,  $j \in \{1, \ldots, k\}$, which can be assumed to be perfect in theoretic studies (see \cite{Mitz18}).
When a new element $x$ of $S$ is added, it is coded using the hash functions: each bit in $\textit{\textbf{v}}$ in position $h_j(x)$ is set to $1$, for each $j \in \{1, \ldots, k\}$.
To test if a key $x\in U$ is a member of $S$, $h_j(x)$ for each $j$ is computed, and $x$ will be rejected if there exists $j \in \{1, \ldots, k\}$ such that $v[h_j(x)] = 0$. However, when the Bloom Filter considers $x$ as a member, it might be a false positive due to the hash collisions.  The false positive rate $\epsilon$ is inversely related to the space usage of the bit array. More accurately, the trade-off formula   connecting the key parameters of the Filter is given in equation (21) in \cite{Bloom70}. Analogous trade-off formulas are also known, e.g., \cite {Broder2005,Mitz18}. In  applications~\cite{Broder2005}, one usually asks for the the most space-conscious filter, given a false positive rate, being the reject time a consequence of those choices.

\medskip

\paragraph{\bf Learned: One classifier and one filter.}
The intent of this data structure, named Learned Bloom Filter (LBF), is to achieve a given false positive rate, as in a classic filter, but in less space, and possibly with little loss in reject time~\cite{Kraska18}. One can proceed as follows. A classifier $C:U \longrightarrow [0,1]$ is trained on a labeled dataset
$(x, y_x)$, where $x\in D \subset U$, $S\subset D$, and $y_x=1$ when $x \in S$,  $y_x=-1$ otherwise. The positive class is thereby the class of keys $S$. The larger $C(x)$, the more likely $x$ belongs to $S$. Then, in order to have a binary prediction, a threshold $\tau \in (0,1)$ is to be fixed, yielding positive predictions for any $x\in U$ such that $C(x) \geq \tau$, negative otherwise.
To avoid false negatives in the learned Bloom Filter, that is elements $x\in S$ rejected by the filter, a classic ``backup'' Bloom Filter $F$ is created on the set $\{x \in S|C(x) <\tau\}$. A generic key $x$ is tested against membership in $S$ by computing the corresponding prediction $C(x)$: $x$ is considered as an element of $S$ if $C(x) \geq \tau$ or $C(x) < \tau$ and $F$ does not reject $x$. $x$ is rejected otherwise. Unlike a classic Bloom Filter, the false positive rate of a LBF depends on the distribution of a given query set $\bar S\in U\setminus S$~\cite{Mitz18}. Hereafter, we will refer to $\epsilon_{\tau} = |\{x \in \bar S |  (C(x)\geq \tau)\}|$ as the \textit{empirical} false positive rate of the classifier on $\bar S$, to $\epsilon_{F}$ as the false positive rate of $F$, and to the \textit{empirical} false positive rate of the LBF on $\bar S$ as $~\epsilon = \epsilon_{\tau} + (1-\epsilon_{\tau})\epsilon_{F}$. Fixed a desired $\epsilon$, the optimal value of $\epsilon_F$ is \[
\epsilon_F = \frac{\epsilon - \epsilon_{\tau}}{1 - \epsilon_{\tau}},\
\] which yields the constraint $\epsilon_{\tau} < \epsilon$.

It is to be pointed out that now, false positive rate $\epsilon$, space and reject time of the entire filter are intimately connected and influenced by the choice of $\tau$. Another delicate point that emerges from the analysis  offered in \cite{Mitz18} is that, while the false positive rate of a classic Filter can be reliably estimated experimentally because  of its data independence, for  the Learned version this is no longer so immediate and further insights are needed. As  an additional contribution, an experimental methodology is  suggested in \cite{Mitz18}  and we adhere  to it here.

\medskip

\paragraph{\bf Learned: Sandwiched classifier.}
The intent of this variant, named Sandwiched Learned Bloom Filter (SLBF), is to filter out most non-keys before they are supplied to the LBF. This would allow the construction of a much smaller backup filter $F$ and an overall more compact data structure~\cite{Mitz18}. The specifics follow.  A Bloom Filter $I$ for the set $S$ precedes the structure of the Learned Bloom Filter described in the previous paragraph. The subsequent LBF is constructed on the elements of $S$ not rejected by $I$. Clearly, $I$ might yield a considerable number of false positives, when a limited budget of bits is dedicated to it. A query $x\in U$ is rejected by the SLBF if $I$ rejects it, otherwise the results of the subsequent LBF is returned.
Denoted by $\epsilon_{I}$ the false positive rate of the filter $I$, the empirical false positive rate of a SLBF is $\epsilon = \epsilon_I \big(\epsilon_{\tau} + (1-\epsilon_{\tau})\epsilon_{F} \big)$. For a desired value of $\epsilon$, the following properties hold~\cite{Mitz18}:
\begin{itemize}
    \item $\epsilon_I=\frac{\epsilon}{\epsilon_{\tau}} \Big(1-\frac{FN}{n}\Big)$, with FN number of false negatives of $C$;
    \item $\epsilon\Big( 1-\frac{FN}{n}\Big) \leq \epsilon_{\tau} \leq 1-\frac{FN}{n}$.
\end{itemize}
As for the previous learned Bloom Filter variant, the classifier accuracy affects all the key factors of a SLBF, namely false positive rate, space and reject time. Considerations and experimental methodologies in this case are the same as in the previous case.

\section{Experimental Methodology}\label{sec:reprod}

\subsection{General Purpose Classifiers}\label{sub:classif}
The classifiers used in our analysis are \rev{briefly described below}. We assume each $x \in U$ is represented through a set of $n$ \rev{real-valued} attributes $A = \{A_1, \dots, A_n\}$, and that $Y = \{-1,1\}$ is the set of labels, with -1 denoting the negative class. The training set is made up by labeled instances $D\subset U$, in the form of couples $(x, y_x)$,  with $x\in D$ and $y_x \in Y$.
\begin{itemize}
\item \textit{RNN-k}. A character-level recurrent neural network with Gated Recurrent Units (GRU)~\cite{RNN}, having $10$-dimensional embedding and $k$-dimensional GRU. RNN is included as baseline from literature for the same problem~\cite{Kraska18}. The parameters to be learned are the connections weights and unit biases for all the layers in the model.

\textit{Hyperparameters}. The hyperparameters here are the embedding dimension, the GRU size $k$, the learning and the dropout rate. No changes in their configuration has been made with regard to the setting used in~\cite{Kraska18}, except for the size of the embedding layer, reduced to $10$, as done in \cite{ma2020}, to comply with the reduced size of our dataset, and the smaller size of the overall filter as well. The embedding dimension and $k$ affect the design of the Learned Filters. Therefore, we refer to them as  key hyperparameters. We use the same terminology also for the other classifiers used in this study.
\\
\item \textit{Naive Bayes (NB)}. A Naive Bayes Classifier~\cite{NaiveBC} ranks instances based on Bayes' rule. It learns the conditional probabilities of having a certain label $Y=y_k$ given a specification of the attributes $A_i$:
\small
\begin{displaymath}
Y \leftarrow \arg\max\limits_{y{_k}} \frac{P(Y=y_k)P(A_1=x_1\ldots A_n=x_n|Y=y_k)}{\sum\limits_{j}P(Y=y_j)P(A_1=x_1\ldots A_n=x_n|Y=y_j)}.
\end{displaymath}
\normalsize
The conditional probabilities on the right are parameters of the model, and are efficiently estimated from training data by assuming all attributes are conditionally independent given $Y$ (naive). To deal with missing attribute configurations and to avoid zero estimates of some parameters, a regularization yielding smooth estimates is applied.

\textit{Hyperparameters}. The only hyperparameter is the one determining the strength of the smoothing for missing combinations of the attributes, which is not a key hyperparameter.
\item \textit{Logistic Regression (LR)}. The logistic regression~\cite{LRegr} classifies an instance $x = (x_1, \ldots, x_n)$ as negative if
\begin{displaymath}
P(Y=-1|A=x) > P(Y=1|A=x),
\end{displaymath}
where
\begin{displaymath}
P(Y=-1|X=x) = \frac{\exp(w_0 + \sum_{i=1}^n w_ix_i)}{1 + \exp(w_0 + \sum_{i=1}^n w_ix_i)},
\end{displaymath}
and $P(Y=1|X=x) = 1 - P(Y=-1|X=x)$. Here, $w = w_0, \ldots w_n$ are parameters of the classifiers, which are estimated from training data. A regularization is typically applied to impose the norm of $w$ to be minimized along with the maximization of the conditional data likelihood.

\textit{Key hyperparameters}. The model has just one hyperparameter, the one determining the strength of the regularization, which is not key.
\item \textit{Linear Support Vector Machine (SVM)}. Linear SVMs~\cite{SVM} classify a given instance $x\in\mathbb{R}^n$ as $f(x) = w^T\cdot x +b$, where $\cdot$ is the inner product operator, $w \in \mathbb{R}^n$, and $b \in \mathbb{R}$. The hyperplane $(w, b)$ is learned to maximize the margin between positive and negative points: \begin{displaymath}\label{eq:SVM}
\begin{array}{l}
	{\displaystyle \min_{\substack{w \in \mathbb{R}^n}} \frac{1}{2}\|w\|^2 +\ C\sum_{x\in D}\xi_x}
\\
	\text{s.t.} \quad y_xf(x) \geq 1-\xi_x  \quad x \in D
\\
\	\quad\hspace*{3mm} \xi_x \geq 0  \hspace{1.65cm} x \in D~,
\end{array}
\end{displaymath}
where $\xi_x$ is the error in classifying instance $x$, and $C$ is an hyperparameter regulating the tolerance to misclassifications. Non-linear SVMs, e.g. with Gaussian kernel, have been discarded due to their excessive size, in light of the fact that they need to store not just the hyperplane, but the also the kernel matrix.

\textit{Hyperparameters}. $C$ is the unique hyperparameter for this classifier, and it is not key.
\item \textit{FFNN-h}. A Feed-Forward neural network~\cite{FFNN} with the input layer of size $n$, one hidden layer with $h$ units, and one output unit with sigmoid activation. The weights of connections and the neuron biases are the parameters to be estimated from training data.

\textit{Hyperparameters}. The learning rate, the activation function for the hidden layer, and the number of hidden units $h$ are hyperparameters here, with the latter being also a key hyperparameter.

\end{itemize}

\subsection{Data and Hardware}
Following the literature, we concentrated on URL data. URLs are  divided into  benign and malicious addresses, with the latter typically stored in the filter. They are as follows.

\begin{itemize}
    \item The first dataset comes from~\cite{URLUnimas}, and contains 15k benign and 15k malicious URLs.
\item The second dataset comes from~\cite{URLTrento}, in particular as benign we have chosen 3637 entries in the category legitimate uncompromised, and as malicious 38419 entries in the category hidden fraudolent.
\end{itemize}
As for the training of the classifiers, we use both the mentioned datasets with their division  in benign and malicious. Since the number of benign elements does not guarantee good training on the NN-based  classifiers included in this research, we also consider the following dataset.

\begin{itemize}
    \item All the 291753 URL available at~\cite{URLBotw}, that we take as being benign.
\end{itemize}

In analogy with~\cite{ma2020}, we processed the Web addresses as follows.
\begin{itemize}
    \item \textit{Standardization}. Common strings like {\tt "www."} and {\tt "http://"}  have been removed from each URL, and URLs have been resized to a length of 150, by either padding shorter addresses with a marker symbol or by truncating excess characters, removing duplicated URLs. The resulting dataset contains $310329$ benign and $43744$ malicious URLs.
\end{itemize}

Finally, the datasets have been suitably coded for the input of the classifiers employed in this work.
\begin{itemize}
    \item \textit{Input coding for RNN}. In analogy with~\cite{ma2020}, URLs have been coded by mapping
each character to consecutive integers starting from 1 to 128 in order of frequency in the training set, and to 0 all the remaining characters, eventually obtaining a 150-dimensional vector. For their nature, such classifiers need an embedding layer taking as input the whole sequence of characters in the address to execute the training.
    \item  \textit{Input coding for other classifiers}. Here a standard \textit{bag of char} coding is adopted, based on the fact that the remaining classifiers are more flexible on their input format (no embedding needed). In this coding, each URL is represented with a vector containing for each distinct character in the training set its frequency in the URL--we tested both relative and absolute frequency, with no significant differences in the classifiers' performance. The extracted vectors are positional, in the sense each distinct character is assigned a fixed position in the vector. This way, addresses are coded with vector of dimension $79$. We point out that other potential URL codings are applicable, which however are beyond the scope of this study, since URL coding is the same for all classifiers (except for RNN), and the aim is to evaluate the role of classifiers in this learned data structure.
    \item \textit{Hardware}. The experiments were run on a Intel Core i5-8250U 1.60GHz Ubuntu machine with 16GB RAM.
\end{itemize}

\subsection{Evaluation Framework}
\subsubsection{Classifiers screening}
Intuition suggests that the better a  classifier is at discriminating benign from malicious URLs, the better the performance of the Learned Bloom Filter using it. Nevertheless, the space occupied by the classifier plays a central role, and the trade-off performance/space is to be taken into account.

In order to shed quantitative  light on this aspect, we perform classification experiments involving the URLs and the classifiers, without the filter.

\begin{itemize}
    \item \textit{Classifier validation}. Classifiers' generalization capabilities have been evaluated through a $5$-fold cross validation on the whole dataset, and the performance assessed in terms of Accuracy, $F1$ measures, and  space occupied. The latter includes the space of both classifier structure and input encoding, stored as a standard in Python via the serialization method {\tt dump} of library \textit{Pickle}~\cite{Pickle}. The results averaged across folds are calculated. In order to have a binary prediction necessary to compute Accuracy and $F1$, in this experiment the best threshold $\tau$ is estimated on the training set to maximize the $F1$.

    \item \textit{Classifier model selection}. The best performing hyperparameter configuration  for each classifier (see Section~\ref{sub:classif}) is selected through a $5$-fold (inner) cross validation on the training set. In order to directly assess the trade-off Accuracy/Space, the key hyperparameters of the RNN and FFNN classifiers have been preset to $k=\{4, 8, 16\}$ (as done in~\cite{ma2020}), and $h=\{8, 16, 64\}$.

\end{itemize}
\subsubsection{Learned Bloom Filters}
Following~\cite{ma2020}, both typologies of learned Bloom Filters have been validated in the following holdout setting. The training regards the construction of the Bloom Filter on the malicious URLs, which follows a standard approach, but it must also account for the training of the classifier embedded in the filter.  Such a task is performed using  half of the   benign URL uniformly selected (in addition to the malicious ones), whereas the rest of benign URLs constitutes the holdout set used to compute the filter performance.
\paragraph{Evaluation.} The filters have been also evaluated in terms of space, including both classifiers and auxiliary Bloom Filters space, and reject time. To this end, as baseline, the space and reject time of the classic Bloom Filter is also reported. As suggested in~\cite{Mitz18}, we tuned $\tau$ to achieve classifier false positive rates $\epsilon_{\tau}$ that are within the bounds required, and the performance of the filter evaluated for different admissible values of $\epsilon_{\tau}$ (see Section~\ref{sub:BFs}).

\begin{table}[t]
    \centering
\scriptsize
\begin{tabular}{|l|c|c|r|}
    \hline
    {\footnotesize     \textbf{Classifier} }&  {\footnotesize\textbf{Accuracy}} & {\footnotesize\textbf{F1} }& {\footnotesize\textbf{Space (Kb)} }\\
    \hline

    NB & $0.909 \pm 0.009$    & $0.522 \pm 0.003$  & $3.40$ \\
    SVM &  $0.929  \pm 0.001$  & $0.673 \pm 0.003$  &  $1.56$\\
    LR &  $0.930 \pm 0.001$  & $0.672  \pm  0.003$ & $ 1.61$\\
    RNN-16 & $0.935 \pm 0.003$ & $0.751 \pm 0.010$ & $ 9.45$ \\
    RNN-8 & $0.925 \pm 0.002$ & $0.733 \pm 0.005$ & $ 6.39$  \\
    RNN-4 & $0.916 \pm 0.009$ & $0.677 \pm 0.035$ & $ 5.51$  \\
    FFNN-64 & $0.962 \pm 0.001$ & $0.846 \pm 0.002$ & $ 21.80$ \\
    FFNN-16 & $0.952 \pm 0.001$ & $0.812 \pm 0.002$ & $ 5.63$ \\
    FFNN-8 & $0.946 \pm 0.001$ & $0.789 \pm 0.003$ & $ 2.94$  \\
    \hline
\end{tabular}
\caption{Cross validation performance of the compared classifiers. For each measure also the standard deviation across folds is shown.}
\label{tab:classPerf}
\end{table}
\normalsize
 \begin{table}[t]
   \scriptsize
    \centering
    \begin{tabular}{|l|c|c|c|c|}
    \hline
    {\small \textbf{$\epsilon$}} & 0.001 & 0.005 & 0.01 & 0.02\\[3pt]
    {\small \textbf{Space}} & $76.8$ & $58.9$ & $51.2$ & $43.5$ \\[3pt]
    {\small \textbf{Time}} & $1.22\cdot 10^{-6}$ & $1.03 \cdot 10^{-6}$ & $1.02 \cdot 10^{-6}$ & $1.00 \cdot 10^{-6}$ \\
    \hline
    \end{tabular}
    \caption{Size (in Kb) and average reject time (in sec.) of Bloom Filters storing malicious URLs by varying the false positive rate $\epsilon$.}\label{tab:BFsize}
\end{table}
\normalsize
\subsection{Results}
\subsubsection{Results of classifiers screening}
In Table~\ref{tab:classPerf} we report performance comparison of the adopted classifiers when trained on the whole dataset.
FFNNs and RNNs achieve Accuracy and $F1$ values higher that the other competitors, with the former being preferable w.r.t. RNNs from all the standpoints (Accuracy, $F1$ and space/performance trade-off). These two families of classifiers are able to unveil (unlike  NB, SVM and LR) even non linear relationships between input and output, accordingly their superior  results are not surprising. The remaining classifiers are competitive in terms of Accuracy, less in terms of $F1$. Their best feature here is the compactness, being SVM and LR around $1.88\times$ and $13.97\times$ smaller than the smallest ($FFNN$-$8$) and biggest ($FFNN$-$64$)  NN-based models, respectively.
This is a central issue in this setting, because the classifier size contributes to the total space of the learned Bloom Filter using it.
To help this analysis, in Table~\ref{tab:BFsize} the size of the classical Bloom Filter with different desired false positive rates $\epsilon$ is shown. A large classifier, like $FFNN$-$64$, is practically not usable on this dataset, since it occupies, for example when $\epsilon = 0.02$, till half of the space of the filter. For this reason, in the next experiment, evaluating the performance of learned Bloom Filters, the range of values tested for $h$ is set to $\{10, 15, 20, 25, 30\}$.

\begin{table}[t]
\centering
\scriptsize
\begin{tabular}{|lc|c|c|c|}
    \hline
      & \multicolumn{4}{c|}{ {\small \textbf{$\epsilon$} }}\\
      Classifier &     0.001 &     0.005 &     0.010 &     0.020 \\
    \hline
    & \multicolumn{4}{c|}{LBF} \\
    \hline
    NB &  3.12e-6 &  3.24e-6 &  3.01e-6 &  3.37e-6 \\
    SVM &  3.35e-6 &  3.23e-6&  3.43e-6 &  3.58e-6 \\
    LR &  3.77e-6 &  3.84e-6 &  3.95e-6 &  3.98e-6 \\
    RNN &  1.64e-3 &  1.75e-3 &  1.76e-3&  1.77e-3\\
    FFNN &  2.27e-4 &  2.73e-4 &  2.72e-4 & 2.73e-4\\
    \hline
    & \multicolumn{4}{c|}{SLBF}   \\
    \hline
    Bayes & 4.83e-6 &  4.90e-3 &  4.71e-6 &  5.03e-6 \\
    SVM &  4.32e-6 &  4.58e-6&  4.41e-6 &  4.59e-6 \\
    LR &  4.47e-6 &  4.64e-6&  4.35e-6 &  4.68e-6 \\
    RNN &  1.57e-3 &  1.71e-3 &  1.71e-3&  1.72e-3 \\
    FFNN &  2.70e-4 &  2.64e-4 &  2.63e-4 & 2.65e-4\\
    \hline
\end{tabular}
\caption{Average reject time in seconds for one query of the different learned Bloom Filters.}\label{tab:time}
\end{table}
\subsubsection{Results of Bloom Filters comparison}
Figure~\ref{fig:LFB_SLBF} depicts overall filter size when employing different classifiers and when varying both $\epsilon$ and $\frac{\epsilon_{\tau}}{\epsilon}$. Having the classifiers FFNN and RNN different choices for the performance/space trade-off, depending on the configuration of their key hyperparameters, here the one leading to the smallest learned filter has been reported. Specifically, $k=16$ and $h=20$.

A first relevant emerging trend is that the choice of $\epsilon_{\tau}$ is critical to determine the best gain in space. In the case of LBFs, for small $\epsilon$ values  (first two columns), the best compression corresponds to low values of $\frac{\epsilon_{\tau}}{\epsilon}$, suggesting that the classifier precision (lower number of false positives) is more relevant when we aim at constructing LBFs with small false positive rates. Indeed, the filter size grows with $\frac{\epsilon_{\tau}}{\epsilon}$. On the other side, this means that when smaller $\epsilon$ values are required, the best choice is to rely more on the backup filter to guarantee a false positive rate $\epsilon$ (a classifier having a low $\epsilon_{\tau}$ produces more false negatives). Only the FFNN-based LBF with $\epsilon = 0.005$ already shows a trend observed also for larger $\epsilon$ values (last two columns), where for most LBFs the overall space decreases till a certain value of $\frac{\epsilon_{\tau}}{\epsilon}$ is attained, then it starts to increase. This means that the classifier plays a more crucial role in this cases, as confirmed by the higher space reduction with respect to the classic Bloom Filter (dashed line).

SLBFs work differently, and it is not intuitive to understand the reason of such a difference. We attempt to provide here some potential clues in this direction. A first and main difference, except for filters relying on NB and LR, for which the best $\epsilon_{\tau}$ is always the lowest one (probably due to the poor performance of NB and LR), is that now for smaller $\epsilon$ values the classifiers are allowed to produce more false positives, and conversely for larger choices of $\epsilon$.  Exactly as opposite to what happens for the LBFs. A possible explanation resides in the role of the initial Bloom Filter of the SLBF. Filtering out a portion of negatives allows the classifier to produce less false positives, thus fostering a different tuning of $\tau$. A second relevant difference with LBFs is the higher stability in terms of space with respect to the choice of $\tau$, which confirms the analyses in~\cite{Mitz18}. Overall, SLBFs tend to achieve larger size reduction than LBFs, mainly for smaller values of $\epsilon$, as a confirm of previous theoretical~\cite{Mitz18} and empirical~\cite{Dai} results.

Regarding the impact of individual classifiers on the overall size, in most cases the filter using a FFNN compresses the most with respect to the classic Bloom Filter, in accordance with the results shown in Table~\ref{tab:classPerf}; however, the SVM is very competitive, mainly when embedded in the SLBF, being almost indistinguishable with FFNN in terms of space gain. Another surprising result is for the LBFs with $\epsilon = 0.001$, where the NB allows the best space reduction. Such results are even more meaningful if we consider the reject times shown in Table~\ref{tab:time}: the filters built using SVMs and NB are two orders of magnitude faster than those using FFNNs.
Thus, what is counterintuitive is that
non-linear or complex is not necessarily better than linear and simple when we are declining the characteristics of a classifier to be employed in a learned Bloom Filter. It is likely such results are tied to the size of key set, being higher the potential gain of a learned version vs.\ its classic counterpart when the number of keys increases~\cite{Dai,ma2020}. This is left to future investigations.
\begin{figure*}[t]
    \centering
    \includegraphics[width=0.99\textwidth]{figs/LBF_total_size.png}\\
    \includegraphics[width=\textwidth]{figs/SLBF_total_size.png}\\
    \caption{Size of LBF (first row) and SLBF (second row) for different classifier false positive rate. Dashed line is the size of the corresponding Bloom Filter. From the left, figures refer to a desired false positive rate $\epsilon$ of 0.001, 0.005, 0.01, 0.02.}
    \label{fig:LFB_SLBF}
\end{figure*}

\section{\uppercase{Conclusions and Future Developments}}
\label{sec:conclusion}
We have preliminarily investigated the impact of general purpose classifiers within recently proposed extension of Bloom Filters, named learned Bloom Filters. Following~\cite{Mitz18}, which emphasized how these learned extensions are dependent on the data distribution,  we have conducted an empirical evaluation in the context of malicious URLs detection, considering a wide range of general purpose classifiers.  Previous works on learned Bloom Filters have not focused on the appropriate choice of the classifier, and simply relied on non-linear models. Our results have confirmed the suitability of such classifiers, but also have affirmed that simpler classifiers (e.g., linear) might be the best choice in some specific contexts, especially when the reject time is also a key factor.
Future works in this directions would extend and further validate the learned Bloom Filters on different application domains, e.g. Genomics, Cyber security, Web networking, and test the obtained results against problems with different key set sizes and distributions, thus allowing to unveil further insights into the role played by the classifiers, possibly including even those  discarded in this paper for their excessive space occupancy. Finally, the adoption of succinct representations of the trained classifiers, e.g. Neural Networks~\cite{NNcompress,SHAM,RRPR21}, might sensibly contribute to reduce the size of a learned filter.
\vfill
\section*{\uppercase{Acknowledgements}}

\xblackout{This work has been supported by the Italian MUR PRIN project ``Multicriteria data structures and algorithms: from compressed to learned
indexes, and beyond'' (Prot. 2017WR7SHH). Additional support to R.G. has been granted by Project INdAM - GNCS  ``Analysis and Processing of Big Data based on Graph Models''.}

\bibliographystyle{apalike}
{\small