# Information content versus word length in natural language: A reply to
Ferrer-i-Cancho and Moscoso del Prado Martin (2011)

Steven T. Piantadosi, Harry Tily, Edward Gibson

###### Abstract

Recently, ? (?) argued that an observed linear relationship between word
length and average surprisal (?, ?) is not evidence for communicative
efficiency in human language. We discuss several shortcomings of their
approach and critique: their model critically rests on inaccurate assumptions,
is incapable of explaining key surprisal patterns in language, and is
incompatible with recent behavioral results. More generally, we argue that
statistical models must not critically rely on assumptions that are
incompatible with the real system under study.

##  1 Introduction

One of the most famous properties of language, first studied by ? (?), is that
frequent words are typically also short. Zipf offered a communicative theory
for this property, under which lexicons have evolved to be efficient: words
which must be re-used repeatedly should be short to minimize the effort of
language users. Recently, we (?, ?, henceforth, PT&G) demonstrated an
improvement on Zipf’s ideas. Under a more elaborate notion of communicative
efficiency, word length should depend not on frequency, but on the typical
_amount_ of information conveyed by a word. Efficient languages will convey
information close to the channel capacity (?, ?) of human perceptual and
cognitive systems. In this case, one should observe a linear relationship
between a word’s negative log probability (surprisal) and its length, in an
attempt to keep the number of bits communicated per unit time roughly
constant. Such a prediction is a lexical version of a now popular idea that
choices made in language production also attempt to maintain a roughly uniform
rate of information transmission (?, ?, ?, ?, ?, ?). PT&G demonstrated across
$10/11$ languages for which corpora were readily available that information
content does predict word length better than frequency, both in total
correlations and partial correlations.

Recently, ? (?, henceforth F&M) argued that the roughly linear relation
observed in PT&G was not necessarily evidence of communicative efficiency.
They prove that a model in which language is generated by choosing characters
independently also shows a linear relationship between average information
content and word length111Because in their model predictability reduces to
frequency, their work replicates ? (?) (e.g. Equation 2) and extends it to the
case of unequal letter probabilities.. In such a system, words are generated
by randomly typing characters, and occasionally hitting the “space” character
to create a word boundary. It is intuitively not surprising that such a system
would show the required linear relationship, since the probability of
achieving a word of a given length $l$ will decrease geometrically in $l$, so
the log probability scales linearly in $l$. F&M furnish a mathematical proof
for a more general version where all words must be longer than some minimum
length $l_{0}$ and individual letters occur with arbitrary probabilities.
Because random typing does not consider communicative efficiency, they argue
that it is possible to achieve a linear relationship without any notion of
communicative optimization222F&M do not specify what they mean by
communicative efficiency. For PT&G and other UID work before them, language
would be efficient if it tended to communicative bits of information at the
channel capacity of human cognitive systems. Under this definition, F&M’s
random typing model actually could be efficient.. Though they do not say so
explicitly, their paper implies that such simple statistical models should be
treated as baselines, where any properties of language that hold in them are
not expected to be the result of any interesting causal processes. F&M’s
random typing model is one exemplar of a long history of _monkey models_ in
psycholinguistics, so-called because they capture the Borel’s process of “a
million monkeys typing on a million typewriters.” Such models were first
articulated in the study of language by ? (?) and ? (?) in an attempt to
account of the power law distribution of word frequencies (?, ?).

F&M’s model is essentially a toy model of language and does indeed exhibit a
linear relationship between word length and information content. However, we
argue that their model is, in some sense, too simplified for the strong claims
they make. Here, we discuss some of the limitations of F&M’s model. After
clarifying the main finding of PT&G, we argue that the model’s assumptions
make it inherently unlike real human language, and therefore a poor choice for
statistical comparison. We then review recent behavioral work indicating that
PT&G’s results are not statistical artifacts.

### Random typing cannot explain the primary finding of PT&G

First—and perhaps most importantly—F&M do not address the primary data point
reported by PT&G. Our main finding was _not_ a linear relationship. Instead,
we focused on reporting that a word’s average in-context surprisal predicted
word length _better than frequency predicts word length_. This pattern held in
general for several different corpora, ways of measuring word length, and ways
of estimating surprisal, and in partial correlations (e.g. surprisal
partialing out frequency vs. frequency partialing out surprisal). Thus, PT&G’s
measure of the average amount of information conveyed by a word was a more
important determinant of word length than frequency—so much so that the
partial effect of frequency was near zero in some languages. Indeed, our
primary correlations reported were not even linear correlations, but
nonparametric (although both give very similar results).

In the random typing setup used by F&M, frequency and our information measure
are mathematically identical—a fact used in their derivations—so random typing
could never find that information content was a better predictor of length
than frequency. This both illustrates a limitation of F&M’s model, and
provides evidence that it is a poor description of the statistical patterns in
natural language.

### Independent data argues against random typing

Beyond the fact that F&M’s analysis cannot address the reported differences
between frequency and information content, it is worth considering its
limitations when viewed as a statistical model of language. The model’s
generative process assumes that words are created by just happening to
randomly sample their component pieces. This probabilistic scheme is what
assigns words of varying lengths their varying probabilities.

But language generation does not work that way333? (?) presented a similar
critique to Miller’s random typing model for deriving the Zipfian distribution
of word frequencies: “If Zipf’s law indeed referred to the writings of ‘random
monkeys,’ Miller’s argument would be unassailable, for the assumption he bases
it upon are appropriate to the behavior of those conjectural creatures. But to
justify his conclusion that people also obey Zipf’s law for the same reason,
Miller must perforce establish that the same assumptions are also appropriate
to human language. In fact, as we shall see, they are directly contradicted by
well-known and obvious properties of languages.”. Instead, speakers _know
whole words_. This fact is not hard to establish psychologically or
statistically. For instance, psychologically, speakers know word meanings and
produce them in the correct context—they don’t just happen to say words by
randomly saying syllables or phonemes. Statistically, idealized models over
sequences of characters infer not only the presence of words but the correct
words themselves (?, ?, ?). Though such models were proposed as language
acquisition models, they equally serve as idealized data analysis models,
demonstrating that the evidence provided by statistical dependencies between
characters in natural language strongly favors the existence of words.

The existence of words as psychological units undermines F&M’s primary point,
that “a linear correlation between information content and word length may
simply arise internally, from the units making a word (e.g., letters) and not
necessarily from the interplay between words and their context … .” If humans
generate language by remembering entire words, rather than by sampling their
component parts, then there is no necessary relationship between word length,
frequency, and information content. In the real psychological system wordforms
are memorized sequences, making their probability of generation is not longer
intrinsically tied to their length. Indeed, it is hard to see what the
behavior of models that critically rely on randomly generating word
_components_ could tell us about a psychological system that does not work
that way.

### Random typing is not even a good statistical model

It is still worth considering that even though the generative assumptions of
random typing models are limiting, they still may provide a useful
_statistical_ description of language. Unfortunately, a considerable amount of
evidence has amassed that such models are poor statistical theories. ? (?,
pg106-107) analyzes the predictions of a random typing model with respect to
coarse properties of lexical systems, including word frequency distributions,
frequency/length relationships, and neighborhood density. He finds that while
a random typing model provides qualitative trends in the right directions, its
quantitative fit is not very good and is eclipsed by the fit of other models
such as a Yule-Simon model. Indeed, a considerable amount of work—confusingly,
much of it by the first author of F&M—has detailed the ways in which the
output of random typing models are _unlike_ those found in natural languages,
especially with respect to Zipf’s law (?, ?, ?, ?, ?, ?). Other statistical
properties of random texts have been found to be divergent from real language.
For instance, ? (?) shows that random texts, but not natural texts, follow the
statistics of Heaps’ law, a growth pattern relating types and tokens to text
sample size (?, ?). ? (?) compares entropy-based measures on natural and
random typing model texts, with the goal of finding metrics that best
distinguish these texts. Our other work has detailed ways in which lexical
systems are not only non-random, but specifically structured for communicative
efficiency, in terms of ambiguity (?, ?) or lexical properties such as stress
(?, ?). Additionally, not all short, phonotactically possible words are used
in language (?, ?), contrary to the predictions of a random typing model, but
consistent with communicative theories based on entropy rate (PT&G) or
possibly the avoidance of confusable code words. In short, it is clear that
random typing models don’t even produce the correct detailed _statistical_
properties of language, although they may appear qualitatively similar with
respect to some coarse-grained properties.

### The importance of a model’s key assumptions

The implication of F&M (and before them, ? (?)) is that even though random
typing models are implausible descriptions of the generative process of
language and poor statistical theories, they still provide a null hypothesis
which should be considered in the course of scientific theorizing. Properties
of language that are also exhibited by random typing models should be looked
on cautiously, as phenomena which likely have a trivial and uninteresting
cause. In contrast, we believe that it is a fallacy to think that the fact a
random typing model exhibits a linguistic property should cast any doubt on
alternative theories, such as those proposed by PT&G and Zipf. The hypothesis
of random typing—and all models like them—have already been disproven by other
sources of evidence like the statistical and psychological existence of words
as memorized units.

We find this point interesting because it raises a difficult issue for
modeling. All models are inaccurate in that they do not exactly mirror the
“real” process happening in the world. Most models do or should attempt to
make their key assumption analogous to the key causal process at play in the
world. Thus, changing “good” models to make them more realistic will not break
their core predictions and properties. But F&M’s model is different: it cannot
be given knowledge of words—like people have—without destroying the behavior
F&M aim to explain. The key assumption of generating words by happening to
choose their components make the model critically _unlike_ people in terms of
representation, processing, and knowledge of language.

### Independent evidence for PT&G’s optimization process

Aside from discussions of the plausibility of various models, there are good
independent reasons for rejecting F&M’s assertion that the relationship
observed by PT&G is a statistical artifact. PT&G posited that the observed
relationships might result from lexicalization of phonetic reduction (e.g. ?,
?, ?). It is well-known that speakers shorten or reduce syllables in
predictable locations and PT&G’s findings plausibly result from these speech
production factors being integrated into lexical representations. If a word is
used in predictable locations, it will be reduced, and eventually might be
learned to be its shorter form, giving a relationship between word length and
predictability.

Second, there are independent behavioral studies showing that speakers
actually _do_ prefer short forms of words in predictable contexts, exactly as
PT&G’s theory would predict. ? (?) gave people a choice between two synonymous
pairs (e.g. “chimp”/“chimpanzee”) in either predictive or non-predictive
contexts. They found that people preferred the the short form when the word
was predictable and the long form was it was not. These kind of behavioral
tendencies have also been examined in corpus research by ? (?), who showed
that contracted forms (“do not” / “don’t”) occur more frequently in predictive
contexts. Such behavior is predicted by PT&G, but not explainable with F&M’s
view that the relationship between information content and word length is a
statistical artifact.

### Conclusion

Random typing models provide an interesting case study for considering what
modelers should want from models. Good models do not simply exhibit the
correct surface statistics; good models capture the right core assumptions of
the system under study, and show how the observed properties of the system
result from those properties. It is not informative to show that other
assumptions could also lead to the observed behavior, _if_ those other
assumptions are demonstrably not at play.

This means that one is not free to study _any_ conceivable statistical process
and conclude that it is relevant for understanding how language works. Models
under consideration must respect what is independently known about the system
under study. Since words are actively _chosen_ by language users to convey a
meaning, there is no point to studying models for which the uttered word is
generated according to some statistical properties of the wordform itself—that
is the wrong causal direction. As such, results about random typing models
only apply to systems that are critically unlike human language in terms of
the structure of language, knowledge of words, and the transmission of
meaningful information.

## References

  * Aylett TurkAylett Turk Aylett, M., Turk, A.  (2004).  The Smooth Signal Redundancy Hypothesis: A Functional Explanation for Relationships between Redundancy, Prosodic Prominence and Duration in Spontaneous Speech.  _Language and Speech_ , _47_ , 31–56.
  * BaayenBaayen Baayen, R.  (2001).  _Word frequency distributions_ (Vol. 1).  Kluwer Academic Publishers.
  * Bernhardsson, Baek, MinnhagenBernhardsson et al. Bernhardsson, S., Baek, S., Minnhagen, P.  (2011).  A paradoxical property of the monkey book.  _Journal of Statistical Mechanics: Theory and Experiment_ , _2011_ , P07013.
  * CohenCohen Cohen, A.  (2006).  Why ambiguity?  In H.-M. Gaertner, S. Beck, R. Eckardt, R. Musan, B. Stiebels (Eds.), _Between 40 and 60 Puzzles for Manfred Krifka._
  * Cohen, Mantegna, HavlinCohen et al. Cohen, A., Mantegna, R., Havlin, S.  (1997).  Numerical analysis of word frequencies in artificial and natural language texts.  _Fractals-an Interdisciplinary Journal on the Complex Geometry_ , _5_(1), 95–104.
  * Ferrer i Cancho ElvevågFerrer i Cancho Elvevåg Ferrer i Cancho, R., Elvevåg, B.  (2010).  Random Texts Do Not Exhibit the Real Zipf’s Law-Like Rank Distribution.  _PLoS ONE_ , _5_(3).
  * Ferrer i Cancho Moscoso del Prado MartínFerrer i Cancho Moscoso del Prado Martín Ferrer i Cancho, R., Moscoso del Prado Martín, F.  (2011).  Information content versus word length in random typing.  _Journal of Statistical Mechanics: Theory and Experiment_ , _2011_ , L12002.
  * Ferrer i Cancho SoléFerrer i Cancho Solé Ferrer i Cancho, R., Solé, R.  (2002).  Zipf’s law and random texts.  _Advances in Complex Systems_ , _5_(1), 1–6.
  * Frank JaegerFrank Jaeger Frank, A., Jaeger, T.  (2008).  Speaking rationally: Uniform information density as an optimal strategy for language production.  In _Proceedings of the Cognitive Science Society._
  * Genzel CharniakGenzel Charniak Genzel, D., Charniak, E.  (2002).  Entropy rate constancy in text.  In _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ (pp. 199–206).
  * Genzel CharniakGenzel Charniak Genzel, D., Charniak, E.  (2003).  Variation of entropy and parse trees of sentences as a function of the sentence number.  In _Proceedings of empirical methods in natural language processing_ (pp. 65–72).
  * GoldwaterGoldwater Goldwater, S.  (2006).  _Nonparametric bayesian models of lexical acquisition_.  Unpublished doctoral dissertation, Brown University.
  * HeapsHeaps Heaps, H.  (1978).  _Information retrieval: Computational and theoretical aspects_.  Academic Press, Inc.
  * HowesHowes Howes, D.  (1968).  Zipf’s Law and Miller’s Random-Monkey Model.  _The American Journal of Psychology_ , _81_(2), 269–272.
  * JaegerJaeger Jaeger, T.  (2010).  Redundancy and reduction: Speakers manage syntactic information density.  _Cognitive Psychology_ , _61_ , 23–62.
  * Jurafsky, Bell, Gregory, RaymondJurafsky et al. Jurafsky, D., Bell, A., Gregory, M., Raymond, W.  (2001).  Evidence from reduction in lexical production.  _Frequency and the emergence of linguistic structure_ , _45_ , 229.
  * Levy JaegerLevy Jaeger Levy, R., Jaeger, T.  (2007).  Speakers optimize information density through syntactic reduction.  _Advances in neural information processing systems_ , _19_ , 849–856.
  * LiebermanLieberman Lieberman, P.  (1963).  Some effects of semantic and grammatical context on the production and perception of speech.  _Language and Speech_ , _6_ , 172–187.
  * Mahowald, Fedorenko, Piantadosi, GibsonMahowald et al. Mahowald, K., Fedorenko, E., Piantadosi, S., Gibson, E.  (in press).  Info/information theory: speakers actively choose shorter words in predictable contexts.  _Cognition_.
  * MandelbrotMandelbrot Mandelbrot, B.  (1953).  An informational theory of the statistical structure of language.  _Communication theory_ , 486–502.
  * MillerMiller Miller, G.  (1957).  Some effects of intermittent silence.  _The American Journal of Psychology_ , 311–314.
  * Miller ChomskyMiller Chomsky Miller, G., Chomsky, N.  (1963).  Finitary models of language users.  _Handbook of mathematical psychology_ , _2_ , 419–491.
  * MontemurroMontemurro Montemurro, M.  (2001).  Beyond the Zipf–Mandelbrot law in quantitative linguistics.  _Physica A: Statistical Mechanics and its Applications_ , _300_(3), 567–578.
  * Pearl, Goldwater, SteyversPearl et al. Pearl, L., Goldwater, S., Steyvers, M.  (2011).  Online learning mechanisms for bayesian models of word segmentation.  _Research on Language & Computation_, 1–26.
  * Piantadosi, Tily, GibsonPiantadosi et al. Piantadosi, S., Tily, H., Gibson, E.  (2009).  The communicative lexicon hypothesis.  In _The 31st annual meeting of the Cognitive Science Society (CogSci09)_ (pp. 2582–2587).
  * Piantadosi, Tily, GibsonPiantadosi et al. Piantadosi, S., Tily, H., Gibson, E.  (2011).  Word lengths are optimized for efficient communication.  _Proceedings of the National Academy of Sciences_.
  * Piantadosi, Tily, GibsonPiantadosi et al. Piantadosi, S., Tily, H., Gibson, E.  (2012).  The communicative function of ambiguity in language.  _Cognition_ , _122_ , 280–291.
  * ShannonShannon Shannon, C.  (1948).  _The mathematical theory of communication_.  Urbana, IL: University of Illinois Press.
  * Tripp FeitelsonTripp Feitelson Tripp, O., Feitelson, D.  (1982).  Zipf’s law re-visited.  _Studies on Zipf’s law_ , 1–28.
  * ZipfZipf Zipf, G.  (1936).  _The Psychobiology of Language_.  London: Routledge.


# Towards Fair Personalization
by Avoiding Feedback Loops

Gökhan Çapan
<EMAIL_ADDRESS>&Özge Bozal
<EMAIL_ADDRESS>&İlker Gündoğdu
<EMAIL_ADDRESS>&Ali Taylan Cemgil
<EMAIL_ADDRESS>
Department of Computer Engineering, Boğaziçi University, Istanbul, Turkey

###### Abstract

Self-reinforcing feedback loops are both cause and effect of over and/or
under-presentation of some content in interactive recommender systems. This
leads to erroneous user preference estimates, namely, overestimation of over-
presented content while violating the right to be presented of each
alternative, contrary of which we define as a fair system. We consider two
models that explicitly incorporate, or ignore the systematic and limited
exposure to alternatives. By simulations, we demonstrate that ignoring the
systematic presentations overestimates _promoted_ options and underestimates
_censored_ alternatives. Simply conditioning on the limited exposure is a
remedy for these biases.

##  1 Introduction

Contemporary digital platforms provide excessive amount of content imposing on
us an exhaustive search to identify the options that match our interest.
Personalized recommender systems step in as a solution by filtering the
alternatives.

Recommendations by the personalized interactive system are based on users’
feedback (_e.g._ , clicks, purchases, ratings) to what is recommended by the
system in the first place. This mechanism has a major impact on the users’
future choices, leading to biased [13, 21, 22] and inconsistent [20]
preference estimates. It gives rise to a vicious cycle that over-presented
content gets more attention and keeps being over-presented, whereas under-
presented content is subject to going unnoticed and being undervalued.
Ignoring this feedback loop reinforces the system’s prior belief on the user’s
interest; the over-presented are overestimated and the under-presented are
underestimated.

For instance, popular (i.e. frequently rated) or promoted content gets a lot
of exposure while less popular ones are under-presented in the recommendations
[1, 2, 3]. On the other hand, relatively favorable alternatives may go under-
presented, if at all they are presented. This observation bias is identified
as a significant cause of biased preference estimates [24, 8].

Another negative impact of ignoring the feedback loops is _bias towards
initial choices_ , _i.e._ , initially recommended alternatives are favored by
the system. Especially when it does not match the user’s interest to begin
with, the user feedback might be misleading for the recommender system. As a
result, the system may lack in adapting itself to the user’s actual
preferences, namely, under-presents favorable alternatives.

Over/under-presentation due to biased preference estimates disturbs the fair
setting for both users and content providers. Overlooking some of the options
that are actually appealing to the user violates the right of each option to
be presented [18, 16], on account of the system’s misconception that this
option is not preferable by the user. Eventually, the user experience is
isolated to a vicinity of only a limited set of alternatives, leading to a
“filter bubble” [19]. An individual’s interests might even go extreme by the
systematic exposure [11].

Undesirable consequences of these scenarios raise the question how a fair and
responsible recommender system should operate. In this paper, we ask whether
incorporating the system’s presentations in estimating a user’s preference
achieve a fair recommender system that is free of bias (_i.e._ , where
preference estimates can be adjusted to potentially misleading user behavior
towards any limited and systematic presentation), novel (_i.e._ , is capable
of eventually finding and presenting to the user her favorite options even if
she was not aware of them to begin with), responsible (_e.g._ , avoiding
censorship or overestimation of promoted and popular options) and
representative (_i.e._ , sufficiently presenting all options over the course
of interactions).

We then give synthetic examples mimicking challenges towards a “fair"
personalization machinery, and demonstrate that explicitly conditioning on
systematic exposure ensures robustness to promotion and unfair comparisons,
and discovery of initially censored favorites.

##  2 Problem Setup and Methodology

We assume an interactive system where the user chooses an option $k$ from a
systematically selected subset of all alternatives, a presentation $C$. Here,
$k\in[K]\coloneqq\\{1,2,\cdots,K\\}$, and $C\in\mathcal{C}$, where
$\mathcal{C}$ denotes the set of all non-empty subsets of $[K]$. We assume a
discrete choice model, an approach that received recent attention in
recommender systems literature [_e.g._ 14, 6], where independence of
irrelevant alternatives holds: relative preferability of an option to another
is independent of other alternatives included in, or absent from the
presentation. The model also conforms with Luce’s choice axiom [17]: i)
options admit a total ordering in their probability of being chosen ii) the
user chooses an option from a certain finite subset of the elements with
probability proportional to the original choice probability of that option,
_i.e._ , the user picks option $k$ from $C$ with probability $p(k\mid
C)\propto p(k\mid[K])$.

The task of the hypothesized _fair_ personalization system is two-fold. The
inference task is to accurately estimate the user’s overall preferences from
her choices (_e.g._ , clicks) which are limited to systematically presented
subsets of alternatives. Incorporation of presentation in inference is
essential to successfully avoid biased or inconsistent estimates [13, 20]. The
discovery task—as $K$ is so large in practice—is to assume responsibility for
_finding all good items_ without overlooking any alternative [10].

Inference can be carried out with any unbiased estimator of preferences from
partial feedback as, _e.g._ , Caron and Doucet [5] described for pairwise
preferences case and Guiver and Snelson [9] or Çapan et al. [4] for $L$-wise
($L<K$) preferences. The discovery task can be handled with a presentation
mechanism that explores “novel” items, and eventually discovers and composes
presentations with the estimated top-$L$ alternatives. Such tasks are widely
framed as “bandit problems” [12].

We use the Dirichlet-Luce model and the associated presentation mechanism that
Çapan et al. [4] describe. This discrete choice model presents a Bayesian
treatment of modeling preferences (cast as choice probabilities) by explicitly
taking systematic exposure into account, thus eliminating feedback loops. The
model is shown to approach overall preferences from a presentation-choice data
set and ensures _independence of unexplored alternatives_ —it does not impose
negative bias towards never-presented options. The conjugate Bayesian
treatment leads to a straightforward _online learning to present_ algorithm
based on Thompson sampling [23], and is shown to achieve superior performance
in various online preference learning simulations. When the systematic
presentations are naively ignored, _i.e._ , the user is assumed to pick an
option $k$ with probability $p(k\mid[K])$ regardless of the presentation,
Dirichlet-Luce reduces to the Dirichlet-Multinomial model.

At this point, we need to clarify some aspects of the assumed setup. We
consider a simplistic single user-system interaction scenario. But as a
probabilistic building block, the setup can be reused in a more complex,
collaborative recommender system. We ignore the position bias, _i.e._ , the
choice probability being dependent on the position of the option within the
presentation [7]. We assume that the user is able to review the shortlisted
alternatives and make a choice based on latent preferences. We ignore that the
repeated and systematic exposure might actually change users’ interests,
leading to an _echo chamber_. We refer to Jiang et al. [11] for such an
analysis, where sufficient conditions that lead to _interest extremes_ are
provided. It is worth noting that the Dirichlet-Luce model with the associated
presentation mechanism at least matches two necessary conditions to avoid such
degeneracy points, by naturally allowing a “growing pool of alternatives” and
due to the randomization inherent in Thompson sampling. We assume that the
user picks one of the presented options, although the model can be extended to
include an artificial ‘browse’ option corresponding to opting not to choose.
We base this assumption on the “principle of least effort [25],” _i.e._ , the
user would conveniently pick from what is presented to her unless the
presented alternatives were too unsatisfactory. Extensions to the model are
conjectured to address some of the limitations as discussed above. The others
are irrelevant to our concern, nevertheless, we mention them for clarity.

We underline that we do not claim that the model is vital to eliminate
feedback loops (see, for instance, [21, 16, 22] for alternative methods). Yet
we believe, and are concerned with in this paper, that the Dirichlet-Luce
model, in comparison to the Dirichlet-Multinomial, provides a test bed to
assess whether remedying feedback loops could correct some of the biases
commonly encountered in personalized recommender systems.

##  3 Simulations

We design a set of simulations to illustrate that the personalization
mechanism of the interactive systems accounting for the systematic exposure,
accompanied with a bandit algorithm for online learning to present, addresses
biased preference estimates due to over-presentation and under-presentation.

We make a comparison between Dirichlet-Luce and Dirichlet-Multinomial models.
The former model infers preferences based on previous choices from systematic
presentations that the naive Dirichlet-Multinomial ignores. For both models,
we consider a Thompson sampling-based presentation mechanism. Contrary to a
greedy mechanism that presents top-$L$ (of $K$) options to the user based on
the posterior preference estimate, Thompson sampling composes a presentation
from a posterior preference sample, thereby achieves exploration of under-
presented alternatives.

We consider an interactive system setup where the user’s preferences,
represented as choice probabilities $\theta_{k}=p(k\mid[K])$ $\forall
k\in[K]$, are latent. Over the course of interactions, the system presents
$\\{C_{t}\mid t=1\cdots T\\}$ (succinctly denoted as $C_{1:T}$) and observes
choice feedback $k_{1:T}$ (where $k_{t}\in C_{t}$). We assume for each
interaction, $L=2$ of $K=5$ alternatives are presented to the user, and the
user picks one of them. For ease of exposition, we assume
$\theta_{1}>\theta_{2}>\cdots>\theta_{K}$ without loss of generality.

Two scenarios are considered to demonstrate how the two models handle
potentially biased setups that might lead to underestimation or overestimation
of true choice probabilities:

Robustness to promotion. We assume a system where a certain option is included
in every presentation. A fair system would _not_ overestimate the preference
probability of this option. This scenario also subsumes the _popularity bias_
, as we artificially include a popular option. Overestimation due to over-
presentation can be corrected by conditioning on the presentations, as
illustrated in Figure 1.

Figure 1: Final (after $T=10000$ interactions) preference estimates
($\hat{\theta}$) averaged over 10 runs when the option 3 is promoted, _i.e._ ,
it is included in every presentation. Over-presented option 3 is over-
estimated (right), whereas conditioning on presentations fixes this bias
(left). Shaded regions denote the standard deviation.

Discovery of censored favorites. Conversely, we assume a system where
originally favorable options are initially _censored_ , _i.e._ , not included
in presentations. A fair system would correct the bias towards initial choices
and give each option equal opportunity to be presented first by not
underestimating the choice probabilities of the censored options, and then by
eventually learning to present the “best" options with the discovery
mechanism. In Figure 2, we reiterate the illustration in [4, Section A.2].

(a) Dirichlet-Luce

(b) Dirichlet-Multinomial

Figure 2: Preference estimates after 100 choices are made from originally
inferior options $\\{4,5\\}$ (left), and final preference estimates after
$T=10000$ interactions (right). Conditioning on presentations does not impose
negative bias towards censored options, and the implied personalization model
eventually learns to present the best two options (a). On the other hand,
over-presented options are overestimated in (b).

It is worth noting that the unbiased results are at the cost of computation.
Many quantities of interest for the Dirichlet-Luce model are intractable [4],
and we resort to Monte Carlo estimates.

Robustness to unfair comparisons. The astute reader would suspect that
Dirichlet-Luce modeling assumptions would introduce other biases. For
instance, repetitive recommendation of a relatively good option along with a
more superior one might lead the system to develop a misconception on this
option that it is overall inferior. The initial misconception is corrected
over the course of interactions, as demonstrated in Figure 3.

Figure 3: When an initial 100 choices are made from the alternatives
$\\{1,2\\}$, Dirichlet-Luce initially imposes negative bias towards option $2$
(left). Over the course of interactions, the system captures that option $2$
is still preferable to other, originally inferior options (right).

##  4 Discussion

A personalization system, _e.g._ , a recommender system, “learns a mechanism
from mechanism induced data [15].” Ignoring this feedback loop is unfair to
both sides (the user and the content provider) of the interactive system due
to overestimation of the over-presented, or underestimation of the under-
presented alternatives. We gave synthetic examples that illustrate promotion
and censorship, and demonstrated the stark difference between ignoring and
explicitly including the systematic exposure to the inference mechanism. As a
future work, these experiments can be conducted with multi-user setups and
real-world data to check if the personalization mechanism of interest is
competent to overcome fairness problems that we investigate.

## References

  * Abdollahpouri [2019] Himan Abdollahpouri.  Popularity bias in ranking and recommendation.  In _The 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 27–28, 2019.
  * Abdollahpouri et al. [2017] Himan Abdollahpouri, Robin Burke, and Bamshad Mobasher.  Controlling popularity bias in learning-to-rank recommendation.  In _Proceedings of the Eleventh ACM Conference on Recommender Systems_ , pages 42–46. ACM, 2017.
  * Abdollahpouri et al. [2019] Himan Abdollahpouri, Robin Burke, and Bamshad Mobasher.  Managing popularity bias in recommender systems with personalized re-ranking.  _arXiv preprint arXiv:1901.07555_ , 2019.
  * Çapan et al. [2019] Gökhan Çapan, İlker Gündoğdu, Ali Caner Türkmen, Çağrı Sofuoğlu, and Ali Taylan Cemgil.  A Bayesian Choice Model for Eliminating Feedback Loops.  _arXiv preprint arXiv:1908.05640_ , 2019.
  * Caron and Doucet [2012] Francois Caron and Arnaud Doucet.  Efficient Bayesian Inference for Generalized Bradley–Terry Models.  _Journal of Computational and Graphical Statistics_ , 21(1):174–196, 2012.
  * Covington et al. [2016] Paul Covington, Jay Adams, and Emre Sargin.  Deep Neural Networks for YouTube Recommendations.  In _Proceedings of the 10th ACM Conference on Recommender Systems_ , New York, NY, USA, 2016.
  * Craswell et al. [2008] Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey.  An Experimental Comparison of Click Position-Bias Models.  In _Proceedings of the 2008 International Conference on Web Search and Data Mining_ , pages 87–94. ACM, 2008.
  * Farnadi et al. [2018] Golnoosh Farnadi, Pigi Kouki, Spencer K Thompson, Sriram Srinivasan, and Lise Getoor.  A fairness-aware hybrid recommender system.  _arXiv preprint arXiv:1809.09030_ , 2018.
  * Guiver and Snelson [2009] John Guiver and Edward Snelson.  Bayesian Inference for Plackett-Luce Ranking Models.  In _Proceedings of the 26th Annual International Conference on Machine learning_ , pages 377–384. ACM, 2009.
  * Herlocker et al. [2004] Jonathan L Herlocker, Joseph A Konstan, Loren G Terveen, and John T Riedl.  Evaluating collaborative filtering recommender systems.  _ACM Transactions on Information Systems_ , 22(1):5–53, 2004.
  * Jiang et al. [2019] Ray Jiang, Silvia Chiappa, Tor Lattimore, Andras Agyorgy, and Pushmeet Kohli.  Degenerate Feedback Loops in Recommender Systems.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , 2019.
  * Lattimore and Szepesvári [2019] Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge (to appear), 2019.
  * Liang et al. [2016] Dawen Liang, Laurent Charlin, and David M Blei.  Causal Inference for Recommendation.  In _UAI Workshop on Causation: Foundation to Application_ , 2016.
  * Liang et al. [2018] Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara.  Variational Autoencoders for Collaborative Filtering.  In _Proceedings of the 2018 World Wide Web Conference on World Wide Web_ , pages 689–698, 2018.
  * Liu et al. [2015] Tie-Yan Liu, Wei Chen, and Tao Qin.  Mechanism Learning with Mechanism Induced Data.  In _AAAI_ , pages 4037–4041, 2015.
  * Liu and Burke [2018] Weiwen Liu and Robin Burke.  Personalizing fairness-aware re-ranking.  _arXiv preprint arXiv:1809.02921_ , 2018.
  * Luce [1959] R. Ducan Luce.  _Individual Choice Behavior_.  Wiley, 1959.
  * Mehrotra et al. [2018] Rishabh Mehrotra, James McInerney, Hugues Bouchard, Mounia Lalmas, and Fernando Diaz.  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_ , pages 2243–2251. ACM, 2018.
  * Pariser [2011] Eli Pariser.  _The Filter Bubble: What the Internet is hiding from you_.  Penguin UK, 2011.
  * Schmit and Riquelme [2018] Sven Schmit and Carlos Riquelme.  Human Interaction with Recommendation Systems.  In _Proceedings of the 21th International Conference on Artificial Intelligence and Statistics_ , 2018.
  * Sinha et al. [2016] Ayan Sinha, David F Gleich, and Karthik Ramani.  Deconvolving Feedback Loops in Recommender Systems.  In _Advances in Neural Information Processing Systems_ , pages 3243–3251, 2016.
  * Sun et al. [2019] Sami Khenissi Sun, Olfa Nasraoui, and Wenlong Patrick Shafto.  Debiasing the human-recommender system feedback loop in collaborative filtering.  In _Companion Proceedings of The 2019 World Wide Web Conference_ , pages 645–651. ACM, 2019.
  * Thompson [1933] William R Thompson.  On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Yao and Huang [2017] Sirui Yao and Bert Huang.  Beyond parity: Fairness objectives for collaborative filtering.  In _Advances in Neural Information Processing Systems_ , pages 2921–2930, 2017.
  * Zipf [1949] George K Zipf.  _Human Behavior and the Principle of Least Effort_.  Addison Wesley Press, Inc., 1949.