Support vector machine classifiers for sequential decision problems

Classification problems in critical applications such as health care or security often require very high reliability because of the high costs of errors. In order to achieve this reliability, such systems often require the use of sequential inspections, where additional data can be collected to resolve ambiguous test cases. It is impractical or costly to collect this additional data on every sample, so one must find identify a policy that selects which samples need further examination. In this paper, we present a theory for designing support vector machine classifiers that include the option to delay decision and collect further information. We present a convex programming formulation for training such classifiers, and define a fast coordinate ascent algorithm to solve the dual of this optimization problem. The performance of the resulting classifiers is evaluated on a test suite involving detection of malignancies in hyperspectral measurements of colon polyps collected during colonoscopies.