Thursday, July 30, 2015

Revolutionary algorithms

Edit: Apparently it is not clear to everyone that the following post is satire. Well, it is.

You have surely heard about evolutionary algorithms and how they, inspired by Darwinian evolution in the natural world, are excellent general-purpose search and optimization algorithms. You might also know about neural networks, which are learning algorithms inspired by biological brains, and cellular automata, inspired by biological developmental processes. The success of these types of natural computation has spurred other attempts to base algorithms on natural phenomena, such as particle swarm optimization, ant colony routing, honey bees algorithm, and cat swarm optimization. These algorithms are popular not only for their biological inspiration but also for their proven performance on many hard computational problems.

However, in an era where unfettered market forces force bankruptcy upon liberal-democratic countries as a result of bank bailouts dictated by the global financial elite, the neoliberal ideological basis of such algorithms can be called into question. After all, they are based on a model of individual betterment at the expense of the weaker members of population, an all-consuming "creative" destruction process where disenfranchised individuals are ruthlessly discarded. "Survival of the fittest" describes the elimination process by which the invisible hand strangles the weak; "self-organization" is the capitalist excuse for exploiting non-unionized labor. Common evolutionary algorithm operators like survivor selection represent the violence inherent in the system.

But there is an alternative: algorithms for socially just optimization based on models of the workers' struggle and the liberation of the oppressed. While rarely discussed in major  (corporate-sponsored) conferences, revolutionary algorithms have certain similarities with  the better-known evolutionary algorithms. The basic structure of a revolutionary algorithm is as follows (Marks and Leanin 2005):

  1. Initialize the population with n individuals drawn at random.
  2. Evaluate all individuals to assign a fitness value to them; sort the population according to fitness.
  3. Remove the most fit part of the population (the "elite").
  4. Calculate the average fitness in the population; assign this fitness to all individuals.
  5. Increase fitness of the whole population linearly according to a five-generation plan.
  6. Repeat step 5 until maximum fitness has been reached.

As you surely understand, this simple scheme does away with the need for elimination of lower-performing individuals while assuring orderly fitness growth according to plan. Just like in evolutionary computation, a number of modifications to the basic scheme have been proposed, and proponents of the various "schools" that have grown up around specific types of algorithms do not always see eye to eye. Here are some of the most important new operators:

  • Forced population migration (Sztaln 2006): While in evolutionary computation much effort is is spent on diversity maintenance, in revolutionary computation it is important to counteract the damaging effects of diversity. Forced population migration moves whole parts of the population around in memory space, so as to counteract any dangerous clustering of similar individuals.
  • Continuous anti-elitism (Polpotte 2008): While standard revolutionary algorithms only cull the elite in the initialization phase, the radical scheme suggested by Polpotte eliminates the most-fit part of the population every generation. When no fitness differences can be discerned, which individuals to remove can be determined based on arbitrary factors.
  • Great leap mutation (Maocedong 2007): This modification of the basic scheme is particularly useful when the initial population has a very low average fitness. Here, the population is sorted into small "villages" and each village is told to accomplish its development goals on its own, including creating its own search operators.

More recently a newer generation of researchers have questioned some of the basic assumptions underlying revolutionary computation, such as the stable identity of individuals and the boundaries of the population array. The replacement of some parts of the population with others has been decried as a form colonialism. Revolutionary algorithms of the poststructuralist variety therefore eschew strict divisions between individuals and practice adding random variables to instruction pointers and array indexes. This naturally meets resistance from antiquated, orthonormative models of computation and operating systems. In this context, it is important to remember that "segmentation fault" is just a form of norm transgression.

In the end, those algorithms that are most efficient will win; society cannot afford substandard optimization. And in the same way as the success of evolutionary algorithms is predicated on the success of Darwinian evolution in nature, the success of revolutionary algorithms is predicated on the success of the ideologies and movements that they are modeled on.

(This post was inspired by discussions with Daan Wierstra, Mark Nelson, Spyros Samothrakis and probably others.)

Saturday, July 25, 2015

How not to review a paper

On occasion of several paper reviews I've received recently, and a few I've written, I'd like to give some useful tips for how to review a paper. That is, how to review a paper if you want to do a really, really bad job of it. Note that I work in the AI and Games field, so somewhat different advice might apply to screwing up a paper review in another field.

First of all, be vague. Say what you think about the paper in very abstract terms, and at all costs avoid pointing out specific flaws with the paper so that they could be easily fixed.

This applies most of all to any comments about the literature review. It's fine to point out that the literature review is missing important related work, but by no means include any references to said work. Ideally, say that the paper cannot be accepted because of glaring omissions in the references, and fail to provide a single paper they should have referenced.

If by any chance you think the paper you are reviewing should have referenced one of your own papers, then you should definitely not say so. Your papers are obviously of such brilliance that everybody already know about them by virtue of them being published somewhere. Instead, treat this omission of citation as a personal insult, and add a passive-agressive slant to your review.

If you find it hard to be abstract enough in your review, then you may consider doing the opposite: only talk about details. Talk at length about verb forms and the possible inclusion of semicolons, and if you have substantial comments about the methodology or results bury them as deep as you can in a wall of text. For maximum effect, use a stream-of-consciousness style where you jot things down as you read the paper, often digressing into reflections on various topics that reading the paper reminded you of. It's great if some of your later comments contradict your earlier comments. At the end of it all, issue an arbitrary accept/reject recommendation without explaining which of the numerous comments made you come to this conclusion.

It's imperative that you don't write any summary of your review, or the effect is lost.

If the language and tone of the paper is not exactly how you would have written it, urge the author(s) to enlist the help of a native English speaker to correct their English. This comment works best if you can tell that the authors are native English speakers, and if you carefully add some grammar and spelling mistakes to your review.

Speaking of how you would have written the paper, it's a good idea to evaluate the paper from the perspective of what you would have done if you wrote the paper. Say for example that the authors present an algorithm and are mostly interested in the algorithm's correctness, whereas you would personally be more interested in its runtime. Then it's perfectly fine to reject the paper because they studied the correctness and not the runtime of the algorithm, and they clearly should have studied the runtime instead. After all, you are the one reviewing the paper, so you should decide what it should be about.

In the same vein, don't just accept any definitions of terms or scoping of the investigation that the paper might contain. Read the paper using whatever meaning of the words in it that you find convenient. And if the authors state that they are not concerned with topic X, that is no reason for you to not go on at length about how important topic X is and why they should have included it.  It's your freedom to read the paper any way you want and assign any kind of meaning to it you like.

This brings to our final and perhaps most important piece of advice. It's likely that there is some part of the paper you don't understand, because like everybody else you are occasionally frequently out of your depth and these authors write like morons anyway. If this happens - don't admit it! Don't lose face by explaining that you don't understand the paper! Your reputation as an anonymous reviewer is at stake. Instead, simply pick at random some interpretation of the part of the paper you don't understand, preferably some interpretation that makes very little sense. Then write your review as if that interpretation was true. Hilarity ensues, at least on your side.

If you heed all this advice, you will surely be able to produce the kind of reviews that one frequently receives after submitting to some famous conferences and well-respected journals.