Understanding spoken location information based on intersections

• US 7,983,913 B2
• Filed: 07/31/2007
• Issued: 07/19/2011
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Seltzer, Michael L., Tashev, Ivan J., Ju, Yun-Cheng
• Primary Examiner(s): Saint Cyr; Leonard
• Application Number:
  US11/888,275
• Publication Number:
  US 20090037174A1
• Time in Patent Office: 1,449 Days
• Field of Search: None
• US Class Current: 704/251
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

In one embodiment, the present system recognizes a user'"'"'s speech input using an automatically generated probabilistic context free grammar for street names that maps all pronunciation variations of a street name to a single canonical representation during recognition. A tokenizer expands the representation using position-dependent phonetic tokens and an intersection classifier classifies an intersection, despite the presence of recognition errors and incomplete street names.

Claims

1. A system for recognizing location information input by a user, the location information including an intersection of streets, the system comprising:

a grammar having a street grammar component that maps various different pronunciations of street names to semantic tags;

a recognition system configured to receive the location information input, access the grammar, and generate a street name recognition hypothesis with associated semantic tags;

an intersection data store storing a plurality of valid street intersections, each street intersection having street names of intersecting streets;

a tokenization component configured to receive the street name recognition hypothesis and the associated semantic tags and to generate, for each of the associated semantic tags, a tokenized query having phonemes that are labeled with a digits position;

a search component configured to search the intersection data store based on the tokenized queries and output at least one recognized intersection result identifying a street intersection recognized from the location information input by the user; and

wherein the phonemes are labeled with a “

100”

for a 100'"'"'s place, with a “

10”

for a 10'"'"'s place, with a “

1”

for a 1'"'"'s place, and with a “

0”

for an ordinal suffix.

2. The system of claim 1 wherein the semantic tags each represent a portion of a given street name, and wherein each tokenized query representing a plurality of different pronunciations associated with the given semantic tag.

3. The system of claim 1 wherein the tokenization component is configured to label each phoneme with a digits position.

4. The system of claim 1 wherein at least one of the tokenized queries includes multiple occurrences of a same phoneme and each of the multiple occurrences is labeled with a different digits position.

5. The system of claim 1 wherein at least one of the tokenized queries includes two different phonemes and each of the two different phonemes is labeled with a same digits position.

6. The system of claim 1 wherein the intersection data store stores a pronunciation for each of the street names in the street intersections tokenized in tokens representative of a set of sub-word units defining words in the street names.

7. The system of claim 6 wherein the tokens further define a position dependence of each sub-word unit that define at least some of the words in the street names.

8. The system of claim 7 wherein the position dependence is provided for each sub-word unit that defines a portion of a numeric word, the position dependence indicating a digits place defined by the sub-word unit in the numeric word.

9. The system of claim 1 wherein the search component is configured to return top N recognized search results based on search scores computed for each search result.

10. The system of claim 1 wherein the search component comprises:

a model configured to calculate a vector of scores corresponding to the query and determine a similarity of the query to the street names in the valid intersections in the intersection data store based on the vector of scores for the query and a vector of scores for each of the street names.

11. The system of claim 1 wherein the street name recognition hypothesis includes semantic tags for a plurality of street names and wherein the tokenization component is configured to generate a query for each semantic tag.

12. The system of claim 11 wherein the search component is configured to compute similarity scores for each query based on a similarity of the query to street names in the intersection data store and to calculate an intersection score by combining the similarity scores for each query relative to street names that occur in a valid intersection in the intersection data store.

13. The system of claim 1 wherein the grammar includes an intersection grammar component defining a plurality of different ways to specify an intersection, having slots for street names, the street grammar component being configured to fill the slots in the intersection grammar component with street names.

14. The system of claim 13 wherein the grammar is configured to have a particular street grammar component loaded into the intersection grammar component based on a city identity input by the user.

15. The system of claim 14 wherein the recognition system is configured to load a plurality of street grammar components for cities in a given geographic proximity to one another based on the city identity input by the user.

16. The system of claim 15 wherein the search component calculates a score for the recognized intersection result based on whether the street intersection recognized is in a city identified in the city identity input by the user or in another city for which a street grammar component is loaded.

17. The system of claim 1 wherein the location information input by the user comprises a spoken input and wherein the recognition system comprises an automatic speech recognition system.

18. A method of generating a street names grammar for use in an intersection recognition system, the method comprising:

receiving an intersection with street names;

parsing each street name into a sequence of entities representing individual components of the street name;

utilizing a processor of a computing device to construct a graph based on the entities, the graph having a plurality of paths representing a plurality of possible pronunciations of the street name, each path through the graph representing a different pronunciation;

generating an utterance representation for each of the plurality of possible pronunciations;

mapping each utterance representation corresponding to a given pronunciation to a common semantic tag;

assigning a prior probability score to each pronunciation;

outputting the plurality of possible pronunciations, utterance representations, semantic tags and prior probabilities as the street names grammar for use in a street names understanding system; and

generating additional utterance representations for each path through the graph, the additional utterance representations including alternative pronunciations and prefix substitutions for the given path.