Margin-infused relaxed algorithm

Margin Infused Relaxed Algorithm (MIRA)^[1] is a machine learning algorithm, an online algorithm for multi-class 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 after each iteration.

The flow of the algorithm^[2]^[3] 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|}}$

References

^ Crammer, K., Singer, Y. (2003): Ultraconservative Online Algorithms for Multiclass Problems. In: Journal of Machine Learning Research 3, 951-991.
^ Wanatabe, T. et al (2007): Online Large Margin Training for Statistical Machine Translation. In: Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 764–773.
^ Bohnet, B. (2009): Efficient Parsing of Syntactic and Semantic Dependency Structures. Proceedings of Conference on Natural Language Learning (CoNLL), Boulder, 67-72.

External links

[1] Crammer, K., Singer, Y. (2003): Ultraconservative Online Algorithms for Multiclass Problems. In: Journal of Machine Learning Research 3, 951-991.

[2] Wanatabe, T. et al (2007): Online Large Margin Training for Statistical Machine Translation. In: Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 764–773.

[3] Bohnet, B. (2009): Efficient Parsing of Syntactic and Semantic Dependency Structures. Proceedings of Conference on Natural Language Learning (CoNLL), Boulder, 67-72.

[1]

[2]

[3]