Training a probabilistic spelling checker from structured data

• US 8,626,681 B1
• Filed: 01/04/2011
• Issued: 01/07/2014
• Est. Priority Date: 01/04/2011
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jurca, Radu, Fleury, Pascal, Murphy, Bruce Winston
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Wu, Fuming
• Application Number:
  US12/984,484
• Time in Patent Office: 1,099 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A spelling system derives a language model for a particular domain of structured data, the language model enabling determinations of alternative spellings of queries or other strings of text from that domain. More specifically, the spelling system calculates (a) probabilities that the various query entity types—such as STREET, CITY, or STATE for queries in the geographical domain—are arranged in each of the various possible orders, and (b) probabilities that an arbitrary query references given particular ones of the entities, such as the street “El Camino Real.” Based on the calculated probabilities, the spelling system generates a language model that has associated scores (e.g., probabilities) for each of a set of probable entity name orderings, where the total number of entity name orderings is substantially less than the number of all possible orderings. The language model can be applied to determine probabilities of arbitrary queries, and thus to suggest alternative queries more likely to represent what a user intended.

Claims

1. A computer-implemented method for generating a geographic language model for computing probabilities of occurrence of geographic queries, comprising:

accessing a geographic database comprising;

a plurality of geographic entities, each geographic entity corresponding to a geographic region and having one or more names and an entity type, and

a plurality of links between pairs of the geographic entities;

accessing a query log comprising geographic queries previously entered by users, a plurality of the geographic queries including names of ones of the geographic entities in the geographic database;

generating, from the query log, a template distribution quantifying probabilities that entity types of the geographic entities named in the geographic queries correspond to ones of a plurality of query templates, each query template comprising an ordered set of the entity types appearing in the geographic database;

generating a geographic distribution from the query log quantifying probabilities of queries in the query log referencing ones of the geographic entities in the geographic database;

generating the geographic language model from the template distribution and the geographic distribution, the geographic language model comprising a set of combinations of names of the geographic entities and associated scores, the scores based on probabilities of occurrence of the combinations in a geographic query; and

storing the geographic language model on a computer readable storage device.

2. The computer-implemented method of claim 1, further comprising computing conditional probabilities of occurrence of words in geographic queries based at least in part on the geographic language model.

3. The computer-implemented method of claim 2, further comprising:

receiving a geographic query from a user;

generating an alternative geographic query that is a variant of the received geographic query;

computing a probability of occurrence of the received geographic query and a probability of occurrence of the alternative geographic query based at least in part on the computed conditional probabilities; and

responsive to the probability of occurrence of the alternative geographic query being higher than the probability of occurrence of the received geographic query, providing the alternative geographic query to the user as an alternative query.

4. The computer-implemented method of claim 1, wherein generating the geographic language model further comprises:

for a pair of names comprising a name of a first geographic entity and a name of a second geographic entity corresponding to a geographic region that includes the first geographic entity, computing a score for the pair using;

a probability of a template of the template distribution corresponding to the pair; and

a probability of the geographic distribution corresponding to the first geographic entity.

5. The computer-implemented method of claim 1, wherein generating the template distribution comprises:

identifying, for each of a plurality of the geographic queries in the query log, a corresponding one of the query templates; and

determining, for each distinct query template, a count of the plurality of the geographic queries that correspond to the template.

6. The computer-implemented method of claim 1, wherein generating the geographic distribution comprises, for each entity of a plurality of the geographic entities:

identifying queries comprising one of the names associated with the entity; and

counting, within the identified queries, queries having results falling within the geographic region corresponding to the entity.

7. The computer-implemented method of claim 4, wherein generating the geographic language model further comprises:

receiving the name of the first geographic entity from the geographic database;

identifying a type of the first geographic entity;

identifying a set of related types, the related types comprising entity types that appear in the geographic database adjacent to the first geographic entity;

identifying a set of neighboring geographic entities in the geographic database, each neighboring geographic entity having a link between the neighboring geographic entity and the first geographic entity, and having a type that is included in the set of related types; and

generating a set of pairs of the name of the first geographic entity and the names of the entities in the set of neighboring geographic entities.

8. The computer-implemented method of claim 7, wherein generating the geographic language model further comprises computing a score for each of the generated pairs.

9. The computer-implemented method of claim 8, wherein the score for a generated pair is based on a probability of a template of the template distribution corresponding to the pair.

10. The computer-implemented method of claim 8, wherein the score for a generated pair is based on a probability of an entity in the geographic distribution corresponding to the first geographic entity.

11. The computer-implemented method of claim 8, wherein the score for a generated pair is based on a rank of the type of the first geographic entity.

12. The computer-implemented method of claim 1, wherein each geographic entity is associated with data demarcating the geographic region corresponding to the geographic entity.

13. The computer-implemented method of claim 1, wherein at least one of the geographic entities has a plurality of names comprising at least two names selected from the group consisting of an official name, an informal name, an abbreviated name, and two or more language variants of a name.

14. A non-transitory computer-readable storage medium having executable computer program instructions embodied therein for generating a language model for analyzing probabilities of occurrence of text strings in a given domain, actions of the computer program instructions comprising:

accessing a geographic database comprising;

a plurality of geographic entities, each geographic entity corresponding to a geographic region and having one or more names, and

a plurality of links between pairs of the geographic entities;

accessing a query log comprising geographic queries previously entered by users, a plurality of the geographic queries including names of ones of the geographic entities in the geographic database;

generating, from the query log, a template distribution quantifying probabilities that entity types of the geographic entities named in the geographic queries correspond to ones of a plurality of query templates, each query template comprising an ordered set of the entity types appearing in the geographic database;

generating a geographic distribution from the query log quantifying probabilities of queries in the query log referencing ones of the geographic entities in the geographic database;

generating the geographic language model from the template distribution and the geographic distribution, the geographic language model comprising a set of combinations of names of the geographic entities and associated scores, the scores based on probabilities of occurrence of the combinations in a geographic query; and

storing the geographic language model on a computer readable storage device.

15. The non-transitory computer-readable storage medium of claim 14, the actions further comprising:

computing conditional probabilities of occurrence of words in geographic queries based at least in part on the geographic language model;

receiving a geographic query from a user;

generating an alternative geographic query that is a variant of the received geographic query;

computing a probability of occurrence of the received geographic query and a probability of occurrence of the alternative geographic query based at least in part on the computed conditional probabilities; and

responsive to the probability of occurrence of the alternative geographic query being higher than the probability of occurrence of the received geographic query, providing the alternative geographic query to the user as an alternative query.

16. The non-transitory computer-readable storage medium of claim 14, wherein generating the geographic language model further comprises:

receiving a name of a first geographic entity from the geographic database;

identifying a type of the first geographic entity;

identifying a set of related types, the related types comprising entity types that appear in the geographic database adjacent to the first geographic entity;

identifying a set of neighboring geographic entities in the geographic database, each neighboring geographic entity having a link between the neighboring geographic entity and the first geographic entity, and having a type that is included in the set of related types; and

generating a set of pairs of the name of the first geographic entity and the names of the entities in the set of neighboring geographic entities.

17. The non-transitory computer-readable storage medium of claim 16, wherein generating the geographic language model further comprises computing a score for each of the generated pairs based on at least one of:

a probability of a template of the template distribution corresponding to the pair;

a probability of the geographic distribution corresponding to the first geographic entity; and

a rank of the type of the first geographic entity.

18. A computer-implemented method for generating a geographic language model for analyzing probabilities of occurrence of geographic queries, the method comprising:

accessing a geographic database comprising;

a plurality of geographic entities, each geographic entity corresponding to a geographic region and having one or more names, and

a plurality of links between pairs of the geographic entities;

accessing a query log comprising a plurality of geographic queries previously entered by users, a plurality of the geographic queries including names of ones of the geographic entities in the geographic database;

generating, from the query log, a template distribution quantifying probabilities that entity types of the geographic entities named in the geographic queries correspond to ones of a plurality of query templates, the generating comprising;

identifying, for each of a plurality of the geographic queries in the query log, a query template comprising an ordered set of the entity types appearing in the geographic database, and

determining, for each distinct query template, a probability that the arbitrary user query corresponds to the template;

generating a geographic distribution from the query log quantifying probabilities of queries in the query log referencing ones of the geographic entities in the geographic database, comprising;

identifying queries comprising one of the names associated with one of the entities, and which have results falling within the geographic region corresponding to the entity; and

generating the geographic language model using the template distribution and the geographic distribution, the geographic language model comprising a set of orderings of names of the geographic entities and associated scores, the scores based on probabilities of occurrence of the orderings in a geographic query.

19. The computer-implemented method of claim 18, wherein generating the geographic language model comprises:

receiving a name of a first geographic entity from the geographic database;

identifying a type of the first geographic entity;

identifying a set of related types, the related types comprising entity types that appear in the geographic database adjacency to the first geographic entity;

identifying a set of neighboring geographic entities in the geographic database, each neighboring geographic entity having a link between the neighboring geographic entity and the first geographic entity and having a type that is included in the set of related types;

generating a set of pairs of the name of the first geographic entity and the names of the entities in the set of neighboring geographic entities; and

for each of the generated pairs, computing a score for the pair based at least in part on;

a probability of a template of the template distribution corresponding to the pair;

a probability of the geographic distribution corresponding to the first geographic entity; and

a rank of the type of the first geographic entity.

20. The computer-implemented method of claim 18, further comprising:

computing conditional probabilities of occurrence of words in geographic queries based at least in part on the geographic language model;

receiving a geographic query from a user;

generating an alternative geographic query that is a variant of the received geographic query;

computing a probability of occurrence of the received geographic query and a probability of occurrence of the alternative geographic query based at least in part on the computed conditional probabilities; and

responsive to the probability of occurrence of the alternative geographic query being higher than the probability of occurrence of the received geographic query, providing the alternative geographic query to the user as an alternative query.