8 ms·

Probably because the mathematicians don't seem to have the ability to explain why it is not sound without devolving into obscure symbols and jargon.

by jev 12y ago

amathstudent 12y ago
I think that's a very important point. Indeed, when you try to explain something simply to people, they often won't believe that it's really that simple, since there's all those symbols!
dxbydt 12y ago
If this was html & written to the point instead of stuffed in a pdf & written up in this roundabout manner, it would be on top of HN with 100+ votes :) I read the whole pdf but here's the TL:DR; anyways - Randomization improves algorithms. This is so obvious to CS folks its taught in basic cs101 - the ones i'm familiar with are where you pick a random pivot element for quicksort, or say the one where you draw a circle inside a square & pick n random points inside the square, four times the number of points inside the circle will equal pi as n becomes large, or you resort to the miller rabin test for primality when you are doing those rsa calculator type problems where you pick keys for encryption, which will randomly sample some number of possible witnesses and call the number prime if none turn out to be witnesses, or using monte-carlo methods to compute integrals for functions for which no closed-form formula exists etc....there's like tons of examples where you introduce a little bit of randomness & it'll speed up your algorithm. So this Page+Hong wrote a paper where they want you to randomly hire employees ( who they call problem-solvers or agents ), because diversity trumps ability ?! So if you have 1000 applicants, instead of hiring based on some metric like ivy-league/test-scores/IQ/github/whatever, you just hire randomly, because the randomness introduces diversity which trumps ability ?!! To prove this nonsensical point, they introduce an artificial math problem where agents proceeding randomly obtain the right answer, & not doing so gets you stuck. Ergo, diversity > ability. Sheesh.
- yummyfajitas 12y ago
  This is in Notices of the AMS, which is about as mainstream (together with SIAM Review) as mathematical publications get. Randomization improves algorithms. This is a contentious claim. Random choices are actually very rarely the best - they are often good enough and versatile, but they are rarely the best. For example, consider Monte Carlo integration. You get O(N^{-1/2}) convergence. If you use a deterministic set of points explicitly designed to have low discrepancy (aka "Quasi-Monte Carlo"), you can get O(N^{-1 + logarithmic stuff}) convergence. http://www.chrisstucchio.com/blog/2014/adversarial_bandit_is_not_statistics_problem.html http://www.chrisstucchio.com/blog/2014/adversarial_bandit_is... Eliezer Yudkowsky also wrote a great critique of this issue, though I can't find it right now.
  - zwegner 12y ago
    I believe the article you're referring to is: http://lesswrong.com/lw/vp/worse_than_random/ http://lesswrong.com/lw/vp/worse_than_random/ Choice quote: > As a general principle, on any problem for which you know that a particular unrandomized algorithm is unusually stupid - so that a randomized algorithm seems wiser - you should be able to use the same knowledge to produce a superior derandomized algorithm. An interesting counterexample to this, an example which to me illustrates a very powerful aspect of randomness, is the monte-carlo revolution in computer Go (AI for the ancient Asian board game). For years, computer progress stagnated, as the techniques were mostly focused on encoding human knowledge into code. While most of this human knowledge is generally correct, it introduces significant bias in the way positions are evaluated. The way these rules-of-thumb interact is very hard to predict, and tree search algorithms are quite good at finding positions that are incorrectly evaluated. Because of this, the worst-case behavior of an evaluation function is much more important than it's best-case or average behavior. Computers started making lots of progress when a new technique was used: rather than try to evaluate positions by a large set of heuristics, they were evaluated by playing random games. Go positions are quite hard to evaluate from simple rules of thumb, and this random game approach gives a much more balanced, long-term view of positions. And most importantly, there is much less bias. Obviously, an entirely random game, with a uniform distribution over possible moves, is easy to improve upon. But computer go programmers noticed an interesting phenomenon: while certain types of knowledge incorporated into the random move distribution (to make it "more intelligent", as judged by a human) were helpful, others were not (even after taking into account the computational cost of adding the knowledge), and it wasn't always clear why. The same observation about heuristic evaluation noted above applied: having a balanced distribution of move choices, with a reasonable probabilistic lower bound of effectiveness, is more important than making an intelligent choice that is usually correct, but has unpredictable, extreme worst-case performance. So we see that randomness does have an important property: it avoids the downside of "knowledge" that generally seems correct but can go horribly wrong in unexpected ways. I don't know of a good writeup of this phenomenon. My understanding of it is mostly assembled from following informal discussions on the computer-go mailing list for several years. In a quick search through my gmail archives I can't find much on the subject, but here's an interesting post about related topics in the computer chess world (that incidentally doesn't talk about randomness, but illustrates well the benefits of avoiding bias): http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=135133&t=15504 http://www.talkchess.com/forum/viewtopic.php?topic_view=thre...
- sopooneo 12y ago
  I have not read the circle-square theorem, but surely you are leaving something out. With a large n, many points will fall inside the circle, and four times that quantity can not logically get closer and closer to 3.14
  - darth_aardvark 12y ago
    It's 4*the proportion of points that fall in the circle.
  - dxbydt 12y ago
    you have to divide by n.Here - def pointInsideCircle = {val (z,w) = (0.5,0.5);val (x,y) = (math.random,math.random); if ((x-z)*(x-z)+(w-y)*(w-y) < 0.25) 1 else 0;} (1 to 1000).map{x=> pointInsideCircle}.sum*4/1000.0 scala> 3.132 (1 to 1000000).map{x=>pointInsideCircle}.sum*4/1000000.0 scala> 3.141612 So as n goes from 1000 to a million, your pi accuracy has improved from 3.13 to 3.1416. As Chris Stuccio pointed out elsewhere on this page, this thing converges O(N^{-1/2} ie. very slowly. You can try Buffon's needle if you want something much faster.
- 4bpp 12y ago
  > Randomization improves algorithms. The better intuition is "randomisation fixes algorithms that get stuck for superficial reasons" - if you wrote that instead of the diversity thing as the intuitive conclusion of the Hong and Page theorem, you could get away with it in a theoretical CS survey paper or introductory textbook. The set of assumptions they make about the different \Phi would be fairly reasonable, for instance, if we were talking about a number of different flawed heuristics for a search problem.
- jev 12y ago
  I also read the paper. I didn't have any trouble understanding it. The point is that it can be explained 10x better in 10x less space, just like you did.
revelation 12y ago
Have you read the linked paper and the one its discussing? I find the critique vastly more readable.

Probably because the mathematicians don't seem to have the ability to explain why it is not sound without devolving into obscure symbols and jargon.

by jev 12y ago

Probably because the mathematicians don't seem to have the ability to explain why it is not sound without devolving into obscure symbols and jargon.

amathstudent 12y ago

I think that's a very important point. Indeed, when you try to explain something simply to people, they often won't believe that it's really that simple, since there's all those symbols!

dxbydt 12y ago

If this was html & written to the point instead of stuffed in a pdf & written up in this roundabout manner, it would be on top of HN with 100+ votes :) I read the whole pdf but here's the TL:DR; anyways - Randomization improves algorithms. This is so obvious to CS folks its taught in basic cs101 - the ones i'm familiar with are where you pick a random pivot element for quicksort, or say the one where you draw a circle inside a square & pick n random points inside the square, four times the number of points inside the circle will equal pi as n becomes large, or you resort to the miller rabin test for primality when you are doing those rsa calculator type problems where you pick keys for encryption, which will randomly sample some number of possible witnesses and call the number prime if none turn out to be witnesses, or using monte-carlo methods to compute integrals for functions for which no closed-form formula exists etc....there's like tons of examples where you introduce a little bit of randomness & it'll speed up your algorithm. So this Page+Hong wrote a paper where they want you to randomly hire employees ( who they call problem-solvers or agents ), because diversity trumps ability ?! So if you have 1000 applicants, instead of hiring based on some metric like ivy-league/test-scores/IQ/github/whatever, you just hire randomly, because the randomness introduces diversity which trumps ability ?!! To prove this nonsensical point, they introduce an artificial math problem where agents proceeding randomly obtain the right answer, & not doing so gets you stuck. Ergo, diversity > ability. Sheesh.

yummyfajitas 12y ago
This is in Notices of the AMS, which is about as mainstream (together with SIAM Review) as mathematical publications get. Randomization improves algorithms. This is a contentious claim. Random choices are actually very rarely the best - they are often good enough and versatile, but they are rarely the best. For example, consider Monte Carlo integration. You get O(N^{-1/2}) convergence. If you use a deterministic set of points explicitly designed to have low discrepancy (aka "Quasi-Monte Carlo"), you can get O(N^{-1 + logarithmic stuff}) convergence. http://www.chrisstucchio.com/blog/2014/adversarial_bandit_is_not_statistics_problem.html http://www.chrisstucchio.com/blog/2014/adversarial_bandit_is... Eliezer Yudkowsky also wrote a great critique of this issue, though I can't find it right now.
- zwegner 12y ago
  I believe the article you're referring to is: http://lesswrong.com/lw/vp/worse_than_random/ http://lesswrong.com/lw/vp/worse_than_random/ Choice quote: > As a general principle, on any problem for which you know that a particular unrandomized algorithm is unusually stupid - so that a randomized algorithm seems wiser - you should be able to use the same knowledge to produce a superior derandomized algorithm. An interesting counterexample to this, an example which to me illustrates a very powerful aspect of randomness, is the monte-carlo revolution in computer Go (AI for the ancient Asian board game). For years, computer progress stagnated, as the techniques were mostly focused on encoding human knowledge into code. While most of this human knowledge is generally correct, it introduces significant bias in the way positions are evaluated. The way these rules-of-thumb interact is very hard to predict, and tree search algorithms are quite good at finding positions that are incorrectly evaluated. Because of this, the worst-case behavior of an evaluation function is much more important than it's best-case or average behavior. Computers started making lots of progress when a new technique was used: rather than try to evaluate positions by a large set of heuristics, they were evaluated by playing random games. Go positions are quite hard to evaluate from simple rules of thumb, and this random game approach gives a much more balanced, long-term view of positions. And most importantly, there is much less bias. Obviously, an entirely random game, with a uniform distribution over possible moves, is easy to improve upon. But computer go programmers noticed an interesting phenomenon: while certain types of knowledge incorporated into the random move distribution (to make it "more intelligent", as judged by a human) were helpful, others were not (even after taking into account the computational cost of adding the knowledge), and it wasn't always clear why. The same observation about heuristic evaluation noted above applied: having a balanced distribution of move choices, with a reasonable probabilistic lower bound of effectiveness, is more important than making an intelligent choice that is usually correct, but has unpredictable, extreme worst-case performance. So we see that randomness does have an important property: it avoids the downside of "knowledge" that generally seems correct but can go horribly wrong in unexpected ways. I don't know of a good writeup of this phenomenon. My understanding of it is mostly assembled from following informal discussions on the computer-go mailing list for several years. In a quick search through my gmail archives I can't find much on the subject, but here's an interesting post about related topics in the computer chess world (that incidentally doesn't talk about randomness, but illustrates well the benefits of avoiding bias): http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=135133&t=15504 http://www.talkchess.com/forum/viewtopic.php?topic_view=thre...
sopooneo 12y ago
I have not read the circle-square theorem, but surely you are leaving something out. With a large n, many points will fall inside the circle, and four times that quantity can not logically get closer and closer to 3.14
- darth_aardvark 12y ago
  It's 4*the proportion of points that fall in the circle.
- dxbydt 12y ago
  you have to divide by n.Here - def pointInsideCircle = {val (z,w) = (0.5,0.5);val (x,y) = (math.random,math.random); if ((x-z)*(x-z)+(w-y)*(w-y) < 0.25) 1 else 0;} (1 to 1000).map{x=> pointInsideCircle}.sum*4/1000.0 scala> 3.132 (1 to 1000000).map{x=>pointInsideCircle}.sum*4/1000000.0 scala> 3.141612 So as n goes from 1000 to a million, your pi accuracy has improved from 3.13 to 3.1416. As Chris Stuccio pointed out elsewhere on this page, this thing converges O(N^{-1/2} ie. very slowly. You can try Buffon's needle if you want something much faster.
4bpp 12y ago
> Randomization improves algorithms. The better intuition is "randomisation fixes algorithms that get stuck for superficial reasons" - if you wrote that instead of the diversity thing as the intuitive conclusion of the Hong and Page theorem, you could get away with it in a theoretical CS survey paper or introductory textbook. The set of assumptions they make about the different \Phi would be fairly reasonable, for instance, if we were talking about a number of different flawed heuristics for a search problem.
jev 12y ago
I also read the paper. I didn't have any trouble understanding it. The point is that it can be explained 10x better in 10x less space, just like you did.

revelation 12y ago

Have you read the linked paper and the one its discussing? I find the critique vastly more readable.