SYSTEMS AND METHODS FOR MAKING RECOMMENDATIONS USING MODEL-BASED COLLABORATIVE FILTERING WITH USER COMMUNITIES AND ITEMS COLLECTIONS

• US 20100169328A1
• Filed: 12/31/2008
• Published: 07/01/2010
• Est. Priority Date: 12/31/2008
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Strands Incorporated (CRIBIS Holding SRL)
• Inventors: Hangartner, Rick
• Application Number:
  US12/347,958
• Publication Number:
  US 20100169328A1
• Time in Patent Office: Days
• US Class Current: 707/751
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Massively scalable, memory and model-based techniques are an important approach for practical large-scale collaborative filtering. We describe a massively scalable, model-based recommender system and method that extends the collaborative filtering techniques by explicitly incorporating these types of user and item knowledge. In addition, we extend the Expectation-Maximization algorithm for learning the conditional probabilities in the model to coherently accommodate time-varying training data.

Claims

1. A computer-implemented method, comprising:

programming one or more processors to;

access a list of users stored in one or more user databases and a list of items stored in one or more item databases;

construct user communities of two or more users having an association there between;

construct item collections of two or more items having an association therebetween;

estimate associations between the user communities and the item collections; and

provide one or more recommendations responsive to estimating the associations; and

displaying the one or more recommendations on a display.

2. The computer-implemented method of claim 1 further comprising programming the one or more processors to access the list of users or list of items in one or more memories.

3. The computer-implemented method of claim 1 further comprising programming the one or more processors to construct the user communities by constructing time-varying user communities responsive to a time-varying list of user-user pairs.

4. The computer-implemented method of claim 3 further comprising programming the one or more processors to construct the user communities responsive to time-varying relational probabilities between the user communities and the list of users, the list of items, item collections, or combinations thereof.

5. The computer-implemented method of claim 3 further comprising programming the one or more processors to construct the user communities y₁(τ

_n) y₂(τ

_n), . . . , y_l(τ

_n) by creating an updated list E_uv(τ

_n) at a time τ

incorporating a time-varying list of user-user pairs D_uv(τ

_n) into E_uv(τ

_n) where l and n are integers.

6. The computer-implemented method of claim 5 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by;

adding (u_i, v_j, α

e_ij) to E_uv(τ

_n) for each triple (u_i, v_j, e_ij) in E_uv(τ

<sub>n−

1</sub>); and

for each pair (u_i, v_j) in D_uv(τ

_n), replacing (u_i, v_j, e_ij) with (u_i, v_j, e_ij+β

) if (u_i, v_j, e_ij) is in E_uv(τ

_n), otherwise add (u_i, v_j, β

) to E_uv(τ

_n);

where β

is a predetermined variable; and

where l, n, i, and j are integers.

7. The computer-implemented method of claim 5 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by estimating at least one of the probabilities Pr(y_l|u_i;

τ

_n)⁻

or Pr(v_j|y_l;

τ

_n)⁻

using the updated list E_uv(τ

_n) and conditional probabilities Q*(y_l|u_i, v_j;

τ

<sub>n−

1</sub>), where l, n, i, and j are integers.

8. The computer-implemented method of claim 7 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by, for each y_l and each (u_i, v_j, e_ij) in E_uv(τ

_n), estimating Pr(v_j|y_l;

τ

_n)⁻

as Pr_N/Pr_D, where Pr_N is a sum across u_i′

of e_ijQ*(y_l|u_i′

, v_j;

τ

<sub>n−

1</sub>) and where Pr_D is a sum across y_l′ and

v_l′

of e_ijQ*(y_l′

|u_i, v_j′

;

τ

<sub>n−

1</sub>).

9. The computer-implemented method of claim 7 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by, for each y_l and each (u_i, v_j, e_ij) in E_uv(τ

_n), estimating Pr(y_l|u_i;

τ

_n)⁻

as Pr_N/Pr_D where Pr_N is a sum across v_j′

of e_ijQ*(y_l|u_i, v_j′

;

τ

<sub>n−

1</sub>) and where Pt_D is a sum across y_l′ and

v_j′

of e_ijQ*(y_l′

|u_i, v_j′

;

τ

<sub>n−

1</sub>).

10. The computer-implemented method of claim 7 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by estimating conditional probabilities Q*(y_l|u_i, v_j;

τ

_n) for each y_l and each (u_i, v_j, e_ij) in E_uv(τ

_n).

11. The computer-implemented method of claim 10 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by setting Q*(y_l|u_i, v_j;

τ

_n) to Pr(v_j|y_l;

τ

_n)⁻

Pr(y_l|u_i;

τ

_n)⁻

/Q*_D where Q*_D is a sum across y_l′

of Pr(v_j|y_l′

;

τ

_n)⁻

Pr(y_l′

|u_i;

τ

_n).

12. The computer-implemented method of claim 10 further comprising programming the one or more processors to construct the user communities y_l(τ

_n), y₂(τ

_n), . . . , t_l(τ

_n) by estimating probabilities Pr(y_l|u_i;

τ

_n)⁺ and Pr(v_j|y_l;

τ

_n)⁺ for each y_l and each (u_i, v_j, e_ij) in E_uv(τ

_n).

13. The computer-implemented method of claim 12 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), Y₂(τ

_n), . . . , y_l(τ

_n) by setting Pr(v_j|y_l;

τ

_n)⁺ to Pr_N1/Pr_D1 where Pr_N1 is a sum across u_i′

of e_ijQ*(y_l|u_i′

, v_j;

τ

) and Pr_D1 is a sum across u_i′ and

v_j′

of e_ijQ*(y_l|u_i′

, v_j′

;

τ

_n).

14. The computer-implemented method of claim 13 further comprising programming the one or more processors to construct the user communities y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by setting Pr(y_l|u_i;

τ

_n)⁺ to Pr_N2/Pr_D2 where Pr_N2 is a sum across v_j′

of e_ijQ*(y_l|u_i, v_j′

;

τ

_n) and Pr_D2 is a sum across y_l′ and

v_j′

of e_ijQ*(y_l′

|u_i, v_j′

;

τ

_n).

15. The computer-implemented method of claim 14 further comprising programming the one or more processors to construct the user communities y_l(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) by;

repeating the estimating conditional probabilities Q*(y_l,|u_i, v_j;

τ

_n) and the estimating probabilities Pr(y_l|u_i;

τ

_n) and Pr(v_j|y_l;

τ

_n)⁺ with Pr(v_j|y_l;

τ

_n)⁻

=Pr(v_j|y_l;

τ

_n)⁺ and Pr(y_l|u_j;

τ

_n)⁻

=Pr(y_l|u_i;

τ

_n)⁺ if |Pr(v_j|y_l;

τ

_n)⁻

−

Pr(v_j|y_l;

τ

_n)⁺|>

d or |Pr(y_l|u_i;

τ

_n)⁻

Pr(y_l|u_i;

τ

_n)⁺|>

d for a predetermined d<

<

1; and

returning the probabilities Pr(y_l|u_i;

τ

_n)=Pr(y_l|u_i;

τ

_n)⁺ and Pr(v_j|y_l;

τ

_n)=Pr(v_j|y_l;

τ

_n)⁺, the conditional probabilities Q*(y_l|u_i, v_j;

τ

_n), and the list E_uv(τ

_n) of triples (u_i, v_j, e_ij), where d is a predetermined number.

16. The computer-implemented method of claim 1 further comprising programming the one or more processors to construct the item collections by constructing time-varying items collections responsive to a time-varying list of item-item pairs.

17. The computer-implemented method of claim 16 further comprising programming the one or more processors to construct item collections responsive to time-varying relational probabilities between the item collections and the list of users, the list of items, user communities, or combinations thereof.

18. The computer-implemented method of claim 16 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by creating an updated list E_st(τ

_n) at a time τ

incorporating a time-varying list of item-item pairs D_st(τ

_n) into E_st(τ

<sub>n−

1</sub>), where k and n are integers.

19. The computer-implemented method of claim 16 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by;

adding (s_i, t_j, α

e_il) to E_st(τ

_n) for each triple (s_i, t_j, e_ij) in E_st(τ

<sub>n−

1</sub>); and

for each pair (s_i, t_j) in D_st(τ

_n) replacing (v_i, t_j, e_ij) with (s_i, t_j, e_ij+β

) if (s_i, t_j, e_ij) is in E_st(τ

_n), otherwise add (s_i, t_j, β

) to E_st(τ

_n);

where β

is a predetermined variable; and

where k, n, i, andj are integers.

20. The computer-implemented method of claim 16 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by estimating at least one of the probabilities Pr(z_k|s_i;

τ

_n)⁻

or Pr(t_j|z_k;

τ

_n)⁻

using the updated list E_st(τ

_n) and conditional probabilities Q*(z_k|s_i, t_j;

τ

<sub>n−

1</sub>), where k, n, i, and j are integers.

21. The computer-implemented method of claim 20 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by, for each Zk and each (s_i, t_j, e_ij) in E_st(τ

_n), estimating Pr(t_j|z_k;

τ

_n)⁻

as Pr_N/Pr_D, where Pr_N is a sum across s_i′

of e_ijQ*(z_k|s_i′

;

τ

<sub>n−

1</sub>) and where Pr_D is a sum across z_k′ and

t_j′

of e_ij Q*(z_k′

|s_i, t_j′

;

τ

<sub>n−

1</sub>).

22. The computer-implemented method of claim 20 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by, for each z_k and each (s_i, t_j, e_ij) in E_st(τ

_n), estimating Pr(z_k|t_i;

τ

_n)⁻

as Pr_N/Pr_D where Pr_N is a sum across t_j′

of e_ijQ*(z_k|s_i, t_j′

;

τ

<sub>n−

1</sub>) and where Pr_D is a sum across z_k′ and

t_j′

of e_ijQ*(z_k′

|s_i, t_j;

τ

<sub>n−

1</sub>).

23. The computer-implemented method of claim 20 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by estimating conditional probabilities Q*(z_k|s_i, t_j;

τ

_n) for each z_k and each (s_i, t_j, e_ij) in E_st(τ

_n).

24. The computer-implemented method of claim 23 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by setting Q*(z_k|s_i, t_j;

τ

_n) to Pr(t_j|z_k;

τ

_n)⁻

Pr(z_k|s_i;

τ

_n)⁻

/Q*_D where Q*_D is a sum across z_k′

of Pr(t_k|z_k′

;

τ

_n)⁻

Pr(z_k′

s_i;

τ

_n)⁻

.

25. The computer-implemented method of claim 23 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by estimating probabilities Pr(z_k|s_i;

τ

_n)⁺ and Pr(t_j|z_k;

τ

_n)⁺ for each z_k and each (s_i, t_j, e_ij) in E_st(τ

_n).

26. The computer-implemented method of claim 25 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by setting Pr(t_j|z_k;

τ

_n)⁺ Pr_N1/Pr_D1 where Pr_N1 is a sum across s_i′

of e_ijQ*(z_k|s_i′

, t_j;

τ

) and Pr_D1 is a sum across s_i′ and

t_j′

of e_ijQ*(z_k|s_i′

, t_j′

;

τ

_n).

27. The computer-implemented method of claim 26 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by setting Pr(z_k|s_i;

τ

_n)⁺ to Pr_N2/Pr_D2 where Pr_N2 is a sum across t_j′

of e_ijQ*(z_k|s_i, t_j′

;

τ

_n) and Pr_D2 is a sum across z_k and t_j′

of e_ijQ*(z_k′

|s_i, t_j′

;

τ

_n).

28. The computer-implemented method of claim 27 further comprising programming the one or more processors to construct item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) by;

repeating the estimating conditional probabilities Q*(z_k|s_i, t_j;

τ

_n) and the estimating probabilities Pr(z_k|s_i;

τ

_n)⁺ and Pr(t_j|z_k;

τ

_n)⁺ with Pr(t_j|z_k;

τ

_n⁻

=Pr(t_j|z_k;

τ

_n)⁺ and Pr(z_k|s_i;

τ

_n)⁻

=Pr (z_k|s_i;

τ

_n)⁺ if |Pr(t_j|z_k;

τ

_n)⁻

−

Pr(t_j|z_k;

τ

_n)⁺|>

d or |Pr(z_k|s_i;

τ

_n)⁻

−

Pr(z_k|s_i;

τ

_n)⁺|>

d for a predetermined d<

<

1; and

returning the probabilities Pr(z_k|s_i;

τ

_n)=Pr(z_k|s_i;

τ

_n)⁺ and Pr(t_j|z_k;

τ

_n)=Pr(t_j|z_k;

τ

_n)⁺, the conditional probabilities Q*(z_k|s_i, t_j;

τ

_n), and the list E_st(τ

_n) of triples (s_i, t_j, e_ij), where d is a predetermined number.

29. The computer-implemented method of claim 1 further comprising programming the one or more processors to estimate associations by constructing time-varying association probabilities between at least two item collections.

30. The computer-implemented method of claim 1 further comprising programming the one or more processors to estimate associations by constructing time-varying association probabilities between at least two item collections z₁(τ

_n), z₂(τ

_n), . . . , z_k(τ

_n) and y₁(τ

_n), y₂(τ

_n), . . . , y_l(τ

_n) responsive to probabilities Pr(y_k|u_i;

τ

_n) that u_i are members of the item collection y_l(τ

_n), probabilities Pr(t_j|z_k;

τ

_n) that the item collection z_k(τ

_n) include the t_j as members, and a time-varying list D(τ

_n) of triples (u_i, t_j, S_o).

31. The computer-implemented method of claim 30 further comprising programming the one or more processors to estimate associations by creating an updated list E(τ

_n) at a time τ

incorporating a time-varying list of triples D(τ

_n) into E(τ

<sub>n−

1</sub>), where l and n are integers.

32. The computer-implemented method of claim 31 further comprising programming the one or more processors to estimate associations by:

adding (u_i, t_j, S_o, α

e_ij) to E(τ

_n) for each 4-tuple (u_i, t_j, S_o, e_ijo) in E(τ

<sub>n−

1</sub>); and

for each triple (u_i, t_j, S_o) in D(τ

_n), replacing (u_i, t_j, S_o, e_ijo) with (u_i, t_j, e_ijo+β

) if (u_i, t_j, S_o, e_ijo) is in E(τ

_n), otherwise add (u_i, s_j, S_o, β

) to E(τ

_n);

where, β

is a predetermined variable; and

where l, n, i, j, o are integers.

33. The computer-implemented method of claim 31 further comprising programming the one or more processors to estimate associations by estimating probabilities Pr(z_k|y_l;

τ

_n)⁻

using the updated list E(τ

_n) and conditional probabilities Q*(z_k, y_l|u_i, t_jSo,;

τ

<sub>n−

1</sub>), where l, n, i, j, and o are integers.

34. The computer-implemented method of claim 33 further comprising programming the one or more processors to estimate associations by, for each y_l and z_k, estimating Pr(z_k|y_l;

τ

_n)⁻

as Pr_N/Pr_D, where Pr_N is a sum across u_i, t_j, and S_o of e_ijoQ*(z_k, y_l|u_i, t_j, S_o;

τ

<sub>n−

1</sub>) and where Pr_D is a sum across u_i, t_j, S_o and z_k′

of e_ijoQ*(z_k′

, y_l|u_i, t_j, S_o;

τ

_n1).

35. The computer-implemented method of claim 33 further comprising programming the one or more processors to estimate associations by estimating conditional probabilities Q*(z_k, y_l|u_i, s_j, S_o;

τ

_n).

36. The computer-implemented method of claim 35 further comprising programming the one or more processors to estimate associations by, each y_l and z_k, estimating probabilities Pr(z_k|y_l;

τ

_n)⁻

as Pr_N/Pr_D, where Pr_N is a sum across u_i, t_j, and S_o of e_ijoQ*(z_k, y_l|u_i, t_j, S_o;

τ

<sub>n−

1</sub>) and where Pr_D is a sum across u_i, t_j, S_o and z_k′

of e_ijoQ*(z_k′

, y_l|u_i, t_j, S_o;

τ

<sub>n−

1</sub>).

37. The computer-implemented method of claim 35 further comprising programming the one or more processors to estimate associations by estimating the probabilities Pr(z_k|y_l;

τ

_n)⁺.

38. The computer-implemented method of claim 37 further comprising programming the one or more processors to estimate associations by, for each y_l and z_k, estimating probabilities Pr(z_k|y_l;

τ

_n)⁺ as Pr_N/Pr_D, where Pr_N is a sum across u_i, t_j, and S_o of e_ijoQ*(z_k, y_l|u_i, t_j, S_o;

τ

_n) and where Pr_D is a sum across u_i, t_j, S_o and z_k′

of e_ijoQ*(z_k′

, y_l|u_i, t_j, S_o;

τ

_n).

39. The computer-implemented method of claim 37 further comprising programming the one or more processors to estimate associations by, for any pair (z_k, y_l), if |Pr(z_k|y_l;

τ

_n)⁻

−

Pr(z_k|y_l;

τ

_n)⁺|>

d for a predetermined d<

<

1 and the estimating probabilities Pr(z_k|y_l;

τ

_n)⁻

and the estimating probabilities Pr(z_k|y_l;

τ

_n)⁺ have not been repeated more than R times, repeat the estimating probabilities Pr(z_k|y_l;

τ

_n)⁻

and the estimating probabilities Pr(z_k|y_l;

τ

_n)⁺ with Pr(z_k|y_l;

τ

_n)⁻

=Pr(z_k|y_l;

τ

_n)⁺, where d is a predetermined variable and R is an integer.

40. The computer-implemented method of claim 38 further comprising programming the one or more processors to estimate associations by, for any pair (z_k, y_l) and for |Pr(z_k|y_l;

τ

_n)⁻

−

Pr(z_k|y_l;

τ

_n)⁺|>

d for a predetermined d<

<

1, let Pr(z_k|y_l;

τ

_n)⁺=[Pr(z_k|y_l;

τ

_n)⁺+Pr(z_k|y_l;

τ

_n)⁺]/2 where d is an predetermined variable.