Max-margin methods for binary classification such as the support vector
machine (SVM) have been extended to the structured prediction setting under the
name of max-margin Markov networks ($M^3N$), or more generally structural SVMs.
Unfortunately, these methods are statistically inconsistent when the
relationship between inputs and labels is far from deterministic. We overcome
such limitations by defining the learning problem in terms of a "max-min"
margin formulation, naming the resulting method max-min margin Markov networks
($M^4N$). We prove consistency and finite sample generalization bounds for
$M^4N$ and provide an explicit algorithm to compute the estimator. The
algorithm achieves a generalization error of $O(1/\sqrt{n})$ for a total cost
of $O(n)$ projection-oracle calls (which have at most the same cost as the
max-oracle from $M^3N$). Experiments on multi-class classification, ordinal
regression, sequence prediction and ranking demonstrate the effectiveness of
the proposed method.

提出了一种名为 max-min margin Markov networks（M4N）的方法，用于解决结构化预测时，输入和标签之间的关系不确定时，支持向量机等二元分类方法具有的一致性问题，并证明了其一致性和有限样本的泛化界限。