{'fraction_non_alphanumeric': 0.029916939151351147, 'fraction_numerical': 0.012064494306009697, 'mean_word_length': 4.454694546945469, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Utility-Driven Approach to Question Ranking in Social QA

We generalize the task of finding question paraphrases in a question repository to a novel formulation in which known questions are ranked based on their utility to a new, reference question. We manually annotate a dataset of 60 groups of questions with a partial order relation reflecting the relative utility of questions inside each group, and use it to evaluate meaning and structure aware utility functions. Experimental evaluation demonstrates the importance of using structural information in estimating the relative usefulness of questions, holding the promise of increased usability for social QA sites.


Introduction
Open domain Question Answering (QA) is one of the most complex and challenging tasks in natural language processing. While building on ideas from Information Retrieval (IR), question answering is generally seen as a more difficult task due to constraints on both the input representation (natural language questions vs. keywordbased queries) and the form of the output (focused answers vs. entire documents). Recently, community-driven QA sites such as Yahoo! Answers and WikiAnswers have established a new approach to question answering in which the burden of dealing with the inherent complexity of open domain QA is shifted from the computer system to volunteer contributors. The computer is no longer required to perform a deep linguistic analysis of questions and generate corresponding answers, and instead acts as a mediator be-tween users submitting questions and volunteers providing the answers. In most implementations of community-driven QA, the mediator system has a well defined strategy for enticing volunteers to post high quality answers on the website. In general, the overall objective is to minimize the response time and maximize the accuracy of the answers, measures that are highly correlated with user satisfaction. For any submitted question, one useful strategy is to search the QA repository for similar questions that have already been answered, and provide the corresponding ranked list of answers, if such a question is found. The success of this approach depends on the definition and implementation of the question-to-question similarity function. In the simplest solution, the system searches for previously answered questions based on exact string matching with the reference question. Alternatively, sites such as WikiAnswers allow the users to mark questions they think are rephrasings ("alternate wordings", or paraphrases) of existing questions. These question clusters are then taken into account when performing exact string matching, therefore increasing the likelihood of finding previously answered questions that are semantically equivalent to the reference question. Like the original question answering task, the solution to question rephrasing is also based on volunteer contributions. In order to lessen the amount of work required from the contributors, an alternative solution is to build a system that automatically finds rephrasings of questions, especially since question rephrasing seems to be computationally less demanding than question answering. The question rephrasing subtask has spawned a diverse set of approaches. (Herm-jakob et al., 2002) derive a set of phrasal patterns for question reformulation by generalizing surface patterns acquired automatically from a large corpus of web documents. The focus of the work in (Tomuro, 2003) is on deriving reformulation patterns for the interrogative part of a question. In (Jeon et al., 2005), word translation probabilities are trained on pairs of semantically similar questions that are automatically extracted from an FAQ archive, and then used in a language model that retrieves question reformulations. (Jijkoun and de Rijke, 2005) describe an FAQ question retrieval system in which weighted combinations of similarity functions corresponding to questions, existing answers, FAQ titles and pages are computed using a vector space model. (Zhao et al., 2007) exploit the Encarta logs to automatically extract clusters containing question paraphrases and further train a perceptron to recognize question paraphrases inside each cluster based on a combination of lexical, syntactic and semantic similarity features. More recently, (Bernhard and Gurevych, 2008) evaluated various string similarity measures and vector space based similarity measures on the task of retrieving question paraphrases from the WikiAnswers repository.
According to previous work in this domain, a question is considered a rephrasing of a reference question Q 0 if it uses an alternate wording to express an identical information need. For example, Q 0 and Q 1 below may be considered rephrasings of each other, and consequently they are expected to have the same answer.
Q 0 What should I feed my turtle?
Q 1 What do I feed my pet turtle?
Community-driven QA sites are bound to face situations in which paraphrasings of a new question cannot be found in the QA repository. We believe that computing a ranked list of existing questions that partially address the original information need could be useful to the user, at least until other users volunteer to give an exact answer to the original, unanswered reference question. For example, in the absence of any additional information about the reference question Q 0 , the expected answers to questions Q 2 and Q 3 above may be seen as partially overlapping in information content with the expected answer for the reference question. An answer to question Q 4 , on the other hand, is less likely to benefit the user, even though it has a significant lexical overlap with the reference question.
Q 2 What kind of fish should I feed my turtle?
Q 3 What do you feed a turtle that is the size of a quarter?
Q 4 What kind of food should I feed a turtle dove?
In this paper, we propose a generalization of the question paraphrasing problem to a question ranking problem, in which questions are ranked in a partial order based on the relative information overlap between their expected answers and the expected answer of the reference question. The expectation in this approach is that the user who submits a reference question will find the answers of the highly ranked question to be more useful than the answers associated with the lower ranked questions. For the reference question Q 0 above, the system is expected to produce a partial order in which Q 1 is ranked higher than Q 2 , Q 3 and Q 4 , whereas Q 2 and Q 3 are ranked higher than Q 4 . In Section 2 we give further details on the question ranking task and describe a dataset of questions that have been manually annotated with partial order information. Section 3 presents a set of initial approaches to question ranking, followed by their experimental evaluation in Section 4. The paper ends with a discussion of future work, and conclusion.

A Partially Ordered Dataset for Question Ranking
In order to enable the evaluation of question ranking approaches, we created a dataset of 60 groups of questions. Each group consists of a reference question (e.g. Q 0 above) that is associated with a partially ordered set of questions (e.g. Q 1 to Q 4 above). The 60 reference questions have been selected to represent a diverse set of question categories from Yahoo! Answers. For each reference questions, its corresponding partially ordered set is created from questions in Yahoo! Answers REFERENCE QUESTION (Q r ) Q 5 What's a good summer camp to go to in FL? PARAPHRASING QUESTIONS (P ) Q 6 What camps are good for a vacation during the summer in FL? Q 7 What summer camps in FL do you recommend? USEFUL QUESTIONS (U ) Q 8 Does anyone know a good art summer camp to go to in FL?
Q 9 Are there any good artsy camps for girls in FL? Q 10 What are some summer camps for like singing in Florida? Q 11 What is a good cooking summer camp in FL? Q 12 Do you know of any summer camps in Tampa and other online repositories that have a high cosine similarity with the reference question. Due to the significant lexical overlap between the questions, this is a rather difficult dataset, especially for ranking methods that rely exclusively on bagof-words measures. Inside each group, the questions are manually annotated with a partial order relation, according to their utility with respect to the reference question. We shall use the notation Q i ≻ Q j |Q r to encode the fact that question Q i is more useful than question Q j with respect to the reference question Q r . Similarly, Q i = Q j will be used to express the fact that questions Q i and Q j are reformulations of each other (the reformulation relation is independent of the reference question). The partial ordering among the questions Q 0 to Q 4 above can therefore be expressed concisely as follows: Note that we do not explicitly annotate the relation Q 1 ≻ Q 4 |Q 0 , since it can be inferred based on the transitivity of the more useful than relation: Also note that no relation is specified between Q 2 and Q 3 , and similarly no relation can be inferred between these two questions. This reflects our belief that, in the absence of any additional information regarding the user or the "turtle" referenced in Q 0 , we cannot compare questions Q 2 and Q 3 in terms of their usefulness with respect to Q 0 . Table 1 shows another reference question Q 5 from our dataset, together with its annotated group of questions Q 6 to Q 20 . In order to make the annotation process easier and reproducible, we divide it into two levels of annotation. During the first annotation stage (L 1 ), each question group is partitioned manually into 3 subgroups of questions: • P is the set of paraphrasing questions.
• U is the set of useful questions.
• N is the set of neutral questions.
A question is deemed useful if its expected answer may overlap in information content with the expected answer of the reference question. The expected answer of a neutral question, on the other hand, should be irrelevant with respect to the reference question. Let Q r be the reference question, Q p ∈ P a paraphrasing question, Q u ∈ U a useful question, and Q n ∈ N a neutral question. Then the following relations are assumed to hold among these questions: 1. Q p ≻ Q u |Q r : a paraphrasing question is more useful than a useful question.
2. Q u ≻ Q n |Q r : a useful question is more useful than a neutral question.
We also assume that, by transitivity, the following ternary relations also hold: Q p ≻ Q n |Q r , i.e. a paraphrasing question is more useful than a neutral question. Furthermore, if Q p 1 , Q p 2 ∈ P are two paraphrasing questions, this implies Q p 1 = Q p 2 |Q r . For the vast majority of questions, the first annotation stage is straightforward and noncontroversial. In the second annotation stage (L 2 ), we perform a finer annotation of relations between questions in the middle group U. Table 1 shows two such relations (using indentation): Q 8 ≻ Q 9 |Q 5 and Q 8 ≻ Q 10 |Q 5 . Question Q 8 would have been a rephrasing of the reference question, were it not for the noun "art" modifying the focus noun phrase "summer camp". Therefore, the information content of the answer to Q 8 is strictly subsumed in the information content associated with the answer to Q 5 . Similarly, in Q 9 the focus noun phrase is further specialized through the prepositional phrase "for girls". Therefore, (an answer to) Q 9 is less useful to Q 5 than (an answer to) Q 8 , i.e. Q 8 ≻ Q 9 |Q 5 . Furthermore, the focus "art summer camp" in Q 8 conceptually subsumes the focus "summer camps for singing" in Q 10 , therefore Q 8 ≻ Q 10 |Q 5 . Table 2 below presents the following statistics on the annotated dataset: the number of reference questions (Q r ), the total number of paraphrasings (P), the total number of useful questions (U), the total number of neutral questions (N ), and the total number of more useful than ordered pairs encoded in the dataset, either explicitly or through transitivity, in the two annotation levels L 1 and L 2 .

Question Ranking Methods
An ideal question ranking method would take an arbitrary triplet of questions Q r , Q i and Q j as input, and output an ordering between Q i and Q j with respect to the reference question Q r , i.e. one of Q i ≻ Q j |Q r , Q i = Q j |Q r , or Q j ≻ Q i |Q r . One approach is to design a usefulness function u(Q i , Q r ) that measures how useful question Q i is for the reference question Q r , and define the more useful than (≻) relation as follows: If we define I(Q) to be the information need associated with question Q, then u(Q i , Q r ) could be defined as a measure of the relative overlap between I(Q i ) and I(Q r ). Unfortunately, the information need is a concept that, in general, is defined only intensionally and therefore it is difficult to measure. For lack of an operational definition of the information need, we will approximate u(Q i , Q r ) directly as a measure of the similarity between Q i and Q r . The similarity between two questions can be seen as a special case of text-to-text similarity, consequently one possibility is to use a general text-to-text similarity function such as cosine similarity in the vector space model (Baeza-Yates and Ribeiro-Neto, 1999): Here, Q i and Q r denote the corresponding tf×idf vectors. As a measure of question-to-question similarity, cosine has two major drawbacks: 1. As an exclusively lexical measure, it is oblivious to the meanings of words in each question.
2. Questions are treated as bags-of-words, and thus important structural information is missed.

Meaning Aware Measures
The three questions below illustrate the first problem associated with cosine similarity. Q 22 and Q 23 have the same cosine similarity with Q 21 , they are therefore indistinguishable in terms of their usefulness to the reference question Q 21 , even though we expect Q 22 to be more useful than Q 23 (a place that sells hydrangea often sells other types of plants too, possibly including cacti). To alleviate the lexical chasm, we can redefine u(Q i , Q r ) to be the similarity measure proposed by (Mihalcea et al., 2006) as follows: Since scaling factors are immaterial for ranking, we have ignored the normalization constant contained in the original measure. For each word w ∈ Q i , maxSim(w, Q r ) computes the maximum semantic similarity between w and any word w r ∈ Q r . The similarity scores are then weighted by the corresponding idf's, and normalized. A similar score is computed for each word w ∈ Q r . The score computed by maxSim depends on the actual function used to compute the word-to-word semantic similarity. In this paper, we evaluated four of the knowledge-based measures explored in (Mihalcea et al., 2006): wup (Wu and Palmer, 1994), res (Resnik, 1995), lin (Lin, 1998), and jcn (Jiang and Conrath, 1997). Since all these measures are defined on pairs of WordNet concepts, their analogues on word pairs (w i , w r ) are computed by selecting pairs of WordNet synsets (c i , c r ) such that w i belongs to concept c i , w r belongs to concept c r , and (c i , c r ) maximizes the similarity function. The measure introduced in (Wu and Palmer, 1994) finds the least common subsumer (LCS) of the two input concepts in the WordNet hierarchy, and computes the ratio between its depth and the sum of the depths of the two concepts: wup(ci, cr) = 2 * depth(lcs(ci, cr)) depth(ci) + depth(cr) Resnik's measure is based on the Information Content (IC) of a concept c defined as the negative log probability − log P (c) of finding that concept in a large corpus: res(ci, cr) = IC(lcs(ci, cr)) Lin's similarity measure can be seen as a normalized version of Resnik's information content: lin(ci, cr) = 2 * IC(lcs(ci, cr)) IC(ci) + IC(cr) Jiang & Conrath's measure is closely related to lin and is computed as follows: jcn(ci, cr) = [IC(ci) + IC(cr) − 2 * IC(lcs(ci, cr))] −1

Structure Aware Measures
Cosine similarity, henceforth referred as cos, treats questions as bags-of-words. The metameasure proposed in (Mihalcea et al., 2006), henceforth called mcs, treats questions as bagsof-concepts. Consequently, both cos and mcs may miss important structural information. If we consider the question Q 24 below as reference, question Q 26 will be deemed more useful than Q 25 when using cos or mcs because of the higher relative lexical and conceptual overlap with Q 24 . However, this is contrary to the actual ordering Q 25 ≻ Q 26 |Q 24 , which reflects that fact that Q 25 , which expects the same answer type as Q 24 , should be deemed more useful than Q 26 , which has a different answer type.
Q 24 What are some good thriller movies?
Q 25 What are some thriller movies with happy ending?
Q 26 What are some good songs from a thriller movie?
The analysis above shows the importance of using the answer type when computing the similarity between two questions. However, instead of relying exclusively on a predefined hierarchy of answer types, we have decided to identify the question focus of a question, defined as the set of maximal noun phrases in the question that corefer with the expected answer. Focus nouns such as movies and songs provide more discriminative information than general answer types such as products. We use answer types only for questions such as Q 27 or Q 28 below that lack an explicit question focus. In such cases, an artificial question focus is created from the answer type (e.g. location for Q 27 , or method for Q 28 ) and added to the set of question words.
Q 27 Where can I buy a good coffee maker?
Q 28 How do I make a pizza?
Let qsim be a general bag-of-words question similarity measure (e.g. cos or mcs). Furthermore, let wsim by a generic word meaning similarity measure (e.g. wup, res, lin or jcn). The equation below describes a modification of qsim that makes it aware of the questions focus: Here, Q i and Q r refer both to the questions and their sets of words, while f i and f r stand for the corresponding focus words. We define qsim to return 1 if one of its arguments is an empty set, i.e. qsim(∅, ) = qsim( , ∅) = 1. The new similarity measure qsim f multiplies the semantic similarity between the two focus words with the bag-of-words similarity between the remaining words in the two questions. Consequently, the word "movie" in Q 26 will not be compared with the word "movies" in Q 24 , and therefore Q 26 will receive a lower utility score than Q 25 . In addition to the question focus, the main verb of a question can also provide key information in estimating question-to-question similarity. We define the main verb to be the content verb that is highest in the dependency tree of the question, e.g. buy for Q 27 , or make for Q 28 . If the question does not contain a content verb, the main verb is defined to be the highest verb in the dependency tree, as for example are in Q 24 to Q 26 . The utility of a question's main verb in judging its similarity to other questions can be seen more clearly in the questions below, where Q 29 is the reference: Q 29 How can I transfer music from iTunes to my iPod?
Q 30 How can I upload music to my iPod?
Q 31 How can I play music in iTunes?
The fact that upload, as the main verb of Q 30 , is more semantically related to transfer (upload is a hyponym of transfer in WordNet) is essential in deciding that Q 30 ≻ Q 31 |Q 29 , i.e. Q 30 is more useful than Q 31 to Q 29 . Like the focus word, the main verb can be incorporated in the question similarity function as follows: The new measure qsim f v takes into account both the focus words and the main verbs when estimating the semantic similarity between questions. When decomposing the questions into focus words, main verbs and the remaining words, we have chosen to multiply the corresponding similarities instead of, for example, summing them. Consequently, a close to zero score in each of them would drive the entire similarity to zero. This reflects the belief that question similarity is sensitive to each component of a question.

Experimental Evaluation
We use the question ranking dataset described in Section 2 to evaluate the two similarity measures cos and mcs, as well as their structured versions cos f , cos f v , mcs f , and mcs f v . We report one set of results for each of the four word similarity measures wup, res, lin or jcn. Each question similarity measure is evaluated in terms of its accuracy on the set of ordered pairs for each of the two annotation levels described in Section 2. Thus, for the first annotation level (L 1 ) , we evaluate only over the set of relations defined across the three  Table 3: Accuracy results, with and without meaning and structure information.
sets R, U, and N . If Q i ≻ Q j |Q r is a relation specified in the annotation, we consider the tuple Q i , Q j , Q r correctly classified if and only if u(Q i , Q r ) > u(Q j , Q r ), where u is the question similarity measure (Section 3). For the second annotation level (L 2 ), we also consider the relations annotated between useful questions inside the group U.
We used the NLTK 1 implementation of the four similarity measures wup, res, lin or jcn. The idf values for each word were computed from frequency counts over the entire Wikipedia. For each question, the focus is identified automatically by an SVM tagger trained on a separate corpus of 2,000 questions manually annotated with focus information. The SVM tagger uses a combination of lexico-syntactic features and a quadratic kernel to achieve a 93.5% accuracy in a 10-fold cross validation evaluation on the 2,000 questions. The main verb of a question is identified deterministically using a breadth first traversal of the dependency tree.
The overall accuracy results presented in Table 3 show that using the focus word improves the performance across all 8 combinations of question and word similarity measures. For cosine similarity, the best performing system uses the focus words and Resnik's similarity function to obtain a 3.4% increase in accuracy. For the meaning aware similarity mcs, the best performing system uses the focus words, the main verb and Lin's word similarity to achieve a 4.1% increase in accuracy. The improvement due to accounting for focus words is consistent, whereas adding the main verb seems to improve the performance only for mcs, although not by a large margin. The second level of annotation brings 261 more relations in the dataset, some of them more difficult to annotate when compared with the three groups in the first level. Nevertheless, the performance either remains the same (somewhat expected due to the relatively small number of additional relations), or is marginally better. The random baseline -assigning a random similarity value to each pair of questions -results in 50% accuracy. A somewhat unexpected result is that mcs does not perform better than cos on this dataset. After analysing the result in more detail, we have noticed that mcs seems to be less resilient than cos to variations in the length of the questions. The Microsoft paraphrase corpus was specifically designed such that "the length of the shorter of the two sentences, in words, is at least 66% that of the longer" (Dolan and Brockett, 2005), whereas in our dataset the two questions in a pair can have significantly different lengths 2 .
The questions in each of the 60 groups have a high degree of lexical overlap, making the dataset especially difficult. In this context, we believe the results are encouraging. We expect to obtain further improvements in accuracy by allowing relations between all the words in a question to influence the overall similarity measure. For example, question Q 19 has the same focus word as the reference question Q 5 (repeated below), yet the difference between the focus word prepositional modifiers makes it a neutral question.
Q 5 What's a good summer camp to go to in FL? Q 19 What's a good summer camp in Canada?
Some of the questions in our dataset illustrate the need to design a word similarity function specifically tailored to reflect how words change the relative usefulness of a question. In the set of questions below, in deciding that Q 33 and Q 34 are more useful than Q 36 for the reference question Q 32 , an ideal question ranker needs to know that the "Mayflower Hotel" and the "Queensboro Bridge" are in the proximity of "Midtown Manhattan", and that proximity relations are relevant when asking for directions. A coarse measure of proximity can be obtained for the pair ("Manhattan", "Queensboro Bridge") by following the meronymy links connecting the two entities in WordNet. However, a different strategy needs to be devised for entities such as "Mayflower Hotel", "JFK", or "La Guardia" which are not covered in WordNet.
Q 32 What is the best way to get to Midtown Manhattan from JFK?
Q 33 What's the best way from JFK to Mayflower Hotel?
Q 34 What's the best way from JFK to Queensboro Bridge?
Q 35 How do I get from Manhattan to JFK airport by train?
Q 36 What is the best way to get to LaGuardia from JFK?
Finally, to realize why question Q 35 is useful one needs to know that, once directions on how to get by train from location X to location Y are known, then normally it suffices to reverse the list of stops in order to obtain directions on how to get from Y back to X.

Future Work
We plan to integrate the entire dependency structure of the question in the overall similarity measure, possibly by defining kernels between questions in a maximum margin model for ranking.
We also plan to extend the word similarity functions to better reflect the types of relations that are relevant when measuring question utility, such as proximity relations between locations. Furthermore, we intend to take advantage of databases of interrogative paraphrases and paraphrase patterns that were created in previous research on question reformulation.

Conclusion
We presented a novel question ranking task in which previously known questions are ordered based on their relative utility with respect to a new, reference question. We created a dataset of 60 groups of questions 3 annotated with a partial order relation reflecting the relative utility of questions inside each group, and used it to evaluate the ranking performance of several meaning and structure aware utility functions. Experimental results demonstrate the importance of using structural information in judging the relative usefulness of questions. We believe that the new perspective on ranking questions has the potential to significantly improve the usability of social QA sites.