# Model-based Unbiased Learning to Rank

Dan Luo<EMAIL_ADDRESS>Lehigh UniversityBethlehemPAUSA ,  Lixin Zou
<EMAIL_ADDRESS>Baidu Inc.BeijingChina ,  Qingyao Ai
<EMAIL_ADDRESS>Tsinghua UniversityBeijingChina ,  Zhiyu Chen∗
<EMAIL_ADDRESS>Amazon.com, Inc.SeattleWAUSA ,  Dawei Yin†
<EMAIL_ADDRESS>Baidu Inc.BeijingChina and  Brian D. Davison
<EMAIL_ADDRESS>Lehigh UniversityBethlehemPAUSA

(2023)

###### Abstract.

Unbiased Learning to Rank (ULTR), _i.e.,_ learning to rank documents with
biased user feedback data, is a well-known challenge in information retrieval.
Existing methods in unbiased learning to rank typically rely on click modeling
or inverse propensity weighting (IPW). Unfortunately, search engines face the
issue of a severe long-tail query distribution, which neither click modeling
nor IPW handles well. Click modeling usually requires that the same query-
document pair appears multiple times for reliable inference, which makes it
fall short for tail queries; IPW suffers from high variance since it is highly
sensitive to small propensity score values. Therefore, a general debiasing
framework that works well under tail queries is sorely needed. To address this
problem, we propose a model-based unbiased learning-to-rank framework.
Specifically, we develop a general context-aware user simulator to generate
pseudo clicks for unobserved ranked lists to train rankers, which addresses
the data sparsity problem. In addition, considering the discrepancy between
pseudo clicks and actual clicks, we take the observation of a ranked list as
the treatment variable and further incorporate inverse propensity weighting
with pseudo labels in a doubly robust way. The derived bias and variance
indicate that the proposed model-based method is more robust than existing
methods. Extensive experiments on benchmark datasets, including simulated
datasets and real click logs, demonstrate that the proposed model-based method
consistently outperforms state-of-the-art methods in various scenarios. The
code is available at https://github.com/rowedenny/MULTR.

Unbiased Learning to Rank; Doubly Robust; User Simulator

† Corresponding author.
∗ The work was done prior to joining Amazon.

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
Sixteenth ACM International Conference on Web Search and Data Mining; February
27-March 3, 2023; Singapore, Singapore††booktitle: Proceedings of the
Sixteenth ACM International Conference on Web Search and Data Mining (WSDM
’23), February 27-March 3, 2023, Singapore, Singapore††doi:
10.1145/3539597.3570395††isbn: 978-1-4503-9407-9/23/02††ccs: Information
systems Learning to rank

##  1\. Introduction

Search engines serve as one of the most important tools for accessing
information online. In modern search engines, learning to rank (LTR)
algorithms play a critical role by creating models to accurately order a list
of candidate documents based on their relevance to the query. As deep
supervised models have been widely applied and been state-of-the-art in many
ranking tasks (Dehghani et al., 2017; Zamani et al., 2018; Zou et al., 2022b,
2021; Ye et al., 2022; Chu et al., 2022), obtaining large-scale and high-
quality training data has become a bottleneck for the development of large
scale learning-to-rank systems (Chapelle et al., 2011; Zou et al., 2022c). In
practice, implicit feedback that reflects users’ information needs (Sanderson,
2010) provides natural, abundant sustainable training data for ranking
optimization without costly time consumption and human annotation. Therefore,
LTR with implicit feedback such as clicks has received considerable attention
in the IR community.

However, click data is biased since relevance is not the only factor
influencing users’ clicks. For example, position bias occurs because users are
more likely to examine documents at higher ranks (Craswell et al., 2008;
Joachims et al., 2007). Consequently, the highly ranked document may receive
more clicks, and the relevant document may be perceived as a negative sample
simply by not being examined by users. Furthermore, ranking positions
(Joachims et al., 2005), display differences (Yue et al., 2010; Shen and Zhao,
2014), users’ first impression (Ovaisi et al., 2020), _etc_., also influence
the implicit feedback. These biases make the data deviate from reflecting true
relevance, and jeopardize the learned ranking model’s performance.

To be unaffected by biases (Joachims et al., 2017), there are two groups of
methods: (1) Click modeling methods explicitly introduce an additional factor
as bias, make hypotheses about users’ browsing behaviors, and estimate true
relevance by optimizing the likelihood of observed user clicks (Chapelle and
Zhang, 2009; Craswell et al., 2008; Dupret and Piwowarski, 2008; Wang et al.,
2013). Click models are straightforward yet effective, and they have made
promising progress for various applications, such as CTR prediction in live
recommendation (Guo et al., 2019) and grid view web applications (Zhuang et
al., 2021). However, search engines are faced with severe long-tail query
distribution, where click models can fall short since multiple observations
for the same query may not be available (Ai et al., 2018b). (2) Propensity-
based methods treat the click bias as the counterfactual factor (Rosenbaum and
Rubin, 1983), and re-weight the click data for a relevance-equivalent training
loss through inverse propensity weighting (IPW) (Joachims et al., 2017; Wang
et al., 2016). To this end, many approaches (Ai et al., 2018b; Hu et al.,
2019; Vardasbi et al., 2020b) are proposed to jointly learn user bias models
(i.e., propensity models) with unbiased rankers. However, propensity-based
methods generally suffer from high variance (Saito, 2020a), which can lead to
suboptimal estimation (Swaminathan and Joachims, 2015). Therefore, a general
debiasing framework with low variance is needed.

Figure 1. The framework of model-based unbiased learning to rank.

To address these challenges, we propose a novel model-based unbiased learning
to rank (MULTR) framework, as shown in Figure 1. MULTR consists of a context-
aware user simulator for addressing the data sparsity problem and a doubly-
robust learning algorithm for reducing the variance and achieving unbiased
estimation. Specifically, we first develop a user simulator that directly
learns from click data, which generates pseudo clicks for unobserved ranked
lists as data imputation and alleviates the sparse training data problem.
Remarkably, the user simulator is unbiased since the factor, _i.e.,_ the
position, influencing the click is being considered as its input, which
ensures the consistency between the training of user simulator and data
augmentation. However, as the user simulator cannot be as accurate as real
users, the discrepancy between pseudo and actual clicks may mislead the
ranking models, and unbiasedness cannot be guaranteed. To reduce the variance
and ensure the unbiasedness, we resort to doubly robust approaches. In
particular, we propose to take the observation of ranked lists as the
treatment, generate pseudo-click data via offline result randomization, and
incorporate the inverse propensity weighting with pseudo-click labels in a
doubly robust way, where the user simulator essentially functions as the
imputation model. The derived bias and variance indicate that the proposed
model-based method has low bias and low variance. Thus, it is more robust than
existing methods. To demonstrate the effectiveness of the proposed method, we
conduct extensive experiments on simulated and real datasets, and demonstrate
that the proposed model-based method consistently outperforms state-of-the-art
methods.

The contributions of the proposed model-based unbiased learning to rank
framework can be summarized as follows:

  * •

We propose model-based unbiased learning to rank (MULTR) – a general debiasing
framework with low variance.

  * •

We devise a user simulator, which addresses data sparsity by generating
pseudo-click labels for unobserved ranked lists.

  * •

We propose the observation of rank lists as treatment, which addresses the
treatment unobservability in unbiased learning to rank, and incorporate
inverse propensity weighting with pseudo labels in a doubly robust way.

  * •

We conduct extensive experiments on simulated datasets and real user click
logs to demonstrate the superiority of MULTR.

##  2\. Related Work

#### Unbiased Learning to Rank

To extract unbiased and reliable relevance signals from biased click signals,
there are two streams of unbiased learning to rank methodologies. One school
depends on click modeling, which makes assumptions about user browsing
behaviors. Such methods maximize the likelihood of the observed data, model
the examination probability and infer accurate relevance feedback from user
clicks (Craswell et al., 2008; Chapelle et al., 2009; Chuklin et al., 2016;
Mao et al., 2018). For example, Guo et al. (2019) propose a position-bias
aware learning framework for CTR prediction that models position-bias in
offline training and conducts online inference without biased information.
Wang et al. (2018) unify the training of the ranker model and the estimation
of examination propensity with a graphical model and an EM algorithm. Despite
their success, one major drawback of click models is that they usually require
that the same query-document pair appears multiple times for reliable
inference (Mao et al., 2019); thus they may fall short for tail queries. The
other school derives from counterfactual learning, which treats bias as a
counterfactual factor and debiases user clicks via inverse propensity
weighting (Joachims et al., 2017; Wang et al., 2016). Recent efforts jointly
model the propensity estimation and unbiased learning to rank. For instance,
Ai et al. (2018b) and Hu et al. (2019) present dual learning frameworks for
estimating bias and training a ranking model. Vardasbi et al. (2020a) propose
cascade model-based inverse propensity scoring for propensity estimation in
the cascade scenario. However, these methods ignore the severe high variance
problem in IPW-based methods, particularly for long-tail data. Our paper falls
in the same propensity-based framework; however, we address the high variance
problem by optimizing the ranking model in a doubly robust way, which has low
bias and low variance.

#### Model-based Methods

Model-based methods aim to construct a predictive user model and ask the
question of the counterfactual form “what will the user click if the search
result page is presented differently?”, which naturally fits debiasing. Recent
work has proposed some methods that improve ranking performance based on user
simulators. For example, Dai et al. (2020) propose a utility estimator to
generate counterfactual data to train the ranking model. Zhang et al. (2019)
develop a reinforcement learning algorithm to learn ranking policies in the
simulation environments. While both methods show promising improvements, the
theoretical guarantees with respect to unbiasedness are unclear. Different
from such work, we leverage the user simulator as the imputation model in a
doubly-robust way, which addresses the high bias issue caused by the
discrepancy between user simulator and real clicks. More importantly, our
derivation demonstrates the unbiasedness of the proposal. Our ablation study
verifies that the doubly robust approach can effectively leverage both real
and pseudo clicks, and improve the ranking performance.

#### Doubly-Robust Methods

Doubly-Robust (DR) methods have been widely applied to position-biased clicks.
Saito (2020b) proposes a DR method for post-click conversions. Guo et al.
(2021) further develop a more doubly robust estimator to reduce the variance.
Kiyohara et al. (2022) develop a cascade doubly robust estimator for off-
policy evaluation, Yuan et al. (2019) introduce a DR estimator for click-
through-rate prediction. Zou et al. (2022a) propose a doubly robust estimator
for relevance estimation. A significant difference between current DR
estimators and those in ULTR is that existing solutions use corrections based
on action propensities, which is similar to generic counterfactual estimation;
while ULTR needs examination propensities (Oosterhuis, 2022), which
unfortunately is unobservable in click logs. In this paper, we address this
challenge by taking the observation of rank lists as treatment, and
incorporate the inverse propensity weighting with pseudo-click labels in a
doubly-robust way.

##  3\. Preliminaries

This section presents the task of unbiased learning to rank and reviews the
preliminary methods of click modeling and propensity-based methods with their
strengths and weaknesses.

###  3.1. Task Formulation

Let $\mathcal{D}$ be the universal set of documents, and $\mathcal{Q}$ be the
universal set of queries. For a user-issued query $q\in\mathcal{Q}$, we use
$r_{d}$ to denote the relevance annotation over the query $q$ and document
$d\in\mathcal{D}$. The goal of learning to rank is to find a mapping function
from a query document pair $(q,d)$ to its relevance $r_{d}$ as
$f:\mathcal{Q}\times\mathcal{D}\rightarrow\mathbb{R}$. A corresponding local
loss function is usually proposed to learn the best $f$, given its retrieved
ranked list $\pi_{q}$ as,

(1)
$\ell_{ideal}(f,q|\pi_{q})=\sum_{d\in\mathcal{D}}\Delta(f(q,d),r_{d}|\pi_{q}),$

where $\Delta$ is a function that computes the individual loss on each
document. $\ell_{ideal}(f,q)$ is the ideal local ranking loss for optimizing
the ranking function $f$ with all the documents annotated. Without loss of
generality, we simplify the individual loss function
$\Delta(f(q,d),r_{d}|\pi_{q})$ as $\Delta(r_{d}|\pi_{q})$.

Typically, the relevance annotation $r_{d}$ is elicited through expert
judgment; thus $r_{d}$ is considered to be unbiased, but expensive. An
alternative approach is to use click data as relevance feedback from users.
Suppose there is a click dataset in which the clicks on documents with respect
to queries by an initial ranking model are logged. If we conduct learning to
rank by replacing the relevance label $r_{d}$ with click label $c_{d}$ in
Equation 1, then the empirical local ranking loss is derived as follows,

(2)
$\displaystyle\ell_{naive}(f,q|\pi_{o})=\sum_{d\in\pi_{o},c_{d}=1}\Delta(c_{d}|\pi_{o}),$

where $\pi_{o}$ is the observed ranked list, which is the ranked list
presented to users, and $c_{d}$ is a binary variable indicating whether the
document $d$ in the ranked list $\pi_{o}$ is clicked. However, this naive loss
function is biased. For instance, position bias occurs because users are more
likely to examine the documents at higher ranks (Joachims et al., 2017).
Consequently, highly ranked documents may receive more clicks, and relevant
(but unclicked) documents may be perceived as negative samples because they
are unexamined by users. To address this issue, unbiased learning-to-rank aims
to eliminate bias in click data and then train a ranking model with the
resulting user clicks.

###  3.2. Click Modeling

To eliminate biases in click data, one intuitive method is to model bias and
relevance as independent factors, and represent the joint effects of bias and
relevance with bias-aware click modeling (Guo et al., 2019; Liu et al., 2020).
Here we refer to the general approach as click modeling. Let $\mathbf{b}$ be
the bias features, and $\mathbf{x}_{d}$ be the vector representation of
document $d$, then the bias-aware click predictor is modeled as follows:

(3) $\hat{P}(c_{d}=1,q)=h(\mathbf{b};\phi)\oplus f(\mathbf{x}_{d};\theta),$

where $\hat{P}(c_{d}=1,q)$ is the estimated click probability of document $d$
of query $q$. $h$ is the bias model parameterized by $\phi$ that generates a
score based on the inputs of bias features. $f$ is the relevance prediction
model parameterized by $\theta$ that generates a relevance score based on the
relevance representations. $\oplus$ is an operation that combines the bias-
based score and the relevance score, which could be addition (Zhuang et al.,
2021), multiplication (Guo et al., 2019), _etc_. The general local ranking
loss of a bias-aware click predictor is defined as:

(4) $\displaystyle\ell_{CLICK}(f,h,q|\pi_{o})$
$\displaystyle=\sum_{d\in\pi_{o},c_{d}=1}\mathrm{CE}(\hat{P}(c_{d}=1,q),c_{d})$
$\displaystyle=\sum_{d\in\pi_{o},c_{d}=1}\mathrm{CE}\left(h(\mathbf{b};\phi)\oplus
f(\mathbf{x}_{d};\theta),c_{d}\right),$

where $c_{d}$ is a binary variable indicating whether document $d$ is clicked,
and $\mathrm{CE}(\cdot,\cdot)$ the cross-entropy function. When conducting the
relevance inference, one can easily eliminate the influence of bias by
dropping the scores from $h(\mathbf{b};\phi)$, _i.e.,_ directly ranking with
$f(\mathbf{x}_{d},\theta)$. Though click models work well with head queries,
they could fall short when multiple observations of the same query may not be
available (Ai et al., 2018b).

###  3.3. Propensity-based Methods

Inverse propensity weighting (IPW) is the first unbiased learning to rank
algorithm proposed under the propensity-based framework (Wang et al., 2016;
Joachims et al., 2017). Let $e_{d},c_{d}$ be the binary variables that
represent whether document $d$ is examined and clicked by a user, based on the
Examination Hypothesis (Richardson et al., 2007) that a user would only click
a document when it is observed by the user and considered relevant to the
user’s need, we have

(5) $c_{d}=1\Longleftrightarrow(e_{d}=1\ \ \text{and}\ \ r_{d}=1).$

Then, IPW instantiates the local ranking loss as

(6)
$\ell_{IPW}(f,q|\pi_{o})=\sum_{d\in\pi_{o},c_{d}=1}\frac{\Delta(c_{d}|\pi_{o})}{\hat{P}(e_{d}=1)},$

where $\hat{P}(e_{d}=1)$ is the estimated probability that document $d$ is
examined in the query session. A nice property is that only clicked documents
$c_{d}=1$ contribute to the estimation in Eq. 6.

#### Bias and Variance Analysis

We analyze the bias and variance of the inverse propensity weighting approach.

###### Theorem 3.1.

The bias of the IPW estimators is

(7)
$\displaystyle{Bias}[\ell_{IPW}(f,q|\pi_{o})]=\left|\sum_{d\in\pi_{o},r_{d}=1}\frac{P(e_{d}=1)-\hat{P}(e_{d}=1)}{\hat{P}(e_{d}=1)}\Delta(c_{d}|\pi_{o})\right|$

###### Proof.

Joachims et al. (2017) proved that a ranking model trained with clicks and IPW
loss will converge to the same model trained with true relevance labels; see
Ai et al. (2018b) for more detail. ∎

As shown in Theorem 3.1, when the estimated examination probability is
accurate, _i.e.,_ $P(e_{d_{i}}=1)=\hat{P}(e_{d_{i}}=1)$, then
$Bias[\ell_{IPW}]=0$, indicating accurate estimation can be achieved with rich
observation data. Then, we derive the variance of the IPW estimators.

###### Theorem 3.2.

The variance of the IPW estimator is

(8)
$\displaystyle\mathbb{V}_{\mathcal{O}}[\ell_{IPW}(f,q|\pi_{o})]=\sum_{d\in\pi_{o},c_{d}=1}\frac{P(e_{d}=1)(1-P(e_{d}=1))}{\hat{P}(e_{d}=1)^{2}}\Delta(c_{d}|\pi_{o})^{2}.$

###### Proof.

For the IPW estimator, its variance on the observed ranking documents is:

(9) $\displaystyle\mathbb{V}_{\mathcal{O}}[\ell_{IPW}(f,q|\pi_{o})]=$
$\displaystyle\mathbb{V}_{\mathcal{O}}\left[\sum_{d\in\pi_{o},c_{d}=1}\frac{\Delta(c_{d}|\pi_{o})}{\hat{P}(e_{d}=1)}\right]$
$\displaystyle=$
$\displaystyle\sum_{d\in\pi_{o},c_{d}=1}\mathbb{V}_{\mathcal{O}}\left[\frac{\Delta(c_{d}|\pi_{o})}{\hat{P}(e_{d}=1)}\right]$
$\displaystyle=$
$\displaystyle\sum_{d\in\pi_{o},c_{d}=1}\mathbb{V}_{\mathcal{O}}[e_{d}]\cdot\left(\frac{\Delta(c_{d}|\pi_{o})}{\hat{P}(e_{d}=1)}\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{d\in\pi_{o},c_{d}=1}\left(\mathbb{E}_{\mathcal{O}}[e^{2}_{d}]-\mathbb{E}^{2}_{\mathcal{O}}[e_{d}]\right)\cdot\left(\frac{\Delta(c_{d}|\pi_{o})}{\hat{P}(e_{d}=1)}\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{d\in\pi_{o},c_{d}=1}\frac{P(e_{d}=1)(1-P(e_{d}=1))}{\hat{P}(e_{d}=1)^{2}}\cdot\Delta(c_{d}|\pi_{o})^{2}.$

∎

Theorem 3.2 illustrates that the variance of IPW estimators depends on the
estimated propensity. When $\hat{P}(e_{d}=1)$ is small, it may lead to high
variance. Especially for long-tail queries with rare observation data, the
high variance of IPW becomes a problem that directly influences the
effectiveness of the ranker.

##  4\. Model-based Unbiased Learning to Rank

In this section, we first introduce the context-aware user simulator, which
generates pseudo-click labels for unobserved ranked lists as data imputation
and addresses the data sparsity. Afterwards, we propose a doubly robust
estimator, which takes the observation of ranked lists as the treatment, and
further incorporates inverse propensity weighting with pseudo labels from the
user simulator above in a doubly robust way. Lastly, we derive the bias and
variance of the proposed method, and demonstrate that our proposed method is
more robust than existing methods.

###  4.1. Context-aware User Simulator

The user simulator consists of two important components: a local context
encoder, which captures different feature distributions from different
queries, and a context-aware click decoder, which produces the click
probability of each document sequentially. The framework of our user simulator
is shown in Fig. 2.

Figure 2. Framework of the Context-aware User Simulator.

#### Local Context Encoder

To capture the characteristics of queries, _i.e.,_ different queries may have
different distributions in the feature space (Ai et al., 2018a), we first
design a local context encoder for each query and use it to refine the query-
specific features, as shown at the bottom block in Figure 2. Formally, given
the top $N$ documents $\\{d_{i}\\}_{i=1}^{N}$ in a ranked list $\pi_{q}$ from
top to bottom, and their corresponding feature vectors
$\\{\mathbf{x}_{i}\\}_{i=1}^{N}$, we use a bi-directional long short-term
memory (Hochreiter and Schmidhuber, 1997) network to obtain a contextual
representation of each document with respect to the entire ranked list:

(10) $\displaystyle\mathbf{h}_{i}$
$\displaystyle=[\overrightarrow{\text{LSTM}}(\mathbf{x}_{i},i);\overleftarrow{\text{LSTM}}(\mathbf{x}_{i},i)]$
$\displaystyle\mathbf{h}_{\pi_{q}}$
$\displaystyle=\mathbf{W}^{\top}\mathbf{h}_{N},$

where $[\cdot;\cdot]$ is concatenation, and
$\overrightarrow{\text{LSTM}}(\mathbf{x}_{i},i)$ processes the document $x$
from top to bottom and returns the LSTM hidden state at position $i$ (and vice
versa for the backward direction $\overleftarrow{\text{LSTM}}$). We then
produce the local context representation $\mathbf{h}_{\pi_{q}}$ by a linear
transformation of the last hidden state $\mathbf{h}_{N}$.

#### Context-aware Click Decoder

To characterize different influences from the previous actions, we encode
actions with an embedding matrix $\mathbf{A}$. In our settings, there are
three types of actions, _i.e.,_ click, skip, and unknown, where unknown is
designed for the initial step. We use $\mathbf{h}_{a_{t}}$ to denote the
action embedding corresponding to action $a_{t}$ at step $t$. The context-
aware click decoder is formulated as:

(11)
$\begin{split}\mathbf{z}_{\pi}&=\mathbf{W}_{1}^{\top}\mathbf{h}_{\pi_{q}}+\mathbf{b}_{1}\\\
\mathbf{z}_{x_{i}}&=\mathbf{W}_{2}^{\top}\mathbf{x}_{i}+\mathbf{b}_{2}\\\
\mathbf{z}_{a_{t}}&=\mathbf{W}_{3}^{\top}\mathbf{h}_{a_{t}}+\mathbf{b}_{3}\\\
\mathbf{z}_{t}&=[\mathbf{z}_{\pi};\mathbf{z}_{x_{i}};\mathbf{z}_{a_{t}}]\\\
\mathbf{h}_{t}&=\overrightarrow{\text{LSTM}}(\mathbf{z}_{t},t),\\\
\end{split}$

where
$\mathbf{W}_{1},\mathbf{W}_{2},\mathbf{W}_{3},\mathbf{b}_{1},\mathbf{b}_{2},\mathbf{b}_{3}$
are the trainable parameters used to transform the query context vector, the
document vector and the previous action embedding, respectively.

At each step $t$, the hidden state $\mathbf{h}_{t}$ is projected into a
conditional click probability score through the sigmoid function:

(12) $p_{t}=\mathrm{sigmoid}(\mathbf{W}_{4}^{\top}\mathbf{h}_{t}+b_{4}),$

where $\mathbf{W}_{4},\mathbf{b}_{4}$ are trainable parameters, and
$p_{t}\in[0,1]$ represents the probability that a user clicks document
$d_{t}$.

#### User Simulator Optimization

After obtaining the click probability score $p_{t}$ for each document, we
train the user simulator by applying the binary cross-entropy:

(13) $\ell_{e}(g,q|\pi_{o})=\sum_{t=1}^{N}\left(-c_{t}\log
p_{t}-(1-c_{t})\log(1-p_{t})\right)+\lambda||\phi||^{2},$

where $g$ is the whole context-aware user simulator, $c_{t}$ denotes the click
label of document $d_{t}$ in observed ranked list $\pi_{o}$, $\phi$ denotes
all the parameters of the user simulator $g$, and $\lambda$ denotes the
$L_{2}$ regularization coefficient.

Discussion. It is worth noting that the goal of this paper is not to propose a
high-performance user simulator. More sophisticated models, such as utility
estimator (Dai et al., 2020) and UBS4RL (Zhang et al., 2022), can be applied
here. We leverage the user simulator as the imputation model to generate
pseudo-click labels for an arbitrary ranked list. In the next section, we will
leverage the user simulator in a doubly robust way to obtain unbiased ranking
models.

###  4.2. Doubly Robust Learning

User simulators have the benefit of data imputation (Hernández-Lobato et al.,
2014). However, directly optimizing the ranking model through the user
simulator could be highly biased due to the discrepancy between pseudo labels
and actual clicks, _i.e.,_ the pseudo clicks cannot be as accurate as real
clicks. To address this problem, we resort to the doubly robust approach.
Unfortunately, the treatment, _i.e.,_ document examination, is not directly
observable in click data. It is because when a document is not clicked, we
cannot determine whether the user chose not to click or the user did not
examine it (Oosterhuis, 2022). To overcome this bottleneck, we propose to take
the observation of ranked lists as the treatment. After that, we incorporate
inverse propensity weighting with pseudo-clicked labels in a doubly robust
way, where the user simulator essentially functions as the imputation model.

Before we describe our doubly robust estimator for unbiased learning to rank,
we introduce two concepts: prediction error and imputation error. We refer to
the local ranking loss $\ell_{naive}$ in Eq 2 with actual clicks as prediction
error. Then the imputed error $\ell_{IMP}$, _i.e.,_ the estimated value of the
prediction error, is defined as:

(14)
$\ell_{IMP}(f,q|\pi_{o})=\sum_{d\in\pi_{o},\hat{c}_{d}=1}\Delta(\hat{c}_{d}|\pi_{o}),$

where $\hat{c}_{d}$ is the imputed click generated from the user simulator for
each document $d$ in the observed ranked list $\pi_{o}$ under query $q$.

Let $\Pi_{q}$ be the set of document permutations, _i.e.,_ all possible ranked
lists. We simplify $\Pi_{q}$ as $\Pi$ when there is no ambiguity for the
issued query $q$. We propose our doubly robust (DR) estimator by combining the
imputed errors for all ranked lists, and the IPW-based prediction error for
observed ranked lists. The loss function of the DR estimator given query $q$
is defined as:

(15) $\displaystyle\ell_{DR}(f,q|\pi_{o})$
$\displaystyle=\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\Bigg{\\{}\hat{\ell}_{IMP}(f,q|\pi)$
$\displaystyle\quad+o_{\pi}\bigg{[}\ell_{IPW}(f,q|\pi)-\hat{\ell}_{IPW}(f,q|\pi)\bigg{]}\Bigg{\\}}$
$\displaystyle=\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\Bigg{\\{}\Bigg{.}\sum_{d\in\pi,\hat{c}_{d}=1}\Delta(\hat{c}_{d}|\pi)$
$\displaystyle\quad+o_{\pi}\bigg{[}\sum_{d\in\pi,c_{d}=1}\frac{\Delta(c_{d}|\pi)}{\hat{P}(e_{d}=1)}-\sum_{d\in\pi,\hat{c}_{d}=1}\frac{\Delta(\hat{c}_{d}|\pi)}{\hat{P}(e_{d}=1)}\bigg{]}\Bigg{.}\Bigg{\\}},$

where
$\hat{\ell}_{IPW}(f,q|\pi)=\sum_{d\in\pi,\hat{c}_{d}=1}\frac{\Delta(\hat{c}_{d}|\pi)}{\hat{P}(e_{d}=1)}$
is the propensity score weighted imputed error, and
$o_{\pi}=\mathbbm{1}\\{\pi=\pi_{o}\\}$ indicates whether $\pi$ is an observed
ranked list. A nice property of the DR estimator is: if either the imputed
error of any unobserved ranked list or the estimated propensities of any
observed ranked list is accurate, the DR estimator is then unbiased (Guo et
al., 2021; Zou et al., 2022a), which is recognized as double robustness.

Discussion. Careful readers may notice that our method is similar in spirit to
result randomization. Ideally, if the pseudo-click labels generated from the
user simulator are accurate for any unobserved ranked lists, learning from
user simulators would be equivalent to learning from online result
randomization, which is unbiased in principle (Joachims et al., 2017; Wang et
al., 2016). However, online result randomization is often impractical since it
can negatively affect the user experience. Our method overcomes the
aforementioned limitations by leveraging the user simulator in a doubly robust
way, and simultaneously obtains unbiased ranking models.

###  4.3. Bias and Variance of DR Estimator

In this section, we derive the bias and variance of MULTR, and prove its
double robustness.

###### Theorem 4.1.

Let $\delta_{\pi,d}=c_{d}\Delta(c_{d}|\pi)-\hat{c}_{d}\Delta(\hat{c}_{d}|\pi)$
be the error deviation, and
$\rho_{q,{d}}=\frac{P(e_{d}=1)-\hat{P}(e_{d}=1)}{\hat{P}(e_{d}=1)}$ be the
propensity deviation. The bias of the doubly robust (DR) estimator is

(16) $\displaystyle
Bias[\ell_{DR}(f,q|\pi_{o})]=\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\sum_{d\in\pi}\rho_{\pi,d}\delta_{\pi,d}\right|.$

###### Proof.

According to the definition of bias,

(17) $\displaystyle Bias[\ell_{DR}(f,q|\pi_{o})]$ $\displaystyle=$
$\displaystyle\Bigg{|}\mathbb{E}_{\mathcal{O}}\left[\ell_{DR}(f,q|\pi_{o})\right]-\ell_{ideal}(f,q|\pi_{o})\Bigg{|}$
$\displaystyle=$
$\displaystyle\Bigg{|}\mathbb{E}_{\mathcal{O}}\left[\ell_{DR}(f,q|\pi_{o})\right]-\sum_{d\in\pi,r_{d}=1}\Delta(c_{d}|\pi)\Bigg{|}$
$\displaystyle=$
$\displaystyle\Bigg{|}\mathbb{E}_{\mathcal{O}}\left[\ell_{DR}(f,q|\pi_{o})\right]-\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\sum_{d\in\pi,c_{d}=1}\Delta(c_{d}|\pi)\Bigg{|}$
$\displaystyle=$
$\displaystyle\Bigg{|}\Bigg{.}\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\Bigg{.}\mathbb{E}_{\mathcal{O}}\bigg{\\{}\big{[}\sum_{d\in\pi,\hat{c}_{d}=1}\Delta(\hat{c}_{d}|\pi)-\sum_{d\in\pi,c_{d}=1}\Delta(c_{d}|\pi_{o})\big{]}$
$\displaystyle\quad+o_{\pi}\big{[}\sum_{d\in\pi,c_{d}=1}\frac{\Delta(c_{d}|\pi)}{\hat{P}(e_{d}=1)}-\sum_{d\in\pi,\hat{c}_{d}=1}\frac{\Delta(\hat{c}_{d}|\pi)}{\hat{P}(e_{d}=1)}\big{]}\bigg{\\}}\Bigg{.}\Bigg{|}\Bigg{.}$

In the third line, we expand $\ell_{ideal}$ with online result randomization.
Based on the examination hypothesis in Eq 5, the terms in the first row can be
derived as,

(18)
$\displaystyle\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\mathbb{E}_{\mathcal{O}}\left[\sum_{d\in\pi,\hat{c}_{d}=1}\Delta(\hat{c}_{d}|\pi)-\sum_{d\in\pi,c_{d}=1}\Delta(c_{d}|\pi_{o})\right]\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\sum_{d\in\pi}\left[\hat{c}_{d}\cdot\Delta(\hat{c}_{d}|\pi)-c_{d}\cdot\Delta(c_{d}|\pi)\right]\right|.$

Then the second term can be derived as,

(19)
$\displaystyle\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\mathbb{E}_{\mathcal{O}}\left\\{o_{\pi}\left[\sum_{d\in\pi,c_{d}=1}\frac{\Delta(c_{d}|\pi)}{\hat{P}(e_{d}=1)}-\sum_{d\in\pi,\hat{c}_{d}=1}\frac{\Delta(\hat{c}_{d}|\pi)}{\hat{P}(e_{d}=1)}\right]\right\\}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\mathbb{E}_{\mathcal{O}}\left\\{o_{\pi}\left[\sum_{d\in\pi,c_{d}=1}\frac{\Delta(c_{d}|\pi)}{\hat{P}(e_{d}=1)}\right]\right\\}-\mathbb{E}_{\mathcal{O}}\left\\{o_{\pi}\left[\sum_{d\in\pi,\hat{c}_{d}=1}\frac{\Delta(\hat{c}_{d}|\pi)}{\hat{P}(e_{d}=1)}\right]\right\\}\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\sum_{d\in\pi}\frac{P(e_{d}=1)}{\hat{P}(e_{d}=1)}\left[c_{d}\cdot\Delta(c_{d}|\pi)-\hat{c}_{d}\cdot\Delta(\hat{c}_{d}|\pi)\right]\right|.$

Finally, combing the two parts above, we derive the bias of the proposed DR
estimator

(20) $\displaystyle
Bias[\ell_{DR}(f,q|\pi_{o})]=\left|\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\sum_{d\in\pi}\rho_{q,d}\delta_{q,d}\right|.$

∎

As shown in Theorem 4.1, when the imputed error is accurate $(\delta_{q,d}=0)$
or the propensity estimation is accurate $(\rho_{q,d}=0)$, the bias of DR
estimator $Bias\left[\ell_{DR}(f,q|\pi_{o})\right]=0$. Next, we derive the
variance of the DR estimator.

###### Theorem 4.2.

The variance of the DR estimator is

(21)
$\displaystyle\mathbb{V}_{\mathcal{O}}[\ell_{DR}(f,q|\pi_{o})]=\frac{1}{|\Pi|^{2}}\sum_{\pi\in\Pi}\sum_{d\in\pi}\bigg{\\{}\Bigg{.}\frac{P(e_{d}=1)\left(1-P(e_{d}=1)\right)}{\hat{P}(e_{d}=1)^{2}}\cdot\delta^{2}_{q,d}\bigg{\\}}\Bigg{.}$

###### Proof.

The variance of $\ell_{DR}(f,q|\pi_{o})$ with respect to the observation
indicator $\mathcal{O}$ is

(22) $\displaystyle\mathbb{V}_{\mathcal{O}}[\ell_{DR}(f,q|\pi_{o})]$
$\displaystyle=$
$\displaystyle\frac{1}{|\Pi|^{2}}\sum_{\pi\in\Pi}\mathbb{V}_{\mathcal{O}}\Bigg{\\{}\hat{\ell}_{IMP}(f,q|\pi)+\mathcal{O}\bigg{[}\ell_{IPW}(f,q|\pi)-\hat{\ell}_{IPW}(f,q|\pi)\bigg{]}\Bigg{\\}}$
$\displaystyle=$
$\displaystyle\frac{1}{|\Pi|^{2}}\sum_{\pi\in\Pi}\mathbb{V}_{\mathcal{O}}[o_{\pi}]\cdot\bigg{[}\ell_{IPW}(f,q|\pi)-\hat{\ell}_{IPW}(f,q|\pi)\bigg{]}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{|\Pi|^{2}}\sum_{\pi\in\Pi}\left\\{\mathbb{V}_{\mathcal{O}}[o_{\pi}]\cdot\left[\sum_{d\in\pi}\left(\frac{c_{d}\cdot\Delta(c_{d}|\pi)}{\hat{P}(e_{d}=1)}-\frac{\hat{c}_{d}\cdot\Delta(\hat{c}_{d}|\pi)}{\hat{P}(e_{d}=1)}\right)\right]^{2}\right\\}$
$\displaystyle=$
$\displaystyle\frac{1}{|\Pi|^{2}}\sum_{\pi\in\Pi}\left\\{\frac{P(e_{d}=1)\left(1-P(e_{d}=1)\right)}{\hat{P}(e_{d}=1)^{2}}\cdot\delta^{2}_{q,d}\right\\},$

where the third step utilizes the similar derivation in Eq 9.

∎

In Theorem 4.2, we demonstrate that the variance of the DR estimator depends
on the estimated propensity, _i.e.,_ $\hat{P}(e_{d}=1)$, which may lead to a
high variance problem. Recall the variance of the IPW estimator in Theorem
3.2; it is worth noting that our DR estimator can still reduce the variance of
the IPW estimator, if any given observed ranked list satisfies
$\left[c_{d}\Delta(c_{d}|\pi)-\hat{c}_{d}\Delta(\hat{c}_{d}|\pi)\right]^{2}\leq[c_{d}\Delta(c_{d}|\pi)]^{2}$.
Then, the variance of the DR estimator is smaller than that of the IPW-based
estimator.

###  4.4. Learning Framework

We summarize the learning framework in Algorithm 1. It is worth noting that
the proposed MULTR is a plug-in model, which can be seamlessly integrated into
any IPW-based unbiased learning to rank framework without result
randomization, such as DLA (Ai et al., 2018b) and REM (Wang et al., 2018).

1

Input : query set $\mathcal{Q}$, an IPW-based framework $F$

Output : ranking model $f(\theta)$ and user simulator $g(\phi)$

2

3Initialize the parameters $\theta,\phi$ ;

4 for  _number of steps for training the user simulator_ do

5 Sample a batch of queries $Q$ from $\mathcal{Q}$, with observed ranked lists
$\Pi_{o}$ ;

6 Update $\phi$, according to Eq. 13 ;

7

8 end for

9

10for  _number of steps for training the unbiased ranking model_ do

11 Sample a batch of queries $Q$ from $\mathcal{Q}$, with observed ranked
lists $\Pi_{o}$ ;

12 Obtain unobserved ranked lists $\Pi_{u}$ by result randomization over
$\Pi_{o}$ ;

13 Generate pseudo-click labels $\hat{c}_{d}$ for all ranked list
$\Pi=\Pi_{o}\cup\Pi_{u}$ by sampling on the click probabilities, according to
Eq. 12111Due to the large sample space of all possible ranked lists (_i.e.,_
$N$ documents have $N!$ permutations), we decrease the sample size in
practice. ;

14 Update $\theta$, according to Eq. 15

15 end for

16

Algorithm 1 Model-based Unbiased Learning to Rank

##  5\. Experimental Setup

To analyze the effectiveness of MULTR, we conduct two types of experiments.
The first is simulation experiments based on two of the largest public
learning-to-rank datasets. The second is an experiment based on the actual
rank lists and user clicks collected from a commercial web search engine.

###  5.1. Simulation Experiment Setup

To fully investigate the spectrum of propensity estimation and performance of
MULTR, we conduct experiments on two of the largest publicly available
datasets:

  * •

Yahoo! LETOR222https://webscope.sandbox.yahoo.com/ comes from the Learn to
Rank Challenge version 2.0 (Set 1), and it is one of the largest benchmark
datasets widely used in unbiased learning to rank (Ai et al., 2018b; Hu et
al., 2019). It consists of 29,921 queries and 710K documents. Each query-
document pair is represented by a 700-D feature vector, and annotated with
5-level relevance labels (Chapelle and Chang, 2011).

  * •

Istella-S333http://quickrank.isti.cnr.it/istella-dataset/ contains 33K queries
and 3,408K documents (roughly 103 documents per query) sampled from a
commercial Italian search engine. Each query-document pair is represented by
220 features and annotated with 5-level relevance judgments (Lucchese et al.,
2016).

We follow the predefined data split of training, validation and testing of all
datasets. The Yahoo! set splits the queries arbitrarily and uses 19,944 for
training, 2,994 for validation and 6,983 for testing. The Istella-S dataset
has been divided into train, validation and test sets according to a
$60\%-20\%-20\%$ scheme.

#### Click Simulation

We generate click data on both datasets with a two-step process as in Joachims
et al. (2017) and Ai et al. (2018b). First, we train a Rank SVM model
(Joachims, 2006) using $1\%$ of the training data with real relevance labels
to generate the initial ranked list $\pi_{q}$ for each query $q$. Then, we
simulate the user browsing process and sample clicks from the initial ranked
list by utilizing the simulation model. The simulation model generates clicks
based on the examination hypothesis in Equation 5. Following the methodology
proposed by Chapelle _et al._ (Chapelle et al., 2009), the relevance
probability is set to be

(23)
$\Pr(r_{d_{i}}=1|\pi_{q})=\epsilon+(1-\epsilon)\frac{2^{y}-1}{2^{y_{\mathrm{max}}}-1},$

where $y\in[0,y_{\mathrm{max}}]$ is the relevance label of the document
$d_{i}$, and $y_{\mathrm{max}}$ is the maximum value of $y$, which is 4 on
both datasets. $\epsilon$ is the noise level, which models click noise such
that irrelevant documents (_i.e.,_ $y=0$) have a non-zero probability to be
perceived as relevant and clicked. We fix $\epsilon=0.1$ as the default
setting.

We use the cascade model (Craswell et al., 2008) to generate the examination
probability. It is a context-aware click model, and a user is modeled as
searching and clicking documents from top to bottom, and deciding whether to
click each result before moving to the next; users stop examining a search
result page after the first click. The cascade model is defined as,

(24) $\displaystyle\Pr(e_{d_{1}}=1)=$ $\displaystyle 1$
$\displaystyle\Pr(e_{d_{j}}|e_{d_{j-1}}=e,c_{d_{j-1}}=c)=$ $\displaystyle
e\cdot(1-c)$

where $e$ and $c$ are binary variables that indicate whether the document $d$
is examined and clicked.

#### Baselines

To demonstrate the effectiveness of our proposed method, we compare with
baseline methods, including IPW-based methods and bias modeling methods, which
are widely used in ULTR problems.

  * •

DLA: The Dual Learning Algorithm (Ai et al., 2018b) treats the problem of
unbiased learning to rank and unbiased propensity estimation as a dual
problem, such that they can be optimized simultaneously.

  * •

REM: The Regression EM model (Wang et al., 2018) uses an EM framework to
estimate the propensity scores and ranking scores.

  * •

PairD: The Pairwise Debiasing (PairD) Model (Hu et al., 2019) uses inverse
propensity weighting for pairwise learning to rank.

  * •

PAL: The Position-bias Aware Learning framework (Guo et al., 2019) is a bias
modeling method. It introduces a position model to explicitly represent
position bias, and jointly model the bias and relevance.

  * •

Oracle: This model utilizes human experts’ annotated labels to train the
ranking model and test its performance. Its performance can be considered as
an upper bound for the ranking model.

  * •

Naive: This model just uses the raw click data to train the ranking model,
without any correction. Its performance can be considered as a lower bound for
the ranking model.

In addition, we also consider two variants of MULTR as follows,

  * •

Rand-MULTR: We replace the well-trained user simulator with the model with
random initialization, _i.e.,_ we skip lines 2-5 in the Algorithm 1. We refer
to this variant as Rand-MULTR.

  * •

EIB-MULTR: We alternate the doubly robust loss in Equation 15 with the error
imputation based loss (Hernández-Lobato et al., 2014), defined as
$\ell_{EIB}=\frac{1}{|\Pi|}\sum_{\pi\in\Pi}\ell_{naive}(f,q|\pi)$. It is
called EIB since it uses the user simulator to compute an imputed error,
_i.e.,_ the estimated values of the ranking loss, for each unobserved ranked
list, and then used it to estimate the true ranking loss for all the ranked
lists. We refer this variant as EIB-MULTR.

#### Experimental Protocols

We implement MULTR and use the baselines in ULTRA444https://github.com/ULTR-
Community/ULTRA_pytorch/ (Tran et al., 2021) to conduct our experiments. In
particular, MULTR is integrated with DLA, as we consider it to be the best
method to estimate propensity. For each query, only the top $N=10$ documents
are assumed to be displayed to the users. For both datasets, all models are
trained with synthetic clicks. Following the setting in Ai et al. (2018b), the
click sessions for training are generated on the fly. We fix the batch size to
256 and train each model for 10K steps. The user simulator is also trained
with batch size of 256 and 10K steps; afterwards, we fix it to generate
pseudo-click labels. We use the AdaGrad optimizer (Duchi et al., 2011) and
tune learning rates from 0.01 to 0.05 for each unbiased learning-to-rank
algorithm.

In our experiments, we train neural networks for our ranking functions. All
reported results are produced using a model with three hidden layers with size
$[512,256,128]$ respectively, with the ELU (Clevert et al., 2016) activation
function and 0.1 dropout (Srivastava et al., 2014). In terms of imputation
model, the dimension of the hidden states is 64. We tune the $L_{2}$
regularization coefficient $\lambda,\mu$ in range of
$\\{1e^{-5},1e^{-4},\cdots,1\\}$, and the number of pseudo samples in
$\\{2,4,8,16,24,32\\}$ based on results in the validation set.

To evaluate all methods, we use the normalized Discounted Cumulative Gain
(nDCG) (Järvelin and Kekäläinen, 2002) and the Expected Reciprocal Rank (ERR)
(Chapelle et al., 2009). For both metrics, we report the results at rank 1, 3,
5, and 10 to show the performance of models at different positions. Following
Ai _et al._ (Ai et al., 2018b), statistical differences are computed based on
the Fisher randomization test (Smucker et al., 2007) with $p\leq 0.05$.

###  5.2. Real Click Experiment Setup

In order to show the effectiveness of MULTR in practice, we also conduct
experiments on click data Tiangong-ULTR555http://www.thuir.cn/data-tiangong-
ultr/ collected from a commercial web search engine (Ai et al., [n. d.],
2018b). It contains 3,449 queries written by real search engine users and the
corresponding top 10 results are sampled from a two-week search log collected
on Sogou666https://www.sogou.com/. The raw HTML documents are downloaded, and
then the rank lists that cannot be crawled are removed. After cleaning, there
are 333,813 documents, 71,106 ranked lists and 3,268,177 anonymous click
sessions.

#### Feature Extraction

To train the learning-to-rank models, features are extracted based on the text
of queries and documents. The ranking features are constructed based on the
URL, title, content and whole text of the documents and queries (Ai et al.,
2018b). In total, each query-document pair has 33 features.

#### Evaluation

Tiangong-ULTR provides a test set with 100 queries written by real users. Each
query has 100 candidate documents (retrieved by BM25) and each query-document
pair has 5-level relevance annotation. We train the ranking model in MULTR and
baselines on the training set with clicks following the same protocols in the
simulation experiments, and we evaluate their performance on the test set with
human annotations. Similar to the simulation experiments, we report nDCG and
ERR for all models.

Table 1. A comparison of the overall performance MULTR and competing methods
on Yahoo! and Istella-S datasets. $``\ast"$ indicates a statistically
significant improvement over the best baseline.
---
Methods | Yahoo! LETOR | Istella-S
NDCG@K | ERR@K | NDCG@K | ERR@K
K = 1 | K = 3 | K = 5 | K = 10 | K = 1 | K = 3 | K = 5 | K = 10 | K = 1 | K = 3 | K = 5 | K = 10 | K = 1 | K = 3 | K = 5 | K = 10
Oracle | 0.689 | 0.691 | 0.714 | 0.761 | 0.350 | 0.428 | 0.449 | 0.465 | 0.671 | 0.641 | 0.667 | 0.729 | 0.598 | 0.709 | 0.725 | 0.731
MULTR | $\textbf{0.681}^{\ast}$ | $\textbf{0.682}^{\ast}$ | $\textbf{0.705}^{\ast}$ | $\textbf{0.751}^{\ast}$ | $\textbf{0.348}^{\ast}$ | $\textbf{0.426}^{\ast}$ | $\textbf{0.447}^{\ast}$ | $\textbf{0.463}^{\ast}$ | $\textbf{0.664}^{\ast}$ | $\textbf{0.627}^{\ast}$ | $\textbf{0.648}^{\ast}$ | $\textbf{0.704}^{\ast}$ | $\textbf{0.594}^{\ast}$ | $\textbf{0.701}^{\ast}$ | $\textbf{0.717}^{\ast}$ | $\textbf{0.724}^{\ast}$
DLA | 0.669 | 0.671 | 0.694 | 0.743 | 0.346 | 0.422 | 0.444 | 0.460 | 0.639 | 0.607 | 0.629 | 0.683 | 0.572 | 0.683 | 0.700 | 0.707
REM | 0.636 | 0.638 | 0.661 | 0.711 | 0.336 | 0.410 | 0.432 | 0.448 | 0.590 | 0.551 | 0.568 | 0.618 | 0.528 | 0.640 | 0.659 | 0.669
PairD | 0.653 | 0.662 | 0.687 | 0.738 | 0.333 | 0.413 | 0.436 | 0.451 | 0.604 | 0.586 | 0.617 | 0.687 | 0.537 | 0.661 | 0.680 | 0.688
PAL | 0.645 | 0.660 | 0.683 | 0.735 | 0.328 | 0.410 | 0.432 | 0.448 | 0.620 | 0.595 | 0.623 | 0.691 | 0.553 | 0.672 | 0.690 | 0.698
Naive | 0.651 | 0.660 | 0.685 | 0.737 | 0.332 | 0.411 | 0.434 | 0.450 | 0.613 | 0.592 | 0.622 | 0.690 | 0.546 | 0.667 | 0.686 | 0.694
Rand-MULTR | 0.667 | 0.670 | 0.693 | 0.743 | 0.341 | 0.419 | 0.441 | 0.457 | 0.633 | 0.604 | 0.631 | 0.693 | 0.564 | 0.681 | 0.698 | 0.706
EIB-MULTR | 0.674 | 0.678 | 0.700 | 0.749 | 0.346 | 0.423 | 0.445 | 0.460 | 0.653 | 0.611 | 0.631 | 0.684 | 0.585 | 0.690 | 0.707 | 0.714

##  6\. Results and Analysis

In this section, we discuss the results of our proposed model-based unbiased
learning to rank method with existing approaches using both simulated and
real-world experiments. In general, we expect the experimental results to
answer the following research questions:

  * •

RQ1: Can MULTR outperform state-of-the-art unbiased learning to rank methods?

  * •

RQ2: What influence do variant designs have on MULTR?

  * •

RQ3: How does the sample number of unobserved ranked lists influence the
performance of MULTR?

  * •

RQ4: How does MULTR perform on real click logs?

###  6.1. Performance Comparison (RQ1)

To answer RQ1, we compare MULTR with other unbiased learning-to-rank
algorithms in the simulation experiments. Table 1 summarizes the performance
of different unbiased learning to rank algorithms under various click
situations. We find that:

  * •

Our model-based unbiased learning to rank achieves the best performance among
all the state-of-the-art methods in terms of nDCG and ERR, which indicates our
model is robust when propensity cannot be accurately estimated.

  * •

Reducing variance can enhance performance on unbiased learning to rank. As
MULTR shares the same method with DLA in estimating propensity, the
improvements over DLA demonstrate the necessity of handling variance in IPW-
based methods.

  * •

The naive method may achieve better performance than some unbiased learning to
rank methods when clicks are generated by a cascade model. One explanation is
that documents displayed at a lower rank have a higher opportunity to be
examined; thus they receive more clicks, which alleviates the bias in click
data. This observation confirms that a mismatch between propensity estimation
and real bias could lead to performance even worse than raw click data.

  * •

The oracle model with human annotation consistently achieves the best
performance. It implies that there is still room to improve in unbiased
learning to rank methods.

###  6.2. Ablation Study (RQ2)

MULTR has specific design features, including a context-aware user simulator
and a doubly robust loss function to train rankers. To demonstrate their
effectiveness, we analyze their respective impacts on the model’s performance
via ablation study. The experimental results of its two variants on two
datasets are summarized in Table 1. We analyze their respective effects as
follows.

(1) Rand-MULTR: When we replace the well-trained user simulator with one from
random initialization, the performance of Rand-MULTR significantly degrades.
This observation verifies the necessity of an accurate user simulator for the
doubly robust estimator learning process: when the user simulator has a high
bias due to inaccurate click imputations, it will mislead the rankers.

(2) EIB-MULTR: When we use the same treatments for real clicks from
observations and pseudo clicks from user simulators, the performance of EIB-
MULTR suffers a significant decrease. This suggests, naturally, that there is
a discrepancy between real clicks and pseudo clicks. The doubly robust
approach effectively leverages pseudo clicks and improves the performance of
rankers.

###  6.3. Parameter Sensitivity Study (RQ3)

As we have explained previously, when $N$ is the maximum number of documents
that can be shown to users, there will be $N!$ candidate ranked lists, which
could be large. Therefore, we decrease the number of samples for unobserved
ranked lists in practice. To investigate its impact in MULTR, we vary the
sample size for unobserved ranked lists in the range of
$\\{0,2,4,8,16,24,32\\}$. Figure 3 shows the NDCG@K and ERR@K for MULTR with
respect to different sample sizes on both datasets.

Figure 3. Study of effect of sample size for unobserved ranked lists on Yahoo!
LETOR and Istella-S.

First, MULTR with sample number 0, _i.e.,_ we merely sample from unobserved
candidate rank lists, derives the worst performance. This observation shows
that the well-trained user simulator enables the unobserved rank lists to
provide rankers with useful information. Second, when the sampling number
increases from 0 to 8, the performance at all levels increases. This shows
that sampling more unobserved rank lists can bring more beneficial information
to rankers. Third, overly large sampling does not show a significant
improvement, even though we should sample all unobserved rank lists in theory.
We even observe that NDCG starts to decrease when the sample number increases
from 8 to 32. One possible reason could be that the observed rank lists are
typically sparse in practice, meaning that we cannot ensure that the rankers
obtain sufficient information. For both datasets, the optimal sampling size is
8. In conclusion, setting the sampling size too conservatively or too
aggressively may adversely affect the ranking performance, and too
aggressively also brings in unnecessary computational cost.

###  6.4. Real Data Study (RQ4)

As we have demonstrated that the proposed MULTR works well in the simulation
study, we would further investigate how it performs on real click logs
recorded by the search engine. We compare MULTR with existing unbiased
learning to rank algorithms on real data. The experimental results are
summarized in Table 2. From the results, we can see that MULTR outperforms
state-of-the-art unbiased learning to rank algorithms. This shows that the
user simulator in MULTR provides reliable pseudo-clicks for the ranker,which
enhances the ranking performance. In addition, propensity models in both MULTR
and baseline methods are developed upon position-based examination assumption,
which makes accurate propensity estimation infeasible on real data. Therefore,
they are more likely to suffer from the high variance problem. The superior
performance of MULTR over baseline methods verifies the necessity of reducing
the variance via doubly-robust learning.

Table 2. Comparison of MULTR and competing methods on Tiangong-ULTR.
---
Methods | NDCG@K | ERR@K
K = 1 | K = 3 | K = 5 | K = 10 | K = 1 | K = 3 | K = 5 | K = 10
MULTR | 0.483 | 0.465 | 0.469 | 0.476 | 0.448 | 0.578 | 0.606 | 0.618
DLA | 0.472 | 0.443 | 0.425 | 0.443 | 0.443 | 0.571 | 0.594 | 0.610
REM | 0.450 | 0.455 | 0.457 | 0.476 | 0.422 | 0.566 | 0.594 | 0.606
PairD | 0.388 | 0.371 | 0.369 | 0.383 | 0.364 | 0.494 | 0.522 | 0.542
PAL | 0.365 | 0.384 | 0.395 | 0.413 | 0.342 | 0.483 | 0.516 | 0.533
Naive | 0.412 | 0.413 | 0.408 | 0.411 | 0.386 | 0.528 | 0.556 | 0.570

##  7\. Conclusion

In this work, we propose MULTR, a model-based unbiased learning to rank
framework. We first design a context-aware user simulator to produce labels
for unobserved ranked lists as supervision signals, which addressed data
sparsity for long-tail queries. However, the natural discrepancy between
pseudo and actual clicks could mislead the ranking models, as pseudo data
cannot be as accurate as real users. Therefore, we resort to DR approaches. In
particular, we take the observation of the ranked lists as the treatment,
which addresses the treatment unobservation when naively applying existing DR
methods. Afterward, we take the pseudo-click data as data imputation, and
propose a doubly-robust learning algorithm to obtain unbiased ranking models.
Theoretical analysis reveals that our method is more robust than existing
methods. Extensive experiments on benchmark datasets, including simulated
datasets and real click logs, demonstrate that the proposed model-based method
consistently outperforms state-of-the-art methods.

## References

  * (1)
  * Ai et al. (2018a) Qingyao Ai, Keping Bi, Jiafeng Guo, and W. Bruce Croft. 2018a.  Learning a Deep Listwise Context Model for Ranking Refinement. In _SIGIR 2018_.
  * Ai et al. (2018b) Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W. Bruce Croft. 2018b.  Unbiased Learning to Rank with Unbiased Propensity Estimation. In _SIGIR 2018_.
  * Ai et al. ([n. d.]) Qingyao Ai, Jiaxin Mao, Yiqun Liu, and W. Bruce Croft. [n. d.].  Unbiased Learning to Rank: Theory and Practice. In _CIKM 2018_.
  * Chapelle and Chang (2011) Olivier Chapelle and Yi Chang. 2011.  Yahoo! Learning to Rank Challenge Overview. In _Proceedings of the Yahoo! Learning to Rank Challenge, held at ICML 2010, Haifa, Israel, June 25, 2010_ _(JMLR Proceedings)_.
  * Chapelle et al. (2011) Olivier Chapelle, Yi Chang, and Tie-Yan Liu (Eds.). 2011\.  _Proceedings of the Yahoo! Learning to Rank Challenge, held at ICML 2010, Haifa, Israel, June 25, 2010_. JMLR Proceedings, Vol. 14. JMLR.org.
  * Chapelle et al. (2009) Olivier Chapelle, Donald Metlzer, Ya Zhang, and Pierre Grinspan. 2009.  Expected reciprocal rank for graded relevance. In _CIKM 2009_.
  * Chapelle and Zhang (2009) Olivier Chapelle and Ya Zhang. 2009.  A dynamic bayesian network click model for web search ranking. In _WWW 2009_.
  * Chu et al. (2022) Xiaokai Chu, Jiashu Zhao, Lixin Zou, and Dawei Yin. 2022\.  H-ERNIE: A Multi-Granularity Pre-Trained Language Model for Web Search. In _CIKM’22_.
  * Chuklin et al. (2016) Aleksandr Chuklin, Ilya Markov, and Maarten de Rijke. 2016\.  Click Models for Web Search and their Applications to IR: WSDM 2016 Tutorial. In _WSDM 2016_.
  * Clevert et al. (2016) Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. 2016.  Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs). In _ICLR 2016_.
  * Craswell et al. (2008) Nick Craswell, Onno Zoeter, Michael J. Taylor, and Bill Ramsey. 2008.  An experimental comparison of click position-bias models. In _WSDM 2008_.
  * Dai et al. (2020) Xinyi Dai, Jiawei Hou, Qing Liu, Yunjia Xi, Ruiming Tang, Weinan Zhang, Xiuqiang He, Jun Wang, and Yong Yu. 2020.  U-rank: Utility-oriented Learning to Rank with Implicit Feedback. In _CIKM ’20_.
  * Dehghani et al. (2017) Mostafa Dehghani, Hamed Zamani, Aliaksei Severyn, Jaap Kamps, and W. Bruce Croft. 2017.  Neural Ranking Models with Weak Supervision. In _SIGIR 2017_.
  * Duchi et al. (2011) John C. Duchi, Elad Hazan, and Yoram Singer. 2011\.  Adaptive Subgradient Methods for Online Learning and Stochastic Optimization.  _J. Mach. Learn. Res._ 12 (2011), 2121–2159.
  * Dupret and Piwowarski (2008) Georges Dupret and Benjamin Piwowarski. 2008.  A user browsing model to predict search engine click data from past observations. In _SIGIR 2008_.
  * Guo et al. (2019) Huifeng Guo, Jinkai Yu, Qing Liu, Ruiming Tang, and Yuzhou Zhang. 2019.  PAL: a position-bias aware learning framework for CTR prediction in live recommender systems. In _RecSys 2019_.
  * Guo et al. (2021) Siyuan Guo, Lixin Zou, Yiding Liu, Wenwen Ye, Suqi Cheng, Shuaiqiang Wang, Hechang Chen, Dawei Yin, and Yi Chang. 2021.  Enhanced Doubly Robust Learning for Debiasing Post-Click Conversion Rate Estimation. In _SIGIR 2021_.
  * Hernández-Lobato et al. (2014) José Miguel Hernández-Lobato, Neil Houlsby, and Zoubin Ghahramani. 2014\.  Probabilistic Matrix Factorization with Non-random Missing Data. In _ICML 2014_ _(JMLR Workshop and Conference Proceedings)_.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Comput._ 9, 8 (1997), 1735–1780.
  * Hu et al. (2019) Ziniu Hu, Yang Wang, Qu Peng, and Hang Li. 2019\.  Unbiased LambdaMART: An Unbiased Pairwise Learning-to-Rank Algorithm. In _WWW 2019_.
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen. 2002\.  Cumulated gain-based evaluation of IR techniques.  _ACM Trans. Inf. Syst._ 20, 4 (2002), 422–446.
  * Joachims (2006) Thorsten Joachims. 2006\.  Training linear SVMs in linear time. In _SIGKDD 2006_.
  * Joachims et al. (2005) Thorsten Joachims, Laura A. Granka, Bing Pan, Helene Hembrooke, and Geri Gay. 2005\.  Accurately interpreting clickthrough data as implicit feedback. In _SIGIR 2005_.
  * Joachims et al. (2007) Thorsten Joachims, Laura A. Granka, Bing Pan, Helene Hembrooke, Filip Radlinski, and Geri Gay. 2007.  Evaluating the accuracy of implicit feedback from clicks and query reformulations in Web search.  _ACM Trans. Inf. Syst._ 25, 2 (2007), 7\.
  * Joachims et al. (2017) Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017\.  Unbiased Learning-to-Rank with Biased Feedback. In _WSDM 2017_.
  * Kiyohara et al. (2022) Haruka Kiyohara, Yuta Saito, Tatsuya Matsuhiro, Yusuke Narita, Nobuyuki Shimizu, and Yasuo Yamamoto. 2022\.  Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model. In _WSDM ’22_.
  * Liu et al. (2020) Dugang Liu, Pengxiang Cheng, Zhenhua Dong, Xiuqiang He, Weike Pan, and Zhong Ming. 2020\.  A General Knowledge Distillation Framework for Counterfactual Recommendation via Uniform Data. In _SIGIR 2020_.
  * Lucchese et al. (2016) Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Fabrizio Silvestri, and Salvatore Trani. 2016.  Post-Learning Optimization of Tree Ensembles for Efficient Ranking. In _SIGIR 2016_.
  * Mao et al. (2019) Jiaxin Mao, Zhumin Chu, Yiqun Liu, Min Zhang, and Shaoping Ma. 2019.  Investigating the Reliability of Click Models. In _ICTIR 2019_.
  * Mao et al. (2018) Jiaxin Mao, Cheng Luo, Min Zhang, and Shaoping Ma. 2018\.  Constructing Click Models for Mobile Search. In _SIGIR 2018_.
  * Oosterhuis (2022) Harrie Oosterhuis. 2022\.  Doubly-Robust Estimation for Unbiased Learning-to-Rank from Position-Biased Click Feedback.  _arXiv preprint arXiv:2203.17118_ (2022).
  * Ovaisi et al. (2020) Zohreh Ovaisi, Ragib Ahsan, Yifan Zhang, Kathryn Vasilaky, and Elena Zheleva. 2020.  Correcting for Selection Bias in Learning-to-rank Systems. In _WWW 2020_.
  * Richardson et al. (2007) Matthew Richardson, Ewa Dominowska, and Robert Ragno. 2007\.  Predicting clicks: estimating the click-through rate for new ads. In _WWW 2007_.
  * Rosenbaum and Rubin (1983) Paul R Rosenbaum and Donald B Rubin. 1983.  The central role of the propensity score in observational studies for causal effects.  _Biometrika_ 70, 1 (1983).
  * Saito (2020a) Yuta Saito. 2020a.  Asymmetric Tri-training for Debiasing Missing-Not-At-Random Explicit Feedback. In _SIGIR 2020_.
  * Saito (2020b) Yuta Saito. 2020b.  Doubly Robust Estimator for Ranking Metrics with Post-Click Conversions. In _RecSys 2020_.
  * Sanderson (2010) Mark Sanderson. 2010\.  Test Collection Based Evaluation of Information Retrieval Systems.  _Found. Trends Inf. Retr._ 4, 4 (2010), 247–375.
  * Shen and Zhao (2014) Chengyao Shen and Qi Zhao. 2014.  Webpage Saliency. In _ECCV 2014_.
  * Smucker et al. (2007) Mark D. Smucker, James Allan, and Ben Carterette. 2007\.  A comparison of statistical significance tests for information retrieval evaluation. In _CIKM 2007_.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _J. Mach. Learn. Res._ 15, 1 (2014), 1929–1958.
  * Swaminathan and Joachims (2015) Adith Swaminathan and Thorsten Joachims. 2015.  The Self-Normalized Estimator for Counterfactual Learning. In _NeurIPS 2015_.
  * Tran et al. (2021) Anh Tran, Tao Yang, and Qingyao Ai. 2021.  ULTRA: An Unbiased Learning To Rank Algorithm Toolbox. In _CIKM 2021_.
  * Vardasbi et al. (2020a) Ali Vardasbi, Maarten de Rijke, and Ilya Markov. 2020a.  Cascade Model-based Propensity Estimation for Counterfactual Learning to Rank. In _SIGIR 2020_.
  * Vardasbi et al. (2020b) Ali Vardasbi, Harrie Oosterhuis, and Maarten de Rijke. 2020b.  When Inverse Propensity Scoring does not Work: Affine Corrections for Unbiased Learning to Rank. In _CIKM ’20_.
  * Wang et al. (2013) Hongning Wang, ChengXiang Zhai, Anlei Dong, and Yi Chang. 2013\.  Content-aware click modeling. In _WWW 2013_.
  * Wang et al. (2016) Xuanhui Wang, Michael Bendersky, Donald Metzler, and Marc Najork. 2016.  Learning to Rank with Selection Bias in Personal Search. In _SIGIR 2016_.
  * Wang et al. (2018) Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018\.  Position Bias Estimation for Unbiased Learning to Rank in Personal Search. In _WSDM 2018_.
  * Ye et al. (2022) Wenwen Ye, Yiding Liu, Lixin Zou, Hengyi Cai, Suqi Cheng, Shuaiqiang Wang, and Dawei Yin. 2022.  Fast semantic matching via flexible contextualized interaction. In _WSDM’22_.
  * Yuan et al. (2019) Bo-Wen Yuan, Jui-Yang Hsia, Meng-Yuan Yang, Hong Zhu, Chih-Yao Chang, Zhenhua Dong, and Chih-Jen Lin. 2019.  Improving Ad Click Prediction by Considering Non-displayed Events. In _CIKM 2019_.
  * Yue et al. (2010) Yisong Yue, Rajan Patel, and Hein Roehrig. 2010.  Beyond position bias: examining result attractiveness as a source of presentation bias in clickthrough data. In _WWW 2010_.
  * Zamani et al. (2018) Hamed Zamani, Bhaskar Mitra, Xia Song, Nick Craswell, and Saurabh Tiwary. 2018.  Neural Ranking Models with Multiple Document Fields. In _WSDM 2018_.
  * Zhang et al. (2022) Junqi Zhang, Yiqun Liu, Jiaxin Mao, Weizhi Ma, Jiazheng Xu, Shaoping Ma, and Qi Tian. 2022.  User Behavior Simulation for Search Result Re-Ranking.  _ACM Transactions on Information Systems_ (2022).
  * Zhang et al. (2019) Junqi Zhang, Jiaxin Mao, Yiqun Liu, Ruizhe Zhang, Min Zhang, Shaoping Ma, Jun Xu, and Qi Tian. 2019\.  Context-Aware Ranking by Constructing a Virtual Environment for Reinforcement Learning. In _CIKM 2019_.
  * Zhuang et al. (2021) Honglei Zhuang, Zhen Qin, Xuanhui Wang, Michael Bendersky, Xinyu Qian, Po Hu, and Dan Chary Chen. 2021.  Cross-Positional Attention for Debiasing Clicks. In _WWW 2021_.
  * Zou et al. (2022a) Lixin Zou, Changying Hao, Hengyi Cai, Shuaiqiang Wang, Suqi Cheng, Zhicong Cheng, Wenwen Ye, Simiu Gu, and Dawei Yin. 2022a.  Approximated Doubly Robust Search Relevance Estimation. In _CIKM ’22_.
  * Zou et al. (2022b) Lixin Zou, Weixue Lu, Yiding Liu, Hengyi Cai, Xiaokai Chu, Dehong Ma, Daiting Shi, Yu Sun, Zhicong Cheng, Simiu Gu, et al. 2022b.  Pre-trained Language Model based Retrieval and Ranking for Web Search.  _ACM Transactions on the Web_ (2022).
  * Zou et al. (2022c) Lixin Zou, Haitao Mao, Xiaokai Chu, Jiliang Tang, Wenwen Ye, Shuaiqiang Wang, and Dawei Yin. 2022c.  A Large Scale Search Dataset for Unbiased Learning to Rank.  _arXiv preprint arXiv:2207.03051_ (2022).
  * Zou et al. (2021) Lixin Zou, Shengqiang Zhang, Hengyi Cai, Dehong Ma, Suqi Cheng, Shuaiqiang Wang, Daiting Shi, Zhicong Cheng, and Dawei Yin. 2021.  Pre-trained language model based ranking in Baidu search. In _KDD ’21_.


0 Research

# Visualization Improvisation

Swaroop Panda  Shatarupa Thakurta Roy
Indian Institute of Technology Kanpur

###### Abstract

Teaching visualization design involve making students familiar and make them
work with visualization models, framework and perspectives. Visualization
research accommodates a plethora of perspectives emerging from researchers of
varied backgrounds. These diverse range of perspectives give rise to multiples
models, frameworks and perspectives to teach visualization design. In this
paper, we look at an approach to visualization teaching by using
improvisational techniques. The basic idea is to design a visualization
without using an existing predefined model. Since improvisation, by
definition, is not a model or a framework, this work presents a reflection on
how improvisation can be a way of teaching visualization design.

###### keywords:

Visualization Design, Visualization Teaching, Improvisation

Human-centered computingVisualization theory, concepts and paradigms;
Visualization design by improvisation as compared to visualization design
using a predefined model.

This paper has been peer-reviewed and accepted to VisActivities: IEEE VIS
Workshop on Data Vis Activities to Facilitate Learning, Reflecting,
Discussing, and Designing, held in conjunction with IEEE VIS 2020, Salt Lake
City, UT. Workshop organizers: Samuel Huron, Benjamin Bach, Uta Hinrichs,
Jonathan C. Roberts, Mandy Keck, http://visactivities.github.io

##  1 Introduction

Visualization has become a very extensive field of research. A lot of
researchers with a variety of research interests engage with visualization;
they submit and participate in visualization conferences, teach visualization
design, practice visualization in industry or work with dedicated
visualization research groups within companies. This wide-ranging engagement
with visualization has resulted in emergence of a vast literature on
visualization, which is evident from not only the number of papers published
at visualization, HCI, graphics conferences but also the large number of
books, blogs and popular articles on data visualization that have surfaced on
the internet. This also signifies the emerging value and importance of
visualization in research, communication, presentation and other aspects of
digital media.

Given such a setting, how does one go about teaching visualisation design?
There are a diverse collection of papers, books, blogs that consider
visualization in completely different contexts. As an instance, take the fact
that visualization researchers include people from backgrounds such as graphic
design, computer graphics, human-computer interaction, data scientists and
architecture. Thus, such a varied background of researchers lead to diverse
visualization perspectives. A visualization design course may take an
algorithmic approach (prioritizing algorithms and software for visualization
design), or be more focused on the visual layout (visualization as graphic
design) or maybe data-centered (visualization is just a technically correct
representation of data). None of these are more or less accurate than the
others; but are the consequence of the diversity of visualization design
research.

Reiterating, visualization as a subject, is approachable by a plethora of
perspectives. This also has implications on how visualization is deployed in a
given setting. For example, take the instance of technique-driven
visualization and problem-driven visualization. Technique driven visualization
are algorithms that accomplish the task of visualization development; such as
graph-drawing or dimensionality reduction. Problem-solving approaches include
solving domain-based problems using visualization. These include the use and
deployment of visualizations in genomics, business intelligence and journalism
among others. So these approaches are means to an end; the end being designing
and developing visualizations. In this mishmash of perspectives, how does one
introduce the idea of visualization? By a visualization technique? By a
visualization to solve a domain problem? Or a visualization for a task?

In this paper we present improVISe; visualization design by improvisation.It
is basically based on the ideas of improvisation. Improvisation, basically, is
the idea of creating spontaneously, on the spur of the moment without any
advance planning. ImproVISe can serve as a beginner’s guide for visualization
design, as we shall see, can also act as guideline for experts to explore new
models of visualization. ImproVISe, by definition, is not a model or a
guideline, but rather a way of doing a given thing (designing visualization in
this case). This paper, thus, does not present a framework but rather a
reflection of how fundamental ideas of improvisation can be useful in
visualization. A reflection, we suppose, is a better way to deal with an open-
ended construct such as improvisation.

##  2 On Improvisation

Improvisation, basically is the activity of doing or making a particular thing
without any plan by using the available resources. The work by Gary Peters [9]
presents a philosophy of improvisation. Peters get around loosely defining
improvisation as ”a work produced within a restricted time frame, within a
delimited productive space with delimited resources”. Improvisation originated
from the performing arts where it was the act of performing without any script
in hand. For example, musical improvisation involves composition on the spot.
Improvisation is the defining attribute of the popular jazz music genre. These
skills and features of improvisation have been eventually transported to other
fields like the sciences, engineering and other academic disciplines. One of
such disciplines, where improvisation has been transported includes design.
The work by Elizabeth Gerber [3] suggests improvisational principles and
techniques for design and observes that improvisational activities by
designers can foster innovation, creative collaboration and learning through
errors. The work in [1] by De Valk et.al. presents a design approach for open-
ended play where they offer interaction techniques for personalized games for
children; allowing them to make their own rules and goals. The work in [10] by
David Sekin et.al. uses an embedded design improvisation as design research
tool by using improvisational ideas in conjunction with embodied design and
video prototyping. Similarly, in this work, we try to implement the basic
ideas of improvisation in the task of visualization design.

##  3 On Improvising Visualization

ImproVISe, then, is the act of improvising a visualization. The advance
planning, in our case, directly translates to having a predefined model
developed in advance. So improVISe as a guide is the practice of visualization
design without a predefined model. It is important to emphasize that
improvising does not amount to designing a visualization without a model; but
rather this is the idea of designing a visualization without a predefined
model. This implies that improvising a visualization simultaneously develops
the visualization and a new model.

What exactly are these predefined models? There has been extensive work on
models in the visualization research. These models are frameworks, theories,
conceptual structures that are basically used to design, develop, validate and
deploy visualizations. The work by Munzner [8] provides a nested model for
visualization design and validation. Similarly the work by Liu et.al. [7]
provides a distributed cognition theoretical framework for understanding and
appreciating visualizations. Kindlmann et.al. [5] provides an algebraic
process for visualization design while the work by Lau et.al. [6]provides an
information aesthetics context for visualization. Demiral et.al. [2] provide a
visual embedding as a model for designing and evaluating visualizations. The
variety of these predefined models (from using aesthetics to cognitive
frameworks to algebraic processes) is evidence for the diversity present in
visualization design.

How feasible is it to design a visualization without using such a predefined
model? We suppose, there are two basic approaches to capture all of the large
variety of models in visualization research literature; one being a unified
model encapsulating all the properties and features and the other our proposed
approach of improvising a visualization; letting go of all predefined models.
We hope other authors in the community will be motivated to pursue the former
approach. Also, we suppose letting go of all models also allows to explore
more possibilities and push disciplinary boundaries by realizing new models of
visualization design that had not been yet explored.

There is always an underlying model (or process) in any given visualization
design process. Thus, an act of improvising a visualization simultaneously
designs a visualization and develops a model for visualization design. Also,
by improvisation, each model is conditioned by the corresponding
visualization. This apparently looks contrary to existing predefined models
(upon whom the visualizations are conditioned and thus the models can be used
to design visualizations in different contexts). We suppose that models
produced by the act of improvisation can also be useful as a predefined model
for designing visualization in other unrelated context. However, such a
proposition needs to be validated by rigorous empirical research which we hope
is an interesting future work for visualization researchers.

The idea of improvisation is also helpful given the fact that there are a
large number of tools and software that are available for visualization
design. Data Scientists and software developers use variety of softwares from
Tableau, MS Excel to Flourish and other chart generating engines to build
visualizations. In fact software like Tableau and MS Excel are coded models
for visualization design (where the input is data and the output is a
visualization). In teaching and learning visualization design, how do students
decide what software to choose for a particular visualization problem. This is
an acute issue more so because there are researchers and developers who are
dedicated research interests to building new software for visualization
design. Thus, with the increasing software and varied tools, improvisation as
a way of designing could provide for answer as to which software works the
best for the visualization. This is because lack of predefined models allows
liberty to the designer to choose software (or a collection of multiple
software) in accordance to the desired visualization. The software is not
imposed by a predefined model but rather chosen so as to adapt (or
conditioned) to the visualization.

Improvisation does not stop after the visualization is designed. Once the
improvisation is done, it is required to place the visualization in context in
the existing visualization literature. This is the vital aspect of
visualization improvisation; placing the design in context. Take for instance,
an existing visualization was improvised by using new data and doing some
changes in the color patterns and say this visualization turned out to be
highly effective. The important questions that are needed to be asked include
why the certain colour palette worked instead of the other? Is there some
logic behind it or was it a matter of chance and context? Why did the new data
fit the existing visualization? Does all such data-structures fall into the
existing visualization? The answers to these questions help comprehending the
design process and thereby also helping in the construction of the model.
Placing the model in context of other predefined models in existing literature
results in gaining more information about its usefulness which we suppose, can
help in deploying the model for designing visualization in other different
contexts.

Another crucial aspect of visualization improvisation remains the improviser,
that is, the visualization student. What did the student learn? The
improvisation method did not teach any existing models or frameworks, nor did
it teach how to solve problems using visualizations. Improvisation, as a way
of doing, helps the student accomplish the task of visualization design.
Improvisation does not feed models, theories, frameworks directly to the
students, but rather keeps these peripheral relative to the central aspect to
teaching students to design visualization. This is more of an indirect way of
teaching and learning visualization design where the student learns existing
methods by contextualizing, examining, placing in context and reflecting the
process in hindsight. How effective would be improvisation as a teaching tool
as compared to other direct methods would be indeed a require larger long term
studies. This is not to say that visualization by improvisation can only be
useful for beginner students. Improvisation, which is letting go of all
predefined models, can also prove effective for experts focusing on exploring
further boundaries of visualization design.

##  4 Implementation

Visualization improvisation is best taught to students in a classroom setting.
The curriculum is more project than instruction-based with reading sessions of
visualization literature research(as literature reading is important to place
the design in context). The instruction is largely technical; based upon
teaching fundamentals of software and other technical tools available for
visualization, lessons of data, statistics and lessons based on the concerned
domain (genetics or aerospace or finance). This is followed by sample
demonstrations of improvisation by the instructor. A demonstration could as
simple fitting in new data on an existing visualization and modifying colours
using a given tool. These demonstrations could nudge the students to further
modify existing visualizations with old/new data, change shapes or colours and
trying whatever works to make the visualization more effective and impactful.
In these instructions, it remains important for the teacher to keep the gist
of the improvisational visualization intact;learning to develop and design the
desired visualization being the primary and studying models and other existing
literature secondary and indirect.

Figure 1: Components of a visualization improvisation class

Visualization improvisation can be also taught by books. However, this is a
much more difficult task to accomplish; though it has been done in other
fields. Johnstone’s book [4] provides an account of improvisation in theatre,
though in retrospect. These books should ideally be able to convince readers
to design visualizations by improvising, by following similar methods of
technical instructions and improvisation demonstrations. But such books, we
suppose, will possibly be much less effective than a classroom engagement with
students on this topic.

##  5 Conclusion

Teaching visualization, we have realized, depends a lot on the academic
background and style of the concerned instructor. A data scientist would teach
visualization much differently than a graphic designer or an HCI researcher.
This emerges from the fact that visualization research accommodates multitudes
of perspectives that are difficult to disentangle and teach to students. Thus,
we propose an improvisational approach to teach visualization design.
Improvisation includes visualization design without using any predefined
models. We reflected on how improvisation can be an effective and reasonable
approach to visualization design; how improvisation process produces new
models along with the visualization and we concluded with some suggestions for
incorporating visualization improvisation into classroom teaching and with
books.

## References

  * [1] L. De Valk, T. Bekker, and B. Eggen.  Leaving room for improvisation: towards a design approach for open-ended play.  In Proceedings of the 12th international conference on interaction design and children, pp. 92–101, 2013.
  * [2] Ç. Demiralp, C. E. Scheidegger, G. L. Kindlmann, D. H. Laidlaw, and J. Heer.  Visual embedding: A model for visualization.  IEEE Computer Graphics and Applications, 34(1):10–15, 2014.
  * [3] E. Gerber.  Improvisation principles and techniques for design.  In Proceedings of the SIGCHI conference on Human factors in computing systems, pp. 1069–1072, 2007.
  * [4] K. Johnstone.  Impro: Improvisation and the theatre.  Routledge, 2012.
  * [5] G. Kindlmann and C. Scheidegger.  An algebraic process for visualization design.  IEEE transactions on visualization and computer graphics, 20(12):2181–2190, 2014.
  * [6] A. Lau and A. V. Moere.  Towards a model of information aesthetics in information visualization.  In 2007 11th International Conference Information Visualization (IV’07), pp. 87–92. IEEE, 2007.
  * [7] Z. Liu, N. Nersessian, and J. Stasko.  Distributed cognition as a theoretical framework for information visualization.  IEEE transactions on visualization and computer graphics, 14(6):1173–1180, 2008.
  * [8] T. Munzner.  A nested model for visualization design and validation.  IEEE transactions on visualization and computer graphics, 15(6):921–928, 2009.
  * [9] G. Peters.  The philosophy of improvisation.  University of Chicago Press, 2009.
  * [10] D. Sirkin and W. Ju.  Using embodied design improvisation as a design research tool.  In Proceedings of the international conference on Human Behavior in Design (HBiD 2014), Ascona, Switzerland, 2014.