Transductive Structured Classification through Constrained Min-Cuts
Kuzman Ganchev, Fernando M. B. Pereira · 2007
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 prespecified associative network. The method has has an ecient approximation through a linear-programming relaxation. On small training data sets, the method achieves up to 34.8% relative error reduction.