and http://videolectures.net/ssll09_slaney_fom/, which is an introduction to meta-logic.
Right now I'm watching http://videolectures.net/ssll09_martin_cai/, which is about computability and logic.
The videolectures.net site is pretty awesome in general. It has good AI lectures, and a lot of other fun subjects.
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
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.
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.
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!
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.
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.
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.
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
c----->Fc
| |
f| Ff|
| |
v v
c`----->Fc`
Tc
Fc--->Gc
| |
Ff| |Gf
| |
v Td v
Fd---->Gd
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?
