A preview:
Our presentation will pull together material from various sources - see the references below. But most of it will come from [Bree1998], [Grif2000], [Herl1999], [Roth2008], and [Su2009].
Consider an abstract market:
The standard approach: a supply-demand marketplace with prices
Market failures:
Let's examine an abstract market along two dimensions:
First, let's describe the problem:
The Proposal Algorithm:
Exercise: Who gets the better deal - men or women?
Algorithm: proposal (M, W) Input: n men M_{1},...,M_{n} and n women W_{1},...,W_{n} with their rankings 1. Add all men to freeList 2. while freeList is not empty 3. M = remove a man from freeList 4. W = highest-ranked woman he has not yet proposed to 5. if W is unengaged 6. M and W are engaged 7. else if W prefers M to her fiance M' 8. M and W are engaged 9. M' is placed on the free list 10. endif 11. endwhile
Does the algorithm work?
History of the stable marriage problem:
Other applications and developments:
A natural extension to the marriage problem is the matching problem:
Types of matching problems:
There are many versions of this problem, but let's start with the most elementary version:
Three different approaches to text retrieval:
Let's look into the details of the latter two:
What is data mining?
Transaction #1: eggs, milk, cookies Transaction #2: beer, chips, pretzels, popcorn ... Transaction #i: beer, chips, diapers ... Transaction #6,391,202: wine, brie, diapers
Amazon's recommendation engine:
1. Initialize purchase-pair-set S = φ 2. for each item i 3. for each customer c who purchased i 4. for each item j purchased by c 5. S = S U {(i,j)} 6. endfor 7. endfor 8. endfor 9. for each item-pair in φ 10. compute similarity-score for (x,y) // The score is the cosine distance between two items. 11. endfor 12. endfor
What is collaborative filtering (CF)?
1 2 3 4 5 6 7 8 Alice | 1 5 5 3 | Bob | 4 2 1 2 | Chen | 1 | Dave | 2 4 3 | Ella | 5 1 1 5 |
Approaches to CF:
The data-driven approach:
Algorithm: userSimilarity (A, u, v) Input: ratings matrix A, and desired missing entry A[u,v] // Compute distances to other users. 1. for each user i 2. s[i] = similarity (i, u) 3. endfor // Find a set of "close" or similar users. 4. similar-user-set S = φ 5. for each user i that has rated item j 6. if similarEnough (i, u) 7. add i to S 8. endif 9. endfor // Use the ratings of these users to predict user u's rating v. 10. r = combineRatings (S, v) 11. return r
1 2 3 4 5 6 7 8 Alice | 1 5 5 3 | Bob | 4 2 1 2 | Chen | 1 | Dave | 2 4 3 | Ella | 5 1 1 5 |
Exercise: What is the cosine of the angle between the "Alice" and "Dave" vectors? What is the cosine of the angle between the "Alice" and "Chen" vectors?
1 2 3 4 5 6 7 8 Alice | 1 5 5 3 | Bob | 4 2 1 2 | Chen | 1 | Dave | 2 4 3 | Ella | 5 1 1 5 |
Model-based approaches:
Simple clustering:
1 2 3 4 5 6 7 8 Alice | 1 5 5 3 | Bob | 4 2 1 2 | Chen | 1 | Dave | 2 4 3 | Ella | 5 1 1 5 | Sci-fi | 0 5 0 5 0 0 0 0 | // Movies 3 and 5 are sci-fi movies. Rest of the ratings are 0.
This is called K-means clustering.
Algorithm: K-means (A, u, v) Input: ratings matrix A, and desired missing entry A[u,v] 1. for each user i // Initially assign each user to a random cluster. 2. cluster[i] = random (1, K) 3. endfor 4. while not converged // Find the mean of each cluster and assign users to the cluster whose mean they are closest to. 5. M_{k} = computeMean (C_{k}) 6. for each user i 7. find closest cluster mean k 8. cluster[i] = k 9. endfor 10. endwhile 11. k = cluster for user u 12. S = users in C_{k} that have rated v 13. r = combineRatings (S, v) 14. return r
A probabilistic approach: the Naive-Bayes method
Algorithm: naiveBayes (A, u, v) Input: ratings matrix A, and desired missing entry A[u,v] // Estimate Pr[U_{v}=r]. 1. for each rating value r 2. num_v_r = # users that rated v as r 3. num_v = # users that rated v 4. RatingEstimate[r] = num_v_r / num_v 5. endfor // Estimate Pr[u_{i} | U_{v}=r] for each possible i and r. 6. for each r 7. for each item j ≠ v 8. num_u_j_r = # users that rate j as u_{j} and v as r 9. num_v_r = # users that rated v as r 10. conditionalRating[j] = num_u_j_r / num_v_r 11. endfor 12. endfor // Estimate Pr[U_{v}=r | u_{1},...,u_{n}] using the product and identify the largest. 13. r_{max} = 0 14. for each r 15. product[r] = ratingEstimate[r] 16. for each item j ≠ v 17. product[r] = product[r] * conditionalRating[j] 18. endfor 19. if product[r] > r_{max} 20. r_{max} = product[r] 21. endif 22. endfor 23. return r_{max}
Machine learning:
1 2 3 4 5 6 7 8 Alice | 1 5 5 3 3 | Bob | 4 2 1 2 | Chen | 1 | Ella | 5 1 1 5 | Dave | 2 4 2 3 ? | // Desired missing entry is for last user and last item.
TRAINING VECTORS CLASS Alice | 1 5 5 3 | 3 | Bob | 4 2 1 | 2 | Ella | 5 1 1 | 5 | QUERY VECTOR Dave | 2 4 2 3 | ? |
TRAINING QUERY 2 4 5 7 8 Alice | 1 5 5 3 | 3 | Bob | | 2 | Chen | 1 | | Ella | 5 1 1 | 5 | Dave | 2 4 2 3 | ? | <- class (y) values
[WP-1]
Wikipedia entry on Collaborative filtering.
[WP-2]
Wikipedia entry on the Stable Marriage problem.
[Agra1993]
R.Agrawal, T.Imielinski and A.Swami.
Mining Association Rules between Sets of Items in Large Databases.
SIGMOD, 1993.
[Agra1994]
R.Agrawal and R.Srikant.
Fast algorithms for mining associative rules.
VLDB, 1994.
[Basu1998]
C.Basu, H.Hirsh and W.Cohen.
Recommendation as classification: using social and content-based information
in recommendation.
AAAI ¡¦98, pp. 714¡V720, July 1998.
[Bill1998]
D.Billsus and M.Pazzani.
Learning collaborative information filters.
Int. Conf. on Machine Learning (ICML ¡¦98), 1998.
[Bree1998]
J.Breese, D.Heckerman and C.Kadie.
Empirical analysis of predictive algorithms for collaborative filtering.
Proc. 14th Conf. Uncertainty in Artificial
Intelligence (UAI ¡¦98), 1998.
[Deer1990]
S.Deerwester, S.T.Dumais, G.W.Furnas, T.K.Landauer and R.Harshman.
Indexing by latent semantic analysis.
J.Am.Soc.Info.Sci., vol.41, no. 6, pp.391-407, 1990.
[Gale1962]
D.Gale and L.S.Shapley.
College Admissions and the Stability of Marriage.
American Mathematical Monthly, Vol.69, pp.9-14, 1962.
[Gold1992]
D.Goldberg, D.Nichols, B.M.Oki and D.Terry.
Using collaborative filtering to weave an information Tapestry.
Comm. ACM, vol. 35, no. 12, pp. 61¡V70, 1992.
[Grif2000]
J.Griffith and C.O'Riordan.
Collaborative filtering.
Technical report NUIG-IT-160900, National University of Ireland.
[Herl1999]
J.L.Herlocker, J.A.Konstan, A.Borchers and J.Riedl.
An algorithmic framework for performing collaborative
filtering.
Conf. Res. Dev. Information Retrieval (SIGIR ¡¦99),
pp.230¡V237, 1999.
[Hill1995]
W.Hill, L.Stead, M.Rosenstein and G.Furnas.
Recommending and evaluating choices in a virtual
community of use.
ACM Conf. Human Factors in Computing, pp.194-201, 1995.
[Kore2009]
Y. Koren,
The BellKor Solution to the Netflix Grand Prize.
(2009).
[Lind2003]
G.Linden, B.Smith and J.York.
Amazon.com recommendations: item-to-item collaborative
filtering.
IEEE Internet Computing, January 2003.
[Mann2008]
C.D.Manning, P.Raghavan and H.Schutze.
Introduction to Information Retrieval,
Cambridge University Press. 2008.
(Also available in
PDF.)
[Moon1999]
R.J.Mooney and L.Roy.
Content-Based Book Recommending Using Learning for Text Categorization.
ACM Conf. Digital Libraries, 1999.
[Piot2009]
M.Piotte and M.Chabbert.
The Pragmatic Theory solution to the Netflix Grand Prize,
2009.
[Resn1994]
P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl.
Grouplens: an open architecture for collaborative filtering of netnews.
Proc. ACM Conf. Computer Supported Cooperative Work,
pp. 175¡V186, New York, NY, 1994.
[Roth2008]
A.E.Roth
Deferred Acceptance Algorithms: History, Theory, Practice,
and Open Questions.
Int. J. Game Theory,
Vol. 36, March, 2008, pp.537-569.
[Sarw2001]
B.M.Sarwar, G.Karypis, J.A.Konstan and J.Riedl.
Item-based collaborative filtering recommendation algorithms.
10th Int. Conf. World Wide Web (WWW ¡¦01),
pp. 285¡V295, May 2001.
[Sing2001]
A.Singhal.
Modern information retrieval: An overview.
Bulletin of the IEEE Computer Society Technical
Committee on Data Engineering, 24:4, 2001.
[Su2009]
X.Su and T.M.Khoshgoftar.
A survey of collaborative filtering techniques.
Adv. AI, Vol. 2009,
Article ID 421425, 19 pages, 2009. doi:10.1155/2009/421425.
[Tosc2009]
A. Toscher, M. Jahrer, R. Bell.
The BigChaos Solution to the Netflix Grand Prize.
2009.
[Unga1998]
L.H.Ungar and D.P.Foster.
Clustering methods for collaborative filtering.
Workshop on Recommendation Systems, 1998.