Subtleties and assumptions

Tuesday, November 11th, 2008

We’re trying to finish off the last bits of refactoring in the Nudge language interpreter core soon, and then expect to release it as an open-source Mercurial repository into which we’ll post updates.

Meanwhile, rooting around inside the connecting gunk that underlies something as simple-sounding as a loop structure wrapped around an “IF:THEN” decision point (which is really what drives the interpreter, at least until somebody formalizes a state machine of some sort), one tends to get philosophical.

Two interesting misapprehensions come to light. Our own, and probably others’.

The first technically subtle point we ignored (but are no longer) is the presumptuousness of the “tree vs. linear genome” dichotomy that holds sway in the Genetic Programming literature. In a nutshell, all the earliest and most influential genetic programming systems represented programs using S-expressions. That’s still the case, and at a conference or inside a book you’ll often come across a core assumption that what you’re dealing with is a tree.

With minor variations, these languages colloquially represent programs as dataflow trees in which branchpoints are functions and leaves are literals or bound variables. Setting aside the fact that this structure deeply influences evaluation, code generation and search, it’s a tacit assumption in a lot of the literature and practical community that genetic programming operates on genomes that are trees.

That said, a substantial minority of genetic programming systems use linear genomes: representations of code that are sequences, read left to right. This is the sort of paper tape, genetic algorithm-like genome that comes a lot closer to the state machine reader paradigm, and allows folks to use the more familiar (and arguably intuitive) crossover and mutation operators they learned when working with genetic algorithms. Snip ‘em in half and swap the chunks, line up an arbitrary sequence of instructions, that sort of thing.

There are important differences between implementing tree and linear representation systems not having to do with search dynamics. In the former, semantics and syntax are typically wrapped up in the rules one uses to construct and preserve a valid tree under the operation of structure-modifying operators: an addition operator needs at least two inputs; a constant can’t have any inputs at all. The tree-based GP literature is bloated with innumerable variations on the theme of sense-preserving rules for operators and tree construction, and the theoretical and practical consequences of using those rules.

But in many cases linear representations, in setting aside some or all of those draconian sense-preserving rules so that snip-and-glue crossover can be used, tend to lead to very contingent interpreters. Sometimes the interpreters thrown at these representations draw on messy GA approaches, and “just skip over” instructions that don’t make sense. Some use cunning indirect representations (grammars, expression systems) to smear sense back into the power set of all “programs”, so that any arbitrary sequence of opcodes “means something”.

Needless to say—hang on, is it needless to say? No. It’s important to say that this sort of decision deeply affects the power and appropriateness of genetic programming for a particular problem. Not merely in the ease of modeling, of matching the structure of the programs to the function in the problem domain, but also because search can fail. It can bog down, it can prematurely converge, it can waste your time or fool you by racing to a false end. And trees, with their [typically] highly constrained rules for safe handling, and linear genomes with their [typically] lackadaisical post hoc sensibility, they act differently when you actually do the work.

So, given a long-winded background, what is the Push language? And for that matter what’s Nudge?

Here’s a snip of Nudge code:

[ [1, 2], ‘code_quote’, [1, 2], ‘int_add’ ]

Structurally—that is, in a literal sense—this is a tree. A nested list of opcodes and literals, with the two copies of the sequence [1, 2] “at a lower level” than the root of the program listing.

But the Push and Nudge are interpreted linearly. That is, we start at the left and read through the sequence of instructions, and when we “come to” a nested list we just unpack it and replace it with its contents. With minor exceptions.

So if it’s not a tree, why bother with the “nested” lists at all? Because of those “minor exceptions”, one of which appears in that program. Nested lists in Push and Nudge are not “branches” in the semantic sense used in typical S-expression languages. They’re block delimiters.

Here’s how that program is interpreted:

  1. The entire program is pushed onto the EXEC stack, and as a list it’s the only element
  2. The first item on the stack is examined. It’s the program is itself, and so the list is unwrapped and the elements pushed back onto the EXEC stack in the original order
  3. the new top item on the stack is the block [1, 2], and so this is unwrapped and pushed onto the stack
  4. the literal 1 is an integer, and is moved to the INT stack
  5. ditto 2
  6. code_quote is a Push instruction that acts on the next element down in the EXEC stack, shifting it to the CODE stack. That element is the list [1, 2], so that entire block is shifted as a unit
  7. the instruction int_add pops two integers from the INT stack, adds them, and pushes the result
  8. [we're done, since we're out of items on the EXEC stack] We’re left with the integer 3 on the top of the INT stack, and the code fragment [1, 2] on the top of the CODE stack.

Point being made: the first occurrence of [1, 2] in this program has no functional effect on the execution of the program, except insofar as it uses an extra interpreter step to unwrap the block. But the second occurrence is manipulated during the execution of other instructions as a block unit, and indeed in this example it remains a block unit even after it’s sitting on the CODE stack.

Push (and Nudge) programs are self-modifying linear code. What seems to an innocuous programmer to be a “tree” structure is in fact something subtler: the equivalent of begin:end or similar block markup. It’s control structure, and it forms the basis of recursion and looping structures in the language.

That’s important to understand as one implements and husbands an automated search. How should search operators manage these “subtrees” or “blocks”? Should they be aware of these code-modifying instructions to expedite search? How do you measure (or minimize) the complexity of a self-modifying program?

So that’s point one. As I said at the top, an observation, but an important one many folks apparently miss when they see Push code discussed in print:

Push is a strongly typed tree based language which does not enforce syntactic constraints. Each of Push’s types has its own stack.

And that leads nicely to my second observation—another that seems abstruse and theoretical but can turn out to be immensely practical—because there’s a second subtle misstatement in same extract [Sorry, Nic, Bill, Riccardo; I tried to tell you in the copy-editing :)].

The Push 3 language is specified as being typed, but it need not be. Again, this may seem to be a subtlety of computer science, but in practice I expect it can have useful consequences. Enough so that I’m leaning, as we’re developing the Nudge interpreter, far away from that consensual restriction.

Push’s typing, strong or not, arises within its interpreter loop. As we saw in example above, the Push interpreter’s root behavior—the core of its control loop—is to pop the top item on the EXEC stack and act on that. If the item is a code block, then the contents are pushed back onto the EXEC stack in the same order they originally occurred. If the item is a defined NAME (or, in the Nudge interpreter, a bound variable), then the value associated with the binding is pushed as a replacement for the original string. If the item is an instruction, then the algorithm invoked by the instruction is executed, typically with the result of moving items present in specified stacks. Finally, if the item is a “literal”—an integer, floating-point value, boolean or string—it’s pushed onto the appropriate stack.

In Push 3, the “appropriate stack” we use for integers is the INT stack, floats go to the FLOAT stack, booleans to the BOOL stack and [unbound] strings to the NAME stack. And “explicitly typed” instructions reach into clearly specified stacks, not stacks based on the type of their contents; Push’s INT.+ (Nudge ‘int_add’) reaches into the INT stack by reference for its parameters, not because the INT stack contains integers, and it pushes the returned value into that same stack because we tell it to.

But what’s wrong with duck-typing? Nothing, not even in the Push 3 specification. The specified details of contingent behavior of the interpreter’s recognizer says integers go to INT. But in practice, nothing dictates we couldn’t use a NUMBER or SCALAR stack. Or define a suite of instructions called scalar_add and scalar_negate, whose results depend on the types of the parameter values. Add a float to an integer, and you’ll get an answer cast as a float in most programming languages.

It’s a tacit assumption. Not a necessity.

Suppose we did have a SCALAR stack, where integers and floats and complex values and characters all go to live. And we implement a fancy scalar_add, that always pops the top two SCALAR values, and lets the type be defined by the first parameter, discarding “extra” information like complex components or fractional value by truncation or rounding. Suppose [3.4, 2, scalar_add] gives us 5.4, but [3, 2.4, scalar_add] gives us 5 (the integer); [3 + 4i, 2.2, scalar_add] might provide the complex result (5.2 + 4i).

Does it matter? No, insofar as the behavior is consistent and predictable, it’s a suitable substrate for both hand-designed and automated programming. The framework that results might end up being more or less brittle, but as long as the underlying rules are internally consistent and don’t result in syntax faults, it’ll still work.

Is what I’m describing still Push? No. Because what I’m suggesting is something that takes Push’s explicit statement of types and generalizes it into an arbitrary sequence of recognizers. The recognizer loop of the Nudge interpreter is becoming more like this: Is the next fragment “code” (for some definition of that class of structures)? Is it a string that appears as a key in a finite list of bound key:value pairs? Is it a string that I recognize as an instruction? Is it some other literal (integer, float, boolean, string)?

The first possibly useful consequence is the relaxation of the relationship between type and specific stack. Why not have two named “boolean” stacks: BOOL1 and BOOL2? Why not have instructions that shift boolean values between them?

And then the snowball starts rolling: Why not have a stack of “boolean” stacks, and instructions that shift items “up a level” and back down? This isn’t theoretically different from the potential of Push’s explicit stacks; you could do it as things stand right now, with the right Push code infrastructure in place. But trust me when I say it would be a royal pain to breed that infrastructure, to automatically discover the surrounding “subroutines” that subdivided the one BOOL stack into zones and flipped stuff around.

And let the snowball roll on farther: What about instructions that create new, “named” stacks? Or recognizers? Or which restructure the order or importance of recognizers in the interpreter’s core loop? Or alternate EXEC stacks came into being as parallel threads? What about an ITERATOR or GENERATOR stack? And so on, and so on.

The point is not to bloat the system with unnecessary extravagance. It’s to consider the practical utility, the reachability of useful solutions represented in a given language. Things become easier and harder to code by hand, or to discover automatically, when you make these changes to the fundamental architecture of a system that’s the substrate for algorithmic search.

And the point we’re heading for—though we’re not quite there yet—is to improve the usefulness of the Nudge interpreter. So sometime soon we’ll probably start haring off in this new direction, where types and recognized code fragments are a matter of application-specific ontological decisions, not inbuilt in the interpreter itself.

Update: In reading through this, I realize I should give credit where it’s due: I’m sure almost everybody working on the Push language projects through the years has proposed extensions and modifications, shifts in architecture and new ways of making it work on the lowest level. My point in all this, really, is to say we’re trying to make that easier to pursue, by keeping units of function in the interpreter itself cleanly separated.

Filed in Nudge | | Permalink | Comments (0)

Status report

Tuesday, July 29th, 2008

So Brian’s enigmatic “howling” post was about our Redmine project tracking software being a bit broken. It’s been fixed, and in the meantime we have implemented all but three of the Push3 instructions in the Nudge interpreter.

At the same time, we’ve been working in “back burner” mode on search functionality: the genetic programming (and particle swarm and differential evolution and hillclimbing and simulated annealing) engine that will take individuals from a search over the space of Nudge programs, evaluate them according to user-defined objective functions, and intelligently select new ones that are better. That’s a big chunk of design spikes, and we’ve got a strong feeling there’s a lot of useful stuff in the design spikes that can be simplified down into a clean, elegant solution for interactive search.

So at the same time we’re polishing off the last of the Nudge Interpreter’s ability to execute Push3 programs, we’re gearing up that effort.

I’m thinking what we should do is plan our first public release of the Nudge interpreter (which will execute Nudge programs, and potentially translate to and from Push3 syntax) as a separate event from the search system. It might take a few weeks to get the implementation done on that, and while there aren’t exactly thronging masses clamoring at the gate, it would be a nice milestone.

Filed in Nudge | | Permalink | Comments (0)

we’re howling into the moon, here

Monday, April 7th, 2008

The activity tracker in the project management thing we are using (Redmine) has sort of drifted off into the wilderness. So this is just to say that some of the issues are getting closed out, even though you’d be hard pressed to tell.

Filed in Uncategorized | | Permalink | Comments (1)

Errors

Thursday, April 3rd, 2008

We made a design decision a while back. Every objective should be a scalar minimization.

What’s an “error”? Programs just run in Push and Nudge. They don’t make decisions, they don’t do much of anything; they just shove shit around, they do a little math now and then, they’re in their own little worlds. So it’s necessary to consider how best to interrogate the state of Nudge program at the end of an interpreter run. The interpreter just hands you back a set of stacks. You might have a stack of integers, and a stack of floats, and a stack of booleans, and so on. How do you use that mess to derive a scalar evaluation of your program’s performance?

Let’s restrict ourselves to the case where we’re creating a numerical model. We handed some input data to the program, and we want to interpret something it’s done as “output”. For the sake of argument, say we’re looking at one integer. We gave it weather data from yesterday, it’s trying to predict temperature today in degrees. We gave it medical observations from a patient, it’s trying to predict their life expectancy in days. We gave it the number of cars parked in all the garages in Ann Arbor over the last week, and it’s trying to predict the total beer revenue at Arbor Brewing Company next week, in dollars.

The program doesn’t “know” what a degree, day or dollar is. It’s like some stupid tourist in a far-off land, emptying its pocket and proffering a bunch of foreign coins and gum and bus tokens. “Here! I don’t know! You take what you need! Please, just take it!” It’s got integers, it’s got floats, it’s got booleans.

You’re the decider.

The simplest thing, of course, is to just take the top integer on the program’s integer stack. Use an arbitrary rule: top integer is defined to be the “output”. You want an integer (degrees, days, dollars), you can have one. If you want to get fancy later on, maybe you make a more complicated rule: topmost non-negative integer, or sum of the top five, or something. For now, stick with “top”.

You run the program and hand it the input data, and it stops running and holds out its random bundle of crap. You reach precisely into the pile and pluck off the “output”. If the program hasn’t managed to drum even one integer up in the course of its run, or if it’s frittered them all away, well too bad, Program: penalize severely. Otherwise, just say “prediction←topmost integer on stack” and be done.

But you have an integer. Assuming you have a bunch of test cases, you have a bunch of integers. How do you assess the accuracy of the “model” your stupid program has internalized?

There are dozens of well-known possibilities for error statistics, and unlimited potential to make stuff up. Don’t forget what it says in the book: every function of data is a statistic. Assuming we want to stick to well-trodden commonplace material, this summary may be a good place to start a shorter list.

I like their list. Mean Squared Error is common and familiar; everybody learns it in high school. It’s rare to meet somebody even in these advanced days who understands why it’s stupid to use it unthinkingly, but it’ll do in most cases. It’s useful.

Note though there are others. A lot of people pushing decision support tools don’t bother to include Bias measures, or Mean Absolute Percent [or Proportional] Error. And that distorts the user’s perception of success. There are many ways to be wrong in numerical modeling; you should always consider different gauges to see what’s happening with your models.

There’s a whole slew of specialized (and general) metrics that should also be available for the general-purpose modeling framework. You may not always want to fit data individually; maybe you want to match a distribution, and you’ll want to use KS or AD tests. Maybe you want to assume a bunch about the way your model behaves, and can get away with using 1−R2 (since we’re always trying to minimize error, you’ll want a smaller objective to be better). If you’re doing classification instead of numerical modeling, you’ll want measures of classification error.

In any case, here’s the interesting benefit about multiobjective optimization: You don’t need to decide. You can throw them all in, if you want; you can minimize MSE and minimize [the magnitude of] Bias and minimize MAPE. All at the same time. Some models will be better at matching by MSE; some will be less biased. You want to collect them all, at least the nondominated ones.

We’re all stupid. But it’s less immediately stupid if you postpone decisions about which error measures to use until the last moment. Be like the programs themselves: “Here, I have these! You pick!”

Filed in Nudge | | Permalink | Comments (0)

Search algorithms

Wednesday, April 2nd, 2008

There are really three basic genetic programming algorithms I like to use out of the box. One’s stupid, one’s (almost) standard, and one’s pretty fancy and effective.

Start with one nugget of assumption: Every search algorithm should be multi-objective. Period. No exceptions. You do a single-objective search on any real-world problem, you’re either lazy or a liar. The end, no exceptions. I don’t care if you’re an Operations Research guru or a lone stock trader looking to make a buck, no problem is single-objective.

So when I say “better” in any context, I am talking about Pareto domination, or if you’re an economist kinda girl, “relative Pareto efficiency”. Say you have two alternatives, A and B, and you’re deciding between them on the basis of two minimization objectives, w1 and w2. A is dominated by B if w1(B)<w1(A), and w2(B)<w2(A). B is dominated by A if w1(A)<w1(B), and w2(A)<w2(B). Neither one dominates the other unless it is strictly better on all comparisons. Otherwise, A and B are nondominated by one another; they can’t be differentiated in a meaningful way without saying which objective is “more important”.

You want to survive a car crash, or do you want to drive really really fast? Which is better? So, get that into your head. There is never one objective. Never.

Let’s make sure we understand why there are always multiple objectives in GP runs. You want accuracy, right? But you also want parsimony. You’re evolving models, solutions to problems, functions, structures. Things can get hairy very quickly in a runaway evolutionary world: programs can get superstitious, they can inherit weird cultish quirks, like learning to use “Cosine(0)” or Sqrt(Sqrt(Sqrt(Sqrt(Sqrt(8.9912)))) instead of “1″, if some forgotten ancestor happened to find that first and passed it on as Big Math Juju. So as God of Your Little Engineering Problem trust me: you honestly want to reach down out of the clouds and say, “Hey, guys, chill. Remember, we use our human-readable voice when we model, OK? Two commandments here: accurate, and succinct.”

So there’s an intrinsic reason right there why you want to minimize model error and model complexity. At least two objectives. Always.

Because there’s always a less efficient way to solve any problem without sacrificing accuracy.

Anyway, those search algorithms.

“Stupid” is random search:

  1. Create a random program, and evaluate it
  2. Create a new random program, and evaluate that
  3. Throw away the one that’s dominated, or the newer one if neither is dominated
  4. Go to 2

Seem so ridiculous it’s not worth considering? Not really. It’s essentially the worst you could possibly do, knowing nothing about your search problem. So if nothing else, it provides a useful baseline, as well as a nice test of your randomization methods, evaluator timing, and other infrastructure that almost any search algorithm will share with this dumb-as-a-sack-of-hammers approach.

Plus: Easy to explain? Damn straight. Always run random search on your problem, with your representation, full-fledged evaluation, and data collection system in place.

“(Almost) standard”? Steady-state Pareto tournament selection works for me for a number of reasons, at least as a first approach:

  1. Create a population of, oh I don’t know, 500 random programs
  2. Select a tournament of maybe, ummm, 10? yeah 10 programs from the population, uniformly at random, and evaluate them
  3. Identify the nondominated “best” programs among them, and the dominated not-so-best ones, and split them into two groups
  4. If there are no dominated ones, pick one of the “best” pool at random and demote it out of spite. If there’s only one “best” program, it’s lonely, and inbreeding is bad, so promote one of the lesser ones out of pity.
  5. Replace all the programs in the not-so-best pool with offspring of the nondominated “best” pool
    • Pick two parents, with replacement, from the nondominated set
    • Use one-point crossover to make offspring
    • Mutate the babies slightly, here and there, to taste
  6. go to 2

OK, I confess. This is standard in almost no ways whatsoever. It’s a “standard” toolkit for me, sure, but it’s a pretty far cry from Koza’s classic lockstep population-based methods, the kind everybody and their brother has copied wholesale. I like it anyway: it gives rapid feedback on progress, it’s kindof elitist (except for that “spite” step), it saves a lot of search time by limiting expensive multiobjective comparisons to relatively small pools, it works with fitness caching. It’s not perfect, but I already linked to the NFL Wikipedia page, so what are you, so dumb you can’t read? Nothing’s perfect.

Fancy and effective? I really like the ParetoGP method from Mark Kotanchek and Guido Smits (and their colleagues):

  1. Create an Archive of 500 random programs
  2. Create a Population of 500 random programs
  3. Create a container for the Next Generation (an empty list; hold onto that)
  4. Select a tournament of 20 Archive programs with uniform probability, and evaluate them, and forget about the dominated ones. Just make a list of the nondominated ones from the Archive tournament.
  5. Select a tournament of 20 Population programs with uniform probability, and evaluate them, and forget about the dominated ones. Just keep the subset of nondominated ones from the Population tournament.
  6. For each Population tournament winner you got from step 5, pick an Archive tournament winner you kept from step 4, at random. Cross them over to create an offspring, maybe with some mutation if you must.
  7. Stick the baby into the Next Generation. If you have 500 programs in the Next Generation, replace the Population with it and go to 3. If you’ve run out of tournament winners before filling the Next Generation, just go to 4. If you choose to attack the Orc, turn to page 88.
  8. You’re going to be wondering when you stop cycling the Next Generations back into the Population, aren’t you? Oh, I dunno. Pick a number. Say “10″. Go on, say it. There: do it ten times. Or more. Or less. Whatever; it’ll work.
  9. Aha! But then: once you’ve done your ten renewals of the Population (what Kotanchek and such call a “cascade”), you’re not done. Oh, no, boyo. You get your butt up there and you start the whole thing, all over again at step 2. That’s right. Another cascade, from another new, random Population, and another ten generations or so. But—but—before you do, take the final Population, the best best best of that cascade you just finished, and you stick it into the Archive. Add it to the programs that were already there, and take the time to trim the Archive back down to 500 programs. You can do a full-fledged 1000-wise Pareto tournament if you have the time, or you could do some other cunning selection method if you want. Often I tend to do something quick and dirty, like just picking tournaments of 20 and culling all the dominated ones until the Archive size drops back down to 500. So, anyway, you were going back to Step 2 to run another cascade.
  10. Do that until you’re bored.

Now this is a close approximation of the ParetoGP algorithm described in a number of papers by Mark Kotanchek, Guido Smits and Katya Vladislavleva. It’s a broadly customizable framework, and if it seems like a lot of extra work compared with the “simpler” GP algorithms described above… well, that may be true. I like it very much because it exposes exploitation (via the Archive) and exploration (via the Population) as almost separable processes. You feel like things are getting stuck, let the Population grow a bit and do more random restarting and exploratory search for weird alternatives; you feel like things are getting too wild, you do fewer, shorter cascades and keep a bigger Archive, really nail down the variations on the already-discovered themes you’ve collected there. Play around, fiddle the knobs, see what you get.

And that’s the point, of course. There is no “best” search algorithm. Don’t make me link to that paper again.

You have to pay attention. You have to bring to bear a vast combinatorial armamentarium. You have to keep a seven-drawer toolbox in the virtual garage, with a hundred different wrenches in it, and then look at your problem and listen to your algorithm purring along, and reach into a drawer without looking and find just the right tool, and give that algorithm a little tightening here, a little shimmy there, grind a bit off the edge, take it apart and put it together again slightly better. With grease.

See, it’s not about solving your problem as fast as possible. It’s about watching it improve, and having the sense to see it improving. About having the tools on hand and the experience under your hat so you can intervene in a reasonable and effective way.

So, yes: there are other ways. None are best.

Filed in Nudge | | Permalink | Comments (2)

How we think we’re doing it, here

Monday, March 31st, 2008

In stolen moments. Afternoons, weekends. Together, mostly.

So far, that’s about it. (And so far, so good.)

Sufficiently

One problem: we haven’t done sufficiently for one another to make it easy to work on Nudge in these stolen moments and weekly-ish meetings together. The whole stupid xp / agile thing doesn’t work, since none of us are embedded in the project on a steady, consistent basis. We don’t need to justify our rain-hungry expanses of time to some control tower, and then bail half-baked some fiscal quarters later. (We can bail half-baked without structure to enable that behavior, thanks.)

Nudge is important, but it’s not the first thing on anybody’s list.

So there’s this push towards a collection of stories goals designs objectives: a frontier of things that need to happen for Nudge to happen.

With some edges of this frontier scoped out sufficiently that we can peel off little one-hour-ish chunks of work to perform and commit.

Not the best

I wonder about quality of the work we do in this environment. I know it’s not my best. Part of that is because I am learning by doing (all this GP stuff is new to me; that’s why I’m grateful for this little black book PDF). Another part is that Nudge never gets the best of my time or energy. But software isn’t about quality, it’s about bringing light into the world. It just has to be something that wasn’t there before, with [1] decent test coverage and [2] reasons for being both plusses. And on that count, I’m pleased by what’s happened so far, since it’s more than we had before, and it seems in danger of becoming something genuinely, demonstrably useful.

Filed in Uncategorized | Tagged , , , , , , , , , , , , , | Permalink | Comments (0)

What we think we’re doing here

Monday, March 17th, 2008

…in one-liner bullets:

As of this writing, we’re:

With luck, we’re getting close to our next iteration release. We’ll post a coherent code repository. Watch this space.

Filed in Nudge | Tagged , , | Permalink | Comments (2)