Check in and we’ll show you the right information card

Figure 1: Different places imply different information needs.

Nowadays, everybody’s cruising the streets with a phone in his/her hand and time to time they send their Pokémon game on the background and search for something useful. They search because they want to satisfy their information needs. This hunger for information is often triggered by person’s context [1]. For instance, waiting on a bus station makes you wonder when the next bus arrives, before going to the ZOO with your whole family you’re likely to search for family ticket prices, and so on. We wrote a paper where we try to predict what are your information needs given your current activity. In this post, I describe how we go about it.

📎 Anticipating Information Needs Based on Check-in Activity, J. Benetka, K. Balog, and K. Nørvåg. In: 10th ACM International Conference on Web Search and Data Mining (WSDM ’17), February 2017.

Check-ins

So what is the ‘check-in‘ in the title? Well, inferring someone’s activity is not an easy task. People don’t like to be spied on, however, sometimes they give away information that can help us. When using services such as Foursquare or Yelp, users can mark their position (they can ‘check in’) to let the world know where they are. Usually they do so at some sort of significant places which are called points of interest (POIs). Services such as Foursquare or Yelp are build around this idea and they keep details about the places including their classification into categories (e.g., restaurant, mountain, church). These categories can be seen as activities and we simply use them interchangeably. Check the Table 1 to see how this makes sense.

Table 1: POI category is a good indicator of related activity.

Regarding the data source, we work with a dataset containing 33 million Foursquare check-ins, which was prepared by Dingqi Yang and you can get it here.

Information needs & activities

The crucial task is to identify which information is relevant to people given their activity. Formally, we need to obtain a set of information needs, $$I$$, and estimate the probability $$P(i|a)$$ of each information need $$i \in I$$, which expresses its relevance with respect to a given activity $$a \in A$$. Without access to a commercial mobile search log, we can turn our attention to Google and try to leverage the query suggestion system. We make two assumptions here:

• people articulate their information need with a query that is likely to produce search results addressing the need,
• query completions suggested by the search engine represent the most popular queries for a given prefix.

With that in mind, we collect query completions for a sample of POIs in each category and aggregate them on the category level. Recall, that the categories represent activities, hence, we obtain a set of query completions per activity. To make sure we get results for sufficiently unambiguous POIs, we add the city name to the query before submitting (see Figure 2).

Figure 2: Google query completion used for extraction of information needs.

After several steps of data cleansing (number/date removal, etc.), we arrive at 66 thousand query completions distributed among 287 second-level and 9 top-level categories. The information needs, as obtained from the query suggestions, are typically expressed in a variety of ways, even when they have the same meaning. To normalize the terms, we cluster synonyms and label each cluster with a canonical name that stands for all the variations. In the table below, you can see some example clusters.

Table 2: Normalized information needs and their synonyms.

Determining relevance

At this moment, we have a bag of normalized information needs divided into categories and we want to establish their relevance. We define the ranking by their relative frequency, because, intuitively, the more often people search for a query, the more relevant information need it represents. Formally, let $$n(i,a)$$ denote the number of times information need $$i$$ appears for activity $$a$$. We then set $$P(i|a) = \frac{n(i,a)}{\sum_{i’ \in I}n(i’,a)},$$ where $$I$$ is the set of distinct information needs.

Figure 3: Ranking of information needs at train station.

Not surprisingly, some categories have a larger portion of domain-specific information needs, such as the ‘College & University’ category with terms like university info, campus or study programme. On the other hand, some information needs are almost universally relevant: address, parking, or operation hours.

Our evaluation is based on a set of crowdsourcing experiments, aimed at measuring recall of the extracted information needs (R@10 ~ 0.25) and their ranking with respect to relevance (NDCG@3 ~ 0.46). For full details on this part, I’ll kindly point the reader to the paper or the page with resources.

Temporal dynamics of information needs

Figure 4: Crowdsourcing experiment

Arguably, time influences our information needs on a large scale. In the paper, we investigate whether information needs vary even throughout the course of an activity. First, we split the temporal neighborhood of an activity into three periods: before, during and after the activity takes place. Second, we introduce the concept of temporal scope, which is defined as the probability of an information need being relevant for a given activity during a certain period in time. To collect the necessary data, we asked participants of a crowdsourcing experiment to fill out a questionnaire, which is depicted in Figure 4.

Findings

After aggregation of the experimental data, we indeed observe very different temporal patterns for different information needs (Figure 5). Some information needs are clearly dominant in one of the periods, for example, ‘location‘ should be addressed before an activity takes place. Other information needs are spread across multiple periods (‘offers‘ within Food-related activities) or there is no preference at all (‘accommodation‘ within Nightlife activities).

Figure 5: Temporal scope of various information needs under various categories.

Moreover, we find that some information needs behave elseways under various activities. Take ‘reviews‘, for instance (Figure 6). People search for reviews of places before going for a night out, they check reviews before and after doing some outdoors activity and when the activity is related to art and entertainment, they check reviews equally likely before, during and after the activity. The fact that this happens suggests the importance of the context even for timing of information delivery.

Figure 6: Temporal scope of ‘reviews’ information need in different categories.

Prediction

Anticipating user’s future information needs.

So far, we have identified information needs related to a given activity and studied how their relevance changes over the course of the activity. Using this knowledge, we can say which information need the user most likely has given we know his current activity and the time period.
A more challenging goal, however, is to anticipate which information he will need next. For that, we need to infer user’s follow-up activity. There is no way to guess the next activity with 100% certainty, nevertheless, for each activity, we can compute how likely it is to come next. Using the Dingqi Yang’s dataset with check-ins ordered in chronological manner, the transition probability between two activities $$a_i$$ and $$a_j$$ is given as $$P(a_j|a_i) = \frac{n(a_i \rightarrow a_j)}{\sum_k n(a_i \rightarrow a_k)}$$. Having this last component in place, we have all we need to build the following model:

$$P_{M2}(i|a_{last}) = \gamma P(i|a_{last}) + (1-\gamma)\sum_{i \in I} P(i|a_{next})P(a_{next}|a_{last})$$

The model (M2) is a linear mixture of two components, corresponding to the probability of the information need given the last activity ($$P(i|a_{last})$$) and the upcoming activity ($$\sum_{i \in I} P(i|a_{next})P(a_{next}|a_{last})$$), where $$i$$ is information need, $$a_{last}$$ is user’s last observed activity and $$a_{next}$$ is user’s next activity. The interpolation parameter $$\gamma \in [0, 1]$$ expresses the influence of the last activity, i.e., the extent to which we want to address post information needs of the last activity. We set the parameter $$\gamma$$ according to the average post-relevance of information needs across all activities.

References

[1] A diary study of mobile information needs, T. Sohn, et al. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2008.