Treating classification as seeking minimum cuts in the appropriate graph has proven effective in a number of applications. The power of this approach lies in its ability to incorporate label-agreement preferences among pairs of instances in a provably tractable way. Label disagreement preferences are another potentially rich source of information, but prior NLP work within the minimum-cut paradigm has not explicitly incorporated it. Here, we report on work in progress that examines several novel heuristics for incorporating such information. Our results, produced within the context of a politically-oriented sentiment-classification task, demonstrate that these heuristics allow for the addition of label-disagreement information in a way that improves classification accuracy while preserving the efficiency guarantees of the minimum-cut framework.
@inproceedings{Bansal+Cardie+Lee:08a, author = {Mohit Bansal and Claire Cardie and Lillian Lee}, title = {The power of negative thinking: Exploiting label disagreement in the min-cut classification framework}, year = {2008}, pages = {15--18}, booktitle = {Proceedings of COLING: Companion volume: Posters} }