=Paper=
{{Paper
|id=Vol-1863/paper_18
|storemode=property
|title=Dynamic social choice for anaphora resolution
|pdfUrl=https://ceur-ws.org/Vol-1863/paper_18.pdf
|volume=Vol-1863
|authors=Sumiyo Nishiguchi
|dblpUrl=https://dblp.org/rec/conf/esslli/Nishiguchi17
}}
==Dynamic social choice for anaphora resolution==
https://ceur-ws.org/Vol-1863/paper_18.pdf
Dynamic Social Choice for Anaphora Resolution
Sumiyo Nishiguchi
Department of Liberal Arts, Faculty of Science Division I, Tokyo University of Science
1-3 Kagurazaka, Shinjuku, Tokyo 162-8601 Japan
Email: nishiguchi@rs.tus.ac.jp
Abstract In linguistic binding theory (Chomsky 1981,
Reinhart 1983), antecedents are called binders,
Disambiguation of pronoun reference has which bind bindees that are anaphoric pronouns,
been an important issue for both theoret- e.g., him or himself. Condition B is that pro-
ical and computational linguists. While nouns must be free in their local domain, mean-
linguistic theories on binding conditions ing that they are not bound by the antecedent by
eliminate impossible readings to a cer- means of coindexing and c-commanding relation.
tain extent, many inter-sentential anaphora C-command is roughly equivalent to precedence,
remain ambiguous. Nishiguchi (2011, with some restrictions.
2012a,b, 2014, 2016a,b) consider pronoun However, (3) is ambiguous in four ways and can
resolution as a social choice among dis- have either one of the following interpretations: i)
course participants which obeys Arrow’s John broke John’s leg, ii) John broke Bill’s leg, iii)
Impossibility Theorem (Arrow 1963). Bill broke Bill’s leg, or iv) Bill broke John’s leg.
This paper further discusses discourse up- He and his can be bound by either John or Bill.
date of Social Welfare Function which The binding theories have no way of disambiguat-
provides updated variable assignment. ing these pronouns since there is no way of know-
In (1), she has multiple candidates for its ing speaker intention. Proximity does not predict
antecedent— Emma, Lisa and Lisa’s mom. Prox- the different readings in (3) either.
imity and saliency of antecedents have been con-
(3) Anna: Billj is a good goalkeeper.
sidered to be key factors to decide (Leass 1991).
Kim: Johni said hei/j broke hisi/j leg re-
In (1), the most proximate antecedent her (Lisa)’s
cently.
mom is identified to be the antecedent for she.
(1) Frances: ...Not while Emma’s not here. You 1 Social Choice Theory
know Emma Although Social Choice Theory (Arrow 1963,
Billy: Mm. Moulin 1988, Taylor 2005, Gaertner 2009) has
Frances: she’s, she was walking with Lisa only been briefly mentioned in van Rooij (2011) in
and I weren’t there and her Mum sh– jus– , relation with interadjective comparison, Arrow’s
like she muc– , she mucks about a lot and Impossibility Theorem is obeyed in a social choice
she told Leigh that if he don’t serve her he’s of pronominal reference. Typically, social choice
gonna die, she’s gonna punch him right! theory explains collective decision making in case
However, proximity does not always resolve of voting and has solved the problems with ma-
referential ambiguity of pronouns. Him in (2a) un- jority decision. Preferences are ordering between
ambiguously means someone other than the clos- alternatives and should satisfy the following ax-
est John—some discourse-salient entity. In (2b), ioms. When R stands for a knowledge of all pairs
the pronoun is ambiguous. and x, y and z for alternatives,
Axiom 1. For all x and y, either xRy or yRx.
(2) a. Johni likes him{∗i/j6=i} .
Axiom 2. For all x, y, and z, xRy and yRz imply
b. Johni said he{i/j} likes himself{i/j} . xRz.
Axiom 1 states that the relation R is 2 Application to Pronoun Resolution
connected—every candidate is related to each
other. Relations that satisfy Axiom 2 are transi- SWF for pronoun resolution satisfies Arrow’s Im-
tive. In (4), N, a finite set of individuals or voters, possibility Theorem, or General Possibility The-
consists of five individuals and χ, a nonempty set orem, by satisfying Axioms 1, 2, Pareto Condi-
of alternatives or candidates, has three members. tion and IIA but demonstrating dictatorship. Pro-
Let L(χ) denote the set of all linear orders on noun resolution is compared with voting by multi-
χ. A profile R is a vector of linear orders, or ple voters, discourse participants. The candidates
preferences. Ri is a vector of preferences of an or choices would be different interpretation of the
individual i. NR sentence. In (5), the referent of he is ambigu-
x>y denotes the set of individuals
that prefer the candidate x to y. Supposing R the ous. Chris meant he to be Bob, while Naomi in-
profile given in this model, NR terpreted him to be John. As the disagreement on
o>c is a set of people
who prefers Obama to Clinton, that are, Anna, pronominal reference is consolidated in the dis-
Heather and George (cf. Endriss 2016). course, pronoun resolution is certainly a social
choice and Social Choice Function (SCF) decides
(4) a. N = {a, k, h, g, n} the antecedent.
b. χ = {o, c, m} (5) Chris: John said he broke his leg.
Naomi: Did he? John looked fine when I saw
c. R ∈ L(χ)N him this morning.
Chris: It is Bob who broke his leg.
d. NR
o>c = {a, h, g} Naomi: I thought you were talking about
John.
e. SWF F: L(χ)N → L(χ)
When individuals I = {c, n}, candidates χ = {j,
A social welfare function (SWF) F is a function
b}, Chris and Naomi’s ordering is jRc b ∧ bRn j,
which takes individual’s preferences and returns
denote the set of linear orders on χ by L(χ). Pref-
collective preference. Arrow demonstrated that
erences (or ballots) are taken to be elements of
any SWF for three or more alternatives the follow-
L(χ). A profile R ∈ L(χ)I is a vector of prefer-
ing conditions must be a dictatorship. Condition 2
ences. SCF or voting rule is a function F : L(χ)I
states that the relative ranking of two candidates
→ 2χ \∅ mapping a given profile to a nonempty
remains unchanged regardless of other candidates.
set of winners; e.g., a singleton set {b} for (5).
Theorem 1 (General Possibility Theorem (Impos- SWF is a function F : L(χ)I → L(χ) mapping any
sibility Theorem)). If there are at least three alter- given profile to a (single) collective preference or-
natives which the members of the society are free der. Although the preferences between the candi-
to order in any way, then every social welfare func- dates vary between the individuals, SWF returns
tion satisfying Conditions 1 and 2 and yielding a a single preference order and ambiguities are re-
social ordering satisfying Axioms 1 and 2 must be solved during the conversation.
either imposed or dictatorial. There are three possible antecedents for she in
Condition 1 (Pareto condition). A SWF F satisfies (1)—Emma (e), Lisa (l) and Lisa’s mother (m).
the Pareto condition if, whenever all individuals Let us say that Billy (b) prefers e to l, and also l
rank x above y, then so does society: NR to m to be the antecedent. On the other hand, the
x>y = N
implies xF(R)y speaker Francis (f) prefers m to l, and l to e ac-
cording to the proximity. All three candidates are
Condition 2 (Independence of irrelevant alterna- ordered in accordance with Axiom 1, i.e., eRb l ∧
tives (IIA)). A SWF F satisfies IIA if the relative lRb m and mRf l ∧ lRf e. Transitivity also holds
social ranking of two alternatives only depends on for pronoun antecedent preferences. Each of them
their relative individual rankings: NR R0
x>y = Nx>y implies eRb lRb m and mRf lRf e. SWF for pronoun
implies xF(R)y ⇔ xF(R’)y resolution also meets Pareto condition. When the
Condition 3 (Nondictatorship). There is no indi- interpretation of the addressees agrees with the
vidual i such that for every element in the domain one of the speaker, the decision of the society fol-
of rule f, ∀x, y ∈ X: xPi y → xPy (Sen 1979) lows. It is unlikely that pronouns refer to someone
else other than speaker’s intention and hearer’s in- (11) a. g = {: x refers to i}
terpretation. A SWF F satisfies IIA if the relative
social ranking of two alternatives only depends b. Information state σ consists of Social
on their relative individual rankings. Let us say Welfare Function F, Social Choice Func-
that the preference relations are denoted by R and tion g for variable assignment, individ-
R’. Assume that IIA does not hold and consider ual’s preferences R, individuals in the dis-
a dialogue in (7) where the relative rankings be- course X, a set of indices such as i, a set of
tween Bob and John is affected by irrelevant can- discourse participants V, and relation be-
didate Victor’s ranking. The social decision differs tween decisions B.
from the relative ranking between John and Bob of Σ = < F, G, R, X, I, V, B>
speaker and hearer, which does not happen, in (8).
(6) Chris: Bob is a good skier. But John said he (12) σ1 There were ooh’s and aah’s when
broke his leg. hex1 finished, and some unbridled laugh-
Naomi: Did he? Poor Bob! ter. Aileena was looking dubiously at hery1
husbandh but hex2 was in no mood to disap-
(7) Chris: Victor is a good skier and so is Bob. prove.
But John said he broke his leg.
σ2 Hex3 winked at the Duked and called
Naomi: Did he? Poor Bob!
across to himx4 , ‘What a grand thing, your
(8) bR’c vR’c j ∧ bR’n jR’n v 6→ jF(R)b Honour, to have a wedding without a min-
0
Then, N R R
b>j = N b>j implies bF(R)j ⇔ bF(R’)j
ister!’ The Duked did hisx5 stately bow at
that and then Donaldm was calling for an-
The speaker’s decision on pronominal reference
other song.
dictates the social preference. Even when there
is disagreement or misunderstanding, the speaker σ3 Some of the veteransv were on the
corrects unifies interpretation in general, as in (9). point of giving tongue but young Donald
Pronoun resolution is dominated, or dictated, by McCullochm was on hisx6 feet and moving
the speaker’s meaning. into the middle of the ring, hex7 was full of
himselfx8 , sparkling with mischief but with
(9) Chris: Bob is a good skier. But John said he
an undertow of ardour.
broke his leg.
Naomi: Did he? Poor Bob! σ4 ‘Duncan Ban MacIntyreb wrote a song for
Chris: No. I mean John broke his leg. hisx9 wife Maryr .
(10) xPc y → xPy σ5 I do not know if Alexl used it to court
his10 M aryr – hex11 must have used some-
Proof. Suppose: xPc y → ∼xPy, that is, xPc y →
thing —‘The joke was unconscious but crow-
yRx, where R is weak preference. However, the
ing laughter came from the young menn be-
dialogue normally proceeds jPc b → jPb as in (10).
side the whisky jar. (BNC A0N1311-1315,
Contradiction.
King Cameron)
Lemma 1. The social welfare function for pro- (13) a. g1= {, }
noun resolution is IIA and Pareto but is dictato- I = {a, r} (a: author, r: reader)
rial.
S = {a, h}
3 Dynamic Update of SCF
b. g2 = {, }
In linguistic literature, a variable assignment func-
tion g has been assumed to assign the referent to S = {a, h, d, m}
indices indexed to pronouns. For example, g may
c. g3 = { , , }
assign John to the variable x: g(x) = John. Now, g
can be considered to be SCF which selects a ref- S = {a, h, d, v, m}
erent for a pronoun socially. Let us define g and
the space as in (11). The assignment function g is d. g4 = {}
updated throughout the discourse as in (12). S = {a, h, d, v, m, b, r}
e. g5 = {, } (17) ‘...And Sarah Morgan likes the idea of An-
S ={a, h, d, v, m, b, r, l, n} gela marrying someone in the government.’
McLeish considered this cold and rational as-
f. [[hery ]]g1 = a sessment. ‘When did you last see her? Miss
Angela Morgan, I mean.’ (BNC AB9)
G is regarded as SCF. Also, the set of best ele-
ments S’ can be called its choice set of the whole Out of 18 instances of “I mean PNP” (PNP
set of alternaties, and is denoted g(S’, R) (cf. Sen stands for proper name” ) found with the query
1979) R is a sequence of individual’s preferences “I mean N” in BNC, 7 instances had a preceding
where Rx is a preference ordering of x. pronoun, the caraphor.
(14) g1(S, R) = {a, h}
References
g2(S, R) = {h, d}
Arrow, K. J.: 1963, Social Choice and Individ-
g3(S, R) = {m}
ual Values, 2 edn, Yale University Press, New
g4(S, R) = {b} Haven.
g5(S, R) = {l} Chomsky, N.: 1981, Lectures on Government and
As the author’s dynamic preferences change in Binding, Foris Publications, Dordrecht.
the discourse as in (15a), g is updated throughout Endriss, U.: 2016, Judgment aggregation, in
the discourse by means of a relation B. H. Moulin, F. Brandt, V. Conitzer, U. Endriss,
J. Lang and A. D. Procaccia (eds), Handbook of
(15) a. σ2: hRa d for hex3 ∧ dRa h for hex4 ∧
Computational Social Choice, Cambridge Uni-
dRa hIa m for hex5 (aIx b: x is indifferent
versity Press, pp. 399–426.
between a and b, ∧: dynamic conjunc-
tion) Gaertner, W.: 2009, A Primer in Social Choice
Theory. Revised edition, LSE Perspectives in
b. Social Decision: hRd ∧ dRh ∧ dRhIm Economic Analysis, Oxford University Press.
c. B(gn ,gn+1 ) Groenendijk, J. and Stokhof, M.: 1991, Dy-
namic predicate logic, Linguistics and Philos-
(16) Dynamic Social Welfare Function: ophy 14, 39–100.
Fn BFn+1 BFn+2 ,... Leass, H. J.: 1991, Anaphora resolution for ma-
4 Comparison with Other Studies chine translation: A study, IWBS Report 187.
Moulin, H.: 1988, Axioms of Cooperative De-
Dynamic Predicate Logic (Groenendijk and
cision Making, Econometric Society Mono-
Stokhof 1991) consider update semantics where
graphs, Cambridge University Press, Cam-
two states differ with respect to variable assign-
bridge.
ment. When h[x]g, the state g is updated with
respect to the assignment to x. The current pa- Nishiguchi, S.: 2011, Computational social choice
per consider an abstract function B between two for pronoun resolution, Ipsj sig-nl.
SCFs. Parkes and Procaccia (2013) model dy- Nishiguchi, S.: 2012a, Social choice for anaphora
namic decision making under constantly changing resolution, NLP2012 Proceedings, pp. 97–100.
preferences using Markov decision processes, in
Nishiguchi, S.: 2012b, Social choice for anaphora
which the states coincide with preference profiles
resolution, Society for Social Choice, New
and a policy corresponds to a social choice func-
Delhi.
tion.
Nishiguchi, S.: 2014, Application of social choice
5 Detection of Speaker Intention theory in pronoun resolution, Society for Social
In order to implement Dynamic Social Choice Choice, Boston College.
for pronoun disambiguation, speaker’s intention Nishiguchi, S.: 2016a, Social choice for anaphora
needs to be detected from the text. The phrases resolution, Studies in Liberal Arts and Sciences,
such as “I mean” are used to resolve ambiguity of Vol. 48, Tokyo University of Science, pp. 147–
pronominal reference in the discourse. as in (17). 156.
Nishiguchi, S.: 2016b, Social choice for disam-
biguation of pronominal reference, Society for
Social Choice, Lund University.
Parkes, D. C. and Procaccia, A. D.: 2013, Dy-
namic social choice with evolving preferences,
Proceedings of the 27th AAAI Conference on
Artificial Intelligence, Palo Alto, CA, pp. 767–
773.
Reinhart, T.: 1983, Anaphora and Semantic In-
terpretation, The University of Chicago Press,
Chicago.
Sen, A. K.: 1979, Collective Choice and Social
Welfare, North-Holland, Amsterdam.
Taylor, A.: 2005, Social Choice and the Mathe-
matics of Manipulation, Cambridge University
Press, Cambridge.
van Rooij, R.: 2011, Measurement and inter-
adjective comparisons, Journal of Semantics
28, 335–358.