7
$\begingroup$

I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for different purposes?

I couldn't find any exact definition for this term, though I have found examples of meta-algorithms such as Boosting in machine learning.

$\endgroup$
13
$\begingroup$

I interpret it as meaning "algorithmic technique". It's a general framework that can be used to solve a number of problems.

Don't worry too much about the meaning of that phrase. It's not something with an accepted definition, and you don't need to understand it to gain the value from that survey paper; it's just a passing phrase. Instead, focus on understanding the ideas and technical results in the survey paper.

$\endgroup$
  • 4
    $\begingroup$ You know, for a field built on the ruthless exactness demanded by the machines we code, when it comes to communicating with fellow humans we're really, really bad at it. $\endgroup$ – corsiKa Apr 16 at 4:13
  • 1
    $\begingroup$ @corsiKa The implementer of humans followed Postel's principle (well half of it...) which makes it hard to tell when ambiguous or erroneous input is processed incorrectly. If communication with humans demanded ruthless exactness and had clear feedback of failure, I'm sure communication would be much more precise. However, Postel's principle leads to a need to maintain bug-compatibility so we can't expect it to be fixed in a future version. More seriously, I don't think computer scientists are particularly worse than average on this front. $\endgroup$ – Derek Elkins Apr 16 at 6:15
1
$\begingroup$

The term "meta-algorithm" has a fairly well-accepted meaning in the context of learning theory, which is the field of research from which multiplicative weights originates.

Specifically, a meta-algorithm, in the context of learning theory, is an algorithm that decides how to take a set of other (typically, though not necessarily non-meta) "algorithms" (which might be as dumb as a constant output, for example), and constructs a new algorithm out of those, often by combining or weighting the outputs of the component algorithms. (Don't take this to be a canonical definition though.) Typically those component algorithms are viewed as black-boxes taking input and producing their output, with the inner workings hidden/irrelevant.

There are a number of examples of meta-algorithms. The referenced Multiplicative Weighting algorithm is one example. A particularly simple example is majority voting for an ensemble of binary classifiers: Suppose you have a bunch of binary classification algorithms, and you don't know how to pick a good one. You can just compute them all, and let them vote. Voting in this case is the meta-algorithm. Of course, this may not work very well, and you might want to do something like weighted voting, where the weight somehow scales with observed performance.

Just a few examples of meta-algorithms that I can think of at the moment:

  • multiplicative weights
  • weighted majority
  • boosting
  • bagging
  • ensemble averaging, voting
  • "Follow the Leader"

As always, you can find examples that blur the line between meta and not meta. For example, K-nearest neighbors could be considered a weighted voting/averaging of component algorithms, where every potential neighbor (i.e. the labeled points in the dataset) is its own component algorithm, having a constant output, and the weighting is a function of distance from the algorithm input.

New contributor
bean is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.