Timezone: »

 
Poster
Auditing: Active Learning with Outcome-Dependent Query Costs
Sivan Sabato · Anand D Sarwate · Nati Srebro

Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »

We propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. We study binary classification in an extreme case, where the algorithm only pays for negative labels. Our motivation are applications such as fraud detection, in which investigating an honest transaction should be avoided if possible. We term the setting auditing, and consider the auditing complexity of an algorithm: The number of negative points it labels to learn a hypothesis with low relative error. We design auditing algorithms for thresholds on the line and axis-aligned rectangles, and show that with these algorithms, the auditing complexity can be significantly lower than the active label complexity. We discuss a general approach for auditing for a general hypothesis class, and describe several interesting directions for future work.

[ PDF] 

Author Information

Sivan Sabato (Ben-Gurion University of the Negev)
Anand D Sarwate (Rutgers, The State University of New Jersey)
Nati Srebro (TTI-Chicago)

More from the Same Authors