Pre-filtering in a messaging platform

• US 10,248,667 B1
• Filed: 03/14/2014
• Issued: 04/02/2019
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: Twitter Inc (X Holdings Corp.)
• Inventors: Agrawal, Parag, Jahr, Mike, Lu, Yue, Zhou, Ke, Srivastava, Utkarsh
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/214,438
• Time in Patent Office: 1,845 Days
• Field of Search: 707748, 707749, 707751, 707752, 707754, 705 144, 705 1446, 705 1448, 705 1449, 705 145- 1459
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0247 Calculate past, present or future revenues
• CPC Class Codes: G06Q 30/0249 based upon budgets or funds
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/0275 Auctions

Abstract

A real-time messaging platform allows advertiser accounts to pay to insert candidate messages into the message streams requested by account holders. To accommodate multiple advertisers, the messaging platform controls an auction process that determines which candidate messages are selected for inclusion in a requested account holder'"'"'s message stream. Selection is based on a bid for the candidate message, the message stream that is requested, and a variety of other factors that vary depending upon the implementation. The process for selection of candidate messages generally includes the following steps, though any given step may be omitted or combined into another step in a different implementation: targeting, filtering, prediction, ranking, and selection.

Claims

1. A computer-implemented method comprising:

receiving, from a client device accessing a real-time messaging platform using a first account of a plurality of accounts, one or more signals indicating a request for a message stream, wherein the first account is associated with one or more account features;

identifying a set of two or more candidate messages each associated with one or more message features;

selecting, based on a machine learning model, a subset of features that includes at least one of the one or more message features and at least one of the one or more account features, wherein only message features and account features included in the subset of features are used to preliminarily evaluate the candidate messages in the set of two or more candidate messages, thereby reducing an amount of processing needed to preliminarily select candidate messages for inclusion in the message stream, wherein the subset of features includes fewer features than a total of the one or more account features and the one or more message features;

determining, based on the machine learning model and ranking data representing past rankings of candidate messages for the plurality of accounts, account ranking weights for the at least one of the one or more account features associated with the first account and that are included in the subset of features, the past rankings used to select one or more candidate messages to present in message streams associated with the plurality of accounts;

for each candidate message of the set of two or more candidate messages;

determining, based on the ranking data and the machine learning model, message ranking weights for the at least one of the one or more message features associated with the candidate message that are included in the subset of features;

determining, by a processor, a value representing a likelihood of the candidate message ranking above a ranking threshold for the first account, the likelihood based at least on the message ranking weights and the account ranking weights; and

in response to the determined value being less than a threshold likelihood value, removing the candidate message from the set of two or more candidate messages to generate a set of remaining candidate messages;

selecting at least one of the set of remaining candidate messages for inclusion in a message stream of the first account; and

sending the message stream to the client device for display on the client device, wherein the message stream includes the selected at least one candidate message of the set of remaining candidate messages.

2. The method of claim 1, wherein determining the account ranking weights and the message ranking weights comprise determining the account ranking weights and the message ranking weights based on a logistic regression of the engagement data.

3. The method of claim 2, wherein the logistic regression is based on a prior probability of ranking above a ranking threshold, the prior probability determined from a number of instances the candidate message ranked above the ranking threshold relative to a total number of ranking instances of the candidate message.

4. The method of claim 1, wherein determining the likelihood of the candidate message ranking above the ranking threshold for the first account comprises:

calculating the value based on a logistic function applied to an inner-product between a features vector and a weights vector, the features vector comprising values of the message ranking features and values of the account ranking features, the weights vector comprising the message ranking weights and the account ranking weights.

5. The method of claim 1, wherein identifying the set of two or more candidate messages comprises:

receiving candidate messages from a plurality of advertiser accounts, each message of the candidate messages associated with targeting criteria; and

selecting the candidate messages from the received candidate messages based on the targeting criteria of the received candidate messages and the account features of the first account.

6. The method of claim 5, wherein the message features are associated with the targeting criteria of the candidate message.

7. The method of claim 6, wherein selecting the subset of features that includes the at least one of the one or more message features and the at least one of the one or more account features comprises selecting the subset of features based on the targeting criteria.

8. The method of claim 1, wherein the account features include features based on connections between the first account and other accounts subscribed to receive messages authored by the first account and based on connections between the first account and other accounts that the first account is subscribed to receive messages from.

9. The method of claim 1, wherein the account features are inferred based on engagements between the first account and other messages and based on message features of the other messages.

10. The method of claim 1, wherein the past rankings include rankings of messages for subscribing accounts subscribed to receive messages from the first account.

11. The method of claim 1, wherein the past rankings include rankings of messages for accounts that the first account is subscribed to receive messages from.

12. The method of claim 1, further comprising:

determining, for each of the remaining candidate messages, a value representing a likelihood of engagement with the candidate message by the first account, the likelihood of engagement based at least on a plurality of message weights and the account weights; and

wherein selecting the at least one remaining candidate messages for inclusion in the message stream is based on the values representing the likelihoods of engagement.

13. The method of claim 1, further comprising:

after sending the message stream to the computing device, receiving, for each of the one or more preferred engagement types, an indication of whether a candidate message of the at least one candidate messages received an engagement; and

responsive to receiving the one or more indications, for each of the one or more indications, updating the machine learning model based on the respective indication of whether the ranked candidate message of the at least one candidate messages received the engagement.

14. A non-transitory computer-readable storage medium comprising instructions executable by a processor, the instructions for:

receiving, from a client device accessing a real-time messaging platform using a first account of a plurality of accounts, one or more signals indicating a request for a message stream, wherein the first account is associated with one or more account features;

identifying a set of two or more candidate messages each associated with one or more message features;

selecting, based on a machine learning model, a subset of features that includes at least one of the one or more message features and at least one of the one or more account features, wherein only message features and account features included in the subset of features are used to preliminarily evaluate the candidate messages in the set of two or more candidate messages, thereby reducing an amount of processing needed to preliminarily select candidate messages for inclusion in the message stream, wherein the subset of features includes fewer features than a total of the one or more account features and the one or more message features;

determining, based on the machine learning model and ranking data representing past rankings of candidate messages for the plurality of accounts, account ranking weights for the at least one of the one or more account features associated with the first account and that are included in the subset of features, the past rankings used to select one or more candidate messages to present in message streams associated with the plurality of accounts;

for each candidate message of the set of two or more candidate messages;

determining, based on the ranking data and the machine learning model, message ranking weights for the at least one of the one or more message features associated with the candidate message that are included in the subset of features;

determining a value representing a likelihood of the candidate message ranking above a ranking threshold for the first account, the likelihood based at least on the message ranking weights and the account ranking weights; and

in response to the determined value being less than a threshold likelihood value, removing the candidate message from the set of two or more candidate messages to generate a set of remaining candidate messages;

selecting at least one of the set of remaining candidate messages for inclusion in a message stream of the first account; and

sending the message stream to the client device for display on the client device, wherein the message stream includes the selected at least one candidate message of the set of remaining candidate messages.

15. The non-transitory computer-readable storage medium of claim 14, wherein determining the account ranking weights and the message ranking weights comprise determining the account ranking weights and the message ranking weights based on a logistic regression of the engagement data, and wherein the logistic regression is based on a prior probability of ranking above a ranking threshold, the prior probability determined from a number of instances the candidate message ranked above the ranking threshold relative to a total number of ranking instances of the candidate message.

16. The non-transitory computer-readable storage medium of claim 14, wherein determining the value representing the likelihood of the candidate message ranking above the ranking threshold for the first account comprises:

calculating the value based on a logistic function applied to an inner-product between a features vector and a weights vector, the features vector comprising values of the message ranking features and values of the account ranking features, the weights vector comprising the message ranking weights and the account ranking weights.

17. The non-transitory computer-readable storage medium of claim 14, wherein the instructions for identifying the set of two or more candidate messages comprise instructions for:

receiving candidate messages from a plurality of advertiser accounts, each message of the candidate messages associated with targeting criteria; and

selecting the candidate messages from the received candidate messages based on the targeting criteria of the received candidate messages and the account features of the first account, wherein the message features are associated with the targeting criteria of the candidate message.

18. The non-transitory computer-readable storage medium of claim 14, wherein the account features include features based on connections between the first account and other accounts subscribed to receive messages authored by the first account and based on connections between the first account and other accounts that the first account is subscribed to receive messages from.

19. The non-transitory computer-readable storage medium of claim 14, wherein the account features are inferred based on engagements between the first account and other messages and based on message features of the other messages.

20. The non-transitory computer-readable storage medium of claim 14, wherein the past rankings include rankings of messages for subscribing accounts subscribed to receive messages from the first account and rankings of messages for accounts from which the first account is subscribed to receive messages.

21. The non-transitory computer-readable storage medium of claim 14, further comprising instructions for:

determining, for each of the remaining candidate messages, a value representing a likelihood of engagement with the candidate message by the first account, the likelihood of engagement based at least on a plurality of message weights and the account weights; and

wherein selecting the at least one remaining candidate messages for inclusion in the message stream is based on the values representing the likelihoods of engagement.

22. The non-transitory computer-readable storage medium of claim 14, wherein the instructions executable by the processor are further for:

after sending the message stream to the computing device, receiving, for each of the one or more preferred engagement types, an indication of whether a candidate message of the at least one candidate messages received an engagement; and

responsive to receiving the one or more indications, for each of the one or more indications, updating the machine learning model based on the respective indication of whether the ranked candidate message of the at least one candidate messages received the engagement.

23. A device comprising:

at least one processor; and

at least one non-transitory computer-readable storage medium storing instructions that are executable by the at least one processor to;

receive, from a client device accessing a real-time messaging platform using a first account of a plurality of accounts, one or more signals indicating a request for a message stream, wherein the first account is associated with one or more account features;

identify a set of two or more candidate messages each associated with one or more message features;

select, based on a machine learning model, a subset of features that includes at least one of the one or more message features and at least one of the one or more account features, wherein only message features and account features included in the subset of features are used to preliminarily evaluate the candidate messages in the set of two or more candidate messages, thereby reducing an amount of processing needed to preliminarily select candidate messages for inclusion in the message stream, wherein the subset of features include fewer features than a total of the one or more account features and the one or more message features;

determine, based on the machine learning model and ranking data representing past rankings of candidate messages for the plurality of accounts, account ranking weights for the at least one of the one or more account features associated with the first account and that are included in the subset of features, the past rankings used to select one or more candidate messages to present in message streams associated with the plurality of accounts;

for each candidate message of the set of two or more candidate messages;

determine, based on the ranking data and the machine learning model, message ranking weights for the at least one of the one or more message features associated with the candidate message that are included in the subset of features;

determine a value representing a likelihood of the candidate message ranking above a ranking threshold for the first account, the likelihood based at least on the message ranking weights and the account ranking weights; and

in response to the determined value being less than a threshold likelihood value, remove the candidate message from the set of two or more candidate messages to generate a set of remaining candidate messages;

select at least one of the set of remaining candidate messages for inclusion in a message stream of the first account; and

send the message stream to the client device for display on the client device, wherein the message stream includes the selected at least one candidate message of the set of remaining candidate messages.

24. The device of claim 23, wherein the instructions executable by the at least one processor to determine the account ranking weights and the message ranking weights are further executable by the at least one processor to determine the account ranking weights and the message ranking weights based on a logistic regression of the engagement data, and wherein the logistic regression is based on a prior probability of ranking above a ranking threshold, the prior probability determined from a number of instances the candidate message ranked above the ranking threshold relative to a total number of ranking instances of the candidate message.

25. The device of claim 23, wherein the instructions executable by the at least one processor to determine the value representing the likelihood of the candidate message ranking above the ranking threshold for the first account are further executable by the at least one processor to:

calculate the value based on a logistic function applied to an inner-product between a features vector and a weights vector, the features vector comprising values of the message ranking features and values of the account ranking features, the weights vector comprising the message ranking weights and the account ranking weights.

26. The device of claim 23, wherein the instructions for identifying the set of two or more candidate messages comprise instructions for:

receiving candidate messages from a plurality of advertiser accounts, each message of the candidate messages associated with targeting criteria; and

selecting the candidate messages from the received candidate messages based on the targeting criteria of the received candidate messages and the account features of the first account, wherein the message features are associated with the targeting criteria of the candidate message.

27. The device of claim 23, wherein the account features include features based on connections between the first account and other accounts subscribed to receive messages authored by the first account and based on connections between the first account and other accounts that the first account is subscribed to receive messages from.

28. The device of claim 23, wherein the account features are inferred based on engagements between the first account and other messages and based on message features of the other messages.

29. The device of claim 23, wherein the past rankings include rankings of messages for subscribing accounts subscribed to receive messages from the first account and rankings of messages for accounts from which the first account is subscribed to receive messages.

30. The device of claim 23, wherein the instructions are further executable by the at least one processor to:

determine, for each of the remaining candidate messages, a value representing a likelihood of engagement with the candidate message by the first account, the likelihood of engagement based at least on a plurality of message weights and the account weights; and

wherein the instructions executable by the at least one processor to select the at least one remaining candidate messages for inclusion in the message stream based on the values representing the likelihoods of engagement.

31. The computing device of claim 23, wherein the instructions are further executable by the at least one processor to:

after sending the message stream to the computing device, receive, for each of the one or more preferred engagement types, an indication of whether a candidate message of the at least one candidate messages received an engagement; and

responsive to receiving the one or more indications, for each of the one or more indications, update the machine learning model based on the respective indication of whether the ranked candidate message of the at least one candidate messages received the engagement.