{"id":335,"date":"2008-06-26T15:10:40","date_gmt":"2008-06-26T19:10:40","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=335"},"modified":"2008-06-26T15:10:40","modified_gmt":"2008-06-26T19:10:40","slug":"quantum-computing-since-democritus-lecture-15-learning","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=335","title":{"rendered":"Quantum Computing Since Democritus Lecture 15: Learning"},"content":{"rendered":"

Lektur iz heer<\/a>.<\/p>\n

This week I explain Valiant’s PAC-learning model (previously covered in GITCS Lectures 19<\/a>, 20<\/a>, 21<\/a>), and also — in response to a question from the floor — take a swipe at Bayesian fundamentalism.\u00a0 When you only know one formalism to describe some phenomenon (in this case, that of choosing hypotheses to fit data), it’s easy to talk yourself into believing that formalism is the Truth: to paraphrase Caliph Omar, “if it agrees with Bayesianism, it is superfluous; if it disagrees, it is heresy.”\u00a0 The antidote is to learn other formalisms.\u00a0 Enter computational learning theory: an account of learning that’s clear, mathematically rigorous, useful, nontrivial, and completely different from the Bayesian account (though of course they have points of contact).\u00a0 The key idea is to jettison the notoriously-troublesome notion of a prior<\/em>, replacing it by a concept class<\/em> (about which one makes no probabilistic assumptions), as well as a probability distribution over sample data rather than hypotheses.<\/p>\n

Incidentally, I’d say the same thing about complexity theory.\u00a0 If you think (for example) that Turing machines are the only way to reason about computational efficiency, then you’re overdue for a heaping helping of communication complexity, circuit complexity, query complexity, algebraic complexity…<\/p>\n

Ah yes, complexity.\u00a0 This week I was at the Conference on Computational Complexity<\/a> at the beautiful University of Maryland in College Park: home of the Terrapins<\/a>, as one is reminded by signs placed roughly every three inches.\u00a0 I heard some great talks<\/a> (ask in the comments section if you want details), gave two<\/a> talks<\/a> myself, and during the business meeting, was elected to the CCC Steering Committee.\u00a0 This being a complexity conference, my declared campaign motto was “No We Can’t!”<\/em>\u00a0 It was inspiring to see how this simple yet hopeful motto united our community: from derandomization to circuit lower bounds, from quantum computing to proof complexity, we might have different backgrounds but we all worry about shrinking grant sizes and the rising costs of conference registration; we all face common challenges to which we want to prove that no solutions exist.\u00a0 Rest assured, I will treat my duties as a steering committee member (mostly helping to select PC chairs, who in turn select the program committees who select the conference papers) with the awesome gravity they deserve.<\/p>\n","protected":false},"excerpt":{"rendered":"

Lektur iz heer. This week I explain Valiant’s PAC-learning model (previously covered in GITCS Lectures 19, 20, 21), and also — in response to a question from the floor — take a swipe at Bayesian fundamentalism.\u00a0 When you only know one formalism to describe some phenomenon (in this case, that of choosing hypotheses to fit […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5,6,4],"tags":[],"class_list":["post-335","post","type-post","status-publish","format-standard","hentry","category-complexity","category-democritus","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=335"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/335\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}