11institutetext: Claudio Tomasi and Rolf Krause 22institutetext: Università
della Svizzera Italiana,Via Buffi 13, CH-6904 Lugano, 22email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Construction of Grid Operators for Multilevel Solvers: a Neural Network
Approach

Claudio Tomasi and Rolf Krause

##  1 Introduction

Multigrid (MG) methods are among the most successful strategies for solving
linear systems arising from discretized elliptic equations. The main idea is
to combine different levels of approximation in a multilevel hierarchy to
compute the solution: it is possible to show that this algorithm is effective
on the entire spectrum, thus leading to an optimal convergence property
Tomasi_mini_10_braess2007finite ; Tomasi_mini_10_briggs2000multigrid . Common
to all these strategies is the need for the transfer of data or information
between the different grids, or meshes. Therefore, a crucial point for
reaching fast convergence is the definition of transfer operators, but they
are generally problem-dependent. Except for the case of nested meshes, the
computation of these operators is very expensive, and domain knowledge is
always required.

The ever-increasing application of Machine Learning (ML) as support for
methods in scientific computing makes it a natural solution to be employed in
the definition of transfer operators, reducing the costs of their
construction. In Tomasi_mini_10_greenfeld2019learning , the learning of a
mapping between PDEs and operators has been proposed. Another approach is
presented in Tomasi_mini_10_katrutsa2020black , where restriction and
prolongation matrices are optimized while minimizing the spectral radius of
the iteration matrix. As an alternative, the method proposed in
Tomasi_mini_10_luz2020learning  uses Graph Neural Networks, for learning AMG
prolongation operators, having classes of sparse matrices as input.

In this paper, we propose a methodology based on Deep Neural Networks to
define transfer operators based on the concept of $L^{2}$-projection. We take
information from the domain to create several examples and to make our model
learn from experience. Therefore, our focus is the construction of a suitable
training set and a correct loss function definition to create a model that can
be employed in MG solvers. The actual state of the method presents some
limitations related to the mesh structure. An extension to a wider range of
scenarios should be considered in future works.

##  2 Problem Definition

Let $\Omega\subset\mathbb{R}^{n}$ be a domain with Lipschitz boundary and let
$H^{1}_{0}(\Omega)$ be the Sobolev space of one-time weakly differentiable
functions on $\Omega$, with weak derivatives in $L^{2}(\Omega)$. We consider a
multigrid method for the solution of the following problem:

$\mathrm{find}\ u\in V:a(u,v)=f(v)~{}~{}\forall v\in V,$ (1)

where $V\subset H_{0}^{1}(\Omega)$, $a:V\times V\rightarrow\mathbb{R}$ is a
continuous symmetric elliptic bilinear form and $f:V\rightarrow\mathbb{R}$ is
a continuous linear functional. Let $V_{h}\subset V$ be the associated finite
elements space, where $\mathrm{dim}(V_{h})=n_{h}$ and $h>0$, and consider a
conforming shape-regular triangulation $\mathcal{T}_{h}$. For a more rigorous
explanation see e.g. Tomasi_mini_10_quarteroni2009numerical . Furthermore, let
$I_{H}^{h}:\mathbb{R}^{n_{H}}\rightarrow\mathbb{R}^{n_{h}}$ be a transfer
operator which transfers information between $\mathcal{T}_{h}$ and a coarser
grid $\mathcal{T}_{H}$, with $H>h$ and $n_{H}<n_{h}$. We denote with
$A_{h}u_{h}=b_{h}$ the linear system arising from the finite element
discretization of (1).

Let us consider a 2-grid correction scheme for solving the linear system. The
extension to a general multigrid scenario is straightforward. To restrict or
prolong information between coarse and fine grids, we apply $I_{H}^{h}$.
Moreover, we define the coarse problem using the expression
$A_{H}=(I_{H}^{h})^{T}A_{h}~{}I_{H}^{h}$. Hence, the definition of the
transfer operator plays a central role in obtaining a fast convergence of the
method. In Tomasi_mini_10_krause2016parallel , a general definition of
transfer operators between meshes is discussed. Here, we focus on the
$L^{2}$-projection as transfer operator. Let us call it $Q$:

$Q=M_{h}^{-1}B_{h},$

where $M_{h}$ is the mass matrix related to the fine level (grid), and $B_{h}$
is a rectangular coupling operator matrix. The latter relates the two meshes,
and it is computed through their intersection. Since the inverse of $M_{h}$ is
a dense matrix, the computation of $Q$ might become expensive. Therefore, we
use the pseudo-$L^{2}$-projection, where we invert the lumped mass matrix
instead of $M_{h}$. For further reading refer to
Tomasi_mini_10_dickopf2010multilevel ; Tomasi_mini_10_dickopf2009pseudo ;
Tomasi_mini_10_dickopf2011study ; Tomasi_mini_10_dickopf2014evaluating .

###  2.1 Neural Networks

ML algorithms are able to learn from data Tomasi_mini_10_goodfellow2016deep ;
we refer to a single data object calling it example. An example is a
collection of features together with a corresponding target. A feature is a
property that has been measured from some object or event. The target is the
correct response to the features, that the system should be able to reproduce.
We represent an example as a couple $(\mathbf{x},\mathbf{y})$, where
$\mathbf{x}\in\mathbb{R}^{n}$ is the feature set and
$\mathbf{y}\in\mathbb{R}^{m}$ is the target. ML can solve different tasks, as
classification, transcription, and so on. Our focus is regression: we ask the
model to predict numerical values given some inputs. In order to solve this
task, the model is asked to output a function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$. To evaluate the ML algorithm
abilities, we define a measure of its performance, called loss function: for
regression, we select the Mean Squared Error (MSE) indicator.

Neural Networks (NNs) belong to the class of supervised ML algorithms. They
consist of layers of neurons, connected by weighted synapses. A NN defines a
mapping $\mathbf{y}=f(\mathbf{x};\bm{\theta})$ and learns the values of the
parameters $\bm{\theta}$, providing the best function approximation. More
details can be found in Tomasi_mini_10_bishop2006pattern ;
Tomasi_mini_10_larochelle2009exploring .

###  2.2 Training Trasfer Operators

We aim to define a NN model to learn and then predict the transfer operator
$Q$. Specifically, we do not learn directly $Q$, but the coupling operator
$B_{h}$. Once the model is optimized, we employ it as a black box for solving
linear systems of equations in an MG fashion. We proceed by coarsening: we
take $M_{h}$ on the fine level, and we extract the features in input to the
NN. More details on the data extraction from $M_{h}$ are given in Section 3.1.
The model produces parts of $B_{h}$ that combined give rise to the full
operator. We then retrieve the transfer operator $Q$, and we employ it in the
MG algorithm. Furthermore, we use the predicted transfer operators to define
the coarser mass matrix $M_{H}$ using the so-called _Galerkin operator_ ,
i.e., $M_{H}=Q^{\top}M_{h}Q.$
We recursively apply this procedure to define coarser problems, giving rise to
a multilevel hierarchy.

##  3 Training Set

In order to allow the NN to learn, we provide a large number of examples (or
records). We need several distinct examples to be sure of avoiding
overfitting, occurring when the model predictions correspond too closely or
exactly to a particular set of data. Thus, we define classes of examples, and
we choose a fixed amount of records for each class. This allows us to create
an unbiased training set without preferring some classes over others. The
definition of class is related to the mesh from which we extrapolate the
records. We set a number of elements $N$: all the records coming from meshes
with $N$ elements belong to class $C_{N}$.

###  3.1 Records

Given a subset of pre-identified coarse nodes, we extract a record for each of
them. Let $j$ be a coarse node. An example contains information related to
_patch( $j$)_; here, _patch( $j$)_ is the set consisting of node $j$ together
with its neighbors. For each node $k\in$ _patch( $j$)_, we define features and
target as the non-zero entries of the $k$th rows of $M_{h}$ and $B_{h}$,
respectively.

We consider different examples of 2-grid scenarios, where we associate to each
fine mesh one coarse mesh, in order to approximate an actual function. Since
we consider several examples for the same class $C_{N}$, we need a strategy to
avoid duplication inside the dataset. For this purpose, in each example, we
consider the fine mesh and we move the nodes along the edges by a random
quantity, proportional to the step size $h$. Therefore, we create different
elements and consequently different records. We generate the examples in
$C_{N}$, and we proceed to the next class by increasing $N$. Since NN models
allow only fixed input and output dimensions, we define distinct models for 1D
and 2D scenarios.

###  3.2 One-Dimensional Model

The records related to one-dimensional meshes are extracted from scenarios
obtained by coarsening: starting from a randomly generated fine mesh, we
decide which nodes to keep for defining the coarse grid. Here, _patch( $j$)_
consists only of $j$ itself, together with its left and right neighbors. For
each coarse node, we take the information on _patch( $j$)_ from $M_{h}$ and
$B_{h}$ following the strategy explained in Section 3.1, to define each
example.

###  3.3 Two-Dimensional Model

Let us call _patch-size_ the number of nodes in a specific patch: given a node
$j$, its patch-size is the cardinality of the set _patch( $j$)_. In 2D, even
in the same mesh, we can have nodes with different patch-sizes. Hence, we
start considering only a fixed triangulation, such that the nodes would have
the same neighborhood pattern. We will focus on dealing with different patch-
sizes later in the paper, referring to their treatment in the context of NNs.

A crucial point is to find a correct distribution of data in the training set,
in terms of magnitude of the values. Since the NN should not prefer some
examples - thus, some classes - over others, we need to define a correct and
even filling of the training set. As a first approach, we relate the concept
of class to the procedure of refinement. Mesh refinement is a strategy to
increase the accuracy of the solution of a discretized problem. It works as an
iterative procedure applied to the single elements of a mesh. Here we consider
two different strategies: bisection, which halves each element, and mid-point
refinement, which takes the mid-points of each edge and joins them to create
new elements. When we refine, we deal with a new class of examples. Applying a
training algorithm on these data results in a poor ability of approximation
and a large prediction error, making a NN model unfit to work in a MG setting.
The refinement procedure makes the number of elements scale by a factor of 2
(bisection) or 4 (mid-point). In terms of domain of training examples, this
means that the initial classes of records, i.e., $C_{N}$ with $N$ small, are
close to each other, while their distance grows when $N$ increases. This turns
out to produce an uneven training set, without a good balance in terms of data
distribution. For this reason, we need a linear increase in the number of
elements. If the classes of examples are evenly spaced in terms of domain, the
network does not prefer some classes over others. Therefore, a second approach
changes the definition of class, independent of the concept of refinement: we
start from a number $N$, and we create a mesh having exactly $N$ elements.
Once we extract enough records, we proceed to the next class, increasing $N$
by a constant $K$, and create a new mesh with $N+K$ elements. For each class,
we extract the same number of examples. Following this simple procedure, the
resulting training set is effectively unbiased and with a good distribution of
the examples. A learning algorithm applied to these data produces the expected
good approximation. Therefore, a model trained on this dataset can be applied
inside an MG scenario.

##  4 Model Training

A NN optimizes its parameters in order to reduce the prediction error.
Employing MSE as loss function results in good predictions, but the model does
not gain a good generalization property, i.e., the ability to perform well on
previously unobserved inputs.

Regularization helps us overcome this issue: it reduces the hypothesis space,
allowing the NN to have a higher probability of choosing the most correct
function. We introduce in the loss function some penalty terms related to the
domain knowledge. These terms force constraints during the training phase in
order to respect properties that the transfer operator must satisfy.

###  4.1 Regularization

During the construction of the training set, for each coarse node $j$, we
extract patches of $M_{h}$ and parts of $B_{h}$. We use this information to
ask the model to force some rules on the rows of the predicted coupling
operator.

We define the $j$th predicted and actual rows of the operator $Q$ as

$Q_{j}^{\text{pred}}=\frac{1}{\sum
M_{j}}B_{j}^{\text{pred}},\;\;\;\;\;\;\;\;\;Q_{j}^{\text{true}}=\frac{1}{\sum
M_{j}}B_{j}^{\text{true}},$ (2)

where $\Phi_{j}$ denotes the $j$th row of the operator
$\Phi=\\{M_{h},B_{h}\\}$.

We know that the predicted transfer operator should preserve constants (more
details can be found in (Tomasi_mini_10_dickopf2010multilevel, , Section
3.2)). Hence, we consider the following penalty terms to specialize our loss
function:

$\displaystyle\|Q_{j}^{\text{pred}}\cdot\mathds{1}_{H}-\mathds{1}_{h}\|_{{}_{2}},$
$\displaystyle\|Q_{j}^{\text{pred}}-Q_{j}^{\text{true}}\|_{{}_{2}},$ (3)

where $\|\cdot\|_{{}_{2}}$ denotes the Euclidean norm, $\mathds{1}_{H}$ and
$\mathds{1}_{h}$ the all-ones vectors of dimensions $n_{H}$ and $n_{h}$,
respectively. We then define, for all the nodes $k\in\;$_patch( $j$)_

$p_{k}=\frac{1}{\alpha}\|Q_{k}^{\text{pred}}\cdot\mathds{1}_{H}-\mathds{1}_{h}\|_{{}_{2}}\,+\,\frac{1}{\beta}\|Q_{k}^{\text{pred}}-Q_{k}^{\text{true}}\|_{{}_{2}},$
(4)

where $0<\alpha,\beta<1$.

Therefore, we define the loss function as

$\mathscr{L}(y_{\text{true}},y_{\text{pred}})=MSE(y_{\text{true}},y_{\text{pred}})+\sum_{k}p_{k}.$
(5)

Adopting the latter during the training phase, in addition to minimize the
simple distance between target and prediction, we aim to respect the above
properties related to the transfer operator.

###  4.2 Model Details

We use a classic splitting for our dataset: $20\%$ for test and $80\%$ for
training, where the latter is divided again in $20\%$ for the validation set
and the remaining for the training phase. For a preliminary examination of the
method, we used around $500.000$ examples. For both one- and two-dimensional
models, we adopt Adam as optimizer. Regarding the architecture, we report here
only the structure for the 2D scenario used as initial test: we need at least
$20$ hidden layers, where for each of them we use $800$ neurons, for a total
of $12$ million parameters. Through further investigations and several tests,
the NN complexity can be improved, giving rise to less expensive computations.
We initialize our weights using a normal distribution, using the methods
provided by Tensorflow. In the context of the NN definition, more extensive
works should be devoted to study the sensitivity of the predictions while
changing the NN parameters.

##  5 Numerical Results

We test our NNs for both prediction accuracy and their application in an MG
setting. We compare our method with the Semi-Geometric multigrid (SGMG) method
(see (Tomasi_mini_10_dickopf2010multilevel, , Chapter 3)), which adopts the
$L^{2}$-projection computed through intersections between meshes. In addition
to the convergence, we consider the difference in the time spent to assemble
the transfer operator. For our method, we take into account patches
extraction, predictions, assembly of $B$ and the computation of the operator.
Regarding the computation of the actual $L^{2}$-projection we consider the
time spent for intersecting fine and coarse mesh, triangulation for each
intersecting polygon and numerical integration. We test the method on one-
dimensional examples, and the results are good as expected, considering two or
more levels. Our method converges with the same number of iterations as the
SGMG method. Comparing the CPU time spent in creating the transfer operators,
we see that the predicted one is assembled faster than the other since it
depends only on the problem dimensions.

During the test on two-dimensional settings we need to deal with different
patch-sizes, as described in Section 3.3. Even if we consider a simple regular
mesh, the nodes near the boundaries have fewer neighbors than the internal
nodes. A preliminary solution requires the mesh to be extended, to make all
the nodes have the same patch-size. Virtually, we add neighbors to those nodes
having a smaller patch in the given mesh. Using this expedient, the method
works, and we can test the convergence against the SGMG method. Extending the
mesh shows to be useful for an initial application of MG, but it is very
expensive in terms of computations. Increasing the degrees of freedom (dofs),
we would have more and more virtual nodes to add and heavier computations to
carry out. Therefore, we consider different NNs, each of them defined and
optimized for a specific patch-size.

Fig. 1 shows the performance of the method on a two-dimensional scenario: in
the left picture, we compare the convergence of our method against the
convergence of Semi-Geometric MG; in the right picture we compare the CPU time
spent in both methods.

Figure 1: Convergence of 2D Neural MG against SGMG on an example of 100.000
dofs (left). Comparison of CPU time between the two methods, increasing the
dofs (right).

##  6 Conclusion

This work presented the study and definition of a methodology to construct NNs
to predict transfer operators for MG solvers. Starting from a one-dimensional
case, we built an unbiased training set allowing the optimization of a model,
which brought very good results in an MG context. Reproducing the same
methodology, we approached the two-dimensional setting, which gave us the
chance to better define a training set for this kind of methods. Furthermore,
we could test our method using different input-sized neural networks,
resulting in fast convergence and bringing a great speedup in the computation
of the transfer operator. The same procedure can be employed for constructing
models to deal with a general $N$-dimensional scenario. Given the limitations
of this method at its current state, further investigations should be devoted
to overcome the necessity of having multiple NNs modeled on different patch-
sizes, in order to define a general strategy for solving arbitrary problems.
Future works should extend the method to deal with a wider class of
triangulation, and for applications in other Multilevel scenarios.

## References

  * (1) C. M. Bishop.  Pattern recognition and machine learning.  Information Science and Statistics. Springer, New York, 2006.
  * (2) D. Braess.  Finite elements: Theory, fast solvers, and applications in solid mechanics.  Cambridge University Press, 2007.
  * (3) W. L. Briggs, V. E. Henson, and S. F. McCormick.  A multigrid tutorial.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 2000.
  * (4) T. Dickopf.  On multilevel methods based on non-nested meshes.  PhD Thesis, 2010.
  * (5) T. Dickopf and R. Krause.  A pseudo-${L}^{2}$-projection for multilevel methods based on non-nested meshes.  INS Preprint, 908, 2009.
  * (6) T. Dickopf and R. Krause.  A study of prolongation operators between non-nested meshes.  In Domain decomposition methods in science and engineering XIX, volume 78 of Lect. Notes Comput. Sci. Eng., pages 343–350. Springer, Heidelberg, 2011.
  * (7) T. Dickopf and R. Krause.  Evaluating local approximations of the $L^{2}$-orthogonal projection between non-nested finite element spaces.  Numer. Math. Theory Methods Appl., 7(3):288–316, 2014.
  * (8) I. Goodfellow, Y. Bengio, and A. Courville.  Deep learning.  Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2016\.
  * (9) D. Greenfeld, M. Galun, R. Basri, et al.  Learning to optimize multigrid pde solvers.  In International Conference on Machine Learning, pages 2415–2423. PMLR, 2019.
  * (10) A. Katrutsa, T. Daulbaev, and I. Oseledets.  Black-box learning of multigrid parameters.  J. Comput. Appl. Math., 368:112524, 12, 2020.
  * (11) R. Krause and P. Zulian.  A parallel approach to the variational transfer of discrete fields between arbitrarily distributed unstructured finite element meshes.  SIAM J. Sci. Comput., 38(3):C307–C333, 2016.
  * (12) H. Larochelle, Y. Bengio, J. Louradour, and P. Lamblin.  Exploring strategies for training deep neural networks.  Journal of machine learning research, 10(1), 2009.
  * (13) I. Luz, M. Galun, H. Maron, et al.  Learning algebraic multigrid using graph neural networks.  In International Conference on Machine Learning, pages 6489–6499. PMLR, 2020.
  * (14) A. Quarteroni.  Numerical models for differential problems, volume 2.  Springer, 2009.


# REAM$\sharp$: An Enhancement Approach to Reference-based Evaluation Metrics
for Open-domain Dialog Generation

Jun Gao
Tencent AI Lab, Shenzhen, China
<EMAIL_ADDRESS>
Wei Bi
Tencent AI Lab, Shenzhen, China
<EMAIL_ADDRESS>
Ruifeng Xu∗
Peng Cheng Laboratory, Shenzhen, China
<EMAIL_ADDRESS>
Shuming Shi
Tencent AI Lab, Shenzhen, China
<EMAIL_ADDRESS>Corresponding authors

###### Abstract

The lack of reliable automatic evaluation metrics is a major impediment to the
development of open-domain dialogue systems. Various reference-based metrics
have been proposed to calculate a score between a predicted response and a
small set of references. However, these metrics show unsatisfactory
correlations with human judgments. For a reference-based metric, its
reliability mainly depends on two factors: its ability to measure the
similarity between the predicted response and the reference response, as well
as the reliability of the given reference set. Yet, there are few discussions
on the latter. Our work attempts to fill this vacancy. We first clarify an
assumption on reference-based metrics that, if more high-quality references
are added into the reference set, the reliability of the metric will increase.
Next, we present REAM$\sharp$: an enhancement approach to Reference-based
EvAluation Metrics111Interested reader may contact the authors to obtain a
copy of the code and the data. for open-domain dialogue systems. A prediction
model is designed to estimate the reliability of the given reference set. We
show how its predicted results can be helpful to augment the reference set,
and thus improve the reliability of the metric. Experiments validate both the
effectiveness of our prediction model and that the reliability of reference-
based metrics improves with the augmented reference sets.

##  1 Introduction

The lack of reliable automatic evaluation metrics is a major impediment to the
development of open-domain dialogue systems (Li and Jurafsky, 2016; Gao et
al., 2019; Li et al., 2020a). The underlying difficulty in evaluation lies in
the diversity of the possible outcomings. Existing evaluation metrics for
open-domain dialogue systems can be roughly divided into reference-based and
reference-free metrics. Reference-based metrics usually measure how similar a
generated response is to the reference responses. Reference-free metrics, on
the other hand, measure the quality of a response without any reference and
usually focus on specific aspects of the responses. For example, much work
often computes the perplexity of a generated response as a measure of fluency
(Li et al., 2020b), and adopts Dist-1/2 (Li et al., 2016b) to measure the
diversity of the response. In this work, we focus on reference-based metrics.

BLEU (Papineni et al., 2002), originally for machine translation, is now a
popular reference-based metric to evaluate open-domain dialog systems
automatically. However, it has been shown that BLEU and other word-overlap
metrics such as METEOR (Banerjee and Lavie, 2005) and ROUGE (Lin, 2004), rely
on surface-form similarities only without considering the semantic diversity,
thus fail to correlate well with human judgements (Liu et al., 2016). Instead,
embedding-based metrics are adopted to consider the semantic meaning of a word
defined by a distributed representation. For example, Zhang et al. (2020)
introduce an embedding-based metric BERTScore that computes the similarity
between the generated response and reference responses using contextual
embeddings obtained from BERT (Devlin et al., 2019).

Intuitively, the reliability of a referenced-based metric depends on two
factors: (1) the ability of the metric to measure the similarity between the
generated response and the reference response and (2) the reliability of the
reference set for evaluating each generated response. As can be seen from
above, most current work falls into improving the former factor, while few
considers the latter. However, without a high-quality reference set, the
results obtained by all these metrics will have a poor correlation with human
judgments.

Unlike most previous studies that propose new evaluation metrics, the focus of
our study is on improving the reliability of the reference set. We first
clarify an assumption on reference-based metrics that, if more high-quality
responses are added into the reference set, the correlation of reference-based
metrics with human judgments will increase. We perform experiments to
demonstrate that the standard BLEU Papineni et al. (2002) does not hold this
assumption, but two existing metrics can. One is a modified BLEU metric
Freitag et al. (2020) that compares the generated response with each reference
response within the set using single-reference BLEU. We refer this modified
BLEU as BLEU*. The other is the BERTScore Zhang et al. (2020), which can also
be used to evaluate responses with multiple references.

In this work, we propose REAM$\sharp$: an enhancement approach to Reference-
based EvAluation Metrics for open-domain dialogue systems. Our approach, which
can enhance a reference-based metric that satisfies our assumption (such as
BLEU* and BERTScore), consists of two parts: (1) reliability prediction and
(2) high-quality references augmentation. In the first part, we devise a
reliability prediction model to estimate the reliability of the reference set.
Given a query and its reference set, the model will predict a reliability
score to reflect how reliable a metric is used to evaluate the results of the
query using the given reference set. In the second part, we aim to augment
high-quality references with the help of the reliability prediction model. We
introduce two ways to handle reference candidates with different qualities. If
the acquired reference candidates are considered reliable, we can adopt
automatic annotation. If we are not certain about the relevance of the
reference candidates, human annotators are needed for an interactive
annotation. Experimental results show that our proposed approach can
effectively enhance the reliability of the reference set and improve the
correlation of the reference-based metrics BLEU* and BERTScore.

The rest of this paper is organized as follows. In Section 2, we introduce our
assumption on the reference-based metrics, and conduct a series of preliminary
experiments to validate this assumption on existing metrics. We also provides
details about data collection and metric evaluation in this section. Section 3
describes our reliability prediction model and Section 4 presents how to
augment high-quality references with the help of the proposed reliability
prediction model. Section 5 shows our experimental results about the proposed
reliability prediction model as well as different strategies to augment the
reference set. Section 6 describes related work. Finally, we conclude our work
and discuss some future work in Section 7.

##  2 Research Questions and Settings

We first make an assumption on reference-based metrics for open-domain dialog
system that if more high-quality reference responses are added to the
reference set, a reference-based metric will show a higher correlation with
human judgments. We want to draw such an assumption due to two considerations.
First, by considering the nature of open-domain dialog, a query is possible to
be relevant to multiple diverse responses. Including more relevant responses
in the reference set can naturally help alleviate the assessment difficulty
associated with linguistic variation. Second, if a low-quality response, e.g.
a general response “I don’t know” is added to the reference set, the
reference-based metric will assign a very high score for the same low-quality
predicted response, resulting in a low correlation. Therefore, only by
ensuring that the responses in the reference set are of high-quality can we
avoid the metric assigning high scores to low-quality responses.

We validate this assumption on three existing metrics: the original multi-
reference BLEU Papineni et al. (2002), BLEU* (Freitag et al., 2020) and
BERTScore (Zhang et al., 2020). The original BLEU uses a modified form of
precision to compare a generated response against multiple reference
responses. For BLEU* and BERTScore, the multi-reference score of a response
$y$ can be computed as:

$score(y,R)=\mathop{\mathrm{max}}\limits_{r\in R}d(y,r)$ (1)

where $d$ is the given metric, $R=\\{r_{1},r_{2},\cdots,r_{n}\\}$ is the given
reference set.

We examine the assumption by answering the following questions:

  1. 1.

Will the correlation of the reference-based metric improve when more high-
quality responses are added to the reference set?

  2. 2.

How will the low-quality responses included in the reference set affect the
correlation of the reference-based metric?

Before presenting the details of the preliminary experiments, we first
describe the data collection used in the experiments and how we estimate the
reliability of a metric.

###  2.1 Data Collection and Metric Evaluation

To evaluate the correlation of reference-based metrics with human judgments,
we collect a dataset as follows. We first crawled 5,000 queries from some
Chinese social websites and the largest reference set for the obtained queries
has 200 responses. Then, we generated 14 responses obtained from several
widely used response generation models (described in Appendix A). We asked 5
annotators to assign each generated response with a score ranging from 1 to 5
respectively, and the final score of each response was obtained by averaging
the five scores. Table 1 shows the data statistics. See Appendix A for a
detailed description of our dataset.

Raw Dataset |
---|---
# Training Samples | 4,000
# Validation Samples | 500
# Test Samples | 500
Each Sample |
# Model Responses | 14
# Reference Responses |  $\leq$ 200
Table 1: Our dataset statistics. Each sample is in the form (query, model
responses, reference responses).

To evaluate the performance of a metric, we leverage the Pearson Correlation.
Given a sample consisting of a query $\bm{q}$, 14 generated responses
$\bm{\mathcal{Y}}=\\{\bm{y}_{1},\cdots,\bm{y_{14}}\\}$ with their human
annotated scores
$\hat{\bm{S}}=\\{\hat{\bm{s}}_{1},\cdots,\hat{\bm{s}}_{14}\\}$ and a set of
reference responses $\bm{\mathcal{R}}=\\{\bm{r}_{1},\cdots,\bm{r}_{n}\\}$
($n\leq 200$), we first score each model response $\bm{y}\in\bm{\mathcal{Y}}$
with a certain metric, yielding a sequence of automatic evaluated scores
$\bm{S}=\\{s_{1},\cdots,s_{14}\\}$. With the automatic evaluated scores
$\bm{S}$ and human annotated scores $\hat{\bm{S}}$ for the 14 generated
responses, we can obtain the reliability score $c$ for each sample using the
Pearson Correlation:

$c=\mathrm{Pearson}(\bm{S},\hat{\bm{S}}).$ (2)

###  2.2 Preliminary Experiments

Next, we conduct our preliminary experiments using the 500 samples in the test
set and present our empirical observations regarding the two questions in
beginning of Section 2. In the experiments in this section, the correlation of
a certain metric is obtained by averaging the reliability scores over all 500
samples.

First, we would like to see how it affects the correlation of the metrics when
high-quality responses are continuously added to the reference set. To ensure
that each added reference response is of high quality, we also have human
annotators assign a quality score to each crawled reference response, and then
randomly select 10 high-quality reference responses (quality score over 4) for
each sample in the test set. We sequentially add the 10 high-quality reference
responses to the reference set initialized with an empty set. Each time a new
reference response is added to the set, we calculate a reliability score of a
certain metric using the updated set. Figure 1 shows the evaluation results of
the original BLEU, BLEU* and BERTScore. Noticeably, the correlation of the
original BLEU does not improve as the number of high-quality sentences
increases. The reason may be that the original BLEU is defined at the corpus-
level and the n-gram precisions are sums over all corpus sentences, which
means the newly added reference will cause the value to fluctuate. We,
however, find that BLEU* and BERTScore are consistent with our assumption that
the correlation of the metric improves as the number of high-quality responses
in the set increases. Therefore, not all metrics meet our assumption, and we
use BLEU* and the BERTScore for our following experiments.

Second, we test how low-quality responses would affect the correlation of the
metric by adding noise into the reference set. In the noisy reference set, the
first 5 responses in the reference set are added with the same high-quality
responses as above, while the later 5 added responses are replaced with
negative samples which are responses sampled from other queries. As shown in
Figure 1, “BLEU*-noisy” and “BERTScore-noisy” denote the results of BLEU* and
BERTScore using the noisy reference sets, respectively. As the number of
negative samples in the set increases, the performance of the metrics starts
to degrade. This further confirms our assumption that only adding more high-
quality responses to the reference set will help the metric.

Based on the above analysis, we can see that for reference-based metrics
satisfying our assumption, we can enhance its reliability by augmenting high-
quality references to calculate the metric. Next, a key question arises, how
can we augment high-quality references? In the following, we propose a
reliability prediction model to estimate the reliability of the reference set
(Section 3) and provide effective approaches to augment high-quality
references with the help of the reliability prediction model (Section 4).

Figure 1: Pearson correlations of BLEU, BLEU* and BERTScore with human
judgements obtained using different numbers of reference responses.

##  3 The Reliability Prediction Model

In this section, we aim to estimate the reliability of a metric, when we use
it to compute a performance score of an output response based on a given gold
response set. We formulate this task as a regression problem. Formally, given
a query sentence $\bm{q}=\\{q_{1},\dots,q_{M}\\}$ of length $M$, and a
reference set $\mathcal{R}=\\{\bm{r}_{i}\\}_{i=1}^{N}$ with $N$ gold responses
of the query, our goal is to learn a function
$\bm{f}:(\bm{q},\mathcal{R})\rightarrow c$ that predicts a reliability score
$c$ that represents how reliable a metric is used to evaluate results of the
input query using this reference set. In this work, we consider using Pearson
correlation ($c$) in Eq. 2 between the human evaluation results and the metric
scores from the given $\mathcal{R}$ as the reliability score of each
$(\bm{q},\mathcal{R})$. We introduce the reliability prediction model in this
section, and discuss efficient methods to augment high-quality responses based
on the trained prediction model in the next section.

Figure 2: Our proposed prediction model. For each training sample
$(\bm{q},\\{\bm{r}\\})$, we construct negative samples
$(\bm{q},\\{\bm{r}\\}^{-})$ according to our assumption and compute the
contrastive loss. The model is trained with the combination of regression loss
and contrastive loss.

Our learning framework is shown in Figure 2, which contains two parts. We
first design a prediction model to predict a reliability score for each
$(\bm{q},\mathcal{R})$. Then, we construct negative samples and use
contrastive learning to train the proposed prediction model.

###  3.1 Model Structure

Input Representation For a query $\bm{q}$ and each response $\bm{r}$ in the
reference response set $\mathcal{R}$, we first concatenate them into one
sequence. Then we can obtain $N$ query-response pairs. We leverage BERT
(Devlin et al., 2019) that learns contextualized representations of the query-
response pairs:

$\\!\\!\\![\bm{v}_{c},\bm{v}_{q_{1}},\cdots,\bm{v}_{r_{1}},\cdots,\bm{v}_{r_{m}}]=\mathrm{BERT}([\bm{q},\bm{r}])$
(3)

where $\bm{v}_{c}$ is the representation for the special token [CLS] in the
BERT and we use its contextualized representation for each query-response
pair. Then, we get $N$ query-response representations.

Graph Encoder: In order to transform the dialogue context features into
higher-level features that consider the intrinsic variance between reference
responses in the reference set, we represent all query-response pairs in a
fully-connected graph and each query-response pair is a node in the graph.
Then we adopt a graph attention layer (Velickovic et al., 2018) to obtain a
better representation of each query-response pair:

$[\hat{\bm{v}}_{c_{1}},\ldots,\hat{\bm{v}}_{c_{n}}]=\mathrm{GAT}([\bm{v}_{c_{1}},\ldots,\bm{v}_{c_{n}}]).$
(4)

The final representation $\bm{v}_{g}$ of the graph is computed using the max-
pooling strategy.

Reliability Score Prediction: The reliability score is computed using a
single-layer feedforward network coupled with a tanh activation function:

$f(\bm{q},\mathcal{R})=\mathrm{tanh}(\mathbf{W}\cdot\bm{v}_{g}+\mathbf{b})$
(5)

where $\mathbf{W}$ and $\mathbf{b}$ are trainable parameters. The model is
trained to minimize the squared error between the model prediction and the
gold correlation coefficient $c$ with L2-regularization:

$\mathcal{L}_{r}=(f(\bm{q},\mathcal{R})-c)^{2}+\gamma\|\theta\|_{2}$ (6)

where $\gamma$ is a hyper-parameter and $\theta$ denotes the parameters of the
model.

###  3.2 Data Augmentation

To address the problem of limited data, we adopt the data augmentation method
to improve the generalization of our models. Our input sample consists of a
query $\bm{q}$ and a set of reference responses $\mathcal{R}$. We can expand
the training data by using different combinations of reference responses,
generating more different reference sets for each query. Since the number of
all combinations is huge, we randomly sample some various combinations for
each query. Given a set of reference responses
$\bm{\mathcal{R}}=\\{\bm{r}_{1},\cdots,\bm{r}_{n}\\}$ of $n$ elements ($n\leq
200$), the set of $k$-combinations are denoted as $\bm{\mathcal{C}}_{n}^{k}$,
where each combination has $k$ different elements. In our work, we use
$k\in\\{3,5,7,10\\}$ and randomly sample 25 different combinations from each
set $\bm{\mathcal{C}}_{n}^{k}$ ($k\in\\{3,5,7,10\\}$). We then expand the
validation set in the same way.

To evaluate the generalization performance of the model, the test set should
be used not only to verify the effectiveness of the model on samples with
$k\leq 10$, but also to test the performance of the model on samples with
$k>10$. Therefore, we use $k\in\\{3,5,10,20,30,40\\}$ to augment the test set.
For each set $\bm{\mathcal{C}}_{n}^{k}$ ($k\in\\{3,5,10,20,30,40\\}$), we only
randomly sample one combination. Finally, applying data augmentation as
described above gives us a total of 400,000/4,000/3,000 augmented
training/validation/test samples.

###  3.3 Contrastive Learning

Optimizing the simple regression objective above with the augmented training
samples may not yield a robust performance. To make the model capable to
capture the differences between different reference set for the same query, we
construct multiple negative samples for each training sample
$(\bm{q},\\{\bm{r}\\})$, and use contrastive learning to train the prediction
model. Given a training sample ($\bm{q},\\{\bm{r}\\}$) we design three kinds
of negative samples ($\bm{q},\\{\bm{r}\\}^{-}$):

  * •

Remove one response $r$ from the existing reference set $\\{\bm{r}\\}$. This
is based on the understanding in Section 2 that a set of gold responses
generally does not yield a higher correlation than a super set of it. We note
that all samples with deteriorated correlation here, are treated as negative
samples.

  * •

Randomly select a response of any other query to add to the existing set. This
is based on the understanding in Section 2 that a noise response included in a
gold reference set should deteriorate the correlation.

  * •

Randomly select a response of any other query to replace a response in the
existing set. The intuition is the same as the above one.

The contrastive loss function $\mathcal{L}_{c}$ with $T$ negative samples
constructed is computed as:

$\mathcal{L}_{c}=\frac{1}{T}\sum_{t}\mathrm{max}\\{0,\Delta-f(\bm{q},\\{\bm{r}\\})+f(\bm{q},\\{\bm{r}\\}_{t}^{-})\\},$
(7)

where $\Delta$ is a margin. The final loss can be computed as:

$\mathcal{L}=\mathcal{L}_{r}+\mathcal{L}_{c}.$ (8)

##  4 Augmenting High-quality References

In this section, we describe how we can augment high-quality references based
on the current gold reference set for a given query with the help of the
proposed reliability prediction model. Suppose a large set of reference
candidates can be easily obtained. For example, more conversation data can be
assessed to build a retrieval system to search for more references for the
given query. We introduce two ways to handle reference candidates with
different qualities. If the acquired reference candidates are considered
reliable, we can adopt automatic annotation. If we are not certain about the
relevance of the reference candidates, human annotators are needed for an
interactive annotation.

###  4.1 Automatic Annotation

We assume the response candidates are all relevant to the given query.
However, there may exist uninformative responses, such as the generic
responses or those similar to the gold references. We now introduce how to use
the predicted scores to automatically select out high-quality responses from
the candidate set. Each time a response is randomly picked to tentatively add
into the gold reference set, the model will predict a reliability score for
the augmented reference set. If the reliability score of the augmented
reference set improves, this picked response can be considered as a high-
quality one and now confirmed to add to the gold reference set. Otherwise, we
remove it from the gold reference set. We continue this process until all
response candidates have been picked once, and return the final augmented gold
reference set.

###  4.2 Interactive Annotation

If the response candidates are of uneven relevance to the query, we need to
hire annotators to manually check and edit the response candidates. We design
an interactive annotation strategy to allow the model to assist annotators.
For each selected response candidate, the annotator mainly executes the
following three steps:

  1. 1.

If he/she considers the response candidate is relevant to the given query and
the reliability score of the set improves with the current candidate response,
he/she can retain this response directly;

  2. 2.

If he/she considers the response candidate is not relevant enough to the given
query but the reliability score of the set shows improvement with the current
candidate response, he/she needs to edit this response and check whether the
reliability score of the set increases with the edited response;

  3. 3.

If the reliability score of the set does not improve with the current
candidate response, no matter whether the candidate response is relevant or
not, he/she still needs to edit this response and check whether the
reliability score of the set increases with the edited response;

In both Step2 and Step3, we allow the interactive annotation with a maximum
number of attempts. Otherwise, we abandon this response and continue to the
next response candidate. This process can help annotators avoid writing
responses with unsatisfactory quality.

##  5 Experiments

###  5.1 Setup

In our experiments, we use the quality scores obtained by BLEU* and BERTScore
to compute the Person correlations with human judgments respectively. The
reliability models introduced in Section 3 trained with BLEU and BERTScore are
referred as REAM$\sharp$(BLEU*) and REAM$\sharp$(BS) respectively. The
augmented dataset mentioned in Section 3.2 is used for the corresponding model
training and testing. To show its effectiveness on automatic annotation and
interactive annotation, we use the 500 test samples in the raw dataset
introduced in Section 2.1. See Appendix B for implementation and training
details.

###  5.2 Results on Reliability Prediction Models

# Refs | MSE | Pred. | Gold
---|---|---|---
REAM$\sharp$(BLEU*)
3 | 0.006 $\pm$0.005 | 0.333 | 0.340
5 | 0.006 $\pm$0.006 | 0.374 | 0.379
10 | 0.006 $\pm$0.005 | 0.399 | 0.402
20 | 0.006 $\pm$0.005 | 0.412 | 0.409
30 | 0.007 $\pm$0.006 | 0.413 | 0.417
40 | 0.006 $\pm$0.006 | 0.422 | 0.425
REAM$\sharp$(BS)
3 | 0.006 $\pm$0.006 | 0.356 | 0.355
5 | 0.006 $\pm$0.005 | 0.367 | 0.375
10 | 0.006 $\pm$0.006 | 0.393 | 0.404
20 | 0.006 $\pm$0.005 | 0.397 | 0.408
30 | 0.006 $\pm$0.005 | 0.406 | 0.417
40 | 0.007 $\pm$0.006 | 0.417 | 0.431
Table 2: Results of the REAM$\sharp$(BLEU*) model and the REAM$\sharp$(BS)
model on multiple test sets consisting of different number of reference
responses.

In Table 2, we report MSE, the averaged predicted reliability scores and
averaged gold reliability scores. Standard deviations are also provided. We
can see that the MSE of both prediction models are kept at a low level on
different test sets. The difference between the average predicted reliability
score and the average gold scores is at most 0.014. Also, the models have good
stability and rarely show extreme cases, as shown by their standard deviations
of less than 0.01. Our proposed models also have good generalization
performance in terms of different sizes of the reference set. The number of
references of training samples in the training set is at most 10, but the two
models still have a small test error on the test set with more than 10
references, which is comparable to the test set with less than 10 references.

Figure 3: Pearson correlations of BLEU* and BERTScore on multiple reference
sets obtained by different strategies. “REAM$\sharp$(BS)-BERTScore” means
using the REAM$\sharp$(BS) to augment the reference set and testing it with
BERTScore. “REAM(BLEU*)-BLEU*” means using the REAM$\sharp$(BLEU*) to augment
the reference set and testing it with BLEU*. We also add a random strategy for
comparison.

###  5.3 Results on Automatic Annotation

Once we have a reliable model, the next is to use the model to help us collect
high-quality references. When enough candidate responses are available, we can
directly use the model to identify which responses are helpful to improve the
reliability of the set. The experiment on automatic annotation is conducted
with the raw test set introduced in Section 2.1. For each sample in the test
set, we initialize the reference set with a randomly sampled crawled reference
response, then add the remaining reference responses (as mentioned before,
each sample has at most 200 reference responses) to its reference set one by
one. Each time a new response is added, the model predicts a reliability
score. The augmentation method follows the strategy mentioned in Sec. 4.1. We
selected 10 responses for each sample.

Figure 3 shows the Pearson correlations of BLEU* and BERTScore on multiple
reference sets obtained by different strategies. “REAM$\sharp$(BS)-BERTScore”
means using the REAM$\sharp$(BS) model to augment the reference set and
testing it with BERTScore. Similarly, “REAM(BLEU*)-BLEU*” means using the
REAM$\sharp$(BLEU*) model to augment the reference set and testing it with
BLEU*. We also use a random strategy for comparison (orange and red), where
the first 5 responses are the same as those previously selected using the
models, and the last 5 responses are obtained by randomly sampling. As shown
in the figure, the reliability of the reference sets constructed using our
proposed method tends to increase steadily as more selected responses are
added to the set, while the reliability of the reference sets constructed
using the random strategy appears to be unstable. We also test the
transferability of the model and find that the model trained with one metric
also yields reliable performance when tested with other metrics. The results
are shown in Appendix E.

The final results are shown in Table 3 which reports Pearson and Kendall
correlations of BLEU* and BERTScore calculated using three reference sets.
“Raw” denotes the initial reference set containing the first selected
reference response. The remaining 9 selected responses for each sample are
then used to augment the “Raw” set. “Aug-REAM$\sharp$(BS)” and “Aug-
REAM$\sharp$(BLEU*)” are the reference sets augmented using the
REAM$\sharp$(BS) and REAM$\sharp$(BLEU*), respectively. “Mix” is the union of
the two sets. As can be seen, the performances of the two metrics both improve
using the augmented reference set. When combining the two augmented reference
sets, both Pearson and Kendall correlations of BERTScore improve, while for
BLEU*, the Pearson and the Kendall correlations dropped slightly. This
indicates that BERTScore is better at capturing semantics than BLEU* and is
able to select the most adequate reference response from multiple augmented
sets for evaluation.

###  5.4 Results on Interactive Annotation

In the following, we perform experiments to augment high-quality references of
30 queries randomly selected in the test set in Section 2.1 using interactive
annotation introduced in Section 5.4. For each test query, we first use
ElasticSearch 222Elasticsearch is a search engine based on the Lucene library.
https://www.elastic.co to retrieve 100 candidate responses from a database
with 200 million (query, response) pairs with Jaccard similarity for each
query, and display them to each annotator. We recruit six annotators and
divide them into two groups. The reliability scores predicted by the
REAM$\sharp$(BERT) model will reveal to annotators in the first group (“Human-
REAM$\sharp$(BS)”) for interactive annotation but not annotators in the second
group (“Human”). Annotators in “Human” perform non-interactive annotations.
They are required to rewrite their considered unsuitable responses directly
without the predicted scores as a reference. For each round of annotation, we
pick one identical candidate response to all annotators.

| Pearson | Kendall
---|---|---
BLEU* |  |
Raw | 0.246 | 0.165
Aug-REAM$\sharp$(BLEU*) | 0.331 | 0.269
Aug-REAM$\sharp$(BS) | 0.315 | 0.261
Mix | 0.329 | 0.266
BERTScore |  |
Raw | 0.288 | 0.209
Aug-REAM$\sharp$(BLEU*) | 0.380 | 0.311
Aug-REAM$\sharp$(BS) | 0.389 | 0.318
Mix | 0.393 | 0.319
Table 3: Pearson and Kendall correlations of BLEU and BERTScore calculated
using different constructed reference sets. “Raw” denotes the reference set
consisting of 1 response.“Aug-REAM$\sharp$(BS)” and “Aug-REAM$\sharp$(BLEU*)”
are the reference sets (10 reference responses) augmented using the
REAM$\sharp$(BS) and REAM$\sharp$(BLEU*), respectively. “Mix” is the union of
the two sets.

Figure 4 shows the Pearson correlations of human evaluation results and
BERTScore with the augmented reference sets after each round of annotation by
one annotator in “Human-REAM$\sharp$(BS)” and another annotator in “Human”.
See Appendix D for the results of all six annotators. We can see that using
the augmented response set from annotators in the first group has already
reached a relatively high Pearson correlation with only a few annotation
rounds. When the number of responses increases to a certain level, the
reliability score of the metric hits a bottleneck and rises more slowly.
However, the correlation results using the augmented response set from
annotators in the second group are not stable. Though the overall trend is
increasing, the final obtained reference set has even worse correlations than
a much small augmented set from the first group. This shows that our
interactive annotation strategy is effective to help annotators avoid writing
responses with unsatisfactory quality.

Figure 4: Pearson correlations of the reference sets constructed with/without
the REAM$\sharp$(BS) model in interactive annotations, respectively. “Human-
REAM$\sharp$(BS)” denotes the annotator with the model assistance and “Human”
is the annotator without the model assistance.

##  6 Related Work

Automatic evaluation is crucial to the research of open-domain dialog systems
(Li and Jurafsky, 2016; Li et al., 2017; Gao et al., 2019; Venkatesh et al.,
2018; Chan et al., 2021; Xiang et al., 2021). Existing metrics can be broadly
categorized into reference-based and reference-free metrics (Chen et al.,
2021). In this work, we focus on reference-based metrics, which usually
measure how similar a generated response is to the reference response.

The most commonly used reference-based metrics for dialog systems were
originally proposed for machine translation. They typically count the amount
of word-overlap between the generated response and the reference response.
BLEU (Papineni et al., 2002) is the most widely used metric in machine
translation that calculates the geometric mean of the precision for $n$-gram.
Other related word-overlap metrics such as NIST (Lin and Och, 2004), METEOR
(Banerjee and Lavie, 2005) and ROUGE (Lin, 2004) also have been used for
dialogue evaluation.

Instead of using word-overlap based metrics, embedding-based metrics are
adopted to consider the semantic meaning of a word as defined by a distributed
representation. They typically compute the similarity between the generated
response and reference response using approximated sentence-level
representations. The most commonly used word embedding based metrics use a
heuristic to combine the vector representation of the individual word in the
sentence. For example, Embedding Average (Foltz et al., 1998; Mitchell and
Lapata, 2008), Vector Extrema (Forgues and Pineau, 2014), and Greedy Matching
(Rus and Lintean, 2012). Zhang et al. (2020) introduce a better embedding-
based metric BERTScore that computes token similarity using contextual
embeddings that capture the specific use of a word in a sentence.

A few reference-based metrics for dialog systems are learnable functions. ADEM
(Lowe et al., 2017) which is based on neural networks is trained to predict a
score of a response given its query and a reference response. RUBER (Tao et
al., 2018) evaluates responses with a blending of scores from the referenced
and unreferenced metrics. RUBER is learnable, but its training does not
require human annotation scores.

As discussed from the very beginning of our work, all the above work focus on
designing a better metric. However, the reliability of the reference set is
also a key to improve the correlation of reference-based metrics, but not
investigated in detail in previous work. Therefore, we believe our work can
fill this vacancy and provide a new direction to improve reference-based
metrics for open-domain dialogue generation.

##  7 Conclusions and Future Work

In this paper, we first clarify an assumption on existing reference-based
metrics that if more high-quality reference responses are added to the
reference set, it should have a higher correlation with human judgment. For
metrics satisfying this assumption, we present REAM$\sharp$, an enhancement
approach to improve their reliability. In our approach, a reliability
prediction model is trained to estimate the reliability of the reference set
and we explore both automatic and interactive ways to augment high-quality
references with the help of the reliability prediction model. Experiments show
that our approach can efficiently help augment high-quality references and the
correlations of reference-based metrics improve when using the augmented
reference sets to evaluate dialog responses. Our work currently focuses on
open-domain dialog systems as a starting point. However, the REAM$\sharp$
framework can be extended naturally to other open-ended text generation tasks
such as story generation and question generation.

##  8 Ethical Considerations

The dataset used in our work are crawled from several Chinese social media
websites, BaiduTieba, Douban, Weibo and Zhihu. We purposefully avoid
deanonymization techniques based on exploiting software vulnerabilities and
our approach that involves human participation in rewriting responses gives us
no access to any personally identifiable information.

## References

  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_.
  * Chan et al. (2021) Zhangming Chan, Lemao Liu, Juntao Li, Haisong Zhang, Dongyan Zhao, Shuming Shi, and Rui Yan. 2021.  Enhancing the open-domain dialogue evaluation in latent space.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics: Findings_.
  * Chen et al. (2021) Wang Chen, Piji Li, and Irwin King. 2021.  A training-free and reference-free summarization evaluation metric via centrality-weighted relevance and self-referenced redundancy.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_.
  * Foltz et al. (1998) P. Foltz, W. Kintsch, and T. Landauer. 1998.  The measurement of textual coherence with latent semantic analysis.  _Discourse Processes_.
  * Forgues and Pineau (2014) Gabriel Forgues and Joelle Pineau. 2014.  Bootstrapping dialog systems with word embeddings.  In _NIPS, modern machine learning and natural language processing workshop_.
  * Freitag et al. (2020) Markus Freitag, David Grangier, and Isaac Caswell. 2020.  BLEU might be guilty but references are not innocent.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing_.
  * Gao et al. (2019) Jun Gao, Wei Bi, Xiaojiang Liu, Junhui Li, and Shuming Shi. 2019.  Generating multiple diverse responses for short-text conversation.  In _The Thirty-Third AAAI Conference on Artificial Intelligence_.
  * Gehring et al. (2017) Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. 2017\.  Convolutional sequence to sequence learning.  In _Proceedings of the 34th International Conference on Machine Learning_.
  * Li and Jurafsky (2016) J. Li and Dan Jurafsky. 2016.  Mutual information and diverse decoding improve neural machine translation.  _ArXiv_.
  * Li et al. (2016a) J. Li, Will Monroe, and Dan Jurafsky. 2016a.  A simple, fast diverse decoding algorithm for neural generation.  _ArXiv_.
  * Li et al. (2016b) Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2016b.  A diversity-promoting objective function for neural conversation models.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_.
  * Li et al. (2017) Jiwei Li, Will Monroe, Tianlin Shi, Sébastien Jean, Alan Ritter, and Dan Jurafsky. 2017.  Adversarial learning for neural dialogue generation.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_.
  * Li et al. (2020a) Xin Li, Piji Li, Wei Bi, Xiaojiang Liu, and Wai Lam. 2020a.  Relevance-promoting language model for short-text conversation.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence_.
  * Li et al. (2020b) Yangming Li, Kaisheng Yao, Libo Qin, Wanxiang Che, Xiaolong Li, and Ting Liu. 2020b.  Slot-consistent NLG for task-oriented dialogue systems with iterative rectification network.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_.
  * Lin and Och (2004) Chin-Yew Lin and Franz Josef Och. 2004.  Automatic evaluation of machine translation quality using longest common subsequence and skip-bigram statistics.  In _Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics_.
  * Liu et al. (2016) Chia-Wei Liu, Ryan Lowe, Iulian Serban, Mike Noseworthy, Laurent Charlin, and Joelle Pineau. 2016.  How NOT to evaluate your dialogue system: An empirical study of unsupervised evaluation metrics for dialogue response generation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_.
  * Liu et al. (2018) Yahui Liu, Wei Bi, Jun Gao, Xiaojiang Liu, Jian Yao, and Shuming Shi. 2018.  Towards less generic responses in neural conversation models: A statistical re-weighting method.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_.
  * Lowe et al. (2017) Ryan Lowe, Michael Noseworthy, Iulian Vlad Serban, Nicolas Angelard-Gontier, Yoshua Bengio, and Joelle Pineau. 2017.  Towards an automatic Turing test: Learning to evaluate dialogue responses.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics_.
  * Mitchell and Lapata (2008) Jeff Mitchell and Mirella Lapata. 2008.  Vector-based models of semantic composition.  In _Proceedings of ACL-08: HLT_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_.
  * Radford et al. (2019) A. Radford, Jeffrey Wu, R. Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019\.  Language models are unsupervised multitask learners.  In _OpenAI blog_.
  * Rus and Lintean (2012) Vasile Rus and Mihai Lintean. 2012.  A comparison of greedy and optimal assessment of natural language student input using word-to-word similarity metrics.  In _Proceedings of the Seventh Workshop on Building Educational Applications Using NLP_.
  * Tao et al. (2018) Chongyang Tao, Lili Mou, Dongyan Zhao, and Rui Yan. 2018.  RUBER: an unsupervised method for automatic evaluation of open-domain dialog systems.  In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence_.
  * Velickovic et al. (2018) Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph attention networks.  In _6th International Conference on Learning Representations_.
  * Venkatesh et al. (2018) Anu Venkatesh, C. Khatri, A. Ram, Fenfei Guo, R. Gabriel, Ashish Nagar, Rohit Prasad, M. Cheng, Behnam Hedayatnia, A. Metallinou, Rahul Goel, Shaohua Yang, and A. Raju. 2018.  On evaluating and comparing open domain dialog systems.  _arXiv: Computation and Language_.
  * Xiang et al. (2021) Jiannan Xiang, Yahui Liu, Deng Cai, Huayang Li, Defu Lian, and Lemao Liu. 2021.  Assessing dialogue systems with distribution distances.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics: Findings_.
  * Zhang et al. (2020) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020\.  Bertscore: Evaluating text generation with BERT.  In _8th International Conference on Learning Representations_.

##  Appendix A Dataset

The dataset used in our work are crawled from several Chinese social media
websites, BaiduTieba, Douban, Weibo and Zhihu. We purposefully avoid
deanonymization techniques based on exploiting software vulnerabilities and
our approach that involves human participation in rewriting responses gives us
no access to any personally identifiable information. We crawled 5,000 queries
and each query has at most 200 ref-erence responses. Then, we collected 14
machine-generated responses obtained from several widely used responses
generation models:

  * •

LSTM-S2S-BS: a LSTM Seq2Seq model that generates responses with beam search.

  * •

LSTM-S2S-Sampling: a LSTM Seq2Seq model that generates responses with top k
sampling.

  * •

LSTM-S2S-MMI: a LSTM Seq2Seq model with a Maximum Mutual Information-based
decoding strategy.

  * •

Fconv-S2S-BS: a convolutional Seq2Seq model (Gehring et al., 2017) that
generates responses with beam search.

  * •

Fconv-S2S-Sampling: a convolutional Seq2Seq model (Gehring et al., 2017) that
generates responses with top k sampling.

  * •

Fconv-S2S-DBS: a convolutional Seq2Seq model (Gehring et al., 2017) that
generates responses with diverse beam search (Li et al., 2016a).

  * •

Transformer-S2S-BS: a Transformer Seq2Seq model that generates responses with
beam search.

  * •

Transformer-S2S-Sampling: a Transformer Seq2Seq model that generates responses
with top k sampling.

  * •

Transformer-S2S-DBS: a Transformer Seq2Seq model that generates responses with
diverse beam search (Li et al., 2016a).

  * •

GPT2-BS: a GPT2 (Radford et al., 2019) model that generates responses with
beam search.

  * •

GPT2-TopK Sampling (k=20): a GPT2 (Radford et al., 2019) model that generates
responses with top 20 sampling.

  * •

GPT2-TopK Sampling (k=10): a GPT2 (Radford et al., 2019) model that generates
responses with top 10 sampling.

The GPT2 model are trained on a 200 million chinese dataset crawled also from
the Chinese social media websites (BaiduTieba, Douban, Weibo and Zhihu). The
LSTM-S2S, Fconv-S2S and Transformer-S2S models are trained on a benchmark
dataset with 7M query-response pairs proposed by Liu et al. (2018).

##  Appendix B Implementation and Training Details

We leverage “bert-as-service” (https://github.com/hanxiao/bert-as-service), an
open-source system that uses BERT as a sentence encoder and hosts it as a
service to map sentences into fixed-length representations. In our work, we
use the character-level BERT pre-trained in Chinese. Our reliability
prediction model is implemented using “PyTorch Geometric” which is a geometric
deep learning extension library for PyTorch. We use one layer. For graph
encoding, we employ a one-layer graph attention network with an input size of
768. The input size of the prediction linear layer also is 768. The model is
trained using Adam optimizer with a learning rate of 0.0005. The batch size is
128.

For computing BLEU, we use the Python NLTK library. For computing BERTScore,
we use the implementation provided by Zhang et al. (2020) at
https://github.com/Tiiiger/bert_score.

##  Appendix C Case Study

Figure 6 shows two examples of using our REAM$\sharp$(BS) model to predict
reliability scores for reference sets. Given a query and a reference set
consisting of four reference responses, we first predict a reliability score
for this set (e.g 0.312 and 0.275). We prepared four different candidate
responses for each sample. The sentences with blue text are high-quality and
diverse responses. Sentences without color are responses that are similar in
meaning to the responses already in the set. Red sentences are responses that
are completely irrelevant to the queries. We add each of the four candidate
responses to the set and predict the reliability score for the new set. As
shown in the figure, when the high-quality responses are added to the set, the
model predicts a higher reliability score than the original reliability score.
When responses with repeated semantics are added to the set, the model
predicts a slightly lower reliability score compared to the original one. When
poor quality responses are added to the set, the reliability scores predicted
by the model drop sharply. It can be seen that our model can effectively
evaluate the impact of responses with different qualities on the reference
set.

##  Appendix D More Results on Interactive Annotation

Figure 5 shows the results of all six annotators. We can see that using the
augmented response set from annotators in the first group has already reached
a relatively high Pearson correlation with only a few annotation rounds. When
the number of responses increases to a certain level, the reliability score of
the metric hits a bottleneck and rises more slowly. However, the correlation
results using the augmented response set from annotators in the second group
are not stable. Though the overall trend is increasing, the final obtained
reference set has even worse correlations than a much small augmented set from
the first group. This shows that our interactive annotation strategy is
effective to help annotators avoid writing responses with unsatisfactory
quality.

Figure 5: Pearson correlations of the reference sets constructed with and
without the REAM$\sharp$(BS) model, respectively. “Human-REAM$\sharp$(BS)”
denotes the annotator with the model assistance and “Human” is the annotator
without the model assistance. Figure 6: Two examples of using our
REAM$\sharp$(BS) model to predict reliability scores for reference sets. The
sentences with blue text are high-quality and diverse responses. Sentences
without colour are responses that are similar in meaning to the responses
already in the set. Red sentences are responses that are completely irrelevant
for the queries.

##  Appendix E Transferbility

Figure 7: Pearson correlations of the two models, REAM$\sharp$(BS) and
REAM$\sharp$(BLEU*) tested using BLEU* and BERTScore, respectively.

We would like to see if the model trained with one metric also yields reliable
performance when tested with other metrics. Figure 7 shows the Pearson
correlations of the two models, REAM$\sharp$(BS) and REAM$\sharp$(BLEU*)
tested using BLEU* and BERTScore, respectively. From the figure, we can see
that whether tested with BLEU* or BERTScore, the difference in performance
between REAM$\sharp$(BS) and REAM$\sharp$(BLEU*) is very small. We also notice
that the difference in performance tested with BLEU* between the two models is
somewhat larger than that tested with BERTScore when the number of references
is large. This may be because BLEU* does not utilize the semantic information
compared to BERTScore, which leads to some high-quality responses in the
reference set being ignored. Therefore, our enhancement approach is more
effective as the metric’s ability to capture semantic similarity increases.