3 ms·

imo the best argument for randomized algorithms is that you may want to show more "underexposed" articles without seeing all of them. The issue with determinis

imo the best argument for randomized algorithms is that you may want to show more "underexposed" articles without seeing all of them. The issue with deterministic algos is that you basically have two options: - Treat new things as guilty until proven innocent and don't push them to the front until they get votes. This is the current approach here. - Push new things without "enough" votes to the front. This makes the front page almost all new items, invites spam, and generally defeats the purpose of a sorting algorithm. The problem here is that you're necessarily combining both the act of "learning" article quality and the act of exploiting it, which necessarily makes at least one of those tasks suboptimal. One advantage of randomized algorithms is that you can add a third option: - Show just enough underexposed articles to gather evidence (votes) without polluting the front page too much.

yummyfajitas 13y ago
The flaw in your post is that deterministic does not mean showing everyone the same thing. You can deterministically decide how much evidence to gather about underexposed articles as well, which is what I advocated Though to be fair, a random number generator would be used to determine which users to expose the article too (just not how many of them). Even if you fail to come up with a deterministic algorithm, you'll probably come up with a better random one simply by coming up with better probability distribution to draw from.
- pyduan 13y ago
  > The flaw in your post is that deterministic does not mean showing everyone the same thing. Though to be fair, a random number generator would be used to determine which users to expose the article too (just not how many of them). Well to be fair, what you are describing is a random experiment in the statistical sense, ie. something modeled by a probability space. I see what you're saying, but I would say your usage of the word is the nonstandard one, not chilldream's.
Houshalter 13y ago
>Show just enough underexposed articles to gather evidence (votes) without polluting the front page too much. That seems pretty much exactly what he is proposing. It doesn't require a randomized sorting though. For example, you pick some item from the new feed that isn't getting a lot of views and shove it on the front page for a small percent of users to get it more views, and therefore more votes to see how good the article actually is. The trick is to trade-off between discovering new good content, and just promoting what has already proven itself. There is an optimal tradeoff somehow.
- feral 13y ago
  >There is an optimal tradeoff somehow. You are basically talking about Bandit Algorithms, which are a family of techniques to solve the problem of trading of exploration ('discovering new good content') and exploitation ('just promoting what has already proven itself'). http://en.wikipedia.org/wiki/Multi-armed_bandit http://en.wikipedia.org/wiki/Multi-armed_bandit There are several bayesian approaches to bandit problems, which calculate the the uncertainty in a bayesian way, and then use this uncertainty to make the tradeoff between explore and exploit (e.g. http://en.wikipedia.org/wiki/Thompson_sampling http://en.wikipedia.org/wiki/Thompson_sampling). So that's a well understood problem. For my money, the 'correct' way to solve the HN problem is as a bandit arm for each article, which you use to decide how much to display low vote articles. I think this bandit process should be run on top of a bayesian model that features not just the estimated quality of the article from its votes, but also a prior which it gets from the submitter's 'quality' (which is updated depending on how their articles do - this would also serve as a brake on spammers). Then you just need a heuristic to age out articles over time. I'm sure PG knows enough ML/stats people to do this sort of thing properly; the fact that its not done means admins are probably happy enough with the status quo. It's also worth looking at this article by the author of XKCD on voting on reddit, for an easy discussion of simple bayesian voting: http://blog.reddit.com/2009/10/reddits-new-comment-sorting-system.html http://blog.reddit.com/2009/10/reddits-new-comment-sorting-s...
  - yummyfajitas 13y ago
    Don't use heuristics. Age out articles by penalizing them in your objective function. It's far cleaner.
chongli 13y ago
Show just enough underexposed articles to gather evidence (votes) without polluting the front page too much The problem with this is that people are biased. Their negative reaction to spam is far greater than their positive reaction to a hidden gem.

yummyfajitas 13y ago

The flaw in your post is that deterministic does not mean showing everyone the same thing. You can deterministically decide how much evidence to gather about underexposed articles as well, which is what I advocated Though to be fair, a random number generator would be used to determine which users to expose the article too (just not how many of them). Even if you fail to come up with a deterministic algorithm, you'll probably come up with a better random one simply by coming up with better probability distribution to draw from.

pyduan 13y ago
> The flaw in your post is that deterministic does not mean showing everyone the same thing. Though to be fair, a random number generator would be used to determine which users to expose the article too (just not how many of them). Well to be fair, what you are describing is a random experiment in the statistical sense, ie. something modeled by a probability space. I see what you're saying, but I would say your usage of the word is the nonstandard one, not chilldream's.

Houshalter 13y ago

>Show just enough underexposed articles to gather evidence (votes) without polluting the front page too much. That seems pretty much exactly what he is proposing. It doesn't require a randomized sorting though. For example, you pick some item from the new feed that isn't getting a lot of views and shove it on the front page for a small percent of users to get it more views, and therefore more votes to see how good the article actually is. The trick is to trade-off between discovering new good content, and just promoting what has already proven itself. There is an optimal tradeoff somehow.

feral 13y ago
>There is an optimal tradeoff somehow. You are basically talking about Bandit Algorithms, which are a family of techniques to solve the problem of trading of exploration ('discovering new good content') and exploitation ('just promoting what has already proven itself'). http://en.wikipedia.org/wiki/Multi-armed_bandit http://en.wikipedia.org/wiki/Multi-armed_bandit There are several bayesian approaches to bandit problems, which calculate the the uncertainty in a bayesian way, and then use this uncertainty to make the tradeoff between explore and exploit (e.g. http://en.wikipedia.org/wiki/Thompson_sampling http://en.wikipedia.org/wiki/Thompson_sampling). So that's a well understood problem. For my money, the 'correct' way to solve the HN problem is as a bandit arm for each article, which you use to decide how much to display low vote articles. I think this bandit process should be run on top of a bayesian model that features not just the estimated quality of the article from its votes, but also a prior which it gets from the submitter's 'quality' (which is updated depending on how their articles do - this would also serve as a brake on spammers). Then you just need a heuristic to age out articles over time. I'm sure PG knows enough ML/stats people to do this sort of thing properly; the fact that its not done means admins are probably happy enough with the status quo. It's also worth looking at this article by the author of XKCD on voting on reddit, for an easy discussion of simple bayesian voting: http://blog.reddit.com/2009/10/reddits-new-comment-sorting-system.html http://blog.reddit.com/2009/10/reddits-new-comment-sorting-s...
- yummyfajitas 13y ago
  Don't use heuristics. Age out articles by penalizing them in your objective function. It's far cleaner.

chongli 13y ago

Show just enough underexposed articles to gather evidence (votes) without polluting the front page too much The problem with this is that people are biased. Their negative reaction to spam is far greater than their positive reaction to a hidden gem.