Selective Labeling in Learning with Expert Advice

An online active learning mechanism using the expert advice framework is considered where the goal is to learn the correct labels of a sequence of revealed items. The learning scheme's efficiency is measured in terms of the regret bound and reduced data labeling queries based on experts' predictions. Two efficient randomized algorithms EPSL and EPAL are proposed in which the opinion ranges of experts are examined in order to decide whether to acquire a label from users for a given instance. It is shown that both algorithms obtain nearly optimal regret bounds and up to a constant factor depending on the characteristics of experts' predictions. While EPSL yields a better regret bound than EPAL, it requires extra prior knowledge of experts' predictions. Relaxing this assumption, EPAL provides a more practical scheme by implying an adaptive time-varying learning rate whose regret is at worst \sqrt{2} times of that for EPSL. Experimental results justify the outperformance of the proposed algorithms compared to the existing ones in this setting.