# The Generalized Cascade Click Model: A Unified Framework for Estimating
Click Models

###### Abstract

Given the vital importance of search engines to find digital information,
there has been much scientific attention on how users interact with search
engines, and how such behavior can be modeled. Many models on user - search
engine interaction, which in the literature are known as click models, come in
the form of Dynamic Bayesian Networks. Although many authors have used the
resemblance between the different click models to derive estimation procedures
for these models, in particular in the form of expectation maximization (EM),
still this commonly requires considerable work, in particular when it comes to
deriving the E-step. What we propose in this paper, is that this derivation is
commonly unnecessary: many existing click models can in fact, under certain
assumptions, be optimized as they were Input-Output Hidden Markov Models (IO-
HMMs), for which the forward-backward equations immediately provide this
E-step. To arrive at that conclusion, we will present the Generalized Cascade
Model (GCM) and show how this model can be estimated using the IO-HMM EM
framework, and provide two examples of how existing click models can be mapped
to GCM. Our GCM approach to estimating click models has also been implemented
in the gecasmo Python package.

##  1 Introduction

In the last decade, a considerable number of models have been proposed to
explain and/or predict web user interaction with search engines [8]. Crucial
to many of these so-called click models, is to provide an explanation to the
position bias: web users tend to be more likely to click on items at the top
of a Search Engine Result Page (SERP). Many of these click models are
probabilistic graphical models (PGMs), in particular in the form of Dynamic
Bayesian Networks (DBNs) [19, 8]. The choice of using DBNs to model user
interaction followed from observations in early eye-tracking studies, which
suggest that web users on average evaluate the items in the (SERP)
sequentially in a top-down fashion [16], and the work of Craswell et al. [10],
who showed that a sequential model, the so-called cascade model, outperformed
other models that try to explain the position bias.

As the parameters of more complex click models do not have a closed-form
maximum likelihood estimator per se, estimation is commonly done via
expectation maximization (EM). To our knowledge, most authors derived the
E-step manually for their proposed click model in a similar fashion as
suggested by [8, Ch. 4], i.e., by explicitly writing out the expectation.
However, as we will argue in this paper, such a derivation is commonly
unnecessary. Many click models can be rewritten as an Input-Output Hidden
Markov Model (IO-HMM) [3], for which the solution to the EM algorithm is
equivalent to the one obtained from deriving the EM algorithm explicitly for
the single click model of interest.

But perhaps more important, if the model can be rewritten as IO-HMM, the IO-
HMM directly provides an explicit expression for the E-step, making use of the
forward-backward algorithm, thereby making a separately derivation of the
E-step for each click model unnecessary. In other words, if we can model a
click model as IO-HMMs, we directly obtain an explicit EM estimation procedure
for the parameters of the click model, without having to derive further
expressions required by the EM algorithm.

This paper contributes to the current click model literature in two ways.
First, we introduce a rather general click model, which we name the
Generalized Cascade Model (GCM), and we show that the EM algorithm of GCM and
the corresponding IO-HMM have the same solution. Furthermore, we show that GCM
is a generalization of many commonly used click models, including the User
Browser Model (UBM) and the Chapelle-Zang Model (CZM). Second, as an example,
we provide explicit mappings from UBM and CZM to GCM, mappings which can be
used in the `gecasmo` package to estimate the parameters of these models. The
package fully utilizes the solution equivalence between GCM and IO-HMM, and
therefore only requires these mappings. I.e., contrary to existing click model
estimation software using EM, `gecasmo` does not require programming the
E-step or M-step explicitly for each click model.

This paper is structured as follows. Section 2 gives an short overview of the
click model literature and the methods used to estimate click models. Section
3 presents the GCM and shows how the EM algorithm of IO-HMMs can be used to
estimate GCMs, and uses some properties of GCMs to simplify this estimation.
Section 5 shows that UBM and CZM can be mapped to GCM, and provides an example
of such a mapping for both click models, which can be used in the `gecasmo`
package. Lastly, Section 6 gives a brief conclusion and ideas for further
research.

##  2 Related work

#### Probabilistic graphical click models

As already briefly discussed, a considerable number of click models have been
proposed in the literature in the form of Dynamic Bayesian Networks (DBNs)
[8], many inspired by the early work on these type of models by Craswell et
al. [10]. Since the work of Crasswell et al., many alternative DBNs have been
proposed, in particular to cope with the two main limitations of the cascade
model: 1) it cannot model more than one click in a SERP, 2) if no item is
clicked, it assumes the web user evaluated all items.

The two perhaps most well known alternatives to the cascade model are the user
browser model (UBM) [14], and the Chapelle-Zhang model (CZM) [7], which we
will discuss in more depth in Section 5.1. From UBM and CZM, many alternative
click models have been derived [8][Ch. 8]. These include the partially
sequential click model (PSCM), and its generalization, the time-aware click
model (TACM) [21, 17]. Both models can be viewed as generalizations of UBM, in
which the depth-first search assumption is replaced by a locally
unidirectional examination assumption.

Unfortunately, CZM is in the literature more commonly known as ‘the dynamic
Bayesian network’ model. However, as the model is a strict subset of all DBNs,
and to avoid confusion in our terminology, we deliberately renamed the model
to CZM in this paper. We do like to stress that the authors of the paper speak
correctly of ‘a dynamic Bayesian network’; the name ‘the dynamic Bayesian
network’ seems to have followed from other authors referring to the paper.

#### Distributed approach to click models

More recently, recurrent neural networks (RNNs) have grown in popularity as
alternatives to DBNs [5, 6, 13], an approach which Borisov et al. [5] name the
distributed approach to click modeling. The work of Borisov et al. [5] is in
particular interesting, as it shows that these RNNs are able to outperform
both UBM and CZM in terms of click perplexity, though they come at the cost of
increased model complexity.

The latter may be problematic if one is interested in studying the optimal
order of items in a SERP under a certain objective function, as was done by
Balakrishnan and Kambhampati [2]. Given the large number of parameters in
these RNNs and their interactions, such analysis would quickly become
intractable. Furthermore, although Borisov et al. [5] attempt to explain the
features learned by the RNN using t-SNE [18], this analysis is post hoc.
Hence, when drawing conclusion based on such analysis, one would be at risk of
the narrative fallacy. We therefore argue that, even though a distributed
approach may lead to better predictions, DBNs are still valuable in explaining
web user behavior and optimizing search engines accordingly.

#### Estimation of PGMs

Click models which have no closed form maximum likelihood estimate are most
commonly estimated using expectation maximization (EM) [8][Ch. 4]. EM has been
implemented for some so-called ‘basic click models’[8][Ch. 3], which include
the earlier mentioned UBM and CZM, in a number of open source software
packages. These include the `ClickModels` [9], and `PyClick`[20] projects.

Even though we focus on a typical textbook implementation of EM (e.g., [4][pp.
438-439]), other authors also consider alterations to EM, or alternatives to
EM, in the context of click models. Especially when the number of parameters
in the model grows large, alternatives to the classic EM implementation become
more interesting to consider.

In one of the more complex click models, the task-centric model, Zhang et al.
[23] make some additional independence assumptions between latent variables in
order to be able to use EM, where these assumptions have little impact on the
likelihood distribution, and propose alternative updates to speed up
convergence. Wang et al. [22] allow for covariates in the model, while still
relying on EM for estimation. They propose a posterior regularized EM
algorithm for click models to cope with noisy clicks and mis-ordered item
pairs. Apart from EM, Zhu et al. [25] propose a click model named the general
click model, which is solved using expectation propagation. Zhang et al. [24]
a use probit Bayesian inference approach, which can be applied to estimate
various click models. Both [25] and [24] allow for covariates in the model.

##  3 On the relationship between GCM and IO-HMM

###  3.1 A brief recap of IO-HMM

We start by a brief recap of the Input-Output Hidden Markov Model (IO-HMM), as
introduced by Bengio and Frasconi [3]. We will use $\mathcal{P}(X)$ to denote
the set of all parents of some node $X$ in a Dynamic Bayesian Network.

######  Definition 3.1.

An Input-Output Hidden Markov Model (IO-HMM) is a Dynamic Bayesian Network
consisting of observed states
$\\{\mathbf{x}_{t},\mathbf{y}_{t}\\}_{t=1,\ldots,T}$, and latent states
$\\{z_{t}\\}_{t=1,\ldots,T}$. For $t>1$ we have:
$\mathcal{P}(z_{t})=\\{z_{t-1},\mathbf{x}_{t}\\}$, whereas
$\mathcal{P}(z_{1})=\\{\mathbf{x}_{t}\\}$. Furthermore, for all $t$ we have:
$\mathcal{P}(\mathbf{y}_{t})=\\{\mathbf{x}_{t},z_{t}\\}$, and
$\mathcal{P}(\mathbf{x}_{t})=\emptyset$. Here
$\mathbf{x}_{t}\in\mathbb{R}^{R_{1}}$, $z_{t}\in\\{1,\ldots,K\\}$, and
$\mathbf{y}_{t}\in\mathbb{R}^{R_{2}}$; $R_{1},R_{2}\in\mathbb{N}$. The
transition probabilities are given by

$\varphi_{k^{{}^{\prime}}k,t}(\Omega):=\mathbb{P}(z_{t}=k|z_{t-1}=k^{{}^{\prime}};\mathbf{x}_{t},\Omega),$
(1)

whereas the probability of being in state $k$ at time $t$ given
$\mathbf{x}_{1:t}$ is given by

$\zeta_{k,t}(\Omega)=\mathbb{P}(z_{t}=k|\mathbf{x}_{1:t},\Omega),$ (2)

with
$\mathbf{x}_{t^{{}^{\prime}}:t}=(\mathbf{x}_{t^{{}^{\prime}}},\ldots,\mathbf{x}_{t})$,
$t^{{}^{\prime}}<t$, and $\Omega=\\{\vartheta_{1},\ldots,\vartheta_{P}\\}$,
$\vartheta_{p}\in(0,1)$, being a set of variables. The emission probability
for $\mathbf{y}_{t}$, given current state $z_{t}$ and covariate vector
$\mathbf{x}_{t}$, is given by some density function
$f_{y}(\mathbf{y}_{t}|z_{t};\mathbf{x}_{t},\Omega)$. A graphic representation
of the IO-HMM is given by Figure 1.

$z_{1}$$\mathbf{x}_{1}$$\mathbf{y}_{1}$$z_{2}$$\mathbf{x}_{2}$$\mathbf{y}_{2}$$z_{T}$$\mathbf{x}_{T}$$\mathbf{y}_{T}$
Figure 1: IO-HMM

Now let us consider IO-HMM under the lens of expectation maximization (EM).
Let $i\in\\{1,\ldots,n\\}$ be the index of some realization of
$\\{\mathbf{x}_{t},\mathbf{y}_{t},z_{t}\\}_{t=1,\ldots,T}$. For brevity, we
write
$\mathbf{z}^{(i)}_{t^{{}^{\prime}}:t}=(z_{t^{{}^{\prime}}}^{(i)},\ldots,z_{t}^{(i)})$,
$t^{{}^{\prime}}<t$ (idem for $\mathbf{y}^{(i)}_{t^{{}^{\prime}}:t}$ and
$\mathbf{x}^{(i)}_{t^{{}^{\prime}}:t}$), and
$\mathbf{Z}=(\mathbf{z}_{1:T}^{(1)},\ldots,\mathbf{z}_{1:T}^{(n)})$ (idem for
$\mathbf{Y}$ and $\mathbf{X}$). We are interested in maximizing the likelihood
function

$\displaystyle\mathcal{L}(\Omega;\mathbf{X},\mathbf{Y})$
$\displaystyle=\mathbb{P}(\mathbf{Y}|\mathbf{X},\Omega)$ (3)
$\displaystyle=\sum_{\mathbf{Z}}\mathbb{P}(\mathbf{Y},\mathbf{Z}|\mathbf{X},\Omega),$

with respect to $\Omega$. Since it is usually not possible to maximize this
function directly, EM rather tries to maximize

$Q(\Omega;\hat{\Omega})=\mathbb{E}_{\mathbf{Z}}\left[l_{c}(\Omega;\mathbf{Z},\mathbf{Y},\mathbf{X})|\mathbf{Y},\mathbf{X},\hat{\Omega}\right],$
(4)

with respect to $\Omega$, keeping some current estimates $\hat{\Omega}$
constant. Here $l_{c}(\Omega;\mathbf{Z},\mathbf{Y},\mathbf{X})$ is the
complete data log-likelihood

$l_{c}(\Omega;\mathbf{Z},\mathbf{Y},\mathbf{X})=\sum_{i=1}^{n}\log\mathbb{P}(\mathbf{y}_{1:T}^{(i)},\mathbf{z}_{1:T}^{(i)}|\mathbf{x}_{1:T}^{(i)};\Omega).$
(5)

Once some (possibly local) optimum $\Omega^{*}$ has been found, the current
estimates are updated: $\hat{\Omega}\leftarrow\Omega^{*}$. This process
continues until convergence.

In the case of IO-HMM, $Q(\Omega;\hat{\Omega})$ can be written as

$Q(\Omega;\hat{\Omega})=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K}\left(\hat{\zeta}_{k,t}^{(i)}\log
f_{y}(\mathbf{y}_{t}^{(i)}|z_{t}^{(i)},\mathbf{x}_{t}^{(i)};\Omega)+\sum_{k^{{}^{\prime}}=1}^{K}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)\right),$
(6)

with

$\hat{h}_{k^{{}^{\prime}}k,t}=\mathbb{E}\left[a_{k,t}^{(i)}a_{k^{{}^{\prime}},t-1}^{(i)}|\mathbf{x}_{1:T}^{(i)},\mathbf{y}_{1:T}^{(i)},\hat{\Omega}\right],$
(7) $a_{k,t}^{(i)}=\left\\{\begin{array}[]{ll}1&\text{if }z_{t}^{(i)}=k\\\
0&\text{otherwise}\end{array}\right.,$ (8)

and $\hat{\zeta}_{k,t}$, being defined as in (2), but conditional on current
estimates $\hat{\Omega}$.

###  3.2 The generalized cascade model (GCM) and its resemblance to IO-HMM

As mentioned by Chapelle and Zhang [7], many click models show considerable
resemblance with hidden Markov models. However, to our knowledge, this
resemblance has so far not been made explicit. Neither has previous literature
taken advantage of this resemblance. Which is unfortunate, as we do believe
there is a considerable advantage to such an approach. Writing out the updates
for the parameters $\Omega$ in a specific click model can be a tedious and
error prone job, as is somewhat illustrated in [8, Ch. 4]. Furthermore, this
approach only makes partial use of the resemblance between the different click
models to quickly find an estimation procedure for $\Omega$. Using the IO-HMM,
we are (only) required to define the latent state space, and transition
probabilities $\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)$ corresponding to a
particular click model, after which we can use the IO-HMM machinery to
evaluate $Q(\Omega,\hat{\Omega})$.

To show that we can indeed use IO-HMM to estimate click models, we will first
provide a definition for click models having a cascade effect, that is, where
the probability of a user clicking an item at position $t$ in a search engine
result page (SERP) depends on clicks/skips on items before $t$, but not after
$t$. First, we shall introduce some extra notation. We now let $i$ represent a
single query session on a search engine. We define a query session as a single
realization of the variables
$\\{\mathbf{x}_{t},\bm{\psi}_{t},y_{t}\\}_{t=1,\ldots,T}$, with
$\bm{\psi}_{t}=(\psi_{t,1},\ldots,\psi_{t,P})$, $\psi_{t,p}\in\\{0,1\\}$, and
$\mathbb{P}(\psi_{t,p}=1|\mathcal{P}(\psi_{t,p});\mathbf{x}_{t},\Omega)=\vartheta_{t,p}$.
$\mathbf{x}_{t}$ has the same interpretation as before, while
$y_{t}\in\\{0,1\\}$, with $y_{t}=1$ if item at position $t$ is clicked, and
$y_{t}=0$ if the $t$-th item is not clicked (i.e., skipped). We assume there
is exactly one configuration of $\bm{\psi_{t}}$ which leads to a positive
probability of $y_{t}=1$. We call this state the ‘click state’, and denote it
by $\mathcal{C}_{t}$. I.e., we allow which state is the click state to depend
on $t$.

Each query session results in a SERP consisting of items
$\mathcal{S}_{i}\subset\mathcal{V}$, with $\mathcal{V}=\\{1,\ldots,V\\}$ the
set of possible items the search engine may return. For simplicity, we will
assume each list $\mathcal{S}_{i}$ has the same number of items $T$, and each
item in $\mathcal{S}_{i}$ occupies an unique position $t\in\\{1,\ldots,T\\}$.
The item in position $t$ in list $\mathcal{S}_{i}$ is given by the bijective
function $r_{i}(t)$. Since, like in IO-HMM, we assume realizations
$i=\\{1,\ldots,n\\}$ to be conditionally independent given
$\mathbf{x}_{1:T}^{(i)}$, we will briefly omit index $i$ in Definition 3.2.

######  Definition 3.2.

A Generalized Cascade Model (GCM) is a Dynamic Bayesian Network consisting of
observed states $\\{\mathbf{x}_{t},y_{t}\\}_{t=1,\ldots,T}$, and latent states
$\\{\bm{\psi}_{t}\\}_{t=1,\ldots,T}$, for which for $t>1$:
$\mathcal{P}(\bm{\psi}_{t})=\\{\bm{\psi}_{t-1},y_{t-1},\mathbf{x}_{t}\\}$;
$\mathcal{P}(\bm{\psi}_{1})=\\{\mathbf{x}_{t}\\}$, and for all $t$:
$\mathcal{P}(y_{t})=\\{\mathbf{x}_{t},\bm{\psi}_{t}\\}$, and
$\mathcal{P}(\mathbf{x}_{t})=\emptyset$.

$\bm{\psi}_{1}$$\mathbf{x}_{1}$$y_{1}$$\bm{\psi}_{2}$$\mathbf{x}_{2}$$y_{2}$$\bm{\psi}_{T}$$\mathbf{x}_{T}$$y_{T}$
Figure 2: GCM

A graphical representation of GCM is given in Figure 2. The similarity between
GCM and IO-HMM should become quickly apparent: in GCM, transition
probabilities also depend on $y_{t-1}$, which is not the case for IO-HMM. On
the other hand, GCM assumes $y_{t}$ to be binary, instead of in
$\mathbb{R}^{R_{2}}$, and $\bm{\psi}_{t}$ is possibly multi-dimensional.
However, as Proposition 1 shows, for optimization by EM these distinctions do
not matter.

######  Proposition 1.

$Q_{\text{GCM}}(\Omega,\hat{\Omega})$ can be written in the form of Eq. (6).

###### Proof.

We will first convert the multi-dimensional state space into a single-
dimensional one, which can easily be done as all we assumed all latent state
variables are binary. E.g., we may use the transformation

$z_{t}^{(i)}=\text{bin}(\bm{\psi}_{t}^{(i)})=\sum_{p=1}^{P}2^{p-1}\psi_{t,p}^{(i)}+1,$
(9)

to obtain the single-dimensional discrete state space. Note that the $+1$ is
strictly not necessary, but simply added to map to some discrete state space
counting from 1.

Using Eq. (4) we now have

$\displaystyle Q_{\text{GCM}}(\Omega,\hat{\Omega})$
$\displaystyle=\mathbb{E}_{\mathbf{Z}|\mathbf{Y},\mathbf{X},\hat{\Omega}}\left[l_{c}^{\text{GCM}}(\Omega;\mathbf{Z},\mathbf{Y},\mathbf{X})\right]$
(10)
$\displaystyle=\mathbb{E}_{\mathbf{Z}|\mathbf{Y},\mathbf{X},\hat{\Omega}}\left[\sum_{i=1}^{n}\log\mathbb{P}\left(\mathbf{y}_{1:T}^{(i)},\mathbf{z}_{1:T}^{(i)}|\mathbf{x}_{1:T}^{(i)};\Omega\right)\right]$
$\displaystyle=\mathbb{E}_{\mathbf{Z}|\mathbf{Y},\mathbf{X},\hat{\Omega}}\left[\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K}\mathds{1}_{\\{z_{t}^{(i)}=k\\}}\log\mathbb{P}\left(y_{t}^{(i)}|z_{t}^{(i)}=k,\mathbf{x}_{t}^{(i)},y_{t-1}^{(i)};\Omega\right)\right.$
$\displaystyle\quad+\left.\sum_{k^{{}^{\prime}}=1}^{K}\mathds{1}_{\\{z_{t}^{(i)}=k,z_{t-1}^{(i)}=k^{{}^{\prime}}\\}}\log\mathbb{P}\left(z_{t}^{(i)}=k|z_{t-1}^{(i)}=k^{{}^{\prime}},\mathbf{x}_{t}^{(i)},y_{t-1}^{(i)};\Omega\right)\right]$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K}\hat{\zeta}_{k,t}^{(i)}\log\mathbb{P}\left(y_{t}^{(i)}|z_{t}^{(i)}=k,\mathbf{x}_{t}^{(i)},y_{t-1}^{(i)};\Omega\right)$
$\displaystyle\quad+\sum_{k^{{}^{\prime}}}^{K}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\mathbb{P}\left(z_{t}^{(i)}=k|z_{t-1}^{(i)}=k^{{}^{\prime}},\mathbf{x}_{t}^{(i)},y_{t-1}^{(i)};\Omega\right)$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K}\hat{\zeta}_{k,t}^{(i)}\log\mathbb{P}\left(y_{t}^{(i)}|z_{t}^{(i)}=k,\mathbf{x}_{t}^{(i)^{\prime}};\Omega\right)$
$\displaystyle\quad+\sum_{k^{{}^{\prime}}}^{K}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\mathbb{P}\left(z_{t}^{(i)}=k|z_{t-1}^{(i)}=k^{{}^{\prime}},\mathbf{x}_{t}^{(i)^{\prime}};\Omega\right)$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K}\left(\hat{\zeta}_{k,t}^{(i)}\log
f_{y}\left(y_{t}^{(i)}|z_{t}^{(i)}=k,\mathbf{x}_{t}^{(i)^{\prime}};\Omega\right)+\sum_{k^{{}^{\prime}}=1}^{K}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\tilde{\varphi}_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)\right),$

with
$\mathbf{x}_{t}^{(i)^{\prime}}=\left(\mathbf{x}_{t}^{(i)},y_{t-1}^{(i)}\right)$.
∎

Hence, as a result, when our objective is to estimate a GCM using EM, we can
simply model it as it were an IO-HMM, but adding the previous click to the
input vector. For notational simplicity, we will in the remainder of this
paper write $\mathbf{x}_{t}^{(i)}$ instead of $\mathbf{x}_{t}^{(i)^{\prime}}$.
We deliberately write $\tilde{\varphi}_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)$,
and not $\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)$, for reasons that will
become apparent in Proposition 2.

##  4 On the estimation of GCMs using EM for IO-HMM

###  4.1 Notes on the E-step

As briefly discussed, we believe that modeling GCMs as IO-HMMs has as main
advantage that, given transition probabilities
$\tilde{\varphi}_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)$, the IO-HMM framework
directly provides an EM procedure. Although this approach will not reduce time
complexity, we believe it does greatly reduces the effort required of finding
expressions for the EM-updates. In particular, given Proposition 1, Bengio and
Frasconi [3] immediately provides the expression required during the E-step.
Since GCM is a simplified case of IO-HMM, we can make use of Proposition 2 to
somewhat simplify Expression (10).

######  Proposition 2.

There exists transition probabilities
$\\{\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)\\}_{i=1,\ldots,n}^{t=1,\ldots,T}$,
with $k^{{}^{\prime}},k\in\\{1,\ldots,K+1\\}$, such that maximizing
$Q_{\text{GCM}}(\Omega,\hat{\Omega})$ is equivalent to maximizing

$Q^{{}^{\prime}}_{\text{GCM}}(\Omega,\hat{\Omega})=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K+1}\sum_{k^{{}^{\prime}}=1}^{K+1}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega).$
(11)

###### Proof.

As one might expect, our objective here is to absorb the emission probability
$f_{y}(\cdot)$ into the new transition probabilities
$\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)$. If we define

$\vartheta_{t,y}^{(i)}=f_{y}\left(y_{t}^{(i)}|z_{t}^{(i)}=k,\mathbf{x}_{t}^{(i)^{\prime}};\Omega\right),$
(12)

then a natural thing to do would be to introduce a new latent binary variable
$\psi_{t,y}^{(i)}$, with

$\mathbb{P}(\psi_{t,y}^{(i)}=1|\bm{\psi}_{t}^{(i)},\mathbf{x}_{t}^{(i)^{\prime}};\Omega)=\vartheta_{t,y}^{(i)}.$
(13)

However, this would imply
$\mathcal{P}(\psi_{t,y}^{(i)})=\\{\bm{\psi}_{t}^{(i)},\mathbf{x}_{t}^{(i)}\\}$.
Hence, the resulting model would not be a GCM, as $\psi_{t,y}^{(i)}$ depends
on the current latent state, not the previous latent state. To circumvent this
problem, we can include the dependency of the emission on the current state
into the definition of the transition probability. Here we make use of the
fact that there exists only one click state. I.e., only when
$k=\mathcal{C}_{t}$ does $\vartheta_{t,y}^{(i)}$ affect the transition
probability.

At this point, it is useful to consider the expression that we, according to
Eq. (10), would expect for the transition probability. Let
$\bm{\psi}_{k}^{{}^{\prime}}=(\psi^{{}^{\prime}}_{k,1},\ldots,\psi_{k,P}^{{}^{\prime}})$
be the (unique) vector corresponding to
$\text{bin}(\bm{\psi}_{k}^{{}^{\prime}})=k$. Under the definition of GCM (Def.
3.2), $\\{\psi_{t,1}^{(i)},\ldots,\psi_{t,P}^{(i)}\\}$ are mutually
independent given $\mathbf{x}_{t}^{(i)}$ and $\bm{\psi_{t-1}}^{(i)}$, such
that we would obtain

$\tilde{\varphi}_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)=\prod_{p=1}^{P}\left(\vartheta_{t,p}^{(i)}\right)^{\psi_{t,p}^{{}^{\prime}}}\left(1-\vartheta_{t,p}^{(i)}\right)^{1-\psi_{t,p}^{{}^{\prime}}}.$
(14)

Now let
$\mathbb{P}(\psi_{t,y}^{(i)}=1|\bm{\psi}_{t-1}^{(i)},\mathbf{x}_{t}^{(i)^{\prime}};\Omega)=\vartheta_{t,y}^{(i)}$,
then after including the additional variable, the transition probability
becomes

$\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)=\prod_{p=1}^{P}\left(\vartheta_{t,p}^{(i)}\right)^{\psi_{t,p}^{{}^{\prime}}}\left(1-\vartheta_{t,p}^{(i)}\right)^{1-\psi_{t,p}^{{}^{\prime}}}\left[\left(\vartheta_{t,y}^{(i)}\right)^{\psi_{t,y}^{{}^{\prime}}}\left(1-\vartheta_{t,y}^{(i)}\right)^{1-\psi_{t,y}^{{}^{\prime}}}\right]^{\mathds{1}_{\\{k=\mathcal{C}_{t}\\}}}.$
(15)

Now let
$z_{t}^{(i)^{\prime}}=\text{bin}\left(\bm{\psi}_{t}^{(i)^{\prime}}\right)$,
with
$\bm{\psi}_{t}^{(i)^{\prime}}=\left(\psi_{t,1}^{(i)},\ldots,\psi_{t,P}^{(i)},\psi_{t,y}^{(i)}\right)$
being the state in the new augmented state space, we obtain
$f_{y}(y_{t}^{(i)}|z_{t}^{(i)^{\prime}}=k,\mathbf{x}_{t}^{(i)};\Omega)=1$.
Hence, indeed this new emission probability does not depend on $\Omega$, and
the emission can be ignored in the maximization.

∎

It should also be noted that in many click models, including CZM and UBM, the
emission probability does not depend on $\Omega$ by definition. Hence, many
models do not require an additional latent state variable, and for those
models the cardinality of the state space could remain the same. Though the
analysis of Proposition 2 still holds if we would have
$\vartheta_{t,y}^{(i)}=1$, hence we can always augment the state space. For
notational simplicity, we will redefine $K$ and $P$ to represent the size of
the augmented state space and augmented number of latent variables at $(i,t)$
respectively.

Dropping superscript $(i)$ for a moment, the E-step is given by Proposition 3,
which are also known as the forward-backward equations.

######  Proposition 3.

Let
$\alpha_{k,t}=\mathbb{P}(\mathbf{y}_{1:t},z_{t}=k|\mathbf{x}_{1:t};\Omega)$
and
$\beta_{k,t}=\mathbb{P}(\mathbf{y}_{t+1:T}|z_{t}=k,\mathbf{x}_{t+1:T};\Omega)$,
then we obtain:

$\hat{\alpha}_{k,t}=\mathds{1}_{\\{y_{t}=1|z_{t}=k\\}}\sum_{k^{{}^{\prime}}=1}^{K}\hat{\varphi}_{k^{{}^{\prime}}k,t}(\mathbf{x}_{t})\hat{\alpha}_{k^{{}^{\prime}},t-1},$
(16)
$\hat{\beta}_{k,t}=\sum_{k^{{}^{\prime}}=1}^{K}\hat{\varphi}_{kk^{{}^{\prime}},t}(\mathbf{x}_{t+1})\hat{\beta}_{k^{{}^{\prime}},t+1}\mathds{1}_{\\{y_{t+1}=1|z_{t+1}=k^{{}^{\prime}}\\}},$
(17)

and

$\hat{h}_{k^{{}^{\prime}}k,t}=\frac{\hat{\beta}_{k,t}\hat{\alpha}_{k^{{}^{\prime}},t-1}\hat{\varphi}_{k^{{}^{\prime}}k,t}(\mathbf{x}_{t})}{\sum_{\ell=1}^{K}\hat{\alpha}_{\ell,T}}\mathds{1}_{\\{y_{t}=1|z_{t}=k\\}},$
(18)

with $\hat{\varphi}_{kk^{{}^{\prime}},t}(\mathbf{x}_{t})$ the estimated
transition probability under $\hat{\Omega}$.

###### Proof.

Follows directly from [3]. ∎

###  4.2 Notes on the M-step

One useful property of GCM is that Eq. (11) can be split into multiple
optimization problems.

######  Proposition 4.

Let $\bm{\theta}_{p}$ be the weight vector of dimension $m_{p}$ for parameter
$p$, such that
$\vartheta_{t,p}^{(i)}=f_{\text{act}}^{p}(\mathbf{x}_{t,p}^{(i)};\bm{\theta}_{p})=\mathbb{P}(\psi_{t,p}^{(i)}=1|\mathcal{P}(\psi_{t,p}^{(i)}),\mathbf{x}_{t,p}^{(i)};\Omega)$,
with $\mathbf{x}_{t,p}^{(i)}$ the covariate vector for parameter $p$, then

$\operatorname*{arg\,max}\limits_{\Omega}Q_{GCM}(\Omega,\hat{\Omega})=\left\\{\operatorname*{arg\,max}\limits_{\bm{\theta}_{p}\in\mathbb{R}^{m_{p}}}Q_{GCM}^{{}^{\prime}}(\bm{\theta}_{p},\hat{\Omega})\right\\}_{p=1,\ldots,P}.$
(19)

###### Proof.

Let
$\bm{\psi}_{k}^{{}^{\prime}}=(\psi^{{}^{\prime}}_{k,1},\ldots,\psi_{k,P}^{{}^{\prime}})$
be the (unique) vector corresponding to
$\text{bin}(\bm{\psi}_{k}^{{}^{\prime}})=k$. Note that we now assume this
represents the state in the augmented state space, i.e., the vector includes
$\psi_{k,y}^{{}^{\prime}}$, which was defined in Proposition 2. Furthermore,
let $\mathcal{K}(k)$ be original state that we would obtain by omitting
$\psi_{k,y}^{{}^{\prime}}$ in $\bm{\psi}_{k}^{{}^{\prime}}$.

We define $\mathcal{A}^{(+)}_{t,p,i}$, $\mathcal{A}^{(-)}_{t,p,i}$ as be the
set of all transition
$(k^{{}^{\prime}},k)\in\\{1,\ldots,K+1\\}\times\\{1,\ldots,K+1\\}$ having
$\vartheta_{t,p}^{(i)}\in(0,1)$, and for which $\psi_{t,p}^{(i)}=1$ and
$\psi_{t,p}^{(i)}=0$ respectively. Then

$\displaystyle Q^{{}^{\prime}}_{\text{GCM}}(\Omega,\hat{\Omega})$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K+1}\sum_{k^{{}^{\prime}}=1}^{K+1}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\varphi_{k^{{}^{\prime}}k,t}^{(i)}(\Omega)$
(20)
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{k=1}^{K}\sum_{k^{{}^{\prime}}=1}^{K}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\sum_{\psi\in\\{\psi_{t,1}^{(i)},\ldots,\psi_{t,P}^{(i)}\\}\setminus\\{\psi_{t,y}^{(i)}\\}}\log\mathbb{P}(\psi|\mathcal{P}(\psi_{t,p}^{(i)}),\mathbf{x}_{t,p}^{(i)};\Omega)$
$\displaystyle\quad+\mathds{1}_{\\{\mathcal{K}(k)=\mathcal{C}_{\mathcal{K}(k)}\\}}\log\mathbb{P}(\psi_{t,y}^{(i)}=\psi_{k,y}^{{}^{\prime}}|\mathcal{P}(\psi_{t,y}^{(i)}),\mathbf{x}_{t,y}^{(i)};\Omega)$
$\displaystyle=\sum_{p=1}^{P}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{(k^{{}^{\prime}},k)\in\mathcal{A}^{(+)}_{t,p,i}}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\mathbb{P}(\psi_{t,p}^{(i)}=1|\mathcal{P}(\psi_{t,p}^{(i)}),\mathbf{x}_{t,p}^{(i)};\Omega)$
$\displaystyle\quad+\sum_{(k^{{}^{\prime}},k)\in\mathcal{A}^{(-)}_{t,p,i}}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log\mathbb{P}(\psi_{t,p}^{(i)}=0|\mathcal{P}(\psi_{t,p}^{(i)}),\mathbf{x}_{t,p}^{(i)};\Omega)$

Hence, optimizing $Q_{\text{GCM}}(\Omega,\hat{\Omega})$ is therefore
equivalent to optimizing

$Q^{p}_{\text{GCM}}(\bm{\theta}_{p},\hat{\Omega})=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{(k^{{}^{\prime}},k)\in\mathcal{A}^{(+)}_{t,p,i}}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log
f_{\text{act}}^{p}(\mathbf{x}_{t,p}^{(i)};\bm{\theta}_{p})+\sum_{(k^{{}^{\prime}},k)\in\mathcal{A}^{(-)}_{t,p,i}}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}\log(1-f_{\text{act}}^{p}(\mathbf{x}_{t,p}^{(i)};\bm{\theta}_{p}))$
(21)

for each $p\in\\{1,\ldots,P\\}$ separately. ∎

######  Proposition 5.

Let

$\hat{h}_{p}^{(+)}=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{(k^{{}^{\prime}},k)\in\mathcal{A}^{(+)}_{t,p,i}}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)},$
(22)

and

$\hat{h}_{p}^{(-)}=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{(k^{{}^{\prime}},k)\in\mathcal{A}^{(-)}_{t,p,i}}\hat{h}_{k^{{}^{\prime}}k,t}^{(i)}.$
(23)

In case
$f_{\text{act}}^{p}(\bm{\theta}_{p};\mathbf{x}_{t,p}^{(i)})=\theta_{p}=\vartheta_{p}$,
$\theta_{p}\in(0,1)$, the M-step becomes:

$\hat{\vartheta}_{p}=\frac{\hat{h}_{p}^{(+)}}{\hat{h}_{p}^{(+)}+\hat{h}_{p}^{(-)}}$
(24)

###### Proof.

Follows directly from [8, pp. 27-30]. ∎

Hence, by modeling GCM as an IO-HMM, we find exactly the same EM updates as in
[8]. However, IO-HMM also directly gives the E-step ( Proposition 3), which in
[8] still had to be derived for each variable separately. Furthermore, Bengio
and Frasconi [3] also show that if $\mathbf{x}_{t}=x_{t}\in\\{1,\ldots,L\\}$
for some $L\in\mathbb{N}$, then the M-step also has an analytical solution.

Apart from introducing IO-HMM and its estimation using EM, Bengio and Frasconi
[3] also model
$\mathbb{P}(\psi_{t,p}^{(i)}|\mathcal{P}(\psi_{t,p}^{(i)}),\mathbf{x}_{t};\Omega)$
as the output of a neural network. In that case, one could interpret Equation
(21) as a weighted log loss function. This may be a ‘best of both worlds’
scenario: as shown by [5], recurrent neural networks may perform quite well in
untangling the manifold obtained from the input vector $\mathbf{x}_{t}$, which
seems in particular relevant when one uses noisy features such as historic
click/skips. However, since we use the loss function of a GCM, we can still
interpret the results of in terms of the latent variables defined in the
proposed click model, such as attraction, satisfaction, or evaluation. I.e.,
our model remains in that respect interpretable.

###  4.3 Vectorized EM

#### Vectorized E-step

To conclude this section, we will elaborate shortly on how $Q_{\text{GCM}}$ is
optimized in the `gecasmo` package. This relates mostly to rewriting the
E-step and M-step in vector notation. Since in the following we consider a
single query session, we will for the time being drop superscript $i$. We
define

$A=\begin{pmatrix}\alpha_{10}&\ldots&\alpha_{1T}\\\ \vdots&\ddots&\vdots\\\
\alpha_{K0}&\ldots&\alpha_{KT}\end{pmatrix},\quad
B=\begin{pmatrix}\beta_{10}&\ldots&\beta_{1T}\\\ \vdots&\ddots&\vdots\\\
\beta_{K0}&\ldots&\beta_{KT}\end{pmatrix},$ (25)

and let

$H_{t}=\begin{pmatrix}h_{11,t}&\ldots&h_{1K,t}\\\ \vdots&\ddots&\vdots\\\
h_{K1,t}&\ldots&h_{KK,t}\end{pmatrix},\quad
M_{t}=\begin{pmatrix}\varphi_{11,t}&\ldots&\varphi_{1K,t}\\\
\vdots&\ddots&\vdots\\\
\varphi_{K1,t}&\ldots&\varphi_{KK,t}\end{pmatrix},\quad
D=\begin{pmatrix}\delta_{10}&\ldots&\delta_{1T}\\\ \vdots&\ddots&\vdots\\\
\delta_{K0}&\ldots&\delta_{KT}\end{pmatrix},$ (26)

with $\delta_{kt}=1$ if state $k$ is the click state at time $t$ (0
otherwise). Note that we only have one click state, i.e.,
$\sum_{k=1}^{K}\delta_{kt}=1$ for all $t\in\\{0,\ldots,T\\}$. Let $\odot$ be
the element-wise product. Using Expressions (16), (17), and (18), we obtain
the following vectorized E-step (Alg. 1).

1 $B_{1:K,T}\leftarrow 1$

2 $A_{1:K,0}\leftarrow D_{1:K,0}$

3 for  _$t\leftarrow 1$ to $T$_ do

4 $A_{1:K,t}\leftarrow
y_{t}\left[D_{1:K,t}\odot\left(M_{t}^{\top}A_{1:K,t-1}\right)\right]+\left(1-y_{t}\right)\left[\left(1-D_{1:K,t}\right)\odot\left(M_{t}^{\top}A_{1:K,t-1}\right)\right]$

5

6for  _$t\leftarrow T$ to $1$_ do

7 $\Lambda_{t}\leftarrow y_{t}\left(D_{1:K,t}\odot
B_{1:K,t}\right)+(1-y_{t})\left[(1-D_{1:K,t})\odot B_{1:K,t}\right]$

8 $B_{1:K,t-1}\leftarrow M_{t}\Lambda_{t}^{\top}$

9
$H_{t}\leftarrow\left[\frac{\Lambda_{t}}{\sum_{k=1}^{K}\alpha_{k,T}}A_{1:K,t-1}^{\top}\right]\odot
M_{t}^{\top}$

Algorithm 1 Vectorized E-step

#### Vectorized M-step

For convenience, we will slightly rewrite (21). Let

$c_{k^{{}^{\prime}}k,t,p,i}^{(o)}=\left\\{\begin{array}[]{cc}1&\text{if
}(k^{{}^{\prime}},k)\in\mathcal{A}_{t,p,i}^{(o)},\quad o=+\\\ -1&\text{if
}(k^{{}^{\prime}},k)\in\mathcal{A}_{t,p,i}^{(o)},\quad o=-\\\
0&\text{otherwise}\\\ \end{array}\right.,$ (27)
$I_{t,p,i}^{(o)}=\begin{pmatrix}c_{11,t,p,i}^{(o)}&c_{12,t,p,i}^{(o)}&\cdots&c_{1K,t,p,i}^{(o)}\\\
\vdots&\vdots&\ddots&\vdots\\\
c_{K1,t,p,i}^{(o)}&c_{K2,t,p,i}^{(o)}&\cdots&c_{KK,t,p,i}^{(o)}\\\
\end{pmatrix},$ (28)

and

$w_{t,p,i}^{(o)}=\left(\left(\hat{H}_{t}^{(i)}\odot
I_{t,p,i}^{(o)}\right)\mathbf{1}\right)^{\top}\mathbf{1},$ (29)

with $\mathbf{1}$ a vector of ones of size $K$, $o\in\\{+,-\\}$, and $\odot$
being the element-wise multiplication operator. Let
$w_{t,p,i}=w_{t,p,i}^{(+)}+w_{t,p,i}^{(-)}$, now (21) can be rewritten as

$\displaystyle Q^{p}_{\text{GCM}}(\bm{\theta}_{p},\hat{\Omega})$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}w_{t,p,i}^{(+)}\log
f_{\text{act}}^{p}(\mathbf{x}_{t};\mathbf{\bm{\theta}}_{p})+(-w_{t,p,i}^{(-)})\log\left(1-f_{\text{act}}^{p}(\mathbf{x}_{t};\mathbf{\bm{\theta}}_{p})\right)$
(30)
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}|w_{t,p,i}|\left[\frac{\text{sgn}(w_{t,p,i})+1}{2}\log
f_{\text{act}}^{p}(\mathbf{x}_{t};\mathbf{\bm{\theta}}_{p})\right.$
$\displaystyle\left.\quad+\left(1-\frac{\text{sgn}(w_{t,p,i})+1}{2}\right)\log(1-f_{\text{act}}^{p}(\mathbf{x}_{t};\mathbf{\bm{\theta}}_{p}))\right].$

In the latter expression, we conveniently make use of the fact that for some
triple ($t,p,i$), either $w_{t,p,i}^{(+)}$ or $w_{t,p,i}^{(-)}$ is non-zero.
Hence, we only have to keep one $T\times P\times n$ tensor in memory, and use
the sign of the weight to determine whether the weight is with respect to
$\psi_{t,p}^{(i)}=1$ or $\psi_{t,p}^{(i)}=0$. Although the former expression
in (30) has the same form as binary cross-entropy, we have
$w_{t,p,i}^{(+)}+(-w_{t,p,i}^{(-)})\leq 1$, hence it should be interpreted as
a weighted log-loss function.

Finally, the GCM’s EM algorithm is summarized in Algorithm 2.

inputs : Initial parameter estimates $\hat{\Omega}$;

Covariates matrices $\\{X_{p}\\}_{p=1,\ldots,P}$;

Parameter activation functions
$\\{f_{\text{act}}^{p}(\cdot)\\}_{p=1,\ldots,P}$;

Parameter activation matrices
$\\{I_{p,t}^{(+)},I_{p,t}^{(-)}\\}_{p=1,\ldots,P}^{t=t\ldots,T}$;

Transition matrices $\\{M_{t}^{(i)}\\}_{i=1,\ldots,n}^{t=1,\ldots,T}$;

Tolerance parameter $\epsilon$

; output : Fitted parameters $\\{\hat{\bm{\theta}}_{p}\\}_{p=1,\ldots,P}$

1 Choose some initial parameters $\\{\hat{\bm{\theta}}_{p}\\}_{p=1,\ldots,P}$,
and $\Delta>\epsilon$;

2 while  _$\Delta >\epsilon$_ do

3 Run the E-step (Alg. 1), given current estimates $\hat{\Omega}$;

4 Compute the weights for each variable $p$ using Expression (29);

5 Find for each variable $p$ new weights $\hat{\bm{\theta}}_{p}^{{}^{\prime}}$
by optimizing (30);

6
$\Delta=\sum_{p=1}^{p}|\hat{\bm{\theta}}_{p}-\hat{\bm{\theta}}_{p}^{{}^{\prime}}|$;

7 Set $\hat{\bm{\theta}}_{p}\leftarrow\hat{\bm{\theta}}_{p}^{{}^{\prime}}$;

8

return $\\{\hat{\bm{\theta}}_{p}\\}_{p=1,\ldots,P}$;

Algorithm 2 GCM’s EM procedure

##  5 Modeling click models as GCM

###  5.1 Mapping click models to GCM

In Section 3.2, we introduced the generalized cascade model, and showed that
optimization with EM is equivalent to that of the IO-HMM model, given that we
add the click/skip at position $t-1$ to the input vector
$\mathbf{x}_{t}^{(i)}$. In this section, we will show that common click models
such as the Chapelle-Zhang model (CZM) [7], and the User Browser Model (UBM)
[14], can be rewritten as GCMs. As a direct consequence, any simplification of
CZM or UBM (such as the cascade model [10] or the dependent click model [15])
are also GCMs. In fact, any click model where the latent variables can be
combined into one discrete latent state variable $z_{t}$, such that the
remaining model is still Markovian w.r.t. its parent as defined in GCM’s
definition (Def. 3.2), can be modeled as GCM. Hence, also more general models
than CZM and UBM can be modeled as GCM.

######  Definition 5.1.

The Chapelle-Zhang model (CZM) [7] is a Dynamic Bayesian Network consisting of
latent binary variables
$\\{R_{r_{i}(t)}^{(i)},S_{r_{i}(t)}^{(i)},E_{t}^{(i)}\\}^{i=1,\ldots,n}_{t=1,\ldots,T}$,
and observed binary variables
$\\{y_{t}^{(i)}\\}^{i=1,\ldots,n}_{t=1,\ldots,T}$, where
$R_{r_{i}(t)}^{(i)}=1$ if the user finds the item at position $r_{i}(t)$
attractive (0 otherwise), $S_{r_{i}(t)}^{(i)}=1$ if the user is satisfied with
the item at position $r_{i}(t)$ after having clicked the item (0 otherwise),
$E_{t}^{(i)}=1$ if the item at position $t$ is evaluated by the user (0
otherwise), and $y_{t}^{(i)}=1$ if the item at position $t$ is clicked (0
otherwise). Given SERP $\mathcal{S}_{i}$, users navigate through the SERP
according to

$\mathbb{P}(R_{r_{i}(t)}^{(i)}=1)=\phi_{r_{i}(t)}^{(R)},$ (31)
$\mathbb{P}(S_{r_{i}(t)}^{(i)}=1|y_{t}^{(i)}=c)=\left\\{\begin{array}[]{ll}\phi_{r_{i}(t)}^{(S)}&\text{if
}c=1\\\ 0&\text{if }c=0\end{array}\right.;$ (32)
$\mathbb{P}(E_{t}^{(i)}=1|E_{t-1}^{(i)}=a,S_{r_{i}(t-1)}^{(i)}=b)=\left\\{\begin{array}[]{ll}\gamma&\text{if
}a=1,b=0\\\ 0&\text{otherwise}\end{array}\right.,\quad t>1;$ (33)
$E_{1}^{(i)}=1;$ (34) $y_{t}^{(i)}=1\iff E_{t}^{(i)}=1,R_{r_{i}(t)}^{(i)}=1.$
(35)

######  Definition 5.2.

The User Browser Model (UBM) [14] is a Dynamic Bayesian Network consisting of
latent binary variables
$\\{R_{r_{i}(t)}^{(i)},E_{t}^{(i)}\\}^{i=1,\ldots,n}_{t=1,\ldots,T}$, and
observed variables $\\{y_{t}^{(i)}\\}^{i=1,\ldots,n}_{t=1,\ldots,T}$, all
having the same interpretation as in CZM, for which we assume users navigate
through a SERP according to

$\mathbb{P}(R_{r_{i}(t)}^{(i)}=1)=\phi_{r_{i}(t)}^{(R)},$ (36)
$\mathbb{P}(E_{t}^{(i)}=1|y_{t^{{}^{\prime}}}^{(i)}=1)=\gamma_{t^{{}^{\prime}}t},\quad
t^{{}^{\prime}}<t$ (37) $y_{0}^{(i)}=1;$ (38) $y_{t}^{(i)}=1\iff
E_{t}^{(i)}=1,R_{r_{i}(t)}^{(i)}=1.$ (39)

In Propositions 6 and 7 again we briefly drop superscript $i$.

######  Proposition 6.

CZM is a GCM

###### Proof.

For simplicity, we again drop subscript $i$. Let
$\bm{\psi}_{t}=(S_{t-1},A_{t},E_{t})$ and $z_{t}=\text{bin}(\bm{\psi}_{t})$.
For completeness, we introduce auxiliary variables $S_{0}=0$ and $x_{t}=1$ for
all $t$. Then indeed we find $\mathcal{P}(z_{t})=\\{z_{t-1},y_{t-1},x_{t}\\}$
for $t>1$, $\mathcal{P}(z_{1})=\\{x_{1}\\}$,
$\mathcal{P}(y_{t})=\\{x_{t},z_{t}\\}$, and $\mathcal{P}(x_{t})=\emptyset$ for
all $t$. ∎

Hence, the idea of modeling click models as GCM is to combine the binary
latent variables $\psi_{t,1}^{(i)},\ldots,\psi_{t,P}^{(i)}$ between two
subsequent clicks into one latent variable by using Equation (9). I.e., the
size of the state space of $z_{t}$ becomes $\mathcal{O}(2^{P})$. If after this
transformation the click model is Markovian with respect to a subset of the
parents as defined in GCM, then we can conclude that the model is a GCM, and
we are allowed to use the IO-HMM machinery to estimate the model’s parameters
using EM.

Perhaps less obvious is that UBM can also be modeled as GCM. Looking at the
definition of UBM (Definition 5.2), we find that UBM is Markovian in the last
clicked item, hence, not Markovian in the previous position as is required by
GCM, something which is called the first-order examination assumption in click
literature [17]. However, we can pass information about the last clicked item
from position $t$ to position $t+1$, by expanding the state space, thereby
making UBM Markovian in the previous position.

######  Proposition 7.

UBM is a GCM

###### Proof.

From the definition of UBM, we find that it only has, at some time $t$, two
latent variables: $E_{t}$ and $A_{t}$. The parents are given by
$\mathcal{P}(A_{t})=\emptyset$, and
$\mathcal{P}(E_{t})=\\{y_{t^{{}^{\prime}}}\\}$, with
$t^{{}^{\prime}}=\max\\{\tilde{t}\in\\{0,\ldots,t-1\\}|y_{\tilde{t}}=1\\}$. We
now define $\mathbf{e}_{t}=(e_{1,t},\ldots,e_{T,t})$, where

$e_{t^{{}^{\prime}},t}=\left\\{\begin{array}[]{ll}\mathds{1}_{\\{t^{{}^{\prime}}<t\\}}e_{t^{{}^{\prime}},t-1}(1-y_{t})+\mathds{1}_{\\{t^{{}^{\prime}}=t\\}}y_{t}&\text{if
}t>0\\\ 1&\text{if }t=0\end{array}\right..$ (40)

I.e., $\mathbf{e}_{t}$ stores the last clicked item before position $t$. Since
$e_{t^{{}^{\prime}},t}\in\\{0,1\\}$, we can define
$\bm{\psi}_{t}=(\mathbf{e}_{t},A_{t},E_{t})$ and
$z_{t}=\text{bin}(\bm{\psi}_{t})$ to again obtain a one-dimensional discrete
latent state space. Let $x_{t}=1$ for all $t$, then indeed we find
$\mathcal{P}(z_{t})=\\{z_{t-1},y_{t-1},x_{t}\\}$ for $t>1$;
$\mathcal{P}(z_{1})=\\{x_{1}\\}$, $\mathcal{P}(y_{t})=\\{x_{t},z_{t}\\}$, and
$\mathcal{P}(x_{t})=\emptyset$ for all $t$. ∎

Following the derivations of Propositions 6 and 7, we also notice that we
could for example replace $\phi^{(A)}_{r_{i}(t)}$, $\phi^{(S)}_{r_{i}(t)}$,
and $\gamma$ with activation functions
$f_{\text{act}}^{(A)}(\mathbf{x}_{t}^{(A)};\bm{\theta}^{(A)})$,
$f_{\text{act}}^{(S)}(\mathbf{x}_{t}^{(S)};\bm{\theta}^{(S)})$, and
$f_{\text{act}}^{(E)}(\mathbf{x}_{t}^{(E)};\bm{\theta}^{(E)})$ in case of CZM.
To ensure the output of these activation functions are probabilities, we
ensure the activation functions all map to the interval $(0,1)$. Here
$\bm{\theta}=(\bm{\theta}^{(A)},\bm{\theta}^{(S)},\bm{\theta}^{(E)})$ is a
vector of unknown parameters, and
$\mathbf{x}_{t}^{(A)},\mathbf{x}_{t}^{(S)},\mathbf{x}_{t}^{(E)}$ is observed
data, stored in $\mathbf{x}_{t}$, i.e.,
$\mathbf{x}_{t}=(\mathbf{x}_{t}^{(A)},\mathbf{x}_{t}^{(S)},\mathbf{x}_{t}^{(E)})$.
The same argument holds for UBM. As a consequence, also generalizations of CZM
and UBM can be modeled as GCM (e.g., the Bayesian Sequential State Model [22],
or many of the ‘advanced click models’ described in Chuklin et al. [8][Ch.
8]), as long as the Markovian properties of GCM are met.

In terms of the cardinality of the state space, we do notice that adding the
vector of the last clicked item to the state space, as we have done with UBM,
at first seems to lead to a considerable memory burden. Where CZM has a
cardinality smaller than $2^{3}+1$ (as some combinations of
$\\{R_{t},E_{t},S_{t-1}\\}$ are infeasible), for UBM this becomes
$\mathcal{O}(2^{T})$. However, it should be noted that in most cases the
number of positions $T$ can be taken small. Click probabilities have a
geometric decay in $T$, and many empirical studies show that these
probabilities are already commonly already negligible for $T>10$ (e.g., [10,
5]). Hence, such state spaces are not likely to become a burden in terms of
computational complexity or storage.

###  5.2 Explicit mappings

In the following examples, we will provide an explicit mapping from CZM and
UBM to GCM. That is, how the transition matrix and activation matrices of
these two models could be defined to be able to run the GCM’s EM procedure
(Alg. 2). These example mappings have also been implemented and can by found
on the `gecasmo`’s Github page [12]

#### CZM to GCM

We will first consider how CZM can be written as GCM. As Proposition 6 already
showed, CZM can be modeled as a GCM by defining the latent state as
$\bm{\psi}_{t}^{(i)}=(S_{r_{i}(t-1)}^{(i)},R_{r_{i}(t)}^{(i)},E_{t}^{(i)})$,
where $S_{r_{i}(t-1)}^{(i)}$, $R_{r_{i}(t)}^{(i)}$, and $E_{t}^{(i)}$ are
interpreted as in Definition 5.1. One of the possible discretizations of the
state space is given by Table 1. We have 3 binary variables, which normally
would lead to a state space of size 8. However, we add an additional absorbing
state $O$, and the two states having $(S_{r_{i}(t-1)}^{(i)}=1,E_{t}^{(i)}=1)$
are infeasible, therefore we end up with a total of 7 states. The click state
represents the state in which an item is clicked, and as discussed before, we
assume there is only one such state for each $t$. For convenience, we also
added the corresponding click value $y_{t}^{(i)}$, though it is not part of
the state space.

State | $S_{r_{i}(t-1)}^{(i)}$ | $E_{t}^{(i)}$ | $R_{r_{i}(t)}^{(i)}$ | $y_{t}^{(i)}$
---|---|---|---|---
$0$ | $0$ | $0$ | $0$ | $0$
$1$ | $0$ | $0$ | $1$ | $0$
$2$ | $0$ | $1$ | $0$ | $0$
$3$ $(\mathcal{C}_{t})$ | $0$ | $1$ | $1$ | $1$
$4$ | $1$ | $0$ | $0$ | $0$
$5$ | $1$ | $0$ | $1$ | $0$
$6$ $(O)$ | - | - | - | -
- | 1 | 1 | 0 | $0$
- | 1 | 1 | 1 | $1$
Table 1: CZM state space mapping

Using this state mapping and the probabilities introduced in Definition 5.1,
and by writing $\bar{x}=1-x$, we find the transition matrix.

$M_{i,t}=\begin{pmatrix}0&0&0&0&0&0&1\\\ 0&0&0&0&0&0&1\\\
\bar{\gamma_{i}}\bar{\phi}^{(A)}_{r_{i}(t)}&\bar{\gamma_{i}}\phi^{(A)}_{r_{i}(t)}&\gamma_{i}\bar{\phi}^{(A)}_{r_{i}(t)}&\gamma_{i}\phi^{(A)}_{r_{i}(t)}&0&0&0\\\
\bar{\gamma_{i}}\bar{\phi}^{(A)}_{r_{i}(t)}\bar{\phi}^{(S)}_{r_{i}(t)}&\bar{\gamma_{i}}\phi^{(A)}_{r_{i}(t)}\bar{\phi}^{(S)}_{r_{i}(t)}&\gamma_{i}\bar{\phi}^{(A)}_{r_{i}(t)}\bar{\phi}^{(S)}_{r_{i}(t)}&\gamma_{i}\phi^{(A)}_{r_{i}(t)}\bar{\phi}^{(S)}_{r_{i}(t)}&\bar{\phi}^{(A)}_{r_{i}(t)}\phi^{(S)}_{r_{i}(t)}&\phi^{(A)}_{r_{i}(t)}\phi^{(S)}_{r_{i}(t)}&0\\\
0&0&0&0&0&0&1\\\ 0&0&0&0&0&0&1\\\ 0&0&0&0&0&0&1\\\ \end{pmatrix}.$ (41)

To further define the model in GCM, we rely on the activation matrices
$\\{I_{\tilde{p},t}^{(+)},I_{\tilde{p},t}^{(-)}\\}_{\tilde{p}=1,\ldots,\tilde{P}}^{t=t\ldots,T}$
and the activation functions $\\{f_{\text{act}}^{p}\\}_{p=1,\ldots,P}$. The
activation matrices can be directly obtained from the transition matrix, using
Equations (27), (28), and (41). To define the activation functions, we rely on
what data is available. To somewhat simplify the model, we assume
$\gamma_{i}=\gamma$ for all $i\in\mathcal{I}$, and we represent items by a
two-dimensional location vector. Although we could optimize $\gamma$ using
Expression (24), we will for uniformity numerically optimize the simple neural
network $f_{\text{act}}^{\gamma}(\theta_{\gamma};1)=\sigma(\theta_{\gamma})$
w.r.t. $\theta_{\gamma}$, $\sigma(\cdot)$ being the sigmoid function.

#### UBM to GCM

As discussed in Proposition 7, we can model UBM as a GCM by passing
information about the last clicked item through positions $1,\ldots,T$. The
state of the system at some session/position $(i,t)$ is defined by
$\bm{\psi}_{t}^{(i)}=(\mathbf{e}_{t}^{(i)},R_{r_{i}(t)}^{(i)},E_{t}^{(i)})$.
For simplicity, we will replace $\mathbf{e}_{t}$ by $t^{{}^{\prime}}$, i.e.,
the last clicked item before $t$, such that we can use the following state
space mapping (Table 2). Note that, although we have multiple click states,
given $t^{{}^{\prime}}$ there is still only one click state.

State | $t^{{}^{\prime}}$ | $E_{t}^{(i)}$ | $R_{r_{i}(t)}^{(i)}$ | $y_{t}^{(i)}$
---|---|---|---|---
$0$ | $0$ | $0$ | $0$ | $0$
$1$ | $0$ | $1$ | $0$ | $0$
$2$ | $0$ | $0$ | $1$ | $0$
$3$ $(\mathcal{C}_{t})$ | $1$ | $1$ | $1$ | $1$
$4$ | $1$ | $0$ | $0$ | $0$
$\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$
$4T+1$ | $T$ | $0$ | $0$ | $0$
$4T+2$ | $T$ | $1$ | $0$ | $0$
$4T+3$ | $T$ | $0$ | $1$ | $0$
$4T+4$ $(\mathcal{C}_{t})$ | $T$ | $1$ | $1$ | $1$
$O$ | - | - | - | -
Table 2: UBM state space mapping

The UBM transition matrix is slightly more involved than that of CZM. First,
we consider two $4\times 4$ matrices containing the probabilities of
clicking/skipping some item at position $t$ given the last click was at
position $t^{{}^{\prime}}$. The click probability matrix is given by

$M_{i,t^{{}^{\prime}}t}^{(+)}=\mathbf{1}\begin{pmatrix}0,&0,&0,&\phi^{(R)}\gamma_{t^{{}^{\prime}}t}\end{pmatrix},$
(42)

whereas the skip probability matrix is given by

$M_{i,t^{{}^{\prime}}t}^{(-)}=\mathbf{1}\begin{pmatrix}\bar{\phi}^{(R)}\bar{\gamma}_{t^{{}^{\prime}}t},&\bar{\phi}^{(R)}\gamma_{t^{{}^{\prime}}t},&\phi^{(R)}\bar{\gamma}_{t^{{}^{\prime}}t},&0\end{pmatrix}.$
(43)

Here $\bm{1}$ is a vector of ones with 4 elements. By combining these matrices
into one transition matrix, we obtain

$M_{0,t^{{}^{\prime}}t}=\begin{pmatrix}M_{i,0t}^{(-)}&M_{i,t^{{}^{\prime}}1}^{+}&\ldots&M_{i,t^{{}^{\prime}}T}^{+}&\mathbf{0}\\\
[0]&M_{i,1t}^{(-)}&\ldots&M_{i,t^{{}^{\prime}}T}^{+}&\mathbf{0}\\\
\vdots&\ddots&\ddots&\vdots&\mathbf{0}\\\
[0]&\ldots&M_{i,(T^{{}^{\prime}}-1)T}^{-}&M_{i,(T^{{}^{\prime}}-1)T}^{+}&\mathbf{0}\\\
[0]&\ldots&\ldots&&\mathbf{1}\\\ 0&\ldots&\ldots&.\ldots&0\end{pmatrix},$ (44)

with $[0]$ a $4\times 4$ matrix consisting of only zeros, and $[1]$ a $4\times
4$ matrix consisting of only ones. The vectors $\mathbf{0}$ and $\mathbf{1}$
are both vectors of 4 elements with only zeros and ones respectively.

Again, the activation matrices can be found using Expressions (27), (28), and
(41). For the activation functions, we use the same strategy as with CZM: we
present the items by their two-dimensional position vector. To model
probabilities $\gamma_{t^{{}^{\prime}}t}$ a vanilla activation function is
used.

#### Comparison of perplexity

After estimating the two models using the `gecasmo` package on a simulated
dataset, where the simulation is based on the method proposed by de Ruijt and
Bhulai [11], we obtain Figure 3. Overall, the perplexity is 1.38 and 1.77 for
CZM and UBM respectively. In this particular example, UBM seems to be biased
towards correctly predicting skips, and therefore scores badly for positions
close to 1.

0.02.55.07.510.012345678910Item positionPerplexityModelCZMUBM Figure 3:
Perplexity UBM vs CZM

##  6 Conclusion

In this paper, we presented two contributions. First, we proposed an
alternative view on estimating click models. We defined the generalized
cascade model (GCM), and showed that the expectation maximization (EM)
algorithm for GCMs is equivalent to the EM algorithm of an Input-Output Hidden
Markov Model (IO-HMM), given that we add the observed click at position $t-1$
to the covariate vector at time $t$. As a consequence, we can directly use the
EM algorithm for IO-HMMs, which provides us with an estimation procedure for
GCMs without having to derive further expressions. Since many click models,
including the User Browser Model (UBM) and Chapelle-Zang Model (CZM), can be
written as GCM, this implies that we obtain an estimation procedure for many
click models, making derivations of the E-step for specific click models
(e.g., as is done in [8]) obsolete.

Second, we introduced the `gecasmo` package, which not only includes an EM
implementation for IO-HMMs, but also takes care of the mapping from GCM to IO-
HMM. As a result, one only needs to define, for some specific GCM, some
activation matrices and activation functions, from which the IO-HMM’s
transition matrix can be determined. To provide some more clarity on how to
define such activation matrices and functions, we included an example for UBM
and CZM. Also implementation-wise the usage of IO-HMM’s EM algorithm is
convenient: where previous packages for estimating click models relied on the
user having to implement the EM updates manually, `gecasmo` only requires the
activation matrices and activation functions. Furthermore, as users can define
their activation functions as neural networks, the model contains substantial
flexibility in modeling click models.

Further research may move into several directions. First, in this paper we
mainly focused on UBM and CZM as examples, as these two click models are both
generalization of many other click models, or are used as a starting point for
more complex models. As we have seen in the UBM case, even models with a non-
first-order examination assumption can be modeled as GCM by expanding the
state space, and under small list sizes, do not suffer too much from the curse
of dimensionality. We expect that even further generalizations to UBM or CZM
can be mapped to a GCM. It would be interesting to consider to what extent
these generalizations can be modeled as GCM, and if such mapping remains
practical.

Second, we limited our scope to EM procedures, which does not imply that
alternative estimation procedures, such as variational inference or Markov
Chain Monte Carlo, could not benefit from viewing click models as GCM. On the
contrary: it would be interesting to consider whether modeling click models as
GCM, or more general as IO-HMM, is also convenient under these estimation
techniques.

Third, as discussed in Section 2, even though the usage of recurrent neural
networks have shown to outperform many probabilistic graphical models (PGM) in
terms of model perplexity, these models provide limited understanding of how
users use search engines, and such understanding is obtained post hoc. As a
result, user behavior may be misinterpreted. PGMs, on the other hand, require
the analyst to define the model beforehand, which allows the analyst to test
hypotheses on browsing behavior. What remains unknown, is to what extent using
neural networks to map contextual data to a probability over a latent variable
closes the gap in accuracy between the two types of models, without losing the
interpretability of the model.

## References

  * [1]
  * Balakrishnan and Kambhampati [2008] Raju Balakrishnan and Subbarao Kambhampati. 2008.  Optimal Ad-Ranking for Profit Maximization. In _Proceedings of the 11th International Workshop on the Web and Databases_. ACM.
  * Bengio and Frasconi [1995] Yoshua Bengio and Paolo Frasconi. 1995.  An input output HMM architecture. In _Advances in neural information processing systems (NIPS)_. 427–434.
  * Bishop [2006] Christopher M. Bishop. 2006\.  _Pattern recognition and machine learning_.  Springer.
  * Borisov et al. [2016] Alexey Borisov, Ilya Markov, Maarten De Rijke, and Pavel Serdyukov. 2016.  A neural click model for web search. In _Proceedings of the 25th International Conference on World Wide Web_. 531–541.
  * Borisov et al. [2018] Alexey Borisov, Martijn Wardenaar, Ilya Markov, and Maarten de Rijke. 2018.  A click sequence model for web search. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 45–54.
  * Chapelle and Zhang [2009] Olivier Chapelle and Ya Zhang. 2009.  A dynamic bayesian network click model for web search ranking. In _Proceedings of the 18th international conference on World wide web_. ACM, 1–10.
  * Chuklin et al. [2015] Aleksandr Chuklin, Ilya Markov, and Maarten de Rijke. 2015\.  Click models for web search.  _Synthesis Lectures on Information Concepts, Retrieval, and Services_ 7, 3 (2015), 1–115.
  * Clickmodels [[n.d.]] Clickmodels. [n.d.].  _Clickmodels Github repository_.  https://github.com/varepsilon/clickmodels, Last accessed: December, 2020.
  * Craswell et al. [2008] Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. 2008.  An experimental comparison of click position-bias models. In _Proceedings of the 2008 international conference on web search and data mining_. 87–94.
  * de Ruijt and Bhulai [2020a] Corné de Ruijt and Sandjai Bhulai. 2020a.  Detecting Users from Website Sessions: A Simulation Study. In _DATA ANALYTICS 2020, The Ninth International Conference on Data Analytics_. 35–40.
  * de Ruijt and Bhulai [2020b] Corné de Ruijt and Sandjai Bhulai. 2020b.  _GCM Github repository_.  https://github.com/cornederuijtnw/GCM, Last accessed: December, 2020\.
  * Deng et al. [2018] Weiwei Deng, Xiaoliang Ling, Yang Qi, Tunzi Tan, Eren Manavoglu, and Qi Zhang. 2018\.  Ad click prediction in sequence with long short-term memory networks: an externality-aware model. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 1065–1068.
  * Dupret and Piwowarski [2008] Georges E. Dupret and Benjamin Piwowarski. 2008.  A user browsing model to predict search engine click data from past observations. In _Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval_. ACM, 331–338.
  * Guo et al. [2009] Fan Guo, Chao Liu, and Yi Min Wang. 2009.  Efficient multiple-click models in web search. In _Proceedings of the Second ACM International Conference on Web Search and Data Mining_. 124–131.
  * Joachims et al. [2005] Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, and Geri Gay. 2005.  Accurately interpreting clickthrough data as implicit feedback. In _Proceedings of the ACM Conference on Research and Development on Information Retrieval (SIGIR)_. ACM, 154–161.
  * Liu et al. [2016] Yiqun Liu, Xiaohui Xie, Chao Wang, Jian-Yun Nie, Min Zhang, and Shaoping Ma. 2016\.  Time-aware click model.  _ACM Transactions on Information Systems (TOIS)_ 35, 3, Article 16 (2016), 24 pages.
  * Maaten and Hinton [2008] Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ 9, 86 (2008), 2579–2605.
  * Murphy and Russell [2002] Kevin P. Murphy and Stuart Russell. 2002.  _Dynamic bayesian networks: representation, inference and learning_.  Ph.D. Dissertation.
  * PyClick [[n.d.]] PyClick. [n.d.].  _PyClick Github repository_.  https://github.com/markovi/PyClick, Last accessed: December 2020\.
  * Wang et al. [2015] Chao Wang, Yiqun Liu, Meng Wang, Ke Zhou, Jian-yun Nie, and Shaoping Ma. 2015\.  Incorporating non-sequential behavior into click models. In _Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 283–292.
  * Wang et al. [2013] Hongning Wang, ChengXiang Zhai, Anlei Dong, and Yi Chang. 2013\.  Content-aware click modeling. In _Proceedings of the 22nd international conference on World Wide Web_. 1365–1376.
  * Zhang et al. [2011] Yuchen Zhang, Weizhu Chen, Dong Wang, and Qiang Yang. 2011\.  User-click modeling for understanding and predicting search-behavior. In _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 1388–1396.
  * Zhang et al. [2010] Yuchen Zhang, Dong Wang, Gang Wang, Weizhu Chen, Zhihua Zhang, Botao Hu, and Li Zhang. 2010.  Learning click models via probit bayesian inference. In _Proceedings of the 19th ACM international conference on Information and knowledge management_. ACM, 439–448.
  * Zhu et al. [2010] Zeyuan Allen Zhu, Weizhu Chen, Tom Minka, Chenguang Zhu, and Zheng Chen. 2010.  A novel click model and its applications to online advertising. In _Proceedings of the third ACM international conference on Web search and data mining_. 321–330.

##  Appendix A Overview of notation

Variable | Interpretation
---|---
$\\{1,\ldots,n\\}$ | The set of query sessions, indexed by $i$.
$\\{1,\ldots,V\\}$ | Set of all items, indexed by $v$.
$\mathcal{S}_{i}$ | Set of items in SERP corresponding to query session $i$.
$\\{1,\ldots,T\\}$ | Set of all list positions, indexed by $t$.
$\Omega$ | Set of all parameters in the GCM.
$K$ | Size of the (possibly augmented) state space.
$r_{i}(t)$ | The item in list position $v$ of query session $i$.
$\mathcal{C}_{t}$ | The click state at time $t$
$\bm{\psi}_{t}^{(i)}=(\psi_{t,1}^{(i)},\ldots,\psi_{t,P}^{(i)})$ | Vector of all latent variables at position $t$ of query session $i$,
| which determines the latent state of GCM,
| and can uniquely be mapped to $z_{t}^{(i)}$.
$\mathbf{x}_{t,p}^{(i)}=(x_{t,p,1}^{(i)},\ldots,x_{t,p,m_{p}}^{(i)})$ | Vector of covariate values for parameter $p$.
$\vartheta_{t,p}^{(i)}$ | Probability of a latent variable being one, given the previous state
$f_{\text{act}}^{p}(\cdot)$ | Activation function for paramter $p$
$\bm{\theta}_{p}$ | Weight vector for parameter $p$
$y_{t}^{(i)}$ | 1 if the item in position $t$ of SERP $i$ is clicked, 0 otherwise.
$\mathcal{P}(X)$ | The set of all parents of node $X$ in a dynamic Bayesian network.
$z_{t}^{(i)}$ | The single-dimensional discrete state,
| which uniquely corresponds to some $\bm{\psi}_{t}^{(i)}$.
$\varphi_{k^{{}^{\prime}}k,t}^{(i)}$, $M_{i,t}$ | Transition probability and transition matrix.
$\zeta_{k,t}^{(i)}$ | Probability of being in state $k$ at $(i,t)$.
$f_{y}(\cdot)$ | Emission probability of the IO-HMM.
$h_{k^{{}^{\prime}}k,t}$, $H_{i,t}$ | Expectation of the joint distribution of being in state $k$ at time $t$,
| and state $k^{{}^{\prime}}$ at time $t-1$, given all available data and
| current estimate $\hat{\Omega}$.
$c_{k^{{}^{\prime}}k,t,p}^{+}$, $c_{k^{{}^{\prime}}k,t,p}^{-}$, $I_{p,t}^{+}$, $I_{p,t}^{-}$ | Indicators of whether parameter $p$ positively ($\psi_{p}=1$) or
| negatively ($\psi_{p}=0$) influences the transition probability
| between state $k^{{}^{\prime}}$ and $k$.
$\alpha_{k,t}^{(i)}$, $A_{i}$ | Forward probabilities in the forward-backward equations.
$\beta_{k,t}^{(i)}$, $B_{i}$ | Backward probabilities in the forward-backward equations.
$\delta_{kt}^{(i)}$, $D_{i}$ | Indicator of whether state $k$ is a click state
$R_{v}^{(i)}$, $\phi_{v,i}^{(R)}$ | Indicator (probability) whether the user (of query session $i$)
| finds item $v$ attractive (also referred to as ‘relevance’ in
| the click literature).
$S_{v}^{(i)}$, $\phi_{v,i}^{(S)}$ | Indicator whether the user (of query session $i$)
| is satisfied with item $v$ after a click.
$E_{i,t}$ | Indicator whether the item at position $t$ is evaluated.
$\gamma_{i}$ | Search continuation probability, has different sub/superscripts
| based on the underlying click model.
Table 3: Notation overview

##  Appendix B Notes on vector notation

In the following we will elaborate shortly on the vectorization of Section
4.3, in particular the expressions in Algorithm 1. From Bishop [4, pp.
618-625] we find (using our own notation and ignoring superscript $i$)

$\alpha_{k,t}=\mathbb{P}(y_{t}|z_{t}=k)\sum_{k^{{}^{\prime}}=1}^{K}\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t})\alpha_{k^{{}^{\prime}},t-1},$
(45)
$\beta_{k,t}=\sum_{k^{{}^{\prime}}=1}\mathbb{P}(y_{t+1}|z_{t+1}=k^{{}^{\prime}})\varphi_{kk^{{}^{\prime}}}(\mathbf{x}_{t+1})\beta_{k^{{}^{\prime}},t+1},$
(46)
$h_{k^{{}^{\prime}}k,t}=\frac{\alpha_{k^{{}^{\prime}},t-1}f_{y}(y_{t}|z_{t}=k)\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t})\beta_{k,t}}{\sum_{l=1}^{K}\alpha_{l,T}}.$
(47)

Writing out $\alpha_{k,t}$ for $t>0$ gives

$\displaystyle\alpha_{k,t}$
$\displaystyle=\mathbb{P}(y_{t}|z_{t}=k)\sum_{k^{{}^{\prime}}=1}^{K}\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t})\alpha_{k^{{}^{\prime}},t-1}$
(48)
$\displaystyle=y_{t}\delta_{k,t}\sum_{k^{{}^{\prime}}=1}^{K}\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t})\alpha_{k^{{}^{\prime}},t-1}+(1-y_{t})(1-\delta_{k,t})\sum_{k^{{}^{\prime}}=1}^{K}\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t})\alpha_{k^{{}^{\prime}},t-1},$

which in vector notation becomes

$A_{1:K,t}=y_{t}\left[D_{1:K,t}\odot\left(M_{t}^{\top}A_{1:K,t-1}\right)\right]+\left(1-y_{t}\right)\left[\left(1-D_{1:K,t}\right)\odot\left(M_{t}A_{1:K,t-1}\right)\right],$
(49)

where $\odot$ is the element-wise product. For $t=0$, using the original
definition, we obtain:

$\alpha_{k,0}=\mathbb{P}(y_{0},z_{0}=t)=\delta_{0k},$ (50)

as we assume the item at position $t=0$ is clicked.

Similar, for $\beta_{k,t}$, $t<T$

$\displaystyle\beta_{k,t}$
$\displaystyle=\sum_{k^{{}^{\prime}}=1}\mathbb{P}(y_{t+1}|z_{t+1}=k^{{}^{\prime}})\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t+1})\beta_{k^{{}^{\prime}},t+1}$
(51)
$\displaystyle=\sum_{k^{{}^{\prime}}=1}^{K}\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t+1})\beta_{k^{{}^{\prime}},t+1}y_{t+1}f_{y}(1|z_{t+1=k})+\varphi_{k^{{}^{\prime}}k}(\mathbf{x}_{t+1})\beta_{k^{{}^{\prime}},t+1}(1-y_{t+1})f_{y}(0|z_{t+1=k}),$

which, again in vector notation, becomes

$\displaystyle B_{1:K,t}$
$\displaystyle=M_{t+1}^{\top}\left[y_{t+1}\left(B_{1:K,t+1}\odot
D_{1:K,t+1}\right)+(1-y_{t+1})\left(B_{1:K,t+1}\odot\left(1-D_{1:K,t+1}\right)\right)\right]$
(52) $\displaystyle=M_{t+1}^{\top}\Lambda_{t+1},$

with

$\Lambda_{t}=y_{t}\left(B_{1:K,t}\odot
D_{1:K,t}\right)+(1-y_{t})\left(B_{1:K,t}\odot\left(1-D_{1:K,t}\right)\right).$
(53)

We take $\beta_{k,T}=1$ for all $k=1,\ldots,K$.

Last, using (47), and the previously found expressions, we obtain:

$H_{t}=\left[\frac{\Lambda_{t}}{\sum_{k=1}^{K}\alpha_{k,T}}A_{1:K,t-1}^{\top}\right]\odot
M_{t}^{\top}$ (54)

##  Appendix C Notes on click simulation

Simulation parameters used in Section 5. For brevity we only consider
simulation parameters which were not obtained from the literature in [11].
Since the simulation is described in more depth in [11], we will only provide
a brief explanation of each variable here.

  * •

Items, number of items $V$.

  * •

Users, total number of users, who may have multiple query sessions.

  * •

Warm-up sessions, number of sessions used to estimate the overall item
popularity. During the simulation, items are ordered at random, with the item
order proportional to this overall item popularity.

  * •

List size, number of items in a SERP, which we denoted by $T$.

  * •

User distance sensitivity, a parameter regulating user attraction to nearby
items.

  * •

Attraction salience, parameter to regulate the attraction salience.

  * •

Satisfaction salience, parameter to regulate the satisfaction salience.

  * •

Model lifetime phases geometric parameter, the number of query sessions a
single user generates is regulated by a sampled total user lifetime, and
sampled times between two sessions (which in [11] is called absence time).
I.e., the number of query sessions one user generates is determined by whether
the sum of absence times fits the user life time. This geometric parameters
regulates the sampled user life time.

Parameter | Value
---|---
Items | 100
Users | 20000
Warm-up sessions | 100
List size | 10
User distance sensitivity | 1
Attraction salience | 5
Satisfaction salience | 5
Model lifetime phases geometric parameter | 0.5
Continuation probability | 0.9
Table 4: Simulation parameters