Slashdot Mirror
Self-Improving Systems
Roland Olsson writes "A relatively easy way to construct "intelligent" systems that improve
themselves practically ad infinitum is described at
http://www-ia.hiof.no/~rolando/SIG/
Maybe Steven Spielberg's AI film is closer to reality than the general
public knows *smile*?"
Please. Two notes on a page? Breakthrough? Hah. It's a hell of a lot tougher than it looks.
Read Koza's three tomes for extensive research on genetic programming (the art of developing programs through genetic-evolutionary techniques).
Read about particle swarms if you want to learn about an evolutionary technique that is quietly kicking the ass of most others wherever it is used.
From a theoretical point of view, this feels like it won't solve or do anything that can't be found within the solution space anyway, by another technique.
if you know what the final correct output should be. what about systems where there are multiple correct and almost-correct values ? i.e. the real world. The real problem is solving problems which dont have one true solution. i.e. recognising an object in a random, slightly blurred photograph from a moving vehicle.
The biggest problem with any genetic system is testing fitness. It has always been that way, and always will. The genetic system can only be as good (regardless of computing power) as the fitness function. Find a way to improve THAT automatically, then you will have true machine intelligence with infinite potential.
a project that took place back in 1996 I think. Programmers wrote a physical environment in which a set of parameters were included (gravity, friction, etc) along with a basic mechanical crawling robot composed of several joints and "muscles". It was left to "evolve" on a machine and actually improved itself to the point of being able to move at something like 5-6mm per second.
Imperium et libertas
Autocracy and freedom
Someone took a GP algorithm and superimposed it on the architecture of an RS Flip-Flop. On the plus side, with all of /.'s traffic, they probably won't have a hard time finding someone to fill that open position at the bottom of the page.
Tired of free ipod spam sigs? Opt ou
The Father of GP (John Koza) may disagree with me - he runs genetic-programming.org and more or less invented the field. He's also known for his vigorous defences of GP: anybody know of real applications?
A somewhat more complete description of GP can be found at Genetic-programming.com.
.sig
Old news! This has already been accomplished:b a7 eadc-03cdf340
http://www.segfault.org/story.phtml?mode=2&id=3
(And it's about time... Dern Perl module Oraperl need fixing by some entity!)
The problem with self-improving programs using Genetic Programming, is that the problem inherent in the process of evolution are present in the programs. When species evolve, it's not always for the better, there have been cases where evolution has made things worser than before.
;-)) with self-improving programs.
This might not be noticable for relatively simply programs, but on a very complex program, how do you tell if a certain modification introduced by the system, is actually an improvement? What if the modifications makes the program slightly faster, but introduces long-term problems?
I think this is one of the biggest problems (other than the programs becoming sentient, and taking over the world
"Knowledge makes us accountable." - Che Guevara
I'm rather fond of how the 'fitness function' is a simple labelled box. Truth of the matter is, this is where all the important (read HARD) stuff happens, and its waved off in the 'a miracle occurs' manner. Cute.
The fitness function amounts to taking your new baby Genertic Algorithm and throwing it into the wildernes filled with GA-eating beasties. Those that manage to survive for more than X amount of time are now determined to be 'fit'.
The catch of course, is that 'fit' for you, and 'fit' for the GA, don't always equate nicely. If a GA decides that it can surive best by eating the rest of your test subjects, well....
If you go look at the page and even begin to think that its a marvelously kean concept, note that people have been failing to get this to work on a large scale for thee past 20 years. Go google on 'genetic algorithms','autonomous agents','self-evolving networks', or just look up exactly how sucessful people are at winning the Loebner prize.
If not, might I suggest getting out more?? :)
"They do not preach that their god will rouse them, a little before the Nuts work loose." Kipling, 'The Sons of Martha'
A Simple Genetic Algorithm: .1 - .01% chance) on the chromosome(genome) to create a new offspring population.
1) Randomly create population of individuals and their genome.
2) Calculate fitness of each individual
3) Probabilistically select individuals for mating, based upon their fitness scores.
4) During Mating, use crossover (usually 70% chance) and mutation (usually
5) If done, then finish, otherwise goto step 2 with the new population.
Using the Genetic Algorithm to evolve new crossover operators seems feasible; however, evolving the mutation operator to produce individuals of higher fitness is flawed logic. Mutation's purpose is to prevent genetic code from becoming "lost" (ie sometimes when you lose genetic information from crossover, you can never get it back w/o random mutations). By evolving the mutation operator to produce individuals of higher fitness, I suspect you will run into the Local Optima problem, where you've reached a local optimum fitness, but you are nowhere the global optimum fitness for the population.
Mutation is very important in preventing the local optimum problem, changing the way mutation works will probably have a detrimental effect on the performance.
Gururuse
ERA Champion Realty, Inc.
The example includes a random function for modifying itself?!? So if the weak program dies, the program tries another random one?
That's brute force, and nature has been doing that since the big-bang-burger-chef.
Also, the ability and drive to improve itself will prove a nececity. Even after this, you would have to make a suitable body and train the new AI system in whatever field it is needed. ;)
It will be quite a while before all those requirements are met, but I expect to have a robotic lab-assistant when i am an old man, so I sure hope they don't stop trying
Does anybody have references to Real World examples of GP being applied and the results, also in real world languages rather than academic languages, ie., C#, C++, Java as opposed to SML, Lisp, Prolog etc?
----- Whats wrong with this picture? http://www.revoh.org:1234/whatswrong
As a practicing AI researcher, I'm as puzzled as some of the other posters about what the news is here. Any decent introductory textbook on AI written in the last few years (I'm currently teaching from the new Nilsson text) has a chapter on GAs and GP. They have much promise, but other standard AI techniques work much better on almost all practical problems.
Let's try to keep the "news", and not just the "for nerds," folks...
GP is useful, as all of Artificial Evolution methods, in the context of optimisatiion, eg, scheduling, place and route, filter design, neural net training.
Unfortunately, GP and GA do not scale up too well, modularity is not being achieved. There is no easy way to define fitness for subroutines (ADFs in KozaSpeak). I believe this is the main reason why the field is stagnating.
This is not a signature.
I've experimented with some of this myself during my free time. It was nothing incredibly complex, however I used the basic concepts of protein synthesis and enzyme function to operate on a 'DNA' code base that was dynamically mutated and generated.
While the 'enzymes' and 'proteins' were fixed during my experiments, they certainly could be mutated and evolved in more advanced versions of my programs.
An interesting side effect was that as a strain of 'DNA' evolved it became longer and longer. Upon tracing advanced mutations I found large sections of the genes to go completely unused.
Anyhow, what I menat to get to was that a model like this could certainly be distributed much like Bovine or SETI. A central server distributes 'DNA' to the client machines as well as a series of environmental test suites to measure their development. The client machines would iterate the DNA code through the test environment and mutate (or even breed) successors to the original DNA so as to discover a more efficient GA. The result set as well as the DNA fragments would then be transmitted back to the Server for analysis, processing and ultimately re-distribution.
An additional benefit of this approach would be that if a single genome is sucessful on a large number of systems it would be relatively easy to identify.
While my inital experiments were written in C, I eventually migrated to C++ (which actually made it much more complex.) However for a distributed client, the use of java would likely be the most efficient, espesially for the distribution of the testing environments.
I'm done with sigs. Sigs are lame.
Is it possible to code self modifying code in C# using Reflection?
C# is at a very high level and thus can focus more on algorithms rather than the nitty gritty of memory management (like Java).
----- Whats wrong with this picture? http://www.revoh.org:1234/whatswrong
Like two halves of the brain, with feedback between them, each doing it's own thing but propagating it's findings to the other. Eternal feedback!
I can find the pictures, read the text, but EE is not my cake. So maybe someone could explain it?
Folks have been doing this for decades. The hard part is the fitness function. If you can get a computer to distinguish between "good" and "bad" (ie, detect what constitutes an "improvement" in the general case, without a human leaning over its shoulder giving it precise parameters to look for) then you'll really have something. That is the component that all of our "self-improving" systems lack.
-- Guges --
So many of these formalisms seem to rely on pushing all the hard stuff into a magic black box: "A miracle appears here." Of course, one shouldn't trivialize the state of research; we usually only make progress in little steps. Then later on, we look back and say "Oh! This little step was actually a big one."
-- We all have enough strength to endure the misfortunes of other people. La Rochefoucauld
Check out the GA Archive. Great collection of the more famous GA's and proceedings.
For those wishing to get an intro to GA, try The Hitchhiker's Guide to Evolutionary Computation.
The General public didn't see AI; they heard it sucked. They heard it from me.
In college, I did a project in which I attempted to evolve programs for Core Wars, in which two programs running in a virtual machine language basically attempt to overwrite each other's memory space.
My algorithm started with random programs and pitted them against each other in the Core Wars arena. The fitness function was simple: programs that beat other programs got higher ratings. Top-rated programs would "breed", and all programs would mutate. The hope was that after time, successful warriors would evolve.
And, lo and behold, they did! My algorithm "evolved" some simple bombers -- not nearly as good as what a human would write, but amazing considering I put no knowledge about strategy into the algorithm, and started with random core wars code.
Ah, but (there's always a but) I found that there was no significant correlation between how successful a warrior was and how many generations of crossover went into it. In other words, the genetic algorithm did no better than an algorithm which simply selected lots of random programs and kept the ones that work. So actually, my result was not very impressive at all -- I was basically doing a brute force random search for programs, and happened to find a few.
Others might get much better results with different languages, because Core Wars machine code does not lend itself to crossover (i.e. it's had to merge two Core Wars programs into a better program). Functional languages do a bit better with this. But I really doubt that Genetic Algorithms will prove useful in the near future for generating any sort of code that wouldn't be trivially easy for a human to write.
...at GECCO 01. His work was done within a language particularly well-suited to the task: http://helios.hampshire.edu/lspector/pubs/ace.pdf
I cant but help notice the lack of trolls, flames etc in this topic as I guess most idiots are out on this Saturday night getting piss blind drunk :)
:D
And as for the rest of us nerds, we are sitting in here reading slashdot (news for nerds)
----- Whats wrong with this picture? http://www.revoh.org:1234/whatswrong
[insert joke about Microsoft OS's needing this software here]
I posted to
Not only has a lot of my lifetime been spent dealing with anal subjects, it has
also been some of my most memory-worthy experiences. I simply love to take a
dump, to shit, to have the content of my bowels plump noisily into the toilet
beneath my fat ass. When I eat something I really like, I try to imagine its
way through my system, how its transformed and how long it takes before it
reaches the outside again. The only way you can test its time cycle, is by
eating stuff which is not digestible. Last time I checked, the carrots I ate at
7 p.m. were part of my morning shit at 8:30 a.m., which is approximately 13-14
hours. Meat takes longer, Ive heard. Meat-eating people are supposed to carry
2-3 kgs of stinking, old and still not digested meat on their intestine-walls. Interesting to do a lavement on a seriously meatloving person!
My sister once ate two coloured wood-bricks when she was very little. They didnt come out in their original, rectangular shape covered with blue and red polish. Her shit was just shit. Our mum went through it every day for two weeks. She stirred it with a cotton swab. The look on her face indicated that she wished for x-ray eyes. She could have asked me to do it. I was standing beside her anyway, closely following her unsuccesful project with my nose almost down the pottie. Unsuccesful because what she expected to find, never appeared. No wooden bricks in original condition, covered with shit. Finally she gave up. This was my first scientific discovery. The human body is capable of digesting wooden toys, but not carrots. Fucking amazing ! Fucking fascinating !
For my birthday I want a pair of electronic scales with 1 gram preciseness. Then my project will be to keep a more strict account on what I eat and how much comes out. Maybe there is a huge amount of "lost" food, simply disappearing on its way through. It would be great, wouldnt it ? New scientific accounts.
When I was a child, around the age of maybe 8-10, I began to find big interest in having my younger sister with me when I went to the toilet to shit. I didnt want her to check out what I had delivered, it was just comfortable; me at the toilet, her on the floor. We talked privately and if it smelled like hell, I dont even think we noticed. It was the most intimate times we spent together during those years. Now we dont see each other so often, but when we do, we repeat our little ritual. Even though we both laugh because it seems stupid, maybe even disgusting, what do I know, we both enjoy it with a mutual understanding, that brings us back to some peaceful memories from our childhood.
In my adult life my dealing with my shit-fascination has changed. Its pure form has been censured by for instance cultural norms. Nobody talks about it when theyve left their childhood. It becomes a taboo when you reach a certain age. Thats sad, I think. The more a subject is submitted taboos, the more I feel an urge to discuss it, relate to it. It becomes an issue in my life, I deal with it every day. But not in a relaxed way. I giggle when I talk to others about the inevitable subject shitting.
A common misconception is that genetic algorithms are based on mutations. For example someone here said:
random mutations used in genetic programming are about as efficient as real random mutations. They get the job done eventually, but require a lot of screw-ups to make one improvement.
Mutations are a red herring. Genetic algorithms produce results faster without mutations. The benefit of mutations is that they allow the search to go farther - potentially indefinitely - and produce better results.
The power of genetic algorithms comes from impicit parallelism. This can increase the search rate by a factor of over a billion. There is a complicated mathematical anaylsis, but here is a description:
one of a genetic algorithm's most important qualities is its ability to evaluate many possible solutions simultaneously. This ability, called implicit parallelism, is the cornerstone of the genetic algorithm's power. Implicit parallelism results from simultaneous evaluation of the numerous building blocks that comprise the string. Each string may contain millions of these building blocks, and the genetic algorithm assesses them all simultaneously each time it calculates the string's fitness. In effect, the algorithm selects for patterns inside the string that exhibit high worth and passes these building blocks on to the next generation.
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
(quote) Windows couldn't improve itself even if it wanted to! (end quote)
Well, at least Windows got the mutation portion working fine.
Table-ized A.I.
Regardless of the intelligence of any computer in the future, I wouldn't consider voice interaction a useful feature. As for me, I can type much faster than I speak, and talking eight hours straight to my computer would not decrease my work-load in any way. :)
I think this voice control thingy stems from this old, rather male, dream in which one commands his secretary to do all kind of nasty things. I mean, who really needs two free hands?
It will delete stuff.
check out my page:
www.contrib.andrew.cmu.edu/~sager
Back in 1992, I predicted MMORPG from muds(tried to make one too www.ebayrp.bizland.com), 1 auction site, and instant messaging(who didn't though)....
I can see it being done in 10 if some corporation attempts it. But I know it will happen within 20, or the whole of humanity is just plain stupid.
I am not so sure we'll be seeing androids because of construction difficulties, but who knows.
God spoke to me
The growth of the proportion of introns (genetic code which does not directly influence the fitness function) to exons ("relevant" genetic information) as the fitness of the individual grows is a reasonably well-documented phenomenon in GP communities, and is commonly called bloat. "Relevant" because, despite conclusive evidence, most researchers believe that the introns are also relevant to the individual, even if not directly.
For example, mutations can occur on introns without any direct change to the individual. As introns are comprised essentially of copies or parts of original genetic code, they probably provide a place where mutations to possibly beneficial (albeit inactive) genes can occur safely.
Besides that, as bloat increases, the active genetic code decreases in proportion, and as a result you get a kind of 'clustering' of active genes, which is a good thing, because the chances of a disrupting crossing-over go down.
A great book on the subject is Genetic Algorithms + Data Structures = Evolution Programs, by Zbigniew Michalewicz (but I'm not sure if he covers bloat in the text). I remember reading a paper on bloat in one of the Springer-Verlag Lecture Notes on Computer Science about Genetic Programming.
Now, to see some really wacky and interesting things, the book to read is Evolutionary Design by Computers, edited by Peter Bentley, with lots of nice papers to read (and a kickass foreword from THE MAN Richard Dawkins)
Links for the paranoid:p ?theisbn=3540606769&vm=p ?theisbn=155860605X&vm=
http://www1.fatbrain.com/asp/bookinfo/bookinfo.as
http://www1.fatbrain.com/asp/bookinfo/bookinfo.as
Carlos
This got me intrigued, so I hopped on to Google, and, lo and behold, this is what I found. Probably one of the more interesting works that I have read online in quite some time, although there were parts that I didn't understand since I haven't yet taken enough coursees in high math to properly comprehend them.
--sdem
"#> echo I am pleased to have joined the Earth as the second sentient race."
And the other sentient race would be...?
...since the seventies. *yawn*
Number of descendants that are _fit_ is the definition of fitness. :->
Having 20 children that all die before having children of their own doesn't make you fit.
My Journal
Maybe Steven Spielberg's AI film is closer to reality than the general public knows *smile*?"
It was more of a Kubrick film than Spielberg's. I mean seriously... Give the man some friggin credit!
--Chemguru
As other readers have pointed out, this is nothing new. John Holland originated the genetic algorithm idea in around 1970's (his book, "Adaptation in Natural and Artificial Systems", was first published in 1975). Then John Koza extends this idea to genetic programming (the first volume of his "Genetic Programming" series came out in 1992). It's still under a lot of research. But there are quite a number of people, most notably Marvin Minsky, that argue that this approach won't be the cure-all and solve-all for the problem of achieving artificial human-level intelligence within a reasonable timeframe (around 50 years from now), which the movie AI exhibits. The argument draws from the evolution of life itself. How long did it take from the first lifeforms to the first human species? In the order of million, if not billion, of years certainly. The point is, it's going to take a heck lot of time for this kind of programs to truly achieve our (human's) level of intelligence, if it's possible at all. Not to say that the technique is not useful--it has been applied in a number of applications. But if we're looking for human-level intelligence, it alone would barely solve the problem.
Sorry, nothing further to add.
Except that if that doesn't pan out and you are still looking for an interesting project, you may want to check out Bluebox. (Something about a universal internet language.)
"Be thankful you are not my student. You would not get a high grade for such a design
this has to be the worst article i have ever seen on slashdot. is this a joke? a undergrad course in ai at any uni will give you a thousand times the info in this "article". give me a break
how about the code that added all of the return values from 10 system calls and then returned success or error if the sum was != 0 ?
I wrote to the patent holder to see if I could use GP in a GPL'd project (offered him a big chunk of my prize money if my project panned out), and after suggesting I publish my results if I get anywhere instead, he totally blew me off. The project in question was a "go/igo/weichi/baduk AI", a really challenging artificial intelligence problem that has eluded many. I'm actually more interested in giving away my code than the prize money though.
So you can probably assume that where OSS and FS are concerned, this guy isn't interested, although maybe if you're project doesn't have prize money involved, he might react differently; I don't know. I'm beginning to think lawyers tell their clients not to tip their hand either way where patents are concerned, because it seems there's a big vacuum surrounding FS/OSS and patents. :(
I believe the patent in question is 4,935,877.
MAC | A polar bear is a cartesian bear after a coordinate transform.
MAC | A polar bear is a cartesian bear after a coordinate transform.
Not quite. Mankind has directed the evolution of many species for a long time: cross pollenating to produce hardier plants, selectively breeding animals for strength, speed, shape, etc. We have husbandry records dating back farther than most people can trace their own ancestry.
"I'm not impatient. I just hate waiting." - My Dad
a competitive co-evolutionary system that plied a system evolving sorting networks against systems that evolved difficult datasets.
:)
Yes, that's probably where I first heard the term parasites in relation to GA. You are correct the technique doesn't quite match the decription I gave.
One of the issues in GA is maintaining diversity.
In reading about biology there is strong evidence that parasites have been one of the major driving forces in creating diversity, and the reason for sexual reproduction itself (as opposed to asexual, which would ordinarily be more efficient). I made the obvious connection, and I assumed this technique was part of the literature. I just did a moderate search and it doesn't seem to be there.
While I haven't actually co-evolved parasites, I have added a 'virtual' parasite cost based on similarity. It was extremely effective.
Maybe I should write a paper on it
The notion of "fleeing parasitic programs" is, as far as I know, a fantasy.
You're right in that I don't see it in the literature, but the result is obvious if you understand GA. The main population would converge and the parasites would be drawn there. The parasites would turn the local optimum into a local minimum and the main population would "flee" the minimum.
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Check out http://www.isd.atr.co.jp/~ray/tierra/ to read about Tierra, the first time evolution was used to grow programs.
Ultimately, Ray used this to try to evolve complex parallel processing programs.
The evolutionary process will be introduced into the context of the global computer network, internet. The objective is to evolve complex MIMD distributed processes.
Neat stuff. Check it out.
S.
Spootnik ought to do some self-improvement and stop ripping off Usenet posts.
Moderators: this is more plagiarism from Spootnik. Remember the name: "Plagiarist Spootnik"!