Transcript Slide 1
AI LIBRARIES By Thomas Dvornik LIBRARIES Creating versatile AI Libraries is difficult Lots of path finding and search libraries Not a lot of AI learning libraries Often incomplete or very basic Some Examples A* Tactical Path finding Used for multi-unit strategy PathLib Individual and group path finding FANN "Fast Artificial Neural Network” Library FFLL Free Fuzzy Logic Library GARFIXIA AI REPOSITORY BY PATRICK VAN BERGEN Open Source Wrote them to learn AI techniques Not tested thoroughly Gives lots of resources. Offers Fuzzy Logic Genetic Algorithms Neural Networks Natural Language Processing Decision Trees Finite State Machines Frame Systems, Semantic Networks, Unification Maes Behavior Network Sparse Distributed Memory Belief, Desire, Intention: dMARS GENETIC ALGORITHMS What was implemented? Interface and classes. CGeneticGenome: An interface that should be implemented by a custom class describing the problem space. It contains all domain specific code of some problem. CGeneticModel: Represents the genetic algorithm. CGeneticPopulation: A single population which is populated at initialization time. The model is able to handle both fixed length and variable length genomes. The interface makes it possible to use any representation you want for the problem at hand. Parent selection types. Crossover types: fixed length one point, fixed length two points, fixed length multiple, variable length one point. Mutation types: change a gene, swap two genes. GENETIC ALGORITHM This implementation is generic, but very limited. The possibilities of extending and modifying a genetic algorithm are large. This is a base. Architecture may be extended without to much hardship. Adjustments to the algorithm can help find the solution faster. The problem? Don’t want to lose the generality of the architecture, in order to optimize the test problem. Testing is very important here, since the algorithm can almost always find a solution sooner or later, even though you completely messed up some of the code. Since the algorithm is tweakable in so many ways, it itself is a candidate for optimization through a Genetic Algorithm. N-QUEENS PROBLEM Need several methods Initialize( ) MutateGene(int geneIndex) Store a random value in the gene CalculateFitness( ) Create random values for the genes Calculate and return the fitness of this genome IsFitEnough( ) Is the genome fit enough to stop evolving? N-QUEENS PROBLEM // genetic algorithms CQueenGenome QueenGenome(100); CGeneticModel GeneticModel(&QueenGenome); GeneticModel.Initialize(); // evolve the model until it found a fit enough genome GeneticModel.Evolve(); Variables that can alter the results GeneticModel.ClearParentSelectionTypes() GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_RANK) GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_TOURNAMENT) GeneticModel.ClearCrossoverTypes() GeneticModel.AddCrossoverType(CROSSOVERTYPE_FIXEDLENGTH_ONEPOINT) GeneticModel.ClearMutationTypes() GeneticModel.AddMutationType(MUTATIONTYPE_CHANGEGENE) GeneticModel.SetPopulationSize(100, 10, 10, -1) GeneticModel.SetMutationRate(1.0f) TORCH Torch is a machine-learning library Written in C++ Aims to provide the best algorithms In development forever Features Many gradient-based methods, including multi-layered perceptrons, radial basis functions, and mixtures of experts. Many small "modules" (Linear module, Tanh module, SoftMax module, ...) can be plugged together. Support Vector Machine, for classification and regression. Several Distribution package and classes for speech recognition with embedded training. Ensemble models such as Bagging and Adaboost. Non-parametric models such as K-nearest-neighbors, Parzen Regression and Parzen Density Estimator. TORCH CONCEPT There are only four important concepts in Torch. Each of them are implemented in a generic class. And almost all classes of Torch are subclasses of one of them. DataSet: this class handles the data. Subclasses could be for static or dynamic data, for data that can fit in memory or on disk, etc… Machine: a black-box that, given an (optional) input and some (optional) parameters, returns an output. It could be for instance a neural network, or a mixture of gaussians. Trainer: this class is able to train and test a given machine over a given dataset. Measurer: when given to a trainer, it prints in different files the measures of interest. It could be for example the classification error, or the mean-squared error. TORCH CONCEPT DataSet, Trainer, Machine TORCH CONCEPT DataSet, Trainer, Machine DataSet produces one “training example” TORCH CONCEPT DataSet, Trainer, Machine DataSet produces one “training example” This training example is given to a machine which computes an output... TORCH CONCEPT DataSet, Trainer, Machine DataSet produces one “training example” ...and with that a trainer tries to tune the machine. This training example is given to a machine which computes an output... WHAT COMES WITH TORCH DataSet: an interface to provide a set of examples setExample(int t): sets the inputs and targets field to the inputs and targets of the example indexed by t Example: data->setExample(0); inputs_0 = data->inputs; targets_0 = data->targets; data->pushExample(); Dealing with subsets: void pushSubset(int *subset_, int n_examples_); void popSubset(); DataSets can be pulled from file with just one call to setExample(int t) Can also deal with encoding for classification WHAT COMES WITH TORCH Machines: Updates outputs given inputs Gradient machines are machines which could be trained with a gradient descent algorithm Connected machines allow you to plug all the machines you want, to obtain the results you want Measures: Entities which can measure anything measureExample() which should be called by the Trainer after doing a forward() for each example (or another similar method, if this one doesn’t make sense) measureIteration() which should be called after having seen all examples. measureEnd() which should be called at... the end! It could be the end of training or testing phase. reset() called once by the Trainer before the training or testing phase. WHO USES TORCH? Mainly Face Recognition. Google Portrait Not associated with Google but pulls from Google Images Given a Celebrity, it will grab images and create portraits Not perfect, can get it wrong http://www.idiap.ch/googleportrait/ Bio Login Login users based on facial recognition and speech Device login, building gate control, remote credit card purchases, secure teleworking. http://www.idiap.ch/biologin/ REFERENCES Library References http://www.ogre3d.org/wiki/index.php/Libraries http://tldp.org/HOWTO/html_single/AI-AlifeHOWTO/#ss2.1 Torch http://www.torch.ch/matos/tutorial.pdf Garfixia AI http://www.dossier-andreas.net/ai/ga.html QUESTIONS?