partition
8 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

6Incrementalgenerationofpluraldescriptions: SimilarityandpartitioningAlbertGatt and KeesvanDeemterDepartmentofComputingScienceUniversityofAberdeen{agatt,kvdeemte}@csd.abdn.ac.ukAbstract TYPE COLOUR ORIENTATION SIZE X Ye desk red back small 3 11Approaches to plural reference generation empha e sofa blue back small 5 22sise simplicity and brevity, but often lack em e desk red back large 1 13pirical backing. This paper describes a corpus e desk red front large 2 34based study of plural descriptions, and proposes e desk blue right large 2 45a psycholinguistically motivated algorithm for plu e sofa red back large 4 16ral reference generation. The descriptive strategy e sofa red front large 3 37e sofa blue back large 3 2is based on partitioning. An exhaustive evaluation 8showsthattheoutputcloselymatcheshumandata.Table1: Avisualdomain1 Introductiondistractors [1.4]. The description and the distractorContent Determination for the Generation of Re setC areupdatedaccordingly[1.5–1.6],andthede ferring Expressions (GRE) starts from a Knowledgescriptionreturnedifitisdistinguishing[1.7].Base (KB) consisting of a set of entitiesU and a setCompared to some predecessors which empha of propertiesP represented as attribute value pairs,sised brevity (Dale, 1989), the IA is highly effi and searches for a descriptionD⊆ P which distin cient, because the use of thePO avoids exhaus guishes a referent r∈ U from its distractors. Fortive combinatorial search, potentially ...

Subjects

Informations

Published by
Reads 110
Language English

6
Incrementalgenerationofpluraldescriptions: Similarityandpartitioning
AlbertGatt and KeesvanDeemter
DepartmentofComputingScience
UniversityofAberdeen
{agatt,kvdeemte}@csd.abdn.ac.uk
Abstract TYPE COLOUR ORIENTATION SIZE X Y
e desk red back small 3 11Approaches to plural reference generation empha
e sofa blue back small 5 22sise simplicity and brevity, but often lack em
e desk red back large 1 13
pirical backing. This paper describes a corpus e desk red front large 2 34
based study of plural descriptions, and proposes e desk blue right large 2 45
a psycholinguistically motivated algorithm for plu e sofa red back large 4 16
ral reference generation. The descriptive strategy e sofa red front large 3 37
e sofa blue back large 3 2is based on partitioning. An exhaustive evaluation 8
showsthattheoutputcloselymatcheshumandata.
Table1: Avisualdomain
1 Introduction
distractors [1.4]. The description and the distractorContent Determination for the Generation of Re
setC areupdatedaccordingly[1.5–1.6],andthede ferring Expressions (GRE) starts from a Knowledge
scriptionreturnedifitisdistinguishing[1.7].Base (KB) consisting of a set of entitiesU and a set
Compared to some predecessors which empha of propertiesP represented as attribute value pairs,
sised brevity (Dale, 1989), the IA is highly effi and searches for a descriptionD⊆ P which distin
cient, because the use of thePO avoids exhaus guishes a referent r∈ U from its distractors. For
tive combinatorial search, potentially overspecify example,the KB inTable1represents8entitiesina
ing the description. Overspecification and the use2D visualdomain,eachwith 6attributes,including
of aPO have been justified on psycholinguistictheir location, represented as a combination of hor-
grounds. Speakers overspecify their descriptionsizontal (X) and vertical (Y) numerical coordinates.
because they begin their formulation without ex To refer to an entity an algorithm searches through
haustively scanning a domain (Pechmann, 1989),valuesofthedifferentattributes.
terminating the process as soon as a referent is dis
GRE has been dominated by Dale and Reiter’s
tinguished (Belke and Meyer, 2002). They pri (1995) Incremental Algorithm (IA), one version
oritise the basic level category ( TYPE) of an ob of which, generalised to deal with non disjunctive
1 ject, and salient, absolute properties like COLOURplural references is shown in Algorithm 1 (van
Deemter, 2002). After initialising the description
Algorithm1 IA (R,U,PO)plurD and the distractor set C [1.1–1.2], IA tra plur
1: D←∅verses an ordered list of properties, called the pref
2: C←U−R
erence order (PO) [1.3], which reflects general or
3: forhA : vi∈PO do
domain specific preferences for attributes. For in
4: if R⊆ [hA : vi ]∧[hA : vi ]−C =∅ then
stance, with thePO in the top row of the Table, 5: D←D∪{hA : vi}
the algorithm first considers values of TYPE, then 6: C←C∩[hA : vi ]
COLOUR, and so on, adding a property to D if it is 7: if[D ] =Rthen
trueoftheintendedreferentsR,andexcludessome 8: returnD
9: endif
1
Non disjunctive descriptions, such as the large red chairs, 10: endif
are logically a conjunction of literals. In disjunctive descrip
11: endfor
tions such as the chair and the table, the and represents set
12: returnD
union(ofthingswhicharechairsortables).(Pechmann, 1989; Eikmeyer and Ahlsen,` 1996), as question of whether previous psycholinguistic re
well as locative properties in the vertical dimen search on singular reference is at all applicable to
sion (Arts, 2004). Relative attributes like SIZE are thepluraldisjunctivecase.
avoidedunlessabsolutelyrequiredforidentification This paper starts with an empirical analysis of
(Belke and Meyer, 2002). This evidence suggests plural descriptions using a semantically transparent
speakers conceptualise referents as gestalts (Pech corpus of elicited in well defined do
mann, 1989) whose core is the basic level TYPE mains,ofwhichTable1isanexample. Basedonthe
(Murphy, 2002) and some other salient attributes data analysis, we propose and evaluate an efficient
like COLOUR. Note that the IA does not fully mir- algorithm for the generation of references to arbi
ror these human tendencies, since it only includes trary sets. Our starting point is the assumption that
preferred attributes in a description if they remove plurals,likesingulars,evincepreferencesforcertain
somedistractors,whereaspsycholinguisticresearch attributes. Based on previous work in Gestalt per-
suggests that people include them irrespective of ception (Wertheimer, 1938; Rock, 1983), we pro
contrastiveness (cf. van der Sluis and Krahmer, pose an extension of Pechmann’s Gestalts Princi
2005). ple, whereby plural descriptions are preferred if (a)
More recent research on plural GRE has de they maximise the similarity of their referents, us
emphasised these issues, especially in case of dis ing the same attributes to describe them as far as
junctive plural reference. The first concrete pro possible;(b)prioritisesalient(‘preferred’)attributes
posal in this area, IA (van Deemter, 2002), first whicharecentraltotheconceptualrepresentationofbool
tries to find a non disjunctive description using Al anobject. Weaddress(3)abovebyinvestigatingthe
gorithm 1. Failing this, it searches through disjunc logicalformofpluralsinthecorpus. Onestrongde
tionsofpropertiesofincreasinglength,generatinga terminant of descriptive form is the basic level cat
descriptioninConjunctiveNormalForm(CNF). For egory of objects. For example, to refer to{e ,e}1 2
example, calling the algorithm with R ={e ,e} intheTable,anauthorhasatleastthefollowingop 1 2
would result in a non disjunctive description, since tions:
both referents can be distinguished usinghSIZE :
(1) (a) thesmalldeskandsofasmalli. However, a conjunction wouldn’t suffice to
distinguishR ={e ,e},and IA wouldconsider (b) thesmallreddeskandthesmallbluesofa1 8 bool
combinations such ashTYPE : deski∨hCOLOUR : (c) thesmalldeskandthesmallbluesofa
bluei. This generalised algorithm has three conse
(d) thesmallobjects
quences:
We refer to (1a) as an aggregated disjunctive de
1. Efficiency: Searching through disjunctive
scription, in that the property small has wide scope
combinations results in a combinatorial explo
scope over the coordinate NP desk and sofa (which
sion(vanDeemter,2002).
is logically a disjunction). By contrast, (1b,c)
2. Gestalts and content: The notion of a ‘pre are non aggregated and overspecified because they
contain COLOUR when SIZE alone suffices. Theferred attribute’ is obscured, since it is dif
ficult to apply the same reasoning that moti most economical description is (1d), which is non
disjunctive. This is possible because it containsvated thePO in the IA to combinations like
a superordinate TYPE (object). Since basic level(COLOUR∨ SIZE).
categorisation is preferred on independent grounds
3. Form: Descriptionscanbecomelogicallyvery
(Rosch et al., 1976), we expect (1a–c) to be more
complex(Gardent,2002;Horacek,2004).
frequent. Notethat(1b,c)representapartitionofR
anddescribeeachelementseparately. In(1b),there
Some proposals to deal with (3) include Gar-
is considerable redundancy in including COLOUR
dent’s (2002) non incremental, constraint based al
twice. The potential benefit of this is that the el
gorithm to generate the briefest available descrip
ements of the partition are described in a parallel
tion of a set. An alternative, by Horacek (2004),
fashion,usingexactlythesameattributes(SIZE and
combines best first search with optimisation to re
COLOUR). Thisisnotthecasein(1c),whichisnon
duce logical complexity. Neither approach benefits
parallel. Byhypothesis,parallelismaddstotheper-
from empirical grounding, and both leave open the
ceptual cohesion of the set. Given the psycholin <DESCRIPTION num=‘pl’>
VS VDS num=‘singular’>
<ATTRIBUTE name=‘size’ value=‘small’>small</ATTRIBUTE> +Disj −Disj +Disj −Disj name=‘colour’ value=‘red’>red</ATTRIBUTE> name=‘type’ value=‘desk’>desk</ATTRIBUTE> +aggr 20.2 15.5 2.4 3.7
</DESCRIPTION> −aggr 64.3 – 93.9 –
and
<DESCRIPTION num=‘sg’> %overall 84.5 15.5 96.3 3.7
<ATTRIBUTE name=‘size’ value=‘small’>small</ATTRIBUTE> name=‘colour’ value=‘blue’>blue name=‘type’ value=‘sofa’>sofa Table2: %disjunctiveandnon disjunctiveplurals
</DESCRIPTION>
domains, referents were identifiable using identical
(hSIZE : smalli∧hCOLOUR : redi∧hTYPE : deski)
∨ valuesoftheminimallydistinguishingattributes. In
(hSIZE : smalli∧hCOLOUR : bluei∧hTYPE : sofai)
the remaining 6 Value Dissimilar (VDS) domains,
Figure1: Corpusannotationexamples the minimally distinguishing values were different.
Table1representsa VS domain,where{e ,e}can1 2
guistic evidence, the hypothesised tendency to em be minimally distinguished using the same value of
phasisesimilaritymayalsobesomewhatdependent SIZE (small). Thus, MD in VS was a logical con
on the attributes involved, so that COLOUR should junction. In VDS, it was a disjunction since, if two
be more likely to be redundantly propagated across referents could be minimally distinguished by dif
0disjunctsthanarelativelydispreferredattributelike ferentvaluesv andv ofanattribute A,then MDhad
SIZE. the formhA : vi∨hA : v’i. However, even in VS,
referents had different basic level types. Thus, an
2 Thedata
authorfacedwithadomainlikeTable1hadatleast
Thedataforourstudyisasubsetofacorpusof900 thedescriptiveoptionsin(1a–d).
references to furniture and household items, col Our analysis will focus on a stratified random
lectedviaacontrolledexperimentinvolving45par- sampleof180pluraldescriptions,referredtoas PL ,1
ticipants. In addition to their TYPE, objects in the generatedbytaking4descriptionsfromeachauthor
domains have COLOUR, ORIENTATION and SIZE. (2 each from VS and VDS conditions). We also use
For each subset of these three attributes, there was the singular data (SG; N = 315). The remaining
anequalnumberofdomainsinwhichtheminimally plural descriptions (PL ; N = 405) are used for2
distinguishing description (MD) consisted of values evaluation.
ofthatsubset. Forexample,Table1representsado
3 Thelogicalformofpluralsmain in which the intended referents,{e ,e}, can1 2
2beminimallydistinguishedusingonly SIZE . Thus, Descriptions in PL were first classified according1
overspecified usage of attributes can be identified to whether they were non disjunctive (cf. 1c) or
in authors’ descriptions. Domain objects were ran disjunctive (1a,b). The latter were further classified
domly placed in a 3 (row)× 5 (column) grid, rep into aggregated (1a) and non aggregated (1b). Ta
resented by X and Y in Table 1. These are relevant ble2displaysthepercentageofdescriptionsineach
for a subset of descriptions which contain locative of the four categories, within each level of Value
expressions. Similarity. Disjunctive descriptions were a major-
Corpus descriptions are paired with an explicit ity in either condition, and most of these were non
XML domainrepresentation,andannotatedwithse aggregated. As noted in relation to (1b), these de
mantic markup which makes clear which attributes scriptions correspond to partitions of the set of ref
adescriptioncontains. Themarkupalsoenablesthe erents.
3compositionalderivationofalogicalform . Forex Since referents in VS had identical properties ex
ample, the XML representation of (1b) is shown in cept for TYPE values, the most likely reason for the
Figure1,whichalsodisplaysthe LFderivedfromit. majority of disjunctives in VS is that people’s de
Descriptions in the corpus were elicited in 7 do scriptions represented a partition of a set of refer-
mains with one referent, and 13 domains with 2 ents induced by the basic level category of the ob
referents. Plural domains represented levels of a jects. This is strengthened by the finding that the
Value Similarity factor. In 7 Value Similar (VS) likelihoodofadescriptionbeingdisjunctiveornon
disjunctivedidnotdifferasafunctionofValueSim 2
TYPE wasnotincludedinthecalculationof MD.
2 2
3 ilarity (χ = 2.56, p > .1). A χ test on over-For details of corpus design and annotation, we refer to
allfrequenciesofaggregatedversusnon aggregated(vanderSluisetal.,2006).2Parallel Non Parallel χ (p≤.001) Actual Predicted
p(A,SG) p(A,PPS) p(A,PPS)overspec. 24.6 75.4 92.467
underspec. 5.3 94.7 42.217 COLOUR .680 .835 .61
well spec. 11 89 26 SIZE .290 .359 .28
ORIENTATION .280 .269 .26
X-DIMENSION .440 .517 .52
Table3: Parallelism: %perdescriptiontype
Y-DIMENSION .630 .647 .65
disjunctives showed that the non aggregated de
Table4: Actualandpredictedusageprobabilities
scriptions (‘true’ partitions) were a significant ma
2jority (χ = 83.63, p < .001). However, the tions for each of the three classes are are shown
greater frequency of aggregation in VS compared in Table 3. In all three description types, there is
2to VDS turned out to be significant (χ = 15.498, an overwhelming majority of Parallel descriptions,
p < .001). Note that the predominance of non 2confirmed by a χ analysis. The difference in pro
aggregated descriptions in VS implies that proper- portions of description types did not differ between
2ties are repeated in two disjuncts (resp. coordinate VS and VDS (χ < 1, p > .8), suggesting that the
NPs), suggesting that a certain kind of redundancy tendency to redundantly repeat attributes, avoiding
is not problematic (contra, for example, Gardent, aggregation, is independent of whether elements of
2002). asetcanbeminimallydistinguishedusingidentical
values.3.1 Conceptualgestaltsandsimilarity
Our second prediction was that the likelihood
Allowingfortheindependentmotivationforsetpar-
withwhichanattributeisusedinaparallelstructure
titioning based on TYPE values, we suggested in§1
isafunctionofitsoverall‘preference’. Thus,weex
that parallel descriptions such as (1b) may be more
pectattributessuchas COLOURtofeaturemorethan
likely than non parallel ones (1c), since the latter
once(perhapsredundantly)inaparalleldescription
doesnotusethesamepropertiestodescribethetwo
to a greater extent than SIZE. To test this, we used
referents. Similarity, however, should also interact
the SG sample, estimating the overall probability of
withattributepreferences.
occurrenceofagivenattributeinasingulardescrip
Forthispartoftheanalysis,wefocusexclusively
tion (denoted p(A,SG)), and using this in a non
on the disjunctive descriptions in PL (N = 150)1
linear regression model to predict the likelihood
in both VS and VDS. The descriptions were cat
of usage of an attribute in a plural partitioned de
egorised according to whether they had parallel
scription with parallel semantic structure (denoted
or non parallel semantic structure. Evidence for
p(A,PPS)). Thedatawasfittedtoaregressionequa
Similarity interacting with attribute preferences is Stion of the form p(A,PPS) = k×p(A,SG) . The
strongest if it is found in those cases where an
resulting equation, shown in (2), had a near perfect
attribute is overspecified (i.e. used when not re 2 4fit to the data (R = .910) . This is confirmed by
quired for a distinguishing description). In those
comparing actual probability of occurrence in the
caseswherecorpusdescriptionsdonotcontainloca
secondcolumnofTable4,tothepredictedprobabil
tive expressions (the X and/or Y attributes), such an
ities in the third column, which are estimated from
overspecified usage is straightforwardly identified
singularprobabilitiesusing(2).
based on the MD of a domain. This is less straight
forward in the case of locatives, since the position .912p(A,PPS) =.713p(A,SG) (2)
of objects was randomly determined in each do
Note that the probabilities in the Table con main. Therefore, we divided descriptions into three
firm previous psycholinguistic findings. To the ex classes: Adescriptionisunderspecifiedifitdoesnot
tent that probability of occurrence reflects salienceincludealocativeexpressionandomitssome MDat
and/or conceptual importance, an order over thetributes. Adescriptionisoverspecifiedifeither(a)it
three attributes COLOUR, SIZE and ORIENTATIONdoes not omit any MD attributes, but includes loca
can be deduced (C>>O>>S), which is compatibletives and/or non required visual attributes; or (b) it
with the findings of Pechmann (1989), Belke andomits some MD attributes, but includes both a loca
Meyer(2002)andothers. Thelocativeattributesaretiveexpressionandother,non requiredattributes. A
descriptionis well specified otherwise. 4A similar analysis using linear regression gave essentially
Proportions of Parallel and Non Parallel descrip thesameresults.6
6
0Algorithm2updateDescription(hA : Vi,R )also ordered (Y>>X), confirming the findings of
Arts (2004) that vertical location is preferred. Or- for hR ,T ,M i∈D doDF DF DF part
0derings deducible from the SG data in turn are ex if R =∅ then
returncellent predictors of the likelihood of ‘propagating’
0elseif R ⊆R thenDFan attribute across disjuncts in a plural description,
M ←M ∪ hA : viDF DFsomething which is likely even if an attribute is re
0 0R ←R −RDFdundant,modulothecentralityorsalienceoftheat 0elseif R ∩R =∅thenDF
tributeinthementalgestaltcorrespondingtotheset. 0R ←R ∩Rnew DF

Together with the earlier findings on logical form, DF ← R ,T ,M ∪{hA : vi}new new DF DF
the data evinces a dual strategy whereby (a) sets D ←D ∪ DFpart part new
are partitioned based on basic level conceptual cat R ←R −RDF DF new
0 0egory; (b) elements of the partitions are described R ←R −Rnew
using the same attributes to if these attributes are endif
endforeasily perceived and conceptualised. Thus, of the
if A = TYPE thendescriptions in (1) above, it is (1b) that is the norm

0D ←D ∪ R ,hA : vi,∅part partamongauthors.
else
0D ←D ∪ hR ,⊥,{hA : vi}ipart part4 Contentdeterminationbypartitioning
endif
In this section we describe IA , a partitioning part
based content algorithm. Though Althoughneither DFisdistinguishing,R indicatesDF
presented as a version of the IA, the basic strat
which referents a fragment is intended to identify.
egy is generalisable beyond it. For our purposes, In this way, the algorithm incorporates a ‘divide
the assumption of a preference order will be main
and conquer’ strategy, splitting up the referential
tained. IA is distinguished from the original IApart intention into ‘sub intentions’ to refer to elements
and IA (cf.§1)intworespects: (a)Itinducespar-bool of a partition. Following the initial step of select
titions opportunistically based on KB information, ing TYPE, the algorithm considers other properties
and this is is reflected in the way descriptions are inPO. SupposehCOLOUR : bluei is considered
represented. (b) The criteria whereby a property is first. This property is true of e and e . Since2 5
addedtoadescriptionincludeaconsiderationofthe
DF refers to e , the new property can be added2 2
overallsalienceorpreferenceofanattribute,andits
to M . Since e is not the sole referent of DF ,DF 5 12
contribution to the conceptual cohesiveness of the the property induces a further partitioning of this
description. Throughout the following discussion,
fragment, resulting in a new DF. This is identical
we maintain a running example from Table 1, in to DF except that it refers only to e and contains1 5
whichR ={e ,e ,e}.1 2 5 hCOLOUR : bluei. DF itself now refers only toe .1 1
OncehCOLOUR : redi is considered, it is added to4.1 Partitioneddescriptions
thelatter,yielding(4).
IA generates a partitioned description (D )part part

of a set R, corresponding to a formula in Disjunc
(4) DF {e},hTYPE : deski,{hCOLOUR : redi}1 1
tive Normal Form. D is a set of Description
part
DF {e},hTYPE : sofai,{hCOLOUR : bluei}2 2Fragments (DFs). A DF is a triplehR ,T ,M i,DF DF DF


whereR ⊆R,T isavalueof TYPE,andM is DF {e},hTYPE : deski,{hCOLOUR : bluei}DF DF DF 3 5
a possibly empty set of other properties. DFs refer
The procedure updateDescription, which cre to disjoint subsets ofR. As the representation sug
ates and updates DFs, is formalised in Algorithm 2.gests, TYPE is given a special status. IA startspart
by selecting the basic level values of TYPE, parti When some propertyhA : vi is found to be ‘useful’
inrelationtoR (inasensetobemadeprecise),thistioningR andcreatinga DF foreachelementofthe
partitiononthisbasis. Inourexample,theselection functioniscalledwithtwoarguments:hA : viitself,
0and R = [hA : vi ]∩R, the referents of whichof TYPE results in two DFs, with M initialised toDF
empty: hA : vi is true. The procedure iterates through the
DFs in D , adding the property to any DF such
part
(3) DF {e ,e},hTYPE : deski,∅ 0 01 1 5 that R ∩ R =∅, until R is empty and all ref DF

erents in it have been accounted for [2.2]. As indi DF {e},hTYPE : sofai,∅2 26
6
catedintheinformaldiscussion,therearetwocases definedviathefollowingBooleanfunction:
toconsiderforeach DF:
contrastive(hA : vi,R)↔
01. R ⊆R [2.4]. Thiscorrespondstoourexam DF ∃r∈R : C[r]−[hA : vi ] =∅ (5)
ple involvinghCOLOUR : bluei and DF . The2
0property is simply added to M [2.5] and RDF We turn next to salience and similarity. Let
is updated by removing the elements thus ac A(D ) be the set of attributes included inD .part part
countedfor[2.6]. A property is salient with respect to D if it sat part
0 isfiesthefollowing:2. R ∩R =∅ (but condition 1 does not hold)DF
[2.7]. This occurred withhCOLOUR : redi
salient(hA : vi,D )↔partin relation to DF . The procedure initialises1
.912R , a set holding those referents in R A∈A(D )∧(.713p(A,SG) > 0.5) (6)new DF part
0whicharealsoinR [2.8]. Anew DF (DF )new
that is, the attribute is already included in the de iscreated,whichisacopyoftheold DF,except
scription, and the predicted probability of its be that(a)itcontainsthenewproperty;and(b)its
ing propagated in more than one fragment of a de intendedreferentsareR [2.9]. Thenew DFnew
scription is greater than chance. A potential prob is included in the description [2.10], while the
lem arises here. Consider the description in (3)old DF is altered by removingR fromRnew DF
once more. At this stage, IA begins to con [2.11]. This ensures that DFs denote disjoint part
sider COLOUR. Thevalue redistrueofe ,butnon subsetsofR. 1
contrastive(allthedeskswhicharenotinRarered).
Two special cases arise when D is empty, or If this is the first value of COLOUR considered, (6)part
0 returns false because the attribute has not beenthere are some elements of R for which no DF ex
ists. Both cases result in the construction of a new used in any part of the description. On later con
sideringhCOLOUR : bluei, the algorithm adds it toDF. Anexampleoftheformercaseistheinitialstate
ofthealgorithm, when TYPE isadded. Asinexam D , since it is contrastive for{e ,e}, but willpart 2 5
ple (3), the TYPE results in a new DF [2.16]. If a havefailedtopropagate COLOUR acrossfragments.
propertyisnota TYPE,thenew DF hasT settonull Asaresult, IA considersvaluesofanattributeinpart
5(⊥)andthepropertyisincludedinM [2.18] . Note orderofdiscriminatorypower(Dale,1989),defined
thatthisprocedureeasilygeneralisestothesingular inthepresentcontextasfollows:
case,whereD wouldonlycontainone DF.part
|[hA : vi ]∩R| +|[hA : vi ]−(U−R)|
(7)4.2 Propertyselectioncriteria |[hA : vi ]|
IA ’s content determination strategy maximisespart
Discriminatory power depends on the number ofthe similarity of a set by generating semantically
referents a property includes in its extension, andparallel structures. Though contrastiveness plays a
the number of distractors (U − R) it removes.role in property selection, the ‘preference’ or con
Byprioritisingdiscriminatoryvalues, thealgorithmceptualsalienceofanattributeisalsoconsideredin
first considers and addshCOLOUR : bluei, andthedecisiontopropagateitacross DFs.
subsequently will include red because (6) returnsCandidate properties for addition need only be
true.true of at least one element of R. Because of the
To continue with the example, at the stage repre partitioningstrategy,propertiesarenotequallycon
sented by (4), onlye has been distinguished. ORI-5strastive for all referents. Therefore, distractors are
ENTATION,thenextattributeconsidered,isnotcon held in an associative array C, such that for all
trastiveforanyreferent. Onconsidering SIZE,smallr∈ R,C[r]isthesetofdistractorsforthatreferent
isfoundtobecontrastivefore ande ,andaddedto1 2atagivenstageintheprocedure. Contrastivenessis
DF and DF . However, SIZE isnotaddedto DF ,in1 2 3
5Thisonlyoccursifthe KBisincomplete,thatis,theresome spite of being present in two other fragments. This
entities have no TYPE, so thatR is not fully covered by the is because the probability functionp(SIZE,PPS) re
intendedreferentsofthe DFswhen TYPE isinitiallyadded.
turns a value below 0.5 (see Table 4, reflecting the
relatively low conceptual salience of this attribute.
The final description is the blue desk, the small redMean Mode PRP a better PRP than on +LOC. This apparent dis
+ LOC 7.716 7 .7 crepancy is partly due to variance in the edit dis IAbool − LOC 8.335 7 3.5
tance scores. For instance, because the Y attribute
+ LOC 4.345 4 6.8
IA washighestinthepreferenceorderfor+LOC,therepart − LOC 1.93 0 44.7
wereoccasionswhenbothreferentscouldbeidenti
fiedusingthesamevalueof Y,whichwasthereforeTable5: Editdistancescores
included by IA at first pass, before consideringbool
desk and the small blue sofa. This example illus disjunctions. Since Y was highly preferred by au
tratesthelimitssetonsemanticparallelismandsim thors (see Table 4), there was higher agreement on
ilarity: only attributes which are salient enough are these cases, compared to those where the values of
redundantlypropagatedacross DFs. Y were different for the two referents. In the latter
case, Y was only when disjunctions were consid
5 Evaluation ered, if at all. The worse performance of IA onpart
IA was compared to van Deemter’s IA (§1) +LOCisduetoalargerchoiceofattributes,alsore part bool
against human output in the evaluation sub corpus sulting in greater variance, and occasionally incur-
PL (N = 405). This was considered an ade ring higher Edit cost when the algorithm overspec 2
ified more than a human author. This is a poten quate comparison, since IA shares with the cur-bool
rent framework a genetic relationship with the IA. tialshortcomingofthepartitioningstrategyoutlined
Otherapproaches,suchasGardent’s(2002)brevity here,whenitisappliedtomorecomplexdomains.
oriented algorithm, would perform poorly on our (8) is an example of the algorithms’ output, in a
data. Asshownin§3,overspecificationisextremely domain where COLOUR sufficed to distinguish the
commoninpluraldescriptions,suggestingthatsuch referents,whichhaddifferentvaluesofthisattribute
astrategyisonthewrongtrack(butsee§6). (i.e. aninstanceofthe VDScondition). Theformula
IA and IA were each run over the domain returnedby IA (8a)isidenticaltothe(LF of)thepart bool part
representation paired with each corpus description. human authored description (with Edit score of 0).
Theoutputof IA isshownin(8b).The output logical form was compared to the LF bool
compiled from the XML representation of an au
(8) (a) fan∧green ∨ sofa∧blue
thor’s description (cf. Figure 1). LFs were repre
(b) sofa∨fan ∧small∧front∧ blue∨greensented as and or trees, and compared using the tree
editdistancealgorithmofShashaandZhang(1990).
As a result of IA ’s requiring a property or dis boolOnthismeasure,avalueof0indicatesidentity.
junction to be true of the the entire set of ref
Because only a subset of descriptions con
erents, COLOUR is not included until disjunctions
tain locative expressions, PL was divided into2
are considered, while values of SIZE and ORIEN-
a +LOC dataset (N = 148) and a −LOC
TATION are included at first pass. By contrast,
dataset (N = 257). The preference orders for
IA includes COLOUR before any other attributepart
both algorithms were (C>>O>>S) for−LOC and
apart from TYPE. Though the data analysis sug
(Y>>C>>X>>S>>O) for +LOC. These are sug
gests that overspecification is common in plural
gestedbytheattributeprobabilitiesinTable4.
descriptions, IA overspecifies with the ‘wrong’bool
Table5displaysthemeanEditscoreobtainedby
attributes (those which are relatively dispreferred
eachalgorithmonthetwodatasets,themodal(most
comparedto COLOUR). Therationalein IA istopart
frequent) value, and the perfect recall percentage
overspecify only if a property will enhance referent
(PRP), the proportion of Edit scores of 0, indicating
similarity, and is sufficiently salient. As for logical
perfectagreementwithanauthor.
form,theConjunctiveNormalFormoutputof IAboolAs the means and modes indicate, IA outper-part
increases the Edit score, given the larger number of
formed IA on both datasets, with a consistentlybool logicaloperatorsin(8b)comparedto(8a).
higher PRP (this coincides with the modal score in
the case of−LOC). Pairwise t−tests showed that 6 Summaryandconclusions
thetrendsweresignificantinboth+LOC (t(147) =
This paper presented an empirical study of plural9.28, p < .001) and−LOC (t(256) = 10.039,
reference, which showed that people undertake the
p<.001).
dual strategy of partitioning sets based on the basic
IA has a higher (worse) mean on−LOC, butbool
level TYPE of their elements and often redundantlypropagating attributes across disjuncts in adescrip References
tion, modulo their salience. Our algorithm per- A. Arts. 2004. Overspecification in Instructive
forms partitioning opportunistically, using KB in Texts. Ph.D.thesis,UniversityofTilburg.
formation, and extends the notion of utility of a
E. Belke and A. Meyer. 2002. Tracking the time
property beyond contrastiveness, utilising a statis course of multidimensional stimulus discrimina
tical model of attribute salience. Evaluation results
tion. EuropeanJournalofCognitivePsychology,
were positive, showing that these principles are on 14(2):237–266.
therighttrack. Thoughpresentedasageneralisation
R. Dale and E. Reiter. 1995. Computational inter-
of Dale and Reiter’s IA, the core aspects of the al
pretation of the Gricean maxims in the genera
gorithm are more widely applicable. The partition
tion of referring expressions. Cognitive Science,
ingstrategyisrelatedtoaproposalbyvanDeemter
19(8):233–263.
and Krahmer (2006), which searches exhaustively
Robert Dale. 1989. Cooking up referring expres
forapartitionofRwhoseelementscanbedescribed
sions. In Proc. ACL 89 .
non disjunctively. This differs from the present ap
H.J.EikmeyerandE.Ahlsen.` 1996. Thecognitive
proach in that it is non incremental and computa
process of referring to an object. In Proc. 16th
tionallycostly.
Scandinavian Conference on Linguistics.
The work described here highlights some open
C. Gardent. 2002. Generating minimal definite de
questions. In IA , a partition can be induced bypart
scriptions. In Proc. ACL 02 .
any property. An alternative would be to aggre
H. Horacek. 2004. On referring to sets of objects
gate same type fragments of a description, produc
naturally. In Proc. INLG0 04 .
ing NPs such as the blue and red chairs rather than
G. L. Murphy. 2002. The big book of concepts.
the blue chair and the red chair. Limits on syntac
MITPress,Cambridge,Ma.
tic complexity of NPs are bound to play a role here,
T. Pechmann. 1989. Incremental speech produc perhapsalonglinessuggestedbyHoracek(2004).
tion and referential overspecification. Linguis Thoughourdatashowsoverspecificationisoften
tics,27:89–110.desirable, a preference order can make this exces
I.Rock. 1983. TheLogicofPerception. MITPress,sive. InTable1,areferencetoalltheentitiesexcept
Cambridge,Ma.{e ,e} might use COLOUR, SIZE and ORIENTA-1 2
E. Rosch, C. B. Mervis, W. Gray, D. Johnson, andTION, ratherthanjust the large desks and sofas. As
P. Boyes Braem. 1976. Basic objects in naturalwe pointed out in§5, brevity oriented alternatives,
categories. Cognitive Psychology,8:382–439.such as Gardent (2002), would perform poorly on
D.ShashaandK.Zhang. 1990. Fastalgorithmsforour corpus data. Nevertheless, the balance between
unit cost editing distance between trees. Journalusing salient attributes and being concise remains
of Algorithms,11:581–621.unclear. Forexample,theextenttowhichaproperty
K.vanDeemterandE.Krahmer. 2006. Graphsandissharedamongreferentsmaybeinvolvedinthede
booleans: On the generation of referring expres cisiontouseanotherwisedispreferredattribute(e.g.
sions. InH.BuntandR.Muskens,editors, Com {e ,...,e} are all of the same SIZE), suggesting3 8
puting Meaning, volume III. Kluwer Academicthat our notion of similarity could be extended, and
Publishers,Dordrecht.takenbeyondapreference orderbasedstrategy.
K. van Deemter. 2002. Generating referring ex Anotherwayofsimplifyingdescriptionsinvolves
pressions: Booleanextensionsoftheincrementalnegation (the desks which are not red) (Horacek,
algorithm. Computational Linguistics, 28(1):37–2004). Though it can be handled relatively eas
52.ily (van Deemter, 2002), there are several untack
I.vanderSluis,A.Gatt,andK.vanDeemter. 2006.led empirical issues. In addition with those al
Manual for the TUNA corpus: Referring expres ready raised, and the arguments made in this pa
sions in two domains. Technical report, Univer-per, they shown that many open questions remain
sityofAberdeen.despite more than a decade of intensive research in
M.Wertheimer. 1938. Lawsoforganizationinper-GRE. Thesequestionsarelargelyempirical.
ceptualforms. In W.Ellis, editor, A Source Book
of Gestalt Psychology.Routledge&KeganPaul.

)