Click Models: Cascade, DBN and UBM

A result at rank 3 is clicked in 9 percent of the 1,000 sessions for its query. Is it a weak result? Suppose that in 400 of those sessions the user clicked rank 1 or 2 and never came back. Then the result was plausibly looked at in only 600 sessions, and its click rate among users who saw it is \(90/600 = 15\) percent. The raw click-through rate is mixing relevance with whatever happened above it on the page.

The neighbouring concept Position Bias and the Examination Hypothesis models examination as a function of rank alone. Click models write down a probabilistic story of how a user moves down the page, so examination depends on what happened above. Fit the story to logs, and relevance falls out as a latent parameter.

The cascade model

Craswell and colleagues perturbed the rankings of a major search engine and measured how clicks moved. Simple position models, where some users click rank 1 regardless or attention decays with rank, did not explain the data well. The best explanation for position bias at the top ranks was a cascade: users scan from the top, click the first result that looks worthwhile, and leave (Craswell, Zoeter, Taylor & Ramsey, 2008, An Experimental Comparison of Click Position-Bias Models, WSDM).

Write \(E_r\), \(A_r\) and \(C_r\) for the binary events that the result at rank \(r\) is examined, is attractive, and is clicked, and \(\alpha_{uq}\) for the attractiveness of document \(u\) for query \(q\):

and examination stops after a click. Estimation is easy because examination is observed: everything down to the first click was examined, which is exactly the opening estimate. The price is one click per session; any multi-click session has probability zero.

The dynamic Bayesian network model

A click is not a verdict: a misleading snippet attracts clicks and the user comes straight back. Chapelle and Zhang separated the two by adding a satisfaction event \(S_r\) after a click and a continuation probability \(\gamma\) (Chapelle & Zhang, 2009, A Dynamic Bayesian Network Click Model for Web Search Ranking, WWW):

Relevance is then the probability of satisfaction given examination, \(R_{uq} = \alpha_{uq}\,\sigma_{uq}\), which the original paper used both directly as a ranking function and as a feature for a learned ranker (Chuklin, Markov & de Rijke, 2015, Click Models for Web Search, Morgan & Claypool).

Fixing \(\gamma = 1\) gives the simplified DBN, where the last click in a session is taken as the satisfied one and parameters have closed-form estimates: \(\alpha_{uq}\) is clicks on \(u\) divided by sessions where \(u\) appeared at or above the last-clicked rank, and \(\sigma_{uq}\) is the fraction of clicks on \(u\) that were the session's last click. Set every \(\sigma_{uq} = 1\) and the simplified DBN collapses back into the cascade model.

The separation is the point. A clickbait result with \(\alpha = 0.25\) whose clicks end the session only a quarter of the time has \(R = 0.0625\). A plainer result with \(\alpha = 0.15\) that satisfies 80 percent of the time has \(R = 0.12\), nearly double, despite fewer clicks.

The user browsing model

Dupret and Piwowarski kept the examination hypothesis but let examination depend on both the rank \(r\) and the distance to the previous click, allowing several clicks and non-linear scanning (Dupret & Piwowarski, 2008, A User Browsing Model to Predict Search Engine Click Data from Past Observations, SIGIR). In the rank-of-last-click form,

where \(r'\) is the rank of the most recent click above \(r\), or 0 if none. Examination is no longer observed, so the \(\gamma\) grid and the \(\alpha\) values are fitted jointly by expectation-maximisation. Their fitted model showed attention to new results falling as the distance from the last click grew, with significantly lower perplexity than the cascade model.

Which model is best depends on who is asking

Grotov and colleagues compared the major models on 32 million sessions from the 2011 Yandex relevance prediction data and found no single winner. DBN and simplified DBN were best by perplexity, UBM by log-likelihood, CCM best for ranking documents, and simple count-based models were fastest and sometimes beat complex ones; relative performance also shifted with query frequency and click entropy (Grotov et al., 2015, A Comparative Study of Click Models for Web Search, CLEF). The model that best simulates users need not give the best relevance labels.

The ideas outlived the models: Expected Reciprocal Rank, the metric that ranked entries in the Yahoo! Learning to Rank Challenge, is built on the cascade user model.

When it breaks

Parameters are per query-document pair. Estimates need many sessions of the same query showing the document. Head queries get good estimates; the long tail of distinct queries gets none.

Satisfaction is inferred from session endings. In the simplified DBN, the last click is treated as satisfying. A user who gives up in frustration looks identical to a satisfied one, and an answer shown directly on the results page produces satisfied sessions with no clicks at all.

Top-to-bottom scanning is an assumption about layout. Grids, carousels, ads, answer boxes and mobile infinite scroll break the linear rank order these models are built on.

Identifiability needs variation. If a document always appears at the same rank, UBM cannot separate its attractiveness from that rank's examination probability, and EM returns one of many equally good splits. The interventions and harvested ranking changes used for propensity estimation are what make the parameters meaningful.