An adaptive algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that changes its behavior at the time it is run,
based on information available and on ''a priori'' defined reward mechanism (or criterion). Such information could be the story of recently received data, information on the available computational resources, or other run-time acquired (or ''a priori'' known) information related to the environment in which it operates.
Among the most used adaptive algorithms is the
Widrow-Hoff’s least mean squares (LMS), which represents a class of stochastic gradient-descent algorithms used in adaptive filtering and machine learning. In adaptive filtering the LMS is used to mimic a desired filter by finding the filter coefficients that relate to producing the least mean square of the error signal (difference between the desired and the actual signal).
For example,
stable partition, using no additional memory is ''O''(''n'' lg ''n'') but given ''O''(''n'') memory, it can be ''O''(''n'') in time. As implemented by the
C++ Standard Library
The C standard library, sometimes referred to as libc, is the standard library for the C programming language, as specified in the ISO C standard.ISO/ IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the origina ...
stable_partition
is adaptive and so it acquires as much memory as it can get (up to what it would need at most) and applies the algorithm using that available memory. Another example is
adaptive sort, whose behavior changes upon the presortedness of its input.
An example of an adaptive algorithm in
radar
Radar is a system that uses radio waves to determine the distance ('' ranging''), direction ( azimuth and elevation angles), and radial velocity of objects relative to the site. It is a radiodetermination method used to detect and track ...
systems is the
constant false alarm rate
Constant false alarm rate (CFAR) detection is a common form of adaptive algorithm used in radar systems to detect target returns against a background of noise, clutter and interference.
Principle
In the radar receiver, the returning echoes are ...
(CFAR) detector.
In
machine learning
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
and
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, many algorithms are adaptive or have adaptive variants, which usually means that the algorithm parameters such as
learning rate are automatically adjusted according to statistics about the optimisation thus far (e.g.
the rate of convergence). Examples include
adaptive simulated annealing,
adaptive coordinate descent,
adaptive quadrature,
AdaBoost,
Adagrad, Adadelta,
RMSprop, and
Adam
Adam is the name given in Genesis 1–5 to the first human. Adam is the first human-being aware of God, and features as such in various belief systems (including Judaism, Christianity, Gnosticism and Islam).
According to Christianity, Adam ...
.
In
data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressi ...
,
adaptive coding algorithms such as
Adaptive Huffman coding or
Prediction by partial matching
Prediction by partial matching (PPM) is an adaptive statistical data compression technique based on context modeling and prediction. PPM models use a set of previous symbols in the uncompressed symbol stream to predict the next symbol in the str ...
can take a stream of data as input, and adapt their compression technique based on the symbols that they have already encountered.
In
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...
, the
Adaptive Transform Acoustic Coding
Adaptive Transform Acoustic Coding (ATRAC) is a family of proprietary audio compression algorithms developed by Sony. MiniDisc was the first commercial product to incorporate ATRAC, in 1992. ATRAC allowed a relatively small disc like MiniDisc t ...
(ATRAC) codec used in
MiniDisc
MiniDisc (MD) is an erasable magneto-optical disc-based data storage format offering a capacity of 60, 74, or 80 minutes of digitized audio.
Sony announced the MiniDisc in September 1992 and released it in November of that year for sale i ...
recorders is called "adaptive" because the window length (the size of an audio "chunk") can change according to the nature of the sound being compressed, to try to achieve the best-sounding compression strategy.
See also
*
Adaptation (computer science)
Adaptation in computer science is a process where an interactive system (adaptive system) adapts its behaviour to individual users based on information acquired about its user(s) and its environment. Adaptation is one of the three pillars of emp ...
*
Adaptive filter
An adaptive filter is a system with a linear filter that has a transfer function controlled by variable parameters and a means to adjust those parameters according to an optimization algorithm. Because of the complexity of the optimization algorit ...
*
Adaptive grammar
An adaptive grammar is a formal grammar that explicitly provides mechanisms within the Formal system, formalism to allow its own Production rule (formal languages), production rules to be manipulated.
Overview
John N. Shutt defines adaptive gramm ...
*
Adaptive optimization
References
Algorithms
{{soft-eng-stub