2.1 Referring expression generation (REG)

The Incremental algorithm (Dale and Reiter Reference Dale and Reiter1995) is the basis of a wide range of approaches to REG. The input to the algorithm is a target object r to be uniquely described within a context C containing a set of distractors. All objects are modelled as sets of properties represented as (attribute-value) pairs, as in (size-small). The goal of the algorithm is to produce a set L of properties of r, such that L distinguishes r from every distractor in C.

Attributes are considered for inclusion in L incrementally by following a domain-dependent list of preferred attributes P, and provided that they help disambiguate the target. When an attribute a is selected for inclusion in L, the corresponding distractors are removed from C. For instance, selecting a property (size-small) rules out all distractor objects whose size is not small. Thus, in the context in the previous Figure 1, given a preferred order as, e.g., P = ⟨type, size, colour⟩, the target r = d ₁ would be described as ‘the small cylinder’. Similarly, r = d ₂ would be described as ‘the large cylinder’ and r = d ₃ as ‘the box’.

The algorithm terminates when C becomes empty, or when all attributes in P have been attempted. In the former, L represents a uniquely identifying attribute set that may be realised as, e.g., a definite description as in ‘the small cone’. In the latter, L may be realised as, e.g., an indefinite description, as in ‘a cone’.

The order of attributes in P may greatly impact the outcome of the algorithm. For instance, had we considered the preference order P = ⟨colour, type, size⟩ in the above example, d ₁ would have been described as ‘the white cylinder’, d ₂ as ‘the blue (cylinder)’Footnote ¹ and d ₃ as ‘the white box’.

The use of discriminatory properties favours the generation of brief descriptions in accordance to the Gricean maxim of quantity (Grice Reference Grice, Cole and Morgan1975). For similar reasons, the Full Brevity algorithm (Dale Reference Dale1989) aims to produce minimally distinguishing descriptions by first attempting solutions conveying one single property, followed by possible alternatives conveying two properties, and so on. Examples of minimally distinguishing descriptions for the objects d ₁..d ₃ in the previous example are ‘the small (object)’, ‘the blue (object)’ and ‘the box’.

In addition to the Incremental algorithm, research in the field has produced a wide range of approaches to REG. These include, for instance, the generation of boolean referring expressions (van Deemter Reference van Deemter2002), the use of graphs to generate relational descriptions (Krahmer et al. Reference Krahmer, van Erk and Verleg2003), the use of lexical information to generate descriptions in open domains (Siddharthan and Copestake Reference Siddharthan and Copestake2004), and the generation of overspecified descriptions to facilitate search (Paraboni and van Deemter Reference Paraboni and van Deemter2013), among many others. In the series of REG shared tasks (Gatt and Belz Reference Gatt and Belz2007; Gatt, Belz and Kow Reference Gatt, Belz and Kow2008, Reference Gatt, Belz and Kow2009) a large number of algorithms have been proposed as well, including the 2007 best-performing IS-FBN algorithm (Bohnet Reference Bohnet2007) and the 2008 winner JU-PTBSGRE (Paladhi and Bandyopadhyay Reference Paladhi and Bandyopadhyay2008). For a comprehensive review of studies of this kind, we refer to Krahmer and van Deemter (Reference Krahmer and van Deemter2012).

2.2 Human variation in REG

Existing REG algorithms, including the Incremental and Full Brevity approaches described in the previous section, generally do not take speaker-related information into account. In other words, given a certain input (i.e., a context C and a target r) these algorithms always produce the same output description. A number of exceptions are discussed below.

In Bohnet (Reference Bohnet2008), extensions of the Incremental (Dale and Reiter Reference Dale and Reiter1995) and Full Brevity (Dale Reference Dale1989) algorithms are evaluated using the TUNA corpus of referring expressions (Gatt, van der Sluis and van Deemter Reference Gatt, van der Sluis and van Deemter2007). In the Incremental extension, human variation is accounted for by computing individual preference lists (the P parameter of the algorithm, cf. the previous section) from the subset of descriptions produced by each speaker. Attributes in each individual list are ordered by frequency. Results in Bohnet (Reference Bohnet2008) show that the use of individual preference lists outperforms the use of a single preference order computed from the entire training data. In the Full Brevity extensions, human variation is accounted for by selecting the description that is closest to the previous descriptions produced by the same speaker.

The work in Fabbrizio, Stent and Bangalore (Reference Fabbrizio, Stent and Bangalore2008) also makes use of the Full Brevity (Dale Reference Dale1989) and Incremental (Dale and Reiter Reference Dale and Reiter1995) algorithms to generate descriptions from the TUNA corpus. In the case of Full Brevity, human variation is accounted for by making use of attribute set frequencies and recency estimates for each speaker. In the case of the Incremental algorithm, human variation is implemented as in Bohnet (Reference Bohnet2008), that is, by computing individual preference lists for each speaker. In both cases, results show that the use of speaker-related information improves accuracy.

The work in Viethen and Dale (Reference Viethen and Dale2010) does not present a REG algorithm proper, but focuses instead on the use of decision-tree induction to predict content patterns (i.e., full attribute sets representing actual referring expressions) from visual scenes in the GRE3D3/7 corpora (Dale and Viethen Reference Dale and Viethen2009; Viethen and Dale Reference Viethen and Dale2011). Human variation is accounted for by including speaker identifiers in the model. Results from Viethen and Dale (Reference Viethen and Dale2010) show that the classifier that has access to speaker’s identifiers outperforms those that do not. This approach is furthered in Viethen (Reference Viethen2011) by modelling individual classifiers for each attribute under consideration (i.e., as opposed to using a single classifier to predict each attribute set, in Viethen and Dale (Reference Viethen and Dale2010)). Once again, human variation is limited to the use of speaker’s identifiers, and the classifiers that include speaker’s IDs outperform those that do not.

In the related task of REG in dialogues (i.e., taking the previous discourse into account), the work in Gupta and Stent (Reference Gupta and Stent2005) proposes a number of variations of the Incremental algorithm to generate descriptions from the Coconut (Eugenio et al. Reference Eugenio, Jordan, Thomason and Moore2000) and MapTask (Anderson et al. Reference Anderson, Bader, Bard, Boyle, Doherty, Garrod, Isard, Kowtko, McAllister, Miller, Sotillo, Thompson and Weinert1991) corpora. Two speaker-dependent strategies are considered. The first strategy uses a preference list ordered according to attribute frequencies observed in recent expressions produced by each speaker. In addition to that, the second strategy includes the attributes mentioned in the latest reference produced by each speaker when generating a new description regardless of its frequency or discriminatory power. The study shows that both strategies outperform a standard REG approach that does not take human variation into account.

In Viethen, Mitchell and Krahmer (Reference Viethen, Mitchell and Krahmer2013), an extension of the GRAPH algorithm (Krahmer et al. Reference Krahmer, van Erk and Verleg2003) called Longest First is presented. The algorithm attempts to find the longest (up to a certain limit) possible description for a given input, a strategy that favours the generation of overspecified descriptions that would not be normally obtainable by using the original GRAPH algorithm. A speaker-dependent variation of this approach divides the training data into two clusters of speakers: one cluster containing descriptions produced by individuals that prefer longer referring expressions, often making use of spatial relations, and another containing descriptions produced by those who prefer short, non-relational expressions. This information is taken into account to compute two attribute preference orders (i.e., one for each cluster). The study shows that the use of the cluster-dependent preference order outperforms the use of a single (i.e., global) preference order in the GRE3D3 domain (Dale and Viethen Reference Dale and Viethen2009).

Finally, a note on human choice in surface realisation. Unlike our current work, which is solely focused on content selection, some of the existing studies (Bohnet Reference Bohnet2008; Fabbrizio, Stent and Bangalore Reference Fabbrizio, Stent and Bangalore2008; Hervás, Francisco and Gervás Reference Hervás, Francisco and Gervás2013) address not only content selection, but also the surface realisation of referring expressions. In particular, the work in Hervás, Francisco and Gervás (Reference Hervás, Francisco and Gervás2013) addresses the issue of personal preferences in reference lexicalisation. By presenting an analysis of the descriptions in the TUNA corpus, the study shows that individuals tend to be consistent with themselves when making lexical choices and, accordingly, a lexicalisation algorithm that uses speaker-specific training data is shown to outperform the same algorithm when using training data produced by all speakers in the corpus.

3.1 Extended incremental algorithm (EIA)

The original Incremental algorithm (Dale and Reiter Reference Dale and Reiter1995) does not explicitly handle relational properties (e.g., as in ‘the cylinder next to the box’). An extension of this kind is in principle not difficult to envisage (Dale and Haddock Reference Dale and Haddock1991; Krahmer et al. Reference Krahmer, van Erk and Verleg2003; Dale and Viethen Reference Dale and Viethen2009; dos Santos Silva and Paraboni Reference Silva and Paraboni2015), but it does give rise to the issue of how to combine relations with ordinary atomic (e.g., ‘the blue cylinder’) properties. For instance, the work in Dale and Haddock (Reference Dale and Haddock1991) makes use of relational properties only as a last resort, that is, when it is not possible to obtain a uniquely identifying set of atomic descriptions. Other studies as Dale and Viethen (Reference Dale and Viethen2009), by contrast, suggest that relational properties are far more common, and may be included in the output description even when they do not help rule out distractors.

In what follows, we describe a relational extension to the basic incremental approach, hereby called Extended Incremental Algorithm (EIA). EIA combines atomic and relational properties as follows. First, individual lists P_atom and P_rel are computed for atomic and relational properties. Both lists are sorted by frequency as seen in the training data (to be discussed in the next section), starting with the most frequent attribute. Next, the overall frequency of relations F_rel is computed as the sum of all frequencies in P_rel . Finally, a combined list P of atomic and relational properties is created by inserting the entire list P_rel in P_atom at the position given by F_rel . The list P is taken as an input to the algorithm as illustrated in Algorithm 1.

Algorithm 1:

Extended Incremental Algorithm (EIA)

EIA works as follows. The algorithm receives as an input the target object r, an initially empty set L representing the description to be generated (recursively), the set D of all domain objects, a list P of preferred attributes, and an initially empty history list H of objects already mentioned in L. The output of the algorithm is the updated set L representing a uniquely distinguishing description of r with respect to D.

The algorithm starts by making the individual description of the current target r an empty set (line 2), making the referential context set C equal to the set of all distractor objects (3), and adding the current target to the history list (4).

As in Dale and Reiter (Reference Dale and Reiter1995), the algorithm iterates over the list of preferred attributes P (line 6) and considers only those that have discriminatory power (7–8). To this end, the rulesOut function is assumed to return the set of objects that would be removed from C by the inclusion of the current property in L.

Ordinary atomic properties – e.g., (colour-red) – are dealt with simply by adding the property to the current description (10), and by updating the context set (11). Relational properties – those in which the attribute value V under consideration corresponds to a domain object identifier, as in (left-d ₁) – are dealt with in lines 14–17. Provided that the intended object V is not yet in the previous history (14), the corresponding property is added to the current description (15), the context set is updated accordingly (16), and the algorithm is called recursively in order to describe V itself (17).

The procedure is repeated until a uniquely identifying description is obtained (21–22), or until all possible attributes in P have been attempted (6–24). In the former, L could be subsequently realised as a definite description (e.g., ‘the red cone’), whereas in the latter L could be realised as an indefinite description (e.g., ‘a red cone’).

3.2 Machine learning REG

Computational REG has been traditionally addressed by making use of knowledge-based models, such as the Incremental algorithm (Dale and Reiter Reference Dale and Reiter1995) and others. In recent years, however, the increasing availability of REG corpora has enabled a number of data-driven approaches to the task, in some cases making use of machine-learning methods (Bohnet Reference Bohnet2007; Viethen and Dale Reference Viethen and Dale2010; Viethen Reference Viethen2011; Viethen, Mitchell and Krahmer Reference Viethen, Mitchell and Krahmer2013). In this section, we will focus on the latter by presenting a REG algorithm based on a series of classifiers. An earlier version of this approach appeared in Ferreira and Paraboni (Reference Ferreira, Paraboni, Sojka, Horák, Kopeček and Pala2014a) using a different (namely, multiclass) set of classifiers.

As in Viethen (Reference Viethen2011), we will make use of individual classifiers to decide whether each referential attribute of a given target object r should be selected to appear in an output description of r. Unlike Viethen (Reference Viethen2011), however, our current work is not limited to making attribute predictions: we will go one step further and combine the output of the classifiers to produce actual referring expressions.

Let D be the set of objects in a given context, and let A be the set of (atomic and relational) attributes associated to them. Given the goal of producing a description L of a target object r ∈ D, we define a set of |A| binary classifiers C = {c ⁽¹⁾, c ⁽²⁾, . . ., c ^(|A|)} so that each classifier c ⁽ⁱ⁾ ∈ C predicts whether an attribute a ⁽ⁱ⁾ ∈ A should appear in L or not.

Individual classifiers are built from a training set of object descriptions E = {e ⁽¹⁾, e ⁽²⁾, . . ., e ^(|E|)}. Given the subsets A_atom and A_rel of atomic and relational attributes in A, respectively, a training description e ∈ E is represented as e = {X, Y_atom, Y_rel }. In this set, X is an n-dimensional feature vector. Y_atom is the atomic class set {y ¹, y ², . . ., y ^|atom|}, in which y^k = 0 when the atomic attribute a^k ∈ A_atom does not belong to e, and y^k = 1 otherwise. In the same way, Y_rel is the relational class set, in which y^k = 0 when the relation a^k ∈ A_rel does not belong to e, and y^k = 1 otherwise.

3.2.3 Combining predictions

The predictions made by the atomic and relational classifiers for a given context are combined to produce a referring expression according to Algorithm 2.

Algorithm 2:

Classification-based REG

The algorithm receives as an input the object r to be referred to, an initially empty set L representing the description to be generated (recursively), the set of all domain objects D, and an initially empty history list H of objects already mentioned in L. Unlike EIA (cf. Section 3.1), the present algorithm does not take any preferred order of atomic properties into account, since all atomic properties that are predicted by the classifiers will be included in L (and a maximum of one relational property per object). The output of the algorithm is the updated set L representing a description of r with respect to D, and which may or may not be uniquely distinguishing.

The algorithm starts by making the individual description of the current object r an empty set (2), and by including it in the history list (3). Based on the number of objects already included in the history list, the current level of description is determined (5). The description level equals 1 when r corresponds to the main target, 2 when r corresponds to the first landmark object, and so on. This information is then taken into account to invoke the appropriate set of classifiers (6–7), which are implemented by the auxiliary functions getPredictions and getSingleRelationPrediction. The former is assumed to invoke the set of atomic classifiers described in Section 3.2.1 to create the Pr_atom vector containing the predictions for every atomic attribute of r, whereas the latter invokes the set of relational classifiers and returns the first relation found to hold between the current target r and the nearest landmark, in order of frequency as seen in the training data. If no such relation is predicted, getSingleRelationPrediction is assumed to return a null value.

The algorithm iterates over the list of possible atomic properties (9–13) and considers only those that are predicted by the corresponding classifier (10). All selected properties are added to the current description, one by one (11).

Relational properties are dealt with in lines 14–20. If a relation is predicted (14), and provided that the intended landmark object lm is not yet in the previous history (16), the corresponding property is added to the current description (17), and the algorithm is called recursively in order to describe lm (18).

A complete example works as follows. Let us consider once again the domain in the previous Figure 1, the target r = d ₂ and the following predictions for the target object (i.e., for a description of level 1):

• getPredictions(1) = {⟨ type, 1 ⟩, ⟨ size, 0 ⟩, ⟨ colour, 0 ⟩}

• getSingleRelationPrediction(1) = {⟨ left-of, d ₃⟩}

The above predictions would select type and left-of for inclusion in the output L, producing the following target description:

• L = {d ₂ = {⟨ type, cylinder ⟩, ⟨ left-of, d ₃⟩}}

Next, the algorithm is called recursively to describe the landmark d ₃. Let us assume that the following (level 2) predictions were made:

• getPredictions(2) = {⟨ type, 1 ⟩, ⟨ size, 0 ⟩, ⟨ colour, 1 ⟩}

• getSingleRelationPrediction(2) = {⟨ null⟩}

In this case, both type and colour would be selected to compose the landmark portion of the description. The final description – which could be realised as, e.g., “The cylinder on the left side of the white box”, is represented as follows:

• L = {d ₂ = {⟨ type, cylinder ⟩, ⟨ left-of, d ₃⟩}, d ₃ = {⟨ type, box ⟩, ⟨ colour, white ⟩}}

Unlike EIA, in the present approach there is no explicit test for uniqueness, and properties are added to L regardless of their discriminatory power. In practice, however, discrimination is implicitly accounted for by using context features that model the similarities between context objects, as described in Section 3.2.2.

5.1 Data

Six datasets are considered for training and testing purposes: the Furniture and People subsets of the TUNA corpus (Gatt et al. Reference Gatt, van der Sluis and van Deemter2007), hereby called TUNA-f and TUNA-p, GRE3D3 (Dale and Viethen Reference Dale and Viethen2009), GRE3D7 (Viethen and Dale Reference Viethen and Dale2011), Stars (Paraboni et al. Reference Paraboni, Yamasaki, da Silva, Teixeira, Sojka, Horák, Kopeček and Pala2014), and Stars2 (Paraboni, Galindo and Iacovelli Reference Paraboni, Galindo and Iacovelli2016). The complete dataset comprises 7,478 descriptions produced by 590 speakers.

Table 1 shows, for each of the datasets, the number of speakers, descriptions, possible attributes, and objects per scene. These are accompanied by an example of description in each domain. Although most of these datasets (with the exception of TUNA-p) make use of scenes conveying geometric objects, the computational challenges involved in the generation of the corresponding descriptions vary considerably as discussed below.

Table 1.

Corpus descriptive statistics and examples

TUNA-f and TUNA-p contain descriptions of pieces of furniture (e.g., chairs, desks, etc.) and human photographs, respectively. TUNA does not contain relational descriptions, but there are references to screen positions (as in the TUNA-f example). The original TUNA corpus includes a subset of references to sets (e.g., ‘the two chairs on the right’) as well, but we presently consider only the singular portion of the data. The small number of possible attributes in the Furniture domain makes the generation of these descriptions relatively straightforward. In the People domain, by contrast, a much larger attribute set is considered and, as a result, a certain degree of data sparsity is observed.

The GRE3D3/7 corpora are the largest REG corpora publicly available to date, both in number of speakers and annotated descriptions. Descriptions produced in these domains consider only a small set of possible attributes (colour, size, and one spatial relation) and, in the case of GRE3D3, also screen position. Both corpora are largely focused on the issue of choice between atomic and relational properties. For that reason, in the situations of reference represented in GRE3D3/7 the use of a relational property is never compulsory for disambiguation. For instance, given the goal of describing a box object, it is always possible to choose between an atomic (e.g., ‘the large box’) and a relational description (e.g., ‘the box near the ball’).

Stars and Stars2 domains represent situations of reference involving up to three referents in a single description and a larger number of distractor objects in each scene. The situations of reference considered in Stars2 include properties that, although not required for disambiguation, are highly salient. These situations are intended to challenge REG algorithms that make use of a fixed preference order (e.g., always preferring colour over size etc.) Stars includes references to screen positions, but Stars2 does not. The original Stars data includes five filler scenes whose descriptions are unconventionally complex, and which are presently disregarded. In other words, only descriptions produced under the critical conditions of the Stars experiment (Paraboni et al. Reference Paraboni, Yamasaki, da Silva, Teixeira, Sojka, Horák, Kopeček and Pala2014) are presently considered.

5.2 Algorithms

The experiment assessed the Extended Incremental Approach (EIA, cf. Section 3.1) and the classifier models (cf. Section 3.2) in two versions each: with (+) and without (−) speaker-dependent information. Further variations are discussed below.

In the case of the classifier model, two alternative implementations were considered: a standard approach based on decision trees (Breiman et al. Reference Breiman, Friedman, Olshen and Stone1984) as in Viethen and Dale (Reference Viethen and Dale2010), and a second version using support vector machines with Gaussian kernel (Cortes and Vapnik Reference Cortes and Vapnik1995) as in Ferreira and Paraboni (Reference Ferreira, Paraboni, Sojka, Horák, Kopeček and Pala2014). We will refer to the former as our decision tree (DT) model, and to the latter as our support vector machine (SVM) model.

All classifiers are built from the entire training dataset, that is, we intend to learn how to generate descriptions produced by every individual speaker by making use of knowledge provided by all speakers. Classifiers related to attributes of the target object are built from atomic and relational descriptions alike, and those related to attributes of landmark objects are built from relational descriptions only.

EIA and the two classifier implementations (SVM and DT), all of which with (+) and without (−) speaker-dependent information, will give rise to 3*2 = 6 REG models to be evaluated.

5.3 Hypotheses

Our two main research hypotheses are as follows:

1. (h1) REG algorithms that take speaker-related information into account outperform those that do not.

2. (h2) REG algorithms based on machine-learning methods outperform a standard incremental approach.

Hypotheses h1 and h2 will be tested by comparing every description in the test data with the equivalent produced by one of our algorithms. In doing so, we will follow Gatt, van der Sluis and van Deemter (Reference Gatt, van der Sluis and van Deemter2007) and others and measure mean Dice coefficients (Dice Reference Dice1945). Dice coefficients range from 0 to 1 and are intended to represent the degree of overlap between the two attribute sets. In addition to that, we will also compute mean Accuracy scores for illustration purposes. Accuracy also ranges from 0 to 1, and represents the proportion of exact matches between the two sets, that is, the proportion of comparisons in which we obtained a Dice score of 1.

For h1, we will compare algorithms that do not take (−) speaker-related information with those that do (+). More specifically, we will compare EIA− with EIA+, SVM− with SVM+, and DT− with DT+. In all cases, we expect the version that uses (+) speaker-related information to outperform the version that does not (−).

For h2, we will compare the EIA with both machine learning models (SVM and DT). More specifically, we will compare EIA− with SVM−, EIA+ with SVM+, EIA− with DT− and EIA+ with DT+. In all cases, we expect SVM/DT to outperform EIA.

Regarding the possible difference between DT and SVM, no predictions will be made. DT and SVM are intended simply as alternative implementations of our machine learning model, and we assume that their results will vary across domains.

5.4 Procedure

All algorithms used six-fold cross validation to generate Stars and TUNA descriptions, and used ten-fold cross-validation to generate GRE3D3, GRE3D7, and Stars2 descriptions. The number of folds for each domain was defined so as to balance the number of speakers within each fold.

In the case of EIA, one fold was left out as test data, and the others were used to estimate attribute frequencies, and also to build the preference lists used in each iteration of the cross-validation.

For the SVM classifiers, optimal values for the cost (C) and the Gaussian Kernel’s gamma (γ) parameters were determined by performing Grid Search as follows. For each iteration of the cross-validation task, one-fold f was reserved for testing, and the remaining folds were used in a secondary cross-validation task in which the classifiers were trained using different combinations of C (1, 10, 100, and 1000) and γ (1, 0.1, 0.001, and 0.0001) values. The parameters that produced highest accuracy were thus selected, and then applied to the primary cross-validation task to test fold f. This procedure was repeated for each iteration of the primary cross- validation.