One of the ways IR systems help searchers is by predicting or assuming what could be useful for their information needs based on analyzing information objects (documents, queries) and finding other related objects that may be relevant. Such approaches often ignore the underlying search process of information seeking, thus forgoing opportunities for making process-based recommendations. To overcome this limitation, we are proposing a new approach that analyzes a searcher's current processes to forecast his likelihood of achieving a certain level of success in the future. Specifically, we propose a machine-learning based method to dynamically evaluate and predict search performance several time-steps ahead at each given time point of the search process during an exploratory search task. Our prediction method uses a collection of features extracted solely from the search process such as dwell time, query entropy and relevance judgment in order to evaluate whether it will lead to low or high performance in the future. Experiments that simulate the effects of switching search paths show a significant number of subpar search processes improving after the recommended switch. In effect, the work reported here provides a new framework for evaluating search processes and predicting search performance. Importantly, this approach is based on user processes, and independent of any IR system allowing for wider applicability that ranges from searching to recommendations.
H.3: INFORMATION STORAGE AND RETRIEVAL H.3.3: Information Search and Retrieval: Search process; H.3: INFORMATION STORAGE AND RETRIEVAL H.3.4: Systems and Software: Performance evaluation (efficiency and effectiveness) Presented at EuroHCIR2013.
Copyright © 2013 for the individual papers by the papers’ authors. Copying permitted only for private and academic purposes. This volume is published and copyrighted by its editors. 1
IR evaluations are often concerned with explaining factors
relating to user or system performance after the search and
retrieval are conducted [
The underlying rational processes involved in information
search are reflected in the actions users make while
searching. These actions include entering search queries,
skimming the results, as well as selecting and collecting
useful information [
A searcher’s performance is a function of these actions
performed during a search episode [
With these assumptions, we propose to quantify a search process using various user actions, and use it for user performance (henceforth, ‘search performance’ or ‘performance’) prediction as well as search process recommendations. 2
Past research on predictive models that relates to the approach we describe in this paper can be grouped into two main categories: (1) behavioral studies and (2) IR approaches. In both cases; however, the focus has been on end products instead of in the process required to produce them.
As far as the behavioral studies go, research has been conducted
to explore users models that help anticipating specific aspects of
the search process. One goal in this context has been the
determination of whether a search process will be completed in a
single or multiple sessions. For example, Agichtein et al. [
There have been also attempts to understand past users'
behaviors in order to predict future ones in similar conditions.
For example, Adar et al. [
From an IR perspective, Radinski et al. [
In a similar track, several works have been conducted on query
performance prediction, focusing on developing techniques that
help IR system to anticipate whether a query will be effective or
not to provide results that satisfy users’ needs [
Unlike previous works in IR, we are not proposing to use time series analyses or seasonal components of historic data. Instead, we investigate predictive models based on machine learning (ML) techniques; namely: SVM, logistic regression, and Naïve Bayes which are trained over a set of features such as time, number of queries, and page dwell time. In contrast to most IR evaluations, our method focuses on user-processes. Also, unlike most recommender systems, our approach could output alternative strategies instead of similar/relevant products to help the searcher. In essence, the work reported here takes several lessons from tradition IR evaluations, recommender system designs, and weather/stock forecasting to come up with a new approach for evaluating and predicting search performance. In the next section we provide a detailed description of our method, feature selection, and the measures we used in order to create ML-based predictive models.
In order to analyze the search processes followed by different
users/teams, we assume that the underlying dynamics of the
search processes are expressed by a collection of activities that
take place from the beginning to the end of the search processes.
The first part of our method is a feature extraction step in which
we extract a wide array of features relating to webpages, queries
and snippets saved from the search processes for each unit of
time t. This step is performed in order to evaluate how well we
could use those features to capture the underlying dynamics
which would lead to recognizing whether a search process is
going to lead to high or low performance in the future time steps
at t+n (n=1,2,….,N), where N is the furthest time step.
The decision to include or exclude a feature was based on
literature (e.g., [
Total coverage (u,t): The total number of distinct
Webpages visited by a user (u) up to time t. This feature
captures the Webpage based activity performed by a user
and provides a measure to see how much distinct
information has been found by the user up to this time.
Useful coverage (u,t): The total number of distinct
webpages in which a user spent at least 30 seconds, up to
time t. This measure evaluates out of the total pages he/she
has visited how many of them were useful in finding
relevant information leading to satisfaction with their
context in completing the exploratory task [
Number of saved snippets (u,t): Total number of snippets saved by user u up to time t. This measures the amount of information that the user thought that might be relevant in the future to complete the task and needed to be remembered. In other words, this feature is an indication of explicit relevance judgments made by the user.
Length of Query (u,q,t): Length of each query(q) executed by a user u based on the character count of the query up to time t. This feature captures how the user imposed the • • queries and how long they were at different times of the search process.
Number of tokens in each query (u,q,t): This is the count of tokens/words in each query(q) executed by user u up to time t. This query based measure takes into account how specific a user was in defining the query. By inspecting the datasets, we realized that queries with a less number of tokens tend to get general results. On the other hand, composed queries with multiple terms are related to more specific searchers. We also observed that typically the users started with general queries with few words at the beginning of the search process but then went into more detailed queries to find more specific information later. For all these reasons, we found it to be useful to capture the number of token used in a query.
Query entropy (u,q,t): This measures the information
content in a given query (q), by finding the expected value
of information contained in a query. We used the widely
recognized notion of Shannon entropy [
The method used to assess the search performance of a user is
described below. We define a measure called Efficiency (u,t), for
each user u up to time t in order to predict whether a given
search process is going to yield in high/low performance in the
future We first define Effectiveness of user u up to time t as the
ratio of useful coverage and total coverage (both defined
earlier). A similar measure was used in [
Effectiveness(u,t) =
(1) (2) We then calculated Efficiency as defined in Equation 2.
Efficiency(u,t) =
In other words, Efficiency is defined as the Effectiveness obtained per query, or how effective a query is in terms of achieving a certain level of useful coverage.
The performance for each user u at each time t was classified in to the two classes; high performance and low performance based on the following criteria: Class = { high ;if low ;else
Efficiency(u, t) ≥ Efficiency(u, t) (3) Using various user studies data available to us, we constructed feature matrices which consist of all aforementioned features for each minute of time t for all the users in each dataset, and converted in to a long vector of features which we fed as the input to the classification models used.1 The class labels were generated as high/low performance at minute t+n based on the 1 In the interest of space and scope of work here, details of these experiments have been omitted, but will be available for discussion at the workshop. above mentioned criteria and threshold and used as the output class labels to be used in the n-step ahead prediction model. If a class label at n-step ahead was correctly predicted based on the features extracted up to time t from the classification model it was considered as correctly classified and if not as misclassified.
In order to evaluate whether users who are predicted to perform at low performance in the future based on the current search process, could benefit from this analysis to improve their search process, we conducted some simple simulation analysis. We considered the individual user search processes as a collection of search paths, where each search path is defined as the search process from the time a user issued a query up to the time user issued another quite different query. This was found out using generalized Levenshtein (edit) distance, which is a commonly used distance metric for measuring the distance between two character sequences. If the Levenshtein (edit) distance between two subsequent queries were greater than 2 (assuming less than 2 was when there were changes in the queries due to simple spelling mistakes or refining of the query), we considered the search process from the former query to the next query as a single search path.
Following this method, we found the first search path of each user and based on the features extracted up to the end of the first search path, and based on the classification model learnt from that corresponding n-step ahead prediction we predicted whether the user is going to have low/high performance at the end of the session. If the user was going to have low performance, then out of the users who predicted to have high performance, we looked at which high performing user has the lowest Levenshtein (edit) distance between the queries issued by low performing user within the first search path and considered it as a pair of users, whom we are going to use in the simulation. Then, for each low performing user and high performing user that was matched, we switched the search process of low performing user at the end of the first search path with the high performing user’s search path up to t=T minutes, where T is the total number of minutes for a session. Then we evaluated by switching the search process early during the overall process whether it would benefit each low performing user to improve their performance. We found that we were able to move most of the underperforming search processes to higher performance by early detection and switching, while keeping the higher performing processes unharmed.
These simulations provide verification that by realizing early during the search process whether a user is going to perform well or not, one could recommend better search processes/strategies for that user which would lead to uplifting the search performance of a previously destined to low performing user.
When it comes to prediction, information retrieval and filtering systems are primarily focused on objects while assessing what and if something could help the users. These approaches are often system-dependent even though the process of information seeking is usually user-specific. Personalization and recommendations are frequently exercised as methods to address user-specific IR and filtering, but still limited to comparing and recommending objects, not focusing on underlying IR processes that are carried out by the searchers. We presented a new approach to address these shortcomings. We began by asking whether we could model a user’s search process based on the actions he/she is performing during an exploratory search task and forecast how well that process will do in the future. This was based on a realization that an information seeker’s search goal/task can be mapped out as a series of actions, and that a sequence of actions or choices the searcher makes, and especially the search path he/she takes, affects how well he/she will do. Thus, in contrast to approaches that measure the goodness of search products (e.g., documents, queries) as a way to evaluate the overall search effectiveness, we measured the likelihood of an existing search process to produce good results. Here we presented simulations to demonstrate what could happen if one can make process-based predictions, but one could develop an actual recommender system using the proposed method. Another potential application of such prediction-based method would be to use such approach in IR systems to provide the awareness to users how their future performance will be based on the current/past search process. The system could identify that a user will have low performance if, he continues this manner at an early stage of the process, and what could be done to provide suggestions to improve overall performance. Given that the proposed technique is independent of any specific kind of system, and solely focused on user-based processes, it will presumably be easy to apply it to a variety of IR systems and situations irrespective of retrieval, ranking, or recommendation algorithms. Finally, while we have used datasets borrowed from previous user studies, one could easily apply the proposed method to Web logs, TREC data, and other forms of datasets with various user actions recorded over time.
The work reported here is supported by The Institute of Museum and Library Services (IMLS) Cyber Synergy project as well as IMLS grant # RE-04-12-0105-12. The author is also grateful to his PhD students Chathra Hendahewa and Roberto GonzalezIbanez for their valuable contributions to this work. 7 in collaborative IR systems. In Proceedings of the 75th Annual Meeting of the Association for Information Science and Technology (ASIS&T). Baltimore, MD, USA.