# Fairness Vs. Personalization: Towards Equity in Epistemic Utility

Jennifer Chien<EMAIL_ADDRESS>UC San DiegoUSA and  David Danks
<EMAIL_ADDRESS>UC San DiegoUSA

###### Abstract.

The applications of personalized recommender systems are rapidly expanding:
encompassing social media, online shopping, search engine results, and more.
These systems offer a more efficient way to navigate the vast array of items
available. However, alongside this growth, there has been increased
recognition of the potential for algorithmic systems to exhibit and perpetuate
biases, risking unfairness in personalized domains. In this work, we explicate
the inherent tension between personalization and conventional implementations
of fairness. As an alternative, we propose equity to achieve fairness in the
context of epistemic utility. We provide a mapping between goals and practical
implementations and detail policy recommendations across key stakeholders to
forge a path towards achieving fairness in personalized systems.

fairness, personalization, recommender systems, equity, epistemic utility,
epistemic harms, policy

††booktitle: FAccTRec ’23: 5th FAccTRec Workshop: Responsible Recommendation,
Sept 18, 2023, Singapore††copyright: none

##  1\. Introduction

Personalized algorithmic systems are being increasingly deployed in a broad
range of sectors. These algorithms hold the potential to provide more
appropriate outputs on an individual basis by personalizing based on
preferences, values, needs, or environmental conditions. Most prominently,
recommender systems are now widely used to provide the most useful
recommendations to each individual in the given domain(Tufekci_2019, 1).

At the same time, we have seen a significant increase in the recognition that
algorithms can exhibit biases and produce unfair or unjust outcomes. There are
many different potential sources of bias in algorithms and models, and hence
many different responses may be appropriate or required. Algorithm development
and deployment efforts now typically recognize the possibility of algorithmic
bias, and the need to (often) do something to mitigate it(Solmaz2020, 2).

We contend that these two desiderata for algorithms – personalization and
fairness – stand in significant tension. At a high level, personalization is
fundamentally about treating each individual in distinct ways; the goal is to
_not_ give the same output for each individual, but rather to tailor the
outputs to their specific situation. In contrast, fairness is fundamentally
about treating individuals similarly; the algorithm ought to be “the same”, in
some sense, for everyone. Of course, this high-level gloss on the tension is
far too quick: for example, fairness allows for differential treatment or
outcomes, as long as it is based on morally or legally defensible grounds.
Nonetheless, these high-level observations point towards a tension that, we
contend, continues to hold when we look deeper. More specifically, we analyze
fairness in the context of personalized systems using the notion of _epistemic
utility_ – essentially, the benefit that an agent receives by an epistemic
improvement (e.g., reduction in uncertainty) – and provide both practical and
policy guidance about how to achieve fair, personalized systems.

##  2\. Preliminaries

#### Recommender System

We consider a recommender system as that which uses an algorithmic approach to
provide an ordering or prioritization for items based on relevance to a user.
This form of personalization is often based on their preferences, past
behavior, or similarities with other users with the overarching goal of
improving user experience and engagement.

#### Group Fairness

Algorithmic fairness is typically framed as metric parity111within some
tolerance as is legally permissible, e.g., the four-fifths
rule(watkins2022four, 3) across two or more relevantly comparable entities
such that the difference between them is deemed socially, legally, and/or
culturally irrelevant. For instance, group fairness may be defined as
demographic parity, meaning equality in the likelihood of a given outcome
conditioned on the group (e.g. gender, age, disability)(dwork2012fairness, 4).
Formally:

(1) $P(\hat{y}\leavevmode\nobreak\ |\leavevmode\nobreak\
g=g_{i})=P(\hat{y}\leavevmode\nobreak\ |\leavevmode\nobreak\ g=g_{j})\forall
g_{i},g_{j}\in\\{1,...,G\\}$

where $G$ is the total number of groups and $\hat{y}$ is the likelihood of a
given outcome.

#### Epistemic Utility

We define epistemic utility as the value or usefulness of information in terms
of improving knowledge, understanding, or beliefs. It encompasses the
epistemic benefits gained from acquiring accurate, reliable, and relevant
information. These benefits could, of course, enhance decision-making,
prediction, problem-solving, or overall intellectual development, but
epistemic utility refers only to the benefits in terms of the agent’s
epistemic state (even if those improvements do not immediately lead to
improved outcomes). It thereby captures the intrinsic value of acquiring
knowledge and understanding. It underscores the role of information as a
valuable resource for intellectual growth, social mobility and production, and
captures the motivational value of information for people’s behavior.

##  3\. Related Work

This work is most closely related to efforts to understand fairness in
recommender systems, many of which define fairness as parity in some
performance measure across some sensitive attribute (mehrotra2018towards, 5,
6, 7, 8, 9, 10). Methods for individual notions of fairness similarly require
a domain-specific similarity function and focus on trade-offs between
individual and group fairness(zhu2018fairness, 11, 12). In contrast, we start
from the position that fairness requires equity across all individuals, rather
than being defined solely through comparisons. This approach enables us to
account for cases of unfairness where everyone is worse off (including
situations with non-comparative injustices), not only those in which one group
is.

More specifically, prior work has aimed to ensure proportional representation
and exposure, often in e-commerce settings. Measures such as disparate
exposure and visibility still require access to sensitive or group attributes
(boratto2021interplay, 8, 9, 10). Calibration, in which the expected
proportions of predicted classes match those observed in available data,
implements group fairness without explicit knowledge of sensitive attribute
status(abdollahpouri2023calibrated, 13, 14, 15, 16, 17). However, its
application in domains such as news can contribute to hegemonic regimes of
representation, making it limited to applications where less diversity is
valued by users(deldjoo2023fairness, 17). Additionally, fairness definitions
that target disparities in utility compare average sensitive attribute group
performance rather than providing assurances for individuals or the entire
population as a whole (zhu2018fairness, 11, 18, 19, 20).

Concerns about unfairness in personalized algorithms is connected to research
on epistemic injustice(fricker2007epistemic, 21). The core concern in this
latter work is that epistemic limitations may impair an agent’s ability to
recognize or respond to injustice. For example, if an individual does not have
the concept of ‘racial discrimination’, then they might fail to detect its
occurrence despite suffering harms from it. That is, the injustice is not only
about what happens to the individual, but also about their (epistemic)
inability to recognize, understand, and respond to it. Personalized systems
can readily lead to different individuals having different information – in
fact, that is one goal of such systems – and so we expect that individuals
would develop different concepts as a result. Hence, personalized systems can
significantly raise the risks of epistemic injustice.

Research on over-personalization and information access is similarly closely
related. While the influence of personalization in filter bubbles and echo
chambers has been denied for purely technical systems
(courtois2018challenging, 22, 23, 24), when considering human interactions,
the influence becomes somewhat complex. This is, in part, due to significant
variability in how users engage with a site, accept or reject information, and
perceive the impartiality of the content they receive (dillahunt2015detecting,
25, 26, 27, 28, 29). Our research adopts a sociotechnical approach to define
and scope the problem, taking into account the concept of epistemic utility
and making reasonable assessments of human effort.

##  4\. Core tension: Personalization and standard approaches to fairness

Fairness is often defined as metric parity across similar groups or
individuals, where determining similarity across units remains an open
question. In search settings, one might start by grouping together individuals
with similar values and interests, as, on fairness grounds, they may be
expected to have a similar disambiguation or content recommendation
experience. However, determining values can be difficult to operationalize
because explicit and implicit preferences may be conflicting or difficult to
collect (charlesworth2022patterns, 30). In addition, the level of granularity
by which to measure such values remains unknown. In this section, we construct
arguments for why user similarity of values is difficult, impractical, or
perhaps even impossible to determine, thereby making similarity-based fairness
definitions difficult to deploy or conceptually impossible.

#### Sensitive attributes are problematic and coarse proxies for values.

The simplest approach to constructing “similar” groups for fairness
considerations could use sensitive attributes (i.e. race, ethnicity, gender,
age, religious affiliation, disability, etc). However, this approach assumes
that individuals with the same sensitive attributes not only face similar
struggles, lived experiences, discrimination, and prejudice, but also have
relevantly similar values. In practice, this approach would likely result in
the treatment of minority groups as monoliths – perhaps even as a homogeneous
‘Other’. This is problematic not only in its instrumental failures of
insufficient specificity and complexity, but also in its intrinsic treatment
of a single sensitive attribute as representative of all values. Additionally,
conditional groupings only ensure parity guarantees for the average member of
a group, not for each individual nor necessarily an individual that exists,
therefore enabling unfairness for anyone that doesn’t satisfy such
assumptions.

Taking an intersectional approach, i.e. considering subgroups of sensitive
attributes may better approximate similarity of values. Consider, for example,
race and gender, meaning groups such as “Black Women” and “White Men”. This
still considers an entire group of people homogeneously, thereby rendering the
plight of, for example, all Black Women into a singular experience. In the
extreme, considering all possible sub-groups across all sensitive attributes
faces practical challenges, as each subgroup becomes impractically small (for
data availability purposes), thereby reifying sensitive attributes in a
constant struggle for relative popularity and public consciousness
(kong2022intersectionally, 31).

#### User search history is noisy, underdetermines values, and can vary
temporally.

An alternative approach would be to use the individual’s behavior to determine
the relevant group for fairness considerations. For instance, in the context
of a search engine, we could condition on exact search history. Unfortunately,
this approach faces three open challenges which we highlight in the context of
search, though the problems naturally generalize to other systems that use
observed behavior to personalize on the basis of unobserved (inferred)
features.

First, not all search behaviors are equally informative. For example, a search
query may be made due to different situational demands (e.g., homework, third
party question) or may arise from very different motivations (e.g., devil’s
advocate vs. searching for validative or supporting arguments). Hence, a
specific history of search queries may or may not be informative about an
individual’s values; the history alone is not sufficient.

Second, even if search behaviors are “genuine,” they are noisy indicators for
the totality of an individual’s interests or values. For example, the
individual agent might not search for a topic they already have sufficient
information on, but it may still be a core value. More generally, consider two
users with identical search histories at any given point in time. Conditioning
on search history would imply that they should receive similar experiences.
However, it is highly unlikely that these individuals have the exact same sets
of values and interests: that is, multiple sets of values and interests could
be consistent with the observed behavior (i.e., the space of values are
underdetermined by the evidence). Therefore, since queries subject to the
limitations of observational data and missing contextual information,
conditioning on search history alone has the potential to greatly under-
specify an individual’s values.

Finally, search history provides no guarantees of stability over time.
Consider, again, two individuals with the same user history. Adding a
different element to each user’s search history could lead them to be placed
in fundamentally different groups. More generally, at any point in time, there
are infinitely many ways that a search history could progress, thereby making
it impossible to guarantee fairness over time for these two individuals, let
alone all. Fairness groupings not sensitive to the time and search history,
therefore, may not ever converge to fair groupings in the limit. This echoes a
similar problem in fairness research, where fairness constraints at each round
of deployment do not ensure long-term aggregate parity in the same metric
(hu2018short, 32). While this has not rendered particular fairness metrics
obsolete, this instability points to ambiguity in the extent to which fairness
must provide guarantees temporally.

##  5\. A Different Approach

###  5.1. Personalization

Delving further into the notion of a system tailored to each person’s needs,
let us define personalization. Given a search engine, companies may strive to
deliver a service that maximizes epistemic utility and convenience. In order
to avoid wasting time, resources, or eroding consumer patience, search engine
providers may optimize to disambiguate queries as efficiently as possible.
Increases in efficiency can be made by leveraging all accessible information
about a user. This may include search history, publicly available data, social
media profiles, and inferred or disclosed demographic information to
accurately disambiguate a user’s query. This motivates the following
definition:

###### Definition 5.1.

Infinite Personalization. Consider a platform that recommends relevant content
to a user $u_{j}$ tailored to their previous history $h_{j,t}$ at time $t$.
Since the space of all possible information is very large, for each piece of
content $c_{i}\in C$, the system calculates probabilities
$P(c_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ h_{j,t})$ estimating the
likelihood of relevance. We define infinite personalization as the phenomena
in which a system is allowed to produce extremely fine-grained
personalization. Formally, there exists some $c_{i}$ such that
$P(c_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ h_{j,t})<\theta$ and
$P(c_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ h_{j,t+\epsilon})<\theta$,
meaning that there exists some content such that it is arbitrarily improbable
$<\theta$ to recommend a particular piece of content $c_{i}$ to a user, even
if a user were to add $\epsilon$ queries to their search history.

For instance, user $u_{j}$ with a search history exclusively composed of cats
inputs “bengal toys” into a search engine and receives recommendations about
Bengal cat toys. We consider the system to be exhibiting infinite
personalization if the user can take $\epsilon$ queries about dogs (or
anything else) and still not receive a recommendation for Bengal dog toys when
searching “bengal toys”.

Having defined personalization and it’s effects in the extreme case, we now
define fairness as equity and provide motivation for the outcome we target.

###  5.2. Equity

In ensuring parity across similar groups, fairness guarantees are only made
across those deemed sufficiently similar. An equity-based approach, however,
centers around every individual achieving their desired outcome. Such
approaches promote social cohesion, collective liberation, and address long-
standing inequities, such as poverty, public health, social mobility, and
overall well-being. Moreover, they tackle concerns regarding temporal
stability and robustness by establishing a consistent criterion for each
deployment phase. Equity-based approaches lend themselves to audits,
legislation, and transparency, as they define a singular outcome requirement
for all users. An open challenge, however, is what metrics to define equity
with respect to, as each metric targets a different kind of unfairness.

Equity across _quality of information_ targets unfairness when one person gets
more utility from their query compared to a different query of another person.
For example, this type of equity requires that we equalize the number of
recommendations and quality of information provided for any given query.
However, this is infeasible as we cannot control the quantity of information
known for a given topic. Thus, given that there are infinitely many distinct
queries any user can make, ensuring that each query has the same number of
relevant articles would require perfect knowledge.

Equity in _speed of access to information_ targets unfairness when one person
receives the relevant information faster than another. This equalizes the
utility for every user by either: slowing down or acting intentionally
uncooperatively for queries that are more easily disambiguated, or speeding up
the service for “slower” queries. Both are infeasible. The former fails to
maximize overall utility and sacrifices function in the name of fairness. This
in turn renders adoption by stakeholders subject to capitalistic pressures
even more unlikely. The latter is also infeasible, as we cannot directly
control disambiguation rate and therefore speed up some queries over others.
More generally, information is an infinitely shareable resource, so providing
information to one person does not deprive someone else the benefit of that
same information. Therefore speed of access to information is a poor target
for an equity-based intervention.

In contrast, equity in _epistemic utility_ targets unfairness in personalized
access to the information resources. This is motivated by the intuition that
although we cannot directly control the availability of information or
disambiguation rate, everyone should have some baseline access to all
information. Thus, we propose an upper bound on the number of queries to
access to any piece of information. This means that if the information does
exist, all users should be able to access it by exerting a “reasonable” amount
of effort. This does not require that all queries have the same accessibility
or disambiguation, nor that all users be provided the exact same service. It
does provide a soft guarantee that everyone is able to achieve some base-level
epistemic utility without requiring the grouping or comparison of individuals
on the basis of their values, needs, or histories. Epistemic utility,
particularly through the internet, is recognized as a universal human right by
Article 19 of the Universal Declaration of Human Rights
(UNESCO_righttoinformation, 33), stating that, “Everyone has the right to
freedom…to seek, receive and impart information and ideas through any media
and regardless of frontiers.”

###### Definition 5.2.

$\epsilon$-Equity Fairness. Given a user $u_{j}$ with history $h_{j,t}$, we
define $\epsilon$-Equity fairness as the upper bound ($\epsilon$) of the
number of additions to the search history such that for any given content
$c_{i}\in C$, adding $\epsilon$ queries to the history will result in
$P(c_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\
h_{j,t+\epsilon})\geq\theta$, enabling the user to obtain the relevant
content. Here, we consider the case in which the relevant content does not
exist as out of scope and focus purely on access.

Embracing equity as a fundamental principle of fairness presents a range of
complex challenges. These challenges encompass defining a baseline level of
equity for all users, determining the pertinent factors that contribute to
establishing such a baseline, and deliberating whether these considerations
should be domain-specific or universally applicable. Rather than proposing a
singular standard, we propose adopting a heuristic operationalization that
prioritizes those who are most disadvantaged in terms of knowledge and
understanding. Our intention is not to argue for a strictly prioritarian
perspective, but that the incremental advancements can achieve the ultimate
goal of equity in the long-term. Thus, we advocate for equity as a guiding
concept to achieve equality by inductively reaching fairness in the limit.

Having established definitions infinite personalization and $\epsilon$-equity
fairness, next we flesh out the tension between the two.

##  6\. Inherent Conflict and Trade-offs

Infinite personalization, we posit, comes at a cost to $\epsilon$-equity
fairness. More explicitly, in infinite personalization, the relevance
probability of some information $c_{i}$ to a user can be less than $\theta$.
This is due to the effects of personalization: indexing and re-ranking for
efficient navigation across the vast space of information. However, this
violates $\epsilon$-equity fairness, as some information will be effectively
rendered unreachable within a fixed window of queries. We provide some
examples of trade-offs below:

  * •

Search engine personalization prioritizes results relative to a user’s input
query and prior history. For any given topic orthogonal to a user’s past
history, personalization may rank desired items far beyond the average,
expected, or typical number of results any given user explores, rendering it
practically infeasible to reach.

  * •

Social media serves many functions: dissemination of news and information,
entertainment, and social connection. Personalization in the extreme may
contribute to propagation of mis- and disinformation, echo chambers, filter
bubbles, radicalization, and social disconnection.

  * •

Github Copilot (developed by OpenAI) focuses on code completion, providing
suggestions for code lines or entire functions directly integrated into
interactive development environments. Here, personalization has the potential
to provide codebase-specific suggestions and completion, but may also infringe
on a coder’s ability construct novel functionality.

  * •

Google Bard is a language model for synthesizing insights for settings with a
wide range of opinions, perspectives, or no right answer. As an augmentation
to search-engine information retrieval, this may facilitate more efficient
ordering and disambiguation of search results, but may also infringe on access
to seemingly irrelevant information.

  * •

ChatGPT is a general-purpose large language model (LLM) designed to engage in
human-like conversations and answer a wide range of questions. Personalization
in an extreme case, may lead to conversational loops – or conversations that
remain within the scope of a single topic, rather than having the flexibility
to move between topics despite a user’s prompt or request. 222Here we list
several examples that use LLMs due to their relevance to personalization,
information synthesis and curation, and appeals to human-language usability.
We acknowledge that there are many open relevant problems related to
personalization, such as contribution or exacerbation of representational
harms. For the scope of this work, we focus on how such systems can impact
access to information.

The key takeaway of this list is not that personalization necessitates
unfairness or inequity, nor that fairness is not achievable in personalized
systems. Rather, to emphasize that personalization _without consideration of
fairness_ can readily lead to systems that deny some individuals a base-level
of expected epistemic utility.

##  7\. Policy Goals and Examples of Implementations

While this conceptual analysis provides guidance about how best to think about
fairness in the context of personalized algorithms, it does not provide
guidance about how to achieve fairer, less biased systems. As we turn to more
practical recommendations, we start by considering key stakeholders and their
associated roles (Table 1). This creates a lexicon and clarifies the expected
function of each stakeholder.

Stakeholder |  Role
---|---
Government |  Develop guidelines, principles, procedures, regulations, and standards for safe, sustainable deployment. May hold the power to create structural supporting systems directly within the government or financially support external systems of enforcement of such regulations. May also enact other means of operationalizing policy, such as hosting interdisciplinary research summits or sending representatives to build collaborations with other stakeholders to better inform outputs. This stakeholder may also set roles and norms for other stakeholder responsibilities and consequences.
Civil Society |  Conduct evaluations and investigations of algorithms and software developed by others. This stakeholder may serve as an external, third-party entity for conducting unbiased evaluations of performance and compliance with policy. May be responsible for developing novel methods of measurement.
Industry |  Implement technical methods, tools, and technological innovations, usually manifesting as a consumer-facing service or product. May be subject to practical implementation constraints (i.e. financial, competition, or legislative). While a particular product may be theoretically feasible, it may not be practically viable or sustainable for a company to produce. Responsibilities may also include foreseeing and adequately mitigating harms of deployed products on those directly and indirectly affected.
Academia (broad) |  Develop and implement technical, theoretical, and conceptual knowledge without direct consideration of profits. Results can include work that builds upon understanding, implications, or evaluation methods (i.e. downstream impacts, sociotechnical approaches). This stakeholder has the potential to act as an unbiased actor in developing best-practices for sustainable, long-term practices, potentially at the direct cost of profits (i.e. considering environmental, social, and cultural norms and influences).
General Public |  Provide input, feedback, criticism, and opinions on direction and alignment with values for research and innovation via implicit and explicit signals on the order of communities, groups, and/or individuals. Public support (or lack thereof) can be collected across a multitude of avenues and granularities, including financial support, interest, engagement, collective action, protests, organizations, and projects.

Table 1. Stakeholder Roles. We define the expected roles of stakeholders for
clarity of responsibilities enumerated in Table 2. We note that these
responsibilities are not restrictive. There are many ways in which one
stakeholder may overlap or even take over the responsibilities of another. For
instance, if a company develops a policy for user privacy while it’s
competitors do not, self-imposed constraints on data collection may impact
their product performance. However, as this design value receives public
support, this can become a standard competitive service without the
intervention of government or civil society.

Each of these stakeholders has a wide range of actions available that can lead
to fairer personalized systems (see Table 2). These actions include a wide
range of governance mechanisms, ranging from hard (e.g., regulation) to soft
(e.g., social norms). We emphasize that there is no single response to “fix”
unfairness in personalized systems: inevitably, many interdependent actions
will likely need to be taken in order to make progress on this problem.
Moreover, these are by no means intended to be exhaustive, but rather provide
a grounded starting point that emphasizes the necessity of cross-stakeholder
collaborations.

Goal |  Example Implementation/Operationalization
---|---
Mitigation |  Industry, Academia: Develop algorithms that facilitate connections between disjoint parts of the data manifold. This might be analogous to connecting different parts of the internet together through links, but done by creating arbitrary injections that fabricate similarities, covariances, or links between disjoint parts of the training data.
|  Government: Construct structural incentives (financial,
prestige/recognition, standards) for achieving baseline levels of
interconnectivity to ensure equitable access.
Audit |  Industry, Academia, Civil Society: Develop measures that quantify epistemic utility for users using a range of behaviors and data (e.g. tool use, experienced frustration, time to complete a task, etc.). Produce formal, domain-specific representations of distributions of utility, such as non-uniform distributions being indicators of threats to fairness. Measure utility and study barriers to utility for non-users and those who have left the platform.
|  Civil Society: Report the utility distributions for non-users to compare
against those that are already using the service.
|  Academia: Defining and measuring downstream impact may be essential to
thorough quantification of disparities and unfairness. Downstream impacts such
as social influences on platform usage can be influenced by an individual’s
experience.
|  Government: Regulation for timing and structure of fairness audits for
personalized systems, including guidance on composition of internal and
external stakeholders.
Transparency |  Industry, Civil Society: Disclosure of aforementioned distributions of utility across various groups of users. Reports should include comments about whether these distributions are problematic, what are the proposed solutions, and on what timeline.
|  Government: Clear consequences and/or reparations for users affected
throughout improvement and for continued negligence.
|  General Public: Active engagement and feedback on reports to inform
appropriate consequences and informed public (dis)favor.
Individual Control |  Industry, Academia: Design control mechanisms over the degree of exploration to a query when serving recommendations. This may include prompting users for additional input before producing a prediction. Alternatively, allowing users to reset their history or set manual preferences over personalization filters.
|  Government: Regulation and enforcement of satisfaction and compliance.
|  General Public: Participation and feedback on norm setting of what features
should be available, how accessible services should be, determine embedded
values such as degree of “reasonableness” that are feasible and realistic for
all users.
Education & Awareness |  Industry, Academia, Government, General Public: Workshops and training sessions can facilitate comprehension of the dangers, limitations, and better calibrate users to appropriate expectations of functionality. These workshops can include education on rights and how to advocate for them. For instance, if companies fail to comply, where can people file their grievances so they can be aggregated and collectively analyzed?
|  Industry, Academia, Civil Society: Development of interactive tools that
enable visualization and comparison of an individual’s utility compared to the
general population or those relevantly comparable.
|  Civil society, Government: Regulation and continued measurement to ensure
such tools flag anomalous data and ensure improvement within some time-frame.
Create and publicly release of reports of corrections, adjustments, and
investigations made to remedy grievances.

Table 2. Example Policy Interventions and Goals by Stakeholder. Although we
separate actions by stakeholders, we emphasize that these goals require
collaborations and contributions across multiple stakeholders to achieve such
solutions.

## References

  * (1) Zeynep Tufekci  “How recommendation algorithms run the world”  In _Wired_ Conde Nast, 2019  URL: https://www.wired.com/story/how-recommendation-algorithms-run-the-world/
  * (2) Gurkan Solmaz, Jesmin Jahan Tithi and Juan Miguel de Joya  “Why algorithmic fairness?”  In _ACM Selects_ ACM, 2020  URL: https://selects.acm.org/selections/why-algorithmic-fairness
  * (3) Elizabeth Anne Watkins, Michael McKenna and Jiahao Chen  “The four-fifths rule is not disparate impact: a woeful tale of epistemic trespassing in algorithmic fairness”  In _arXiv preprint arXiv:2202.09519_ , 2022
  * (4) Cynthia Dwork et al.  “Fairness through awareness”  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , 2012, pp. 214–226
  * (5) Rishabh Mehrotra et al.  “Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems”  In _Proceedings of the 27th acm international conference on information and knowledge management_ , 2018, pp. 2243–2251
  * (6) Nasim Sonboli et al.  “Opportunistic multi-aspect fairness through personalized re-ranking”  In _Proceedings of the 28th ACM Conference on User Modeling, Adaptation and Personalization_ , 2020, pp. 239–247
  * (7) Weiwen Liu et al.  “Personalized fairness-aware re-ranking for microlending”  In _Proceedings of the 13th ACM Conference on Recommender Systems_ , 2019, pp. 467–471
  * (8) Ludovico Boratto, Gianni Fenu and Mirko Marras  “Interplay between upsampling and regularization for provider fairness in recommender systems”  In _User Modeling and User-Adapted Interaction_ 31.3 Springer, 2021, pp. 421–455
  * (9) Elizabeth Gómez et al.  “The winner takes it all: geographic imbalance and provider (un) fairness in educational recommender systems”  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2021, pp. 1808–1812
  * (10) Abhisek Dash et al.  “When the umpire is also a player: Bias in private label product recommendations on e-commerce marketplaces”  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , 2021, pp. 873–884
  * (11) Ziwei Zhu, Xia Hu and James Caverlee  “Fairness-aware tensor-based recommendation”  In _Proceedings of the 27th ACM international conference on information and knowledge management_ , 2018, pp. 1153–1162
  * (12) Bora Edizel et al.  “FaiRecSys: mitigating algorithmic bias in recommender systems”  In _International Journal of Data Science and Analytics_ 9 Springer, 2020, pp. 197–213
  * (13) Himan Abdollahpouri et al.  “Calibrated recommendations as a minimum-cost flow problem”  In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_ , 2023, pp. 571–579
  * (14) Himan Abdollahpouri et al.  “User-centered evaluation of popularity bias in recommender systems”  In _Proceedings of the 29th ACM Conference on User Modeling, Adaptation and Personalization_ , 2021, pp. 119–129
  * (15) Bruna Wundervald  “Cluster-based quotas for fairness improvements in music recommendation systems”  In _International Journal of Multimedia Information Retrieval_ 10.1 Springer, 2021, pp. 25–32
  * (16) Diego Corrêa Silva, Marcelo Garcia Manzato and Frederico Araújo Durão  “Exploiting personalized calibration and metrics for fairness recommendation”  In _Expert Systems with Applications_ 181 Elsevier, 2021, pp. 115112
  * (17) Yashar Deldjoo et al.  “Fairness in recommender systems: research landscape and future directions”  In _User Modeling and User-Adapted Interaction_ Springer, 2023, pp. 1–50
  * (18) Yashar Deldjoo et al.  “Recommender systems fairness evaluation via generalized cross entropy”  In _arXiv preprint arXiv:1908.06708_ , 2019
  * (19) Yashar Deldjoo, Tommaso Di Noia and Felice Antonio Merra  “Adversarial machine learning in recommender systems (aml-recsys)”  In _Proceedings of the 13th International Conference on Web Search and Data Mining_ , 2020, pp. 869–872
  * (20) Yunqi Li et al.  “User-oriented fairness in recommendation”  In _Proceedings of the Web Conference 2021_ , 2021, pp. 624–632
  * (21) Miranda Fricker  “Epistemic injustice: Power and the ethics of knowing”  Oxford University Press, 2007
  * (22) Cédric Courtois, Laura Slechten and Lennert Coenen  “Challenging Google Search filter bubbles in social and political information: Disconforming evidence from a digital methods case study”  In _Telematics and Informatics_ 35.7 Elsevier, 2018, pp. 2006–2015
  * (23) William H Dutton, Bianca C Reisdorf, Grant Blank and Elizabeth Dubois  “Searching through filter bubbles, echo chambers”  In _Society and the internet: How networks of information and communication are changing our lives_ , 2019, pp. 228
  * (24) Efrat Nechushtai and Seth C Lewis  “What kind of news gatekeepers do we want machines to be? Filter bubbles, fragmentation, and the normative dimensions of algorithmic recommendations”  In _Computers in human behavior_ 90 Elsevier, 2019, pp. 298–307
  * (25) Tawanna R Dillahunt, Christopher A Brooks and Samarth Gulati  “Detecting and visualizing filter bubbles in Google and Bing”  In _Proceedings of the 33rd Annual ACM Conference Extended Abstracts on Human Factors in Computing Systems_ , 2015, pp. 1851–1856
  * (26) Axel G Ekström, Diederick C Niehorster and Erik J Olsson  “Self-imposed filter bubbles: Selective attention and exposure in online search”  In _Computers in Human Behavior Reports_ 7 Elsevier, 2022, pp. 100226
  * (27) Mykola Makhortykh and Mariëlle Wijermars  “Can filter bubbles protect information freedom? Discussions of algorithmic news recommenders in Eastern Europe”  In _Digital Journalism_ Taylor & Francis, 2021, pp. 1–25
  * (28) Jaime Teevan  “How people recall, recognize, and reuse search results”  In _ACM Transactions on Information Systems (TOIS)_ 26.4 ACM New York, NY, USA, 2008, pp. 1–27
  * (29) Kelly Shelton  “Council post: The value of search results rankings”  In _Forbes_ Forbes Magazine, 2017  URL: https://www.forbes.com/sites/forbesagencycouncil/2017/10/30/the-value-of-search-results-rankings/
  * (30) Tessa ES Charlesworth and Mahzarin R Banaji  “Patterns of implicit and explicit attitudes: IV. change and stability from 2007 to 2020”  In _Psychological Science_ 33.9 SAGE Publications Sage CA: Los Angeles, CA, 2022, pp. 1347–1371
  * (31) Youjin Kong  “Are “Intersectionally Fair” AI Algorithms Really Fair to Women of Color? A Philosophical Analysis”  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , 2022, pp. 485–494
  * (32) Lily Hu and Yiling Chen  “A short-term intervention for long-term fairness in the labor market”  In _Proceedings of the 2018 World Wide Web Conference_ , 2018, pp. 1389–1398
  * (33) In _UNESCO.org_ URL: https://www.unesco.org/en/right-information


# Contextual Semantic Parsing for Multilingual Task-Oriented Dialogues

Mehrad Moradshahi Victoria Tsai Giovanni Campagna Monica S. Lam
Computer Science Department
Stanford University
Stanford, California, USA
<EMAIL_ADDRESS>

###### Abstract

Robust state tracking for task-oriented dialogue systems currently remains
restricted to a few popular languages. This paper shows that given a large-
scale dialogue data set in one language, we can automatically produce an
effective semantic parser for other languages using machine translation. We
propose automatic translation of dialogue datasets with alignment to ensure
faithful translation of slot values and eliminate costly human supervision
used in previous benchmarks. We also propose a new contextual semantic parsing
model, which encodes the formal slots and values, and only the last agent and
user utterances. We show that the succinct representation reduces the
compounding effect of translation errors, without harming the accuracy in
practice.

We evaluate our approach on several dialogue state tracking benchmarks. On
RiSAWOZ, CrossWOZ, CrossWOZ-EN, and MultiWOZ-ZH datasets we improve the state
of the art by 11%, 17%, 20%, and 0.3% in joint goal accuracy. We present a
comprehensive error analysis for all three datasets showing erroneous
annotations can obscure judgments on the quality of the model.

Finally, we present RiSAWOZ English and German datasets, created using our
translation methodology. On these datasets, accuracy is within 11% of the
original showing that high-accuracy multilingual dialogue datasets are
possible without relying on expensive human annotations.

##  1 Introduction

Tremendous effort has gone into the research and development of task-oriented
dialogue agents for English and a few other major languages in recent years. A
methodology that can transfer the effort to other languages automatically will
greatly benefit the large population of speakers of the many other languages
in the world.

Underlying an effective TOD agent is dialogue state tracking, the task of
predicting a formal representation of the conversation sufficient for the
dialogue agent to reply, in the form of slots and values. However, DST
currently remains restricted to a few popular languages Razumovskaia et al.
(2021). Traditional DST agents require large hand-annotated Wizard-of-Oz
Kelley (1984) datasets for training, which are prohibitively labor-intensive
to produce in most languages Gunasekara et al. (2020). Large, multi-domain WOZ
datasets are only available in English and Chinese Quan et al. (2020); Ye et
al. (2021a).

The contributions of this paper are as follows:

1\. We propose an automatic technique to build high-quality multilingual data
sets using machine translation. Machine translation has been shown effective
for localizing question-answering agents Moradshahi et al. (2020). It shows
that for open ontology datasets, we need to use an alignment model to properly
translate entities in the source language to entities in the target language.
This paper shows that alignment is necessary even for closed ontology datasets
and dialogues.

Furthermore, we improve alignment to address these challenging issues we
discovered unique to dialogues: (1) Translation errors accumulate and can
prevent a correct parse for the rest of the dialogue; (2) There are logical
dependencies between slot values across different turns; (3) Utterances are
generally longer and more complex carrying multiple entities. We found that
alignment improves the accuracy on the RiSAWOZ benchmark by 45.6%. This
technique eliminates the cost of human post-editing used on all previous
translation benchmarks, and can improve machine translation quality on other
tasks too.

2\. We created the first automatically obtained, high-quality, translated
dialogue data sets: RiSAWOZ-EN-auto (English) and RiSAWOZ-DE-auto (German)
datasets. They show only an 8% drop in accuracy compared to the original.
RiSAWOZ-EN-auto and RiSAWOZ-DE-auto will be released upon publication.

3\. We show that the accumulation of translation and annotation errors across
turns can be mitigated with a Contextual Semantic Parsing (CSP) model for
state tracking. We propose a BART-CSP model, a seq-to-seq based on BART, that
encodes the belief state, and the last agent and user utterances, rather than
the full history of utterances.

BART-CSP improves SOTA on RiSAWOZ Quan et al. (2020) and CrossWOZ Zhu et al.
(2020), two large-scale multi-domain WoZ dialogue datasets, by 10.7% and 17%
in Joint Goal Accuracy(JGA). Notably, BART-CSP is more effective on translated
data as evident by bigger performance improvement: on RiSAWOZ-EN-auto and
RiSAWOZ-DE-auto datasets, automatically translated versions of RiSAWOZ, BART-
CSP improves SOTA by 32.4% and 52.5%.

##  2 Related Work

###  2.1 Dialogue State Tracking

Dialogue state tracking (DST) refers to the task of predicting a formal state
of a dialogue at its current turn, as a set of slot-value pairs at every turn.
State-of-the-art approaches apply large transformer networks Peng et al.
(2020); Hosseini-Asl et al. (2020) to encode the full dialogue history in
order to predict slot values. Other approaches include question-answering
models Gao et al. (2019), ontology matching in the finite case Lee et al.
(2019), or pointer-generator networks Wu et al. (2019). Both zero-shot cross-
lingual DST transfer Ponti et al. (2018); Chen et al. (2018) and multilingual
knowledge distillation Hinton et al. (2015); Tan et al. (2019) have been
investigated; however, training with translated data is the dominant approach,
outperforming zero-shot and few-shot methods.

###  2.2 Contextual Semantic Parsing

Alternatively to encoding the full dialogue history, previous work has
proposed including the state as context Lei et al. (2018); Heck et al. (2020);
Ye et al. (2021b) together with the last agent and user utterance. Recently,
Cheng et al. (2020b) proposed replacing the agent utterance with a formal
representation as well. Existing models rely on custom encoder architectures
and loss functions for the state Heck et al. (2020). Our formulation of CSP is
different since we encode the formal dialogue state directly as text, which
simplifies the architecture and makes better use of the pretrained model’s
understanding of natural text.

Previous work also applied rule-based state trackers that compute the state
based on the agent and user dialogue acts Schulz et al. (2017); Zhong et al.
(2018); Zhu et al. (2020). Such techniques cannot handle state changes outside
of a state machine defined ahead of time and do not achieve state-of-the-art
accuracy on WOZ dialogues.

###  2.3 Multilingual Dialogues

Several multilingual dialogue benchmarks have been created over the past few
years. Dialogue State Tracking Challenge (DSTC) has released several datasets
Kim et al. (2016); Hori et al. (2019); Gunasekara et al. (2020), covering only
a few domains and languages. CrossWOZ Zhu et al. (2020) and RiSAWOZ Quan et
al. (2020) are Chinese datasets collected through crowdsourcing which is
expensive and human errors degrade quality. The creation of affordable high-
quality datasets for other languages still remains a challenge Razumovskaia et
al. (2021).

##  3 Task Setting

We are interested in the dialogue state tracking task, in which the goal is to
predict a formal representation of a conversation up to a certain point, also
known as belief state, consisting of the slots that were mentioned in the
dialogue and their value. At the beginning of the conversation, the belief
state is empty, and it grows as the conversation progresses, accumulating the
slots that were mentioned across all turns prior.

Formally, the problem is formulated given a predefined set of slots
$s_{1},s_{2},\ldots s_{n}$ (such as “restaurant name”, “restaurant food”,
etc.). Each slot has one value taken from the ontology
$v_{1},v_{2},\ldots,v_{n}$. The ontology contains the legitimate values for
the slot from the database (i.e. the list of restaurant names or restaurant
cuisines), as well as the special values “none” indicating the slot was not
mentioned, and “dontcare” indicating the slot was explicitly mentioned by the
user but the user has no preference.

Therefore, given a partial conversation history composed of turns
$x_{1},x_{2},\ldots x_{t}$, where each turn consists of an agent response
($a_{t}$) and user utterance ($u_{t}$), the task is to predict the belief
state:  $b_{n}(x_{1},\ldots x_{t})=\\{s_{1}=v_{1,t},s_{1}=v_{2,t},\ldots
s_{n}=v_{n,t}\\}$ where $n$ is the number of slots and $v_{i,t}$ is the value
of the slot $s_{i}$ up to turn $t$ of the conversation. Note that the slot
could be mentioned immediately at turn $t$, or in any of the turns before.

Figure 1: Visualization of difference between inputs of CSP and traditional
DST models. While previous model encode the full history of the dialogue, CSP
only encodes the current state and turn.

##  4 Reducing Translation Noise

Key to the success of the dialogue state tracking is a precise and consistent
annotation of the belief state at every turn. This is challenging in the
multilingual setting, when we apply automatic translation to produce new
training sets for DST: (1) translation can be ungrammatical, incorrect, or
introduce spurious information, and (2) the new annotation (in the target,
translated ontology) can diverge from the translation of sentence, for example
when the same value can be referred to in multiple ways in the target
language.

We refer to the error introduced in translation collectively as translation
noise. We posit that translation noise is the reason for poorer performance in
existing translated dialogue datasets, compared to the same model on the
dialogue dataset in the source language. In this section, we describe our
methods to reduce translation noise.

###  4.1 Alignment

A major source of translation noise is due to mismatches between the
translation of an entity by itself and in sentence. For instance, given a
Chinese sentence that refers to an utterance containing the word “aquarium”
(水族馆), incorrect translation may result in “ocean museum” in the English
utterance, which does not match the slot value “aquarium” in the ontology and
annotation anymore. Slot values may also get dropped or transliterated.

Translation with alignment was previously proposed by Moradshahi et al. (2020)
for tackling open-ontology multilingual semantic parsing by preserving
entities during translation and replacing after with local entity values. We
show alignment is beneficial also for a finite (closed) ontology.

The dialogue setting is more challenging for alignment since the replacement
needs to consider the dependency between slot values across turns. For
instance, the corresponding price range for a fast food restaurant should be
cheap, or a speaker looking for an attraction to go to with his girlfriend
wants a place where best-for-crowd = “lover’s date”. Furthermore, utterances
are generally longer and more complex containing multiple entities.

We have made several changes in alignment to address these issues: (1) We use
a dictionary for translating the dependent slots to ensure relations are
preserved. For all other slots, we randomly replace them with values from the
target language ontology similar to previous work. (2) In previous work,
quotation marks were used to mark boundary of entities and used to retrieve
alignment between tokens in the input and output. Dialogues contain longer
utterances with multiple entities per turn and we found translation of
quotation marks to be inconsistent. Instead, we omit those marks before
translation and purely rely on cross-attention between subwords to compute
alignment. (3) We observed alignment does poorly on digits and often misplaces
them in the output. We apply some heuristics to retrieve spans for numbers,
dates, and time slots if present in the output and omit alignment if
successful. (4) NMT quality is better on shorter texts Hu et al. (2020) when
there are fewer entities to align. We break down utterances into individual
sentences before translation.

We translate MultiWOZ English dev set to Chinese with the new and previous
alignment approaches using MBART-MMT (see section 5.3 for details). The new
approach improves BLEU score by 8 points using MultiWOZ-ZH as reference.

###  4.2 Contextual Semantic Parsing

Previous work on dialogue state tracking encodes all turns up to the current
one using a neural model, which then predicts the value for each slot. Hence,
the input of the model consists exclusively of natural language, and grows as
the conversation grows, accumulating any translation noise.

At the same time, we observe that the belief state at turn $t$ ($b_{t}$) can
be computed from the belief state at turn $t-1$ and the slots mentioned in the
utterances at turn $t$. Hence, we propose to use a contextual semantic parser
(CSP) for dialogue state tracking that computes
$P(b_{t}|a_{t};u_{t};b_{t-1})$.

The CSP model is applied to the dialogue state tracking task by iteratively
predicting the belief state of all turns, starting from $b_{0}$, the initial
state which consists of all empty slots.

The CSP formulation condenses the dialogue history into a formal
representation of fixed length. Because the representation does not grow with
the dialogue, it does not suffer from accumulation of translation noise.

Our CSP model is based on Seq2Seq Transformer models BART Lewis et al. (2019)
for English and MBART Liu et al. (2020) for all others. Here we refer to them
as CSP-BART for simplicity.

The model encodes the belief state as a textual sequence of slot names and
slot values. This encoding is concatenated to the agent utterance and user
utterance, and fed to the model to predict the belief state at the end of the
turn (Fig. 2). Our model differs from previous CSP models Cheng et al. (2020a)
because we encode the belief state directly as text, which simplifies the
architecture and allows for better use of BART pretraining.

Figure 2: Contextual Semantic Parser model. We use BART for English and MBART
for Chinese and German as the seq2seq model.

##  5 Experiments

Our experiments are designed to answer the following questions: 1) How well
does CSP perform on WOZ datasets compared to DST models that encode the full
conversation history? 2) Is our approach effective to reduce dataset
translation noise?

###  5.1 Datasets

We evaluate our models on the RiSAWOZ Quan et al. (2020), MultiWOZ
Budzianowski et al. (2018); Eric et al. (2019), and CrossWOZ Zhu et al. (2020)
datasets and their available translated versions: MultiWOZ Chinese Li et al.
(2021), CrossWOZ English Li et al. (2021). These particular datasets were
chosen because they are large Wizard-of-OZ dialogue datasets and therefore
more natural and representative of task-oriented dialogues. Additionally, we
use our methodology to create the RiSAWOZ English and German datasets.

RiSAWOZ Quan et al. (2020) is a Chinese-language WOZ dataset of 11k annotated
dialogues and over 150k utterances spanning the 12 domains of attraction,
restaurant, hotel, flight, train, weather, movie, TV, computer, car, hospital,
and courses. Dialogues are formed from both single-domain and multi-domain
goals, and annotated with dialogue states, dialogue acts, and coreference
clusters.

MultiWOZ is an English-language WOZ dataset of 10k single- and multi-domain
dialogues spanning the following 7 domains: taxi, restaurant, hotel,
attraction, train, police, hospital. Following prior work with this dataset
Lee et al. (2019); Kim et al. (2019), we drop hospital and police from the
training set as they are not included in the validation and test set. After
the release of MultiWOZ 2.0 Budzianowski et al. (2018), later iterations Eric
et al. (2019); Zang et al. (2020); Han et al. (2020) corrected some of the
misannotations.

CrossWOZ is a Chinese-language WOZ dataset of 6k dialogues and over 102k
utterances spanning the same 5 domains as the MultiWOZ validation and test
sets: hotel, restaurant, attraction, metro, and taxi. CrossWOZ dialogues are
annotated with dialogue states and dialogue acts, and average over 3.24
domains per dialogue, as opposed to the 1.80 of MultiWOZ.

For DSTC-9, Google NMT was used to translate MultiWOZ 2.1 to Chinese and
CrossWOZ to English Gunasekara et al. (2020); Li et al. (2021). To ensure
translations of slot values in the dialog are faithful to the ontology, they
replace them with their translations from a dictionary before feeding it to
the NMT. This approach creates mixed-language sentences, shifting input
distribution away from what public NMTs have been trained on, and thus
reducing quality Moradshahi et al. (2020). Note that human translators were
employed to proofread the translations and check certain slots to ensure
values are correctly translated.

Table 1 shows a comparison of statistics for the training split of datasets
used or created in this work. All the datasets have a closed ontology: the
same entities appear in the train, validation, and test sets.

###  5.2 Models

We compare BART-CSP results against SOTA for each dataset. Models include the
following:

  * •

TRADE Wu et al. (2019) uses a sequence-to-sequence architecture that encodes
all utterances in the dialogue. It uses a pointer-generator to output the
value of each slot.

  * •

MLCSG Quan and Xiong (2020) extends TRADE by improving modeling of long
contexts through a multi-task learning framework.

  * •

SOM Kim et al. (2019) considers dialogue state as an explicit fixed-sized
memory and uses state operation to selectively update slot values at each
turn.

  * •

SUMBT Lee et al. (2019) applies a BERT encoder to each utterance on the
dialogue and a recurrent network to compute a representation of the whole
dialogue, which is then matched against the ontology of each slot. jointly
learning dialogue states and agent responses. They generate Levenshtein belief
spans instead of full state to reduce generation length and improve data
efficiency.

  * •

STAR Ye et al. (2021b) STAR uses two BERT models for encoding context and slot
values. Additionally, they use a slot self-attention mechanism that can learn
the slot correlations automatically. They use as input both the previous
belief state and history of dialogue.

BART-CSP is implemented using the Huggingface Wolf et al. (2019) and GenieNLP
Campagna et al. (2019) libraries. We use the available open-source code for
the other models. Hyperparameters for BART-CSP are discussed in Section 5.3;
hyperparameters for other models are taken from the respective papers.

###  5.3 Implementation Details

For semantic parsing we used bart-base (~139M parameters) for English and
mbart-large-50 (~611M parameters) model for other languages. For translation
we used mbart-large-50-many-to-many-mmt (~611M parameters) which can translate
directly between any pairs of 50 languages it supports. All models use a
standard Seq2Seq architecture with a bidirectial encoder and left-to-right
autoregressive decoder. All the models are pretrained using text denoising
objective. mbart-large-50-many-to-many-mmt is additionally finetuned to do
translation. BART uses BPE Gage (1994) to tokenize the input sentences whereas
MBART uses sentence-piece model Kudo and Richardson (2018). We used Adam
Kingma and Ba (2014) as our optimizer with a learning rate of $1\times
10^{-5}$ and used transformer warmup schedule Popel and Bojar (2018) with a
warmup of 80. These hyper-parameters were chosen from the best performing
model over the dev set. We batch sentences based on their input and
approximate output token count for better GPU utilization. We set the total
number of tokens to 700 for Mbart and 2000 for Bart models. We use gradient
accumulation of 3 for Mbart and 9 for bart models boosting the effective batch
size for better training. Our models were trained on NVIDIA V100 GPU using AWS
platform. For a fair comparison, all models were trained for the same number
of iterations of 50K.

| Dataset
---|---
RiSAWOZ | CrossWOZ | MultiWOZ 2.1
Languages | ZH, EN∗, DE∗ | ZH, EN | EN, ZH
# Domains | 12 | 5 | 7
# Dialogues | 10,000 | 5,012 | 8,438
# Turns | 134,580 | 84,692 | 115,424
# Slots | 159 | 72 | 25
# Values | 4,061 | 7,871 | 4,510
Table 1: Statistics of the training datasets (excluding validation and test).
∗Created using our method.

| SOTA | BART-CSP
---|---|---
Dataset | Model | Context | Dialogue | Encodes | Predefined | GJGA | JGA | GJGA | JGA
Encoder | History | State | Slots/ Ont.
RiSAWOZ | MLCSG | Bi-GRU | Full | ✗ | ✓ | – | 66.2 | 90.4 | 76.9
RiSAWOZ-EN-auto | MLCSG | Bi-GRU | Full | ✗ | ✓ | – | 36.2 | 88.8 | 68.6
(-alignment) | MLCSG | Bi-GRU | Full | ✗ | ✓ | – | 15.6 | 65.2 | 22.9
RiSAWOZ-DE-auto | MLCSG | Bi-GRU | Full | ✗ | ✓ | – | 13.4 | 86.7 | 65.9
CrossWOZ | TRADE | Bi-GRU | Full | ✗ | ✓ | 71.3† | 36.1 | 80.2 | 53.6
CrossWOZ-EN | SOM | BERT | Partial | ✓ | ✗ | – | 32.3‡ | 81.1 | 52.3
MultiWOZ 2.1 | STAR | BERT | Full | ✓ | ✓ | 78.7∗ | 56.7 | 81.2 | 53.7
MultiWOZ-ZH 2.1 | SUMBT | BERT | Full | ✓ | ✓ | – | 46.0‡ | 75.9 | 46.3

Table 2: Comparison of results on test set for the BART-CSP model vs state-of-
the-art on various datasets. †RuleDST uses the previous system state and user
dialogue acts as input. ∗STAR-GT uses ground truth previous dialogue state as
input. ‡ indicates results are reported from their paper. We reproduced all
results for models that source code and pretrained models were available to
ensure correct comparison. “-align.” denotes an ablation where translation is
done without slot-value alignment.

###  5.4 Metrics

We evaluate the models using the following two metrics:

  * •

Joint Goal Accuracy (JGA): The standard metric of evaluation in DST is joint
goal accuracy, which measures the average accuracy of predicting all slot
assignments to exact match (EM) for any given turn. To compute this metric for
CSP, the belief state predicted in previous turn is used as input for the
current turn.

  * •

Gold Joint Goal Accuracy (GJGA): This metric is similar to JGA but is
calculated on a turn by turn basis, with ground-truth belief state used as
input. Assuming the belief state correctly captures the state up to current
turn of the dialogue, this metric acts as an oracle in evaluation removing the
compounding effect of errors from previous turns.

##  6 Analysis and Results

Table 2 shows the results on test set for BART-CSP and previous SOTA models.
For a better comparison we have included some details for each model:

  * •

Context Encoder: The neural model used to encode the input.

  * •

Dialogue History: If dialogue history is included in the input. A turn is
defined as a pair of user utterance and agent response. Partial means only
last m turns of dialogue are kept while Full history models encode all
previous turns.

  * •

Encodes State: indicates if user belief state up to the current turn is
included in the input.

  * •

Predefined slots or ontology: whether model design or data processing needs
knowledge of slot names or values.

As shown all previous models encode either partial or full history. BART-CSP
encodes significantly less information as it relies only on the current turn
and latest belief state. This simplifies model design and and improves data
efficiency for training.

Furthermore, models that rely on predefined ontologies require changes in
architecture for new datasets. On the other hand, BART-CSP is a generative
model that learns to copy slots from context and can be deployed for a new
dataset as is.

On RiSAWOZ, current SOTA is MLCSG which uses Bi-GRU encoders so we could not
perform an ablation with more recent Transformer models such as BERT. However,
on MultiWOZ, we report results for MinTL which uses T5 and BART-large. Our
model achieves similar performance despite not having access to the history.

###  6.1 RiSAWOZ

The RiSAWOZ experiments shows that contextual semantic parsing delivers better
accuracy that the state-of-the-art on the original data sets, and even more so
for translated data sets because it is more robust to translation errors.

BART-CSP improves the state of the art by 10.7% on JGA to 76.9% for the
original Chinese data set. It provides an even greater improvement on the
translated data sets: by 32.4% to 68.6% and by 42.5% to 65.9% on the
automatically translated English and German data sets, respectively.

BART-CSP holds two major advantages over models that predict the slot-value
pairs from the dialogue history. First, by distilling the belief state into a
concise representation, it reduces noise in the input that would otherwise be
present in a long dialogue history. Second, by taking the belief state as
input, the model becomes more robust to translation errors in utterances from
previous turns than models that accept dialogue histories. Hence it is even
more effective on translated datasets.

Alignment is critical to generating a high-quality translated dialogue data
set. The English and German semantic parser show only a degradation of 8-11%
from the Chinese parser. In an ablation study of direct translation without
alignment, the JGA on RiSAWOZ English drops from 68.6% to 22.9%, a difference
of 45.7%.

Alignment ensures that entities are translated to the right phrase from the
target ontology. For example, the phrase “姑苏区" is translated to “Aguzhou
district” in a user utterance when the whole sentence is translated directly,
but becomes “Gusu district” in the annotation. With alignment, both are
translated identically to “Gusu district.” The correspondence of utterance and
belief state leads to higher DST performance.

###  6.2 CrossWOZ

Compared to MultiWOZ and RiSAWOZ, CrossWOZ is a more challenging dataset.
Besides having longer conversations with more domains per dialogue, the cross-
domain dependency is stronger. For example, the choice of location in one
domain will affect the choice of location in a related domain later in the
conversation, requiring models to have better contextual understanding.
CrossWOZ is not only a smaller, more complex dataset than RiSAWOZ, but also
exhibits a higher misannotation rate, to be discussed in section 7. The
current state of the art result was obtained with TRADE, which achieves 36.1%
JGA.

The experiments with CrossWOZ also confirm that BART-CSP outperforms prior
state-of-the-art models that encode full or partial history. Specifically, it
exhibits an improvement of 17.5% in JGA on the original dataset and 20.0% in
JGA on the English translated data set.

The GJGA metric for CrossWOZ was obtained by using RuleDST Zhu et al. (2020),
a set of hand-written rules specialized to the dataset to compute the new
belief state from the ground truth user and system dialogue acts. BART-CSP
outperforms the use of RuleDST in GJGA by 9%, showing that it is not necessary
to handcraft these rules.

The translated CrossWOZ-EN data have been manually corrected for slot-value
errors. Application of our automatic slot-value alignment technique would have
greatly reduced the tedious manual effort required. In both GJGA and JGA,
BART-CSP performs within 1% of the original Chinese dataset on English
CrossWOZ.

###  6.3 MultiWOZ

MultiWOZ is a challenging data set because of the well-documented problem of
misannotations in the data set Eric et al. (2019). Misannotations teach the
model to mispredict; conversely, correct predictions may be deemed to be
incorrect. Thus the current state-of-the-art STAR model can only achieve an
accuracy of 56.7%.

While BART-CSP accepts only the belief state as input context, the STAR model
accepts both the previous belief state and the dialogue history. The latter
offers an opportunity for the model to recover missing state values from the
history, giving a 3% advantage in JGA over BART-CSP. However, we note that
once an agent misinterprets a user input, it is not meaningful to measure the
accuracy for subsequent turns since the conversation would have diverged from
the test data.

On the other hand, parsing history has its own cost: (1) It is less data
efficient as you need more data to learn the same task. (2) It requires a more
complex model that can find relevant slots among a large number of sentences.
BART-CSP outperforms STAR by a 2.5% improvement in GJGA, suggesting that
having the dialogue history as input can be detrimental when the past turns of
a dialogue have been predicted correctly.

On the Chinese translation of MultiWOZ, BART-CSP does slightly better than
state of the art, improving JGA by 0.3% to 46.3%.

##  7 Error Analysis

A manual inspection revealed the following sources of errors on the CSP model,
showing some of the inference limitations and its susceptibility to
misannotations.

###  7.1 Misannotations

A significant fraction of perceived incorrect predictions comprise existing
annotation errors in all the datasets. In particular, in a manual review of
200 randomly chosen turns from each dataset, RiSAWOZ exhibits a 10.0%
misannotation rate while CrossWOZ and MultiWOZ respectively exhibit 17.9% and
26% misannotation rates.

Prevalent misannotation error types observed in the three datasets are noted
below, with examples in the appendix.

  * •

Inconsistency: Annotation inconsistency is an underlying issue of the Wizard-
of-Oz data collection method: slots mentioned by the agent but ignored by the
user are not always present or absent in the annotation. Similarly, inferred
slots are not always present or absent in analogous turns and dialogues.

  * •

Inexact Match: Typos, i.e. minor mismatches between utterance and annotation
slot values. Chinese is a homonym-heavy language. It is not unexpected for
single-character mismatch typos to occur frequently in the dataset. A second
kind of typo is for a character to be entirely missing in an entity name.

  * •

Missing Slots: Some annotations are missing slots such as restaurant name or
hotel name, despite the choice of restaurant or hotel in that particular turn.

CrossWOZ and MultiWOZ 2.1 are also susceptible to the following:

  * •

Extra Slots: The presence of slot names which are not mentioned by either the
user or the agent. For example: hotel-parking, hotel-pricerange, attraction-
area

The following additional annotations problems are salient in MultiWOZ 2.1:

  * •

Delayed Annotations: Slot value that are already confirmed by the user shows
up at a later turn in the conversation. For example: hotel-number of people

In RiSAWOZ, the final parting turn in a dialogue has no annotations,
indicating a state reset:

  * •

Empty Annotation (Hard State Reset): Some turns are missing annotations
altogether despite continuing an existing subject. Although empty annotations
are used in the dataset to denote the end of a conversation or a subject
change, it is incorrect for them to occur elsewhere.

###  7.2 Logical Relation Inference

In RiSAWOZ, it is expected that the model infers the logical relationships
between entities: for instance, the corresponding price range for a fast food
restaurant should be cheap, or a speaker looking for an attraction to go to
with his girlfriend wants a place where best-for-crowd = “lover’s date”. Hotel
rating is also inferred from the utterance rather than explicitly mentioned.

For example:

  * •

我们一家是外地的 ， 来苏州游玩 ， 你可以帮我找一个在吴中区 ， 中等消费水平的景点吗 (Our family is foreign, we have
come to Suzhou to have fun, could you help me find a WuZhong area, medium
priced attraction?)

The slot 最适合人群 = " 家庭亲子 " (best-for-crowd = “family”) must be inferred.

  * •

好的 。 再看看高新区有什么好吃的火锅店 ？(Okay. Can you also see if GaoXin District has some good
hotpot?)

The slot 价位 = " 偏贵 " (price = “expensive”) must be inferred from the fact that
it is hotpot.

We found that most models struggle with this type of inference which requires
higher level language understanding and reasoning. It is unclear whether this
weakness is inherent to the model or whether it is an artifact of inconsistent
annotations. Of the misannotations counted, 33% were missing the slot “Best
for crowd.”

##  8 Conclusion

Given a dialogue dataset in one language, this paper shows how to build
contextual semantic parsers for a new language using automatically machine-
translated data. We propose an improved alignment approach for dialogues to
ensure faithful translation of slot values. This removes the need for costly
human-post editing used in all previous benchmarks.

We show that the compounding effects of translation noise across turns can be
mitigated with a CSP model for dialogue state tracking. By leveraging
pretrained seq2seq models such as BART, training with CSP can outperform
state-of-the-art results on RiSAWOZ, CrossWOZ, and MultiWOZ-ZH while remaining
competitive on MultiWOZ despite not encoding any previous conversation turns
or having access to a predefined ontology.

Using our methodology, we create RiSAWOZ English and German, the first
automatically created high-quality translated datasets for dialogue state
tracking with no human-in-the-loop. We have implemented our methodology as a
toolkit which developers can use to create a new multilingual dialogue
datasets and contextual semantic parsers for it. Our new datasets and software
will be released open-source upon publication.

## References

  * Budzianowski et al. (2018) Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Ultes Stefan, Ramadan Osman, and Milica Gašić. 2018.  MultiWOZ - a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Campagna et al. (2019) Giovanni Campagna, Silei Xu, Mehrad Moradshahi, Richard Socher, and Monica S. Lam. 2019.  Genie: A generator of natural language semantic parsers for virtual assistant commands.  In _Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , PLDI 2019, pages 394–410, New York, NY, USA. ACM.
  * Chen et al. (2018) Wenhu Chen, Jianshu Chen, Yu Su, Xin Wang, Dong Yu, Xifeng Yan, and William Yang Wang. 2018.  Xl-nbt: A cross-lingual neural belief tracking framework.  _arXiv preprint arXiv:1808.06244_.
  * Cheng et al. (2020a) Jianpeng Cheng, Devang Agrawal, Héctor Martínez Alonso, Shruti Bhargava, Joris Driesen, Federico Flego, Dain Kaplan, Dimitri Kartsaklis, Lin Li, Dhivya Piraviperumal, et al. 2020a.  Conversational semantic parsing for dialog state tracking.  _arXiv preprint arXiv:2010.12770_.
  * Cheng et al. (2020b) Jianpeng Cheng, Devang Agrawal, Héctor Martínez Alonso, Shruti Bhargava, Joris Driesen, Federico Flego, Dain Kaplan, Dimitri Kartsaklis, Lin Li, Dhivya Piraviperumal, Jason D. Williams, Hong Yu, Diarmuid Ó Séaghdha, and Anders Johannsen. 2020b.  Conversational semantic parsing for dialog state tracking.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 8107–8117, Online. Association for Computational Linguistics.
  * Eric et al. (2019) Mihail Eric, Rahul Goel, Shachi Paul, Adarsh Kumar, Abhishek Sethi, Peter Ku, Anuj Kumar Goyal, Sanchit Agarwal, Shuyang Gao, and Dilek Hakkani-Tur. 2019.  Multiwoz 2.1: A consolidated multi-domain dialogue dataset with state corrections and state tracking baselines.  _arXiv preprint arXiv:1907.01669_.
  * Gage (1994) Philip Gage. 1994.  A new algorithm for data compression.  _C Users Journal_ , 12(2):23–38.
  * Gao et al. (2019) Shuyang Gao, Abhishek Sethi, Sanchit Agarwal, Tagyoung Chung, and Dilek Hakkani-Tur. 2019.  Dialog state tracking: A neural reading comprehension approach.  _arXiv preprint arXiv:1908.01946_.
  * Gunasekara et al. (2020) Chulaka Gunasekara, Seokhwan Kim, Luis Fernando D’Haro, Abhinav Rastogi, Yun-Nung Chen, Mihail Eric, Behnam Hedayatnia, Karthik Gopalakrishnan, Yang Liu, Chao-Wei Huang, et al. 2020.  Overview of the ninth dialog system technology challenge: Dstc9.  _arXiv preprint arXiv:2011.06486_.
  * Han et al. (2020) Ting Han, Ximing Liu, Ryuichi Takanobu, Yixin Lian, Chongxuan Huang, Wei Peng, and Minlie Huang. 2020.  Multiwoz 2.3: A multi-domain task-oriented dataset enhanced with annotation corrections and co-reference annotation.  _arXiv preprint arXiv:2010.05594_.
  * Heck et al. (2020) Michael Heck, Carel van Niekerk, Nurul Lubis, Christian Geishauser, Hsien-Chin Lin, Marco Moresi, and Milica Gašić. 2020.  Trippy: A triple copy strategy for value independent neural dialog state tracking.  _arXiv preprint arXiv:2005.02877_.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_.
  * Hori et al. (2019) Chiori Hori, Julien Perez, Ryuichiro Higashinaka, Takaaki Hori, Y-Lan Boureau, Michimasa Inaba, Yuiko Tsunomori, Tetsuro Takahashi, Koichiro Yoshino, and Seokhwan Kim. 2019.  Overview of the sixth dialog system technology challenge: Dstc6.  _Computer Speech & Language_, 55:1–25.
  * Hosseini-Asl et al. (2020) Ehsan Hosseini-Asl, Bryan McCann, Chien-Sheng Wu, Semih Yavuz, and Richard Socher. 2020.  A simple language model for task-oriented dialogue.  _arXiv preprint arXiv:2005.00796_.
  * Hu et al. (2020) Yue Hu, Jiahao Qin, Zemeiqi Chen, Jingshi Zhou, and Xiaojun Zhang. 2020.  Comparison of the effects of attention mechanism on translation tasks of different lengths of ambiguous words.  In _Proceedings of the Second International Workshop of Discourse Processing_ , pages 18–21.
  * Kelley (1984) John F Kelley. 1984.  An iterative design methodology for user-friendly natural language office information applications.  _ACM Transactions on Information Systems (TOIS)_ , 2(1):26–41.
  * Kim et al. (2016) Seokhwan Kim, Luis Fernando D’Haro, Rafael E Banchs, Jason D Williams, Matthew Henderson, and Koichiro Yoshino. 2016.  The fifth dialog state tracking challenge.  In _2016 IEEE Spoken Language Technology Workshop (SLT)_ , pages 511–517. IEEE.
  * Kim et al. (2019) Sungdong Kim, Sohee Yang, Gyuwan Kim, and Sang-Woo Lee. 2019.  Efficient dialogue state tracking by selectively overwriting memory.  _arXiv preprint arXiv:1911.03906_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  _arXiv preprint arXiv:1808.06226_.
  * Lee et al. (2019) Hwaran Lee, Jinsik Lee, and Tae-Yoon Kim. 2019.  SUMBT: Slot-utterance matching for universal and scalable belief tracking.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5478–5483, Florence, Italy. Association for Computational Linguistics.
  * Lei et al. (2018) Wenqiang Lei, Xisen Jin, Min-Yen Kan, Zhaochun Ren, Xiangnan He, and Dawei Yin. 2018\.  Sequicity: Simplifying task-oriented dialogue systems with single sequence-to-sequence architectures.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1437–1447.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Li et al. (2021) Jinchao Li, Qi Zhu, Lingxiao Luo, Lars Liden, Kaili Huang, Shahin Shayandeh, Runze Liang, Baolin Peng, Zheng Zhang, Swadheen Shukla, Ryuichi Takanobu, Minlie Huang, and Jianfeng Gao. 2021.  Multi-domain task-oriented dialog challenge ii at dstc9.  In _AAAI-2021 Dialog System Technology Challenge 9 Workshop_.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Moradshahi et al. (2020) Mehrad Moradshahi, Giovanni Campagna, Sina Semnani, Silei Xu, and Monica Lam. 2020\.  Localizing open-ontology QA semantic parsers in a day using machine translation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5970–5983, Online. Association for Computational Linguistics.
  * Peng et al. (2020) Baolin Peng, Chunyuan Li, Jinchao Li, Shahin Shayandeh, Lars Liden, and Jianfeng Gao. 2020.  Soloist: Few-shot task-oriented dialog with a single pre-trained auto-regressive model.  _arXiv preprint arXiv:2005.05298_.
  * Ponti et al. (2018) Edoardo Maria Ponti, Ivan Vulić, Goran Glavaš, Nikola Mrkšić, and Anna Korhonen. 2018.  Adversarial propagation and zero-shot cross-lingual transfer of word vector specialization.  _arXiv preprint arXiv:1809.04163_.
  * Popel and Bojar (2018) Martin Popel and Ondřej Bojar. 2018.  Training tips for the transformer model.  _The Prague Bulletin of Mathematical Linguistics_ , 110(1):43–70.
  * Quan and Xiong (2020) Jun Quan and Deyi Xiong. 2020.  Modeling long context for task-oriented dialogue state generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7119–7124, Online. Association for Computational Linguistics.
  * Quan et al. (2020) Jun Quan, Shian Zhang, Qian Cao, Zizhong Li, and Deyi Xiong. 2020.  Risawoz: A large-scale multi-domain wizard-of-oz dataset with rich semantic annotations for task-oriented dialogue modeling.  _arXiv preprint arXiv:2010.08738_.
  * Razumovskaia et al. (2021) Evgeniia Razumovskaia, Goran Glavaš, Olga Majewska, Anna Korhonen, and Ivan Vulić. 2021.  Crossing the conversational chasm: A primer on multilingual task-oriented dialogue systems.  _arXiv preprint arXiv:2104.08570_.
  * Schulz et al. (2017) Hannes Schulz, Jeremie Zumer, Layla El Asri, and Shikhar Sharma. 2017.  A frame tracking model for memory-enhanced dialogue systems.  _arXiv preprint arXiv:1706.01690_.
  * Tan et al. (2019) Xu Tan, Yi Ren, Di He, Tao Qin, Zhou Zhao, and Tie-Yan Liu. 2019.  Multilingual neural machine translation with knowledge distillation.  _arXiv preprint arXiv:1902.10461_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Wu et al. (2019) Chien-Sheng Wu, Andrea Madotto, Ehsan Hosseini-Asl, Caiming Xiong, Richard Socher, and Pascale Fung. 2019.  Transferable multi-domain state generator for task-oriented dialogue systems.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 808–819.
  * Ye et al. (2021a) Fanghua Ye, Jarana Manotumruksa, and Emine Yilmaz. 2021a.  Multiwoz 2.4: A multi-domain task-oriented dialogue dataset with essential annotation corrections to improve state tracking evaluation.  _arXiv preprint arXiv:2104.00773_.
  * Ye et al. (2021b) Fanghua Ye, Jarana Manotumruksa, Qiang Zhang, Shenghui Li, and Emine Yilmaz. 2021b.  Slot self-attentive dialogue state tracking.  _arXiv preprint arXiv:2101.09374_.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen. 2020.  Multiwoz 2.2: A dialogue dataset with additional annotation corrections and state tracking baselines.  _arXiv preprint arXiv:2007.12720_.
  * Zhong et al. (2018) Victor Zhong, Caiming Xiong, and Richard Socher. 2018.  Global-locally self-attentive encoder for dialogue state tracking.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1458–1467.
  * Zhu et al. (2020) Qi Zhu, Kaili Huang, Zheng Zhang, Xiaoyan Zhu, and Minlie Huang. 2020.  Crosswoz: A large-scale chinese cross-domain task-oriented dialogue dataset.  _Transactions of the Association for Computational Linguistics_ , 8:281–295.

##  Appendix A Ethical Considerations

Our translation method replaces the manual work needed to create multilingual
dialogue datasets usually done via crowdsourcing. Instead, it requires some
computation time which can be an environmental concern. However, in practice,
such additional computing is small and much cheaper than the cost of human
annotation for the same amount of data. Dataset translation takes about half
an hour on an Nvidia TITAN V GPU. Training takes about 6 hours on an Nvidia
V100 GPU. We did not use crowdworkers for this paper. The error analysis was
done by the authors.

##  Appendix B Error Analysis

###  B.1 Expanded Range Inference

In CrossWOZ, when a user requests, for instance, a restaurant where the cost
per person is within a price range, oftentimes the agent cannot find such a
restaurant, and responds with a suggestion with a cost outside of that range.
In subsequent slots, the price range is expanded to include that cost,
typically by rounding to the nearest ten. For example:

  * •

你好，我想去吃饭。请帮我找一家人均消费是100-150元，有井冈山豆皮这个菜的餐馆。 (Hello, I’d like to go eat. Please
help me find a place where the cost per person is 100-150 yuan, and has
Jingangshan bean curd.) In this turn, the slot value for cost per person is
100-150. However, following the agent response, the slot changes:
只为您找到一家叫西江美食舫(健德桥店)，但是它家的人均消费是83元。 (I could only find a place called XiJiang
Gourmet Boat (Jiandeqiao location), but the cost per person is 83 yuan.) Since
83 is outside the original range 100-150, the slot value is expanded to 80-150
for the remaining turns of the dialogue.

We find that CSP struggles with such turns and will typically mispredict the
slot value, assigning the previous range rather than inventing a new one.

###  B.2 Missannotation Examples

See Table 3 below for missannotation examples discussed in Section 7.

Error Type | Dataset |  Agent Utterance; User Utterance |  Annotation |  Correct Annotation
---|---|---|---|---
Delayed Annotation | MultiWOZ |  great , i can get you a ticket for that train . how many people are riding with you ?; i need to book it for 6 people , can i get the reference number too ? |  train day = " thursday " train departure = " cambridge " train destination = " birmingham new street " train leaveat = " 10:00 " |  train book people = " 6 " train day = " thursday " train departure = " cambridge " train destination = " birmingham new street " train leaveat = " 10:00 "
[next turn] can i confirm you want to book this train for 6 people ?; yes , i would like to book the train for 6 people . i need the reference number , please . |  train book people = " 6 " train day = " thursday " train departure = " cambridge " train destination = " birmingham new street " train leaveat = " 10:00 " |  (already correct)
Extra Slot | MultiWOZ |  ; hello ! i am planning my trip there and i am trying to find out about an attraction called kettle s yard . what can you tell me about it ? |  attraction name = " kettles yard " , attraction area = " west " |  attraction name = " kettles yard "
Empty Annotation | RiSAWOZ |  ;你好 ， 刚到苏州 ， 想先找个餐厅吃点东西 。 有价位便宜的江浙菜餐厅吗 |  null |  餐厅 价位 = " 便宜 " 餐厅 菜系 = " 江浙菜 "
Hello, I just came to Suzhou and am looking for a restaurant to grab a bite. Is there a cheap Jiangzhe restaurant? |  |  Restaurant Price = "Cheap" Restaurant Cuisine = "Jiangzhe"
Inexact Match | RiSAWOZ |  ;你好 ， 我这几天在苏州度假 ， 明天准备去狐狸家手工奶酪这家餐厅吃饭 ， 但不是很了解 ， 你能帮我查查那个餐馆附近有没有地铁能直达呢 ？ |  餐厅 名称 = " 狐狸家手工酸奶酪 " |  餐厅 名称 = " 狐狸家手工奶酪 "
; Hello, I’m vacationing in Suzhou these several days, tomorrow I plan to go to the Fox Family Handmade Cheese restaurant to eat, but I don’t really understand, can you help me look up whether there is direct subway access to anywhere near there? |  Restaurant Name = "Fox Family Handmade Yogurt (Yogurt = Sour Cheese)" |  Restaurant Name = "Fox Family Handmade Cheese"
Missing Slot | RiSAWOZ |  有呀 ， 推荐您去鑫花溪牛肉米粉 。; 这家店地址在哪 ？ |  餐厅 价位 = " 中等 " 餐厅 菜系 = " 快餐简餐 " |  餐厅 价位 = " 中等 " 餐厅 名称 = " 鑫花溪牛肉米粉 " 餐厅 菜系 = " 快餐简餐 "
Yes, I recommend you go to Xinhuaxi Beef Noodle; What is the address of this place? |  Restaurant Price = "Medium" Restuarant Cuisine = "Quick and Easy" |  Restaurant Price = "Medium" Restaurant Name = "Xinhuaxi Beef Noodle" Restaurant Cuisine = "Quick and Easy"

Table 3: Prevalent annotation error types found in the datasets.


# An Elementary Proof of the Generalization of the Binet Formula for
$k$-bonacci Numbers

Harold R. Parks  Department of Mathematics
Oregon State University
Corvallis
Oregon 97331 USA<EMAIL_ADDRESS>and  Dean C. Wills  AppDynamics,
San Francisco, California 94107 USA<EMAIL_ADDRESS>
###### Abstract.

We present an elementary proof of the generalization of the $k$-bonacci Binet
formula, a closed form calculation of the $k$-bonacci numbers using the roots
of the characteristic polynomial of the $k$-bonacci recursion.

###### 2010 Mathematics Subject Classification:

Primary 15A15; Secondary 11B39

##  1\. Introduction

The Binet formula for the Fibonacci numbers is:

(1.1)
$F_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)\,.$

Noting that $\phi_{1}=(1+\sqrt{5})/2$ and $\phi_{2}=(1-\sqrt{5})/2$ are the
roots of $x^{2}-x-1=0,$ the characteristic equation of the Fibonacci
recursion, we can rewrite (1.1) as

$F_{n}=\frac{\phi_{1}^{n}-\phi_{2}^{n}}{\phi_{1}-\phi_{2}},$

which in turn can be written in the symmetric form

(1.2)
$F_{n}=\frac{\phi_{1}^{n}}{\phi_{1}-\phi_{2}}+\frac{\phi_{2}^{n}}{\phi_{2}-\phi_{1}}\,.$

This leads one to conjecture that (1.2) ought to generalize in a natural way
to the $k$-bonacci numbers, $k>2$. Indeed, such a natural generalization,
given in (1.3) below, is true.

Certainly, this result is known. The subject has been explored in various
forms in all the papers, [1] [2], [3], [4], [5], [6], [7], [8], [9], [10],
[11], listed as references.

We call special attention to [9] and [10]. In [9], a more general result is
developed using the theory of symmetric functions. The particular application
to the generalized $k$-bonacci sequence is Example 1 on page 291. In [10], the
Binet formula for the $k$-bonacci sequence is equation (2)′′ on page 749. In
that paper, the result is obtained via the general theory of difference
equations.

Despite the available references, the authors feel that the proof given below,
relying only on Vandermonde determinants, is simpler and more succinct than
any available elsewhere in the literature.

######  Theorem 1.1.

For $k\geq 2$, let $\phi_{i}$, $i=1,2,\dots,k$, be the solutions of the
characteristic equation, $x^{k}-x^{k-1}-\cdots-1=0$, of the $k$-bonacci
recursion. If the $k$-bonacci numbers, $F^{(k)}_{n}$, are defined with initial
values of $F^{(k)}_{n}=0,$ for $0\leq n<k-1$, and $F^{(k)}_{k-1}=1,$ then

(1.3) $\displaystyle F^{(k)}_{n}$
$\displaystyle=\sum_{i=1}^{k}\frac{\phi_{i}^{n}}{(\phi_{i}-\phi_{1})\cdots(\phi_{i}-\phi_{i-1})(\phi_{i}-\phi_{i+1})\cdots(\phi_{i}-\phi_{k})}=\sum_{i=1}^{k}\frac{\phi_{i}^{n}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}$

The expressions in the center and right-hand side of (1.3) simply use
different notations for the same denominator. It is important to know that the
$k$ solutions of the characteristic equation are all distinct, so that no
division by zero occurs. To see this, note that if the characteristic
polynomial had a multiple root, then that same multiple root would be a
multiple root of $(x-1)(x^{k}-x^{k-1}-\cdots-1)=x^{n+1}-2x^{n}+1$ and thus a
root of $d(x^{n+1}-2x^{n}+1)/dx=(n+1)x^{n}-2nx^{n-1}$. This last polynomial
has only rational roots, and the Rational Root Theorem tells us that they are
not roots of $x^{k}-x^{k-1}-\cdots-1$.

##  2\. Proofs

The proof of the next lemma and the theorem will involve various Vandermonde
determinants, so we make the following definition.

######  Definition 2.1.

Set

$\mathcal{V}\left(\phi,k\right)=\begin{vmatrix}1&\phi_{1}&\phi_{1}^{2}&\cdots&\phi_{1}^{k-2}&\phi_{1}^{k-1}\\\\[2.15277pt]
1&\phi_{2}&\phi_{2}^{2}&\cdots&\phi_{2}^{k-2}&\phi_{2}^{k-1}\\\\[2.15277pt]
1&\phi_{3}&\phi_{3}^{2}&\cdots&\phi_{3}^{k-2}&\phi_{3}^{k-1}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&\phi_{k}&\phi_{k}^{2}&\cdots&\phi_{k}^{k-2}&\phi_{k}^{k-1}\\\
\end{vmatrix}=\prod_{1\leq m<n\leq k}(\phi_{n}-\phi_{m}).$

Similarly, define the minor

$\mathcal{V}_{i}\left(\phi,k\right)=\begin{vmatrix}1&\phi_{1}&\phi_{1}^{2}&\cdots&\phi_{1}^{k-2}&\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&\phi_{i-1}&\phi_{i-1}^{2}&\cdots&\phi_{i-1}^{k-2}\\\\[2.15277pt]
1&\phi_{i+1}&\phi_{i+1}^{2}&\cdots&\phi_{i+1}^{k-2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&\phi_{k}&\phi_{k}^{2}&\cdots&\phi_{k}^{k-2}\end{vmatrix}=\prod_{\begin{subarray}{c}1\leq
m<n\leq k\\\ m,n\neq i\end{subarray}}(\phi_{n}-\phi_{m}).$

######  Lemma 2.2.

Let $K$ be a field, and $\phi_{i},f_{i}\in K,$ for $1\leq i\leq k$. If the
$\phi_{i}$ are all distinct, then

(2.1) $\sum_{i=1}^{k}\frac{f_{i}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}=\frac{1}{\mathcal{V}\left(\phi,k\right)}\
\begin{vmatrix}1&\phi_{1}&\phi_{1}^{2}&\cdots&\phi_{1}^{k-2}&f_{1}\\\\[2.15277pt]
1&\phi_{2}&\phi_{2}^{2}&\cdots&\phi_{2}^{k-2}&f_{2}\\\\[2.15277pt]
1&\phi_{3}&\phi_{3}^{2}&\cdots&\phi_{3}^{k-2}&f_{3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&\phi_{k}&\phi_{k}^{2}&\cdots&\phi_{k}^{k-2}&f_{k}\end{vmatrix}$

###### Proof.

Expanding the determinant on the right-hand side of (2.1) along the last
column, we see that

$\begin{vmatrix}1&\phi_{1}&\phi_{1}^{2}&\cdots&\phi_{1}^{k-2}&f_{1}\\\\[2.15277pt]
1&\phi_{2}&\phi_{2}^{2}&\cdots&\phi_{2}^{k-2}&f_{2}\\\\[2.15277pt]
1&\phi_{3}&\phi_{3}^{2}&\cdots&\phi_{3}^{k-2}&f_{3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&\phi_{k}&\phi_{k}^{2}&\cdots&\phi_{k}^{k-2}&f_{k}\end{vmatrix}=\sum_{i=1}^{k}(-1)^{k-i}\
f_{i}\cdot\mathcal{V}_{i}\left(\phi,k\right)$

For each $i$, observe that

$\prod_{1\leq m<n\leq
k}(\phi_{n}-\phi_{m})=(-1)^{k-i}\prod_{\stackrel{{\scriptstyle 1\leq m<n\leq
k}}{{\vrule height=4.52083pt,width=0.0pt,depth=0.0ptm,n\neq
i}}}(\phi_{n}-\phi_{m})\prod_{j\neq i}(\phi_{i}-\phi_{j})$

so

$\sum_{i=1}^{k}\frac{f_{i}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}=\sum_{i=1}^{k}\frac{(-1)^{k-i}\
f_{i}\cdot\mathcal{V}_{i}\left(\phi,k\right)}{\mathcal{V}\left(\phi,k\right)}$

holds, and the result follows. ∎

###### Proof of Theorem 1.1.

For $n=0,1,\dots,k-2$, Lemma 2.2 tells us that the right-hand side of (1.3)
equals $\mathcal{V}\left(\phi,k\right)^{-1}$ times the value of a determinant
with a repeated column, thus the right-hand side of (1.3) equals $0$. When
$n=k-1$, Lemma 2.2 tells us that the right-hand side of (1.3) equals
$\mathcal{V}\left(\phi,k\right)^{-1}$ times the value of a Vandermonde
determinant and that Vandermonde determinant clearly equals
$\mathcal{V}\left(\phi,k\right)$.

Now suppose that $n\geq k-1$. Arguing inductively and noting that
$\phi^{k}=\sum_{m=0}^{k-1}\phi^{m}$, we have

$\displaystyle F^{(k)}_{n+1}$
$\displaystyle=\sum_{m=0}^{k-1}F^{(k)}_{(n+1-k)+m}\ =\
\sum_{m=0}^{k-1}\sum_{i=1}^{k}\frac{\phi_{i}^{(n+1-k)+m}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}\ =\
\sum_{i=1}^{k}\frac{\phi_{i}^{n+1-k}\sum_{m=0}^{k-1}\phi_{i}^{m}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}$ $\displaystyle=\
\sum_{i=1}^{k}\frac{\phi_{i}^{n+1-k}\phi_{i}^{k}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}\ =\ \sum_{i=1}^{k}\frac{\phi_{i}^{n+1}}{\prod_{j\neq
i}(\phi_{i}-\phi_{j})}\,.$

∎

## References

  * [1] Gregory P. Dresden and Zhaohui Du.  A simplified binet formula for k-generalized fibonacci numbers.  J. Integer Seq., 17:14.4.7, 2014.
  * [2] David E. Ferguson.  An expression for generalized Fibonacci numbers.  Fibonacci Quarterly, 4(3):270–272, October 1966.
  * [3] Ivan Flores.  Direct calculation of $k$-generalized Fibonacci numbers.  Fibonacci Quarterly, 5(3):259–266, October 1967.
  * [4] Hyman Gabai.  Generalized Fibonacci $k$-sequences.  Fibonacci Quarterly, 8(1):31–38, February 1970.
  * [5] Gautam S. Hathiwala and Devbhadra V. Shah.  Binet – type formula for the sequence of tetranacci numbers by alternate methods.  Mathematical Journal of Interdisciplinary Sciences, 6(1):37–48, May 2019.
  * [6] Dan Kalman.  Generalized Fibonacci numbers by matrix methods.  Fibonacci Quarterly, 20(1):73–76, February 1982.
  * [7] David Kessler and Jeremy Schiff.  A combinatoric proof and generalization of Ferguson’s formula for $k$-generalized Fibonacci numbers.  Fibonacci Quarterly, 42(3):266–273, August 2004.
  * [8] Gwang-Yeon Lee, Sang-Gu Lee, Jin-Soo Kim, and Hang-Kyun Shin.  The Binet formula and representations of $k$-generalized Fibonacci numbers.  Fibonacci Quarterly, 39(2):158–164, May 2001.
  * [9] Claude Levesque.  On $m$-th order linear recurrences.  Fibonacci Quarterly, 23(4):290–293, November 1985.
  * [10] E. P. Miles.  Generalized fibonacci numbers and associated matrices.  The American Mathematical Monthly, 67(8):745–752, 1960.
  * [11] W. R. Spickerman.  Binets’s formula for the Tribonacci sequence.  Fibonacci Quarterly, 20(2):118–120, May 1982.