tag:blogger.com,1999:blog-3722233.post140442697667456694..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Machine Learning and ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-78301527318872330482022-10-03T21:27:00.144-05:002022-10-03T21:27:00.144-05:00I don't think Scott's quote makes sense. ...I don't think Scott's quote makes sense. How many people can actually recognize that Warren Buffett has a good investment strategy? Of course, "buy companies based on intrinsic value" sounds good, but understanding that Coca-Cola, for example, is a good investment is much more difficult. And there's not that many people presenting investment strategies, so if one actually could recognize which were good investment strategies, one would be set. Similarly, how many people can actually follow a step-by-step math argument? You should know from teaching that students have trouble understanding the proofs of theorems when they are taught.Unknownhttps://www.blogger.com/profile/14738696573852659665noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83687844492710661352022-09-30T17:02:00.622-05:002022-09-30T17:02:00.622-05:00I don't hear any of the current AI blokes (oth...I don't hear any of the current AI blokes (other than the critics) saying "humans build models of the world in their heads and do causal reasoning on those models. We need to figure out how to do that." Quite the contrary, the game in current AI is to _avoid_ doing that work, and simply pray that statistical computation will somehow magically create things that act as though they were doing that.<br /><br />In particular, humans really do build really good models of the world and do seriously amazing causal reasoning on those models. Another way of putting it is to point out that the singularity _already happened_ and it is us.<br /><br />But that's something noone wants to hear. Go figure. I still find human intelligence amazing, and GPT-3 and the like fundamentally boring (since it isn't even trying to actually reason, it's trying to pretend to reason). YMMV, but the field looks completely committed to being at the intellectual level of parlor tricks (i.e. appearing to do X without actually doing X; this really is high-tech parlor trickery.)<br />DJLhttps://www.blogger.com/profile/04036156397398405817noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1026105358162236092022-09-29T16:40:38.155-05:002022-09-29T16:40:38.155-05:00Given how little we can currently control the resu...Given how little we can currently control the results of ML, getting ML to do only what we want it to do, or getting ML to provide explanations for its decisions feels a bit like getting ML to find proofs related to its own behavior. In TCS/Math we typically think of coming up with proofs as a creative process, and that feels like a lot of what's behind Scott's "automating creativity" phrase. So far, this is the kind of thing that seems outside of the wheelhouse for ML methods.<br /><br />(BTW: Systems for taking images and rendering them automatically in some artistic style was something that showed up in SIGGRAPH in the 1990s. They didn't have the connection to text of course.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18654764038459061392022-09-29T13:14:07.297-05:002022-09-29T13:14:07.297-05:00Dall-E must have envisioned Monet visiting Dagstuh...Dall-E must have envisioned Monet visiting Dagstuhl after some really awful flooding!Eric Allenderhttps://www.blogger.com/profile/07417405562053586552noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87828380366692736902022-09-29T12:44:59.365-05:002022-09-29T12:44:59.365-05:00I think computational complexity and theory at lar...I think computational complexity and theory at large should be thinking of the implications of ML, though I am not sure the question of implications of P=NP is the central one. You are right that "automating creativity" doesn't have the same ring to it, but there are many other ones. I think several of the applications in my chapter https://introtcs.org/public/lec_14_PvsNP.html are still relevant. Also, while beating mere humans might not be a big deal, imagine the ability to find a small model that is as good as text completion as GPT-3 (or GPT-4,5) or proving that it doesn't exist...<br /><br />So I think the P vs NP question will still be here to stay, but it may well be that many other parts of the field will change. It is a bit like what the discovery of computers did to math. Some questions that people were interested in (solving various specific equations) became trivial, many new questions became important. Whole new subfields were created, in particular our own.<br /><br />Boaz Barak<br />Anonymousnoreply@blogger.com