Method and system for automatically generating a response to a user query

• US 10,657,572 B2
• Filed: 03/20/2017
• Issued: 05/19/2020
• Est. Priority Date: 03/16/2017
• Status: Active Grant

• Current Assignee: Wipro Limited
• Original Assignee: Wipro Limited
• Inventors: Kumar, Channarayapatna Sathyanarayana Kiran, Bade, Sawani
• Primary Examiner(s): Pyo, Monica M
• Application Number:
  US15/464,106
• Publication Number:
  US 20180268456A1
• Time in Patent Office: 1,156 Days
• Field of Search: 707759
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 30/0625 Directed, with specific intent or strategy

Abstract

Disclosed subject matter relates to virtual assistance that includes a method and system for automatically generating response to a user query without language constraints. A response generating system receives the user query from a computing device associated with an end user and determines whether the user query belongs to at least one domain to determine goal data and a problem category of the user query. Further, a problem node associated with the user query is detected from problem nodes by parsing a predefined knowledge graph based on the goal data and the problem category. Furthermore, questions are provided based on problem sub-nodes of the problem node to the computing device to receive a feedback. The response to the user query extracted from the one of the problem sub-nodes is displayed to the end user based on the feedback. The present disclosure is highly scalable, reusable and requires minimal human supervision.

Claims

1. A method for automatically generating a response to a user query, the method comprising:

receiving, by a response generating system, the user query from a computing device associated with an end user;

determining, by the response generating system, whether the user query belongs to at least one domain from a plurality of predefined domains;

determining, when the user query belongs to the at least one domain, by the response generating system, goal data and a problem category of the user query, wherein determining the goal data comprises determining one or more features of one or more tokens based on Part-Of-Speech (POS) tags, wherein the one or more features comprise satisfying features that indicate steps successfully performed by the end user for resolving a problem;

detecting, by the response generating system, a problem node and one or more problem sub-nodes associated with the user query by parsing a predefined knowledge graph corresponding to a category of the at least one domain, based on the goal data and the problem category;

comparing, by the response generating system, each of the one or more problem sub-nodes with the satisfying features for semantic similarity;

removing, upon comparison, by the response generating system, the one or more problem sub-nodes that are semantically similar to the satisfying features;

providing, upon removal, by the response generating system, at least one of open-ended questions and closed-ended questions based on the one or more problem sub-nodes of the problem node to the computing device to receive a feedback for at least one of the open-ended questions and the closed-ended questions from the end user; and

displaying, by the response generating system, the response to the user query extracted from one of the one or more problem sub-nodes to the end user based on the feedback;

wherein determining the problem category comprises;

creating, by the response generating system, a vocabulary file comprising each of one or more words in the user query and an Identifier (ID) corresponding to each of one or more words in the user query;

assigning, by the response generating system a weightage for each of the one or more words in the user query;

filtering, by the response generating system, the one or more words from the user query based on the weightage;

generating, by the response generating system, one or more feature vectors by assigning a feature vector weightage to each of the one or more filtered words based on one or more parameters; and

comparing, by the response generating system, each of the one or more feature vectors with each of the one or more predefined feature vectors related to the at least one domain to determine the problem category.

2. The method as claimed in claim 1, wherein the user query is related to at least one of features of a product, working of a product and services related to the product.

3. The method as claimed in claim 1, wherein determining the at least one domain to which the user query belongs, comprises detecting presence of at least one of predefined domain-related words and cue words representing the at least one domain.

4. The method as claimed in claim 1, wherein determining the goal data comprises:

obtaining, by the response generating system, one or more tokens from the user query;

assigning, by the response generating system, a POS tag to each of the one or more tokens;

determining, by the response generating system, the goal data based on the one or more features of the one or more tokens, wherein the goal data comprises at least one of, one or more goals present in the user query and one or more features affecting each of the one or more goals.

5. The method as claimed in claim 1, wherein the one or more features comprises at least one of position of each of the one or more tokens in the user query, presence of one or more tokens indicating at least one of the plurality of predefined domains, presence of one or more tokens indicating negation, presence of one or more tokens that provide a negative impact and presence of one or more tokens indicating context modifiers.

6. The method as claimed in claim 1, wherein the one or more features further comprises unsatisfying features.

7. The method as claimed in claim 1, further comprises annotating, by the response generation system, a tag to each of the one or more tokens in the user query based on the goal data.

8. The method as claimed in claim 1, wherein the problem category of the user query is at least one of a problem, an information, an instruction and a check.

9. The method as claimed in claim 1, wherein the one or more parameters comprise at least one of presence of predefined-domain related words and cue words representing the at least one domain in the user query and range of the user query.

10. The method as claimed in claim 1, wherein the one or more problem sub-nodes of the problem node are selected based on the goal data.

11. The method as claimed in claim 1, wherein the at least one of the open-ended questions and the closed-ended questions are provided to the computing device until one of the one or more problem sub-nodes comprising a response to the user query is detected based on the feedback of the end user.

12. The method as claimed in claim 1 further comprises prompting, by the response generation system, the end user to rephrase the user query, if the one of the one or more problem sub-nodes comprising the response is not detected.

13. The method as claimed in claim 1 further comprises generating the predefined knowledge graph by:

extracting, by the response generating system, text from each of one or more documents received from a document database, wherein each of the one or more documents are related to the predefined domain;

arranging, by the response generating system, each of one or more logical units of the text in the one or more problem nodes and the one or more problem sub-nodes based on structure of the text;

assigning, by the response generating system, a node Identifier (ID) to each of the one or more problem nodes and the one or more problem sub-nodes; and

generating, by the response generation system, the predefined knowledge graph comprising each of the one or more problem nodes and the one or more problem sub-nodes, the node ID and a trained problem category corresponding to each of the one or more problem nodes and the one or more problem sub-nodes.

14. A response generating system for automatically generating a response to a user query, the response generating system comprising:

a processor; and

a memory communicatively coupled to the processor, wherein the memory stores the processor-executable instructions, which, on execution, causes the processor to;

receive the user query from a computing device associated with an end user;

determine whether the user query belongs to at least one domain from a plurality of predefined domains;

determine, when the user query belongs to the at least one domain, by the response generating system, goal data and a problem category of the user query, wherein determining the goal data comprises determining one or more features of one or more tokens based on Part-Of-Speech (POS) tags, wherein the one or more features comprise satisfying features that indicate steps successfully performed by the end user for resolving a problem;

detect a problem node and one or more problem sub-nodes associated with the user query by parsing a predefined knowledge graph corresponding to a category of the at least one domain, based on the goal data and the problem category;

compare each of the one or more problem sub-nodes with the satisfying features for semantic similarity;

remove, upon comparison, the one or more problem sub-nodes that are semantically similar to the satisfying features;

provide, upon removal, at least one of open-ended questions and closed-ended questions based on the one or more problem sub-nodes of the problem node to the computing device to receive a feedback for at least one of the open-ended questions and the closed-ended questions from the end user; and

display the response to the user query extracted from one of the one or more problem sub-nodes to the end user based on the feedback;

wherein to determine the problem category, the instructions cause the processor to;

create a vocabulary file comprising each of one or more words in the user query and an Identifier (ID) corresponding to each of one or more words in the user query;

assign a weightage for each of the one or more words in the user query;

filter the one or more words from the user query based on the weightage;

generate one or more feature vectors by assigning a feature vector weightage to each of the one or more filtered words based on one or more parameters; and

compare each of the one or more feature vectors with each of the one or more predefined feature vectors related to the at least one domain to determine the problem category.

15. The response generating system as claimed in claim 14, wherein the user query is related to at least one of features of a product, working of a product and services related to the product.

16. The response generating system as claimed in claim 14, wherein the processor determines the at least one domain to which the user query belongs, by detecting presence of at least one of predefined domain-related words and cue words representing the at least one domain.

17. The response generating system as claimed in claim 14, wherein to determine the goal data, instructions cause the processor to:

obtain one or more tokens from the user query;

assign a POS tag to each of the one or more tokens; and

determine the goal data based on the one or more features of the one or more tokens, wherein the goal data comprises at least one of, one or more goals present in the user query and one or more features affecting each of the one or more goals.

18. The response generating system as claimed in claim 14, wherein the one or more features comprises at least one of position of each of the one or more tokens in the user query, presence of one or more tokens indicating at least one of the plurality of predefined domains, presence of one or more tokens indicating negation, presence of one or more tokens that provide a negative impact and presence of one or more tokens indicating context modifiers.

19. The response generating system as claimed in claim 14, wherein the one or more features further comprises unsatisfying features.

20. The response generating system as claimed in claim 14, wherein the processor is further configured to annotate a tag to each of the one or more tokens in the user query based on the goal data.

21. The response generating system as claimed in claim 14, wherein the problem category of the user query is at least one of a problem, an information, an instruction and a check.

23. The response generating system as claimed in claim 14, wherein the one or more problem sub-nodes of the problem node are selected based on the goal data.

24. The response generating system as claimed in claim 14, wherein the processor provides at least one of the open-ended questions and the closed-ended questions to the computing device until one of the one or more problem sub-nodes comprising a response to the user query is detected based on the feedback of the end user.

25. The response generating system as claimed in claim 14, wherein the processor is further configured to prompt the end user to rephrase the user query, if the one of the one or more problem sub-nodes comprising the response is not detected.

26. The response generating system as claimed in claim 14, wherein to generate the predefined knowledge graph, the instructions cause the processor to:

extract text from each of one or more documents received from a document database, wherein each of the one or more documents are related to the predefined domain;

arrange each of one or more logical units of the text in the one or more problem nodes and the one or more problem sub-nodes based on structure of the text;

assign a node Identifier (ID) to each of the one or more problem nodes and the one or more problem sub-nodes; and

generate the predefined knowledge graph comprising each of the one or more problem nodes and the one or more problem sub-nodes, the node ID and a trained problem category corresponding to each of the one or more problem nodes and the one or more problem sub-nodes.

22. The response generating system as claimed in 14, wherein the one or more parameters comprise at least one of presence of predefined-domain related words and cue words representing the at least one domain in the user query and range of the user query.

27. A non-transitory computer readable medium including instructions stored thereon that when processed by at least one processor cause a response generating system to automatically generate a response to a user query by performing operations comprising:

receiving the user query from a computing device associated with an end user;

determining whether the user query belongs to at least one domain from a plurality of predefined domains;

determining when the user query belongs to the at least one domain, by the response generating system, goal data and a problem category of the user query, wherein determining the goal data comprises determining one or more features of one or more tokens based on Part-Of-Speech (POS) tags, wherein the one or more features comprise satisfying features that indicate steps successfully performed by the end user for resolving a problem ;

detecting a problem node and one or more problem sub-nodes associated with the user query by parsing a predefined knowledge graph corresponding to a category of the at least one domain, based on the goal data and the problem category;

comparing each of the one or more problem sub-nodes with the satisfying features for semantic similarity;

removing, upon comparison, the one or more problem sub-nodes that are semantically similar to the satisfying features;

providing, upon removal, at least one of open-ended questions and closed-ended questions based on the one or more problem sub-nodes of the problem node to the computing device to receive a feedback for at least one of the open-ended questions and the closed-ended questions from the end user; and

displaying the response to the user query extracted from one of the one or more problem sub-nodes to the end user based on the feedback;

wherein to determining the problem category comprises;

creating a vocabulary file comprising each of one or more words in the user query and an Identifier (ID) corresponding to each of one or more words in the user query;

assigning a weightage for each of the one or more words in the user query;

filtering the one or more words from the user query based on the weightage;

generating one or more feature vectors by assigning a feature vector weightage to each of the one or more filtered words based on one or more parameters; and

comparing each of the one or more feature vectors with each of the one or more predefined feature vectors related to the at least one domain to determine the problem category.