Efficient active and semi-supervised algorithms for Two-sided Disjunctions

Series: 
ACO Student Seminar
Friday, November 2, 2012 - 13:00
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
College of Computing, Georgia Tech
We present a new algorithm learning the class of two-sided disjunctions in semi-supervised PAC setting and in the active learning model. These algorithms are efficient and have good sample complexity. By exploiting the power of active learning we are able to find consistent, compatible hypotheses -- a task which is computationally intractable in the semi-supervised setting.