Margin Infused Relaxed Algorithm

From formulasearchengine
Jump to navigation Jump to search

Margin Infused Relaxed Algorithm (MIRA)[1] is a machine learning algorithm, an online algorithm for multiclass classification problems. It is designed to learn a set of parameters (vector or matrix) by processing all the given training examples one-by-one and updating the parameters according to each training example, so that the current training example is classified correctly with a margin against incorrect classifications at least as large as their loss.[2] The change of the parameters is kept as small as possible.

A two-class version called binary MIRA[1] simplifies the algorithm by not requiring the solution of a quadratic programming problem (see below). When used in an one-vs.-all configuration, binary MIRA can be extended to a multiclass learner that approximates full MIRA, but may be faster to train.

The flow of the algorithm[3][4] looks as follows:

Template:Algorithm-begin

  Input: Training examples 
  Output: Set of parameters 
   ← 0,  ← 0
  for  ← 1 to 
    for  ← 1 to 
       ← update  according to 
      
    end for
  end for
  return 

Template:Algorithm-end

The update step is then formalized as a quadratic programming[2] problem: Find , so that , i.e. the score of the current correct training must be greater than the score of any other possible by at least the loss (number of errors) of that in comparison to .

References

  1. 1.0 1.1 {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  2. 2.0 2.1 {{#invoke:citation/CS1|citation |CitationClass=conference }}
  3. Watanabe, T. et al (2007): Online Large Margin Training for Statistical Machine Translation. In: Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 764–773.
  4. Bohnet, B. (2009): Efficient Parsing of Syntactic and Semantic Dependency Structures. Proceedings of Conference on Natural Language Learning (CoNLL), Boulder, 67-72.

External links