Crowdsourcing-Assisted Query Structure Interpretation

1 Introduction

Structured Web search incorporates the results from structured data sources into Web search, and it has attracted much attention from both academic and industrial communities. Many commercial search engines, such as Google and Yahoo, have begun to offer structured Web search to effectively answer users' queries which target the structured data in various domains-of-interest, e.g., products, movies, etc.

A key problem of structured Web search is how to interpret a keyword query by not only identifying the target domain of the query, but also mapping query terms to their semantically relevant attributes in the domain. For example, given a keyword query "Seattle Microsoft jobs", we need to first identify the target domain is JOB, and then respectively map "Seattle" and "Microsoft" to the attributes, i.e., location and company in the JOB domain.

∗This work was supported in part by National Natural Science Foundation of China under grant No.60833003 and No.61272090.

In order to accurately interpret queries, this paper studies the query structure interpretation problem. Consider a query log from a search engine and a target domain. For every query in the log, we generate a set of structure interpretations for the terms in the query, where each structure interpretation (or interpretation for simplicity) is a mapping from a term to an attribute in the domain (e.g., a mapping from "Microsoft" to the company attribute). The generated interpretations can be used to interpret online queries in structured Web search.

Previous works for query structure interpretation have proposed methods to identify the query intent and extract semantic structure of named entities [Li, 2010; Li et al., 2009; Sarkas et al., 2010; Manshadi and Li, 2009; Cheung and Li, 2012]. The methods employ supervised (e.g., conditional random field, CRF) or semi-supervised (e.g., semi-CRF) methods to interpret queries from a small number of correct interpretations (i.e., the "seeds"). However, the existing methods assume all queries have been ideally classified into the target domain, which is impractical to real query logs consisting of queries in various domains. Our experimental result also shows that, even applying an effective query classifier, these methods still achieve low interpretation accuracy.

The limitation of the machine-based methods can be alleviated with the help of crowdsourcing by utilizing wellestablished platforms such as Amazon Mechanical Turk (AMT), since human are good at interpreting queries from different domains. [Demartini et al., 2013] proposes a framework by publishing all uninterpreted queries for crowdsourcing. This method, however, is costly and time-consuming given the large scale of query logs. To address the problem, we introduce a human-machine hybrid method to select a small number of query terms for crowdsourcing and best utilize the crowdsourcing results for effective interpretation.

This paper studies the research challenges that naturally arise in the proposed method. The first challenge is, given a user-defined budget k (i.e., the maximal number of microtasks), how to select the "most useful" k terms for crowdsourcing. To address this challenge, our method considers two factors to quantify the usefulness of a term: 1) its relevance to the target domain and 2) the benefit, i.e., the reduction of overall error, if the term is correctly interpreted. The second challenge is how to utilize the crowdsourced interpretations to infer other interpretations. We introduce an iterative probabilistic inference model based on a similarity graph of query terms. We prove that the iteration would converge and show the effectiveness of the model in experiments.

To summarize, we make the following contributions.

1. To the best of our knowledge, this paper is the first to study the problem of crowdsourcing-assisted query structure interpretation given budget constraints.
2. We introduce an iterative probabilistic inference model to fully utilize crowdsourcing results, and develop an effective method for selecting query terms for crowdsourcing.
3. We have conducted experiments on real datasets, and the experimental results show that our method outperforms the state-of-the-art method at a low money cost.

This paper is organized as follows. The problem is formulated in Section 2. We introduce our crowdsourcing-assisted method in Section 3, and report the experimental result in Section 4. The related work is reviewed in Section 5 and we conclude the paper in Section 6.

2 ProblemFormulation

Our work considers a query log Q = {Q1,Q2, . . . ,Q|Q|}, where each query Q consists of a set of query terms, denoted by Q = {q1, q2, . . . , q|Qi|}. Table 1 provides an example log containing 14 queries. We also consider a domain-of-interest (or domain for simplicity) with a set of attributes, denoted by D = {A1,A2, . . . ,A|D|}. For example, the JOB domain containing the employment information has three attributes, i.e., location, company, and position.

Given a query Q ∈ Q, we aim to interpret the structure of Q by mapping each term q ∈ Q to its semantically relevant attribute in the domain D. Specifically, a term is semantically relevant to an attribute, if and only if the term refers to the values or the name of the attribute. For example, the term "Microsoft" is semantically relevant to attribute company, since it refers to a value of the attribute. Formally, we define the mapping from a term to its semantically relevant attribute.

Definition 1 (Query Term Interpretation). An interpretation of term q, denoted by I A q , is a pair 〈q,A〉 where A ∈ D is a domain attribute which is semantically relevant to q.

In particular, we also consider the case that q refers to the domain D, e.g., the term "jobs" in Table 1 referring to the JOB domain, and formally denote it as I D q .

Then, we define the problem of query structure interpretation by considering all the term interpretations.

Definition 2 (Query Structure Interpretation). Given each query Q ∈ Q, the problem finds a set of query term interpretations, i.e., IQ = {I A q | q ∈ Q,A ∈ D}.

For instance, given the JOB domain, query Q1 in Table 1 can be interpreted as IQ1 = {〈"Seattle",location 〉, 〈"Microsoft",company 〉, 〈"job",JOB 〉 }.

Note that our work does not assume that all queries belong to the domain D, which is different from existing methods [Li, 2010; Li et al., 2009; Sarkas et al., 2010; Manshadi and Li, 2009]. Some queries in Table 1 are irrelevant to the JOB domain, e.g., Q8 about the restaurant information and Q13 about the hotel information.

3 ACrowdsourcing-AssistedMethod

Our method differs from existing query structure interpretation techniques in two key aspects. First, our method leverages the intelligence of crowdsourcing workers to interpret queries from different domains since the workers are good at identifying domain-relevant queries and providing accurate interpretation. Second, the method utilizes a crowd-machine hybrid framework to avoid asking the workers all queries in the log, and thus controls the crowdsourcing cost. Figure 1 provides an overview of our method consisting of two phases.

Phase I: Query Term Selection. This step is to select a small number of terms with significant usefulness and generate microtasks for the terms. Specifically, a microtask includes a term as well as the query containing the term, and provides candidate domain attributes 1 . When presented with the microtask, the workers are asked to choose the attributes semantically relevant to the corresponding term. Based on workers' choices, we obtain a set of crowdsourced interpretations.

Phase II: Interpretation Inference. This step is to infer the structure interpretation for each query in the log. The inference takes two kinds of known interpretations as input: 1) a very small number of seed interpretations that maps terms to correct attributes, and 2) the crowdsourced interpretations generated in Phase I. It bootstraps the known term interpretations to predict the unknown ones, and outputs IQ for each Q ∈ Q. For effective inference, we propose a graphical model to capture the relationship of query terms, and develop iterative inference based on the graph.

1 There is also a "none-of-the-above" choice to indicate the term is irrelevant to the domain

Since the usefulness of a term depends on how we use it in the inference, we first introduce the inference model in Section 3.1, while assuming we have obtained the crowdsourced interpretations. Then, we present how to select query terms for crowdsourcing in Section 3.2.

3.1 Iterative Probabilistic Inference Model

Probabilistic Modeling for Candidate Interpretations. Given a term q, we consider all the attributes that are possibly relevant to it, and generate candidate interpretations. Then, for each candidate I A q , we introduce a probability P (I A q ) to model the confidence of the interpretation. The larger the probability P (I A q ) is, the more likely term q can be interpreted as attribute A. Considering all the candidate interpretations of q, we introduce a candidate vector.

Definition 3 (Candidate Interpretation Vector). Given a query term q, its candidate interpretation vector consists of the probabilities between q to all attributes in D, denoted by Pq = (P (I A1 q ), P (I A2 q ), . . . , P (I A|D| q )).

Given the candidate vector of term q, we take the one with the maximal probability as the best interpretation of q, i.e.,

In particular, if all probabilities in Pq are smaller than a pre-defined threshold (e.g., 0.501 in our experiments), we regard term q as an domain-irrelevant term. For example, the term "renting" in Q12 is irrelevant to domain JOB.

The key challenge in Equation (1) is to estimate the probability P (I A q ) for each candidate interpretation in the vector. To address the challenge, we develop an inference method based on an interpretation graph.

Interpretation Graph (I-Graph).

The interpretation graph is used to capture the relationship of query terms, which is formally defined as follows.

Definition 4 (Interpretation Graph). An interpretation graph is an undirected graph, denoted by G(T , E), where T

represents all query terms in the log, i.e., T = ⋃1≤i≤|Q| Qi. Each term q ∈ T is associated with its candidate vector Pq. If two terms qi and qj are similar to each other, there exists an edge e ∈ E with weight w(qi, qj).

Figure 2 and Table 2 provide an example I-graph based on the query terms in Table 1. We can see that each node corresponds to a query term, and nodes are connected by edges weighted with normalized similarities. For example, the two nodes q2 (i.e., "Microsoft") and q3 (i.e., "Google") are connected by an edge with weight 0.38.

We propose a novel method to measure the similarity between two query terms. Since Web queries are usually very short, i.e., the number of terms in a query is small [Cui et al., 2002], traditional string similarity measures, such as Jaccard, are rather limited. To address this problem, we introduce the context similarity. The basic idea is that two terms qi and qj are similar if the queries containing qi is similar to those containing qj . Formally, we introduce the query context.

Definition 5 (Context of Query Term). The context of a term q ∈ Q with respect to query Q, denoted by C(q | Q), is the set of terms in Qwithout q, i.e., C(q | Q) = Q-{q}.

For example, the context of term "Microsoft" with respect to Q1 is {Seattle, jobs}. Considering all the queries in Q, we obtain a set of contexts for term q, denoted by C(q) = {C(q | Q),Q ∈ Q}. Then, we measure the similarity between qi and qj as

Example 1 (Context Similarity). Consider the queries in Table 1. For the query term "HR", we can obtain the set of its contexts, i.e., C("HR" ) = {{Seattle}, {salary}}. Similarly, we can also compute C("programmer" ) = {{Seattle, jobs}, {salary}}. Based on the obtained contexts, we have sim("HR" , "programmer" ) = 0.33.

Then, we define weight of the edge between qi and qj as the normalized context similarity, i.e.,

Iterative Inference based on I-Graph.

We propose an effective inference method by iteratively updating the candidate vector of each term in the I-Graph. Before iteration, the candidate vectors of different types of terms are initialized as follows.

1. For a term qs in a seed interpretation that is mapped to As , we set P (I As qs ) to 1 and others in the vector to 0.
2. For a term q in a Crowdsourced interpretation, since we assign a microtask to l workers, we aggregate workers' answers as follows. Suppose the number of workers choosing attribute Ak is lk. We estimate probability P (I Ak q ) in the vector as lk/l.

3) For a term q with unknown interpretations, we set each probability in the vector as P (I A q ) = 0.5.

We denote the initial candidate vector for each term qi ∈ T as P0qi and the vector after n iterations as Pnqi . Then, we iteratively update the candidate vector for qi as follows. If qi is a seed term, we keep its vector unchanged. On the other hand, if qi is either a crowdsourced term or a term with unknown interpretations, we compute its vector by considering all the neighbor terms of qi. Formally, we can compute the vector Pnqi as Equation (4), where α is a parameter in (0, 1).

We iteratively update candidate vectors in the I-graph using Equation (4) until convergence. After convergence, we normalize each probability P (I A q ) by dividing the number of seeds of attribute A, in order to avoid the case that attributes with more seeds dominate those with less seeds.

Example 2. In our example I-graph in Figure 2, the query terms q3 and q6 (black color) are seed interpretations, and q4 (gray color) is a crowdsourced interpretation. Then, based on our iterative model in Equation (4), we can obtain the converged candidate vector for each term in T .

Next, we provide some theoretical analysis of our iterative inference method.

Theorem 1. The iteration of I-graph according to Equation (4) will converge.

Construct a matrix W, where Wii = 0 and Wij = w(qi, qj) if qi is not seed node, otherwise Wii = 1 and Wij = 0. Then Equation (4) is equivalent to Pn = αWPn-1 + (1 - α)P0 . Hence, we can get

Let D be a diagonal matrix with the i-th element Dii = ∑k̸=i sim(qi, qk). Construct matrix S satisfying: 1) For qi which is not a seed, we set Sij = sim(qi, qj ) and Sii = 0, and 2) For a seed qi, we set Sij = 0 and Sii = ∑k̸=i sim(qi, qk). Thus, we can easily get W = D-1/2SD-1/2 .

Since F = D-1/2WD1/2 = D-1S is a stochastic matrix and W is similar to F . Hence the eigenvalues of W is within the interval [-1, 1]. Considering α is in (0,1), we have

.

Hence,P∗

Thus, we prove the convergence of the iteration.

3.2 Query Term Selection for Crowdsourcing

This section discusses how to select query terms for crowdsourcing. A straightforward method is to randomly select a subset of query terms in T . However, this method has the following limitations. First, since the query log contains many queries that not belong to the domain, the method may involve many domain-irrelevant terms, which are useless for structure interpretation. Second, the random selection method treats all terms equal and fails to consider the usefulness of different terms in our inference model.

To address the above problems, we propose a novel model to judiciously select query terms by considering the following two factors: 1) the relevance of the terms to the domain, and 2) the benefit of correctly interpreting the terms through crowdsourcing. Our model prefers the terms which are not only more relevant to the domain, but also have more benefit. Formally, given a term qi ∈ T , we use r(qi) and b(qi) to respectively represent the relevance and the benefit of qi. Based on the two factors, we assign the following score to qi.

Then, given a budget, i.e., the maximal number of terms for crowdsourcing, we select the terms with the highest scores. The challenge is how to estimate the term relevance and benefit. We discuss the estimation methods as follows.

Estimating term relevance. Given a term qi, we estimate the relevance r(qi) as its overall similarity to the seeds, i.e., r(qi) = ∑qs sim(qi, qs ) where qs is a seed. Then, we normalize the relevance as r(qi)/r∗ where r∗ is the maximum relevance among all the terms, i.e., r∗ =maxqi∈T r(qi).

Estimating term benefit. We introduce the overall error reduction to model the benefit of correctly interpreting term qi. Intuitively, if qi is mapped to an incorrect attribute, the error would "propagate" to other terms through our inference model, which may induce the overall error to all terms. Thus, a correct interpretation of qi would not only benefit qi itself, but also reduce the overall error induced by qi. More formally, let the vector △P0qi denote the error of qi. We use △P∗ to represent the overall error induced by △P0qi after iterations, which is estimated as follows.

where △P∗qk is the error of qk induced by △P0qi after iterations, and θk is a weight capturing the importance of P∗qk to the overall error. We estimate θk by ∑|T | j=1 w(qk, qj )/ ln(1 + |qk|) where |qk| is number of characters in term qk.

Next, we discuss how to induce △P∗qk from △P0qi . For ease of presentation, we use matrixW∗ to denote (1-α)(IαW)-1 . Then, based on Equation (5), we have

Based on Equations (7) and (8), we have

Using Equation (9), we estimate the benefit of qi as

Algorithm for Top-k Term Selection. Based on Equation (6), we select top-k query terms as follows. We first compute the best termwith highest score q∗ = argq∈T score(q). Then, we recalculate the matrix W ∗ by removing the elements corresponding to q∗ , and obtain the next query term. After obtaining k terms, the algorithm terminates.

Then we add crowdsourced interpretations to the graph by modifying initial vectors of corresponding nodes.

Example 3 (Query Term Selection for Crowdsourcing). Consider the I-graph in Figure 2. We can see that some nodes have higher relevance but lower benefit (e.g., r(q2) = 0.48 and b(q2) = 0.77), while others have lower relevance but higher benefit (e.g., r(q8) = 0 and b(q8) = 1.07). By combining both relevance and benefit, we select q4 (r(q4) = 0.36 and b(q4) = 1.18) as the top-1 term for crowdsourcing.

4 Experiments

4.1 Experiment Setup

Query Log. We evaluated our method on a real Chinese query log from Sogou search engine 2 . The number of queries is 34, 000, and the number of distinct query terms is 43, 520. Note that the query log contains queries belonging to various domains, e.g., JOB, ESTATE, PRODUCT, etc.

Since the log is too large to be manually labeled, we generated three benchmark sets, BENCHMARK1, BENCHMARK2 and BENCHMARK3 by randomly selecting queries from the log. In each benchmark set, we manually identified the queries belonging to the target domain and mapped query terms to domain attributes. The numbers of queries in the three benchmark sets are respectively 161, 154 and 148.

Domains-of-Interest. We examined three domains for query structure interpretation, i.e., ESTATE, JOB and PRODUCT. The domain attributes and number of seeds for each attribute are listed in Table 3. We can see that the proportion of seeds is very small, i.e. 0.8% (ESTATE), 1.9% (JOB) and 0.5% (PRODUCT). Notice that queries in ESTATE and JOB may share some common attributes, e.g., location and company, which increases the challenge of interpreting queries. However, as we will show later, our method still performs well.

Baseline Method. We implemented the state-of-the-art query structure interpretation method [Li, 2010]. Since this method requires all queries to be classified into the target domain (e.g., JOB), we employed a state-of-the-art query classifier [Tang et al., 2009] to obtain the queries classified into the target domain. Then we used the method in [Li, 2010] to interpret the classified queries. Note that both the method in [Li, 2010] and our method used the same set of seeds.

Crowdsourcing. We ran crowdsourcing on AMT platform. In each microtask, we presented a highlight term with its query and candidate attributes and asked worker to select the best attribute. We assigned each microtask to 4 different workers and paid $0.01 for each assignment. The method of aggregating workers' answers can be referred in Section 3.1. Evaluation Metrics. We employed the standard precision and recall metrics for evaluation. Specifically, let P denote the number of queries interpreted by a method, and TP denote the number of queries that were correctly interpreted by the method. Specifically, a query was correctly interpreted if all its terms had been mapped to correct domain attributes. In addition, let A denote the number of queries that should be interpreted. We compute the metrics, precision, recall and F1 as: P recision = TP P , Recall = TP A , and F 1 = 2·P recision·Recall Precision+Recall .

2 http://www.sogou.com/

All the programs were implemented in JAVA and all the experiments were run on a CentOS machine with an Intel(R) Xeon(R) E5607 2.27GHz processor and 32 GB memory.

4.2 Effect of Inference Parameter α

In this section, we evaluate the effect of the inference parameter α (Equation (4)) on the performance. For each domain, we ran the experiments with different α on the benchmark sets, then averaged the F1 score. Figure 3 provides the results. With the increase of α, the F1 score first increases and then deceases. It means we can select a best α to achieve good performance. In the remaining experiments, we use α = 0.25 by default, which achieves the best performance in all domains as shown in Figure 3.

4.3 Evaluating Term Selection for Crowdsourcing

In this section, we evaluate our method of query term selection for crowdsourcing in Section 3.2. We compared the method with two baselines: 1) Non-Crowd without crowdsourced interpretations and 2) Random-Crowd with randomly selected query terms. We selected 150 query terms (0.3% of all query terms) for each domain and ran the experiments on three benchmarks and averaged the F1 score.

Table 4 shows the experimental result. We can see that the Random-Crowd method is sometimes even worse than the Non-Crowd method. For example, the F1 score of Non-Crowd method in the PRODUCT domain is 67.0%, while that of Random-Crowd is 50.2%. The main reason is that the Random-Crowd method may select many query terms which are irrelevant to the target domain. Using too many irrelevant interpretations may damage the performance. Our methods achieves the best performance as shown in Table 4. The best performance is attributed to the selection model considering both relevance and benefit of query term.

4.4 Comparison with ExistingMethod

In this section, we compare our method with the baseline method mentioned in Section 4.1. Specifically, we evaluated both our inference method without crowdsourcing (Inference) and the method with crowdsourcing (Inference+Crowd). Figure 4 provides the results. We can see that the baseline method cannot effectively interpret queries from different domains in the real query log. For example, the average F1 scores of the baseline method on the three domains are 39%, 24% and 39%. The reason is that the baseline method assumes all queries are well classified. When interpreting noisy queries, the recall is low. For example, in the ESTATE domain, although the precision was acceptable (65%), the recall was very low (30%).

Our inference method significantly outperforms the baseline method. For example, the average F1 score of the inference method is increased by about 20% compared with the baseline in the JOB domain in Figure 4. Moreover, using crowdsourced interpretations can further improve the performance, even though we only selected 0.3% query terms for crowdsourcing. For example, in the PRODUCT domain, the F1 score can be further increased by about 8% when using crowdsourcing. The better performance of our method is mainly attributed to our effective inference model and the method of selecting crowdsourcing query terms.

5 RelatedWork

Query Structure Interpretation. Query structure interpretation can be applied to various tasks, such as question answering systems [Li et al., 2008], query refinement [Baeza-Yates et al., 2004; Sadikov et al., 2010], deep Web search [Cheng et al., 2010; Pound et al., 2011], etc. This problem has been extensively studied. The methods based on conditional random field (CRF) [Li, 2010; Li et al., 2009; Sarkas et al., 2010] formulate the problem as a query tagging problem, and employ CRF or semi-supervised CRF for tagging. [Manshadi and Li, 2009] employed context-free rules while requiring vocabulary for each domain attribute. [Cheung and Li, 2012] proposed an unsupervised method using knowledge bases (e.g., Freebase), and [Pandey and Punera, 2012] also proposed an unsupervised method based on graphical models. Existing methods have the limitation that they assume the queries have been classified into the target domain using query classifiers [Tang et al., 2009; Ji et al., 2011], and they cannot provide good interpretations for queries from different domains, which is very common in real logs. To this end, we propose a crowdsourcing-assisted method which is different from existing machine-learning based method.

Crowdsourcing. Crowdsourcing has attracted much attention in various communities [Lease and Yilmaz, 2011]. Many crowdsourcing-assisted methods have been proposed to improve the performance of various tasks. [Wang et al., 2012] provided a hybrid method for entity resolution. [Yan et al., 2010] combined automatic search and crowd validation to provide better image search. [Zaidan and Callison-Burch, 2011] introduced crowdsourcing to obtain professional translations from non-professional workers. [Law and Zhang, 2011] decomposed high-level mission into sub-goals to answer queries using crowdsourcing. [Demartini et al., 2013] addressed the interpretation problem by publishing all unknown queries for crowdsourcing and may result in costs larger than budgets. To the best of our knowledge, we are the first to study query interpretation using crowd-machine hybrid techniques given budget constraints.

6 Conclusion

This paper has studied the structure interpretation problem for queries from different domains in real query logs. We introduced a crowdsourcing-assisted framework to improve the performance. In the framework, we selected a small number of query terms for crowdsourcing, and employed the obtained interpretations for inference. We proposed an iterative probabilistic inference method, and judiciously selected crowdsourcing terms. We evaluated our method on a real query log, and the result shows the superiority of our method.