Establishing “is a” relationships for a taxonomy

• US 8,874,553 B2
• Filed: 09/28/2012
• Issued: 10/28/2014
• Est. Priority Date: 08/30/2012
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Lamba, Digvijay Singh, Deshoande, Omkar, Chai, Xiaoyong
• Primary Examiner(s): Leroux, Etienne
• Assistant Examiner(s): Glasser, Dara J
• Application Number:
  US13/630,345
• Publication Number:
  US 20140095478A1
• Time in Patent Office: 760 Days
• Field of Search: 707/722
• US Class Current: 707/722
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Disclosed are methods for returning to a user an answer to the question “what is <string>.” Concepts and classes to which the concepts belong are determined from a corpus, such as taxonomy. The concepts are mapped to categories according to the structure of the taxonomy. Homonyms for words are collected and scored according to likeliness of use. Concept vectors are assembled for the identified concepts based on articles in the corpus and social media usage. Words are evaluated for generic-ness and a generic score is associated therewith. In responding to a query, the generic-ness of the terms of the query is evaluated and additional context solicited if the terms are generic. Candidate homonym concepts for a string in the query are selected according to context vectors for the homonym concepts. One or more homonym concepts are selected and the one or more categories corresponding to these concepts are returned.

Claims

1. A method establishing is-a relationships, the method comprising:

receiving, by a server, a query from a user, the query including a string and one or more context words;

generating a first co-occurrence vector indicating co-occurrence statistics for terms in a reference corpus with respect to the string;

generating a second co-occurrence vector indicating terms and co-occurrence statistics for terms in current social media postings;

determining a difference between the first and second co-occurrence vectors;

determining that the difference between the first and second co-occurrence vectors exceeds a threshold condition;

in response to determining that the difference between the first and second co-occurrence vectors exceeds a threshold condition, requesting from the user additional context words;

retrieving homonym concepts corresponding to the string and concept vectors for each homonym concept;

comparing the concept vectors to the one or more context words;

selecting at least one homonym concept according to the comparison;

retrieving from a category-concept mapping database at least one category for the selected at least one homonym concept, the category-concept mapping database establishing is-a relationships between a plurality of categories and a plurality of concepts; and

transmitting, by the server, the retrieved at least one category for display to the user.

2. The method of claim 1, further comprising:

evaluating generic-ness of the string and zero or more context words; and

if the string and zero or more context words are excessively generic, soliciting more context words.

3. The method of claim 1, further comprising generating the concept vectors for the homonym concepts by, for each homonym concept:

determining a first word usage for an article in a reference corpus corresponding to the homonym concept;

determining a second word usage for documents using the homonym concept in current social media documents; and

combining the first and second word usages to generate the concept vector for the homonym concept.

4. The method of claim 3, wherein the first and second word usage include first and second vectors, respectively, the first and second vectors having entries including words and a corresponding frequency metric;

and

wherein combining the first and second word usages comprises combining the first and second vectors.

5. The method of claim 4, wherein combining the first and second vectors comprises performing a cosine ratio of the first and second vectors.

6. The method of claim 4, wherein the reference corpus is a taxonomy and the article is a node in the taxonomy.

7. The method of claim 6, further comprising generating a lineage vector by combining concept vectors for any descendent articles of the article corresponding to the homonym concept in the taxonomy;

and

wherein combining the first and second word vectors to generate the concept vector for the homonym concept further comprises combining the first and second vectors and the lineage vector.

8. A system for establishing is-a relationships, the system comprising one or more processors and one or more memory devices operably coupled to the one or more processors and storing executable and operational data effective to cause the one or more processors to:

receive a query from a user, the query including a string and one or more context words;

generate a first co-occurrence vector indicating co-occurrence statistics for terms in a reference corpus with respect to the string;

generate a second co-occurrence vector indicating terms and co-occurrence statistics for terms in current social media postings;

determine a difference between the first and second co-occurrence vectors;

determine that the difference between the first and second co-occurrence vectors exceeds a threshold condition;

in response to determining that the difference between the first and second co-occurrence vectors exceeds a threshold condition, request from the user additional context words;

retrieve homonym concepts corresponding to the string and concept vectors for each homonym concept;

compare the concept vectors to the one or more context words;

select at least one homonym concept according to the comparison;

retrieve from a category-concept mapping database at least one category for the selected at least one homonym concept, the category-concept mapping database establishing is-a relationships between a plurality of categories and a plurality of concepts; and

transmit the retrieved at least one category for display to the user.

9. The system of claim 8, wherein the executable and operational data are further effective to cause the one or more processors to:

evaluate generic-ness of the string and zero or more context words; and

if the string and zero or more context words are excessively generic, soliciting more context words.

10. The system of claim 8, wherein the executable and operational data are further effective to cause the one or more processors to generate the concept vectors of the homonym concepts by, for each homonym concept:

determining a first word usage for an article in a reference corpus corresponding to the homonym concept;

determining a second word usage for documents using the homonym concept in current social media documents; and

combining the first and second word usages to generate the concept vector for the homonym concept.

11. The system of claim 10, wherein the first and second word usage include first and second vectors, respectively, the first and second vectors having entries including words and a corresponding frequency metric;

and

wherein the executable and operational data are further effective to cause the one or more processors to combine the first and second word usages comprises combining the first and second vectors.

12. The system of claim 11, wherein the executable and operational data are further effective to cause the one or more processors to combine the first and second vectors by performing a cosine ratio of the first and second vectors.

13. The system of claim 11, wherein the reference corpus is a taxonomy and the article is a node in the taxonomy.

14. The system of claim 13, wherein the executable and operational data are further effective to cause the one or more processors to generate a lineage vector by combining concept vectors for any descendent articles of the article corresponding to the homonym concept in the taxonomy;

and

wherein the executable and operational data are further effective to cause the one or more processors to combine the first and second word vectors to generate the concept vector for the homonym concept by combining the first and second vectors and the lineage vector.

15. A computer program product for establishing is-a relationships, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving a query from a user, the query including a string and one or more context words;

generating a first co-occurrence vector indicating co-occurrence statistics for terms in a reference corpus with respect to the string;

generating a second co-occurrence vector indicating terms and co-occurrence statistics for terms in current social media postings;

determining a difference between the first and second co-occurrence vectors;

determining that the difference between the first and second co-occurrence vectors exceeds a threshold condition;

in response to determining that the difference between the first and second co-occurrence vectors exceeds a threshold condition, requesting from the user additional context words;

retrieving homonym concepts corresponding to the string and concept vectors for each homonym concept;

comparing the concept vectors to the one or more context words;

selecting at least one homonym concept according to the comparison;

retrieving from a category-concept mapping database at least one category for the selected at least one homonym concept, the category-concept mapping database establishing is-a relationships between a plurality of categories and a plurality of concepts; and

transmitting the retrieved at least one category for display to the user.

16. The computer program product of claim 15, further comprising computer instructions for:

evaluating generic-ness of the string and zero or more context words; and

if the string and zero or more context words are excessively generic, soliciting more context words.

17. The computer program product of claim 15, further comprising computer instructions for generating the concept vectors of the homonym concepts by, for each homonym concept:

determining a first word usage for an article in a reference corpus corresponding to the homonym concept;

determining a second word usage for documents using the homonym concept in current social media documents; and

combining the first and second word usages to generate the concept vector for the homonym concept.

18. The computer program product of claim 17, wherein the first and second word usage include first and second vectors, respectively, the first and second vectors having entries including words and a corresponding frequency metric;

and

wherein combining the first and second word usages comprises combining the first and second vectors.

19. The computer program product of claim 18, wherein combining the first and second vectors comprises performing a cosine ratio of the first and second vectors.

20. The computer program product of claim 18, wherein the reference corpus is a taxonomy and the article is a node in the taxonomy.

21. The computer program product of claim 20, further comprising computer instructions for generating a lineage vector by combining concept vectors for any descendent articles of the article corresponding to the homonym concept in the taxonomy;

and

wherein combining the first and second word vectors to generate the concept vector for the homonym concept further comprises combining the first and second vectors and the lineage vector.