Logical Uncertainty

Add to your list(s) Download to your calendar using vCal

• Adrià Garriga Alonso (University of Cambridge)
• Wednesday 13 February 2019, 13:45-15:15
• Engineering Department, CBL Room 438.

If you have a question about this talk, please contact jg801.

Is P≠NP? Is the Riemann hypothesis true? Are there infinitely many twin primes? These conjectures haven’t been proven or disproven, but we have quite a bit of “evidence” for them in the form of proven related sentences.

For example, there exist many decision problems known to be in P, and many that known to be NP-complete, along with schemes for reducing problems to other problems within those clusters. But no single link, in 50 years, has yet been discovered from NP-complete to P. [1] As another example, Zhang [2] showed that for any n, we can find a larger prime such that it’s at most 7·10^7 away from the next prime.

This is the problem of logical uncertainty: to which degree should we believe in these logical sentences? How should we update our beliefs based on the related evidence? One might turn to probability theory for answers. However, the veracity of the sentences is implied by things we assume (the ZF/C axioms), rather than any data we need to observe. Probability theory thus dictates we should assign them probability 1 if they are true, and 0 if they are false, which is clearly impossible to do in general for an algorithm that runs in a finite amount of time.

In this session we will learn about the problem of logical uncertainty, what should a solution to it look like, and how some naive approaches to it fall short [3]. Then, we will examine the “Logical Induction” algorithm [4], which satisfies many desirable properties including being computable, but unfortunately only does so asymptotically and it is not usable in practice. We will conclude with a recap and an outline of a few extra open problems.

[1] Aaronson, S. “The Scientific Case for P≠NP”. https://www.scottaaronson.com/blog/?p=1720 [2] Zhang, Yitang. “Bounded gaps between primes.” Annals of Mathematics 179.3 (2014): 1121-1174. [3] Demski, A. “All Mathematicians are Trollable: Divergence of Naturalistic Logical Updates” https://agentfoundations.org/item?id=815 [4] Demski, A. and Eisenstat, S. “An Untrollable Mathematician”. https://agentfoundations.org/item?id=1750 [5] Garrabrant, Scott, et al. “Logical induction.” https://arxiv.org/abs/1609.03543 (2016)

This talk is part of the Machine Learning Reading Group @ CUED series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Engineering Department, CBL Room 438
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• ML
• Machine Learning Reading Group
• Machine Learning Reading Group @ CUED
• Machine Learning Summary
• Quantum Matter Journal Club
• Required lists for MLG
• School of Technology
• Simon Baker's List
• TQS Journal Clubs
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.