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.

The flow of the algorithm looks as follows:

Algorithm MIRA
  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*|T|}w^{(j)}}{N*|T|}}$

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

The update step is then formalized as an optimization problem: Find $min||w^{(i+1)}-w^{(i)}||$, so that $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 $y$ must be greater than the score of any other possible $y'$ by at least the loss (number of errors) of that $y'$ in comparison to $y$.