6 ms·

I've experienced issues like those mentioned. Imagine a recommendation service for online shopping, using a simple co-occurrence model, aka "People who viewed t

by bcbrown 11y ago

I've experienced issues like those mentioned. Imagine a recommendation service for online shopping, using a simple co-occurrence model, aka "People who viewed this also viewed". Hopefully, your model will eventually hit a steady state, with generally helpful recommendations. Now, imagine someone comes up with an almost-perfect replacement algorithm, that provides a high lift in clickthrough rate, that's being tested against the original system. The original co-occurrence system has access to all the data, including that from sessions exposed to the new algorithm. If the A/B test runs for long enough, the original system will learn the new system's behaviour and emulate it, because for a given seed item, a lot of the co-occurring clicks will be on items recommended by the new system. Although initially the new system will show a lift, eventually the two systems will tend towards showing the improved recommendations, and the lift will tend towards zero.

shoo 11y ago
Interesting! Is this an example of where the old algorithm is capable of exploiting the information in its training database, but is not capable / not configured to ever explore? So by feeding it additional (context, recommendation, result) samples from the new algorithm, it is rapidly able to exploit the information to offer improved recommendations, even though it would never have proposed those recommendations? More generally, it sounds like the old algorithm (and perhaps the new one too) are rigged to myopically try to make the best decision right now - to conservatively maximise the value of this recommendation - without considering that there will be value in future of carrying out some ongoing experimental work to try new things and grow a diverse training dataset, which could pay off in subsequent rounds of recommendation. A simple to describe but sub-optimal strategy to improve this would be to use an epsilon-greedy recommendation system: e.g. set epsilon=1%, so 99% of the time it makes a recommendation using the original algorithm, and 1% of the time makes a recommendation at random (to gain novel information). I read a little about this kind of thing a few years ago: explore/exploit tradeoffs, online learning, regret minimisation, bandit algorithms, contextual bandits, upper confidence bounds, ...
- ves 11y ago
  It sounds like you're talking about the idea of introducing noise in order to prevent stagnation and make sure learning continues. One of the trivial ways to do this with a recommender system is to change the priority of some search results so that, say, a page 5 result shows up on page 1. You also do something similar with introducing noise in nns for image processing.
- keyboardwarrior 11y ago
  It sounds like biologic growth, processes bootstrapped to other processes.
- bcbrown 11y ago
  A co-occurrence model isn't really meant to be used for exploration. I'm eliding a bunch of details, as it's just one of many different recommendation algorithms, and there's an exploration layer on top of the whole ensemble, which includes an epsilon-greedy component.
  - shoo 11y ago
    I may have missed the subtext/point of your earlier comment: that the additional samples generated using the new candidate algorithm were visible to the existing algorithm, making comparison of the two algorithms difficult, and that this visibility (or its consequences) was not initially anticipated.
mistercow 11y ago
> The original co-occurrence system has access to all the data, including that from sessions exposed to the new algorithm Wouldn't the solution be to exclude that data from the original system?
xamuel 11y ago
>eventually the two systems will tend towards showing the improved recommendations, and the lift will tend towards zero While this is probably true in many realistic cases, I'm skeptical on theoretical grounds. Suppose the replacement algorithm happens to be run on a quantum computer. When you search for a book such as "I wish I knew a prime factor of 132,200,813,987,918,309", it near-instantly recommends you might be interested in the book "Interesting facts about 373,587,911". If P!=NP and the original system is running on conventional hardware, there's no way it can match the replacement.
NumberCruncher 11y ago
>> The original co-occurrence system has access to all the data, including that from sessions exposed to the new algorithm. This is obviously a bad A/B Test design. The original algorithm shouldn´t have access to the data generated by the new algorithm. Designing an adequate test for ML systems is often as hard as designing the ML systems itself. And this is my main concern with machine learning.

by bcbrown 11y ago

shoo 11y ago

Interesting! Is this an example of where the old algorithm is capable of exploiting the information in its training database, but is not capable / not configured to ever explore? So by feeding it additional (context, recommendation, result) samples from the new algorithm, it is rapidly able to exploit the information to offer improved recommendations, even though it would never have proposed those recommendations? More generally, it sounds like the old algorithm (and perhaps the new one too) are rigged to myopically try to make the best decision right now - to conservatively maximise the value of this recommendation - without considering that there will be value in future of carrying out some ongoing experimental work to try new things and grow a diverse training dataset, which could pay off in subsequent rounds of recommendation. A simple to describe but sub-optimal strategy to improve this would be to use an epsilon-greedy recommendation system: e.g. set epsilon=1%, so 99% of the time it makes a recommendation using the original algorithm, and 1% of the time makes a recommendation at random (to gain novel information). I read a little about this kind of thing a few years ago: explore/exploit tradeoffs, online learning, regret minimisation, bandit algorithms, contextual bandits, upper confidence bounds, ...

ves 11y ago
It sounds like you're talking about the idea of introducing noise in order to prevent stagnation and make sure learning continues. One of the trivial ways to do this with a recommender system is to change the priority of some search results so that, say, a page 5 result shows up on page 1. You also do something similar with introducing noise in nns for image processing.
keyboardwarrior 11y ago
It sounds like biologic growth, processes bootstrapped to other processes.
bcbrown 11y ago
A co-occurrence model isn't really meant to be used for exploration. I'm eliding a bunch of details, as it's just one of many different recommendation algorithms, and there's an exploration layer on top of the whole ensemble, which includes an epsilon-greedy component.
- shoo 11y ago
  I may have missed the subtext/point of your earlier comment: that the additional samples generated using the new candidate algorithm were visible to the existing algorithm, making comparison of the two algorithms difficult, and that this visibility (or its consequences) was not initially anticipated.

mistercow 11y ago

> The original co-occurrence system has access to all the data, including that from sessions exposed to the new algorithm Wouldn't the solution be to exclude that data from the original system?

xamuel 11y ago

>eventually the two systems will tend towards showing the improved recommendations, and the lift will tend towards zero While this is probably true in many realistic cases, I'm skeptical on theoretical grounds. Suppose the replacement algorithm happens to be run on a quantum computer. When you search for a book such as "I wish I knew a prime factor of 132,200,813,987,918,309", it near-instantly recommends you might be interested in the book "Interesting facts about 373,587,911". If P!=NP and the original system is running on conventional hardware, there's no way it can match the replacement.

NumberCruncher 11y ago

>> The original co-occurrence system has access to all the data, including that from sessions exposed to the new algorithm. This is obviously a bad A/B Test design. The original algorithm shouldn´t have access to the data generated by the new algorithm. Designing an adequate test for ML systems is often as hard as designing the ML systems itself. And this is my main concern with machine learning.