Genetic Programming - Again

Learning Classifier Rules

A system using genetic programming to automatically generate
classifiers.

Each classifier is a genetic programming tree expressed recursively:

 struct Node {
   o:Operator,
   l:Option<Node>,
   r:Option<Node>,
   d:Option<Node>,
 }

Each classifier is evolved using the genetic programming algorithm
with training data. Each classifier is associated with a Score object:

#[derive(PartialEq, Debug, Clone)]
pub struct Score {
    pub quality:f64,
    pub class:String,
}

Score::quality is defined as the 1/(1+S), S is the sum of the
classification error over the training data.

Classification error is currently calculated using Hinge Loss.
Given T in 1.0, -1.0 the true classification of the case and Y the
estimate of the classifier, Hinge Loss is:

1.0-T*Y < 0 ? 0.0 : 1.0-T*Y

A classifier is assigned to a class by evaluating a Score for each
class and choosing the one with the highest score.

FIXME: There is no measure of differentiation. How good a classifier
is at telling one class from another.

When it classifies a case the ideal classifier will output 1 if the
case is of the class and -1 if the case is not. Classifiers are
implemented as programme trees and prepared using genetic programming.

To classify a new case a collection, Forest, of trees is used. Each
classifier examines the case and produces a result in [-1.0, 1.0].

For each class, calculate the mean score for classifiers in the Forest
specialised for that class, as:

sum(result * Score::quality)/#classifiers

The class with the highest score is selected.

The value returned from classify in population.rs is

Option<(String, String)>

The first String in the 2-tuple is the winning class. The second
string is in the format: <class> <score>,... listing all classes and
the score for the class in descending score order.

Operators implemented

• Terminals All terminals are implemented as floating point values.
  On terminal nodes Node::l, Node::r and Node::d are None.
  • Inputs. From the domain of the function.
  • Constants. C
• Arity one functions. Apply to Node::l. Node::r and Node::d are None.
  • Invert. Returns one over the value of l.
  • Negate. Returns negative one times ‘l’

• Arity two functions. Apply to Node::l and Node::r. Node::d is None

  • Multiply. Returns l times r.

  • Gt. If the value of l is greater than the value of ‘r return 1.
    Otherwise return -1

  • Lt. If the value of l is less than the value of ‘r return 1.
    Otherwise return -1

  • Addition. Returns l plus r

• Arity three functions. Apply to Node::l and Node::r, and
  Node::d

  • If. Calculate the value or ‘d’. If that is less than or equal to
    zero return the value of l, otherwise the value of r

Classes and Quality

Configuration File

Format is:

<key> <value>

num_generations

The number of generations to simulate 
Example: num_generations 20000

max_population

The maximum size of the population
Example: max_population 10000

crossover_percent

Each generation new individuals are created by combining two
individuals.  The number of new individuals created is at most
population x crossover_percent / 100.  New individuals are only
added if they are not already in the population, duplicates are
not allowed in the population.
Example: crossover_percent 50

training_percent

The data supplied for the simulation is divided into training and
testing.  This sets the percentage of data used to train the
model.  During model development the training data is used.  When
a new model that performs best in the training data is discovered
it is run against the testing data and the results recorded
Example: training_percent 80

data_file

The file name of the training and testing data.  Comma separated
line per record.  The first line is the field names (these
constitute the inputs to the generated functions).  The last
column is the objective value.
Example: data_file Abalone.in

generations_file

The name of the file out to which a line is written every
generation
Example: generations_file AbaloneGenerations.txt

birthsanddeaths_file

Every individual has a line in this file when it is created and
when it is destroyed.
Example: birthsanddeaths_file AbaloneBirthsAndDeaths.txt

copy_prob

data_file

filter

mutate_prob

rescore

save_file

training_percent

work_dir