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.
The Challenge of Mobile Search
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.
Key Innovations:
- Side Information Integration: Instead of relying solely on raw IDs, the model extracts features:
- Queries ($Q$): Classification labels (e.g., "business," "travel") derived from clicked webpages.
- Locations ($R$): Annotated tags (e.g., "food," "hotpot") from Dianping (a Chinese Yelp-like service).
- Users ($U$): Metadata such as phone brand and operating system.
- 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.
- 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.
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