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 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 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\times |T|}{w}^{(j)}}{N\times |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 a quadratic programming problem: Find $min\Vert w^{(i+1)}-w^{(i)}\Vert$, so that $score(x_t,y_t)-score(x_t,y^{\prime })\ge L(y_t,y^{\prime })\mathrm{\forall }{y}^{\prime }$, i.e. the score of the current correct training $y$ must be greater than the score of any other possible $y^{\prime }$ by at least the loss (number of errors) of that $y^{\prime }$ in comparison to $y$.

External links

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