Translating search queries on online social networks

• US 10,678,786 B2
• Filed: 10/09/2017
• Issued: 06/09/2020
• Est. Priority Date: 10/09/2017
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Zeng, Bo, Wang, Haixun
• Primary Examiner(s): Vital, Pierre M
• Assistant Examiner(s): Ho, Andrew N
• Application Number:
  US15/728,189
• Publication Number:
  US 20190108228A1
• Time in Patent Office: 974 Days
• Field of Search: 707722
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06N 3/042 Knowledge-based neural networks; Logical representations of neural networks
• 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/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes receiving a search query comprising one or more n-grams from a client system associated with a user of an online social network, generating one or more term embeddings representing the one or more n-grams of the search query, respectively, encoding the one or more term embeddings to generate a query embedding representing the search query, decoding the query embedding to generate one or more output term embeddings representing one or more query tokens, constructing a query command from the one or more output term embeddings, executing the query command to retrieve one or more search results, and sending, to the client system in response to the search query, instructions for generating a search-results interface for presentation to the user, the search-results interface comprising one or more of the retrieved search results.

Claims

1. A method comprising, by a computing device:

receiving, from a client system associated with a user of an online social network, a search query comprising one or more n-grams;

generating, using a word embedding model, one or more term embeddings representing the one or more n-grams of the search query, respectively, wherein each term embedding is a point in a d-dimensional embedding space;

encoding, by a translator neural network, the one or more term embeddings to generate a query embedding representing the search query, wherein the query embedding is a point in an n-dimensional embedding space;

decoding, by the translator neural network, the query embedding to generate one or more output term embeddings representing one or more query tokens, wherein the translator neural network comprises a number of memory units equal to a sum of a number of input term embeddings and a number of output term embeddings, wherein the first k memory units of the translator neural network belong to an encoding module and the last l memory units of the translator neural network belong to a decoding module, wherein k is the number of the input term embeddings and l is the number of the output term embeddings;

constructing a query command from the one or more output term embeddings generated by the translator neural network, wherein the query command comprises the one or more query tokens represented by the one or more output term embeddings;

executing the query command to retrieve one or more search results; and

sending, to the client system in response to the search query, instructions for generating a search-results interface for presentation to the user, the search-results interface comprising one or more of the retrieved search results.

2. The method of claim 1, further comprising:

parsing the search query to identify one or more unique entities associated with the online social network referenced in the search query, wherein each term embedding for an n-gram referencing one of the unique entities is a term embedding for the respective unique entity.

3. The method of claim 1, wherein the translator neural network is a Long Short-Term Memory (LSTM) network.

4. The method of claim 1, wherein the translator neural network performs a sequence to sequence (seq2seq) translation, wherein the seq2seq translation requires two recurrent neural networks working together to transform one sequence to another.

5. The method of claim 1, wherein the translator neural network comprises an encoding module and a decoding module, wherein the encoding module takes the one or more term embeddings representing the one or more n-grams of the search query as an input and the decoding module generates the one or more output term embeddings representing one or more query tokens for a query command.

6. The method of claim 1, wherein the memory units in the encoding module encode the input term embeddings into the query embedding, wherein an i-th memory unit receives an (i−

1)st intermediary encoding query embedding from an (i−

1)st memory unit, generates an i-th intermediary encoding query embedding by processing the (i−

1)st intermediary encoding query embedding and the i-th input term embedding with a first hidden-layer matrix, and forwards the i-th intermediary encoding query embedding to an (i

     1)st memory unit.

7. The method of claim 1, wherein the memory units in the decoding module decode term embeddings for the query command from the query embedding received from the encoding module, wherein a j-th memory unit receives a (j−

1)st intermediary decoding query embedding from a (j−

1)st memory unit, generates a j-th output term embedding and a j-th intermediary decoding query embedding by processing the received (j−

1)st intermediary decoding query embedding with a second hidden-layer matrix, sends out the j-th output term embedding, and forwards the j-th intermediary decoding query embedding to a (j

     1)st memory unit.

8. The method of claim 1, wherein the number of input term embeddings is upper-bounded by a first maximum vocabulary size.

9. The method of claim 1, wherein the number of output term embeddings is upper-bounded by a second maximum vocabulary size.

10. The method of claim 1, wherein the translator neural network is trained with training data comprising a plurality of a natural language query and a corresponding query command pairs.

11. The method of claim 10, wherein the plurality of pairs are generated from context-free grammar rules, wherein the context-free grammar rules are production rules that describe all possible strings in a formal language, wherein the formal language comprises a set of strings of symbols and a set of rules that are specific to the language.

12. The method of claim 10, wherein the plurality of pairs are generated by accessing logged queries from a data store of the online social network, wherein a query command for a given natural language query is constructed by a context-free grammar parser.

13. The method of claim 1, wherein the translator neural network constructs identical query commands for a plurality of paraphrased search queries that are represented by similar term embeddings.

14. The method of claim 1, wherein the translator neural network constructs a query command for a search query in any language that has corresponding term embeddings available.

15. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive, from a client system associated with a user of an online social network, a search query comprising one or more n-grams;

generate, using a word embedding model, one or more term embeddings representing the one or more n-grams of the search query, respectively, wherein each term embedding is a point in a d-dimensional embedding space;

encode, by a translator neural network, the one or more term embeddings to generate a query embedding representing the search query, wherein the query embedding is a point in an n-dimensional embedding space;

decode, by the translator neural network, the query embedding to generate one or more output term embeddings representing one or more query tokens, wherein the translator neural network comprises a number of memory units equal to a sum of a number of input term embeddings and a number of output term embeddings, wherein the first k memory units of the translator neural network belong to an encoding module and the last l memory units of the translator neural network belong to a decoding module, wherein k is the number of the input term embeddings and l is the number of the output term embeddings;

construct a query command from the one or more output term embeddings generated by the translator neural network, wherein the query command comprises the one or more query tokens represented by the one or more output term embeddings;

execute the query command to retrieve one or more search results; and

send, to the client system in response to the search query, instructions for generating a search-results interface for presentation to the user, the search-results interface comprising one or more of the retrieved search results.

16. The media of claim 15, wherein any unique entities referenced by one or more n-grams in the search query are identified, wherein an n-gram referencing a unique entity is represented by a word embedding for the unique entity when the one or more term embeddings are generated.

17. The media of claim 15, wherein the translator neural network is a Long Short-Term Memory (LSTM) network.

18. The media of claim 15, wherein the translator neural network performs a sequence to sequence (seq2seq) translation, wherein the seq2seq translation requires two recurrent neural networks working together to transform one sequence to another.

19. A system comprising:

one or more processors; and

a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

receive, from a client system associated with a user of an online social network, a search query comprising one or more n-grams;

generate, using a word embedding model, one or more term embeddings representing the one or more n-grams of the search query, respectively, wherein each term embedding is a point in a d-dimensional embedding space;

encode, by a translator neural network, the one or more term embeddings to generate a query embedding representing the search query, wherein the query embedding is a point in an n-dimensional embedding space;

decode, by the translator neural network, the query embedding to generate one or more output term embeddings representing one or more query tokens, wherein the translator neural network comprises a number of memory units equal to a sum of a number of input term embeddings and a number of output term embeddings, wherein the first k memory units of the translator neural network belong to an encoding module and the last l memory units of the translator neural network belong to a decoding module, wherein k is the number of the input term embeddings and l is the number of the output term embeddings;

construct a query command from the one or more output term embeddings generated by the translator neural network, wherein the query command comprises the one or more query tokens represented by the one or more output term embeddings;

execute the query command to retrieve one or more search results; and

send, to the client system in response to the search query, instructions for generating a search-results interface for presentation to the user, the search-results interface comprising one or more of the retrieved search results.