I’d vote for removing the stage “developing some sort of polytime solution” and just calling 4 “developing a practical solution”. I think listing that extra step is coming from the perspective of something who’s more heavily involved in complexity classes. We’re usually interested in polynomial time algorithms because they’re usually practical, but there are lots of contexts where practicality doesn’t require a polynomial time algorithm, or really, where we’re just not working in a context where it’s natural to think in terms of algorithms with run-times.
Alex_Altair
Karma: 4,728
Thank you for writing this! Your description in the beginning about trying to read about the GRT and coming across a sequence of resources, each of which didn’t do quite what you wanted, is a precise description of the path I also followed. I gave up at the end, wishing that someone would write an explainer, and you have written exactly the explainer that I wanted!
Positive feedback, I am happy to see the comment karma arrows pointing up and down instead of left and right. I have some degree of left-right confusion and was always click and unclicking my comments votes to figure out which was up and down.
Also appreciate that the read time got put back into main posts.
(Comment font stuff looks totally fine to me, both before and after this change.)
[Some thoughts that are similar but different to my previous comment;]
I suspect you can often just prove the behavioral selection theorem and structural selection theorem in separate, almost independent steps.
Prove a behavioral theorem
add in a structural assumption
prove that behavioral result plus structural assumption implies structural result.
Behavior essentially serves as an “interface”, and a given behavior can be implemented by any number of different structures. So it would make sense that you need to prove something about structure separately (and that you can prove it for multiple different types of structural assumption).
Further claims: for any given structural class,
there will be a natural simplicity measure
simpler instances will be exponentially rare.
A structural class is something like programs, or Markov chains, or structural causal models. The point of specifying structure is to in some way model how the system might actually be shaped in real life. So it seems to me that any of these will be specified with a finite string over a finite alphabet. This comes with the natural simplicity measure of the length of the specification string, and there are exponentially fewer short strings than long ones.[1]
So let’s say you want to prove that your thing X which has behavior B has specific structure S. Since structure S has a fixed description length, you almost automatically know that it’s exponentially less likely for X to be one of the infinitely many structures with description length longer than S. (Something similar holds for being within delta of S) The remaining issue is whether there are any other secret structures that are shorter than S (or of similar length) that X could be instead.
- ^
Technically, you could have a subset of strings that didn’t grow exponentially. For example, you could, for some reason, decide to specify your Markov chains using only strings of zeros. That would grow linearly rather than exponentially. But this is clearly a less natural specification method.
For some reason the “only if” always throws me off. It reminds me of the
unlesskeyword in ruby, which is equivalent toif not, but somehow always made my brain segfault.
It’s maybe also worth saying that any other description method is a subset of programs (or is incomputable and therefore not what real-world AI systems are). So if the theoretical issues in AIT bother you, you can probably make a similar argument using a programming language with no while loop, or I dunno, finite MDPs whose probability distributions are Gaussian with finite parameter descriptions.
Yeah, I think structural selection theorems matter a lot, for reasons I discussed here.
This is also one reason why I continue to be excited about Algorithmic Information Theory. Computable functions are behavioral, but programs (= algorithms) are structural! The fact that programs can be expressed in the homogeneous language of finite binary strings gives a clear way to select for structure; just limit the length of your program. We even know exactly how this mathematical parameter translates into real-world systems, because we can know exactly how many bits our ML models take up on the hard drives.
And I think you can use algorithmic information distance to well-define just how close to agent-structured your policy is. First, define the specific program A that you mean to be maximally agent-structured (which I define as a utility-maximizing program). If your policy (as a program) can be described as “Program A, but different in ways X” then we have an upper bound for how close it is to agent-structured it is. X will be a program that tells you how to transform A into your policy, and that gives us a “distance” of at most the length of X in bits.
For a given length, almost no programs act anything like A. So if your policy is only slightly bigger than A, and it acts like A, then it’s probably of the form “A, but slightly different”, which means it’s agent-structured. (Unfortunately this argument needs like 200 pages of clarification.)
FWIW I think this would be a lot less like “tutoring” and a lot more like “paying people to tell you their opinions”. Which is a fine thing to want to do, but I just want to make sure you don’t think there’s any kind of objective curriculum that comprises AI alignment.
Nice! Yeah I’d be happy to chat about that, and also happy to get referrals of any other researchers who might be interested in receiving this funding to work on it.
Note to readers; it is an obligatory warning on any post like this that you should not run random scripts downloaded from the internet without reading them to see what they do, because there are many harmful things they could be doing.
<3!
Work with me on agent foundations: independent fellowship
FWIW I have used Perplexity twice since you mentioned it, it was somewhat helpful both times, but also, both times the citations had errors. By that I mean it would say something and then put a citation number next to it, but what it said was not in the cited document.
Aren’t they sick as hell???
Can confirm, these are sick as hell
I know that there’s something called the Lyapunov exponent. Could we “diminish the chaos” if we use logarithms, like with the Richter scale for earthquakes?
This is a neat question. I think the answer is no, and here’s my attempt to describe why.
The Lyapunov exponent measures the difference between the trajectories over time. If your system is the double pendulum, you need to be able to take two random states of the double pendulum and say how different they are. So it’s not like you’re measuring the speed, or the length, or something like that. And if you have this distance metric on the whole space of double-pendulum states, then you can’t “take the log” of all the distances at the same time (I think because that would break the triangle inequality).
It possesses this subjective element (what we consider to be negligible differences) that seems to undermine its standing as a legitimate mathematical discipline.
I think I see what you’re getting at here, but no, “chaotic” is a mathematical property that systems (of equations) either have or don’t have. The idea behind sensitive dependence on initial conditions is that any difference, no matter how small, will eventually lead to diverging trajectories. Since it will happen for arbitrarily small differences, it will definitely happen for whatever difference exists within our ability to make measurements. But the more precisely you measure, the longer it will take for the trajectories to diverge (which is what faul_sname is referring to).
The paper Gleick was referring to is this one, but it would be a lot of work to discern whether it was causal in getting telephone companies to do anything different. It sounds to me like the paper is saying that the particular telephone error data they were looking at could not be well-modeled as IID, nor could it be well-modeled as a standard Markov chain; instead, it was best modeled as a statistical fractal, which corresponds to a heavy-tailed distribution somehow.
Definitely on the order of “tens of hours”, but it’d be hard to say more specifically. Also, almost all of that time (at least for me) went into learning stuff that didn’t go into this post. Partly that’s because the project is broader than this post, and partly because I have my own research priority of understanding systems theory pretty well.
For what it’s worth, I think you’re getting downvoted in part because what you write seems to indicate that you didn’t read the post.
Isn’t it more like, the value of the sum of the things is greater than the sum of the value of each of the things? That is, f(a+b)>f(a)+f(b) (where perhaps f is a utility function). That seems totally normal and not-at-all at odds with Reductionism.