Collaborative filtering with mixtures of bayesian networks

• US 6,496,816 B1
• Filed: 12/23/1998
• Issued: 12/17/2002
• Est. Priority Date: 12/04/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Chickering, David Maxwell, Heckerman, David Earl, Thiesson, Bo
• Primary Examiner(s): Powell, Mark R
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/220,199
• Time in Patent Office: 1,455 Days
• Field of Search: 706/10, 706/50, 706/52
• US Class Current: 706/52
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

One aspect of the invention is the construction of mixtures of Bayesian networks. Another aspect of the invention is the use of such mixtures of Bayesian networks to perform inferencing. A mixture of Bayesian networks (MBN) consists of plural hypothesis-specific Bayesian networks (HSBNs) having possibly hidden and observed variables. A common external hidden variable is associated with the MBN, but is not included in any of the HSBNs. The number of HSBNs in the MBN corresponds to the number of states of the common external hidden variable, and each HSBN is based upon the hypothesis that the common external hidden variable is in a corresponding one of those states. In one mode of the invention, the MBN having the highest MBN score is selected for use in performing inferencing. In another mode of the invention, some or all of the MBNs are retained as a collection of MBNs which perform inferencing in parallel, their outputs being weighted in accordance with the corresponding MBN scores and the MBN collection output being the weighted sum of all the MBN outputs. In one application of the invention, collaborative filtering may be performed by defining the observed variables to be choices made among a sample of users and the hidden variables to be the preferences of those users.

Claims

1. A method in a computer system for predicting a desired preference of a user based on attributes of the user, comprising the computer-implemented steps of:

receiving a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs) having nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, each of said HSBNs containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user, the preference nodes reflecting available preferences of the user;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attribute and preference values for a given user;

for each HSBN, determining the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes of the HSBN given the values of the attribute nodes of the HSBN; and

indicating the available preference having the greatest likelihood of being the desired preference to the user.

2. In a decision support system that receives as an input on a signal-bearing medium data representing attributes of a user, an apparatus having a collaborative filtering system for predicting a desired preference of a user based on an attribute of the user, comprising:

a processor;

a memory having executable instructions stored therein; and

wherein said processor, in response to instructions stored in memory;

creates a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs) having nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, each of said HSBNs containing an attribute node and preference nodes, the attribute node reflecting an attribute of the user, the preference nodes reflecting available preferences of the user;

provides the created belief network to the collaborative filtering system;

receives a request by the collaborative filtering system to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attribute and preference values for a given user;

for each HSBN, determines the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes of the HSBN given the value of the attribute node of the HSBN; and

indicates the available preference having the greatest likelihood of being the desired preference to the user.

3. In a decision support system that receives, as an input on a signal-bearing medium, observed data representing available preferences of a user, an apparatus having collaborative filtering system for predicting a desired preference of a user, comprising:

a processor;

a memory having executable instructions stored therein; and

wherein said processor, in response to instruction stored in memory;

provides a mixture of Bayesian networks comprising plural hypothesis-specific Bayesian networks (HSBNs), each of said HSBNs containing a hidden attribute node and preference nodes, the hidden attribute node reflecting an unobserved attribute of the user that causally influences the desired preference, each HSBN corresponding to a hypothesis that said hidden attribute node is in a particular state, the preference nodes reflecting available preferences of the user, each of said attribute and preference nodes storing a set of probability parameters and structure representing dependence relationships among said nodes;

receives the observed data containing values for the preference nodes;

for each one of said HSBNs, conducts a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifying the probability parameters of said one HSBN accordingly;

for each one of said HSBNs, computes a structure score of said one HSBN reflecting the goodness of said one HSBN in predicting said observed data, conducts a structure search for a change in said structure which improves said structure search score, and modifies the structure of said one HSBN accordingly;

receives a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attributes and preference values of a given user;

determines an available preference having the greatest likelihood of being the desired preference by evaluating, for each HSBN, the individual probabilities of the preference nodes given the value for the at least one preference node; and

computing a weighted average over said individual probabilities and indicating the available preference having the greatest likelihood of being the desired preference to the user.

4. A method in a collaborative filtering system for predicting a desired preference of a user, comprising the computer-implemented steps of:

providing a mixture of Bayesian networks comprising plural hypothesis-specific Bayesian networks (HSBNs), each of said HSBNs containing a hidden attribute node and preference nodes, the hidden attribute node reflecting an unobserved attribute of the user that causally influences the desired preference, each HSBN corresponding to a hypothesis that said hidden attribute node is in a particular state, the preference nodes reflecting available preferences of the user, each of said attribute and preference nodes storing a set of probability parameters and structure representing dependence relationships among said nodes;

receiving data containing values for the preference nodes;

for each one of said HSBNs, conducting a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifying the probability parameters of said one HSBN accordingly;

for each one of said HSBNs, computing a structure score of said one HSBN reflecting the goodness of said one HSBN in predicting said observed data, conducting a structure search for a change in said structure which improves said structure search score, and modifying the structure of said one HSBN accordingly;

receiving into the collaborative filtering system said MBN;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attributes and preference values of a given user;

determining an available preference having the greatest likelihood of being the desired preference by evaluating, for each HSBN, the individual probabilities of the preference nodes given the value for the at least one preference node; and

computing a weighted average over said individual probabilities and indicating the available preference having the greatest likelihood of being the desired preference to the user.

5. The apparatus of claim 4 wherein the processor computes said ECMSS, in that the processor:

computes the probability of each combination of the states of the discrete hidden and observed variables;

forms a vector for each observed case in said set of observed data, each entry in said vector corresponding to a particular one of the combinations of the states of said discrete variables; and

sums the vectors over plural cases of said observed data.

6. In a decision support system that receives as an input on a signal-bearing medium observed data representing user attributes, a collaborative filtering system for predicting a desired preference of a user based on attributes of the user, comprising:

a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs) having nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, each of said HSBNs containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user, the preference nodes reflecting available preferences of the user;

a receive component for receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attribute and preference values of a given user;

a determination component for determining the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes given the values of the attribute nodes; and

an output component for indicating the available preference having the greatest likelihood of being the desired preference.

7. A collaborative filtering system for predicting a desired preference of a user based on attributes of the user, comprising:

a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs) having nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, each of said HSBNs containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user, the preference nodes reflecting available preferences of the;

a receive component for receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attribute and preference values of a given user;

a determination component for determining the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes given the values of the attribute nodes; and

an output component for indicating the available preference having the greatest likelihood of being the desired preference.

8. The collaborative filtering system of claim 7 wherein the attribute nodes of each HSBN contain discrete values and the preference nodes contain discrete values.

9. The collaborative filtering system of claim 7 wherein at least one of the attribute nodes contains a non-numerical value.

10. The collaborative filtering system of claim 7 wherein at least one of the preference nodes contains a non-numerical value.

11. In a decision support system that receives as an input on a signal-bearing medium data representing attributes of a user, a method for predicting a desired preference of a user based on the attributes of the user, comprising:

receiving on the signal-bearing medium the data representing the attributes of the user;

providing a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypotheses-specific Bayesian networks (HSBNs) having nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, each of said HSBNs containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user, the preference nodes reflecting available preferences of the user;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attribute and preference values for a given user;

for each HSBN, determining the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes of the HSBN given the values of the attribute nodes of the HSB; and

indicating the available preference having the greatest likelihood of being the desired preference to the user.

12. A computer-readable medium storing computer-executable instructions for performing the steps of claim 11.

13. In a decision support system that receives as an input n a signal-bearing medium data representing attributes of a user, a method of performing collaborative filtering for predicting a desired preference of a user based on an attribute of the user, comprising:

receiving on the signal-bearing medium the data representing the attributes of the user;

creating a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs) having nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, each of said HSBNs containing an attribute node and preference nodes, the attribute node reflecting an attribute of the user, the preference nodes reflecting available preferences of the user;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attribute and preference values for a given user;

for each HSBN, determining the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes of the HSBN given the value of the attribute node of the HSBN; and

indicating the available preference having the greatest likelihood of being the desired preference to the user.

14. A computer-readable medium storing computer-executable instructions for performing the steps of claim 13.

15. In a decision support system that receives, as an input on a signal-bearing medium, observed data representing available preferences of a user, a collaborative filtering method for predicting a desired preference of a user, comprising:

receiving the data on the signal-bearing medium;

producing a mixture of Bayesian networks comprising plural hypothesis-specific Bayesian networks (HSBNs), each of said HSBNs containing a hidden attribute node and preference nodes, the hidden attribute node reflecting an unobserved attribute of the user that casually influences the desired preference, each HSBN corresponding to a hypothesis that said hidden attribute node is in a particular state, the preference nodes reflecting available preferences of the user, each of said attribute and preference nodes storing a set of probability parameters and structure representing dependence relationships among said nodes;

for each one of said HSBNs, conducting a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifying the probability parameters of said one HSBN accordingly;

for each one of said HSBNs, computing a structure score of said one HSBN reflecting the goodness of said one HSBN in predicting said observed data, conducting a structure search for a change in said structure which improves said structure search score, and modifying the structure of said one HSBN accordingly;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request consisting of attributes and preference values of a given user;

determining an available preference having the greatest likelihood of being the desired preference by evaluating, for each HSBN, the individual probabilities of the preference nodes given the value for the at least one preference node; and

computing a weighted average over said individual probabilities and indicating the available preference having the greatest likelihood of being the desired preference to the user.

16. A computer-readable medium storing computer-executable instructions for performing the steps of claim 15.