Margin-infused relaxed algorithm

Margin-infused relaxed algorithm (MIRA)^[1] is a machine learning and 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:

Algorithm MIRA
 Input: Training examples ${\displaystyle T=\{x_{i},y_{i}\}}${\displaystyle T=\{x_{i},y_{i}\}}
 Output: Set of parameters ${\displaystyle w}${\displaystyle w}

 ${\displaystyle i}${\displaystyle i} ← 0, ${\displaystyle w^{(0)}}${\displaystyle w^{(0)}} ← 0
 for ${\displaystyle n}${\displaystyle n} ← 1 to ${\displaystyle N}${\displaystyle N}
 for ${\displaystyle t}${\displaystyle t} ← 1 to ${\displaystyle |T|}${\displaystyle |T|}
 ${\displaystyle w^{(i+1)}}${\displaystyle w^{(i+1)}} ← update ${\displaystyle w^{(i)}}${\displaystyle w^{(i)}} according to ${\displaystyle \{x_{t},y_{t}\}}${\displaystyle \{x_{t},y_{t}\}}
 ${\displaystyle i}${\displaystyle i} ← ${\displaystyle i+1}${\displaystyle i+1}
 end for
 end for
 return ${\displaystyle {\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}}${\displaystyle {\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}}

The update step is then formalized as a quadratic programming ^[2] problem: Find ${\displaystyle min\|w^{(i+1)}-w^{(i)}\|}${\displaystyle min\|w^{(i+1)}-w^{(i)}\|}, so that ${\displaystyle score(x_{t},y_{t})-score(x_{t},y')\geq L(y_{t},y')\ \forall y'}${\displaystyle score(x_{t},y_{t})-score(x_{t},y')\geq L(y_{t},y')\ \forall y'}, i.e. the score of the current correct training ${\displaystyle y}${\displaystyle y} must be greater than the score of any other possible ${\displaystyle y'}${\displaystyle y'} by at least the loss (number of errors) of that ${\displaystyle y'}${\displaystyle y'} in comparison to ${\displaystyle y}${\displaystyle y}.

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

• Classification algorithms

• Articles with short description
• Short description matches Wikidata