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

C_f = subset of C whose n^th 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 C_f.

Given analogous sets of predictors P_f and evaders E_f, there exists a predictor that can learn to predict all of E_f, and an evader that can learn to evade all of P_f.

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 < 10⁹⁰ bits and performed < 10¹²⁰ operations.

f(n) = 2ⁿ > 10¹²⁰ for n > 400, so C_f includes all sequences that can be generated in our universe.

Similarly for P_f and E_f.

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.