aRecommender System

Table of Content

1. Recommender Systems 1.1. Collaborative Filtering 1.1.1. User-based Collaborative Filtering 1.1.2. Item-based Collaborative Filtering 1.1.3. Considerations on Memory-based Filtering 1.2. Matrix Factorization 1.2.1. Implicit Ratings 1.2.2. Alternating Least Squares (ALS) 1.2.3. Predicting with ALS 1.3. Deep Learning Extension 1.4. Challenges of Collaborative Filtering 1.5. Content-based Filtering 1.6. Deep Learning Recommender Systems

1. Recommender Systems1.1. Collaborative Filtering• The goal of collaborative filtering is to use the user-item matrix to get an idea of how a user would respond to an unseen item.1.1.1. User-based Collaborative Filtering• In user-based collaborative filtering, the goal is to find similar users and recommend to a a user a particular item that is used by other similar users.

p1p2p3p4u1u2110101?1 • Note: If we're using binary indicators in the user-item matrix, we can use Jaccard/Cosine/Hamming metrics to measure similarity.– – Jaccard Similarity → no. matching 1s

no. matching 1s + no. ui=1 & uj=0 + no. ui=0 & uj=1${\displaystyle \frac{\text{no. matching}1\text{s}}{\text{no. matching}1\text{s}+\text{no.}{u}_i=1\&u_j=0+\text{no.}{u}_i=0\&u_j=1}}$* * Note: We don't count the number of matching 0${\displaystyle 0}$s here.– Cosine Similarity → ∑nuiuj

∑nu2i. ∑nu2j${\displaystyle \frac{\sum _n^{}{u}_i{u}_j}{\sqrt{\sum _n^{}{u}_i^2}.\sqrt{\sum _n^{}{u}_j^2}}}$– – Hamming Distance → sum of the differences → n∑i=11(xi≠yi)${\displaystyle \sum _{i=1}^{n}1(x_i\ne y_i)}$– • How do we predict for a particular user (given the user similarities?) → responseup = ∑usim(up,ui).responseui

∑usim(up,ui)${\displaystyle res\widehat{po}ns{e}_{u_p}=\frac{\sum _u^{}sim(u_p,u_i).respons{e}_{u_i}}{\sum _u^{}sim(u_p,u_i)}}$– • Note: We can use the KNN to find k${\displaystyle k}$ number of neighbor users for prediction.• Note: We can use MSE to evaluate our predictions.• Note: Generally, we'd like to recommend the item that generates the highest predicted value.• Note: If the user-item is not binary, we can use the following similarity measures:– Euclidean– Manhattan → n∑i=1|xi-yi|${\displaystyle \sum _{i=1}^n|x_i-y_i|}$– Pearson Correlation → ∑n(u1-⏨u1)(u2-⏨u2)

∑n(u1-⏨u1)2 ∑n(u2-⏨u2)2${\displaystyle \frac{\sum _n^{}(u_1-{\overline{u}}_1)(u_2-{\overline{u}}_2)}{\sqrt{\sum _n^{}(u_1-{\overline{u}}_1{)}^2}\sqrt{\sum _n^{}(u_2-{\overline{u}}_2{)}^2}}}$– Cosine• Steps of user-based collaborative filtering:– Find KNN of ui${\displaystyle u_i}$ to form prediction for.– Calculate the similarity score between the neighbor users– Using the KNN, predict the response for ui${\displaystyle u_i}$. 1.1.2. Item-based Collaborative Filtering• Here, we use the similarity between the items to make recommendations.

p1p2p1p211.86.86u1u2u3u4u5p1p21011011110cosine • Here, we calculate the item-item similarity.• To predict user response, we use a similar formula as above → responsepl = ∑psim(pl,pi).responsepi

∑psim(pl,pi)${\displaystyle res\widehat{po}ns{e}_{p_l}=\frac{\sum _p^{}sim(p_l,p_i).respons{e}_{p_i}}{\sum _p^{}sim(p_l,p_i)}}$ • Steps of item-based collaborative filtering:– Calculate item-item similarity matrix– Predict response for ui${\displaystyle u_i}$– Recommend the item with the highest prediction 1.1.3. Considerations on Memory-based Filtering• Time complexity of user-based → O(u.p) → O(u+p)${\displaystyle O(u.p)\to O(u+p)}$– Greater diversity ↑${\displaystyle \mathbf{\uparrow }}$– More Expensive ↓${\displaystyle \mathbf{\downarrow }}$ (because of KNN calculations)• Time complexity of item-based → O(u,p2) → O(u.p)${\displaystyle O(u,p^2)\to O(u.p)}$– Less re-calculations ↑${\displaystyle \mathbf{\uparrow }}$ (items change less than users)– Lack of diversity ↓${\displaystyle \mathbf{\downarrow }}$• The user-item matrices are sparse, so the → denotes the effective time complexity.• Both user-based and item-based are collectively part of memory-based filtering.• Time Decay: We can apply time decay to the predictions as follows → responseup = ∑usim(up,ui).dt.responseui

∑usim(up,ui)${\displaystyle res\widehat{po}ns{e}_{u_p}=\frac{\sum _u^{}sim(u_p,u_i).d_t.respons{e}_{u_i}}{\sum _u^{}sim(u_p,u_i)}}$ where dt = 0.5t

half-life${\displaystyle d_t={0.5}^{\frac{t}{\text{half-life}}}}$ • – Time decay means that as time goes on, less influence will be given to a particular rating.• Inverse User Frequency: Another thing that we can do is to apply more weights to less frequent items → responsepl = ∑psim(pl,pi).fi.responsepi

∑psim(pl,pi)${\displaystyle res\widehat{po}ns{e}_{p_l}=\frac{\sum _p^{}sim(p_l,p_i).f_i.respons{e}_{p_i}}{\sum _p^{}sim(p_l,p_i)}}$ where fi=log(N

n+1)${\displaystyle f_i=\log \left(\frac{N}{n+1}\right)}$ – where * N${\displaystyle N}$ → total number of users and* n${\displaystyle n}$ → no. of users who interacted with item i${\displaystyle i}$.– fi${\displaystyle f_i}$ is called Inverse User Frequency (IUF). 1.2. Matrix Factorization• One problem withe memory-based approaches is that the user-item matrix (or item-item similarity) matrix is extremely large.• One approach we can use is Matrix Factorization → it takes the same user-item matrix and factorizes it into some terms as followsU.P = uTp + bp+bu${\displaystyle \mathit{U}\mathit{.}\mathit{P}={\tilde{\mathbf{u}}}^T\tilde{\mathbf{p}}+b_p+b_u}$• Here, both uT${\displaystyle {\tilde{\mathbf{u}}}^T}$ and p${\displaystyle \tilde{\mathbf{p}}}$ need to be learned.• Also, note that we have two bias terms, one for the users, bp${\displaystyle b_p}$, and one for the items, bu${\displaystyle b_u}$.• The loss function for matrix factorization is,L = 1

N ∑N(U.P - uTp - bp-bu)2 + 𝜆( ∑u||ui||2+ ∑p||pi||2+ ∑u||bu,i||2+ ∑p||bp,i||2)${\displaystyle L=\frac{1}{N}\sum _N^{}(\mathit{U}\mathit{.}\mathit{P}-{\tilde{\mathbf{u}}}^T\tilde{\mathbf{p}}-b_p-b_u{)}^2+𝜆(\sum _u^{}||u_i|{|}^2+\sum _p^{}||p_i|{|}^2+\sum _u^{}||b_{u,i}|{|}^2+\sum _p^{}||b_{p,i}|{|}^2)}$• The second term is the regularization term. 1.2.1. Implicit Ratings• If we have some binary user item matrix, we can transform that into a non-binary matrix of implicit ratings. – Example: Let's say the implicit rating (rimp${\displaystyle r_{imp}}$) of an item is like this,* 1 → view${\displaystyle 1\to view}$* 2 → like${\displaystyle 2\to like}$* 3 → comment${\displaystyle 3\to comment}$– We can multiply (1+𝛼rimp)${\displaystyle (1+𝛼r_{imp})}$ to all the binary values where 𝛼${\displaystyle 𝛼}$ is an adjusting parameter which can be tuned through cross validation.– With the implicit ratings, the loss function looks like this, L = 1

N ∑N(U.P.Cpu - uTp - bp-bu)2 + regularization${\displaystyle L=\frac{1}{N}\sum _N^{}(\mathit{U}\mathit{.}\mathit{P}.C_{pu}-{\tilde{\mathbf{u}}}^T\tilde{\mathbf{p}}-b_p-b_u{)}^2+regularization}$1.2.2. Alternating Least Squares (ALS)• Since we need to optimize with respect to both uT${\displaystyle {\tilde{\mathbf{u}}}^T}$ and p${\displaystyle \tilde{\mathbf{p}}}$ , we can't use ordinary least squares (like in linear regression).• We have to use something called Alternating Least Squares (found in libraries such as Spark ML).• ALS keeps constant one of uT${\displaystyle {\tilde{\mathbf{u}}}^T}$ or p${\displaystyle \tilde{\mathbf{p}}}$ and performs OLS on the other one. Then, it would fix the other one, and runs an OLS on the one that kept fixed in the previous round.• ALS performs well in practice and we can also tune the dimensions of U${\displaystyle U}$ and P${\displaystyle P}$. 1.2.3. Predicting with ALS• Here's the initial equation → U.P = uTp + bp+bu${\displaystyle \mathit{U}\mathit{.}\mathit{P}={\tilde{\mathbf{u}}}^T\tilde{\mathbf{p}}+b_p+b_u}$• By estimating this equation with ALS, we can get prediction for a particular user and an item as follows → pred(ui,pj) = ${\displaystyle pred(u_i,p_j)=}$uTrowipcolumnj + bpj+bui${\displaystyle {\tilde{\mathbf{u}}}_{ro{w}_i}^T{\tilde{\mathbf{p}}}_{colum{n}_j}+b_{p_j}+b_{u_i}}$ • The problem with the above approach is that, we'd have to retrain for every new customer that came in.• Note: To evaluate the performance of the predictions, we can use MSE on the validation set.• How can we avoid having to retrain these models for every new customer? 1.3. Deep Learning Extension• To avoid the prediction limitation of ALS, we can use the deep learning extension of matrix factorization.– In this case, the row and column of the user-item matrix are the inputs to the NN.– These inputs would have their own separate fully connected layers which would act as an embedding layer.– Then, the results of these embedding layers are combined into a single fully connected layer to finally be sent through a linear activation function.– The NN output would be the prediction for a particular user and item.• This typically requires less retraining. 1.4. Challenges of Collaborative Filtering• Cold-start Problem – We can't generate predictions for brand new users with no information (or items with no purchase history).– There are some ways to mitigate this such as:* Recommending new users popular items* Presenting new items to random subgroups• Echo Chamber– Let's say we recommend an item to a user so that increments some of their values in the user-item matrix.– Now that value has been incremented, it has more weights for other users and it just spins into this positive feedback loop of recommending potentially the same or very similar items over and over.– This doesn't make for a very good customer experience because these users won't see the variety that they need to see (they just see the same thing).– One way to avoid that is to recommend some random new items into the mix. • Shilling Attacks– This happens in systems where everyone can provide a rating.– For example, someone can provide a bunch of fake accounts to promote its own products in a platform (similarly when disliking a product).– We can limit that by allowing one user per phone number for example. 1.5. Content-based Filtering• Content-based filtering represents users with respect to items that they've interacted with.• Now, if we get the dot product of user vector with respect to every other items, and the item with the highest dot product will be recommended.• Content-based filtering doesn't require any user data to make a prediction about a particular user.– So, if you have tons of users, you can use content-based filtering to avoid running KNN.• The downside of content-based filtering is that it requires context about the items, i.e. products are need to evaluated in terms of some of their characteristics. 1.6. Deep Learning Recommender Systems• We can use deep learning to combine collaborative and content-based filtering.• It's going to be a similar NN as described in section ?, but with addition of input (and embedding layers) of user and item features. Back to Top