Activation
The time-varying value that is the output of a neuron.
Activation Function
A function that translates a neuron's net input to an
activation value.
Adaptive
Subject to adaptation; can change over time to improve fitness or
accuracy.
Adaptation
An internal change in a system that mirrors an external event in
the system's environment.
Affine
An equation that can be written in terms of
matrix-vector multiplication and vector addition.
Agent
See Autonomous Agent.
AI
An abbreviation for Artificial Intelligence.
Algorithm
A detailed and unambiguous sequence of instructions that describes how
a computation is to proceed and can be implemented as a
program.
Algorithmic Complexity
The size of the smallest program that can produce a particular
sequence of numbers. Regular patterns have low algorithmic complexity
and random sequences have high algorithmic complexity.
Always Cooperate
A Prisoner's Dilemma strategy that cooperates with its
opponent under all circumstances (the exact opposite of always
defect).
Always Defect
A Prisoner's Dilemma strategy that never cooperates with its
opponent under any circumstance (the exact opposite of
always cooperate).
Analog
Having a continuous value.
Analytical
Can be symbolically represented in a closed form that does not require
any of the complex aspects of a program such as an iterative
sum.
Analytical Solution
An exact solution to a problem that can be calculated symbolically by
manipulating equations (unlike a numerical solution).
Arms Race
Two or more species experience adaptation to one another in a
coevolutionary manner. This often seen in predator-prey
systems.
Artificial Intelligence
The science of making computers do interesting things that humans do
effortlessly.
Artificial Life
The study of life processes within the confines of a computer.
Associative Memory
Memory that can be referenced by content, as opposed to location.
Hopfield networks will act as associative memories
when trained with the Hebbian learning rule.
Asynchronous
Describes events that occur independently of each other but on a
similar time scale.
Attractor
A characterization of the long-term behavior of a dissipative
dynamical system. Over long periods of time, the state
space of some dynamical systems will contract toward this
region. Attractors may be fixed points, periodic,
quasiperiodic, or chaotic. They may also be
stable or unstable.
Autonomous Agent
An entity with limited perception of its environment that can
process information to calculate an action so as to be goal-seeking on
a local scale. A boid is an example of an autonomous agent.
Axiom
A statement that is assumed to be true and can later be used
along with theorems to prove other theorems. Also, the starting
configuration of an L-System.
Backpropagation
An algorithm for efficiently calculating the error
gradient of a neural network, which can then be used
as the basis of learning. Backpropagation is equivalent to the
delta rule for perceptrons, but can also calculate
appropriate weight changes for the hidden layer weights of
a multilayer perceptron by generalizing the notion of an error
correction term. In the simplest case, backpropagation is a type of
steepest descent in the search space of the network
weights, and it will usually converge to a local minimum.
Basin of Attraction
A region of state space in which all included states of a
dynamical system ultimately lead into the attractor.
Bias
See threshold.
Bifurcation
The splitting of a single mode of a system's behavior into two
new modes. This usually occurs as a function of a
continuously varying control parameter. A cascade of
bifurcations will usually precede the onset of chaos.
Binary
Written in a form that uses only 0s and 1s. A string of
bits.
Bit
The smallest unit of information; the answer to a yes/no question; the
outcome of a coin toss; a 0 or a 1.
Boid
An autonomous agent that behaves like a simplified bird but will
display flocking patterns in the presence of other boids.
Boolean
Taking only 0/1, true/false, yes/no values.
Bottom-Up
A description that uses the lower-level details to explain
higher-level patterns; related to reductionism.
Brown Noise/Brownian Motion
A form of randomness that is the result of cumulatively adding
white noise, to yield a random walk pattern.
Bucket Brigade Algorithm
A learning algorithm that is a method for adjusting the
strengths of the classifiers of a classifier system.
``Winning'' classifiers pay a portion of their earnings to other
classifiers that assisted them in being activated, similar to an
economic system.
Byte
Eight bits. In programming, often used to store a single text
character.
Cantor Set
A simple fractal set composed of an uncountable
infinity of dust-like points, but that also has 0 measure (meaning
that the sum width of all points is 0). The Cantor set is constructed
by removing the middle third of a unit line segment, and then
recursively removing the middle third of any remaining line
segments, for an infinite number of steps.
Cellular Automaton (CA)
A discrete dynamical system that is composed of an array of
cells, each of which behaves like a finite-state automaton. All
interactions are local, with the next state of a cell being a
function of the current state of itself and its neighbors.
Conway's Game of Life is a CA.
Chaos/Chaotic
Irregular motion of a dynamical system that is
deterministic, sensitive to initial conditions, and impossible
to predict in the long term with anything less than an infinite and
perfect representation of analog values.
Chomsky Hierarchy
Four classes of languages (or computing machines) that have increasing
complexity: regular (finite-state automata), context-free
(push-down automata), context-sensitive (linear bounded automata), and
recursive (Turing machines).
Classifier
A rule that is part of a classifier system and has a condition
that must be matched before its message (or action) can be posted
(or effected). The strength of a classifier determines the
likelihood that it can outbid other classifiers if more than one
condition is matched.
Classifier System
An adaptive system similar to a Post production system
that contains many ``if ... then'' rules called classifiers.
The state of the environment is encoded as a message by a
detector and placed on the message list from which
the condition portion of the classifiers can be matched. ``Winning''
classifiers can then post their own messages to the message list,
ultimately forming a type of computation that may result in a message
being translated into an action by an effector. The
strengths of the classifiers are modified by the bucket
brigade algorithm, and new rules can be introduced via a genetic
algorithm.
Coevolution
Two or more entities experience evolution in response to one
another. Due to feedback mechanisms, this often results in a
biological arms race.
Complement
A set composed of all elements that are not members of another
set.
Combinatorial Optimization
A class of problems in which the number of candidate solutions is
combinatorial in size. Each possible solution has an associated cost.
The goal is to find the solution with the lowest cost. Because of the
vast numbers involved, explicit search an entire
search space is not always possible.
Complete
Describes a formal system in which all statements can be
proved as being true or false. Most interesting formal systems are
not complete, as proved in Gödel's Incompleteness Theorem.
Complex Number
A number that has a real component and an imaginary
component and is characterized as a point on a plane (instead of the
real number line).
Complex System
A collection of many simple nonlinear units that operate in
parallel and interact locally with each other so as to produce
emergent behavior.
Complexity
An ill-defined term that means many things to many people. Complex
things are neither random nor regular, but hover somewhere in
between. Intuitively, complexity is a measure of how interesting
something is. Other types of complexity may be well defined; see the
index for other references.
Compressible
Having a description that is smaller than itself; not random;
possessing regularity.
Computable
Expressible as a yes/no question that can be answered in any case by a
computer in finite time.
Computation
The realization of a program in a computer.
Connectivity
The amount of interaction in a system, the structure of the
weights in a neural network, or the relative number of
edges in a graph.
Conservative System
A dynamical system that preserves the volume of its state
space under motion and, therefore, does not display the types of
behavior found in dissipative systems.
Consistence
In formal systems, having the property that all statements
are either true or false.
Continuous
Taking a real value, i.e., not discrete. Dynamical
systems may operate in continuous time or space.
Control
Exerting actions to manipulate a system or environment in a
goal-seeking manner.
Convergence
For computers, halting with an answer; for dynamical systems,
falling into an attractor; for searches (e.g.,
backpropagation and
genetic algorithms), finding a location that cannot be improved
upon; for infinite summations, approaching a definite value.
Conway's Game of Life
A cellular automaton rule set that operates on a two-dimensional
grid. Each cell changes its state according to the states of its
eight nearest neighbors: dead cells come alive with exactly three live
neighbors, and cells die if they have anything but two or three
neighbors. The Game of Life can display complex patterns such as
gliders, fish, and glider guns, and is also capable of
universal computation.
Co-Recursively Enumerable (CO-RE)
The complement of a set that can be recursively
enumerated.
Countable Infinity
Having the same number of objects as the set of natural
numbers.
Crossover
A genetic operator that splices information from two or more parents
to form a composite offspring that has genetic material from all
parents.
Darwinism
The theory of evolution as proposed by Charles Darwin, which
combined variation of inheritable traits with natural
selection. After the discovery of the physical mechanism of
genetics, this was further refined into neo-Darwinism.
Delta Rule
The perceptron learning rule that specifies that weight
changes should be proportional to the product of a weight's input and
the error (or delta) term for the perceptron.
Derivative
An expression that characterizes how the output of a function
changes as the input is varied. Unlike integrals, derivatives
can be calculated in an analytical manner very easily.
Decision Problem
A problem in which all questions take the form ``Is something a member
of a particular set?'' and all answers are either ``yes'' or
``no.''
Detector
A sensor that translates the state of a classifier's
environment into a message that is suitable for posting to
the message list of the classifier system.
Determinant
A quantity of a matrix that characterizes the amount of expansion
or contraction that the matrix inflicts on a vector when that
vector is multiplied by the matrix.
Deterministic
Occurring in a non-random manner such that the next state of a
system depends only on prior states of the system or the
environment. Perfect knowledge of previous states implies
perfect knowledge of the next state.
Diagonal Matrix
A matrix that has 0 entries along all nondiagonal entries,
i.e., only the main diagonal may have non-zero values.
Difference Equation
An equation that describes how something changes in discrete time
steps. Numerical solutions to integrals are usually
realized as difference equations.
Differential Equation
A description of how something continuously changes over time.
Some differential equations can have an analytical solution
such that all future states can be known without simulation of
the time evolution of the system. However, most can have a
numerical solution with only limited accuracy.
Differentiation
The act of calculating a derivative; the inverse operation of
calculating an integral.
Diffusion Limited Aggregation
A type of stochastic fractal formed by particles floating
about in a random manner until they stick to something solid.
Discrete
Taking only non-continuous values, e.g., Boolean or
natural numbers.
Dissipative System
A dynamical system that contains internal friction that deforms
the structure of its attractor, thus making motion such as
fixed points, limit cycles, quasiperiodicity, and
chaos possible. Dissipative systems often have internal
structure despite being far from equilibrium, like a whirlpool
that preserves its basic form despite being in the midst of constant
change.
Diverge
For algorithms or computers, to run forever and never halt; for
iterative systems (like the equations for the Mandelbrot
set), reaching a state such that all future states explode in size.
Dot Product
The inner product of two vectors.
Dynamical System
A system that changes over time according to a set of fixed rules
that determine how one state of the system moves to another state.
Dynamics/Dynamical
Pertaining to the change in behavior of a system over time.
Ecology
The study of the relationships and interactions between organisms and
environments.
Ecosystem
A biological system consisting of many organisms from different
species.
Edge of Chaos
The hypothesis that many natural systems tend toward
dynamical behavior that borders static patterns and the
chaotic regime.
Effector
The part of a classifier system that can translate messages
into actions that can manipulate a system or an environment.
Eigenvalue
The change in length that occurs when the corresponding
eigenvector is multiplied by its matrix.
Eigenvector
A unit length vector that retains its direction when multiplied
to the matrix that it corresponds to. An (n * n) matrix
can have as many as n unique eigenvectors, each of which will have
its own eigenvalue.
Embedding
A method of taking a scalar time series and using delayed
snapshots of the values at fixed time intervals in the past so that
the dynamics of the underlying system can be observed as a
function of the previously observed states.
Emergent
Refers to a property of a collection of simple subunits that comes
about through the interactions of the subunits and is not a property
of any single subunit. For example, the organization of an ant colony
is said to ``emerge'' from the interactions of the lower-level
behaviors of the ants, and not from any single ant. Usually, the
emergent behavior is unanticipated and cannot be directly deduced from
the lower-level behaviors. Complex systems are usually
emergent.
Entropy
A measure of a system's degree of randomness or disorder.
Environment
If that which is under study is a system, then the rest of the
world is the environment.
Equilibrium
A state of a system that, if not subjected to perturbation,
will remain unchanged.
Ergodic
The property of a dynamical system such that all regions of a
state space are visited with similar frequency and that all
regions will be revisited (within a small proximity) if given enough
time.
Euclidean
Pertaining to standard geometry, i.e., points, lines, planes, volumes,
squares, cubes, triangles, etc.
Euler's Method
The simplest method of obtaining a numerical solution of a
differential equation. There are many other numerical techniques
that are more accurate; however, an analytical solution (i.e., a
closed form of an integral) is always preferred but not always
possible.
Evolution
A process operating on populations that involves variation among
individuals, traits being inheritable, and a level of
fitness for individuals that is a function of the possessed
traits. Over relatively long periods of time, the distribution of
inheritable traits will tend to reflect the fitness that the traits
convey to the individual; thus, evolution acts as a filter that
selects fitness-yielding traits over other traits.
Evolutionary Stable Strategy (ESS)
In game theory and biology, a strategy that, when possessed
by an entire population, results in an equilibrium such that
mutation of the strategy can never result in an improvement for an
individual. Always Defect is an ESS, while
Always Cooperate is not.
Excitatory
Refers to a neural synapse or weight that is positive such
that activity in the source neuron encourages activity in the
connected neuron; the opposite of inhibitory.
Experimentation
One process by which scientists attempt to understand nature. A
phenomenon is observed and/or manipulated so that changes in the
phenomenon's state can be seen. The resulting data can be used to
derive new models of a process or to confirm an existing model.
Experimentation is the complement of theorization. See also
simulation.
Expert System
A special program that resembles a collection of ``if ...
then'' rules. The rules usually represent knowledge contained by a
domain expert (such as a physician adept at diagnosis) and can be used
to simulate how a human expert would perform a task.
Feedback
A loop in information flow or in cause and effect.
Feedback Neural Network
A neural network that has every neuron potentially connected
to every other neuron. The activations of all neurons are
updated in parallel (synchronous or asynchronous
order), unlike a
feedforward or recurrent neural network.
Feedforward Neural Network
A neural network that is organized with separate layers of
neurons. Connections in such a network are limited to one
direction such that the activations of the input neurons are
updated first, followed by any hidden layers, and then finished
with the outputs.
Feigenbaum Constant
A constant number that characterizes when bump-like maps such as
the logistic map will bifurcate.
Finite-State Automaton (FSA)
The simplest computing device. Although it is not nearly powerful
enough to perform universal computation, it can recognize
regular expressions. FSAs are defined by a state transition table
that specifies how the FSA moves from one state to another when
presented with a particular input. FSAs can be drawn as
graphs.
Fish
A simple object in Conway's Game of Life that swims vertically or
horizontally.
Fitness
A measure of an object's ability to reproduce viable offspring.
Fitness Landscape
A representation of how mutations can change the fitness of
one or more organisms. If high fitness corresponds to high locations
in the landscape, and if changes in genetic material are mapped to
movements in the landscape, then evolution will tend to make
populations move in an uphill direction on the fitness landscape.
Fixed Point
A point in a dynamical system's state space that maps back
to itself, i.e., the system will stay at the fixed point if it does
not undergo a perturbation.
Formal System
A mathematical formalism in which statements can be constructed
and manipulated with logical rules. Some formal systems are built
around a few basic axioms (such as Euclidean geometry) and
can be expanded with theorems that can be deduced through
proofs.
Fractal
An object with a fractal dimension. Fractals are
self-similar and may be deterministic or stochastic.
See also Cantor Set, Diffusion Limited Aggregation,
IFS, Julia Set, L-Systems, MRCM, Mandelbrot
Set, and Strange Attractor.
Fractal Dimension
An extension of the notion of dimension found in Euclidean
geometry. Fractal dimensions can be non-integer, meaning that objects
can be ``more than a line but less than a plane'' and so on. There is
more than one way of computing a fractal dimension, one common type
being the Hausdorff-Besicovich dimension. Roughly speaking, a fractal
dimension can be calculated as the quotient of the logarithm of the
object's size and the logarithm of the measuring scale, in the limit
as the scale approaches 0. Under this definition, standard Euclidean
objects retain their original dimension.
Function
A mapping from one space to another. This is usually understood to be
a relationship between numbers. Functions that are computable
can be calculated by a universal computer.
Function Approximation
The task of finding an instance from a class of functions that is
minimally different from an unknown function. This is a common task
for neural networks.
Game Theory
A mathematical formalism used to study human games, economics,
military conflicts, and biology. The goal of game theory is to find
the optimal strategy for one player to use when his opponent also
plays optimally. A strategy may incorporate randomness, in which
case it is referred to as a mixed strategy.
Gaussian
Normally distributed (with a bell-shaped curve) and having a mean
at the center of the curve with tail widths proportional to the
standard deviation of the data about the mean.
Generalized Delta Rule
Another name for backpropagation.
Genetic Algorithm (GA)
A method of simulating the action of evolution within a
computer. A population of fixed-length strings is evolved with a
GA by employing crossover and mutation operators along with
a fitness function that determines how likely individuals
are to reproduce. GAs perform a type of search in a
fitness landscape.
Genetic Programming (GP)
A method of applying simulated evolution on programs or
program fragments. Modified forms of mutation and crossover
are used along with a fitness function.
Glider
A simple object in Conway's Game of Life that swims diagonally
through the grid space.
Glider Gun
An object in Conway's Game of Life that builds and emits
gliders, which can then be collided in purposeful ways to
construct more complicated objects.
Global Minimum (Maximum)
In a search space, the lowest (or highest) point of the surface,
which usually represents the best possible solution in the space with
respect to some problem.
Gödel Number
A natural number computed via a Gödelization procedure
that uniquely corresponds to a string.
Gödelization
A method for mapping arbitrary strings to natural numbers
such that the process is one-to-one and invertible. The
process usually exploits the properties of prime numbers. Since
Gödelization can be defined as a computable
function, and since functions can be Gödelized, some
functions (or programs) can assert statements about other
functions or programs, or themselves.
Gödel's Incompleteness Theorem
Any sufficiently interesting formal system can express true
statements for which there can be no proof in the original
formal system.
Gödel's Statement
Given the formal statement ``There does not exist any proof
for the statement with Gödel number x applied to x,'' which
has it own Gödel number, g, Gödel's statement paraphrased is
``There does not exist a proof of the statement with Gödel number
g applied to itself.'' Gödel's statement is true, but cannot be
proven true in the formal system in which it is constructed,
which leads to Gödel's Incompleteness Theorem.
Gradient
A vector of partial derivatives of a function that
operates on vectors. Intuitively, the gradient represents the slope
of a high-dimensional surface.
Graph
A construct that consists of many nodes connected with edges. The
edges usually represent a relationship between the objects represented
by the nodes. For example, if the nodes are cities, then the edges
may have numerical values that correspond to the distances between the
cities. A graph can be equivalently represented as a matrix.
Halting Problem
The problem of determining if a program halts or doesn't halt on
a particular input. This is an incomputable problem.
Halting Set
The recursively enumerable set of Gödel numbers that
correspond to programs that halt if given their own Gödel
number as input.
Hebbian Learning
A rule that specifies that the strength of a synapse between two
neurons should be proportional to the product of the activations
of the two neurons.
cd
Hénon Map
A chaotic system (defined by the two equations x(t+1) = a
- x(t)^2 + b y(t) and y(t+1) = x(t)) that has a fractal
strange attractor and operates in discrete time.
Hidden Layer
In a feedforward or recurrent neural network, a layer
of neurons that is neither the input layer nor the output layer
but is physically between the two.
Hill-Climbing
One of the simplest search methods that attempts to find a
local maximum by moving in an uphill direction. It is related
to steepest ascent. Hill-climbing may use gradient
information, or random sampling of nearby points, in order to
estimate the uphill direction.
Holism
The idea that ``the whole is greater than the sum of the parts.''
Holism is credible on the basis of emergence alone, since
reductionism and bottom-up descriptions of nature often fail
to predict complex higher-level patterns. See also top-down.
Hopfield Network
A type of feedback neural network that is often used as an
associative memory or as a solution to a combinatorial
optimization problem.
IFS
An iterated functional system; it constructs a fractal by
iterating a vector quantity through an affine equation that
is randomly selected on each iteration.
Imaginary Number
The square root of a negative number. The square root of -1 is often
denoted as i for the purpose of writing out complex numbers.
Implicit Parallelism
The idea that genetic algorithms have an extra built-in form of
parallelism that is expressed when a GA searches through a
search space. Implicit parallelism depends on the similarities
and differences between individuals in the population. The theory
posits that GAs process more schemata than there are strings
in a population, thus getting something of a free lunch. See also
no free lunch.
Incomputable
Something that cannot be characterized by a program that always
halts. Sets that are incomputable may be recursively
enumerable (like the halting set),
co-recursively enumerable
(e.g., the halting set's complement),
or not recursively enumerable
(which, if also not CO-RE, is a random
set).
Incomputable Number
A real number with an infinite decimal (or binary) expansion
that cannot be enumerated by any universal computer.
Inheritable
Refers to a trait that can be genetically passed from parent to
offspring.
Inhibitory
Refers to a neural synapse or weight that is negative such
that activity in the source neuron encourages inactivity in the
connected neuron. The opposite of excitatory.
Inner Product
For two vectors of the same dimensionality, the sum of the
pairwise products of the two vector components.
Integral
The cumulative continuous sum of a function. The integral
of a differential equation represents the future state of a
dynamical system; however, most integrals do not have an
analytical solution, which means that they may only have
numerical solutions, an admittedly inexact process.
Integration
The act of calculating an integral, by either a numerical or
an analytical solution; the inverse operation of
differentiation.
Invertible
A function is invertible (with a unique inverse) if the output
uniquely determines the input (i.e., it is one-to-one) and the
set of legal outputs is equal to the set of legal inputs. The
function x^2 is not strictly invertible, while x^3 has an inverse.
For operations the definition is slightly looser. While
integration and differentiation are considered to be
inverse operations, there are an infinite number of
integrals that are valid results for integrating any function;
thus, the process is not one-to-one.
Irrational Number
A real number that cannot be represented as a fraction.
Iterated Prisoner's Dilemma
The Prisoner's Dilemma game played in an iterative manner
for a number of rounds that is unknown to both players.
Iterate/Iterative
Doing something repeatedly. Doing something repeatedly. Doing
something repeatedly. Doing something repeatedly. Doing something
repeatedly.
Julia Set
A set of complex numbers that do not diverge if
iterated an infinite number of times via a simple equation. The
points form an extremely complex fractal. There is an
uncountable infinity of Julia sets, each of which
corresponds to a particular complex number that appears as a constant
in the iterative procedure. Julia sets are similar to
co-recursively enumerable sets because only points that are not a
members of the set can actually be identified as such. All of the
Julia sets are related to the Mandelbrot set.
Koch Curve
A fractal curve that looks like the edge of a snowflake. It has
no derivative at any point.
Lamarckism
A method of heredity that does not apply to genetics but is applicable
to social adaptation. Lamarckism posits that acquired traits can
be passed from parent to offspring.
Lambda Calculus
A model of computation that is capable of universal
computation. The Lisp programming language was inspired by
Lambda calculus.
Learning
A process of adaptation by which synapses, weights of
neural network's, classifier strengths, or some other set
of adjustable parameters is automatically modified so that some
objective is more readily achieved. The backpropagation and
bucket brigade algorithms are two types of learning
procedures.
LIFE
See Conway's Game of Life.
Limit Cycle
A periodic cycle in a dynamical system such that previous
states are returned to repeatedly.
Linear
Having only a multiplicative factor. If f(x) is a linear
function, then f(a+b) = f(a) + f(b) and c f(x) = f(cx) must
both be true for all values of a, b, c, and x. Most things in
nature are nonlinear.
Linearly (In)separable
Two classes of points are linearly separable if a linear
function exists such that one class of points resides on one
side of the hyperplane (defined by the linear function), and all
points in the other class are on the other side. The XOR
mapping defines two sets of points that are linearly inseparable.
Lisp
A programming language designed to manipulate lists that was inspired
by
Lambda Calculus and was the inspiration for Stutter.
Local Minimum (Maximum)
The bottom of a valley or the top of a peak; a point in a search
space such that all nearby points are either higher (for a minimum)
or lower (for a maximum). In a continuous search space, local
minima and maxima have a 0 gradient vector. Note that
this particular valley (or peak) may not necessarily be the lowest (or
highest) location in the space, which is referred to as the global
minimum (maximum).
Logistic Map
The simplest chaotic system that works in discrete time
and is defined by the map x(t) = 4r x(t) (1-x(t)).
Feigenbaum's constant was first identified for this map.
Lorenz System
A system of three differential equations that was the first
concrete example of chaos and a strange attractor.
Lotka-Volterra System
A two-species predator-prey system that in its simplest form can
display only fixed points or limit cycles. More complicated
versions with three or more species can yield chaos.
L-System
A method of constructing a fractal that is also a model for
plant growth. L-systems use an axiom as a starting
string and iteratively apply a set of parallel
string substitution rules to yield one long string that can be used
as instructions for drawing the fractal. One method of interpreting
the resulting string is as an instruction to a turtle graphics
plotter. Many fractals, including the Cantor set, Koch
curve, and Peano curve, can be expressed as an L-system.
Mackey-Glass System
A delay differential equation (dx/dt = (ax(t-tau))/(1 +
x^10(t-tau)) - bx(t)) that can display a wide variety of behaviors
via an adjustable delay term, tau. Even though this system
generates a single scalar time series, it can be extremely
chaotic because its value at any time may depend on its entire
previous history.
Mandelbrot Set
An extremely complex fractal that is related to Julia sets
in the way that it is constructed and by the fact that it acts as a
sort of index to the Julia sets. Like the Julia sets, the Mandelbrot
set is calculated via an iterative procedure. Starting
conditions that do not diverge after an infinite number of
iterations are considered to be inside the set. If, and only if, a
complex number is in the Mandelbrot set, then the Julia set that
uses that complex number as a constant will be connected; otherwise,
the corresponding Julia set will be unconnected.
Map
A function that is usually understood to be iterated in
discrete time steps.
Matrix
A rectangular two-dimensional array of numbers that can be thought of
as a linear operator on vectors. Matrix-vector
multiplication can be used to describe geometric transformations such
as scaling, rotation, reflection, and translation. They can also
describe the affine transformation used to construct IFS and
MRCM fractals.
Mean
The arithmetical average of a collection of numbers; the center of a
Gaussian distribution.
Meme
A unit of cultural information that represents a basic idea that can
be transferred from one individual to another, and subjected to
mutation, crossover, and adaptation.
Message
The basic unit of information in a classifier system that is
stored in the message list. A message may correspond to an
external state of an environment or an internal state of the
classifier system.
Message List
The portion of a classifier system that retains information in
the form of messages.
Mixed Strategy
In game theory, a strategy that uses randomness by
employing different actions in identical circumstances with different
probabilities.
Model
In the sciences, a model is an estimate of how something works. A
model will usually have inputs and outputs that correspond to its
real-world counterpart. An adaptive system also contains an
implicit model of its environment that allows it to change its
behavior in anticipation of what will happen in the environment.
Model of Computation
An idealized version of a computing device that usually has some
simplifications such as infinite memory. A Turing machine, the
lambda calculus, and Post production systems are all models
of computation.
Monotonic
The property of a function that is always strictly increasing or
strictly decreasing, but never both. The sigmoidal
activation function of a multilayer perceptron is
monotonically increasing.
MRCM
The Multiple Reduction Copy Machine algorithm, which can be used
to make affine fractals. MRCM fractals are related to
IFS fractals in that they both use the same types of affine
transformations. The MRCM algorithm performs several affine
transformations of a seed image in parallel to yield a secondary
seed image. The output of the MRCM is recursively passed back
through to its input multiple times, to yield the fractal.
Multilayer Perceptron (MLP)
A type of feedforward neural network that is an extension of the
perceptron in that it has at least one hidden layer of
neurons. Layers are updated by starting at the inputs and ending
with the outputs. Each neuron computes a weighted sum of the incoming
signals, to yield a net input, and passes this value through its
sigmoidal activation function to yield the neuron's
activation value. Unlike the perceptron, an MLP can solve
linearly inseparable problems.
Mutation
A random change in any portion of genetic material. For a
genetic algorithm, this means that a value in a bit
string is randomly set.
Nash Equilibrium
In game theory, a pair of strategies for a game such that
neither player can improve his outcome by changing his strategy. A
Nash equilibrium sometimes takes the form of a saddle structure.
Under some cases, when a strategy is at a Nash equilibrium with
itself, the strategy resembles an evolutionary stable strategy.
Natural Number
Any of the standard counting numbers; a positive integer.
Natural Selection
The natural filtering process by which individuals with higher
fitness are more likely to reproduce than individuals with lower
fitness.
Neo-Darwinism
A synthesis of Darwinism with the mechanisms of genetics; the
idea that adaptation equals a combination of variation,
heredity, and selection. See also evolution, inheritable,
and natural selection.
Net Input
The weighted sum of incoming signals into a neuron plus a
neuron's
threshold value.
Neural Network (NN)
A network of neurons that are connected through synapses or
weights. In this book, the term is used almost exclusively to
denote an artificial neural network and not the real thing. Each
neuron performs a simple calculation that is a function of the
activations of the neurons that are connected to it. Through
feedback mechanisms and/or the nonlinear output
response of neurons, the network as a whole is capable of performing
extremely complicated tasks, including universal computation and
universal approximation. Three different classes of neural
networks are feedforward, feedback, and recurrent neural
networks, which differ in the degree and type of connectivity
that they possess.
Neuron
A simple computational unit that performs a weighted sum on incoming
signals, adds a threshold or bias term to this value to yield a
net input, and maps this last value through an activation
function to compute its own activation. Some neurons, such as
those found in feedback or Hopfield networks, will
retain a portion of their previous activation.
Newton's Method
An iterative method for finding 0 values of a function.
Niche
A way for an animal to make a living in an ecosystem.
No Free Lunch (NFL)
A theorem that states that in the worst case, and averaged over
an infinite number of search spaces, all search methods
perform equally well. More than being a condemnation of any search
method, the NFL theorem actually hints that most naturally occurring
search spaces are, in fact, not random.
Nonlinear
A function that is not linear. Most things in nature are
nonlinear. This means that in a very real way, the whole is at least
different from the sum of the parts. See also holism.
Not Recursively Enumerable (not-RE)
An infinite set that cannot be recursively enumerated.
Sets of this type that are also not co-recursively enumerable
are effectively random.
NP
Nondeterministic polynomial time problems; a class of computational
problems that may or may not be solvable in polynomial time but
are expressed in such a way that candidate solutions can be tested for
correctness in polynomial time. See also time complexity and
NP-Complete.
NP-Complete
A problem type in which any instance of any other NP class
problem can be translated to in polynomial time. This means that
if a fast
algorithm exists for an NP-complete problem, then any problem
that is in NP can be solved with the same algorithm.
Numerical Solution
A solution to a problem that is calculated through a simulation.
For example, solving the Three Body Problem is not possible in
the worst case; however, with the differential equations that
describe the motions of three bodies in space, one could simulate
their movements by simulating each time step. Nevertheless, numerical
solutions are usually error-prone due to sensitivity and,
therefore, can be used to estimate the future for only relatively
short time spans, in the worst case.
Occam's Razor
The principle that when faced with multiple but equivalent
interpretations of some phenomenon, one should always choose the
simplest explanation that correctly fits the data. Occam's Razor is
useful for selecting competing models for some phenomena.
One-to-One
A function or map that for every possible output has only
one input that yields that particular output; if f(a) = f(b), then
a = b.
Optimization
The process of finding parameters that minimizes or maximizes a
function.
Outer Product
An operation on two vectors that yields a matrix. Given two
vectors with the same dimensionality, the outer product is a square
symmetric matrix that contains the product of all pairs of elements
from the two vectors, i.e., A[i,j] = x[i] y[j].
Parallel/Parallelism
Many things happening at once.
Pattern Classification
A task that neural networks are often trained to do. Given some
input pattern, the task is to make an accurate class assignment to the
input. For example, classifying many images of letters to one of the
twenty-six letters of the alphabet is a pattern classification task.
Payoff
In game theory, the amount that a player wins, given the player's
and his opponent's actions.
Peano Curve
A fractal space-filling curve that can fill a plane even
though it is a line of infinite length. Oddly enough, it has an
integer fractal dimension of 2.
Perceptron
The simplest type of feedforward neural network. It has only
inputs and outputs, i.e., no hidden layers.
Periodic
Refers to motion that goes through a finite number of regions, returns
to a previous state, and repeats the same fixed pattern forever.
Perturbation
A slight nudge.
Phase Space
In this book, another name for state space. In the scientific
literature, ``phase space'' is used to denote the space of motion in a
dynamical system that moves in continuous time, while
state space is often used for discrete time systems.
Phase Transition
In physics, a change from one state of matter to another. In
dynamical systems theory, a change from one mode of behavior to
another.
Planning
In computer science, and particularly in artificial intelligence,
the task of determining a stepwise plan to accomplish a very specific
task.
Polynomial
A function in which the output is the sum of terms that are the
products of constant values and the input raised to some integer
power. The polynomial of a polynomial is another polynomial. From a
time complexity point of view, polynomials are well-behaved.
Post Production System
A model of computation that resembles a collection of ``if
... then'' rules and is capable of universal computation.
Predator-Prey System
An ecosystem in which one portion of the population consumes
another. With three or more species, simple predator-prey
interactions can lead to chaos and biological arms races.
See also Lotka-Volterra system.
Prime Number
A natural number that can be evenly divided only by itself and 1.
Prisoner's Dilemma
A non-zero-sum game in which both players have incentive not to
cooperate under any circumstances. Thus, the optimal game theory
strategy of always defect has the paradoxical property that
both players would have a higher payoff if they ignored the
advice of game theory.
Probability
The likelihood that a random event will occur.
Program
An algorithm that is written in a programming language for
execution on a physical computer.
Proof
A sequence of statements in which each subsequent statement is
derivable from one of the previous statements or from an axiom of
a formal system. The final statement of a proof is usually the
theorem that one has set out to prove.
Quasiperiodic
Refers to a form of motion that is regular but never exactly
repeating. Quasiperiodic motion is always composed of multiple but
simpler periodic motions. In the general case, for motion that
is the sum of simpler periodic motions, if there exists a length of
time that evenly divides the frequencies of the underlying motions,
then the composite motion will also be periodic; however, if no such
length of time exists, then the motion will be quasiperiodic.
Random/Randomness
Without cause; not compressible; obeying the statistics of a fair
coin toss.
Random Walk
A walk in one or more dimensions that is dictated by the outcome of a
coin toss. The direction of each step of the walk is specified by the
coin toss. The resulting random motion is often referred to as
Brownian motion.
Rational Number
A number that can be expressed as a fraction.
Real Number
Any number that can be represented with a potentially infinite decimal
expansion to the right of the decimal point. Natural,
rational, irrational, and incomputable numbers are all
real numbers.
Recurrent Neural Network
A network similar to a feedforward neural network except that
there may be connections from an output or hidden layer to the
inputs. Recurrent neural networks are capable of universal
computation.
Recursive
Strictly speaking, a set or function is recursive if it is
computable; however, in the usual sense of the word, a
function is said to be recursive if its definition make reference
to itself. For example, factorial can be defined as x! = x * (x -
1)! with the base case of 1! equal to 1. See also
self-referential.
Recursively Enumerable (RE)
A potentially infinite set whose members can be enumerated by a
universal computer; however, a universal computer may not be able
to determine that something is not a member of a recursively
enumerable set. The halting set is recursively enumerable but
not recursive.
Reductionism
The idea that nature can be understood by dissection. In other words,
knowing the lowest-level details of how things work (at, say, the
level of subatomic physics) reveals how higher-level phenomena come
about. This is a bottom-up way of looking at the universe, and
is the exact opposite of holism.
Regular Expression
A definition for a class of strings that can be recognized by a
finite-state automaton. An example of a class of strings that is
regular would be legal mathematical expressions using only ``+'' and
digits. An example that is not regular is the same legal
mathematical expressions as before, but with properly nested
parentheses.
Saddle
A type of surface that is neither a peak nor a valley but still has a
0 gradient. Saddle points are situated such that moving in
one direction takes one uphill, while moving in another direction
would be downhill. Hence, saddles look like the things that cowboys
ride on.
Scalar
A single number, as opposed to a multidimensional vector or
matrix.
Schema/Schemata
A similarity template used to analyze genetic algorithms. By
using wild-card characters, a schema defines an entire class of
strings that may be found in a population.
Search/Search Method
A method for finding a region of interest in a search space.
Usually, the interesting regions correspond to solutions to a specific
problem. Hill-climbing, steepest descent (ascent),
simulated annealing, and genetic algorithms are all search
methods.
Search Space
A characterization of every possible solution to a problem instance.
For a neural network the search space is defined as all possible
assignments to the network weights; for a genetic algorithm,
it is every conceivable value assignment to the strings in the
population.
Selection
See natural selection.
Self-Organization
A spontaneously formed higher-level pattern of structure or
function that is emergent through the interactions of
lower-level objects.
Self-Organized Criticality (SOC)
A mathematical theory that describes how systems composed of many
interacting parts can tune themselves toward dynamical behavior
that is critical in the sense that it is neither stable nor
unstable but at a region near a phase transition. SOC
systems display events in a power-law distribution and are never quite
at equilibrium. See also edge of chaos and
self-organization.
Self-Referential
Referring directly back to oneself through information flow,
influence, or cause and effect. See Self-Referential.
Self-Similar
An object that is structurally recursive in that a part will look
like the whole. See also fractal.
Sensitivity
The tendency of a system (sometimes chaotic) to change
dramatically with only small perturbations.
Set
A collection of things, usually numbers. Sets may be infinite in size.
Shadowing Lemma
Implies that a numerical simulation of chaos may ``shadow''
a real trajectory of a real chaotic system.
Sigmoidal
An ``S'' shaped function that is often used as an activation
function in a neural network.
Simulate/Simulation
Experimentation in the space of theories, or a combination
of experimentation and theorization. Some numerical simulations
are programs that represent a model for how nature works.
Usually, the outcome of a simulation is as much a surprise as the
outcome of a natural event, due to the richness and uncertainty of
computation.
Simulated Annealing
A partially random method of search and optimization
usually used for combinatorial optimization problems. The
technique is modeled on how the molecular structure of metals is
disordered at high temperatures but very ordered and crystalline at
low temperatures. In simulated annealing, a problem instance is
reformulated so that it loosely resembles disordered material.
Gradually, the temperature is lowered such that the ordered states
correspond to good solutions to a problem.
Space Complexity
A function that describes the amount of memory required for a
program to run on a computer to perform a particular task. The
function is parameterized by the length of the program's input. See
also time complexity.
Space-Filling
Refers to a curve that manages to twist and turn in such a way that it
actually fills a space or volume. All space-filling curves are
fractal.
Special Function
In Lisp or Stutter, a built-in function that may or may
not fully evaluate its arguments, such as the if primitive.
Stable
Having a basin of attraction that is non-zero in size; an
attractor that can withstand some form of perturbation.
Standard Deviation
A measure of the spread of a set of data. For a Gaussian
distribution, the standard deviation hints at the width of the tails
of the distribution function.
Statement
In a formal system, a string of characters that is formed
according to well-defined rules such that it is legal for the language
that is the formal system. For example, in the formal system of
arithmetic, the expression ``5 + 3 * (2 - 4)'' is a valid and
well-formed statement, but ``5 + )3 * * (2 (- 4)'' is not.
State Space
In this book, another name for the phase space of a dynamical
system. Roughly speaking, if the dynamics of a dynamical system
can be described by n values, then the state space is the
n-dimensional volume that the system moves through. Systems
that are continuous in time will form a smooth trajectory through
this volume, while discrete systems may jump to different
locations on subsequent time steps. In either case, if a system ever
returns to a previously visited location in the state space, then the
system is in either a fixed point or a limit cycle. For
chaotic systems, or for programs that never halt, the system
will always be at a previously unvisited portion of the state space.
Steepest Descent (Ascent)
A search method that uses the gradient information of a
search space and moves in the opposite direction from the gradient
until no further downhill (or uphill) progress can be made. See also
hill-climbing.
Stochastic
Something that is random.
Strange Attractor
An attractor of a dynamical system that is usually
fractal in dimension and is indicative of chaos.
Strategy
In game theory, a policy for playing a game. A strategy is a
complete recipe for how a player should act in a game under all
circumstances. Some policies may employ randomness, in which
case they are referred to as mixed strategies.
Strength
For a classifier system, a classifier's relative ability to
win a bidding match for the right to post its message on the
message list.
String
Any sequence of letters, numbers, digits, bits, or symbols.
Stutter
A silly programming language used in this book that is based on
Lisp and is capable of universal computation.
Symmetric Matrix
A matrix with the lower-left half equal to the mirror image of
the upper-right half.
Synapse
The junction between two neurons in which neural activity is
propagated from one neuron to another. See also
excitatory, inhibitory, and weight.
Synchronous
Acting in a lockstep fashion, with each event occurring in a precise
order, or in such a way as to eliminate the notion of order entirely.
System
Something that can be studied as a whole. Systems may consist of
subsystems that are interesting in their own right. Or they may exist
in an environment that consists of other similar systems.
Systems are generally understood to have an internal state, inputs
from an environment, and methods for manipulating the environment or
themselves. Since cause and effect can flow in both directions of a
system and environment, interesting systems often posses
feedback, which is self-referential in the strongest case.
Theorem
A statement in a formal system that has proof.
Theorization
A process by which scientists attempt to understand nature; it is the
complement to experimentation. Theorization is the process of
building mathematical models for how things work. Scientists
always desire theories that are simpler than the data they explain.
See also Occam's Razor and simulation.
Three Body Problem
The problem of determining the future positions and velocities of
three gravitational bodies. The problem was proved unsolvable in the
general case by Henri Poincaré, which forshadowed the importance of
chaos. Although no analytical solutions are possible in the
worst case, a numerical solution is sometimes sufficient for
many tasks.
Threshold
A quantity added to (or subtracted from) the weighted sum of inputs
into a neuron, which forms the neuron's net input.
Intuitively, the net input (or bias) is proportional to the amount
that the incoming neural activations must exceed in order for a
neuron to fire.
Time Complexity
A function that describes the amount of time required for a
program to run on a computer to perform a particular task. The
function is parameterized by the length of the program's input. See
also space complexity.
Time-Reversible
A property of dynamical systems that can be run unambiguously
both forward and backward in time. The Hénon map, Lorenz
system, and vant cellular automata are all time-reversible,
while the logistic map, the Mackey-Glass system, and most
other cellular automata are not. Time-reversible systems are
described by functions that are invertible.
Time Series
A sequence of values generated from a dynamical system over time.
Chaotic systems can be analyzed by examining the time series
generated by a single portion of the system. See also
embedding.
Tit-for-Tat
An effective strategy for playing the Iterated Prisoner's
Dilemma. Tit-for-Tat starts by cooperating, and then does whatever
its opponent did in the previous round of play.
Top-Down
A method of examining things that first looks at higher-level
phenomena and then tries to explain lower-level patterns in terms of
the higher-level observations. This is the exact opposite of
bottom-up. See also holism and reductionism.
Transpose
An operation that flips a matrix about the main diagonal.
Turing Machine
A model of computation that uses an underlying finite-state
automaton but also has an infinite tape to use as memory. Turing
machines are capable of universal computation.
Turtle Graphics
A simple language for drawing graphics in which a ``turtle'' is used
to make strokes on a plotting device. Typical commands include ``move
forward,'' ``draw forward,'' and ``turn left.''
Uncountable Infinity
An order of infinity that is larger than the number of natural
numbers. The number of real numbers is uncountably infinite.
Universal Approximation
Having the ability to approximate any function to an arbitrary
degree of accuracy. Neural networks are universal approximators.
Universal Computation
Capable of computing anything that can in principle be computed; being
equivalent in computing power to a Turing machine, the
lambda calculus, or a Post production system.
Universal Computer
A computer that is capable of universal computation, which means
that given a description of any other computer or program and
some data, it can perfectly emulate this second computer or
program. Strictly speaking, home PCs are not universal computers
because they have only a finite amount of memory. However, in
practice, this is usually ignored.
Unstable
Having a basin of attraction that is 0 in size; being such
that the slightest perturbation will forever change the state of
a system. A pencil balanced on its point is unstable.
Value Function
A built-in function in Lisp or Stutter that evaluates
all of its arguments prior to being executed, e.g., car,
cdr, and cons.
Vant
A virtual ant; a type of cellular automaton that vaguely emulates
the activity of one or more ants.
Variation
Genetic differences among individuals in a population.
Vector
A one-dimensional array of numbers that can be used to represent a
point in a multidimensional space.
Weight
In a neural network, the strength of a synapse (or
connection) between two neurons. Weights may be positive
(excitatory) or negative (inhibitory). The thresholds
of a neuron are also considered weights, since they undergo
adaptation by a learning algorithm.
White Noise
Noise that uniformly distributed in the frequency domain;
randomness that is uniformly distributed; thus, a white noise
process with a range of 0 to 1 would yield a random number in this
range with probability equal for all possible values. Brown
noise is a result of cumulatively adding white noise.
XOR
The exclusive-or function; given two Boolean inputs, the
output of XOR is 1 if and only if the two inputs are different;
otherwise, the output is 0.
Zero-Sum Game
In game theory, a game in which a win for one player results in
an equal but opposite loss for the other players.
