Automatically suggesting completions of text

• US 9,807,037 B1
• Filed: 09/01/2016
• Issued: 10/31/2017
• Est. Priority Date: 07/08/2016
• Status: Active Grant

• Current Assignee: Asapp, Inc.
• Original Assignee: Asapp, Inc.
• Inventors: Sapoznik, Gustavo, Henry, Shawn
• Primary Examiner(s): Anyan, Barbara B
• Application Number:
  US15/254,041
• Time in Patent Office: 425 Days
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/047 Probabilistic or stochastic networks
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 3/088 Non-supervised learning, e.g. competitive learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/022 : Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 10/06311 : Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/1053 : Employment or hiring
• CPC Class Codes: G06Q 10/107 : Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: G06Q 30/01 : Customer relationship services
• CPC Class Codes: G06Q 30/016 : After-sales
• CPC Class Codes: G10L 15/26 : Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: H04L 41/04 : Network management architectures or arrangements
• CPC Class Codes: H04L 51/02 : using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
• CPC Class Codes: H04L 51/52 : for supporting social networking services
• CPC Class Codes: H04L 67/02 : based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/306 : User profiles
• CPC Class Codes: H04L 67/53 : using third party service providers
• CPC Class Codes: H04M 3/42382 : Text-based messaging services in telephone networks such as PSTN/ISDN, e.g. User-to-User Signalling or Short Message Service for fixed networks
• CPC Class Codes: H04M 3/5141 : Details of processing calls and other types of contacts in an unified manner unified messaging in packet-switching networks H04L51/56
• CPC Class Codes: H04M 3/5183 : Call or contact centers with computer-telephony arrangements

Abstract

A user may respond to a request of another user by entering text, such as a customer service representative responding to a customer. As the responding user enters text, a completion of the text may be suggested to the responding user so that the responding user may select the completion instead of continuing to enter text. Previous messages between the two users and other information may be used to determine an appropriate completion to the entered text. A topic vector may be determined from previous messages, and a feature vector may be determined from the entered text. The topic vector and the feature vector may be used to identify characters that may follow the entered text.

Claims

1. A computer-implemented method for suggesting a completion to text entered by a user on a computing device, the method comprising:

receiving, at a sever, text of a message from a first computing device of a first user;

computing a topic vector using the text of the message from the first computing device, wherein each element of the topic vector comprises a score corresponding to a topic of a plurality of topics;

causing the message to be presented by a second computing device to a second user;

receiving text from the second computing device entered by the second user;

computing a first feature vector using the topic vector and the text entered by the second user;

identifying a first plurality of characters to follow the text entered by the second user by processing, by the server, the first feature vector, wherein the first plurality of characters comprises a first character;

computing a second feature vector using the topic vector and the first character;

identifying a second plurality of characters to follow the first character by processing, by the server, the second feature vector, wherein the second plurality of characters comprises a second character;

generating a suggested completion to the text entered by the second user, the suggested completion comprising the first character and the second character, and

transmitting the suggested completion to the second computing device for presenting to the second user.

2. The computer-implemented method of claim 1, wherein computing the topic vector comprises using text of a second message between the first user and the second user.

3. The computer-implemented method of claim 1, wherein computing the first feature vector comprises using a neural network.

4. The computer-implemented method of claim 3, wherein the neural network comprises a recurrent neural network with long short-term memory units.

5. The computer-implemented method of claim 1, wherein identifying the first plurality of characters comprises processing the first feature vector with a classifier.

6. The computer-implemented method of claim 5, wherein the classifier comprises a logistic regression classifier.

7. The computer-implemented method of claim 1, wherein the first user is a customer of a company and the second user is a customer service representative of the company.

8. A system for suggesting a completion to text entered by a user on a computing device, the system comprising:

at least one server computer comprising at least one processor and at least one memory, the at least one server computer configured to;

receive, at the server, text of a message from a first computing device of a first user;

compute a topic vector using the text of the message from the first computing device, wherein each element of the topic vector comprises a score corresponding to a topic of a plurality of topics;

cause the message to be presented by a second computing device to a second user;

receive text from the second computing device entered by the second user;

compute a first feature vector using the topic vector and the text entered by the second user;

identify a first plurality of characters to follow the text entered by the second user by processing, by the server, the first feature vector, wherein the first plurality of characters comprises a first character;

compute a second feature vector using the topic vector and the first character;

identify a second plurality of characters to follow the first character by processing, by the server, the second feature vector, wherein the second plurality of characters comprises a second character;

generate a suggested completion to the text entered by the second user, the suggested completion comprising the first character and the second character, and

transmit the suggested completion to the second computing device for presenting to the second user.

9. The system of claim 8, wherein the at least one server computer is configured to compute the first feature vector using a neural network.

10. The system of claim 8, wherein the at least one server computer is configured to compute the first feature vector by:

computing a sequence of 1-hot vectors using the text entered by the second user;

computing a sequence of input vectors by combining each of the 1-hot vectors with the topic vector; and

processing the sequence of input vectors with a neural network.

11. The system of claim 8, wherein the at least one server computer is configured to generate the suggested completion by creating a graph, wherein the first character corresponds to a first node of the graph and the second character corresponds to a second node of the graph.

12. The system of claim 11, wherein the at least one server computer is configured to generate the suggested completion by selecting the suggested completion using a beam search algorithm and the graph.

13. The system of claim 8, wherein the at least one server computer is configured to:

present the suggested completion to the second user;

receive a selection of the suggested completion by the second user;

transmit a message to the first user, the transmitted message comprising the suggested completion.

14. The system of claim 8, wherein the at least one server computer is configured to generate a second suggested completion to the text entered by the second user, the second suggested completion comprising the first character and the second character.

15. One or more non-transitory computer-readable media comprising computer executable instructions that, when executed, cause at least one processor to perform actions comprising:

receiving, at a server, text of a message from a first computing device of a first user;

computing a topic vector using the text of the message from the first computing device, wherein each element of the topic vector comprises a score corresponding to a topic of a plurality of topics;

causing the message to be presented by a second computing device to a second user;

receiving text from the second computing device entered by the second user;

computing a first feature vector using the topic vector and the text entered by the second user;

identifying a first plurality of characters to follow the text entered by the second user by processing, by the server, the first feature vector, wherein the first plurality of characters comprises a first character;

computing a second feature vector using the topic vector and the first character;

identifying a second plurality of characters to follow the first character by processing, by the server, the second feature vector, wherein the second plurality of characters comprises a second character;

generating a suggested completion to the text entered by the second user, the suggested completion comprising the first character and the second character, and

transmitting the suggested completion to the second computing device for presenting to the second user.

16. The one or more non-transitory computer-readable media of claim 15, wherein computing the topic vector comprises using an autoencoder.

17. The one or more non-transitory computer-readable media of claim 15, wherein computing the first feature vector comprises using a neural network.

18. The one or more non-transitory computer-readable media of claim 17, wherein the neural network comprises a recurrent neural network.

19. The one or more non-transitory computer-readable media of claim 15, wherein identifying the first plurality of characters comprises processing the first feature vector with a classifier.

20. The one or more non-transitory computer-readable media of claim 19, wherein the classifier comprises a logistic regression classifier.