The Learning of Parameters for Generating Compound Characterizers for Pattern Recognition

Introduction

Programs that have used n-tuples as their characterizers appear to perform with the very best of pattern recognition programs (for discus­ sions, see Uhr, 1963, 1969a; for a good recent example, see Andrews, Atrubin, and Hu, 1968). This is not surprising, for n-tuples are easily handled by the digital computer. And although Programs that use n-tuples either have them designed by human beings and pre-programmed in (e.g., Andrews, Atrubin, and Hu, 1968), or ran­ domly generate a fixed set of fixed-n-size n­ tuples (e.g., Bledsoe and Browning, 1959). An interestingly simple generalization of this is the following: Let the program begin with no char­ acterizers, but have it generate new character­ izers that are as simple as possible, and only when needed. Thus the program might start by generating one 1-tuple, continue generating more !-tuples as it finds itself continuing to choose wrong names to assign to input patterns, and at some point begin generating n+l-tuples. It further should be assessing how well each characterizer is working, by in effect conducting a running ex­ periment that examines its successes and failures. This information should be used a) to weight the importance of this characterizer' s implications in combining them for the decisions as to names to choose·, b) to decide whether a characterizer is good and should therefore be used, or is bad and should therefore be discarded, to be replaced by another, and c) to gather information about gen­ eral ~ of characterizers, so that new charac­ terizers are generated that are similar in impor­ tant parameter values to characterizers that have proved themselves good.

This paper describes a program that is a first approximation to this simple, but hazy, scheme of generating as few characterizers as needed, keeping them as simple as possible, but using what has been learned about charac­ terizers to direct the generation of new charac­ terizers, so that they will be similar in their characteristics to good characterizers that have

been generated in the past.

The program has a second general purpose - to puch deeper into techniques for learning char­ acterizers.

The basic structure of this program seems to us extremely simple - the generation, when needed, of the best new specific n-tuple of the best general type possible, and the learning of as much as possible. But when the program is described or given in detail, as in the following pages, it inevitably sounds more complex - for indeed it is more complex when forced to the level of code for a discrete digital computer. In order to get flexibility into our n-tuples so that they need not be precisely positioned and can be considered to match even though all parts do not always match, extra details must be added to the code. These in turn suggest additional learning mechanisms that will search for good values for this allowed wobbling and threshold matching.

There are also several points at which we simply evade quite subtle decisions that should be made by the program: Should the program spend more time adjusting the weights of its present set of characterizers, or should it gen­ erate one or more new characterizers ? This we handle by having the program generate one new characterizer per pattern, up to a fixed maximum (also discarding characterizers found to be bad, to make room for more). When the program generates a new characterizer, should it be of the same size n, or of size n + 1 ? This we handle by treating n-size as just another para­ meter, so that, as described below, the program will choose the n for a new tuple as a func­ tion of the goodness of the tuples of different n-size that have been generated so far. Thus n is initialized to equal 1; the program will keep tabs on the goodness of each n-size and will generate tuples with an n-size that reflects this goodness, but with some probability will occasionally generate a new tuple of size n + I. Thls procedure is used for all parameters of characterizers.

Precursors

As an introduction to the structure of our program, let us consider the Bledsoe-Browning pattern recognition program (1959), which was among the first to use n-tuples randomly se­ lected from the input grid to recognize typed or handwritten characters. For each n-tuple, the possible pattern names having the same state as the unknown input pattern are added into a comparison tally. After all tuples are consid­ ered, the name that matches the unknown pat­ tern most closely (i.e., having the highest sum of same-state n-tuples) is chosen as the name

of the input pattern.

Using the string manipulation language SNOBOL, Uhr (1969b) coded a somewhat extended version of the Bledsoe-Browning program. Uhr's short program uses weighted implications, rather than merely tallying them, and it allows varying sizes for the n-tuples and for the individual

pieces of the n-tuples.

There are several weaknesses in this type of program: It does not learn, so its perform­ ance remains only as good as the n-tuple characterizers it starts with. . N -~uples are rig­ idly positioned, and must match exactly and entirely.

A Basic N-Tuple Pattern Recognition and Learning Program

Let's try to generalize the basic n-tuple pro­ gram. For example, the characterizer tuples will be looked for one part at a time, instead of all at once. Each tuple piece of the character­ izer n-tuple will contain pertinent information about its expected location within the pattern grid, its size, and the specific configuration that should be found. Optionally, a tuple ·part will have no particular position specified, sig­ naling the program to look anywhere (presently meaning from its current position on down) for this tuple part. If a characterizer is matched, its implied pattern names are put on a list of found implications. When the same name is im­ plied by several characterizers, the separate weights of implications are added together. The tuples are allowed to be non-exclusive, so that grid points in important locations (such as, per­ haps, the left edge of the grid) may reappear in several characterizers.

This basic program will also have the abili­ ty to learn from its experience, by comparing its chosen answer with the feedback giving the cor­ rect pattern name. If the program gave the right answer, the memory is left as is, since it pro­ duced satisfactory results. But a wrong answer calls for reweighting of implications in the char­ acterizers whose tuple configurations were matched. The weights of implications : of the wrongly chosen name are decreased, and impli­ cations of the feedback name are increased. If the answer was wrong the program will also gen­ erate a new characterizer using this wrongly named input pattern. To do this, a random n­ tuple is extracted (n is chosen to reflect the distribution of weights attached to the generated values of n) from the input and assembled into a characterizer which implies the correct feed­ back name. Each run has an upper limit to the number of characterizers generated, to prevent saturation of memory or unnecessary slowing of processing time. Poor characterizers are dis­ carded, making room for new ones, when the weights of all their implications fall below a

minimal acceptable level.

Characterization Over Variations

Presented with only standard, non-varying instances (in a single type font, perhaps) of its repertoire of patterns, it is no great problem for a pattern recognition program to learn to recog­ nize a set 'of characters. But if patterns can vary, even slightly, in position or shape from time to time, then problems mushroom. Our program tries to handle this in several ways. Wobbly Patterns Each part of a tuple is allowed to wobble a given horizontal distance to either side. (A somewhat more limited capability for handling vertical wobbling is the "anywhere" search men­ tioned previously, plus the fact that all tuple part addresses are given relative to the last position, wherever that may be. Uhr (I969b) presents programs that also allow vertical wob­ ble.) In each characterizer tuple part there is an explicitly given wobble which tells the pro­ gram just how big a hunk of the grid row it can look in for the desired configuration. This al­ lowable wobble may vary from tuple piece to piece, as learning has indicated was needed for good performance. Thus if a desired configura­ tion was not found within the specified wobble, but would have been found were the wobble slightly larger, then the program remembers how it almost found this characterizer. When feed­ back shows it chose the wrong name, if the program finds that this almost-matched charac­ terizer would have implied the right answer, it increases the wobble allowance to improve per­ formance.

Threshold Characterizers that Can Partially Match

Suppose that three parts of a 4-tuple were found, but the other part was not. We would like to allow use of the implications of this nearly matched characterizer even though the program did not find a perfect match. In order to do this the program uses threshold matching, where each part of a tuple has its own weight to add into the tuple's sum of ''foundness." Each implication of the characterizer is preceded by a threshold requirement which must be met by the tuple sum before the implication may be merged into the list of possible pattern names. Thus one implication may" require all but one part of the tuple's configuration to be found, where another implication of the same character­ izer might require a perfect match of all parts.

Compound Characterizers

Besides having a primitive sort of tuple con­ sisting of a set of 0-I configurations to be looked for at certain points on the pattern grid, our program can also use compound characteri­ zers, where one or more of the tuple parts is itself the name of another chara cterizer. The program looks in the stated position (or else ''anywhere") for the name of the desired compo­ nent characterizer and treats this tuple part just as any other. Now the program must add the names of found characterizers to the input that it is processing.

Compound characterizers are currently gen­ erated from primitive characterizers that are on the list of characterizers found for this input. There must be two or more such component char­ acterizers in order to generate a compound char­ acterizer. When the program decides to gener­ ate a compound characterizer, it chooses the maximum number of parts to give the tuple. Then the parts are pulled off the list of charac­ terizers found in this input, and the characteri­ zer is assembled as initially implying only the feedback.

These compound characterizers are more gen­ eral than primitive characterizers in that a more sophisticated set of pattern characteristics can be represented by one tuple. Indeed, with com­ pound characterizers we approach a method for learning stroke or feature recognition, where primitive characterizers might represent the vari­ ous primary curves and lines, and the compound characterizers could form the desired combina­ tions of strokes to imply the various patterns. For example, if CHARI is the tuple describing a small open-left curve, CHAR2 is a long vertical line, and CHAR3 is a large open-left curve, then CHAR4 compounding CHAR2 and CHARI could imply the pattern "P" and CHAR5 coupling CHAR2 and CHAR3 could imply "D".

Parameters That Characterize Characterizers

An important part of learning in humans is generalization. In order to enable our program to, in effect, "generalize" on what it has learned and thus perform better, we have given it an expandable set of parameters or character­ izer traits. For each trait (such as the number of parts, or their closeness, or their maximum horizontal spread), a value can be computed for every characterizer. With every characterizer there is associated a list of this characterizer's value for each trait. In addition we keep a common traits list of all traits and all values that have been generated and used for them. A weight is associated with each value for each trait. For example, suppose the program gives a wrong name for an input pattern on the basis of found characterizer N. Then after the im­ plication weight of the wrong name in CHAR N is decreased, the program goes through the trait list of CHAR N and, for every trait, downweights CHAR N' s value for that trait in the common trait list. In particular, if CHAR N's value for VERTSPRED (vertical point spread) is "I", then our program will look for the value "I" under the trait VERTSPRED in the general characterizer traits list, and decrease the "goodness weight" of the value "I".

When upweighting a good characterizer' s trait values, the program also enters (if not already there) on each trait value list a slightly larger parameter value, In this way it broadens the range of parameter values that will be used to generate new characterizers. The value and goodness weight information in the general traits list is used when a new characterizer is generated. The program tries to generate the new characterizer tuple within the framework of what the program has already learned; currently it uses the three traits necessary to control the basic generation (tuple size, piece size, wob­ ble) plus a fourth chosen randomly from the other possible traits (currently, these are hori­ zontal spread, vertical spread, average close­ ness of parts, number of parts on the edge of the grid, and compound or primitive). A de­ sired value for the new characterizer is chosen with a probability that reflects the weights as­ sociated with the various possible values of the trait. The program tries several times to find a randomly positioned tuple which will have this same value. Thus the program generalizes on what it has learned, in that if a value of "6" for VERTSPRED has been upweighted several times, the program may decide that this is a good value to try for in a new characterizer. (For further details, see functions TRAITWT and PROBCHOOSE and the section labeled PRIMITIVE in the precis and the code.)

The Complete Program

The preceding sections describe independent features, any or all of which could be added to a Qasic learning program to create a complete program. The final program containing all the features is described at the end of this section. As might be expected, the characterizers for this final program have become fairly complex. As an example,

CHARO = "D=0.1.1*0-2,5.3.4*01-1, / " "I=3*I.2,1*T.1, / "

"P=CHAR4 ,/T=TR0/ 1=5. 4/ "

means the following:

".Qescription=at row 0, column 1 look in the next 1 position for the string "0" , adding 2 to the tuple sum of weights on success; 5 rows down and 3 cols, over look in the next 4 posi­ tions for the string "01 ", adding 1 to the tuple sum on success/lmplications=if sum ~ 3 then imply I with weight 2; if sum ~ 1 imply T with weight 1/CHARO is Part of the compound CHAR4/ Trait list na~e=TRO/Last tuple part's absolut; address is row 5, ~ol. 4/ ",

An outline of the program's operation fol­ lows.

Detailed Description of Program

StiHgment

described. The program itself is given in the Appendix. Thus the reader can examine exactly what has been done to implement any of the aspects of the program about which he is curi­ ous. This seems to us of crucial importance: if the program can be used to document itself there is no need for lengthy and usually mis­ leading descriptions and discussions.

The program listing is too long and complex to be followed with ease, even by someone who knows SNOBOL; but it should give an idea of what's going on to the casual observer, and those parts in which the reader is interested enough to make some effort should become un­ derstandable. SNOBOL is a very simple lan­ guage in its basic conception, for its programs are built up from sets of production and re­ placement statements (of the sort "Let A= B; Look for C on A and, if it's found, replace it by B), tied together by labels and gotos. A brief description of SNOBOL is given in the Appendix.

This program was written to exa·mine whether a wide variety of learning methods could be implemented together in a single pat­ tern recognition program. Using the language SNOBOL allowed us to code a relatively power­ ful, yet short, program. However, the program runs too slowly to make extensive tests of its abilities to learn and achieve interesting asymp­ totic performance levels. We therefore give only a brief listing of a short run, to indicate that the program works, and that it at least be­ gins to learn. The program will be recoded in a faster language if we decide to make more extensive tests.

Further developments might be to have the program try to learn good weights of character­ izer tuple parts and the thresholds required to imply a pattern name. We would also like it to generate new parameters with which to char­ acterize its characterizers (see Uhr, 1969b).

Summary

The program described in this paper at­ tempts to combine a very simple basic pattern recognition scheme with a wide variety of powerful learning mechanisms. The program at­ tempts 1) to generate its own n-tuple charac­ terizers as needed, and to adjust their weights as a function of feedback, 2) to decide what type of characterizer to generate, and 3) to learn what are good general characteristics of characterizers. It can further decide 4) whether and how to modify any particular characterizer that it is evaluating. These decisions are all made within the framework of a program that tries to recognize patterns with as small a set of characterizers that are as simple as possible.

It therefore starts out with no characteri:(;ers, and generates other characterizers which are as simple as it has been able to get away with and which fall within the range of what the program conjectures to be optimal values for the charac­ teristics of characterizers. In terms of charac­ terizer size, this means the program starts out generating !-tuples and then, to the extent that feedback indicates that it must improve upon its performance, 2-tuples, 3-tuples, and n+ !-tuples.

Acknowledgements

This research has been supported in part by NIH grant MH-12266 and NSF grant GP-7069.