Query Parser Derivation Computing Device and Method for Making a Query Parser for Parsing Unstructured Search Queries

• US 20130031113A1
• Filed: 07/29/2011
• Published: 01/31/2013
• Est. Priority Date: 07/29/2011
• Status: Active Grant

• Current Assignee: Thryv, Inc. (Mudrick Capital Management LP)
• Original Assignee: YellowPages.com LLC (Mudrick Capital Management LP)
• Inventors: Feng, Donghui, Retzer, Clarke, Shanahan, James G., Zajac, Remi, Boydston, Kirk, Murray, Nathaniel A.
• Granted Patent: US 9,218,390 B2
• Time in Patent Office: Days
• US Class Current: 707/755
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A system and method is provided which may comprise parsing an unstructured geographic web-search query into a field-based format, by utilizing conditional random fields, learned by semi-supervised automated learning, to parse structured information from the unstructured geographic web-search query. The system and method may also comprise establishing semi-supervised conditional random fields utilizing one of a rule-based finite state machine model and a statistics-based conditional random field model. Systematic geographic parsing may be used with the one of the rule-based finite state machine model and the statistics-based conditional random field model. Parsing an unstructured local geographical web-based query in local domain may be done by applying a learned model parser to the query, using at least one class-based query log from a form-based query system. The learned model parser may comprise at least one class-level n-gram language model-based feature harvested from a structured query log.

Claims

1. A method comprising:

deriving, via a query parser derivation computing device, a query parser for parsing an unstructured geographic web-search query into a field-based format; and

utilizing, by the query parser, conditional random fields, learned by semi-supervised automated learning, to produce structured information from the unstructured geographic web-search query.

2. The method of claim 1, further comprising:

defining, via the query parser derivation computing device, class-based language model features comprising at least one token appearing in a defined position in a model feature comprising a grouping of tokens of a given length n, where n is an integer, including GEO_UNI_FIRST, for the first token in a grouping of tokens of length one, relating to a geographic term, GEO_BI_FIRST, for the first token in a grouping of tokens of length two relating to a geographic term, GEO_BI_SECOND, for the second token in a grouping of tokens of length two relating to a geographic term, GEO_TRI_FIRST, for the first token in a grouping of tokens of length three relating to a geographic term, GEO_TRI_SECOND, for the second token in a grouping of tokens of length three relating to a geographic term, GEO_TRI_THIRD, for the third token in a grouping of tokens of length three relating to a geographic term, and including ST_UNI_FIRST, for the first token in a grouping of tokens of length one, relating to a search term, ST_BI_FIRST, for the first token in a grouping of tokens of length two relating to a search term, ST_BI_SECOND, for the second token in a grouping of tokens of length two relating to a search term, ST_TRI_FIRST, for the first token in a grouping of tokens of length three relating to a search term, ST_TRI_SECOND, for the second token in a grouping of tokens of length three relating to a search term, ST_TRI_THIRD, for the third token in a grouping of tokens of length three relating to a search term, for tokens relating to one of a geographic term and a search term, for any'"'"' grouping of length n where n is an integer; and

utilizing, via the query parser derivation computing device, the class-based language model features as high-level language model features in deriving the query parser.

3. The method of claim 2, wherein the query parser recognizes both a geographic location token and a search term token in an input query.

4. The method of claim 1, further comprising:

establishing the semi-supervised conditional random fields via one of a rule-based finite state machine model and a statistics-based conditional random field model.

5. The method of claim 4, wherein the semi-supervised conditional random fields are established via utilizing systematic geographic parsing with the one of the rule-based finite state machine model and the statistics-based conditional random field model.

6. The method of claim 4, wherein the statistics-based conditional random field model is utilized with class transition features learned from a labeled set of features and extracting at least one high-level language model as a state feature, thereby allowing at least one learned language model to be learned from at least one large-scale class-based log.

7. The method of claim 4, wherein the rule based finite state machine model is utilized with a phrase level grammar to construct a phrase level grammar composition.

8. The method of claim 7, further comprising:

constructing the phrase level grammar, via the query parser derivation computing device, using a context free grammar composition.

9. The method of claim 4, wherein the semi-supervised conditional random fields are utilized in a linear-chain Markov random field model.

10. The method of claim 9, further comprising:

processing, via the query parser derivation computing device, an input query as a sequence of individual tokens Q=(t1, t2, . . . , tn), with a corresponding labeling sequence of labels for each token (t1, t2, . . . tn), L=(l1, l2, . . . , ln), wherein each label L is defined as respective data, including data from a list comprising search terms, geographic expression, geographic expression relation indication, and uninteresting information; and

finding, via the computing device, the most probable labeling sequence L for the input query Q.

11. The method of claim 10, wherein for each label in L,

12. The method of claim 11, further comprising:

characterizing, via the query parser derivation computing device, a conditional random field model of Q and L as a set of feature functions fk, each having a corresponding weight λ

k and computing via the query parser derivation computing device, the conditional probability

13. The method of claim 12, further comprising:

learning, via the query parser derivation computing device, the state transition feature fk (lt−

1, lt, Q, t) as limited by learning the output state features fk (lt, Q).

14. A method comprising:

deriving a query parser, via a query parser derivation computing device;

utilizing an unstructured local geographical web-based query in local domain by applying a learned model parser to the query.

15. The method of claim 14, wherein the learned model parser uses at least one class-based query log from a form-based query system.

16. The method of claim 15, wherein the learned model parser comprises at least one class-level multi-token language model-based feature harvested from a structured query log.

17. The method of claim 16, wherein the structured query log comprises a class-based log from a form-based query system.

18. The method of claim 14, wherein the learned model parser comprises a learning statistical conditional random field parser.

19. The method of claim 18, wherein the learning statistical conditional random field parser performs at least one of segmenting and labeling query sequence data.

20. A tangible machine readable medium storing instructions, the instructions, when executed by a computing device, causing the computing device to perform a method, comprising:

deriving a query parser by defining class-based language model features comprising at least one token appearing in a defined position in a model feature comprising a grouping of tokens of a given length n, where n is an integer, including GEO_UNI_FIRST, for the first token in a grouping of tokens of length one, relating to a geographic term, GEO_BI_FIRST, for the first token in a grouping of tokens of length two relating to a geographic term, GEO_BI_SECOND, for the second token in a grouping of tokens of length two relating to geographic term, GEO_TRI_FIRST, for the first token in a grouping of tokens of length three relating to a geographic term, GEO_TRI_SECOND, for the second token in a grouping of tokens of length three relating to a geographic term, GEO_TRI_THIRD, for the third token in a grouping of tokens of length three relating to geographic terms, and including ST_UNI_FIRST, for the first token in a grouping of tokens of length one, relating to a search term, ST_BI_FIRST, for the first token in a grouping of tokens of length two relating to a search term, ST_BI_SECOND, for the second token in a grouping of tokens of length two relating to a search term, ST_TRI_FIRST, for the first token in a grouping of tokens of length three relating to a search term, ST_TRI_SECOND, for the second token in a grouping of tokens of length three relating to a search term, ST_TRI_THIRD, for the third token in a grouping of tokens of length three relating to a search term, for tokens relating to one of a geographic term and a search term, for any grouping of length n where n is an integer; and

utilizing the features as high-level language model features for deriving the parser.