Usage based query response

• US 8,775,160 B1
• Filed: 07/11/2011
• Issued: 07/08/2014
• Est. Priority Date: 12/17/2009
• Status: Expired due to Fees

• Current Assignee: Connexity, Inc.
• Original Assignee: Shopzilla Incorporated
• Inventors: Roizen, Igor, Jawor, Wojciech, Dutton, Keith
• Primary Examiner(s): Vo, Huyen X.
• Application Number:
  US13/179,645
• Time in Patent Office: 1,093 Days
• Field of Search: 704 1- 10, 704/251, 704/255, 704/257, 704/270, 704/270.1, 1/1, 707/759
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

It is possible to provide meaningful responses to queries using systems which consider usage of words in the queries when analyzing those queries and determining what information is possibly relevant. This approach can be applied in online shopping systems by identification of nouns or noun phrases reflecting products available through the system.

Claims

1. A system comprising:

(a) a database storing a plurality of records;

(b) a computer readable medium storing data comprising a dictionary list comprising a plurality of word groups identified as corresponding to an invented part of speech, wherein the word groups in the dictionary list are organized according to a hierarchy comprising a plurality of classes in which each class from the plurality of classes is associated with a plurality of word groups corresponding to the invented part of speech;

(c) a computer configured via a set of data to perform a set of tasks comprising;

(i) receiving an input string, the input string comprising a plurality of words comprising an input word group corresponding to the invented part of speech;

(ii) calculating a set of part of speech scores for the input string, wherein calculating the set of part of speech scores comprises, for each word group from a set of word groups from the dictionary list, calculating a measure of similarity between;

(1) the input word group corresponding to the invented part of speech; and

(2) a comparison word group from the dictionary list;

wherein the measure of similarity is set as a maximum measure of similarity if the following conditions are true;

 

each word in the input word group is also a word in the comparison word group;

 

there exists some nonzero number, i, such that the last i words in the input word group and the last i words in the comparison word group are the same;

 

the comparison word group is associated with a class from the plurality of classes which is also associated with a second word group corresponding to the invented part of speech; and

the last i words in the input word group are the same as the second word group;

(iii) determining a result set comprising a set of records retrieved from the database, wherein each record from the result set comprises an identifying word group corresponding to the invented part of speech; and

(iv) for each record in a subset of records from the result set, determining a match score based on a relevant part of speech score from the previously calculated set of part of speech scores, wherein the relevant part of speech score corresponds to the identifying word group from the record in the subset of records for which the match score is being determined; and

wherein the cardinality of the subset of records is less than or equal to the cardinality of the set of records from the result set.

2. The system of claim 1, wherein:

(a) each record from the plurality of records stored in the database corresponds to a class from the plurality of classes;

(b) the data stored on the computer readable medium further comprises a class probability index, wherein the class probability index comprises, for each class in a subset of the plurality of classes;

(i) general probability data that words appear in records corresponding to the class; and

(ii) specialized probability data that word groups in the dictionary list are used as the invented part of speech in records corresponding to the class;

(c) the set of tasks that the computer is configured to perform further comprises calculating a set of class scores for the input string, wherein the set of class scores comprises, for each class from the subset of the plurality of classes, a probability that the input string corresponds to that class;

(d) each record from the result set corresponds to a class from the subset of the plurality of classes; and

(e) the match score for each record from the subset of records from the result set is further based a relevant class score from the previously calculated set of class scores, wherein the relevant class score corresponds to the class corresponding to the record from the subset of records for which the match score is being determined;

wherein the cardinality of the subset of the plurality of classes is less than or equal to the cardinality of the plurality of classes.

3. The system of claim 2, wherein calculating the set of class scores for the input string comprises, for each class in the subset of the plurality of classes, calculating a corresponding class score using an equation, wherein using the equation comprises calculating:

P_combined(class|input)=w_class*P_invented(class|input)+(1−

w)*P<sub>non—

invented</sub>(class|input)

wherein;

(a) P_invented(class|input) is a specialized probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to the class;

(b) P<sub>non—

invented</sub>(class|input) is a general probability that the words from the input string appear in records corresponding to the class;

(c) P_combined(class|input) is the corresponding class score, representing a probability that the input string corresponds to the class; and

(d) w_class is a weight reflecting confidence in the values of P_invented(class|input) and P<sub>non—

invented</sub>(class|input) for the class.

4. The system of claim 3, wherein P_combined(class|input) for a first class from the subset of the plurality of classes is calculated using a different w_class value than is used to calculate P_combined(class|input) for a second class from the subset of the plurality of classes.

5. The system of claim 2, wherein calculating the set of class scores for the input string comprises:

(a) if there is at least one class in the plurality of classes for which a probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to that class is greater than zero then, for class in the subset of the plurality of classes, calculating a corresponding class score using an equation wherein using the equation comprises calculating;

P_combined(class|input)=w_class*P_invented(class|input)+(1−

w_class)*P<sub>non—

invented</sub>(class|input)

wherein;

P_invented(class|input) is a specialized probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to the class;

(ii) P<sub>non—

invented</sub>(class|input) is a general probability that the words from the input string appear in records corresponding to the class;

(iii) P_combined(class|input) is the corresponding class score, representing a probability that the input string corresponds to the class; and

(iv) w_class is a weight reflecting confidence in the values of P_invented(class|input) and P<sub>non—

invented</sub>(class|input) for the class;

(b) otherwise, if there is no class in the plurality of classes for which the probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to that class is greater than zero then, for class in the subset of the plurality of classes, calculating the corresponding class score comprises calculating the class score based on P<sub>non—

invented</sub>(class|input), without considering whether the input word group is used as the invented part of speech in records corresponding to the class.

6. The system of claim 2 wherein determining the match score for each record in the subset of records from the result set comprises combining a set of scoring data comprising:

(a) the relevant class score corresponding to the record;

(b) the relevant part of speech score corresponding to the record; and

(c) a baseline score corresponding to the record;

wherein combining the set of scoring data comprises weighting the relevant part of speech score corresponding to the record by multiplying the relevant part of speech score corresponding to the record by a weighting factor.

7. The system of claim 1, wherein calculating the set of part of speech scores for the input string comprises, for each word group from the set of word groups from the dictionary list, calculating a cosine similarity measure between:

(a) a first word group corresponding to the input word group corresponding to the invented part of speech; and

(b) a second word group corresponding to the word group from the set of word groups from the dictionary list;

wherein the cosine similarity measure is weighted by giving exponentially increasing the weight given to the similarity of words as those words approach the end of the first word group and the second word group.

8. The system of claim 7, wherein calculating the set of part of speech scores for the input string comprises:

(a) defining the first word group by reordering the input word group by moving any grouping words from the input word group to the beginning of the input word group;

(b) defining the second word group by reordering the word group from the set of word groups from the dictionary list by moving any grouping words from the word group from the set of word groups from the dictionary list to the beginning of the word group from the set of word groups from the dictionary list.

9. The system of claim 7, wherein calculating the set of part of speech scores for the input string comprises:

(a) defining the first word group by deleting any grouping words from the input word group; and

(b) defining the second word group by deleting any grouping words from the word group from the set of word groups from the dictionary list.

10. A method comprising:

(a) receiving an input string, the input string comprising a plurality of words comprising an input word group corresponding to an invented part of speech;

(b) calculating via a computer a set of part of speech scores for the input string, wherein calculating the set of part of speech scores comprises, for each comparison word group from a set of word groups corresponding to the invented part of speech from a dictionary list stored in advance on a computer readable medium, wherein the dictionary list is organized according to a hierarchy comprising a plurality of classes in which each class from the plurality of classes is associated a plurality of word groups corresponding to the invented part of speech, calculating a measure of similarity between;

(i) the input word group corresponding to the invented part of speech; and

(ii) the comparison word group;

wherein the measure of similarity is set as a maximum measure of similarity if the following conditions are true;

(1) each word in the input word group is also a word in the comparison word group;

(2) there exists some nonzero number, i, such that the last i, words in the input word group and the last i words in the comparison word group are the same;

(3) the comparison word group is associated with a class from the plurality of classes which is also associated with a second word group corresponding to the invented part of speech;

(4) the last i words in the input word group are the same as the second word group;

(c) determining a result set comprising a set of records retrieved from a database, wherein each record from the result set comprises an identifying word group corresponding to the invented part of speech; and

(d) for each record in a subset of records from the result set, determining via the computer a match score based on a relevant part of speech score from the previously calculated set of part of speech scores, wherein the relevant part of speech score corresponds to the identifying word group from the record in the subset of records for which the match score is being determined; and

wherein the cardinality of the subset of records is less than or equal to the cardinality of the set of records from the result set.

11. The method of claim 10, wherein:

(a) each record stored in the database corresponds to a class from the plurality of classes;

(b) in addition to storing the dictionary list, the computer readable medium also has stored therein a class probability index, wherein the class probability index comprises, for each class in a subset of the plurality of classes;

(i) general probability data that words appear in records corresponding to the class; and

(ii) specialized probability data that word groups in the dictionary list are used as the invented part of speech in records corresponding to the class;

(c) the method further comprises calculating a set of class scores for the input string, wherein the set of class scores comprises, for each class from the subset of the plurality of classes, a probability that the input string corresponds to that class;

(d) each record from the result set corresponds to a class from the subset of the plurality of classes; and

(e) the match score for each record from the subset of records from the result set is further based a relevant class score from the previously calculated set of class scores, wherein the relevant class score corresponds to the class corresponding to the record from the subset of records for which the match score is being determined;

wherein the cardinality of the subset of the plurality of classes is less than or equal to the cardinality of the plurality of classes.

12. The method of claim 11, wherein calculating the set of class scores for the input string comprises, for each class in the subset of the plurality of classes, calculating a corresponding class score using an equation, wherein using the equation comprises calculating:

P_combined(class|input)=w_class*P_invented(class|input)+(1−

w_class)*P<sub>non—

invented</sub>(class|input)

wherein;

(a) P_invented(class|input) is a specialized probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to the class;

(b) P<sub>non—

invented</sub>(class|input) is a general probability that the words from the input string appear in records corresponding to the class;

(c) P_combined(class|input) is the corresponding class score, representing a probability that the input string corresponds to the class; and

(d) w_class is a weight reflecting confidence in the values of P_invented(class|input) and P<sub>non—

invented</sub>(class|input) for the class.

13. The method of claim 11, wherein calculating the set of class scores for the input string comprises:

(a) if there is at least one class in the plurality of classes for which a probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to that class is greater than zero then, for class in the subset of the plurality of classes, calculating a corresponding class score using an equation wherein using the equation comprises calculating;

P_combined(class|input)=w_class*P_invented(class|input)+(1−

w_class)*P<sub>non—

invented</sub>(class|input)

wherein;

(i) P_invented(class|input) is a specialized probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to the class;

(ii) P<sub>non—

invented</sub>(class|input) is a general probability that the words from the input string appear in records corresponding to the class;

(iii) P_combined(class|input) is the corresponding class score, representing a probability that the input string corresponds to the class; and

(iv) w_class is a weight reflecting confidence in the values of P_invented(class|input) and P<sub>non—

invented</sub>(class|input) for the class;

(b) otherwise, if there is no class in the plurality of classes for which the probability that the input word group corresponding to the invented part of speech is used as the invented part of speech in records corresponding to that class is greater than zero then, for class in the subset of the plurality of classes, calculating the corresponding class score comprises calculating the class score based on P<sub>non—

invented</sub>(class|input), without considering whether the input word group is used as the invented part of speech in records corresponding to the class.

14. The method of claim 11 wherein determining the match score for each record in the subset of records from the result set comprises combining a set of scoring data comprising:

(a) the relevant class score corresponding to the record;

(b) the relevant part of speech score corresponding to the record; and

(c) a baseline score corresponding to the record;

wherein combining the set of scoring data comprises weighting the relevant part of speech score corresponding to the record by multiplying the relevant part of speech score corresponding to the record by a weighting factor.

15. The method of claim 10, wherein calculating via the computer the set of part of speech scores for the input string comprises, for each word group from the set of word groups from the dictionary list, calculating a cosine similarity measure between;

(a) a first word group corresponding to the input word group corresponding to the invented part of speech; and

(b) a second word group corresponding to the word group from the set of word groups from the dictionary list;

wherein the cosine similarity measure is weighted by giving exponentially increasing the weight given to the similarity of words as those words approach the end of the first word group and the second word group.

16. The method of claim 15, wherein calculating the set of part of speech scores for the input string comprises:

(a) defining the first word group by reordering the input word group by moving any grouping words from the input word group to the beginning of the input word group;

(b) defining the second word group by reordering the word group from the set of word groups from the dictionary list by moving any grouping words from the word group from the set of word groups from the dictionary list to the beginning of the word group from the set of word groups from the dictionary list.

17. The method of claim 15, wherein calculating the set of part of speech scores for the input string comprises:

(a) defining the first word group by deleting any grouping words from the input word group; and

(b) defining the second word group by deleting any grouping words from the word group from the set of word groups from the dictionary list.