This impressive augmented reality demo from GE inserts computer-generated 3D objects into live video. First, watch the short video. Then, try it yourself.
Israeli musician “Kutiman” took a big pile of seemingly random YouTube video clips and used them as instruments in his own musical compositions. I could not stop listening to these. My favorites are tracks 2 and 3. His site is overloaded at the time of this post; for now you can see samples here, here, and here.
Can you be an awesome DJ using nothing but a web browser and your computer’s keyboard? Yes you can.
instantwatcher.com – “Netflix for impatient people”. A remix of the Netflix site that is “about a quadrillion times easier to browse than Netflix’s own site”.
Cursebird. A real time feed of people swearing on Twitter. THANK YOU, INTERNET!
Leapfish. An interesting new meta-search engine with a clean interface. “It’s OK, you’re not cheating on Google.”
Twittersheep. “Enter your twitter username to see a tag cloud from the ‘bios’ of your twitter flock.”
PWN! YouTube. This is a great idea. You just type “pwn” in front of “youtube” in the URL, and voila; instant links for downloading and saving the videos.
Roger Alsing’s idea is to start with a random pile of polygons. Random mutations are applied to the polygons. The result is compared to the Mona Lisa source image, and mutations resulting in improvements are kept. Over many generations, the evolved image begins to resemble the Mona Lisa.
This site evolves music by generating loops randomly from sounds and effects. Listeners to the site’s audio streams rank the results, and the genetic algorithm creates “baby loops” for the listeners to rank.
CSS Evolve
This site shows you variations of a web site’s cascading style sheets. You pick the best results, and their genetic algorithm breeds them to create new styles for the web site.
You never know… a random walk may lead to serendipity.
Today’s xkcd comic is well-timed because just yesterday I sent out an announcement of the availability of my implementation of Cartesian Genetic Programming for ECJ, a Java-based evolutionary computing software framework. Genetic programming (GP) is a problem-solving technique in computer science that is inspired by evolution in biology. You start with a population of randomized computer programs and measure the “fitness” of each program. The fitness is a measurement of how well a program solves a particular problem. You can think of the program itself as the “gene”.
In this simulation of evolution, the best programs in the bunch are selected for “breeding” for the next generations. Breeding is done by exchanging pieces of genetic material – in this case, we exchange pieces of the computer programs themselves. Good programs have different parts that are useful, and these parts are combined or exchanged in new “child” programs that are even better than their parents. Then, every so often, random mutations are introduced into the programs to promote diversity. Good mutations survive to future generations, and bad ones die out.
Parent programs producing offspring by exchanging pieces of themselves. Credit: Michael Adam Lones, Enzyme Genetic Programming
This sounds like a completely random way to solve a problem, but it is surprisingly effective for many kinds of problems, such as learning mathematical expressions that can describe some data set, discovering winning game-playing strategies, making forecasts and predictions from data sets, learning decision trees to classify data, evolving emergent behavior, and optimization of complex systems. Of great interest to me in applying genetic programming is the emergence of unique and fascinating solutions that are not likely to be conceived by human minds.
Cartesian Genetic Programming (CGP), the genetic programming technique I implemented for ECJ, is a variation of genetic programming invented by Julian Miller. CGP uses simple lists of numbers to represent the programs (most GP implementations use some kind of explicit tree representation). It has some interesting benefits over traditional tree-based genetic programs, such as improved search performance, reduced overhead, and less “bloat” in generated programs. My implementation includes some sample problems: regression (fitting a bunch of data to an equation), classification (identifying a species of iris flower based on simple measurements of its parts, or predicting if a breast cancer tumor will be benign or malignant), and parity (counting the number of “on” bits in a binary string).
The iris classification problem is a classic machine learning problem, dating all the way back to 1936. You have a set of measurements taken from various kinds of iris flowers, and your task is to figure out which species it is: iris virginica, iris versicolor, or iris setosa.
From left to right: iris virginica, iris versicolor, and iris setosa.
Starting with randomized programs, one of my CGP tests evolved the following programs (expressions) which correctly classified about 95% of the irises:
I don’t expect you to be able to read and understand the expressions – they are in a format that isn’t easy to read! What’s more important is that I didn’t have to create them myself – the CGP algorithm discovered them for me using only the input data (iris measurements) and the fitness function (a measurement of how many irises were correctly identified).
CGP also had good results when I tested the Wisconsin breast cancer data set. This data set contains measurements taken from fine needle biopsies of suspicious breast lumps. Our task is to predict whether the lumps are benign or malignant using only the measurements.
Fine needle aspiration. A thin needle is used to sample material from a suspicious lump in a breast. The data set contains the microscopic measurements taken from the sampled material.
CGP evolved the following program that correctly diagnoses the tumors 95% of the time:
Again, using only a fitness function and some test data, we are able to evolve a highly accurate cancer diagnosis tool.
Seems too good to be true? Well, it can be. Overfitting is a big problem when evolving these kinds of classifiers. For example, if each of the malignant tumor patients happened to be wearing red shoes during the biopsy (and the shoe type was included in the data set), a machine might be inclined to think that wearing red shoes was what determined the diagnosis. So, the evolved classifier is going to be very sensitive to whatever data set you unleash it upon.
Oh and then there’s the whole “no free lunch” thing. But that’s a depressing topic for another time.
If you want to find out more about my CGP implementation, check out the documentation. If you want to give it a whirl yourself, grab the distribution (you need at least Java 1.5). Check out the ECJ project page for more info about the evolutionary software framework my CGP implementation uses.
Give Up and Use Tables
"We've scientifically determined the max amount of time that you should need to make a layout work in CSS: 47 minutes. When your time is up, we'll even give you the table code you need. Take 3 minutes to build a table. Bill the client for an hour. Done."
reCAPTCHA: Stop Spam, Read Books
This is an interesting idea: Digitize books by filling out CAPTCHAs (those cryptic words you have to type in to prove you are a human being)
T-SQL is a database-centric programming language for Microsoft SQL Server. It is used primarily for data processing, not for such geekery as drawing fractals. So, my hat’s off to the creative re-imagining of this previously dull language.
Take Stanford’s iPhone Programming Class For Free – I would love to take this class. The internet-connected iPhone’s multi-touch interface and powerful multimedia features provide an amazing playground for programmers, if you can stomach Apple’s strong-armed policies on application distribution in the App Store. (BTW here is a site that tracks activity of iPhone apps in the App Store, and posts information about apps that aren’t yet available in the App Store: apptism.com).
bitalizer – bending bits into structure – Upload a file, and this site will turn its binary contents into a simple set of rules governing an interesting image rendering process.
A visualization of the bits that make up the common “shell32.dll” library file found on Windows machines.
The Pomegranate Phone – A really well-done marketing campaign for a new touch-screen GPS-enabled smartphone that also makes coffee, projects video, instantly translates your voice into other languages, has a built-in shaver, and works as a harmonica. And doesn’t really exist. Instead, it is an elaborate ad campaign created by the Nova Scotia government to generate interest for the Canadian province. The little videos included in the ad are a good touch.
MTV Music – huge archive of linkable and embeddable music videos. Finally! MTV does something music-related!
Roanoke Robotics Society and Club – We actually have a Robotics club in little ol’ Roanoke? Very surprising! In fact, they are hosting a robotics competition event at our science museum this Saturday. We’re definitely taking Iris to this!
Paris Hilton In Space – “Paris Hilton will be among the passengers on Richard Branson’s first Virgin spaceflight.” OK, this article just made space less cool. We send enough junk into space as it is.
This morning on AOL instant messenger, I got hit with some bizarre messages out of the blue:
kemptcoho: Let's look at the world with respect to theta.
doranchak: ok, let's do that
kemptcoho: what up
kemptcoho: so who is this?
doranchak: i was going to ask you the same thing
kemptcoho: and why am I your fellow prisoner? ha
kemptcoho: and I am Adam...
doranchak: adam who?
kemptcoho: Well now if I give everything away with nothing back then where is the fun?
kemptcoho: remember you sent me a message first...
doranchak: no, i didn't doranchak: you did
kemptcoho: [06:36] DecayingCoho: Hello, my fellow prisoner!
[06:36] JudgeKaos: what up
What the hell???
So, I start thinking, maybe this was one of those AIM robots. This type of chat robot scrapes messages from blog posts and other online content. The robot then sends one of these messages to a person via AIM. If the person responds, the robot sends the response to some other person on AIM. When THAT person responds, the message is funneled back to the first person. And so it goes, causing all sorts of confusion.
Here’s where I start to wise up on what’s happening:
doranchak: oooh doranchak: are you a trout bot? (Ed.: A trout bot is a variation of TheGreatHatsby)
kemptcoho: no....
doranchak: prove it 🙂 doranchak: ahh doranchak: you're a coho bot doranchak: my mistake 🙂
kemptcoho: and one proves they are not a bot how?
doranchak: that's a good existential question
kemptcoho: so you still haven't given me any indication as to who you are...
doranchak: my mommy told me not to talk to strangers
kemptcoho: or where I would know you from and what would prompt you to message me
doranchak: hey, whoever's on the other end of this: look up "coho bots" on wikipedia doranchak: there's a bot funneling our responses back and forth to each other
kemptcoho: nice so we were put in touch by a bot how wonderful
doranchak: yeah, these bots are annoying, aren't they?
kemptcoho: very much so
kemptcoho: I was wondering why someone just messaged me outta the blue
doranchak: yeah, i was wondering that too
kemptcoho: I figured it was someone from the overnight forums at crackberry
doranchak: did you post "Let's look at the world with respect to theta." somewhere online? doranchak: the bot scrapes messages like that to fool people into thinking they are talking to real people
kemptcoho: cant say that I did
doranchak: i wonder where it found that message
kemptcoho: so you are a real person?
doranchak: yeah; "kemptcoho" is the bot. it has two chats going on at once: one with me, and one with you. it's taking my messages to it and passing them along to you, and vice-versa.
kemptcoho: one word
kemptcoho: ANNOYING!
doranchak: agreed. 🙂 doranchak: well, nice chatting with you anyway. have a good day!
What a waste of time. But it was interesting to experience the scam. I think a lot of people get really angry when they experience the bot since it seems like some weirdo is stalking them (this is kind of what I felt at the beginning of the conversation above).
The Atlanta trip was a lot of fun. We stayed in a really nice rental house not far from Turner Field. The McCubbins managed to put up with me for a week and even went so far as to make dinner for me on several occasions. You haven’t had a good meal until you’ve tried their cooking. Mmm, tuna bites, fruit and goat cheese salad, steak, and black bottomed cupcakes. Our friends Jon and Kate are also accomplished cooks – we should host a cookoff between both couples so we can reap the delicious benefits.
Our rental house
Between home-cooked meals we sampled a variety of Atlanta dining options. Chris and I ate at Gladys and Rons Chicken and Waffles, a restaurant chain started by Gladys Knight that serves the most delicious fried chicken and waffles I’ve ever had. The waffles are warm and soft on the inside and nice and crispy on the outside. Perfect. And eating there has only amplified my weakness for fried chicken. I also managed to meet up with the Atlanta-based contingent of my LegalEdge coworkers at the Vortex Bar and Grill. While I did not sample the infamous bypass burgers, I did partake of the big-ass mushroom swiss burger, and my brain’s burger receptors were alight with glee. This celebration of manliness was a mere coverup for the earlier, emasculating experience of eating at the American Girl Boutique and Bistro to celebrate Eris’ fifth birthday. Despite the pink/pastel surroundings, bad service, and proliferation of little girls tending to their creepy shark-eyed dolls, we had a great time and the food was really good.
We checked out the Georgia Aquarium and World of Coca Cola during our stay. The aquarium is fantastic; definitely a must-see. The whale shark tank there is a massive, imposing, wondrous display. The Coca Cola museum is fun but they really hammer you with Coca Cola propaganda while you are there. YOU MUST DRINK IT. The tasting room is awesome, though. In it you can try unlimited samples of around 70 different Coca-Cola products sold around the world. We shuffled among dispensers over the sticky floors and tasted all sorts of delicious sugary carbonated water, and occasionally experienced horrid drinks such as Beverly. The tasting room gets you nice and high on sugar and caffeine before you go to the gift shop, which is the only way to exit the museum. A brilliant scheme to coax dollars from your wallet.
According to Nic McPhee’stwitters, GECCO 2008 had 471 attendees from 46 countries. This universal appeal of scientific research is one of things I liked about last year’s GECCO conference, too. This year’s conference, though, was almost as bad as last year’s when it came to feeding the attendees. Food was given out during the two hour poster session where I was presenting my poster, but all the food was gone in less than 20 minutes, and it was not replenished. Boo!
Keynotes
Nevertheless, there were plenty of fascinating presentations and workshops. The keynotes were again from experts in the field of biology, source of many of the great ideas in evolutionary computing. Dr. Martin I. Meltzer, senior health economist at the Centers for Disease Control, gave an interesting keynote talk about developing scientific models to study public health policy and how well we’d react to sudden outbreaks of disease. In particular, he used the example of pandemic influenza. Overall it was a fascinating but extremely depressing talk, since much of it dwelled on how unprepared we are for situations such as the 1918 flu pandemic. Well-known biology professor, popular science blogger, fierce skeptic, and “expelled from Expelled” victim PZ Meyers gave the second keynote talk. He spoke about the importance of development during evolutionary processes (aka “evo-devo”). For example, many animals share the same exact genes but the organisms themselves have vast differences. The differences are due to other important developmental processes outside of the animals’ genes. He talked about some interesting specific examples, such as development of bats and mice. Cretekos et al (2008) recently chopped out a regulatory sequence from bats and stuck them into mice. The mice then developed longer forelimbs, corresponding to the lengthened forelimbs of bats needed for flight. PZ’s blog post explains this in more detail (and with cool pictures!) This example showed that there are many elements at play that create variety in organisms, and many of these elements are strongly influenced by their environment. We are only barely beginning to understand how these things all work together to form life.
PZ’s other interesting example of environmental factors in evolutionary development was Suzuki and Nijhout’s 2006 paper “Evolution of a Polyphenism by Genetic Accommodation”. The researchers were able to evolve environmentally-driven traits in a type of caterpillar. In cooler temperatures, the evolved caterpillars remain black in color. But some of the ones exposed to hotter temperatures turn green in color; all the rest remain black. So the experimenters selected the greenest caterpillars and let them breed with each other. They also selected the black, unchanging caterpillars and bred them with each other. Over a small number of generations, descendants of the green-changing caterpillars more reliably changed colors, while the unchanging caterpillars reliably resisted changing colors in hotter temperatures. Read PZ’s post for more interesting info on how this all works. It reminds me of Ryan Somma’s post about Daisyworld, a thought experiment world in which black and white daisies affect the temperature of their planet as well as their own survival.
Chris and I entered the 2D packing problem contest, where you have to evolve a grid of numbers that yield the highest scores for adjacent pairs of numbers. We didn’t win but we did well enough to give a presentation about our approach. We developed an “embryonic” growth technique to evolve the 2D grid, using block-based growth, and something that ended up looking like mold.
Animation of the “mold” evolution technique. Brighter red spots indicate formation of high-scoring areas of the grid. Click to see the supersized version.
Other contests included evolving Rubik’s cube solvers on a massively parallel grid computing platform (the winner gets $1000), evolving L-systems to match pre-existing images, and evolving intelligent agents to search a virtual landscape for food as efficiently as possible. Nobody qualified for the Rubik’s cube contest, and nobody entered the L-system contest. Which is too bad, since they are very interesting problems. And the $1000 bounty for the Rubik’s cube problem remains unclaimed; Parabon is keeping the competition open and is upping the ante to $2000 for GECCO 2009.
There was also the so-called “HUMIES” awards, which is a competition to showcase evolutionary methods that match or outperform human efforts to solve problems. The winning paper used genetic programming to evolve ways to find special algebraic terms that no human has been able to accomplish.
Interesting research
Below is a list of some of the other presentations and papers that interested me:
Games: Moshe Sipper spoke about evolving artificial players for Robocode, backgammon, and chess. The evolved Robocode player was able to beat all of its competitors, which were all written by humans. The evolved backgammon player beat “pubeval”, a strong hand-written backgammon algorithm, 62% of the time. Sipper claims the evolved player will beat human players “most of the time”. The evolved chess-playing AI was able to win or draw against Crafty, a hand-written chess-playing program that is a top competitor at the World Computer Chess Championships.
Kenneth Stanley discussed “generative and developmental systems”. He explored the question, “how is it possible that 100 trillion connections in the human brain can arise from a mere 30,000 genes in the human genome?” The belief is that biological processes such as embryonic development cause complex things to emerge. If we stole some of these ideas from nature and used them in evolutionary computing, maybe we could solve some really interesting and difficult problems. Dr. Stanley cited the work of Gregory Hornby, who evolved robots and other objects using an L-system grammar. The advantage of using an L-system is you can get complex behaviors out of very compact, simplistic rules instead of describing or defining each part individually.
Dr. Stanley went on to describe a technique to evolve abstract representations for development, based on how evolutionary artwork is made. This was a big surprise to me; I’ve done a little bit of evolutionary art research, so I was happy to discover that there are real uses for the techniques other than just making pretty pictures. Along the way, the technique Dr. Stanley described turned into a side project called Picbreeder where computer-generated art is evolved via an online community. I’ve been wanting to see something like this!
In the defense applications track, we saw a talk about evolving swarm behaviors for unmanned aerial vehicles (UAVs). Some of the swarming, self-organizing, and attacking behaviors are inspired by behaviors of insects such as bees and wasps. Several interesting micro-UAV technologies were mentioned, such as the Black Widow, UAVs with flapping wings (including bat wings), and parasitic (!!!) UAVs such as SilentEyes (it is launched from larger UAVs). Don’t do anything suspicious, or a swarm of these damned things will form a stinging cloud around you.
Black Widow micro-UAV. Watch out for its poisonous bite.
In another talk, an Australian researcher described their technique of evolving collective intelligence for UAVs to detect and report bush fires (that’s Australian for “wildfires”). Their challenge was to evolve swarm behaviors so the UAVs have the best possible coverage of the surveyed area, and also so the UAVs can adapt if there are malfunctions in members of the swarm.
There were many more interesting papers, too numerous to describe, showcasing the widespread and diverse applications of evolutionary computing. Some examples include evolving circuits with high testability, automatic defect classification in electronic wafer manufacturing, quantifying quality degradation on voice-over-IP networks, detection of malware (including zero-day virus attacks) using techniques inspired by biological immune systems, evolving color schemes for people with color blindness, investment portfolio optimization, modeling the Milky Way galaxy using BOINC volunteer computing, developing no-loss strategies for tic-tac-toe, finding deadlocks in large concurrent java programs, radar jamming, evolving functions that can detect computer program code plagiarism by students (beware, cheaters!), automatic route planning that takes traffic into consideration, automatic composition of rock music using genetic algorithms (seriously?), interactive evolution of facial composites of suspects in criminal investigations, detection of moving objects in videos, using a bacterial foraging algorithm to detect circles on images (wait, what?), evolving a World Computer Chess Champion-beating chess program by mimicking the behavior of a mentor, and prediction of whether a company will have financial losses.
The list goes on. But I’ve punished you long enough with this mercilessly long post. Long story short: Trip good. Science good. Computers fun.
