Transductive structured classification through constrained min-cuts
Abstract
We extend the Blum and Chawla
(2001) graph min-cut algorithm to
structured problems. This extension
can alternatively be viewed as a joint
inference method over a set of training and test instances where parts of
the instances interact through a pre-specified associative network.
The
method has has an efficient approximation through a linear-programming relaxation. On small training data sets,
the method achieves up to 34.8% relative error reduction.
(2001) graph min-cut algorithm to
structured problems. This extension
can alternatively be viewed as a joint
inference method over a set of training and test instances where parts of
the instances interact through a pre-specified associative network.
The
method has has an efficient approximation through a linear-programming relaxation. On small training data sets,
the method achieves up to 34.8% relative error reduction.
