\section{Introduction}
Relation extraction plays an essential role in information extraction, which aims to predict relations of entities in texts. Early work on relation extraction mainly focuses on sentence-level relation extraction, i.e., predicting relation from a single sentence, and has achieved promising results. Recently, the research of relation extraction has advanced to document-level relation extraction, a scenario more practical than sentence-level relation extraction and more challenging.

The relation pattern between entity pairs across different sentences is often more complex, and the distance of these entity pairs is relatively long. Therefore, DocRE requires models to figure out the relevant context and conduct reasoning across sentences instead of memorizing the simple relation pattern in a single sentence. Moreover, multiple entity pairs co-exist in one document, and each entity may have more than one mention appearing across sentences.
Thus, DocRE also requires the model to extract relations of multiple entity pairs from a single document at once. In other words, DocRE is a one-example-multi-instances task while sentence-level RE is a one-example-one-instance task.

Another unique challenge of DocRE that cannot be overlooked is long-tailed distribution. Long-tailed distribution is a common phenomenon in real-world data. In DocRE, we also observe the long-tailed distribution. Figure \ref{fig:docred-long-tail-distribution} presents the relation distribution of DocRED\citep{yao-etal-2019-docred}, a widely-used DocRE dataset: $7$ most frequent relations from $96$ relations takes up $55.12\%$ of total relation triples; while the frequencies of $60$ relations are only less than $200$. Vanilla training on long-tailed data will cause the model to achieve overwhelming performance on head relations but underfitting on tailed relations. Although the overall DocRE performance is largely dependent on performance on head relations since they are the majority, model failure on tailed relations is a big concern in real-world DocRE scenarios.
\begin{figure}[h]
    \centering
    \includegraphics[width=8cm]{relation_distribution.pdf}
    \caption{Relation Distribution of DocRED Train set. Relation index are sorted by frequency count from high to low.}
    \label{fig:docred-long-tail-distribution}
\end{figure}

Data augmentation is a commonly used strategy for addressing the long-tailed problem. Nonetheless, applying data augmentation efficiently on DocRE is non-trivial. Ordinary data augmentation operation on the document, including text random-dropping or replacing\citep{wei-zou-2019-eda} would require the DocRE model for extra encoding process of the entire document, which is computation in-efficient on DocRE since the document may contain numerous sentences. Besides, DocRE is a one-example-multi-instances task, so tailed relations and head relations presumably co-exist in one document. As a result, the head relations would also be augmented if we augment the tailed relations by aforementioned trivial augmentation methods on text, which is unexpected and may lead to over-fitting on head relations.

In this paper, we propose a novel data augmentation mechanism for DocRE, named ERA, for improving the document-level relation extraction by mitigating the long-tailed problem. The proposed ERA method applies augmentation on relation representations rather than texts, so it can augment tail relations without another encoding operation of the long document, which is computation-efficient and also effective for improving performance on tailed relations.

In addition, we propose a contrastive learning framework based on our ERA method, i.e., ERACL, for pre-training on the distantly-supervised data. The proposed ERACL framework can further enhance the model performance on tailed relations and achieve comparable overall DocRE performance compared to the state-of-art methods on DocRED.

\section{Background and Related Works}
\subsection{Problem Formulation}
Given a document $\mathcal{D}=\{w_1,w_2,...,w_l\}$ with $l$ words, a set of $n$ entities $\mathcal{E}= \{{e}_{i}\}^n_{i=1}$ are identified by human annotation or external tools. For each entity ${e}_i$, $m$ mentions of ${e}_i$ denoted as $\{m_{ij}\}^m_{j=1}$ are also annotated by providing the start position and end position in $\mathcal{D}$. In addition, the relation scheme $\mathcal{R}$ is also defined.

The objective of DocRE is to extract the relation triple set $\{(e_h,r,e_t)|e_h\in \mathcal{E},r\in \mathcal{R},e_t\in \mathcal{E}\} \subseteq \mathcal{E} \times \mathcal{R} \times \mathcal{E}$ from all possible relation triples, where each realtion triple $(e_h,r,e_t)$ extracted by the model can be interpreted as relation $r\in \mathcal{R}$ holds between head entity $e_h \in \mathcal{E}$ and tail entity $e_t \in \mathcal{E}$. For future simplicity, we denote tail relations as $\mathcal{R}^t \subset \mathcal{R}$ and head relations as $\mathcal{R}^h \subset \mathcal{R}$.
\subsection{Document-Level Relation Extraction}
\label{sec:docre-background}

To address the prior challenges in DocRE, one main branch of DocRE works use \textbf{Graph-based Methods}\citep{sahu_inter-sentence_2019,christopoulou_connecting_2019,wang_global--local_2020,zeng_double_2020,nan_reasoning_2020,li_graph_2020,xu_discriminative_2021}. The general idea of graph-based methods is to conduct multi-hop reasoning across entities, mentions and sentences in a document by graph neural networks. First a document is converted to a document graph by human designed heuristics, attention mechanism or dependency parser. Then the document graph is encoded by graph neural networks\cite{DBLP:conf/iclr/KipfW17,NEURIPS2018_182be0c5,wu2021graph} to conduct multi-hop reasoning across graph nodes and edges. Another branch of DocRE methods adopt \textbf{Transformer-based Methods}\citep{wang_fine-tune_2019,ye_coreferential_2020, DBLP:conf/aaai/XuWLZM21, zhou_atlop_2021, zhang_docunet_2021}. Transformer-based methods rely on the strong long-context representation capability of pre-trained transformers\citep{devlin-etal-2019-bert,liu_roberta_2019}. In addition, self-attention mechanism in transformer architecture can implicitly model the dependency between entities, mentions and contexts, which can be utilized for relation reasoning\citep{zhou_atlop_2021}.

Different from previous works, in this paper we focus more on addressing the challenges of long-tailed distribution in DocRE.
\subsection{Contrastive Learning}
\label{sec:contrastive-learning-background}
Contrastive learning is proved to be a promising self-supervised pre-training task for image recognition\citep{pmlr-v119-chen20j,he_momentum_2020}.
The principle of contrastive learning is to increase the representation similarity of anchor example $x$ and positive examples $x^+$ while decreasing the representation similarity of anchor example $x$ and negative examples $x^-$ by INFONCE loss\citep{Oord_INFONCE_2018}.

Under the self-supervised setting, positive samples $x^+$ are constructed by data augmentation operation, including image cropping, resizing on anchor samples. The motivation of creating $x^+$ via data augmentation is that augmented samples are still similar or even the same in semantic space, then it can provide training signals for self-supervised pre-training. Therefore, models pre-trained by self-supervised contrastive learning can learn task-agnostic and robust representation for down-streaming tasks, which also can capture the semantic information of input samples.

The general contrastive learning framework has been applied in language tasks and achieved competitive performance.  \citet{fang_cert_2020} adapted the contrastive learning framework for self-supervised pre-training on transformers and achieved superior performance compared to BERT\cite{devlin-etal-2019-bert}. \citet{sclnlp_gunel_2021} proposed to use supervised contrastive learning for more robust fine-tuning on pre-trained transformers. In relation extraction, \citet{peng-etal-2020-learning} and \citet{qin-etal-2021-erica} adopted contrastive learning as one pre-training task to improve the relation understanding capability of BERT. It has been demonstrated that proper adaptation of contrastive learning framework can encourage the model to learn more robust task-agnostic or task-related representations, especially when the training data is limited. The problem of long-tail relation distribution is essentially lack of training samples of certain relation types. Considering this, we proposed a new contrastive learning framework based on a new data augmentation method in DocRE, called Easy Relation Augmentation(ERA), which can learn more robust relation representations for DocRE, especially for the tailed relations.

\section{Easy Relation Augmentation}
\subsection{Overview}

    We summarize the main components of ERA framework as follow: ERA takes a document $\mathcal{D}$ as input, then the Document Encoding and Relation Encoding modules will encode each entity pair $(e_h,e_t) \in \mathcal{E} \times \mathcal{E}$ from two aspects: contextualized entity representation and pooled context representation via self-attention mechanism of Pre-trained Transformers\citep{zhou_atlop_2021}. Afterwards, we proposed a novel Easy Relation Augmentation(ERA) mechanism to enhance the entity pair representation by applying a random mask on pooled context representation. The proposed ERA mechanism can augment the tail relations $r \in \mathcal{R}^t$ without another Relation Encoding and Document Encoding, which is computation-efficient and also effective. Finally, we train the relation prediction module on the augmented relation representations.

\subsection{Document Encoding}
    In light of the promising capability of Pre-trained Transformers\citep{devlin-etal-2019-bert,liu_roberta_2019} for modeling the long-range text dependency, We resort to pre-trained transformers for document encoding. We add a special entity marker "*"\citep{zhang-etal-2017-position} at the start and end position of each mention $m_{ij}$, and "*" can be replaced with other special tokens. Entity markers can spotlight the mention words and also provide entity positional information for Pre-trained Transformers, which proves to be effective in DocRE\citep{zhou_atlop_2021}. Feeding the document $\mathcal{D}$ to the pre-trained transformers, we can get the contextualized representation $\mathbf{H}$ of all words and vanilla multi-head self-attention $\mathbf{A}$ from the last block of Pre-trained Transformers($\mathbf{Ptr}$).
    \begin{equation}
        \mathbf{H},\mathbf{A} = \mathbf{Ptr}(\mathcal{D}=\{w_1,w_2,...,w_l\})
    \end{equation}
    Where $\mathbf{H} \in \mathbb{R}^{l \times d}$, $\mathbf{A} \in \mathbb{R}^{l \times l \times h}$. $d$ is the model dimension of the Pre-trained Transformers and $h$ is the number of self-attention heads of Pre-trained transformers.
\subsection{Relation Encoding}
    Given the contextualized representation $\mathbf{H}$ and self-attention $\mathbf{A}$ of the document $\mathcal{D}$, the goal of Relation Encoding module is to encode each entity pair $(e_h,e_t) \in \mathcal{E} \times \mathcal{E}$ by aggregating the contextualized entity representation and pooled context representation, which are crucial for relation understanding and reasoning across the long document.

    Contextualized entity representation can provide the contextualized entity naming and entity typing information for relation inference. For entity $e_h \in \mathcal{E}$, we obtain the contextualized mention representation by collecting the Pre-trained transformer last layer output of "*" marker at the start of mention $m_{ij}$, denoted as $\mathbf{m_{hj}}$. Subsequently, we can get the final contextualized entity representation $\mathbf{e_h}$ by logsumexp pooling \citep{jia-etal-2019-document}, which can achieve better results compared to max pooling and average pooling on DocRE\citep{zhou_atlop_2021}.
    \begin{equation}
        \mathbf{e_h} = log \sum _{j=1}^{m} exp(\mathbf{m_{hj}})
    \end{equation}

    As mentioned in Section \ref{sec:docre-background}, DocRE requires the model to capture the dependencies among entities, mentions, and context words, and also filter out the unnecessary context information from the long document. We named the aforementioned information as pooled context information. The self-attention matrix $\mathbf{A} \in \mathbb{R}^{l\times l \times h}$ obtained from Pre-trained transformers have already implicitly modeled the dependency among entities, mentions, and context words, which can be utilized for getting meaningful pooled context representation\citep{zhou_atlop_2021}. We follow \citet{zhou_atlop_2021} to obtain the pooled context information by utilizing the self-attention matrix $\mathbf{A}$.

    Given a entity pair $(e_h,e_t) \in \mathcal{E} \times \mathcal{E}$, one can get the pooled context representation $\mathbf{c_{h,t}}$ by Equation \ref{eq:pooled-context-representation} and \ref{eq:attention-dot-product}.
    \begin{equation}
        \label{eq:pooled-context-representation}
        \mathbf{c_{h,t} = H^T \cdot \frac{A_{h,t}}{1^T\cdot A_{h,t}}}
    \end{equation}

    \begin{equation}
        \label{eq:attention-dot-product}
        \mathbf{A_{h,t}} = \mathbf{A_h} * \mathbf{A_t}
    \end{equation}
    Where $\mathbf{A_h} \in \mathbb{R}^{l \times 1}$,$\mathbf{A_t} \in \mathbb{R}^{l \times 1}$ and $\mathbf{1} \in \mathbb{R}^{l \times l}$. $\mathbf{A_h}$ is the attention score of entity $e_h$ to all words in $\mathcal{D}$, which is obtained by averaging the attention score of all entity mentions $m_{hj}$, denoted as $\mathbf{A_{m_{hj}}}$. Similar to contextualized mention representation $\mathbf{m_{hj}}$, we obtain the mention attention score $\mathbf{A_{m_{hj}}}$ by indexing the vanila self-attention matrix $\mathbf{A}$ with position of starting "*" marker. In addition, note that the vanila self-attention matrix is first averaged over all attention heads before performing the indexing. $\mathbf{A_t}$ is also calculated following the same procedure.

    In the end, for the entity pair $(e_h,e_t)$, we can form a triple represention $\mathbf{\mathcal{T}_{h,t}} = \left( \mathbf{e_h},\mathbf{c_{h,t}},\mathbf{e_t} \right)$. $\mathbf{\mathcal{T}_{h,t}}$ contains all the information for relation prediction and form the basis for our Easy Relation Augmentation and Contrastive Leaning framework.

\subsection{Relation Representation Augmentation}
    \label{sec:era-relation-aug}
     To address the long-tailed problem residing in the DocRE, we propose a novel Easy Relation Augmentation(ERA) mechanism to increase the frequency of tailed relations and enhance the entity pair representation.

    Denote the set of triple representation of all entity pairs as $\mathcal{T}_{orig} = \{(\mathbf{e_h,c_{h,t},e_t}) |  e_h \in \mathcal{E}, e_t \in \mathcal{E}\}$. In addition, we can manually select the set of relations need to be augmented, i.e., $\mathcal{R}^{aug} \subseteq \mathcal{R}$.

    Given a entity pair $(e_h,e_t)$ whose relation $r \in \mathcal{R}^{aug}$, we first retrieve the original triple representation $(\mathbf{e_h,c_{h,t},e_t})$ from $\mathcal{T}_{orig}$. Recall that the pooled context representation $\mathbf{c_{h,t}}$ encodes the unique context information for relation inference, and a slight perturbation on the context should not affect the relation prediction. Established on this intuition, we add a small perturbation on $\mathbf{c_{h,t}}$.

    We first apply a random mask on $\mathbf{A}_{h,t}$ described in Equation \ref{eq:pooled-context-representation} by multiplying $\mathbf{A}_{h,t}$ with a randomly generated mask vector $\mathbf{p} \in \mathbb{R}^{l\times 1}$. Each dimension of $\mathbf{p}$ is in $\{0,1\}$ and generated by a Bernoulli distribution with parameter $p$.
    \begin{equation}
        \mathbf{A'_{h,t}} = \mathbf{p} * \mathbf{A_{h,t}}
    \end{equation}
    Applying the random mask on attention score $\mathbf{A_{h,t}} \in \mathbb{R}^{l\times 1}$ can be interpreted as randomly filter out some context information since the attention score for them are set to $0$. In addition, the degree of perturbation can be controlled by setting proper $p$.
    Then we can get the perturbed pooled context representation $c'_{h,t}$ in Equation \ref{eq:pertubed-context-representation}.
    \begin{equation}
        \label{eq:pertubed-context-representation}
        \mathbf{c'_{h,t} = H^T \cdot \frac{A'_{h,t}}{1^T\cdot A_{h,t}}}
    \end{equation}

    For all the entity pairs $(e_h,e_t)$ whose relation $r$ in $\mathcal{R}^{aug}$, we apply the prior steps to get $\alpha$ distinct pertubed context representations $\{\mathbf{c'_{i,h,t}}\}^{|\alpha|}_{i=1}$ by using $\alpha$ random mask, where $\alpha$ is a hyper-parameter for controlling the number of ERA operations. Eventually, we can get the augmented triple representation set $\mathcal{T}_{aug}$, which can be formulated in Equation \ref{eq:augset-formulaiton}.
    \begin{equation}
        \label{eq:augset-formulaiton}
        \mathcal{T}_{aug} = \{\mathbf{(e_h,c'_{i,h,t},e_t)} | e_h \in \mathcal{E}, r \in \mathcal{R}^{aug}, e_t \in \mathcal{E}\}
    \end{equation}

    Combining the original triple representation set $\mathcal{T}_{orig}$ and $\mathcal{T}_{aug}$, we can get the total tripe representation set $\mathcal{T}$ for relation prediction and our Contrastive Learning framework.
    \begin{equation}
        \mathcal{T} = \mathcal{T}_{orig} \cup \mathcal{T}_{aug}
    \end{equation}

\subsection{Relation Prediction}
    Based on the triple representation of all entity pairs, the relation prediction module finally predict the relations hold between each pair. For a triple representation $\mathbf{(e_h,c_{ht},e_t) \in \mathcal{T}}$, we first apply two linear transformations with Tanh activation to fuse the pooled context representation $\mathbf{c}_{ht}$ with $\mathbf{e}_h$ and $\mathbf{e}_t$.
    \begin{equation}
        \label{eq:h_fusing}
        \mathbf{h} = tanh(\mathbf{W}_h \cdot \mathbf{e}_h + \mathbf{W}_{c1} \cdot \mathbf{c}_{h,t})
    \end{equation}
    \begin{equation}
        \label{eq:t_fusing}
        \mathbf{t} = tanh(\mathbf{W}_t \cdot \mathbf{e}_t + \mathbf{W}_{c2} \cdot \mathbf{c}_{h,t})
    \end{equation}
    Where $\mathbf{W}_{h},\mathbf{W}_{t},\mathbf{W}_{c1},\mathbf{W}_{c2} \in \mathbb{R}^{d\times d}$, which are trainable parameters of the model. Following \citet{zhou_atlop_2021}, then we used a grouped bi-linear layer to calculate a score for relation $r$, which splits the vector representation to $k$ groups and performs bilinear within group.
    \begin{equation}
        score_{r} = \sum_{i=1}^{k} \mathbf{h}^{iT}  \mathbf{W}_r^i \mathbf{t}^i
    \end{equation}
    Where $\mathbf{W}_r^i \in \mathbb{R}^{d/k \times d/k}$ is the bilinear parameter of group $i$. During training stage, we apply the adaptive thresholding loss \citep{zhou_atlop_2021} to dynamically learn a threshold $\theta_{h,t}$ for each entity pair by introducing a threshold class $TH$.
    \begin{equation}
        \label{eq:atlop-loss}
        \begin{aligned}
            \mathcal{L}_{h,t} = & -\sum _{r\in \mathcal{P}_{h,t}} log \left[ \frac{exp(score_r)}{\sum _{r' \in \mathcal{P}_{h,t} \cup \{TH\}} exp(score_{r'}) }\right]\\
                                & - log \left[ \frac{exp(score_{TH})}{\sum _{r' \in \mathcal{N}_{h,t} \cup \{TH\}} exp(score_{r'})}\right]
        \end{aligned}
    \end{equation}
    $\mathcal{P}_{h,t} \subset \mathcal{R}$ is the set of all valid relations that hold between entity pair $(e_h,e_t)$, and it is empty when no relation hold between the pair. In addition, $\mathcal{N}_{h,t} = \mathcal{R} - \mathcal{P}_{h,t}$. In the inference stage, the threshold $\theta$ for valid relation scores is set to $score_{TH}$.

\section{Contrastive Learning for relation pre-training}

\subsection{Overview}
   We propose a contrastive learning(CL) framework for unifying the augmented relation representations and improving the robustness of learned relation representations, especially for tailed relations. Specifically, we use the CL framework for pre-training on the distantly-supervised DocRE dataset\citep{yao-etal-2019-docred}, which is annotated by querying the knowledge graph but is noised. Considering that the model will be fine-tuned on the human-annotated dataset after the representation learning stage, the noise in the distantly supervised dataset is acceptable and correctable.

    Under DocRE setting, we claim that the semantically-similar samples should be the entity pairs that have the same relation $r$, including both of the original pairs and augmented pairs by ERA. However, only a few entity pairs have the same relation within one document, especially for the tailed relation $r$.

    Increasing the mini-batch size can partially mitigate the problem, but it requires large GPU memory for training which may not be accessible. Thus, we adapted the MOCO framework \citep{he_momentum_2020} to the DocRE setting, named MoCo-DocRE. The moCo-DocRE framework can conduct the CL without using large batch-size by keeping a relation representation queue $Q_r$ holding $q$ relation representations from the previous mini-batch for each relation $r \in \mathcal{R}$. This allows us to reuse the encoded positive and negative relation representations in prior mini-batches. We summarize our contrastive learning framework in Figure \ref{fig:cl_overview}.
    \begin{figure}[t]
        \centering
        \includegraphics[width=8cm]{cl_overview.pdf}
        \caption{Overview of the proposed MoCo-DocRE framwork.}
        \label{fig:cl_overview}
    \end{figure}
\subsection{Anchor relation encoding}
    For document $\mathcal{D}$ in pre-training dataset, we first conduct the aforementioned document encoding, relation encoding and Easy Relation Augmentation(ERA) and obtain the triple representation set $\mathcal{T}$ of all entity pairs. For a triple representation $\mathbf{(e_h,c_{h,t},e_t)} \in \mathcal{T}$, we use two linear transformations to fuse the triple representation, which are same as Equation \ref{eq:h_fusing} and \ref{eq:t_fusing}. Next, we use a MLP layer with ReLU activation for final relation representation:
    \begin{equation}
        \mathbf{x} = relu(\mathbf{W}_2(\mathbf{W}_1 [\mathbf{h:t}] + \mathbf{b}_1) + \mathbf{b}_2)
    \end{equation}
    Where $[:]$ denotes the vector concatenation operation, $\mathbf{W}_1 \in \mathbb{R}^{2d\times d}$ and $\mathbf{W}_2 \in \mathbb{R}^{d\times d_r}$ are trainable model parameters in pre-training stage, and $d_r$ is the dimension of final relation representation $\mathbf{x}_{h,t}$. After contrastive pre-training, the MLP layer will not be used for relation prediction in fine-tuning.
\subsection{MoCo-DocRE}
    To keep the consistency of relation representation in $Q_r$, we also use a momentum updated model to encode the positive and negative samples in contrastive learning\citep{he_momentum_2020}. The original model $\mathcal{M}$ is updated via back-propagation, and the momentum-updated model $\mathcal{M}'$ is updated by Equation \ref{eq:momentum-updated}.
    \begin{equation}
        \label{eq:momentum-updated}
        \mathcal{M}' = m \cdot \mathcal{M}' + (1-m) \cdot \mathcal{M}
    \end{equation}
    Where $m$ is the momentum hyper-parameter, which can control the evolving speed of $M'$. Next we feed the document $\mathcal{D}$ to $\mathcal{M}'$ for $\mathbf{x}'$ by following the same procedure as getting anchor relation representation $\mathbf{x}$. Then we push $\{\mathbf{x'} | (\mathbf{e}_h,\mathbf{c}_{h,t},\mathbf{e}_t) \in \mathcal{T}'\}$ to $|\mathcal{R}|$ relation representation queues according to their relation labels. If relation $r$ holds between $(e_h,e_t)$, then $x'$ will be pushed to $Q_r$. Eventually, we can get the set of positive and negative relation representations of $\mathbf{x}$ from queues, i.e, $\mathcal{P} = \cup _{r \in \mathcal{P}_{h,t}} Q_r$ and $\mathcal{N}=\cup _{r \in \mathcal{N}_{h,t}} Q_r$.

    For anchor relation representation $\mathbf{x}$, now we can formalize the INFONCE loss \citep{Oord_INFONCE_2018} under our MoCo-DocRE in Equation \ref{eq:info-nce}.
    \begin{equation}
        \label{eq:info-nce}
        \mathcal{L} = - \sum_{x^+ \in \mathcal{P}} log \left[ \frac{e^{\mathbf{x}^T  \mathbf{x^+ / \tau}}}{e^{\mathbf{x}^T  \mathbf{x^+/\tau}} + \sum_{x^- \in \mathcal{N}}{e^{\mathbf{x}^T \mathbf{x}^-/\tau}}}   \right]
    \end{equation}
    Where $\tau$ is the temperature hyperparameter. In addition $\mathbf{x},\mathbf{x}^+,\mathbf{x}^-$ in Equation \ref{eq:info-nce} are \textit{l2}-normalized.

\begin{table*}[ht]
    \centering

    \begin{tabular}{lcccc}
        \toprule
        \multirow{2}*{\textbf{Model}} & \multicolumn{2}{c}{\textbf{Dev}} & \multicolumn{2}{c}{\textbf{Test}}  \\
         & Ign $F_1$ & $F_1$ & Ign $F_1$ & $F_1$ \\
        \midrule
        \textit{Graph-based Methods}  & & & &\\
        GLRE\citep{wang_global--local_2020} & -- & -- & 55.40 & 57.40 \\
        LSR\citep{nan_reasoning_2020} &52.43&  59.00& 56.96& 59.05 \\
        GAIN\citep{zeng_double_2020} &59.14& 61.22 & 59.00& 61.24\\
        DRN\citep{xu_discriminative_2021} &59.33& 61.39& 59.15& 61.37 \\

        \midrule
        \textit{Transformer-based Methods} & & & &\\

        SSAN\citep{DBLP:conf/aaai/XuWLZM21} &57.04& 59.19& 56.06& 58.41 \\
        ATLOP\citep{zhou_atlop_2021} & 59.22  & 61.09  &59.31 &61.30 \\
        DocuNet\citep{zhang_docunet_2021} &59.86 &61.83& 59.93& 61.86 \\
        AFLKD\citep{tan-etal-2022-document} &60.08 &62.03 &60.04 &62.08 \\

        \midrule
        \textit{Our Methods} & & & &\\
        ERA & 59.30 $\pm$ 0.09 & 61.30 $\pm$ 0.08 &58.71 &60.97 \\
        ERACL &59.72 $\pm$ 0.19 & 61.80 $\pm$ 0.20&59.08 &61.36  \\
        \toprule
    \end{tabular}
    \caption{Overall DocRE performance evaluated on DocRED benchmark. We report the mean and standard deviation of 3 runs with different random seeds on the development set. The official test results are reported by the best checkpoint on the development set. Results of all other models are reported in their original paper and use BERT-base-cased as backbone encoder.}
    \label{tb:main-results}
\end{table*}

\section{Experiment}

\subsection{Experiment Setup and Dataset}
   \begin{table}[h]
        \centering
        \begin{tabular}{lcc}
            \toprule

            Statistics & DocRED & HacRED \\
            \midrule
            \# Train & 3053 &6231 \\
            \# Dev &1000 &1500 \\
            \# Test &1000 &1500 \\
            \# Relations &96 &26 \\
            \toprule
        \end{tabular}
        \caption{Dataset Statistics of DocRED and HacRED}
          \label{tb:data-stat}
    \end{table}

    \textbf{Dataset:}
   We evaluate the proposed ERA and contrastive learning framework on two popular DocRE datasets, DocRED\citep{yao-etal-2019-docred} and HacRED\citep{cheng-etal-2021-hacred}. DocRED contains 5053 English documents extracted from Wikipedia and 96 relations, which are human-annotated. Besides, DocRED also provide a distantly-supervised dataset with 101873 documents, and the relation of entitity pairs are annotated by querying Wikidata. HacRED is a human annotated Chinese dataset with 26 relations. Statistics of Datasets are listied on Table \ref{tb:data-stat}.  \\
    \textbf{Implementation Details:} We use the pre-trained BERT-base-cased\citep{devlin-etal-2019-bert} as our backbone for DocRED dataset. All the hyperparameters are tuned on the development set. Specifically, we set the random mask probability $p$ to 0.1 and the number of augmentation $\alpha$ to $2$. In addition, the number of grouped bilinear $k$ is set to $64$. The temperature parameter $\tau$ is set to $0.5$ and the size of $Q_r$, i.e., $q$ is set to $500$, and the momentum $m$ is set to 0.99. The learning rate is set to $1e-5$ for pre-training on our CL framework. In the fine-tune on human-annotated data, we set the learning rate to $5e-5$ for parameters of BERT and $1e-4$ for other parameters. We use AdamW\citep{losch_adamw_2019} for optimization of all parameters and a linear-decayed scheduler with a warmup ratio $0.06$. Gradients whose norm is larger than $1$ are clipped. For HacRED dataset, we use XLM-Roberta-base\citep{conneau-etal-2020-unsupervised} as backbone. Under HacRED scenario, we set the random mask probability $p$ to 0.05 and the number of augmentation $\alpha$ to $3$. All the other parameters are same as the DocRED scenario.

\subsection{Evaluation Metric}
    DocRED benchmark provide two evaluation metrics, i.e. $F_1$ Ign $F_1$. $F_1$ is the minor $F_1$ value for all predicted relations in test/development dataset, which can reflect the overall performance of DocRE. Compared to $F_1$, Ign $F_1$ excludes the entity pairs which appear both on training and test/dev data.
    To demonstrate how ERA and contrastive learning can improve the performance of tailed relations, we propose to use the following evaluation metrics: \\
    $\mathbf{Macro}$: it computes the $F_1$ value by first calculating $F_1$ for each relation separately and then getting the average of all relation classes. Compared to minor $F_1$, macro $F_1$ treat all relation classes equally, $F_1$ of tailed relations will have equal impact compared to head relations.\\
    $\mathbf{Macro@500}$,$\mathbf{Macro@200}$,$\mathbf{Macro@100}$: Those metrics target at tailed relations whose frequency count in train dataset is less than 500,200,100 respectively. Values are computed by averaging the F1 value of the targeted relations.

\begin{table*}[h]
\centering
    \begin{tabular}{lcccc}
    \toprule
    Methods & $\mathbf{Macro}$ & $\mathbf{Macro@500}$ & $\mathbf{Macro@200}$ & $\mathbf{Macro@100}$  \\
    \midrule
    DocuNet &40.69 & 36.54 & 28.95 & \bf{22.37}          \\
    ATLOP   & 39.54 & 35.20 & 26.82 & 18.76         \\
    \hline
    --Deletion &39.22 &34.88 &26.62 &18.78 \\
    --Mask &38.31 &33.80 &25.30 &17.35 \\
    --AFL &40.04 &35.78 &27.78 &20.52 \\
    \hline
    ERA     & 40.55 & 36.21 & 28.51 & 20.50 \\
    ERACL   & \bf{41.34} & \bf{37.13} & \bf{29.43} & 22.31     \\
    \toprule
\end{tabular}
    \caption{Evaluation on tailed relations. All the results are averaged on 3 runs with different random seeds on development set. Relation labels of test set are not accessible, so the results on test set cannot be reported.}
    \label{tb:tail-results}
\end{table*}

\subsection{Main Results}
We compare the proposed ERA and ERACL methods to graph-based and transformer-based models on the DocRED benchmark by using $F_1$ and Ign $F_1$ metrics on the dev/test dataset. Results are reported in Table \ref{tb:main-results}. The proposed ERACL method, which first conducts contrastive learning under our MoCo-DocRE framework on the distantly supervised dataset and then conducts ERA fine-tuning on the training set, can achieve competing $F_1$ and Ign $F_1$ value, compared to state-of-art graph-based methods and transformer-based methods. Besides, compared to ATLOP\citep{zhou_atlop_2021} which is the baseline of ERACL, ERACL can improve the minor $F_1$ on the development set by $0.71$ and ERA can improve the minor $F_1$ by $0.29$, which demonstrate the effectiveness of the proposed ERA method and contrastive learning pretraining.

\subsection{Results on tailed relation}
    To demonstrate the effectiveness of our ERA and ERACL on improving model performance on tailed relations, we evaluated ERA and ERACL using Macro, Macro@500, Macro@200, and Macro@100 metrics. Besides, we compare ERA and ERACL with three baseline methods which are used for addressing long-tailed distribution on DocRED.
    \textbf{Text Random Deletion/Mask} are commonly used data augmentation techniques for NLP tasks. We apply the Text Random Deletion and masking as data augmentation for documents which contain  tailed relations.
    \textbf{Adaptive Focal Loss} proposed by \citet{tan-etal-2022-document} is a adaptation of Focal Loss\citep{Lin_2017_ICCV} on DocRE scenario. AFL proved to be effective on tail relations. We implement those three methods based on ATLOP. Results are listed on Table \ref{tb:tail-results}. The proposed ERA and ERACL method can outperform those three baselines on tailed relations, which demonstrates the effectiveness and necessities of our ERA and ERACL for addressing the long-tailed distribution on DocRE scenario.

    Moreover, the proposed ERA method can improve the Macro over ATLOP by $1.01$, $1.01$ on Macro@500, $1.69$ on Macro@200, and $1.74$ on Macro@100. We observe that the improvements are more significant on relations that appear less frequently. In addition, the proposed ERACL method can further gain improvements over ERA: 0.79 on Macro, 0.92 on Macro@500, 0.92 on Macro@200, 1.81 on Macro@100, which also show similar trends as ERA over ATLOP.

    \begin{figure}[h]
        \centering
        \includegraphics[width=7cm]{long-tail-demo2.pdf}
        \caption{Comparison of F1 across 10 relation clusters. All results are averaged by 3 runs with different random seeds.}
        \label{fig:relationF1-demo}
    \end{figure}

      \begin{table*}[h]
        \centering
        \begin{tabular}{lccccc}
        \toprule
        Methods & F1 & $\mathbf{Macro}$ & $\mathbf{Macro@500}$ & $\mathbf{Macro@200}$ & $\mathbf{Macro@100}$ \\
        \midrule
        ERACL   & 61.80 & 41.34 & 37.13     & 29.43     & 22.31     \\
        \hline
        -- ERA   & 61.36 & 40.49 & 36.22     & 28.61     & 21.52     \\
        -- CL    & 61.30 & 40.55 & 36.21     & 28.51     & 20.50     \\
        -- both  & 60.97 & 39.54 & 35.20     & 26.82     & 18.76    \\
        \toprule
        \end{tabular}
        \caption{Ablation Study on development set.}
        \label{tb:ablation-study}
    \end{table*}

    To better illustrate the performance gain on the tailed relations, we sort 96 relations according to their frequency count in the DocRED train set from high to low, then slice 96 relations to 10 relation clusters equally for more clear visualization. For each cluster, we calculate the cluster F1 by averaging the F1 of relation within the cluster. The results are demonstrated in Figure \ref{fig:relationF1-demo}. We observe that the proposed ERA method gain improvements compared to ATLOP on relation clusters 4-10, which correspond to the tailed relation in DocRED, and also achieve competing performance on clusters 1-3, which correspond to the head relations. Those findings show that our ERA methods are effective for improving the DocRE performance on tailed relations while keeping the performance on head relations. In addition, similar performance gain is also achieved by the proposed ERACL method, and ERACL can further improve the tailed relations compared to ERA and achieve competing performance on head relations.

    In addition, we conduct another set of experiments by manually reducing the percentage of training data in order to explore the performance of the proposed ERA methods and ERACL methods under a limited-data scenario. The results are listed in Table \ref{tb:with-few-data}. Compared to the setting that uses all of the train data, we observe that the performance gain of the proposed ERA and ERACL under 10\% and 5\% settings are more significant, which also indicate that the proposed ERA and ERACL can improve the DocRE performance by mitigating the long-tailed problem and are especially effective when training data is limited.
    \begin{table}[!h]
        \centering
        \begin{tabular}{lccc}
            \toprule
            Methods & F1 & $\mathbf{Macro}$ & $\mathbf{Macro@200}$\\
            \midrule
            \textit{10\%} &  &  &     \\
            ATLOP &51.92   &23.68  &7.97  \\
            ERA    &52.46   &24.80  &11.20   \\
            ERACL    &\bf{53.73}   &\bf{27.88}  &\bf{14.89}   \\
            \hline
            \textit{5\%} &  &  &     \\
            ATLOP    &45.17   &16.17   &5.59    \\
            ERA     &47.18  &17.27    &6.22    \\
            ERACL     &\bf{49.40}   &\bf{23.47}   &\bf{11.84}    \\
            \toprule
        \end{tabular}
        \caption{Results on the development set under the limited-data setting. 10\% refers to only using 10\% of training data, and 5\% refers to only using 5\% of training data. All results are reported by averaging 3 runs with different random seeds.}
        \label{tb:with-few-data}
    \end{table}

    Besides, we also conduct experiments on HacRED to investigate whether our ERA can generalize well on other long-tailed DocRE datasets. Results are shown on Table \ref{tb:hacred-results}. We observe that ERA can still outperform the ATLOP on tailed relations.

     \begin{table}[!h]
        \centering
        \begin{tabular}{lccc}
            \toprule
            Methods & F1 & $\mathbf{Macro}$ & $\mathbf{Macro@500}$\\
            \midrule
            ATLOP &77.84   &70.99  &55.11  \\
            ERA    &78.27   &71.73  &57.13   \\
            \hline
            \toprule
        \end{tabular}
        \caption{Results on HacRED. Since HacRED do not have distant-labeled data, we can only evaluate ERA on HacRED. ATLOP results are implemented by us. All experiments use XLM-Roberta-base as the backbone encoder.}
        \label{tb:hacred-results}
    \end{table}

\subsection{Ablation Study}
    To evaluate the contribution of the ERA and contrastive learning(CL) framework separately, we conduct an ablation study on the development set by reducing one component at a time. The results are shown in Table \ref{tb:ablation-study}. All of the results are tuned on the development set for best performance.

    Note that reducing ERA refers to turning off the relation representation augmentation operation described in Section \ref{sec:era-relation-aug} and only keeping the original relation representations. In addition, reducing CL means without conducting contrastive learning on distantly supervised data. We observe that the ERA component and contrastive learning(CL) framework are almost equally important, which lead to $0.44$ and $0.50$ performance drop on F1 metric, $0.85$ and $0.79$ performance drop on Macro F1.

\section{Conclusion}
   We propose a novel Easy Relation Augmentation(ERA) method for the Document-level Relation Extraction task, which improves the DocRE performance by addressing the long-tailed problem residing in DocRE by augmentation on relation representations. In addition, we propose a novel contrastive learning framework based on ERA, i.e., MoCo-DocRE, for unifying the augmented relation representations and improving the robustness of learned relation representations, especially for tailed relations. Experiments on the DocRED dataset demonstrate that the proposed ERA and ERACL can achieve competing performance compared to state-of-arts models, and we demonstrate that the performance gain of ERA and ERACL are mainly from the tailed relations.

    Nonetheless, addressing the long-tailed problem is still challenging for DocRE. One limitation of our method is it still relies on large amount of annotated data to achieve overwhelming performance. We hope it can be mitigated in future research.


\section{Introduction}
Research in sign language has focused mainly on supervised learning with the aims of classifying phonological parameters \cite{liaw2002classification,cooper2007large,buehler2009learning,buehler2010employing,cooper2012sign,7780781}, providing glosses for isolated signs \cite{1288342,ong2014sign,fagiani2015signer,devisign_attempt,mocialovtowards,8622141,tornay2019hmm}, or translation of signed utterances that consist of multiple signs to written languages \cite{neidle2012new,8614068,cihan2018neural,ko2019neural}.

Despite the field being mainly approached with supervised methods, few attempts have been made to model sign language using unsupervised methods \cite{papapetrou2009mining,ostling2018visual} and these are mainly for data mining.

The aim of this work is to exploit sign language resources available on social media and cluster segmented phonemes without access to transcriptions during clustering. Two clustering methods are compared, one is the general DBSCAN clustering method \cite{witten2002data} and another one is iterative grouping clustering method. Experiments show that it is possible to find similar phonemes in continuous signing data using clustering approach with linguistically liable distance metric based on phonological parameters.
\\

\section{Related Work}
Deldjoo et al. \shortcite{deldjoo2016content} build a recommendation system based on the extracted visual features from the videos, such as lighting, colour, and motion. Snoek et al. \shortcite{snoek2009concept} and Hu et al. \shortcite{hu2011survey} identify colour, texture, shape, objects, and movements as features to serve as a basis for video indexing and retrieval. Furthermore, the extracted features can be grouped across the temporal dimension and used for querying similar groups during data mining. Other methods create specialised groups, such as human actions and can vary depending on the application. Unknown patterns within the groups are usually found through clustering.

Karypis et al. \shortcite{karypis2000comparison} identify bottom-up and top-down approaches to clustering. In the bottom-up approach, every element is assigned to an individual cluster and then clusters are merged in the iterative process. In the top-down approach, every element is in the same cluster and then the cluster is split into different clusters. The merging and splitting are done using a similarity metric with bottom-up approach being more common. Cluster quality can be assessed by measuring the inter-cluster entropy or relationship between the precision and recall. When no external information about the clusters is available, the inter- and intra-cluster cohesion can be used to evaluate the quality of the clusters \cite{corral2006cohesion}.

Ert{\"o}z et al. \shortcite{ertoz2003finding} describe a range of clustering methods, outlining their advantages and disadvantages and pointing out to the fact that it is difficult to design a clustering algorithm that would be able to identify non-globular clusters of different sizes in the presence of outliers without having a bias towards one or another type of clusters. Moreover, by increasing the dimensionality of the data that needs to be clustered, the similarity metric becomes more uniform, which leads to poor clustering.

Recently, Dwibedi et al. \shortcite{Dwibedi_2020_CVPR} used pre-trained ResNet \cite{he2016deep} for image recognition in an end-to-end model that generates embeddings for each frame of a video, which are then used in generating affinity matrix for the whole video. Finally, the model uses Transformer architecture \cite{vaswani2017attention} for predicting whether each frame belongs to a repetition or not. This process is more general and can be applied to any video in order to find repetitions in that video.

Despite the necessity for general purpose video clustering methods, this work extracts linguistic information from the signing videos during the pre-processing, reducing the data complexity and clustering linguistic features specific to sign languages.

\section{Data}\label{sec:data}
Four videos of different signers interpreting the song `Halo' by Beyoncé in the American Sign Language (ASL) were collected from YouTube with average time length of 4 minutes 22 seconds. The audio of the song plays in the background, the lyrics of which were used as ground truth when referring to the translation of what is being signed in the videos due to no knowledge of ASL.

\begin{figure}[H]
    \centering

    \includegraphics[width=0.25\textwidth]{pics/im1}
    \includegraphics[width=0.25\textwidth]{pics/im4}
    \\

    \includegraphics[width=0.25\textwidth]{pics/im2}
    \includegraphics[width=0.25\textwidth]{pics/im3}
    \caption{Screenshots from the four ASL interpreters of the song `Halo' by Beyoncé from YouTube.}
    \label{fig:data_screenshots}
\end{figure}

Figure \ref{fig:data_screenshots} shows screenshots from the four collected videos. Due to the fact that the data is collected from online resources, it is more unpredictable than the corpora as described in \cite{Schembri2013BuildingTB,troelsgaard2008electronic,crasborncorpus} that was collected in controlled environments. After a short qualitative analysis of the collected videos, the following factors were noted to vary across videos:\\
\begin{minipage}{.24\textwidth}
\vspace{1em}
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
    \item Video aspect ratio
    \item Video quality
\end{itemize}
\vspace{1em}
\end{minipage
\begin{minipage}{.24\textwidth}
\vspace{1em}
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
    \item Camera proximity
    \item Background
\end{itemize}
\vspace{1em}
\end{minipage}
\begin{minipage}{.24\textwidth}
\vspace{1em}
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
    \item Body orientations
    \item Dialects
\end{itemize}
\vspace{1em}
\end{minipage}
\begin{minipage}{.24\textwidth}
\vspace{1em}
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
    \item Signing fluency
\end{itemize}
\vspace{1em}
\end{minipage}\\
This work takes advantage of the nature of the data since music usually has verses, which repeat themselves over a course of a song. This is useful when performing clustering since it can be assumed that every verse could belong to the same cluster.

\section{Methodology}
\begin{figure}[H]
    \centering
    \includegraphics[trim={3.5cm 22cm 3.5cm 5cm},clip,width=0.7\textwidth]{pics/Methodology.pdf}
    \caption{Methodology steps}
    \label{fig:my_label}
\end{figure}

\subsection{Pose Estimation}
We process raw signing video and estimate the pose and the hand of a signer by using the OpenPose pose estimation library \cite{wei2016cpm,simon2017hand,cao2017realtime,cao2018openpose}. The library detects 2D anatomical key-points, associated with the human body and hands in every frame. The library provides $21$ (x,y) key-points for every part of the hand and $25$ key-points for the whole body skeleton.

Due to the fact that there are variations in videos listed in Section 3, normalisation similar to Fragkiadakis et al. \shortcite{fragkiadakis-etal-2020-signing} is applied to extracted key-points to force fixed shoulder distance in all videos by resizing all \((x,y)\) positions of the inferred key-points \( (\hat{x},\hat{y})\rightarrow(x*r_x,y*r_y) \) and bring the signer to the centre of the screen by adding the difference between desired and current positions \( (x,y)\rightarrow(\hat{x}+t_x,\hat{y}+t_y) \), where \(r\) and \(t\) are the resize ratio and translation pixels. Such normalisation counteracts the fact that the signers appear at different distances away from the camera.

\subsection{Phonological Parameters}\label{sec:phonological_parameter}
Stokoe identified phonological parameters such as hand movement, hand location relative to the body, hand and extended finger orientation, and non-manual gestures such as facial expressions, all used simultaneously during signing \cite{stokoe1976dictionary}. HamNoSys \cite{hanke2004hamnosys} is one of the notation systems for sign language that has been proposed over the time to record the use of phonological parameters during signing. The notation aims to enumerate hand shape observations from all sign languages and presents combinations of palm curvature, extent of the thumb, and finger configuration to describe a handshape. As for the orientation and location phonological parameters, the orientation is split into extended finger direction and palm orientations, which can point to either of the four cardinal directions. Location, on the other hand, defines specific body parts (e.g. shoulder, head, etc.) and uses those relative body locations to identify the hand location. Movement categorises hand movement types and movement speeds. Using the key-points from the first stage, the extended finger orientation and the hand location relative to the body for both right and left hands are estimated for every frame, following the HamNoSys notation system as was reported in \cite{mocialov2020towards}. The orientation phonological parameter is divided into eight categories using trigonometry \(-\pi/2 < \arctan (q_y - p_y, q_x - p_x) < \pi/2 \) where \(q\) and \(p\) are the \((x, y)\) coordinates of the radius and middle finger metacarpal bones. Relative hand location is estimated using Euclidean distance between identified key-points and distance matrix is generated

\[
D =
 \begin{pmatrix}
  M_r & M_l \\
  \vdots  & \vdots  \\
  N_r & N_l
 \end{pmatrix}
\]
where \(M_{r,l} \dots N_{r,l} = \lvert q_{m \dots n}- centroid_{r,l} \rvert \) are the Euclidean distances between \( (x,y) \) body parts key-points \(q\) and \( centroid_{r,l} = (\sum_{i=1}^{N} x_{i_{r,l}} / N, \sum_{i=1}^{N} y_{i_{r,l}} / N) \) is hands centroid of all hand key-points \(N\) provided by the OpenPose library.

\subsection{Temporal Segmentation}
Using the key-points from the first stage, phonemes are segmented in a continuous signing as described in \cite{Mocialov2017TowardsCS}. The method splits continuous signing by tracking \(centroid_{r,l}\) speed \(f\) and making a split at time \(t\) when the hand movement either slows down or accelerates \(\sign(f'(t-1)) \neq \sign(f'(t))\) as it has been observed that the signing speed is different from that of the epentheses.

\subsection{Clustering}\label{sec:clustering}
\begin{figure}[H]
\centering
    \begin{tikzpicture}
    \node[anchor=south west,inner sep=0] at (2,0) {\includegraphics[width=0.45\textwidth,trim={3cm 20cm 6cm 5cm},clip]{pics/distances_metrics.pdf}};

    \node[very thick] at (3,0) {Location Categories};
    \node[very thick] at (7,0) {Orientation Categories};
    \end{tikzpicture}
    \caption{Categories for distances for both location and orientation phonological parameters}
    \label{fig:cluster_distances}
\end{figure}

The similarity of two phonemes ($p_n \sim^{T} p_m$) is then evaluated by comparing their phonological parameters using a threshold value $T$. Both phonemes should have similar phonological parameters (\mbox{$p_n$ $\subsetneq^T$ $p_m$ $\wedge$ $p_m$ $\subsetneq^T$ $p_n$}) for the phonemes to be considered similar.

\[
\exists p_n, p_m \in P, p_n \sim^{T} p_m \iff p_n \subsetneq^T p_m \wedge p_m \subsetneq^T p_n
\]

To realise the comparison of the phonemes, the weighted Levenshtein distance \cite{rajalingam2011hierarchical} is used to measure the difference between two phonemes, which finds the minimum number of edits where an edit can be a substitution or deletion of phonological parameter and the weights determine the cost of such edits. Since the majority of clustering algorithms operate on the affinity matrices, where every item corresponds to a distance between the two items, a distance metric is needed for the orientation and location phonological parameters. The orientation phonological parameter is divided into eight equal ranges, as described in Section \ref{sec:phonological_parameter}, while the location phonological parameter is divided into three ranges (eye, shoulder, abdomen levels). Therefore, the orientation distance range is between 0 and 4 while the location distance range is between 0 and 2, as shown in Figure \ref{fig:cluster_distances}. Distances between the two items also become the weights for weighted Levenshtein distance matrix.

Since there is no way of knowing how many similar phonemes there are in a video prior to watching the video, the clustering approach selected should not assume the number of clusters. Two clustering methods will be compared. The first clustering method is an iterative grouping clustering, which iterates a list of phonemes, compares them and puts the two similar phonemes into the same cluster and repeats until all the phonemes are have been iterated. The second clustering method is the general clustering method DBSCAN. This density-based clustering method searches its neighbourhood for the members of the same cluster and can detect arbitrary-shaped cluster shapes. For the DBSCAN, the number of samples in the neighbourhood was modified \([1-5]\) for an item to be considered a core item using fixed \(\epsilon = 0.5\) since the largest distance between the two phonemes is in \([0-1]\) range. The complexity of both algorithms is $\bigO(n^2)$ \cite{schubert2017dbscan}.

\subsection{Matching Consecutive Sequences of Phonemes}
Phonemes carry little to no linguistic meaning when viewed separately as they are very short (majority of 3 frames length as shown in Figure \ref{fig:phonemes}). Therefore, the same phoneme similarity measure, as described in Section \ref{sec:clustering} is applied to a chain of consecutive phonemes in an attempt to find similar signs or even phrases in continuous signing videos. This approach works in an iterative manner. The list of phonemes is iterated and each combination of consecutive phonemes is compared to another combination of consecutive phonemes elsewhere in the video, combining consecutive phonemes if they are similar. The process is repeated until no new combinations are found.

\section{Results}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{pics/phonemes.png}
    \caption{Total number phonemes for each video and relative phoneme sizes measured in number of frames}
    \label{fig:phonemes}
\end{figure}

Figure \ref{fig:phonemes} shows the total number of phonemes for each video, as well as, the number of phonemes of particular lengths measured in the number of frames for each video. The figure shows that using the same phoneme segmentation method on different videos produces slightly different results. For example, video 4 has fewer phonemes identified for the right hand as compared to other 3 videos. Similarly, video 1 has fewer phonemes identified for the left hand than other 3 videos. Moreover, the largest share of the overall number of phonemes belongs to the short phonemes consisting of three and six frames, while the average sign length has been reported to be of 3 seconds, or 75 frames in \cite{lichtenauer2008sign}.

\subsection{Phoneme Clustering Analysis}
This section shows how relaxing the phoneme similarity metric defined in Section \ref{sec:clustering}, affects the number of clusters and the cluster sizes with both the DBSCAN and the proposed grouping methods.

Figure \ref{fig:clusters} (a) shows identified clusters and their average sizes with varying phoneme similarity threshold. Setting the threshold to 0\%, puts all the phonemes in one cluster, whereas setting the threshold to 100\% results in almost every phoneme being assigned to an individual cluster. This means that throughout each video, there are very few similar phonemes using proposed distance metric. This supports the fact that sign languages are fluid and the same sign can have inter-signer \cite{lucas2002location} as well as intra-signer \cite{bhuyan2006continuous} variations.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.49\textwidth]{pics/clusters.png}
    \includegraphics[width=0.49\textwidth]{pics/dbscan_clustering.png}
    (a) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (b)
    \caption{Number of clusters and average cluster size using grouping clustering method with different similarity thresholds (a) and using DBSCAN clustering method with different neighbourhood sizes (b).}
    \label{fig:clusters}
\end{figure}

Similar behaviour is observed when clustering using the DBSCAN method, as can be seen in Figure \ref{fig:clusters} (b). As the neighbourhood size decreases, the number of clusters increase. However, it is important to notice the rate of change in the average cluster size as the similarity thresholds change (convex vs concave curve shape). Similarly, the rate of change in number of clusters is not as steep when clustered using the DBSCAN method (25\%-75\% vs 4-2 neighbours). This shows that the DBSCAN produces clusters where the number of phonemes are more uniformly distributed than with the grouping clustering method.

\subsection{Quantitative Clustering Evaluation}
Both DBSCAN and the proposed grouping clustering methods are compared using the Silhouette metric \cite{rousseeuw1987silhouettes}. The Silhouette metric has been deemed to resemble human judgement \cite{lewis2012human}. The metric is bound in range \([1,-1]\) with $1$ signifying a good clustering results and $-1$ indicating that the items in a cluster are assigned to the wrong cluster. $0$ represents many overlapping clusters in the data, which makes clustering challenging.

Figure \ref{fig:out_method} (a) shows how the Silhouette metrics changes with respect to the phoneme similarity threshold when using the proposed grouping clustering method. As the threshold is becoming more restrictive, identified clusters become clustered better at the expense of increasing number of clusters (Figure \ref{fig:clusters}). Figure \ref{fig:out_method} (b) shows DBSCAN's clustering performance with respect to the number of neighbours while having \(\epsilon=0.5\). The Silhouette coefficient is more volatile to the neighbourhood size and the number of identified clusters increases as the neighbourhood becomes smaller.

What is worth noting is that for every video, the proposed grouping clustering method has relatively similar Silhouette value while DBSCAN at \mbox{$neighbourhood=2$} and \mbox{$neighbourhood=3$} has very different Silhouette values for each video, which makes it unpredictable to use in the general case. On the other hand, having more uniformly distributed cluster sizes at different thresholds and relatively good Silhouette metric makes it an attractive clustering option for sign language data.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.49\textwidth]{pics/out_method.png}
    \includegraphics[width=0.49\textwidth]{pics/dbscan.png}
    (a) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (b)
    \caption{Silhouette clustering evaluation metric applied to grouping clustering algorithm at various similarity thresholds (a) and DBSCAN clustering algorithm with different neighbourhood sizes (b)}
    \label{fig:out_method}
\end{figure}

\subsection{Qualitative Clustering Evaluation}
This section shows example phonemes from different clusters when clustered using the grouping method with the similarity threshold set to 50\%.

Figure \ref{fig:all_clusters} shows visualisation of all the clusters for a single video when plotting two principal components on (x,y) axes. Clusters are identified using the iterative grouping method with 50\% threshold. Figures below show two examples for each region of interest (red and violet).

\begin{figure}[H]
\centering
    \begin{tikzpicture}
    \node[anchor=south west,inner sep=0] at (2,0) {\includegraphics[width=0.5\textwidth,trim={4cm 4cm 4cm 4cm},clip]{pics/clusters_video_1_0.5_0.5.png}};
    \draw[draw=red,line width=0.7mm] (4.2,5.5) rectangle ++(0.6,0.6);
    \node at (3,6) {\shortstack[l]{Phonemes\\belonging to\\cluster A}};
    \draw[draw=violet,line width=0.7mm] (6.8,0.9) rectangle ++(0.55,0.55);
    \node at (9,0.5) {\shortstack[l]{Phonemes\\belonging to\\cluster B}};
    \end{tikzpicture}
    \caption{Single video phonemes clustered using iterative grouping method with 50\% threshold where each cluster has a distinct colour}
    \label{fig:all_clusters}
\end{figure}

From the Figures \ref{fig:visual1} and \ref{fig:visual2} it can be seen that the phonemes are visually similar where every phoneme is described with the location and orientation phonological parameters. It is worth noting that the meaning can or cannot be the same, but the phonological parameters are similar having at least 50\% phoneme similarity.

\begin{figure}[H]
    \centering
    \shortstack[c]{\vspace{0.7cm}(a)} \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_1.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_2.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_3.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_4.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_5.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_6.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2/video_1_cluster_2_7.jpg}

    \shortstack[c]{\vspace{0.7cm}(b)} \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/1.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/2.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/3.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/4.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/5.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/6.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster2_2/7.jpg}
    \caption{Two similar phonemes (Frames 1196-1202 for the phoneme (a) \& 3556-3562 for the phoneme (b)) from cluster A (red). Phoneme (a) being a part of the `I found a way to let you in' lyrics and phoneme (b) being a part of the `to pull me back to the ground again' lyrics.}
    \label{fig:visual1}
\end{figure}

\begin{figure}[H]
    \centering
    \shortstack[c]{\vspace{0.7cm}(a)} \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/1.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/2.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/3.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/4.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/5.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/6.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1_2/7.jpg}

    \shortstack[c]{\vspace{0.7cm}(b)} \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_1.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_2.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_3.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_4.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_5.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_6.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/vid1_cluster1/video_1_cluster_1_7.jpg}
    \caption{Two similar phonemes (Frames 4736-4742 for the phoneme (a) \& 7126-7132 for the phoneme (b)) from cluster B (violet). Phonemes (a) and (b) being a part of the `Halo, halo' lyrics.}
    \label{fig:visual2}
\end{figure}

\subsection{Matching Consecutive Sequences of Phonemes}
Single video is chosen to search for similar consecutive phonemes in different parts of the video. The lyrics in the background music in the video are used as the ground truth for verifying the results. Phoneme similarity threshold is chosen to be 50\%.

\begin{figure}[H]
    \centering
    \shortstack[c]{\vspace{0.7cm}(a)} \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/1.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/2.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/3.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/4.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/5.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/6.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/2/7.jpg}\hspace{-1em}

    \shortstack[c]{\vspace{0.7cm}(b)} \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/1.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/2.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/3.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/4.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/5.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/6.jpg}\hspace{-1em}
    \includegraphics[width=0.13\textwidth,trim={5cm 1cm 5cm 1cm},clip]{pics/match_vid1/1/7.jpg}\hspace{-1em}

    \caption{Two similar combinations of consecutive phonemes (Frames 5012-5207 for consecutive phonemes (a) \& 2451-2839 for consecutive phonemes (b)) corresponding to the same lyrics:}
    \label{fig:visual4}
\end{figure}

\begin{table}[H]
\vspace{-2em}
    \centering
    \begin{tabular}{l}
        \qquad\qquad\qquad\qquad\qquad\qquad\qquad  ``I can feel your Halo, Halo, Halo. I can see your Halo, Halo, Halo \\
        \qquad\qquad\qquad\qquad\qquad\qquad\qquad  \; I can feel your Halo, Halo, Halo. I can see your Halo, Halo, Halo''
    \end{tabular}
    \caption*{}
\end{table}

As a result it can be seen that the same phoneme similarity approach described in Section 4.4 can be used to find similar consecutive phonemes in the same video as shown in Figure \ref{fig:visual4}, where consecutive phonemes in (a) and consecutive phonemes in (b) correspond to the same lyrics from the song.

\section{Conclusion}
This work explored phoneme clustering for continuous signing videos obtained online using only location and orientation phonological parameters for phoneme comparison. An iterative grouping method and the DBSCAN methods were compared, showing that the DBSCAN is more unpredictable for the same signed content when the phoneme similarity conditions (neighbourhood) are relaxed. Nevertheless, DBSCAN has a more even distribution of identified clusters and the average cluster size when similarity conditions are relaxed as compared to the iterative grouping method. This work has shown that it is possible to use a linguistically viable distance metric for general purpose clustering algorithms to work on sign language data. To improve the clustering approach, it would be beneficial to include other phonological parameters, such as handshape and even non-manual features. In the future all the obtained interpretation videos for the same song will be clustered in order to compare phonemes from the same clusters across the different signers.

The benefit of using clustering on music videos is that it is possible to identify repeating patterns in videos, which correspond to verses in music. This knowledge can be used to generate datasets for the computational sign language models as more and more song interpretations in sign languages performed by different signers become available online. Moreover, such phoneme clustering approaches could be used during the resource annotation for linguistic purposes. Similar phonemes, signs, and even phrases could be identified in continuous signing videos prior to watching such videos.

\bibliographystyle{coling}


\section{Estimation of resolution on the future $Z$ factory}
 The resolution of the measurement $\sigma(\ensuremath{\phi_s}\xspace)$ is proportional to the inverse square root of the signal statistic. The signal statistic is proportional to the number of $b\bar{b}$ pairs produced in a collider.
And it is also proportional to the acceptance and efficiency of the detector.
Two other effects have a significant impact on resolution.
One is the ability to determine the initial flavor of the $B_s$ or $\bar{B}_s$ meson, which is called the flavor tagging power $p$.
The other effect is the resolution in measuring the decay time $\sigma_t$.
It is shown that the tagging power and the resolution of the decay time affect the $\sigma(\ensuremath{\phi_s}\xspace)$ in the formats $\sigma({\ensuremath{\phi_s}\xspace}) \propto 1/\sqrt{p}$ and $\sigma({\ensuremath{\phi_s}\xspace}) \propto 1/\exp({-\frac12\Delta m_{s}^2\sigma_t^2})$. The effect of tagging power and time resolution on $\sigma(\ensuremath{\phi_s}\xspace)$ is investigated in [] and validated with some toy Monte Carlo simulations.
 A scaling factor can be defined as
\begin{equation}
	\label{eq:scaling}
	\xi = 1/\left(\sqrt{N_{b\bar{b}}\times\varepsilon}\times\sqrt{p}\times\exp({-\frac12\Delta m_{s}^2\sigma_t^2})\right)
\end{equation}

The expected $\ensuremath{\phi_s}\xspace$ resolution measured in future $Z$-factories can be estimated as $\sigma(\ensuremath{\phi_s}\xspace,\mathrm{ FE }) = \xi_{\mathrm{ FE }}\times\frac{\sigma(\ensuremath{\phi_s}\xspace,\mathrm{ EE })}{\xi_{\mathrm{ EE }}}$. (FE: future experiment, EE: existing experiment).

The resolution and scaling factor of the existing experiment are from the LHCb studies~\cite{LHCb:2019nin}. For the LHCb measurement, the number of extracted signals is $N_{b\bar{b}}\times\varepsilon$ = \ensuremath{117000}. The flavor tagging power $p$ is \ensuremath{4.73\%}. And the decay time resolution $\sigma_t$ is at \ensuremath{45.5~\mathrm{fs}}. The resolution $\sigma(\ensuremath{\phi_s}\xspace)$ is \ensuremath{0.041~\mathrm{rad}}. Then the scale factor $\xi_{\text{lhcb}} = \ensuremath{0.018}$ and the ratio $\sigma(\ensuremath{\phi_s}\xspace)/\xi_{\text{lhcb}} = \ensuremath{2.28}~\mathrm{rad}$.

The scaling factor of the future $Z$-factory is estimated using the Monte Carlo study, which is described in detail in the following sections.

It is also worthwhile to estimate the scaling factor of the experiments at the High-Luminosity LHC. Assuming no significant changes in detector acceptance and efficiency, tagging power, and decay time resolution at HL-LHC, the scaling factor is calculated by scaling the luminosity. At HL-LHC, the expected luminosity is $300~\mathrm{fb^{-1}}$, with respect to $1.9~\mathrm{fb^{-1}}$ at the current measurement of LHCb. The scaling factor is then $\xi_{\text{ HL-LHC -LHCb}}=\ensuremath{0.0014}$ and the expected resolution is $\sigma(\phi_s,\text{ HL-LHC -LHCb})=\xi_{\text{ HL-LHC -LHCb}}\times\sigma(\ensuremath{\phi_s}\xspace)/\xi_{\text{lhcb}} = 3.2~ \mathrm{mrad}$.

The expected resolution of $\Delta \Gamma$ and $\Gamma_s$ is scaled in the same way from previous measurements. The key difference with $\ensuremath{\phi_s}\xspace$ is that they are insensitive to the tagging power and proper decay time resolution. The variable
\begin{equation}
	\label{eq:scaling2}
	\zeta = 1/\left(
	\sqrt{N_{b\bar{b}}\times\varepsilon}
	\right)
\end{equation} is introduced as the scaling factor for $\Gamma_s$ and $\Delta_s$. The scaling factor $\zeta_{\text{lhcb}} = 2.9\times10^{-3}$,

\subsection{CEPC and the baseline detector}
The CEPC and the baseline detector (CEPC-v4)~\cite{cepc2018cepc} are taken as an example to study the resolution of $\ensuremath{\phi_s}\xspace$.
As a baseline, we assume that the CEPC will run in the Tera-$Z$ mode, i.e., produces $10^{12}$ $Z$ bosons during its lifetime.
The geometry of the CEPC baseline detector consists of a vertex system, a silicon inner tracker, a TPC, a silicon external tracker, an electromagnetic calorimeter, an Hadron calorimeter, a solenoid of 3 Tesla, and a Return Yoke.

\subsection{Monte carlo sample and reconstruction}
\label{sec:MC}
A Monte Carlo sample is generated to study the geometry acceptance and reconstruction efficiency of the $\ensuremath{B_{s}\rightarrow J/\psi \phi}\xspace$ decay channel. Another utility of this sample is to investigate the proper decay time resolution of the $B_{s}$, which is directly related to the spatial resolution of the $B_{s}$ decaying vertex.

Using the WHIZARD\cite{whizard} generator, about 6000 $Z\rightarrow b\bar{b} \rightarrow B_{s}(\bar{B}_{s})+X$ events are generated. The $B_s$ particles are then forced to decay via the $B_s\rightarrow J/\psi(\rightarrow \mu^+ \mu^-)\phi(\rightarrow K^+ K^-)$ decay channel, which is performed with PYTHIA ~\cite{pythia}. The standard configurations are used for the decay of the other particles. The transport of the particles in the detector is then simulated with MokkaC based on the GEANT4~\cite{agostinelli2003geant4} transport code. Then they are reconstructed into tracks.

The reconstructed particle species are identified with the Monte Carlo truth information. Since the detector is very good at distinguishing between leptons and hadrons, if the species of the true particle is a muon or electron, the track is identified as a lepton. And if the species of the true particle is a charged kaon, pion or proton, the track is identified as a hadron.

Further identification of the hadron as a kaon, pion, or proton is somewhat more difficult for a real detector. To avoid losing too much signal due to the efficiency of particle identification, the PID cuts are not applied in the reconstruction of the $B_{s}$ particles.
The $J/\psi$ candidates are reconstructed from all combinations of a positively charged muon and a negatively charged muon, and they are selected within the window of invariant mass from $\ensuremath{3.07}$ to $\ensuremath{3.14}$~$\mathrm{GeV}/c^2$.
The $\phi$ candidates are reconstructed by all combinations of a positively charged hadron and a negatively charged hadron. The invariant mass of the $\phi$ meson is calculated assuming that the mass of the hadron is equal to the mass of the kaon.
The $\phi$ candidate is selected within the mass window from \ensuremath{1.017}~ to \ensuremath{1.023}~$\mathrm{GeV}/c^2$. The $B_s$ meson is reconstructed over the combination of all $J/\psi$ and $\phi$ candidates.
And these are selected within a mass window from $\ensuremath{5.28}$ to $\ensuremath{5.46}$~$\mathrm{GeV}/c^2$.
After the reconstruction of the $B_s$ meson, a decaying vertex is reconstructed with the tracks associated with the $B_s$ particle.

The sample is also used to estimate the flavor tagging power. For this purpose, only truth-level information is passed to the flavor tagging algorithm, i.e., assuming that we have perfect particle identification.

At the same time, a sample of $Z\rightarrow b\bar{b}\rightarrow X$ is generated to verify a low background level. The detector simulation and event reconstruction procedure are the same as for the signal.

\subsection{Signal and background statistics}
The branching fraction of $b\bar{b}$ hadronized to $B_s$ is 10\%.
At first order, we assume that all $b\bar{b}$ events can be selected with high purity. The background in this study is the $b\bar{b}$ events that do not contain $\ensuremath{B_{s}\rightarrow J/\psi \phi}\xspace$ signal. The branching ratio of $\ensuremath{B_{s}\rightarrow J/\psi \phi}\xspace$ is $1.08\times10^{-3}$. And the branching ratio of $J/\psi\rightarrow\mu^+\mu^-$, $\phi\rightarrow K^+ K^-$ are $6\%$ and $50\%$ separately. The number of background events is $1.7\times10^{5}$ times larger than the number of signal events.
The selection criteria described in section~\ref{sec:MC} are applied to the background sample. It is shown that the probability of reconstructing a fake $B_s$ candidate is $6.7\times10^{-6}$. After the event selection, background has the same magnitude as the signal, which is far from satisfactory.

The vertex information is another power variable to supress the backgrounds. Because in the background, the candidates come from four arbitrarily combined tracks, two of which are lepton tracks and two of which are hadron tracks. Normally, the lepton has a small impact parameter and the hadron has a large impact parameter. It is difficult to reconstruct a high-quality vertex with arbitrarily combined tracks. The figure shows the $\chi_{xy}^2$ distribution of the signal
where
\begin{displaymath}
\chi_{xy}^2 = \sum_\mathrm{tracks} d_{xy}^2.
\end{displaymath}
The $d_{xy}$ in the formula represents the distance from the reconstructed vertex to the track in the $xy$ plane.
For most signals, the vertex $\chi_{xy}^2$ is very small. For backgrounds, on the other hand, $\chi_{xy}^2$ is distributed over a large area.
With a very loose cut at $\chi_{xy}^2 < 0.1$, $95\%$ of the signals are selected and $99.2\%$ of the backgrounds are discarded.
\begin{figure}[!hbt]
\begin{center}
\includegraphics[width=0.8\textwidth]{chi2.pdf}
\end{center}
\caption{$\chi_{xy}^2$ distribution of the signal.}
\label{fig:chi2}
\end{figure}

With a combination of invariant mass and vertex cut, the acceptance and efficiency of the signal are $75\%$, and the background is controlled in the $1\%$ of the signal level.

\subsection{Flavor tagging}
To extract the parameters from the equation~\ref{eq:BsJPsiPhi}, one needs to know the initial flavor ($B_s$ or $\bar{B}_s$) of the parent particle, which is called flavor tagging. In experiment, it is not always possible to determine the initial flavor, and sometimes the flavor can be determined incorrectly. The fraction of particles that could be identified (correctly or incorrectly) is called the tagging efficiency $\varepsilon$. The proportion of misidentified particles among the identified particles is referred to as the misidentification rate $\omega_\mathrm{tag}$. The inability to identify the initial flavor and misidentification both reduce the ability to extract parameters from the fit. The effective statistic is lowered by a factor of $p$ compared to perfect tagging, where
\begin{displaymath}
	p = \varepsilon_\mathrm{tag}(1-2\omega_\mathrm{tag})^2.
\end{displaymath}

\subsubsection{Flavor tagging algorithm}
A simple algorithm is developed to identify the initial flavor of the particle. Rather than knowing the limit of flavor tagging ability. The algorithm is intended to show a realistic estimate of the tagging power. The idea of the algorithm is as follows:

The $b$($\bar{b}$) quarks are predominantly produced in $b\bar{b}$ pairs that fly to the opposite side in space. The flavor of the opposite $b$ quark can be used to determine the initial flavor of the interested $B_s$. To judge the flavor of this opposite $b$ quark, we take a lepton and a charged kaon with maximum momentum in the opposite direction of the $B_s$. The charge of the lepton and the kaon provides the flavor of the opposite $b$ quark.
Furthermore, when the $b$ quark is hadronized to a $B_s$ meson, another $s$ quark is spontaneously created, which then has the chance to become a charged kaon, flying in the similar direction as the $B_s$. Based on this kaon, one can identify the flavor of the particle. The algorithm simply takes the particle with the largest momentum. If these particles provide different determinants for the flavor, the algorithm simply says that it cannot identify the flavor.

\subsubsection{Flavor tagging power}
The algorithm is applied to a Monte Carlo truth-level simulation, assuming perfect particle identification. With the tagging algorithm, the tagging efficiency is estimated as 67\%. The miss-tagging rate is 22.5\%. Thus, the tagging power is estimated to be 20.2\%.

If the particle identification is imperfect, the flavor tagging power decreases. The effect is studied by randomly misidentifying some particles. A pion is identified as a kaon with probability $\omega/2$, and it has probability $\omega/2$ to be identified as a proton. The probability of being correctly reconstructed is $1-\omega$. A kaon also has a $\omega/2$ chance of being identified as a pion and a $\omega/2$ chance of being identified as a proton. The probability of a proton being identified as a proton or a kaon is also $\omega/2$ in each case.

The tagging power varying with the correct particle identification rate $1-\omega$ is shown in Figure~\ref{fig:pid_tag}.
It can be seen that the tagging power is sensitive to the $\omega$ parameter.
\begin{figure}[!hbt]
\begin{center}
\includegraphics[width=0.8\textwidth]{tagging_power.pdf}\end{center}
\caption{Tagging power as a function of the correct particle identification rate~$1-\omega$.}
\label{fig:pid_tag}
\end{figure}

\subsection{Time resolution}
The measurement accuracy of $\ensuremath{\phi_s}\xspace$ is affected by the inaccurate determination of the time resolution. It is powered by the factor $\exp(-\frac12 \Delta m_s^2 \sigma_t^2)$, where $\sigma_t$ is the resolution of the proper decay time. The proper decay time of the $B_s$ particle is calculated from the vertex position and momentum of the $B_s$ particle as follows:
\begin{displaymath}
	t_{xy} = \frac{ml_{xy}}{p_{\mathrm{T}}},
\end{displaymath}
 where $l_{xy} = \sqrt{x^2+y^2}$ is the vertex position.

Figure~\ref{fig:time_res} shows the distribution of the difference between $t_{\text{reco}}$ and $t_{\text{sim}}$, where $t_{\text{reco}}$ is the proper decay time calculated from the reconstructed particle information, and $t_{\text{sim}}$ is obtained with the Monte Carlo simulated particle information without considering the detector effects.

The distribution is fitted using the sum of three Gaussian functions with the same mean value.
The effective time resolution is combined as
\begin{displaymath}
\sigma_{\text{eff}}=\sqrt{
-\frac{2}{\Delta m_s^2}\ln(\sum_i f_i e^{-\frac{1}{2}\sigma_i^2\Delta m_s^2})
},
\end{displaymath}
where $f_i$ and $\sigma_i$ are fraction and width of the i-th Gaussian function. The obtained effective resolution of the decay time is ${4.7~\mathrm{fs}}$.

The CEPC detector is expected to achieve a proper time resolution around 10 times better than the current LHCb. For one reason, the CEPC has a excellent vertex detector and a precise tracker. For another reason, the $B_s$ produced from $Z$-decay is energetic resulting in a smaller proper time resolution.

\begin{figure}[!hbt]
\begin{center}
\includegraphics[width=0.8\textwidth]{distime.pdf}
\end{center}
\caption{distribution of $t_\text{reco}-t_\text{sim}$. The distribution is fitted with the sum of three Gaussian functions with equal mean.}
\label{fig:time_res}
\end{figure}

\begin{comment}
The \ensuremath{\phi_s}\xspace parameter appears in the $a_k, b_k, c_k, d_k$ parameters of the fitting function.

And that terms are nearly linear with \ensuremath{\phi_s}\xspace(If they have \ensuremath{\phi_s}\xspace in the first order expansion.) So to study the effects on the parameter from the resolution of t. We did a simple MC study by fitting a function of $h = \phi_s \cos(\Delta m_s t)$. The resolution of $\phi_s$ follows $1/\exp(-\frac12 \Delta m_s^2 \sigma_t^2)$:
\end{comment}

\begin{comment}
$\Delta m_s=17.757\times10^12  \hbar s^{-1}$

	LHCb: $\sigma_t=50 fs \rightarrow 0.67$

	CEPC: $\sigma_t=10 fs \rightarrow 1$

	It is a conservative assumption that the SV reconstruction is 10 times worse than PV reconstruction.
We also need that study from direct simulation.
\end{comment}
\section{Introduction}
It is suggested that the New Physics may have a major impact on the CP-violating observables.
The CP violation provides a powerful tool to test the Standard Model (SM).
The CKM matrix describes the mixture of mass and interaction eigenstates of quarks~\cite{Cabibbo:1963yz,Kobayashi:1973fv}.
In the study of $B_{s}$ meson decays,
the CP-violating phase \ensuremath{\phi_s}\xspace arises from the interference between the amplitude of the $B_{s}$ and $\bar{B}_{s}$ decays, where the $\bar{B}_{s}$ comes from the $B_{s}$--$\bar{B}_{s}$ oscillation.
In the SM, the \ensuremath{\phi_s}\xspace can be derived as $\ensuremath{\phi_s}\xspace = -2 \beta_s$, where the $\beta_s \equiv \arg[-(V_{ts}V^*_{tb})/(V_{cs}V^*_{cb})]$, expressed  as CKM matrix elements, if the subordinate contribution is ignored.

The light (L) and heavy (H) mass eigenstates of the $B_s$ meson have different decay widths $\Gamma_L$ and $\Gamma_H$. The difference of the decay width $\Delta\Gamma_s \equiv \Gamma_L - \Gamma_H$ and the average decay width $\Gamma_s \equiv (\Gamma_L + \Gamma_H)/2$ are also of great interest in theory. They can be calculated using heavy quark expansion (HQE) theory~\cite{HQE}. The precise measurements provide a test of the HQE theory.

With the discovery of the Higgs boson in 2012, the Circular Electron-Position Collider (CEPC) and Future Circular Collider (FCC-ee) projects were proposed. In addition to being designed as Higgs factories, they can also be operated in the $Z$ pole configuration. At the $Z$ pole, they are expected to produce $10^{12}$ to $10^{13}$ $Z$ bosons in 10 years.
It is estimated that $0.152\times(10^{12}-10^{13})$ $b\bar{b}$ pairs will be produced from $Z$ decays. This implies that the future $Z$-factories are also future $b$-factories.
The detectors (with time projection or wired chamber as the main tracker) on the CEPC and FCC-ee provide good particle identification, very precise track and vertex reconstruction, and good acceptance, making the future $Z$-factory a perfect place to study the heavy flavor physics.
\subsection{Measurement of \ensuremath{\phi_s}\xspace ($\Delta\Gamma$, $\Gamma_s$) in experiments}

The CP -violating phase $\ensuremath{\phi_s}\xspace$ was measured in the experiments ATLAS ~\cite{ ATLAS:2020lbz, ATLAS:2014nmm}, CDF ~\cite{ CDF:2012nqr}, CMS~\cite{CMS:2015asi}, D0~\cite{D0:2011ymu}, and LHCb~\cite{LHCb:2017hbp,LHCb:2019nin,LHCb:2014ini,LHCb:2016tuh,LHCb:2019sgv}. In these experiments, the parameter $\ensuremath{\phi_s}\xspace$ is extracted from a fit to the time-dependent angular distribution of $B_s$ decays.

If the $\ensuremath{B_{s}\rightarrow J/\psi \phi}\xspace$ decay channel is used, the distribution is a sum of ten terms corresponding to the four polarization amplitudes and their interference terms:
\begin{equation}
    \label{eq:BsJPsiPhi}
\frac{d^4\Gamma(\ensuremath{B_{s}\rightarrow J/\psi \phi}\xspace)}
{dt d\Omega}
\propto
\sum_{k=1}^{10}
h_{k}(t)f_{k}(\Omega),
\end{equation} where
\begin{displaymath}
h_k(t|B_{s}) = N_k e^{-\Gamma_s t}
\left[
a_k \cosh(\frac12\Delta\Gamma_st)  +
b_k \sinh(\frac12\Delta\Gamma_st)
+c_k \cos(\Delta m_s t) + d_k \sin(\Delta m_s t)
\right]
\end{displaymath}
\begin{displaymath}
h_k(t|\bar{B}_{s}) = N_k e^{-\Gamma_s t}
\left[
a_k \cosh(\frac12\Delta\Gamma_st)  +
b_k \sinh(\frac12\Delta\Gamma_st)
-c_k \cos(\Delta m_s t) - d_k \sin(\Delta m_s t)
\right]
\end{displaymath}
and $f_k(\Omega)$ is the amplitude function.

In the expression of $h_k(t)$, $\Delta m_{s}$ stands for the mass difference between the $B_s$ mass eigenstates and $N_k$ for the amplitude of the component at $t=0$.
The \ensuremath{\phi_s}\xspace appear in the function as parameters, hidden in the $a_k, b_k, c_k, d_k$ parameters. The extended expression of the parameters can be found in the LHCb publication~\cite{LHCb:2019nin}. The $\Delta\Gamma$ and $\Gamma_s$ can also be extracted by fitting together with $\ensuremath{\phi_s}\xspace$.

\section*{Abstracts}
The CP violating phase \ensuremath{\phi_s}\xspace, the $B_s$ decay width and the decay width difference are sensitive probe to new physics and can constrain the heavy quark expansion theory. The potential for the measurement at future $Z$ factories is studied. It is found that operating at Tera-$Z$ mode, the expected precision can reach: $\sigma(\ensuremath{\phi_s}\xspace) = 4.3~\mathrm{mrad}$, $\sigma(\Delta\Gamma) = 0.24~\mathrm{ns^{-1}}$ and $\sigma(\Gamma) = 0.072~\mathrm{ns^{-1}}$. The precision of $\ensuremath{\phi_s}\xspace$ is competitive while a little worse than the expected resolution that could be achieved by LHCb at High-Luminosity LHC. If operating at 10-Tera-$Z$ mode, all the parameters are expected to have a better precision than what it can be measured by LHCb at High-Luminosity LHC.

\input{introduction.tex}
\input{estimation.tex}

\begin{comment}
\begin{itemize}
\item CP violation arises through a single phase in the CKM quark mixing matrix.
\item In neutral B meson decays to a final state the interference between the amplitude for the direct decay and the amplitude for decay after oscillation, leads to a time-dependent CP-violating asymmetry between the decay time distributions of B and anti-B mesons.
\item $\Delta\Gamma_s \equiv \Gamma_L - \Gamma_H$, \ensuremath{\phi_s}\xspace = $-arg(-V_{ts} V_{tb}^*/V_{cs} V_{cb}^*)$
\item SM: small CPV phase-\ensuremath{\phi_s}\xspace
\item Contributions from physics beyond the SM could lead to much larger values of \ensuremath{\phi_s}\xspace.
\end{itemize}
There are quite a bit of new physics model of \ensuremath{\phi_s}\xspace prediction. One of the famous model is the AC model(arxiv: 0910.1032). In the plot, the small points construct a theory space. The red line represents the experimental measurement of the BR. The black dots represent the SM prediction of the \ensuremath{\phi_s}\xspace. The constrain of the theory means that the new physics prediction is $\sim< 0.1$ deviation from the SM prediction.
\begin{center}
\includegraphics[width=0.8\textwidth]{pred.png}
\end{center}
\end{comment}

\input{results.tex}

\section*{Acknowledgements}
We would like to thank Jibo He, Wenbin Qian, Yuehong Xie, and Liming Zhang for the help in discussion, polishing the manscript, and crossing the results.

\section{Results and discussion}

\begin{table}[!hbt]
\begin{center}
\caption{Parameters summary table}
\label{tab:results}
\begin{tabular}{cccccc}
    \hline
    & LHCb(HL-LHC) & CEPC(Tera-Z) & CEPC/LHCb& \\
    \hline
    $b\bar{b}$ statics &$43.2\times10^{12}$&$0.152\times10^{12}$
    &1/284&& \\
    Acceptance$\times$efficiency &$7\%$&$75\%$&10.7&&\\
    Br &$6\times10^{-6}$&$12\times10^{-6}$&2&& \\
    Flavour tagging${}^*$ &$4.7\%$&$20\%$&{4.3}&& \\
    Time resolution${}^*$ ($\exp({-\frac12\Delta m_{s}^2\sigma_t^2}^2$) &$0.52$&$1$&1.92&& \\
    scaling factor $\xi$ &0.0014&0.0019&0.8&& \\
    $\sigma(\ensuremath{\phi_s}\xspace)$ &$3.3~\mathrm{mrad}$&$4.3~\mathrm{mrad}$&&& \\
    \hline
    \end{tabular}
    \end{center}
\end{table}

Our simulations and estimates show that in future $Z$-factories, the proper decay time resolution can reach $4.7~\mathrm{fs}$, the detector acceptance$\times$efficiency can be as good as $75\%$, and the flavor tagging power can be $20\%$.
Assuming that the future $Z$-factory will operate in Tera-$Z$ mode (i.e., $10^{12}$ Z will be produced), the scaling factor $\xi_{ FE }$ is $0.0019$. The expected $\ensuremath{\phi_s}\xspace$ resolution is $\sigma(\ensuremath{\phi_s}\xspace,\text{ FE })=\xi_{\text{ FE }}\times\sigma(\phi_s,\text{LHCb})/\xi_\text{LHCb} = 4.3~\mathrm{mrad}$, which is competitive to $3.3~\mathrm{mrad}$, the expected $\ensuremath{\phi_s}\xspace$ measurement resolution of LHCb at the High-Lumionisity LHC.

Figure 4 shows the resolution ratio of \ensuremath{\phi_s}\xspace as a function of the tagging power and decay time resolution. The baseline resolution is with the parameters described above. The dashed red line represents the ratio for $\Gamma$ or $\Delta \Gamma$ resolution, and the solid black line represents the ratio for $\phi_s$ resolution. The ratio of $\phi_s$ is calculated analytically and the resolution of $\Delta \Gamma$ is from the toy Monte Carlo study. The ratio of $\Gamma$ is expected to be the same as that of $\Delta\Gamma$.

It is shown that when the tagging power is optimized to 30\%,
the \ensuremath{\phi_s}\xspace precision can be improved by another 20\%.
The current time resolution is already good enough and reaches the saturation point. \begin{figure}[!hbt]
\begin{center}
\includegraphics[width=0.49\textwidth]{res_time.pdf}
\includegraphics[width=0.49\textwidth]{res_tagging.pdf}
\end{center}
\label{fig:res}
\caption{The expected resolution of $\ensuremath{\phi_s}\xspace$ varies with the resolution of the proper decay time (left) and tagging power (right). The resolution is shown as the ratio between the baseline calculation and the varied calculation.}
\end{figure}

The weak dependence of tagging power and decay time on $\Gamma$ and $\Delta\Gamma$ means that the 4.3 times better flavor tagging power and 1.92 times better time resolution factor of CEPC, in contrast to $\ensuremath{\phi_s}\xspace$, have no effect on these observables. The estimated resolution is $0.24~\mathrm{ns^{-1}}$ for $\Delta\Gamma$ and $0.072~\mathrm{ns^{-1}}$ for $\Gamma$. Note that the measured resolution of $\Gamma_s-\Gamma_d = 0.0024~\mathrm{ps^{-1}}$\cite{LHCb:2019nin} is taken as the resolution of $\Gamma$ for the projection.

\begin{figure}[!hbt]
    \begin{center}
\includegraphics[width=0.7\textwidth]{phisgamma.pdf}
    \end{center}
    \label{fig:phisgamma}
    \caption{expected confidential region ($68\%$ confidential level) of $\Delta\Gamma-\ensuremath{\phi_s}\xspace$. The black dots in the paper is the Standard Model prediction. The red and blue circle represents the expected precision of Tera-$Z$ CEPC and LHCb on High-Luminosity LHC. The green circle represents the expected precision of 10-Tera-$Z$ CEPC. The black point represents the current standard model prediction. All the circles are centered at the standard model central value.}
    \end{figure}

    Figure~\ref{fig:phisgamma} shows the expected confidential range ($68\%$ confidential level) of $\Delta\Gamma-\ensuremath{\phi_s}\xspace$. The black dot in the paper is the prediction of the standard model. The red and blue circles represent the expected precision of Tera-$Z$ CEPC and LHCb at the High-Luminosity LHC. The expected precision of $\ensuremath{\phi_s}\xspace$ at the future $Z$-factory is competitive with future hadron colliders. These results change our mind about the measurement of flavor physics at the $Z$ pole. It is usually believed that the advantage of the electron position machine over the hadron collider is the decay channel with the neutrion, since the neutrion can be reconstructed at the electron position collider with missing energy. However, as shown in Table 1, the statistical disadvantage of the Tera-$Z$ $Z$ factory can be overcome with a much cleaner environment, good PID, and accurate track and vertex measurement. Without the benefits of flavor tagging and time resolution, the $\Gamma$ and $\Delta\Gamma$ resolution is much worse than expected for the LHC at high-luminosity. Only with the 10-Tera-$Z$ $Z$ factory can the expected resolution of $\Delta\Gamma$ and $\Gamma$ be competitive. This represents a requirement for the future $Z$-factory.

    Particle identification is found to be critical in this study. It is found that tagging performance degrades rapidly when particles are incorrectly identified. And with the particle identification information, the different hadrons can be distinguished to achieve a cleaner environment. The resolution of the vertex reconstruction determines the proper resolution of the decay time. It is found that the resolution is good enough to reach the saturation point. However, a good vertex reconstruction is required to rule out combinatorial backgrounds.