tag:blogger.com,1999:blog-3722233.post114047401343508421..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: Accuracy of Predicted ProbabilitiesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1140557418066188672006-02-21T15:30:00.000-06:002006-02-21T15:30:00.000-06:00I suspect that the big problem with measuring the ...I suspect that the big problem with measuring the accuracy of this service is that some students take their advice. If the report comes back, "Your chances of becoming a Harvard freshman are 0.001 percent," the student may well decide to save his money and apply to the local community college. Since the student was advised not to apply and ultimately didn't get in, this presumably counts as a successful prediction. They ought to be counting only those students who actually applied and were rejected.<BR/><BR/>Once we solve that problem, then ideally we would like to know the actual percentage of students accepted for each percentage predicted. For example, taking the subset of students who got a 60-percent prediction, the service would score perfect accuracy if 60 percent of them were admitted. Making the corresponding calculation for each percentage from 0 to 100 then gives you a graph of accuracy as a function of predicted success. Reducing that graph to a single scalar score is not trivial, but simply taking the average of the accuracies at all percentages is a reasonable way to start.<BR/><BR/>The actual scoring algorithm the service uses is not ideal, but on the other hand it doesn't strike me as being obviously unfair or designed to make the service look good. They leave themselves no middle ground for doubtful cases. In effect, they apply a threshold at 50 percent and turn each prediction into a simple binary value. Given that this algorithm is the basis of their guarantee, maybe they should also communicate results to the applicant in the same form. Don't tell the poor baffled kid, "Your chances are 54 percent." Just say, "Yes: Apply" or "No: Forget about it." If they can actually achieve 98 percent accuracy on that basis, I'm pretty impressed.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1140549494225318112006-02-21T13:18:00.000-06:002006-02-21T13:18:00.000-06:00I was thinking about this problem once with regard...I was thinking about this problem once with regard to online medical records. I figured it might one day be possible to go online and discover the probability that you'd acquire some medical conditions. The question is, how do we know the system performs well.<BR/><BR/>One simple approach is to give everyone the same probability. If p percent of people eventually develop condition y, everyone has a p percent chance of getting y. This approach seems "correct" in some sense, it is certainly not optimal.<BR/><BR/>In the case of the college service, you need a penalty system that gives full refunds for exactly this type of blanket prediction. Many penalty systems could work, but I'm not clear what the right choice is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1140534866974634442006-02-21T09:14:00.000-06:002006-02-21T09:14:00.000-06:00This is an interesting problem.What is a quadratic...This is an interesting problem.<BR/><BR/>What is a quadratic penalty scheme? Is it provably good?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1140526576807744612006-02-21T06:56:00.000-06:002006-02-21T06:56:00.000-06:00They should use a quadratic penalty scheme.They should use a quadratic penalty scheme.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1140501352963540742006-02-20T23:55:00.000-06:002006-02-20T23:55:00.000-06:00Very nice post!Very nice post!Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1140493343790604712006-02-20T21:42:00.000-06:002006-02-20T21:42:00.000-06:00More to the point: this scheme could be a money-ma...More to the point: this scheme could be a money-maker even if the company totally ignored each student's application materials. Like the lazy desert weatherman who gets paid by his accuracy, and always predicts a sunny day.Anonymousnoreply@blogger.com