# Joy, Genetic Programming, and Handwriting Recognition

## cpcogan — 2007-01-08 02:15:55

    [This is rather long. You may want to just skim it first time through,

    to see if it's even something you want to bother with.]

    Imagine a version of Joy in which all the terms used would never cause

    an executing program to crash. Instead, they would leave an error code

    somewhere, so subsequently-executed code could reference it if it

    wanted to. Now, imagine that we generate strings of valid Joy code,

    and try executing them with given input and with a place to put their

    output. Then imagine that we build a mechanism that generates strings

    of Joy code, executes them, and checks the actual output against

    test-output. If there is a match, the string of joy is retained. If

    not, not.

    The strings of Joy are built in batches of, say fifty at a time. They

    are all tried on (let us suppose) a hundred examples of input and

    hoped-for output. For each generation, the top few are saved and used

    as the "baseline" for the next generation of fifty strings of Joy

    code, each of which is a variation on one or more of the saved strings

    (at some point we can do recombination of bits of Joy, and thus have

    "The Sex of Joy"   !!!  ;-)   )

    This process is repeated until we get at least one string of Joy code

    that does a very good job of producing the right outputs for all of

    the inputs. Then, we give it a test on input data it hasn't seen, so

    as to exclude cases where the evolver evolves code that is effectively

    hard-coded for the particular input we have. When we get something

    that really seems to work, we increase the difficulty of the task by

    providing more-difficult input-output pairs (making the inputs more

    complicated, generally). Each time we get a very good success rate on

    what has been required so far; we increase the difficulty.

    The reason for wanting errors not to crash the whole program is now

    obvious: We don't know what code will be generated, by the evolver,

    and we don't want to needlessly constrain the code to non-crashing

    code (even if we knew how to do this mechanically while still doing

    anything interesting).

    My own desired application would be handwriting recognition. We start

    with input-output pairs that consist of bitmaps of single-stroke

    symbols (backslashes, slashes, hyphens, and maybe parentheses, etc.).

    For each bitmap we have an output that the generated code is to

    produce if it works.

    We set up the system as described above, with a bunch of input-output

    pairs, and let it run (overnight, a week -- it doesn't much matter, if

    we are letting the computer do all the work).

    Eventually, we would, if this method works, produce a program that

    could take any amount of handwritten text that's sufficiently similar

    to that used during development and process it with about as much

    accuracy as we can expect from software that doesn't know a lot about

    the meaning or context in which the material was written.

    Why am I interested in handwriting recognition? Well, I'm not, really,

    which is why I would use this approach instead of a more nearly

    conventional approach (the conventional approaches don't seem too

    successful anyway). By using an evolver to evolve handwriting

    recognition, I don't have to know what I'm doing. More accurately, I

    don't have to know what the code the evolver produces is doing. I

    don't have to know about edge-detection, curve recognition, the shapes

    of letters, whether they are connected to each other (one recognizer I

    tried only works if you feed it handwriting in which each letter is

    disconnected from the previous and the next letters -- but my

    handwriting is more or less normal script, with each letter in a word

    connected to at least one other letter, so the program was a failure).

    With an evolver, I can even let it evolve its own general approach. I

    don't have to decide whether to try some sort of Bayesian analysis or

    God knows what. I just give it what it has to do and let it find its

    own way of doing things. This may mean that re-starting from scratch

    and using the current time for the randomization seed could cause it

    to ultimately produce wildly different solutions at the end, and that

    would be very interesting but, if my goal is handwriting recognition,

    I don't really care about that. As a programmer, and a student of

    computer science, I might find it fascinating if one "from-scratch"

    run produced a solution that was truly different in fundamental

    approach from another "from-scratch" run, but the immediate goal is to

    produce a good handwriting recognizer (and only for my own handwriting

    at that).

    But, I have about 200 POUNDS of handwritten material (and many

    thousands of pages more already in a computer-editable form) that I've

    written over the past forty years, and I'd like to convert some

    significant portion of it to editable text, so that at least a small

    portion of it could possibly be published. (I joke that I have

    "Asimov's Disease" but without all that annoying fame and monetary

    success.).

    Worse, there don't seem to be any commercial or freeware or even

    shareware programs that do handwriting recognition on text that is

    already written (i.e., scanned, not written directly into a device

    such as a PDA). Much of the existing software depends on processing

    the strokes as they are entered, so it knows whether one stroke or

    part of a symbol was done before another part. I came across a paper

    describing an experiment in recognizing more or less unconstrained

    scanned handwritten text, but it was an old paper and I got no

    response to my one e-mail, and it is likely that the program would not

    be available for others to use anyway.

    Further, I have come across experiments in very limited genetic

    programming, where genetic programming was used in conjunction with

    pre-determined methods based on a pre-determined theory about how to

    do handwriting recognition. I suspect that this is not the best way to

    do it. Instead, I'm hoping, it would be better to let the evolver

    itself eventually produce its own methods that might or might not end

    up being roughly equivalent to some method that people have tried

    already. What if the evolver would develop, for example, some

    "Gestalt" method of recognizing handwriting, similar to the way people

    do it? Should we prevent it from finding such a method by imposing on

    the evolver a prior fixed idea about the type of method we want it to

    develop?

    Why Joy? Why not a conventional language? Why not Prolog?

    Conventional languages are too complex, though generating pre-defined

    bits of code is easier than recognizing arbitrary code correctly, it

    still makes for needless complexity, because we have to make sure that

    all the language constructs are well-formed (even if they extend over

    pages of code). Also, we don't normally have the ability to make sure

    that no errors in coding will crash the program, as we do if we have

    our own Joy processor. We can write a collection of functions for a

    conventional language that automatically ignore errors, of course, but

    that's almost what we do when we write a Joy processor anyway.

    Prolog is another prospect, because it has a simple syntax, and

    because the Prolog "engine" automatically searches the solution space

    for whatever code it has, and we can fairly easily make it pretty much

    immune to crash-causing errors. For years, whenever I considered doing

    genetic programming, I thought I would do it in Prolog, for just these

    reasons. Also, full Prologs allow the executing code itself to

    generate new rules (the inability to do this cleanly was a problem for

    some early compiled Prologs, like the one Borland sold), so a generate

    and test "engine" (which is what a genetic programming evolver is,

    basically, with the refinement of producing each new trial as a

    variation on an existing one, and with the ability to do things in

    batches per cycle (or "generation")).

    But I still think Joy is a better choice, because it is even easier

    than Prolog to generate, and has most of Prolog's other advantages

    (including, in my implementation, the ability to define new atoms at

    run-time). Prolog's one main "trick" is its automatic ability to

    search the entire "tree" of the solution space if you let it (more on

    this below). However, I see no reason why this cannot be implemented

    in Joy. Even better, if it is implemented in Joy, the code that it

    executes can contain normal Joy code. Let me explain, for those who

    may happen not to know about Prolog.

    Prolog works from a set of "rules" and "facts." A rule has the form:

    	name(parameters) conditions;

    The conditions are specified as a series of Boolean expressions

    separated by commas, like this:

    	name(parameters) condition1, condition2, condition3, ... conditionN;

    In normal execution, the conditions are processed sequentially until

    they are all used up or one of them returns false. This means that the

    string of conditions is essentially a lazy-execution string of

    conditions ANDed together. Thus, we might have a rule like this:

    	dog(animalname) hasfourlegs(animalname), barks(animalname)

    (Somebody correct me if I've gotten this wrong; it's been a while, and

    as with Joy, I never actually wrote more than the most trivial of

    programs in Prolog).

    This rule would normally mean, roughly, "A thing is a dog if it has

    four legs and if it barks."

    Each rule is thus a Boolean expression in its own right, so when it is

    used as a condition in another rule, it applies its own defining

    conditions as criteria, and returns whether all of the conditions were

    met or not. Believe it or not, this (and a little bit more) allows

    Prolog to do almost any kind of logic programming (such as theorem

    proving) you might want.

    Now, for the "magical" part of Prolog. If a rule fails partway through

    the sub-conditions, execution backs up to the last successful

    sub-condition, and then, if any more rules for the failed predicate

    are available that match the parameters for this reference, the first

    of them will automatically be tried (and, if it fails, the next one

    will be tried). Prolog will keep on working this way until it finds a

    completely successful series of rules or it runs out of rules to try.

    That is, given a database with a whole bunch of rules for each

    predicate, and given an initial question (entered in the format of a

    rule without the conditions, like "dog(fido)?" -- meaning "is fido a

    dog?"), it will keep trying possibilities until the hardware gives out

    or a crash occurs or it simply runs out of possibilities to try.

    Of course, real Prologs have ways to constrain searches, and to

    prematurely terminate a search for a solution if some condition occurs

    (such as something that indicates that no solution is possible), and

    they also have ways to do things like user-input and user-output, and

    ways to make predicates that will only be executed one time when they

    are encountered so the user isn't inflicted with millions of outputs

    where one will do, etc.).

    But the real key to Prolog is the automatic tree-searching. The

    programmer only needs to define the predicates that define the domain

    he is working with and what he wants done. If all the needed rules

    have been specified, the Prolog engine will do the rest (though not

    necessarily in the most efficient way, of course, because it is

    searching mechanically, not intelligently).

    The thing is, this mechanism is not (in its bare forms) terribly

    complicated, so it's reasonable to implement it in a language like

    Joy, even as a primitive. Doing so would allow Prolog processing to be

    freely intermingled with regular programming, thus giving us the power

    of the Prolog engine without the limitations of having to make

    everything fit into the Prolog way of doing things.  The predicates

    would be in the form of tables formed by lists of lists, one such

    table for each predicate. Each predicate would go into the dictionary

    as a Joy atom, with internal code for the appropriate processing of

    its rules.

    The entire Prolog-like engine would just be a combinatory that would

    be passed a list of lists and that would return a Boolean value. Code

    that doesn't return a Boolean to be tested could be inserted at any

    point, as long as executing it at that point would be appropriate and

    as long as it didn't leave disruptive values on the stack.

    We wouldn't need to add all the tricks real Prolog uses, because we

    wouldn't have to fit everything into the Prolog way of doing things.

    Instead, we would be intersperse chunks of Prolog-like activity into

    otherwise normal Joy code.

    Back to the Evolution Question

    The evolver would only have to be made smart enough to make sure that

    all lists were properly terminated at some point (so we don't reach

    the end of a program with lists still un-terminated and with no code

    actually to execute following the placement of the list on the stack.

    Unterminated lists (and unterminated strings and function definitions,

    as well) might not prevent our evolver from evolving solutions to our

    problems, but it would tend to slow it down.

    Back to handwriting recognition. The reason for giving the evolver

    simple cases initially is that there is a better chance of it being

    able to find a solution quickly for those cases (such as recognizing a

    forward slash). If we give it large blocks of handwriting to

    recognize, it would be very difficult to know if it has found a

    partial solution because the partial solution might not look very much

    like the desired output (for example, it might recognize all the

    letters in the input but output them all in the wrong order, thus

    producing garbage that doesn't look at all like what we are after).

    Using a bunch of simple cases makes it possible to do meaningful

    fitness testing automatically (if the output is not the desired

    character, we can be fairly sure the code is still doing something

    fairly far off the mark (though we MIGHT want to test for approximate

    matches, such as dashes for hyphens, brackets for parentheses, etc.)).

    A Visit to "Handwriting World"

    A variant possibility is this: We would construct a "handwriting

    world" in which there would be "ecological niches" for a range of

    possible species of Joy functions, all of them related (somehow) to

    handwriting recognition. The range that I have in mind is not just

    many of the possible simple-case solutions, but also a range of

    complexity, so that, over time, functions would evolve that would be

    able to "eat" larger and larger chunks of handwriting and produce the

    correct output. I say "ideally" for a reason. Constructing such a

    world would not be particularly easy, although the more I think about

    it, the more nearly feasible it seems. Disk, memory, and processing

    constraints could all be imposed as well as fitness for handwriting

    recognition (large functions that took a long time and that occupied a

    lot of disk space would be killed off before smaller ones that were

    fast and that used very little disk space, if they both produced the

    same results. These constraints would only become part of the fitness

    criteria when necessary, so as to allow as much opportunity as

    possible for handwriting success to be the main criterion.

    Multiple bits of successful code could join together in a symbiotic

    way to produce longer chunks. Thus, if a bit of code was good at

    recognizing the word "the" in the "handwriting world," and another was

    good at recognizing "cat," they might join together to recognize "the

    cat," when it was encountered (obviously, if "the cat" did not occur

    often in the "world," and if memory or disk was precious, this

    combination might be killed off in favor of bits of code that were

    more general in their abilities). Helper functions could evolve, as

    well. These would be functions that might do such things as marking

    the parts of the "world" that were just white-space, so as to reduce

    the amount of work for other functions.

    Various things could be tweaked, such as the degree of variation

    introduced in each generation, the specific Joy constructs used, the

    rigor of the external constraints, and different methods of judging

    partial success at producing correct output.

    This approach would have the main advantages of the earlier,

    more-incremental approach, without some of its disadvantages. One

    disadvantage of that approach is that the fact that the input-output

    pairs are simple might bias the evolver to overly-specific solutions

    that would later be a liability (a simple recognizer for a single

    straight stroke of handwriting might evolve well into a

    more-nearly-global recognition method (i.e., the "Gestalt" approach

    mentioned earlier), for example). Having a "world" filled with

    handwriting would allow all sorts of things to be tried that might

    work in such a world but not in an incremental approach.

    Of course, the evolution process itself would still be incremental,

    but, because there would be this "world" of handwriting for the

    "organisms" to live in, they could do their own incrementing as far as

    what they do is concerned. Since fitness would be judge largely on the

    basis of the amount of handwriting correctly recognized, there would

    be constant evolutionary "pressure" to be able to "eat" larger and

    larger amounts of handwriting compatible with correct output. The ones

    that only do a little, or that don't actually "eat" or produce any

    output text would be given fitness ratings based partly on whether

    they were used by ones that do produce correct output successfully

    (after all, we wouldn't want to cripple a major chunk of  successful

    by removing the separate functions that it depends on, would we?).

    I THINK all of this could be handled mechanically, once a large enough

    "world" of handwriting was scanned in, and once a mechanism was

    devised for being able to compare the input to a function with its

    output (this could get tricky, because we'd have to know where in the

    "world" the input came from in order to know whether or not the output

    was correct for whatever was at that location, which could involve a

    lot of tedious work by actual humans (such as, ugh, myself).

    Maybe the incremental approach would be better after all. It would

    certainly simplify things for the developer of the evolver.

    At any rate, I don't see any insurmountable barriers to making such an

    evolver for evolving a handwriting recognizer in Joy.

    Or, quite possibly, for other things as well, such as image

    recognition, electronic circuit development (as long as we have a way

    of adequately testing each proposed design, either in actual hardware

    or by very good circuit simulation in software), process design

    (again, in cases where we have some easy means of testing design

    fitness). [Note: I read of a case where an evolver was to evolve an

    oscillator, and it did so by devising circuits that picked up an

    oscillation from some other device and feeding it to the output,

    showing that evolvers may solve the problem you give them without

    solving the problem you actually have in mind.]

    I hope I live long enough to try some of the things I've talked about.

    Especially some of the handwriting recognizer ideas. I'd like to see

    comments, if you have any.

    Also, if anyone knows of available handwriting software that will

    really work on scanned handwriting and that doesn't cost more than a

    mansion in New York City, please let me know. If good handwriting

    software actually exists and doesn't cost too much, I'd still like to

    do some of the things I talked about, but more as research, just

    because it would be so wonderful to evolve something like that from

    the ground up (and then try to figure out how it does what it does).

    Now, if I could only evolve a good artificial intelligence that would

    automatically convert and edit my bazillions of drafts into

    publishable documents . . . .