System for determining and optimizing for relevance in match-making systems

• US 9,449,282 B2
• Filed: 07/01/2010
• Issued: 09/20/2016
• Est. Priority Date: 07/01/2010
• Status: Active Grant

• Current Assignee: Match Group, LLC (Match Group, Inc.)
• Original Assignee: Match.com LLC (Match Group, Inc.)
• Inventors: Diaz, Fernando, Metzler, Donald, Amer-Yahia, Sihem
• Primary Examiner(s): OWYANG, MICHELLE N
• Application Number:
  US12/829,152
• Publication Number:
  US 20120005204A1
• Time in Patent Office: 2,273 Days
• Field of Search: 705/1, 705 711- 742, 707705-780, 709/205, 709/218
• US Class Current: 1/1
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Disclosed are methods and apparatus for automatically determining the relevance of matches between entities. A set of one or more indicators of relevance for each of a plurality of matches may be detected, where each of the plurality of matches exists between a first entity and a different one of a plurality of entities. Each set of one or more indicators of relevance indicates a degree of two-way interest for a corresponding one of the plurality of matches, the degree of two-way interest indicating both a degree of interest of the first entity in the corresponding one of the plurality of entities and a degree of interest of the corresponding one of the plurality of entities in the first entity. A probability of relevance of each of the plurality of matches may be determined based at least in part upon a corresponding set of one or more indicators of relevance. Each of the plurality of matches may be ranked based at least in part on the corresponding probability of relevance. A ranking function may be trained based upon the probability of relevance of each of the plurality of matches. The ranking function may subsequently be applied to identify and rank matches (e.g., in the absence of indicators of relevance).

Claims

1. A method for ranking unlabeled matches, each of the unlabeled matches existing between a first member of a dating website and a corresponding one of a first set of members of the dating website, the method comprising:

transmitting, by a first mobile device via a web server, messages and profile views directed toward one of a second set of members of the dating website, the first mobile device being associated with the first member of the dating website;

transmitting, by each of a plurality of mobile devices via the web server, messages and profile views directed toward the first member of the dating website, each of the plurality of mobile devices being associated with a corresponding one of the second set of members of the dating website;

receiving, by the web server, a plurality of labeled matches, wherein each of the plurality of labeled matches exists between the first member of the dating website and the corresponding one of the second set of members of the dating website, and wherein each of the plurality of labeled matches are labeled based on a dating profile of the first member of the dating website, a dating profile of the corresponding one of the second set of members of the dating website, and behavioral features, the behavioral features comprising;

a first density of profile views initiated by the first member of the dating website toward the corresponding one of the second set of members of the dating website, the first density of profile views being measured within a time period between a first message and a last message exchanged between the first member of the dating website and the corresponding one of the second set of members of the dating website,

a second density of profile views initiated by the corresponding one of the second set of members of the dating website toward the first member of the dating website, the second density of profile views being measured within the time period,

a message disparity that identifies a difference between a number of messages sent by the first member of the dating website and a number of messages sent by the corresponding one of the second set of members of the dating website,

a number of times that the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website,

a number of times that the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website, and

whether the first member of the dating website and the corresponding one of the second set of members of the dating website exchange phone numbers with one another;

determining, by the web server, a probability of relevance of each of the plurality of labeled matches based on the behavioral features, wherein;

the probability of relevance increases as a first difference decreases and the probability of relevance decreases as the first difference increases, the first difference being between the first density of profile views initiated by the first member of the dating website toward the corresponding one of the second set of members of the dating website within the time period and the second density of profile views initiated by the corresponding one of the second set of members of the dating website toward the first member of the dating website within the time period,

the probability of relevance increases as the message disparity decreases and the probability of relevance decreases as the message disparity increases,

the probability of relevance increases as a second difference decreases and the probability of relevance decreases as the second difference increases, the second difference being between the number of times that the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website and the number of times that the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website, and

ones of the plurality of labeled matches where the first member of the dating website and the corresponding one of the second set of members of the dating website exchange phone numbers with one another are assigned a higher probability of relevance than other ones of the plurality of labeled matches where the first member of the dating website and the corresponding one of the second set of members of the dating website do not exchange phone numbers with one another;

for each of the plurality of labeled matches;

comparing, by a processor in the web server on an attribute-by-attribute basis, first binary data in each attribute of the dating profile of the first member of the dating website to second binary data in a corresponding attribute of the dating profile of the corresponding one of the second set of members of the dating website to produce ranking features of each of the plurality of labeled matches, and

correlating, by the processor in the web server, the ranking features of each of the plurality of labeled matches to the probability of relevance of each of the plurality of labeled matches to produce a ranking function;

training, by the web server, boosted regression trees based on the probability of relevance of each of the plurality of labeled matches, the behavioral features, the ranking features of each of the plurality of labeled matches, the ranking function, the dating profile of the first member of the dating website, and the dating profile of the corresponding one of the second set of members of the dating website, wherein, upon completion of the training, the boosted regression trees are configured to utilize, as input, ranking features observed from a given unlabeled match and generate, as output, a probability of relevance of the given unlabeled match;

determining, by the processor in the web server utilizing the boosted regression trees, a probability of relevance of each of the unlabeled matches by;

comparing, on an attribute-by-attribute basis, the first binary data in each attribute of the dating profile of the first member of the dating website to third binary data in a corresponding attribute of a dating profile of the corresponding one of the first set of members of the dating website to produce ranking features of each of the unlabeled matches, wherein each of the unlabeled matches lack the behavioral features, and

calculating the probability of relevance each of the unlabeled matches by inputting, into the ranking function, the ranking features of each of the unlabeled matches and retrieving, from the ranking function, the probability of relevance each of the unlabeled matches, wherein the ranking features of each of the unlabeled matches are used as a proxy for the behavioral features;

calculating, by the web server, a rank for each of the unlabeled matches based on the probability of relevance of each of the unlabeled matches to generate a set of ranked matches; and

transmitting, by the web server over a network interface, at least a portion of the set of ranked matches to the first mobile device associated with the first member of the dating website.

2. The method as recited in claim 1, wherein the ranking features of each of the plurality of labeled matches further comprise at least one selected from a group consisting of:

a query of the first member of the dating website and a query of the corresponding one of the second set of members of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise at least one selected from a group consisting of;

the query of the first member of the dating website and a query of the corresponding one of the first set of members of the dating website.

3. The method as recited in claim 2, wherein the ranking features of each of the plurality of labeled matches further comprise:

match features for which attributes of the dating profile of the corresponding one of the second set of members of the dating website match corresponding attributes in the query of the first member of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise;

match features for which attributes of the dating profile of the corresponding one of the first set of members of the dating website match the corresponding attributes in the query of the first member of the dating website.

4. The method as recited in claim 2, wherein the ranking features of each of the plurality of labeled matches further comprise:

match features for which attributes of the dating profile of the first member of the dating website match corresponding attributes in the query of the corresponding one of the second set of members of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise;

match features for which the attributes of the dating profile of the first member of the dating website match the corresponding attributes in the query of the corresponding one of the first set of members of the dating website.

5. The method as recited in claim 1, wherein the behavioral features further comprise at least one selected from a group consisting of:

1) the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website but did not send a message to the corresponding one of the second set of members of the dating website; and

     2) the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website but did not send a message to the first member of the dating website.

6. The method as recited in claim 1, wherein the training the boosted regression trees comprises:

storing, for each of the boosted regression trees, a reduction in a loss function for each of the ranking features of each of the plurality of labeled matches; and

summing the reduction in the loss function for each of the ranking features of each of the plurality of labeled matches across all of the boosted regression trees to produce a feature importance of each of the ranking features of each of the plurality of labeled matches, wherein the ranking function further applies a weigh to the probability of relevance of each of the plurality of labeled matches based upon the feature importance of each of the ranking features of each of the plurality of labeled matches.

7. A non-transitory computer-readable medium storing thereon computer-readable instructions for a method for ranking unlabeled matches, each of the unlabeled matches existing between a first member of a dating website and a corresponding one of a first set of members of the dating website, the computer-readable instructions comprising:

instructions for receiving, by a web server from a first mobile device, messages and profile views directed toward one of a second set of members of the dating website, the first mobile device being associated with the first member of the dating website;

instructions for receiving, by the web server from a second mobile device, messages and profile views directed toward the first member of the dating website, the second mobile device being one of a plurality of mobile devices, and wherein each of the plurality of mobile devices is associated with a corresponding one of the second set of members of the dating website;

instructions for receiving, by the web server, a plurality of labeled matches, wherein each of the plurality of labeled matches exists between the first member of the dating website and the corresponding one of the second set of members of the dating website, and wherein each of the plurality of labeled matches are labeled based on a dating profile of the first member of the dating website, a dating profile of the corresponding one of the second set of members of the dating website, and behavioral features, the behavioral features comprising;

a first density of profile views initiated by the first member of the dating website toward the corresponding one of the second set of members of the dating website, the first density of profile views being measured within a time period between a first message and a last message exchanged between the first member of the dating website and the corresponding one of the second set of members of the dating website,

a second density of profile views initiated by the corresponding one of the second set of members of the dating website toward the first member of the dating website, the second density of profile views being measured within the time period,

a message disparity that identifies a difference between a number of messages sent by the first member of the dating website and a number of messages sent by the corresponding one of the second set of members of the dating website,

a number of times that the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website,

a number of times that the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website, and

whether the first member of the dating website and the corresponding one of the second set of members of the dating website exchange phone numbers with one another;

instructions for determining, by the web server, a probability of relevance of each of the plurality of labeled matches based on the behavioral features, wherein;

the probability of relevance increases as a first difference decreases and the probability of relevance decreases as the first difference increases, the first difference being between the first density of profile views initiated by the first member of the dating website toward the corresponding one of the second set of members of the dating website within the time period and the second density of profile views initiated by the corresponding one of the second set of members of the dating website toward the first member of the dating website within the time period,

the probability of relevance increases as the message disparity decreases and the probability of relevance decreases as the message disparity increases,

the probability of relevance increases as a second difference decreases and the probability of relevance decreases as the second difference increases, the second difference being between the number of times that the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website and the number of times that the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website, and

ones of the plurality of labeled matches where the first member of the dating website and the corresponding one of the second set of members of the dating website exchange phone numbers with one another are assigned a higher probability of relevance than other ones of the plurality of labeled matches where the first member of the dating website and the corresponding one of the second set of members of the dating website do not exchange phone numbers with one another;

for each of the plurality of labeled matches;

instructions for comparing, by a processor in the web server on an attribute-by-attribute basis, first binary data in each attribute of the dating profile of the first member of the dating website to second binary data in a corresponding attribute of the dating profile of the corresponding one of the second set of members of the dating website to produce ranking features of each of the plurality of labeled matches, and

instructions for correlating, by the processor in the web server, the ranking features of each of the plurality of labeled matches to the probability of relevance of each of the plurality of labeled matches to produce a ranking function;

instructions for training, by the web server, boosted regression trees based on the probability of relevance of each of the plurality of labeled matches, the behavioral features, the ranking features of each of the plurality of labeled matches, the ranking function, the dating profile of the first member of the dating website, and the dating profile of the corresponding one of the second set of members of the dating website, wherein, upon completion of the training, the boosted regression trees are configured to utilize, as input, ranking features observed from a given unlabeled match and generate, as output, a probability of relevance of the given unlabeled match;

instructions for determining, by the processor in the web server utilizing the boosted regression trees, a probability of relevance of each of the unlabeled matches-by;

comparing, on an attribute-by-attribute basis, the first binary data in each attribute of the dating profile of the first member of the dating website to third binary data in a corresponding attribute of a dating profile of the corresponding one of the first set of members of the dating website to produce ranking features of each of the unlabeled matches, wherein each of the unlabeled matches lack the behavioral features, and

calculating the probability of relevance each of the unlabeled matches by inputting, into the ranking function, the ranking features of each of the unlabeled matches and retrieving, from the ranking function, the probability of relevance each of the unlabeled matches, wherein the ranking features of each of the unlabeled matches are used as a proxy for the behavioral features;

instructions for calculating, by the web server, a rank for each of the unlabeled matches based on the probability of relevance of each of the unlabeled matches to generate a set of ranked matches; and

instructions for transmitting, by the web server over a network interface, at least a portion of the set of ranked matches to the first mobile device associated with the first member of the dating website.

8. The non-transitory computer-readable medium as recited in claim 7, wherein the ranking features of each of the plurality of labeled matches further comprise at least one selected from a group consisting of:

a query of the first member of the dating website and a query of the corresponding one of the second set of members of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise at least one selected from a group consisting of;

the query of the first member of the dating website and a query of the corresponding one of the first set of members of the dating website.

9. The non-transitory computer-readable medium as recited in claim 8, wherein the ranking features of each of the plurality of labeled matches further comprise:

match features for which attributes of the dating profile of the corresponding one of the second set of members of the dating website match corresponding attributes in the query of the first member of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise;

match features for which attributes of the dating profile of the corresponding one of the first set of members of the dating website match the corresponding attributes in the query of the first member of the dating website.

10. The non-transitory computer-readable medium as recited in claim 7, wherein the training the boosted regression trees comprises:

storing, for each of the boosted regression trees, a reduction in a loss function for each of the ranking features of each of the plurality of labeled matches; and

summing the reduction in the loss function for each of the ranking features of each of the plurality of labeled matches across all of the boosted regression trees to produce a feature importance of each of the ranking features of each of the plurality of labeled matches, wherein the ranking function further applies a weigh to the probability of relevance of each of the plurality of labeled matches based upon the feature importance of each of the ranking features of each of the plurality of labeled matches.

11. The non-transitory computer-readable medium as recited in claim 8, wherein the behavioral features further comprise at least one selected from a group consisting of:

1) the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website but did not send a message to the corresponding one of the second set of members of the dating website; and

     2) the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website but did not send a message to the first member of the dating website.

12. The non-transitory computer-readable medium as recited in claim 7, wherein the ranking features of each of the plurality of labeled matches further comprise:

match features for which attributes of the dating profile of the first member of the dating website match corresponding attributes in the query of the corresponding one of the second set of members of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise;

match features for which the attributes of the dating profile of the first member of the dating website match the corresponding attributes in the query of the corresponding one of the first set of members of the dating website.

13. A web server for ranking unlabeled matches, each of the unlabeled matches existing between a first member of a dating website and a corresponding one of a first set of members of the dating website, the web server comprising:

a memory storing data associated with the dating website; and

at least one of processor, that when executed, performs operations comprising;

receiving, from a first mobile device, messages and profile views directed toward one of a second set of members of the dating website, the first mobile device being associated with the first member of the dating website;

receiving, from a second mobile device, messages and profile views directed toward the first member of the dating website, the second mobile device being one of a plurality of mobile devices, and wherein each of the plurality of mobile devices is associated with a corresponding one of the second set of members of the dating website;

receiving a plurality of labeled matches, wherein each of the plurality of labeled matches exists between the first member of the dating website and the corresponding one of the second set of members of the dating website, and wherein each of the plurality of labeled matches are labeled based on a dating profile of the first member of the dating website, a dating profile of the corresponding one of the second set of members of the dating website, and behavioral features, the behavioral features comprising;

a first density of profile views initiated by the first member of the dating website toward the corresponding one of the second set of members of the dating website, the first density of profile views being measured within a time period between a first message and a last message exchanged between the first member of the dating website and the corresponding one of the second set of members of the dating website,

a second density of profile views initiated by the corresponding one of the second set of members of the dating website toward the first member of the dating website, the second density of profile views being measured within the time period,

a message disparity that identifies a difference between a number of messages sent by the first member of the dating website and a number of messages sent by the corresponding one of the second set of members of the dating website,

a number of times that the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website,

a number of times that the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website, and

whether the first member of the dating website and the corresponding one of the second set of members of the dating website exchange phone numbers with one another;

determining a probability of relevance of each of the plurality of labeled matches based on the behavioral features, wherein;

the probability of relevance increases as a first difference decreases and the probability of relevance decreases as the first difference increases, the first difference being between the first density of profile views initiated by the first member of the dating website toward the corresponding one of the second set of members of the dating website within the time period and the second density of profile views initiated by the corresponding one of the second set of members of the dating website toward the first member of the dating website within the time period,

the probability of relevance increases as the message disparity decreases and the probability of relevance decreases as the message disparity increases,

the probability of relevance increases as a second difference decreases and the probability of relevance decreases as the second difference increases, the second difference being between the number of times that the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website and the number of times that the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website, and

ones of the plurality of labeled matches where the first member of the dating website and the corresponding one of the second set of members of the dating website exchange phone numbers with one another are assigned a higher probability of relevance than other ones of the plurality of labeled matches where the first member of the dating website and the corresponding one of the second set of members of the dating website do not exchange phone numbers with one another;

for each of the plurality of labeled matches;

comparing, on an attribute-by-attribute basis, first binary data in each attribute of the dating profile of the first member of the dating website to second binary data in a corresponding attribute of the dating profile of the corresponding one of the second set of members of the dating website to produce ranking features of each of the plurality of labeled matches, and

correlating the ranking features of each of the plurality of labeled matches to the probability of relevance of each of the plurality of labeled matches to produce a ranking function;

training boosted regression trees based on the probability of relevance of each of the plurality of labeled matches, the behavioral features, the ranking features of each of the plurality of labeled matches, the ranking function, the dating profile of the first member of the dating website, and the dating profile of the corresponding one of the second set of members of the dating website, wherein, upon completion of the training, the boosted regression trees are configured to utilize, as input, ranking features observed from a given unlabeled match and generate, as output, a probability of relevance of the given unlabeled match;

determining, utilizing the boosted regression trees a probability of relevance of each of the unlabeled matches by;

comparing, on an attribute-by-attribute basis, the first binary data in each attribute of the dating profile of the first member of the dating website, to third binary data in a corresponding attribute of a dating profile of the corresponding one of the first set of members of the dating website to produce ranking features of each of the unlabeled matches, wherein each of the unlabeled matches lack the behavioral features, and

calculating the probability of relevance each of the unlabeled matches by inputting, into the ranking function, the ranking features of each of the unlabeled matches and retrieving, from the ranking function, the probability of relevance each of the unlabeled matches, wherein the ranking features of each of the unlabeled matches are used as a proxy for the behavioral features;

calculating a rank for each of the unlabeled matches based on the probability of relevance of each of the unlabeled matches to generate a set of ranked matches; and

transmitting, over a network interface, at least a portion of the set of ranked matches to the first mobile device associated with the first member of the dating website.

14. The web server as recited in claim 13, wherein the behavioral features further comprise at least one selected from a group consisting of:

1) the first member of the dating website viewed the dating profile of the corresponding one of the second set of members of the dating website but did not send a message to the corresponding one of the second set of members of the dating website; and

     2) the corresponding one of the second set of members of the dating website viewed the dating profile of the first member of the dating website but did not send a message to the first member of the dating website.

15. The web server as recited in claim 13, wherein the ranking features of each of the plurality of labeled matches further comprise at least one selected from a group consisting of:

a query of the first member of the dating website and a query of the corresponding one of the second set of members of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise at least one selected from a group consisting of;

the query of the first member of the dating website and a query of the corresponding one of the first set of members of the dating website.

16. The web server as recited in claim 15, wherein the ranking features of each of the plurality of labeled matches further comprise:

match features for which attributes of the dating profile of the corresponding one of the second set of members of the dating website match corresponding attributes in the query of the first member of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise;

match features for which attributes of the dating profile of the corresponding one of the first set of members of the dating website match the corresponding attributes in the query of the first member of the dating website.

17. The web server as recited in claim 15, wherein the ranking features of each of the plurality of labeled matches further comprise:

match features for which attributes of the dating profile of the first member of the dating website match corresponding attributes in the query of the corresponding one of the second set of members of the dating website; and

wherein the ranking features of each of the unlabeled matches further comprise;

match features for which the attributes of the dating profile of the first member of the dating website match the corresponding attributes in the query of the corresponding one of the first set of members of the dating website.

18. The web server as recited in claim 13, wherein the training the boosted regression trees comprises:

storing, for each of the boosted regression trees, a reduction in a loss function for each of the ranking features of each of the plurality of labeled matches; and

summing the reduction in the loss function for each of the ranking features of each of the plurality of labeled matches across all of the boosted regression trees to produce a feature importance of each of the ranking features of each of the plurality of labeled matches, wherein the ranking function further applies a weigh to the probability of relevance of each of the plurality of labeled matches based upon the feature importance of each of the ranking features of each of the plurality of labeled matches.