Adversarial Sequence Prediction
Bill Hibbard
University of Wisconsin
http://www.ssec.wisc.edu/~billh/
Sequence Prediction
Adversarial Sequence Prediction
(The Woods Have Eyes)
C = computable binary infinite sequences
f: N → N monotonically increasing
Cf = subset of C whose nth symbol can be computed in time < f(n), for n large enough
Legg's lemma 6.2: There is a predictor that can learn to predict all sequences in Cf.
Given analogous sets of predictors Pf and evaders Ef, there exists a predictor that can learn to predict all of Ef, and an evader that can learn to evade all of Pf.
So the game between predictors and evaders is a computational resources arms race: if either side can simulate all possible opponents, it always wins.
Lloyd estimates that the universe contains < 1090 bits and performed < 10120 operations.
f(n) = 2n > 10120 for n > 400, so Cf includes all sequences that can be generated in our universe.
Similarly for Pf and Ef.
Software experiments with table lookup algorithm, stores game sequences up to length that fits in table. Uses modest computing resources.
Table size measures computing resources,
increases (decreases) with win (loss).
Over a broad range of parameters, one side gets and keeps all resources.
Unstable computational resources arms race.
AI Ethics
Increasing intelligence creates increasing economic and political inequality.
Not AI vs humanity, but an elite vs the mass.
Market won't need the mass for workers or soldiers.
Yudkowsky / Legg on provably friendly AI
Legg: cannot prove what an AI will achieve physically.
Yudkowsky: only trying to prove intentions.
But intentions must have physical implementation.