Copy of `MIT - Press Statistics Glossary`

The wordlist doesn't exist anymore, or, the website doesn't exist anymore. On this page you can find a copy of the original information. The information may have been taken offline because it is outdated.

MIT - Press Statistics Glossary
Category: Mathematics and statistics
Date & country: 13/09/2007, USA
Words: 279

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.

A simple object in Conway's Game of Life that swims vertically or horizontally.

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.

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.…

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.

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.

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.

A vector of partial derivatives of a function that operates on vectors. Intuitively, the gradient represents the slope of a high-dimensional surface.

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.

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.

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.

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.

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.

Refers to a trait that can be genetically passed from parent to offspring.

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.

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.

The act of calculating an integral, by either a numerical or an analytical solution; the inverse operation of differentiation.

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 …

Irrational Number
A real number that cannot be represented as a fraction.

Doing something repeatedly. Doing something repeatedly. Doing something repeatedly. Doing something repeatedly. Doing something repeatedly.

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.

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 th…

Koch Curve
A fractal curve that looks like the edge of a snowflake. It has no derivative at any point.

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.

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.

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.

See Conway's Game of Life.

Limit Cycle
A periodic cycle in a dynamical system such that previous states are returned to repeatedly.

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.

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.

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; …

A function that is usually understood to be iterated in discrete time steps.

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.

The arithmetical average of a collection of numbers; the center of a Gaussian distribution.

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.

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.

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.

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.

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.

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.

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 univers…

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.

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.

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.

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.

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.

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.

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].

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.

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.

The simplest type of feedforward neural network. It has only inputs and outputs, i.e., no hidden layers.

Refers to motion that goes through a finite number of regions, returns to a previous state, and repeats the same fixed pattern forever.

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.