Margin-infused relaxed algorithm (MIRA) 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. 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:

  Input:T = \{x_i, y_i\}
  Output:w

iw^{(0)} ← 0
  forn ← 1 toN
    fort ← 1 to|T|
w^{(i+1)}w^{(i)}\{x_t, y_t\}
ii + 1
    end for
  end for
  return\frac{\sum_{j=1}^{N \times |T|} w^{(j)}}{N \times |T|}

The update step is then formalized as a quadratic programming.

References

External links

• adMIRAble – MIRA implementation in C++

• Miralium – MIRA implementation in Java

• MIRA implementation for Mahout in Hadoop