Margin Infused Relaxed Algorithm
Encyclopedia
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
Output: Set of parameters
← 0, 
← 0
for
← 1 to 
for
← 1 to 
← update 
according to 
← 
end for
end for
return
The update step is then formalized as a quadratic programming
problem: Find
, so that 
, i.e. the score of the current correct training 
must be greater than the score of any other possible 
by at least the loss (number of errors) of that 
in comparison to 
.
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
algorithm, an online algorithm
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
for multiclass classification
Multiclass classification
In machine learning, multiclass or multinomial classification is the problem of classifying instances into more than two classes.While some classification algorithms naturally permit the use of more than two classes, others are by nature binary algorithms; these can, however, be turned into...
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
Quadratic programming
Quadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables....
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
Output: Set of parameters
← 0, ← 0for
← 1 to for
← 1 to ← update according to ← end for
end for
return
The update step is then formalized as a quadratic programming
Quadratic programming
Quadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables....
problem: Find
, so that , i.e. the score of the current correct training must be greater than the score of any other possible by at least the loss (number of errors) of that in comparison to .