Belief propagation for generalized matching

• US 9,117,235 B2
• Filed: 01/26/2009
• Issued: 08/25/2015
• Est. Priority Date: 01/25/2008
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Jebara, Tony, Huang, Bert
• Primary Examiner(s): VAN BRAMER, JOHN W
• Application Number:
  US12/864,438
• Publication Number:
  US 20110040619A1
• Time in Patent Office: 2,402 Days
• Field of Search: 705/14.46, 705/14.4, 705/14.49, 705/26.3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0247 Calculate past, present or future revenues
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 30/0613 Third-party assisted
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

Entities may be matched to enhance the efficiency of various commercial activities using various system and method embodiments of the disclosed subject matter. Belief propagation on a graph data structure defining a bipartite or unipartite matching opportunity is used to calculate a best matching. In embodiments, functions are implemented based upon the match, such as executing sales between matched buyers and sellers in an online auction system. In embodiments, messages with scalar values carry information about the relative value of possible matchings, initially provided as weights or values for the possible matchings. Weights may depend on, for example, bids or costs. Messages may be passed, for example over a network between processors respective to the nodes. Belief values reflecting a best matching can be continuously updated for each node responsively to the value information and received messages to rank the matches respective to each node, which progressively improve. This allows short or complete terminations conditions to determine the goodness of the matching. Differing numbers of matches respective to each member of the disjoint sets and distributions of the desirability of different numbers of matches can be integrated in the matchings in respective embodiments.

Claims

1. A computer readable medium having software instructions stored thereon for matching an advertisement with a key term using belief propagation, the software instructions, when executed by a processor, cause the processor to perform operations comprising:

identifying a predetermined number of advertiser nodes matching a selected key term node;

updating a belief value corresponding to each neighboring advertiser node of a selected key term node in a graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on profit matrix values and received messages, where a data content of each message is determined according to a compressed message update process;

the compressed message update process comprising calculating one or more intermediate values for each neighboring advertiser node of a selected key term node that is based on exponentiated profit matrix values and received messages, sorting the one or more intermediate values, selecting an intermediate value from the one or more intermediate values based on the predetermined number of advertiser nodes matching the selected key term node, and calculating a new message based on the exponentiated profit matrix values, the received messages, and the selected intermediate value;

the passing messages including applying data signals to and receiving signals from a multiprocessor data input/output system;

storing each updated belief value and each received message in an electronic storage associated with the selected key term node;

selecting the predetermined number of advertiser nodes matching the selected key term node, the matching based on updated belief values of advertiser nodes neighboring the selected key term node; and

outputting the selected advertiser nodes.

2. The computer readable medium of claim 1, wherein the data content of each message is a single scalar value.

3. The computer readable medium of claim 2, wherein the single scalar value corresponds to a potential matching of the selected key term node with a respective one of its neighboring advertiser nodes.

4. The computer readable medium of claim 3, wherein the single scalar value includes a profit matrix value corresponding to a potential matching of the selected key term node and the respective one of the neighboring nodes and a value of a message received by that respective neighbor node from another node and a profit matrix value corresponding to a potential matching between the respective neighbor node and the other node.

5. The computer readable medium of claim 1, wherein the software instructions are adapted for use on distributed processors.

6. A distributed processing system for matching advertisements with search terms using belief propagation, the system comprising:

a plurality of processors each corresponding to a node of a graph data structure having advertisement nodes and search term nodes where each advertisement node is a neighbor to at least one search term node;

a network coupling the plurality of processors and adapted to transfer messages between the processors;

wherein each processor is adapted to load and execute software instructions stored on a computer readable medium, the software instructions, when executed, cause the processor to perform operations including;

identifying a predetermined number of advertiser nodes matching a selected search term node;

updating belief values corresponding to its respective neighbor nodes by passing messages between neighboring nodes until a termination condition is met, a data content of each message being based on profit matrix values and received messages, where a data content of each message is determined according to a message update process;

the compressed message update process comprising calculating one or more intermediate values for each neighboring advertiser node of a selected search term node that is based on exponentiated profit matrix values and received messages, sorting the one or more intermediate values, selecting an intermediate value from the one or more intermediate values based on the predetermined number of advertiser nodes matching the selected search term node, and calculating a new message based on the exponentiated profit matrix values, the received messages, and the selected intermediate value;

storing each updated belief value and each received message in an electronic storage associated with the respective processor;

selecting the predetermined number of matching neighbor nodes, the matching being determined based on updated belief values of neighbor nodes; and

outputting the selected matching neighbor nodes.

7. The distributed processing system of claim 6, wherein the data content of each message is a single scalar value.

8. The distributed processing system of claim 7, wherein the single scalar value corresponds to a potential matching of the selected search term node with a respective one of its neighboring advertiser nodes.

9. The distributed processing system of claim 8, wherein the single scalar value includes a profit matrix value corresponding to a potential matching of the selected search term node and the respective one of the neighboring nodes and a value of a message received by that respective neighbor node from another node and a profit matrix value corresponding to a potential matching between the respective neighbor node and the other node.

10. The distributed processing system of claim 6, wherein each profit matrix value represents a profit amount associated with an edge between neighboring nodes.

11. The distributed processing system of claim 6, wherein the updating is performed iteratively until the termination condition is met.

12. The distributed processing system of claim 6, wherein the termination condition is a predetermined number of iterations of the updating.

13. The distributed processing system of claim 6, wherein the termination condition is defined as receiving no changed message values within a predetermined period of time.

14. The distributed processing system of claim 6, wherein the termination condition is a number of messages sent from each node.

15. The distributed processing system of claim 6, wherein the termination condition is an elapsing of a predetermined period of time.

16. The distributed processing system of claim 6, wherein the termination condition is defined as the earliest occurrence of one of receiving no changed message values within a first predetermined period of time and an elapsing of a second predetermined period of time.

17. A computerized method for matching advertisements with search terms using belief propagation, the method comprising:

providing a bipartite graph data structure having a plurality of advertiser nodes and a plurality of search term nodes, where each advertiser node is connected to a corresponding search term node by an edge;

providing a profit matrix having a profit for each edge of the bipartite graph data structure;

identifying a predetermined number of advertiser nodes matching a selected search term node;

updating, with a processor adapted to perform belief propagation generalized matching, a belief value corresponding to each advertiser node connected to a selected search term node by passing messages between adjacent nodes until a termination condition is met, each message being based on profit matrix values and received messages, where a data content of each message is determined according to a compressed message update process;

the compressed message update process comprising calculating one or more intermediate values for each neighboring advertiser node of a selected search term node that is based on exponentiated profit matrix values and received messages, sorting the one or more intermediate values, selecting an intermediate value from the one or more intermediate values based on the predetermined number of advertiser nodes matching the selected search term node, and calculating a new message based on the exponentiated profit matrix values, the received messages, and the selected intermediate value;

storing each updated belief value and each received message in an electronic storage associated with the corresponding advertiser node;

selecting the predetermined number of advertiser nodes matching each search term node of a group of search term nodes of interest, the matching being determined based on updated belief values of advertiser nodes adjacent to each search term node of interest; and

outputting the selected advertiser nodes matching each search term node of interest.

18. The method of claim 17, further comprising displaying advertisements associated with each of the selected advertiser nodes on a search results page corresponding to the search term node associated with the selected advertiser nodes.

19. The method of claim 17, further comprising storing at each advertiser node and at each search term node a portion of the profit matrix, where each portion is selected based on adjacent nodes of each respective advertiser node and each respective search term node.

20. The method of claim 17, wherein the compressed message update process generates a message that includes

21. The method of claim 17, wherein the updating and storing are performed using parallel processing.

22. The method of claim 17, wherein each profit represents a profit on placement of an advertisement by an advertiser associated with the advertisement.

23. The method of claim 17, wherein the updating is performed iteratively until the termination condition is met.

24. The method of claim 17, wherein the termination condition is a predetermined number of iterations of the updating.

25. The method of claim 17, wherein the termination condition is defined as a steady state of updated belief values during a predetermined period of time.