Intelligent Agent Foundations Forumsign up / log in
by Alex Mennen 150 days ago | Vadim Kosoy likes this | link | parent | on: Meta: IAFF vs LessWrong

There is a replacement for IIAF now: https://www.alignmentforum.org/

reply

by Jessica Taylor 149 days ago | Vadim Kosoy likes this | link

Apparently “You must be approved by an admin to comment on Alignment Forum”, how do I do this?

Also is this officially the successor to IAFF? If so it would be good to make that more clear on this website.

reply

by Alex Mennen 149 days ago | link

There should be a chat icon on the bottom-right of the screen on Alignment Forum that you can use to talk to the admins (unless only people who have already been approved can see this?). You can also comment on LW (Alignment Forum posts are automatically crossposted to LW), and ask the admins to make it show up on Alignment Forum afterwards.

reply


A related question is, whether it is possible to design an algorithm for strong AI based on simple mathematical principles, or whether any strong AI will inevitably be an enormous kludge of heuristics designed by trial and error. I think that we have some empirical support for the former, given that humans evolved to survive in a certain environment but succeeded to use their intelligence to solve problems in very different environments.

I don’t understand this claim. It seems to me that human brains appear to be “an enormous kludge of heuristics designed by trial and error”. Shouldn’t the success of humans be evidence for the latter?

reply

by Vadim Kosoy 160 days ago | link

The fact that the human brain was designed by trial and error is a given. However, we don’t really know how the brain works. It is possible that the brain contains a simple mathematical core, possibly implemented inefficiently and with bugs and surrounded by tonnes of legacy code, but nevertheless responsible for the broad applicability of human intelligence.

Consider the following two views (which might also admit some intermediates):

View A: There exists a simple mathematical algorithm M that corresponds to what we call “intelligence” and that allows solving any problem in some very broad natural domain \(D\).

View B: What we call intelligence is a collection of a large number of unrelated algorithms tailored to individual problems, and there is no “meta-algorithm” that produces them aside from relatively unsophisticated trial and error.

If View B is correct, then we expect that doing trial and error on a collection \(X\) of problems will produce an algorithm that solves problems in \(X\) and almost only in \(X\). The probability that you were optimizing for \(X\) but solved a much larger domain \(Y\) is vanishingly small: it is about the same as the probability of a completely random algorithm to solve all problems in \(Y \setminus X\).

If View A is correct, then we expect that doing trial and error on \(X\) has a non-negligible chance of producing M (since M is simple and therefore sampled with a relatively large probability), which would be able to solve all of \(D\).

So, the fact that homo sapiens evolved in a some prehistoric environment but was able to e.g. land on the moon should be surprising to everyone with View B but not surprising to those with View A.

reply

by Paul Christiano 158 days ago | link

I think the most plausible view is: what we call intelligence is a collection of a large number of algorithms and innovations each of which slightly increases effectiveness in a reasonably broad range of tasks.

To see why both view A and B seem strange to me, consider the analog for physical tasks. You could say that there is a simple core to human physical manipulation which allows us to solve any problem in some very broad natural domain. Or you could think that we just have a ton of tricks for particular manipulation tasks. But neither of those seems right, there is no simple core to the human body plan but at the same time it contains many features which are helpful across a broad range of tasks.

reply

by Vadim Kosoy 158 days ago | link

I think that your view is plausible enough, however, if we focus only on qualitative performance metrics (e.g. time complexity up to a polynomial, regret bound up to logarithmic factors), then this collection probably includes only a small number of innovations that are important.

reply

by Vadim Kosoy 152 days ago | link

Regarding the physical manipulation analogy: I think that there actually is a simple core to the human body plan. This core is, more or less: a spine, two arms with joints in the middle, two legs with joints in the middle, feet and arms with fingers. This is probably already enough to qualitatively solve more or less all physical manipulation problems humans can solve. All the nuances are needed to make it quantitatively more efficient and deal with the detailed properties of biological tissues, biological muscles et cetera (the latter might be considered analogous to the detailed properties of computational hardware and input/output channels for brains/AGIs).

reply


I think the asymptotic nature of LI is much more worrying than the things you compare it to. In order for an asymptotic result to be encouraging for practical applications, we need it to be an asymptotic result such that in most cases of interest when it holds, you tend to also have good finite results. If you give a \(O(n^{12})\) algorithm for some problem, this is an encouraging sign that maybe you can develop a practical algorithm. But if a problem is known not to be in \(P\), and then you give an exponential-time algorithm for it, and argue that it can probably be solved efficiently in practice because you’ve established an asymptotic bound, then no one will take this claim very seriously. It seems to me that this is roughly the position logical induction is in, but lifted from efficiency all the way up to computability.

The probabilities given by logical induction converge to coherent probabilities, but there is no computable function that will tell you how long you have to run logical induction to know the eventual probability of a certain sentence within a certain precision. We know logical induction doesn’t do this because it cannot be done; if it could be, then there would be a computable set containing all provable sentences and no disprovable sentences (since every sentence would eventually be shown either not to have probability 0 or not to have probability 1), but there is no such computable set. So we know for sure that in the naive sense, there is no way, even in principle, to run logical induction long enough that you have probabilities you can trust to be reasonably accurate. Maybe a better complexity theory analogy would be if you give a \(PP\) algorithm for a problem known not to be in \(BPP\) (although there would need to be exciting advancements in complexity theory before that could happen); this gives good reasons to believe that improvements to the algorithm would make it practical to run, and if you run it enough times the majority vote will probably be correct, but it will never be practical to run it enough times for that to happen. Likewise, efficient approximations to logical induction should be able to complete each step in a reasonable amount of time, but will not be able to complete enough steps to give you accurate probabilities.

In order to take the probabilities given by logical induction at very large finite steps seriously, you would need effective asymptotic results, and since this cannot be done for the probabilities converging to coherent probabilities, there would need to be subtler senses in which the probabilities given at finite times can be taken seriously even if they are not close to the limiting probabilities. Now, the logical induction paper does give interesting subtler senses in which the probabilities given by logical induction can be taken seriously before they approach their limiting values, but the fundamental problem is that all of those results say that some pattern will eventually hold, for the same sense of “eventually” in which the probabilities eventually converge to coherent probabilities, so this does not give strong evidence that those desirable patterns can be made to emerge in any reasonable amount of time.

reply

by Vadim Kosoy 521 days ago | Alex Mennen likes this | link

Alex, the difference between your point of view and my own, is that I don’t care that much about the applications of LI to formal logic. I’m much more interested in its applications to forecasting. If the author is worried about the same issues as you, IMO it is not very clear from ’eir essay. On the other hand, the original paper doesn’t talk much about applications outside of formal logic, and my countercriticism might be slightly unfair since it’s grounded in a perspective that the author doesn’t know about.

reply

by Tarn Somervell Fletcher 520 days ago | link

Clarification: I’m not the author of the linked post, I’m just linking it here on behalf of the author (who objects to signing up for things with facebook). I found the most interesting part to be the observation about pointwise convergence - because the LI framework proves its results pointwise, it cannot guarantee that each result which is proved about P_infty will obtain for any finite time n; see also his example about preemptive learning, where for an infinite set of e.c sequences, there may be no finite n that works for all of the set.

reply

by Vadim Kosoy 520 days ago | link

Replying to “240”

First, yes, the convergence property is not uniform, but it neither should nor can be uniform. This is completely analogous to usual Bayesian inference where the speed of convergence depends on the probability of the correct hypothesis within the prior, or to the Structural Risk Minimization principle in PAC learning. This is unavoidable: if two models only start to differ at a very late point in time, there no way to distinguish between them before this point. In particular, human brains have the same limitation: it would take you more time to notice a complex pattern than a simple pattern.

Second, of course we can and should work on results about convergence rates, it is just that there is only that much ground you can reasonably cover in one paper. For example, the classical paper on merging of opinions by Blackwell and Dubins also doesn’t analyze convergence rates, and nevertheless it has 500+ citations. To make one concrete guess, if we consider a sequence of observations in \(\{0,1\}\) and look at the deviation between the probability the incomplete model forecaster assigns to the next observation and the probability interval that follows from a given correct incomplete model, then I expect to have some sort of cumulative bound on these deviations analogous to standard regret bounds in online learning. Of course the bound will include some parameter related to the “prior probability” \(\xi(k)\).

Third, the only reason the sum in equation (31) is finite is because I wanted to state Theorem 2 in greater generality, without requiring the gamblers to be bounded. However, the gamblers that I actually use (see section 5) are bounded, so for this purpose I might as well have taken an infinite sum over all gamblers.

reply

by Vadim Kosoy 520 days ago | link

Replying to 240 (I can’t reply directly because of some quirk of the forum).

(I’m not sure that I know your name, is it Robert?)

I’m actually not interested in discussing the verbal arguments in the paper. Who reads the verbal arguments anyway? I go straight for the equations ;) The verbal arguments might or might not misrepresent the results, I don’t care either way.

I am interested in discussing the mathematical content of the LI paper and whether LI is a valuable mathematical discovery.

I agree that there is a relevant sense in which the dominance property in itself is too weak. The way I see it, LI (more generally, dominant forecasting, since I don’t care much about the application to formal logic in particular) is a generalization of Bayesian inference, and the dominance property is roughly analogous to merging of opinions (in my paper there is a more precise analogy, but it doesn’t matter). In the Bayesian case, we can also say that merging of opinions is a too weak property in itself. However:

  • Proving this weak property is already non-trivial, so it is a valuable and necessary step towards proving stronger properties.

  • Besides the property, we have an actual construction and I expect this construction to have stronger properties (even though I don’t expect it to be a practical algorithm), like Bayesian inference has stronger properties than just merging of opinions.

Now, nobody currently has a proof of stronger properties or even a formulation (I think), but IMO this is not a reason to disregard all work done so far. Rome wasn’t built in a day :)

reply

by Vadim Kosoy 519 days ago | Alex Appel likes this | link

Replying to Rob.

Actually, I do know a stronger property of LI / dominant forecasting. In the notation of my paper, we have the following:

Let \(\{G^k\}\) be a family of gamblers, \(\xi,\zeta\) probability distributions supported on \(\mathbb{N}\). Then, there exists a forecaster \(F\) s.t. for any \(k,m,b \in \mathbb{N}\) (\(b > 0\)) and \(x \in \mathcal{O}^\omega\), if the first condition holds then the second condition holds:

\[\inf_{n \leq m} {\operatorname{\Sigma V}_\min G^{kF}_{n}(x_{:n-1})} > -b\]

\[\sup_{n \leq m} {\operatorname{\Sigma V}_\max G^{kF}_{n}(x_{:n-1})} \leq \frac{\sum_{j,c} \xi(j) \zeta(c) c}{\xi(k)\sum_{c > b} \zeta(c)}\]

The above is not hard to see from the proof of Theorem 2, if you keep track of the finite terms. Now, this is not really a bound on the time of convergence, it is something like a bound on the number of mistakes made, which is completely analogous to standard guarantees in online learning.

If you’re running LIA and stop enumerating traders at \(N\), you will get the same dominance property, only for traders up to \(N\).

The fact that VC dimension is non-decreasing for a family of nested classes is a tautology. There is nothing special about the order of the hypotheses in SRM: the order (and weighting) of hypotheses is external information that reflects your prior about the correct hypothesis. Similarly, in LIA we can order the traders by description complexity, same as in Solomonoff induction, because we expect simpler patterns to be more important than complex patterns. This is nothing but the usual Occam’s razor. Or, we can consider more specialized dominant forecasting, with gamblers and ordering selected according to domain-specific considerations.

reply

by Vadim Kosoy 518 days ago | link

Replying to Rob.

I don’t think that stopping at \(N\) does some kind of “disproportionate” damage to the LI. For example, Theorem 4.2.1 in the LI paper requires one trader per each \(\epsilon > 0\) and sequence of theorems. If this trader is in the selection, then the probabilities of the theorems will converge to 1 within \(\epsilon\). Similarly, in my paper you need the gambler \(\Gamma S^{Mk}\) to ensure your forecaster converges to incomplete model \(M\) within \(1/k\).

You can do SRM for any sequence of nested classes of finite VC dimension. For example, if you have a countable set of hypotheses \(\{h_n\}\), you can take classes to be \(H_n:=\{h_m\}_{m < n}\). This is just as arbitrary as in LI. The thing is, the error bound that SRM satisfies depends on the actual class in which the reference hypothesis lies. So, compared to a hypothesis in a very high class, SRM can converge very slowly (require very large sample size). This is completely analogous to the inequality I gave before, where \(\xi(k)\) appears in the denominator of the bound, so gamblers that are “far away” in the “prior” can win a lot of bets before the forecaster catches up. SRM is useful iff you a priori expect “low” hypotheses to be good approximations. For example, suppose you want to fit a polynomial to some data but you don’t know what degree to use. SRM gives you a rule that determines the degree automatically, from the data itself. However, the reason this rule has good performance is because we expect most functions in the real world to be relatively “smooth” and therefore well-approximable by a low degree polynomial.

Ordering by description complexity is perfectly computable in itself, it just means that we fix a UTM, represent traders by programs (on which we impose a time bound, otherwise it really is uncomputable), and weight each trader by 2^{-program length}. It would be interesting to find some good property this thing has. If we don’t impose a time bound (so we are uncomputable), then the Bayesian analogue is Solomonoff induction, which has the nice property that it only “weakly” depends on the choice of UTM. Will different UTMs gives “similar” LIs? Off the top of my head, I have no idea! When we add the time bound it gets more messy since time is affected by translation between UTMs, so I’m not sure how to formulate an “invariance” property even in the Bayesian case. Looking through Schmidhuber’s paper on the speed prior, I see ey do have some kind of invariance (section 4) but I’m too lazy to understand the details right now.

reply


I think the general principle you’re taking advantage of is:

Do a small amount of very predictable reasoning in PA+Sound(PA). Then use PA for the rest of the reasoning you have to do. When reasoning about other instances of agents similar to you, simulate their use of Sound(PA), and trust the reasoning that they did while confining themselves to PA.

In your example, PA+Con(PA) sufficed, but PA+Sound(PA) is more flexible in general, in ways that might be important. This also seems to solve the closely related problem of how to trust statements if you know they were proven by an agent that reasons approximately the same way you do, for instance, statements proven by yourself in the past. If you proved X in the past, and you want to establish that that makes X true, you fully simulate everything your past self could have done in PA+Sound(PA)-mode before confining itself to PA, and then you can just trust that the reasoning you did afterwards in PA-mode was correct, so you don’t have to redo that part.

This also might allow for an agent to make improvements in its own source code and still trust its future self, provided that the modification that it makes still only uses Sound(PA) in ways that it can predict and simulate. On the other hand, that condition might be a serious limitation to recursive self-improvement, since the successor agent would need to use Sound(PA) in order to pick its successor agent, and it can’t do so in ways that the predecessor agent can’t predict.

Perhaps it could be worse than that, and attempting to do anything nontrivial with this trick leads to a combinatorial explosion from every instance of the agent trying to simulate every other instance’s uses of Sound(PA). But I’m cautiously optimistic that it isn’t quite that bad, since simply simulating an agent invoking Sound(PA) does not itself require you to invoke Sound(PA) yourself, so these simulations can be run in PA-mode, and only the decision to run them needs to be made in PA+Sound(PA)-mode.

reply


This notion of dependency seems too binary to me. Concretely, let’s modify your example from the beginning so that \(P_3\) must grant an extra \(10^{-10}\) utility to either \(P_1\) or \(P_2\), and gets to decide which. Now, everyone’s utility depends on everyone’s actions, and the game is still zero-sum, so again, so any strategy profile with \(p=q\) will be a stratified Pareto optimum. But it seems like \(P_1\) and \(P_2\) should ignore still ignore \(P_3\).

reply

by Scott Garrabrant 553 days ago | link

I agree with this. I think that the most interesting direction of future work is to figure out how to have better notions of dependency. I plan on writing some on this in the future, but basically we have not successfully figured out how to deal with this.

reply

by Alex Mennen 554 days ago | link | parent | on: Futarchy Fix

When modeling the incentives to change probabilities of events, it probably makes sense to model the payoff of changing probabilities of events and the cost of changing probabilities of events separately. You’d expect someone to alter the probabilities if they gain more in expectation from the bets than the cost to them of altering the probabilities. If someone bets on an event and changes the probability that it occurs from \(p\) to \(q\), then their expected payoff is \(\frac{q}{p}-1\) times their investment, so if, in a prediction market in which there are \(n\) possible outcomes, the expected payoff you can get from changing the probability distribution from \((p_1,...,p_n)\) to \((q_1,...,q_n)\) is proportional to \(\max_i(\frac{q_i}{p_i})-1\).

Modeling the cost of changing a probability distribution seems harder to model, but the Fisher information metric might be a good crude estimate of how difficult you should expect it to be to change the probability distribution over outcomes from one distribution to another.

reply


This comment is to explain partial results obtained by David Simmons in this thread, since the results and their proofs are difficult to follow as a result of being distributed across multiple comments, with many errors and corrections. The proofs given here are due to David Simmons.

Statements

Theorem 1: There is no metric space \(X\) and uniformly continuous function \(f:X\times X\rightarrow[0,1]\) such that every uniformly continuous function \(X\rightarrow[0,1]\) is a fiber of \(f\).

Theorem 2: There is no metric space \(X\) and function \(f:X\times X\rightarrow[0,1]\) that is uniformly continuous on bounded sets, such that every function \(X\rightarrow[0,1]\) which is uniformly continuous on bounded sets is a fiber of \(f\).

Theorem 3: There is no locally compact Polish space \(X\) and continuous function \(f:X\times X\rightarrow[0,1]\) such that every continuous function \(X\rightarrow[0,1]\) is a fiber of \(f\).

Commentary

Theorem 1 says that there is no solution to the version of Scott’s problem with continuity in topological spaces replaced with uniform continuity in metric spaces. A plausible reason that this version of the problem might be important is that if an agent has to be able to compute what its policy says to do to any desired precision using an amount of computational resources that does not depend on the input, then its policy must be uniformly continuous. The gist of the proof is that for any uniformly continuous \(f:X\times X\rightarrow[0,1]\), it is possible to construct a uniformly continuous function \(g:X\rightarrow[0,1]\) that requires greater precision in its input than \(f\) does to determine the output to any desired precision. I suspect it might be possible to adapt the proof to work in uniform spaces rather than just metric spaces, but I have not studied uniform spaces.

Theorem 2 is similar to theorem 1, but with uniform continuity replaced with uniform continuity on bounded subsets. I was not convinced that this is an important notion in its own right, but theorem 2 is useful as a lemma for theorem 3. See the thread under David Simmons’s comment for more discussion about what sort of continuity assumption is appropriate. The gist of the proof is to apply the proof of theorem 1 on a bounded set. The function \(g\) constructed will be uniformly continuous everywhere, so the proof actually shows a stronger result that unifies both theorems 1 and 2: there is no \(f:X\times X\rightarrow[0,1]\) that is uniformly continuous on bounded sets and admits every uniformly continuous function \(X\rightarrow[0,1]\) as a fiber.

Theorem 3 almost says that Scott’s problem cannot be solved with Polish spaces. It doesn’t quite say that, because there are Polish spaces that are not locally compact. However, non-locally-compact Polish spaces are not exponentiable, so in the version of the problem in which we want a surjection \(X\rightarrow[0,1]^X\), it isn’t even clear whether there exists an exponential object \([0,1]^X\), which may mean that non-exponentiable spaces are not promising, although I’m not sure. A reason to restrict attention to Polish spaces is that effective Polish spaces provide a topological setting in which there is a good notion of computability, so the nonexistence of a solution in Polish spaces would make it impossible to provide a computable solution in that sense. That said, there may be other notions of computability in topological spaces (domain theory?), which I am unfamiliar with. The gist of the proof is to find a metric in which bounded sets are compact, and apply theorem 2.

Proofs

Proof of theorem 1: Let \(X\) be a metric space, and \(f:X\times X\rightarrow[0,1]\) be uniformly continuous. If \(X\) is uniformly discrete, then all functions from \(X\) are uniformly continuous, so there is a uniformly continuous function \(X\rightarrow[0,1]\) that is not a fiber of \(f\) by Cantor’s theorem.

So assume that \(X\) is not uniformly discrete. Let \((x_n,y_n)_{n\in\mathbb{N}}\) be such that \(\forall k\) \(d(x_{k+1},y_{k+1})\leq\frac{1}{6}d(x_k,y_k)\). Note that for all \(k\) and \(\ell>k\), either (A) \(d(x_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)\) and \(d(x_k,x_\ell)\geq\frac{1}{3}d(x_k,y_k)\) or (B) \(d(y_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)\) and \(d(y_k,x_\ell)\geq\frac{1}{3}d(x_k,y_k)\). By extracting a subsequence we can assume that which of (A) or (B) holds depends only on \(k\) and not on \(\ell\). By swapping \(x_k\) and \(y_k\) if necessary we can assume that case (A) always holds.

For each \(z\) there is at most one \(k\) such that \(d(z,x_k)<\frac{1}{6}d(x_k,y_k)\), because if \(d(z,x_k)<\frac{1}{6}d(x_k,y_k)\) and \(d(z,x_\ell)<\frac{1}{6}d(x_\ell,y_\ell)\) with \(\ell>k\), then \(d(x_k,x_\ell)<\frac{1}{3}d(x_k,y_k)\), a contradiction.

It follows that by extracting a further subsequence we can assume that \(d(y_k,x_\ell)\geq\frac{1}{6}d(x_\ell,y_\ell)\) for all \(\ell>k\).

Since \(f\) is uniformly continuous, there is a function \(\delta:(0,\infty)\rightarrow(0,\infty)\) such that \(\forall\varepsilon>0\;d((u,v),(w,z))<\delta(\varepsilon)\rightarrow|f(u,v)-f(w,z)|<\varepsilon\). By extracting a further subsequence, we can assume that \(d(x_k,y_k)<\delta(2^{-k})\) for all \(k\). Let \(j:[0,\infty)\rightarrow[0,\infty)\) be an increasing uniformly continuous function such that \(j(0)=0\) and \(j(\frac{1}{6}d(x_k,y_k))>2^{-k}\) for all \(k\). Finally, let \(g(z):=\inf_kd(z,y_k)\). Then for all \(k\) we have \(g(y_k)=0\). On the other hand, for all \(\ell>k\) we have \(d(x_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)\), for \(\ell=k\) we have \(d(x_k,y_\ell)=d(x_k,y_k)\), and for \(\ell<k\) we have \(d(x_k,y_\ell)\geq\frac{1}{6}d(x_k,y_k)\). Thus \(g(x_k)=\inf_\ell j(d(x_k,y_\ell))\geq j(\frac{1}{6}d(x_k,y_k))>2^{-k}\). Clearly, \(g\) cannot be a fiber of \(f\). Moreover, since the functions \(j\) and \(z\mapsto\inf_kd(z,y_k)\) are both uniformly continuous, so is \(g\). \(\square\)

Proof of theorem 2: Let \(X\) be a metric space, and \(f:X\times X\rightarrow[0,1]\) be uniformly continuous on bounded sets. If all bounded subsets of \(X\) are uniformly discrete, then all functions from \(X\) are uniformly continuous on bounded sets, so there is a function \(X\rightarrow[0,1]\) that is uniformly continuous on bounded sets but not a fiber of \(f\) by Cantor’s theorem. Otherwise, let \(B\subseteq X\) be a bounded set that is not uniformly discrete, take a sequence \((x_n,y_n)_{n\in\mathbb{N}}\) in \(B\) as in the proof of theorem 1, and a function \(\delta:(0,\infty)\rightarrow(0,\infty)\) such that \(\forall\varepsilon>0\;d((u,v),(w,z))<\delta(\varepsilon)\rightarrow|f(u,v)-f(w,z)|<\varepsilon\) for \((u,v),(w,z)\in B\times B\), and define \(j\) and \(g\) as in the proof of theorem 1. \(g\) is uniformly continuous, but not a fiber of \(f\). \(\square\)

Proof of theorem 3: Let \(d\) be a metric for \(X\). Let \(f(x):=\sup\{r|B(x,r)\text{ is compact}\}\), where \(B(x,r)\) is the closed ball around \(x\) of radius \(r\). Let \(F(x,y):=f(x)/[f(x)-d(x,y)]\) if \(f(x)>d(x,y)\), and \(F(x,y):=\infty\) otherwise. Next, let \(g(y):=\min_n[n+F(x_n,y)]\), where \((x_n)_{n\in\mathbb{N}}\) enumerates a countable dense set. Then \(g\) is continuous and everywhere finite. \(g^{-1}([0,N])\subseteq\bigcup_{n\leq N}B(x_n,(1-\frac{1}{N})f(x_n))\), and is thus compact. It follows that with the metric \(d'(x,y):=d(x,y)+|g(y)-g(x)|\), which induces the same topology, bounded sets are compact. Thus theorem 3 follows from theorem 2 applied to \((X,d')\). \(\square\)

reply


You talk like \(p\) is countably supported, but everything you’ve said generalizes to arbitrary probability measures \(p\) over \(S\), if you replace “for all \(u\) assigned nonzero probability by \(p\)” with “for all \(u\) in some set assigned probability \(1\) by \(p\)”.

If you endow \(\mathbb{U}\) with the quotient topology from \(\mathbb{R^S}/\sim\), then the only open set containing \(0\) is all of \(\mathbb{U}\). This is a funny-looking topology, but I think it is ultimately the best one to use. With this topology, every function to \(\mathbb{U}\) is continuous at any point that maps to \(0\). As a consequence, the assumption “if \(f(\mathbb{S},p)\in S\)” in the continuity axiom is unnecessary. More importantly, what topology on the space of probability distributions did you have in mind? Probably the weak topology?

I find independence of irrelevant alternatives more compelling than symmetry, but as long as we’re accepting symmetry instead, it probably makes sense to strengthen the assumption to isomorphism-invariance: If \(\rho:\mathbb{S}_1\rightarrow\mathbb{S}_2\) is a bijection, then \(f(\mathbb{S}_2,p)\circ\rho=f(\mathbb{S}_1,p\circ\rho)\).

The relevance axioms section is riddled with type errors. \(u(s)=u(\sigma(s))\) only makes sense if \(\mathbb{S}=\mathbb{S}_{\neg X}\sqcup\mathbb{S}_{X}\), which would make sense if \(\mathbb{S}\) represented a space of outcomes rather than a space of strategies (which seems to me to be a more natural space to pay attention to anyway), or if \(X\) is fully under the agent’s control, whereas \(\mathbb{S}=\mathbb{S}_{\neg X}\times\mathbb{S}_{X}\) makes sense if \(X\) is fully observable to the agent. If \(X\) is neither fully under the agent’s control nor fully observable to the agent, then I don’t think either of these make sense. If we’re using \(\times\) instead of \(\sqcup\), then formalizing irrelevance seems trickier. The best I can come up with is that \(p\) is supported on \(u\) of the form \(u(s,t)=(1-q)\tilde{u}(\sigma(s))+q\tilde{u}(t)\), where \(q\) is the probability of \(X\). The weak and strong irrelevance axioms also contain type errors, since the types of the output and second input of \(f\) depend on its first input, though this can probably be fixed.

I didn’t understand any of the full theory section, so if any of that was important, it was too brief.

reply

by Stuart Armstrong 590 days ago | link

Yes to your two initial points; I wanted to keep the exposition relatively simple.

Do you disagree with the reasoning presented in the picture-proof? That seems a simple argument against IIA. Isomorphism invariance makes sense, but I wanted to emphasise the inner structure of \(\mathbb{S}\).

Updated the irrelevance section to clarify that \(X\) is fully observed and happens before the agent takes any actions, and that \(u(s)\) should be read as \(u(s|\neg X)\).

The full theory section is to write up some old ideas, to show that the previous axioms are not set in stone but that other approaches are possible and were considered.

reply

by Alex Mennen 590 days ago | link

Your picture proof looks correct, but it relies on symmetry, and I was saying that I prefer IIA instead of symmetry. I’m not particularly confident in my endorsement of IIA, but I am fairly confident in my non-endorsement of symmetry. In real situations, strategies/outcomes have a significant amount of internal structure which seems relevant and is not preserved by arbitrary permutations.

You’ve just replaced a type error with another type error. Elements of \(\mathbb{U}\) are just (equivalence classes of) functions \(\mathbb{S}\rightarrow\mathbb{R}\). Conditioning like that isn’t a supported operation.

reply

by Stuart Armstrong 587 days ago | link

Ok, I chose the picture proof because it was a particularly simple example of symmetry. What kind of internal structure are you thinking of?

reply

by Alex Mennen 586 days ago | link

For strategies: This ties back in to the situation where there’s an observable event \(X\) that you can condition your strategy on, and the strategy space has a product structure \(\mathbb{S}=\mathbb{S}_X\times\mathbb{S}_{\neg X}\). This product structure seems important, since you should generally expect utility functions \(u\) to factor in the sense that \(u(s,t)=qu_X(s)+(1-q)u_{\neg X}(t)\) for some functions \(u_X\) and \(u_{\neg X}\), where \(q\) is the probability of \(X\) (I think for the relevance section, you want to assume that whenever there is such a product structure, \(p\) is supported on utility functions that factor, and you can define conditional utility for such functions). Arbitrary permutations of \(\mathbb{S}\) that do not preserve the product structure don’t seem like true symmetries, and I don’t think it should be expected that an aggregation rule should be invariant under them. In the real world, there are many observations that people can and do take into account when deciding what to do, so a good model of strategy-space should have a very rich structure.

For outcomes, which is what utility functions should be defined on anyway: Outcomes differ in terms of how achievable they are. I have an intuition that if an outcome is impossible, then removing it from the model shouldn’t have much effect. Like, you shouldn’t be able to rig the aggregator function in favor of moral theory 1 as opposed to moral theory 2 by having the model take into account all the possible outcomes that could realistically be achieved, and also a bunch of impossible outcomes that theory 2 thinks are either really good or really bad, and theory 1 thinks are close to neutral. A natural counter-argument is that before you know which outcomes are impossible, any Pareto-optimal way of aggregating your possible preference functions must not change based on what turns out to be achievable; I’ll have to think about that more. Also, approximate symmetries between peoples’ preferences seem relevant to interpersonal utility comparison in practice, in the sense that two peoples’ preferences tend to look fairly similar to each other in structure, but with each person’s utility function centered largely around what happens to themselves instead of the other person, and this seems to help us make comparisons of the form “the difference between outcomes 1 and 2 is more important for person A than for person B”; I’m not sure if this way of describing it is making sense.

reply

by Stuart Armstrong 586 days ago | link

I think I’ve got something that works; I’ll post it tomorrow.

reply

by Stuart Armstrong 585 days ago | link

OK, got a better formalism: https://agentfoundations.org/item?id=1449

reply

by Stuart Armstrong 587 days ago | link

You’re right. I’ve drawn the set of utility functions too broadly. I’ll attempt to fix this in the post.

reply


\(g\) can be a fiber of \(f\), since for each \(n\), \(x_n\) and \(y_n\) could be distance greater than \(n\) from the basepoint.

Example: let \(X:=\{x_n,y_n|n\in\mathbb{N}\}\), with \(d(x_n,x_m)=d(y_n,y_m)=d(x_n,y_m)=2|n-m|\) for \(n\neq m\) and \(d(x_n,y_n)=6^{-n}\). Let \(x_0\) be the basepoint (so that \((x_0,x_0)\) is the point you were calling “\(0\)”). Let \(g(x_n):=0\), \(g(y_n):=1\), \(f(z,w):=g(z)\), and \(h_n(r):=3^nr\).

I also don’t see how to even construct the function \(g\), or, relatedly, what you mean by “geometrically nicely”, but I guess it doesn’t matter.

Also, I’m not convinced that metric spaces with uniform continuity on bounded subsets is a better framework than topological spaces with continuity.

reply

by Alex Mennen 594 days ago | link

This is intended as a reply to David Simmons’s comment, which for some reason I can’t reply to directly.

In the new version of your proof, how do we know \(Y_k\) isn’t too close to \(X_l\) for some \(l>k\)? And how do we know that \(g\) is uniformly continuous on bounded subsets?

About continuity versus uniform continuity on bounded sets:

It seems to me that your point 1 is just a pithier version of your point 4, and that these points support paying attention to uniform continuity, rather than uniform continuity restricted to bounded sets. This version of the problem seems like it would be a less messy version of the “fixed modulus of continuity” version of the problem you mentioned (which I did not understand your solution to, but will look again later).

I’m not sure what you’re getting at about singularities in point 3. I wouldn’t have asked why you were considering uniform continuity on bounded sets instead of uniform continuity away from singularities (in fact, I don’t know what that means). I would ask, though, why uniform continuity on bounded sets instead of uniform continuity on compact sets? As you point out, the latter is the same as continuity.

Your point 2 is completely wrong, and in fact this is the primary reason I was convinced that continuity is a better thing to pay attention to than uniform continuity on bounded sets. The type of object you are describing is an effective Polish space that remembers its metric. Typically, descriptive set theorists forget the metric, and the isomorphisms between Polish spaces are homeomorphisms (and the isomorphisms between effective Polish spaces are computable homeomorphisms). Changing the metric in a computably homeomorphic way does not change what can be done when points are represented as descending chains of basic open sets with singleton intersection. So the thing you described was really topological rather than metric in nature, even though it involves introducing a metric in the setup. I am not aware of any notions of computability in metric spaces in which the metric matters in the way you are suggesting. It is not true that uniform continuity gives you an algorithm for computing the function. As a counterexample, let \(a\) be an uncomputable number, and let \(f:\mathbb{R}\rightarrow\mathbb{R}\) be given by \(f(x)=a\) for every \(x\). \(f\) is clearly uniformly continuous, but not computable. It is also not true that uniform continuity is necessary in order for the function to be computable. For instance, \(\sin(1/x)\) is computable on \((0,1]\). Of course, \((0,1]\) is not complete, but for another example, consider an effective infinite-dimensional Hilbert space, and let \(\{e_n|n\in\mathbb{N}\}\) be an effective orthonormal basis. Let \(f_n(x):=\max(0,\frac{1}{2}-\Vert x-e_n\Vert)\). This sequence of functions is computable, they have disjoint support, and for any point, a sufficiently small neighborhood around it will be disjoint from the supports of all but at most one of these functions. Thus \(f(x):=\sum_n nf_n(x)\) is computable, but of course it is not uniformly continuous on the unit ball, which is bounded. However, it is true that every computable function is continuous, and conversely, every continuous function is computable with respect to some oracle. Of course, we really want computability, not computability with respect to some oracle, but this still seems to show that continuity is at least a good metaphor for computability, whereas uniform continuity on bounded sets doesn’t seem so to me.

Of course, all this about continuity as a metaphor for computability makes the most sense in the context of Polish spaces, and we can only talk about actual computability in the context of effective Polish spaces. Scott’s problem involves a space \(X\) and the exponential \([0,1]^X\). If \(X\) is a locally compact Polish space, then \([0,1]^X\) is also Polish. I think that this might be necessary (that is, if \(X\) and \([0,1]^X\) are Polish, then \(X\) is locally compact), although I’m not sure. If so, and if your proof is correct, it seems plausible that your proof could be adapted to show that there is no locally compact Polish space with the property that Scott was looking for, and that would show that there is no solution to the problem in which \(X\) and \([0,1]^X\) are both Polish spaces, and hence no computable solution, if computability is formalized as in effective descriptive set theory.

reply


I haven’t checked that argument carefully, but that sounds like it should give you \(X'\) with a continuous bijection \(\phi:X'\rightarrow[0,1]^{X'}\), which might not necessarily be a homeomorphism.

reply

by Stuart Armstrong 615 days ago | link

Yes, you’re right.

reply

Older

NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

[Note: This comment is three
by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

RSS

Privacy & Terms