Sunday, June 26, 2011

Video Lectures

I've been watching video lectures recently, and I have to recommend SICP:

and, which is an introduction to meta-logic.

Right now I'm watching, which is about computability and logic.

The site is pretty awesome in general. It has good AI lectures, and a lot of other fun subjects.

Thursday, June 9, 2011

Arduino is Coming!

I ordered an Arduino last week, and it should come fairly soon. I finally committed to getting an Arduino when I was playing around with my friends Arduino and we implemented Pulse Width Modulation (which I learned about from him and his blog post: without using the built in PWM, but rather by turning on and off a port (which gives you more control than the built ability which is available on some of the ports).

One of my main interests in having an Arduino is actually making programming languages for it. I don't think it would be hard to implement a simple Forth (without a command line interpreter- I'm not really interested in tackling that right now), especially if it was just in C and maybe some assembly. I might do that, but I have another idea I'm looking at right now- I want to implement a concatenative language, like Forth, but with a strong, safe, static type system with polynomial types (ideally). My other main interest is giving it easy-to-use combinators, including anonymous ones. I may have to look over Factor, Cat, or Joy and see if there is some inspiration there.

I want to write a compiler in Haskell that outputs a C program (really in the C-like language provided with the Arduino). An example program might (I imagine) look like this:

: inc dup @ 1+ ! ;
: wait 50 ms delay ;
: blink 14 port dup on wait off wait ;
0 count =
[ blink count inc ] [ count @ 10 != ] while

Which would turn port 14 on and off 10 times, with a delay of 50 ms between each change in state. The stuff between the [] is an anonymous combinator. I would like the usual cast of higher order functions and the special ones for stack-based languages (I remember Factor having some very nice ones). The won't be as sophisticated a language as a real general purpose language, but if I could get it to run the sort of simple programs I imagine myself wanting to execute on the Arduino that would be great.

I will of course report my successes and failures here. I want to note here that the language may end up being less powerful than I would like as I would be willing to remove features to ensure correctness and beauty in this project. Good things come from formalism and from well understood and controlled programming languages.

Tuesday, June 7, 2011

Object Oriented Perl

I will be doing some work involving Perl this summer. I've been reading up on the language- I'm not terribly familiar with it. One thing that has become clear is that it is sort of an anti-Haskell in some ways. It is very ad-hoc, there is no attention to formalism or static analysis (there is very little we can say statically), and of course the type system is dynamic.

I am very interested in programming languages- their expressiveness and the tools each offers-, and looking at Perl from that perspective there is one interesting thing that I came across- the object system. As far as I can tell, an object is simply a reference that can be tagged as an object (blessed) such that, when referenced, will allow methods in the module it was tagged to be called with it as the first parameter. The interesting thing here is that the reference may be to anything. It looks like it is often a Hash because of their versatility, but it does not have to be- it could be any value.

The reason this is interesting is that it adds a little something to the concept of an object. I'm not sure what the implications are, but I like that its a little different and gives Perl's objects some personality. They need the extra boost, because otherwise they have a bit of an identity crisis I think- are very implicit and ad-hoc (there is no explicit syntax even) and its a little hard to see what they even are. Interestingly it is useful for the reference to be to a closure, and we can get some information hiding (important in OOP) from this.

Sunday, June 5, 2011

Robust Gene Expression Programming as a Genetic Algorithm

I've posted before about the structure of Robust Gene Expression Programming (RGEP), but I wanted to go over the sense in which RGEP is a variation on the standard Genetic Algorithm (GA). Of course, it is closely related to Gene Expression Programming (GEP), Prefix Gene Expression Programming (PGEP), and Binary Gene Expression Programming (BGEP), and it takes inspiration from Genotype-Phenotype Mapping systems (GPM), but because of its simplicity it is closer to a simple GA than these other systems.

RGEP can be considered a bit vector encoded GA with point mutation, one and two point crossover, tournament selection, and a special "rotation" operator that does a left wrap around shift of its bit vector in multiples of the length of the encoding of a single symbol. Besides the rotation operator the main difference between RGEP and a GA is the expression mechanism.

Expression is very important in RGEP. It takes the bit vector and turns it into an expression tree, giving the genotype/phenotype distinction with the nice expressive structure of trees as the result and the simple and easy to manipulate structure of bit vectors as the encoding that we actually operate on with the genetic operators.

Expression takes several stages- first we group bits into fixed size chunks, the first bit of each group determines the type of symbol (operator or terminal) and the rest indexes into the list of that type of symbol. If the index is higher than the number of symbols, we wrap back around (so its an index modulus the size of the list). This new list of symbols is called the raw symbol list. Then we do a postfix evaluation of the raw symbol lists, and if any operator would cause a stack underflow we ignore it. This implicitly does a GPM-style editing of the symbol list and results in either some object whose fitness we evaluate, or builds a tree structure that we can use. Notice that we don't have to create the tree if we don't want to- it is okay to just do a postfix evaluation and create the object directly.

The nice thing about RGEP is that this is really it. Thats all! GEP is much more complex and I tried to make the most natural choice for each part so that it would be easy to code and easy to explain. The only thing missing in this post is some details about encoding. A Genetic Algorithm library should support this technique with very little work and we get to solve problems with nice tree structured solutions nearly for free if we have a good GA library!

Gene Expression Programming

Some papers on Gene Expression Programming that I found useful for my thesis (I am trying to get a paper on my variation of GEP called Robust Gene Expression Programming accepted at the Complex Adaptive Systems conference, and I will post a reference to that paper if it is accepted):

X. Li, C. Zhou, W. Xiao, and P.C. Nelson, “Prefix Gene Expression Programming”, in Late Breaking Paper at the Genetic and Evolutionary Computation Conference(GECCO- 8. References 2005), Washington, D.C., 2005.

Xin Li, Chi Zhou, Weimin Xiao, and Peter C. Nelson. "Direct Evolution of Hierarchical Solutions with Self-Emergent Substructures." In Proceedings of the 4th International Conference on Machine Learning and Applications (ICMLA'05), pp. 337-342. Dec 15-17, 2005. Los Angeles, CA, USA.

Xin Li. "Self-Emergence of Structures in Gene Expression Programming." In
AAAI/SIGART Doctoral Consortium 2005. July 9-10, 2005. Pittsburgh, Pennsylvania, USA

Xin Li, Chi Zhou, Peter C. Nelson, and Thomas M. Tirpak. "Investigation of Constant Creation Techniques in the Context of Gene Expression Programming." In Late Breaking Paper at Genetic and Evolutionary Computation Conference (GECCO-2004). June 26-30, 2004. Seattle, Washington, USA

Ferreira, C. Gene Expression Programming: a New Adaptive Algorithm for Solving Problems. Complex Systems, 13, 2 (2001)

Ferreira, C. Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Angra do Heroismo, Portugal, 2002.

J. G. Moreno-Torres, X. Llorfla, and D. E. Goldberg. Binary representation in gene expression programming: Towards a better scalability. Technical report, Illinois Genetic Algorithms Lab (IlliGAL) at UIUC, 2009.

Banzhaf, W., Genotype-Phenotype-Mapping and Neutral Variation – A Case Study in Genetic Programming. In Y. Davidor, H.-P. Schwefel, and R. Männer, eds., Parallel Problem Solving from Nature III, Lecture Notes in Computer Science, 866: 322-332, Springer-Verlag, 1994.

R. E. Keller and W. Banzhaf, “Genetic Programming Using Genotype-phenotype Mapping from Linear Genomes into Linear Phenotypes”, in J. R. Koza, D. E., Goldberg, D. B. Fogel, J. R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D. B.Fogel, and R. L. Riolo, eds., Genetic Programming 1996

My favorite of these is the Prefix Gene Expression Programming paper- PGEP is (imho) a much cleaner and easy to use system then the original GEP and I think that it should be used for the basis of future extensions to GEP (I definitely based RGEP on PGEP (and on BGEP) not GEP).

Notice the papers on Genotype-Phenotype Mapping Systems- they are the basis of GEP, Grammatical evolution, Binary Genetic Programming, Developmental Genetic Programming, Cartesian Genetic Programming, and probably many other systems.

Saturday, June 4, 2011

Computation is Simplifying Proofs

I've been reading "Lectures on the Curry-Howard Isomorphism" recently. It covers all sorts of awesome things like intuitionistic logic, the lambda calculus, combinatorial logic, as well as things I haven't gotten to yet like dependent types (which are very neat), the lambda cube, and pure type systems.

This paper has made something clear to me which I've wondered for a while now, which is the question of why the lambda calculus would be the term language for a type system. What is it about the lambda calculus that makes it appropriate for determining the truth of propositions in the logic that a type theory corresponds to? Can we come up with other term languages that are just as good? I often have trouble with questions of why things are the way they are in math, as they can seem arbitrary at times, but every once in a while I stumble across an answer and all is well in the world.

In this case this paper mentions that normalizing in the typed lambda calculi is like proof simplification, hence the name of the post. Therefore computation is just simplifying a proof if we take normalization in the lambda calculus as our basis for computation. This is pretty awesome by itself, but it has one other surprising facet- the lambda terms are simply a linear representation of proofs in some logic! Amazing! I never saw it this way (perhaps it is obvious? certainly not to me) and I always took the idea that a term in a type made the proposition that it corresponds to true loosely as if the existence of the term simply validated the type by showing a construction for it, but it is a literal statement- the term is actually literally a proof of the statement of the type! Beta reduction is then simplifying the term which simplifies the proof.

When I get to dependent types and the lambda cube I will certainly post more about this.

Learning Genetic Algorithms, encodings

We have got all the basics of GAs down so far. We have an encoding (a representation of solutions- often as bit vectors) a mutation a crossover and a selection. Often this is enough, but if we want to use this technique for a particular problem we have to determine how to encode solutions to the problem as a linear structure. There are a series of problems that may arise here, the main one being that the easiest encoding may be too "loose" in the sense that it may be able to express invalid individuals.

A common example is in the traveling salesman problem (TSP) where we want a tour of a set of cities such that we visit each city once and only once. If this is represented as a list of cities then it is hard to enforce the constraints. Even starting out with only valid tours a single point mutation will almost certainly result in a tour that visits a city twice and one city zero times.

So what do we do about it? We have talked about editing as a way to ensure each individual is valid, and for the case of expression trees I believe that editing (it done simply and easily as in RGEP) is a very nice choice.

Other possibilities include modifying the fitness function such that invalid individuals take a fitness hit often proportional to some measure of how invalid they are. This may work in some cases, but in other there is no meaning for invalid individuals and we would have to turn them into valid ones (which is basically editing). Another possibility is to modify the operators to create problem specific mutations and crossovers (or sometimes adding different operators or removing ones that don't seem to work- often crossover is the casualty here). For the traveling salesman example we could replace point mutation by an inversion operator that inverts the path between two indices. We could also add a swap operator that just swaps the cities in two indices. Crossover is a bit difficult to modify here, but it has been done in several ways. This turns a general GA into a problem specific algorithm that may perform very well for some small (but possibly interesting) set of problems.

Another possibility is to come up with some clever encoding that cannot even express invalid individuals. This is very difficult in general as we are (very) often concerned with a subset of some obvious set of solutions like the valid tours in the set of all paths for the TSP. An example of such an encoding would be a (even length) list of numbers where each pair of number in the list (the first and the second, the third and the fourth, etc) are a swap of some fixed ordering of the cities. This cannot express an invalid individual as all swaps preserve validity and we can use the regular genetic operators we know so well. The only problem is that a level of indirection can have consequences that are hard to predict and reason about. For example a small change from point mutation on this list may have a large change on the resulting tour, so point mutation is more disruptive then we might expect it to be.

Another problem with encoding is that it may not be obvious that the problem can even be expressed as a vector of symbols. In Gene Expression Programming (GEP) and Linear Genetic Programming the linear representation allows us to do a GA style algorithm (especially with Robust Gene Expression Programming) on a tree structure, but there algorithm also specialize their operators to work with the resulting expressions. For other problems we may have to be very indirect or clever just to create an appropriate encoding, and we may have to simplify the problem or exclude certain possibilities. If we are laying out a factory, how do we determine where each component goes without duplicates (which may or may not be allowed)? If solving sudoku, maybe the linear encoding of reading the board off row by row is not the best because there is a lack of locality (squares nearby in the game board are not necessarily nearby in the representation) which makes crossover less helpful and more disruptive. Perhaps we need an inversion operator that only inverts with respective to crossover but not with respect to expression into a sudoku board (an interesting possibility usually done with a type of inversion operator which evolves the encoding along with the solutions).

So, we have seen some possible difficulties with encodings in a Genetic Algorithm. I would like to post some about my musing about the natural of GAs and evolutionary algorithms in general, as I have an interest in generalizing and making them more rigorous.

Wednesday, June 1, 2011

Learning Category Theory, natural transformations

One of the nice things about category theory is that is abstracts a very common pattern in math- we have some objects in our theory and some mappings between these objects. The morphisms in category theory are, if we are talking about the mappings between objects in our theory (categories are very general objects and can be used for all sorts of stuff), the appropriate notion of homomorphism in whatever theory we are concerned with.

Last time we saw functors as the notion of mapping between categories, but of course we can go much (much) further than that. If we take functors as themselves objects of a category (which is actually a nice thing to do sometimes) than we need some notion of morphism between functors. This is whats called a natural transformation.

So- what data specifies a natural transformation? Recall the definition of a functor- a functor F:C->D gives, for each object c in C, an object d in D, and for each morphism f in C a morphism g in D satisfying the diagrams

| |
f| Ff|
| |
v v

A natural transformation T must be between two functors (which the same source and target) F, G:C -> D, and gives for each object c in C a morphism f:Fc -> Gc in D such that the following diagram commutes:

| |
Ff| |Gf
| |
v Td v

The idea may be difficult at first- especially if we are not comfortable with the commutativity of diagrams, but the idea is so pervasive in category theory that it is in some sense obvious (at least conceptually)- a natural transformation must "preserve additional structure" of its objects. Since its objects are functors it must preserve the structure of the action of the functors (which in turn preserve the structure of a category (composition and identity)).

Natural transformations are one of the basic parts of category theory. Some categories turn out to be isomorphic to categories of functors, so the morphism of such categories (direct graphs for example) can be understood as natural transformations.

That's all I'm going to say about that for now. Next time: products and coproducts?