Tag based recommenders

One special case of the segmentation model for item-based recommenders is a tag-based recommender. This is a quite common first recommender to try, when you have some human labels and need to quickly turn this into a working recommender. Let’s talk through a toy example: you have a personal digital wardrobe, where you’ve logged many features about each article of clothing in your personal closet. You want your fashion recommender to give you suggestions for what else to wear, given that you’ve selected one piece for the day. You wake up, and see that it’s rainy outside so you start by choosing a cozy cardigan. The model you’ve trained has found that cardigan has tags outerwear and cozy, which it knows correlate well with bottoms and warm–so it’s likely to recommend you some heavier jeans today.

The upside of a tag recommender, is how explainable and understandable the recommendations are. The downside, is that performance is directly tied to how much effort is put into tagging items.

Let’s discuss a slightly more involved example of a tag-based recommender that one of the Authors built – in collaboration with Ashraf Shaik and Eric Bunch – for recommending blog posts.

The goal was to warm-start the blog post recommender utilizing high-quality tags that classified the blogs into themes. One thing that was special about this tagging system, is that it was a very rich hierarchical tagging system maintained by the marketing team. In particular, each tag type had several different values, and there were 11 tag types with up to 10 values each. Blogs had values for each tag type, and sometimes had multiple tags in a single tag type for the blog. This may sound a bit complicated, but suffice to say each blog post could have some of the 47 tags, and the tags were further grouped into types.

One first thing that could be done, is to simply use those tags to build a simple recommender, and we did, but that would be missing a very important additional opportunity when afforded such high quality tag data – evaluating our embeddings.

First, we needed to understand how we could build user embeddings – our plan was to average the blog-embeddings a user had seen, a very simple collaborative filtering approach when you have a clear item-embedding. Thus we wanted to train the best embedding model possible for these blogs. We started by considering models like BERT, but we were unsure if the highly technical content would be meaningfully captured by our embedding model. This led us to realize that we could use the tags as a classifier dataset for our embedding – if we could test several different embedding models by training a simple MLP to perform multi-label multi-classification for each of the tag types, where the input features were the embedding dimensions, then our embedding space captured well the content. Some of the embedding models were of varying dimensions, and some were quite large, so we also first used a dimension reduction (UMAP) to a standard size before we trained the MLP. We used [F1 scores](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.f1_score.html) to determine which of the embedding models led to the best classification model for tags, and did some visual inspection to ensure the groups were as we’d hoped. This worked quite well and showed that some embeddings were much better than others.

Hybridization

We saw in the previous section how we can blend our matrix factorization with simpler models via taking priors from the simpler models, and learning how to transition away. There are more coarse approaches to this process of hybridization.

• As mentioned before; weighted combinations of models is incredibly powerful, and the weights can be learned in a standard bayesian framework.

• multi-level modeling can include learning a model to select which recommendation model should be used, and then learning models in each regime–for example utilize a tree-based model on user features when the user has <10 historical ratings and then use MF after that. There are a variety of multi-level approaches including switching and cascading which correspond roughly to voting vs boosting.

• feature augmentation which allows multiple vectors of features to be concatenated and a larger model be learned. By definition, if we wish to combine feature vectors with factor vectors, like those coming from a collaborative filter, we will expect substantial nullity. Learning despite that nullity allows a somewhat naive combination of the different kinds of features to be fed into the model and operated on in all regimes of user activity.

There are a variety of useful ways to combine these models, however we take the position that instead of more complicated combinations of several models that work well in different paradigms, we will attempt to stick to a relatively straightforward model-service architecture:

• we will train the best model we can using matrix factorization based collaborative filtering

• we will utilize user and item feature-based models for cold start.

Let’s see why we might think feature-based modeling may not be the best strategy, even if we do it via Neural Networks and latent factor models.

Return to the most-popular-item-recommender

Our super simple scheme from before, to implement the MPIM, provided us with a convenient toy model, but what are the practical considerations of deploying an MPIM? It turns out, that the MPIM provides an excellent framework for getting started on a Bayesian approximation approach to recommendations. Note that in this section, we’re not even considering a personalized recommender–everything here is reward maximization across the entire user population. We follow the treatment in Agarwal and Chen.

For the sake of simplicity, let’s consider Click Through Rate (CTR) as our simple metric to optimize with respect to. Our formulation is as follows: we have $ℐ=\left.i\right\}$ items available to recommend, and initially only one time period in which to do it, we’re interested in an allocation plan or a set of proportions $x_i,{\sum }_{i\in ℐ}{x}_i=1,$ of how to recommend items. This can be seen as a very simple Multi-armed bandit problem with the reward given by

where $c_i$ are prior distributions of CTR for each item. It’s plain to see that maximizing this reward is achieved by allocating all recommendations to the item with greatest $p_i$, i.e. picking the most popular item in terms of CTR.

This setup makes obvious that if we have strong confidence in our priors, this problem seems trivial. So let’s move to a case where we have a mismatch in confidence.

Let’s consider two time periods, $N_0$ and $N_1$ their number of user visits–note that we think of 0 as the past, and 1 as the future in this model. Let’s assume we offer only two items and, somewhat mysteriously, that for one item we have 100 percent confidence in it’s CTR in each time period: $q_0$ and $q_1$ will denote these rates respectively. In contrast, we have only priors for our second item: $p_0\sim ?\left({\theta }_0\right)$ and $p_1\sim ?\left({\theta }_1\right)$ will denote these rates respectively, and we regard ${\theta }_i$ as a state vector. We again notate the allocations with $x_{i,t}$ where now the second index refers to time period. Then we can simply compute the expected number of clicks as

which is maximized by assuming a distribution for $p_1$ as a function of $x_0$ and $p_0$. With distributional assumptions that $p_0$ is Gamma distributed and $p_1$ is Normally distributed, we can treat this as a convex optimization problem to maximize the clicks. See Agarwal and Chen for a full treatment of the statistics.

This toy example extends in both dimensions to model larger item sets and more time windows, and provides us with relatively straightforward intuition about the relationship between our priors for each item and time step, and the opportunity during this step-forward optimization.

Let’s put this recommender in context: we’ve started with item popularity and generalized to a Bayesian recommender that learns with respect to user feedback. You might consider a recommender like this for a very trend-based recommendations context like news–popular stories are often important, but that can change rapidly and we want to be learning from user behavior.

Correlation mining

We’ve seen ways to utilize correlations between features of items, and recommendations, but we should not forget to utilize correlations between items themselves. Think back to our early discussions of Cheese in Chapter 2, Figure 2-1, we said that our collaborative filtering gave us a way to find mutual cheese taste to recommend new cheeses. This was built on the notion of ratings, but we can abstract away from the ratings and simply look at the correlations in which items a user chooses. You can imagine for an e-commerce bookseller, that users’ choice of one book to read may be useful in recommending others – even if that user chooses not to rate the first book. We also saw this phenomena in our chapter on Wikipedia (Chapter 8), we used the co-occurrence of tokens in Wikipedia entries.

We introduced the co-occurrence matrix as the multi-dimensional array of counts where two items, $i$ and $j$, co-occur. Let’s take a moment and discuss co-occurrence a bit more deeply.

Co-occurrence is context-dependent, in our case of Wikipedia articles, we considered co-occurrence of tokens in an article. In the case of e-commerce, co-occurrence can be two items purchased by the same user. For ads, two things that the user clicked on, and so on. Mathematically, given users and items we construct what is called an incidence vector for each user, the binary vector of 1-hot encoded features for each item of did they interact with it. Those vectors are stacked into a vector to yield a $\#\left(users\right)\times \#\left(items\right)$ matrix where each row is a user, each column is an item, and the elements equal to 1 are when a user-item pair has interacted.

To be mathematically precise, an user-item incidence structure is a collection of sets of user iteractions, ${\left.y_u\right\}}_{u\in U}$, with items, ${\left.x_i\right\}}_{i\in I}$, where $U$ indexes user and $I$ indexes items.

The associated user-item incidence matrix, $?$, is the binary matrix with rows indexed by sets, and columns indexed by nodes, such that elements:

The co-occurrences of $x_a$ and $x_b$ is the order of the set $\left.y_u\mid x_a\in y_u\text{and}{x}_b\in y_u\right\}$. We can also write that as a matrix and it has a simple formula for computing it; let $C_{ℐ}$ be the co-occurrences matrix, i.e. the matrix with rows and columns indexed by ${\left.x_i\right\}}_{i\in I}$ and elements the co-occurrences of the indices. Then:

As mentioned in “Customers also Bought”, we can build a new variant of our MPIM by considering the rows or columns of the co-occurence matrix. The conditional MPIM is the recommender which returns the max of the elements in row corresponding $x_i$ given the user’s last iteraction was the item $x_i$.

In practice, we often think of the row corresponding to $x_i$ as a basis-vector, i.e. a vector $q_{x_i}$ with one non-zero element in the $x_i$‘th position:

Then we can consider max – or even softmax – of the dot products above:

Which yields the vector of co-occurrence counts between $x_i$ and each other item. Here we frequently will call $q_{x_i}$ a query to indicate that it’s the input to our co-occurrence recommendation model.

{
  'indices': indices,
  'values': values,
  'shape': [user_dim, items_dim]
}

Pointwise mutual information via co-occurrences

An early recommendation system for articles utilized the concept of pointwise mutual information, or PMI, which is closely related to co-occurrences. In the context of NLP, PMI attempts to express how much more frequent co-occurrence is that random chance. Given what we’ve seen before, you can think of this as a normalized co-occurrences model. Computational linguists frequently use PMI as an estimator for word similarity or word meaning following from the Distributional Hypothesis:

You shall know a word by the company it keeps.

John R. Firth 1957

In the context of recommendation ranking, items with very high PMI are said to have a highly meaningful co-occurrence. This can thus be used as an estimator for complementary items: given you’ve iteracted with one of them you should interact with the other.

PMI is computed for two items, $x_i,x_j$ via:

The PMI calculation allows us to modify all of our work on co-occurrence to a more normalized computation, and thus a bit more meaningful. This is actually very related to the “Glove model definition” model we learned before. The negative PMI values allow us to understand when two things are not witnessed together often.

These PMI calculations can be used to recommend another item in a cart when an item has been added and you find those with very high PMI. It can be used as a retrieval method by looking at the set of items a user has already interacted with and finding items that have high PMI with several of them.

Let’s look at how we turn co-occurrences into other similarity measures.

Similarity from co-occurrence

Earlier, we discussed similarity measures and how they come from Pearson correlation. The Pearson correlation is a special case of similarity when we have explicit ratings, so let’s instead look at when we don’t.

Consider incidence sets associated to users, ${\left.y_u\right\}}_{u\in U}$, we define three distance metrics:

1. Jaccard Similarity, $Jac(-)$, the ratio of shared items by two users to the total items those users have interacted with.

2. Sørensen-Dice Similarity, $DSC(-)$, twice the ratio of shared items by two users to the sum of total items each user has interacted with.

3. Cosine Similarity, $Cosim(-)$, the ratio of shared items by two users to the product of total items each user has interacted with.

These are all very related metrics with slightly different strengths. Some things to consider:

• Jaccard similarity is a real distance metric which has some nice properties for geometry, neither of the other two are

• All three are on the interval $\left.0,1\right)$, but you’ll often see Cosine extended to $\left.-1,1\right)$, by including negative ratings.

• Cosine can accommodate “thumbs up/thumbs down” by merely extending all interactions to have a polarity $\pm 1$

• Cosine can accommodate “multiple interactions” if you allow the vectors to be non-binary and count the number of times a user iteracts with an item

• Jaccard and Dice are related by a simple equation: $S=2J/(1+J)$ and you can easily compute one from the other.

Notice in the above, that we’ve defined all of these similarity measures between users. We’ll see in the next section how to extend these definitions to items, and how to turn these into recommendations.

Similarity based recommendations

In each of the above, we’ve defined a similarity measure, but we’ve not yet discussed how similarity measures turn into recommendations in the above. As we discussed in “Nearest Neighbors”, we utilize similarity measures in our retrieval step; we wish to find a space in which items which are close to one another are good recommendations. In the context of ranking, our similarity measure can be used directly to order the recommendations in terms of how likely the recommendation is relevant. In the next chapter, we’ll talk more about metrics of relevance.

In the above, we looked at three similarity scores, but we need to expand our notion of the relevant sets are for these measures. Let’s consider Jaccard Similarity as a prototype.

Given a user, $y_u$ and an unseen item $x_i$, let’s we could ask: What is the Jaccard similarity between this user and item? Let’s remember that Jaccard similarity is the similarity between two sets, and in the definition those sets were both incidence sets of users’ interactions. Here are three ways to use this for recommendations:

1. User-user, using the above definition, find the $k$ users with maximum Jaccard similarity. Compute the percentage of these users who have interacted with $x_i$. You may also wish to normalize this by popularity of the item $x_i$.

2. Item-item, Compute the set of users that each item has interacted with, compute the $k$ items most similar to $x_i$ with respect to Jaccard similarity of these item-user incidence sets. Compute the percentage of these items that are in $y_u$’s set of interactions. You may also wish to normalize this by total interactions of $y_u$ or the popularity of the similar items.

3. User-item, Compute the user $y_u$s set of items they’ve interacted with, and the set of items co-occurrening with $x_i$ in any users incidence set of interaction. Compute the Jaccard similarity between these two sets.

Frequently in designing ranking systems, we specify what the query is, which refers to what you’re whose nearest-neighbors you’re looking for. We then specify how you use those neighbors to yield a recommendation. The items that may become the recommendation are the candidates, but as you see above, the neighbors may not be the candidates themselves. An additional complication is that you need to usually compute many candidate scores simultaneously, which requires optimized computations which we’ll see in a later chapter.