Logical Induction: a computable approach to logical non-omniscience

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

• Adrià Garriga Alonso (University of Cambridge)
• Wednesday 21 February 2018, 17:00-18:30
• Cambridge University Engineering Department, CBL Seminar room BE4-38. For directions see http://learning.eng.cam.ac.uk/Public/Directions.

If you have a question about this talk, please contact Adrià Garriga Alonso.

Link to slides: https://valuealignment.ml/talks/2018-02-21-logical-induction.pdf

Is P≠NP? 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, the difference between any two consecutive primes is less than 7·10^7 (Zhang, 2014).

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 a computable agent (read: its program runs in a finite amount of time).

In this session we will talk about Logical Induction (Garrabrant et al., 2016), a computable algorithm for assigning probabilities to every logical statement in a formal language. We will examine several desirable properties of the algorithm. For example, Logical Induction (almost quoting from their abstract):

(1) learns to predict patterns of truth and falsehood in logical statements, often long before having the resources to prove or disprove the statements, so long as the patterns can be written in polynomial time,

(2) learns to use appropriate statistical summaries to predict sequences of statements whose truth values appear pseudorandom

(3) learns to have accurate beliefs about its own current beliefs, in a manner that avoids the standard paradoxes of self-reference.

Finally, we will talk about its construction, and its implications for solving the value alignment problem.

References:

Logical Induction (Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor): https://arxiv.org/abs/1609.03543

Abridged version: https://intelligence.org/files/LogicalInductionAbridged.pdf

Zhang, Yitang. “Bounded gaps between primes.” Annals of Mathematics 179.3 (2014): 1121-1174. http://annals.math.princeton.edu/wp-content/uploads/annals-v179-n3-p07-p.pdf

This talk is part of the Engineering Safe AI series.

This talk is included in these lists:

• Cambridge University Engineering Department, CBL Seminar room BE4-38. For directions see http://learning.eng.cam.ac.uk/Public/Directions
• Cambridge talks
• Chris Davis' list
• Engineering Safe AI
• Trust & Technology Initiative - interesting events

Note that ex-directory lists are not shown.