MACHINE OPTIMIZATION DEVICES, METHODS, AND SYSTEMS
First Claim
1. A computer readable medium having software instructions stored thereon for matching an advertisement with a phrase, the software instructions, when executed by a processor, cause the processor to perform operations comprising:
- receiving a first graph data structure, a first weight matrix and degree distribution data as input, the first graph data structure having a first group of nodes each representing an advertisement and a second group of nodes each representing a phrase, the first weight matrix including a bid value for each connection between an advertisement and a phrase in the first graph data structure;
generating a second graph data structure including nodes corresponding to the first graph data structure and additional dummy nodes;
generating a second weight matrix including the first weight matrix and additional weight values each associated with one of the nodes in the first graph data structure and one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data and the second weight matrix also including a group of zero weight values;
constraining the nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not constraining the dummy nodes in the second graph data structure;
determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values;
truncating the intermediate graph data structure; and
generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.
2 Assignments
0 Petitions
Accused Products
Abstract
A method, system, computer program product and computer readable media for matching using degree distribution information are disclosed. An embodiment of the method can include performing b-matching on a graph data structure expanded using degree distribution information in order to identify neighbors of a selected input node. The b-matching can be performed using belief propagation. The belief propagation method is adapted to use a compressed message update rule and to be suitable for use with distributed processing systems. An embodiment can also include enhancing a matching result by applying degree distribution information to a first matching result to generate a second matching result. Embodiments for online advertisement/search term matching, product recommendation, dating service and social network matching, auction buyer/seller matching and resource allocation, among other, are disclosed.
-
Citations
77 Claims
-
1. A computer readable medium having software instructions stored thereon for matching an advertisement with a phrase, the software instructions, when executed by a processor, cause the processor to perform operations comprising:
-
receiving a first graph data structure, a first weight matrix and degree distribution data as input, the first graph data structure having a first group of nodes each representing an advertisement and a second group of nodes each representing a phrase, the first weight matrix including a bid value for each connection between an advertisement and a phrase in the first graph data structure; generating a second graph data structure including nodes corresponding to the first graph data structure and additional dummy nodes; generating a second weight matrix including the first weight matrix and additional weight values each associated with one of the nodes in the first graph data structure and one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data and the second weight matrix also including a group of zero weight values; constraining the nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not constraining the dummy nodes in the second graph data structure; determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values; truncating the intermediate graph data structure; and generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 54)
-
-
18. A distributed processing system for matching advertisements with search terms, the system comprising:
-
a plurality of processors each corresponding to at least one node of a graph data structure having advertisement nodes, search term nodes and dummy 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; receiving a portion of a first graph data structure, a portion of a profit matrix and a portion of degree distribution data as input, the first graph data structure having a first group of nodes each representing an advertisement and a second group of nodes each representing a phrase, the profit matrix including a bid value for each connection between an advertisement and a search term in the first graph data structure; generating a second graph data structure including nodes corresponding to the first graph data structure and a plurality of dummy nodes; generating a weight matrix portion including the portion of the profit matrix and, when the processor corresponds to one of the dummy nodes, generating an additional weight value associated with the dummy node, the additional weight value in the weight matrix portion being based on the portion of degree distribution data or having a zero value depending on a location of the dummy node in the second graph data structure; receiving a node constraint value for nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not receiving a constraint value for the dummy nodes in the second graph data structure; determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values, the determining including; 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 weight matrix values and received messages, where a data content of each message is determined according to a message update rule; storing each updated belief value and each received message in an electronic storage associated with the respective processor; truncating the intermediate graph data structure; generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output, including selecting a 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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. A computerized method for matching an advertiser with a search term, the method comprising:
-
providing a first 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; providing degree distribution data representing a degree distribution of each node; generating a second bipartite graph data structure including nodes of the first bipartite graph data structure and a plurality of dummy nodes; generating, with a processor adapted to perform weight matrix expansion, a weight matrix including values of the profit matrix and additional values associated with the dummy nodes, the additional values in the weight matrix being determined based on the degree distribution data and including a group of zero weight values; constraining the nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not constraining the dummy nodes in the second graph data structure; determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value; generating an intermediate bipartite graph data structure having binary weight values; generating a result graph data structure by truncating the intermediate graph data structure to remove the dummy nodes; selecting a 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 result graph 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. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
-
44. A computerized method for matching customers with suppliers in an auction, the method comprising:
-
providing a first bipartite graph data structure having a plurality of supplier nodes and a plurality of customer nodes, where each supplier node is connected to a customer node by an edge; providing a first weight matrix data structure having a weight value for each edge of the bipartite graph data structure, where a portion of the weight matrix is provided to each supplier node and each customer node, the weight matrix portion including weight values for nodes adjacent to each respective supplier node and customer node; generating, using a processor adapted to estimate graph structure using prior degree distribution information, a second graph data structure including nodes corresponding to the first bipartite graph data structure and having a plurality of dummy nodes; generating, with the processor, a second weight matrix including the first weight matrix and additional weight values each associated with one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data, the second weight matrix also including a group of zero weight values associated with a group of dummy nodes; storing the second weight matrix in an electronic memory coupled to the processor; constraining nodes of the second graph data structure that correspond to nodes of the first graph data structure to a predetermined degree value, and leaving the dummy nodes in the second graph data structure unconstrained; determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values; truncating the intermediate graph data structure; and generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output. - View Dependent Claims (45, 46, 47, 48, 49, 50, 51, 52, 53)
-
-
55. A computer readable medium having software instructions stored thereon for matching buyers with sellers in an auction, the software instructions, when executed by a processor, cause the processor to perform operations comprising:
-
providing a first graph data structure having a plurality of seller nodes and a plurality of buyer nodes, where each seller node is connected to a buyer node by an edge; providing a first weight matrix data structure having a weight value for each edge of the first graph data structure, where a portion of the first weight matrix is provided to each supplier node and each customer node, the weight matrix portion including weight values for nodes adjacent to each respective supplier node and customer node; generating, using a processor adapted to estimate graph structure using prior degree distribution information, a second graph data structure including nodes corresponding to the first graph data structure and a plurality of dummy nodes; generating, using the processor, a second weight matrix including the first weight matrix and additional weight values each associated with one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data, the second weight matrix also including a group of zero weight values associated with a group of edges between dummy nodes; storing the second weight matrix in an electronic memory coupled to the processor; constraining nodes of the second graph data structure that correspond to nodes of the first graph data structure to a predetermined degree value, and leaving the dummy nodes in the second graph data structure unconstrained; determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, the determining including; updating a belief value corresponding to each of the supplier nodes and customer nodes, with a processor adapted to perform belief propagation, by passing electronic messages between adjacent nodes until a termination condition is met, each message being based on the weight matrix portion values and received messages, where a value of each message is determined according to a compressed message update rule; and storing, in an electronic memory, received messages and an updated belief value for each supplier node and customer node in storage locations of the electronic memory associated with the corresponding node; generating an intermediate graph data structure having binary weight values by truncating the intermediate graph data structure; and selecting, with the processor, a predetermined number of seller nodes and a predetermined number of respective buyer nodes matching each selected seller node, the selecting of the buyer nodes being based on updated belief values; and outputting the selected seller nodes and respective matching buyer nodes.
-
-
56. A computerized method for matching social network members using belief propagation, the method comprising:
-
accessing a first graph data structure having a plurality of member nodes each representing a member of a social network service and a compatibility matrix representing a compatibility between member nodes joined by an edge of the graph data structure; accessing degree distribution data including a degree distribution for each member node; generating a second graph data structure that includes nodes copied from the first graph data structure and a group of dummy nodes; generating a weight matrix including the compatibility matrix and additional weight values corresponding to edges between member nodes and dummy nodes, the additional weight values being based on a portion of the degree distribution data, the weight matrix also including a group of zero weight values corresponding to edges between dummy nodes; constraining a degree value of the member nodes within the second graph data structure and leaving the dummy nodes within the second graph data structure unconstrained; updating, with a processor adapted to perform social network service member matching using degree distribution and belief propagation, a belief value corresponding to edges between nodes of the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on weight matrix values and received messages, where data content of each message is determined according to a compressed message update rule; storing each updated belief value and each received message in an electronic storage associated with the corresponding node; extracting a portion of the second graph data structure that corresponds to the member nodes as a result graph data structure; selecting a predetermined number of neighboring member nodes matching a member node of interest from the result graph data structure, the matching being determined based on updated belief values of neighbor member nodes of the member node of interest; and outputting the selected member nodes.
-
-
57. A system for matching items with other items comprising:
-
a storage adapted to store software instructions for performing a method of matching items with other items using degree distribution, a first graph data structure having nodes representing items, a first weight matrix having weight values associated with an edge in the first graph data structure connecting two items and degree distribution data having degree distribution data for each node in the first graph data structure; a processor coupled to the storage and adapted to execute the software instructions and perform operations including; generating a second graph data structure including nodes representing the first graph data structure and a plurality of dummy nodes; generating a second weight matrix including values representing the first weigh matrix and having additional values associated with the dummy nodes, the additional values being determined based on the degree distribution data; determining a constraint value for the nodes of the second graph data structure that represent the nodes of the first graph data structure; performing a maximum weight b-matching operation on the second graph data structure and the second weight matrix to produce a result matrix; extracting a portion of the result matrix corresponding to the nodes of the first graph data structure; and providing a portion of the result matrix as output. - View Dependent Claims (58, 59, 60)
-
-
61. A computerized method for post processing recommender outputs, the method comprising:
-
receiving a training data set containing a plurality of nodes having a group of nodes representing users and a group of nodes representing items; receiving a ratings matrix representing preferences of users for items in the training data set, with each cell in the ratings matrix containing a value representing a rating of one of the items by one of the users; receiving a testing data set containing a plurality of nodes having a group of nodes representing users and a group of nodes representing items generating deviation bound data including a deviation bound for each user and item in the training data set; learning values for edge weights based on the training data set and the ratings matrix and storing the edge weights in a first weight matrix; generating an expanded graph data structure including the nodes of the testing data set and additional dummy nodes; generating a second weight matrix including values from the first weight matrix corresponding to nodes from the testing data set and additional values corresponding to the dummy nodes, the additional values being determined based on a portion of the deviation bound data; constraining the expanded graph data structure nodes corresponding to the testing data set nodes to a predetermined degree value and not constraining the dummy nodes in the expanded graph data structure; determining a maximum weight b-matching based on the expanded graph data structure and the second weight matrix, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary values; truncating the intermediate graph data structure so that only the nodes corresponding to the nodes of the testing data set remain; and generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output. - View Dependent Claims (62, 63, 64)
-
-
65. A recommender system comprising:
-
a first processor adapted to learn edge weights for edges of a graph data structure having a plurality of nodes including a group of user nodes and a group of item nodes and to store the edge weights in a first weight matrix; a second processor coupled to the first processor and adapted to receive a portion of the graph data structure and the first weight matrix from the first processor, the second processor being further adapted to perform a matching operation using degree distribution data, the degree distribution data being based on deviation bound data including a deviation bound for each user and item in the graph data structure, the deviation bound data determined based on the portion of the graph data structure and a preference matrix corresponding to the graph data structure, wherein the matching operation includes; generating an expanded graph data structure including the nodes of the portion of the graph data structure and a plurality of dummy nodes; generating a second weight matrix including values from the first weight matrix corresponding to nodes from the portion of the graph data structure and additional values corresponding to the dummy nodes, the additional values being determined based on a portion of the deviation bound data; constraining the expanded graph data structure nodes corresponding to the portion of the graph data structure nodes to a predetermined degree value and not constraining the dummy nodes in the expanded graph data structure; determining a maximum weight b-matching based on the expanded graph data structure and the second weight matrix, where b is set to the predetermined degree value, the determining including; updating a belief value corresponding to each neighboring item node of a selected user node in the expanded graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule; and storing each updated belief value and each received message in an electronic storage associated with the selected user node; truncating the intermediate graph data structure so that only the nodes corresponding to the portion of nodes of the graph data structure remain; and generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output. - View Dependent Claims (66, 67, 68, 69, 70, 71)
-
-
72. A computer readable medium having software instructions stored thereon for programming a computer to perform post processing on recommendation data, the software instructions, when executed by a processor, cause the processor to perform operations comprising:
-
receiving a training data set containing a plurality of nodes including a group of user nodes and a group of item nodes; receiving a ratings matrix representing preferences of users for items in the training data set, with each cell in the ratings matrix containing a value representing a rating of one of the items by one of the users; receiving a testing data set containing a plurality of nodes including a group of user nodes and a group of item nodes; generating deviation bound data including a deviation bound for each user and each item in the training data set; learning values for edge weights in the testing data set based on the training data set and the ratings matrix and storing the edge weights in a first weight matrix, the learning including performing a fast Max-Margin Matrix Factorization routine with a logistic loss function; generating an expanded graph data structure including nodes of the testing data set and additional dummy nodes; generating a second weight matrix including values from the first weight matrix corresponding to nodes from the testing data set and additional values corresponding to the dummy nodes, the additional values being determined based on a portion of the deviation bound data; constraining the expanded graph data structure nodes corresponding to the testing data set nodes to a predetermined degree value and not constraining the dummy nodes in the expanded graph data structure; determining a maximum weight b-matching based on the expanded graph data structure and the second weight matrix, where b is set to the predetermined degree value, the determining including updating a belief value corresponding to each neighboring item node of a selected user node in the expanded graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule, and storing each updated belief value and each received message in an electronic storage associated with the selected user node; truncating the intermediate graph data structure so that only the nodes corresponding to the nodes of the testing data set remain; and generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output. - View Dependent Claims (73, 74, 75, 76, 77)
-
Specification