Article Title]Evaluation of Question Answering Systems: Complexity of judging a natural language

1]Amer Farea
1]Zhen Yang
1]Kien Duong
1]Nadeesha Perera
[1]Frank<EMAIL_ADDRESS>
[1]Predictive Society and Data Analytics Lab, Faculty of Information Technology and Communication Sciences, Tampere University, Finland

Question answering (QA) systems are among the most important and rapidly developing research topics in natural language processing (NLP). A reason, therefore, is that a QA system allows humans to interact more naturally with a machine, e.g., via a virtual assistant or search engine. In the last decades, many QA systems have been proposed to address the requirements of different question-answering tasks. Furthermore, many error scores have been introduced, e.g., based on n-gram matching, word embeddings, or contextual embeddings to measure the performance of a QA system. This survey attempts to provide a systematic overview of the general framework of QA, QA paradigms, benchmark datasets, and assessment techniques for a quantitative evaluation of QA systems. The latter is particularly important because not only is the construction of a QA system complex but also its evaluation. We hypothesize that a reason, therefore, is that the quantitative formalization of human judgment is an open problem.

§ INTRODUCTION

Natural language processing (NLP) is an important branch of artificial intelligence (AI) concerned with text understanding and text generation. The former subject is studied in the sub-branch natural language understanding (NLU) [Bates, 1995, Liu et al., 2021, Radford et al., 2018] and the latter in natural language generation (NLG) [Reiter and Dale, 1997, Gatt and Krahmer, 2018]. Over the years, both fields, i.e., NLU and NLG developed enormously with an extensive literature which requires nowadays a dedicated discussion of specialized subtasks when presenting approaches or methods thereof despite the fact that a systems understanding of NLP can only be achieved holistically.

In this paper, we focus on subtasks of NLP centered around question answering (QA). The task of a  QA system is to find an answer (output) in the form of a natural language for a given question (input) usually presented in form of a sentence. While our focus is on QA systems and their quantitative evaluations, we discuss also evaluation scores introduced in related fields. The reason for this is that machine translation (MT), text summarization (TS) and dialogue systems (DS) (also called conversational agents) also have the problem of evaluating various forms of input-output text pairs. Hence, despite the fact that there are considerable differences between question answering, machine translation, text summarization, and dialogue systems several evaluation scores are typically used across those tasks.

For QA many methods and techniques have been introduced varying from simple rule-based systems to advanced and complex machine learning techniques [Cho et al., 2014, Sutskever et al., 2014, Bahdanau et al., 2014, Vaswani et al., 2017]. In recent years, deep neural network-based approaches to realizing different forms of data-driven representation learning have gained widespread interest due to their competitiveness and flexibility. Question Answering (QA) is widely considered one of the most important tasks of NLP, as it enables humans to interact with machines in a more natural way by either extracting information related to questions from different knowledge sources or by generating the answer without the need for using structural query languages. In other words, QA tries to retrieve or generate answers in the form of a natural language based on a given input, instead of, providing a ranked list of documents as provided by search engines or classic information retrieval systems which require additional steps for checking each document to find useful content [Peñas et al., 2012].

Since the 1960s many question-answering systems have been proposed [Androutsopoulos et al., 1995, Kolomiyets and Moens, 2011]. Among the first QA systems were BASEBALL [Green Jr et al., 1961] and LUNAR [Woods, 1973] which provided information associated with the US baseball league and soil samples from the Apollo lunar exploration. While both approaches provided good results in their corresponding closed-domain applications, a generalization to other domains was impaired. In order to enhance research in open-domain applications, in 1999, the Text REtrieval Conference (TREC) initiated a research area about question answering (TREC-8) in the form of competitions [Voorhees et al., 1999]. Since then there is an ongoing series of campaigns addressing increasingly complex QA problems. As a result, QA systems have evolved to become more relevant to diverse tasks, e.g., generative QA [Yih et al., 2015, Indurthi et al., 2017, Pan et al., 2019, Zhang et al., 2021], extractive QA [Sukhbaatar et al., 2015, Yue et al., 2017, Kumar et al., 2016, Ojokoh and Adebisi, 2018], knowledge-based QA [Luo et al., 2018, Zhu et al., 2020, Qu et al., 2018, Lan and Jiang, 2020, Dimitrakis et al., 2020], question classification [Cortes et al., 2020, Zhang et al., 2019], community QA and question answering matching [Ben Abacha and Demner-Fushman, 2019, Hu et al., 2017, Lan et al., 2019, He et al., 2019, Zhang et al., 2019].

The literature about question answering has widely investigated different QA tasks, and many studies have been conducted in this regard according to various criteria such as question types, answer types, knowledge sources, and training strategy techniques [Ojokoh and Adebisi, 2018, Dimitrakis et al., 2020, Abbasiantaeb and Momtazi, 2021, Lan et al., 2021, Zhang et al., 2021, Hao et al., 2022, Lee et al., 2019, Yang et al., 2017, Fabbri et al., 2020, Bashath et al., 2022]. Interestingly, recent studies still focus on how to process a complex question and extract the answer from multiple sources. In contrast, this paper tries to present a broader look at the current state of the literature that is essential for a better understanding of question-answering systems. Specifically, we start by briefly describing the general question-answering framework which allows us to introduce a formal definition of a QA system. For the practical construction of QA systems, we discussed the three main paradigms: (1) Information Retrieval-Based Question Answering (IRQA), (2) Knowledge Base Question Answering (KBQA), and (3) Generative Question Answering (GQA). In order to evaluate a QA system, task-specific benchmark data are needed together with evaluation scores. Due to the fact that there is a large number of such evaluation scores with quite different properties, we introduce a hierarchical taxonomy for such error scores. Furthermore, we discuss important representatives of the main categories of the taxonomy.

This paper is organized as follows: Section <ref> briefly indicates the main contributions of this paper. Section <ref> introduces a general framework for QA system. Section <ref> discusses three different types of the question answering paradigms. Benchmark datasets and evaluation scores are presented in Section <ref>, and different types of quantitative scores are discussed in Section <ref>. In Section <ref>, we discuss challenges for evaluation scores and in Section <ref> we provide a general discussion. This paper finishes in Section <ref> with a conclusion.

§ MAIN CONTRIBUTIONS OF THIS SURVEY FOR QA

There are previous review articles about question answering, e.g., [Ojokoh and Adebisi, 2018, Abbasiantaeb and Momtazi, 2021, Zhang et al., 2021, Kolomiyets and Moens, 2011, Dimitrakis et al., 2020, Lan et al., 2021, Alwaneen et al., 2021, Mishra and Jain, 2016, Diefenbach et al., 2018, Ni et al., 2021, Wu et al., 2017, Srivastava et al., 2020], however, each of these studies has investigated a particular type of question answering paradigms and sheds light on some specific requirements of QA tasks (i.e, generative QA, extractive QA, knowledge-based QA, question classification, community QA, or question answering matching) along with some criteria for a specific QA task, such as question types, answer types, knowledge sources, and training strategy techniques. Many studies have also tried to shed light on assessment techniques of NLP in general, and on those used in question-answering systems, e.g., [Deriu et al., 2021, Emmert-Streib et al., 2019, Gatt and Krahmer, 2018, Sai et al., 2022, Celikyilmaz et al., 2020, Emmert-Streib et al., 2019].

In contrast to those surveys, our survey is not trying to focus on a specific QA paradigm or on a particular QA system, instead, we attempt to provide a comprehensive overview of the general framework of QA, QA paradigms, benchmark datasets, and assessment techniques for a quantitative evaluation of QA systems. Specifically, our contribution comprises the following topics.

* Surveying the question answering framework

* Definition of a question-answering system

* Question answering paradigms

* Benchmark data

* Taxonomy of evaluation scores

* Discussion of quantitative evaluation scores

1. Surveying the question answering framework: Question answering has been developed for decades, and there are various designs and approaches for a question answering system. The first goal of the paper is to review all approaches to give a concrete view of the question-answering framework, discussed in Section <ref>. We propose a general framework for question answering, which consists of four main components: Question Answering Algorithms, Knowledge Sources, Question Types, and Answer Types. For each component, we explain the different approaches as well as the advantages and drawbacks of those approaches.

2. Definition of a question answering system: Based on the QA framework, we introduce in Section <ref> a formal definition of a question answering system which allows summarizing its formal structure abstractly.

3. Question answering paradigms: In order to provide a clear overview of QA systems, we introduce in Section <ref> the three main paradigms of QA systems, i.e., (1) Information Retrieval-Based Question Answering, (2) Knowledge Base Question Answering, and (3) Generative Question Answering and discuss differences among them.

4. Benchmark data: Since QA systems can be defined for many different and complex tasks with many variations, task-specific datasets are needed for the evaluation of such QA systems. For this reason, we discuss different benchmarking datasets for different QA paradigms. These benchmarking datasets of QA systems are presented in Section <ref>.

5. Taxonomy of evaluation scores: Many different types of evaluation scores have been proposed in the literature, including Untrained Automatic Evaluation Scores (UAES) and Machine-Trained Evaluation Score (MTES), making it hard to distinguish the advantages or drawbacks of those approaches. In Section <ref>, we introduce a hierarchical taxonomy of evaluation score classes used for different QA systems.

6. Discussion of quantitative evaluation scores: For the evaluation score classes of the taxonomy many individual error scores have been introduced. In Section <ref>, we discuss the main representatives for the three major classes of error measures. Specifically, for Simple Untrained Automatic Evaluation Scores (S-UAES) in Section <ref> we discuss exact match (EM), precision, recall, F1-score, error rate (ER), average precision (AP), mean average precision (MAP) and mean reciprocal rank (MRR), for Advanced Untrained Automatic Evaluation Scores (A-UAES) in Section <ref> we discuss  BLEU, NIST, ROUGE and METEOR and for Machine-trained Evaluation Scores (MTES) in Section <ref> we discuss ADEM, RUBER, RUSE, BLEUERT, BertScore, MaUde, and learning-based composite metrics.

§ THE QUESTION ANSWERING FRAMEWORK

QA systems have been intensively adopted in many areas like chatbots, search engines, standalone databases, or virtual assistants most notably Alexa, Siri, Cortana, or Google assistance. In general, a QA system accepts questions in the form of text or speech; and tries to parse them into dependency formats [Zhang et al., 2019] to find relationships between their content by looking for matching words or embedded semantics that are located in a context or relevant content [Wang et al., 2007]. Despite the fact that there are many modern QA systems, which will be discussed below, their underlying framework is similar and is outlined in the following.

The design of QA approaches may vary from system to system according to the requirements of specific QA tasks. However, a general framework for a QA system, as illustrated in Figure <ref>, can be structured into the following components: (1) Question Answering Algorithms, (2) Knowledge Sources, (3) Question Types and (4)  Answer Types. These components are described in the following sections.

A general framework for a Question Answering system that consists of four main components.  (1) Question Answering Algorithms, (2) Knowledge Sources, (3) Question Types, and (4) and  Answer Types.

§.§ Question Answering Algorithms

QA algorithms are at the heart of question answering systems, where they play a vital role in manipulating the given context (i.e., passage, document) and classifying the question/query types of the QA system, and identifying the predicted answer types accordingly. Such algorithms can be classified into rule-based (heuristic), retrieval-based, and sequence-to-sequence techniques.

Rule-based techniques can be further subdivided into template-based [Sammut and Banerji, 1986, Liu et al., 2017, Fabbri et al., 2020], syntax-based [Straach and Truemper, 1999, Harabagiu et al., 2005, Heilman and Smith, 2010] and semantic-based rules [Levy and Andrew, 2006, Dhole and Manning, 2020, Yao and Zhang, 2010]. To identify the answer or question type, traditional methods of QA need to perform some of these rule-based approaches in order to detect the semantics or syntactical parsing of a given input and then produce the required output by converting the in-between representation into a natural language content. Unfortunately, rule-based techniques are somewhat cumbersome because they usually require large efforts to build handcrafted features, which is considered to be expensive, time-consuming, tedious, and requires an extensive experience in the related domain. In addition, the heuristic technique pipeline may compose many different components, which may affect the quality of the generalization of the selected model.

Unlike rule-based approaches, retrieval-based techniques are using hybrid rules and feature-based classifiers, which can employ plenty of training data and provide an elegant, comprehensive, and trustworthy method to exploit the informative entities of a given input and optimize the content selection along with formulated task (i.e., answer extraction, or question generation) at the same time. A retrieval-based QA system contains two components: intent classifier, and response selector. The intent classifier consists of multiple natural language understanding (NLU) techniques to classify the type of input, understand the intent of the input, and extract the informative entities in the input. Then, the information extracted from the intent classifier is fed to the response selector to query the most appropriate answer from the KB. The techniques for the response selector can be statistical approaches [Ko et al., 2007] or neural-network approaches [Zhou et al., 2016, Wu et al., 2016]. Importantly, retrieval-based techniques do not require handcrafted features; but require instead, large amounts of data to be trained. Also, the obtained results cannot be easily interpreted.

For improving the quality of question answering systems and to free researchers from tedious feature engineering, many neural-based techniques have proposed complex pipelines with deep neural network architectures to formulate the numerous tasks of QA as a sequence-to-sequence problem. This design boosts the flexibility of a model to handle diverse tasks ranging from synthetic question answering to language modeling [Jing et al., 2019, Sukhbaatar et al., 2015, Kumar et al., 2016]. Examples for such architectures include encoders and decoders models [Cho et al., 2014, Cho et al., 2019], attention [Bahdanau et al., 2014, Huang et al., 2018, Kim et al., 2018, Zhang et al., 2016, Chen et al., 2017, Zhang et al., 2019, Seo et al., 2016], transformer-based and pre-trained models [Cho et al., 2014, Devlin et al., 2018, Dong et al., 2019, Lopez et al., 2021, Indurthi et al., 2017, Lin et al., 2017, Zhang et al., 2019, Qu et al., 2018, Liu et al., 2019, Lan et al., 2019, Sanh et al., 2019, Roberts et al., 2020]. The goal behind each model is to encode the relationship between the question and given context,  handle the long-range dependencies in the answer processing modules, and capture the concepts and hidden patterns of hierarchical features in a comprehensive way, to produce an accurate response.

Despite most of the above-mentioned techniques being found to be more robust 'in somehow' compared to the traditional techniques, such complex techniques require huge datasets along with vast computational resources to be trained. Moreover, a lot of effort is required to fine-tune the model structure to a particular dataset, since there is no single model that can fit efficiently to all QA tasks (each dataset may require different hyperparameters tuning), and the model that performs well for some specific-task dataset may fail to get outstanding result on different tasks or datasets [Joshi et al., 2017].

§.§ Knowledge Source

A knowledge source in general is either a closed or an open repository that stores data related to a QA system in a structured, unstructured or semi-structured format. Hence, it is the most general source of information that includes a knowledge base. Despite knowledge bases are often in the form of text, due to the growth of signal processing, text KBs are also complemented by audio data [Chuang et al., 2019, Fayek and Johnson, 2020] and visual data [Wu et al., 2017, Srivastava et al., 2020].

§.§.§ Closed-domain knowledge source

A closed-domain could be a single document-based or a compatible and interpretable knowledge-base (KB) based on an entity-linking technique that relies on assigning a unique identity to each entity mentioned in the corpus [Ji and Grishman, 2011]. In other words, a closed-domain can refer to a single specific knowledge domain, in which the correct answer for an associated question is supposed to be part of a specific document. Closed-domain makes it easy to evaluate a predicted answer against the golden answers; and find the most accurate evaluation for the identical answer at a specific position, especially when the start and end indices of entities are included as labels in the given dataset. For example, in the sentence "[START] Frank [END] was born in [START] 1980 [END].", the golden answers for two questions  "Who was born in 1980?" and "When was Frank born?" are labeled with [START] and [END] indices.

Many KB datasets [Berant and Liang, 2014, Berant et al., 2013, Yih et al., 2016, Dubey et al., 2019, Zhang et al., 2018, Zhang et al., 2016, Bisk et al., 2016, Talmor and Berant, 2018, Zhou et al., 2018, Bollacker et al., 2008, Lehmann et al., 2015, Pellissier Tanon et al., 2016, Wilcke et al., 2017, Vakulenko et al., 2019, Wang et al., 2019, Bordes et al., 2015] have been proposed to tackle the requirements of different applications by providing specific knowledge such as medical, temporal, educational, geospatial to name just a few. The content of a KB is frequently collected from Wikipedia or web pages [Mihalcea and Csomai, 2007] either as a graph-based base with entities and edges (subject, relation, object) or as a logic-based base, such as  compositional semantic parsing with labeled entities of precise meaning.

Graph-based: The graph-based model uses edges to represent relationships that link the data items in a dataset to a collection of nodes (e.g., subjects or objects) as illustrated in Figure <ref>. Such relations in graph-based models can be used to predict the answer (object) for a question (subject), e.g., "Who was born in 1980?" or "When was Frank born?" by computing the similarity between the encoded question and each possible relation.

An illustration of a simple knowledge-base with graph-based representation, which uses edges to represent the relationships that exist within a dataset as a collection of nodes (e.g., subjects or objects), in order to predict the answer (object).

The transformers such as BERT [Devlin et al., 2018] or GPT [Radford et al., 2018, Radford et al., 2019] have also been used for a variety of NLP tasks including question answering. For example, BERT has been used to detect the entity and the relation over the question and context, to predict the answer, by using separated trained vectors that represent each possible entity-relation. It starts with tokenizing the given sentences into a vocabulary, normalizes the output of this process, and adds padding when needed. Then it uses the [CLS] and [SEP] tokens to encode a sequence of question and context, and produces the embedding vectors with position and sequence-type information [Lukovnikov et al., 2019]. In the entity span detection step, the embedding vectors are fed into the transformer to detect and predict the start and the end positions of each entity span in the context based on the obtained probability of the start position of the entity span as follows:

\begin{equation}
P(t=START\vert{x_{0}...x_{T}}) =\frac{e^{h_{i}.w_{START}}}{\sum_{j=0}^{T}e^{h_{j}.w_{START}}}
\end{equation}

where \(x_{0}...x_{T}\) is the input sequence, \(h_{i}\) is a contextualized   vector feature for timestamp \(i\), and \(w_{START}\) is a parameter vector for the start position classifier. Similarly, the prediction of end positions can be computed using a \(w_{END}\) parameter vector. Then the setting of the transformer model is adjusted to predict the relation \(r\) over the question. The probability of the relation \(R_{i}\) is given by the following formula:

\begin{equation}
P(r=R_{i}\vert{x_{0}...x_{T}}) =\frac{e^{h_{CLS}.w_{R_{i}}}}{\sum_{k=0}^{N_{R}}e^{h_{CLS}.w_{R_{k}}}}
\end{equation}

where \(h_{CLS} = h_{1}\) is the contextualized vector feature for the beginning token of the question, \(w_{R_{i}}\) is the parameter vector for relation \(R_{i}\), and \(N_{R}\) is the total number of relation pairs. The entity-relation pairs are created from outputs of the entity span detection and relation detection, re-ranked, and then exploited to query an answer from a knowledge graph.

Logic-based: On another hand, knowledge-base datasets may contain different structure, e.g., it may contain question-answer-pairs in a logical format, which require  semantic parsing algorithms, to perform the necessary parsing for such data in a supervised manner, or it may contain question paired with a semantic-answer, in which the logical form needs to be modeled as a latent variable [Zelle and Mooney, 1996, Iyer et al., 2017]. For example, the question "What countries border Finland?" could be formulated as follows:

\begin{eqnarray}
(\lambda{x}.(countries(x) \land borders(x, Finland))
\end{eqnarray}

Besides, the BERT model has been also used with a KB based of semantic parsing to transform the training tuples of question-answer-pairs into a logical form. This is accomplished by encoding the input sequence; and mapping it to a contextualized vector, followed by a decoding phase to produce a logical representation. An example of this is shown in Figure <ref>.

An illustration of a semantic parsing algorithm used by the BERT model over a knowledge-base dataset to formulate a question in a logical representation.

§.§.§ Open-domain knowledge source

In contrast to closed-domain, an open-domain knowledge source [Rajpurkar et al., 2016, Zhang et al., 2018, Ben Abacha and Demner-Fushman, 2019, Huang et al., 2018, Kim et al., 2018, Lee et al., 2019, Nguyen et al., 2016, Yang et al., 2015, Rajpurkar et al., 2018, Yang et al., 2018, Joshi et al., 2017, Kwiatkowski et al., 2019, Clark et al., 2020, He et al., 2019] is a repository with a huge content that could be collected from various sources (i.e., text passage, books, web documents, knowledge bases, tables, images), in any possible format, i.e., in the form of tuples (Question, Passage, Answer), question-answer pairs, or questions without assuming a given passage, where the answer could be located in some documents that exist in a large collection of documents (e.g., Wikipedia). In general, open-domain QA datasets can be acquired from an open knowledge source, like the universal ontology, or other crawled web sources, and mostly adopted to answer a general query that does not require specific domain knowledge, as illustrated in Figure <ref>. In other words, an open domain can be referred to as a multiple-document QA, in which the labeled answer for an associated question is not supposed to be located within the specific start and end indices, and also it may not be a part of a particular document (it may be in the same document, in different documents, or not exist at all).

An illustration of the open-domain knowledge source, which illustrates the most relevant document(s)/passage(s) to the open-questions that are being asked. This dataset can be retrieved from various knowledge sources (i.e., texts passage, web documents, knowledge bases, tables, images)

§.§ Question and Answer Types

This section addresses Question Types and Answer Types in order to provide an abstract and coherent view of the QA framework in general. It is important to understand Question Types and Answer Types since they are essential elements in all of the QA paradigms, which are discussed in Section <ref>

Determining and categorizing question  and answer types is an important approach that is needed to obtain the most relevant information with the expected response based on the given input. Thus, QA techniques need to perform different rule-based or neural-based strategies to analyze the input, understand the type of a given structure, and capture the subjects, predicates, patterns, concepts, and conditions that could be embedded in a given content, as well as, in order to detect, extract or validate the answer. Then, the most appropriate answer or generated response could be determined accordingly. Such strategies can follow different paths to achieve this goal, either by using pre-defined patterns to be compared with a given context [Sammut and Banerji, 1986, Liu et al., 2017], or by using a semantic representation to automatically discover the patterns of lexical, syntactic, and semantic information embedded in a given context [Levy and Andrew, 2006, Yao and Zhang, 2010], or by parsing the syntactic structure of the given input and extracting named entities (e.g., people, organizations, dates, etc.). The part-of-speech (PoS) tagger, is another strategy to determine the candidate answers  [Harabagiu et al., 2005, Heilman and Smith, 2010]. The determined content is then extracted and validated based on a set of heuristics [Moldovan et al., 1999, Voorhees et al., 2001]. Sequence-to-Sequence or transformer methods are further strategies that could also be used to capture the requirement of the formulated tasks, as mentioned in the previous sections. However, usually, the context with specific topics and information in the closed-domain knowledge source is usually more accurate than those in the open-domain.

In the same context, a question type can be standalone, sequential or multi-choice. Furthermore a question type can contain various forms of contexts, e.g., factoid, list, causal, hypothetical, long-form or complex <cit.>.

* The most common questions start with wh (e.g., what, when, where, which, who) and are usually referred to as simple factual or factoid questions.

* Both factoid and list questions are having a simple answer or a short text of continuous tokens, often as a named entity. Such questions do not require deep processing to obtain the answers, they just need to be matched with the answer vectors which are usually represented by a single word or a span of tokens [Wang et al., 2007].

* The answer to a confirmation question can be yes or no; and needs to be inferred with quantitative or comparative reasoning. Unfortunately, for some non-factoid questions like (what-if, what kind, why, how), the answer may appear out of the given context as abstractive answer.

* The hypothetical questions (i.e., what-if) usually require information related to an event and depend on a specific context. Therefore, there may not be a specific answer for this type of question and for this reason, the accuracy of the obtained answer could be low.

* The causal questions require a description of their entities and cannot be answered with just a named entity as the previous question types. This type of question is often containing justified descriptive answers that can span from sentences to paragraphs to an entire document, and it is most commonly used in an open-domain.

* Complex questions usually consist of several independent questions and often require different types of information that are inferred from multiple sentences, paragraphs, or documents to find an agnostic answer without the supervision of annotated answers. This type of question is therefore more difficult compared to other types of questions. Once the question is classified [Cortes et al., 2020, Lin et al., 2017], then it is possible to determine the related answer using rule-based or neural-based techniques [Kumar et al., 2016, Jing et al., 2019, Tan et al., 2017, Sukhbaatar et al., 2015, Ojokoh and Adebisi, 2018]. However, when the classification of questions is ambiguous, the system must allow for multiple types of answers.

Analyzing the question and detecting the answer type, or finding the embeddings of most similar vectors of question and context, is one of the core tasks of QA algorithms. The QA algorithms also facilitate the query formulation during the query processing stage via parsing the passing tokens with precise descriptions in order to identify what kind of answer is supposed to be returned (e.g., paragraph, description, etc). Different strategies have been proposed to deal with such requirements, such as: Regular Expressions (regex), Part-of-Speech (POS), matched n-gram features, finding the first noun phrase after the question headword ‘wh*’, and  Named Entity Recognition (NER) to identify the given tokens such as human, place, location, entity. The question types classification with different answer types have been investigated in many studies such [Cortes et al., 2020, Rajpurkar et al., 2018, Ben Abacha and Demner-Fushman, 2019, Yang et al., 2018, Joshi et al., 2017, Kwiatkowski et al., 2019, Clark et al., 2020]. The focus detection is meant to capture the question words that are most similar to the answer, while the purpose of the relation extraction is to find the relation that links the entities (i.e., object and subject) in the question to the entity that appears in the context.

A simple question [Bordes et al., 2015] could be represented as bag-of-words or n-grams, and the cosine similarity could be used to find the match between the embedding vector of the candidate answer and the given references [Ojokoh and Adebisi, 2018]. For instance, in [Dai et al., 2016], the formulated task for single-fact QA is to predict the candidate subject and candidate relation of a fact $\{subject, relation, object\}$, i.e, the fact "Frank was born in 1980" have the subject "Frank", relation "was born", and object "1980". For such a task, a neural-based model for single-fact QA was proposed to find the most probable relation and subject, by ranking the relations and the entities of the candidate subjects separately. It employs a conditional factoid factorization to infer the probability of the target relation, and then the target subject can be associated with the candidate relation.

Importantly, modern QA can also deal with complex or narrative questions [Alwaneen et al., 2021] that may assume different question formats, e.g., hypothesis, confirmation, inferential, cause-effect, etc., which require a different form of answers, i.e., single fact, a span of continuous words, generic paragraph/full-document, focus-generic paragraph, dialog or multiple choices, and are expected to return an answer with a contiguous span of words along with quantitative and comparative reasoning [Dubey et al., 2019, Trivedi et al., 2017].

§.§ Definition of a question answering system

A general summary of the description in the previous sections can be provided by the formulation of an abstract QA system. In Figure <ref>, we show a visualization of this abstract model and in the following, we discuss its components in detail. Specifically, in order to define such a QA system one needs to, first, define two components, (i) task and (ii) input data, which will then inform the definition of the prediction model (M).

Abstract formulation of a general question answering (QA) system. The QA system is a prediction model (M) where the question (Q) and the knowledge source (KS) form the input of the model (M) and the answer (A) is its output. A knowledge source can be closed or open-domain. Valid question types are either standalone, sequential or multi-choice question, and a predicted answer type can be a span, abstractive, or agnostic.

A QA task is either (i) answer extraction or (ii) response generation.

In Section <ref>, we have already seen that for realizing a particular QA system one needs to specify all components of a QA framework (see Figure <ref>). However, Definition <ref> refers to a global abstraction level of the overall functioning of a QA system rather than on its individual components. In this respect, we distinguish only two fundamentally different tasks: (i) answer extraction and (ii) response generation. Each of these tasks focuses on a different mechanism of a model (M) for producing an answer, and in Section <ref> we will elaborate on different paradigms that can be used therefor and we will see that for answer extraction there are two paradigms, Information Retrieval-based Question Answering (IRQA) and Knowledge Base Question Answering (KBQA) while for response generation the paradigm is Generative Question Answering (GQA).

The next component we need to define is the input of a QA system. The input can be described as follows:

\begin{equation*}
\text{Input} = (Q,KS): \left\{
\begin{array}{ll}
\text{question,}    & \ Q \  = \{q_{1}, ..., q_{m}\}\\
\text{knowledge source,} & KS  =\{d_{1}, ..., d_{n}\}\\
\end{array}
\right.
\end{equation*}

That means the input is a tuple $(Q,KS)$ where $Q$ can consist of questions $q_i$ with $i \in \{1, \dots, m\}$ and a knowledge source $KS$. Valid question types have been discussed in Section <ref> and can include standalone, sequential, or multi-choice questions while the knowledge source can contain many documents $d_j$ with $j \in \{1, \dots, n\}$ where each document can contain text passages, web documents, or knowledge bases. The information provided by a knowledge source is formally defined as follows.

As a knowledge source (KS) we denote the most general source of information storing of data accessible for a QA system. The data can be closed-domain or open-domain and their format can be structured, unstructured, or semi-structured. A knowledge source can also contain a knowledge base (KB).

From Definition <ref> one can see that a knowledge source is a very flexible source of information that is not restricted in any way. However, a given task and a specific formulation of a QA problem will in general lead to special cases of a knowledge source. In order to clarify this, we distinguish two representative cases:

\begin{eqnarray}
\text{Case 1: } KS = \{ D=\{d_{i}\}_{i=1}^{n}, \text{with } q_j, r_k \in D  \label{eqn.case1}\\
\text { for all } j \in \{1, \dots, m\} \text{ and } k\in \{1, \dots, p\} \} \nonumber
\end{eqnarray}

where $Q=\{q_{j} \}_{j=1}^{m}$ and $R=\{r_{k}\}_{k=1}^{p}$ represent the questions and references (or called gold answers) respectively and $D$ is a set of documents also called a collection. In this case, the questions and gold answers are a subset of the knowledge source, i.e., $Q \subset D$ and $R \subset D$. If the number of questions is the same as the number of answers then $m=p$ and the cardinality of set $Q$ is the same as set $R$, i.e., there are as many answers as questions. However, for multiple or complex answers this is usually not the case which means $m \not = p$. We would like to highlight that the information provided by the gold answer set $R$ is not directly accessible but is sealed within $D$ and the QA system needs to find its elements, i.e., $r_i \in R$.

A knowledge source with this structure can be used for a QA system that solves either the task of answer extraction or response generation. In Section <ref>, we will discuss the QA paradigms, such as Information Retrieval-based Question Answering (IRQA), Knowledge Base Question Answering (KBQA), and Generative Question Answering (GQA) which could all be used for these tasks. However, the task of response generation is commonly considered much harder than answer extraction, and for this reason for a knowledge source with the structure defined in Eqn. <ref> one would prefer to solve the task via answer extraction.

\begin{equation}
\text{Case 2: } KS = \{ D=\{d_{j}\}_{j=1}^{n} \}
\end{equation}

In the second case, the knowledge source does neither contain the questions nor the gold answers. This is the most difficult case because the QA system needs to generate the right responses. Hence, the task of a QA system is answer generation because answer extraction cannot be used. The QA paradigm for this case is Generative Question Answering (GQA) which we will discuss in Section <ref>.

We would like to remark that the above cases do not provide an exhaustive list of different knowledge sources but are merely major instances frequently encountered in the literature. Common extensions of the above cases include answer sets allowed to include no answer, i.e., $A \cup \text{NULL}$, or KS could include a knowledge base (KB). The latter case would have implications for the QA paradigm allowing to use of Knowledge Base Question Answering (KBQA), discussed in Section <ref>.

This heterogeneity is one of the reasons why QA is such a complex problem with a multitude of individual solutions to suit the corresponding cases, e.g., given by the different forms of the knowledge source (KS).

Formally, a QA system can now be defined as a prediction model (M) that assumes the following functional form.

A QA system is a prediction model (M) (either rule-based or neural-based) realized via a function, $M$, that maps an input space, $(Q; KS)$, to an output space, $A$, corresponding to the predicted answers. Its general definition is given by

\begin{eqnarray}
M: (Q; KS) \rightarrow A.
\end{eqnarray}

For a particular question $q_i\in Q$ and knowledge source $KS$ a particular answer, $a_i \in A$ is obtained via the mapping

\begin{eqnarray}
a_i = M(q_i; KS).
\end{eqnarray}

From Definition <ref>, one can see that the output of a QA system is given by $A$ and can assume the following form:

\begin{equation*}
\text{Output: Answer}\ A  =\{a_{1}, ..., a_{n}\}\left\{
\begin{array}{ll}
span, & \ 1\leq a_{start}\leq a_{end} \leq N\\
abstractive \\
agnostic \\
\end{array}
\right.
\end{equation*}

Valid answer types of $a_i$ have been discussed in Section <ref> and a predicted answer \( {a_{i} \in A}\) (e.g., long answer, span answer or NULL) can be marked within specific positions (i.e., \(a_{start}\) and \(a_{end}\)) in a given document, while the abstractive answer could be out of a given context. Finally, an agnostic answer can be inferred from multiple sentences, paragraphs, or documents without the supervision of the annotated answers.

It is important to emphasize that from Definition <ref> follows that the meaning of Q and KS is not symmetric. Instead, the knowledge source provides a form of parametrization of the prediction model M. Hence, different questions $q_i$ can be asked without changing the knowledge source.

Finally, in order to evaluate a predicted answer one needs a gold answer (also called a reference, labeled answer, or ground truth) corresponding to ${ r_i \in R}$. Here $R$ is the reference set containing all gold answers.

An error score of a QA system is a function that maps the input space, $(A, R)$ or $(A)$ respectively to case 1 and case 2 of definition <ref>, to the output space $S$, corresponding to error scores, by

\begin{eqnarray}
E_{Case1}: (A, R) \rightarrow S
\end{eqnarray}

\begin{eqnarray}
E_{Case2}: (A) \rightarrow S
\end{eqnarray}

whereas a particular pair $(a_i, r_i) \in (A, R)$ is mapped to a particular score, $s_i \in S$, by

\begin{eqnarray}
s_i = E_{Case1}(a_i, r_i).
\end{eqnarray}

\begin{eqnarray}
s_i = E_{Case2}(a_i).
\end{eqnarray}

The output space of scores $S$ can assume different forms. For instance, a score $s_i$ can either assume values between zero and one.

\begin{eqnarray}
S = [0,1],
\end{eqnarray}

or it is either zero or one, i.e.,

\begin{eqnarray}
S = \{0,1\}.
\end{eqnarray}

An example of an error score of the former is the precision and for the latter the exact match (EM). Both error scores and many more will be discussed in detail in Section <ref>.

§ QUESTION ANSWERING PARADIGMS

It is clear that the number of different QA systems that can be established for different combinations of the main components of a QA framework described in Section <ref> is enormous. Interestingly, all of these realizations can be categorized into three QA paradigms that are dominating the design of current QA systems: (1) Information Retrieval-Based Question Answering, (2) Knowledge Base Question Answering, and (3) Generative Question Answering.

§.§ Information Retrieval-Based Question Answering

The first paradigm we discuss is Information Retrieval-based Question Answering (IRQA) which is also known as open-domain QA. It is widely used and the most typical paradigm for many commercial applications such as IBM's Watson [Ferrucci, 2012] or search engines like Google.

IRQA tries to predict the intent that may exist in the question, in order to identify the most relevant documents among available collections [Kolomiyets and Moens, 2011]. It is not just taking a query in natural language form to find a list of relevant documents, but it provides an extra layer for handling those relevant documents and for extracting the answer by matching identified intent found in the question within the responses that may exist in the database. Usually, this paradigm includes two fundamental components called document-retriever and document-reader as depicted in Figure <ref>. In the following, we describe their functioning.

Architecture of information retrieval-based question answering (IRQA). In an IRQA the document-reader processes the query using different approaches(i.e.,  parsing, focus detection, relation extraction, lexical answer type detection, named entity tagging, question classification, etc). Furthermore, it retrieves the most relevant documents or passages from an available knowledge source (structured or unstructured data) and scores the candidate's answers. The document-reader is used for reading the retrieved documents and extracting the response.

§.§.§ Document-retriever

The purpose of a document-retriever is to process the query and retrieve the most relevant documents, then rank every retrieved document to a given query (question) based on similarity score. This process starts with weighting the terms of each document using, e.g., Term Frequency-Inverse Document Frequency (TF-IDF) [Luhn, 1957, Jones, 1972] or Okapi Best Matching (BM25) [Kamphuis et al., 2020, Robertson et al., 1995] or any other dense weighing mechanisms, to identify the informative terms among the most relevant documents. Then both query and retrieved document vectors need to be normalized, and a similarity score is computed between these vectors using e.g., the cosine similarity or the dot product. In order to efficiently improve the search speed and rank the most relevant documents that contain informative data, like the document frequency or term counts, an inverted index or alternative indexing technique based on e.g., hashing algorithm needs to be used[Chen et al., 2017, Manning et al., 2010]. However,  the dictionary and postings list are the main components of the inverted index that hold the given query term frequencies and the list of document IDs associated with each term respectively.

§.§.§ Document-reader

A document-reader is also called a comprehension algorithms that deals with different responsibilities, such as parsing the query Q, reading the relevant documents D that have already been retrieved by the document retriever from the available knowledge source (e.g., open-domain datasets), selecting the scored passages, and extracting the appropriate answer A. The document reader performs these tasks, which usually start with detecting the focus and extracting the relation from the question itself, and then, formulating certain keywords or embeddings in order to find a possible answer to the given question among the retrieved documents by computing a probability as \(P(a\vert{q},p)\).

Moreover, the positions of the start and end tokens of the answer could be represented as \(a_{s}\) and \(a_{e}\) respectively, and the probability of finding each token can be written as follows:

\begin{equation}
P(a\vert{q},p)= P_{s}(a_{s}\vert{q},p_{i}) \times P_{e}(a_{e}\vert{q},p_{i})
\label{eq:pOD}
\end{equation}

Usually, the knowledge source (i.e., relevant document) needs to be retrieved by document-retriever, and then it should be passed along with the questions to QA comprehension algorithms, to train the document-reader component for predicting the candidate answer(s).

However, during the testing phase, the system is given only the question without the passage. The document-retriever component is expected to search for the relevant passages in the entire web resources or Wikipedia corpus and then feed these retrieved passages to the document-reader in order to produce the answer, either in an extractive form (e.g., a span of a text) or in an abstractive form.

Alternatively, recent transformer-based algorithms treat the associated questions and passages as encoded strings, separated by a [SEP] token, in order to produce an embedding token for each passage token \(p_{i}\), as shown in Figure <ref>.

An illustration of a simple training phase of an IRQA as used by BERT. Here the associated question and the passage are treated as encoded strings separated by a [SEP] token, and the output word vector is encapsulating the sequence of tokens that are located between the start (PS) and the end position (PE) and represents the anticipated response.

The positions of start and end tokens of the possible  answer in each passage \(p_{i}\), can be predicted by learning the start S and end E embedding vectors through a trained linear layer (e.g. SoftMax), during the fine-tuning phase as shown in Equations <ref> and <ref>:

\begin{equation}
P_{s}= \frac{exp(S.{\acute{p}_{i}})}{\sum _{j}exp(S.{\acute{p}}_{j})}
\label{eq:b1}
\end{equation}

\begin{equation}
P_{e}= \frac{exp(E.{\acute{p}_{i}})}{\sum _{j}exp(E.{\acute{p}}_{j})}
\label{eq:b2}
\end{equation}

Here \(p_{s}\) and \(p_{s}\) are the probabilities of the span-start, and the span-end respectively, which could be estimated by finding the cosine similarity between the start or the end vector and each output token in the passage \(\acute{p}_{i}\) and then normalize the result over all the output tokens in the passage \(\acute{p}_{j}\).

For estimating the training loss of each instance, the Log-Likelihood function (LL) is used to compute the negative sum of probabilities of the start \(P_{s}\) and the end \(P_{e}\) positions, as shown in equation <ref>:

\begin{equation}
LL= -log P_{s} - log P_{e}.
\label{eq:LL}
\end{equation}

A possible problem is that some datasets may not include the answer within their passages [Rajpurkar et al., 2018, Kwiatkowski et al., 2019]. In this case, the [CLS] token will be used as the answer with a start and end pointer for a given question [Devlin et al., 2018]. In addition, a concatenation for each observation may be required [Alberti et al., 2019] when the 512 input tokens of BERT are smaller than the annotated gold passages of some datasets [Kwiatkowski et al., 2019]. Hence, all observations in the entire document/passage will be scanned with a sliding window of size 512, to find the span answer, and the observation will be marked if an answer is found, otherwise, no label will be obtained. If more than one observation is found, the final answer will be selected from the observations with the highest probability. Some QA systems may use hybrid knowledge sources, see, e.g., [Ferrucci, 2012].

Most modern IRQA systems utilize neural-based techniques, which require huge amounts of data. Unfortunately, the domain knowledge is not fully utilized, the available datasets still suffer from a limited size, and annotating process is very expensive.

In order to enhance the capabilities of IRQA systems and to avoid the vocabulary mismatch problem in the extractive QA task [Furnas et al., 1987], several techniques have been proposed. For example, instead of using the sparse vector of word counts for editing the distance or finding the exact match between the sequence of words in the query and answer, a dense embedding vector was introduced to find the semantic similarity between the candidate answer and query [Deerwester et al., 1990, Mahmoud and Zrigui, 2019].

in addition, a more sophisticated neural network architecture with two encoders has e been proposed to address the vocabulary mismatch issue by encoding the query and the context [Karpukhin et al., 2020, Lee et al., 2019, Liu et al., 2016]. Moreover, instead of using a [CLS] token for representing the encoded text, variant models of BERT have been used along with an average pooling layer over the output of all tokens, to add extra encoding weight and compute the similarity [Lee et al., 2019].

Transformer models like BERT [Devlin et al., 2018], RoBERTa [Liu et al., 2019], ALBERT [Lan et al., 2019], distilBERT [Sanh et al., 2019] have been employed as pre-trained models with a large number of example (training) questions and answers and have shown promising results. These models can also extract the answer of a given query from the collection of documents directly without the need to manually define features like the answer type. However, those models require massive computing resources along with huge training datasets.

Moreover, some of these transformers have adjusted their encoders to enhance the dense vector representations in order to deal with long documents and to improve IRQA components [Roberts et al., 2020, Radford et al., 2019].

Finally, Only IRQA paradigm has a document-retriever component, while the other paradigms like knowledge-based and generative question answering that will be discussed in the following sections, do not have it, and involve just the document-reader component.

§.§ Knowledge Base Question Answering

Another main paradigm of QA systems is Knowledge Base Question Answering (KBQA) which is also known as closed-domain QA. A KBQA retrieves the answer directly from a specific knowledge-base; and eliminates the need for the document recovery component, which is an essential component of IRAQ.

In order to accomplish this, KBQA relies on an internal search using parse or semantic vector representations to map the query to a local database [Dimitrakis et al., 2020]. For realizing such a mapping there are two common approaches, the first uses a graph-based model and the second semantic parsing [Yih et al., 2015, Xu et al., 2015, Sun et al., 2022, Zhang et al., 2022]. Such algorithms can be designed to address task-specific requirements [Diefenbach et al., 2018, Dong et al., 2015, Bordes et al., 2015, Hu et al., 2017, Lan et al., 2019], e.g., by detecting frequently observed patterns or relationships. This can be done in a supervised or unsupervised manner.

Supervised learning methods are used to process the query against the question-answering pairs dataset and create required segments of the parsing tree. Then it maps the relevant entities, e.g., parts-of-speech (nouns, verbs, and modifiers) to an appropriate form and matches the segments with existing relationships.

At this point, the KBQA model needs to gather more data from the parsing tree, and map it to more complex and coherent queries. It begins with identifying the subject of the question and linking it to the subject entity of the knowledge base. The answer is then derived by implementing a parsed logic model or via a graph representation.

KBQA based on closed-domain can be more coherent and interpretable by including dictionaries that are able to capture the semantics and the structure of a natural language. Recently, studies have begun to pay more attention to answering complex KB questions [Hu et al., 2018, Luo et al., 2018] that comprise small scope entities or those with numerous subjects, complex relationships, multi-hops reasoning along with numerical operations, and compiled further the final answer by choosing the possible candidates [Zhu et al., 2020, Lan et al., 2019, Qu et al., 2018]. To address such tasks, KBQA has used a variety of mechanisms, either by representing the overall information related to the question by means of a specific graph, e.g., a knowledge graph, that is capable of classifying all the entities extracted based on their relevance to a question, or by using a symbolic logic model to represent the question and then apply it to the knowledge-base to obtain the final answers [Hu et al., 2017, Bordes et al., 2015, Dong et al., 2015].

§.§ Generative Question Answering

In recent years, a third paradigm is becoming increasingly popular, which is called Generative Question Answering (GQA) [Ni et al., 2021]. This paradigm seeks to directly generate a response according to the given input [Duan et al., 2017, Zhang et al., 2021]. The response can be generated as standalone, sequential or multiple choice question [Reddy et al., 2019, Duan et al., 2017, Zhou et al., 2017], based on different levels of context such as: keywords [Pan et al., 2020, Indurthi et al., 2017], sentences [Gao et al., 2018, Ali et al., 2010, Wang et al., 2007], paragraphs [Du et al., 2017, Zhao et al., 2018], documents [Yang et al., 2017, Pan et al., 2020], or multiple documents [Cho et al., 2019, Cho et al., 2019].

In the literature, one can find many studies employing a large variety of architectures with different levels of complexity along with bulky features and auxiliary mechanisms in order to generate a suitable response from a given input (i.e., passages or documents). However, deep learning models with a sequence-to-sequence architecture and transformer models are becoming the most widely used technique [Sutskever et al., 2014]. The sequence-to-sequence architecture has been built using different models and employs two layers of sequence neural network such as RNN or LSTM [Song et al., 2018, Sutskever et al., 2014], one as an encoder for the input source context, and the other as a decoder for the embedded information (context vector) of the generated response [Duan et al., 2017]. A long input sequence can cause a problem with RNN models; since RNN can forget such long sequences during the training phase due to the gradient vanishing phenomenon that hindered the model from updating its learning weights with too small gradients [Hochreiter, 1998]. Such architecture has been further extended to be adjusted with block cells to tackle the gradient vanishing problem [Gers et al., 2000] and with more linguistic features [Zhou et al., 2017]. The attention-based model also has been introduced to investigate the effect of encoding sentences against paragraph-level information [Du et al., 2017, Zhao et al., 2018]. Moreover, reinforcement models based on policy gradients have been proposed for QA to obtain good results [Yuan et al., 2017, Zhang and Bansal, 2019]. To mitigate the memory bottleneck of RNNs [Dong et al., 2019], a transformer over RNNs [Vaswani et al., 2017, Dong et al., 2019, Lopez et al., 2021, Qi et al., 2020] has been adopted to focus on a particular context in a paragraph. Despite the fact that most of the above-mentioned techniques were found to be more robust compared to the traditional techniques, they were also found to be more complex and hungry for more data (it demands huge amounts of data along with vast computational resources). For this reason, fine-tuned transformers with a pretrained language model [Lopez et al., 2021, Radford et al., 2019] were proposed to diminish some needs for data and computational resources.

§ BENCHMARK DATA AND EVALUATION SCORES

Since QA comprises many complex tasks with many variations, the benchmarking of QA is not straightforward. For this reason, task-specific datasets are needed in combination with expressive error scores. Therefore, drawing a conclusion about the quality of a QA system requires an informed assessment using labeled (annotated) data together with quantifiable scores that allow a comparison of the performance between different QA systems. In the following section, benchmark datasets and evaluation scores are discussed which are widely used in the literature.

§.§ Benchmark Datasets

Many datasets have been proposed for benchmarking QA systems. Such datasets vary in their formats, types, the number of questions, and the related answers they contain. Each question of such datasets may be associated with one or more answers or none. When there is no answer associated with a question, the answer is usually marked by the annotators as 'none' as a gold answer to be returned during the evaluation process. Some QA systems based on neural techniques (e.g., end-to-end models) try to limit the number of duplicate questions in each subset of a dataset by randomly dividing the question-answer pairs into three subsets, known as training, development, and testing set, where the development set is used for fine-tuning the hyperparameters of a selected model, see [Du et al., 2017, Lewis et al., 2020].

Usually, a QA system needs to be trained upon such datasets in order to be able to produce an answer or generate a desirable response. For this reason, several efforts have been made by researchers to create different types of datasets to be investigated with different QA paradigms. For example, Table <ref> shows a list of document-based datasets that can be used for IRQA, and Table <ref> shows another list of datasets that can be used for KBQA.

A list of document-based datasets that contain a set of passages and associated questions. The column 'Size' gives the number of questions and answers in the corresponding datasets and 'Description' provides information about the application domain.

Dataset     Size     Description     Reference

BMKC-LS     369780 questions     Biomedical dataset    [Kim et al., 2018]

cMedQA v2.0     180K questions, and 203569 answers    Medical dataset     [Zhang et al., 2018]

MedQuAD     47457questions, and 47457 answers    Medical dataset     [Ben Abacha and Demner-Fushman, 2019]

StackExchange cQA     20278 questions, and 82260 answers     Financial dataset     [Huang et al., 2018]

TOEFL     963 questions, and 3852 answers     Listening Comprehension Test dataset     [Lee et al., 2019]

WebMedQA     63284 questions, and 316420 answers    Medical dataset     [He et al., 2019]

A list of knowledge-based datasets that contain a set of entities and associated relations. The column 'Size' gives the number of entities and relations in the corresponding datasets and 'Description' provides information about the application domain.

Dataset     Size     Description     Reference

LC-QuAD 2.0    21258 entities, and 1310 relations    large scale complex question answering dataset    [Dubey et al., 2019]

MetaQA   43233 entities     A movie dataset with multi-hops questions    [Zhang et al., 2018]

PathQuestion   2215 entities, and 364 relations    A Freebase dataset with 2-hop path   [Zhou et al., 2018]

PathQuestion Large   5035 entities, and 14 relations    A Freebase dataset with 3-hop path   [Zhou et al., 2018]

SPADES   4K entities    A dataset that contains question types with blanks to fill in   [Bisk et al., 2016]

WorldCup2014   1127 entities, and 6 relations    A football players knowledge base with multi-hops reasoning.    [Zhang et al., 2016]

In general, knowledge base datasets are created by considering the question subject as the topic entity in a knowledge base, while various templates may be used to pre-create simple questions. Relying on these templates, more complex questions can also be created,  as well as by using an executable logic template. In addition, a set of rules can also be used to extract the response. Besides, to further improve the generated logical models and generate natural language questions that appear more diverse and fluent, crowd workers are hired to reformulate the queries.

Creating a high-quality data set dedicated to generative question answering is an important direction that can significantly enhance the development of QA systems. Popular GQA datasets can be classified based on the type of target answers and generated questions, as shown in Table <ref> (standalone questions with simple answers), Table <ref> (standalone questions with abstractive answers), Table <ref> (standalone questions with agnostic answers), Table <ref> (sequential questions with abstractive answers), Table <ref> (multiple choice questions with simple answers) and Table <ref> (multiple choice questions with abstractive answers.). Moreover, many of these datasets have been also tailored to be used for information retrieval-based or knowledge-base QA systems.

GQA datasets for standalone questions with simple answers. The column 'Size' gives the number of examples (i.e., question-answer pairs) in the corresponding datasets, and 'Description' provides more information about the datasets.

Dataset     Size     Description     Reference

SQuAD 1.1     107,785 question-answer pairs       Collected as crowdsourced QA pairs from Wikipedia from 536 Wikipedia articles.     [Rajpurkar et al., 2016]

NewsQA    120,000 question answer pairs     Collected as crowdsourced QA pairs from 10K CNN news articles.     [Trischler et al., 2016]

SearchQA    140,000 question answer pairs     Each pair has 49.6 snippets on average.     [Dunn et al., 2017]

HotpotQA    113,000 question answer pairs     Wikipedia-based QA pairs with questions and answer reasoning.    [Yang et al., 2018]

Natural Questions     307,373 training examples, 7,830 development examples, and 7,842 test examples.    Each example consists of a Google query (i.e., question) and a related answer within the Wikipedia page.    [Kwiatkowski et al., 2019]

TriviaQA    650K question-answer-evidence triples.    Collected as triples of question-answer pairs from different Wikipedia and Web pages.    [Joshi et al., 2017]

GQA datasets for standalone questions with abstractive answers. The column 'Size' gives the number of examples in the corresponding datasets and 'Description' provides information about the datasets.

Dataset     Size     Description     Reference

MS MARCO     1010916 questions, 8,841,823 paragraphs retrieved via Bing from 3,563,535 web documents.
The answer for each question has been manipulated by crowdsourced, and around 182669 answers were completely rewritten.     [Bajaj et al., 2016]

NarrativeQA    46765 QA pairs written by crowdsourced.     The script was gathered as 1567 stories from different resources i.e., books and movies.     [Kočiskỳ et al., 2018]

DuReader    200K questions, along with 420K answers.     An open-domain dataset
with 1M documents where answers are manually generated.
[He et al., 2017]

SQuAD 2.0     150K    This dataset combines the 100,000 questions in SQuAD1.1 with over 50,000 un-answerable questions.     [Rajpurkar et al., 2018]

GQA datasets for standalone questions with agnostic answers. The column 'Size' gives the number of examples in the corresponding dataset and 'Description' provides information about the dataset.

Dataset     Size    Description     Reference

LearningQ     230K document-question pairs.     Based on popular online learning platforms.     [Chen et al., 2018]

GQA dataset for sequential questions with abstractive answers. The column 'Size' gives the number of examples in the corresponding dataset and 'Description' provides information about the dataset.

Dataset    Size     Description     Reference

CoQA     127K conversational questions with answers.
Designed to enable machines to respond to a series of questions that appear in conversation, based on 8K conversations about texts gathered from seven different domains.
[Reddy et al., 2019]

QuAC    14K information-seeking QA dialogues (100K questions in total).     In order to make QuAC more like search engine queries that are retrieved from users’ dialogues, this dataset consists of large-scale dialogues of Wikipedia articles, in which crowd-workers do not know the answer to their questions ahead of time.
[Choi et al., 2018]

GQA dataset for multiple choice questions with simple answers. The column 'Size' gives the number of examples in the corresponding dataset and 'Description' provides information about the dataset.

Dataset    Size    Description     Reference

CBT    687343 questions
collected from 108 books.
It aims to measure the robustness of language models based on a wider linguistic context.
Each question is provided with up to 10 possible answers that appear in the context sentences as well as the query.     [Hill et al., 2015]

GQA datasets for multiple choice questions with abstractive answers. The column 'Size' gives the number of examples in the corresponding datasets and 'Description' provides information about the datasets.

Dataset     SizeNumber of Questions     Description     Reference

RACE    97687 multiple choice questions along with 27933 passages.
Large-scale reading comprehension dataset collected from English exams for middle and high Chinese schools consists of nearly 28,000 passages and nearly 100,000 questions generated by human experts, where each question has four possible answers, and only one answer is correct.
[Lai et al., 2017]

MCTest     500 fictional stories and 2000 questions.     a freely available set of stories and associated questions. Each story has four multiple-choice questions. The stories and questions are selectively chosen to reflect what a young child would understand.     [Richardson et al., 2013]

§.§ Taxonomy of Evaluation Scores

Every natural language is rich in words and synonyms, which makes it possible to produce a sheer unlimited combination of output sentences that can include different phrases with vastly different interpretations. Hence, due to this diversity of language expressions, the generated output of a QA system may involve different forms of ambiguities that can exist in many forms, e.g., lexical, semantic, syntactic, etc.; The generated output could be less informative and difficult to understand due to these ambiguities, which may add some complexity and vagueness in terms of fluency, correctness, and coherence to the language. However, the goal of NLG is to obtain a more valuable and coherent output text that has more readability and understandability. Thus, the system's output (i.e.,  hypothesis, generated/predicted response/answer) needs to be evaluated against the given reference (also called ground truth, gold answer, labeled response) in order to determine its quality [Van Der Lee et al., 2019, Gatt and Krahmer, 2018]. However, due to the complexity of natural language, such output is a structured object rather than a single number, which makes the evaluation itself a complex task.

For this reason, many different types of evaluation scores have been proposed [Gatt and Krahmer, 2018, Lin and Hovy, 2003, Sai et al., 2022, Celikyilmaz et al., 2020]. Overall, these scores can be broadly classified into two categories, see Figure <ref>:

(i) Human Centric Evaluation Score (HCES)

(ii)  Automatic Evaluation Score (AES)

Every category has its own strengths and weaknesses. In general, a HCES is considered the best evaluation that gives the most trustworthy score. Typically, HCES relies on a group of people (e.g. experts or specialists) to evaluate the output of a QA system based on certain guidelines and criteria, e.g., regarding adequacy, fluency, and coherence of a text. However, it is also prone to human errors caused by subjectivity and bias in opinion. Frequently, a 5-point Likert-scale [Likert, 1932] or numerical ranking criteria is used as a measurement tool for HCES evaluations [Amidei, 2021].  Conceptually, HCES can be further classified into two sub-categories: Absolute evaluation and relative evaluation.

Absolute evaluation: In this type of HCES, individuals are asked to evaluate the output of a natural language generation/inference model using a 5-point scale [Belz and Kow, 2010]. The evaluator assesses the output texts of a task based on predefined criteria or rubric, rating each from 1-5 or on a nominal scale, For example, a statement such as "Rate the output based on the naturalness of the language" with options as very unnatural, unnatural, neutral, natural and very natural, or with 1-5 numerical options, each responding to a similar semantic meaning. The results of which will be averaged over the rubric and used as the evaluation/annotation output. For example, in machine translation, the task may require an evaluation from a person who is familiar with either the target language (i.e., monolingual) or both source and target languages (i.e., bilingual) to perform the required assessment (rating) on the generated text. The absolute method is often subjected to the bias of the evaluator due to the discreteness of the scale and inter-annotator disagreements. Therefore, individual evaluators may not always be preferred for some tasks, e.g., in order to obtain a more accurate assessment.

Relative evaluation: In this approach, the task output is not given an exact absolute score, instead given several outputs to a given task, the evaluator is asked to order them based on the quality of the output [Amidei, 2021]. often tasks with lengthier outputs (e.g., dialogue generation, machine translation) requires that they be evaluated as a whole conversation or a whole translation. In this case, either experts or crowd-source workers could be asked to rate the output of a system (i.e., the multiple responses or comparing the predicted response with the multiple references), by ranking each output as compared to each other (for example $n$ different conversations with a chatbot from most human-like to least human-like). Relative evaluation is preferred when the speed of assessment matters. However, crowdsource workers are not preferred when a given task does require domain knowledge (e.g., in a medical field).

The scores acquired by each evaluator can be computed as a weighted average based on their past performance, or aggregated as a simple average [Raykar et al., 2010]. In order to ensure the reliability of the evaluation or/and annotations, HCES are subjected to reliability measures such as intra-observer agreement (IA), and inter-annotator agreement (IAA). In the case there are clearly defined expected evaluation outputs, the accuracy of the evaluation can also be a measure of data reliability. In general, a high inter-annotation agreement is desirable, which measures the agreement between several evaluators on the quality ranking of an output. Whereas, the intra-observer agreement is used as a reliability measure when the evaluation or annotation is done by a smaller group of experts over a long period of time. Here a certain amount of time is let to pass after the initial evaluation, thereafter same evaluator is asked to rate the same outputs. If the evaluator's previous and current ratings have a high agreement then the data is considered reliable. The IAA is the most utilized data reliability measure in HCES due to convenience and in literature, several a coefficient of the agreement have been introduced to measure IAA such as Cohen's Kappa, Fleiss Kappa, or Krippendorff's alpha [Krippendorff, 2011]. However, achieving a sufficiently high IAA is difficult due to human error, insufficient guidance or preparation, and ambiguity in the generated response [Gatt and Krahmer, 2018, Thomson and Reiter, 2020].

Despite its obvious benefits and superiority. HCES is expensive, time-consuming, tedious, and requires domain expertise, which makes it an impractical choice when dealing with a task with a larger data output or some dynamic behavior. However combining HCES with MTES, where the trained evaluator models receive some feedback from human annotators, a more practical success can be achieved. An example of this is ADEM [Lowe et al., 2017], which will be discussed later in the section.

The taxonomy of evaluation scores. The used acronyms have the following meaning: HCES: Human-Centric Evaluation Scores,  AES: Automatic Evaluation Scores, UAES: Untrained Automatic Evaluation Scores,  MTES: Machine-Trained Evaluation Scores. The legend indicates the type of score in the branches.

Unlike HCES, the AES  are cheaper evaluation techniques (e.g., do not require domain experts as the HCES do) and found to be more practical when dealing with a large task that may involve some dynamic behavior  [Reiter and Belz, 2009]. Importantly, such scores are usually correlated well with human judgments <cit.>.

AES can be further sub-categorized into: context-based and context-free evaluation, discussed below, depending on the utilized mechanisms of the evaluation process.

A context-free evaluation does not consider the context during the evaluation process. Instead, it just considers the sequences of words (e.g., n-grams) among the obtained output and the reference in order to assess the overlap or match. For this reason, this evaluation category can be seen as tasks-agnostic and easily adopted to a wider range of QA systems. In contrast, a context-based evaluation is specifically designed to address a particular requirement of a specific problem and cannot be easily adopted for different problems like the context-free evaluation.

Both context-free and context-based AES scores can be further sub-categorized into:

(i) Untrained Automatic Evaluation Score (UAES)

(ii) Machine-Trained Evaluation Score (MTES)

A UAES does not require any pre-training because such scores do not depend on pre-defined parameters. The lack of parameters makes UAES easy to use, so it becomes very popular. Such category can be further sub-categorized based on the operation level among the text units, which can be:

* Character-based

* Word-based

* Embeddings-based

A character-based score shows promising performance in evaluation task for machine translation [Popović, 2015]. Importantly, this error score is simple enough to directly work on the response and reference strings, and does not require tokenization.

A word-based score treats the response and the reference as a bag-of-words and does not usually consider the context of an input text for the evaluation. Instead, it compares and evaluates the response against the available reference via a set of heuristic features,  such as Precision or Recall, and computes the similarity between text units based on the matching overlap, or based on the number of word edits required to make the response similar to the given reference [Levenshtein et al., 1966, Roemmele and Gordon, 2015]. The  word-based scores include a wide range of error scores, such as BLEU [Papineni et al., 2002], METEOR [Banerjee and Lavie, 2005], ROUGE [Lin, 2004], NIST [Doddington, 2002] and CIDEr [Vedantam et al., 2015].

An embedding-based score is not designed to simply rely on overlap matching between response and reference, as most of the word-based scores do, but to capture the semantic similarity (i.e., word or distributional similarities) that may exist between answer and reference [Mikolov et al., 2013, Lo, 2017, Clark et al., 2019, Zhang et al., 2019].

In contrast to UAES, a MTES contains adjustable components, i.e., parameters, which are specifically estimated for a given task via a learnable model. That means an MTES is a parametric model which needs to be trained based on data. MTES can be classified into two sub-categories:

(i) Composite measures

(ii) Holistic measures

In the literature, composite measures are also called feature-based measures and holistic measures are called end-to-end measures. The difference is that a holistic measure cannot be separated into individual error scores while this is the case for feature-based measures where the features correspond to such individual error scores.

Composite measures: This category of error scores combines features using a parametric model whereas the features can correspond to any score in the categories S-UAES or A-UAES, e.g, precision, recall, or BLEU. Typically, a large number of such heuristic scores are used. For combining those features either simple parametric models are used, e.g., linear regression (see BEER [Stanojević and Sima’an, 2014] or BLEND [Ma et al., 2017]), or complex models based on neural networks (see [Sharif et al., 2018]).

Holistic measures: This category of error scores utilizes end-to-end models based on neural networks, e.g., transformers, to perform the evaluation. The end-to-end models can be directly applied to statistical or contextualized features that exist within the response or reference to compute the scores.  Such models may use different strategies to perform the evaluation process: (i) referenced scores, which compare the generated response with a provided gold answer, by learning an alignment score between context and response to approximate human judgments [Lowe et al., 2017], (ii) hybrid referenced-unreferenced evaluation score [Tao et al., 2018], where the score is trained without needs for human responses by smoothing the negative samples directly from the dataset,  or (iii) unreferenced scores (i.e., learned in an unsupervised manner) that uses large pre-trained language models to extract latent representations of text units (i.e., utterances or words), and take advantage of the time shifts that exist between them [Sinha et al., 2020]. The MTES based on  end-to-end  models include a wide range of error scores such as BertScore[Zhang et al., 2019], RUSE [Shimanaka et al., 2018], RUBER [Tao et al., 2018], BLEURT [Sellam et al., 2020], ADEM [Lowe et al., 2017], MaUde [Sinha et al., 2020].

§ QUANTITATIVE ERROR SCORES

In the previous section, we introduced a taxonomy of evaluation scores providing an organization of the many score categories. In this section, we discuss specific scores thereof that are used as UAES and MTES. For reasons of clarity we further sub-categorize UAES into Simple Untrained Automatic Evaluation Scores (S-UAES) and Advanced Untrained Automatic Evaluation Scores (A-UAES).

For the following presentation of the scores, we assume the predicted answer $A$ and gold answer (reference) $R$ are given by:

\begin{eqnarray}
\text{predicted answer: } A &=& a_1, a_2,\dots a_m \label{eqn.A} \\
\text{gold answer: } R &=& r_1,r_2,\dots r_n \label{eqn.R}
\end{eqnarray}

That means $A =a_1, a_2,\dots a_m$ is a response (sentence) consisting of $m$ words $a_i$ and correspondingly $R=r_1,r_2,\dots r_n$ is the gold answer (sentence) consisting of $n$ words $r_j$. Depending on the context $a_i$ and $r_j$ can be words, unigrams, bigrams, or n-grams. Hence, our notation should be flexible enough to accommodate the common cases encountered. Hence, we assume A and R are tokenized and indexed according to Equation <ref> and <ref>.

§.§ Simple Untrained Automatic Evaluation Scores (S-UAES)

In the category Simple Untrained Automatic Evaluation Scores (S-UAES), the most widely used error scores in the literature are an exact match (EM), precision, recall, F1-score, error rate (ER), average precision (AP), mean average precision (MAP) and mean reciprocal rank (MRR). In the following, we provide a discussion for each score.

* Exact Match (EM): EM is a score that gives a one if the predicted answer is identical to the gold answers and a zero otherwise. That means EM is a binary score assuming values in $\{0, 1\}$.

Suppose we have a labeled answer R:  "The quick brown fox jumps over the lazy dog",  and a predicted response  A  "the dog has slept on the mat".

Based on the given definition of EM, the EM score of Example <ref> is $0$, since there are some differences between A and R.

* Precision: The precision is the proportion of correct answers over all anticipated answers. It indicates the relevant returned documents.

\begin{equation}\label{key}
Precision =\frac{\{relevant\ documents\} {\displaystyle \cap }\{retrieved\ documents\}}{\{retrieved\ document\}}
\end{equation}

Alternatively, the precision can be calculated as follows:

\begin{equation}\label{key}
Precision =\frac{TP}{TP+FP}
\end{equation}

where TP is the number of true positives and FP is the number of false positives. At that point, the precision can be computed as the number of n-grams that match between A and R divided by the total number of n-grams in A. On this basis, the computed precision of  Example <ref> is $3/7=0.43$, where  $3$ is the number of n-grams found to be matched between A and R, and  $7$ is the total number of n-grams of A. The n-gram match for precision is position independent.

* Recall: The recall is the proportion of correct anticipated answers over the gold answer. It measures the relevant (correct) documents over all the actual possible documents. The output of such a score for each query is a binary value that indicates either or not the document is contained in the selection.

\begin{equation}\label{key}
Recall =\frac{\{relevant\ documents\} {\displaystyle \cap }\{retrieved\ documents\}}{\{relevant\ document\}}
\end{equation}

Alternatively, the recall can be calculated as follows:

\begin{equation}\label{key}
Recall =\frac{TP}{TP+TN}
\end{equation}

where TP is the number of true positives and TN is the number of true negatives. Therefore, the recall score could be computed as the number of n-grams that match between A and R divided by the total number of n-grams in R. Thus, the computed recall score of example <ref> is ($3/9=0.33$), where  $3$ is the number of n-grams found to be matched between A and R, and  $9$ is the total number of n-gram that R composed from.

* F1-score: The F1-score aims to find the harmonic mean (balanced in importance)  between recall and precision. It measures the word overlap between the predicted and the gold answer in a more flexible way than that used in EM, as it allows us also to trade off precision against the recall. However, it does not capture the similarity between two correct answers that differ in their semantic content. The F1-score is defined as follows:

\begin{equation}
F1 = 2 * \frac{Precision * Recall}{Precision + Recall}
\label{eq:f1}
\end{equation}

The F1 score  could be computed based on the equation <ref> as \(2 \times \frac {0.43 \times 0.33}{ 0.43 + 0.33  } =0.37\), where  $0.43$ and  $0.33$ are the score values of precision and recall respectively, that found over A and R in the given example.

* Error Rate (ER): The ER is the frequency or the probability of errors occurring when comparing A with R.

\begin{equation}\label{key}
Error \; Rate =\frac{FP+FN}{N}
\end{equation}

where FP is the number of false positives, FN is the number of false negatives, and N is the total number of data points examined overall.

* Average Precision (AP): The AP is calculated as the weighted mean of precision for a query in the query set.

\begin{equation}\label{key}
AP = \frac{\sum _{x=1} ^{n} P(k)* R(k)}{number\ of\ the\ relevant\ documents}
\end{equation}

where k is the rank in the sequence of retrieved documents, n is the number of retrieved documents, P(k) is the precision at cut-off k ranked list documents, and R(k) is an indicator function equaling 1 if the item at rank k is a relevant document, zero otherwise.  The average is over all relevant documents and when the relevant documents are not retrieved it holds a precision score of zero.

* Mean Average Precision (MAP): The MAP is a score for evaluating the ranked retrieval list of answers, as the mean of AP scores for encountered relevant documents for each query.

\begin{equation}\label{key}
MAP =\frac{1}{N} \sum _{x=1} ^{n} AP_{i}
\end{equation}

where the N is the number of queries, and \(AP_{i}\) is the average precision score for encountered relevant documents for each query.

* Mean Reciprocal Rank (MRR): The MRR takes the position (rank) of an answer into account, evaluates the probability of correctness of each possible answer related to a sample of queries, and ranks them according to probability, where the inverted order of the query answer is the multiplicative inverse of the order of the first correct answer: 1 for first place, 1⁄2 for second place, and so on. Thus, the mean reciprocal order is the mean of the reciprocal orders of results of a sample of Q queries.

\begin{equation}\label{key}
MRR =\frac{1}{\vert{Q}\vert} \sum _{x=1} ^{\vert{Q}\vert} \frac{1}{rank_{i}}
\end{equation}

where \(rank_{i}\) is the rank position of the first relevant document related to the \(i^{th}\) query, while the reciprocal value of the mean reciprocal rank corresponds to the harmonic mean of the ranks.

§.§ Advanced Untrained Automatic Evaluation Scores (A-UAES)

The next category of UAES is advanced scores. Among the most widely used context-free error scores are BLEU, NIST, ROUGE, and METEOR discussed in the following. All of these scores utilize precision, recall, and F1 score in some form.

§.§.§ Bilingual Evaluation Understudy (BLEU)

BLEU compares the n-grams of the answer with the n-grams of the reference by counting the number of matches. These matches are position-independent. Obtaining the BLEUE score is a three steps process.

First, the logarithmic geometric mean of the modified n-gram precision, $P_n$, is calculated using n-grams up to length $N$ and positive weights $w_n =1/N$ that summing to one

\begin{eqnarray}
\log (GM) =  \Big( \sum_{n=1}^N \frac{1}{N} \log P_n \Big) = \log \Big( \prod_{n=1}^N  \log P_n \Big)^{\frac{1}{N}}
\end{eqnarray}

where $\Big( \prod_{n=1}^N  \log P_n \Big)^{\frac{1}{N}} = \prod_{n=1}^N  \log (P_n)^{w_n} $ is the geometric mean of the modified n-gram precision. Here the n-gram precision, $P_n$, is defined by

\begin{equation}
P_{n}=\frac{\sum _{c \in C} \sum _{n-gram \in c} Count_{clip}( n-gram)}
{\sum_{c^{'} \in C} \sum _{n-gram ^ {'} \in c^{'}} Count( n-gram^{'})} \label{mod.precision}
\end{equation}

where c is the generated response (i.e., answer) that contains n-gram of text and appear in C, C is  set of the generated output (i.e., responses),  \(Count_{clip}(n-gram) =max(n-gram  \ \exists \ A) \subseteq R\), is the maximum number of times the given n-gram of A appears in any corresponding R references (i.e., gold answer), and  \(Count(n-gram)\)  is the total number of words in  R  and  \(\forall \ n-gram \in c^{'} \).

Second, a brevity penalty is calculated by

\begin{equation}
BP  =\left\{
\begin{array}{ll}
1, & \text{if } c > r \\
e^{(1-\frac{r}{c})}, & otherwise
\end{array}
\right.
\end{equation}

where $c$ is the length of the predicted answer and $r$ is the effective reference answer length.

Finally, the BLEU score is calculated by

\begin{eqnarray}
BLEU = BP \cdot GM
\label{eq:bleu}
\end{eqnarray}

As default parameters the original BLUE [Papineni et al., 2002] used $N = 4$ and uniform weights $w_n = 1/N$.

In order to calculate the precision, BLEU starts counting up to the maximum number of times a word occurs in any single reference, it clips the total count of each candidate word, then, the modified n-gram Precision is equal to the clipped count divided by the total number of words in the candidate response.

Suppose we have two reference answers: (R1) "The dog sat on the mat", and (R2): "There is a dog on the mat". The predicted answer A is "the the the the the the the".

In this case, all words of A appear in R1 and R2, so the (ordinary) precision is $\frac {c}{c^{'}}$, where c is the number of words from A found in R1 or R2, and \(c^{'}\) is the total number of words in the generated answer A. As a result the (ordinary) precision of Example <ref> is $7/7=1$ for R1 and $7/7=1$ for R2.

However, BLEU makes slight changes to the ordinary precision, as it takes into consideration the maximum total count of \(Count_{clip}(\text{\it n-gram})\) in any candidate references. Specifically, in Example <ref>, the word 'the' has a max count of $2$ as it appears twice in R1, hence, the clipped unigram count is $2$, and the total number of counts in R1 is $7$, thus, the modified n-gram precision according to Eqn. <ref> is $2/7$. For R2 a similar calculation gives $1/7$.

Suppose R  is "the fox" and A is "the the fox".

Here, if the n-gram length  in example <ref> is $1$ (i.e., unigram), then the precision score will be ($1+1+1/3 = 1$), and if the n-gram  length is $2$ (e.g., bigram), then the precision score will be ($0+1/2 = 1/2$).
Since the precision score depends only on the length on A and not of R, the evaluation system in this case can exploit the score and acquire high scores by obtaining only a few matching of n-gram with R. In other words, the score of evaluation can be high even if A is not the perfect match with any R. For this, the BLEU tries to prevent the short n-gram length of A  from receiving too high scores, by using the geometric mean to combine the n-grams scores and multiply it by a brevity penalty as shown in equation <ref>.

§.§.§ National Institute of Standards and Technology (NIST)

NIST [Doddington, 2002] is a modified version of BLEU originally proposed for evaluating machine translation. Unlike BLEU, which gives equal weight to each n-gram precision, NIST weighs matched n-grams differently based on an information gain to show how informative a particular n-gram is:

\begin{equation}\label{key}
\text{info}(w_{1},\dots, w_{n})= \log_{2} \frac{  \text{\it \# occurrences of } w_{1},\dots, w_{n-1}} {\text{\it \# occurrences of } w_{1},\dots, w_{n}}
\end{equation}

The evaluation score could be improved by assigning more weight to the rarely matched n-gram and lower weight to the common n-grams. For example, the bigram receives a lower weight than the rare n-gram "the brevity penalty". NIST uses an alternative brevity penalty as follows:

\begin{equation}\label{key}
BLEU-N= \exp({\sum _{n=1}^{N} weight_{n} \log(Precision_{n})})  \cdot \exp(min(1-\frac{\vert r \vert}{\vert p \vert},0))
\end{equation}

The final  NIST score is given by:

\begin{multline}\label{key}
NIST= \sum_{n=1}^{N} (\frac{ \sum _{\text{\it all matched n-gram}} {\text{\it \text{info}(n-gram)}}} { \sum _{ n-gram \in  A}}) \\
\cdot \exp(\beta \log^{2} [min(\frac{\vert p \vert}{\vert r^{'} \vert},1)])
\end{multline}

Here, \(r^{'}\) is the average number of n-gram in  R, that averaged over all references, p is the number of n-gram in A being scored, and \(\beta \) is the chosen value to make BP factor =0.5, when the number of n-gram in A  is \(2/3^{rd}\) the average number of n-gram in R.

§.§.§ Recall-Oriented Understudy for Gisting Evaluation  (ROUGE)

ROUGE [Lin, 2004] is another modified version of BLEU that is based on recall instead of precision-based.

There are four different versions of the ROUGE measure (ROUGE-N, ROUGE-L, ROUGE-W, and ROUGE-S) which are meant to automatically determine the quality of a response $A$ against the references $R$ in the abstractive summarization evaluation task. To evaluate the quality of a summarized text, those measures try to find how many n-grams in the referenced text (R) appear in the generated response (A).

ROUGE-N: The ROUGE-N score is an n-gram recall-based score that counts the n-gram matches between A and R by:

\begin{equation}\label{eq:rouge-n}
\text{ROUGE-N} = \frac{\sum _{S \in R} \sum _{gram_n \in S} Count_{match}(gram_n)}  {\sum_{S^{'} \in R} \sum _{gram_n^{'} \in S^{'}} Count( gram_n)}
\end{equation}

where S is the reference (i.e., ground truth)  which contains n-gram of text that appear in R, R is the set of the given references,  \( Count_{match}(gram_n)\) is  the maximum number of times the n-grams in R appear in any generated output A (i.e., response), \(S^{'}\) is the total number of words in the reference R and $n$ is the length of the n-grams. That means with ROUGE-N, the $N$  corresponds to the maximal n-gram length between the predicted answer and the given reference.

Returning to Example <ref>, we see that the word "the" is co-occurring twice in A and R1 and once between A and R2. Thus, the ROUGE-N score according to Equation <ref> can be calculated as the ratio of the number of unigrams in A found in R, over the total number of unigrams in R. This gives the ROUGE-1 scores for R1 and R2 of $2/6$ and $1/7$ respectively.

Let's look at another example and calculate this time ROUGE-2 considering bigrams (i.e., n-gram=2).

Suppose that the given (R) is "The dog sat on the mat",  and the predicted response  A  was 'the dog and the cat'.

In this example, we see that there is only one bigram 'the dog' that overlaps between A and R, and the total number of bigrams in R is $5$. The ROUGE-2 score can be calculated as the total number of bigrams in A that appear also in R, divided by the total number of bigrams in R. Thus, the ROUGE-2 scores, in this case, are $1/5$, whereas recall is $1/4$ and the F1-score is $0.22$ respectively.

ROUGE-N is used only to calculate the error score over a single reference. However, when there are multiple references available then the ROUGE-N scores for each pair between A and every reference in reference set R is calculated. Finally, the maximum score is taken as the final score as follows:

\begin{equation}\label{eq:rouge-n}
\text{ROUGE-N}_{multi} = \max_i \text{ROUGE-N}(r_i, {A})
\end{equation}

Here, $r_i$ is the reference set, and A is the predicted response (i.e., candidate summary).

ROUGE-L: Is another version of ROUGE that uses the longest common subsequence (LCS) between A and R, where the matched words are not necessarily consecutive and the n-gram length is not required to be predefined. ROUGE-L can be calculated via two methods, named sentence-level LCS and summary-level LCS, to evaluate the generated response (i.e., summary). In the following, we discuss both approaches.

Sentence-level LCS: This method treats the summary sentence as a sequence of words, where the similarity between R of length m and A of length n could be increased; if the matched LCS is found to be longer. The ROUGE-L score can be computed as follows:

\begin{equation}\label{eq:RougeRecall}
R_{lcs}= \frac{LCS(A,R)}{m}
\end{equation}

\begin{equation}\label{eq:RougePrecision}
P_{lcs}= \frac{LCS(A,R)}{n}
\end{equation}

\begin{equation}\label{eq:RougeF1}
F_{lcs}= \frac{(1+\beta^2)R_{lcs}P_{lcs}}{R_{lcs}+\beta^2 P_{lcs}}
\end{equation}

Here, LCS(A,R) is the length of longest common subsequence of predicted response A and given reference R, where $\beta$ is a non-negative real, so when $\beta = 1$, then $F_{lcs}$ is the harmonic mean of $R_{lcs}$ and $P_{lcs}$, and if $\beta < 1$, then ROUGE-L is weighted toward precision, otherwise, it is weighted toward recall. Thus, based on Equations <ref>, <ref> and <ref> the ROUGE-L scores, recall, F1-score for Example <ref> are $3/5$, $3/6$ and $0.55$ respectively, with $\beta = 1$.

Unlike bigram ROUGE-N which fails with capturing the different meanings among two different responses and the given reference, ROUGE-L can capture a  sentence-level structure in a natural way. However,  since LCS only counts the main in-sequence words, the other alternative LCS and shorter sequences can not be distinguished in the final score [Lin, 2004].

Summary-level LCS: This measure can be thought of as a union of LCS matches between the reference $r_i$  and every candidate response A. The summary-level LCS score is calculated by

\begin{equation}\label{eq:RougeRecall-s}
R_{lcs}= \frac { \sum _{i=1}^{u}LCS_{\union}(A,R)}{m}
\end{equation}

\begin{equation}\label{eq:RougePrecision-s}
P_{lcs}= \frac { \sum _{i=1}^{u}LCS_{\union}(A,R)}{n}
\end{equation}

\begin{equation}\label{eq:RougeF1-s}
F_{lcs}= \frac{(1+\beta^2)R_{lcs}P_{lcs}}{R_{lcs}+\beta^2 P_{lcs}}
\end{equation}

Suppose R is given by "The quick brown fox jumps",  and the predicted response A1 is "The quick over the lazy"  and  A2 is "The brown lazy dog jumps".

In this example,  the LCS of $R$ and $A1$ is "The quick", and the LCS of $R$ and $A2$ is "The brown jumps". The union LCS of $R$, $A1$, and of $R$, $A2$ is "The quick brown jumps" and the $LCS_{\union}(R,A) = 4/5$.

ROUGE-W: is the weighted longest common subsequence that considers the different spatial relations of LCS and their embeddings sequences.

Suppose that  the given R: 'The quick brown fox jumps over dog',  and the predicted response A1: 'The quick brown fox lazy so quickly'  and  A2: 'The lazy quick quickly brown dog fox'

Here, $A1$ and $A2$ have the same ROUGE-L score, However, $A1$ is more adequate in terms of meaning than $A2$, because $A1$ has consecutive matches.

To improve the basic LCS method and to give consecutive matches more awarded scores than non-consecutive matches, ROUGE-W introduces a weighting function that assigns different credit to consecutive in-sequence matches along with two-dimensional dynamic programming table $c(i,j)$ and $w(i,j)$, where $c$ is the dynamic programming table to store the weighted LCS (WLCS) score ending at words $a_i$  of $A$ and $r_j$ of $R$, and $w(i,j)$ is a table that store the length of consecutive matches ended at $c$ table position $i$ and $j$ [Lin, 2004]. The weighting function must have the property that $f(A+R)> f(A)+ f(R)$ for any positive integers A and R.

ROUGE-S: is a skip-bigram concurrence score that allows to add a degree of indulgence to the n-gram matching that is performed with ROUGE-N and ROUGE-L. This allows any pair of consecutive words from $R$ that appear in $A$  to be considered even when the words are separated by any arbitrary gaps (i.e., one-or-more other words). The skip-bigram-based F-measure can be computed as follows:

\begin{equation}\label{eq:RougeRecall-sk}
R_{skip2}= \frac { SKIP2(A,R)}{C(m,2)}
\end{equation}

\begin{equation}\label{eq:RougePrecision-sk}
P_{skip2}= \frac { SKIP2(A,R)}{C(n,2)}
\end{equation}

\begin{equation}\label{eq:RougeF1-sk}
F_{skip2}= \frac{(1+\beta^2)R_{skip2}P_{skip2}}{R_{skip2}+\beta^2 P_{skip2}}
\end{equation}

Here, the $SKIP2(A,R)$ is the number of skip-bigram matches between $R$ and $A$,  $m$ is the length of $A$, $n$ is the length of $R$, $\beta\ $ is a parameter that control the relative importance of  $P_{skip2}$ and $R_{skip2}$, and C is the combination function.

Suppose R is: "the fox sat on the mat",  and the predicted response A is: "the white fox  and the dog"

Here, the bigram "the fox" in $R$ would not match any bigram in $A$ if ROUGE-2 would be used since ROUGE-2 will try to find only exact consecutive bigram matches between $A$ and $R$. However, this is not the case with ROUGE-S, which will try to find any matched bigrams between $A$ and $R$ even when the words of the bigrams are separated by any arbitrary gap. In order to calculate the ROUGE-S score, first, we need to count the skip-bigram matches, SKIP2(A,R), within the maximum skip distance, so. In this example, R has the following skip-bigrams: ("the-fox", "the-jumps", "the-over", "the-dog", "fox-jumps", "fox-over", "fox-dog", "jumps-over", "jumps-dog", "over-dog"), and A has ("the-white", "the-fox", "the-and", "the-black", "the-dog", "white-fox", "white-and", "white-black", "white-dog", "fox-and", "fox-black", "fox-dog", "and-black", "and-dog", "black-dog"). Furthermore, there are three skip-bigram matches between R and A ("the-fox", "the-dog", "fox-dog"). Then by applying Equations <ref>, <ref> and <ref> one obtains the scores of $precision_{skip2}$, $recall{skip2}$ and $F{skip2}$ as $3/15=0.2$, $3/10=0.3$, and $(1+1) \times 0.3\times 0.2 / 0.3+1 \times 0.2)= 0.24$ respectively, with $\beta\ =1$.

§.§.§ Metric for Evaluation of Translation with Explicit ORdering (METEOR)

Unlike BLEU, METEOR [Banerjee and Lavie, 2005] is based on the harmonic mean with a recall weighted higher than precision. METEOR is explicitly designed to work for sentence level rather than corpora level. METEOR  also has a set of variants (e.g., METEOR-NEXT, METEOR Universal, METEOR++, and METEOR++2) that came up with many features, such as: considering the word matching synonyms,  allowing relaxed matches with word stems, along with the standard exact word matching, applying importance weighting to different matching types,  allowing to integrate learned external paraphrasing resources (i.e., WordNet synonyms). METEOR correlates much better with human judgment, compared to BLEU, however, on contrary to BLEU which supports different lengths of n-grams, METEOR only considers unigram matches.

In order to calculate the METEOR score, one needs first to form an alignment between A and R. An alignment is a set of mappings between the unigrams string, where each unigram in A must map 0 or 1 unigram in R. Then, the METEOR score computes the F-score using this relaxed matching strategy as follows:

First, precision and recall are calculated by

\begin{eqnarray}
\text{Precision} = Pr = \frac{w} {\vert{w} \vert}
\label{eq:precision} \\
\text{Recall} = Re = \frac{w} {\vert{w}^{'} \vert}
\label{eq:recall}
\end{eqnarray}

where \(w\) is the number of mapped unigrams in A that are also found in R, and \(\vert{w}\vert\) is the total number of unigrams in A and \(\vert{w}^{'}\vert\) is the total number of unigrams in R.

Second, the harmonic mean, $F_{mean}$, which places most of the weight on recall, is calculated by

\begin{equation}
F_{mean}= \frac{ 10\times PrRe} {Re+9Pr}
\label{eq:fmean}
\end{equation}

However, the longest contiguous unigram matches are rewarded by METEOR using a function named fragmentation penalty. Thus,  in order to find the longest sequence of adjacent unigrams that appear both in A and R, the unigrams need to be grouped into the fewest possible chunks of longest sequences with the fewest mappings. The fragmentation penalty is calculated as follows:

\begin{equation}
Penalty= 0.5 (\frac{ c} {w_{n}}) ^{3}
\label{eq:penalty}
\end{equation}

where c is the number of chunks and \({w_{n}}\) is the number of mapped unigrams. Here, the penalty increases as the number of chunks increases and vice versa.

Finally, the METEOR score is calculated as follows:

\begin{equation}
\text {\it METEOR: } score= F_{mean} (1-Penalty)
\label{eq:Meteor}
\end{equation}

This can reduce the $F_{mean}$ score by a maximum of $50\%$ when there are no bigrams or longer matches found between A and R  [Banerjee and Lavie, 2005].

The procedure of calculating a METEOR score starts with finding the number of fragmentations with the longest sequence of adjacent unigrams that appear both in A and  R. Here, the number of possible fragmentations can be found as the number of possible chunks divided by the total number of unigram matches. Whereby, the longer unigram matches lead to a fewer number of chunks, and when there are no bigrams or longer matches, then the number of chunks is equal to the number of unigram matches, whereas the penalty is calculated according to Equation <ref>.

Let's consider the following examples to show how the METEOR score can be obtained.

Suppose R is given by "the dog sat on the mat" and A is "on the mat sat the dog".

Suppose R is given by "the dog sat on the mat" and A is "the dog was sat on the mat".

Suppose R is given by "the dog sat on the mat" and A is "the dog sat on the mat".

For Example <ref>, we have $6$ chunks and $6$ unigram matches. Thus, the penalty is \(0.5 \times \frac{6}{6}=0.5\). The scores of precision, recall and F-mean are $1$,$1$, $1$ according  to Equations <ref>,  <ref> and <ref> respectively. Then, the final METEOR score can be calculated based on Equation <ref> as \(1\times(1-0.5)=0.5\).

Following the same procedure, for Example <ref> we have $2$ chunks and $6$ matches which gives a METEOR score of $0.96$ and for Example <ref> we have $1$ chunk and $6$ matches with a final METEOR score of $0.99$.

§.§ Machine-trained Evaluation Scores (MTES)

The measures in the category MTES are the most recent type of error scores. All of these measures have parameters that need to be learned from training data. This makes MTES more flexible than UAES. In the following, we discuss some of the most widely used scores in this category, i.e., ADEM [Lowe et al., 2017], RUBER [Tao et al., 2018], RUSE [Shimanaka et al., 2018], BLEURT [Sellam et al., 2020], BertScore [Zhang et al., 2019], MaUde [Sinha et al., 2020] and learning-based composite metrics [Sharif et al., 2018].

§.§.§ Automatic Dialogue Evaluation Model (ADEM)

Although many automatic evaluation metrics have been proposed to help reduce or eliminate the efforts of human evaluation in machine translation, the automatic evaluation for dialogue systems remains a challenge as traditional word-overlap metrics such as BLEU or ROUGE are considered as biased and do not correlate well with human judgment. Due to the fact that such metrics only detect the same words from the response and reference they are incapable of dealing with the semantic similarity of words. This problem might not be essential in evaluating machine translation as the range of words that could be used in the reference translation is rather limited, however, in a dialogue system the appropriateness of the spawned responses depends on the context and thus the influence can be more severe.

In order to counter those drawbacks in the automatic evaluation of dialogue responses, learning-based scores were introduced which are models that can be trained through supervised, unsupervised, or semi-supervised learning to evaluate the score of a response.

An example of such a parametric score is ADEM [Lowe et al., 2017], which aims to learn distributed representations of the context, response and reference using RNN encoders through supervised learning.
The goal of ADEM is to calculate a score given a context $c$, the reference $r$ and the model response $\hat{r}$, according to the following function:

\begin{equation}
\begin{aligned}
\text{ADEM: } score(c,\hat{r},r; M, N) = (c^{T}M\hat{r}+r^{T}N\hat{r} - \alpha)/\beta
\end{aligned}\label{eqn.ademscore}
\end{equation}

Overall, ADEM consists of two layers of RNNs. The first layer takes the input as a sequence of words and then produces a vector output at the end of each sentence (utterance). The second layer of the RNN takes each output utterance representation and produces a higher level of context representation from the last hidden state.

The model is pretrained with VHRED [Serban et al., 2017] which means the parameters of the RNN are frozen during the training, and the only trainable parameters are $M$,$N$ in Equation <ref>. These two matrices project the model response $\hat{r}$ into the space of context and reference responses.
By introducing $M$,$N$ into the model, the model will be able to give high scores for responses that have similar vector representations with the context and the reference responses.

The training loss function $L$ of the ADEM model can be formulated as the squared error between the prediction ADEM score in Equation <ref> and a human score plus an additional L2-regularization term:

\begin{equation}
\begin{aligned}
L(M, N) =  \sum_{i=1:N}[score(c_i,\hat{r_i},r_i; M, N) - human\_score_i]^2 + \gamma\|\theta\|_2
\end{aligned}
\end{equation}

Here $\gamma\|\theta\|_2$ is the l2-regularization term where $\gamma$ is a scalar constant and $\theta$ is the set of parameters $\theta$ = {M,N}.

A successful training will obtain the parameters of the model, $M$ and $N$, which minimize the loss $L$. One example of an ADEM score that correlates highly with a human score can be seen in the table <ref>.

Examples for the comparison of scores for human score (HS), BLEU-2 (B2), ROUGE (RG) and ADEM (AM) (results from [Lowe et al., 2017]). All three scores are normalized to the same scale as human score.

Context     Model responses     Reference responses     HS     B2     RG     AM

i’d recommend {url} - or build buy an htpc and put {url} on it. → you’re the some nd person this week that’s recommended roku to me.
because it's brilliant
an htpc with xmbc is what i run . but i’ve decked out my setup. i’ve got {number} tb of data on my home server
5     1     1     4.726

imma be an auntie this weekend. I guess I have to go albany. here we go → u supposed to been here → i come off nd on. → never tell me smh
haha, anyway, how're you?
lol you some timing
5     1     1     4.201

my son thinks she is plain. and the girl that plays her sister.seekhelp4him? → send him this. he’ll thank you. {url}
i will do
you are too kind for words
5     1     1     5.0

§.§.§ Referenced metric and Unreferenced metric Blended Evaluation Routine (RUBER)

RUBER [Tao et al., 2018] is a learning-based hybrid score originally developed for the automatic evaluation of open-domain dialog systems. RUBER consists of a referenced part, $S_R$, and a unreferenced part, $S_{UR}$, hence, the term hybrid score.

For the referenced part, $S_R$, the cosine similarity is evaluated between the generated representation of the response $\hat{r}$ and the representation of the ground truth response $r$ forming a score evaluating the similarity between the two responses. Both representations are obtained through pooling the maximum and minimal value from the word embeddings in each dimension given by:

\begin{equation}
\begin{aligned}
v_{max}[i] &=& maxpooling\{w_{1}[i],w_{2}[i],...,w_{n}[i]\} \\
v_{min}[i] &=& minpooling\{w_{1}[i],w_{2}[i],...,w_{n}[i]\}
\end{aligned}
\end{equation}

where $w_{1}[i],w_{2}[i],...,w_{n}$ are the words from the response, $i\in R^{d}$, $d$ is the dimension of the word embeddings. Then $v_{max}$ and $v_{min}$ are concatenated together by $v = v_{max} v_{min}$ to form the representation of reply.

The same procedure is applied to $\hat{r}$ and ground-truth reply $r$. Finally, the cosine distance is calculated to obtain the score which gives:

For the unreferenced score, $S_{UR}$, Bi-GRU RNN is utilized to measure the relatedness of the generated reply $r$ and its query $q$, the aim of this structure is to predict the quality of the generated reply given its query context. In order to do this the query and the reply are mapped to the word-level embeddings and then passed through two Bi-GRU RNNs individually where the last hidden states from forward and backward passes are concatenated to form the vector representations of $r$ and $q$. Finally $r$ and  $q$ form a quadratic feature, i.e., $q^TMr$, where $M$ is a parameter matrix are concatenated together and a multi-layer perceptron is applied to the final concatenated feature to predict a scalar score $S_UR$.

The objective of the model is to minimize the difference between the true pair $(q,r)$ and a randomly chosen false pair $(q,r^-)$ from the training set by at least a margin $\Delta$:

\begin{equation}
\begin{aligned}
L = max\{0,\Delta-S_{UR}(q,r)+S_{UR}(q,r^-)\}
\end{aligned}
\end{equation}

The RUBER score can be used individually by either referenced or unreferenced part, however, the combined version of both parts by either minimal, maximum, geometric averaging, or arithmetic averaging provide the best RUBER score which is highly correlated with human annotation[Tao et al., 2018], a simple illustration of RUBER score can be seen in table<ref>.

Examples for the comparison of scores for human score (HS), BLEU-2 (B2), ROUGE (RG) and RUBER unreferenced ($S_U$), RUBER referenced ($S_{UR}$) and RUBER Blended (RB) using the arithmetic mean (results are from [Tao et al., 2018]). All four scores are normalized to the same scale as the human score (0-2).

Query     True reply     Candidate reply     HS     B2     RG     $S_U$     $S_{UR}$     RB

2*It seems very near
2*Where are you
I also think it's near
1.78     0.00     0.00     1.87     1.53     1.71

Where are you from
1.78     0.00     0.77     1.15     1.78     1.47

§.§.§ Metric for automatic Unreferenced dialogue evaluation (MaUdE)

While the learning-based referenced metric ADEM shows good results over traditional word-overlap-based metrics, its nature of supervised learning requires human efforts for generating the score. This prevents ADEM from being applied to the field of online evaluation of dialogue systems where the generation of human reference scores is practically impossible. Furthermore, these types of referenced metrics have been shown to behave poorly on out-of-distribution data. In contrast, unreferenced metrics can easily overcome these challenges meanwhile keeping competitive performance against referenced metrics.

MaUde [Sinha et al., 2020] is a fully unreferenced metric developed for evaluating dialogue systems. It utilizes a pre-tained BERT model and applies a Noise Contrastive Estimation Technique [Gutmann and Hyvärinen, 2010] to generate negative samples allowing completely unsupervised training.
MaUdE provides a score for a given context c and response r by combining the learned representation vectors $f_e^{\theta_{1}}(c)$ and $f_e^{\theta_{2}}(r)$ using the combine function, $f_{comb}$. Then these are passed through a final classifier $f_c$ to produce a score $\{0,1\}$:

\begin{equation}
\begin{aligned}
\text{MaUdE: } score(c,r) =     \sigma(f_c(f_{comb}(f_e^{\theta_{1}}(c),f_e^{\theta_{2}}(r)))
\end{aligned}
\end{equation}

where $f_e^{\theta_{1}}$ and  $f_e^{\theta_{2}}$ are the encoders to encoder the context and the responses respectively, and $c$ is the context that may contain many sentences $u_i$ and $c = \{u_1,u_2,u_3...u_n\}$. $f_e^{\theta_{1}}$ consist of a BERT model $f_e^{B}$ and a Bidirectional LSTM $f_e^{R}$. For obtaining representations of the context, each sentence $u_i$ passes through $f_e^{B}$ and then the encoded state $h_{u_i}$ is  passed through $f_e^{R}$. Finally, a max-pooling is applied to each hidden state $\hat{h_{u_i}}$ from $f_e^{R}$ and a weight matrix $W$ is applied to map the pooled representation to the response vector space for forming the final representation of context denoted by $h_{c_i}$. $f_e^{\theta_{2}}(r)$ was learned through the same procedure without the need of pooling operation to form a final representation of response $h_{r_i}$.

Finally, the context representation $h_{c_i}$ and the response representation $h_{r_i}$ are combined in the following way [Conneau et al., 2017]

\begin{equation}
\begin{aligned}
f_{comb}(h_{c_i},h_{r_i}) =  concat([h_{c_i},h_{r_i},h_{c_i}*h_{r_i},h_{c_i} - h_{r_i}])
\end{aligned}
\end{equation}

The model is trained to distinguish between a correct response given by $score(c,r) \rightarrow 1$ and a false response corresponding to $score(c,r_n) \rightarrow 0$.

A comparison of original MaUdE with baselines models trained with the same Noise Contrastive Estimation procedure, e.g., LSTM-based model unreferenced RUBER, InferSent and also BERT-based model DistilBERT-NLI *unclear InferSent is no score, or is it?*, showed that MaUdE obtained promising results, e.g., for the  PersonaChat dataset which is a public validation set. In addition, it was shown that MaUdE has a high correlation with human judgments on the PersonaChat dataset. Table <ref> demonstrates an evaluation example of a chat between a human and robot using several different models for evaluation.

Please remove this line of spacing argument if you find problems in other tables

Examples for a comparison of scores generated from unreferenced RUBER (R) based, InferSent (I) based, BERT-NLI (B) based baseline models against the original MaUde (M) model (results from [Sellam et al., 2020]). The conversation was generated between a human and a strong dialogue model (model that generated dialogues that have high human scores) *what does this mean*.

Human     Model reply     RUBER     InferSent     BERT-NLI     MaUde

How are you today
Hello how are you doing today
0.943     0.908     0.998     1.0

Horrible, I'm about to file for divorce
How long have you been married
0.339     0.300     0.993      0.997

10 years, but she spends all my money!
Wow that's a lot of money
0.464     0.593     0.981     0.998

Yep. What do you do for a living
I work as a scientist
0.432     0.591     0.956     0.998

Do you have any hobbies
I grow my farm
0.247     0.284     0.980     0.999

So I guess you live in the country
Yes I live in the country
0.542     0.733     0.957     0.995

§.§.§ Regressor Using Sentence Embeddings (RUSE)

RUSE [Shimanaka et al., 2018] is a learning-based score originally proposed for automatic evaluation for machine translation.
RUSE formulates the training procedure as a regression problem that predicts the quality of a translation based on the machine translation hypothesis and the reference translation using human judgment data, therefore RUSE is a supervised model, in addition, RUSE also leverages the advantages of pre-trained universal sentence embeddings from InferSent [Conneau et al., 2017], Quick-Thought [Logeswaran and Lee, 2018] and Universal Sentence Encoder [Cer et al., 2018] by using the sentence embeddings produced by these models as the inputs, this critical step helps the model to better understand the semantic differences between sentences.

RUSE has two variants, one uses MLP (Multilayer Perceptron) as the regressor and the other one uses SVR (Support Vector Regression), though the author suggests that RUSE with MLP outperforms SVR version in many cases.

Once the sentence representations for MT hypothesis $t$ and the reference translation $r$ are generated using 3 universal sentence embeddings, they are concatenated to form a $d$ dimension vector $\hat{t}$ and $\hat{r}$, the final input feature to the regressor $f_r$ has $4d$ dimension and result from 3 types of matching methods:

\begin{eqnarray}
\text{RUSE: } score = f_r(concat\{\hat{t},\hat{r}\},\hat{t}  *\hat{r},\|\hat{t} - \hat{r}\|)
\end{eqnarray}

where $\hat{t}*\hat{r}$ is the element-wise product and $\|\hat{t} - \hat{r}\|$ is the absolute element-wise difference.
The final regressor $f_r$ computes the score then the difference between the human judgment score and the produced score is measured to further adjust the parameters of the regressor during training.

The best setup of RUSE achieved the state-of-the-art result for the WMT16 and WMT17 datasets in both segment- and system-level metrics tasks[Tao et al., 2018] by 2018.

§.§.§ BLEURT

This is a learning-based text generation score based on BERT. However, instead of using the naive BERT with a single pre-training procedure[Devlin et al., 2018], BLEURT [Sellam et al., 2020] introduces another pre-training step on top of the basic pre-training to improve the generalization capabilities of the final score compared to most of the automatic scores even when the training data is very limited.

The training of BLEURT [Sellam et al., 2020] consists of 3 main steps: (I) Normal pre-training of BERT, (II) pre-training on large-scale synthetic data, and (III) fine-tuning on task-specific data. The key to the model is the second step which is the pre-training using large-scale synthetic data collected from Wikipedia. From this, a rich collection of synthetic reference-candidate pairs is generated by randomly perturbing the original sentences from Wikipedia. The perturbing technique includes mask-filling with BERT, back-translation, and dropping words. Then the original sentence $s$ and the generated pairs $\hat{s}$ are fed into BERT for 6 tasks which include regression tasks such as predicting BLEU, ROUGE, BERTscore, and the back-translation likelihood, and classification tasks such as textual entailment and back-translation flag prediction. It has been shown that the robustness of the model increases dramatically after the transfer learning phase on large-scale synthetic data.

The last step is to fine-tune a specific task and the goal of the model is to simply predict the score of a given sentence and the reference sentence. After all training steps, the model can be used to perform a human-like judgment score even when the dataset for fine-tuning is small and out-of-distribution[Sellam et al., 2020].

§.§.§ BERTScore

BERTScore is an unsupervised learning-based metric proposed for automatic machine translation evaluation, it aims to calculate the semantic distance between the reference and the candidate sentence, by taking advantage of the unsupervised training of the BERT model, BERTScore offers better generalization to varies domains and is capable of understanding the semantic meaning of sentences especially capturing the distant dependencies and ordering information of sentences.

BERTScore computes the cosine distance between each token from reference sentence to each token candidate sentence using word embeddings produced by pre-trained BERT, the cosine similarity for a given reference token $x_i$ where $x = [x_1,x_2,...,x_n]$ and a candidate token $\hat{x_j}$ where $\hat{x} = [\hat{x_1},\hat{x_2},...,\hat{x_k}]$ of length $k$ is $cos = \frac{x_{i}^{T}\hat{x_{j}}}{||x_{i}||||\hat{x_{j}}||}$, the pre-normalized vectors are used in the calculation which leads to simply a inner product of $x_{i}^{T}\hat{x_{j}}$. The definition of BERTScore precision, BERTScore recall, and BERTScore F1 are:

\begin{equation}
\begin{aligned}
\label{eq:BERTScore}
P_{BERT} = \frac{1}{\hat{x}}\displaystyle\sum_{\hat{x_{j}}\in \hat{x},x_{i}\in x}\max x_{i}^{T}\hat{x_{j}} \\
R_{BERT} = \frac{1}{x}\displaystyle\sum_{x_{i}\in x,\hat{x_{j}}\in \hat{x}}\max x_{i}^{T}\hat{x_{j}} \\
F_{BERT} = 2\times\frac{P_{BERT}\times R_{BERT}}{P_{BERT}+R_{BERT}}
\end{aligned}
\end{equation}

As several works discovered that rare words are more indicative for sentence similarity measure than common words[Vedantam et al., 2015], BERTScore involves Inverse Document Frequency (IDF) as a weight in the calculation, which further modifies the formula from <ref> for example $R_{BERT}$ to:

\begin{equation}
R_{BERT} = \frac{\sum_{x_{i}\in x}idf(x_i)\max_{\hat{x_{j}}\in\hat{x}}x_{i}^{T}\hat{x_{j}}}{\sum_{x_{i}\in x}idf(x_{i})}
\end{equation}

Since pre-normalized vectors are used in the calculation, $P_{BERT}$ and $R_{BERT}$ essentially have the range of the same cosine similarity of -1 and 1, in order to make the score more interpretable, $P_{BERT}$ and $R_{BERT}$ are rescaled to the range from 0 to 1.

Table <ref> shows some toy examples of 2 traditional word-overlap machine translation scores and 3 learning-based machine translation scores.

Examples for the comparison of scores mainly used for machine translation such as BLEU-2(B2), ROUGE-L(RO), RUSE with Infersent feature (RU), BLEURT (BL), and BERTScore-F1 (BE), all the sentence pairs are considered to have high semantic similarity by human annotators.

Reference ($x$) and candidate ($\hat{x}$)      B2     RO     RU     BL     BE

$x$: It is very cold today. $\hat{x}$: The weather is freezing today.
0.00     0.40     0.42     0.62     0.76

$x$: Wage gains have shown signs of picking up. $\hat{x}$: Increases of wages showed signs of a recovery.
0.19     0.38     0.44     0.71     0.68

$x$: What is your name? $\hat{x}$: What can I call you?
0.00     0.22     0.10     0.48     0.41

$x$: There are, indeed, multiple variables at play. $\hat{x}$: In fact, several variables play a role.
0.00     0.28     0.40     0.75     0.56

$x$: Currently the majority of staff are men. $\hat{x}$: At the moment the men predominate among the staff.
0.00     0.25     0.43     0.79     0.62

§.§.§ Learning-based Composite Metrics

Automatic evaluation of image captioning is another challenging field. A good quality of an evaluation depends on accurate measures of both adequacy and fluency of the generated caption corresponding to lexical and semantic characteristics of a caption. However, most of the proposed metrics only focus on dealing with one of these two aspects of a caption. Learning-based Composite Metrics are proposed for the automatic evaluation aiming to address this problem by using a neural network in combination with different metrics taking advantage of each metric to produce a score that can effectively capture both adequacy and fluency of a caption.

The training of the Composite Metrics is formulated as a classification problem that distinguishes between a machine-generated caption and a human-generated caption using an MLP as a classifier. For each image, 3 machine-generated captions are produced by Show and Tell [Vinyals et al., 2015], Show Attend and Tell [Xu et al., 2015] and adaptive attention [Lu et al., 2017] are 3 well-known image captioning models respectively, and 5 human-generated captions will be used for each image.
Each generated human caption is paired with the other 4 human-generated captions, for example, machine translation 1 for image $i$ will be paired with all human-generated captions for $i$ excluding caption 1, while machine translation 2 for image $i$ will be paired with all the human-generated captions for $i$ excluding caption 2. Each pair is considered to be one sample and each pair receives scores from METEOR, CIDEr, WMD, and SPICE. These scores are then used as input feature vectors for the classifier. Then the classifier predicts which samples are human-generated while machine-generated pairs are the negative samples, and human-generated pairs are the positive examples.

In this paper [Sharif et al., 2018], it is stated that by combining different metrics and using them as input features to learn a classifier, the trained classifier can be further used to generate scores for automatic evaluation of image captions and this score is capable of capturing multiple aspects including adequacy and fluency. These results have been obtained by using the PASCAL-50s dataset.

§ CHALLENGES FOR EVALUATION SCORES

From our discussion of quantitative error scores in Section <ref>, we can see that there is an impressive number of different error measures for evaluating QA systems. Regarding the historic development of such scores, it is interesting to note that till about 2014 there seem only $10$ automatic error measures that have been in wider usage, including BLEU, NIST and ROUGE [Sai et al., 2022]. However, since then more than $50$ new scores have been introduced. An important contribution made by such new scores is that they add novel characteristics. Specifically, evaluation scores can have the following six properties:

* word-based, character-based, n-gram-based or
word embeddings-based