Margin-infused relaxed algorithm explained

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 a 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:

Input: Training examples

T=\{x_i,y_i\}

Output: Set of parameters

← 0,

w⁽⁰⁾

← 0 for

← 1 to

for

← 1 to

|T|

w⁽ⁱ⁺¹⁾

← update

w⁽ⁱ⁾

according to

\{x_t,y_t\}

←

i+1

end for end for return

	N x \|T\|
\sum		w^(j)
	j=1

N x |T|

The update step is then formalized as a quadratic programming^[2] problem: Find

min\|w⁽ⁱ⁺¹⁾-w⁽ⁱ⁾\|

, so that

score(x_t,y_t)-score(x_t,y')\geqL(y_{t,y') \forall}y'

, 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

External links

adMIRAble – MIRA implementation in C++
Miralium – MIRA implementation in Java
MIRA implementation for Mahout in Hadoop

Notes and References

Crammer . Koby . Singer . Yoram . 2003 . Ultraconservative Online Algorithms for Multiclass Problems . . 3 . 951–991 .
McDonald . Ryan . Crammer . Koby . Pereira . Fernando . Online Large-Margin Training of Dependency Parsers . Proceedings of the 43rd Annual Meeting of the ACL . . 2005 . 91–98 .
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.
Bohnet, B. (2009): Efficient Parsing of Syntactic and Semantic Dependency Structures. Proceedings of Conference on Natural Language Learning (CoNLL), Boulder, 67–72.