Constrained Classification on Structured Data

Abstract

Most standard learning algorithms, such as Logistic Re-gression (LR) and the Support Vector Machine (SVM), are designed to deal with i.i.d. (independent and identi-cally distributed) data. They therefore do not work ef-fectively for tasks that involve non-i.i.d. data, such as “region segmentation”. (Eg, the “tumor vs non-tumor” labels in a medical image are correlated, in that adja-cent pixels typically have the same label.) This has mo-tivated the work in random fields, which has produced classifiers for such non-i.i.d. data that are significantly better than standard i.i.d.-based classifiers. However, these random field methods are often too slow to be trained for the tasks they were designed to solve. This paper presents a novel variant, Pseudo Conditional Ran-dom Fields (PCRFs), that is also based on i.i.d. learners, to allow efficient training but also incorporates correla-tions, like random fields. We demonstrate that this sys-tem is as accurate as other random fields variants, but significantly faster to train.