# Margin Infused Relaxed Algorithm

Margin Infused Relaxed Algorithm (MIRA) 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. The change of the parameters is kept as small as possible.

A two-class version called binary MIRA 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 looks as follows:

  Input: Training examples $T=\{x_{i},y_{i}\}$ Output: Set of parameters $w$ $i$ ← 0, $w^{(0)}$ ← 0
for $n$ ← 1 to $N$ for $t$ ← 1 to $|T|$ $w^{(i+1)}$ ← update $w^{(i)}$ according to $\{x_{t},y_{t}\}$ $i$ ← $i+1$ end for
end for
return ${\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}$ 