19-10-2012, 04:42 PM
Genetic Algorithms in Artificial Neural Networks
Genetic Algorithms.ppt (Size: 1.05 MB / Downloads: 103)
DM Challenges and scope
Developing a unifying theory of DM
Scaling up for high dimensional data and high speed data streams
DM for biological and environmental problems
Mining complex knowledge from complex data
DM is an inter-disciplinary field of disciplines such as statistics, machine learning, Pattern Recognition (PR), Artificial Intelligence (AI), database technology …
Intelligent Data Mining
DM techniques are all data analysis methods and can support/interact with each other.
Each discipline has its own distinct attributes that make it particularly useful for certain types of problems and situations.
Ex. the most fundamental difference between classical statistical applications and data mining is the size of the dataset.
Intelligent System (IS) is all about learning rules and patterns from the data
It is a collection of methodologies that works synergistically and provides, in one form or another, flexible information processing capability for handling real-life situations.
It differs from conventional data analysis (e.g. statistical methods) in that it is tolerant of imprecision, uncertainty, partial truth, approximation and expolits it in order to achieve tractabillity, robustness, and low-cost solutions.
Artificial Neural Networks (ANNs)
Biological neural systems (BNSs) can perform extraordinarily complex computations without recourse to explicit quantitative operations, and are capable of learning over time.
Reflect the ability of large ensembles of neurons to learn through exposure to external stimuli and to generalize across related instances of the signal.
Attractive as a model for IS methods.
ANNs are distributed, adaptive, generally nonlinear means of learning comprised of different processing elements (PEs) called neurons.
Based on a computing model similar to the underlying structure of the human brain, the aim being to model the brain’s ability to learn and/or adapt in response to external inputs.
Algorithms for rule extraction
Decompositional approaches - rule extraction at the level of hidden and output units, involves the extraction of rules from a network in a neuron-by-neuron series of steps.
They can generate a complete set of rules for the trained ANNs.
The process results in large and complex descriptions (exponential).
Pedagogical approaches - map inputs directly into outputs and views ANNs as black-boxes where the aim is to extract symbolic rules which map the input-output relationship as closely as possible.
The number of these rules and their form do not directly correspond to the number of weights or the architecture
Sheer number of rules generated for even the simplest domains
Eclectic approaches - incorporate elements of both decompositional and pedagogical techniques to complement a symbolic learning algorithm.
Very little understanding for constructing and of the domains where it may outperform their traditional symbolic and ANN counterparts, and how to evaluate the results.
Genetic algorithms - biology
Organism has a set of rules (a blueprint) defining how it is built up from the tiny building blocks of life.
Rules are encoded in the genes, which are connected together into long strings called chromosomes.
Each gene represents a specific trait of the organism and has several different settings.
Genes and their settings are usually referred to as an organism's genotype. The physical expression of the genotype(the organism itself) is called the phenotype.
When two organisms mate, their resultant offspring ends up having shared genes - recombination.
Occasionally a gene may be mutated.
Life on earth has evolved to be as it is through the processes of natural selection, recombination and mutation.
Genetic algorithm (GA)
Before using a GA to solve a problem, a way must be found of encoding any potential solution to the problem. This could be as a string of real numbers or, more typically, a binary bit string. It is referred to as the chromosome. A typical chromosome may look like this: 10010101110101001010011101101
At the beginning of a run a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem at hand. Let's say there are N chromosomes in the initial population.
The following steps are repeated until a solution is found:
Test each chromosome to see how good it is at solving the problem at hand and assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem to hand.
Select two members from the current population. The chance of being selected is proportional to the chromosomes fitness. Roulette wheel selection is a commonly used method.
Dependent on the crossover rate crossover the bits from each chosen chromosome at a randomly chosen point.
Step through the chosen chromosomes bits and flip dependent on the mutation rate.
Repeat steps 2, 3, 4 until a new population of N members has been created
The Genetic Algorithm/Neural Network System (1/3)
The starting point of any rule-extraction system is firstly to train the network on the data required, i.e. the ANN is trained so that a satisfactory error level is reached.
For classification problems, each input unit typically corresponds to a single feature in the real world, and each output unit to a class value or class.
The first objective of this approach is to encode the network in such a way that a genetic algorithm can be run over the top of it which is achieved by creating an n-dimensional weight space where n is the number of layers of weights.
The network can be represented by simply
enumerating each of the nodes and/or connections.
Typically, there will be more than one output class
or class value and therefore more than one output node.