Posts
Comments
Seems also like the "playing dead" behaviour. If you're under attack and aren't going to summon/indicate allies (via sadness) or enforce your boundary yourself (via anger) or appease the attacker (via submission), another option is to give up on active response and hope that if you play dead just right, they'll lose interest for some reason. Many attackers' goals are better served by a responsive opponent; and attacking someone dead is both potentially unhealthy and no fun.
Ah, I think I can stymy with 2 nonconstant advisors. Namely, let and . We (setting up an adversarial ) precommit to setting if and if ; now we can assume that always chooses , since this is better for .
Now define and . Note that if we also define then is bounded; therefore if we can force or then we win.
Let's reparametrize by writing and , so that .
Now, similarly to how worked for constant advisors, let's look at the problem in rounds: let , and for . When determining , we can look at . Let . Let's set to 1 if ; otherwise we'll do something more complicated, but maintain the constraint that : this guarantees that is nondecreasing and that .
If then and we win. Otherwise, let , and consider such that .
We have . Let be a set of indices with for all , that is maximal under the constraint that ; thus we will still have . We shall set for all .
By the definition of :
For , we'll proceed iteratively, greedily minimizing . Then:
Keeping this constraint, we can flip (or not flip) all the s for so that . Then, we have , if , and for , if .
Therefore, , so we win.
I don't yet know whether I can extend it to two nonconstant advisors, but I do know I can extend it to a countably infinite number of constant-prediction advisors. Let be an enumeration of their predictions that contains each one an infinite number of times. Then:
def M(p, E, P):
prev, this, next = 0, 0, 1
def bad(i):
return sum(log(abs((E[k] + P[i] - 1) /
(E[k] + p[k] - 1)))
for k in xrange(prev))
for k in xrange(this, next): p[k] = 0.5
prev, this, next = this, next, floor(exp(next - 1)) + 1
for i in xrange(0, Inf):
for k in xrange(this, next): p[k] = P[i]
prev, this, next = this, next, floor(exp(next - 1)) + 1
bad(i) is now up to date through E[:this], not just E[:prev]
bound = 2 * bad(i)
for j in xrange(0, Inf):
if P[j] == P[i]: continue
flip = P[j] < P[i]
p1, p2 = abs(P[i] - flip), abs(P[j] - flip)
for k in xrange(this, next): p[k] = abs(p1 - flip)
prev, this, next = this, next, floor(exp(next - 1)) + 1
if bad(i) <= 0: break
while bad(i) > 0 and bad(j) > 0:
# won't let bad(i) surpass bound
eps = (bound - bad(i)) / 2 / abs(1 - p1 - flip) / (next - this)
This is just for early iterations of the inner loop; in the limit, eps should be just enough for bad(i) to go halfway to bound if we let p = abs(p1 + eps - flip):
while eps >= 1 - p1 or
bound <= bad(i) + (next - this) *
log((1 - p1) / (1 - p1 - eps)):
eps /= 2
for k in xrange(this, next): p[k] = abs(p1 + eps - flip)
prev, this, next = this, next, floor(exp(next - 1)) + 1
for k in xrange(this, next): p[k] = abs(p1 - flip)
# this is where the P[i] + d * eps affects bad(i)
Consider . This is the probability between p1 and p2 such that if E[k] is chosen with probability then that will have an equal impact on bad(i) and bad(j). Now consider some between p1 and .
Every iteration where will decrease bad(j) by a positive quantity that's at least linear in this-prev, so (at least after the first few such iterations) this will exceed , so it will turn bad(j) negative. If this happens for all j then M cannot be bad for E. If it doesn't, then let's look at the first j where it doesn't. After a finite number of iterations, every iteration must have . However, this will cause bad(i) to decrease by a positive quantity that's at least proportional to bound - bad(i); therefore, after a finite number of such iterations, we must reach . So if M is bad for E then for each value of i we will eventually make and then move on to the next value of i. This implies M is not bad for E.
Emboldened by this, we can also consider the problem of building an that isn't outperformed by any constant advisor. However, this cannot be done, according to the following handwavy argument:
Let be some incompressible number, and let . When computing , can't do appreciably better than Laplace's law of succession, which will give it standard error , and relative badness (relative to the -advisor) on average. For , and , the greatest deviation of the badness from the trend is (according to the law of the iterated logarithm), which isn't enough to counteract the expected badness; therefore the badness will converge to infinity.
def M(p, E):
p1, p2 = 1./3, 2./3
prev, this, next = 0, 0, 1
bad1 and bad2 compute log-badnesses of M relative to p1 and p2, on E[:prev]; the goal of M is to ensure neither one goes to . prev, this, next are set in such a way that M is permitted access to this when computing p[this:next].
def bad(advisor):
return lambda:
sum(log(abs((E[i] + advisor(i) - 1) /
(E[i] + p[i] - 1)))
for i in xrange(prev))
bad1, bad2 = bad(lambda i: p1), bad(lambda i: p2)
for i in xrange(this, next): p[i] = 0.5
prev, this, next = this, next, floor(exp(next - 1)) + 1
while True:
for i in xrange(this, next): p[i] = p1
prev, this, next = this, next, floor(exp(next - 1)) + 1
bad1() is now be up to date through E[:this], not just E[:prev]
bound = 2 * bad1()
while bad1() > 0:
# won't let bad1() surpass bound
eps = (bound - bad1()) / 2 / (1 - p1) / (next - this)
This is just for early iterations; in the limit, eps should be just enough for bad1 to go halfway to bound:
while eps >= 1 - p1 or
bound <= bad1() + (next - this) *
log((1 - p1) / (1 - p1 - eps)):
eps /= 2
for i in xrange(this, next): p[i] = p1 + eps
prev, this, next = this, next, floor(exp(next - 1)) + 1
for i in xrange(this, next): p[i] = p1
# this is where the p1 + eps affects bad1()
prev, this, next = this, next, floor(exp(next - 1)) + 1
Now every iteration (after the first few) where will decrease bad2() by roughly at least , which is large enough to turn bad2() negative. Therefore, if M is bad for E, there can be only finitely many such iterations until the loop exits. However, every iteration where will cause bound - bad1() to grow exponentially (by a factor of ), so the loop will terminate.
Now we'll perform the same procedure for bad2():
for i in xrange(this, next): p[i] = p2
prev, this, next = this, next, floor(exp(next - 1)) + 1
bound = 2 * bad2()
while bad2() > 0:
# won't let bad2() surpass bound
eps = (bound - bad2()) / 2 / p2 / (next - this)
while eps >= p2 or
bound <= bad2() + (next - this) *
log( p2 / (p2 - eps)):
eps /= 2
for i in xrange(this, next): p[i] = p2 - eps
prev, this, next = this, next, floor(exp(next - 1)) + 1
for i in xrange(this, next): p[i] = p2
# this is where the p2 - eps affects bad2()
prev, this, next = this, next, floor(exp(next - 1)) + 1
For the same reasons as the previous loop, this loop either stops with bad2() < 0 or runs forever with bad2() bounded and bad1 repeatedly falling back below 0.
Therefore, this algorithm either gets trapped in one of the inner while loops (and succeeds) or turns bad1() and bad2() negative, each an infinite number of times, and therefore succeeds.
These results are still a bit unsatisfying.
The first half constructs an invariant measure which is then shown to be unsatisfactory because UTMs can rank arbitrarily high while only being good at encoding variations of themselves. This is mostly the case because the chain is transient; if it was positive recurrent then the measure would be finite, and UTMs ranking high would have to be good at encoding (and being encoded by) the average UTM rather than just a select family of UTMs.
The second half looks at whether we can get better results (ie a probability measure) by restricting our attention to output-free "UTMs" (though I misspoke; these are not actually UTMs but rather universal semidecidable languages (we can call them USDLs)). It concludes that we can't if the measure will be continuous on the given digraph - however, this is an awkward notion of continuity: a low-complexity USDL whose behavior is tweaked very slightly but in a complex way may be very close in the given topology, but should have measure much lower than the starting USDL. So I consider this question unanswered.
There is a lot more to say about the perspective that isn't relaxed to continuous random variables. In particular, the problem of finding the maximum entropy joint distribution that agrees with particular pairwise distributions is closely related to Markov Random Fields and the Ising model. (The relaxation to continuous random variables is a Gaussian Markov Random Field.) It is easily seen that this maximum entropy joint distribution must have the form where is the normalizing constant, or partition function. This is an appealing distribution to use, and easy to do conditioning on and to add new variables to. Computing relative entropy reduces to finding bivariate marginals and to computing , and computing marginals reduces to computing , which is intractable in general[^istrail], though easy if the Markov graph (ie the graph with edges for ) is a forest.
There have been many approaches to this problem (Wainwright and Jordan[^wainwright] is a good survey), but the main ways to extend the applicability from forests have been:
-
decompose components of the graph as "junction trees", ie trees whose nodes are overlapping clusters of nodes from the original graph; this permits exact computation with cost exponential in the cluster-sizes, ie in the treewidth[^pearl]
-
make use of clever combinatorial work coming out of statistical mechanics to do exact computation on "outerplanar" graphs, or on general graphs with cost exponential in the (outer-)graph genus[^schraudolph]
-
find nodes such that conditioning on those nodes greatly simplifies the graph (eg makes it singly connected), and sum over their possible values explicitly (this has cost exponential in the number of nodes being conditioned on)
A newer class of models, called sum-product networks[^poon], generalizes these and other models by writing the total joint probability as a positive polynomial in the variables and requiring only that this polynomial be simplifiable to an expression requiring a tractable number of additions and multiplications to evaluate. This allows easy computation of marginals, conditionals, and KL divergence, though it will likely be necessary to do some approximate simplification every so often (otherwise the complexity may accumulate, even with a fixed maximum number of sentences being considered at a time).
However, if we want to stay close to the context of the Non-Omniscience paper, we can do approximate calculations of the partition function on the complete graph - in particular, the Bethe partition function[^weller] has been widely used in practice, and while it's not logconvex like is, it's often a better approximation to the partition function than well-known convex approximations such as TRW.
[^istrail]: Istrail, Sorin. "Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intractability for the partition function of the Ising model across non-planar surfaces." In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 87-96. ACM, 2000.
[^weller]: Weller, Adrian. "Bethe and Related Pairwise Entropy Approximations."
[^pearl]: Pearl, Judea. "Probabilistic reasoning in intelligent systems: Networks of plausible reasoning." (1988).
[^schraudolph]: Schraudolph, Nicol N., and Dmitry Kamenetsky. "Efficient Exact Inference in Planar Ising Models." arXiv preprint arXiv:0810.4401 (2008).
[^wainwright]: Wainwright, Martin J., and Michael I. Jordan. "Graphical models, exponential families, and variational inference." Foundations and Trends® in Machine Learning 1, no. 1-2 (2008): 1-305.
[^poon]: Poon, Hoifung, and Pedro Domingos. "Sum-product networks: A new deep architecture." In Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on, pp. 689-690. IEEE, 2011.
In order to understand what the measure that was constructed from will reward, here's the sort of machine that comes close to :
Let be an arbitrary UTM. Now consider the function (or, really, any function with that visits every nonnegative integer infinitely many times), and let . (The indices here are zero-based.) Choose such that has no proper prefix in . Then, construct the UTM that does:
repeat:
s := ""
while s not in L:
# if there is no next character, halt
s := s + readchar()
if s == x0:
break
M0()
This will have .
here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to "encode" from the UTMs it efficiently encodes, using at most 2 bits (an average of ). This is somewhat interesting, but clearly doesn't capture the kind of computational expressivity we're primarily interested in.
Consider the function where . The reversible Markov chain with transition probabilities has a bounded positive invariant measure . Of course, as the post showed, the total measure is infinite. Also, because the chain is reversible and transient, the invariant measure is far from unique - indeed, for any machine , the measure will be a bounded positive invariant measure.
It seems tempting (to me) to try to get a probability measure by modding out the output-permutations (that the post uses to show this isn't possible for the full set of UTMs). To this end, consider the set of UTMs that have no output. (These will be unaffected by the output-permutations.) We can try to use the induced sub-digraph on these to build a probability measure . The measure of each UTM should be a function of the rooted edge-labeled digraph rooted at that UTM.
The most natural topology on rooted edge-labeled infinite digraphs is the one generated by the sets where ranges over finite rooted edge-labeled digraphs - we could hope that is continuous according to this topology. Unfortunately, this can't work: if then must be open, and so it must contain some finite intersection of the generating sets; however, every such intersection that's nonempty (as this one is) contains infinitely many UTMs, so the total measure must be infinite as well.
Actually, on further thought, I think the best thing to use here is a log-bilinear distribution over the space of truth-assignments. For these, it is easy to efficiently compute exact normalizing constants, conditional distributions, marginal distributions, and KL divergences; there is no impedance mismatch. KL divergence minimization here is still a convex minimization (in the natural parametrization of the exponential family).
The only shortcoming is that 0 is not a probability, so it won't let you eg say that ; but this can be remedied using a real or hyperreal approximation.
An easy way to get rid of the probabilities-outside-[0,1] problem in the continuous relaxation is to constrain the "conditional"/updated distribution to have (which is a convex constraint; it's equivalent to ), and then minimize KL-divergence accordingly.
The two obvious flaws are that the result of updating becomes ordering-dependent (though this may not be a problem in practice), and that the updated distribution will sometimes have , and it's not clear how to interpret that.
It may still be possible to get a unique (up to scaling) invariant measure (with infinite sum) over the UTMs by invoking something like the Krein-Rutman theorem and applying it to the transition operator. I haven't yet verified that all the conditions hold.
This measure would then be an encoding-invariant way to compare UTMs' "intrinsic complexity" in the sense of "number of bits needed to simulate".
This is interesting! I would dispute, though, that a good logical conditional probability must be able to condition on arbitrary, likely-non-r.e. sets of sentences.
What's the harm in requiring prior coordination, considering there's already a prior agreement to follow a particular protocol involving s? (And something earlier on in the context about a shared source of randomness to ensure convexity of the feasible set.)
If the fairness constraints are all pairwise (ie each player has fairness curves for each opponent), then the scheme generalizes directly. Slightly more generally, if each player's fairness set is weakly convex and closed under componentwise max, the scheme still generalizes directly (in effect the componentwise max creates a fairness curve which can be intersected with the surfaces to get the points.
In order to generalize fully, the agents should each precommunicate their fairness sets. In fact, after doing this, the algorithm is very simple: player X can compute what it believes is the optimal- feasible-and-fair-according-to-everyone point (which is unique because these are all convex sets), and if PA proves the outcome will be fair-according-to-X, then output ; otherwise output 0.
You did miss something: namely from PA+2 X wants to show feasibility of , not . In your example, , so the Löbian circle you describe will fail.
I'll walk through what will happen in the example.
The are just areas (ie ), not rectangles. In this example, is enough to contain and . For conciseness let's have , , and (so ).
Both X and Y have . According to X, , , and .
First the speculative phase will happen:
X will try to prove in PA+1 that and that is in the feasible set. The latter is immediately false, so this will fail.
Next, X will try to prove in PA+2 that and that is in the feasible set. This too is immediately false.
Next, X will try to prove in PA+3 that and that is feasible (in short, that ), and return 3 if so. This will fail to reach a cycle.
Then the bargaining phase:
Next, X will try to prove in PA+4 that and that is feasible, and return 3 if so. This will fail identically.
Next, X will try to prove in PA+5 that and that is feasible, and return 2 if so. This will reach a Löbian circle, and X and Y will both return 2, which is what we want.
How about a gridless scheme like:
The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.
Now discretize the possible "rectangle areas": let them be . (This requires a way to agree on that, but this seems easier than agreeing on grid points; the finer the better, basically. Perhaps the most obvious way to do it is to have these be evenly spaced from to ; then only and need to be agreed upon.)
X will do the following:
let be the first area in this list that is achieved by a feasible point on X's fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)
for , let be the "fair" utility distribution that achieves area ; let .
let be Y's output.
# Speculative phase:
if proves and is feasible, return .
else if proves and is feasible, return .
else if proves and is feasible, return .
# Bargaining phase:
else if proves and is feasible, return .
else if proves and is feasible, return .
else if proves and is feasible, return .
else return .
If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent's fairness curve.
Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area for some and X and Y follow the protocol then on the step, they will be able to agree on the coordinatewise min of their proposed feasible points with area .
If they're both really generous and their fairness curves don't intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.
How about a gridless scheme like:
The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.
Now discretize the possible "rectangle areas": let them be . (This requires a way to agree on that, but this seems easier than agreeing on grid points; the finer the better, basically. Perhaps the most obvious way to do it is to have these be evenly spaced from to ; then only and need to be agreed upon.)
X will do the following:
let be the first area in this list that is achieved by a feasible point on X's fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)
for , let be the "fair" utility distribution that achieves area ; let .
let be Y's output.
# Speculative phase:
if proves and is feasible, return .
else if proves and is feasible, return .
else if proves and is feasible, return .
# Bargaining phase:
else if proves and is feasible, return .
else if proves and is feasible, return .
else if proves and is feasible, return .
else return .
If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent's fairness curve.
Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area for some and X and Y follow the protocol then on the step, they will be able to agree on the coordinatewise min of their proposed feasible points with area .
If they're both really generous and their fairness curves don't intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.
How about a gridless scheme like:
The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.
Now discretize the possible "rectangle areas": let them be . (This requires a way to agree on that, but this seems easier than agreeing on grid points; the finer the better, basically. Perhaps the most obvious way to do it is to have these be evenly spaced from to ; then only and need to be agreed upon.)
X will do the following:
let be the first area in this list that is achieved by a feasible point on X's fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)
for , let be the "fair" utility distribution that achieves area ; let .
let be Y's output.
# Speculative phase:
if proves and is feasible, return .
else if proves and is feasible, return .
else if proves and is feasible, return .
# Bargaining phase:
else if proves and is feasible, return .
else if proves and is feasible, return .
else if proves and is feasible, return .
else return .
If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent's fairness curve.
Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area for some and X and Y follow the protocol then on the step, they will be able to agree on the coordinatewise min of their proposed feasible points with area .
If they're both really generous and their fairness curves don't intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.