论文标题
一致的结构化预测与最大边距马尔可夫网络
Consistent Structured Prediction with Max-Min Margin Markov Networks
论文作者
论文摘要
二进制分类（例如支持向量机（SVM））的Max-Margin方法已扩展到以Max-Margin Markov网络的名称（$ M^3n $）或更一般的结构SVMS的名称扩展到结构化预测设置。不幸的是，当输入和标签之间的关系远非确定性时，这些方法在统计学上是不一致的。我们通过根据“最大值”保证金公式定义学习问题来克服此类限制，并命名了最大的方法Max-Min Margin Markov Networks（$ M^4n $）。我们证明了$ m^4n $的一致性和有限的样本概括范围，并提供了一种明确的算法来计算估算器。该算法以$ O（1/\ sqrt {n}）$的概括错误为$ O（n）$（n）$投影式呼叫（最大的成本与$ m^3n $的最大成本相同）。关于多类分类，顺序回归，序列预测和排名的实验证明了该方法的有效性。
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.
