Margin Infused Relaxed Algorithm

This method is used by Watanabe et al., EMNLP 2007 to train an MT system a with a very large number of features of the order of millions. The training step was performed using a specific algorithm called the Margin Infused Relaxed Algorithm (MIRA) proposed by Crammer et al., 2006.

Summary

MIRA is an online large-margin training algorithm which updates the weight vector according to certain margin constraints and loss function.

It is used to learn the weights of features after processing each training instance similar to the structured perceptron algorithm with an additional loss function and margin constraint in its update rule.

General Definition

A general definition of online training algorithms can be written down as follows:

• $\forall t,\quad (f^{t},\mathbf {e} ^{t})\in {\mathcal {T}}$ and a list of $m$ -best oracles ${\mathcal {O}}^{t}$. A $k$ -best list of candidates is generated by $best_{k}(\cdot )$ using the current weight vector $\mathbf {w} _{i}$. Each training instance $f_{t}$ can have a multiple number of correct outputs or references, $\mathbf {e} ^{t}$, in this case, target translations.

• Using the $k$-best list, $m$-best oracle translations ${\mathcal {O}}^{t}$ is updated by $oracle_{m}(\cdot )$ in each iteration.

• New weight vector $\mathbf {w} ^{i+1}$ is computed using the $k$-list ${\mathcal {C}}^{t}$ with respect to the oracle ${\mathcal {O}}^{t}$.

• After $N$ iterations, the algorithm returns an averaged weight vector over $T$ training instances to avoid overfitting.

MIRA

The difference in MIRA lies in the weight update rule which differs from one algorithm to the other. It has been widely used in structured classification tasks such as dependency parsing (McDonald et al., 2005) and joint-labeling/chunking (Shimizu and Haas, 2006).

• The basic idea is to keep the norm of the updates to the weight vector as small as possible,
• Considering a margin at least as large as the loss of the incorrect classification.
• The update rule in MIRA is given by:

$\mathbf {\hat {w}} ^{i+1}={\underset {w}{\operatorname {argmin} }}\quad ||\mathbf {w} ^{i+1}-\mathbf {w} ^{i}||^{2}+C\sum _{{\hat {e}},e^{\prime }}\xi ({\hat {e}},e^{\prime })$

subject to

$s^{i+1}(f^{t},{\hat {e}})-s^{i+1}(f^{t},e^{\prime })+\xi ({\hat {e}},e^{\prime })\geq L({\hat {e}},e^{\prime };\mathbf {e} ^{t})$

$\xi ({\hat {e}},e^{\prime })\geq 0$

$\forall {\hat {e}}\in {\mathcal {O}}^{t},\quad \forall {\hat {e}}\in {\mathcal {C}}^{t}$

where, $s^{i}(f^{t},e)=\left\{\mathbf {w} ^{i}\right\}^{\mathrm {T} }\cdot \mathbf {h} (f^{t},e)$.

$\xi (\cdot )$ is a nonnegative slack variable and $C\geq 0$ is a constant to control the influence to the objective function. A larger C implies larger updates to the weight vector.

$L(\cdot )$ is a loss function, that measures the "difference" between ${\hat {e}}$ and $e^{\prime }$ according to the set of references $\mathbf {e} ^{t}$.

A larger error means a larger distance between the scores of the predicted correct and incorrect outputs.

Dual Form

The Langrage dual form for MIRA's objective function is given by:

$max_{\alpha (\cdot )\geq 0}\quad -{\frac {1}{2}}||\sum _{{\hat {e}},e^{\prime }}\alpha ({\hat {e}},e^{\prime })\left(\mathbf {h} (f^{t},{\hat {e}})-\mathbf {h} (f^{t},e^{\prime })\right)||^{2}\quad +\quad \sum _{{\hat {e}},e^{\prime }}\alpha ({\hat {e}},e^{\prime })L({\hat {e}},e^{\prime };\mathbf {e} ^{t})\quad -\quad \sum _{{\hat {e}},e^{\prime }}\alpha ({\hat {e}},e^{\prime })\left(s^{i}(f^{t},{\hat {e}})-s^{i}(f^{t},e^{\prime })\right)$

subject to

$\sum _{{\hat {e}},e^{\prime }}\alpha ({\hat {e}},e^{\prime })\leq C$

with the weight vector update,

$\mathbf {w} ^{i+1}=\mathbf {w} ^{i}\;+\;\sum _{{\hat {e}},e^{\prime }}\alpha ({\hat {e}},e^{\prime })\left(\mathbf {h} (f^{t},{\hat {e}})-\mathbf {h} (f^{t},e^{\prime })\right)$

The dual form is solved using a QP-solver, such as a coordinate ascent algorithm, by heuristically selecting $({\hat {e}},e^{\prime })$ and by updating $\alpha (\cdot )$ iteratively:

$\alpha ({\hat {e}},e^{\prime })=max\left\{0,\;(\alpha ({\hat {e}},e^{\prime })+\delta ({\hat {e}},e^{\prime }))\right\}$

$\delta ({\hat {e}},e^{\prime })={\frac {L({\hat {e}},e^{\prime };\mathbf {e} ^{t})-\left(s^{i}(f^{t},{\hat {e}})-s^{i}(f^{t},e^{\prime })\right)}{||\mathbf {h} (f^{t},{\hat {e}})-\mathbf {h} (f^{t},e^{\prime })||^{2}}}$

$C$ is used to clip the amount of updates.

Related Papers

[1] Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, Yoram Singer. Online Passive-Aggressive Algorithms. Journal of Machine Learning Research, 7(Mar):551--585, 2006.

[2] Taro Watanabe, Jun Suzuki, Hajime Tsukada, Hideki Isozaki. 2007. Online large-margin training for statistical machine translation. In Proceedings of EMNLP-CoNLL, pp 764–773.

[3] David Chiang, Yuval Marton and Philip Resnik. 2008. Online Large-Margin Training of Syntactic and Structural Translation Features. In Proceedings of EMNLP-2008.