Collaborative Filtering

Collaborative Filter is a machine learning algorithm to work as recommendation system.

Problem Setting

First, look at the problem.

img

There is a relationship between then users and items. Different users may have different preferences for different items. So the problem is how we infer the user's preference, or given the matrix like above image, how can we estimate the missing values.

---

Assumption

Collaborative Filtering assumes each item has a few features, and each user has respective preferences of these features.

Let's say the number of features of the items or the number of preferences of users is K. User number is M and item number is N. Then there are M*K parameters on the users side, and N*K ones on the item side. We have some scores/relations M*N but some elements are missed.

So, let X be preference matrix, whose shape is (M, K), and Theta be feature matrix, whose shape is (N,K). Y is the scores matrix (M, N). Finally, Let R be the selective matrix, which indicate which elements in the Y is not missed.

Thus, we want to get:

X*Theta'=R

---

Training

The cost function

J(X, theta)=sum(R .* (X*theta'-Y) .* (X*theta'-Y) )
First random set the theta, then
∂J/∂X=(X*Theta'-Y).*Rtheta*
∂J/∂theta=(X*Theta'-Y).*RX*

---

Prediction

p=X*theta

more