TL;DR
This paper introduces a Partially Observable Markov (POM) model to infer hidden user behaviors during web search, such as reading and skipping search results, which are not directly recorded in search logs. By adapting Viterbi algorithms for training and decoding, they demonstrate that search logs contain rich, albeit indirect, information about user interactions, validated against eye-tracking studies.
What Problem Does This Paper Address?
Web search engines collect vast amounts of data on user interactions, primarily through clicks and query refinements. However, these logs don't capture crucial behaviors like users reading and then skipping search results without clicking. This "unobservable" behavior is a significant gap in understanding user intent and can lead to biases, like the "positional bias" (where top results get more clicks regardless of relevance), when trying to infer relevance from click data alone. Existing methods often rely on simplifying assumptions (like the "depth-first" model) that don't fully reflect real-world user behavior, especially given the complexity of modern search result pages (SERPs) with ads, suggestions, and varying layouts. The paper aims to bridge this gap by developing a model that can infer these hidden browsing patterns from observable log data.
Methods
The core of the paper is the Partially Observable Markov (POM) model. Unlike standard Hidden Markov Models (HMMs), POMs allow for state transitions that don't necessarily emit observable events. This is crucial for modeling the "view and skip" behavior.
Key methodological contributions include:
- Segmental Decoding: A technique adapted from speech recognition to find the most likely sequence of hidden user actions (the "scanpath") given an observed sequence of events (clicks, hovers, etc.). This is necessary because the length of the hidden sequence is unknown.
- Segmental Viterbi Training: A novel algorithm for training the POM model parameters. It combines segmental decoding with Viterbi approximation to efficiently estimate the model parameters from search log data, overcoming the computational challenges of dealing with an infinite number of possible hidden sequences.
- Model Assumptions: The authors make two key assumptions to simplify the POM:
- Engagement (skip/click) depends only on the current viewed item.
- The decision to view the next item is independent of whether the previous item was skipped or engaged with.
Datasets
The paper uses search log data collected from a commercial web search service deployed in the EN-US market. The SERP layout is described as a two-column format with core search results (CR) on the left and query suggestions (QS) on the right, with advertisements (TA, SA) also present. The logs captured various events including clicks, hovers, query reformulations, and page navigation. The authors also compare their findings with published eye-tracking studies, which serve as a form of validation rather than a dataset for training.
Key Insights and Ideas
- Search logs are richer than they appear: Even without direct observation, search logs contain enough subtle cues to infer unobservable behaviors like "view and skip."
- The "depth-first" model is an oversimplification: Real user browsing patterns are more complex. Users don't always scan sequentially; they might skip results, look back, or reformulate queries frequently, especially at the top of the SERP.
- Positional bias is real and complex: Both POM inference and eye-tracking studies confirm a strong positional bias in viewing and clicking. However, the POM model reveals nuances, like the impact of advertisements and query reformulation, that can explain discrepancies in previous eye-tracking findings.
- The scroll line matters: The point on the SERP where users typically scroll significantly impacts their browsing behavior, with a more sequential "depth-first" pattern observed below the scroll line.
- User behavior is not uniform: The paper hints that factors like query type and user demographics (gender) likely influence behavior, suggesting future work on mixture models.
Key Results
- The POM model successfully infers hidden browsing patterns that closely align with findings from eye-tracking studies, validating its ability to uncover unobservable user actions.
- POM analysis suggests that users largely ignore top advertisements (TA) and query suggestions (QS) upon page load, directly proceeding to core search results (CR).
- Transition probabilities from the POM model show that users are not strictly following a depth-first model at the top of the SERP, with a significant portion of transitions leading to query reformulation.
- The POM model infers backward viewing probabilities that are position-dependent, with users tending to look back one result or to the first result, a detail not quantitatively reported in prior eye-tracking literature.
- The POM inferred view rates closely resemble eye-tracking data, showing strong positional bias, but also highlight differences due to factors like query reformulation frequency in real-world logs versus controlled lab settings.
Limitations and Future Work
- First-order Markov assumption: The current model assumes a first-order Markov chain, which might be too simplistic for complex temporal dependencies.
- Single parameter set: The model uses a single set of probabilities to represent average user behavior, neglecting variations across different user groups (e.g., gender) or query types (informational vs. transactional).
- Simple skip probability: The model uses a basic skip probability, not fully differentiating between the relevance of snippets and landing pages.
Future work suggested includes:
- Relaxing the first-order Markov assumption using techniques like variable N-grams or infinite HMMs.
- Developing mixture models to capture behavioral variations across different user segments and query types.
- Incorporating more sophisticated models for click behavior that distinguish between snippet and landing page relevance.
Summary updated