Mobile Query Recommendation via Tensor Function Learning

Zhou Zhao, Ruihua Song, Xing Xie, Xiaofei He, Yueting Zhuang

Presented at IJCAI 2015, this research introduces a novel approach to mobile search by transitioning from reactive query refinement to proactive intent prediction. By leveraging tensor algebra and contextual side information—such as location tags and user device metadata—the authors provide an efficient and accurate framework for suggesting search queries before a user finishes typing.

Mobile search environments differ significantly from desktop settings. Smartphone typing is inherently slower, averaging 21 words per minute compared to over 60 on a PC. This makes query auto-completion and recommendation critical for user experience. However, mobile devices provide a unique advantage: context.

Traditional recommendation systems often suffer from data sparsity; most users have not searched for most items at most locations. Standard tensor completion methods, which treat the user-location-query space as a massive 3D matrix, are computationally expensive and often fail to capture the underlying semantics of a location or query. This paper addresses these challenges by using external knowledge to "fill in the blanks" in sparse data environments.

Methodology: Tensor Function Learning (TFL)

The researchers propose Tensor Function Learning (TFL) to model the relationships between users, locations, and query intents as a 3-way tensor: User $\times$ Location $\times$ Query.

The TFL framework mapping side information (U, Q, R) to query data (Y) via parameter tensor (W).

Key Innovations:

  1. Side Information Integration: Instead of relying solely on raw IDs, the model extracts features:
  2. Queries ($Q$): Classification labels (e.g., "business," "travel") derived from clicked webpages.
  3. Locations ($R$): Annotated tags (e.g., "food," "hotpot") from Dianping (a Chinese Yelp-like service).
  4. Users ($U$): Metadata such as phone brand and operating system.
  5. Parameterization: Rather than completing the massive, sparse data tensor directly, TFL learns a smaller parameter tensor ($W$). This $W$ acts as a bridge mapping side information features to observed search behaviors. The size of $W$ depends on the number of features rather than the total number of users or locations, drastically reducing the computational burden.
  6. Optimization via ADMM: The problem is formulated as a convex optimization task using nuclear norm minimization to ensure a low-rank (simple) model. This is solved using the Alternating Direction Method of Multipliers (ADMM), an efficient iterative algorithm.

Experimental Setup and Datasets

The study utilized real-world data from Beijing:

  • Bing Search Logs: Data from January to June 2014, encompassing 3,000 users, 1,000 unique queries, and over 114,000 relations.
  • Dianping API: Used to collect 105,271 location entities and their associated tags to provide geographic context.
  • Location Categories: 30 distinct categories (e.g., "shopping," "education") were used to maintain context while protecting user privacy.

Results and Performance

TFL was compared against five state-of-the-art algorithms, including Canonical Polyadic (CP) and Tucker decompositions.

  • Accuracy: TFL consistently achieved the lowest Root Mean Square Error (RMSE). With 90% training data, TFL reached an RMSE of 0.1104, significantly outperforming the next best method, UCLAF (0.1349).
  • Robustness: Even with only 50% training data, TFL maintained a strong lead, proving that side information effectively mitigates the "cold start" problem.
  • Convergence: The model demonstrates reliable convergence, typically within 500 iterations, making it viable for real-world deployment.
Convergence of the objective function over iterations using the ADMM algorithm.

Conclusion and Future Directions

By parameterizing the recommendation problem through feature dimensions, TFL overcomes the scalability and sparsity issues of traditional tensor methods. However, the current model assumes linear relationships and does not explicitly account for temporal dynamics (e.g., time of day). Future work may explore kernel tensor functions to capture non-linear relationships and integrate temporal features to further refine mobile search intent prediction.

Summary updated

Abstract

With the prevalence of mobile search nowadays, the benefits of mobile query recommendation are well recognized, which provide formulated queries sticking to users' search intent. In this paper, we introduce the problem of query recommendation on mobile devices and model the user-location-query relations with a tensor representation. Unlike previous studies based on tensor decomposition, we study this problem via tensor function learning. That is, we learn the tensor function from the side information of users, locations and queries, and then predict users' search intent. We develop an efficient alternating direction method of multipliers (ADMM) scheme to solve the introduced problem. We empirically evaluate our approach based on the mobile query dataset from Bing search engine in the city of Beijing, China, and show that our method can outperform several state-of-the-art approaches.
BibTeX
@inproceedings{zhao2015mobile,
  author = {Zhou Zhao and Ruihua Song and Xing Xie and Xiaofei He and Yueting Zhuang},
  title = {{Mobile Query Recommendation via Tensor Function Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure