Let X be a time series of vectors such as the numeric vector x = #(num| xtime x1 x2 x3 ... xm), and let Y be a numeric vector of "score" values. Let both X and Y be of length N.
The time series, X, together with the "scores", Y, are used to train this learning machine. There is also a testing set, TX and TY, of vectors similar to those in X and Y but for the testing time period (a time period not present in X or Y). After training, the machine is presented with the testing set, TX, and outputs an estimator Lambda, Estimator, which attempts to estimate ty in TY when presented with the corresponding tx in TX.
Running this Estimator on every tx in TX returns a Vector EY, of estimates for TY. Each element in EY contains a numeric estimate for the corresponding value in TY. The Estimator Lambda attempts to:
The internal model used by the Estimator Lambda to compute ey is important. The range of possible X and Y training sets and the power of the possible estimates is determined by the internal model used in the Estimator Lambda.
Linear Regression
Using the technique of linear regression the Estimator Lambda could provide accurate estimates for all X and Y training sets which had been constructed from the following model, y = c0 + c1*F1(x), where c0 and c1 are internal numeric constants and F1 is an arbitrary numeric function on members of X. If the choice of F1 is known, linear regression can estimate the values of C0 and C1 quite accurately just by training on X and Y. If the choice of F1 is unknown, linear regression works very poorly.
Multiple Linear Regression
Using the technique of multiple linear regression the Estimator Lambda could provide accurate estimates for all X and Y training sets which had been constructed from the following model, y = c0 + c1*F1(x) + c2*F2(x) ... + cm*Fm(x), where c0 through cm are internal numeric constants and F1 through Fm are arbitrary numeric functions on members of X. If the choices of F1 through Fm are known, multiple linear regression can estimate the values of C0 through Cm quite accurately just by training on X and Y. If the choices of F1 through Fm are unknown, multiple linear regression works very poorly.
Grammatical Swarm Symbolic Regression
The Grammatical Swarm Symbolic Regression uses the techniques of linear regression, multiple linear regression, support vector regression and percentile grid regression. The Estimator Lambda can provide accurate estimates for all X and Y training sets which have been constructed from the following models, y = c0 + c1*E1(x) or y = c0 + c1*E1(x) + c2*E2(x) ... + cm*Em(x), where c0 through cm are internal numeric constants and E1 through Em are valid Estimator language regression expressions. Even when the choices of E1 through Em are unknown, Grammatical Swarm Symbolic Regression works very well, performing natural order preservation as its first priority and minimizing the least squared error as its second priority. An explanation of the power and limitations of valid Estimator regression expressions is contained in the next section.
The Grammatical Swarm Symbolic Regression Machine evolves a population of well-formed-formulas (WFFs) in a regression-oriented grammar known as Estimator. Each WFF is known as a Estimator, and is trained to map number vectors in X and XT to numbers in Y and YT. The Estimator language is a dialect of JavaScript, to make learning and reading easy by the current generation of programmers. Each Estimator Lambda, wff, supports the following methods.
The Estimator grammar is defined, within the GSM Lambda, in gsm:estimator:%DECLARATION, which is a feature-based grammar specification understood by the parseLib. The gsm.estimator child Lambda is a "Estimator" parser, generated from gsm:estimator:%DECLARATION by parseLib. The Estimator parser translates ASCII text strings into Estimator WFFs which are annotated s-expressions. Each WFF s-expression, in the population, may be annotated with grammar notes taken from the rules defined in gsm:estimator:%DECLARATION.
Each Estimator WFF must chose one of the following regression model syntax to remain gramatically correct.
Linear Regression
regress expression; for example: regress (x10 / sin(x12));
Trains a linear regression Estimator WFF for the model expression. The expression must be a valid Estimator regression expression.
Support Vector Regression
svmregress(expression1, expression2,..., expressionM); for example: svmregress (x10,cos(x12)/log(x3));
Trains a support vector regression Estimator WFF, with a cubic kernel, for the models expression1 through expressionM. The models expression1 through expressionM must each be valid Estimator regression expressions. There must be AT LEAST one model expression and there may be up to M model expressions (where M is the number of elements in each x vector). The special case of svmregress(); is assumed to mean svmregress(xtime,x1,x2,...,xm);
Percentile Grid Regression
pgmregress(expression1, expression2,..., expressionM); for example: pgmregress (x1,exp(x12)/log(x3));
Trains a percentile grid regression Estimator WFF for the models expression1 through expressionM. The models expression1 through expressionM must each be valid Estimator regression expressions. There must be AT LEAST one model expression and there may be up to M model expressions (where M is the number of elements in each x vector).
Estimator Expressions
Valid Estimator regression expression well-formed-formulas (WFFs) can be constructed by recursively applying the following production grammar rules.
TERMINAL: xtime x1 x2 ... xm explanation: A TERMIAL is any one of the elements of the input vector, x. example: svmregress (xtime, x3, x10);
UNARY: abs(EXP) cos(EXP) cube(EXP) exp(EXP) integer(EXP) log(EXP) (- EXP) sign(EXP) sin(EXP) sqrt(EXP) square(EXP) tan(EXP) tanh(EXP) explanation: A UNARY is any one of the unary operators, shown above, enclosing a valid Estimator regression expression WFF. example: svmregress (sin(xtime), abs(x3), log(sqrt(x10)));
BINARY: avg(EXP1,EXP2) (EXP1+EXP2) (EXP1-EXP2) (EXP1/EXP2) (EXP1*EXP2) expt(EXP1,EXP2) max(EXP1,EXP2) min(EXP1,EXP2) mod(EXP1,EXP2) explanation: A BINARY is any one of the binary operators, shown above, enclosing two valid Estimator regression expression WFFs. example: svmregress (sin(xtime)-abs(x3), log(sqrt(x10))*x2);
EXP: TERMINAL UNARY BINARY explanation: An EXP is any WFF resulting from invoking the TERMINAL, UNARY, or BINARY Estimator grammar rules up to five times recursively. example: pgmregress (sin(xtime)*abs(x3), tan(sqrt(x10))*x2);
A more detailed description of the Estimator language is provided in the chapters on Estimator Introduction and Estimator Statements.
There are many specialties in the umbrella field of Evolutionary Computation including (but not limited to): Genetic Algorithms; Genetic programming; Artificial Life; Grammatical Evolution; Evolvable Hardware, etc. However different, these various specialties all have a least common denominator of similarities; and, each of these specialties possess at least some techniques which have proven useful when applied to selected problem domains.
Populations
One of the primary least common denominator areas across all specialties in the umbrella field of Evolutionary Computation, is the commonality of large populations of things which change, over time, becoming a population of fitter things. In the specialties of Genetic Algorithms, Genetic Programming, and Grammatical Evolution, the things are called genomes. In other specialties the things are called Lambdas, organisms, robots, rules, DNA sequences, etc.
Fitness
Another important least common denominator area across all specialties in the umbrella field of Evolutionary Computation, is the commonality of fitness. The population is said to become fitter over time. In each specialty, the concept of fitness is expressed via a mapping from things in the population to a fitness score. In our observations, of each area of specialty, the concept of fitness mapping can be generalized to a mapping from elements of a population of things to a real vector space.
Survival
Survival is another least common denominator area across all specialties and is related to the fitness measure in some manner. In all specialties there are discrete time steps during which the things in the population are promoted (survive) into the next time frame. Normally, this survival mechanism is related to the fitness measure in that the population becomes fitter over time.
Operators
In almost all areas of specialty which we studied the concept of population operators morphing the population is a least common denominator. In the specialties of Genetic Algorithms, Genetic Programming, and Grammatical Evolution, the operators are called mutation, recombination, reproduction, etc. In many cases the population operators incorporate the concept of survival. In these architectures, the population operators map things (in the current population) into things (in the population one time step in the future). Things which are not promoted do not survive.
Data
All areas of specialty which we studied supported the concept of training data in one form or another. In many cases the training data can be numeric vectors. In other cases the training data is the initial environment for an ant colony, or a geographic playing field for robot traversal, etc. In all these architectures, the training data, population operators, and fitness mapping work together to produce populations of things which better solve a training problem. In many architectures, there is a concept of problem generalization. In these architectures, once trained, things in the population can be presented with testing data (not seen during the training period) and better solve a testing problem (presumably because the previous training experience was generalized).
Evaluation
All areas of specialty which we studied supported the concept of evaluation in one form or another. There must be some process by which each thing in the population can be evaluated so as to produce a fitness score. In the specialty of Genetic Programming, the genome is often an Lisp s-expression and the evaluation is the Lisp eval function. In the specialty of Genetic Algorithms, a translator is normally required to convert the genome into a program which can be evaluated. In the specialty of Grammatical Evolution, the genome is run through a grammar production resulting in a program which can be evaluated.
Design Principle
The Grammatical Swarm Symbolic Regression Machine Lambda (GSM) is a symbolic regression engine, designed to accept an X Y training matrix as input and to output an estimator Lambda (Estimator) which attempts to map elements in X onto elements in Y, in an order preserving manner, with a high degree of accuracy. In order to accomplish this task, the Grammatical Swarm Symbolic Regression Machine Lambda (GSM) is designed, to take advantage of practical research results in the general field of Evolutionary Computation, regardless of their specialty of origin.
The Grammatical Swarm Symbolic Regression Machine (GSM) is designed, from its basic foundation, to take advantage of any practical research results in the general field of Evolutionary Computation, regardless of the specialty of origin. The Grammatical Swarm Symbolic Regression Machine architecture is a merger of a wide range of evolutionary techniques and theories from throughout the whole field of Evolutionary Computation.
Population of WFFs
The Grammatical Swarm Symbolic Regression Machine evolves a population of well-formed-formulas (WFFs) in a problem-oriented grammar known as Estimator. The Estimator grammar is defined, within the GSM Lambda, in gsm:estimator:%DECLARATION, which is a feature-based grammar specification understood by the parseLib. The gsm.estimator child Lambda is a "Estimator" parser, generated from gsm:estimator:%DECLARATION by parseLib. The Estimator parser translates ASCII text strings into Estimator WFFs which are annotated s-expressions.
By implementing its genomes as annotated s-expressions, the Grammatical Swarm Symbolic Regression Machine takes advantage the large body of Genetic Programming tools while also facilitating the use of many interesting techniques available in other specialties. Bit string annotations to the WFF s-expressions, facilitate the use of many interesting techniques available in Genetic Algorithm. Grammar annotations to the WFF s-expressions, facilitate the use of many interesting techniques available in the Gramatical Evolution. Goal and plan annotations to the WFF s-expressions, facilitate the use of many interesting techniques available in MultiLambda Systems and Swarm Learning. Nevertheless, since each WFF in the population is essentially an s-expression, evaluation requires only a call to the AIS Lisp eval function.
Operators on WFFs
The Grammatical Swarm Symbolic Regression Machine applies a set of grammar preserving operators to evolve the population of well-formed-formulas (WFFs) into a population of fitter WFFs. The GSM population operators are grammar preserving such that each operator maps from a population of Estimator WFFs to a population of Estimator WFFs. Each Estimator WFF evaluates to an AIS Lambda which accepts a set of Number Vectors and returns a proper subset of those same Number Vectors (attempting to pick the fittest in the set).
The Grammatical Swarm Symbolic Regression Machine raises the grammar concepts embodied in Grammatical Evolution far above the WFF genome's grammar annotations, making the understanding and preservation of WFF grammar an essential task of the population operators. Thus GSM operators can understand that two WFF s-expressions cannot be combined because their are grammatically incompatible, that two GSM WFF s-expressions must be combined in specific ways because of their grammar annotations, that two GSM WFF s-expressions are essentially equivalent, or that two GSM WFF s-expressions can be combined and reduced to a more primal form.
Furthermore, the task of fitness improvement is raised far above any requirement for operational purity. Grammatical Swarm Symbolic Regression Machine WFFs can be annotated with a wide variety of information to help the population operators raise the population fitness level. Annotations can aid operators in establishing protected or unprotected sub-populations. Annotations can aid operators in enhancing populations with WFFs generated via exhaustive parital-search, statistical learning methods, etc. In general the GSM uses annotations to extend the style and type of population operator far beyond those listed in any one specialty while requiring only that the operator be grammar preserving.
Data
The Grammatical Swarm Symbolic Regression Machine learns to select and score the best individuals from a universe of individuals over time. Over a series of discrete time steps, a universe of individuals is collected for each time step (the training data). During prediction the GSM attempts to select the best individuals from the testing data (the GSM is NOT given the "score" values for the testing data). The individuals are Number vectors and represent quantitative information about things such as Stocks, People, Cities, etc. The score values are single Numbers and represent some quantitative value about these same Stocks, People, Cities, etc.
Each individual followed by the system is given a unique identifier which remains unique across all time periods studied (no two individuals ever have the same identifier). Furthermore, each time period studied is given a unique ascending integer index (i.e. week 1, week 2, etc.). So, for a series of time periods, historical information about groups of individuals is collected for each time period. The historical information collected for each individual for each time period is stored in a Number Vector and includes: the time period index; the unique identifier of the individual; and other numeric information about the individual pertinent to the current investigation. Finally, each individual in each time period is given a numeric "score" which determines the value of the individual in that time period. The "best" individuals have the highest "score" values.
Fitness of WFFs
During training, the GSM is given historical information and the "score" values for time periods 0 through T for all individuals. For each time period 0 through T, we can calculate the average score for both the theoretic best and worst selections of N individuals. The GSM currently computes the theoretic best and worst scores for the each of the top and bottom 5% partitions (5%, 10%, 15%, ... 45%, 50%). The order preserving "fitness" of a Estimator WFF are measured by what percentage of the theoretical "best" averages it obtained on each of these top and bottom percentile partitions. In addition, the GSM also computes the least squares error between the predictions and the "score" values for each individual.
During training, each WFF in the population (without knowing the score values), attempts to score the N individuals for time periods 0 through T. Associated with each WFF in the population {w in P} is the least squares error and the order preservation measure for time periods 0 through T. These two fittness measures are normalized into a single fittness score as follows S[w,t] = g(Error[w,t],Order[w,t]).
The fitness measure for each WFF {F[w] == (S[w,0] * S[w,1] * ... * S[w,t])} is the product of its normalized scores for time periods 0 through T. The fitness measure tends to favor those WFFs which have done consistantly well during the training period (as opposed to those with only an occasional big success).
The Grammatical Swarm Symbolic Regression Machine applies a set of grammar preserving operators to evolve the population of well-formed-formulas (WFFs) into a population of fitter WFFs. The population operators are grammar preserving such that each operator maps from a population of Estimator WFFs to a population of Estimator WFFs. The understanding and preservation of WFF grammar is an essential task of the population operators. WFFs can be annotated with a wide variety of information to help the population operators raise the population fitness level. Annotations can aid operators in establishing protected or unprotected sub-populations evolved with different grammars. Annotations can aid operators in enhancing populations with WFFs generated via exhaustive parital-search, statistical learning methods, etc.
Here follows an overview of the population operators supported during Grammatical Swarm Symbolic Regression.
The grow operator generates a new WFF, from the empty set, by randomly invoking Estimator grammar rules so as to create a WFF.
The mutate operator generates a new WFF, from a parent WFF, by randomly mutating the parent WFF in a grammar preserving manner.
The children operator generates two new WFFs, from two parent WFFs, by randomly invoking Estimator grammar rules so as to cut and recombine child WFFs in a grammar preserving manner.
The greed operator generates a new WFF, from the empty set, by using greedy search to invoke Estimator grammar rules so as to create a WFF.
The Grammatical Swarm Symbolic Regression Machine supports multiple grammars in evolving the population of well-formed-formulas (WFFs) problem solutions. All GSM population operators are grammar preserving such that each operator maps from a population of Estimator WFFs to a population of Estimator WFFs, in a grammar preserving manner. The design concept of grammar preservation extends to establishing protected and unprotected sub-populations evolved with different grammars. The understanding and preservation of multiple WFF grammars is an essential task of the Grammatical Swarm Symbolic Regression Machine. The Grammatical Swarm Symbolic Regression Machine certainly attempts to evolve general programs, with evolved functions and variables; but, there are also attempts to evolve program solutions using Support Vectors, Multiple Regression, and Decision Tree models. In fact the GSM supports the co-evolution of a wide variety of Estimator WFF grammars, providing potentially unique strategies for approaching the problem.
There Estimator grammars currently supported during Grammatical Swarm Symbolic Regression.
The REG grammar forms valid Estimator WFFs which train and run a simple linear regression model on a the training data set.
The MVL grammar forms valid Estimator WFFs which train and run a multiple linear regression model on a the training data set.
The SVM grammar forms valid Estimator WFFs which train and run a support vector regression model with a cubic kernel on a the training data set.
The FRM grammar forms valid Estimator WFFs which train and run a multiple factor regression model on the training data set.