One of the things you realize after a while is that projects drop into your lap faster than they can be completed. Some sources of inspiration are things you encounter all the time: your work (I know a lot about molecular design and pharmaceutical lead compound discovery), your hobbies (I know a lot about image recognition and segmentation for OCR of digitized books), and things you see other folks doing and just want to try (I’ve enjoyed my years doing Symbolic Regression because so many other people have paved the way, while leaving other paths less traveled and thus more interesting).
I’m finding that writing the introductory material for the book is difficult. In fact I’ll probably postpone releasing the intro until more of the core guts are written. Mainly the introductory material has been about that perennial question, “How do I find and pursue ideas?” My core argument is that GP is useful for accelerating the fruitful investigation of your ideas, but the challenge for many folks is recognizing the heuristics I personally take for granted. Some of this means I’m revisiting Polya’s How To Solve It: A New Aspect of Mathematical Method, but I find that it’s not philosophically compatible with the agile stance I personally prefer, so I’m actually finding Andrew Abbott’s Methods of Discovery: Heuristics for the Social Sciences more useful, not least because he suggests Aristotle’s four causes and Kant’s schema as interesting “kicks to the head”. And there’s Michalewicz and Fogel’s excellent How to Solve It: Modern Heuristics, which goes in a more technical direction (and closer to GP) tan Polya was able to do.
But I look over all that good advice, and I find it troubling. So I’m up in the air about it.
I decided more than a month back to change something important in the book. I still think Learning by Doing is crucial and important. But I can’t see a way to provide acceptance tests alone (with no pseudocode or worked-out examples) in an enticing-enough way that provokes reasonable responses from the readers. That is, I got a lot of pushback from potential audience members who don’t actually know how to write their own code based on acceptance tests.
So I’m trying what Ron Jeffries did in his Extreme Programming Adventures in C#: describing what I am thinking, what motivates me, what I actually do, and as a result I hope to make the process itself more transparent, not just the externally visible steps. As Ron pointed out a few weeks back when we chatted about it, this smacks of arrogance. Who am I to think other people care about the mistakes I’m making, or want to be misled by watching me do stuff I subsequently undo? Just to prove I “learn something” from it?
Them’s the breaks. The alternative would be the crap one already has: pseudocode presented as if it were the one “right” way to do stuff, and the inclusion of idiomatic (or worse, generic) libraries that the reader should re-create themselves for every project, not borrow and re-use indiscriminately just because it happened to be in a book. In other words, better sorry than unsafe.
So inspiration is a thing I’ll set aside and talk about subjectively, not in terms of heuristics which (as Abbott points out in his excellent account) can quickly become fossilized and ritualized as though they were “correct” instead of useful.
So I picked up a book
I seem to like mathematical recreations. Just the other day I sketched a little game thing that somebody should pick up and run with. If it sits around long enough, maybe I’ll do it myself, but not until the book is farther along.
In the pile of interlibrary loans that I picked up the other day was a treasure trove in one volume: Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Now the mathematics of origami and stuff is all modern and weird and “advanced” to my generation; most of the actual mathematical results came after I graduated from University, and appeared in fancy esoteric mathematics journals even then. But there’s a constant chorus in New Scientist and Science News and stuff about new results, and there’s this other thing I used to do when I was a structural biologist that involves folding and abstractions of physical reality surprisingly similar to those in origami. Which is the Holy Grail of a multi-trillion dollar industry at the moment, by the way.
I’m trying to put my finger on what it is about some books— Martin Gardner’s or Cliff Pickover’s or Ivan Moscovitch’s, for example — that makes them so inspiring. Is it the density of open questions? A tone that makes you wonder before disclosing anything? Something inherent in this semi-abstracted recreational game stuff that makes it clear how to write a simple computer program but unclear how to solve a problem? Something about puzzles? I have no idea.
At any rate, this one has that same stuff on it. It’s fun.
I picked it up from the stack this morning, opened to a random page, and started reading about one-dimensional origami. Now this is a book that’s framing new work in modeling physical systems like folded paper (and proteins) by setting up the mathematical constructs and abstractions in a traditional way. But there’s a heuristic I find myself adding to the other handy “kicks to the head”, especially useful for GP work: What would it take to build a software system that “did” this?
So let’s think about one-dimensional origami for a second.
Does it fold?
Before they even get very far in the formal mathematics of paper-folding, Demaine and O’Rourke talk a bit about representing one-dimensional folded structures. You know, the traditional necessary and sufficient conditions for determining whether a thing is what you call it or not. Those core concepts, the stuff hanging off the “trivial” parts of traditional science and engineering that you often elide because you’re just defining your terms, that’s where there’s often low-hanging fruit for GP projects.
I recommend a browse through the excellent book, or just peek at Erik Demaine’s lecture notes on the subject. We’re talking about what starts out as a line segment, which we crease at certain (arbitrary) points, and then press flat so that it produces a sort of accordioned stack of squiggles. Think of a cross-section through a piece of folded paper.
Let’s use paper, for a minute, and just assume for now we are folding it only in the vertical direction. Just to get a slightly more visceral sense of it.
Plop a (big) sheet of paper down on the table in front of your mind’s eye for me, OK?
We can make “mountain” or “valley” folds. Think of a “valley” fold as taking either the left or right edge of the paper and folding it upwards and across towards the opposite; think of “mountain” folds as tucking the right or left edge down underneath the stack. You can make these mountain or valley folds anywhere between the edges of the paper, and as long as the creases are parallel with the left and right sides you’re mimicking one-dimensional folding. Just peek at the end of the sheet to lose the extra dimension.
There’s a tricky bit of mathematics hidden inside this simple-seeming physical model, though: how do we capture the physical constraint that keeps paper from passing through itself?
Demaine and O’Rourke’s contributions are eminent and interesting and well-considered. There are cunningly-crafted constraints that capture the physicality of paper’s inability to cross itself, and identify feasible flat foldings (and implicitly foldings that aren’t “flat” at all), while maintaining the integrity of the paper itself. In other words, you carry on that direction, and you have a formal representation that lets you do some fascinating mathematics and modeling.
But what would it take to build a software system that “did” this?
By “this” I mean the work of establishing necessary and sufficient conditions for realistic folded lines. The implicit and tacit stuff a human being takes for granted when they have some notion of “crossing” or even “folding” in their heads already.
Does this make sense?
So let’s ask a GP system to look at a stack of line segments of various lengths and “merely” say whether there is any way a single line segment could have been folded that way, without crossing itself. Heck, there are probably long-range situations in which a partially-folded crumple would interfere with itself; let’s ignore those.
So here’s a quick sketch to help out:
The top two squiggles are actual folded line segments.
The first is definitely feasible, in the sense that you can imagine crunching up a pipe cleaner or folding the edges-only paper I mentioned above and making the cross section look like that.
The second it infeasible, because the middle leaf is too big for the space it’s in, and protrudes through the crease.
But I think we need to go farther for this to be reasonably interesting. Think about how you would represent these objects or situations in your GP system. What is a “folded stack”? Do you start from a line segment and introduce mountain and valley folds at certain positions in some order? Or do you start from the folded stack and represent it as a series of orders in certain positions, like those I’ve shown below?
I’ve sketched five little situations down there in the bottom, indicating with the dotted green lines where the nominal “crease” points are. Which of those five might be feasible? Which of them are feasible but represent a line segment that’s not the same size as the original shown in the top two? Which if them is infeasible even when you allow the raw material to be any size at all?
See how this works? Those are all reasonably interesting questions. I can totally see a set of a few hundred (or thousand) examples and counterexamples for each category. Some examples (I assume) from every combination of feasible/infeasible, same/different, congruent/incongruent, single/multiple pieces. It’s an interesting algorithmic exercise to fill in that chart with diagrammatic examples. Training and test data are yours for the taking then.
But what this sort of project wants from us, as GP folks, is a bit of ontological work.
I’m the one who does this for a living, so let me preempt your versions now:
Diagramis a list of
Stretchhas a numeric
lengthattribute, and a list
Segmentslist contains integers representing the segments present, in top-to-bottom order, numbered from 1 at the top and increasing downwards
So for the five examples I’ve shown, each would have three
Stretches. Say their lengths are 4, 11, and 5 respectively. And the
Stretches would contain these
Segments lists, respectively:
Notice that the only difference between the feasible and infeasible examples (the first two) is the third
Segment. What sort of “thinking work” does your GP-developed algorithm need to do in order to differentiate usefully between these?
Notice that the first and third are both feasible, but that the third doesn’t add up to the same amount of material. Again, what does your GP-developed algorithm need to “know” to be able to identify which diagrams might and which might not be the same line? On the other hand, if we think of the
Segment lengths as proportions rather than explicit measurements, we’re suddenly allowing the third diagram as well; in some sense it’s congruent to the first, but not identical.
And so on.
What sort of manipulations of these input structures might a general-purpose classification algorithm do? What, in other words, is the Answer Language like?