I'm not trying to win any arguments, but I am trying to solve the problem of whether RSI is possible at all. It is an important question because it profoundly affects the path that a singularity would take, and what precautions we need to design into AGI. Without RSI, then a singularity has to be a (very fast) evolutionary process in which agents compete for computing resources. In this scenario, friendliness is stable only to the extent that it contributes to fitness and fails when the AGI no longer needs us.
If RSI is possible, then there is the additional threat of a fast takeoff of the kind described by Good and Vinge (and step 5 of the OpenCog roadmap). Friendliness and ethics are algorithmically complex functions that have to be hard coded into the first self-improving agent, and I have little confidence that this will happen. An unfriendly agent is much easier to build, so is likely to be built first. I looked at Legg's paper again, and I don't believe it rules out Goedel machines. Legg first proved that any program that predicts all infinite sequences up to Kolmogorov complexity n must also have complexity n, and then proved that except for very small n, that such predictors cannot be proven to work. This is a different context than a Goedel machine, which only has to learn a specific environment, not a set of environments. I don't know if Legg's proof would apply to RSI sequences of increasingly complex environments. -- Matt Mahoney, [EMAIL PROTECTED] ----- Original Message ---- From: Abram Demski <[EMAIL PROTECTED]> To: agi@v2.listbox.com Sent: Thursday, August 28, 2008 11:42:10 AM Subject: Re: Goedel machines (was Re: Information theoretic approaches to AGI (was Re: [agi] The Necessity of Embodiment)) PS-- I have thought of a weak argument: If a fact is not probabilistically learnable, then it is hard to see how it has much significance for an AI design. A non-learnable fact won't reliably change the performance of the AI, since if it did, it would be learnable. Furthermore, even if there were *some* important nonlearnable facts, it still seems like significant self-improvements could be made using only probabilistically learned facts. And, since the amount of time spent testing cases is a huge factor, RSI will not stop except due to limited memory, even in a relatively boring environment (unless the AI makes a rational decision to stop using resources on RSI since it has found a solution that is probably optimal). On Thu, Aug 28, 2008 at 11:25 AM, Abram Demski <[EMAIL PROTECTED]> wrote: > Matt, > > Ok, you have me, I admit defeat. > > I could only continue my argument if I could pin down what sorts of > facts need to be learned with high probability for RSI, and show > somehow that this set does not include unlearnable facts. Learnable > facts form a larger set than provable facts, since for example we can > probabilistically declare that a program never halts if we run it for > a while and it doesn't. But there are certain facts that are not even > probabilistically learnable, so until I can show that none of these > are absolutely essential to RSI, I concede. > > --Abram Demski > > On Wed, Aug 27, 2008 at 6:48 PM, Matt Mahoney <[EMAIL PROTECTED]> wrote: >> Abram Demski <[EMAIL PROTECTED]> wrote: >>>First, I do not think it is terribly difficult to define a Goedel >>>machine that does not halt. It interacts with its environment, and >>>there is some utility value attached to this interaction, and it >>>attempts to rewrite its code to maximize this utility. >> >> It's not that the machine halts, but that it makes no further improvements >> once the best solution is found. This might not be a practical concern if >> the environment is very complex. >> >> However, I doubt that a Goedel machine could even be built. Legg showed [1] >> that Goedel incompleteness is ubiquitous. To paraphrase, beyond some low >> level of complexity, you can't prove anything. Perhaps this is the reason we >> have not (AFAIK) built a software model, even for very simple sets of axioms. >> >> If we resort to probabilistic evidence of improvement rather than proofs, >> then it is no longer a Goedel machine, and I think we would need >> experimental verification of RSI. Random modifications of code are much more >> likely to be harmful than helpful, so we would need to show that >> improvements could be detected with a very low false positive rate. >> >> 1. http://www.vetta.org/documents/IDSIA-12-06-1.pdf >> >> >> -- Matt Mahoney, [EMAIL PROTECTED] >> >> >> >> ----- Original Message ---- >> From: Abram Demski <[EMAIL PROTECTED]> >> To: agi@v2.listbox.com >> Sent: Wednesday, August 27, 2008 11:40:24 AM >> Subject: Re: Goedel machines (was Re: Information theoretic approaches to >> AGI (was Re: [agi] The Necessity of Embodiment)) >> >> Matt, >> >> Thanks for the reply. There are 3 reasons that I can think of for >> calling Goedel machines "bounded": >> >> 1. As you assert, once a solution is found, it stops. >> 2. It will be on a finite computer, so it will eventually reach the >> one best version of itself that it can reach. >> 3. It can only make provably correct steps, which is very limiting >> thanks to Godel's incompleteness theorem. >> >> I'll try to argue that each of these limits can be overcome in >> principle, and we'll see if the result satisfies your RSI criteria. >> >> First, I do not think it is terribly difficult to define a Goedel >> machine that does not halt. It interacts with its environment, and >> there is some utility value attached to this interaction, and it >> attempts to rewrite its code to maximize this utility. >> >> The second and third need to be tackled together, because the main >> reason that a Goedel machine can't improve its own hardware is because >> there is uncertainty involved, so it would never be provably better. >> There is always some chance of hardware malfunction. So, I think it is >> necessary to grant the possibility of modifications that are merely >> very probably correct. Once this is done, 2 and 3 fall fairly easily, >> assuming that the machine begins life with a good probabilistic >> learning system. That is a big assumption, but we can grant it for the >> moment I think? >> >> For the sake of concreteness, let's say that the utility value is some >> (probably very complex) attempt to logically describe Eliezer-style >> Friendliness, and that the probabilistic learning system is an >> approximation of AIXI (which the system will improve over time along >> with everything else). (These two choices don't reflect my personal >> tastes, they are just examples.) >> >> By tweaking the allowances the system makes, we might either have a >> slow self-improver that is, say, 99.999% probable to only improve >> itself in the next 100 years, or a faster self-improver that is 50% >> guaranteed. >> >> Does this satisfy your criteria? >> >> On Wed, Aug 27, 2008 at 9:14 AM, Matt Mahoney <[EMAIL PROTECTED]> wrote: >>> Abram Demski <[EMAIL PROTECTED]> wrote: >>>>Matt, >>>> >>>>What is your opinion on Goedel machines? >>>> >>>> http://www.idsia.ch/~juergen/goedelmachine.html >>> >>> >>> Thanks for the link. If I understand correctly, this is a form of bounded >>> RSI, so it could not lead to a singularity. A Goedel machine is >>> functionally equivalent to AIXI^tl in that it finds the optimal >>> reinforcement learning solution given a fixed environment and utility >>> function. The difference is that AIXI^tl does a brute force search of all >>> machines up to length l for time t each, so it run in O(t 2^l) time. A >>> Goedel machine achieves the same result more efficiently through a series >>> of self improvments by proving that each proposed modification (including >>> modifications to its own proof search code) is a actual improvement. It >>> does this by using an instruction set such that it is impossible to >>> construct incorrect proof verification code. >>> >>> What I am looking for is unbounded RSI capable of increasing intelligence. >>> A Goedel machine doesn't do this because once it finds a solution, it >>> stops. This is the same problem as a chess playing program that plays >>> randomly modified copies of itself in death matches. At some point, it >>> completely solves the chess problem and stops improving. >>> >>> Ideally we should use a scalable test for intelligence such as Legg and >>> Hutter's universal intelligence, which measures expected accumulated reward >>> over a Solomonoff distribution of environments (random programs). We can't >>> compute this exactly because it requires testing an infinite number of >>> environments, but we can approximate it to arbitrary precision by randomly >>> sampling environments. >>> >>> RSI would require a series of increasingly complex test environments >>> because otherwise there is an exact solution such that RSI would stop once >>> found. For any environment with Kolmogorov complexity l, and agent can >>> guess all environments up to length l. But this means that RSI cannot be >>> implemented by a Turing machine because a parent with complexity l cannot >>> test its children because it cannot create environments with complexity >>> greater than l. >>> >>> RSI would be possible with a true source of randomness. A parent could >>> create arbitrarily complex environments by flipping a coin. In practice, we >>> usually ignore the difference between pseudo-random sources and true random >>> sources. But in the context of Turing machines that can execute exponential >>> complexity algorithms efficiently, we can't do this because the child could >>> easily guess the parent's generator, which has low complexity. >>> >>> One could argue that the real universe does have true random sources, such >>> as quantum mechanics. I am not convinced. The universe does have a definite >>> quantum state, but it is not possible to know it because a memory within >>> the universe cannot have more information than the universe. Therefore, any >>> theory of physics must appear random. >>> -- Matt Mahoney, [EMAIL PROTECTED] >>> >>> >>> >>> ----- Original Message ---- >>> From: Abram Demski <[EMAIL PROTECTED]> >>> To: agi@v2.listbox.com >>> Sent: Monday, August 25, 2008 3:30:59 PM >>> Subject: Re: Information theoretic approaches to AGI (was Re: [agi] The >>> Necessity of Embodiment) >>> >>> Matt, >>> >>> What is your opinion on Goedel machines? >>> >>> http://www.idsia.ch/~juergen/goedelmachine.html >>> >>> --Abram >>> >>> On Sun, Aug 24, 2008 at 5:46 PM, Matt Mahoney <[EMAIL PROTECTED]> wrote: >>>> Eric Burton <[EMAIL PROTECTED]> wrote: >>>> >>>> >>>>>>These have profound impacts on AGI design. First, AIXI is (provably) not >>>>>>computable, >>>>>>which means there is no easy shortcut to AGI. Second, universal >>>>>>intelligence is not >>>>>>computable because it requires testing in an infinite number of >>>>>>environments. Since >>>>>>there is no other well accepted test of intelligence above human level, >>>>>>it casts doubt on >>>>>>the main premise of the singularity: that if humans can create agents >>>>>>with greater than >>>>>>human intelligence, then so can they. >>>>> >>>>>I don't know for sure that these statements logically follow from one >>>>>another. >>>> >>>> They don't. I cannot prove that there is no non-evolutionary model of >>>> recursive self improvement (RSI). Nor can I prove that there is. But it is >>>> a question we need to answer before an evolutionary model becomes >>>> technically feasible, because an evolutionary model is definitely >>>> unfriendly. >>>> >>>>>Higher intelligence bootstrapping itself has already been proven on >>>>>Earth. Presumably it can happen in a simulation space as well, right? >>>> >>>> If you mean the evolution of humans, that is not an example of RSI. One >>>> requirement of friendly AI is that an AI cannot alter its human-designed >>>> goals. (Another is that we get the goals right, which is unsolved). >>>> However, in an evolutionary environment, the parents do not get to choose >>>> the goals of their children. Evolution chooses goals that maximize >>>> reproductive fitness, regardless of what you want. >>>> >>>> I have challenged this list as well as the singularity and SL4 lists to >>>> come up with an example of a mathematical, software, biological, or >>>> physical example of RSI, or at least a plausible argument that one could >>>> be created, and nobody has. To qualify, an agent has to modify itself or >>>> create a more intelligent copy of itself according to an intelligence test >>>> chosen by the original. The following are not examples of RSI: >>>> >>>> 1. Evolution of life, including humans. >>>> 2. Emergence of language, culture, writing, communication technology, and >>>> computers. >>>> 3. A chess playing (or tic-tac-toe, or factoring, or SAT solving) program >>>> that makes modified copies of itself by >>>> randomly flipping bits in a compressed representation of its source >>>> code, and playing its copies in death matches. >>>> 4. Selective breeding of children for those that get higher grades in >>>> school. >>>> 5. Genetic engineering of humans for larger brains. >>>> >>>> 1 fails because evolution is smarter than all of human civilization if you >>>> measure intelligence in bits of memory. A model of evolution uses 10^37 >>>> bits (10^10 bits of DNA per cell x 10^14 cells in the human body x 10^10 >>>> humans x 10^3 ratio of biomass to human mass). Human civilization has at >>>> most 10^25 bits (10^15 synapses in the human brain x 10^10 humans). >>>> >>>> 2 fails because individual humans are not getting smarter with each >>>> generation, at least not nearly as fast as civilization is advancing. >>>> Rather, there are more humans, and we are getting better organized through >>>> specialization of tasks. Human brains are not much different than they >>>> were 10,000 years ago. >>>> >>>> 3 fails because there are no known classes of problems that are provably >>>> hard to solve but easy to verify. Tic-tac-toe and chess have bounded >>>> complexity. It has not been proven that factoring is harder than >>>> multiplication. We don't know that P != NP, and even if we did, many >>>> NP-complete problems have special cases that are easy to solve, and we >>>> don't know how to program the parent to avoid these cases through >>>> successive generations. >>>> >>>> 4 fails because there is no evidence that above a certain level (about IQ >>>> 200) that childhood intelligence correlates with adult success. The >>>> problem is that adults of average intelligence can't agree on how success >>>> should be measured*. >>>> >>>> 5 fails for the same reason. >>>> >>>> *For example, the average person recognizes Einstein as a genius not >>>> because they are >>>> awed by his theories of general relativity, but because other people >>>> have said so. If you just read his papers (without understanding their >>>> great insights) and knew that he never learned to drive a car, you might >>>> conclude differently. >>>> >>>> -- Matt Mahoney, [EMAIL PROTECTED] >>>> >>>> >>>> >>>> ------------------------------------------- >>>> agi >>>> Archives: https://www.listbox.com/member/archive/303/=now >>>> RSS Feed: https://www.listbox.com/member/archive/rss/303/ >>>> Modify Your Subscription: https://www.listbox.com/member/?&; >>>> Powered by Listbox: http://www.listbox.com >>>> >>> >>> >>> ------------------------------------------- >>> agi >>> Archives: https://www.listbox.com/member/archive/303/=now >>> RSS Feed: https://www.listbox.com/member/archive/rss/303/ >>> Modify Your Subscription: https://www.listbox.com/member/?&; >>> Powered by Listbox: http://www.listbox.com >>> >>> >>> >>> ------------------------------------------- >>> agi >>> Archives: https://www.listbox.com/member/archive/303/=now >>> RSS Feed: https://www.listbox.com/member/archive/rss/303/ >>> Modify Your Subscription: https://www.listbox.com/member/?&; >>> Powered by Listbox: http://www.listbox.com >>> >> >> >> ------------------------------------------- >> agi >> Archives: https://www.listbox.com/member/archive/303/=now >> RSS Feed: https://www.listbox.com/member/archive/rss/303/ >> Modify Your Subscription: https://www.listbox.com/member/?&; >> Powered by Listbox: http://www.listbox.com >> >> >> >> ------------------------------------------- >> agi >> Archives: https://www.listbox.com/member/archive/303/=now >> RSS Feed: https://www.listbox.com/member/archive/rss/303/ >> Modify Your Subscription: https://www.listbox.com/member/?&; >> Powered by Listbox: http://www.listbox.com >> > ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?&; Powered by Listbox: http://www.listbox.com ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=111637683-c8fa51 Powered by Listbox: http://www.listbox.com
