Hacker News Reader

Comment by chilldream | Hacker News Reader

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.

View on HN

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.

> 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.

>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.

>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

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).

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-s...

Don't use heuristics. Age out articles by penalizing them in your objective function. It's far cleaner.

Well, it depends.

If you already know exactly the 'age-out' behaviour that you want to capture, then maybe the best thing to do is bolt that on after doing your statistical inference.

This keeps the 'complicated' bit of your system that uses the statistical models simpler.

Also, you'll know exactly what the heuristic does, and be able to predictably hack changes into it in a single place, without affecting your inference code.

If you instead put the aging-out into your objective function, you'll have a more elegant implementation, but the 'age-out' behaviour might surprise you.

Well-specified models are great, but heuristic hacks that force the system to behave how you want also have a place. In general, I would start out by only using the statistical modelling in places where you can't describe exactly what you want with a heuristic.

What the best approach actually is depends, and I'd need to be implementing the system to say more.

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.

Reply on news.ycombinator.com