The true sample complexity of active learning
作者:Maria-Florina Balcan, Steve Hanneke, Jennifer Wortman Vaughan
摘要
We describe and explore a new perspective on the sample complexity of active learning. In many situations where it was generally believed that active learning does not help, we show that active learning does help in the limit, often with exponential improvements in sample complexity. This contrasts with the traditional analysis of active learning problems such as non-homogeneous linear separators or depth-limited decision trees, in which Ω(1/ε) lower bounds are common. Such lower bounds should be interpreted carefully; indeed, we prove that it is always possible to learn an ε-good classifier with a number of samples asymptotically smaller than this. These new insights arise from a subtle variation on the traditional definition of sample complexity, not previously recognized in the active learning literature.
论文关键词:Active learning, Sample complexity, Selective sampling, Sequential design, Learning theory, Classification
论文评审过程:
论文官网地址:https://doi.org/10.1007/s10994-010-5174-y