# RLStop: A Reinforcement Learning Stopping Method for TAR

Reem Bin-Hezam1,2<EMAIL_ADDRESS>0000-0002-9156-6186 1Department of
Information Systems
College of Computer and Information Sciences
Princess Nourah Bint Abdulrahman UniversityRiyadhSaudi Arabia and  Mark
Stevenson2<EMAIL_ADDRESS>0000-0002-9483-6006 2Department of
Computer Science
Faculty of Engineering
University of SheffieldSheffieldUnited Kingdom

(2024)

###### Abstract.

We present RLStop, a novel Technology Assisted Review (TAR) stopping rule
based on reinforcement learning that helps minimise the number of documents
that need to be manually reviewed within TAR applications. RLStop is trained
on example rankings using a reward function to identify the optimal point to
stop examining documents. Experiments at a range of target recall levels on
multiple benchmark datasets (CLEF e-Health, TREC Total Recall, and Reuters
RCV1) demonstrated that RLStop substantially reduces the workload required to
screen a document collection for relevance. RLStop outperforms a wide range of
alternative approaches, achieving performance close to the maximum possible
for the task under some circumstances.

Reinforcement Learning, Deep Reinforcement Learning, Technology Assisted
Review, TAR, Stopping Methods

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
47th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 14–18, 2024; Washington, DC, USA††booktitle:
Proceedings of the 47th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’24), July 14–18, 2024,
Washington, DC, USA††doi: 10.1145/3626772.3657911††isbn:
979-8-4007-0431-4/24/07††submissionid: 1932††ccs: Information systems
Retrieval effectiveness††ccs: Information systems Retrieval efficiency

##  1\. Introduction

Identifying all, or a significant proportion of, the relevant documents in a
collection has applications in multiple areas including identification of
scientific studies for inclusion in systematic reviews (Higgins et al., 2019;
Kanoulas et al., 2017, 2018, 2019), satisfying legal disclosure requirements
(Mcdonald et al., 2020; Baron et al., 2020; Grossman et al., 2016), social
media content moderation (Yang et al., 2021c) and test collection development
(Losada et al., 2019). These problems often involve large collections where
manually reviewing all documents would be prohibitively time-consuming.
Technology Assisted Review (TAR) develops techniques to support these document
review processes, including stopping rules which help reviewers to decide when
to stop assessing documents, thereby reducing the effort required to screen a
collection for relevance.

TAR stopping rules aim to identify when a desired level of recall (the target
recall) has been reached during document review, while also minimising the
number of documents examined. The problem is challenging since these two
objectives are in opposition; increasing the number of documents examined
provides more information about whether the target has been reached.

A common approach involves estimating the total number of relevant documents
in the collection and therefore whether the target recall has been reached,
e.g. (Shemilt et al., 2014; Howard et al., 2020; Callaghan and Müller-Hansen,
2020; Cormack and Grossman, 2016c; Yu and Menzies, 2019; Yang et al., 2021a;
Molinari and Esuli, 2023). Alternative approaches include randomly sampling
documents until a sufficient number of relevant ones have been discovered to
guarantee that the target recall has been reached (Cormack and Grossman,
2016a; Yang et al., 2021b) and observing the rate at which relevant documents
occur within a ranking until it drops below a pre-defined threshold (Cormack
and Grossman, 2016a).

Existing methods suffer from a number of limitations. Several approaches carry
out repeated statistical testing to determine whether the target recall has
been achieved, e.g. (Li and Kanoulas, 2020; Shemilt et al., 2014; Howard et
al., 2020; Callaghan and Müller-Hansen, 2020; Yang et al., 2021a), but this
type of sequential testing is statistically invalid (Yang et al., 2021b).
Lewis et al. (2021) avoided this problem using techniques from manufacturing
quality control (Grant and Leavenworth, 1980) but their approach often
required more documents to be reviewed than alternative methods (Stevenson and
Bin-Hezam, 2023). Some methods, e.g. (Cormack and Grossman, 2016a; Yang et
al., 2021b), fail to take account of the fact that standard TAR workflows
(Cormack and Grossman, 2014, 2016c; Li and Kanoulas, 2020) are highly
effective at prioritising relevant documents, meaning that their distribution
within the ranking is non-uniform. Exploiting this fact reduces the number of
documents that need to be examined before a stopping decision is made (Li and
Kanoulas, 2020; Stevenson and Bin-Hezam, 2023; Cormack and Grossman, 2016c).
However, existing approaches to modelling the distribution of relevant
documents rely on a particular rate function (e.g. power law (Zobel, 1998) or
AP Prior (Aslam et al., 2005)) but the choice of rate function is a modelling
decision and may not be appropriate in all circumstances.

Approaches to TAR stopping essentially involve repeated decisions to either
stop or examine more documents. Reinforcement learning (RL) is designed for
such sequential decision-making scenarios and has been widely applied within
Information Retrieval, e.g. (Zeng et al., 2018; Zhou and Agichtein, 2020;
Rosset et al., 2018; Nogueira and Cho, 2017; Montazeralghaem et al., 2020).
However it has not previously been applied to TAR stopping. This paper
proposes a novel TAR stopping method based on RL. This approach does not rely
on invalid statistical assumptions and is able to model rankings to make
informed decisions about when to stop. Experiments using a range of target
recall levels on multiple benchmark datasets demonstrate that the proposed
method is able to identify suitable stopping points and performs well in
comparison with several previously reported approaches.

The contributions of this paper are: (1) introduces a novel approach to the
TAR stopping problem that makes use of RL, (2) evaluates the proposed
algorithm using a range of collections commonly used for TAR problems, and (3)
demonstrates that the proposed approach effectively identifies an appropriate
stopping point and outperforms a wide range of alternative methods, often
substantially.111Code for the experiments available from
https://github.com/ReemBinHezam/RLStop/

##  2\. Approach

RL is a decision-making method in which an agent aims to maximise the reward
obtained from interacting with an environment and making sequential decisions
through trial-and-search (Sutton and Barto, 2018). The agent’s actions are
guided by a learned policy ($\pi$) which maps states in the environment to
actions.

RL is applied to the TAR stopping problem by considering an agent that
examines a ranked list of documents with the aim of stopping when a predefined
target recall has been achieved. The agent examines the ranking sequentially,
starting with the highest ranked documents and working down the ranking. For
efficiency, documents are examined in batches with relevance judgements
obtained for the entire batch simultaneously. After a batch of documents has
been examined the agent can either stop examining documents (if it judges that
the target recall has been achieved) or continue to the next batch of
documents (if not). This approach is similar to previous approaches of the
stopping problem in which a ranked list of documents is examined sequentially
(e.g. (Hollmann and Eickhoff, 2017; Di Nunzio, 2018; Stevenson and Bin-Hezam,
2023)), although the stopping decision is made by the agent (following a
policy) rather than according to some alternative criteria.

###  2.1. RLStop

This section describes how RL is applied to the stopping problem by outlining
how the key elements of an RL system are implemented within it.

State Space: A ranking is split into $B$ fixed size batches containing
$\frac{N}{B}$ documents for a collection of $N$ documents. The agent examines
batches sequentially and obtains relevance judgements for all documents in the
batch simultaneously. The initial state for each ranking, $S_{1}$, occurs when
the first batch (but none of the subsequent batches) has been explored.
Additional batches are examined in subsequent states, i.e. in the $n$th state,
$S_{n}$, the first $n$ batches have been examined. The final state, $S_{B}$,
represents the situation in which the entire ranking has been examined. If the
agent reaches this state, it will always stop here since all documents in the
ranking have been examined.

States are represented by a fixed size vector of length $B$ in which each
element represents a batch. For batches that have been examined the
corresponding element shows the number of relevant documents within the batch,
while elements corresponding to unexamined batches are given a dummy value
(-1).

Action Space: At each point in the ranking, the agent has a choice between two
discrete actions: STOP and CONTINUE. The first action is chosen when the agent
(informed by the policy) judges that the target recall has been reached. The
stopping point returned is the end of the last batch that has been examined so
far. If the agent does not stop it continues to examine the ranking, i.e.
moves from state $S_{i}$ to $S_{i+1}$.

Reward function: A reward function, $R(S_{i})$, assigns a score to $S_{i}$
indicating its attractiveness for the agent. The reward function is used to
train the policy and designing a suitable one is therefore important. A
suitable function should: 1) encourage the agent to continue examining
documents until the target recall has been reached, 2) discourage further
examination after it has been reached and 3) be independent from each topic’s
specific properties (e.g. total number of documents, ranking shape). In
addition, continuous functions are more straightforward for RL algorithms to
optimise.

The following function achieves these goals:

(1) $R(S_{i})=\begin{dcases*}1-\frac{i}{T}&if $i\leq T$\\\ -\frac{i-T}{B-T}&if
$i>T$\end{dcases*}$

where (as above) $B$ is the number of batches into which the ranking is split,
$i$ is the index of the current state (i.e. $i$th batch) and $T$ is the batch
at which the target recall is reached. (Note that while the value of $T$ is
known while the RL algorithm is being trained, it is not known when it is
applied.) The function assigns a positive reward when the current state is at,
or below, the target recall and a negative reward when it has been exceeded.

The cumulative reward for an RL episode (i.e. examining a ranking until a
stopping decision is made) is the sum of rewards for all positions examined by
the agent from $S_{1}$ to the stopping step $S_{s}$, i.e.
$\sum_{i=1}^{s}R(S_{i})$

Policy: RL aims to learn a policy, $\pi(s,a)$, that maximises the expected
cumulative reward obtained by taking an action ($a$) given a state ($s$).
Since the state space for our problem is high-dimensional, a neural network is
a choice for the policy. The policy is a feed-forward network consisting of an
input layer of length $B$, representing the current state, two 64-node hidden
layers and a binary output layer indicating the chosen action, which is
converted to a probability distribution over actions by a softmax activation
function.

RL Algorithm: RLStop uses Proximal Policy Optimization (PPO) (Schulman et al.,
2017), a policy gradient approach to RL. PPO is an actor-critic RL algorithm
that combines policy-based (actor) and value-based (critic) RL, where the
actor decides the actions, and the critic evaluates them. It is based on the
REINFORCE (Williams, 1992) algorithm but with several enhancements, including
the employment of parallel actors running independently by collecting
trajectories of different environments simultaneously which allows a policy to
be trained using multiple rankings. PPO is also more sample-efficient than
some alternative methods, such as DQN (Mnih et al., 2013), thereby reducing
the amount of data required to learn effective policies.

Implementation: The Stable-Baseline3 library (Raffin et al., 2021) was used to
implement RLStop. The RL environment was created using the Gymnasium library
(Towers et al., 2023) which allows multiple environments to be stacked,
thereby allowing simultaneous training on multiple topics to ensure the agent
is as general as possible. The number of batches, $B$, was set to 100.

##  3\. Experiments

Experiments were carried out on multiple datasets and evaluation metrics.

###  3.1. Datasets

Performance was evaluated on six datasets widely used in previous TAR work and
representing multiple domains. All datasets are highly imbalanced, with a very
low percentage of relevant documents per topic.
CLEF 2017/2018/2019 (Kanoulas et al., 2017, 2018, 2019): Collections of
systematic reviews produced for the Conference and Labs of the Evaluation
Forum (CLEF) 2017, 2018, and 2019 e-Health lab Task 2: Technology-Assisted
Reviews in Empirical Medicine. The CLEF 2017 dataset contains 42 reviews; CLEF
2018 contains 30 and CLEF 2019 contains 31. RLStop was trained using the 12
reviews provided with the CLEF 2017 dataset.
TREC Total Recall (TR) (Grossman et al., 2016) A collection of 290,099 emails
associated with Jeb Bush’s eight-year tenure as Governor of Florida (athome4).
The collection contains 34 topics. RLStop was trained using the athome1
dataset consisting of 10 topics.
RCV1 (Lewis et al., 2004) A collection of Reuters news articles labelled with
subject categories. Following (Yang et al., 2021b, a), 45 categories were used
to represent a range of topics, and the collections were downsampled to 20%.
RLStop was trained using the remaining RCV1 topics, excluding those already
included in the test set.

Each collection was ranked with the use of a reference implementation (Li and
Kanoulas, 2020) of AutoTAR (Cormack and Grossman, 2015), a greedy Active
Learning approach representing state-of-the-art performance on total recall
tasks widely used for TAR experiments. The use of AutoTAR rankings allows
direct comparison between RLStop and alternative approaches used as baselines
in previous work (Li and Kanoulas, 2020; Stevenson and Bin-Hezam, 2023).

###  3.2. Evaluation Measures

A wide range of metrics have been used to evaluate TAR stopping methods, e.g.
(Yang et al., 2021a; Li and Kanoulas, 2020). These essentially measure the
method’s success of meeting the two objectives of stopping algorithms: (1)
reach the target recall and (2) examine as few documents as possible. Two
metrics were used to capture these objectives. Recall: the proportion of
relevant documents identified by the method. Cost: percentage of documents
examined. Results for these metrics are reported as average scores for all
topics in each collection.

An additional metric captures elements of both objectives and is used to
quantify the variation in performance across topics contained within a
collection. Excess: proportion of documents examined after the target recall
has been reached or that needs to be examined reach it (Bin-Hezam and
Stevenson, 2023). Excess is defined as follows:

(2) $excess=\frac{cost(method)-cost(optimal)}{1-cost(optimal)}$

where $cost(method)$ and $cost(optimal)$ are the cost of the method being
evaluated and stopping at the optimal point (i.e. oracle). An excess of 0
indicates that the optimal stopping point for the target recall has been
reached, a positive score indicates that more documents than absolutely
necessary were examined (i.e. the target was overshot) and a negative
indicates that the target was not reached (i.e. undershot).

Metrics were calculated using the tar_eval open-source evaluation
script.222https://github.com/CLEF-TAR/tar

###  3.3. Training and Hyper-parameter Tuning

RLStop models were trained for 100,000 timesteps on the each target recall
using each dataset’s training split. PPO hyper-parameters were set via a grid
search on the CLEF 2017 training dataset and the following values chosen:
batch size = 100, number of steps (used to collect trajectories before each
policy update rollout) = 100, learning rate = 0.0001, number of epochs = 8,
entropy coefficient (which encourages policy exploration) = 0.1, discount
factor = 0.99 and KL coefficient (which controls the clipping range) = 0.2.

###  3.4. Baselines and Oracle

RLStop was compared against a range of alternative approaches used as
baselines in previous work (Li and Kanoulas, 2020; Stevenson and Bin-Hezam,
2023). The target method (TM) (Cormack and Grossman, 2016b) randomly samples
documents until a set of predefined target set is identified with results
reported for the original method (Cormack and Grossman, 2016b) and two
extensions: TM-adapted (Stevenson and Bin-Hezam, 2023) and QBCB (Lewis et al.,
2021). SCAL (Cormack and Grossman, 2016c) and AutoStop (Li and Kanoulas, 2020)
estimate the number of relevant documents by sampling across the entire
ranking. SD-training/SD-sampling (Hollmann and Eickhoff, 2017) are score
distribution methods. The knee method (Cormack and Grossman, 2016a) identifies
the inflection point in the gain curve. IP-H (Stevenson and Bin-Hezam, 2023)
uses a counting process to estimate the number of relevant documents.

Baselines are computed using reference implementations from previous work (Li
and Kanoulas, 2020; Stevenson and Bin-Hezam, 2023) where possible. Otherwise,
previously reported results are used and are directly comparable since they
are also based on AutoTAR rankings. However, some baselines are not available
for RCV1 since we were unable to run the reference code and results have not
been provided in previous work.

Performance was also compared against an Oracle method (OR) which examines
documents in ranking order and stops when the target recall level has been
achieved (or exceeded). The oracle represents the behaviour of an ideal
stopping method but is not useful in practise since it requires full
information about the ranking.333Note that the recall achieved by the oracle
is higher than the target recall when it is not possible to achieve the target
recall exactly, e.g. given a target recall of 0.8 and collection containing 9
relevant documents, the oracle will stop after 8 relevant documents have been
found, i.e. recall 0.89.

##  4\. Results and Analysis

Figure 1 shows the recall and cost for RLStop and alternative methods for each
data set at multiple target recall levels: {1.0, 0.9, 0.8}. Performance of
RLStop (denoted by blue hexagon) is often close to the optimal oracle results
(e.g. sub-figures (b), (c), (f), (g), (j) and (n)) and is also Pareto
optimal444No other approach achieves the same, or greater, recall with lower
cost. in the majority of cases. RLStop is not Parteo optimal in two cases
(sub-figures (n) and (o)) but is very close to the Pareto frontier both times.
Other baselines that are commonly Pareto optimal include IP-H and the Knee
method (cyan star and a green square, respectively). However, both methods
tend to overshoot the target more than RLStop. Other baselines are
substantially more costly and either undershoot or overshoot the target more
frequently than RLStop.

Figure 1. Performance of RLStop and baselines for Recall vs. Cost metrics.
Grey lines indicates non-oracle Pareto optimal approaches. (Note differences
in range of y-axis (recall) to avoid clustering of results.)

RLStop vs baselines

Although RLStop tends to follow the target recall it does not do so exactly
and tends to overshoot for lower target recalls (e.g. 0.8). This overshooting
is particularly pronounced for the TR dataset where the target recall is often
reached very quickly (as demonstrated by the oracle performance). For some
topics overshooting is caused by the ranking being divided into fixed batches
(1% of the ranking) where examining only a single batch (i.e. the earliest
possible stopping point) overshoots the target recall. Increasing the number
of batches may be a potential solution to this problem. On the other hand,
RLStop tends to undershoot for higher target recall levels, although it
normally stops within a few percentage points of the target. This
undershooting may be due to topics that contain a small number of relevant
documents towards the end of their rankings, which RLStop does not reach.

Figure 2 shows how RLStop’s excess varies across topics for all datasets at
different target recall levels. For the majority of topics the excess costs is
confined within a fairly narrow range, particularly for the TR collection. The
variation is higher for all collections when target recall is 1.0 due to the
additional challenge of identifying all relevant documents. This is more
pronounced for RCV1, although the excess is within a relatively narrow range
for the majority of topics.

Figure 2. Distribution of RLStop excess across topics. (Outliers for target
recall 1.0 removed for clarity.)

RLStop excess across topics

##  5\. Conclusion

This paper proposes RLStop, a novel TAR stopping rule based on reinforcement
learning. RLStop substantially reduces the workload required to screen
collections for relevance. RLStop performs well in comparison with several
baselines on multiple benchmark datasets at different target recall levels.

RLStop requires training data which may be available (e.g. from previous
relevance screening carried out within a similar environment, such as within a
systematic review team). It may not be suitable if these are not available or
if confidence guarantees of reaching the target recall are required. RLStop
also requires a new model to be trained for each target recall level. We plan
to address these issues in future work.

## References

  * (1)
  * Aslam et al. (2005) Javed A Aslam, Virgiliu Pavlu, and Emine Yilmaz. 2005.  Measure-based metasearch. In _Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval_. 571–572.
  * Baron et al. (2020) Jason R Baron, Mahmoud F Sayed, and Douglas W Oard. 2020.  Providing More Efficient Access To Government Records: A Use Case Involving Application of Machine Learning to Improve FOIA Review for the Deliberative Process Privilege.  _arXiv preprint arXiv:2011.07203_ (2020).
  * Bin-Hezam and Stevenson (2023) Reem Bin-Hezam and Mark Stevenson. 2023.  Combining Counting Processes and Classification Improves a Stopping Rule for Technology Assisted Review. In _Findings of the Association for Computational Linguistics: EMNLP 2023_. Association for Computational Linguistics, Singapore, 2603–2609.  https://doi.org/10.18653/v1/2023.findings-emnlp.171
  * Callaghan and Müller-Hansen (2020) Max W Callaghan and Finn Müller-Hansen. 2020.  Statistical stopping criteria for automated screening in systematic reviews.  _Systematic Reviews_ 9, 1 (2020), 1–14.
  * Cormack and Grossman (2015) Gordon Cormack and Maura Grossman. 2015.  Autonomy and Reliability of Continuous Active Learning for Technology-Assisted Review.  _arXiv preprint arXiv:1504.06868_ (apr 2015).  arXiv:1504.06868
  * Cormack and Grossman (2014) Gordon V Cormack and Maura R Grossman. 2014.  Evaluation of machine-learning protocols for technology-assisted review in electronic discovery. In _Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval_. 153–162.
  * Cormack and Grossman (2016a) Gordon V Cormack and Maura R Grossman. 2016a.  Engineering Quality and Reliability in Technology-Assisted Review. In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_. 75–84.
  * Cormack and Grossman (2016b) Gordon V. Cormack and Maura R. Grossman. 2016b.  Engineering quality and reliability in technology-assisted review. In _Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval_. Association for Computing Machinery, Inc, 75–84.  https://doi.org/10.1145/2911451.2911510
  * Cormack and Grossman (2016c) Gordon V Cormack and Maura R Grossman. 2016c.  Scalability of continuous active learning for reliable high-recall text classification. In _Proceedings of the 25th ACM international on conference on information and knowledge management_. 1039–1048.
  * Di Nunzio (2018) Giorgio Maria Di Nunzio. 2018.  A study of an automatic stopping strategy for technologically assisted medical reviews. In _European Conference on Information Retrieval_. Springer, 672–677.
  * Grant and Leavenworth (1980) Eugene Lodewick Grant and Richard S Leavenworth. 1980.  _Statistical quality control_. Vol. 7.  McGraw-Hill New York.
  * Grossman et al. (2016) Maura R. Grossman, Gordon V. Cormack, and Adam Roegiest. 2016.  TREC 2016 Total Recall Track Overview. In _Proceedings of The Twenty-Fifth Text REtrieval Conference, TREC 2016_ _(NIST Special Publication, Vol. 500-321)_. National Institute of Standards and Technology (NIST).
  * Higgins et al. (2019) Julian PT Higgins, James Thomas, Jacqueline Chandler, Miranda Cumpston, Tianjing Li, Matthew J Page, and Vivian A Welch. 2019.  _Cochrane Handbook for Systematic Reviews of Interventions_.  John Wiley & Sons.
  * Hollmann and Eickhoff (2017) Noah Hollmann and Carsten Eickhoff. 2017.  Ranking and Feedback-based Stopping for Recall-Centric Document Retrieval. In _Working Notes of CLEF 2017 - Conference and Labs of the Evaluation Forum_. 7–8.
  * Howard et al. (2020) Brian E. Howard, Jason Phillips, Arpit Tandon, Adyasha Maharana, Rebecca Elmore, Deepak Mav, Alex Sedykh, Kristina Thayer, B. Alex Merrick, Vickie Walker, Andrew Rooney, and Ruchir R. Shah. 2020.  SWIFT-Active Screener: Accelerated document screening through active learning and integrated recall estimation.  _Environment International_ 138 (2020), 105623.  https://www.sciencedirect.com/science/article/pii/S0160412019314023
  * Kanoulas et al. (2017) Evangelos Kanoulas, Dan Li, Leif Azzopardi, and Rene Spijker. 2017.  CLEF 2017 Technologically Assisted Reviews in Empirical Medicine Overview. In _CEUR workshop proceedings_ , Vol. 1866.
  * Kanoulas et al. (2018) Evangelos Kanoulas, Dan Li, Leif Azzopardi, and Rene Spijker. 2018.  CLEF 2018 Technologically Assisted Reviews in Empirical Medicine Overview. In _CEUR workshop proceedings_ , Vol. 2125.
  * Kanoulas et al. (2019) Evangelos Kanoulas, Dan Li, Leif Azzopardi, and Rene Spijker. 2019.  CLEF 2019 Technology Assisted Reviews in Empirical Medicine Overview. In _CEUR workshop proceedings_ , Vol. 2380.
  * Lewis et al. (2021) David Lewis, Eugene Yang, and Ophir Frieder. 2021.  Certifying One-Phase Technology-Assisted Reviews. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_.
  * Lewis et al. (2004) David D Lewis, Yiming Yang, Tony Russell-Rose, and Fan Li. 2004.  RCV1: A New Benchmark Collection for Text Categorization Research.  _Journal of Machine Learning Research_ 5 (2004), 361–397.  https://doi.org/10.5555/1005332.1005345
  * Li and Kanoulas (2020) Dan Li and Evangelos Kanoulas. 2020.  When to Stop Reviewing in Technology-Assisted Reviews: Sampling from an Adaptive Distribution to Estimate Residual Relevant Documents.  _ACM Trans. on Information Systems_ 38, 4 (2020), 1–36.  https://doi.org/10.1145/3411755
  * Losada et al. (2019) David E. Losada, Javier Parapar, and Alvaro Barreiro. 2019.  When to stop making relevance judgments? A study of stopping methods for building information retrieval test collections.  _Journal of the Association for Information Science and Technology_ 70, 1 (2019), 49–60.
  * Mcdonald et al. (2020) Graham Mcdonald, Craig Macdonald, and Iadh Ounis. 2020.  How the accuracy and confidence of sensitivity classification affects digital sensitivity review.  _ACM Transactions on Information Systems (TOIS)_ 39, 1 (2020), 1–34.
  * Mnih et al. (2013) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013.  Playing Atari with Deep Reinforcement Learning.  arXiv:1312.5602 [cs.LG]
  * Molinari and Esuli (2023) Alessio Molinari and Andrea Esuli. 2023.  SAL$\tau$: efficiently stopping TAR by improving priors estimates.  _Data Mining and Knowledge Discovery_ (2023), 1–34.
  * Montazeralghaem et al. (2020) Ali Montazeralghaem, Hamed Zamani, and James Allan. 2020.  A reinforcement learning framework for relevance feedback. In _Proceedings of the 43rd international acm sigir conference on research and development in information retrieval_. 59–68.
  * Nogueira and Cho (2017) Rodrigo Nogueira and Kyunghyun Cho. 2017.  Task-oriented query reformulation with reinforcement learning.  _arXiv preprint arXiv:1704.04572_ (2017).
  * Raffin et al. (2021) Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. 2021.  Stable-Baselines3: Reliable Reinforcement Learning Implementations.  _Journal of Machine Learning Research_ 22, 268 (2021), 1–8.  http://jmlr.org/papers/v22/20-1364.html
  * Rosset et al. (2018) Corby Rosset, Damien Jose, Gargi Ghosh, Bhaskar Mitra, and Saurabh Tiwary. 2018.  Optimizing query evaluations using reinforcement learning for web search. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 1193–1196.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ (2017).
  * Shemilt et al. (2014) Ian Shemilt, Antonia Simon, Gareth J Hollands, Theresa M Marteau, David Ogilvie, Alison O’Mara-Eves, Michael P Kelly, and James Thomas. 2014.  Pinpointing needles in giant haystacks: use of text mining to reduce impractical screening workload in extremely large scoping reviews.  _Research Synthesis Methods_ 5, 1 (2014), 31–49.
  * Stevenson and Bin-Hezam (2023) Mark Stevenson and Reem Bin-Hezam. 2023.  Stopping Methods for Technology-assisted Reviews Based on Point Processes.  _ACM Transactions on Information Systems_ 42, 3 (2023), 1–37.
  * Sutton and Barto (2018) Richard S. Sutton and Andrew G. Barto. 2018.  _Reinforcement learning: An introduction_.  MIT Press.  http://incompleteideas.net/book/RLbook2020.pdf
  * Towers et al. (2023) Mark Towers, Jordan K. Terry, Ariel Kwiatkowski, John U. Balis, Gianluca de Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun KG, Markus Krimmel, Rodrigo Perez-Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis. 2023.  Gymnasium.  https://doi.org/10.5281/zenodo.8127026
  * Williams (1992) Ronald J Williams. 1992.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8 (1992), 229–256.
  * Yang et al. (2021a) Eugene Yang, David Lewis, and Ophir Frieder. 2021a.  Heuristic Stopping Rules for Technology-Assisted Review. In _Proceedings of the 21st ACM Symposium on Document Engineering 2021 (DocEng ’21)_. Article 31, 10 pages.  https://doi.org/10.1145/3469096.3469873
  * Yang et al. (2021b) Eugene Yang, David D Lewis, and Ophir Frieder. 2021b.  On minimizing cost in legal document review workflows. In _Proceedings of the 21st ACM Symposium on Document Engineering 2021 (DocEng ’21)_. Article 30, 10 pages.  https://doi.org/10.1145/3469096.3469872
  * Yang et al. (2021c) Eugene Yang, David D Lewis, and Ophir Frieder. 2021c.  TAR on social media: A framework for online content moderation. In _2nd international conference on Design of Experimental Search & Information REtrieval Systems (DESIRES 2021)_. 147–155.
  * Yu and Menzies (2019) Zhe Yu and Tim Menzies. 2019.  FAST2: An Intelligent Assistant for Finding Relevant Papers.  _Expert Systems with Applications_ 120 (2019), 57–71.
  * Zeng et al. (2018) Wei Zeng, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2018.  Multi page search with reinforcement learning to rank. In _Proceedings of the 2018 ACM SIGIR international conference on theory of information retrieval_. 175–178.
  * Zhou and Agichtein (2020) Jianghong Zhou and Eugene Agichtein. 2020.  Rlirank: Learning to rank with reinforcement learning for dynamic search. In _Proceedings of The Web Conference 2020_. 2842–2848.
  * Zobel (1998) Justin Zobel. 1998.  How Reliable Are the Results of Large-Scale Information Retrieval Experiments?. In _Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_. 307–314.


# Sentence-level Aggregation of Lexical Metrics Correlate
Stronger with Human Judgements than Corpus-level Aggregation

Paulo Cavalin  IBM Research<EMAIL_ADDRESS>Pedro H. Domingues  PUC-Rio,
<EMAIL_ADDRESS>Claudio Pinhanez  IBM Research<EMAIL_ADDRESS>
###### Abstract

In this paper we show that corpus-level aggregation hinders considerably the
capability of lexical metrics to accurately evaluate machine translation (MT)
systems. With empirical experiments we demonstrate that averaging individual
segment-level scores can make metrics such as BLEU and chrF correlate much
stronger with human judgements and make them behave considerably more similar
to neural metrics such as COMET and BLEURT. We show that this difference
exists because corpus- and segment-level aggregation differs considerably
owing to the classical average of ratio versus ratio of averages Mathematical
problem. Moreover, as we also show, such difference affects considerably the
statistical robustness of corpus-level aggregation. Considering that neural
metrics currently only cover a small set of sufficiently-resourced languages,
the results in this paper can help make the evaluation of MT systems for low-
resource languages more trustworthy.

##  1 Introduction

We can currently group machine translation (MT) metrics into two main groups:
lexical and neural metrics [3]. While lexical metrics such as the BLEU score
[15] have considerably contributed to the progress in MT in the past 20 years,
neural metrics emerged in the past few years as viable alternatives to
overcome not only the shortcomings of lexical matches of n-grams, but also to
leverage corpus-based training to improve MT evaluation [23, 26, 28].

Although it is quite clear that neural metrics are more robust and will
eventually replace the lexical ones [13, 5, 4], in this paper we argue not
only that lexical metrics are still quite needed but also that there is room
to improve the robustness of such metrics. We say that they are needed because
most progress with neural metrics is observed on the one hundred or so most-
resourced languages in the world, but almost 7,000 languages in the world
still lack the minimum amount of data to train a MT model [12]. It is thus
unrealistic to think that a neural metric will be applied for such scenarios
in the near future. With this perspective in mind, we argue that there is a
very under-explored and important component of lexical metrics, which is the
aggregation method.

Lexical metrics such as BLEU and chrF usually rely on corpus-level aggregation
(CLA) [15, 17], but one can easily rely on segment-level aggregation (SLA).
The main difference between CLA and SLA is that, while in the former we
compute n-gram matching statistics for all samples in a first step and then we
compute a global score for the entire test set, with the latter we compute the
statistics and the score for each sample individually and then use the mean of
these scores for evaluating a test set. We notice that SLA is a very under-
explored method for lexical metrics (see Appendix A for detailed statistics)
and, for the best of our knowledge, there is no previous work demonstrating
why corpus-level should be preferred besides theoretical assumptions.

At a glance, it surely looks that, in the worst-case-scenario, both CLA and
SLA present comparable results, so there would be no good reason to question
the aggregation method choice. But in this paper we show that, counter-
intuitively against the common belief that CLA is better and should be the
aggregation method of choice for lexical metrics, SLA is far more correlated
to human judgements and to more robust neural metrics. To support this claim,
we first show that there is a conceptual difference between these two
aggregation methods, which we can mathematically relate to the _average of
ratios vs ratios of averages_ problem. And based on empirical experiments, we
show not only that the choice between the aggregation method significantly
impacts the resulting system-level scores but also that CLA is not
statistically robust.

In greater details, in a first set of experiments we investigated whether the
aforementioned mathematical differences between CLA and SLA statistically
impact the scores provided by the metrics. For this, we considered 492 system
outputs from the WMT23 metrics shared task [3], and computed system-level
scores considering not only these two aggregation methods with both BLEU and
chrF as base metrics but also scores computing the mean of bootstrap-resampled
scores (BRS), as a reference point of a more statistically-robust approach.
For this evaluation, we computed the pairwise Pearson correlation of the
scores of each pair of metric and the results clearly show not only that the
scores from CLA and SLA differ considerably but also that the scores from SLA
correlate quite stronger with those from BRS.

We then conducted a deeper investigation of the statistical robustness of the
two aggregation methods, where we focused on evaluating the impact of the size
of the test set on the correlation of scores. For that, we relied on
downsampled test sets and computed the correlations of scores from downsampled
versions of both CLA and SLA against each other, and against the
statistically-robust BRS. The results corroborated our previous findings that
SLA is not only more statistically robust than CLA but also show that this
method is as statistically robust as BRS and can replace it as a much
computationally-cheaper alternative.

However, the most surprising and relevant result, in our opinion, is that CLA
is not only statistically weaker than SLA but it actually lacks any
statistical robustness. In other words, when compared to BRS, the correlations
of CLA scores computed on larger test sets are quite close to those computed
on a test set with only a single sample. That means that the corpus-level
evaluation could be simply replaced by single-sample evaluations.

Finally, in order to materialize what actually means the previous mathematical
and statistical differences between the aggregation methods, in terms of the
impact on the resulting quality of system-level scores, we computed
correlations between the metrics and human judgements. For this, we considered
human annotations from the WMT23 Metrics Shared Task, and we also included
additional neural metrics, i.e. COMET, BLEURT, and BERTScore, to provide a
better view on the impact of the aggregation method. Our results provide
strong evidence that SLA correlates much stronger with human judgements, and
are much more comparable to the outcomes of BERTScore. Considering that
BERTScore is the only neural metric among these three which does not takes
into account the input sentence to compute the score, which is compatible to
the way lexical metrics work, we believe that our results show that the use of
segment-level aggregation reduces considerably the gap between lexical and
neural metrics.

##  2 Related work

The most well-known _lexical metric_ for machine translation evaluation is the
BLEU score, introduced more than two decades ago as a solution to make the
development of MT system more scalable [16]. The idea was to take advantage of
a set of translations created by humans and to somehow measure the discrepancy
between the outputs generated by a MT system and the reference translations.
With that approach, one could develop different systems and select the one
which produced the highest BLEU score in a completely automated fashion.

The way BLEU works is based on computing a Precision-like metric on overlaps
of _n-grams_ between the MT outputs and the references. That is done by
counting up the number of n-grams generated in the MT outputs that also appear
in the references. This computation is then heuristically refined to address
some issues such as wrongly-generated repetitions and very short texts, and to
combine different n-gram levels. BLEU also inspired other popular lexical
metrics such as _chrF_ [18] and _chrF++_[19], which play important roles to
expand current NLP efforts into low-resource languages.

Despite the wide adoption of BLEU for about two decades, several works have
focused on exploiting and overcoming its limitations [7, 13, 4, 3]. One issue
already tackled by the community is the reliance in a large set of parameters
and lack of standard and transparency in reporting results [20]. But another
limitation, which is the reliance on lexical matches, resulted in the proposal
of different alternative metrics, notably _neural metrics_ such as COMET [24],
BLEURT [26], and UniTE [27].

As outlined in the WMT22 shared task results [4], across diverse domains and
tasks, neural-based metrics like MetricX XXL [9], COMET-22 [22], UniTE [27]
and BLEURT-20 [25] consistently outperformed BLEU and other non-neural
counterparts in capturing evaluation nuances. In the subsequent WMT23 shared
task [3], the evaluation framework has been enhanced, expanding the metrics
set and relying on a global score calculated through a weighted average across
tasks. The results underscored the better alignment of neural-based metrics
with human judgments than with non-neural ones.

Nevertheless, it is worth highlighting that neural metrics come with
additional cost. Some metrics such as UniTE and COMET compute scores by
relying also on the input provided to generate the translation, which
obviously limits the application to cases where both the source and the target
languages were used to train the underlying model. Even the neural metrics
that consider only the MT outputs and the reference to compute the scores are
quite limited, since they are usually trained with just dozens of languages.
That limits neural metrics to, at best, hundreds of languages, the high- and
mid-resourced ones.

Considering the currently-limited application of neural metrics and the vast
number of under-studied languages in the world, there is still a vast
application field for metrics based on overlaps of n-grams such as BLEU and
chrF. At the same time, we observe here that there is a gap on a better
understanding on the shortcomings of corpus-level aggregation, considering
that most of the recent metrics rely on averages of segment-level scores.

As we show in Appendix A, from 345 papers we inspected, only one relied on
segment-level aggregation for the BLEU metric [2]. And we can find the use of
segment-level aggregation for chrF in very few works, such as in the reports
for the WMT Metrics shared task [5, 4, 3]. What seems to be missing is a work
showing the impact of the choice of the aggregation method. This paper aims to
bridge this gap.

##  3 Corpus- vs Segment-level Aggregation

In this section we focus on describing in details both corpus-level
aggregation (CLA) and segment-level aggregation (SLA) methods, and on explaing
why the choice of one over another is mathemathically different and might
affect the resulting scores. For the sake of simplicity, we will focus on the
BLEU score, but in our empirical evaluations presented afterwards we
demonstrate that our hyphoteses are not limited to BLEU and are at least also
applicable to chrF.

###  3.1 A case study with BLEU

With a case study with BLEU, in this section we discuss why we expect
differences in the results according to the the aggregation method. For that
we will rely on a simplified abstraction of BLEU, considering that this metric
consists of computing a Precision-like score for the generated translation or
for a set of generated translations [16].

Before explaining the aggregation method, it is worth explaining how BLEU is
computed for a single sentence, i.e. the so-called _sentence-level_ BLEU
score. For this case, we basically compute the total of _n-gram matches_
between the _candidate_ sentence, i.e. the sentence generated by the ML model,
and the _references_ , representing the ground-truth translations generated by
a person that is fluent enough in the target language. The matching is
computed by evaluating the number of n-grams present in the candidate sentence
that also appear in the references. After we computed that number of matches,
we divide this number by the total of n-grams contained in the candidate
output, to compute a Precision-ish score that represents the sentence-level
evaluation score. Of course, since this is a simplified abstraction, we are
not taking into account modified n-gram precision, clipping, combination of
different n-gram levels, and brevity penalty, but this does not affect our
rationale.

When we expand sentence-level BLEU to evaluate the MT system on a corpus of
text or on an entire test set, for instance, the main approach is to rely on
the so-called _corpus-level_ BLEU (check Section 2.2.1 in [16] for further
details). The corpus-level aggregation (CLA) of BLEU consists of a global
computation of n-gram matches and a single scoring for all samples in the test
set, done at once. That is, all n-gram matches are counted and summed up, and
this number is divided by the sum of the lengths of all candidate sentences.

Although corpus-level BLEU is the usual choice and the default options in
tools such as SacreBLEU111https://github.com/mjpost/sacrebleu, it is quite
easy to adopt averages of segment-level scores, or simply _segment-level
aggregation_ (SLA), to compute system-level scores [1, 14]. The implementation
is straightforward, where one simply need to compute sentence-level BLEU
scores for each individual test sample, than using the mean of such scores as
the final system-level scores. This aggregation method presents some
advantages, such as allowing to compute statistical metrics such as standard
deviations, which is not possible with corpus-level aggregation. Notice that
bootstrap resampling is a somewhat popular method to compute statistical
significance tests on corpus-level scores [10, 8, 6] and can also be used to
compute statistical metrics, but it is a more expensive approach in terms of
computation requirements.

At a first sight, it is reasonable to believe that CLA and SLA provide the
same results, so the main advantage of the latter would only be the less
expensive way to compute statistical metrics. But there is a conceptual
mathematical difference between these two aggregation methods, which we
explain next.

###  3.2 CLA and SLA as differently weighted ratio averages

We dive now into a mathematical explanation of the difference between corpus-
level and segment-level aggregations, to demonstrate why these two methods may
present differences in the results. We argue that the main difference between
the two aggregation methods can be seen as a classical case of ratio of
averages vs average of ratios.

To understand this, let us adopt a simplified definition of BLEU as a ratio of
the number of matches $m$ by n-grams $w$ in a corpus, as in the previous
section. And let us also refer to the corpus-level and segment-level BLEU as
simply BLEU and m-BLEU, respectively. Considering all the $n$ sentences $i$ of
the corpus, it is evident that BLEU can be computed by the ratio between the
sum of all partial matches $m_{i}$ in each sentence $i$ by the sum of n-grams
in all sentences $i$, $w_{i}$:

$\mbox{BLEU}=\frac{m}{w}=\frac{\sum_{i=1}^{n}m_{i}}{\sum_{i=1}^{n}w_{i}}$ (1)

Accordingly, m-BLEU is the average of ratios between the number of matches
$m_{i}$ and the number of words $w_{i}$ of each sentence $i$:

$\mbox{m-BLEU}=\frac{1}{n}\sum_{i=1}^{n}\frac{m_{i}}{w_{i}}=\sum_{i=1}^{n}\left(\frac{1}{n}\right)\frac{m_{i}}{w_{i}}$
(2)

It is easy to derive that BLEU is the weighted average of the sentence ratios
by the proportional length of each sentence $i$:

BLEU
$\displaystyle=\frac{\sum_{i=1}^{n}m_{i}}{\sum_{i=1}^{n}w_{i}}=\sum_{i=1}^{n}\frac{m_{i}}{w}=\sum\limits_{i=1}^{n}\frac{w_{i}}{w_{i}}\frac{m_{i}}{w}$
(3)
$\displaystyle\mbox{BLEU}=\sum\limits_{i=1}^{n}\left(\frac{w_{i}}{w}\right)\frac{m_{i}}{w_{i}}$

As we see, m-BLEU weights the ratios equally with $1/n$ weights while BLEU
weights the ratios with the value $w_{i}/w$ which is proportional to the
length of each sentence $i$. Therefore, BLEU results are likely to be biased
by the proportion of matches and candidate sentences lengths, while m-BLEU
considers the performance independently of that.

##  4 Empirical evaluation

In this section we present experiments aiming at investigating whether the
choice of aggregation method actually impacts the score provided by a lexical
metric. For that, we consider three different implementations of BLEU and chrF
and, considering the outputs from 492 different systems, we present a detailed
analysis on the distribution of scores provided by these metrics.

###  4.1 The dataset

For this investigation we rely on the WMT 2023 Metrics Shared Task
dataset222https://wmt-metrics-task.github.io/, or simply _WMT23 dataset_ ,
comprising the results of 492 different MT systems, involving different
languages and domains. This dataset contains 468,850 system outputs with the
corresponding inputs and references, in a quite diverse setting, containing
147 different language pairs, being 48 different source languages and 44
target languages.

We converted the 468,850 raw entries to 492 system evaluations by grouping the
data by dataset type (challengesets2023 or generaltest2023), dataset
(challenge_ACES, challenge_DFKI, challenge_NRC-MSLC23, or generaltest2023),
language pair (147 options), and system (two systems for the challegeset2023
dataset type and 14 systems for the generaltest2023). Those are all inner
structures of the dataset and the aggregated data will be made publicly
available333anonimous link to dataframe.

###  4.2 Three implementations of BLEU

We considered three different implementations for BLEU. Two of them are based
on the corpus- (CLA) and segment-level aggregation (SLA), and the third relies
on bootstrap-resampled scores (BRS) for providing more robust statistical
estimates, so that we can use this approach as a reference point for
statistically-reliable scores.

As a consequence, the first implementation is referred to as simply BLEU,
consisting of the traditional BLEU score with CLA, here computed with the
SacreBLEU tool with default parameters
[21]444nrefs:1—case:mixed—eff:no—tok:13a—smooth:exp—version:2.0.0. For this
metric, given a test set with samples and the corresponding reference MT
outputs, we take all MT outputs and references at once, in a single list, and
compute the score with the `corpus_bleu` function in Python code.

The second metric, referred to as m-BLEU, implements SLA. For this we simply
compute the score of each segment (i.e. a test sample) with SacreBLEU’s
`sentence_bleu` function, again with default parameters, and calculate the
overall average to provide the system-level score.

The third metric, named x-BLEU, consists of implementing the BRS method, as in
[14, 11]. This is an alternative to computing system-level scores with higher
statistical robustness, where the resamplings represent varied rearrangements
of the test set to compute corpus-level BLEU. We rely on 1,000 resamplings,
with replacement, of 1,000 samples555Notice that 1,000 samples is roughly very
close the mean of samples in the WMT23 dataset, which is 952.94. for each
system, and we applied the same SacreBLEU’s `corpus_bleu` function, with
default parameters, on top of each resampled set, generating 1,000 scores for
each system. We then provide the average of those 1,000 scores as the system-
level score.

###  4.3 Three implementations of chrF

In order to investigate whether our observation also generalize to other
lexical metrics, we explored also three different implementations of chrF.
Notice that chrF is quite similar to BLEU, where overlaps of characters
n-grams are computed instead of overlap of words, and the final score is based
on an F1 score instead of the precision-ish score used by BLEU. More
importantly, the same variety of aggregation methods are possible to be used
with chrF, and those varieties can be put in practice with the `corpus_chrf`
and a `sentence_chrf` functions from SacreBLEU.

Consequently, the three different chrF implemenations that we consider in this
work are: chrF, the CLA version computed with `corpus_chrf` SacreBLEU’s
function; m-chrF, the SLA implementation relying on the average of segment-
level scores computed with `sentence_chrf`; and x-chrF, the BRS metric
computed with averages of `corpus_chrf` on 1,000 resamplings with 1,000
samples. Notice that we always rely on the default SacreBLEU’s parameters for
such functions.

###  4.4 CLA and SLA correlate weakly to each other, and SLA correlates
strongly to BRS

Our first evaluation focused on investigating the distribution of scores
provided by the three different aggregation methods, how these distributions
correlate to each other, and how they correlate to more statistically-robust
scores. We focus first on analysing BLEU, and then show results with chrF to
understand the impact of the base metric.

Figure 1: Correlation plots of the different BLEU metrics to each other and,
in the diagonal, the distribution of the scores of the 3 metrics. Figure 2:
Correlation plots of the different chrF metrics to each other and, in the
diagonal, the distribution of the scores of the 3 metrics.

Figure 1, displaying a grid of 9 plots, presents the main results of this
analysis. Notice that in the diagonal we show the histogram of the
distribution of scores for each metric, considering the scores for the 492
systems, and in the upper and lower non-diagonal cells we present the pairwise
scatter plots and Pearson correlations, in the -1 to 1 range, considering the
metrics scores. The main intuition of computing Pearson correlation is to
assess the linear correlation between the metrics. That is, a highly-positive
correlation, i.e. a value close to 1.0, indicates that high scores in one
metric correspond to high scores in another metric, and vice-versa. This
correlation helps determine whether the metrics are aligned in capturing what
are the good and bad translation results and what is in-between.

From both the distributions and correlation values, we can clearly see that
x-BLEU and m-BLEU tend to produce much closer results to one-another than to
BLEU. We can see that the distribution of BLEU is right-skewed, while the
other distributions are more centralized. In details, the means of the
distributions are 0.29, 0.43, and 0.39, for BLEU, x-BLEU, and m-BLEU; and the
correlations of BLEU to x-BLEU and m-BLEU are of 0.53 and 0.48, respectively,
and x-BLEU and m-BLEU present 0.95 of Pearson correlation.

The results of a repetition of the experiments with chrF as the base metric is
presented in Figure 2, and we observe quite similar outcomes. That is, chrF
correlates weakly with the other metrics and m-chrF correlates strongly to
x-chrF. However, we observe that, unlike the BLEU metrics, the distributions
of chrF, x-chrF, and m-chrF can be seen as centralized, presenting means of
0,54, 0.57, and 0.58, respectively. In terms of Pearson correlation, x-chrF
and m-chrF present almost perfect correlations to each other with 0.99, while
chrF correlates weakly to the other methods, with correlations of 0.56 and
0.55.

What it is very noticeable from these experiments, is that SLA presents a
quite higher correlation to BRS than CLA does, which is strong evidence that
SLA is not only as capable as BRS to compute statistically-robust scores but
also a more-cost-effective option. Moreover, it also indicates that CLA is a
quite less statistically-robust method.

###  4.5 Aggregation methods present strong cross-metric correlation

We now focus on investigating the correlations between the different
aggregation methods of the different BLEU and chrF implementations. The
experiments are analogous to those presented in the previous sections, so in
Figure 3 we present the scatter plot and the Pearson correlation of each pair
of similar implementations, i.e. BLEU vs chrF, x-BLEU vs x-chrF, and m-BLEU vs
m-chrF.

Interestingly, these results indicate that similar aggregation methods
correlate strong with each other. Although the correlation of BLEU to chrF is
the weakest, with 0.77, it is above the 0.50 to 0.55 correlation values that
such metrics presented to the non corpus-level ones. And the non corpus-level
metrics correlate quite strong to each other, since x-BLEU vs x-chrF present a
correlation of 0.88, and m-BLEU vs m-chrF of 0.93. These results indicate
that, as we mentioned in Section 3.2, corpus-level aggregation might biased by
the ratio between n-gram matches and sentence lengths, and that can explain
why BLEU and chrF correlate strong to one another, and weakly to the other
methods.

Figure 3: Correlation plots of the differeent implementations based on the
BLEU and chrF metrics. Figure 4: Correlation plots of the m-BLEU and m-chrF to
the BLEU, chrF, x-BLEU, and x-chrF metrics.

In order to gather additional evidence, in Figure 4 we present a cross-metric
comparison betweem m-BLEU and m-chrF, against BLEU, chrF, x-BLEU, and x-chrF,
respectively. Again, a weak correlation of BLEU and chrF to the non corpus-
level metrics is seen, given that BLEU correlates weakly to x-chrF and m-chrF,
and vice-versa. Moreover, m-BLEU and x-BLEU also correlate strongly to x-chrF
and m-chrF, respectively, indicating that the corpus-level aggregation
introduces a bias that can hinder the statistical robustness of lexical
metrics.

###  4.6 Characterizing the statistical robustness of CLA and SLA

Given that one main outcome from the previous section is that corpus-level
aggregation (CLA) metrics correlate weakly to their more statistically robust
counterparts such as bootstrap-resampled scores (BRS), and that the segment-
level aggregated (SLA) metrics correlate strongly to BRS, in this section we
focus at investigating the statistical robustness of the aggregation methods.

Our methodology consists of using BRS as an upper bound for statistical
robustness for system-level scores, since they rely on the well-known
bootstrap resampling method, and on not only evaluating the correlation
between the distributions of BRS-based scores against downsampled versions of
both CLA- and SLA-based scores, but also the correlation of these downsampled
metrics to each other. With this approach we believe we can understand the
sensitiveness of the aggregation methods to the number of samples and how
their statistical robustness is affected by the number of samples.

In greater detail, we created downsampled test sets for each of 492 datasets,
considering three different sizes, i.e. $N=\\{1,10,100\\}$, and computed
scores with both CLA- and SLA-based metrics on each of these downsampled test
sets. Then, we computed the Pearson correlation between the scores of these
downsampled version of each aggregation method and between these scores and
the more statistically-robust ones computed with BRS. This process were
repeated 1,000 times for a better statistical estimate. The distribution of
correlations, for both BLEU- and chrF-related evaluations, are presented in
Figure 5.

Figure 5: Boxplots of the correlations of downsampled (DS) m-BLEU scores to
BLEU and x-BLEU, and of m-chrF scores to chrF and x-chrF.

The results show that CLA-based metrics are statistically weak. That is, as we
can see in both top and bottom left-most plots, the downsampled CLA- and SLA-
based metrics correlate strongly only in the case of datasets with only one
sample, i.e. $N=1$, with correlation values approaching 1.0. Nevertheless, as
the number of samples increases, their correlation reduces quite drastically,
to about 0.7 with $N=10$ and about 0.6 with $N=100$. That means that,
statistically speaking, we can claim that those metrics differ considerably to
each other.

We can go further and dare to claim that an evaluation of an entire test set
with CLA is similar to conducting the evaluation of the same system with just
a single sample. In the central plots of Figure 5, we can see that the
correlation of their downsampled scores to the more statistically-robust BRS-
based methods does not increase, or increases very insignificantly, with the
number of samples. On the other hand, as we can observe in the right-most
plots of the same figure, the correlation of donwsampled SLA-based metrics
correlate weakly with the bootstrapped scores with $N=1$, but the correlation
increases significantly with $N=10$ and $N=100$, showing that this aggregation
method does not suffer from the same lack-of-statistical-robustness problem.

##  5 Impact of the aggregation method

In order to materialize the actual impact of the aggregation method in
computing system-level scores, in this section we present an evaluation
comparing the scores of the metrics described in Section 4 compared to ground-
truth data from human judgements. For that we rely on three language pairs
with Multidimensional Quality Measurements (MQM), used to benchmark metrics
for the WMT23 Metrics Shared Task [3]. The human scores are computed with the
weighted average of the multiple dimensions. To present a more extensive
evaluation, we also consider the eight language pairs annotated with Direct
Assessment (DA) scores666We relied on the DA assessments available in the
wmt23 folder of the data downloaded with the code in
https://github.com/google-research/mt-metrics-eval.

By evaluating MQM and DA data individually, we compute the mean Pearson
correlation of the system scores from each language pair to the implementation
of BLEU and chrF described in Section 4. Again, we consider plain Pearson
correlation values, ranging from -1 to 1. For comparison purposes, we also
include three neural metrics to present a better reference point related the
impact of the aggregation method compared with these more robust metrics:
COMET777Unbabel/wmt22-cometkiwi-da base model
888https://github.com/Unbabel/COMET, BLEURT999BLEURT-20 base
model101010https://github.com/google-research/bleurt, and BERTScore111111bert-
base-multilingual-cased base model121212https://github.com/Tiiiger/bert_score.

The results are presented in Table 1, where we list the rankings of the
metrics according to their correlation to the human-annotated data. The
results, interestingly, show that the SLA-based methods, i.e. m-BLEU and
m-chrF, not only considerably outperform BLEU and chrF, the CLA-based ones,
but also that they provide correlations that are much closer to those of the
neural metrics. We can also see that, with chrF and MQM annotations, we can
improve from a moderate-to-low correlation of 0.392 to a strong correlation of
0.806, which is just 0.049 correlation points weaker than the correlation of
BERTScore and just 0.066 of BLEURT. With the DA annotations, we can observe
that m-chrF performs even closer to the neural metrics. Notice that the SLA-
based metrics also outperform their BRS counterparts, i.e. x-BLEU and x-chrF,
demonstrating again the statistical robustness of the SLA method.

Table 1: Rankings of Person correlations from metric scores to human judgements | MQM | DA
---|---|---
| metric | corr. | metric | corr.
1 | COMET | 0.923 | COMET | 0.926
2 | BLEURT | 0.872 | BLEURT | 0.917
3 | BERTScore | 0.855 | BERTScore | 0.821
4 | m-chrF | 0.806 | m-chrF | 0.802
5 | x-chrF | 0.804 | x-chrF | 0.793
6 | m-BLEU | 0.776 | m-BLEU | 0.729
7 | x-BLEU | 0.762 | x-BLEU | 0.456
8 | BLEU | 0.425 | chrF | 0.285
9 | chrF | 0.392 | BLEU | -0.006

##  6 Final discussion

In this work we presented a comparison of the traditional corpus-level
aggregation against the less popular method based on averaging individual
segment-level scores, showing that the latter can generate system evaluation
scores which correlate stronger to human judgements and to neural metrics. We
demonstrate that this difference happens because of a fundamental mathematical
difference: CLA metrics are biased towards the performance on long sentences,
considerably reducing the capability of lexical metrics to correlate with
human judgements when corpus-level aggregation is considered. The main issue
we observed is that corpus-level aggregation voids the statistical robustness
of a test set-based evaluation, providing scores that are comparable to
evaluations with a single sample.

One main outcome of this paper should be regarded as a clear recommendation of
MT researchers: stop using corpus-level aggregation. As we show, segment-level
aggregation is not only better than corpus-level in terms of correlation to
human judgments, but also comparable, if not better, than robust statistical
evaluations based on bootstrap resampling. Similarly, MT researchers should
use segment-level scores for statistical evaluation instead of the expensive
computations for bootstrap resampling, although one could also bootstrap
resample segment-level scores to get even more robust estimates.

Finally, we would like to draw the attention for the vast application field
that lexical metrics still have since neural metrics cover only about a
hundred or so languages. Moreover, it is important to understand that some of
the bad reputation which lexical metrics received in the past years might be
under-deserved because of the wide, but wrong, adoption of corpus-level
aggregation.

##  7 Limitations

One clear limitation of this work is relying on a single data source, which is
the WMT23 Shared Task dataset. Nevertheless, since it is a very recent
dataset, considerably large, and coming from a very well-known workshop on
machine translation, we believe that this dataset is strong enough to
experimentally provide evidence as used in our empirical evaluations.

Another limitation is to rely on a single tool to compute BLEU and chrF, which
is SacreBLEU, even though there are other implementations available. Again,
since this tool can be viewed as a de facto standard BLEU implementation [21],
we believe that the tool is strong enough to experimentally prove our
assumptions in the empirical evaluation.

Additionally, we have not thoroughly evaluated the metrics, in the sense of
changing parameters of the metrics such as the maximum n-gram lengths and thus
forth. We stayed with the default SacreBLEU’s parameters only. But again,
given the level of impact the changing the aggregation method presents, as we
show, we do not believe that simply changing the base metrics’ parameters
would affect significantly the outcomes of this paper.

##  8 Ethical considerations

We are not aware of any ethical issue that this paper might raise. All of the
data used for this research are publicly-available, and the outcomes of this
paper are likely to contribute to improving the quality of the research of the
whole machine translation community.

## References

  * [1] Emanuele Bugliarello, Sabrina J. Mielke, Antonios Anastasopoulos, Ryan Cotterell, and Naoaki Okazaki.  It’s easier to translate out of English than into it: Measuring neural translation difficulty by cross-mutual information.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1640–1649, Online, July 2020. Association for Computational Linguistics.
  * [2] Mingda Chen, Paul-Ambroise Duquenne, Pierre Andrews, Justine Kao, Alexandre Mourachko, Holger Schwenk, and Marta R. Costa-jussà.  BLASER: A text-free speech-to-speech translation evaluation metric.  In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9064–9079, Toronto, Canada, July 2023\. Association for Computational Linguistics.
  * [3] Markus Freitag, Nitika Mathur, Chi-kiu Lo, Eleftherios Avramidis, Ricardo Rei, Brian Thompson, Tom Kocmi, Frederic Blain, Daniel Deutsch, Craig Stewart, Chrysoula Zerva, Sheila Castilho, Alon Lavie, and George Foster.  Results of WMT23 metrics shared task: Metrics might be guilty but references are not innocent.  In Philipp Koehn, Barry Haddow, Tom Kocmi, and Christof Monz, editors, Proceedings of the Eighth Conference on Machine Translation, pages 578–628, Singapore, December 2023. Association for Computational Linguistics.
  * [4] Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, Eleftherios Avramidis, Tom Kocmi, George Foster, Alon Lavie, and André F. T. Martins.  Results of WMT22 metrics shared task: Stop using BLEU – neural metrics are better and more robust.  In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 46–68, Abu Dhabi, United Arab Emirates (Hybrid), December 2022\. Association for Computational Linguistics.
  * [5] Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, George Foster, Alon Lavie, and Ondřej Bojar.  Results of the WMT21 metrics shared task: Evaluating metrics with expert-based human evaluations on TED and news domain.  In Proceedings of the Sixth Conference on Machine Translation, pages 733–774, Online, November 2021. Association for Computational Linguistics.
  * [6] Dennis Fucci, Marco Gaido, Sara Papi, Mauro Cettolo, Matteo Negri, and Luisa Bentivogli.  Integrating language models into direct speech translation: An inference-time solution to control gender inflection.  In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 11505–11517, Singapore, December 2023. Association for Computational Linguistics.
  * [7] Yvette Graham and Timothy Baldwin.  Testing for significance of increased correlation with human judgment.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 172–176, Doha, Qatar, October 2014\. Association for Computational Linguistics.
  * [8] Josef Jon and Ondřej Bojar.  Breeding machine translations: Evolutionary approach to survive and thrive in the world of automated evaluation.  In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2191–2212, Toronto, Canada, July 2023\. Association for Computational Linguistics.
  * [9] Juraj Juraska, Mara Finkelstein, Daniel Deutsch, Aditya Siddhant, Mehdi Mirzazadeh, and Markus Freitag.  MetricX-23: The Google Submission to the WMT 2023 Metrics Shared Task.  In Philipp Koehn, Barry Haddow, Tom Kocmi, and Christof Monz, editors, Proceedings of the Eighth Conference on Machine Translation, pages 756–767, Singapore, December 2023. Association for Computational Linguistics.
  * [10] Philipp Koehn.  Statistical significance tests for machine translation evaluation.  In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, pages 388–395, Barcelona, Spain, July 2004. Association for Computational Linguistics.
  * [11] Yijin Liu, Fandong Meng, Yufeng Chen, Jinan Xu, and Jie Zhou.  Scheduled sampling based on decoding steps for neural machine translation.  In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3285–3296, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
  * [12] Michela Lorandi and Anya Belz.  High-quality data-to-text generation for severely under-resourced languages with out-of-the-box large language models.  In Yvette Graham and Matthew Purver, editors, Findings of the Association for Computational Linguistics: EACL 2024, pages 1451–1461, St. Julian’s, Malta, March 2024. Association for Computational Linguistics.
  * [13] Nitika Mathur, Timothy Baldwin, and Trevor Cohn.  Tangled up in BLEU: Reevaluating the evaluation of automatic machine translation evaluation metrics.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4984–4997, Online, July 2020. Association for Computational Linguistics.
  * [14] Xing Niu, Prashant Mathur, Georgiana Dinu, and Yaser Al-Onaizan.  Evaluating robustness to input perturbations for neural machine translation.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 8538–8544, Online, July 2020. Association for Computational Linguistics.
  * [15] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics.
  * [16] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics.
  * [17] Maja Popović.  chrF: character n-gram F-score for automatic MT evaluation.  In Proceedings of the Tenth Workshop on Statistical Machine Translation, pages 392–395, Lisbon, Portugal, September 2015. Association for Computational Linguistics.
  * [18] Maja Popović.  chrF: character n-gram F-score for automatic MT evaluation.  In Proceedings of the Tenth Workshop on Statistical Machine Translation, pages 392–395, Lisbon, Portugal, September 2015. Association for Computational Linguistics.
  * [19] Maja Popović.  chrF++: words helping character n-grams.  In Proceedings of the Second Conference on Machine Translation, pages 612–618, Copenhagen, Denmark, September 2017. Association for Computational Linguistics.
  * [20] Matt Post.  A call for clarity in reporting BLEU scores.  In Proceedings of the Third Conference on Machine Translation: Research Papers, pages 186–191, Brussels, Belgium, October 2018. Association for Computational Linguistics.
  * [21] Matt Post.  A call for clarity in reporting BLEU scores.  In Proceedings of the Third Conference on Machine Translation: Research Papers, pages 186–191, Brussels, Belgium, October 2018. Association for Computational Linguistics.
  * [22] Ricardo Rei, Ana C Farinha, José G.C. de Souza, Pedro G. Ramos, André F.T. Martins, Luisa Coheur, and Alon Lavie.  Searching for COMETINHO: The little metric that could.  In Proceedings of the 23rd Annual Conference of the European Association for Machine Translation, pages 61–70, Ghent, Belgium, June 2022\. European Association for Machine Translation.
  * [23] Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie.  COMET: A neural framework for MT evaluation.  In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2685–2702, Online, November 2020. Association for Computational Linguistics.
  * [24] Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie.  COMET: A neural framework for MT evaluation.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2685–2702, Online, November 2020\. Association for Computational Linguistics.
  * [25] Thibault Sellam, Dipanjan Das, and Ankur Parikh.  BLEURT: Learning robust metrics for text generation.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7881–7892, Online, July 2020. Association for Computational Linguistics.
  * [26] Thibault Sellam, Dipanjan Das, and Ankur P Parikh.  Bleurt: Learning robust metrics for text generation.  In Proceedings of ACL, 2020.
  * [27] Yu Wan, Dayiheng Liu, Baosong Yang, Haibo Zhang, Boxing Chen, Derek Wong, and Lidia Chao.  UniTE: Unified translation evaluation.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8117–8127, Dublin, Ireland, May 2022. Association for Computational Linguistics.
  * [28] Tianyi Zhang*, Varsha Kishore*, Felix Wu*, Kilian Q. Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  In International Conference on Learning Representations, 2020.

##  Appendix A An comprehensive evaluation of of the use of lexical metrics in
recent machine translation papers

Table 2: Metrics used in 345 recent MT papers (a single paper may use more than one metrics). Metric | Total | %
---|---|---
BLEU | 341 | 98.8
COMET | 36 | 10.4
chrF | 30 | 8.4
METEOR | 17 | 4.9
BERTScore | 15 | 4.3
TER | 15 | 4.3
BLEURT | 10 | 2.9
BLONDE | 3 | 0.8
UniTE | 3 | 0.8
Others | 17 | 4.9
Table 3: Distribution of BLEU implementations in 341 recent MT papers which used BLEU as a metric. Metric | Total | %
---|---|---
BLEU (inferred) | 210 | 60.1
Unclear | 122 | 36.2
BLEU (explictly) | 6 | 1.7
x-BLEU | 3 | 0.9
m-BLEU | 1 | 0.3

In this section we present an evaluation of the usage of lexical metrics in MT
papers. To demonstrate the impact of our results, we analysed MT-related
papers published in recent editions of _ACL_ and _EMNLP_ , two of the major
venues for MT research, and catalogued the ways the evaluation of MT systems
are reported.

We inspected 345 papers which contained evaluations of MT systems published in
the past four editions of ACL and EMNLP conferences, i.e. from 2020 to 2023.
We selected those papers both by searching for terms such as _Translation_ ,
_Machine Translation_ , _MT_ , and _BLEU_ in the title, and by a further fine-
grained manual inspection. We considered all papers that conducted evaluations
of systems for MT-related tasks, an average of 43.12 per conference edition.

The distribution of metrics that appear in those papers is presented in Table
2. All but only 4 out of 345 papers did not report the use of BLEU, meaning
that BLEU was employed by 98.8% of papers we inspected. Also, the adoption of
neural metrics is still low, with COMET being the metric with the most
prominent level of usage, but only in 10.4% of the papers. Notice that all
neural metrics combined are reported in less than 1/4 of the papers, i.e.
about 80 papers, considering also all the 17 metrics with less than 3 mentions
grouped in the Others row.

Given the domination of the BLEU score in these papers, we then conducted a
study on understanding what aggregation methods for this specific lexical
metric are used and report the results in Table 3. Only 10 papers explicitly
mention the aggregation method used for BLEU, where 6 of them explicitly
mention that they are using corpus-level aggregation (simply BLEU in the
table), 3 stated they are using averages of bootstrapped resamplings (x-BLEU),
and only a single paper relies on averages of segment-level BLEU scores
(m-BLEU). For the remaining 335 papers, we inferred the aggregation method by
looking for references of specific tools they used, such as SacreBLEU [21] and
Moses. We observed that 210 papers, 60.1%, contained at least some minimal
references to such tools, being 183 to SacreBLEU and 36 to Moses. Considering
that both tools implement the corpus-level aggregation as default, we
considered that most of these papers relied on corpus-level BLEU, so there is
likely 216 (63%) papers which implemented corpus-level aggregation for BLEU.

Considering that it is likely that about 2/3 of these papers relied on corpus-
level BLEU scores, one first remarkable conclusion is that the results of
those papers should be looked with care considering the low statistical
significance of corpus-level aggregation. However, we noticed that there are
at lest 40 of those papers (about 20%) that rely on bootstrap resamplings to
compute significance tests for system comparisons [10], which can make the
statistical evaluation more robust, even though they in the end reported plain
corpus-level BLEU scores [8, 6].