TRAINING PARSERS TO APPROXIMATELY OPTIMIZE NDCG
First Claim
1. A method to be executed at least in part in a computing device for training a parser to optimize search operations, the method comprising:
- receiving a query and a plurality of returned documents with relevance judgments;
parsing the query and the documents to obtain parse trees;
computing tree edit distances for each query-document pair based on the parse trees;
incorporating the tree edit distances to a ranking function employed for ranking the documents for the received query;
determining updated parser parameters from the ranking function; and
updating the parser with the updated parser parameters in an iterative manner until a predefined threshold is reached.
2 Assignments
0 Petitions
Accused Products
Abstract
A supervised technique uses relevance judgments to train a dependency parser such that it approximately optimizes Normalized Discounted Cumulative Gain (NDCG) in information retrieval. A weighted tree edit distance between the parse tree for a query and the parse tree for a document is added to a ranking function, where the edit distance weights are parameters from the parser. Using parser parameters in the ranking function enables approximate optimization of the parser'"'"'s parameters for NDCG by adding some constraints to the objective function.
20 Citations
20 Claims
-
1. A method to be executed at least in part in a computing device for training a parser to optimize search operations, the method comprising:
-
receiving a query and a plurality of returned documents with relevance judgments; parsing the query and the documents to obtain parse trees; computing tree edit distances for each query-document pair based on the parse trees; incorporating the tree edit distances to a ranking function employed for ranking the documents for the received query; determining updated parser parameters from the ranking function; and updating the parser with the updated parser parameters in an iterative manner until a predefined threshold is reached. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computing device for training a parser to optimize search operations, the computing device comprising:
-
a memory storing instructions; a processor coupled to the memory, the processor executing a search engine in conjunction with the instructions stored in the memory, wherein the search engine is configured to; receive a query and a plurality of returned documents with relevance judgments; initialize parser parameters of the parser heuristically; parse the query and the documents to obtain parse trees; compute tree edit distances for each query-document pair based on the parse trees; incorporate the tree edit distances to a ranking function employed for ranking the documents for the received query; collect counts for a parser parameter gradient descent to determine updated parser parameters for optimizing a Normalized Discount Cumulative Gain (NDCG) of the search engine; and update the parser with the updated parser parameters in an iterative manner until a predefined threshold is reached. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
-
18. A computer-readable storage medium with instructions stored thereon for supervised training of a dependency parser to optimize search operations, the instructions comprising:
-
receiving a query and a plurality of returned documents with relevance judgments; initializing parser parameters of the parser heuristically; parsing the query and the documents to obtain parse trees; computing tree edit distances for each query-document pair based on the parse trees, wherein each tree edit distance between a query tree and a corresponding document tree is a combination of at least one from a set of;
node insertion, deletion, and substitution operations;incorporating the tree edit distances to a ranking function employed for ranking the documents for the received query; collecting counts for a parser parameter gradient descent to determine updated parser parameters for optimizing a Normalized Discount Cumulative Gain (NDCG) of the search engine; and updating the parser with the updated parser parameters in an iterative manner until a predefined threshold for NDCG optimization is reached. - View Dependent Claims (19, 20)
-
Specification