The example seems to be that a using a Turing machine to generate your priors somehow results in an expectation of p(uncomputable universe)=0. That idea just seems like total nonsense to me. It just doesn’t follow. For all I care, my priors could have been assigned to me using a Turing machine model at birth—but I don’t think p(uncomputable universe)=0. The whole line of reasoning apparently makes no sense.
Priors are probabality estimates for uncertain quantities.
In Solomonoff induction they are probabality estimates for bitstrings—which one can think of as representing possible sensory inputs for an agent.
With a standard TM_length-based encoding, no finite bitstring is assigned a zero probability—and we won’t have to worry about perceiving infinite bitstrings until after the universal heat death—so there is no problem with assigning certain bitstrings a zero prior probability.
Whether the bitstrings were created using uncomputable physics is neither here nor there. They are still just bitstrings—and so can be output by a TM with a finite program on its tape.
No, sorry. You’re confused. A prior is not an assignment of credences to all bitstrings that you can observe. A prior is an assignment of credences to hypotheses, i.e. possible states of the world that generate bitstrings that you observe. Otherwise you’d find yourself in this text (see part II, “Escaping the Greek Hinterland”).
No. We were talking about the universal prior. Here is how that is defined for sequences:
“The universal prior probability of any prefix p of a computable sequence x is the sum of the probabilities of all programs (for a universal computer) that compute something starting with p.”
The universal prior of a sequence is the probability of that particular sequence arising (as a prefix). It is not the probabilty of any particular hypothesis or program. Rather is a weighted sum of the probabilities of all the programs that generate that sequence.
You can talk about the probabilities of hypothesis and programs as well if you like—but the universal prior of a sequence is perfectly acceptable subject matter—and is not a “confused” idea.
No finite sequence has a probabilty of zero—according to the universal prior.
All finite bitstrings can be produced by computable means—even if they were generated as the output of an uncomputable physical process.
Is this misconception really where this whole idea arises from?
This is all true, but… Why do you think the universal prior talks about computer programs at all? If I only wanted a prior over all finite bitstrings, I’d use a simpler prior that assigned every string of length N a credence proportional to 2^-N. Except that prior has a rather major shortcoming: it doesn’t help you predict the future! No matter how many bits you feed it, it always says the next bit is going to be either 0 or 1 with probability 50%. It will never get “swamped” by the data, never gravitate to any conclusions. This is why we want the universal prior to be based on computer programs instead: it will work better in practice, if the universe is in fact computable. But what happens if the universe is uncomputable? That’s the substantive question here.
ETA: the last two sentences are wrong, disregard them.
Nothing much happens to intelligent agents—because an intelligent agents’ original priors mostly get left behind shortly after they are born—and get replaced by evidence-based probability estimates of events happening. If convincing evidence comes in that the world is uncomputable, that just adds to the enormous existing stack of evidence they have about the actual frequencies of things.
Anyhow, priors being set to 0 or 1 is not a problem for observable sense data. No finite sense data has p assigned to 0 or 1 under the universal prior—so an agent can always update successfully—if it gets sufficient evidence that a sequence was actually produced. So, if it sees a system that apparently solves the halting problem for arbitrary programs, that is no big deal for it. It may have found a Turing oracle! Cool!
I suppose it might be possible to build an semi-intelligent agent with a particular set of priors permanently wired into it—so the agent was incapable of learning and adapting if its environment changed. Organic intelligent agents are not much like that—and I am not sure how easy it would be to build such a thing. Such agents would be incapable of adapting to an uncomputable world. They would always make bad guesses about uncomputable events. However, this seems speculative—I don’t see why people would try to create such agents. They would do very badly in certain simulated worlds—where Occam’s razor doesn’t necessarily hold true—and it would be debatable whether their intelligence was really very “general”.
The reason the universal prior is called “universal” is because given initial segments, where the infinite strings come from any computable distribution, and updating on those samples, it will, in fact, converge to the actual distribution on what the next bit should be. Now I’ll admit to not actually knowing the math here, but it seems to me that if most any prior had that property, as you seem to imply, we wouldn’t need to talk about a universal prior in the first place, no?
Also, if we interpret “universe” as “the actual infinite string that these segments are initial segments” of, then, well… take a look at that sum you posted and decompose it. The universal prior is basically assigning a probability to each infinite string, namely the sum of the probabilities of programs that generate it, and then collapsing that down to a distribution on initial segments in the obvious way. So if we want to consider its hypotheses about the actual law of the universe, the whole string, it will always assign 0 probability to an uncomputable sequence.
Convergence is more the result of the updates than the original prior. All the initial prior has to be to result in convergence is not completely ridiculous (1, 0, infinitessimals, etc). The idea of a good prior is that it helps initially, before an agent has any relevant experience to go on. However, that doesn’t usually last for very long—real organic agents are pretty quickly flooded with information about the state of the universe, and are then typically in a much better position to make probabililty estimates. You could build agents that were very confident in their priors—and updated them slowly—but only rarely would you want an agent that was handicapped in its ability to adapt and learn.
Picking the best reference machine would be nice—but I think most people understand that for most practical applications, it doesn’t matter—and that even a TM will do.
Convergence is more the result of the updates than the original prior. All the initial prior has to be to result in convergence is not completely ridiculous (1, 0, infinitessimals, etc).
Are you certain of this? Could you provide some sort of proof or reference, please, ideally together with some formalization of what you mean by “completely ridiculous”? I’ll admit to not having looked up a proof of convergence for the universal prior or worked it out myself, but what you say were really the case, there wouldn’t actually be be very much special about the universal prior, and this convergence property of it wouldn’t be worth pointing out—so I think I have good reason to be highly skeptical of what you suggest.
However, that doesn’t usually last for very long—real organic agents are pretty quickly flooded with information about the state of the universe, and are then typically in a much better position to make probabililty estimates.
Better, yes. But good enough? Arbitrarily close?
You could build agents that were very confident in their priors—and updated them slowly—but only rarely would you want an agent that was handicapped in its ability to adapt and learn.
Sorry, but what does this even mean? I don’t understand how this notion of “update speed” translates into the Bayesian setting.
Here’s Shane Legg on the topic of how little priors matter when predicting the environment:
“In some situations, for example with Solomonoff induction, the choice of the reference machine doesn’t matter too much. [...] the choice of reference machine really doesn’t matter except for very small data sets (which aren’t really the ones we’re interested in here). To see this, have a look at the Solomonoff convergence bound and drop a compiler constant in by the complexity of the environment. The end result is that the Solomonoff predictor needs to see just a few more bytes of the data sequence before it converges to essentially optimal predictions.”
This doesn’t address what I said at all. We don’t speak of “the” universal prior because there’s a specific UTM it’s defined with respect to, we speak of “the” universal prior because we don’t much care about the distinction between different universal priors! The above article is still about doing Bayesian updating starting with a universal prior. That which particular universal prior you start from doesn’t matter much is not new information and in no way supports your claim that any “reasonable” prior—whatever that might mean—will also have this same property.
I think when he says “the choice of the reference machine doesn’t matter too much” and “the choice of reference machine really doesn’t matter except for very small data sets” he literally means those things. I agree that my position on this is not new.
Sorry, how does “literally” differ from what I stated? And you seem to be stating something very different from him. He is just stating that the UTM used to define the universal prior is irrelevant. You are claiming that any “reasonable” prior, for some unspecified but expansive-sounding notion of “reasonable”, has the same universal property as a universal prior.
That seems like quite a tangle, and alas, am not terribly interested in it . But:
The term was “reference machine”. No implication that it is a UTM is intended—it could be a CA—or any other universal computer. The reference machine totally defines all aspects of the prior. There are not really “universal reference machines” which are different from other “reference machines”—or if there are “universal” just refers to universal computation. A universal machine can define literally any distribution of priors you can possibly imagine. So: the distinction you are trying to make doesn’t seem to make much sense.
Convergence on accurate beliefs has precious little to do with the prior—it is a property of the updating scheme. The original priors matter little after a short while—provided they are not zero, one—or otherwise set so they prevent updating from working at all.
Thinking of belief convergence as having much to do with your priors is a wrong thought.
The term was “reference machine”. No implication that it is a UTM is intended—it could be a CA—or any other universal computer. The reference machine totally defines all aspects of the prior. There are not really “universal reference machines” which are different from other “reference machines”—or if there are “universal” just refers to universal computation. A universal machine can define literally any distribution of priors you can possibly imagine. So: the distinction you are trying to make doesn’t seem to make much sense.
Sorry, what? Of course it can be any sort of universal computer; why would we care whether it’s a Turing machine or some other sort? Your statement that taking a universal computer and generating the corresponding universal prior will get you “literally any distribution of priors you can imagine” is just false, especially as it will only get you uncomputable ones! Generating a universal prior will only get you universal priors. Perhaps you were thinking of some other way of generating a prior from a universal computer? Because that isn’t what’s being talked about.
Convergence on accurate beliefs has precious little to do with the prior—it is a property of the updating scheme. The original priors matter little after a short while—provided they are not zero, one—or otherwise set so they prevent updating from working at all.
Thinking of belief convergence as having much to do with your priors is a wrong thought.
You have still done nothing to demonstrate this. The potential for dependence on priors has been demonstrated elsewhere (anti-inductive priors, etc). The “updating scheme” is Bayes’ Rule. (This might not suffice in the continuous-time case, but you explicitly invoked the discrete-time case above!) But to determine all those probabilities, you need to look at the prior. Seriously, show me (or just point me to) some math. If you refuse to say what makes a prior “reasonable”, what are you actually claiming? That the set of priors with this property is large in some appropriate sense? Please name what sense. Why should we not just use some equivalent of maxent, if what you say is true?
“Of course it can be any sort of universal computer; why would we care whether it’s a Turing machine or some other sort?”
Well, different reference machines produce different prior distributions—so the distribution used matters initially, when the machine is new to the world.
“Your statement that taking a universal computer and generating the corresponding universal prior will get you “literally any distribution of priors you can imagine” is just false, especially as it will only get you uncomputable ones! ”
“Any distribution you can compute”, then—if you prefer to think that you can imagine the uncomputable.
“You have still done nothing to demonstrate this.”
Actually, I think I give up trying to explain. From my perspective you seem to have some kind of tangle around the word “universal”. “Universal” could usefully refer to “universal computation” or to a prior that covers “every hypothesis in the universe”.
There is also the “universal prior”—but I don’t think “universal” there has quite the same significance that you seem to think it does. There seems to be repeated miscommunication going on in this area.
It seems non-trivial to describe the class of priors that leads to “fairly rapid” belief convergence in an intelligent machine. Suffice to say, I think that class is large—and that the details of priors are relatively insignificant—provided there is not too much “faith”—or “near faith”. Part of the reason for that is that priors usually get rapidly overwritten by data. That data establishes its own subsequent prior distributions for all the sources you encounter—and for most of the ones that you don’t. If you don’t agree, fine—I won’t bang on about it further in an attempt to convince you.
Firstly, please use Markdown quotes for ease of reading? :-/
Well, different reference machines produce different prior distributions—so the distribution used matters initially, when the machine is new to the world.
Indeed, but I don’t think that’s really the property under discussion.
“Any distribution you can compute”, then—if you prefer to think that you can imagine the uncomputable.
....huh? Maybe you are misunderstanding the procedure in question here. We are not taking arbitrary computations that output distributions and using those distributions. That would get you arbitrary computable distributions. Rather, we are taking arbitrary universal computers/UTMs/Turing-complete programming languages/whatever you want to call them, and then generating a distribution as “probability of x is sum over 2^-length over all programs that output something beginning with x” (possibly normalized). I.e. we are taking a reference machine and generating the corresponding universal prior.
Not only will this not get you “any distribution you can compute”, it won’t get you any distributions you can compute at all. The resulting distribution is always uncomputable. (And hence, in particular, not practical, and presumably not “reasonable”, whatever that may mean.)
Am I mistaken in asserting that this is what was under discussion?
It seems non-trivial to describe the class of priors that leads to “fairly rapid” belief convergence in an intelligent machine. Suffice to say, I think that class is large—and that the details of priors are relatively insignificant—provided there is not too much “faith”—or “near faith”. Part of the reason for that is that priors usually get rapidly overwritten by data. That data establishes its own subsequent prior distributions for all the sources you encounter—and for most of the ones that you don’t. If you don’t agree, fine—I won’t bang on about it further in an attempt to convince you.
You don’t have to attempt to convince me, but do note that despite asserting it repeatedly you have, in fact, done zero to establish the truth of this assertion / validity of this intuition, which I have good reason to believe to be unlikely, as I described earlier.
FWIW, what I meant was that—by altering the reference machine, p() - for all bitstrings less than a zillion bits long—can be made into any set of probabilities you like—provided they don’t add up to more than 1, of course.
The reference machine defines the resulting probability distribution completely.
AH! So you are making a comment on the use of universal priors to approximate arbitrary finite priors (and hence presumably vice versa). That is interesting, though I’m not sure what it has to do with eventual convergence. You should have actually stated that at some point!
Re: “I don’t understand how this notion of “update speed” translates into the Bayesian setting.”
Say you think p(heads) is 0.5. If you see ten heads in a row, do you update p(heads) a lot, or a little? It depends on how confident you are of your estimate.
If you had previously seen a thousand coin flips from the same coin, you might be confident of p(heads) being 0.5 - and therefore update little. If you were told that it was a biased coin from a magician, then your estimate of p(heads) being 0.5 might be due to not knowing which way it was biased. Then you might update your estimate of p(heads) rapidly—on seing several heads in a row.
What you have just laid out are not different “update speeds” but different priors. “It’s a biased coin from a magician” is of the same class of prior assumptions as “It’s probably a fair coin” or “It’s a coin with some fixed probability of landing heads, but I have no idea what” or “It’s a rigged coin that can only come up heads 10 times once activated”.
After each toss, you do precisely one Bayesian update. Perhaps the notion of “update speed” might make sense in a more continuous setting, but in a discrete setting like this it is clear it does not. The amount you update is determined by Bayes’ Law; different apparent “update speeds” are due to differing priors. “Speed” probably isn’t even a good term, as updates aren’t even necessarily in the same direction! If you think the coin can only come up heads 10 times, each appearance of heads makes it less likely to come up again.
I do not know where the idea that “speeds” are “parameters” and not “statistics” comes from. An entity being a statistic doesn’t imply that it is not a speed.
The same goes for discrete systems. They have the concept of speed too:
This is utterly irrelevant. The problem with what you say is not that there’s no notion of speed, it’s that there is precisely one way of doing updates, and it has no “speed” parameter.
In the game of life, the update speed is always once per generation. However, that doesn’t mean it has no concept of speed. In fact the system exhibits gliders with many different speeds.
It’s much the same with an intelligent agent’s update speed in response to evidence—some will update faster than others—depending on what they already know.
You claimed that:
“Perhaps the notion of “update speed” might make sense in a more continuous setting, but in a discrete setting like this it is clear it does not.”
However, the concept of “speed” works equally well in discrete and continuous systems—as the GOL illustrates. “Discreteness” is an irrelevance.
“Perhaps the notion of “update speed” might make sense in a more continuous setting, but in a discrete setting like this it is clear it does not.”
However, the concept of “speed” works equally well in discrete and continuous systems—as the GOL illustrates. “Discreteness” is an irrelevance.
You really seem to be missing the point here. I’m sorry but from your posts I can’t help but get the idea that you don’t really understand how this sort of prediction scheme works. Sure, “update speed” in the sense you described it elsewhere in the thread makes sense, but who cares? Update speed in these you described it elsewhere in the thread is a consequence of the prior (or current state, rather), it isn’t some sort of parameter, and it’s not clear it’s something at all stable or meaningful. You’ve established the existence of something trivial and probably irrelevant. In the parametric sense you seemed to be originally using it, it doesn’t exist. Can we agree on this?
Probably nobody cares—apart from you, it seems. Apparently, one can’t get away with using the phrase “update speed” in connection with an intelligent agent without getting bounced.
When you said:
“I don’t understand how this notion of “update speed” translates into the Bayesian setting.”
...and I said...
“Say you think p(heads) is 0.5. If you see ten heads in a row, do you update p(heads) a lot, or a little? It depends on how confident you are of your estimate. If you had previously seen a thousand coin flips from the same coin, you might be confident of p(heads) being 0.5 - and therefore update little. If you were told that it was a biased coin from a magician, then your estimate of p(heads) being 0.5 might be due to not knowing which way it was biased. Then you might update your estimate of p(heads) rapidly—on seing several heads in a row. Like that.”
...IMO, the conversation could and should have stopped—right there.
In the game of life, the update speed is always once per generation. However, that doesn’t mean it has no concept of speed. In fact the system exhibits gliders with many different speeds.
This is not analogous. We are speaking of a complete system here.
It’s much the same with an intelligent agent’s update speed in response to evidence—some will update faster than others—depending on what they already know.
I have already addressed this. What you have called “update speed” is determined by current distribution.
I assure you that I could exhibit a GOL field that consisted entirely of gliders moving at c/2 - and then exhibit another GOL field that consisted entirely of gliders moving at c/4. These systems would have different characteristic speeds. Hopefully, you see the analogy now.
Just so. I never said otherwise. You already asked for clarification about whether I thought that the system’s “update speed” was to do with its prior Prob. Dist. - and I said that “yes”, it was.
Hm; there may not be a disagreement here. You seemed to be using it in a way that implied it was not determined by (or even was independent of) the prior. Was I mistaken there?
The idea was that some agents update faster than others (or indeed not at all).
If you like you can think of the agents that update relatively slowly as being confident that they are uncertain about the things they are unsure about. That confidence in their own uncertainty could indeed be represented by other priors.
If you want to think about it that way, please don’t say “other priors”. That’s very confusing, because “prior” in this context refers to the whole prior, not to pieces of it (which I’m not sure how you’re detangling from each other, anyway). If we’re talking about something of the universal-prior sort, it has one prior, over its total sensory experience; I’m not clear how you’re decomposing that or what alternative model you are suggesting.
The two types of prior probability I discussed were “belifs about the world” and “beliefs about the certainty of those beliefs”.
An agent that updates its beliefs about the world rapidly (in response to evidence) would have a low degree of certainty about those beliefs—while an agent that updates its beliefs about the world slowly would have a high degree of certainty that those beliefs were already correct—and were backed up with lots of existing evidence.
I gave an example of this already when I discussed the magician’s coin.
Except these aren’t separate things. That isn’t how this sort of system works! Its beliefs about the certainty of those beliefs are determined by its beliefs about the world.
Well, everything is about the world, if materialism is true.
You don’t seem to be even trying to perform a sympathetic reading. Leave aside quibbling about what is to do with the world—can you at least see that in the first case, updates happen quickly, and in the second case they happen slowly? “Speed” just refers to distance divided by time. Here distance is the probabiliy delta, and time is simply time. So, updates can happen fast and slow. Some systems update quickly, others update slowly—and others don’t update at all. This all seems fairly simple to me—what is the problem?
Right. I really don’t think that what I am saying is controversial. The way I remember it, I talked about systems with different update speeds—and you jumped on that.
Alternatively, I could say, I went with the assumption that you were attempting to carve the relevant concepts at the joints and getting it wrong, rather than that you were making a true statement which doesn’t even try to accomplish that.
M, sorry then. But you didn’t explain the term anywhere, so I assumed it meant what it sounded like—the original context makes it sound like you mean something separate from the prior, rather than something determined by it. If instead of talking about building an agent that were “confident in their priors” and “updated them slowly” you had just spoken of “priors that result in slow updating” I don’t think there would have been a problem. (I must admit I probably also wasn’t inclined to look for a sympathetic reading as your other comments about the universal prior seem to be just wrong. )
Re: “there wouldn’t actually be be very much special about the universal prior”
Well, Occam’s razor is something rather special. However, agents don’t need an optimal version of it built into them as a baby—they can figure it out from their sensory inputs.
Uncomputable strings are all infinite. Those concerned with the real world don’t have to concern themselves with such things. Everything you encounter in practice is finite, and therefore computable.
Nothing much happens to intelligent agents—because an intelligent agents’ original priors mostly get left behind shortly after they are born—and get replaced by evidence-based probability estimates of events happening.
Prior determines how evidence informs your estimates, what things you can consider. In order to “replace priors with evidence-based probability estimates of events”, you need a notion of event, and that is determined by your prior.
Prior evaluates, but it doesn’t dictate what is being evaluated. In this case, “events happening” refers to subjective anticipation, which in turn refers to prior, but this connection is far from being straightforward.
“Determined” in the sense of “weakly influenced”. The more actual data you get, the weaker the influence of the original prior becomes—and after looking at the world for a little while, your original priors become insignificant—swamped under a huge mountain of sensory data about the actual observed universe.
Priors don’t really affect what things you can consider—since you can consider (and assign non-zero probability to) receiving any sensory input sequence.
I use the word “prior” in the sense of priors as mathematical objects, meaning all of your starting information plus the way you learn from experience.
I can’t quite place “you need a notion of event, and that is determined by your prior”, but I guess the mapping between sample space and possible observations is what you meant.
Well yes, you have “priors” that you learn from experince. An uncomputable world is not a problem for them—since you can learn about uncomputable physics, the same way as you learn about everything else.
This whole discussion seems to be a case of people making a problem out of nothing.
Well yes, you can have “priors” that you have learned from experience. An uncomputable world is not a problem in that case either—since you can learn about uncomputable physics, in just the same way that you learn about everything else.
This whole discussion seems to be a case of people making a problem out of nothing.
If you are assigning p(some empirical hypothesis) = 0, surely you are a broken system.
The example seems to be that a using a Turing machine to generate your priors somehow results in an expectation of p(uncomputable universe)=0. That idea just seems like total nonsense to me. It just doesn’t follow. For all I care, my priors could have been assigned to me using a Turing machine model at birth—but I don’t think p(uncomputable universe)=0. The whole line of reasoning apparently makes no sense.
The universal prior enumerates all Turing machines, not all possible priors generated by all Turing machines.
Priors are probabality estimates for uncertain quantities.
In Solomonoff induction they are probabality estimates for bitstrings—which one can think of as representing possible sensory inputs for an agent.
With a standard TM_length-based encoding, no finite bitstring is assigned a zero probability—and we won’t have to worry about perceiving infinite bitstrings until after the universal heat death—so there is no problem with assigning certain bitstrings a zero prior probability.
Whether the bitstrings were created using uncomputable physics is neither here nor there. They are still just bitstrings—and so can be output by a TM with a finite program on its tape.
No, sorry. You’re confused. A prior is not an assignment of credences to all bitstrings that you can observe. A prior is an assignment of credences to hypotheses, i.e. possible states of the world that generate bitstrings that you observe. Otherwise you’d find yourself in this text (see part II, “Escaping the Greek Hinterland”).
No. We were talking about the universal prior. Here is how that is defined for sequences:
“The universal prior probability of any prefix p of a computable sequence x is the sum of the probabilities of all programs (for a universal computer) that compute something starting with p.”
http://en.wikipedia.org/wiki/Inductive_inference
The universal prior of a sequence is the probability of that particular sequence arising (as a prefix). It is not the probabilty of any particular hypothesis or program. Rather is a weighted sum of the probabilities of all the programs that generate that sequence.
You can talk about the probabilities of hypothesis and programs as well if you like—but the universal prior of a sequence is perfectly acceptable subject matter—and is not a “confused” idea.
No finite sequence has a probabilty of zero—according to the universal prior.
All finite bitstrings can be produced by computable means—even if they were generated as the output of an uncomputable physical process.
Is this misconception really where this whole idea arises from?
This is all true, but… Why do you think the universal prior talks about computer programs at all? If I only wanted a prior over all finite bitstrings, I’d use a simpler prior that assigned every string of length N a credence proportional to 2^-N. Except that prior has a rather major shortcoming: it doesn’t help you predict the future! No matter how many bits you feed it, it always says the next bit is going to be either 0 or 1 with probability 50%. It will never get “swamped” by the data, never gravitate to any conclusions. This is why we want the universal prior to be based on computer programs instead: it will work better in practice, if the universe is in fact computable. But what happens if the universe is uncomputable? That’s the substantive question here.
ETA: the last two sentences are wrong, disregard them.
Nothing much happens to intelligent agents—because an intelligent agents’ original priors mostly get left behind shortly after they are born—and get replaced by evidence-based probability estimates of events happening. If convincing evidence comes in that the world is uncomputable, that just adds to the enormous existing stack of evidence they have about the actual frequencies of things.
Anyhow, priors being set to 0 or 1 is not a problem for observable sense data. No finite sense data has p assigned to 0 or 1 under the universal prior—so an agent can always update successfully—if it gets sufficient evidence that a sequence was actually produced. So, if it sees a system that apparently solves the halting problem for arbitrary programs, that is no big deal for it. It may have found a Turing oracle! Cool!
I suppose it might be possible to build an semi-intelligent agent with a particular set of priors permanently wired into it—so the agent was incapable of learning and adapting if its environment changed. Organic intelligent agents are not much like that—and I am not sure how easy it would be to build such a thing. Such agents would be incapable of adapting to an uncomputable world. They would always make bad guesses about uncomputable events. However, this seems speculative—I don’t see why people would try to create such agents. They would do very badly in certain simulated worlds—where Occam’s razor doesn’t necessarily hold true—and it would be debatable whether their intelligence was really very “general”.
The reason the universal prior is called “universal” is because given initial segments, where the infinite strings come from any computable distribution, and updating on those samples, it will, in fact, converge to the actual distribution on what the next bit should be. Now I’ll admit to not actually knowing the math here, but it seems to me that if most any prior had that property, as you seem to imply, we wouldn’t need to talk about a universal prior in the first place, no?
Also, if we interpret “universe” as “the actual infinite string that these segments are initial segments” of, then, well… take a look at that sum you posted and decompose it. The universal prior is basically assigning a probability to each infinite string, namely the sum of the probabilities of programs that generate it, and then collapsing that down to a distribution on initial segments in the obvious way. So if we want to consider its hypotheses about the actual law of the universe, the whole string, it will always assign 0 probability to an uncomputable sequence.
Convergence is more the result of the updates than the original prior. All the initial prior has to be to result in convergence is not completely ridiculous (1, 0, infinitessimals, etc). The idea of a good prior is that it helps initially, before an agent has any relevant experience to go on. However, that doesn’t usually last for very long—real organic agents are pretty quickly flooded with information about the state of the universe, and are then typically in a much better position to make probabililty estimates. You could build agents that were very confident in their priors—and updated them slowly—but only rarely would you want an agent that was handicapped in its ability to adapt and learn.
Picking the best reference machine would be nice—but I think most people understand that for most practical applications, it doesn’t matter—and that even a TM will do.
Are you certain of this? Could you provide some sort of proof or reference, please, ideally together with some formalization of what you mean by “completely ridiculous”? I’ll admit to not having looked up a proof of convergence for the universal prior or worked it out myself, but what you say were really the case, there wouldn’t actually be be very much special about the universal prior, and this convergence property of it wouldn’t be worth pointing out—so I think I have good reason to be highly skeptical of what you suggest.
Better, yes. But good enough? Arbitrarily close?
Sorry, but what does this even mean? I don’t understand how this notion of “update speed” translates into the Bayesian setting.
Here’s Shane Legg on the topic of how little priors matter when predicting the environment:
“In some situations, for example with Solomonoff induction, the choice of the reference machine doesn’t matter too much. [...] the choice of reference machine really doesn’t matter except for very small data sets (which aren’t really the ones we’re interested in here). To see this, have a look at the Solomonoff convergence bound and drop a compiler constant in by the complexity of the environment. The end result is that the Solomonoff predictor needs to see just a few more bytes of the data sequence before it converges to essentially optimal predictions.”
http://www.vetta.org/2009/05/on-universal-intelligence/
This doesn’t address what I said at all. We don’t speak of “the” universal prior because there’s a specific UTM it’s defined with respect to, we speak of “the” universal prior because we don’t much care about the distinction between different universal priors! The above article is still about doing Bayesian updating starting with a universal prior. That which particular universal prior you start from doesn’t matter much is not new information and in no way supports your claim that any “reasonable” prior—whatever that might mean—will also have this same property.
I think when he says “the choice of the reference machine doesn’t matter too much” and “the choice of reference machine really doesn’t matter except for very small data sets” he literally means those things. I agree that my position on this is not new.
Sorry, how does “literally” differ from what I stated? And you seem to be stating something very different from him. He is just stating that the UTM used to define the universal prior is irrelevant. You are claiming that any “reasonable” prior, for some unspecified but expansive-sounding notion of “reasonable”, has the same universal property as a universal prior.
That seems like quite a tangle, and alas, am not terribly interested in it . But:
The term was “reference machine”. No implication that it is a UTM is intended—it could be a CA—or any other universal computer. The reference machine totally defines all aspects of the prior. There are not really “universal reference machines” which are different from other “reference machines”—or if there are “universal” just refers to universal computation. A universal machine can define literally any distribution of priors you can possibly imagine. So: the distinction you are trying to make doesn’t seem to make much sense.
Convergence on accurate beliefs has precious little to do with the prior—it is a property of the updating scheme. The original priors matter little after a short while—provided they are not zero, one—or otherwise set so they prevent updating from working at all.
Thinking of belief convergence as having much to do with your priors is a wrong thought.
Sorry, what? Of course it can be any sort of universal computer; why would we care whether it’s a Turing machine or some other sort? Your statement that taking a universal computer and generating the corresponding universal prior will get you “literally any distribution of priors you can imagine” is just false, especially as it will only get you uncomputable ones! Generating a universal prior will only get you universal priors. Perhaps you were thinking of some other way of generating a prior from a universal computer? Because that isn’t what’s being talked about.
You have still done nothing to demonstrate this. The potential for dependence on priors has been demonstrated elsewhere (anti-inductive priors, etc). The “updating scheme” is Bayes’ Rule. (This might not suffice in the continuous-time case, but you explicitly invoked the discrete-time case above!) But to determine all those probabilities, you need to look at the prior. Seriously, show me (or just point me to) some math. If you refuse to say what makes a prior “reasonable”, what are you actually claiming? That the set of priors with this property is large in some appropriate sense? Please name what sense. Why should we not just use some equivalent of maxent, if what you say is true?
“Of course it can be any sort of universal computer; why would we care whether it’s a Turing machine or some other sort?”
Well, different reference machines produce different prior distributions—so the distribution used matters initially, when the machine is new to the world.
“Your statement that taking a universal computer and generating the corresponding universal prior will get you “literally any distribution of priors you can imagine” is just false, especially as it will only get you uncomputable ones! ”
“Any distribution you can compute”, then—if you prefer to think that you can imagine the uncomputable.
“You have still done nothing to demonstrate this.”
Actually, I think I give up trying to explain. From my perspective you seem to have some kind of tangle around the word “universal”. “Universal” could usefully refer to “universal computation” or to a prior that covers “every hypothesis in the universe”. There is also the “universal prior”—but I don’t think “universal” there has quite the same significance that you seem to think it does. There seems to be repeated miscommunication going on in this area.
It seems non-trivial to describe the class of priors that leads to “fairly rapid” belief convergence in an intelligent machine. Suffice to say, I think that class is large—and that the details of priors are relatively insignificant—provided there is not too much “faith”—or “near faith”. Part of the reason for that is that priors usually get rapidly overwritten by data. That data establishes its own subsequent prior distributions for all the sources you encounter—and for most of the ones that you don’t. If you don’t agree, fine—I won’t bang on about it further in an attempt to convince you.
Firstly, please use Markdown quotes for ease of reading? :-/
Indeed, but I don’t think that’s really the property under discussion.
....huh? Maybe you are misunderstanding the procedure in question here. We are not taking arbitrary computations that output distributions and using those distributions. That would get you arbitrary computable distributions. Rather, we are taking arbitrary universal computers/UTMs/Turing-complete programming languages/whatever you want to call them, and then generating a distribution as “probability of x is sum over 2^-length over all programs that output something beginning with x” (possibly normalized). I.e. we are taking a reference machine and generating the corresponding universal prior.
Not only will this not get you “any distribution you can compute”, it won’t get you any distributions you can compute at all. The resulting distribution is always uncomputable. (And hence, in particular, not practical, and presumably not “reasonable”, whatever that may mean.)
Am I mistaken in asserting that this is what was under discussion?
You don’t have to attempt to convince me, but do note that despite asserting it repeatedly you have, in fact, done zero to establish the truth of this assertion / validity of this intuition, which I have good reason to believe to be unlikely, as I described earlier.
FWIW, what I meant was that—by altering the reference machine, p() - for all bitstrings less than a zillion bits long—can be made into any set of probabilities you like—provided they don’t add up to more than 1, of course.
The reference machine defines the resulting probability distribution completely.
AH! So you are making a comment on the use of universal priors to approximate arbitrary finite priors (and hence presumably vice versa). That is interesting, though I’m not sure what it has to do with eventual convergence. You should have actually stated that at some point!
Re: “I don’t understand how this notion of “update speed” translates into the Bayesian setting.”
Say you think p(heads) is 0.5. If you see ten heads in a row, do you update p(heads) a lot, or a little? It depends on how confident you are of your estimate.
If you had previously seen a thousand coin flips from the same coin, you might be confident of p(heads) being 0.5 - and therefore update little. If you were told that it was a biased coin from a magician, then your estimate of p(heads) being 0.5 might be due to not knowing which way it was biased. Then you might update your estimate of p(heads) rapidly—on seing several heads in a row.
Like that.
What you have just laid out are not different “update speeds” but different priors. “It’s a biased coin from a magician” is of the same class of prior assumptions as “It’s probably a fair coin” or “It’s a coin with some fixed probability of landing heads, but I have no idea what” or “It’s a rigged coin that can only come up heads 10 times once activated”.
After each toss, you do precisely one Bayesian update. Perhaps the notion of “update speed” might make sense in a more continuous setting, but in a discrete setting like this it is clear it does not. The amount you update is determined by Bayes’ Law; different apparent “update speeds” are due to differing priors. “Speed” probably isn’t even a good term, as updates aren’t even necessarily in the same direction! If you think the coin can only come up heads 10 times, each appearance of heads makes it less likely to come up again.
“Update speed” seems fine to me—when comparing:
.5, .500001, .500002, .500003, .500004...
....with...
.5, 0.7, 0.9, 0.94, 0.96
...but use whatever term you like.
That’s a statistic, not a parameter—and it’s a statistic ultimately determined by the prior.
I do not know where the idea that “speeds” are “parameters” and not “statistics” comes from. An entity being a statistic doesn’t imply that it is not a speed.
The same goes for discrete systems. They have the concept of speed too:
http://en.wikipedia.org/wiki/Glider_%28Conway%27s_Life%29
This is utterly irrelevant. The problem with what you say is not that there’s no notion of speed, it’s that there is precisely one way of doing updates, and it has no “speed” parameter.
In the game of life, the update speed is always once per generation. However, that doesn’t mean it has no concept of speed. In fact the system exhibits gliders with many different speeds.
It’s much the same with an intelligent agent’s update speed in response to evidence—some will update faster than others—depending on what they already know.
You claimed that:
“Perhaps the notion of “update speed” might make sense in a more continuous setting, but in a discrete setting like this it is clear it does not.”
However, the concept of “speed” works equally well in discrete and continuous systems—as the GOL illustrates. “Discreteness” is an irrelevance.
You really seem to be missing the point here. I’m sorry but from your posts I can’t help but get the idea that you don’t really understand how this sort of prediction scheme works. Sure, “update speed” in the sense you described it elsewhere in the thread makes sense, but who cares? Update speed in these you described it elsewhere in the thread is a consequence of the prior (or current state, rather), it isn’t some sort of parameter, and it’s not clear it’s something at all stable or meaningful. You’ve established the existence of something trivial and probably irrelevant. In the parametric sense you seemed to be originally using it, it doesn’t exist. Can we agree on this?
Probably nobody cares—apart from you, it seems. Apparently, one can’t get away with using the phrase “update speed” in connection with an intelligent agent without getting bounced.
When you said:
“I don’t understand how this notion of “update speed” translates into the Bayesian setting.”
...and I said...
“Say you think p(heads) is 0.5. If you see ten heads in a row, do you update p(heads) a lot, or a little? It depends on how confident you are of your estimate. If you had previously seen a thousand coin flips from the same coin, you might be confident of p(heads) being 0.5 - and therefore update little. If you were told that it was a biased coin from a magician, then your estimate of p(heads) being 0.5 might be due to not knowing which way it was biased. Then you might update your estimate of p(heads) rapidly—on seing several heads in a row. Like that.”
...IMO, the conversation could and should have stopped—right there.
This is not analogous. We are speaking of a complete system here.
I have already addressed this. What you have called “update speed” is determined by current distribution.
Re: “We are speaking of a complete system here”
I assure you that I could exhibit a GOL field that consisted entirely of gliders moving at c/2 - and then exhibit another GOL field that consisted entirely of gliders moving at c/4. These systems would have different characteristic speeds. Hopefully, you see the analogy now.
OK, sure. But then to continue the analogy, in the resulting speed is a function of the initial configuration. :)
Just so. I never said otherwise. You already asked for clarification about whether I thought that the system’s “update speed” was to do with its prior Prob. Dist. - and I said that “yes”, it was.
Hm; there may not be a disagreement here. You seemed to be using it in a way that implied it was not determined by (or even was independent of) the prior. Was I mistaken there?
The idea was that some agents update faster than others (or indeed not at all).
If you like you can think of the agents that update relatively slowly as being confident that they are uncertain about the things they are unsure about. That confidence in their own uncertainty could indeed be represented by other priors.
That’s not “other priors”, there’s just one prior. All the probabilities in Bayes’ Rule come from the updated-to-current version of the prior.
Other prior probabilities. There is one prior set of probabilities, which is composed of many prior probabilities and probability distributions.
If you want to think about it that way, please don’t say “other priors”. That’s very confusing, because “prior” in this context refers to the whole prior, not to pieces of it (which I’m not sure how you’re detangling from each other, anyway). If we’re talking about something of the universal-prior sort, it has one prior, over its total sensory experience; I’m not clear how you’re decomposing that or what alternative model you are suggesting.
The two types of prior probability I discussed were “belifs about the world” and “beliefs about the certainty of those beliefs”.
An agent that updates its beliefs about the world rapidly (in response to evidence) would have a low degree of certainty about those beliefs—while an agent that updates its beliefs about the world slowly would have a high degree of certainty that those beliefs were already correct—and were backed up with lots of existing evidence.
I gave an example of this already when I discussed the magician’s coin.
Except these aren’t separate things. That isn’t how this sort of system works! Its beliefs about the certainty of those beliefs are determined by its beliefs about the world.
Well, everything is about the world, if materialism is true.
You don’t seem to be even trying to perform a sympathetic reading. Leave aside quibbling about what is to do with the world—can you at least see that in the first case, updates happen quickly, and in the second case they happen slowly? “Speed” just refers to distance divided by time. Here distance is the probabiliy delta, and time is simply time. So, updates can happen fast and slow. Some systems update quickly, others update slowly—and others don’t update at all. This all seems fairly simple to me—what is the problem?
Well, sure. But that statement is trivial.
Right. I really don’t think that what I am saying is controversial. The way I remember it, I talked about systems with different update speeds—and you jumped on that.
Alternatively, I could say, I went with the assumption that you were attempting to carve the relevant concepts at the joints and getting it wrong, rather than that you were making a true statement which doesn’t even try to accomplish that.
M, sorry then. But you didn’t explain the term anywhere, so I assumed it meant what it sounded like—the original context makes it sound like you mean something separate from the prior, rather than something determined by it. If instead of talking about building an agent that were “confident in their priors” and “updated them slowly” you had just spoken of “priors that result in slow updating” I don’t think there would have been a problem. (I must admit I probably also wasn’t inclined to look for a sympathetic reading as your other comments about the universal prior seem to be just wrong. )
Re: “there wouldn’t actually be be very much special about the universal prior”
Well, Occam’s razor is something rather special. However, agents don’t need an optimal version of it built into them as a baby—they can figure it out from their sensory inputs.
Uncomputable strings are all infinite. Those concerned with the real world don’t have to concern themselves with such things. Everything you encounter in practice is finite, and therefore computable.
And if you are faced with a black box emitting one digit at a time, how will you do better than maxent?
Prior determines how evidence informs your estimates, what things you can consider. In order to “replace priors with evidence-based probability estimates of events”, you need a notion of event, and that is determined by your prior.
Prior evaluates, but it doesn’t dictate what is being evaluated. In this case, “events happening” refers to subjective anticipation, which in turn refers to prior, but this connection is far from being straightforward.
“Determined” in the sense of “weakly influenced”. The more actual data you get, the weaker the influence of the original prior becomes—and after looking at the world for a little while, your original priors become insignificant—swamped under a huge mountain of sensory data about the actual observed universe.
Priors don’t really affect what things you can consider—since you can consider (and assign non-zero probability to) receiving any sensory input sequence.
I use the word “prior” in the sense of priors as mathematical objects, meaning all of your starting information plus the way you learn from experience.
I can’t quite place “you need a notion of event, and that is determined by your prior”, but I guess the mapping between sample space and possible observations is what you meant.
Well yes, you have “priors” that you learn from experince. An uncomputable world is not a problem for them—since you can learn about uncomputable physics, the same way as you learn about everything else.
This whole discussion seems to be a case of people making a problem out of nothing.
Well yes, you can have “priors” that you have learned from experience. An uncomputable world is not a problem in that case either—since you can learn about uncomputable physics, in just the same way that you learn about everything else.
This whole discussion seems to be a case of people making a problem out of nothing.