What are Universal Inductors, Again?post by Diffractor · 2018-11-07T22:32:57.364Z · score: 11 (5 votes) · LW · GW · None comments
[Attention Conservation Notice: This just recaps an old result and patches a hole in it, it doesn't contain substantially new ideas.]
Universal Inductors can be thought of as logical inductors over bitstrings, which are notable because they can act as a logical inductor over any theory you want (PA, ZFC, 2nd order arithmetic), by fixing some efficiently computable function from bits to sentences in the language of your theory, conditioning the universal inductor (which is a probability distribution over infinite bitstrings) on the bits which correspond to proven theorems, and reading out the probability of other bits/sentences from the resulting conditional distribution. This trick works by Theorem 4.7.2 in the logical induction paper, "Closure Under Conditioning", which shows that conditioning the probabilities of a logical inductor on a sequence of non-inconsistent sentences, yields a logical inductor over a deductive process where all the conditionals are true.
Also, since they are a probability distribution over infinite bitstrings, it makes sense to think about them as having a probability measure over worlds (assignments of statements to true or false, for all statements) at all finite stages, instead of just in the limit.
However, in Scott's old post about universal inductors, their construction was never described.
Note that a Universal Inductor corresponds to a Logical Inductor, but the associated Logical Inductor will not have finite support, and so will be different from the one constructed in the paper. Never the less, Universal Inductors can be shown to exist using a similar construction.
This post will give that construction. To begin with, a Universal Inductor must fulfill the following two properties:
First, it must be a distribution over infinite bitstrings, such that is computable for all and all which are finite bitstrings. This gives the probability that an infinite bitstring starts with as a prefix.
Second, the theory is one where the th atomic statement is of the form "the th bit in this infinite bitstring is a ", and induces a function from these statements to probabilities, and the sequence of probability assignments must form a logical inductor over the empty deductive process. (ie, the inductor never sees any evidence of the form "this bit is a ", it just runs forever without getting any feedback.)
To begin with, the supertrader construction from Section 5 of the logical induction paper is the exact same. Traders look at the prices of boolean combinations of atomic statements, and use them in continuous functions to buy or sell shares in boolean combinations of atomic statements.
The interesting part is the construction of the space that we'll be finding a fixed-point in. At timestep , there is a most-distant bit that has ever appeared in a boolean combination of bits that a trader has bought/sold shares in, or looked at the price of. This is bit . If we assign prices to all bitstrings of length , then the probability of any finite bitstring that is longer can be given by just using the uniform distribution on bits after that point. This corresponds to assigning 50/50 probability to all statements which are too large to have thought about them yet. Therefore, our space of interest is the dimensional simplex of probability distributions over all bitstrings of length .
Given a point in this space, it is possible to read out the probability of any particular boolean combination of bits by just summing up the probability on all -length bitstrings that fit that constraint, so we can determine the prices that the supertrader sees.
We can also assign all bitstrings but one to a basis vector for the space, by letting the basis vector for a bitstring be the vector pointing to the corresponding vertex of the simplex from its center. A purchase of one share in a boolean combination corresponds to the vector comprised of the sum of basis vectors that correspond to the bitstrings fulfilling the conditions of the boolean. Note that a purchase of the one bitstring we left out can be re-expressed as a purchase of 1 dollar and selling a share of all other bitstrings.
As a simple case of this re-expression, when , (because it has to be a probability distribution), so the price of the purchase is the same. And as for the purchase, both purchases have the feature that they are worth dollar if the world is and dollars if the world is something different.
Therefore, given a point in the simplex, the net purchase and selling of a bunch of different boolean combinations of bits can be broken down into a whole bunch of vectors, which sum up to give a net trade vector , and finding the point in the simplex that's closest to is the output of the continuous function that we can then find the fixed-point of.
Now, given a fixed-point in the interior of the simplex, , so there is no net trade. Given a fixed-point on the boundary of the simplex, can be interpreted as being composed entirely of selling shares with a price of , which obviously has or negative value, although this is quite nontrivial to show. Once this is proved, it then immediately follows that this process described above is a Universal Inductor.
From here on, we will simply take care of this last theorem to be shown.
For all price vectors on the boundary of the simplex that are a fixed-point, the vector representing the net trade can be interpreted as being composed entirely of 's for all components in which has a nonzero entry, and nonpositive for all components in which has a entry.
First, some notation will be laid out.
, and it is the dimension of the space the simplex is in. denotes the vector of length that is the fixed-point, and denotes the unique "canonical interpretation" of this vector as a vector of length with nonnegative coordinates that sum to , which gives the probabilities of the various bitstrings. Similarly, denotes the vector of length which corresponds to the net trade. Given a constant , will denote a vector with all coordinates being , with the length clear from context. Given a vector and coordinate a, with being the value of the 'th coordinate of , is the vector that is in all coordinates except for , and at the 'th coordinate.
To begin, note that, given , there are multiple possible vectors of length which give the net purchase of shares. As an example of this, when , and both correspond to the same trade, because buying a share 0f is equivalent to selling a share of . We will show that has an interpretation as a vector which is everywhere is positive, and nonpositive everywhere is , because this corresponds to the net trade being interpretable as buying no shares, and only selling shares of bitstrings with a price of , which cannot lead to any gain no matter which bitstring is the true one.
Now, we will fix our basis vectors for the space. Because is on the boundary of the simplex, must have at least one entry. Fix that vertex that corresponds to that bitstring as the origin of the coordinate system, and let the basis be comprised of the set of unit vectors that point from the center of the simplex to the vertices that correspond to all the other bitstrings. This spans the space that the simplex is embedded in. Annoyingly, this is not an orthonormal basis, so computing the dot product will be more complicated. The dot product between any two different basis vectors is (hat tip to Vanessa from MIRIxDiscord)
We can start by asking the question "In this basis, what condition on a vector corresponds to being inside the simplex?" The condition is that there exist a s.t. has all entries in and the entries sum up to . Note that for specifically, by the way we have defined the basis, .
Also, the coordinates for can be broken down into coordinates where has entries, and coordinates where has positive entries. Therefore, given an arbitrary vector , it can be expressed as , where is the vector of coordinates where is , and is the vector of coordinates where is positive.
The proof strategy that will be used is dividing into cases, and showing that for all cases besides the ones that prove the theorem, there is an "allowable perturbation vector" s.t. lies in the simplex, and is closer to than it is to . This implies that is not a fixed-point, because it isn't the point closest to , but is a fixed-point, so we have a contradiction. Note that being closer to than to is equivalent to , which can be rewritten as which can be rewritten as . This last statement will be the proof target in the following cases.
Case 1: There is some pair of coordinates , , s.t , and .
Let be s.t. , , and all other coordinates are . Note that since (because and adds up to ), and adds up to , then for sufficiently small , has all entries lie in and sums up to . Then can be taken as , to yield that lies in the simplex.
Define as . Note that is at coordinates and .
Rewriting as , and using the fact that the dot product between any two different basis vectors of our space is , , so .
and because , for some positive .
A similar analysis applies to show for some positive , and for sufficiently small , we get our desired result that .
Now, the elimination of this case shows that must have all entries equal some constant , while must have all entries if it is nonempty. This produces three more exhaustive cases.
Case 2: , is positive.
In this case, note that a purchase of all shares but one can be reinterpreted as buying of all shares but one, and selling the remaining share. Therefore, this trade is equivalent to selling shares in the probability-zero bitstring that we took as the origin, buying of all shares with positive probability, and selling a non-negative amount of all shares with probability (because has all entries ). Theorem 1 follows.
Case 3: , is .
This case immediately proves Theorem 1, because , and is or negative on all entries.
Case 4: , is negative.
If we can show that this case is impossible, we will be done. Let be some coordinate where is positive.
Let be s.t. , and all other coordinates are . Let . has all terms lie in for sufficiently small , because the is canceled out when is added, and the is taken out of a positive term. Because has entries, sums up to . sums up to 1, and sums up to , so the resulting vector sums up to , and lies in the simplex.
Now we will break down the dot products.
And for the next pair,
Note that the second term combines with the term from the first dot product we looked at to yield the following equation
Finally, because , by grouping terms and factoring out , we get
and, because all coordinates in are negative, this equals for some positive constant . By the same proof path,
For some positive constant . Therefore, for sufficiently small , and Case 4 is impossible, and the theorem follows because only Case 2 and 3 are left.
Comments sorted by top scores.