Dealing with Suggestions Loops in Recommender Methods — Deep Bayesian Bandits | by Sachin Hosmani | Jul, 2024

Understanding fundamentals of exploration and Deep Bayesian Bandits to sort out suggestions loops in recommender methods

Picture from ChatGPT-4o

Recommender system fashions are sometimes educated to optimize for person engagement like clicks and purchases. The well-meaning intention behind that is to favor objects that the person has beforehand engaged with. Nevertheless, this creates a suggestions loop that over time can manifest because the “chilly begin drawback”. Merely put, the objects which have traditionally been fashionable for a person are likely to proceed to be favored by the mannequin. In distinction, new however extremely related objects don’t obtain a lot publicity. On this article, I introduce exploration methods from the fundamentals and finally clarify Deep Bayesian Bandits, a highly-effective algorithm described in a paper by Guo, Dalin, et al [1].

Allow us to use a easy advert recommender system for example all through this text.

A easy three-component advert recommender system. Picture by writer

It’s a three-component system

  • Retrieval: a part to effectively retrieve candidates for rating
  • Rating: a deep neural community that predicts the click-through price (CTR) because the rating for an advert given a person
    rating = predict_ctr(person options, advert options)
  • Public sale: a part that
    – retrieves candidate adverts for the person
    – scores them utilizing the rating mannequin
    – selects the highest-scored advert and returns it*

Our focus on this article will probably be solely on the rating mannequin.

*real-world public sale methods additionally take the advert’s bid quantity into consideration, however we ignore that for simplicity

Rating mannequin structure

The rating mannequin is a deep neural community that predicts the click-through price (CTR) of an advert, given the person and advert options. For simplicity, I suggest a easy absolutely linked DNN beneath, however one might very effectively enrich it with methods like wide-and-deep community, DCN, and DeepFM with none lack of applicability of the strategies I clarify on this article.

A binary classifier deep neural community that predicts pCTR. Picture by writer

Coaching knowledge

The rating mannequin is educated on knowledge that includes clicks as binary labels and, concatenation of person and advert options. The precise set of options used is unimportant to this text, however I’ve assumed that some advertiser brand-related options are current to assist the mannequin be taught the person’s affinity in direction of manufacturers.

Coaching knowledge with pattern options. Picture by writer

Think about we efficiently educated our rating mannequin on our adverts click on dataset, and the mannequin has realized that one in every of our customers Jane loves shopping for baggage from the bag firm “Vogue Voyage”. However there’s a new bag firm “Radiant Clutch” available in the market they usually promote nice baggage. Nevertheless, regardless of “Radiant Clutch” operating advert campaigns to achieve customers like Jane, Jane by no means sees their adverts. It is because our rating mannequin has so firmly realized that Jane likes baggage from “Vogue Voyage”, that solely their adverts are proven to her. She typically clicks on them and when the mannequin is additional educated on these new clicks, it solely strengthens the mannequin’s perception. This turns into a vicious cycle resulting in some objects remaining at the hours of darkness.

The suggestions loop in motion, inflicting the cold-start drawback: baggage from Radiant Clutch don’t stand an opportunity. Picture by writer, thumbnails generated with ChatGPT-4o

If we ponder about this, we’d notice that the mannequin didn’t do something flawed by studying that Jane likes baggage from “Vogue Voyage”. However the issue is just that the mannequin just isn’t being given an opportunity to study Jane’s pursuits in different corporations’ baggage.

Exploration vs exploitation

It is a nice time to introduce the trade-off between exploration vs exploitation.

Exploitation: Throughout advert public sale, as soon as we get our CTR predictions from our rating mannequin, we merely choose the advert with the very best rating. It is a 100% exploitation technique as a result of we’re utterly performing on our present greatest information to realize the best instant reward.

Exploration: What our method has been missing is the willingness to take some threat and present an advert even when it wasn’t assigned the very best rating. If we did that, the person would possibly click on on it and the rating mannequin when up to date on this knowledge would be taught one thing new about it. But when we by no means take the chance, the mannequin won’t ever be taught something new. That is the motivation behind exploration.

Exploration vs exploitation is a balancing act. Too little exploration would go away us with the cold-start drawback and an excessive amount of exploration would threat exhibiting extremely irrelevant adverts to customers, thus shedding person belief and cash.

Now that we’ve set the stage for exploration, allow us to delve into some concrete methods for managed exploration.

ε-greedy coverage

The thought right here is easy. In our public sale service, when we have now the scores for all of the candidate adverts, as a substitute of simply taking the top-scored advert, we do the next

  1. choose a random quantity r in [0, 1)
  2. if r < ε, select a random ad from our candidates (exploration)
  3. else, select the top-scored ad (exploitation)

where ε is a constant that we carefully select in [0, 1) knowing that the algorithm will explore with ε probability and exploit with 1 — ε probability.

Exploration with ε probability: pick any candidate ad at random. Image by author
Exploitation with 1 — ε probability: pick the highest CTR ad. Image by author

This is a very simple yet powerful technique. However, it can be too naive because when it explores, it completely randomly selects an ad. Even if an ad has an absurdly low pCTR prediction that the user has repeatedly disliked in the past, we might still show the ad. This can be a bit harsh and can lead to a serious loss in revenue and user trust. We can certainly do better.

Upper confidence bound (UCB)

Our motivation for exploration was to ensure that all ad candidates have an opportunity to be shown to the user. But as we give some exposure to an ad, if the user still doesn’t engage with it, it becomes prudent to cut future exposure to it. So, we need a mechanism by which we select the ad based on both its score estimate and also the amount of exposure it has already received.

Imagine our ranking model could produce not just the CTR score but also a confidence interval for it*.

*how this is achieved is explained later in the article

The model predicts a confidence interval along with the score. Image by author

Such a confidence interval is typically inversely proportional to the amount of exposure the ad has received because the more an ad is shown to the user, the more user feedback we have about it, which reduces the uncertainty interval.

Increased exposure to an ad leads to a decrease in the confidence interval in the model’s score prediction. Image by author

During auction, instead of selecting the ad with the greatest pCTR, we select the ad with the highest upper confidence bound. This approach is called UCB. The philosophy here is “Optimism in the face of uncertainty”. This approach effectively takes into account both the ad’s score estimate and also the uncertainty around it.

UCB in action: Ad-1 wins auction at first on account of its large confidence interval, but as the model learns about it, its UCB falls leading to Ad-2 winning auction. Image by author

Thompson sampling

The UCB approach went with the philosophy of “(complete) optimism in the face of uncertainty”. Thompson sampling softens this optimism a little. Instead of using the upper confidence bound as the score of an ad, why not sample a score in the posterior distribution?

For this to be possible, imagine our ranking model could produce not just the CTR and the confidence interval but an actual score distribution*.

*how this is achieved is explained later in the article

The model can predict a distribution of scores for one ad. Image by author

Then, we just sample a score from this distribution and use that as the score during auction.

Ad-1 wins auction due to a high sampled score from its wide distribution. Image by author
Ad-1 has received exposure and the model has lesser uncertainty about it. Ad-2 wins auction due to its higher score distribution mass. Image by author
Ad-2’s score distribution stdev further shrinks as it gets more exposure. Image by author

For the UCB and Thompson sampling techniques to work, we must update our models as often as possible. Only then will it be able to update its uncertainty estimates in response to user feedback. The ideal setup is a continuous learning setup where user feedback events are sent in near-real time to the model to update its weights. However, periodically statefully updating the weights of the model is also a viable option if continuous learning infrastructure is too expensive to set up.

A high-level continuous learning setup utilizing streaming infrastructure. Image by author, thumbnail generated by ChatGPT-4o

In the UCB and Thompson sampling approaches, I explained the idea of our model producing not just one score but an uncertainty measure as well (either as a confidence interval or a distribution of scores). How can this be possible? Our DNN can produce just one output after all! Here are the approaches discussed in the paper.

Bootstrapping

Bootstrapping in statistics simply means sampling with replacement. What this means for us is that we apply bootstrapping on our training dataset to create several closely related but slightly different datasets and train a separate model with each dataset. The models learned would thereby be slight variants of each other. If you have studied decision trees and bagging, you would already be familiar with the idea of training multiple related trees that are slight variants of each other.

Bootstrapped datasets are used to train separate models, resulting in a distribution of scores. Image by author

During auction, for each ad, we get one score from each bootstrapped model. This gives us a distribution of scores which is exactly what we wanted for Thompson sampling. We can also extract a confidence interval from the distribution if we choose to use UCB.

The biggest drawback with this approach is the sheer computational and maintenance overhead of training and serving several models.

Multi-head bootstrapping

To mitigate the costs of several bootstrapped models, this approach unifies the several models into one multi-head model with one head for each output.

Multi-head model. Image by author

The key cost reduction comes from the fact that all the layers except the last are shared.

Training is done as usual on bootstrapped subsets of data. While each bootstrapped subset of data should be used to update the weights of all the shared layers, care must be taken to update the weight of just one output head with a subset of data.

Constrained influence of each bootstrapped subset of data on one head during backprop. Image by author

Stochastic Gradient descent (SGD)

Instead of using separate bootstrapped datasets to train different models, we can just use one dataset, but train each model with SGD with random weight initialization thus utilizing the inherent stochasticity offered by SGD. Each model trained thus becomes a variant of the other.

Multi-head SGD

In the same way, using a multi-head architecture brought down the number of models trained with bootstrapping to one, we can use a multi-head architecture with SGD. We just have to randomly initialize the weights at each head so that upon training on the whole dataset, each head is learned to be a slight variant of the others.

Forward-propagation dropout

Dropout is a well-known regularization technique where during model training, some of the nodes of a layer are randomly dropped to prevent chances of overfitting. We borrow the same idea here except that we use it during forward propagation to create controlled randomness.

We modify our ranking model’s last layer to introduce dropout. Then, when we want to score an ad, we pass it through the model several times, each time getting a slightly different score on account of the randomness introduced by dropout. This gives us the distribution and confidence interval that we seek.

The same model produces a distribution of scores through random dropout. Image by author

One significant disadvantage of this approach is that it requires several full forward passes through the network which can be quite costly during inference time.

Hybrid

In the hybrid approach, we perform a key optimization to give us the advantages of dropout and bootstrapping while bringing down the serving and training costs:

  • With dropout applied to just the last-but-one layer, we don’t have to run a full forward pass several times to generate our score distribution. We can do one forward pass until the dropout layer and then do several invocations of just the dropout layer in parallel. This gives us the same effect as the multi-head model where each dropout output acts like a multi-head output.

Also, with dropout deactivating one or more nodes randomly, it serves as a Bernoulli mask on the higher-order features at its layer, thus producing an effect equivalent to bootstrapping with different subsets of the dataset.

Unfortunately, there is no easy answer. The best way is to experiment under the constraints of your problem and see what works best. But if the findings from the authors of the Deep Bayesian Bandits paper are anything to go by,

  1. ε-greedy unsurprisingly gives the lowest CTR improvement due to its unsophisticated exploration, however, the simplicity and low-cost nature of it make it very alluring.
  2. UCB generally outperformed Thompson sampling.
  3. Bootstrap UCB gave the highest CTR return but was also the most computationally expensive due to the need to work with multiple models.
  4. The hybrid model which relied on dropout at the penultimate layer needed more training epochs to perform well and was on par with SGD UCB’s performance but at lower computational cost.
  5. The model’s PrAuc measured offline was inversely related to the CTR gain: this is an important observation that shows that offline performance can be easily attained by giving the model easier training data (for example, data not containing significant exploration) but that will not always translate to online CTR uplifts. This underscores the significance of robust online tests.

That said, the findings can be quite different for a different dataset and problem. Hence, real-world experimentation remains vital.

In this article, I introduced the cold-start problem created by feedback loops in recommender systems. Following the Deep Bayesian Bandits paper, we framed our ad recommender system as a k-arm bandit and saw many practical applications of reinforcement learning techniques to mitigate the cold-start problem. We also scratched the surface of capturing uncertainty in our neural networks which is a good segue into Bayesian networks.

[1] Guo, Dalin, et al. “Deep bayesian bandits: Exploring in on-line personalised suggestions.” Proceedings of the 14th ACM Convention on Recommender Methods. 2020.

Leave a Reply