OMEGA : A probabilistic approach to referring expression generation in a virtual environment (2020)

Abstract: In recent years, referring expression genera- tion algorithms were inspired by game theory and probability theory. In this paper, an al- gorithm is designed for the generation of re- ferring expressions (REG) that base on both models by integrating maximization of utilities into the content determination process. It im- plements cognitive models for assessing visual salience of objects and additional features. In order to evaluate the algorithm properly and validate the applicability of existing models and evaluative information criteria, both, pro- duction and comprehension studies, are con- ducted using a complex domain of objects, pro- viding new directions of approaching the eval- uation of REG algorithms.

## introduction probabilistic and game-theoretic approaches to reg base on the maximization of utilities @xcite or on corpus frequencies of attributes that are selected according to random float values (e.g. the pro model, @xcite . these models and their humanlikeness of production were tested on domains of limited size, mostly three objects, and a minimal set of 3 to 4 properties. the parameters of these models are learned using maximum likelihood estimation. due to the non-deterministic nature of probabilistic models, evaluation metrics used for deterministic models, especially the dice score, cannot be applied. therefore, the likelihood of the predicted distribution, given the observed data, is computed using the bayesian information criterion (bic). with a limited set of possible referring expressions, the likelihood function, which bases on the multinomial distribution, produces reasonable results, but an increasing complexity of the domain may necessitate a different evaluation approach. empirical data against which the reference games model @xcite ) was tested has been collected in betting games in a forced-choice paradigm. such data sets are not only non-reproducible for larger domains, but also circumvent the integration of underlying cognitive processes of content determination into the model. hence, the aim of this paper is to develop a new probabilistic reg-algorithm that is able to handle the choice of complex attributes and spatial relations on the basis of a cognitively motivated tradeoff between salience, preference and discriminatory power (dp). an important aspect of this tradeoff must be the possibility of generating minimal and overspecified expressions in complex domains for overcoming the deficiency of models rooted in game theory, which typically produce unary expressions only. overspecification is of essential importance for a humanlike modeling of reference, since overspecification has been proved to facilitate the identification task for the hearer if the redundant information is easily accessible @xcite . in what follows, first the domain underlying the experimental studies will be presented. then the production survey is described. subsequently, cognitive models for the approximation of visual salience are introduced which are used in the omega algorithm. section 5 gives a detailed description of the developed model. section 6 evaluates the algorithm performance in both humanlikeness and comprehension, giving insight into problems and advantages of deployed evaluation methods. ## the reference domain the domain for the empirical studies consists of 3d geometric primitives with different properties. atomic properties are shape and name tag, while size is a scalar property whose value is determined in the context, and colour relies on the calculation of shades for red, blue and green. the light and dark shades are each prefixed with the according specifier light-or dark-. two further relational properties are given as coordinates for x-axis and y-axis. the design of this corpus is different from other well-renowned corpora (e.g. tuna) in several important aspects. colors provide different degrees of visual difference. size is varying by fixed ratios. the domain on which the production data from participants is collected must agree with the domain for the comprehension study. last but not least, the type attribute is fixed as gift box, such that the generation of the shape attribute does not vary. attribute values colour {(light-, dark-) blue, red, green, grey, black, brown} type {ball, cube, torus, cone, cylinder, flower} size {0.5, 0.75, 1} tag {circle, square} x-coord. ## empirical production survey a web-based empirical survey has been conducted in order to collect production data from native speakers of english. this data reveals the attribute choice and reference habits of the participants. the production survey is split into two subexperiments. in the first part, speakers are rating the visual salience of attribute values for each attribute separately, e.g. in the set of colour values, participants rate the salience of each value within the set of colours. additionally, for size and colour, the correlation between the gradience and the salience ratio is assessed by letting the participants rate the visual difference between values. an example of this assessment of the visual difference is given in figure 2 . the intention behind this survey design is to provide an attribute-specific rating of visual salience or prominence, respectively. these values serve as input to the reg models presented in the following sections. the downside of this is the dependence of models on corpora for each unseen domain. for this reason, section 4 proposes cognitive models that may replace corpus data and make reg models independent from corpora and collected production data. the second part of the study comprises production sessions. in each session, between 3 and 9 objects are depicted in a grid (see figure 1 ). the speaker's task is to compose an expression that uniquely identifies the target object which is highlighted by a golden frame. participants were able to select and deselect attribute values, candidate objects for spatial relations and in turn attributes for the description of the spatially related object. attribute selection is restricted to the choice from domain attributes and their values in order to avoid the necessity of normalizing free text input after collecting the corpus data. participants could also produce a surface realization from their selected attributes. an intriguing fact is that this restriction of attribute selection does not trigger a shift in preferential usage of attributes in comparison to e.g. the tuna corpus and other psycholinguistic studies (e.g. @xcite . the production subdomains of 10 sessions were fixed, 15 subsequent sessions were randomized. the web application allowed for the integration of identical objects several times, such that identification may be possible only via using coordinates. via prolific, 100 native speakers of english from the united kingdom were acquired. the produced corpus consists of about 2500 production sessions. the pie chart in figure 3 reveals the amount of overspecified phrases with 60% of all produced expressions in the data. the capability of producing overspecified expressions is consequently of high importance for humanlikeness in the reg task. the outer circle is divided into expressions with and without spatial relations, while the inner circle visualizes the sum of the respective generation quality. 4 cognitive models for approximation of visual salience a well justified metric is needed in order to model the perceptual prominence of each object as a substitute for salience ratings. if this salience is a joint effect of the visual salience of the object's properties, a utility function for a reg model needs to integrate a computation of how much the object springs to the speaker's eye. for size, this is straightforward, since the domain objects were rendered with three different size factors. the prior production survey reveals a linear relation between the increase in size factor and the increase in perceptual size difference. van deemter and his coauthors @xcite prove that in reg, the ratio of size difference has essential importance on the production probability of this property. therefore, for a reg model, this ratio models the salience for size in a set of objects. for colour, comparing values is more complex. cognitive experiments on colour perception led to the conception of the cielab colour space @xcite . formulas have been construed that calculate the difference between two colours, the ∆e value, that humans may still perceive. multiple revisions of the cielab ∆e functions exist with different terms for compensating hue and saturation, but they all base on the euclidean distance of colours which are represented as 3-dimensional vectors in the cielab colour space. these ∆e functions allow to compute the difference between two colours in a cognitively reasonable way and can be used in a utility function. a challenge to be faced is that in realistic settings corresponding metrics are required for other attributes as well, e.g. shapes. although not implemented in the model presented in this paper, attempts are made to formalize the similarity measures between shapes by analysing their vertices @xcite and points on the contour @xcite . @xcite developed a model for shape comparison that is close to cognitive processes of noisy shape perception. relational attributes may be modeled using an approach comparable to @xcite measure of assessing the distance towards the center of the visual field, but this is subject to further research. the main advantage of approximating visual salience with these cognitive models is that values are calculated in situ on the present visual field, instead of optimizing parameters such that they fit a large data set best. in this way, referring expressions may be generated in a more individual way and be tailored to the present domain, while other methods rather capture the whole data on average. finally, these cognitive models make reg models independent from experimental studies as given in section 3 under the premise that they perform equally well. at its core, a utility function as used in reference games @xcite computes production probabilities which guide content determination. the concept of this utility function is crucial for the performance of the whole model. at this point, an observation made on the empirical data from the prior study becomes a decisive factor. when high dp coincides with high salience, the usage of the respective attribute increases drastically, while high dp for non-salient attributes does not influence attribute selection significantly. additionally, van deemter (2016) and @xcite show that larger proportional differences in gradable attributes, e.g. size, trigger a higher usage in referring expressions than small differences that are cognitively less easily assessable. after all, this is the interference between dp and salience. the 'object-distractor contrast', as mast (2016, p.140) terms it, in regard to a specific attribute is influenced both by the number of distractors that provide the same attribute value as well as by the visual distinctiveness of the attribute value in comparison with other values of the same attribute that apply to the distractors. therefore, salience, preference and dp must be taken balanced when defining the utility function. the salience computation which is used in the utility definition of the omega algorithm integrates the cognitive models of perception presented in the previous section. the formulae below describe how the salience values are computed. the attribute value of the target object is compared to the values of the distractors in regard to that attribute and the average value is calculated. therefore, salience is represented as the average visual difference between the target and the set of distractors d. the more different, the higher is the salience. the factor α projects the ∆ e value onto the interval of numbers between 0 and 1, c is a colour vector. for size, the absolute value of the difference between s and s i is needed in order to prevent negative values when @xmath0. the same method is used for discriminatory power which is a ratio of how many distractors an attribute value rules out. considering the fact that attribute selection is performed across attributes (and not across attribute values), it is possible to calculate for each attribute, of which a value applies to the target, what the average dp is in comparison with values of the respective attribute that apply to the distractors. in order to prevent negative utilities, the function only adds the difference of e to some e @xmath1. in other words, if the dp of the target attribute is smaller than the dp of a competitive attribute, the negative distance is not added, but the average dp nevertheless is decreased since it is normalized against the number of all competitive attributes, i.e. including those with higher dp. for the omega model, the utility function u is defined as the product of the average dp and the salience of the value v a of attribute a that is true of the target object in domain d. to this product, the preference degree estimated by the frequency of attributes in the production data can be added under the assumption that preference is not independent from the joint effect of salience and dp. the decision to integrate preference is also motivated by the findings of @xcite , who prove that the integration of speaker preferences enhances the quality of their svm classifiers for reg. in rsa and other log-linear models a logarithm is used in order to map large utility values to a smaller interval of results @xcite . this has the positive effect of assigning the lowest possible utility, namely negative infinity, to attributes with a literal interpretation of 0, or, as in omega, irrelevant information. in combination with softmaximizing utilities, the model conforms with grice's maxim of quantity. softmaximization which is deployed in omega means turning the utilities into weighted production probabilities, as shown in the formula (5). by means of the chain rule we are able to calculate the probabilities of all candidate referring expressions e which are sequences of attribute values a that are true of the referent. after attribute value a 1 is selected, the set of distractors d of domain m is updated, as well as the attribute a 1 belongs to is removed from the set of selectable properties. this probability is multiplied with the result of calculating the probability of a 2 given the updated data structures and the already selected attributes, and so on until a n has been achieved. this mechanism permits the omega model to produce a probability distribution over all possible expressions that are true of the target. a closer analysis of the pseudo code in algorithm 1 will show how omega implements the selection of reference objects and production of spatial relations, as well as the enrichment with redundant attributes for overspecification. line 4 initializes two empty data structures e and e rel for attributes that are selected during the production process. in line 5, rel c is a container for storing possible candidates from the set of distractors that may be used for a spatial relation. the subsequent while-loop (lines 6 to 14) calculates for each attribute a in the set of attributes a what production probability it provides in the given visual field. in line 9, the production probability is calculated, which integrates the utility function described earlier as well as the cognitive models for salience approximation. if the probability is higher than the one of the previous attribute, the maximally probable attribute is replaced with a. then, data structures are updated. if some distractor is found for which the production probability for the present attribute a is larger then for the target, it is stored as a candidate for spatial relations (line 10). the while-loop terminates when either the set of distractors m or the set of attributes a is empty. in line 15, if some candidate for spatial relations has been found, omega is recursively called on that object. otherwise, the overspecification process starts (line 18). while overspecification is selected and a is not empty, maximal probable attributes are added to the expression using the same mechanism as in the first while loop. a possible point of criticism is that the usage of the formula for production probability may not be suitable for overspecification, since the utility tries to calculate the average salience and dp values on an empty set of distractors. in full awareness of this circumstance the functions for salience and dp are intended to integrate default values. for dp, the default value is 1, while for salience, the prior algorithm 1 overspecifying utility-maximizing referring expression generation algorithm (omega) 1: input: reference domain d with target object r and a non-empty set of distractors m, a set of attributes a at least one of whose values is true of r. 2: output: the referring expression with maximal probability 3: function omega(r, d, m, a, ω) 4: e, e rel ← [ ] 5: relc ← [ ] 6: while @xmath2: amax ← none 8: for @xmath3: p ← p(a|r, d) 10: relc ← relc ∪ {r ′ |r ′ ∈ m ∧ p(a|r ′ ,d) > p} 11: if @xmath4: amax ← a 13: e.insert(a) 14: update m , a 15: if @xmath5: r rel ← argmax(relc) 17: e rel ← omega(r rel , d, m , a rel , ω) 18: while randomboolean(ω) is t rue ∧ @xmath6: a ′ max ← none 20: for a ′ ∈ a ′ do 21: p ′ ← p(a ′ |r, d) 22: if p ′ > a ′ max then 23: a ′ max ← a ′ 24: e.insert(a ′ ) 25: update a ′ 26: return e, e rel ## evaluation for evaluation, the omega model has been tested competitively against the pro model and the standard ia algorithm. both, humanlikeness in production and performance in a comprehension task, have been evaluated. ## conclusion the omega model succeeds in integrating the tradeoff between the most important parameters of reg, namely discriminatory power, salience and preference. the maximization of their joint effect, which defines the utility, allows to incrementally and probabilistically build referring expressions that may also contain spatial relations. the omega model outperforms both ia and pro in a comprehension task in a virtual environment. nonetheless, more research is needed to further optimize the cognitive models that compute the salience values for different attributes which are needed for the omega model. these measures provide the advantage of calculating salience in situ on the preset visual field, resulting in more independence from empirical input and parameter tuning at an improved performance level. one of the most important findings is the inapplicability of information criteria like bic and optimization methods like mle to models, given complex domains with numerous, realistically infinite, possible referring expressions. this is a reasonable indicator for the shift to comprehension as the standard evaluative method for reg models.