Solomonoff induction - Revision history

IssaRice: /* Turing machines, prefix machines, monotone machines */

2020-02-03T07:32:06Z

Turing machines, prefix machines, monotone machines

← Older revision		Revision as of 07:32, 3 February 2020
Line 111:		Line 111:

	prefix machines are used for discrete version, and monotone machines are used for continuous version?		prefix machines are used for discrete version, and monotone machines are used for continuous version?

			http://www.hutter1.net/ai/sintro2kc.pdf -- this is the only page that really makes the prefix vs montone distinction clear. For prefix we care that the machine halts, but for monotone we don't.

	What functions can prefix/monotone machines compute? Can they compute everything a regular Turing machine can, but just add an "interactive" component? Or is there some Turing-computable function that prefix/monotone machines can't compute? -- since the work tape is bidirectional and we can move freely on it, we can start by copying the program to it, then going back to the leftmost nonblank square, then executing the program like a normal Turing machine, and finally copying the resulting tape onto the write-only output tape. This only works if the program is finite though.		What functions can prefix/monotone machines compute? Can they compute everything a regular Turing machine can, but just add an "interactive" component? Or is there some Turing-computable function that prefix/monotone machines can't compute? -- since the work tape is bidirectional and we can move freely on it, we can start by copying the program to it, then going back to the leftmost nonblank square, then executing the program like a normal Turing machine, and finally copying the resulting tape onto the write-only output tape. This only works if the program is finite though.

IssaRice: /* Model selection vs sequence prediction */

2020-02-03T02:20:52Z

Model selection vs sequence prediction

← Older revision		Revision as of 02:20, 3 February 2020
Line 8:		Line 8:
	* sequence prediction -- this is the topic of solomonoff induction		* sequence prediction -- this is the topic of solomonoff induction
	* supervised learning and unordered prediction: see e.g. http://world.std.com/~rjs/compj99.pdf		* supervised learning and unordered prediction: see e.g. http://world.std.com/~rjs/compj99.pdf
	* counterfactual prediction (e.g. when acting in the world)		* counterfactual prediction (e.g. when acting in the world) see https://www.greaterwrong.com/posts/pHWTNMESuAEjZg2Qn/occam-s-razor-may-be-sufficient-to-infer-the-preferences-of#comment-QRoA55njPWxBqWgfH

	Solomonoff induction is formulated in terms of ''sequence prediction'' so the nature of the prediction = the nature of the data, i.e. we want to predict the likely data we will observe next.		Solomonoff induction is formulated in terms of ''sequence prediction'' so the nature of the prediction = the nature of the data, i.e. we want to predict the likely data we will observe next.

IssaRice: /* Model selection vs sequence prediction */

2020-02-03T02:19:20Z

Model selection vs sequence prediction

← Older revision		Revision as of 02:19, 3 February 2020
Line 8:		Line 8:
	* sequence prediction -- this is the topic of solomonoff induction		* sequence prediction -- this is the topic of solomonoff induction
	* supervised learning and unordered prediction: see e.g. http://world.std.com/~rjs/compj99.pdf		* supervised learning and unordered prediction: see e.g. http://world.std.com/~rjs/compj99.pdf
			* counterfactual prediction (e.g. when acting in the world)

	Solomonoff induction is formulated in terms of ''sequence prediction'' so the nature of the prediction = the nature of the data, i.e. we want to predict the likely data we will observe next.		Solomonoff induction is formulated in terms of ''sequence prediction'' so the nature of the prediction = the nature of the data, i.e. we want to predict the likely data we will observe next.

IssaRice: /* Turing machines, prefix machines, monotone machines */

2020-02-03T02:06:06Z

Turing machines, prefix machines, monotone machines

← Older revision		Revision as of 02:06, 3 February 2020
Line 102:		Line 102:
	Consider a prefix machine T. Then T(p)=x means that p is a self-delimiting program, and halts with output x. This means that T(p01010)!=x, since p01010 is not self-delimiting (because T halts immediately after reading p, so it doesn't get to the extra 01010 part). Like the monotone case, this is notationally a little confusing for me. I would rather have T(p) mean a separate expression, meaning if we feed T with p, then the output of that (if it ever halts). So in my world, T(p01010) is x, and x=x. Now the problem with this is that when we're summing over these programs, we need to filter out the non-self-delimiting ones. So for that we can just define some set like <math>S^x</math> (set of all p which are self-delimiting for x). I think this makes more sense, and is actually what the LW wiki page does, but not what marcus hutter does.		Consider a prefix machine T. Then T(p)=x means that p is a self-delimiting program, and halts with output x. This means that T(p01010)!=x, since p01010 is not self-delimiting (because T halts immediately after reading p, so it doesn't get to the extra 01010 part). Like the monotone case, this is notationally a little confusing for me. I would rather have T(p) mean a separate expression, meaning if we feed T with p, then the output of that (if it ever halts). So in my world, T(p01010) is x, and x=x. Now the problem with this is that when we're summing over these programs, we need to filter out the non-self-delimiting ones. So for that we can just define some set like <math>S^x</math> (set of all p which are self-delimiting for x). I think this makes more sense, and is actually what the LW wiki page does, but not what marcus hutter does.
	I guess the way to think about this in terms of the hutter way is to say that if p01010 is on the tape then we never read past p, so it's not quite true to say T(p01010)=x. Instead, we should say T(p)=x. There is no way to feed T with p01010, since it refuses to read past p. So we should summarize this by saying that T(p01010) is undefined.		I guess the way to think about this in terms of the hutter way is to say that if p01010 is on the tape then we never read past p, so it's not quite true to say T(p01010)=x. Instead, we should say T(p)=x. There is no way to feed T with p01010, since it refuses to read past p. So we should summarize this by saying that T(p01010) is undefined.

			One difference between prefix machines and monotone machines: for prefix machines, there is no difference between saying "self-delimiting program" and "self-delimiting program for x". But for monotone machines, saying "minimal program" and "minimal program for x" are different. Actually, saying "minimal program" might not even make sense.

	"can be computed by a monotone machine" = "can be computed by an interactive algorithm" = "process" (see Hay 2007)		"can be computed by a monotone machine" = "can be computed by an interactive algorithm" = "process" (see Hay 2007)

IssaRice: /* Turing machines, prefix machines, monotone machines */

2020-02-03T01:57:49Z

Turing machines, prefix machines, monotone machines

← Older revision		Revision as of 01:57, 3 February 2020
Line 101:		Line 101:

	Consider a prefix machine T. Then T(p)=x means that p is a self-delimiting program, and halts with output x. This means that T(p01010)!=x, since p01010 is not self-delimiting (because T halts immediately after reading p, so it doesn't get to the extra 01010 part). Like the monotone case, this is notationally a little confusing for me. I would rather have T(p) mean a separate expression, meaning if we feed T with p, then the output of that (if it ever halts). So in my world, T(p01010) is x, and x=x. Now the problem with this is that when we're summing over these programs, we need to filter out the non-self-delimiting ones. So for that we can just define some set like <math>S^x</math> (set of all p which are self-delimiting for x). I think this makes more sense, and is actually what the LW wiki page does, but not what marcus hutter does.		Consider a prefix machine T. Then T(p)=x means that p is a self-delimiting program, and halts with output x. This means that T(p01010)!=x, since p01010 is not self-delimiting (because T halts immediately after reading p, so it doesn't get to the extra 01010 part). Like the monotone case, this is notationally a little confusing for me. I would rather have T(p) mean a separate expression, meaning if we feed T with p, then the output of that (if it ever halts). So in my world, T(p01010) is x, and x=x. Now the problem with this is that when we're summing over these programs, we need to filter out the non-self-delimiting ones. So for that we can just define some set like <math>S^x</math> (set of all p which are self-delimiting for x). I think this makes more sense, and is actually what the LW wiki page does, but not what marcus hutter does.
			I guess the way to think about this in terms of the hutter way is to say that if p01010 is on the tape then we never read past p, so it's not quite true to say T(p01010)=x. Instead, we should say T(p)=x. There is no way to feed T with p01010, since it refuses to read past p. So we should summarize this by saying that T(p01010) is undefined.

	"can be computed by a monotone machine" = "can be computed by an interactive algorithm" = "process" (see Hay 2007)		"can be computed by a monotone machine" = "can be computed by an interactive algorithm" = "process" (see Hay 2007)

IssaRice: /* Turing machines, prefix machines, monotone machines */

2020-02-03T01:41:51Z

Turing machines, prefix machines, monotone machines

← Older revision		Revision as of 01:41, 3 February 2020
Line 98:		Line 98:
	Kraft's inequality		Kraft's inequality

	prefix machine = prefix-free machine?		prefix machine = prefix-free machine? (I think so)

			Consider a prefix machine T. Then T(p)=x means that p is a self-delimiting program, and halts with output x. This means that T(p01010)!=x, since p01010 is not self-delimiting (because T halts immediately after reading p, so it doesn't get to the extra 01010 part). Like the monotone case, this is notationally a little confusing for me. I would rather have T(p) mean a separate expression, meaning if we feed T with p, then the output of that (if it ever halts). So in my world, T(p01010) is x, and x=x. Now the problem with this is that when we're summing over these programs, we need to filter out the non-self-delimiting ones. So for that we can just define some set like <math>S^x</math> (set of all p which are self-delimiting for x). I think this makes more sense, and is actually what the LW wiki page does, but not what marcus hutter does.

	"can be computed by a monotone machine" = "can be computed by an interactive algorithm" = "process" (see Hay 2007)		"can be computed by a monotone machine" = "can be computed by an interactive algorithm" = "process" (see Hay 2007)

IssaRice: /* Applications */

2020-02-02T23:33:27Z

Applications

← Older revision		Revision as of 23:33, 2 February 2020
Line 160:		Line 160:
	==Applications==		==Applications==

	* there are some standard applications you can find standard references		* there are some standard applications you can find in standard references
	* AIXI		* AIXI
	* carl's analogy to psychophysical laws -- rob bensinger's post about AIXI also talks about "qualia factory"		* carl's analogy to psychophysical laws -- rob bensinger's post about AIXI also talks about "qualia factory"

IssaRice: /* Two different ways to think about conditional predictions */

2020-02-02T23:28:14Z

Two different ways to think about conditional predictions

← Older revision		Revision as of 23:28, 2 February 2020
Line 155:		Line 155:

	Simplifying this, we get <math>\sum_\nu \frac{\nu(x)w_\nu}{\xi(x)} \cdot \frac{\nu(xy)}{\nu(x)} = \frac{\sum_\nu w_\nu\nu(xy)}{\xi(x)} = \frac{\xi(xy)}{\xi(x)} = \xi(xy\mid x)</math>, which is exactly what we had before!		Simplifying this, we get <math>\sum_\nu \frac{\nu(x)w_\nu}{\xi(x)} \cdot \frac{\nu(xy)}{\nu(x)} = \frac{\sum_\nu w_\nu\nu(xy)}{\xi(x)} = \frac{\xi(xy)}{\xi(x)} = \xi(xy\mid x)</math>, which is exactly what we had before!

			So we can think of conditional sequence prediction in two different ways: (1) we could start out with an all-powerful prior, and just do regular bayesian updating using this prior; (2) given new evidence, we can update our beliefs in the experts, and then let those experts make conditional predictions, and finally aggregate those predictions.

	==Applications==		==Applications==

IssaRice: /* Two different ways to think about conditional predictions */

2020-02-02T23:24:55Z

Two different ways to think about conditional predictions

← Older revision		Revision as of 23:24, 2 February 2020
Line 154:		Line 154:
	Now using these new weights, to predict xy, we should have <math>P(xy \mid x) = \sum_\nu w_\nu(x)\nu(xy \mid x)</math>.		Now using these new weights, to predict xy, we should have <math>P(xy \mid x) = \sum_\nu w_\nu(x)\nu(xy \mid x)</math>.

	Simplifying this, we get <math>\sum_\nu \frac{\nu(x)w_\nu}{\xi(x)} \cdot \frac{\nu(xy)}{\nu(x)} = \~~frac1~~{~~\xi(x)}~~ \sum_\nu w_\nu\nu(xy) = \frac{\xi(xy)}{\xi(x)} = \xi(xy\mid x)</math>, which is exactly what we had before!		Simplifying this, we get <math>\sum_\nu \frac{\nu(x)w_\nu}{\xi(x)} \cdot \frac{\nu(xy)}{\nu(x)} = \frac{\sum_\nu w_\nu\nu(xy)}{\xi(x)} = \frac{\xi(xy)}{\xi(x)} = \xi(xy\mid x)</math>, which is exactly what we had before!

	==Applications==		==Applications==

IssaRice: /* Two different ways to think about conditional predictions */

2020-02-02T23:16:33Z

Two different ways to think about conditional predictions

← Older revision		Revision as of 23:16, 2 February 2020
Line 153:		Line 153:

	Now using these new weights, to predict xy, we should have <math>P(xy \mid x) = \sum_\nu w_\nu(x)\nu(xy \mid x)</math>.		Now using these new weights, to predict xy, we should have <math>P(xy \mid x) = \sum_\nu w_\nu(x)\nu(xy \mid x)</math>.

			Simplifying this, we get <math>\sum_\nu \frac{\nu(x)w_\nu}{\xi(x)} \cdot \frac{\nu(xy)}{\nu(x)} = \frac1{\xi(x)} \sum_\nu w_\nu\nu(xy) = \frac{\xi(xy)}{\xi(x)} = \xi(xy\mid x)</math>, which is exactly what we had before!

	==Applications==		==Applications==