In
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
, weighted majority algorithm (WMA) is a
meta learning
Meta-learning is a branch of metacognition concerned with learning about one's own learning and learning processes.
The term comes from the meta prefix's modern meaning of an abstract recursion, or "X about X", similar to its use in metaknowled ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
used to construct a compound algorithm from a
pool
Pool may refer to:
Water pool
* Swimming pool, usually an artificial structure containing a large body of water intended for swimming
* Reflecting pool, a shallow pool designed to reflect a structure and its surroundings
* Tide pool, a rocky pool ...
of prediction algorithms, which could be any type of learning algorithms, classifiers, or even real human experts.
The algorithm assumes that we have no prior knowledge about the accuracy of the algorithms in the pool, but there are sufficient reasons to believe that one or more will perform well.
Assume that the problem is a binary
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
. To construct the compound algorithm, a positive weight is given to each of the algorithms in the pool. The compound algorithm then collects weighted votes from all the algorithms in the pool, and gives the prediction that has a higher vote. If the compound algorithm makes a mistake, the algorithms in the pool that contributed to the wrong predicting will be discounted by a certain ratio β where 0<β<1.
It can be shown that the
upper bounds on the number of mistakes made in a given sequence of predictions from a pool of algorithms
is
:
if one algorithm in
makes at most
mistakes.
There are many variations of the weighted majority algorithm to handle different situations, like shifting targets, infinite pools, or randomized predictions. The core mechanism remains similar, with the final performances of the compound algorithm bounded by a function of the performance of the specialist (best performing algorithm) in the pool.
See also
*
Randomized weighted majority algorithm The randomized weighted majority algorithm is an algorithm in machine learning theory.
It improves the mistake bound of the weighted majority algorithm.
Example
Imagine that every morning before the stock market opens,
we get a prediction from ...
References
Machine learning algorithms