Multi-field search query ranking using scoring statistics

A computerized method comprising using hardware processor(s) for receiving, from a computerized search engine, digital input data comprising a group of relevancy score sets, where each relevancy score set comprises scores associated with computerized search terms and search field pairs found in electronic documents. Two or more statistical values are computed of the relevancy score sets, one or more of the two or more statistical values for each relevancy score set. Based on some of the two or more statistical values, some relevancy scores sets are reduced from the group to create a reduced group. The reduced group is sent to the computerized search engine for presenting a search result to a user on a computer display.

BACKGROUND

The invention relates to the field of information retrieval (IR).

Many information retrieval tasks involve retrieving documents based on multiple search terms, each searched for in many electronic documents. Each document may include multiple fields, each with a document field index, such as a tag, and a field text content. For example, searching for terms in the author, title, and abstract field among multiple documents. Each search term may include a search field index and a text string, the search field index indicating the document field to search in each electronic document for the text string. For example, a search term may be directed to search in an author name field for a text string “Tom Jones”, a second search term may be directed to search in a keyword field for a text string “valve failure”, and these terms are searched for in multiple electronic documents, such as a corpus of electronic documents. Within each document the search terms are searched for in the document author field, the document keyword field, and the like. Thus searches are performed routinely in medical record databases, maintenance systems, patent databases, academic journal articles, newspaper articles, online shopping sites, problem management records, and the like.

Methods for searching multiple fields of documents, such as multi-field searches, structured queries, or the like, may be performed using basic IR scoring techniques, such as field concatenation techniques, field combination techniques, divergence from randomness techniques, probabilistic techniques, fusion techniques, and/or the like.

SUMMARY

There is provided, in accordance with some embodiments, a computerized method comprising using one or more hardware processors for receiving, from a computerized search engine, digital input data comprising a group of relevancy score sets, where each relevancy score set comprises two or more scores associated with one of two or more computerized search terms and one of two or more search fields pair found in two or more electronic documents. The hardware processor(s) are used for computing two or more statistical values of the relevancy score sets, one or more of the two or more statistical values for each relevancy score set. The hardware processor(s) are used for reducing, based on some of the two or more statistical values, some relevancy scores sets from the group to create a reduced group. The hardware processor(s) are used for sending the reduced group to the computerized search engine for presenting a search result to a user on a computer display.

Optionally, the reduced group consists of a final relevancy scoring of some of the two or more electronic documents.

Optionally, the reducing comprises normalizing a statistical distribution of at least some members of the group.

Optionally, the reducing comprises pruning all relevance scores from the group that have a distribution equal to one or more member of the group consisting of a uniform distribution, a null distribution, and an abnormal distribution.

Optionally, the reducing comprises segmenting the group into two or more subgroups based on at least some of the two or more statistical values. For each subgroup, the relevancy scores of the subgroup are combined using information retrieval fusion techniques specific to the at least some of the two or more statistical values, to produce two or more fused relevancy scores. The two or more fused relevancy scores are combined to produce the reduced group.

Optionally, the reducing comprises segmenting the group into two or more subgroups based on statistical distribution type. For each subgroup, the relevancy scores of the subgroup are combined using information retrieval fusion techniques specific to the statistical distribution type, to produce two or more fused relevancy scores. The two or more fused relevancy scores are combined to produce the reduced group.

Optionally, the reducing comprises segmenting the group into two or more subgroups based on statistical distribution types. For each subgroup, the relevancy scores of each member of the subgroup are transformed to an approximately normal distribution using a transformation specific to respective the statistical distribution type. For each subgroup, the relevancy scores of the subgroup are combined using information retrieval fusion techniques, to produce two or more fused relevancy scores. The two or more fused relevancy scores are combined to produce the reduced group.

The embodiments of the above method may be implemented as computerized method embodiments, incorporated into computerized system embodiments, as computer program product embodiments, as software-as-a-service embodiments, and/or the like.

DETAILED DESCRIPTION

Disclosed herein are methods, systems, and computer program products for performing a multiple term search query in multiple electronic documents, each search term comprising a field tag and each electronic document comprising multiple document fields. For conciseness, the methods will be described, but these descriptions apply equally to embodiments of methods, systems, and products. The disclosed methods receive from an information retrieval system, such as a computerized search engine, the scoring results of multiple terms, associated with multiple search fields, searched for in multiple document fields of multiple electronic documents. The collection of electronic documents may be referred to as a corpus of electronic documents, or simply corpus. As used herein, the term “field combination pair”, or FCP means a particular single combination pair of a search field index and a document field.

This application describes fusion methods for generating multi-field search query results, improved over previously existing techniques. For each FCP score set of the corpus, statistical values are analyzed, computed, modelled, and/or the like. By applying one or more similarity rules to the statistical values, distributions, and/or the like, the number of relevant search results, such as the query results, may be reduced and the ranking of the relevant search results improved. As used herein, the terms FCP(s) and FCP score set(s) may be used interchangeably to mean the FCP score set(s).

These similarity rules may be ordered on a statistical complexity scale. A zeroth-order similarity rule may be an irrelevancy rule, represented by statistical distribution that is flat, uniform, non-existent, and the like. For example, when an FCP score set has no results, the irrelevancy rule removes this score set from further consideration in the fusion process. For example, the zeroth order rule removes trivial score sets from further consideration, such as score sets with no distribution, uniform distribution, no scores, not enough scores to determine a statistically significant distribution rule, and/or the like.

A first-order similarity rule compares the mean and standard deviation of each FCP score set distribution, normalizes the means of each distribution, and segregates the FCP score sets into similar variance subgroups, such as by comparing to thresholds, clustering techniques, quartile techniques, and/or the like. Each subgroup is then fused using known fusion techniques, and the fused results are fused together.

These similarity rules may be applied individually or in ordered combinations to the FCP score results to reduce the number of irrelevant query results, improve the relevancy ranking of the query results, increase processing time, and/or the like. For example, when the query is a complex query comprising multiple fields and multiple terms, and when the corpus is a very large collection of electronic documents, such as used in data mining applications, the score results may be multidimensional and different FCPs exhibiting different statistical properties, such as mean, variance, distribution shape, and/or the like. By taking into account these statistical properties as part of the fusion process the query results may be more relevant to the search goal of the user, saving computer time in processing combining multi-field scores from multiple documents, user time in reviewing the search query results to find achieve the search goal, and/or the like.

For example, a search score is computed for each search term of 20 search terms in each field of 10 fields of each document in a corpus of 5 million of documents, producing 200 FCP score sets each comprising 5 million scores. This score data can be arranged in a multidimensional matrix, such as a 20×10×5,000,000 matrix. Each element of the first two dimensions (20×10) is one of the 200 FCP score sets and each 5,000,000 vector can be analyzed to compute an FCP score set distribution.

Reference is now made toFIG. 1, which is a schematic illustration of a system100for multi-field search query ranking using scoring statistics. Electronic document relevancy ranking system100comprises one or more hardware processors101, a network interface110, a non-transitory computer readable storage medium102, and a user interface111. Network interface is configured to allow access to a computer network, and thereby access to network attached storage120, other servers130, such as an information retrieval system, a computerized search engine, and/or the like. Storage medium102has encoded thereon software modules comprising processor instructions, such as a relevancy score evaluator102A, a relevance score reducer102B, and/or the like. Relevancy score evaluator102A is adapted to (such as by comprising processor instructions that when executed on a hardware processor instruct the hardware processor to) receive digital input data, such as two or more sets of relevancy score values, one for each combination of a search field of a search field term and a document field in a corpus of electronic documents. Relevancy score evaluator102A is also adapted to compute statistical values for each of the relevancy score sets. Relevance score reducer102B is adapted to receive the statistics and automatically determine which statistical similarity rules to use in reducing the number of relevancy score sets. Optionally, the processor instructions may be partitioned into similar of different software modules.

Reference is now made toFIG. 2, which is a flowchart of a method200for multi-field search query ranking using scoring statistics. Relevance scores (i.e. digital input data) are received201from internal or external IR system130by hardware processor101. Relevancy score evaluator102A comprises instructions adapted to compute202statistics for each FCP score set. The statistics are used to reduce203the FCP score set, and the subset of remaining FCP scores are sent to IR system130for presentation of the electronic document relevancy rankings and/or scores. Optionally, IR system130performs further score set reduction, fusion, and/or the like before presenting the search query results to the user.

Reference is now made toFIG. 3A, which is a flowchart of a pruning embodiment300for query results reduction using scoring statistics. Pruning embodiment300is a specific embodiment of score reduction203. A rule is applied to determine when301the statistical distribution is flat, such as a uniform distribution, a non-existent distribution, a zero variance distribution, and/or the like. When the FCP distribution is flat the score set is pruned302, and when not the scores are kept303, and returned for optional further rule application and/or processing.

Reference is now made toFIG. 3B, which is a flowchart of a variance embodiment310for query results reduction using scoring statistics. Variance embodiment310is a specific embodiment of score reduction203. After statistic computation202, FCP scores may be normalized311, and segmented312according to variance into groups of similar variance, such as by using a threshold(s), clustering, peak finding, and/or the like. Fusion methods, such as CombMIN, CombMAX, CombMED, CombANZ, CombSUM, CombMNZ, or the like, may be used to combine the score sets within each segment, and then the results of all segments fused together with similar methods. This may reduce the effect of irrelevant search results on the final electronic document rankings.

Reference is now made toFIG. 3C, which is a flowchart of a distribution transformation embodiment320for query results reduction using scoring statistics. Distribution transformation embodiment320is a specific embodiment of score reduction203. FCP score sets may be segmented321by distribution types, such as normal distributions, Poisson distributions, Binomial distributions, and the like. Each distribution may then be transformed322to a normal or pseudo-normal distribution. The scores may then be normalized323, fused within each variance segment324, and fused across segments325as in variance embodiment310.

Reference is now made toFIG. 3D, which is a flowchart of an iterative embodiment330for query results reduction using scoring statistics. Iterative embodiment330is a specific embodiment of score reduction203. Optionally, score sets may be normalized331, and some score sets may be segmented332by a statistical value, fused333, and then returned to the group of FCP sets. This process continues until only one score set remains.

Reference is now made toFIG. 3E, which is a flowchart of a segregating embodiment340for query results reduction using scoring statistics. Segregating embodiment340is a specific embodiment of score reduction203. In this embodiment, score sets are segmented341, normalized342, fused within each segment343, and then fused344across segments.

Multiple embodiments of the score set reduction step may be used together, for example first applying a pruning step, and then a variance clustering step.

Following are detailed examples of application of the methods described hereinabove.

Searching a problem management record (PMR) database for a previous relevant management problem may involve searching multiple combinations of PMR problem aspects and technical documents to find one or more best matches. Alternative solutions to this problem may use different approaches including both state-of-the-art and novel QA, NLP, deep-learning and learning-to-rank techniques. A “multi-field” retrieval approach may allow consideration of cross field querying options, while focus on those field combinations that are relevant to answering the PMR query.

Following is an example PMR query and a corresponding relevant technote:

PMR:{ID:”*****-***-***_***-**-**”,PRODUCT_DESC:”Tivoli Federated Identity MGR”,COMPONENT_DESC:”SAM WebSEAL”,OS:”Appliance Formware”,BUSINESS_IMPACT:”Trying to simplify management of our WebSEALenvironments”,PROBLEM_TITLE:”Curl/JSON scripting assistance”,PROBLEM_DESC:”I am looking for information and best practicesaround using Curl and JSON scripts to do administrative tasks onWebSEAL...”}Technote:{URL:http://ww-01.ibm.com/support/document.wss?uid=swg21663434TITLE:”IBM Security Access Manager for Web API Documentation”}

Existing IR techniques for handling multi-field queries have been described as part of the INitiative for the Evaluation of eXtensible markup language retrieval (INEX), as described by Fuhr et al. in “INEX: INitiative for the Evaluation of XML Retrieval” published in The Proceedings of the SIGIR 2002 Workshop on XML and Information Retrieval.

For example, language model (LM) approaches may include a concatenation (standard) model, a combination LM, a fielded LM, and the like, as described by Azzopardi et al. in “Query intention acquisition: A case study on automatically inferring structured queries” published in The Proceedings the Dutch-Belgium Information Retrieval Workshop 2006.

Concatenation (standard) models may concatenate textual fields into a single meta-field, and search for terms as a single query using the standard LM query-likelihood approach:

p⁡(q|θd)=∏t∈q⁢{(1-λ)⁢p⁡(t|d)+λ⁢⁢p⁡(t)}n⁡(t,q)
A drawback of this approach is the inability to accommodate the relative importance of the various search terms embedded within a multi-field query.

A Combination LM may smooth over multiple document fields using the equation:

This approach needs to estimate p(xld) which may require training data. With the lack of training data, p(xld)=1/|X| if field x exists in document d.

Fielded LMs assume that the field generative process (i.e., p(xld)) is independent and extends the basic LM approach with concurrent field generation:

The log of this formula may be equivalent to the CombSUM fusion approach over multiple LM models, one per each field.

Another approach, alternative to the LMs, may be based on an extension to the Divergence From Randomness (DFR) method described by Plachouras et al. in “Multinomial randomness models for retrieval with document fields” published in the Proceedings of the 29th European conference on IR research (ECIR), 2007, pages 28-39, Springer-Verlag, Berlin, Heidelberg, ISBN: 978-3-540-71494-1. The extension is based on a multinomial distribution over multifield term occurrence events:

Pℳ⁡(t∈d|D)=(TFtf1tf2⁢⁢…⁢⁢tfktf′)⁢p1tf1⁢p2tf2⁢⁢…⁢⁢pktfk⁢pnf′
where term generation may occur in a random process over multiple generators (fields). Such an approach may be implemented in Apache/Lucene DFRSimilarity class objects.

Another approach is Okapi Best Matching (BM) 25F, an extension to the BM25 probabilistic scoring model that considers multiple fields:

BM⁢⁢25⁢Fd=∑t∈q⋂d⁢tf⁡(t,d)k1+tf⁡(t,d)·idf⁡(t)tf⁡(t,d)=∑c∈d⁢wc·tfc⁡(t,d)
The BM25F model may be similar to the Concatenation LM approach, with a slight change that terms are duplicated according to a predefined boosting factor, such as a weight value. This approach may require learning techniques to determine the term boosts (weights) for all fields.

An alternative to extensions of existing IR models is the use of fusion (metasearch) approaches. Within a fusion approach, each FCP may be searched for independently, and then the scores are combined using one of many score fusion methods. An initial step to fusion is score normalization, such as sum-norm, 0-1 norm, and the like, which transforms scores of various FCPs so they can be comparable on the same scale. Common fusion approaches are CombSUM, CombMNZ, and the like. CombSUM sums over various FCP scores, CombMNZ boosts (weights) the score by the number of FCPs a given electronic document satisfies, and the like. Other more sophisticated fusion approaches may be applied based on an available training data, such as Weighted CombSUM, LambdaMerge, and/or the like.

Fusion approaches may require training data for devising a learning to rank algorithm that can effectively accommodate all FCPs. The lack of experimentation with multi-field queries that include many FCPs such as found in projects with problem management records (PMRs). Common to such approaches is a simple evaluation over very small number of FCPs, such as title, description, anchor-text, and the like, as in the case of Text REtrieval Conference (TREC) and/or INEX data, which may not be robust enough nor provide satisfactory retrieval quality.

Similar to fusion approaches, the proposed methods are transparent to the actual base IR model(s) and/or scoring techniques employed to each FCP, such as LM, DFR, BM25, term frequency—inverse document frequency (TF-IDF), or the like. Therefore, many different IR scores may be accommodated within a generic scoring framework, optionally simultaneously.

The zeroth-order similarity rule may filter FCPs that may not provide an actual benefit in electronic document ranking and information retrieval. More specifically, for example, filtering results retrieved for FCPs with zero variance or exhibit approximately random scoring process, may be discarded from the query with no effect on the overall retrieval quality. Furthermore, zeroth similarity rule score set result pruning helps to obtain a less noisy overall document score for the final ranking which may be better integrated into additional query processing pipelines, such as applying a re-ranking approach on the base multi-field search results and the like. Zeroth-order rules may be used to filter (ie prune) unnecessary query FCPs to improve overall retrieval quality. The pruning rules may filter out scores that may not have a desired statistical distribution, such as a Gaussian distribution, binomial distribution, and the like, may. Thus, a FCP score set is pruned when the scores for that FCP do not fit the chosen statistical distribution.

The first-order rule may allow some specific query FCP score sets to dominate others, such as when search terms of title fields are more important than those of description fields. Thus, but clustering FCP score sets, for example by variance categories or bins, FCPs of similar relevance can be fused first before fusing the category results together. For example, the FCPs are ranked, and then grouped into two groups. Each group is fused, and then the combined results are fused together. For example, ranker selection is used to group FCPs into weak and strong, such as when a weak FCP means an FCP with a larger variance and a strong FCP means an FCP with a smaller variance. Alternatively, distributions of scores in a FCPs are clustered statistically to determine FCP groups.

By combining the different order statistical property rules, multi-field queries in may allow automated and unsupervised performance which may perform better than state-of-the-art techniques.

Let F be the list of query FCPs and let score(qld,f) be the “relevance” score of document d to query q given FCP f in F. The function score(qld,f) of different FCPs can be determined by any base information retrieval approach, such as LM, TF-IDF, and/or the like.

For example, the top-N, such as N=5000, score results are retrieved for each FCP in F. Select a single dominant FCP from F, denoted qf, for example such a selection may be done either manually, using title as the dominant field, or automatically using an existing Query Performance Prediction (QPP) method. Optionally, each score result list of FCP fin F\{qf} may be pruned using one of many pruning rules. For example, a “Hard” pruning rule is when the variance of observed FCP f document scores is 0. For example, a “Soft” pruning rule is found by letting U[min,max] be a uniform distribution with min the minimum document score in FCP f and max is the maximum. A “goodness of fit” test is performed, such as a Kolmogorov-Smirnov Test, with a null hypothesis of distribution(score(qld,f)) equal to U[min,max]. Let pv be the p-value of the test. When (pv>1−conf_level) then prune f (common conf_level is 95% for statistical significance).

Before applying a first order rule the FCPs may be normalized such as using a 0-1 normalization, i.e. (score(qld,f)−min)/(max−min)). The FCP score sets of each cluster/bin/group may be combined using a weighted CombMNZ approach with weights determined, such as automatically with no supervision, by a QPP predictor. Specifically, the QPP weight found to be effective for this step is (score(qld1,f)−min)/((score(qld2,f)−min), where d1 and d2 are the documents ranked at the first and second place according to score(qld,f). Since there may be many FCPs, comparing to regular NZ factor which counts on lists we further log-scale it to get a concave factor (i.e., Log 2(1+NZ)). The top-N highest scored electronic documents are retained for each cluster/bin/group.

The results from each fused cluster/bin/group, such as weak FCP fusion results with dominant FCP results, may be performed using a weighted CombSUM approach. For example, by sum-normalizing the fused scores. Weights may be determined using the same QPP (s) as described hereinabove.

Optionally, iterative grouping and fusion of FCPs with similar statistics is performed. For example, a QDD method is used to group similar score sets and each group is fused using existing methods. Ranks of the fused results may be compared by measuring by different ranker methods for sets of different queries. The less correlation in ranks between FCPs, such as measured using rank-correlation methods, the less chance two FCPs have to correlate. In this manner, sub-groups may be segregated that may have similar documents and/or ranks. This may mean that two lists in the same sub-group represent ranking results that are “like-minded”. For example, the fusion approach is as follows:a) Segregate FCPs into sub-groups.b) Within each subgroup, perform internal fusion, such as using CombMNZc) Combine subgroups so as to maximize quality, such as by applying a principle of similar performance/independence in decisions.d) repeat steps 2-3 until only one relevancy score set remains.

As an evaluation example for the effectiveness of this approach, a more traditional approach is compared that is similar to the combination LM and CombSUM approaches that were described above (with p(xld)=1/|X|). In the traditional approach a P@1 value of 0.196 was achieved, and a MAP@20 value was 0.236. In the new approach escribed herein, the P@1 value was 0.256 (+30.6%), and the MAP@20 value was 0.296 (+25.4%).