\section{Introduction}

Chinese text error correction plays an important role in many NLP related scenarios~\citep{martins2004spelling,afli2016using,wang2018hybrid,burstein1999automated}. For Chinese native speakers, the common errors include mistaken characters, missing characters, and redundant characters. Mistaken characters type means the sentence contains wrong characters and we should replace them with the right ones. Missing characters type means short of characters in the sentence and the way to correct it is inserting characters in the position identified. Redundant characters type refers to the situation when useless or repeated characters exist and thus need to be deleted. For mistaken characters type, the sentence length keeps the same before and after correction, while for the other two types, the length changes. If texts only contain mistaken errors, we call it a text-aligned situation; if there exist missing or redundant errors besides mistaken errors, we call it a text non-aligned situation. Most methods proposed for Chinese error correction can only tackle text-aligned situation for now.

For text-aligned situation, many approaches apply the detect-correct framework, which is to detect the positions of wrong characters first and then correct them~\citep{hong2019faspell,zhang2020spelling}. Although this kind of methods have achieved competitive results, they cannot deal with text non-aligned situation with missing and redundant errors. For text non-aligned situation, the two mainstream schemes are Seq2Seq-based and sequence tagging-based. The former borrows ideas from machine translation by setting wrong sentences as input and correct sentences as output~\citep{zhao2019improving,kaneko2020encoder,chollampatt2019cross,zhao2020maskgec,lichtarge2019corpora,ge2018reaching,junczys2018approaching}. This kind of approaches requires a large number of training data and may generate uncontrollable results~\citep{kiyono2019empirical,koehn2017six}. The latter is based on sequence tagging by taking wrong sentences as input and the modification operation of each token as output~\citep{awasthi2019parallel,malmi2019encode,omelianchuk2020gector}. However, since Chinese language has more than 20 thousand characters which can generate lots of combinations with token operation labels, it is difficult for the sequence tagging models to cover all the combinations and generate results with high coverage rates.

To address the above issues, we propose an alignment-agnostic detect-correct model, which can handle text non-aligned errors compared to the current detect-correct methods, and can also relieve the problem of huge value space search leading to uncontrollable or low coveraged results of the Seq2Seq or Sequence tagging based methods.

We conduct experiments to compare our alignment-agnostic model with other models by utilizing three datasets: CGED 2020, SIGHAN 2015, SIGHAN-synthesize. Experimental results show
that alignment-agnostic model preforms better than other models.

The contributions of our work include (1) proposal of a novel detect-correct architecture for Chinese text error correction, (2) empirical verification of the effectiveness of the alignment-agnostic model, (3) easy reproduction and fast adaptation to practical scenario with limited annotation data.

\section{Our Approach}
\subsection{Problem Description}
Chinese text error correction can be formalized as the following task. Given a sequence of $n$ characters $X=(x_1,x_2,x_3,...,x_n)$ , the goal is to transform it into another sequence of $m$ characters $Y=(y_1,y_2,y_3,...,y_m)$, where $n$ and $m$ can be equal or not. The task can be viewed as a sequence transform problem with a mapping function $f:X \rightarrow Y$

\begin{figure}[h]
\includegraphics[width=0.4\textwidth]{./figure1.pdf}
\caption{Architecture of alignment-agnostic model}
\label{figure1}
\end{figure}

\subsection{Model}
Our alignment-agnostic model is illustrated in Figure \ref{figure1}. The basic structure is composed of a detection network evolved from ELECTRA’s discriminator~\citep{clark2020electra} and a correction network based on BERT MLM~\citep{devlin2018bert}. The two networks are connected through a modification logic unit and are trained separately. The detection network is responsible for locating the errors and identifying error types. The modification logic unit denotes where and how to correct. And the correction network focuses on correction.

\textbf{The detection network} is composed of
a ELECTRA’s discriminator and a token-level error type classifier. The ELECTRA’s discriminator’s architecture has been described in \citet{clark2020electra}. The error type classifier contains four categories, namely $label_{keep}$, $label_{mistaken}$, $label_{missing}$, $label_{redundant}$. $label_{keep}$ means the character is correct and we should keep it unchanged. $label_{mistaken}$ indicates the character is mistaken and we should replace it. $label_{missing}$ denotes we should insert characters before the current character. $label_{redundant}$ means the character is useless and we should delete it. We get the label probability of each token with the 4-class token-level classifier:
\begin{equation}
    P_{i,label}(z_i=k|X)=softmax(w^Th^D(X))
\end{equation}
Where $P_{i,label}(z_i=k|X)$ denotes the conditional
probability of character $x_i$ being tagged with the label of $k$, $h^D(X)$ is the last hidden state of ELECTRA’s discriminator and $k$ is in [$label_{keep}$, $label_{mistaken}$, $label_{missing}$, $label_{redundant}$]. The loss function
of the detection network is:
\begin{equation}
    Loss_{detect}=-\sum_{i=1}^{n}\log{p_{i,label}}
\end{equation}

\textbf{The modification logic unit} rewrites the input sequence $X$ according to detection network’s output $Z$:
\begin{equation}
if z_i=\left\{
\begin{aligned}
& label_{keep}, \; x_{i}^{'}=x_i \\
& label_{mistaken}, \; x_{i}^{'}=[MASK] \\
& label_{missing}, \; x_{i}^{'} = [MASK] \; x_i \\
& label_{redundant}, \; x_{i}^{'} =  ''
\end{aligned}
\right.
\end{equation}
We get a new sequence $X^{'}=(x_{1}^{'}, x_{2}^{'}, x_{3}^{'},..., x_{n}^{'},)$ based on the above formula. For each token with empty characters $''$, we delete it directly from the sequence $X^{'}$, For each token with $'[MASK] \; x_i'$, we reorder it as two characters and obtain the final modified sequence $Y^{'}=(y_{1}^{'}, y_{2}^{'}, y_{3}^{'},..., y_{m}^{'},)$, whose length might be different from $X^{'}$.

\begin{center}
\begin{table*}[!h]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\textbf{Test Set}} & \multirow{2}{*}{\textbf{Method}} & \multicolumn{3}{c|}{\textbf{Detection}} & \multicolumn{3}{c|}{\textbf{Correction}}\\
\cline{3-8}
~ & ~ & Prec. & Rec. & $F_1$. & Prec. & Rec. & $F_1$.\\
\hline
\multirow{5}{*}{SIGHAN 2015} & Hybrid~\citep{wang2018hybrid} & 56.6 & 69.4 & 62.3 & - & - & 57.1 \\
\cline{2-8}
~ & FASpell~\citep{hong2019faspell} & 67.6 & 60 & 63.5 & 66.6 & 59.1 & 62.6 \\
\cline{2-8}
~ & Confusionset~\citep{wang2018hybrid} & 66.8 & 73.1 & 69.8 & 71.5 & 59.5 & 64.9 \\
\cline{2-8}
~ & Soft-Masked BERT(2020) & \textbf{73.7} & \textbf{73.2} & \textbf{73.5} & 66.7 & \textbf{66.2} & 66.4 \\
\cline{2-8}
~ & our model & 79.1 & 64.0 & 71.3 & \textbf{72.2} & 60.6 & \textbf{68.2} \\
\hline
\end{tabular}
\caption{\label{table1} Performances of Different Methods on SIGHAN 2015. }
\end{table*}
\end{center}
\vspace{-1.5em}
\textbf{The correction network} is BERT. We do the prediction for positions with the $[MASK]$ symbol on the sequence $Y^{'}$.

\section{Experiments}
\subsection{Datasets and Metrics}
Chinese text error correction tasks mainly have two public datasets: the benchmark of SIGHAN 2015~\citep{tseng2015introduction} which just contains text-aligned data and the competition of CGED 2020~\citep{cged2020} which contains text non-aligned data. In order to better verify the models’ effect on text non-aligned scenario, we synthesized some non-aligned data based on SIGHAN 2015 dataset. Next, we will introduce how to utilize the three datasets.

For SIGHAN 2015 dataset, since the use of extra resources is allowed in SIGHAN competitions, we incorporated SIGHAN 2013 and 2014 datasets in the training phase, and incorporated SIGHAN 2013 confusion set, in order to keep accordance with other methods in comparison. The test set contains 1100 passages and the train set contains 8738 passages. We used the evaluation tool provided by SIGHAN, with metrics of precision (Prec.), recall(Rec.) and $F_1$, all are based on sentence level.

CGED 2020 contains an additional error type besides three error types mentioned. That is the reversed order. As this type happens less frequent in Chinese text writing scenario, and is beyond the scope of our model setting, we remove 575 relevant samples from a total sample of 2586, and get 846 training samples and 1165 testing samples.

To better verify our model’s effect on text non-aligned scenario, we synthesized some non-aligned data based on SIGHAN 2015 dataset (SIGHAN-synthesized). For mistaken characters error type, we kept the original errors unchanged. For missing characters error type, we randomly selected 50\% samples and deleted one character from each of them. For redundant characters error type, we randomly selected 50\% samples and inserted characters in each of them through four ways. (1) We inserted repeated characters in 35\% of the selected samples. (2) We inserted confusing characters in 30\% of the selected samples. (3) We inserted characters from high-frequency words in 30\% of the selected samples. (4) We also inserted random characters in 5\% of the selected samples.

For both CGED 2020 dataset and SIGHAN-synthesized dataset, we used the $M^2$ score~\citep{dahlmeier2012better} and ERRANT~\citep{bryant2017automatic} to evaluate models’ performance, which are the two commonly adopted evaluation tools for English text non-aligned situations.

\subsection{Experiment Settings}
The pre-trained ELECTRA discriminator model and BERT model adopted in our experiments are all from \url{https://github.com/huggingface/transformers}. We utilize the large size for ELECTRA and the base size for BERT. We train detection network and correction network on the three datasets respectively by Adam optimizer with default hyperparameters. All the experiments are conducted on 2 GPUs (Nvidia Tesla P100).

For SIGHAN 2015, we kept the default binary classifier of ELECTRA’s discriminator because the dataset just contains one error type when fine tuning ELECTRA’s discriminator. And in retraining of BERT, we applied two kinds of ways. One is an unsupervised method by re-pretraining BERT with its original MLM objective. The other is a supervised method by masking the mistaken characters and predicting them.
\begin{center}
\begin{table*}[htbp]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\textbf{Test Set}} & \multirow{2}{*}{\textbf{Method}} & \multicolumn{3}{c|}{\textbf{\bm{$M_2$}(Correction)}} & \multicolumn{3}{c|}{\textbf{ERRANT(Correction)}}\\
\cline{3-8}
~ & ~ & Prec. & Rec. & $F_{0.5}$. & Prec. & Rec. & $F_{0.5}$.\\
\hline
\multirow{4}{*}{CGED 2020} & Copy-augmented(2019) & 4.62 & 0.8 & 2.36 & 3.51 & 0.56 & 1.7\\
\cline{2-8}
~ & Lasertagger(2019) & 14.99 & 3.48 & 9.02 & 12.95 & 2.61 & 7.22 \\
\cline{2-8}
~ & PIE(2019) & 22.3 & 10 & 17.9 & 17.1 & 6.6 & 13 \\
\cline{2-8}
~ & our model & \textbf{29.71} & \textbf{22.03} & \textbf{27.77} & \textbf{24.8} & \textbf{17.56} & \textbf{22.91} \\
\hline
\multirow{4}{*}{SIGHAN-synthesized} & Copy-augmented(2019) & 38.44 & 8.03 & 21.87 & 38.31 & 7.8 & 21.5 \\
\cline{2-8}
~ & Lasertagger(2019) & 51.29 & 43.21 & 49.44 & 50.14 & 39.99 & 47.72 \\
\cline{2-8}
~ & PIE(2019) & 54.1 & 47.6 & 52.6 & 52 & 42.6 & 49.8 \\
\cline{2-8}
~ & our model & \textbf{59.3} & \textbf{62.2} & \textbf{59.8} & \textbf{56.9} & \textbf{57.8} & \textbf{57} \\
\hline
\end{tabular}
\caption{\label{table2} The $M^2$ score and ERRANT score of Different Methods on CGED 2020 and SIGHAN-synthesized. }
\end{table*}
\end{center}

\begin{center}
\begin{table*}[htbp]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
\multirow{2}{*}{\textbf{Method}} & \textbf{SIGHAN 2015} & \textbf{CGED 2020} & \textbf{SIGHAN-synthesized} \\
\cline{2-4}
~ & $F_1$ & $F_{0.5}$ & $F_{0.5}$ \\
\hline
ELECTRA+BERT & 38.7 & - & - \\
\hline
Finetune ELECTRA+BERT & 66.2 & 22.91 & 54.7 \\
\hline
Finetune ELECTRA+Finetune BERT & 68.2 & 22.54 & 54.4 \\
\hline
Finetune ELECTRA+Pretrain BERT & 42 & 22.6 & 57 \\
\hline
\end{tabular}
\caption{\label{table3} Ablation study of alignment-agnostic model on three datasets. }
\end{table*}
\end{center}
\vspace{-3.2em}
\quad For CGED 2020 and SIGHAN-synthesized datasets, we added a 4-class classifier to recognize three error types on ELECTRA’s discriminator’s last hidden layer and then fine tune it. As in retraining of BERT, we applied the same ways with SIGHAN 2015.

\subsection{Results}
Table~\ref{table1} shows the results in comparison on SIGHAN 2015 dataset. From the table we can see that our method outperforms the previous SOTA method Soft-Masked BERT~\citep{zhang2020spelling} by 1.8\% on $F_1$ score in correction phase.

Table~\ref{table2} compares the results of our model with other SOTA models on  CGED 2020 dataset and SIGHAN-synthesized dataset. Our model performs the best on correction level by exceeding the second best model 9.87 points for CGED 2020 and 7.2 points for SIGHAN-synthesized dataset on $F_{0.5} M^{2}$ score. Copy-augmented~\citep{zhao2019improving} is a Seq2Seq model which requires a large number of training data to achieve an acceptable result. That’s why it performs poorer than Lasertagger~\citep{malmi2019encode} and PIE~\citep{awasthi2019parallel} models on both two datasets with a relative small amount of training samples. Lasertagger and PIE are sequence tagging based models. As we analyzed before, this kind of models doesn’t work well on Chinese language due to huge value space search.

\subsection{Ablation Study}
We carried out ablation study of our model on the three datasets. Table~\ref{table3} shows the results on correction level. For SIGHAN 2015, We can see that finetuning ELECTRA can produce great improvement of 27.5\% on $F_1$ score, while finetuning BERT generates a relatively small improvement of 2\% on $F_1$ score and pretraining BERT leads to a negative effect of -24.2\% on $F_1$ score. Possible reason is that finetuning can help BERT learn the knowledge about confusion set of characters that prone to be mistaken, while pretraining is unsupervised and may destroy the original learned words distribution when training data is quite different from the original training data. Besides, our model can get 38.7\% on $F_1$ score without any training data, which means it can work as a strong baseline in cold start conditions. For CGED 2020 and SIGHAN-synthesized datasets, two ways of retraining BERT didn’t improve much. Compared with the results of other SOTA models, the transformation of ELECTRA is the most effective part.

\section{Conclusion}
We proposed a new detect-correct model for Chinese text error correction tasks, which can handle both text-aligned and non-aligned situations, and can serve as a strong baseline even in cold start situations. Our model firstly locates the errors and identifies error types, and then corrects the sentence with a MLM. Experimental results on three datasets show that our model performs better than existing methods. Furthermore, it is easy to reproduce and can achieve good results with a small amount of training data, which is the key for rapid application to the industry.

\newpage

\input{acl2021.bbl}
\bibliographystyle{acl_natbib}

\end{document}


\section{Introduction}
Recently, dialogue systems have achieved significant improvement in many areas thanks to the plethora of publicly available conversational data and the rapid advance of deep learning techniques~\cite{GaoGL19,gao2021advances,lei2020conversational}.  One of the critical challenges to enhancing the systems is generating more human-like conversation~\cite{lei2018sequicity,poria2019emotion,serban2016building}.  Hence, a system should perceive users' emotion states and express the content in an empathetic manner, e.g., by selecting suitable responses from the database or automatically generating human-like responses~\cite{DBLP:journals/tois/HuangZG20,DBLP:journals/inffus/MaNXC20}.

\begin{figure}[t]
  \label{introduction}
  \centering
  \includegraphics[width=1\columnwidth]{introduction}
  \caption{An example of conversations with emotion dynamics \label{fig:ex}}
\end{figure}

In the literature, Emotion Recognition in Conversation (ERC) is a sub-field of emotion recognition and aims to automatically identify human emotions in conversational scenarios~\cite{abdul2017emonet,poria2019emotion}. A critical task in this field is to model emotion dynamics in conversation~\cite{hazarika2018conversational}.  The emotion dynamics explain the conversational emotion behaviors from two dependencies, i.e., the inter-interlocutor dependency and intra-interlocutor dependency.   In a dialogue, the \textbf{inter}-interlocutor dependency describes the emotional influence \textbf{among} different interlocutors.  That is, one interlocutor tries to coerce other interlocutors changing their emotions~\cite{morris2000emotions}.  For example, as illustrated in Fig.~\ref{fig:ex}, Person B's emotion at timestamp 6 changes from \textit{Neutral} to \textit{Fear} due to the consecutive impact of Person A's strong emotion of \textit{Surprise} at timestamp 3 and 5.  Meanwhile, the \textbf{intra}-interlocutor dependency describes the emotional inertia \textbf{within} individual interlocutors.  That is, one interlocutor tries to resist the change of their own emotion against external influence~\cite{kuppens2010emotional}.  For instance, in Fig.~\ref{fig:ex}, though Person A has changed the emotion to \textit{Surprise} at timestamp 3, Person B remains the original emotion of \textit{Neutral}.

To model emotion dynamics in conversation, researchers have explored various methods based on the Recurrent Neural Networks (RNNs)~\cite{DBLP:conf/naacl/JiaoYKL19,ghosal-etal-2019-dialoguegcn,hazarika2018icon,DBLP:conf/aaai/JiaoLK20,li2020bieru,majumder2019dialoguernn,poria2017context}.  Some studies have adopted the flat structured Recurrent Neural Networks (RNNs), i.e., concatenating utterances of different interlocutors in a single sequence, for context modeling~\cite{li2020bieru,poria2017context}.  Meanwhile, other studies have established variants of hierarchically structured RNNs for context modeling~\cite{DBLP:conf/naacl/JiaoYKL19,ghosal-etal-2019-dialoguegcn,hazarika2018icon,DBLP:conf/aaai/JiaoLK20,majumder2019dialoguernn}, e.g., lining up a sequence of features extracted from a sub-sequence of utterances spoken by the same interlocutor.  However, existing approaches contain the following limitations: (1) the flat structure cannot distinguish the interlocutors because they are blended in the same sequence during temporal modeling; (2) the hierarchical structure cannot distinguish the emotional influence among interlocutors because it applies a flat structure on the extracted sub-sequence features; (3) RNNs can hardly fulfill the power of pre-training language models on large-scale data~\cite{peters2017semi,peters2018ELMo} than recently-developed Transformer-based models~\cite{liu2019roberta,vaswani2017attention,lei2021have}, e.g., BERT~\cite{devlin2019bert}.

In this paper, we propose a series of BERT-based models to tackle the above challenges.  More specifically, we apply a Flat-structured BERT (F-BERT) to directly link up utterances in a conversation and extend the structure to a Hierarchically-structured BERT  (H-BERT) to distinguish different interlocutors in a conversation.  Both F-BERT and H-BERT can facilitate the power of BERT and can learn better representations by fulfilling pre-training strategies than RNN counterparts.  More importantly, we propose a Spatial-Temporal-structured BERT, namely ST-BERT, to further distinguish emotional influence among interlocutors by first independently capturing the intra-interlocutor and inter-interlocutor emotional influence and then unifying those emotional influence via fusion strategies.

We highlight the contributions of our work as follows:
\begin{itemize}
\item We develop a series of BERT-based models to explore the potential of applying Transformer-based pre-training models to capture the inter-interlocutor and intra-interlocutor dependencies of the conversational emotion dynamics.
\item We propose two basic models, F-BERT and H-BERT, as the baselines of their RNN counterparts to exploit the effect of BERT with pre-training strategies.  More importantly, we develop ST-BERT to overcome the weakness of existing work in distinguishing the emotional influence among interlocutors when modeling the emotion dynamics.
\item We conduct extensive experiments on two ERC benchmark datasets to illustrate the effectiveness of our proposed models and observe that we attain  averaged accuracy of about 5\% and 10\% improvement on IEMOCAP and MELD, respectively, over the state-of-the-art (SOTA) baselines.
\end{itemize}

\section{Related Work}

Emotions are hidden mental states associated with human thoughts and feelings~\cite{poria2019emotion}.  Emotion recognition is an interdisciplinary field that spans psychology, cognitive science, machine learning, and natural language processing~\cite{picard2010affective}. The aim is to identify correct emotions from multi-modal expressions~\cite{tsai2019multimodal,tsai2019learning,tzirakis2017end,wang2015constructing}.

\textbf{Emotion recognition in conversation} (ERC) is to predict the emotion in conversational scenarios. Rather than treating emotions as static states, ERC involves emotion dynamics in a conversation.  By comparing with the recent proposed ERC approaches~\cite{hsu2018emotionlines,majumder2019dialoguernn}, Poria et al.~\cite{poria2019emotion} discover that traditional emotion recognition methods~\cite{colneric2018emotion,kratzwald2018decision,mohammad2010emotions,shaheen2014emotion} fail to perform well because the same utterance within different context may exhibit different emotions.  Mao et al.~\cite{mao2020dialoguetrm} indicate that emotion expressions in different modalities exhibit different dependence on conversational context, where emotion dynamics mainly affect emotion expressions in textual modality.  Recently, various methods have been proposed to tackle ERC in the natural language processing community.  For example, the bi-directional Long Short-Term Memory (LSTM)~\cite{poria2017context} has been applied to capture the intra-interlocutor dependency.  The intra-interlocutor and inter-interlocutor dependencies between dyadic interlocutors have been distinguished by leveraging the hierarchical Gated Recurrent Unit (GRU) and memory networks~\cite{hazarika2018icon,hazarika2018conversational}.  Multiple GRUs with global attention mechanism have been designed and further developed in multi-party ERC~\cite{majumder2019dialoguernn}.  Graph Convolutional Networks (GCNs) have also been employed to mine complex interactions between interlocutors~\cite{ghosal-etal-2019-dialoguegcn,zhang2020generalized}.  GRU-based attention gated hierarchical memory networks have been proposed for ERC~\cite{DBLP:conf/aaai/JiaoLK20}.  However, these methods are mainly based on RNNs and do not sufficiently distinguish the emotional influence among interlocutors.

\textbf{Transformer-based pre-training language models} have applied the Transformer architecture~\cite{vaswani2017attention} to promote language understanding by a two-staged training strategy, i.e., a self-supervised pre-training on a general-domain text corpus and a fine-tune training on the downstream application data.  Pioneers~\cite{peters2017semi,peters2018ELMo} conduct pre-training on bi-directional RNNs to obtain the contextualized representation of each token.  However, RNN-based models are inefficient for long-term modeling and have limited lifting power when stacking more layers due to the limitation of the recurrent connections.  Recently, due to the power of parallel computation and deep-model construction, Transformer-based models, e.g., GPT~\cite{radford2019language}, BERT~\cite{devlin2019bert}, and ELECTRA~\cite{Clark2020ELECTRA}, have been deployed and achieved the SOTA performance in many downstream NLP applications.  Several pieces of work, e.g., transfer learning ERC~\cite{hazarika2019emotion}, utterance-level dialogue understanding~\cite{ghosal2020utterance}, and contextualized emotion sequence tagging~\cite{wang2020contextualized}, have employed pre-training models as a feature extractor in the task of ERC.  However, the potential of the Transformer-based models is less explored and does not address the problem of modeling emotion dynamics yet.

\section{Task Definition}
\label{sec:tf}
We first define the task of utterance-level emotion recognition in conversation.
\begin{definition}[Emotion Recognition in Conversation]
Let $\mathcal{D}=\{\mathcal{D}_i|i\in[1,N]\}$ be a corpus of $N$ conversations, where $\mathcal{D}_i=\{(u^{\lambda_\tau}_\tau, y_\tau)|\tau\in[1,{L_i}],\lambda_\tau\in[1,S]\}$ is the $i$-th conversation consisting of a sequence of $L_i$ utterances.   $u^{\lambda_\tau}_\tau=w_1\cdots w_{T_\tau}$ is the $\tau$-th utterance of $T_\tau$ words spoken by the ${\lambda_\tau}$-th interlocutor from one of the total $S$ interlocutors. The corresponding emotion type is $y_\tau\in\mathcal{Y}$, where the emotion set $\mathcal{Y}$ consists of all emotions, such as anger, joy, and neutral. The goal is to train a model that can tag each utterance in a new conversation with a emotion label as accurately as possible.
\end{definition}

In our work, we aim to capture emotion dynamics in conversations and need the following preliminary notions:
\begin{definition}[Contexts\footnote{In this paper, the notion of context denotes the preceding utterances of the target in a conversation.} in Conversation]
Let $u^{\lambda_i}_i$ be the target utterance in a conversation session
$U=\{ u^{\lambda_\tau}_\tau|\tau\in[1,L],{\lambda_\tau}\in[1,S] \}$. According to the interlocutors that are involved, we define three types of context utterances within a sliding window of $K$ as follows:
\begin{compactitem}
\item {\bf intra-context:} the preceding utterances of the $i$-th utterance from the interlocutor $\lambda_i$ in $U$ within the window size of $K$:
\[
\varphi(u^{\lambda_i}_i,U,K)=\{u^{\lambda_\tau}_\tau|\tau\in[\max(i-K, 1), i),{\lambda_\tau}= \lambda_i\},
\]
\item {\bf inter-context:} the preceding utterances of the $i$-th utterance from the interlocutors, except $\lambda_i$, in $U$ within the window size of $K$:
\[
\phi(u^{\lambda_i}_i,U,K)=\{u^{\lambda_\tau}_\tau|\tau\in[\max(i-K, 1), i),{\lambda_\tau}\neq \lambda_i\}
\]
\item {\bf conv-context:} the preceding utterances of the $i$-th utterance in $U$ within the window size of $K$:
\[
\psi(u^{\lambda_i}_i,U,K)=\{u^{\lambda_\tau}_\tau|\tau\in[\max\{i-K,1\},i),{\lambda_\tau}\in [1,S]\}.
\]
\end{compactitem}
\end{definition}

Table~\ref{tab:example} presents an example of the three types of contexts in a conversation.

\begin{table}[h]
\scriptsize
\centering
  \caption{An example of context utterances in a conversation when $L=8$, $S=3$, and $K=5$.
  }
  \small
  \label{tab:example}
  \begin{tabular}{p{3cm}|p{4cm}}
    \toprule
    conversation                       & $U= u^1_1\, u^2_2\,u^1_3\,u^1_4\,u^3_5\,u^2_6\,u^1_7\,u^2_8$\\
    \midrule
    target utterance                   & $u^1_7$\\
    \midrule
    intra-context                      & $\varphi(u^1_7,U,5)=u^1_3\,u^1_4$\\
    \midrule
    inter-context                      & $\phi(u^1_7,U,5)=u^2_2\,u^3_5\,u^2_6$\\
    \midrule
    conv-context                       & $\psi(u^1_7,U,5)=u^2_2\,u^1_3\,u^1_4\,u^3_5\,u^2_6$\\
    \bottomrule
  \end{tabular}
\end{table}

\section{BERT}
\begin{figure}[h]
  \centering
  \includegraphics[width=1\columnwidth]{transformer}
  \caption{Architecture of the temporally unfolded Transformer blocks\label{fig:TB}}
\end{figure}
BERT is a powerful Transform-based language model and performs exceptionally well in many downstream NLP tasks~\cite{devlin2019bert}.  A standard BERT model consists of a stack of $L$ identical Transformer blocks expanding in a sequence mode as illustrated in Fig.~\ref{fig:TB} to naturally exploit the temporal information.  Each Transformer block consists of two sublayers, i.e., a multi-head self-attention sublayer and a position-wise fully connected feed-forward sublayer.  Residual connection with layer normalization is employed on each of the two sublayers to avoid the problem of gradient vanishing in training.  The final output is then computed by $\mbox{LayerNorm}(x + \mbox{Sublayer}(x))$, where $\mbox{Sublayer}(x)$ is one of the above mentioned sublayers~\cite{vaswani2017attention}.  In the following, we briefly elucidate the three main layers in BERT.

\textit{Embedding layer:} given utterance-context pairs, BERT has 5 key operations in dealing with the input pairs: (1) packing the utterance and its context into a sequence of tokens by WordPiece tokenization; (2) adding $[\mbox{CLS}]$ as the classification token at the head of a sequence; (3) adding the special token $[\mbox{SEP}]$ and token type embeddings to differentiate the utterance and its context; (4) applying WordPiece embeddings~\cite{WuSCLNMKCGMKSJL16} on the tokens; (5) adding position embeddings to maintain the order information in a sequence.

\textit{Multi-head attention sublayer:} the output of embedding layer is fed to the multi-head self-attention sublayer (the orange blocks in Fig.~\ref{fig:TB}) to model temporal dependency.  A multi-head attention independently applies attention mechanism $H$ times along with the query $Q\in\mathbb{R}^{d_k}$, key $K\in\mathbb{R}^{d_k}$, and value $V\in\mathbb{R}^{d_v}$, respectively, and concatenates them together:
\begin{align}
& \mbox{MultiHead}(Q, K, V) = \mbox{Concat}(head_1,...,head_H)W^O,\\\nonumber
& head_h = \mbox{Attention}(QW_h^Q, KW_h^K, VW_h^V), \\\nonumber
&\qquad~~ = \mbox{softmax}(\frac{QW_h^Q(KW_h^K)^T}{\sqrt[]{d_k}})VW_h^V,~~ h=1,\ldots, H,
\end{align}
where $\frac{1}{\sqrt{d_k}}$ is a scaling factor to avoid pushing the softmax function into small gradients regions when $d_k$ is large~\cite{vaswani2017attention}.  $head_h$ is the $h$-th output of attention operation.  $W_h^Q\in\mathbb{R}^{d_{model}\times d_k}, W_h^K\in\mathbb{R}^{d_{model}\times d_k}, W_h^V\in\mathbb{R}^{d_{model}\times d_v},W^O\in\mathbb{R}^{Hd_v\times d_{model}}$ are the weights of the projection matrices for computing the $h$-th attention operations.  Practically, we set the dimension $d_k=d_v=d_{model}/H$.
\if 0
\begin{align}
head_h &= \mbox{Attention}(QW_h^Q, KW_h^K, VW_h^V)\\
       &= \mbox{softmax}(\frac{QW_h^Q(KW_h^K)^T}{\sqrt[]{d_k}})VW_h^V
\end{align}
\fi

\textit{Fully connected feed-forward sublayer:} after applying the multi-head attention, a two-layer fully connected feed-forward network is computed by a RELU on the hidden state:
\begin{equation}
    \max(0, xW_1 + b_1)W_2 + b_2,
\end{equation}
where $x$ is the output from the multi-head attention sublayer, $W_1\in\mathbb{R}^{d_{model}\times d_{hidden}}$, $W_2\in\mathbb{R}^{d_{hidden}\times d_{model}}$, and $b_1\in\mathbb{R}^{d_{hidden}}$, $b_2\in\mathbb{R}^{d_{model}}$ are the projection matrices and biases for the fully-connected networks, respectively.

\section{Our Proposal}
In the following, we present our proposed series of BERT-based models.
\subsection{F-BERT}
{The Flat-structured BERT (F-BERT), as illustrated in Fig.~\ref{fs}, is to directly {concatenate} the target utterance with the conv-context while applying BERT afterwards.} The input is a sequence of utterance-context pair, i.e., the {target utterance} of $T$ sub-words, $u^{\lambda_i}_i=w_1\cdots w_{T}$, and the  {conv-context} of $\mathcal{T}_\psi$ sub-words, $\psi(u^{\lambda_i}_i, U, K)=\omega_1\cdots \omega_{\mathcal{T}_\psi}$. We pack the pairs into a sequence of tokens:
\begin{equation}
X_i=  [\mbox{CLS}]\,u^{\lambda_i}_i\,[\mbox{SEP}]\,\psi(u^{\lambda_i}_i, U, K)\,[\mbox{SEP}].
\end{equation}
Hence, $X_i$ includes the information of the target utterance with the conversation context, but does not distinguish the identity of interlocutors.

After pre-processing, $X_i$ is fed to BERT and represented by the last hidden layer at the $[\mbox{CLS}]$ token, denoted by
\begin{equation}
r_i=\mbox{BERT}(X_i),
\end{equation}
where $r_i$ is the output representation of $u^{\lambda_i}_i$ for emotional predictions.

\begin{figure}[t]
  \centering
  \subfigure[Flat Structure]{\includegraphics[width=0.31\columnwidth]{model_a}\label{fs}}
  \subfigure[{Hierarchical Structure}]{\includegraphics[width=0.645\columnwidth]{model_b}\label{hs}}
  \subfigure[{Spatial-Temporal Structure}]{\includegraphics[width=1\columnwidth]{model_c}\label{sts} }
  \caption{Architecture of the proposed BERT-based models given inputs of table~\ref{introduction}}
\end{figure}

\subsection{H-BERT}
\label{sec:HS}

{The Hierarchically-structured BERT (H-BERT), as illustrated in Fig.~\ref{hs}, first applies BERT to wrap up an utterance with its intra-context to capture the intra-interlocutor dependency as the branch feature.  Next, it lines up the branch features in conversational order by the backbone Transformer to produce the final output representation.}  More specifically, the input of a branch BERT is a sequence of utterance-context pair, i.e., the target utterance of $T$ sub-words, $u^{\lambda_i}_i=w_1\cdots w_T$, and the intra-context of $\mathcal{T}_\varphi$ sub-words, $\varphi(u^{\lambda_i}_i,U,K)=\omega_1\cdots \omega_{\mathcal{T}_\varphi}$. After packing, we compute the input sequence by
\begin{equation}
X^{\lambda_i}_i =  [\mbox{CLS}]\,u^{\lambda_i}_i\,[\mbox{SEP}]\,\varphi(u^{\lambda_i}_i,U,K)\,[\mbox{SEP}].
\end{equation}
Thus, $X^{\lambda_i}_i$ includes the information of the target utterance with historical utterances only spoken by the target interlocutor. By feeding $X^{\lambda_i}_i$ to BERT, we obtain
\begin{equation}
f^{\lambda_i}_i=\mbox{BERT}(X^{\lambda_i}_i),
\end{equation}
we can obtain $f^{\lambda_i}_i$, the intra-interlocutor dependency of the $\lambda_i$-th interlocutor, which maintains the $i$-th emotion influence in a conversation.

{Let $F=f^{\lambda_1}_1\cdots f^{\lambda_L}_L$ be the sequence of the branch features of the entire conversation. The input of the backbone Transformer is a sliding window of $K+1$ in $F$:
\begin{equation}
F_i =f^{\lambda_{i-K}}_{i-K}\cdots f^{\lambda_{i-1}}_{i-1}f^{\lambda_i}_i.
\end{equation}
where $f^{\lambda_i}_i$ is the target feature at the last position.  $f^{\lambda_{i-K}}_{i-K}\cdots f^{\lambda_{i-1}}_{i-1}$ are the preceding $K$ features that may produce emotional influence to the target.  $F_i$ is fed to the backbone Transformer and represented by the last hidden layer at the target position.  The computation of the Transformer is
\begin{equation}
r_i=\mbox{Transformer}(F_i),
\end{equation}
where $r_i$ is the representation of $u^{\lambda_i}_i$ conditioned on the temporally wrapped emotion influence for making predictions.}

\subsection{ST-BERT}

The Spatial-Temporal-structured BERT (ST-BERT), as illustrated in Fig.~\ref{sts}, first applies BERT to individually wrap up the inter-context and intra-context of the target utterance as two types of temporally captured emotion influence.  After that, different fusion strategies are applied to combine the two temporally captured emotional influence into a single spatial representation.

\textbf{Temporal Construction.}
Given the target utterance $u^{\lambda_i}_i=w_1\cdots w_T$ of $T$ sub-words, we construct two individual sequences of utterance-context pairs:
\begin{align}
& X^\varphi_i = [\mbox{CLS}]\,u^{\lambda_i}_i\,[\mbox{SEP}]\,\varphi(u^{\lambda_i}_i,U,K)\,[\mbox{SEP}],\\
& X^\phi_i = [\mbox{CLS}]\,u^{\lambda_i}_i\,[\mbox{SEP}]\,\phi(u^{\lambda_i}_i,U,K)\,[\mbox{SEP}],
\end{align}
where $X^\varphi_i$ includes the information, which maintains the emotion inertia of the $\lambda_i$-th interlocutor by incorporating the intra-context $\varphi(u^{\lambda_i}_i,U,K)=\omega^\varphi_1\cdots \omega^\varphi_{\mathcal{T}_\varphi}$. $X^\phi_i$ includes the information, which produces emotional influence from the non-$\lambda_i$ interlocutor by incorporating the inter-context $\phi(u^{\lambda_i}_i,U,K)=\omega^\phi_1\cdots \omega^\phi_{\mathcal{T}_\phi}$. The two types of token sequences are then fed to the BERT,
\begin{equation}
f^\varphi_i=\mbox{BERT}(X^\varphi_i), \quad
f^\phi_i=\mbox{BERT}(X^\phi_i ),
\end{equation}
we can directly and explicitly capture the intra-interlocutor and inter-interlocutor dependencies in $f^\varphi_i\in\mathbb{R}^{d_{model}}$ and $f^\phi_i\in\mathbb{R}^{d_{model}}$, respectively. The two temporally contextualized features are fused vertically in different spatial fusion strategies.

\textbf{Spatial Fusion.}
We explore three types of spatial fusion strategies, including direct concatenation, gate operation, and attention mechanism.

\textit{Direct concatenation} is a simple but effective strategy.  It does not involve interactions between features and can be computed by a fully-connected network:
\begin{equation}
r_i=W^C[f^\varphi_i; f^\phi_i] + b^C,
\end{equation}
where $[\cdot;\cdot]$ is the concatenation. $r_i\in\mathbb{R}^{d_{hidden}}$ is the output representation for emotional predictions. $W^C$ and $b^C$ are the projection matrix and bias, respectively.

\textit{Gate operation} is a neuron-level interactive weighting strategy.  The computation can be formulated as
\begin{align}
& h^\varphi_i=\tanh(W^\varphi f^\varphi_i + b^\varphi),\\
&h^\phi_i=\tanh(W^\phi f^\phi_i + b^\phi),\\
&z_i=\sigma(W^Z [f^\varphi_i; f^\phi_i] + b^Z),\\
&r_i=z_i * h^\varphi_i + (1-z_i)*h^\phi_i,
\end{align}
where $h^\varphi_i\in\mathbb{R}^{d_{hidden}}$ and $h^\phi_i\in\mathbb{R}^{d_{hidden}}$ are the projections of $f^\varphi_i$ and $f^\phi_i$, respectively. $*$ refers to the Hadamard product whose function is to use neurons in one vector to weight the neurons of its counterpart at the same position. Here, $z_i\in\mathbb{R}^{d_{hidden}}$ is to weight neurons in $h^\varphi_i$ and $1-z_i$ is to weight neurons in $h^\phi_i$, where $z_i$ is computed by feature interactions between $f^\varphi_i$ and $f^\phi_i$, $\sigma$ is to maps the $z_i$ to $(0,1)$. Note that the impact of ``$1-z_i$" on $h^\phi_i$ is critical  because it allows to learn the weights of the neurons in $h^\varphi_i$ and $h^\phi_i$ contrastively~\cite{arevalo2020gated}.  $W^\varphi$ and $b^\varphi$, $W^\phi$ and $b^\phi$, and $W^Z$ and $b^Z$, are the corresponding projection matrices and biases, respectively.  $r_i$ is the final output representation.

\textit{Attention mechanism} is a vector-level interactive weighting strategy.  The insight is identical to that of the gate operation. The major difference is that gate operation allocate different weights to neurons in a vector while attention operation allocate the same weight to neurons in a vector.  The attention operation can be computed by
\begin{align}
&\alpha_i=\sigma(\frac{f^\varphi_i (f^\phi_i)^T}{\sqrt{d_{model}}}),\\
\label{eq:ST-BERT-att}
&r_i=\alpha_i * h^\varphi_i + (1-\alpha_i)*h^\phi_i,
\end{align}
where $\frac{1}{\sqrt[]{d_{model}}}$ is the scaling factor. $d_{model}$ is the dimention of  $f^\varphi_i, f^\phi_i$. $\alpha_i$ is the attention weight and a scalar computed by dot-product between $f^\varphi_i$ and $f^\phi_i$.  Again, the operation of ``$1-\alpha_i$" plays a trade-off on the weight for contrastive learning~\cite{cho2014learning}. $r_i$ is the final output representation.

\subsection{Discriminator}
The discriminator is a two-layer perceptron with the hidden layer activated by the $\tanh$ function, which can be trained by minimizing the cross-entropy loss.  Given the representation $r_i$, the discriminator output emotion distributions computed by the softmax function:
\begin{align}
&o_i=\tanh(W^O \cdot r_i),\\
&\mathcal{P}_i=\mbox{softmax}(W^{\mathcal{P}_i}\cdot o_i),\\
&\hat{y}_i=\mathop{\arg \max}\limits_k\mathcal{P}_i[k],
\end{align}
where $\hat{y}_i$ is the predicted emotion. $W^O$ and $W^{\mathcal{P}_i}$ are the corresponding projection matrices.

\section{Experiments}
In this section, we present the experiments with detailed analysis.
\subsection{Datasets}
Two popular ERC datasets, IEMOCAP~\cite{busso2008iemocap} and MELD~\cite{poria2019meld}, are adopted to evaluate our proposed models. Statistics on the two datasets are presented in Table~\ref{fig:stat}.

{IEMOCAP} consists of dyadic conversation videos between pairs of 10 speakers. Each utterance is annotated with one of the six emotion types, including happy, sad, neutral, angry, excited, and frustrated. Following~\cite{majumder2019dialoguernn}, we apply the first four sessions in training and use the last session for test.  The validation conversations are randomly selected from the training set with a ratio of 0.1.

{MELD} consists of multi-party conversation videos collected from the Friends TV series. Each utterance is annotated with one of the seven emotion types, including anger, disgust, sadness, joy, neutral, surprise, and fear. We apply the official splits for training, validation, and test in this dataset.

\begin{table}[htp]
\centering
\caption{Statistics of the two datasets}
\label{fig:stat}
\begin{tabular}{l|P{20pt}|P{20pt}|P{20pt}|P{25pt}|c}
\toprule
\multirow{2}{*}{Dataset} & \multicolumn{3}{c|}{\# Utterances} & \multirow{2}{*}{Classes} & \multirow{2}{*}{Avg. conv. length} \\
                         & train      & val       & test     &                           &                                           \\
\midrule
IEMOCAP                  & 5,663      & 647       & 1,623    & 6                         & 50                                        \\
MELD                     & 9,989      & 1,109     & 2,610    & 7                         & 8                                         \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Implementation Details}
In the experiment, BERT$_{\tiny\mbox{Base}}$ is adopted as the fundamental sequential module, where it consists of 12 Transformer blocks, 12 self-attention heads, and 768 hidden-units.  We employ the off-the-shelf implementation of BERT$_{\tiny\mbox{Base}}$ model in ``\textit{Transformers}"\footnote{https://github.com/huggingface/transformers}. The pre-trained parameters are deployed for initializing BERT. Other parameters are randomly initialized. All the hyperparameters are keeping default. The backbone of the H-BERT is a 6-layer, 12-head-attention, and 768 hidden-unit Transformer encoder implemented using \textit{torch.nn.TransformerEncoder}\footnote{https://pytorch.org/docs/stable/generated/torch.nn.TransformerEncoder.html} in PyTorch. The parameters of the backbone Transformer are randomly initialized. We use AdamW~\cite{loshchilov2018fixing} as the optimizer with the following setup: an initial learning rate of $6e-6$, $\beta_1=0.9$, $\beta_2=0.999$, L2 weight decay of $0.01$, learning rate warms up steps being $0$, and linear decay of the learning rate. All the results are based on an average of 5 runs.

\begin{table*}[htp]
\small
\centering
\begin{threeparttable}
  \caption{Main Results on IEMOCAP and MELD.\label{tab:rs}}
  \begin{tabular}{l|p{16pt}p{16pt}|p{16pt}p{16pt}|p{16pt}p{16pt}|p{16pt}p{16pt}|p{16pt}p{16pt}|p{16pt}p{16pt}|p{16pt}p{16pt}|p{16pt}p{16pt}}
    \toprule
    \multirow{3}{*}{Model} & \multicolumn{14}{c|}{IEMOCAP} & \multicolumn{2}{c}{MELD}\\
    \cline{2-17}
    & \multicolumn{2}{c|}{happy} & \multicolumn{2}{c|}{sad} & \multicolumn{2}{c|}{neutral} & \multicolumn{2}{c|}{angry} & \multicolumn{2}{c|}{excited} & \multicolumn{2}{c|}{frustrated} & \multicolumn{2}{c|}{\textbf{Avg.(w)}} & \multicolumn{2}{c}{\textbf{Avg.(w)}}\\
                 & ACC   & F1    & ACC   & F1    & ACC   & F1    & ACC   & F1    & ACC   & F1    & ACC   & F1    & ACC   & F1 & ACC & F1        \\
    \midrule\midrule
    scLSTM       & 37.5  & 43.4  & 67.7  & 69.8  & 64.2  & 55.8  & 61.9  & 61.8  & 51.8  & 59.3  & 61.3  & 60.2  & 59.2  & 59.1& 57.5  & 55.9 \\
    TL-ERC       & -    & -     & -     & -     & -     & -     & -     & -     & -     & -     & -     & -     & -     & 58.8& -        & -    \\

    DRNN*        & 25.7 & 33.2 & 75.1   & 78.8  & 58.6 & 59.2 & 64.7 & 65.3 & \textbf{80.3} & 71.9 & 61.2 & 59.0 & 63.4  & 62.8& 56.1  & 55.9 \\
    DRNN$\dag$*  & - & - & -   & - & - & - & - & -& - & - & - & - & - & 64.1  & -        & - \\
    DGCN*        & 40.6 & 42.8 & \textbf{89.1}   & \textbf{84.5} & 61.9 & 63.5 & 67.5 & 64.2 & 65.5 & 63.1 & 64.2 & \textbf{67.0} & 65.3 & 64.2  & -        & 58.1 \\

    AGHMN        & 48.3 & \textbf{52.1} & 68.3   & 73.3  & 61.6  & 58.4  & 57.5  & 61.9  & 68.1  & 69.7  & 67.1  & 62.3  & 63.5  & 63.5& 59.5  & 57.5 \\
    CESTa*       & -    & 47.7 & -      & 80.8  & -    & 64.8 & -    & 63.4 & -    & \textbf{76.0} & -   & 62.7 & - & 67.1 & -      & 58.4 \\
    \midrule\midrule
    F-BERT       & \textbf{52.8} & 50.8 & 77.6 & 77.6 & 65.1 & 64.1 & \textbf{71.2} & 61.9 & 65.6 & 69.4 & 58.5 & 61.9 & 65.1 & 65.2 & 63.0 & 62.5\\
    H-BERT       & 30.8 & 33.2 & 68.4 & 73.9 & 69.2 & 68.7 & 66.0 & 59.0 & 70.3 & 70.0 & 65.1  & 64.6 & 65.1 & 65.1 & 63.2 & 62.6\\
    \midrule\midrule
    ST-BERT-ATT  & 37.5 & 41.7 & 80.0 & 77.2 & 72.1 & 66.3 & 54.7 & 57.6 & 63.2 & 68.6 & 64.6 & 64.0 & 65.0 & 64.7 & 64.4 & 62.7 \\
    ST-BERT-CON  & 46.5 & 49.1 &81.2 & 80.4 &\textbf{76.3} & \textbf{68.6}& 61.2 & 62.7 & 68.2 & 71.7& 60.4 & 63.6 & 67.6 & 67.4 & 65.5 & 63.5 \\
    ST-BERT-GAT  & 45.1 & 48.5 & 80.0 & 82.2 & 72.4 & 68.6 & 66.5 & \textbf{65.6} & 66.9 & 69.9 & \textbf{67.2} & 66.6 & \textbf{68.5} & \textbf{68.4} & \textbf{65.7} & \textbf{63.8} \\
    \bottomrule
  \end{tabular}
  \begin{tablenotes}
      \scriptsize
      \item Symbol * indicate that models are fed with succeeding context. DRNN$\dag$*~\cite{ghosal2020utterance} is fed with RoBERTa~\cite{liu2019roberta} features. -ATT, -CON, and -GAT denote the attention, concatenation, and gate mechanism in ST-BERT.
  \end{tablenotes}
\end{threeparttable}
\end{table*}

\subsection{Comparing Methods and Metrics}
We investigate previous ERC methods based only on the textual modality:
\begin{compactitem}
\item {scLSTM}~\cite{poria2017context} is the earliest study that we can track in the task of ERC. It makes predictions by only considering intra-interlocutor dependency.

\item {TL-ERC}~\cite{hazarika2019emotion} applies BERT as a transfer learning module for context modeling. That is, it simply employs BERT as a feature extractor and applies RNN for modeling emotion dynamics in conversation afterwards.

\item {DRNN}~\cite{majumder2019dialoguernn} is DialogueRNN, a hierarchical attention-based model with three GRUs to capture the emotion dynamics.  In the experiment, we compare both DRNN with the CNN and DRNN with the RoBERTa features~\cite{liu2019roberta,ghosal2020utterance}, denoted by DRNN$\dag$.

\item {DGCN}~\cite{ghosal-etal-2019-dialoguegcn} applies GCN to model utterance interactions among interlocutors by considering speaker positions in the historical conversation.

\item {AGHMN}~\cite{DBLP:conf/aaai/JiaoLK20} finetunes sentence representation and uses GRU to wrap the attention-weighted representations rather than summing them up.

\item {CESTa}~\cite{wang2020contextualized} is the SOTA ERC method.  It first applies a flat Transformer at the bottom layer to obtain contextualized representation for each utterance in the conversation.  Next, it cascades a hierarchical LSTM upon the Transformer to distinguish contextualized representations of interlocutors.
\end{compactitem}

Following~\cite{ghosal-etal-2019-dialoguegcn,majumder2019dialoguernn}, we use the weighted accuracy (ACC)  and weighted average F1 (F1) as the evaluation metrics:
\begin{align}
    \mbox{ACC} = \sum_{c=1}^{|\mathcal{C}|}p_c\cdot a_c,\quad
    \mbox{F1} &= \sum_{c=1}^{|\mathcal{C}|}p_c\cdot \mbox{F1}_c,
\end{align}
where $p_c$ is the percentage of the class $c$ in the testing set, $a_c$ and $F1_c$ are the corresponding accuracy and F1 score for the class $c$, respectively.  It is worth mentioning that we mainly focus on the average scores because all the methods have trade-off among individual emotion types.
\subsection{Main Results}
Table~\ref{tab:rs} reports the main results.  We can observe that
\begin{compactitem}[--]
\item The Transformer-based models, i.e., {CESTa} and our proposed models, achieve better performance than RNN-based models on IEMOCAP.  Notice that, the results of F-BERT and H-BERT are competitive.  By observing the average conversation length on IEMOCAP is 50, we can note that Transformer-based models can effectively capture information for long sentences.
\item The average ACC and F1 of our {ST-BERT-GAT} significantly ($p<0.05$ in $t$-test) outperforms the SOTA baselines and attains 5\% and 2\% improvement on IEMOCAP in terms of ACC and F1 metrics, respectively, while achieving 10\% and 8\% improvement on MELD in terms of ACC and F1, respectively.  By examining more details, we notice that
\begin{compactitem}
\item ST-BERT outperforms {TL-ERC} (applying BERT), {DRNN$\dag$} (using the RoBERTa features), and {CESTa} (applying Transformer), which exhibits the superiority of our model structure rather than simply using the pre-training models.
\item ST-BERT also outperforms models using the succeeding context, i.e., {DRNN}, {DRNN$\dag$}, {DGCN}, and {CESTa}.  This implies that our model is more practical in real conversations.
\end{compactitem}
\item ST-BERT also attains the best scores in many individual emotion types, especially ``neutral".  The type of ``neutral" is hard to distinguish because the ``neutral" utterances often contain emotional words.  For example, the word ``excited" colored in blue of Table~\ref{tab:case} may mislead the recognition.  On the contrary, if the model can distinguish the emotional influence among interlocutors, it could easily discover the ``frustrated" emotion from the single word utterance ``Yeah." because most of the time, the emotions of ``frustrated" and ``excited" do not appear simultaneously in a conversation.  The ST-BERT can distinguish the emotional influence through independent temporal modeling and different types of fusion.
\item By comparing different fusion mechanisms in ST-BERT, we notice that the gate mechanism outperforms others.  Surprisingly, the attention mechanism performs worse than the one by direct concatenation.  We conjecture that the linear combination may not  sufficient absorb the two representations defined in Eq.~(\ref{eq:ST-BERT-att}).  Though the attention mechanism in the Transformer can learn the complex interactions between interlocutors, the hierarchical structure does not provide more information gain than the Flat structure.
\end{compactitem}

\begin{table}[htp]
\small
\centering
  \caption{Ablation study on IEMOCAP.}
  \label{tab:ab}
  \begin{tabular}{cccc|c}
    \toprule
    target & intra-context & inter-context & pre-train & Avg.(w) F1 \\
    \midrule
    $\surd$       & $\times$      & $\times$      & $\times$  & 49.2    \\
    $\surd$       & $\surd$       & $\times$      & $\times$  & 56.2    \\
    $\surd$       & $\times$      & $\surd$       & $\times$  & 55.5    \\
    $\surd$       & $\surd$       & $\surd$       & $\times$  & 60.8    \\
    \midrule
    $\surd$       & $\times$      & $\times$     & $\surd$   & 55.6    \\
    $\surd$       & $\surd$       & $\times$     & $\surd$   & 63.5    \\
    $\surd$       & $\times$      & $\surd$      & $\surd$   & 61.5    \\
    $\surd$       & $\surd$       & $\surd$      & $\surd$   & 68.4    \\
    \bottomrule
\end{tabular}
\end{table}

\subsection{Ablation Study}
Table~\ref{tab:ab} shows the ablation study on IEMOCAP to test the effect of the components in ST-BERT, including target utterance, intra-context, inter-context, and pre-training.  The first four cases are based on BERT without pre-training, i.e., randomly initializing the parameters. The first case is to test the vanilla BERT$_{\tiny\mbox{Base}}$ without including any context information. The following three cases are to test ST-BERT with intra-context, ST-BERT with inter-context, and ST-BERT with both intra-context and inter-context, respectively.  Similarly, the last four cases are to test the above four cases by the pre-training BERT$_{\tiny\mbox{Base}}$ initialization.  The average F1 scores reported in Table~\ref{tab:ab} clearly show that
\begin{compactitem}
\item Without pre-training, our ST-BERT performs even worse than some baselines in Table~\ref{tab:rs}.  We conjecture that because IEMOCAP is a small dataset, the deep structure of BERT cannot be well-trained in this dataset.
\item Though the models perform poorly when applying randomly initialization, our ST-BERT still beats {TL-ERC} (applying pre-trained BERT). This implies that ST-BERT indeed sufficiently capture emotion dynamics to improve the model performance.
\item When we apply pre-trained BERT on our models, we can obtain significant improvement in all four compared cases. Especially, in ST-BERT, we attain 68.4 F1 score and outperforms {DRNN$\dag$*}, which has applied more advanced pre-training techniques, e.g., RoBERTa.  By comparing other cases, we observe that by including intra-context, more gains can be obtained than by including inter-context.
\end{compactitem}

\begin{figure}[htp]
  \centering
  \subfigure[{BERT$_{\tiny\mbox{Base}}$}] {
  \label{bs_rs}
  \includegraphics[width=0.445\columnwidth]{BS_CM.png}
  }
  \subfigure[F-BERT] {
  \label{fs_rs}
  \includegraphics[width=0.445\columnwidth]{FS_CM.png}
  }
  \subfigure[{H-BERT}]{
    \label{hs_rs}
  \includegraphics[width=0.445\columnwidth]{HS_CM.png}
  }
  \subfigure[{ST-BERT}]{
    \label{sts_rs}
  \includegraphics[width=0.445\columnwidth]{ST_CM.png}
  }
  \caption{Heat map of confusion matrix of four BERT-based models.\label{fig:cm}}
\end{figure}

\subsection{Case Study}
We depict the confusion matrices in the form of heat maps to better understand our proposed BERT-based models. The confusion matrices are based on the results of BERT$_{\tiny\mbox{Base}}$, F-BERT, H-BERT, and ST-BERT on IEMOCAP as shown in Fig.~\ref{fig:cm}.  Notice that the types of ``happy", ``excited", and ``neutral" comprise more  easy-to-confuse cases in the positive emotion group while the types of ``sad", ``angry", ``frustrated", and ``neutral"  comprises more easy-to-confuse cases in the negative emotion group.  The ``neutral" type belongs to both groups and is thus particularly hard for recognition.  However, our proposed F-BERT, H-BERT, and ST-BERT perform better than BERT$_{\tiny\mbox{Base}}$ in recognizing ``neutral".  By comparing Fig.~\ref{hs_rs} and Fig.~\ref{sts_rs}, we can notice that ST-BERT exhibits more power in distinguishing the negative emotions and obtain higher performance.

Table~\ref{tab:case} illustrates a conversation snippet classified by our proposed BERT-based models. There are two challenges in predicting the four utterances.  One is to predict the emotion of a short utterance at the second turn.  The other is to predict the emotion of an utterance with the misleading word ``excited" at the fourth turn.  The results show that ST-BERT correctly predicts the emotion in all four  utterances.  H-BERT cannot distinguish the emotion when there is a misleading word.  Meanwhile, F-BERT fails in predicting both cases.

\begin{table}[htp]
\small
\centering
\caption{A conversation snippet classified by F-BERT (F), H-BERT (H), and ST-BERT (ST). GT stands for ground truth of the emotion types in neutral (Neu.), frustrated (Fru.), and excited (Exc.) .  \label{tab:case}}
\begin{tabular}{|m{6pt}|m{0.7cm}|m{3.4cm}|m{8pt}m{8pt}m{8pt}m{12pt}|}
\hline
&&&&&&\\[-1ex]
 &  A &  B & GT & F  & H    & ST    \\[1.25ex]
\hline\hline
&&&&&&\\[-1.25ex]
\#1    &                        & There's like mystery here, there's magic. It's like a little bit of the unexplainable. I just can't see how you're not interested.                    & Neu.     & Neu. & Neu.    & Neu.    \\[3.5ex]
\hline\hline
&&&&&&\\[-0.75ex]
\#2  & Yeah.                  &                                                                                & Fru.   & \red{Neu.} & Fru. & Fru. \\[1.75ex]
\hline\hline
&&&&&&\\[-1.25ex]
\#3  &                        & God, I don't get it. you know the first time we came here, you said it was the best night of your life?                                               & Neu.     & Neu. & Neu.    & Neu.    \\[3.5ex]
\hline\hline
&&&&&&\\[-1.25ex]
\#4  &                        & And last year, I remember distinctly you said, you were so \blue{excited} to get here that you don't remember you stubbed your toe until we were in the car. & Neu.      & \red{Exc.} & \red{Exc.}    & Neu.    \\[4.5ex]
\hline
\end{tabular}
\end{table}

\section{Conclusion}
In this paper, we develop a series of BERT-based models to model emotion dynamics in conversation.  Two basics, a flat-structured and a hierarchically-structured BERT, are proposed to model the preceding utterance information and the direct dependencies in intra-interlocutors and inter-interlocutors.  More importantly, a  spatial-temporal-structured BERT is proposed to specifically distinguish emotional influence among interlocutors, so that we can effectively capture the emotion dynamics.  We conduct extensive experiments on two popular ERC datasets and demonstrate that our proposed BERT-based models can significantly outperform the SOTA baselines.  Detailed ablation study and case study have provided to verify our observations.

\bibliographystyle{plain}


\subsection{Case Study}

COIL differs from all previous embedding-based models in that it does not use a single unified embedding space. Instead, for a specific token, COIL learns an embedding space
to encode and measure the semantic similarity of the token in different contexts.
In this section, we show examples where COIL differentiates different senses of a word under different contexts.
In \autoref{tab:analysis}, we show how the token similarity scores differ across contexts in relevant and irrelevant query document pairs.

The first query looks for ``cabinet'' in the context of ``govt'' (abbreviation for ``government''). The two documents both include query token "cabinet" but of a different concept. The first one refers to the government cabinet and the second to a case or cupboard. COIL  manages to match ``cabinet'' in the query to ``cabinet''  in the first document with a much higher score. In the second query, "pass" in both documents refer to the concept of permission. However, through contextualization, COIL captures the variation of the same concept and assigns a higher score to ``pass'' in the first document.

Stop words like ``it'', ``a'', and ``the'' are commonly removed in classic exact match IR  systems as they are not informative on their own. In the third query, on the other hand, we observe that COIL is able to differentiate ``is''  in an explanatory sentence  and ``is'' in a passive form, assigning the first higher score to match query context.

All examples here show that COIL can go beyond matching token surface form and introduce rich context information to estimate matching. Differences in similarity scores across mentions under different contexts demonstrate how COIL systems gain strength over lexical systems.
\section{Appendix}
\label{sec:appendix}
\subsection{Index Building Illustration}
The following figure demonstrates how the document "apple pie baked ..." is indexed by COIL. The document is first processed by a fine-tuned deep LM to produce for each token a contextualized vector. The vectors of each term "apple" and "juice" are collected to the corresponding inverted list index along with the document id for lookup.
\begin{figure*}[h]
    \centering
    \includegraphics[width=0.8\textwidth]{figs-index/indexing.pdf}
    \caption{COIL Index Building of document "apple pie baked..."}
    \label{fig:index-build}
\end{figure*}

\newpage
\subsection{Search Illustration}
The following figure demonstrates how the query "apple juice" is processed by COIL. Contextualized vectors of each term "apple" and "juice" go to the corresponding inverted list index consisting of a lookup id array and a matrix stacked from document term vectors. For each index, a \emph{matrix vector product} is run to produce an array of scores. Afterwards a \emph{max-scatter} of scores followed by a \emph{sort} produces the final ranking. Note for each index, we show only operations for a subset of vectors~(3 vectors) in the index matrix.
\begin{figure*}[h]
    \centering
    \includegraphics[width=\textwidth]{figs-index/query.pdf}
    \caption{COIL Search of query "apple juice".}
    \label{fig:index-search}
\end{figure*}
\section{Related Work}

\paragraph{Lexical Retriever} Classical IR systems rely on exact lexical match retrievers such as Boolean Retrieval, BM25~\cite{bm25} and statistical language models~\cite{lafferty2001document}.
This type of retrieval model can process
queries very quickly by organizing the documents into inverted index, where each distinct term has an inverted list that
stores information about documents it appears in. Nowadays, they are still widely used in production systems.
However, these retrieval models fall short of matching related terms (vocabulary mismatch) or modeling context of the terms (semantic mismatch). Much early effort was put into improving exact lexical match retrievers, such as matching n-grams~\cite{metzler2005markov} or expanding queries with terms from related documents~\cite{Lavrenko2001RelevanceBasedLM}. However, these methods still use BOW framework and have limited capability of modeling human languages.

\paragraph{Neural Ranker} In order to deal with vocabulary mismatch, neural retrievers that rely on soft matching between numerical text representations are introduced. Early attempts compute similarity between pre-trained word embedding such as word2vec~\cite{w2v} and GLoVe~\cite{glove} to produce matching score~\cite{ganguly2015word, diazquery}. One more recent approach encodes query and document each into a vector and computes vector similarity~\cite{dssm}. Later researches realized the limited capacity of a single vector to encode fine-grained information and introduced full interaction models to perform soft matching between all term vectors~\cite{DRMM,KNRM}. In these approaches, scoring is based on learned neural networks and the hugely increased computation cost limited their use to reranking a top candidate list generated by a lexical retriever.

\paragraph{Deep LM Based Ranker and Retriever} Deep LM made a huge impact on neural IR. Fine-tuned Transformer~\cite{transformer} LM BERT~\cite{BERT} achieved state-of-the-art reranking performance for passages and documents~\cite{Nogueira2019PassageRW, DBLP:conf/sigir/DaiC19}. As illustrated in \autoref{fig:cross-attn-model}, the common approach is to feed the concatenated query document text through BERT
and use BERT’s [CLS] output token to produce a
relevance score.
The deep LM rerankers addressed both vocabulary and semantic mismatch by computing full cross attention between contextualized token representations.
Lighter deep LM rankers are developed~\cite{MacAvaney2020EfficientDR,MORES}, but their cross attention operations are still too expensive for full-collection retrieval.

Later research therefore resorted to augmenting lexical retrieval with deep LMs by expanding the document surface form to narrow the vocabulary gap, e.g., DocT5Query~\cite{docTTTTTquery}, or altering term weights to emphasize important terms, e.g., DeepCT~\cite{DeepCT}. Smartly combining deep LM retriever and reranker can offer additive gain for end performance~\cite{LCE}. These retrievers however still suffer from vocabulary and semantic mismatch as traditional lexical retrievers.

Another line of research continues the work on single vector representation and build dense retrievers, as illustrated in \autoref{fig:dense-model}. They store document vectors in a dense index and retrieve them through Nearest Neighbours search. Using deep LMs, dense retrievers have achieved promising results on several retrieval tasks~\cite{DPR}. Later researches show that dense retrieval systems can be further improved by better training~\cite{ANCE, CLEAR}.

Single vector systems have also been extended to multi-vector representation systems. Poly-encoder~\cite{Humeau2020PolyencodersAA} encodes queries into a set of vectors. Similarly, Me-BERT~\cite{Luan2020SparseDA} represents documents with a set of vectors. A concurrent work ColBERT (\autoref{fig:late-model}) use multiple vectors to encode both queries and documents~\cite{ColBERT}. In particular, it represents a documents with all its terms' vectors and a query with an expanded set of term vectors. It then computes all-to-all~(Cartesian) soft match between the tokens. ColBERT performs interaction as dot product followed pooling operations, which allows it to also leverage a dense index to do full corpus retrieval. However,  since ColBERT encodes a document with all tokens, it adds another order of magnitude of index complexity to all aforementioned methods: document tokens in the collection need to be stored in a \emph{single} huge index and considered at query time. Consequently, ColBERT is engineering and hardware demanding.

\section{Conclusion and Future Work}
Exact lexical match systems have been widely used for decades in classical IR systems and prove to be effective and efficient.
In this paper, we point out a critical problem, semantic mismatch, that generally limits all IR systems based on surface token for matching.
To fix semantic mismatch, we introduce contextualized exact match to differentiate the same token in different contexts, providing  effective semantic-aware token match signals.
We further propose contextualized inverted list~(COIL) search index which swaps token statistics in inverted lists with contextualized vector representations to perform effective search.

On two large-scale ad hoc retrieval benchmarks, we find COIL substantially improves lexical retrieval and outperforms state-of-the-art dense retrieval systems.
These results indicate large headroom of the simple-but-efficient exact lexical match scheme.   When the introduction of contextualization handles the issue of semantic mismatch, exact match system gains the capability of modeling complicated matching patterns that were not captured by classical systems.

Vocabulary mismatch in COIL can also be largely mitigated with a high-level CLS vector matching. The full system performs on par with more expensive and complex all-to-all match retrievers.
The success of the full system also shows that dense retrieval and COIL's exact token matching give complementary effects, with COIL making up dense system's lost token level matching signals and dense solving the vocabulary mismatch probably for COIL.

With our COIL systems showing viable search latency, we believe this paper makes a solid step towards building next-generation index that stores semantics. At the intersection of lexical and neural systems,
efficient algorithms proposed for both can push COIL towards real-world systems.
\section{Experiment Methodologies}
\label{sec: exp-method}

\paragraph{Datasets}
We experiment with two large scale ad hoc retrieval benchmarks from the TREC 2019 Deep Learning (DL) shared task: MSMARCO passage~(8M English passages of average length around 60 tokens) and MSMARCO document~(3M English documents of average length around 900 tokens)\footnote{Both datasets can be downloaded from \url{https://microsoft.github.io/msmarco/}}. For each, we train models with the MSMARCO Train queries, and record results on MSMARCO Dev queries and TREC DL 2019 test queries.  We report mainly full-corpus retrieval results but also include the rerank task on MSMARCO Dev queries where we use neural scores to reorder BM25 retrieval results provided by MSMARO organizers. Official metrics include MRR@1K and NDCG@10 on test and MRR@10 on MSMARCO Dev. We also report recall for the dev queries following prior work~\cite{DeepCT, docTTTTTquery}.

\begin{table*}[t]
\caption{MSMARCO passage collection results. Results not applicable are denoted `--' and no available `n.a.'.}
\centering
\renewcommand{\arraystretch}{0.9}
\begin{tabular}{ l || c | c c | c c}
\hline \hline
 & \multicolumn{4}{c}{MS MARCO Passage Ranking}\\
\hline
 & Dev Rerank & \multicolumn{2}{c|}{Dev Retrieval} & \multicolumn{2}{c}{ DL2019 Retrieval} \\

Model & MRR@10 & MRR@10 & Recall@1K & NDCG@10 & MRR@1K  \\
\hline
\textbf{Lexical Retriever} & & & & & \\
BM25  & -- &  0.184	& 0.853 & 0.506 & 0.825 \\
DeepCT & -- & 0.243 & 0.909 & 0.572  & 0.883 \\
DocT5Query & -- & 0.278 & 0.945 & 0.642 & 0.888  \\
BM25+BERT reranker  & 0.347 &  --	& -- & -- &  --  \\

\hline
\textbf{Dense Retriever} & & & & & \\

Dense (BM25 neg) & n.a. & 0.299 & 0.928 & 0.600 & n.a.\\
Dense (rand + BM25 neg) & n.a.  & 0.311 & 0.952 & 0.576 & n.a.\\
Dense (our train) & 0.312 & 0.304 & 0.932 & 0.635 & 0.898  \\
\hline
ColBERT & 0.349 &  0.360 & 0.968 & n.a. & n.a.\\
\hline
COIL-tok & 0.336 & 0.341 & 0.949 & 0.660 & 0.915 \\
COIL-full & 0.348 & 0.355 & 0.963 & 0.704 & 0.924 \\

\hline \hline
\end{tabular}
\label{tab:perf-marco-psg}
\end{table*}

\begin{table*}[t]
\caption{MSMARCO document collection results. Results not applicable are denoted `--' and no available `n.a.'.}
\centering
\renewcommand{\arraystretch}{0.9}
\begin{tabular}{ l || c | c c | c c}
\hline \hline
 & \multicolumn{4}{c}{MS MARCO Document Ranking}\\
\hline
 & Dev Rerank & \multicolumn{2}{c|}{Dev Retrieval} & \multicolumn{2}{c}{ DL2019 Retrieval} \\

Model & MRR@10 & MRR@10 & Recall@1K & NDCG@10 & MRR@1K  \\
\hline
\textbf{Lexical Retriever} & & & & & \\
BM25  & -- &  0.230	& 0.886 & 0.519 &  0.805  \\
DeepCT & -- & 0.320 & 0.942 & 0.544 & 0.891 \\
DocT5Query & -- & 0.288 & 0.926 & 0.597 & 0.837 \\
BM25+BERT reranker  & 0.383 &  --	& -- & -- &  --  \\

\hline
\textbf{Dense Retriever} & & & & & \\
Dense (BM25 neg) & n.a. & 0.299 & 0.928 & 0.600 & n.a. \\
Dense (rand + BM25 neg) & n.a. & 0.311 & 0.952 & 0.576 & n.a. \\
Dense (our train) & 0.358 & 0.340 & 0.883 & 0.546 & 0.785  \\
\hline
COIL-tok & 0.381 & 0.385 & 0.952 & 0.626 & 0.921 \\
COIL-full & 0.388 & 0.397 & 0.962 & 0.636 & 0.913 \\
\hline \hline
\end{tabular}
\label{tab:perf-marco-doc}
\end{table*}

\begin{table*}[t]
\caption{Performance and latency of COIL systems with different representation dimensions. Results not applicable are denoted `--' and no available `n.a.'. Here $n_c$ denotes COIL CLS dimension and $n_t$ token vector dimension. *: ColBERT use approximate search and quantization. We exclude I/O time from measurements.}
\centering
\renewcommand{\arraystretch}{0.9}
\begin{tabular}{ c  c | c c | c c | c c }
\hline\hline
&  & \multicolumn{2}{c|}{Dev Retrieval} & \multicolumn{2}{c|}{ DL2019 Retrieval} & \multicolumn{2}{c}{Latency/ms}  \\

\multicolumn{2}{l|}{Model} & MRR@10 & Recall@1K & NDCG@10 & MRR & CPU & GPU  \\
\hline
\multicolumn{2}{l|}{BM25} & 0.184 & 0.853 & 0.506 & 0.825 & 36 & n.a. \\
\multicolumn{2}{l|}{Dense} & 0.304 & 0.932 & 0.635 & 0.898 & 293 & 32 \\
\multicolumn{2}{l|}{ColBERT} & 0.360 & 0.968 & n.a. & n.a. & 458* & -- \\
\hline
\multicolumn{2}{l|}{COIL} & & & &\\
$n_c$ & $n_t$ & & & & &\\
768 & 32 & 0.355 & 0.963 & 0.704 & 0.924 & 380 & 41 \\
128 & 32 &0.350 & 0.953 & 0.692 & 0.956 & 125 & 23\\
128 & 8 & 0.347 & 0.956 & 0.694 & 0.977 & 113 & 21 \\

0 & 32 & 0.341 & 0.949 & 0.660 & 0.915 & 67 & 18 \\
0 & 8 & 0.336 & 0.940 & 0.678 & 0.953 & 55 & 16 \\

\hline \hline
\end{tabular}
\label{tab:dimension}
\end{table*}

\paragraph{Compared Systems}
Baselines include 1) traditional exact match system BM25, 2) deep LM augmented BM25 systems DeepCT~\cite{DeepCT} and DocT5Query~\cite{docTTTTTquery},  3) dense retrievers, and 4)  soft all-to-all retriever ColBERT.  For DeepCT and DocT5Query, we use the rankings provided by the authors. For dense retrievers, we report two dense retrievers trained with BM25 negatives or with mixed BM25 and random negatives, published in \citet{ANCE}.  However since these systems use a robust version of BERT, RoBERTa~\cite{RoBERTa} as the LM and train document retriever also on MSMARCO passage set, we in addition reproduce a third dense retriever, that uses the exact same training setup as COIL. All dense retrievers use 768 dimension embedding. For ColBERT, we report its published results (available only on passage collection). BERT reranker is added in the rerank task.

We include 2 COIL systems: 1) COIL-tok, the exact token match only system, and 2) COLL-full, the model with both token match and CLS match.

\paragraph{Implementation}
We build our models with Pytorch~\cite{pytorch} based on huggingface transformers~\cite{hf-transformers}. COIL's LM is based on BERT's base variant. COIL systems use token dimension $n_t=32$ and COIL-full use CLS dimension $n_c=768$ as default, leading to 110M parameters. We add a Layer Normalization to CLS vector when useful.
All models are trained for 5 epochs with AdamW optimizer, a learning rate of 3e-6, 0.1 warm-up ratio, and linear learning rate decay, which takes around 12 hours. Hard negatives are sampled from top 1000 BM25 results. Each query uses 1 positive and 7 hard negatives; each  batch uses 8 queries on MSMARCO passage  and  4 on MSMARCO document. Documents are truncated to the first 512 tokens to fit in BERT.  We conduct validation on randomly selected 512 queries from corresponding train set. Latency numbers are measured on dual Xeon E5-2630 v3 for CPU and RTX 2080 ti for GPU.
We implement COIL's inverted lists as matrices as described in \autoref{sec:retrive-and-index}, using NumPy~\cite{numpy} on CPU and Pytorch on GPU. We perform a) a set of matrix products to compute token similarities over contextualized inverted lists, b) scatter to map token scores back to documents,
and c) sort to rank the documents. Illustration can be found in the appendix, \autoref{fig:index-search}.

\section{Introduction}
Widely used, bag-of-words~(BOW) information retrieval~(IR) systems such as BM25 rely on exact lexical match~\footnote{Exact match up to morphological changes.} between query and document terms. Recent study in neural IR takes a different approach and compute soft matching between all query and document terms to model complex matching.

The shift to soft matching in neural IR models attempts to address \emph{vocabulary mismatch} problems, that query and the relevant documents use different terms, e.g. cat v.s. kitty, for the same concept~\cite{dssm,DRMM,KNRM}.
Later introduction of contextualized representations~\cite{ELMo} from deep language models~(LM) further address \emph{semantic mismatch}, that the same term can refer to different concepts, e.g., bank of river vs. bank in finance.
Fine-tuned deep LM rerankers produce token representations based on context and achieve state-of-the-art in text ranking with huge performance leap \cite{Nogueira2019PassageRW, DBLP:conf/sigir/DaiC19}.

Though the idea of soft matching all tokens is carried through the development of neural IR models, seeing the success brought by deep LMs, we take a step back and ask: how much gain can we get if we introduce contextualized representations back to lexical exact match systems? In other words, can we build a system that still performs exact query-document token matching but compute matching signals with contextualized token representations instead of heuristics?
This may seem a constraint on the model, but exact lexical match produce more explainable and controlled patterns than soft matching. It also allows search to focus on only the subset of documents that have overlapping terms with query, which can be done efficiently with inverted list index. Meanwhile, using dense contextualized token representations enables the model to handle semantic mismatch,  which has been a long-standing problem in classic lexical systems.

To answer the question, we propose a new lexical matching scheme that uses vector similarities between query-document overlapping term contextualized representations to replace heuristic scoring used in classical systems. We present COntextualized Inverted List~(COIL), a new exact lexical match retrieval architecture armed with deep LM representations.
COIL processes documents with deep LM offline and produces representations for each document token.
The representations are grouped by their surface tokens into inverted lists. At search time, we build representation vectors for query tokens and perform contextualized exact match: use each query token to look up \emph{its own} inverted list and compute vector similarity with document vectors stored in the inverted list as matching scores. COIL enables efficient search with rich-in-semantic matching between query and document.

Our contributions include 1) introduce a novel retrieval architecture, \textit{contextualized inverted lists}~(COIL) that brings semantic matching into lexical IR systems, 2) show matching signals induced from exact lexical match can capture complicated matching patterns, 3) demonstrate COIL significantly outperform classical and deep LM augmented lexical retrievers as well as state-of-the-art dense retrievers on two retrieval tasks.
\section{Methodologies}
\label{sec:method}
In this section, we first provide some preliminaries on exact lexical match systems. Then we discuss COIL's contextualized exact match design and how its search index is organized. We also give a comparison between COIL and other popular retrievers.
\begin{figure}[t]
    \centering
    \includegraphics[width=0.49\textwidth]{figs/index.pdf}
    \caption{An illustration of traditional inverted lists. The inverted list maps a term to the list of documents where the term occurs. Retriever looks up query terms' inverted lists and scores those documents with stored statistics such as term frequency (tf).}
    \label{fig:traditional-index}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.47\textwidth]{figs/coil-index.pdf}
    \caption{COIL's index and retrieval architecture.  COIL-tok relies on the exact token matching (lower). COIL-full includes in addition CLS matching (upper).}
    \label{fig: coil-index}
\end{figure}

\subsection{Preliminaries}
Classic lexical retrieval system relies on \emph{overlapping} query document terms under morphological generalization like stemming, in other words, \emph{exact lexical match}, to score query document pair. A scoring function is defined as a sum of matched term scores. The scores are usually based on statistics like term frequency (\textit{tf}). Generally, we can write,
\begin{equation}
    \label{eq:general}
    s = \sum_{t \in q \cap d} \sigma_t (h_q(q, t), h_d(d, t))
\end{equation}
where for each overlapping term $t$ between query $q$ and document $d$, functions $h_q$ and $h_d$ extract term information and a term scoring function $\sigma_t$ combines them.
A popular example is BM25, which computes,
\begin{equation}
\begin{split}
    &s_{\text{BM25}} = \sum_{t \in q \cap d} idf(t) h_q^\text{BM25}(q, t) h_d^\text{BM25}(d, t) \\
    &h_q^\text{BM25}(q, t) = \frac{tf_{t,q}(1+k_2)}{tf_{t,q} + k_2} \\
    &h_d^\text{BM25}(d, t) = \frac{tf_{t,d}(1+k_1)}{tf_{t,d} + k_1 (1-b + b \frac{|d|}{\text{avgdl}})}
\end{split}

\label{eq:bm25}
\end{equation}
where $tf_{t, d}$ refers to term frequency of term $t$ in document $d$, $tf_{t,q}$ refers to the term frequency in query, $idf(t)$ is inverse document frequency, and $b$, $k_1$, $k_2$ are hyper-parameters.

One key advantage of exact lexical match systems lies in efficiency. With summation over exact matches, scoring of each query term only goes to documents that contain matching terms.
This can be done efficiently using \emph{inverted list} indexing (\autoref{fig:traditional-index}). The inverted list maps back from a term to a list of documents where the term occurs. To compute \autoref{eq:general}, the retriever only needs to traverse the subset of documents in query terms' inverted lists instead of going over the entire document collection.

While recent neural IR research mainly focuses on breaking the exact match bottleneck with soft matching of text, we hypothesize that exact match itself can be improved by replacing semantic independent frequency-based scoring with semantic rich scoring.
In the rest of this section, we show how to modify the exact lexical match framework with contextualized term representations to build effective and efficient retrieval systems.

\subsection{Contextualized Exact Lexical Match}
\label{sec:arch}
Instead of term frequency, we desire to encode the semantics of terms to facilitate more effective matching. Inspired by recent advancements in deep LM, we encode \emph{both} query and document tokens into contextualized vector representations and carry out matching between exact lexical matched tokens. \autoref{fig:coil-model} illustrates the scoring model of COIL.

In this work, we use a Transformer language model\footnote{We used the base, uncased variant of BERT.}  as the contextualization function.
We encode a query $q$ with the language model~(LM) and represent its $i$-th token by projecting the corresponding output:
\begin{equation}
\begin{aligned}
    \bm{v}_i^q &= \bm{W}_{tok} \text{LM}(q, i) + \bm{b}_{tok}

    \label{eq:proj-q-tok}
\end{aligned}
\end{equation}
where $\bm{W}_{tok}^{n_t \times n_{lm}}$ is a matrix that maps the LM's $n_{lm}$ dimension output into a vector of lower dimension $n_t$. We down project the vectors as we hypothesize that it suffices to use lower dimension token vectors. We confirm this in \autoref{sec:results}.
Similarly, we encode a document $d$'s $j$-th token $d_j$ with:
\begin{equation}
\begin{aligned}
    \bm{v}_j^d &= \bm{W}_{tok} \text{LM}(d, j) + \bm{b}_{tok}
    \label{eq:proj-d-tok}
\end{aligned}
\end{equation}

We then define the \emph{contextualized exact lexical match scoring function} between query document based on vector similarities between exact matched query document token pairs:
\begin{equation}
    s_\text{tok}(q, d)
    = \sum_{q_i \in q \cap d} \underset{d_j = q_i}{\max} ({\bm{v}_i^q}^\intercal \bm{v}^d_j)
    \label{eq:score-max}
\end{equation}
Note that, importantly, the summation goes through only overlapping terms, $q_i \in q \cap d$. For each query token $q_i$, we finds all \emph{same} tokens $d_j$ in the document, computes their similarity with $q_i$ using the \emph{contextualized} token vectors. The maximum similarities are picked for query token $q_i$. Max operator is adopted to capture the most important signal~\cite{textCNN}. This fits in the general lexical match formulation, with $h_q$ giving representation for $q_i$, $h_t$ giving representations for all $d_j=q_i$, and $\sigma_t$ compute dot similarities between query vector with document vectors and max pool the scores.

As with classic lexical systems, $s_{tok}$ defined in \autoref{eq:score-max} does not take into account similarities between lexical-different terms, thus faces vocabulary mismatch.
Many popular LMs~\cite{BERT,XLNet,RoBERTa} use a special CLS token to aggregate sequence representation. We project the CLS vectos with $\bm{W}_{cls}^{n_c \times n_{lm}}$ to represent the entire query or document,
\begin{equation}
\begin{aligned}
    \bm{v}_{cls}^q &= \bm{W}_{cls} \text{LM}(q, \text{CLS}) + \bm{b}_{cls} \\
    \bm{v}_{cls}^d &= \bm{W}_{cls} \text{LM}(d, \text{CLS}) + \bm{b}_{cls}
    \label{eq:proj-cls}
\end{aligned}
\end{equation}
The similarity between $\bm{v}_{cls}^q$ and $\bm{v}_{cls}^d$ provides high-level semantic matching and mitigates the issue of vocabulary mismatch. The full form of COIL is:
\begin{equation}
    s_\text{full}(q, d)
    = s_\text{tok}(q, d)  + {\bm{v}_{cls}^q}^\intercal \bm{v}_{cls}^d
\end{equation}
In the rest of the paper, we refer to systems with CLS matching \textbf{COIL-full} and without \textbf{COIL-tok}.

COIL's scoring model (\autoref{fig:coil-model}) is fully differentiable. Following earlier work~\cite{DPR}, we train COIL with negative log likelihood defined over query $q$, a positive document $d^+$ and a set of negative documents $\{d^-_1, d^-_2, .. d^-_l ..\}$ as loss.
\begin{equation}
    \mathcal{L} = -\log \frac{\exp(s(q, d^+))}{ \exp(s(q, d^+)) + \underset{l}{\sum} \exp(s(q, d^-_l)) }
\end{equation}
Following \citet{DPR}, we use in batch negatives and hard negatives generated by BM25. Details are discussed in implementation, \autoref{sec: exp-method}.

\subsection{Index and Retrieval with COIL}
\label{sec:retrive-and-index}
COIL pre-computes the document representations and builds up a search index, which is illustrated in \autoref{fig: coil-index}. Documents in the collection are encoded offline into token and CLS vectors. Formally, for a unique token $t$ in the vocabulary $V$, we collect its contextualized vectors from all of its mentions from documents in collection $C$, building token $t$'s contextualized inverted list:
\begin{equation}
    I^t = \{ \bm{v}_j^{d} \; | \; d_j=t , d \in C \},
\end{equation}
where $\bm{v}_j^{d}$ is the BERT-based token encoding defined in \autoref{eq:proj-d-tok}. We define search index to store inverted lists for all tokens in vocabulary, $\mathbb{I}=\{ I^t \; | \; t \in V\}$. For COIL-full, we also build an index for the CLS token $I^{cls} = \{ \bm{v}_{cls}^{d} \; | \; d \in C \}$ .

As shown in \autoref{fig: coil-index}, in this work we implement COIL's  by stacking vectors in each inverted list $I^t$ into a matrix $M^{n_t \times |I^k|}$,
so that similarity computation that traverses an inverted list and computes vector dot product can be done efficiently as one matrix-vector product with optimized BLAS~\cite{blas} routines on CPU or GPU.
All $\bm{v}_{cls}^d$ vectors can also be organized in a similar fashion into matrix $M_{cls}$ and queried with matrix product. The matrix implementation here is an exhaustive approach that involves all vectors in an inverted list.
As a collection of dense vectors, it is also possible to organize each inverted list as an approximate search index~\cite{faiss, scann} to further speed up search.

When a query $q$ comes in, we encode every of its token into vectors $\bm{v}_i^q$. The vectors are sent to the subset of COIL inverted lists that corresponds query tokens $\mathbb{J}=\{ I^t \; | \; t \in q\}$. where the matrix product described above is carried out. This is efficient as $|\mathbb{J}| << |\mathbb{I}|$, having only a small subset of all inverted lists to be involved in search.
For COIL-full, we also use encoded CLS vectors $\bm{v}_{cls}^q$ to query the CLS index to get the CLS matching scores. The scoring over different inverted lists can serve in parallel. The scores are then combined by \autoref{eq:score-max} to rank the documents.

Readers can find detailed illustration figures in the \autoref{sec:appendix}, for index building and querying, \autoref{fig:index-build} and \autoref{fig:index-search}, respectively.

\subsection{Connection to Other Retrievers}
\paragraph{Deep LM based Lexical Index}
Models like DeepCT~\cite{DeepCT, HDCT} and DocT5Query~\cite{docTTTTTquery} alter $tf_{t,d}$ in documents with deep LM BERT or T5. This is similar to a COIL-tok with token dimension $n_t = 1$. A single degree of freedom however measures more of a term \emph{importance} than \emph{semantic agreement}.

\paragraph{Dense Retriever}  Dense retrievers (\autoref{fig:dense-model}) are equivalent to COIL-full's CLS matching. COIL makes up for the lost token-level interactions in dense retriever with exact matching signals.

\paragraph{ColBERT} ColBERT (\autoref{fig:late-model}) computes relevance by soft matching \emph{all} query and document term's contextualized vectors.
\begin{equation}
    s(q,d) = \sum_{q_i \in [cls;q;exp]} \max_{d_j \in [cls;d]} ({\bm{v}_i^q}^\intercal \bm{v}^d_j)
\end{equation}
where interactions happen among query $q$, document $d$, $cls$ and set of query expansion tokens $exp$. The all-to-all match contrasts COIL that only uses exact match.
It requires a dense retrieval over all document tokens' representations as opposed to COIL which only considers query's overlapping tokens, and are therefore much more computationally expensive than COIL.

\section{Results}
\label{sec:results}
This section studies the effectiveness of COIL and how vector dimension in COIL affects the effectiveness-efficiency tradeoff. We also provide qualitative analysis on contextualized exact match.

\subsection{Main Results}

 \autoref{tab:perf-marco-psg} reports various systems' performance on the MARCO passage collection. COIL-tok exact lexical match only system significantly outperforms all previous lexical retrieval systems.  With contextualized term similarities, COIL-tok achieves a MRR of 0.34 compared to BM25's MRR 0.18. DeepCT and DocT5Query, which also use deep LMs like BERT and T5, are able to break the limit of heuristic term frequencies but are still limited by semantic mismatch issues. We see COIL-tok outperforms both systems by a large margin.

COIL-tok also ranks top of the candidate list better than dense retrieves. It prevails in MRR and NDCG while performs on par in recall with the best dense system, indicating that COIL's token level interaction can improve precision.
With the CLS matching added, COIL-full gains the ability to handle mismatched vocabulary and enjoys another performance leap, outperforming all dense retrievers.

COIL-full achieves a very narrow performance gap to ColBERT. Recall that ColBERT computes all-to-all soft matches between all token pairs. For retrieval, it needs to consider for each query token \emph{all} mentions of \emph{all} tokens in the collection (MSMARCO passage collection has around 500M token mentions). COIL-full is able to capture matching patterns as effectively with exact match signals from only query tokens' mentions and a single CLS matching to bridge the vocabulary gap.

We observe a similar pattern in the rerank task. COIL-tok is already able to outperform dense retriever and COIL-full further adds up to performance with CLS matching, being on-par with ColBERT.
Meanwhile, previous BERT rerankers have little performance advantage over COIL \footnote{Close performance between COIL and BERT rerankers is partially due to the bottleneck of BM25 candidates.}. In practice, we found BERT rerankers to be much more expensive, requiring over 2700 ms for reranking compared to around 10ms in the case of COIL.

\autoref{tab:perf-marco-doc} reports the results on MSMARCO document collection. In general, we observe a similar pattern as with the passage case. COIL systems significantly outperform both lexical and dense systems in MRR and NDCG and retain a small advantage measured in recall. The results suggest that
COIL can be applicable to longer documents with a consistent advantage in effectiveness.

The results indicate exact lexical match mechanism can be greatly improved with the introduction of contextualized representation in COIL. COIL's token-level match also yields better fine-grained signals than dense retriever's global match signal. COIL-full further combines the lexical signals with dense CLS match, forming a system that can deal with both vocabulary and semantic mismatch, being as effective as all-to-all system.

\begin{table*}[t]
\caption{Sample query document pairs with similarity scores produced by COIL. Tokens in examination are colored blue. Numbers in brackets are query-document vector similarities computed with vectors generated by COIL.}
\adjustbox{max width=0.98\linewidth}{
\begin{tabular}{l| l | c}
\hline\hline
Query Token  & \multicolumn{1}{c|}{COIL Contextualized Exact Match Score} & Relevance\\
\hline
\multirow{2}{*}{what is a \textbf{\textcolor{blue}{cabinet}}  in govt}
& \begin{tabular}[l]{p{0.7\textwidth}} \textbf{\textcolor{blue}{\textcolor{blue}{Cabinet  {[}16.28{]} }}} (government) A \textbf{\textcolor{blue}{cabinet {[}16.75{]}}} is a body of high-ranking state officials, typically consisting of the top leaders of the .... \end{tabular} & +\\
\cline{2-3}
&  \begin{tabular}[l]{p{0.7\textwidth}} \textbf{\textcolor{blue}{Cabinet {[}7.23{]}}} is 20x60 and top is 28x72. .... I had a 2cm granite countertop installed with a 10 inch overhang on one side and a 14 inch.... \end{tabular} & -\\
\hline
\multirow{2}{*}{what is priority \textbf{\textcolor{blue}{pass}}  }
& \begin{tabular}[l]{p{0.7\textwidth}} Priority \textbf{\textcolor{blue}{Pass {[}11.61{]}}} is an independent airport lounge access program. A membership provides you with access to their network of over 700 ....\end{tabular} & +\\
\cline{2-3}
& \begin{tabular}[l]{p{0.7\textwidth}} Snoqualmie \textbf{\textcolor{blue}{Pass {[}7.98{]}}} is a mountain \textbf{\textcolor{blue}{pass {[}6.83{]}}} that carries Interstate 90 through the Cascade Range in the U.S. State of Washington....  \end{tabular} & -\\
\hline
\multirow{2}{*}{what \textbf{\textcolor{blue}{is}} njstart }
& \begin{tabular}[l]{p{0.7\textwidth}} NJSTART \textbf{\textcolor{blue}{is {[}1.25{]}}} a self-service online platform that allows vendors to manage forms, certifications, submit proposals, access training .... \end{tabular} & +\\
\cline{2-3}
& \begin{tabular}[l]{p{0.7\textwidth}} Contract awardees will receive their Blanket P.O. once it \textbf{\textcolor{blue}{is {[}-0.10{]}}} converted, and details regarding that process will also be sent...\end{tabular} & -\\
\hline\hline
\end{tabular}
}
\label{tab:analysis}
\end{table*}

\subsection{Analysis of Dimensionality}

The second experiment tests how varying COIL's token dimension $n_t$ and CLS dimension $n_c$ affect model effectiveness and efficiency. We record retrieval performance and latency on MARCO passage collection in \autoref{tab:dimension}.

In COIL-full systems, reducing CLS dimension from 768 to 128 leads to a small drop in performance on the Dev set, indicating that a full 768 dimension may not be necessary for COIL. Keeping CLS dimension at 128, systems with token dimension 32 and 8 have very small performance difference, suggesting that token-specific semantic consumes much fewer dimensions. Similar pattern in $n_t$ is also observed in COIL-tok~($n_c=0$).

On the DL2019 queries, we observe that reducing dimension actually achieves better MRR. We believe this is due to a regulatory effect, as the test queries were labeled differently from the MSMARCO train/dev queries~\cite{craswell2020overview}.

We also record CPU and GPU search latency in \autoref{tab:dimension}.
Lowering COIL-full's CLS dimension from 768 to 128 gives a big speedup, making COIL faster than DPR system. Further dropping token dimensions provide some extra speedup. The COIL-tok systems run faster than COIL-full, with a latency of the same order of magnitude as the traditional BM25 system. Importantly, lower dimension COIL systems still retain a performance advantage over dense systems while being much faster.
We include ColBERT's latency reported in the original paper, which was optimized by approximate search and quantization. All COIL systems have lower latency than ColBERT even though our current implementation does not use those optimization techniques. We however note that approximate search and quantization are applicable to COIL, and
 leave the study of speeding up COIL to future work.