SYSTEMS AND METHODS FOR MAKING RECOMMENDATIONS USING MODEL-BASED COLLABORATIVE FILTERING WITH USER COMMUNITIES AND ITEMS COLLECTIONS
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.
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 1 (τ n ) y 2 (τ 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 1 (τ n ), y 2 (τ 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 (τ n−1 ); 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 1 (τ n ), y 2 (τ 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 ; τ n−1 ), 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 1 (τ n ), y 2 (τ 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 ij Q*(y l |u i ′, v j ; τ n−1 ) and where Pr D is a sum across y l ′ and v l ′ of e ij Q*(y l ′|u i , v j ′; τ n−1 ).
9 . The computer-implemented method of claim 7 further comprising programming the one or more processors to construct the user communities y 1 (τ n ), y 2 (τ 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 ij Q*(y l |u i , v j ′; τ n−1 ) and where Pt D is a sum across y l ′ and v j ′ of e ij Q*(y l ′|u i , v j ′; τ n−1 ).
10 . The computer-implemented method of claim 7 further comprising programming the one or more processors to construct the user communities y 1 (τ n ), y 2 (τ 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 1 (τ n ), y 2 (τ 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 2 (τ 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 1 (τ n ), Y 2 (τ 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 ij Q*(y l |u i ′, v j ; τ) and Pr D1 is a sum across u i ′ and v j ′ of e ij Q*(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 1 (τ n ), y 2 (τ 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 ij Q*(y l |u i , v j ′; τ n ) and Pr D2 is a sum across y l ′ and v j ′ of e ij Q*(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 2 (τ 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 1 (τ n ), z 2 (τ 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 (τ n−1 ), 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 1 (τ n ), z 2 (τ 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 (τ n−1 ); 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 1 (τ n ), z 2 (τ 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 ; τ n−1 ), 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 1 (τ n ), z 2 (τ 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 ij Q*(z k |s i ′; τ n−1 ) and where Pr D is a sum across z k ′ and t j ′ of e ij Q*(z k ′|s i , t j ′; τ n−1 ).
22 . The computer-implemented method of claim 20 further comprising programming the one or more processors to construct item collections z 1 (τ n ), z 2 (τ 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 ij Q*(z k |s i , t j ′; τ n−1 ) and where Pr D is a sum across z k ′ and t j ′ of e ij Q*(z k ′|s i , t j ; τ n−1 ).
23 . The computer-implemented method of claim 20 further comprising programming the one or more processors to construct item collections z 1 (τ n ), z 2 (τ 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 1 (τ n ), z 2 (τ 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 1 (τ n ), z 2 (τ 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 1 (τ n ), z 2 (τ 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 ij Q*(z k |s i ′, t j ; τ) and Pr D1 is a sum across s i ′ and t j ′ of e ij Q*(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 1 (τ n ), z 2 (τ 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 ij Q*(z k |s i , t j ′; τ n ) and Pr D2 is a sum across z k and t j ′ of e ij Q*(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 1 (τ n ), z 2 (τ 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 1 (τ n ), z 2 (τ n ), . . . , z k (τ n ) and y 1 (τ n ), y 2 (τ 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(τ n−1 ), 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(τ n−1 ); 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 jS o ,; τ n−1 ), 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 ijo Q*(z k , y l |u i , t j , S o ; τ n−1 ) and where Pr D is a sum across u i , t j , S o and z k ′ of e ijo Q*(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 ijo Q*(z k , y l |u i , t j , S o ; τ n−1 ) and where Pr D is a sum across u i , t j , S o and z k ′ of e ijo Q*(z k ′, y l |u i , t j , S o ; τ n−1 ).
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 ijo Q*(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 ijo Q*(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.