Course:CPSC522/Self Improving Machines

Self-Improving Machines

Self-improving machines as literally refer to machines that capable of improving itself over time.

Principal Author: Wenyi Wang
Collaborators:

Abstract

Self-improving machines as literally refer to machines that capable of improving itself over time. In this page, we focus on recursively self-improving (RSI) machines that not only perform better with time, but getting better at getting better. We will discuss two papers: Steunebrink and Schmidhuber (2011) and Yampolskiy (2014) . The first paper describes a particular type of RSI machines, i.e. the Gödel machine. And the second paper provides a higher-level review and analysis of RSI systems.

Builds on

The self-improving machine is an approach to Artificial Intelligence, and particularly proposed for Artificial General Intelligence.

Related Pages

The self-improving machine is highly related to Reinforcement Learning and Metalearning.

Content

Introduction

As early as year 1950, Turning proposed that to build a machine with human-level intelligence, instead of simulating the adult mind, an alternative approach is to produce a machine with children’s level of intelligence and learning capability, and educate it to achieve adult-level intelligence . This kind of self-improving approach is particularly interesting for AGI researchers since many of them believed that a general propose system would be adequately complex so that it cannot be hard coded, therefore need to be discovered by machines. The concept self-improving machines include a board family of systems including systems that simply optimize a fixed set of parameters, non-parametric algorithms, and various kinds of metalearning methods. In this page, we are particularly interested in recursively self-improving (RSI) machines, which improve the system’s ability of self-improving iteratively. With this property, the system has potential to completely rewrite its original implementation, and take completely different approaches . This leads to the idea of intelligence explosion.

Paper 1: A Family of Gödel Machine Implementations

The Gödel machine is originally proposed in Schmidhuber’s (one of the authors of this paper) previous work . It is a universal problem solver that may interacts with some partially observable unknown environment, and optimize a given utility. In this paper, they adapt the expected cumulative future reward utility. A Gödel machine arbitrarily rewrites any parts of itself if the rewrite is proved to be useful. The proof procedure requires evaluating the machine itself; therefore a Gödel machine is a self-referential machine. The Gödel machine are proved to be globally optimal. In this paper, they refine inconvenient component of the original Gödel machine definition in the implementation aspect, and describe different approaches of attaining self-reflectivity for implementing a Gödel machine.

A Gödel machine consists two parts: a solver and a searcher. The solver is a program that interacts the environment. The searcher is a program that tries to find a provably improving rewrite of both the solver and the searcher. The main topic of this paper is on how to construct a target theorem of proving a given rewrite is an improvement so that the searcher is implementable.

The Utility Function and Target Theorem

Consider a utility function that measure the goodness of a given program $s$ for an environment $env$ state in the following form.

$u(s,env)=\mathbb {E} _{\mu }[\sum _{t=time}^{T}r(t)|env],$

where $\mu$ is an environment distribution that describes the probabilistic dynamics of the environment, $T$ equals machine’s life time, $time$ equals the current time, and $r$ is the reward of a time based on the program state and environment at the time. Note that the terms $\mu ,T,time$ and $r$ are part of the utility function $u$, although any program $s$ that represents a Gödel machine encodes possibly different values of these terms. Another clarification needs to be made is that times $T$ and $time$ do not relate to the interactive steps between the machine and environment but the step’s for the machine performs internal computational operations. The goal of a Gödel machine initially is to optimize $u(s,Env)$ for current $s$ and $Env$ with the true unknown environment distribution $\mu$ and user defined $T,t,r$. Since all $T,t,r$ and $\mu$ are encoded in the Gödel machine and the Gödel machine may rewrite arbitrary part of its code, the machine will not directly optimize the originally defined objective function, but the objective function encoded in the current version of the Gödel machine. Because of the difficulty of implementation and conceptual understanding, in this work they extend the utility function with the concept of continuation .

Within a computational platform, a continuation states what is going to be executed next. An example is illustrated from the paper. “For example, suppose the current continuation is {A(); if B() then C() else D()}; this continuation specifies that the next thing to be done is expanding A and executing its body, and then the conditional statement will be executed, which means that first B will be expanded and depending on its result, either C or D will be expanded. Note that before executing B, it is not clear yet whether C or D will be executed in the future; so it makes no sense to expand either of them before we know the result of B.” With this definition of continuation, the utility function encoded in program ${\bar {s}}$ is rewritten as a function of program state $s$ and continuation $c$

$u_{\bar {s}}(s,c)=\mathbb {E} _{\mu _{s},M_{s}}[u'],{\text{where }}u'(env)=r_{\bar {s}}(s,env)+\mathbb {E} _{\kappa _{c},K_{c}}[u_{\bar {s}}|env],$

$\mu _{s}$ and $M_{s}$ represent the environment distribution encoded in $s$, and $\kappa _{c}$ and $K_{c}$ are the program-continuation pair encoded in $c$.

Based on the new utility function, they introduce a target theorem that explicitly includes a program rewrite function $switchprog()$. The utility of rewrite the program using $switchprog()$ at time $t$ with expected future program state before time $t$ equals $s$ is formulated as $u_{\bar {s}}(s,\{waitUntil(t),switchprog()\})$ with evaluating program (e.g. the current program) ${\bar {s}}$. Denote "proceeding following program s" by continuation $scheduler_{s}()$. A target theorem to show a rewrite is an improvement is constructed as

$tt_{\bar {s}}(s,t,switchprog())=[u_{\bar {s}}(s,\{waitUntil(t),switchprog()\})>u_{\bar {s}}(s,\{scheduler_{s}()\})].$

Intuitively the target theorem being true means that utility of applying the rewrite is greater than then utility of continuing with the same program.

Self-Referential Implementation

As we mentioned above, a programming language with self-referential construction is needed for a Gödel machine implementation. In the discussion and conclusion section of this paper, meta-circular evaluators as an existing technique for attaining self-reflexivity is stated. A meta-circular evaluator is an interpreter that interprets its own source code. They propose that double nesting of meta-circular evaluators can be used to realize a Gödel machine's self-evaluation and self-modification. Although in theory such technique is sufficient for the Gödel machine, a practically efficient way is to implement a Gödel machine directly in an assembly language.

Paper 2: From Seed AI to Technological Singularity via Recursively Self-Improving Software

Self-improving systems has been dreamed since the early days of computer science and artificial intelligence. This paper provides definitions and classifies types for self-improving software, and particularly focused on RSI systems. Since there was no working RSI software exists, the paper analysis RSI systems conceptually. This paper may serve as a guideline for future RSI system development.

Definitions and Types of Self-Improvement

Self-improving software products allow for some optimization or customization of the product. Non-recursive optimization processes proposed by Yudkowsky is a common class of self-improving systems. The non-recursive optimization refers to a situation that one component of the system is optimized by the other part. A concept, the law of diminishing returns, is introduced as a common phenomenon for self-improving systems. It refers to the behavior that a self-improving system quickly discovers the "low-hanging fruits", and further improvements are less frequent and less significant. It is common that a Non-recursive optimization process quickly fails into the law of diminishing. RSI systems is hypothesized to overcome this issue.

Recursive self-improving systems create new software iteratively. The newly created software should be better at creating future software. Chalmers' proportionality thesis hypothesizes that increases in the capability of designing future intelligent systems is propositional to the increases in intelligence. With this hypothesis he shows if a process iteratively generate a greater intelligent system using current system, this process leads to superintelligence. One classification of the RSI software is based on number of possible improvements. The hope is that meaningful RSI systems will be able to make many improvements. Possibilities of infinite number of improvements and upper bound of intelligence remain as open questions.

Another way to classify RSI systems is to distinguish how the improvements are found. One approach is to consider a set of possible source codes and to prove one of them is an improvement. Another approach is to use the system's capability of designing and testing for producing the newer version of the system. There is an existing phenomena considerable as a hybrid RSI system: the the collaboration of artificial intelligence system and human scientists. The combinations of human and artificial intelligence achieved significant success in many regions.

Limits of RSI Systems

The first type of limits relies on physical restrictions. Such restrictions include speed of light, uncertainty principle and other physical laws we many not know. Similar limits has been studied for human brains. However we are far from reaching these limits. Another type of limits are based on computability. Results of non computable problems and non polynomial problems apply to RSI systems. Limits developed for general artificial intelligence also apply to RSI systems. As an example, Wiedermann classifies cognitive systems using Arithmetic Hierarchies . He argues that the human intelligence are upper bounded by the $\Sigma _{2}$ class of hierarchy, and a machine's intelligence should be bounded by the level of hierarchy limited by its computational limits.

Beside the limits that apply to more general problems, many specific limits are developed for RSI systems. Two limits are discussed for RSI systems in general. One attempt is to prove a RSI process is impossible by contradiction. Assume program $P_{1}$ is capable of solving problems with maximum difficulty of $X_{1}$. Let $P_{2}$ be a machine generated by $P_{1}$ that is capable of solving a problem $Q$ with difficulty $X_{2}>X_{1}$. This is a contradiction since $P_{1}$ solves $Q$ with difficulty greater than $X_{1}$ via $P_{2}$. Another more precise limit made by Mahoney is that for a family of goal orientated RSI systems, he proves the algorithmic complexity of a improving sequence of programs is $O(logn)$ .

Other obstacles that might be faced when designing a particular class of RSI systems is discussed: Löb's theorem states that a formal system contains arithmetic is either inconsistent or not sound ; "Errors which are not detrimental to system's performance are very hard to detect and may accumulate from generation to generation ... until a critical mass" leads to irreversible failures; A system with lower level of intelligence may not able to understand higher intelligence; A system may not able to predict itself without ruining it.

RSI Convergence Theory

The RSI convergence theory is about the limiting behavior of RSI systems. A possibility is that all intelligent enough RSI systems will converge to the same software architecture. It is also possible that an upper bound of intelligence exists, so that all RSI systems eventually converge to the same level of intelligence. Alternatively, intelligence might be an unbounded property, and RSI system does not converge. If the RSI systems converge to be equal in some sense, it may lead to creation of a Singleton, i.e. a single system that controls everything , since all the RSI systems may recognize them as a single agent due to their equalities. It is also arguable that humanity is on the early path of converging with a slow speed.

Discussion

From the author of this paper's perspective, it is questionable that how would the initial utility function of a Gödel machine be evaluated since the model assumes unknown environment dynamics. If one uses the current estimation of environment dynamics, the Gödel machine may modify the reward function such that the modified version of reward function is equivalent to the user defined reward function in the sense of optimization with current estimation environment dynamics but not equivalent with the true environment dynamics. Then in the future when the estimation of environment dynamics being correct, the utility function defined by the estimation of environment dynamics and reward function is no longer correct. It is also questionable that why there is no working implementation of Gödel machine exists.

The second paper provides useful tools and scopes to analysis Gödel machines. For example, dose the Löb's theorem tell us a Gödel machine with a sound and consistent target theorem proof searcher cannot include arithmetic? On the other hand, the Gödel machine provide a useful framework for answering questions or testing hypotheses mentioned in paper two, i.e. with the precisely defined architecture, one may be able to analyze its convergence for particular problems.

To Add

Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.