Collaborative filtering utilizing a belief network

• US 5,704,017 A
• Filed: 02/16/1996
• Issued: 12/30/1997
• Est. Priority Date: 02/16/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chickering, David Maxwell, Horvitz, Eric, Heckerman, David E., Breese, John S.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Rhodes, Jason W.
• Application Number:
  US08/602,238
• Time in Patent Office: 683 Days
• Field of Search: 395/62, 395/61, 395/77, 395/50, 395/51, 395/10, 395/11, 395/12, 395/13
• US Class Current: 706/12
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04N 21/252 Processing of multiple end-users' preferences to derive collaborative data

Abstract

The disclosed system provides an improved collaborative filtering system by utilizing a belief network, which is sometimes known as a Bayesian network. The disclosed system learns a belief network using both prior knowledge obtained from an expert in a given field of decision making and a database containing empirical data obtained from many people. The empirical data contains attributes of users as well as their preferences in the field of decision making. After initially learning the belief network, the belief network is relearned at various intervals when additional attributes are identified as having a causal effect on the preferences and data for these additional attributes can be gathered. This relearning allows the belief network to improve its accuracy at predicting preferences of a user. Upon each iteration of relearning, a cluster model is automatically generated that best predicts the data in the database. After relearning the belief network a number of times, the belief network is used to predict the preferences of a user using probabilistic inference. In performing probabilistic inference, the known attributes of a user are received and the belief network is accessed to determine the probability of the unknown preferences of the user given the known attributes. Based on these probabilities, the preference most likely to be desired by the user can be predicted.

Claims

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

receiving into the collaborative filtering system a belief network containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user and having a value, the preference nodes reflecting available preferences of the user, each preference node having a probability indicating the likelihood that the available preference is the desired preference of the user given the values of the attribute nodes;

receiving into the collaborative filtering system a request to determine an available preference having a greatest likelihood of being the desired preference, the request coutaining values for the attribute nodes;

determining by the collaborative tiltering system 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

indicating by the collaborative filtering system the available preference having the greatest likelihood of being the desired preference to the user.

2. The method of claim 1, including the steps of, for each available preference, calculating by the collaborative filtering system a likelihood that the available preference is the desired preference given the values of the attribute nodes and indicating by the collaborative filtering system the calculated likelihood to the user.

3. A method in a computer system having a collaborative filtering system for predicting a desired preference of a user based on an attribute of the user, comprising the computer-implemented steps of:

creating a belief network containing an attribute node and preference nodes, the attribute node reflecting an attribute of the user and having a value, the preference nodes reflecting available preferences of the user, each preference node having a probability indicating a likelihood that the available preference is the desired preference of the user given the value of the attribute node;

providing the created belief network to the collaborative filtering system;

receiving a request by the collaborative filtering system to determine an available preference having a greatest likelihood of being the desired preference, the request containing a value for the attribute node;

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

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

4. The method of claim 3 wherein the step of creating a belief network includes the steps of:

receiving expert data comprising an initial belief network containing a hidden attribute node and at least one preference node, the hidden attribute node being an unknown factor that causally influences the available preferences;

receiving data comprising sets of values for the preference nodes;

determining groups of sets having similar values, wherein each group has a plurality of sets of values;

receiving an indication of a causal factor in the determined groups to account for the similarity of the values in the sets of values in the groups;

receiving observations for the identified causal factor and adding the observations to the data; and

adding the causal factor to the initial belief network as an attribute node after receiving the observations, and

wherein the step of providing the created belief network includes providing the initial belief network to the collaborative filtering system.

5. The method of claim 4 wherein the steps of determining groups, receiving an indication, receiving observations and adding the causal factor are repeatedly performed until either a causal factor cannot be identified or observations for the causal factor cannot be gathered.

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

receiving a belief network into the collaborative filtering system, the belief network 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, the preference nodes reflecting available preferences of the user, each preference node having a value and having a probability indicating a likelihood that the available preference is the desired preference of the user given the values of the preference nodes;

receiving data containing values for the preference nodes;

receiving a plurality of a number of states for the hidden attribute node;

for each number of states for the hidden attribute node,

generating a belief network having the preference nodes and the hidden attribute node, wherein the hidden attribute node has the number of states; and

scoring the generated belief network for goodness in predicting the desired preference based on the data;

selecting a generated belief network having a best goodness in predicting the desired preference based on the data;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request containing a value for at least one of the preference nodes;

determining an available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes in the selected belief network given the value for the at least one preference node; and

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

7. A method in a computer system for generating a belief network containing caused variables and unbidden causal variables, the computer system having a decision support system, the belief network for providing decision support in a given field of expertise, the caused variables reflecting a decision to be rendered by the decision support system and the causal variables reflecting factors that causally effect the decision, comprising the computer-implemented steps of:

receiving expert data from an expert in the given field comprising a belief network containing a hidden causal variable and caused variables and wherein the expert data includes a plurality of a number of states for the hidden causal variable, the hidden causal variable being an unknown factor that causally influences the caused variables;

receiving data comprising sets of values for the caused variables after receiving the expert data;

determining groups of sets in the received data having similar values;

receiving an indication of a causal factor in the determined groups to account for the similarity of the values in each group;

receiving observations for the identified causal factor and adding the observations to the data;

adding the causal factor to the belief network as an unbidden causal variable after receiving the observations;

receiving a new plurality of a number of states for the hidden causal variable after adding the causal factor; and

repeatedly performing the steps of determining groups, receiving an indication, receiving observations, adding the causal factor and receiving a new plurality of a number of states until either a causal factor cannot be identified to account for the similarity of the values in each group or observations for the causal factor cannot be obtained.

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

a belief network containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user and having a value, the preference nodes reflecting available preferences of the user, each preference node having a probability indicating a likelihood that the available preference is the desired preference of the user given the values of the attribute nodes;

a receive component for receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request containing values for the attribute nodes;

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.

9. The collaborative filtering system of claim 8 wherein the attribute nodes of the belief network contain discrete values and the preference nodes contain discrete values.

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

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

12. The collaborative filtering system of claim 8 wherein one of the attribute nodes contains a known preference of the user.

13. A computer-readable memory device containing:

a data structure representing a belief network that comprises nodes, the belief network for use in a collaborative filtering system for predicting a desired preference of a user based on attributes of the user, the nodes further comprising;

attribute nodes reflecting the attributes of the user, wherein each attribute node has a value; and

preference nodes reflecting available preferences of the user, each preference node having a probability indicating a likelihood that the available preference is the desired preference of the user given the values of the attribute nodes, wherein the collaborative filtering system receives a request for determining a desired preference of a user among the available preferences, wherein the request contains values for the attribute nodes and in response to receiving the request, the collaborative filtering system evaluates the probabilities of the preference nodes to determine the available preference that is most likely to be the desired preference given the values for the attribute nodes in the request.

14. A computer-readable media that causes a collaborative filtering system in a computer system to predict a desired preference of a user based on attributes of the user, by performing the steps of:

receiving a belief network into the collaborative filtering system, the belief network containing attribute nodes and preference nodes, the attribute nodes reflecting the attributes of the user and having a value, the preference nodes reflecting available preferences of the user, each preference node having a probability indicating the likelihood that the available preference is the desired preference of the user given the values of the attribute nodes;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request containing values for the attribute nodes;

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

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

15. A computer-readable media that causes a collaborative filtering system in a computer system to predict a desired preference of a user based on an attribute of the user, by performing the steps of:

creating a belief network containing an attribute node and preference nodes, the attribute node reflecting an attribute of the user and having a value, the preference nodes reflecting available preferences of the user, each preference node having a probability indicating a likelihood that the available preference is the desired preference of the user given the value of the attribute node;

providing the created belief network to the collaborative filtering system;

receiving a request by the collaborative filtering system to determine an available preference having a greatest likelihood of being the desired preference, the request containing a value for the attribute node;

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

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

16. A computer-readable media that causes a collaborative filtering system in a computer system to predict a desired preference of a user, by performing the steps of:

receiving a belief network into the collaborative filtering system, the belief network containing a hidden attribute node and preference nodes, the hidden attribute node reflecting an unobserved attribute of the user that causally influence the desired preference, the preference nodes reflecting available preferences of the user, each preference node having a value and having a probability indicating a likelihood that the available preference is the desired preference of the user given the values of the preference nodes;

receiving data containing values for the preference nodes;

receiving a range of a number of states for the hidden attribute node;

for each number of states for the hidden attribute node,

generating a belief network having the preference nodes and the hidden attribute node, wherein the hidden attribute node has the number of states; and

scoring the generated belief network for goodness in predicting the desired preference based on the data;

selecting a generated belief network having a best goodness in predicting the desired preference based on the data;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request containing a value for at least one of the preference nodes;

determining an available preference having the greatest likelihood of being the desired preference by accessing the generated belief network having the best goodness and evaluating the probabilities of the preference nodes given the value for the at least one preference node; and

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

17. A computer-readable media that causes a computer system to generate a belief network containing caused variables and unbidden causal variables, the computer system having a decision support system, the belief network for providing decision support in a given field of expertise, the caused variables reflecting a decision to be rendered by the decision support system and the causal variables reflecting factors that causally effect the decision, by performing the steps of:

receiving expert data from an expert in the given field comprising a belief network containing a hidden causal variable and caused variables and wherein the expert data includes a plurality of a number of states for the hidden causal variable, the hidden causal variable being an unknown factor that causally influences the caused variables;

receiving data comprising sets of values for the caused variables after receiving the expert data;

determining groups of sets in the received data having similar values;

receiving an indication of a causal factor in the determined groups to account for the similarity of the values in each group;

receiving observations for the identified causal factor and adding the observations to the data after identifying a causal factor;

adding the causal factor to the belief network as an unhidden causal variable after receiving the observations;

receiving a new plurality of a number of states for the hidden causal variable after adding the causal factor; and

repeatedly performing the steps of determining groups, receiving an indication, receiving observations, adding the causal factor and receiving a new range of a number of states until either a causal factor cannot be identified to account for the similarity of the values in each group or observations for the causal factor cannot be obtained.

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

receiving a belief network into the collaborative filtering system, the belief network containing preference nodes reflecting available preferences of the user, each preference node having a probability indicating the likelihood that the available preference is the desired preference of the user given a value for the characteristic of the user;

receiving a request to determine an available preference having a greatest likelihood of being the desired preference, the request containing a value for the characteristic of the user;

determining the available preference having the greatest likelihood of being the desired preference by evaluating the probabilities of the preference nodes given the value of the characteristics; and

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

19. The method of claim 18 wherein the collaborative filtering system predicts a desired song of a user, wherein the preference nodes of the belief network contain available songs, and wherein the step of indicating the available preference includes indicating the available song.

20. The method of claim 18 wherein the collaborative filtering system predicts a desired music video of a user, wherein the preference nodes of the belief network contain available music videos, and wherein the step of indicating the available preference includes indicating the available music video having the greatest likelihood of being the desired music video.

21. The method of claim 18 wherein the collaborative filtering system predicts desired music to be purchased by a user, wherein the preference nodes of the belief network contain available music, and wherein the step of indicating the available preference includes indicating the available music having the greatest likelihood of being the desired music.

22. The method of claim 18 wherein the collaborative filtering system predicts a desired television show of a user, wherein the preference nodes of the belief network contain available television shows, and wherein the step of indicating the available preference includes indicating the available television show having the greatest likelihood of being the desired television show.

23. The method of claim 18 wherein the collaborative filtering system is used to incorporate a desired customization of a user into an electronic newspaper, wherein the preference nodes of the belief network contain available customizations for the electronic newspaper, and wherein the step of indicating the available preference includes indicating the available customization having the greatest likelihood of being the desired customization.

24. The method of claim 18 wherein the collaborative filtering system predicts a desired Internet page of a user, wherein the preference nodes of the belief network contain available Internet pages, and wherein the step of indicating the available preference includes indicating the available Internet page having the greatest likelihood of being the desired Internet page.

25. The method of claim 18 wherein the collaborative filtering system predicts a desired Encarta article of a user, wherein the preference nodes of the belief network contain available Encarta articles, and wherein the step of indicating the available preference includes indicating the available Encarta article having the greatest likelihood of being the desired Encarta article.

26. The method of claim 18 wherein the collaborative filtering system predicts a desired graphical layout of a user for a graphical presentation program, wherein the preference nodes of the belief network contain available graphical layouts, and wherein the step of indicating the available preference includes indicating the available graphical layout having the greatest likelihood of being the desired graphical layout.

27. The method of claim 18 wherein the collaborative filtering system predicts a desired email alias of a user, wherein the preference nodes of the belief network contain available email aliases, and wherein the step of indicating the available preference includes indicating the available email alias having the greatest likelihood of being the desired email alias.

28. The method of claim 18 wherein the request includes a selection criteria, wherein the step of determining the available preference includes determining the available preference that has the greatest likelihood of being the desired preference and that conforms to the selection criteria, and wherein the step of indicating the available preference includes indicating the available preference that has the greatest likelihood of being the desired preference and that conforms to the selection criteria.

29. The method of claim 18 wherein the collaborative filtering system predicts a desired movie of a user, wherein the preference nodes of the belief network contain available movies, and wherein the step of indicating the available preference includes indicating the available movie having the greatest likelihood of being the desired movie.

30. The method of claim 18 wherein the collaborative filtering system predicts a desired wine of a user, wherein the preference nodes of the belief network contain available wines, and wherein the step of indicating the available preference includes indicating the available wine having the greatest likelihood of being the desired wine.

31. The method of claim 18 wherein the collaborative filtering system predicts a desired restaurant of a user, wherein the preference nodes of the belief network contain available restaurants, and wherein the step of indicating the available preference includes indicating the available restaurant having the greatest likelihood of being the desired restaurant.

32. The method of claim 18 wherein the collaborative filtering system predicts desired real estate of a user, wherein the preference nodes of the belief network contain available real estate, and wherein the step of indicating the available preference includes indicating the available real estate having the greatest likelihood of being the desired real estate.

33. The method of claim 18 wherein the collaborative filtering system predicts a desired advertisement of a user, wherein the preference nodes of the belief network contain available advertisements, and wherein the step of indicating the available preference includes indicating the available advertisement having the greatest likelihood of being the desired advertisement.

34. The method of claim 33 wherein the step of indicating the available advertisement includes viewing the available advertisement having the greatest likelihood of being the desired advertisement by the user via an on-line system.

35. The method of claim 33 wherein the step of indicating the available advertisement includes viewing the available advertisement having the greatest likelihood of being the desired advertisement by the user via an interactive television.

36. The method of claim 33 wherein the step of indicating the available advertisement includes viewing the available advertisement having the greatest likelihood of being the desired advertisement by a user via a computer network.

37. The method of claim 18 wherein the collaborative filtering system predicts desired products of a user, wherein the preference nodes of the belief network contain available products, and wherein the step of indicating the available preference includes indicating the available product having the greatest likelihood of being the desired product.

38. The method of claim 18 wherein the collaborative filtering system predicts inappropriate material that is deemed unsuitable for viewing by children, wherein the preference nodes of the belief network contain available material, and wherein the step of indicating the available preference includes indicating the available material having the greatest likelihood of being the inappropriate material.

39. The method of claim 38 wherein the available material includes music.

40. The method of claim 38 wherein the available material includes music videos.

41. The method of claim 38 wherein the available material includes movies.

42. The method of claim 38 wherein the available material includes Internet pages.

43. The method of claim 18 wherein the collaborative filtering system predicts a desired user interface of a user, wherein the preference nodes of the belief network contain available user interfaces, and wherein the step of indicating the available preference includes indicating the available user interface having the greatest likelihood of being the desired user interface.