Why Hacker News should use a different Deterministic Algorithm, Not a Random One
bayesianwitch.com
bayesianwitch.com
We assert that a randomized algorithm is unnecessary, and the
problem can be solved deterministically (though of course random
numbers will be used for sampling).
Random vs deterministic is a spectrum, anyway. Given enough information about the state of the machine doing the random picking/number generation all computer algorithms are deterministic anyway.
Heck, given enough information about the state of the universe everything is theoretically predictable, some predictions are just really hard.
Hopefully this achieves the needed philosophical wankery quota.
I suppose any algorithm involving sampling will be random in this manner, but the point is that randomness is not being introduced to work around flaws in the decision procedure.
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.
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.
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.
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.
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...
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.
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.
Yes, echo chamber, but also people talking about topics they know or want to know about with other people who do. Having an arbitrary and often rather short window of opportunity to discuss something sometimes really sucks.
Reddit doesn't allow one to fold away particular threads, or favourite others - for me there is a difference between upvoting something and filing it away for later reference/response... oh, and maybe also a link showing just the new comments of all the discussions you favourited. While I'm dreaming, even let us give our own tags to discussion threads.
Next section is coming very soon. Just gotta finish the last visualisation. (Interesting that both bandit algorithms and Angular + d3 feature on HN today.)
I haven't had the time to read either article closely (at a conference) but the main issue I'd be concerned with is non-stationary rewards. What is interesting today is not interesting tomorrow. A simple hack to get around this is to decay the prior over time. Other issues to consider include:
- the amount of data available. Even HN might not have enough readers to get sufficient data on each arm. Here you might use a similarity measure between arms (articles), such as tf-idf so votes for one article can inform the ranking of other articles.
- the effect of ranking on votes. The highest ranked articles probably gets more votes just by virtue of being at the top. There is some work on submodular bandits that might be relevant here, but this research is very new.
I've cooked up a method of my own which I believe is theoretically sound, but I imagine there must be methods out there that don't involve solving PDEs. (Or at least simpler closed form approximations to the PDEs.)
http://www.chrisstucchio.com/blog/2013/time_varying_conversi...
And I believe, that comments would also count a fair amount. An up-vote is a strong signal, but a comment is an even stronger signal.
I would (without telling anybody) even take the length of comments into account when weighting. I would at least try this and do an A/B-test, to see if this heightens the quality of articles on the front-page.
I would also use clicks on the link as an indicator, but one would have to be careful, as this would push link-bait articles to the top. So here one should not put too much weight into clicks.
I think a better way of doing it would be to get a large number of articles which are known to be controversial or uncontroversial and then use features from them (not just the number of comments) and try to develop a good predictor of how controversial something is. It would probably be a lot more effective than just arbitrary penalties for articles with 40 comments.
Though I kind of object to this stuff being done automatically at all. There aren't that many articles on HN that human moderation is impossible. As cool as automation is.
A better indicator of how trollish a thread is and how much that's getting in the way of the conversation (because those are two different things - users may be willing to put up with vehement discussion in one instance but not another) would be the ratio of downvoted comments to comments. I can even see measuring the length of comments and the depth of a thread, as a deep thread with lots of tiny comments might be an indication of sniping.
I realize i'm probably being incredibly naive and that the whole thing is complex with multiple factors interrelating but I don't see how the ratio of upvotes to comments tells you anything useful, if it doesn't take into account that people may comment without upvoting, and people might upvote bad comments. I make certain to upvote the article now with every comment because i'm aware that not doing so, regardless of the content of my comment, is an implicit downvote.
I think it's also a mistake to correlate "controversial" with "unwanted" but that might just be a matter of semantics.
Read pg's comments in this thread. https://news.ycombinator.com/item?id=6596038
That's not quite right. Anything with >= 40 comments AND more comments than upvotes gets the controversy penalty. Both conditions need to be true. An article with tons of comments will have NO controversy penalty as long as there are more votes than comments.
For most articles, there are more votes than comments, so commenting will not harm the article's rank. (I wrote the recent article analyzing HN ranking.)
I would believe, that PG had analyzed a lot of articles, to find a good ratio, that does penalize these kind of controversial topics, that he does not want to gain too much traction.
What I do not understand though is the fact, that controversial topics are penalized in the first place. But that is just me, one who loves to argue, to find optimal solutions (or to see, that there are really only two believe-systems at work).
The flamewar detector does its intended job with things like the gender discrimination stories but it looks like it throws out the baby with the bathwater and contributes to the echo chamber effect.
Here's a couple of Samsung stories that met the same fate. http://hnweird.tumblr.com/
It's really hard to tell(except if you're pg or HN staff) whether a story disappeared because of the flamewar detector, or flagging or the domain greylist or something else. I guess this is intentionally so.
Some do and some don't. Certainly, many interesting articles never make it to the front page. Due to lack of exposure rather than some failing intrinsic failing of the article.
It raises an interesting question of priorities; Is it more important that every interesting article spends some time on the front page, or that no non-interesting article spends some time on the front page?
In other words, given that there are lots of interesting things in the world, does it matter if a particular interesting thing never makes it to the front page, so long as the front page is full of interesting things?
The filter would give a range of possible scores for the post -- ones with few votes would have a very broad range, ones with lots of votes would have a tight range. Then you order based on a random number in that range (discounted based on its age).
I too believe random numbers are usually the wrong choice.
[1] http://www.mathworks.co.uk/help/stats/generating-quasi-rando...
Nitpicking aside, I disagree with the usage of the original quote:
> “It appears to be a quite general principle that, whenever there is a randomized way of doing something, then there is a nonrandomized way that delivers better performance but requires more thought.” E.T. Jaynes
What randomized methods are good at is reducing bias. In our case, there are several sources of bias: - The population that upvotes links on the 'new' page is different than the one that upvotes links on the frontpage - The probability of upvotes (which I assume are either ratios of upvotes to impressions or the ratio of upvotes to clicks) itself is determined by several factors other than article quality: article type and headline quality (and there is another interesting debate about quality vs. popularity, since sensationalized headlines are likely to get more clicks) to cite the main culprits, but there are many others.
I have three problems with this article:
1. The proposed strategy answers the question of variance but not bias, which is where the problem differs from a simple multi-armed bandit problem. Now we could build sophisticated models that try to take all these into account and get an unbiased estimator of quality, but it's likely be a pursuit that's not worth the payoff.
2. Adding random noise to the rankings is likely to be much more efficient. The author here suggests computing the posterior probability of an article being better than another for each pair of articles, which seems rather impractical.
3. Most importantly: is overall quality of the frontpage really the ultimate optimization objective? This solution doesn't solve the problem of the N+1th article receiving much fewer votes than the Nth, where N is the number of articles shown on the frontpage, while being arguably equally deserving. I would argue that the problem of minimizing the probability of a good article getting few pageviews is actually the more important one, because we have more good articles than slots on the frontpage. A randomized algorithm would be much better equipped for this purpose.
Of course, the other thing is that for bragging purposes "We made the frontpage of HN" sounds much better than "We made the frontpage of HN for 60% of the users". But that's a different problem altogether...
Edit: writing this comment made me think of alternative solutions. An easy-to-implement one would be to add 5 or so slots at the bottom of the frontpage that would contain random picks from the 2nd or 3rd page in a rotating manner. That would give good articles which weren't fortunate enough to get good visibility a chance at floating up to the top, without all the implications of changing the ranking algorithm itself. In other words, add fuzziness to the threshold instead of the ranking.
However, one place I'd argue with you strongly is that handling beliefs about the world should be part of your model. For example, you mention different upvote probabilities on the new and front page - I'd simply model that with a new parameter beta (possibly related to alpha in some way).
It's far from clear to me how randomization such as what Dan Luu proposed actually addresses this at all.
I'll also discuss one other point: The author here suggests computing the posterior probability of an article being better than another for each pair of articles, which seems rather impractical.
It probably is. However, suppose we went through the effort of computing posteriors, only to discover that we get stuck at the stage of computing pairwise probabilities. There is still a very good chance we can draw samples from the posteriors.
Even though our deterministic algorithm has failed, we still get a much better random algorithm out of the exercise. Given the posteriors on P(good article), we can draw samples from them and employ Thompson Sampling to sort the articles. (I.e., draw a sample from each posterior and then order the articles by increasing sampled posterior.)