SIGIR 2007 Proceedings Poster Applying Ranking SVM in Query Relaxation Ciya Liao Oracle Corporation Thomas Chang Oracle Corporation david.liao@oracle.com ABSTRACT We propose an approach QRRS (Query Relaxative Ranking SVM) that divides a ranking function into different relaxation steps, so that only cheap features are used in Ranking SVM of early steps for query efficiency. We show search quality in the approach is improved compared to conventional Ranking SVM. thomas.chang@oracle.com query and a hit document. Only items with the same query are ranked. Each item is represented by a feature vector, which lists features and corresponding feature weights. A feature can be any factor that is used to determine the relevance of a document related to a given query. In general, a feature can be: occurrence of query terms in metadata (title, keyword, description, reference text), occurrence of query terms in content, or static ranks (pagerank or other static ranks, etc). A ranking function accepts an item feature vector and produces a relevancy score for the item. The higher the score, the higher this item will be ranked. Ranking function evaluation normally consists of two steps. The first step is to extract feature vector of the item. The second step is to compute relevancy score based on input feature vector. In practice, the second step can finish with in-memory operations. But feature vector formation has to be done by looking through an inverted index. If the inverted index is too large to put into memory, the costly disk access is necessary. Query relaxation is a method to handle this efficiency challenge. Instead of forming a whole feature vector and using a single ranking function, query relaxation forms several feature vectors, each corresponding to a ranking function for each relaxation step. In executing each step query, feature vector is formed and ranking function is evaluated. To produce the first page of search result, normally of 10 hits, query relaxation steps are executed one after anther until the relaxation steps finish or the first result page is filled up. The union of hit lists from all relaxation steps should consist of all documents hit by the query for completeness. The query relaxation can improve query efficiency and generate hit list with high relevancy, when the following two conditions are satisfied: · · Feature vector formation for early step is cheaper. Early step generates higher relevant hits than in later step. Categories and Subject Descriptors H.3.3 [Information Search and Retrieval]: Information Search and Retrieval ­ Retrieval Models General Terms: Algorithms, Experimentation Keywords Information Retrieval, Query Relaxation, Ranking SVM 1. INTRODUCTION Ranking functions in a search engine should be adjusted for different information needs. In internet web search, ranking functions need to be changed frequently to handle search spams. In enterprise search, different deployments of search systems or different types of search corpora may require different ranking functions. One way to adjust ranking functions is using machine learning methods to automatically train ranking functions. Ranking SVM [1,2] treats the ranking function learning problem as binary classification training. Ranked item pairs are input to learning process. The pair belongs to one class if the first item is ranked higher than the other, and to the other class otherwise. Output is a classification function minimizing classification errors with a large margin. The trained function can be used directly as a ranking function to evaluate the relevancy of a single item. On the other hand, for query response time, query relaxation technique is normally used. It divides a query execution into several subsequent relaxation steps. Sub-query from the first step is executed first. Generated hits will be ranked higher than those from other steps. If the first page of search result is filled up, the whole execution stops. Otherwise, sub-query from the next step is then executed. The process continues until all relaxation steps are executed or the first result page is filled up. Here we propose a new approach: Query Relaxative Ranking SVM (QRRS). We apply Ranking SVM in each relaxation step. Each step has its own learned ranking function. QRRS has quick query response time benefited from its relaxation nature and can also generate more relevant hits compared to no relaxation. The two conditions can be satisfied simultaneously if we choose some metadata as features for early steps. Firstly, the inverted list for metadata can be indexed in separate rows for separate access. Normally metadata index size is much smaller compared to content, therefore smaller data need to be read in metadata step. Secondly, documents that match query terms in those metadata are more relevant than in other metadata or content. In Ranking SVM, a training item pair can be represented by two feature vectors xi, xj. To introduce non-linear kernels, we apply a generic mapping (x) on feature vectors. When (x) = x, it reduces to linear kernel. The training process is to learn a ranking function in the form of w(x), where w is weight vector to be learned. The classification problem is formed by the Ranking SVM as [2,3]: minimize: 2. TECHNIQUE In a search ranking system, a ranked item is a pair consisting of a Copyright is held by the author/owner(s). SIGIR'07, July 23-27, 2007, Amsterdam, The Netherlands. ACM 978-1-59593-597-7/07/0007. 12 w + C k 2 , subject to k 0, w((xi)- (xj)) > 1- k, when xi ranks higher, or w((xj)- (xi)) > 1- k, when xj ranks higher 763 SIGIR 2007 Proceedings Poster where C is a parameter that allows trading-off margin size against training error, k are non-negative slack variables to allow some training error. The only difference between the Ranking SVM and the conventional binary SVM classification is that the single vector is replaced with a pair of vectors:(xi)- (xj). The solution weight vector can be written in the form of training pairs as [1]: metadata query terms occur. For example, a feature can be: if query phrase occurs in title tag, or if all query terms occur proximately in content, etc. The combination results in about 50 different features. We randomly sampled query list and found 100 unique queries. A pool of relevant hits was generated. It was formed by top 30 hits from each of four search engines, which have largely different ranking functions. We asked people to manually evaluate the relevancy of each pooled (query, document) pair. We only formed two relaxation steps. The first step only contains features that involve metadata and link information. The second step contains all features. We randomly chose 50 queries and corresponding feature vectors to train ranking function using SVMlight[2]. Other 50 queries were used to test ranking functions. In Figure 2, we compare the MRR (Mean Reciprocal Rank) for the accuracy of learned ranking functions between QRRS and the Ranking SVM not using query relaxation. We see the ranking accuracy improves with different kernels for QRRS. 0.6 0.5 0.4 0.3 0.2 0.1 0 w * = k t k ( (x i ) - (x j )) * where * can be computed by kernel function of training pairs [1]. From the above equation, the ranking function w*(x) can also be written in the form of kernel k(x, xj) = (x) (xj). In linear kernel case, w* can be computed explicitly, which makes the ranking function just a linear combination with feature weights. To apply the Ranking SVM to query relaxation, we train a separate ranking function for each step from the corresponding feature vector. 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 50000 100000 150000 200000 250000 300000 350000 400000 Number of Documents N Last Step Probability of Relaxing to Last Step Query Response Time First Step MRR Figure 1: Query response time for a two-step relaxation 3. EXPERIMENTS Query efficiency with relaxation is shown in Fig 1 as a simulated experiment. A two-step relaxation is formed, with first step having the metadata features and second step having all the features. Assuming the number of documents hit by the first step obeys binomial distribution with total number of documents N and probability p. The diamond curve shows the probability that the first step cannot return 10 or more than 10 hits with p=0.0001. It smoothly declines as N increases. We assume the response time for each step grows linearly with N. Therefore we can draw two straight lines showing that the response time in the first step grows in a much more gradual slope than in the last step due to index size difference. The simulated response time curve in square symbols grows first in steep slope because the last step is necessary for enough hits. As N increase, more queries only need the first step, the query response time decreases and gradually close to the straight line shown as the trend of first step response time only. The probability p can vary for different queries, if averaging different queries, the transition from the first step to last step will be more blur and last for much longer time. For relevancy test, we used a part of www.oracle.com as experiment collection. It contains about 60000 documents, most of them are html pages. Document metadata (for example: title, keywords, description, etc), content, and link information (for example: reference text) are extracted and indexed. The feature weights are binary values (0 means query does not occur, 1 means query does occur). The features are formed based on combination of linguistic characteristics of occurring query terms and in which Figure 2: Ranking accuracies for learned ranking functions 4. DISCUSSIONS The ranking function learned from the last relaxation step is the same as that learned without using relaxation. So the accuracy improvement from QRRS must be due to the ranking function learned from the first relaxation step, which picks up more relevant document onto hit list top. During the process of learning the first step ranking function, only documents whose metadata matches query terms are treated as training samples. That means, we give different weights (or ranking parameters in [3]) on query and document pairs: 1 for pair that matches metadata, 0 for pair that does not match metadata. The accuracy improvement by assigning different weights on different document query pairs in the Ranking SVM has been shown in [3]. Here we improve ranking accuracy by choosing ranking parameters in a more heuristic way through query relaxation. 5. REFERENCES [1] R. Herbrich, T.Graepel and K.Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115-132. MIT Press, 2000. [2] T. Joachims, Optimizing Search Engines using Clickthrough Data. In SIGKDD, 2002. [3] Y. Cao, J. Xu, T-Y Liu, H. Li, Y. Huan, H-W Hon, Adapting Ranking SVM to Document Retrieval. In SIGIR, 2006. 764 de gr e li de e p nea gr oly r e n 2 de e p om gr oly ial ee no po mi al G lyn au om ss ia G ian l au g= ss 2 G ian au g= G ssia 3 au ss n g =1 ia n g= 0. 5 3 no relaxation w ith relaxation 5