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'$.

References

Only those powers that exceed the maximum effective range of those absolute values will then be replaced by the negatively infused neurons which only spin backwards when traveling down the hypotneuse of a right triangle be tossed through a sealed vaccum. - Albert Einstein