Mobile Query Recommendation via Tensor Function Learning

1 Introduction

Search marketing is witnessing a dramatic change in the recent years where mobile search has a tremendous growth in the market share. As the sales of smartphones and tablets continue to rise, there's no end in sight to the popularity of mobile search. The benefits of query recommendation in mobile environment are well recognized, which provide formulated queries sticking to users' search intent.

Query recommendation is considered an important component in enhancing keyword-based queries in search engines. The existing approaches [Guo et al., 2010; Feild and Allan, 2013; Li et al., 2008; Anagnostopoulos et al., 2010] mainly focus on desktop query recommendation, which aims to provide alternative queries of the users' issued queries or assist users in refining their queries in desktop search. However, they may not be suitable for mobile query recommendation because of two reasons. First, typing or data entry on mobile devices is more difficult than on desktop computers. It is reported in [Fu et al., 2009] that even for skilled users, they can only reach 21 words per minute on mobile devices; while on desktop computers, the rate is at least 60 words for common users.Second, many mobile devices come with position functions such as Geographical Positioning System (GPS) and sensors. Through these devices, more and more data are being accumulated in the form of current user's location and location annotations. For example, the location-based entity system, yelp 1 provides the location annotations such as the reviews for restaurants, shops and etc. Thus, we can identify users' current activities and further improve the performance of mobile query recommendation.

In this paper, we introduce a new problem of mobile query recommendation, which is not limited to query refinement, but to find what users need. For example, Figure 1 shows the automatic query recommendation system in Bing search engine. We model the user-location-query relations with a tensor representation. Unlike previous studies on tensor decomposition and completion, we study this problem from the viewpoint of missing value estimation via tensor function learning. Given a tensor indicating the existing user-locationquery relations, we want to recommend the right query for users based on their current location. Since the relations between users and queries at some locations are unknown (missing values in the mobile query tensor data), we want to predict the missing values in the tensor first, then recommends users with the queries with high predicted values. We then learn a tensor function based on the mobile query data, location annotations and query information. We obtain the annotations for the location in Beijing, China from a yelp-like location-based entity reviewing system, dianping 2 . We extract the users' clicked webpages to enrich the information of their issued queries. The main contributions of this paper are as follows:

1 http://www.yelp.com/

1. We introduce a new problem of query recommendation on mobile devices, and formulate a tensor function learning model based on the side information of user, location and query.
2. We introduce a tractable relaxation of the tensor function learning, and then obtain a convex problem of functional coefficient nuclear norm minimization. We present an efficient alternating direction method of multipliers (ADMM) scheme to solve the introduced problem.
3. We evaluate the performance of our method on Bing search engine on mobile devices for three months in the city of Beijing, China, and show that our method can outperform several state-of-the-art solutions to the problem.

The rest of this paper is organized as follows. In Section 2, we introduce the notions of the problem and provide a brief review of the related work about tensor completion and query recommendation. We introduce the problem of mobile query recommendation and provide the optimization algorithm in Section 3. A variety of experimental results are presented in Section 4. Finally we provide some concluding remarks in Section 5.

2 Notions and RelatedWork

Before reviewing previous work, we first introduce basic tensor notions and terminologies. An n-mode tensor is defined as Y ∈ RI1×I2×...×In , and its elements are denoted as yi1,...,in where 1 ≤ ik ≤ Ik and 1 ≤ k ≤ n. For example, a matrix is a 2-mode tensor. The k-th mode unfolding, also known as matricization, of an n-mode tensor Y is denoted as unfoldk(Y) = Y(k) ∈ RIk×∏j̸=k Ij where the k-th mode becomes the row index and all other (n - 1) modes become the column indices. The tensor element (i1, i2, . . . , iN) is mapped to the matrix element (in, j), where

The opposite operation is defined as foldk(Y(k)) = Y. The Frobenius norm of the tensor Y is defined as ‖Y‖F = √∑i1,i2,...,in y2 i1,...,in . It is clear that ‖Y‖F = ‖Y(k)‖F for any 1 ≤ k ≤ n.

Mode-n product is the product of a tensor W ∈ Rp1×...×pN with a matrix A ∈ RJ×pn , denoted by W×n A. The result is a new tensor of size p1×. . .×pn-1×J×pn+1× . . . × pN , where each mode-n fiber is multiplied by A, that is

2 http://www.dianping.com/

Vectorization is a linear transformation which converts a matrix into a column vector. Specially, the vectorization of a matrix X ∈ Rm×n , denoted by vec(X), is the mn×1 column vector obtained by stacking the columns of the matrix X on top of one another, that is,

where xij represents the (i, j)-th element of matrix X. We consider that vectorization is an instance of tensor unfold, which unfolds a matrix to a vector (i.e., X(1)). Similarly, we define the unvec that folds a vector to a matrix (i.e., unvec(X(1)) = X).

Let A ∈ Rm×n and B ∈ Rp×q be two matrices, respectively. The Kronecker product of two matrices A and B, denoted by A ⊗ B, is an mp × nq matrix given by A ⊗ B = [aijB]mp×nq .

Tensor Decomposition and Completion has witnessed the applications in machine learning and data mining. The two popular tensor decomposition methods are CP decomposition [Acar et al., 2010] and Turk decomposition [Kolda and Bader, 2009]. The tensor decomposition method aims to factorize an input tensor into a number of low-rank factors, which are prone to local optimal because they are solving essentially non-convex optimization problems [Liu et al., 2013; 2009]. In order to address this problem, Liu et.al. [Liu et al., 2013] extends the trace norm of matrices to tensors, and generalize matrix completion to convex tensor completion. Specially, given an incomplete n-mode tensor matrix Y ∈ RI1×I2×...×In with low rank, the tensor completion problem is given byminX rank(X)

where Y, X ∈ RI1×I2×...×In , and PΩ keeps the entries in Ω and zeros out others. The missing elements of X are determined such that the rank of the tensor X is as small as possible. Unfortunately, the above rank minimization problem is NP-hard in general due to the nonconvexity and discontinuous nature of the rank function. Theoretical studies [Recht et al., 2010] show that the nuclear norm is the tightest convex lower bound of the rank function. The trace norm of a tensor is a convex combination of the trace norms of all matrices unfolded along each mode. Therefore, a widely used approach is to apply the nuclear norm as a convex surrogate of the nonconvex tensor rank function

where ‖X(i)‖∗ = ∑min(m,n) j=1 δj(X(i)) is the nuclear norm of the i-th mode X(i) and δj(X(i)) is the j-th largest singular value of X(i). The existing approaches [Zhang et al., 2014; Liu et al., 2013; Wang et al., 2014; Liu et al., 2014; Zhao et al., 2015] based on the combination of the trace norms of all matrices have achieved excellent empirical performance.

However, the objective of our approach is to learn the tensor function from the data tensor instead of completing the data tensor directly. Therefore, these methods are not applicable to our problem.

Query Recommendation is an important functionality in the mobile search engine. In existing work [Guo et al., 2010; Feild and Allan, 2013; Li et al., 2008; Anagnostopoulos et al., 2010] for query recommendation aims to assist users to refine the issued queries. In this paper, we introduce a new problem of query recommendation on mobile devices, which is not limited to query refinement, but to find what users need.

3 Query Recommendation via Tensor Function Learning

In this section, we first introduce some notions for mobile query recommendation, which are the observed data tensor of user-location-query relations Y, the side information matrix of users U, annotation of locations matrix R and query intent matrix Q. We then formally present the problem of mobile query recommendation via tensor function learning and provide the optimization algorithm to solve the problem.

We denote the observed data tensor of user-location-query relations Y ∈ Rm×l×n where m is the number of queries, l is the number of locations and n is the number of users. The observed user-location-query entries in Y are the query issued by users at some location. However, we observe that the tensor Y of mobile query data is very sparse and there are a number of missing relations. We let Ω be the set of observed user-location-query relations in Y. Entry Yijk is said to be observed if the k-th user issue the i-th query at the j-th location (i.e. (i, j, k) ∈ Ω).

We consider that the query intent is the side information for the existing queries, denoted by Q ∈ RI1×n . We extract the clicked webpages of the mobile queries and collect their classification labels such as "enterprise" and "business" . We note that the webpage can have multiple labels. We then denote the side information of locations by R ∈ RI2×l , which is collected from the location-based entity reviewing systems. We extract the annotated tags for the locations such as "food" and "hotpot" . We represent the feature of locations and query intent using the bag-of-words model. We denote the side information of users by U ∈ RI3×m, which is obtained from the mobile devices such as its brand and operating system. The I1, I2 and I3 are the feature dimension of users, locations and query intent, respectively. Using the notions above, we introduce the problem of tensor function learning below.

3.1 The Problem

We now describe the learning problem for mobile query recommendation. Given query intent Q ∈ RI1×n , annotated locations R ∈ RI2×l and user information U ∈ RI3×m, we denote the parameter tensor byW ∈ RI1×I2×I3 . Therefore, we present the tensor function by

where ×1 is the mode-1 product for parameter tensorWand query intent Q. For example, the prediction for entry Yijk based on parameter tensor W is given by

where Qi,:, Rj,: and Uk,: are the side information of the i-th query, j-th location and k-th user, respectively. We illustrate the framework of tensor function learning for mobile query recommendation in Figure 2. The tensor Y, matrices U, R and Q with the gray color are known and the parameter tensor Wwith the white color is unknown.

We observe that there is a strong correlation between queries, locations and users in the mobile query data Y. For example, both the query "having an injection" and the query "where is the zoo" often co-exist in the mobile queries of some users. Thus, to avoid the overfitting problem of function learning and exploit the correlation between queries, locations and users, we encourage the parameter tensor W to have a simple structure in the sense that they involves a small number of "degree of freedoms". Thus, it is natural to assume that the tensor function learning are of low-rank constraints. Consequently, we cast the problem of tensor function learning into the optimization problem of tensor completion, given by

where the minimization of rank(W) is considered as the regularizer for function learning. By requiring PΩ(Y ) = PΩ(fW(Q,R,U)), we expect that the learned tensor function can accurately estimate the query-location-user relations in Y.

Unlike the standard algorithm for tensor completion that requires solving an optimization problem involved the data matrix Y of m × l × n, the optimization problem given in Problem (4) only deals with the parameter tensor W with I1 ×I2 ×I3. The size of parameter tensor W is much smaller than the data tensor Y. Thus, the computation burden of our model is significantly more efficient.

Following the convex relaxation approach for tensor trace norm in [Liu et al., 2013; Tomioka and Suzuki, 2013], we introduce the auxiliary matrix variables Z1, Z2 and Z3 for the unfolding of parameter tensor W on the mode of query

Algorithm 1 Solving Problem (5) via TFL

Input: data tensor Y, user matrix U, query matrix Q and location matrix R Initialize: W = 0, Zn = 0, Γn = 0, µ = 10-6 , maxµ = 1010 , ρ = 1.05, ε = 10-8

• 1: while not converge do
• 2: Update Zn,Wand X by Equation (8), (14) and (16), respectively.
• 3: Update the multiplier Γn by Γn = Γn +µ(W(n) -Zn).
• 4: Update the parameter µ by µ =min(ρµ,maxµ).
• 5: Check the convergence condition, max(‖W(n) -Zn‖2F , n = 1, 2, 3) < ϵ.
• 6: return X andW.

W(1), locationW(2) and userW(3), respectively. Therefore, we convert Problem (4) to the following equivalent problem:

where the summation of the auxiliary matrix variables ∑3n=1 ‖Zn‖∗ is the convex relaxation of rank(W). The trade-off parameter λ balances the weight between the data penalty ‖X - fW(Q,R,U)‖2F and the regularization term ∑3n=1 ‖Zn‖∗, which is usually set empirically.

3.2 The Optimization

In this section, we propose an efficient Tensor Function Learning algorithm (TFL) based on alternating direction method of multipliers (ADMM) to solve the Problem (5). ADMM [Boyd and Vandenberghe, 2004] decomposes a large problem into a series of smaller subproblems, and coordinates the solutions of subproblems to compute the optimal solution.

We rewrite Problem (5) via augmented Lagrangian function, given by

where Γn, n = 1, 2, 3, are the matrices of Lagrange multipliers, and µ > 0 is a penalty parameter. ADMM solves the proposed problem by minimizing the Lagrange function L over W, X, {Zn}, and then updating the multipliers {Γn}.

We first introduce a useful tool: the singular value shrinkage operator [Cai et al., 2010] to estimate the matrix Zn in tensor function learning.

Definition 1 (Singular Value Shrinkage Operator) Consider the singular value decomposition (SVD) of a matrix Z ∈ Rm×n of rank r,

Define the singular value shrinkage operator Dτ as follows:

and Using the singular value shrinkage operator above, we have the following useful theorems for the composite objective functions below:

Theorem 1 ( [Cai et al., 2010]) For each λ ≥ 0 and W ∈ Rm×n , we have

where the matrix Dλ(W) is the solution to this optimization problem with nuclear norm regularizer.

Updating Zn: Ignoring constant terms, the minimization with respect to Zn is given by

Thus, we can obtain the closed form solution of Zn by Theorem 1 as follows:

We then introduce the following Theorem to estimate the parameter tensor W given the side information of queries Q, locations R and users U.

Theorem 2 (Block Matrices and Kronecker Products) Suppose vec(X) denotes the vectorization of the matrix X formed by stacking the columns of X into a single column vector. Consider for instance the equation AXB = C, where A, B and C are given matrices and the matrix X is the unknown. We can rewrite this equation as

Updating W: Ignoring constant terms, the minimization with respect toW is given by

For ease of presentation, we let

Figure 3: Data Distribution in Beijing: The dotted points in the left figure represent the GPS of mobile queries and the dotted points in the right figure represent the GPS of annotated locations. The x-axis and y-axis represent the longitude and latitude of the dotted points, respectively.

Therefore, the optimal solution of W is given by

Updating X: The optimization problem with respect to X is formulated as follows:

By deriving the KKT conditions for Equation (15), the optimization solution of X is given by

where Ωc is the complement of Ω, i.e., the set of the unobserved query log entries.

The entire procedure for tensor function learning is summarized in Algorithm 1. The main computation cost of the algorithm in each iteration is the cost of SVD in Line 2. The addition cost in Line 3 and Line 4 is much smaller. Note that our function learning model alleviates the computation burden since the size of parameter tensor is much smaller than data tensor. For large scale problems, we can adopt some existing techniques [Li et al., 2010] to accelerate the computation of SVD and make Algorithm 1 more efficient, and apply the parallel ADMM techniques [Shang et al., 2014] for the proposed optimization problem. Suppose the penalty term µ in the final iteration is µ∗ , the convergence of Algorithm 1 for Problem (5) is O( 1 µ∗ ), which is guaranteed in [Lin et al., 2011].

4 Experiments

In this section, we conduct several experiments on the mobile queries from Bing search engine and location-based entity reviewing systems dianping, to show the effectiveness of our proposed approach for query recommendation on mobile devices. The experiments are conducted by using Matlab and TensorToolBox [Bader et al., 2015], tested on machines with Windows OS Intel(R) Core(TM) i7-2600 CPU 3.40GHz, and 128 GB RAM.

4.1 Data Preparation

In the experiment, we apply our method on the Bing mobile dataset, which consists of users' location and their mobile queries from Bing search engine during Jan. 2014 to June 2014 in the city of Beijing, China. To protect users' privacy, we remove the GPS points for work places, homes, and users' information, and use the sampled data for doing the experiments. We sample 3,000 users and 1,000 different mobile queries from the dataset where users' id is anonymized during the sampling. Thus, we collect the 114,138 querylocation-user relations. We sample 10% of the mobile queries and illustrate the GPS distribution of them in Figures 3(a).

We collect 105,271 entities from the location-based entity reviewing system, dianping. We sample 10% of the locationbased entities and illustrate the their GPS distribution 3(b). The locations used in the experiments are in the categories of "shopping", "food", "hotel", "education", "automotive" and etc. We then obtain query intent from the clicked webpages and side information of location-based entities from the reviews in dianping. To further protect users' location privacy, we represent the users' location by location category. In this work, we use 30 location categories to represent users' location.

4.2 Evaluation Criteria

We evaluate the performance of our method for mobile query recommendation using RMSE (root mean-square error). We randomly sample 90% of the observed querylocation-user relations in tensor Y as training data. We then consider the remaining 10% of the observed relations as testing data. The RMSE metric is given by

where Y and fW(Q,R,U)) are the true and predicted query-location-user relations, respectively. The set Ωt consists the indices of all the relations in the testing data and PΩt keeps the entries in Ωt and zeros out others. The metric RMSE has been widely adopted in the evaluation of recommender systems, such as Netflix Prize [Bennett and Lanning, 2007]. In our setting, the RMSE indicates the difference between the true existing query-location-user relations and the predicted ones. The smaller RMSE means better performance of the method. For each setting, we carry out the cross-validation on RMSE for ten times and record the mean value.

4.3 Performance Comparisons

We compare our proposed method with other five popular tensor recommendation algorithms including canonical polyadic decomposition (CP) [Acar et al., 2010], Turk decomposition (Turk) [Kolda and Bader, 2009], generalized higher-order orthogonal decomposition (gHOI ) [Liu et al., 2014], and tensor recommendation incorporating side information (UCLAF) [Zheng et al., 2010]. We summarize these algorithm as follows:

• CP algorithm: The canonical polyadic decomposition algorithm is a generalization of the matrix singular value

decomposition (SVD) to tensors, which represents a tensor by a sum of the outer products of rank-1 tensors.

• Turk algorithm: The Turk decomposition algorithm decomposes a tensor into a set of matrices and one small core tensor, where each matrix is orthogonal.
• gHOI algorithm: The generalized higher-order orthogonal decomposition algorithm decomposes a tensor under the framework of Turk decomposition, where the core tensor is regularized by nuclear norm.
• UCLAF algorithm: The UCLAF algorithm decomposes a tensor into a set of matrices, where the matrices are regularized by side information.

We illustrate the performance of all the algorithm in Table 1 by sampling 50% to 90% of the training data. The best mean values are bolded. We expect the relative decreasing of RMSE for a more effective recommendation method.

We summarize the experimental results in Table 1 as follows:

• We observe that the performance of the gHOI algorithm is better than both the popular tensor decomposition algorithms CP and Turk. Apart from CP and Turk, gHOI formulates the convex relaxation of the tensor decomposition problem based on the combination of the nuclear norm of all matrices and achieves excellent empirical performance.
• The UCLAF method achieves better performance than other baseline methods. This suggest that the side information can also improve the performance of mobile query recommendation.
• In all the cases, our TFL method achieves the best performance. This shows that leveraging the power of both the side information of locations and queries, and the convex formulation based on nuclear norm minimization on parameter tensor of tensor function learning, the performance of mobile query recommendation can be further improved.

4.4 Convergence Study

The updating rule for minimizing the objective function of TFL is essentially iterative. Here we investigate how TFL method converges.

Figure 4 shows the convergence curve of TFL method. The y-axis is the value of error rate on the training set (i.e., |PΩ(Y-fW(Q,R,U))| |Ω| and x-axis denotes the iteration number. We can observe that method TFL converges after the 500-th iteration.

5 Conclusions

In this paper, we introduce the problem of mobile query recommendation from the perspective of tensor function learning. Unlike previous studies based on tensor decomposition and completion, we propose the tensor function learning approach for estimating the missing query-location-user relations for mobile query recommendation. We learn the tensor function from the side information of the queries, locations and users with low-rank constraints. We then provide an iterative procedure for Tensor Function Learning, TFL, to solve the proposed optimization problem, using the framework of ADMM. We collect the mobile queries in Bing search engine for three months in the city of Beijing, China. We conduct the experiments on Bing mobile query dataset, and the locationbased entity reviewing system, dianping. The experimental results demonstrate the effectiveness of our method against several state-of-the-art tensor recommendation algorithms. In the future, we will explore the kernel tensor function for the problem of mobile query recommendation.

Acknowledgements This work was supported by National Basic Research Program of China (973 Program) under Grant

2012CB316400 and Grant 2015CB352300, National Program for Special Support of Top-Notch Young Professionals, and National Natural Science Foundation of China under Grant 61233011 and Grant 61125203, and the Fundamental Research Funds for the Central Universities.