GECCO 2009

A big shout-out to the organizers and participants of the 2009 Genetic and Evolutionary Computation Conference.
I really missed not being there. Can’t wait to read the proceedings.

A penny for your thoughts (literally)

Image via Wikipedia

There are companies developing devices that can read your brain’s output and use it to control external devices. The technology used is similar to that used by an MRI scanner; as with an MRI scanner these technologies have the potential of providing a wealth of benefits for health care. An example application is their use to aid people with missing limbs control artificial replacement.

These devices are getting cheaper (in the $100 range). They are being used to allow  people to interact with games and other software applications. The easy and cheap availability of such brain scanning devices however raises some ethical questions. As this emotiv systems presentation shows, these devices can inadvertently read your mind. seeing what are your likes and dislikes.

Such data in the hands of a commision-based salesman is scary. It is easy to imagine a website that can assembles  text and  pictures on the fly (based on your preferences) to get you to buy whatever is being sold. Worse still they can sell your thoughts, such that other companies know how to target you better.

That is scary.

Search, Neutral Evolution and Mapping in Evolutionary Computing:2

Here is a pre-proof copy of my accepted paper: “Search, Neutral Evolution and Mapping in Evolutionary Computing: A Case Study of Grammatical Evolution”.

I would encourage you to read section X  (Analysis of related works) , to see its true implications.

I plan to do a series of posts on what this paper means for Evolutionary Computing, and to post some of the MATLAB code used in this work.

You might want to subscribe to my RSS feed.

“This paper is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.”

Search, Neutral Evolution and Mapping in Evolutionary Computing: A Case Study of Grammatical Evolution

The above is the title of my paper that has been accepted by IEEE Trans. on Evolutionary Computing. My doctoral supervisor Dr Kaur is a coauthor of the paper.

Here is the abstract:

We present a new perspective of search in Evolutionary Computing (EC) by using a novel model for the analysis and visualization of genotype to phenotype maps. The model groups genes into quotient sets and shows their adjacencies. A unique quality of the quotient model is that it details geometric qualities of maps that are not otherwise easy to observe. The model shows how random mutations on genes make non-random phenotype preferences, based on the structure of a map. The interaction between such mutation-based preferences with fitness preferences is important for explaining population movements on neutral landscapes. We show the widespread applicability of our approach by applying it to different representations, encodings and problems including Grammatical Evolution (GE), Cartesian Genetic Programming, Parity and Majority Coding, OneMax, Needle-in-Haystack, Deceptive Trap and Hierarchical if-and-only-if. We also use the approach to address conflicting results in the neutral evolution literature and to analyze concepts relevant to neutral evolution including robustness, evolvability, tunneling and the relation between genetic form and function.

We use the model to develop theoretical results on how mapping and neutral evolution affects search in GE. We study the two phases of mapping in GE; these being transcription (i.e. unique identification of genes with integers), and translation (i.e. many-to-one mapping of genotypes to phenotypes). It is shown that translation and transcription schemes belong to equivalence classes, therefore the properties we derive for specific schemes are applicable to classes of schemes. We present a new perspective on population diversity. We specify conditions under which increasing degeneracy (by increasing codon size) or rearranging the rules of a grammar do not affect performance. It is shown that there is a barrier to nontrivial neutral evolution with the use of the natural transcription with modulo translation combination; a necessary but not sufficient condition for such evolution is at least three bits should change on mutation within a single codon. This barrier can be avoided by using Gray transcription. We empirically validate some findings.

This paper was originally written with a more modest scope limited to Grammatical Evolution (which was a central part of my dissertation). If it seems overachieving it is partly due to me and partly due to reviewer requests for a more general approach. The amount of work behind this paper is painful to even think of. I am not complaining though, the final product is certainly worth the effort and I am very satisfied at the quality.

Please email me if you want to see a draft copy.

Some ways you can go wrong with Evol. Comp. II

Misunderstanding Randomness

There are two aspects of randomness in Evolutionary computing that are frequently misunderstood . The first issues is the assumption that the effects of random mutations are always random. No that is not a typo, the effects of random mutation are usually not random but are coordinated into nonrandom distributions based on how genes map to their measured behavior (aka their phenotypes).

A good analogy to explain this concept is the bean machine. As explained in Wikipedia, the bean machine

Bean Machine

was invented to demonstrate the law of error and the normal distribution. The machine consists of a vertical board with interleaved rows of pins. Balls, dropped from the top, bounce in random directions on hitting the pins. Not withstanding their random horizontal motions on descent, the balls settle at the bottom of the machine in an approximately normal distribution.

The second misunderstood aspect of randomness has to do with the way it is measured in populations. Some researchers measure the amount of diversity in a population by summing the variance of genetic (or allelic) values for all locations on genomes.Based on the evolutionary landscape this measure can overstate the search potential of a population. A population can be effectively converged (i.e. all of the genomes can have the same fitness and all can be searching the representation space the same way) without there being a low variance between their gene values.

I have a forthcoming  paper (accepted by IEEE Transactions on Evolutionary Computing) , which among other things, looks at preferred directions of motion due to random mutation as well as randomness in evolutionary populations. I will blog on this further when it is published.

Some ways you can go wrong with Evolutionary Computing

Image via Wikipedia

The second, feeling of his tusk,
Cried, “Ho! What have we here
So very round and smooth and sharp?
To me ’tis mighty clear
This wonder of an Elephant
Is very like a spear”.
by John Godfrey Saxe

The state of Evolutionary Computing is somewhat like the blind men’s observations in Saxe’s poem above. A practitioner’s opinion of what EC is can be influenced based on the sub-area of their specialty; the development of sub-areas themselves being accidents of history.

The basic approach behind Evolutionary Computing algorithms is that they process symbols based on principles that mimic biological evolution mechanisms. The research behind them involves:

• Understanding the science of how they process symbols;

• Figuring out the engineering aspect of how to make such symbol processing problem friendly.

This post is the start to a series on some ways EC practitioners can and do go wrong.

1. One way you can go wrong is to give their symbol processing human attributes. Although EC algorithms can solve problems it does not mean they use the same problem solving techniques humans use. The most prevalent example of the anthropomorphizing of such algorithms is the Building Block Hypothesis. In my opinion the Building Block hypothesis is really an attempt at trying to decipher how EC algorithms (specifically Genetic Algorithms) work based on the common human divide-and-conquer approach.
2. Do not follow biological models too closely, only follow the principles. This advise also works for other biologically inspired optimization algorithms such as neural networks. If the reason for your use of EC is to understand biological phenomena then this advise is not for you. However if you objective is to get an EC algorithm to solve a problem on some digital hardware then you are most likely not constrained by the physics and chemistry of DNA and RNA interactions. As an analogy, consider that airplanes don’t flap their wings though birds do.

My GECCO 2008 Conference Presentation

Image via Wikipedia

Genetic and Evolutionary Computing Conference (GECCO Atlanta, Georgia) 2008 is the best academic conference I have ever attended. There were lots of tutorials and workshops, many interesting papers and concepts.

I got to stay at Georgia Tech – What a nice university.

Unfortunately, I did not find time to see the sites in Atlanta as much as I wanted to. There was always something interesting going on in the conference.

Got to meet Poli, McPhee, Ryan, and many other stars of the Evolutionary Computing Community for the first time. Just that was worth the price of the conference.

Below are the slides of my presentation for the paper ” Using Quotient Graphs to Model Neutrality in Evolutionary Search”

presentation-for-gecco-2008

Some Data Mining amd Machine Learning Presentations

Statistical Aspects of Data Mining, David Mease

---

Human Computation, Luis von Anh

---

Winning the DARPA Grand Challenge, Sebastian Thrun

---

Scalability and Efficiency on Data Mining Applied to Internet Applocations, Wagner Meira

---

Sparse and large-scale learning with heterogeneous data, Gert Lanckriet

---

The first class(ification)-oriented representational formalism, Lev Goldfab

---

Using Statistics to Search and Annotate Pictures, Nuno Vasconcelos

{Sentence} -> {Word} {Space} {Word} {Stop} -> Hello world!

Welcome to my blog!

I am just about finishing my PhD and that gives me some time to express my opinions and ideas on the science and engineering of intelligent machines. Intelligent machines are machines (or systems of machines) that show abilities we commonly associate with intelligence; these include the capacity to learn, reason, plan and derive and use knowledge from their environment towards achieving some goal.

I am using the term machine in the wide sense, i.e. a machine does not have to be mechanical, it just has to have some machinery (defined as ” A system of related elements that operate in a definable manner”). There we go, you really can’t go far into machine intelligence without considering grammars. Grammars are the rules governing the operations of machines. Grammars say what machines can legally do, how they are defined to operate. Grammars can be viewed from the perspectives of being guides and/or restrictions on the operations of machines. Grammars are everywhere, trust me.

You should have guessed by now that I am a fan of grammars. My doctoral dissertation is on applying Grammatical Evolution to the task of data mining network intrusion data. I have to defend it some time next month, and then I am done (I hope). See you around.