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/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 matching demonstrate the effectiveness of
the proposed method.
Description
[2007.01012] Consistent Structured Prediction with Max-Min Margin Markov Networks
%0 Generic
%1 nowakvila2020consistent
%A Nowak-Vila, Alex
%A Bach, Francis
%A Rudi, Alessandro
%D 2020
%K 2020 deep-learning markov network
%T Consistent Structured Prediction with Max-Min Margin Markov Networks
%U http://arxiv.org/abs/2007.01012
%X 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/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 matching demonstrate the effectiveness of
the proposed method.
@misc{nowakvila2020consistent,
abstract = {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 matching demonstrate the effectiveness of
the proposed method.},
added-at = {2020-07-04T20:30:04.000+0200},
author = {Nowak-Vila, Alex and Bach, Francis and Rudi, Alessandro},
biburl = {https://www.bibsonomy.org/bibtex/2040c8687e39b54ab2096f107f0a609d9/analyst},
description = {[2007.01012] Consistent Structured Prediction with Max-Min Margin Markov Networks},
interhash = {1b497eed717d789406e4657617768d5e},
intrahash = {040c8687e39b54ab2096f107f0a609d9},
keywords = {2020 deep-learning markov network},
note = {cite arxiv:2007.01012},
timestamp = {2020-07-04T20:30:04.000+0200},
title = {Consistent Structured Prediction with Max-Min Margin Markov Networks},
url = {http://arxiv.org/abs/2007.01012},
year = 2020
}