5
$\begingroup$

I am trying to understand how genetic programming can be used in autoencoders. I am going through a few papers (the classic one and another) but they dont help me to even grasp the concept of genetic programming in autoencoders. I understand that autoencoders are supposed to reconstruct the instances of the particular classes they have been trained on. If another fed instance is not reconstructed as expected, then it could be called an anomaly.

How does one use genetic programming in autoencoders? You are still required to create a neural network just instead of feed forward you use autoencoders? I would appreciate any tutorials or explanations.

$\endgroup$
  • 1
    $\begingroup$ Added an "autoencoder" tag :) $\endgroup$ – DukeZhou Apr 23 '18 at 21:30
3
$\begingroup$

Both are specific types of a broad class of what are now usually called Evolutionary Algorithms. There's no single definition of what makes an Evolutionary Algorithm, but it's generally construed to be very broad. A rough description might be any search method that starts with a population of one or more stochastically generated candidate solutions to a problem, applies operators to those solutions to produce new solutions, and applies some form of selection to guide the process towards better solutions over time.

Note: This implies some encoding mechanism for solutions, which might be as simple as just recording the parameters to the problem as numbers directly, or may be more complex, binary coded, represented as finite state machines, represented as program code, or any other representation that can be decoded and evaluated in a programmable way.

Also note: This definition can encompass all sorts of things we wouldn't necessarily call "GAs" -- things like random hill climbers, simulated annealing, etc. Most of what we actually call evolutionary methods are a bit more restricted. They typically use a population much larger than one, the operators are generally some form of binary crossover and unary mutation, and a handful of well known selection mechanisms are used.

With that in mind, we can sketch out an abstract form of an evolutionary algorithm:

  Generate initial population of size N;   while(not done)     while(offspring population not full)           select parents;           generate offspring;           evaluate offspring;           insert offspring into offspring population;       select survivors for next generation;

While this is obviously highly abstracted version, both "Genetic Algorithms" and "Genetic Programming" match this template. The differences are almost entirely in how solutions are encoded and how they are evaluated.

The canonical "Genetic Algorithm" uses a binary encoding of all parameters, but aside from historical references, we don't really consider that to be a requirement anymore. For solving the traveling salesman problem, for instance, the standard representation would be a permutation of the city labels. In any case, for a GA, we have program code that evaluates how good a particular solution is for solving our problem, and we simply feed it evolved parameters. Imagine you're optimizing the design of a wind turbine. For a GA, you'd have code that took as parameters, all the important properties of a turbine, and that code would spit out a number, efficiency or whatever you're trying to optimize. We can encode those properties as real numbers, binary encoded numbers, gray-coded, whatever, but we always decode them into the form required by the fitness function.

Genetic programming is different. Rather than evolving parameters, we're evolving executable code itself. So the representation generally isn't something like binary-coded decimal numbers, but rather abstract syntax trees, often expressed in syntactically regular languages like Lisp. It's easiest to see this with an example, and the "Hello world" of GP is undoubtedly symbolic regression.

Imagine you have some set of variables (x1, x2, x3), and for each, you know the value y = f(x1, x2, x3). The symbolic regression problem is to find an expression that most accurately matches the unknown function f. In classical regression analysis, we would first select a model -- we make an assumption that f is linear, quadratic, whatever. For the sake of simplicity, let's assume a linear model. This means that f(x1, x2, x3) = ax1 + bx2 + cx3 + d. We simply minimize an error term over the training examples to find the values of a, b, c, and dthat give us the "correct" model. One major problem with this approach is that the assumptions required are very strong. If you guess the wrong model for f, you're going to get poor results.

With GP, you relax the assumptions somewhat. Rather than say "f must be linear", we say something like, "f must be expressed using only arithmetic operators, trigonometric functions, exponentials, and numeric constants". We can then generate a bunch of random expressions as candidates for our unknown f. We might start with x1^2 + 4.2*(x2-2) - x1 + 2*x3*s2. This expression is our representation (probably suitably encoded as a Lisp expression because this makes it much easier to perform the genetic operators). We can recombine and mutate the expressions themselves to generate new expressions. To evaluate the fitness of an expression, we can compute the error across our training data. Other than the encoding and the evaluation method, the standard evolutionary framework applies.

I've mentioned Lisp a few times. The earliest GP work was almost exclusively done in Lisp because it makes it easy to cut and splice programs together. A Lisp expression is a straightforward translation of the parse tree, so cutting a branch off of the parse tree and swapping it with a branch from another parse tree can be done easily. Trying to do similar things with, say, C or Java, can be done, but is much more difficult to do without generating syntax errors. In more recent times, GP approaches have broadened a bit, and there are now methods using concatenative languages and other choices, but Lisp and Lisp-family languages (e.g., Clojure) are still popular as well.

There are a few other minor differences that pop up. Practitioners found that the normal EA parameters that work well for GAs often don't work well for GP. Things like the population size can differ dramatically, with 100 or so being very common in GAs, while GP might use 500 or 1000 individuals in a population. GP approaches typically require some additional methods to control things like bloat, where the GP system may evolve expressions like 2 + 2 - 1 + x + 4 - 2 * x instead of the equivalent 3x+7 or evolve the same sub-expressions over and over again.

Because of these differences, GA and GP researchers tend to work in fairly different ways. Most people are specialized in one camp or the other, where each knows mostly what the others are doing, but don't delve much into the specifics.

$\endgroup$
  • $\begingroup$ Welcome to ai.se....Thanks for your comprehensive and detailed answer,...but you need not use up so much of your time writing long answers and can instead write concise answers targeting the problem..I have tried to improve the formatting of your answer, feel free to change things you think was not an improvement...Also keep visiting :) $\endgroup$ – DuttaA Apr 26 '18 at 6:34
  • 1
    $\begingroup$ This is great summary of GA and GP. However, no mention of autoencoders, which is a major part of OP's question. $\endgroup$ – Neil Slater Apr 26 '18 at 7:09
1
$\begingroup$

Unfortunately your second link does not work. However, I will try and answer your question.

The classic paper your present uses a genetic algorithm (GA) while you mention genetic programming (GP). @Saadmrb provided a great explanation, however in short a GA uses an evolutionary process to evolve a fixed length vector normally a bit string, while a GP evolves variable length decision trees which could be a computer program or mathematical function.

An autoencoder is something that automatically encodes or decodes something. For example a noisy image is decoded to the original image (very simplified I know), the point here is automatically, so without any defined process an autodecoder can "learn" how to remove the noise from the image.

Generally an autoencoder is made using a neural network (NN). The noisy image is read in as input and the output is a clear image. To train the NN, back propagation is used. For back propagation to work an error is needed to calculate the weight changes. Alternatively the weights could be encoded a vector. A fixed length vector is then evolved using a GA to evolve the weights of the NN. This is what the "classic paper" mentioned does.

Using a GA to evolve the weights of a NN is not really efficient, because weights affect each other which means each time crossover happens the weights are totally messed up and the GA can easily get stuck in a local optima. Gradient descent is far more efficient.

The structure of a multi-layered network is important, here gradient descent is still used to update the weights, but a GP could be used to evolve the structure of the NN.

Alternatively the GP itself could be used to evolve an auto encoder without using a NN. Here the chromosome will contain nodes such as mathematical operations or computer code that would alter the input to produce the output.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.