Encyclo - MIT - Press Statistics Glossary

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

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.

In computer science, and particularly in artificial intelligence, the task of determining a stepwise plan to accomplish a very specific task.

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.

The likelihood that a random event will occur.

An algorithm that is written in a programming language for execution on a physical computer.

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.

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

Without cause; not compressible; obeying the statistics of a fair coin toss.

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.

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.

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.

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.

A single number, as opposed to a multidimensional vector or matrix.

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

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.

See natural selection.

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.

Referring directly back to oneself through information flow, influence, or cause and effect. See Self-Referential.

An object that is structurally recursive in that a part will look like the whole. See also fractal.

The tendency of a system (sometimes chaotic) to change dramatically with only small perturbations.

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.

An ``S'' shaped function that is often used as an activation function in a neural network.

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.

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.

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.

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

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.

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.

Something that is random.

Strange Attractor
An attractor of a dynamical system that is usually fractal in dimension and is indicative of chaos.

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.

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.

Any sequence of letters, numbers, digits, bits, or symbols.

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.

The junction between two neurons in which neural activity is propagated from one neuron to another. See also excitatory, inhibitory, and weight.

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.

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

A statement in a formal system that has proof.

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.

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

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.

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.

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.

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.

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.

A virtual ant; a type of cellular automaton that vaguely emulates the activity of one or more ants.

Genetic differences among individuals in a population.

A one-dimensional array of numbers that can be used to represent a point in a multidimensional space.

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.

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.