Elamur Research⌕
☰
home / papers / 2019 / Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds

Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds

Paper · 2019 · Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy et al.

Summary

The paper addresses batch active learning for deep neural networks. The task is to select a whole group of unlabeled examples for labeling at once while spending as little annotator effort as possible. Methods that consider only model uncertainty often fill a batch with nearly identical examples. Methods that seek only diversity may select points that give the model little benefit. Moreover, the success of both approaches depends on the architecture, the batch size, and the data.

The authors propose the BADGE method. Each example is represented as the gradient of the loss function with respect to the output-layer weights, computed for the label the model considers most likely. The length of this vector shows how uncertain the model is, and its direction shows what the model update would be. The batch is formed using k-MEANS++ initialization. This favors long vectors and vectors far from one another at the same time, and it needs no hyperparameters to balance these criteria. Experiments with MLP and ResNet on SVHN, CIFAR10, MNIST, and OpenML datasets show that BADGE consistently performs no worse than the best baseline, and often better. This matters because in active learning, hyperparameter tuning itself costs additional labels.

Key points

  • Theoretical basis (Proposition 1): if the network output is a softmax, the gradient norm for the predicted label is a lower bound on the gradient norm for any other label. Therefore, the vector length serves as a measure of uncertainty.
  • k-MEANS++ is used as a cheap substitute for k-DPP. The accuracy of the two selection methods is nearly the same, but k-DPP (MCMC sampling following Kang, 2013) is much slower for batches of size 1000. For batches of size 10,000, it did not fit in memory at all.
  • Experimental settings: batch sizes 100, 1000, and 10,000; MLP and ResNet architectures; datasets OpenML #6, #155, #156, #184, SVHN, MNIST, CIFAR10. Each learning curve is the average of five independent runs.
  • Batch diversity analysis: CONF has the largest average gradient norm. However, it sometimes selects linearly dependent examples: the log-determinant of the Gram matrix for such a batch equals −∞. These cases coincide with drops in accuracy. k-DPP and FF-k-CENTER form less diverse batches than BADGE.
  • The paper was published at ICLR 2020 (arXiv:1906.03671). The authors include researchers from Princeton, University of Arizona, and Microsoft Research.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 works

Cite

Cite as Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford and Alekh Agarwal. 2019. Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds. arXiv:1906.03671 · 2020 International Conference on Learning Representations.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1906.03671 · arXiv 1906.03671

@misc{ash2019deep,
  title = {{Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds}},
  author = {Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford and Alekh Agarwal},
  year = {2019},
  doi = {10.48550/arxiv.1906.03671},
  eprint = {1906.03671},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1906.03671}
}

References

51 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 1994. find
  2. Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In International Conference on Machine Learning, 2006. find
  3. Alina Beygelzimer, Daniel J Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. In Neural Information Processing Systems, 2010. find
  4. Nicolo Cesa-Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In International Conference on Machine Learning, 2009. find
  5. David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In ACM-SIAM symposium on Discrete algorithms, 2007. find
  6. Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In International Conference on Machine Learning, 2011. find
  7. Michał Dereziński and Manfred K Warmuth. Reverse iterative volume sampling for linear regression. The Journal of Machine Learning Research, 19(1), 2018. find
  8. Byungkon Kang. Fast determinantal point process sampling with application to clustering. In Neural Information Processing Systems, 2013. find
  9. Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. In Conference on Learning Theory, 2016. find
  10. Michał Dereziński. Fast determinantal point processes via distortion-free intermediate sampling. arXiv preprint, 2018. find
  11. Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018. find
  12. Dan Wang and Yi Shang. A new active labeling method for deep learning. In 2014 International joint conference on neural networks, 2014. find
  13. Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In European Conference on Machine Learning, 2006. find
  14. Wei-Ning Hsu and Hsuan-Tien Lin. Active learning by learning. In Association for the advancement of artificial intelligence, 2015. find
  15. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  16. Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint, 2014.
  17. Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011. find
  18. Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009. find
  19. Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. IEEE, 1998. find
  20. Jordan T Ash and Ryan P Adams. On the difficulty of warm-starting neural network training. arXiv preprint, 2019. find
  21. Yao-Yuan Yang, Shao-Chuan Lee, Yu-An Chung, Tung-En Wu, Si-An Chen, and Hsuan-Tien Lin. libact: Pool-based active learning in python. arXiv preprint, 2017. find
  22. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017. find
  23. Burr Settles. Active learning literature survey. University of Wisconsin, Madison, 2010.
  24. Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 2011. find
  25. Steve Hanneke. Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 2014. find
  26. Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprint, 2017. find
  27. Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. arXiv preprint, 2019. find
  28. Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2001. find
  29. Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. In International Conference on Machine Learning, 2000. find
  30. Gokhan Tur, Dilek Hakkani-Tür, and Robert E Schapire. Combining active and semi-supervised learning for spoken language understanding. Speech Communication, 2005. find
  31. Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, 2017. find
  32. Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach. arXiv preprint, 2018. find
  33. William H Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning in image classification. In IEEE Conference on Computer Vision and Pattern Recognition, 2018. find
  34. Yoram Baram, Ran El Yaniv, and Kobi Luz. Online choice of active learning algorithms. Journal of Machine Learning Research, 2004. find
  35. Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. In Neural Information Processing Systems, 2010. find
  36. Yuhong Guo and Dale Schuurmans. Discriminative batch mode active learning. In Neural Information Processing Systems, 2008. find
  37. Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. Transactions on Knowledge Discovery from Data, 2015. find
  38. Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In International Conference on Machine Learning. Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Lea… find
  39. Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Neural Information Processing Systems 32, 2019. find
  40. Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. In Neural Information Processing Systems, 2008. find
  41. Jiaji Huang, Rewon Child, and Vinay Rao. Active learning for speech recognition: the power of gradients. arXiv preprint, 2016. find
  42. Ye Zhang, Matthew Lease, and Byron C Wallace. Active discriminative text representation learning. In AAAI Conference on Artificial Intelligence, 2017a. find
  43. Lei Han, Kean Ming Tan, Ting Yang, and Tong Zhang. Local uncertainty sampling for large-scale multi-class logistic regression. arXiv preprint, 2016. find
  44. HaiYing Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. Journal of the American Statistical Association, 2018. find
  45. Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. In Neural Information Processing Systems, 2018. find
  46. Cheng Zhang, Hedvig Kjellstrom, and Stephan Mandt. Determinantal point processes for mini-batch diversification. Uncertainty in Artificial Intelligence, 2017b. find
  47. Haw-Shiuan Chang, Erik Learned-Miller, and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In Neural Information Processing Systems, 2017. find
  48. Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 2012. find
  49. Erdem Bıyık, Kenneth Wang, Nima Anari, and Dorsa Sadigh. Batch active learning using determinantal point processes. arXiv preprint, 2019. find
  50. Stephen Mussmann and Percy S Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Neural Information Processing Systems, 2018. find
  51. T HE k- MEANS ++ SEEDING ALGORITHM A find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ash-2019-deep-batch-active-learning-diverse/