Monotone Classification with Relative Approximations

Abstract

In monotone classification, the input is a multi-set P of points in R^d, each associated with a hidden label from \-1, 1\. The goal is to identify a monotone function h, which acts as a classifier, mapping from R^d to \-1, 1\ with a small error, measured as the number of points p P whose labels differ from the function values h(p). The cost of an algorithm is defined as the number of points having their labels revealed. This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most (1 + ) k^* where 0 and k^* is the minimum error achieved by an optimal monotone classifier -- in other words, the error is allowed to exceed the optimal by at most a relative factor. Nearly matching upper and lower bounds are presented for the full range of . All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.

Tasks

Reproductions