Breathe intelligence into Java
Making AI work in your Java programs is easier than you think
Evolutionary computation is crucial for the next generation of applications. Evolutionary computation is software that adds and removes methods, parameters, and iterators, as well as generally modifies the elements of an algorithm in response to a fitness test: Did algorithm i yield a better fitness result than algorithm j, where fitness is time, distance, or some other value measure? The field of evolutionary computation, while shrouded in academia, provides the gateway for writing smart, adaptive, and self-evolving Java applications. Sadly, Sun Microsystems has invested thousands of man-hours in APIs related to dashboard technology and has yet to show a serious initiative for bringing artificial intelligence (AI) into the Java mainstream. Support for such an effort would make for a tremendous step in the advancement of Java computing.
For now, I will examine the basic concepts, look at the wealth of resources, and show how I am developing a Java component in the area of security and authentication using AI technology. Making AI work in your Java programs is easier than you think.
Terminology and concepts
The framework for developing an intelligent Java component requires the application of key concepts and discerning the branches of AI:
Statement of problem
Most important, an evolved component does something intelligently. The statement of what it does, not how it does it, is the important part. In 1959 Arthur Samuel asked, “How can computers be made to do what needs to be done, without being told exactly how to do it.” Establishing the tableau, “what needs to be done” is shared between the domain expert and the engineer; for example, “find all schedules that get the project done in less than n months without exceeding cost X using human resources Y and machines Z.” Another example, germane to the subject of this article, “find all users who have stolen the credential of a valid user within an error rate of 10 percent.”
Fitness
You will require a fitness measure for your intelligent component. There must be some standard; for example, your component must have authentication errors fewer than 0.1 percent, mean time between failure (MTBF) greater than 90 days, least amount of time, lowest cost, shortest distance, and so forth.
Training set
You should employ a training set with known values to test the fitness of your Java component. Training sets are data sets that measure known fitness against a specific instance of an algorithm undergoing evolution. The program evolves against the fitness tests where each generation of solutions improves over time (milliseconds not eons).
The training set then provides the right answers for a given individual Java instance. If the instance is wrong for many of the training set elements, it is less likely to be combined with other instances into the next generation.
A training set is sometimes provided as part of the fitness test but not always. For example, for an algorithm to evolve, it may need an external training set to check its results. For classification components, the training set tells the fitness evaluator if the classification was right or wrong.
A good training set is essential, as you project that the variables that helped to evolve the algorithm in the real world are the same variables found in the field. If not, you get a lot of false negatives and positives in the field, which I will explain further in this article.
Evolution through reproduction, crossover, and mutation
An evolving component follows the principle of natural selection, survival of the fittest. The component has to be built so it can evolve to a fit state. This entails a strategy that allows the instances of your Java component to compete against other instances, and for creating new generations of instances, which over time, are more fit than previous ones. The reproduction strategy must allow for the exploration of fitness across a wide spectrum of instance values.
In evolving an algorithm to detect credential fraud, we start with an instance population of N. Let’s call this class CredentialGuardian. Then, using the training set, we instantiate 1,000 instances of CredentialGuardian as our initial population with a random weight variable vector so that each instance explores the training set differently. Each instance will add and remove iterators and method calls, and return a result set that will be measured against the training set. The fittest instance can then be combined with less-fit instances and the weight values, and other algorithm elements can be randomized to produce a new population of 1,000 instances. That new population is the offspring of the fittest algorithm. The new instance is subjected to crossover, mutation, and randomization, which are strategy elements in evolution. Thus the new population is not a clone of the fittest; rather it is a genetic offspring of the fittest elements, other algorithm elements, and randomization. Without such genetic combining, true fitness will not be found and the algorithm will get trapped in a point of local optimization without discovering the true point of fitness.
Expert rules
Expert rules is the subject of Java Specification Request (JSR) 094: Java RuleEngine. Rule engines, which are static and require human intervention to add, delete, and modify rules, are not self-evolving. They are a substitute for evolutionary computing when the problem is small in nature and the rules are not interdependent. Of course, rule sets can evolve genetically. Expert rules impose a hard-wired condition upon an algorithm. For example:
if (credential.domain.equalsIgnoreCase("itworld.com"))
break;
Expert rules are therefore orthogonal to evolutionary computing. Logic decisions superimposed by an expert preclude the discovery of rare or obscure solutions within the total search space, which evolution tends to examine.
Neural networks
A neural network is a popular mathematical model with a number of variants for producing an output, discrete or continuous, from multiple inputs that often share no linear relationship. Neural Networks: A Comprehensive Foundation is an excellent and readable primer on this subject. Neural networks consist of nodes, weights, and layers. To obtain these values, a neural network itself is often subject to genetic evolution to produce a fit neural net.
Figure 1 depicts a neural net with five inputs, two internal processing layers, and two outputs. Thus, the modeler felt that the problem could be solved with an input vector consisting of five variables and an output vector consisting of two outputs.
Every processing node in a neural net consists of multiple inputs x(1), …, x(n), weighing values for those inputs w(1), …, w(n), and an output value that, depending on the inputs and weights, can be a discrete or continuous value. This value can, in turn, be an input to one or more nodes or it can be a “result” value of the neural net itself. Figure 2 illustrates this process:
Genetic algorithms
A genetic algorithm (GA) includes any algorithm that derives its behavior from the evolutionary pattern of natural selection, fitness, reproduction, crossover, mutation, randomization, life, and death.
A GA in Java is an algorithm that reproduces new code from existing code using crossover, randomization, and selection against a fitness model. At my company, we have filed a patent to detect the theft of userid and password. Our GA to implement evolution might look like the following code segment:
// start with an initial generation, result container
int generation = 0;
Vector results = new Vector();
// create an instance of the interface
// which implements the evolution signature
// methods allowing evolution of a populations
Evolutionary evolution =
(Evolutionary) Class.forName("org.opendoors.security.EvolvingSecurityScreener").newInstance();
// create an initial population of evolvable instances
// implementing the evolvable pattern.
Evolvable[] population = evolution.createPopulation(t);
while (! evolution.isOptimal(results)) {
Fitness fitness = evolution.evaluate(population, generation);
// add the fitness element which is a composite object, not just a value:
results.addElement(fitness);
// increase the generation
generation++;
// select parents from the population according to fitness, generation
Evolvable[] parents = evolution.selectParents(population, fitness, generation);
// recombine the parents using fitness, generation as variables
evolution.recombine(parents, fitness, generation);
// mutate the population of parents possibly using fitness
evolution.mutate(parents, fitness, generation);
// evaluate parental fitness
Fitness parentalFitness = evolution.evaluate(parents);
// determine who survives according to fitness
population = evolution.survive(parents, parentalFitness, population, fitness, generation);
}
System.out.println("At generation " + generation + ", optimality was attained or time ran out.");
Object mostFit = evolution.mostFit(results);
System.out.println("Instance " mostFit " is most fit");
SysEnv.iceObject(mostFit, "instances/FraudDetector"); // serialize to disk.
A GA is appropriate when you are optimizing against a fitness test and the variable set is large and the discriminators are not obvious.
Check out these applets on the Web to see GAs in action:
- https://www.wi.leidenuniv.nl/~gusz/Flying_Circus/3.Demos/Java/index.html
- https://www.apm.tuwien.ac.at/~guenther/tspga/TSPGA.html
- https://alphard.ethz.ch/gerber/approx/default.html
Genetic programming
Genetic programming is the application of a genetic algorithm to programming. This is the area of greatest promise, in my view, for Java. First, Java has a rich and standard introspection API that allows a method to discover and then invoke other methods. This feature cannot be underestimated. Evolution is all about invoking small, simple methods with changing parameters. The ability to invoke a method dynamically is a strong chromosome in the language architecture. Another compelling feature is the notion of runtime compilation. With Java, you can compose and compile class files on the fly — another important tool to the GA developer.
Some programs are better written by software than by humans. In particular, if the program can evolve against a fitness test, it can be optimized far faster than the time in which it would take a human to identify and optimize by hand. For example, a compiler could be subjected to genetic evolution. The fitness test would always include correctness, but could also include the size of generated output, speed of generated-output execution, or speed of compiler execution. In the earlier code example, the recombine() method could introduce new functions, variables, or states to the individual instance.
The bible on this topic is Genetic Programming III by John R. Koza, et al.; see Resources for a link.
Authentication and genetic programming
The transaction settlement engine I am developing consists of three parts: presentation, funds transfer, and financing. Security, which is important to this application, applies to authentication, privacy, authorization, and repudiation. The application shows that genetic programming can be applied to login authentication to detect identity theft. In essence, there are a host of variables that can be presented with every login. Obvious variables are:
- Time of day
- Time zone
- IP number and domain name
- Browser ID
And, with a Java applet as a front end, the programmer can produce biometric variables:
- Mouse versus keyboard actions
- Typing rate
- Hardware keys
It is very important in financial applications to detect before (not after) funds exit the bank, if the controller’s credentials are actually in use by an illegal user. So, the statement of the problem is as follows:
“Apply a second level of authentication if other characteristics suggest that the user providing the credentials is not the true owner of the credentials.”
There is no statement about how to solve this problem, because it is not clear which variables discriminate between a fraud and the real user.
How it is “to be done” is the problem solved by the program’s evolution. Further, there is no “cooking” of the variables or the weights of those variables. By cooking, I mean an expert will not pour over the variables and make some assessment about how to weigh one variable versus another and then test the hypothesis against a training set. That, too, is the work of a program derived from genetic software engineering. It finds the variables that act as strong and weak discriminators.
Looking at the previous code segment, the programmer must implement the signature methods of the Evolutionary interface. This is a design decision made for evolving the population into a fit space.
With authentication, you have two training data sets: a set where users are properly using their credentials and a set where an impersonator is using those credentials. In theory, however, the algorithm could evolve against this training set. In that case, your training needs to be redone. With evolutionary computing, your job is to make sure that the training data set variable space is large enough to enable algorithm evolution to a fitness point where it can run unsupervised against real inputs.
For the security training set, the classification consists of two states: valid user or a fraud. With respect to the training set there are four outcomes:
- Positive: The credential owner presented the credentials and was validated positively
- Negative: An imposter presented the credentials and was challenged to supply a second level of authentication
- False negative: The credential owner presented the credentials but was also challenged to supply a second level of authentication
- False positive: An imposter presented the credentials and was granted access unchallenged
Evolving imposters
In my application, I will use a large training set, some of it machine-generated, and I will retrain as the environment itself changes. Retraining means taking new training data, and rerunning the GA according to the psuedo code above.
I will define fitness as having zero occurrences of “false positive” and not more than 10 percent of “false negative.” The initial training set will allow me to create an Evolved Authenticator (EA). My genetic algorithm will produce a Java instance of an EA that is serializable and embodies the evolution required to meet the fitness goals set out. The code to generate such an instance will follow the same pattern as the code shown above. The psuedo code for such an algorithm is under the subhead “Genetic Algorithms.”
As time goes by, I expect to see EA fail as imposters themselves evolve. The forensic hypothesis is that an imposter is different than the credential owner. Therefore, a different digital fingerprint exists. Retraining EA requires it to evolve to discriminate new variables in the new environment. EA will never be perfect. But, it will be a far better approach than blindly admitting the imposter into the financial system, which more than 95 percent of all Web apps do today. It irks me that I can use my fiancé’s credentials at any time, at any place, and on any device without being challenged.
Evolving the JDK
The JDK needs a robust and clean GP package implemented as a set of interfaces, allowing pluggable implementations of genetic programming. I would propose that Sun bring in Dr. Koza, or someone with his level of experience, as an expert technical adviser. Using existing Java introspection, it is clear how to implement the components of genetic programming. The components specified in
Genetic Programming III
are automatically defined iterations, loops, recursion, and storage coupled with architecture-altering operations on methods and program hierarchies.
Dr. Koza and his associates created the Genetic Progamming Problem Solver (GPPS), a software library that works to evolve parts of programs — namely methods, instance variables, loops, and iterators. This is amply demonstrated in Genetic Programming, now in its second release. Sun would be wise to license GPPS and use it as the first implementation of the GP interface package. As it stands today, JDK is not the best of breed for genetic programming.
