class test 2 Flashcards
What was Rosenblatt’s main consideration
The problem of pattern recognition where a teacher is essential
What is a perceptron
A neural network that changes with experience using an error correction rule
What is stated by the perceptron error correction rule
The weight of a neuron changes when it makes an error response to the input presented to the network
Describe the structure of perceptron
One layer of inputs- real, a0 = 1
One layer of output neurons
Every input layer is connected to every output neuron
Each output neuron works independently
What can a perceptron be used for
Weights can be adjusted between 2 layers to learn knowledge from a given data set
If the data set is unlabelled, we can train the perceptron network to cluster the inputs to different groups (unsupervised learning)
If the data is labelled, we can train the perceptron network to produce the desired output in response to certain inputs (supervised learning)
What is a training set
A set of inputs is repeatedly presented to the network during training
What is a target output
The pre-defined correct output of an input pattern in the training set
What is the goal of training
To arrive at a single set of weights that allow each input in the training set to be mapped to the correct output by the network
What is the perceptron learning rule
A weight of connection changes only if the input value and the error of the output are not equal to 0
What is C in a perceptron calculation
Learning rate
Usually set below 1
Determines the amount of correction made in a single iteration
How does overall learning time of a network relate to C
Slower for small values
Faster for large values
How is perceptron network performance during a training session measured
Using a root mean square error value
When does training stop
When RMS is close to 0
What is the learning curve
Dependency of the RMS error on the number of iterations
Does the learning rule always make a network converge
Only for the absolutely linear separable data set
Describe a multi-layer perceptron
A layered architecture of neurons where:
All the neurons are divided into l subsets, each set is called a layer
There are only connections between 2 adjacent layers, usually the neurons within a layer are not connected with each other
Describe the types of layers in a multi-layer perceptron
First layer is an input layer
Last layer is an output layer
All other layers are hidden layers and have no connection to/from the outside
What is forward propagation
Input is processed from one layer to the next, until the final result is computed
What is error propagation
Error of output neurons is propagated back to derive weight adjustment of a given hidden neuron, based on how much the neuron contributes to the output error.
What is the purpose of the gradient descent method
addresses the issues of how to update weights
What is the purpose of the backpropagation algorithm
Makes the weight updating efficient
Describe the Darwinian Theory of Evolution
Species adapt to the environment via natural selection
The selection favours those species that are best adapted to the environmental condition
What is phenotype
The manner of response and physical embodiment of an individual
When do phenotype mutations prevail through selection
If they prove their worth in the current environment, otherwise they perish
What is the basic driving force for selection
Production of offspring
How does population grow in a favourable environment
Exponentially
What limits population growth
Finite resources
Describe the Neo-Darwinism Theory of Evolution
All living organisms consist of cells
Each cell contains the same set of one or more chromosomes
What are chromosomes
Strings of DNA that serve as a blueprint for the organism
Describe DNA structure
2 ribbons of phosphate sugar chains and horizontal rods of the pairs of nitrogenous bases holding the chains together
What is a gene
A functional block of DNA coding a particular protein.
What is the DNA alphabet (nitrogenous bases)
A- adenine
G- guanine
T- thymine
C- cytosine
What nitrogenous bases pair together
Adenine with Thymine (A = T)
Guanine with Cytosine (G = C)
What carries the genetic information
The precise sequence of bases
What is the solution to 20 amino acids being found in proteins but only 4 letters in the DNA alphabet to code
Genetic code is based on the triplet codons
The genetic code is universal, as the codons for amino acids are the same in bacteria, plants and animals
Define haploid
Organisms with unpaired sets of chromosomes
Define diploid
Organisms whose chromosomes are arranged in pairs
When does crossing-over/gene recombination occur
During sexual reproduction
Describe the process of crossing over/gene recombination
In each parent cell, a pair of chromosomes doubles and then the chromosomes exchange genes, and finally produce 4 gametes, ready to couple with the other parent gametes to form a new diploid cell
What is a gamete
A single chromosome
What is mutation
A random change of a letter, a single nucleotide in a chromosome
How do mutations occur
As a result from copying errors in parent chromosomes and then are reproduced in offspring
What are alleles
Different possible settings for a trait
Where is each gene located in the chromosome
At a particular locus (position)
What is a genome/genotype
The complete collection of all genetic material, all chromosomes taken together
What is the purpose of genes
They are transfer units of heredity
What is the purpose of phenotype
Expresses complex interaction within the genotype and its interaction with the environment
What type of unit is an individual
A selection unit, as selection acts on the individual
What type of unit is population
The evolving unit
How is individual fitness measured
Indirectly, as the individual growth rate in comparison to others
Define natural selection according to individual fitness
Not an active driving force
Is differential survival and reproduction within a population
Describe parallelism in natural evolution
Every individual in the population is tested independently in parallel with the others, and that speeds up evolution of the population
The nature addresses the 2 problems implicitly in parallel and comes up with a better fitted population
Describe adaptation to a changing environment in natural evolution
Survival of the fittest due to natural selection
Results in the population as a whole best adapted to the environment
Describe optimisation in natural evolution
Due to natural selection, only individuals optimal for the current environment survive and reproduce
Selection performs optimisation on an individual level
What was introduced by Rechenberg
Evolutionary strategies as a method to optimise real-valued parameters for airfoils
What was developed by Fogel, Owens and Walsh
Evolutionary programming, representing candidate solutions to a problem as finite-state machines evolving by randomly mutating their state-transition diagrams and selecting the fittest
What was introduced by Holland
A population of binary strings he called chromosomes
Population evolves by natural selection and operators of crossover, mutation and inversion
Bits in a chromosome represent genes, each gene is an allele of 0 or 1
Selection operator chooses chromosomes in population allowed to reproduce, fitter chromosomes reproduce more
What is the function of the crossover operator
Exchange subparts of 2 operators
What is the function of the mutator operator
Randomly changes the allele values at some location of the chromosome
What is the function of the inversion operator
Reverses the order of a continuous section of a chromosome, rearranging the gene’s order
Compare genetic algorithms with nature
There is no universal code in genetic algorithms
Every coding is problem dependent
Why is the art of coding important in genetic algorithms
From the very beginning the approach depends on whether the problem can be coded as a string of characters at all
Implies serious restrictions on the class of problems solvable by genetic algorithms
What is Holland’s definition of a chromosome
A string of characters coding a candidate solution for a particular problem
Often defined as a fixed length binary string
According to Holland, what is the relationship between chromosome and genotype
Genetic algorithm’s chromosome usually coincides with genotype
Genotype consists of a single chromosome
How is phenotype used in genetic algorithm
It usually isn’t used
GA’s chromosome = GA’s genotype = GA’s organism
What does a character represent in a GA chromosome
A gene
What is the locus of the gene in the context of GA’s by Holland
The position of a gene in the string
Describe the process of crossover in GA’s by Holland
Recombines parts of 2 parent chromosomes to make 2 children
The crossover cutting point is chosen randomly
One point crossover is considered most often
Describe the process of mutation in GA’s by Holland
Randomisation of allele of gene at a randomly chosen location
For binary chromosomes, a bit is flipped at a random locus
For chromosomes with a larger alphabet, a character at a random location is replaced with a random new character
Describe the process of inversion in GA’s by Holland
A mutation where part of a chromosome is cut out, rotated 180 degrees and fitted back in the same position
Usually needs 2 break
Describe the process of translocation in GA’s by Holland
A mutation where part of the chromosome is cut out and moved to a different location in the chromosome
Usually needs 2 break
What is the purpose of a fitness function in GA’s by Holland
To evaluate chromosome fitness- how well the candidate solution solves the problem
Describe the process of the fitness function
Takes a chromosome as input
Produces its quantitative fitness evaluation as an output
What are the requirements of the fitness function
Correlate to the designer’s goal
Should be computationally efficient
What is better:
Precise fitness function but time consuming
or
Approximate fitness function but efficient
Approximate fitness function but efficient
When is an approximate fitness function used
When precise fitness function is time consuming
When precise fitness function is missing or hard to obtain
When precise fitness function model contains uncertainties
What is a selection operator in GA’s by Holland
A rule for how to choose which chromosome is more likely to produce offspring for the next generation, used to simulate natural evolution of population of chromosomes
What is a search space in GA’s by Holland
Set of all possible solutions to a problem in consideration
What is a fitness landscape in GA’s by Holland
A representation of all possible solutions and their fitness
Candidate solutions are represented by points on the co-ordinate plane and fitness is measured along an additional dimension
What does evolution cause on a fitness landscape
Movement towards peaks
Why do GAs work
Observation 1: similar looking chromosomes have similar fitness values
-almost optimal chromosome can be obtained by searching for a chromosome that looks similar to the optimal solution
Observation 2: A chromosome can be described by a set of substrings
-similar looking chromosomes have similar substrings
What is stated by a similarity template
Similarity template = schema = building block
What is a schema
A similarity template describing a subset of strings with similarities at certain string positions
A building block of a chromosome
For a scheme with k placeholder *s how many chromosomes are matched
2^k
How many building blocks are there in a particular chromosome of a fixed length l
Schema must:
-be same length
-have same symbol as chromosome or have a * at any particular locus
There are 2^l
What is the order of schema
Denotes the number of defining (non * ) symbols it contains
Represented as O( )
What is the defining length
Denotes the maximum distance between 2 defining symbols
Represented as 𝛿( )
What is stated by the schema theorem
Highly fit,
Short defining length,
Low order schemas increase exponentially in frequency in successive generations
How do you calculate the change in weight (delta w) for perceptron learning
Learning rate x error x input
C x e x a
How do you update the weights for perceptron learning
original weight + change in weight
w + delta w
What kind of learning is perceptron learning
Supervised
-Error is calculated based on network’s output and the input label
-Weights are updated based on error
