Analysis of Perceptron-Based Active Learning
We start by showing that in an active learning setting, the Perceptron algorithm needs $\Omega(\frac{1}{\epsilon^2})$ labels to learn linear separators within generalization error $\epsilon$. We then present a simple selective sampling algorithm for this problem, which combines a modification of th...
| Main Authors: | , , |
|---|---|
| Language: | en_US |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/30585 |
| _version_ | 1826209738322345984 |
|---|---|
| author | Dasgupta, Sanjoy Kalai, Adam Tauman Monteleoni, Claire |
| author_facet | Dasgupta, Sanjoy Kalai, Adam Tauman Monteleoni, Claire |
| author_sort | Dasgupta, Sanjoy |
| collection | MIT |
| description | We start by showing that in an active learning setting, the Perceptron algorithm needs $\Omega(\frac{1}{\epsilon^2})$ labels to learn linear separators within generalization error $\epsilon$. We then present a simple selective sampling algorithm for this problem, which combines a modification of the perceptron update with an adaptive filtering rule for deciding which points to query. For data distributed uniformly over the unit sphere, we show that our algorithm reaches generalization error $\epsilon$ after asking for just $\tilde{O}(d \log \frac{1}{\epsilon})$ labels. This exponential improvement over the usual sample complexity of supervised learning has previously been demonstrated only for the computationally more complex query-by-committee algorithm. |
| first_indexed | 2024-09-23T14:28:16Z |
| id | mit-1721.1/30585 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:28:16Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305852019-04-12T08:37:52Z Analysis of Perceptron-Based Active Learning Dasgupta, Sanjoy Kalai, Adam Tauman Monteleoni, Claire AI active learning perceptron label-complexity mistake bound selective sampling We start by showing that in an active learning setting, the Perceptron algorithm needs $\Omega(\frac{1}{\epsilon^2})$ labels to learn linear separators within generalization error $\epsilon$. We then present a simple selective sampling algorithm for this problem, which combines a modification of the perceptron update with an adaptive filtering rule for deciding which points to query. For data distributed uniformly over the unit sphere, we show that our algorithm reaches generalization error $\epsilon$ after asking for just $\tilde{O}(d \log \frac{1}{\epsilon})$ labels. This exponential improvement over the usual sample complexity of supervised learning has previously been demonstrated only for the computationally more complex query-by-committee algorithm. 2005-12-22T02:40:49Z 2005-12-22T02:40:49Z 2005-11-17 MIT-CSAIL-TR-2005-075 AIM-2005-033 http://hdl.handle.net/1721.1/30585 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 15 p. 11491832 bytes 599624 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | AI active learning perceptron label-complexity mistake bound selective sampling Dasgupta, Sanjoy Kalai, Adam Tauman Monteleoni, Claire Analysis of Perceptron-Based Active Learning |
| title | Analysis of Perceptron-Based Active Learning |
| title_full | Analysis of Perceptron-Based Active Learning |
| title_fullStr | Analysis of Perceptron-Based Active Learning |
| title_full_unstemmed | Analysis of Perceptron-Based Active Learning |
| title_short | Analysis of Perceptron-Based Active Learning |
| title_sort | analysis of perceptron based active learning |
| topic | AI active learning perceptron label-complexity mistake bound selective sampling |
| url | http://hdl.handle.net/1721.1/30585 |
| work_keys_str_mv | AT dasguptasanjoy analysisofperceptronbasedactivelearning AT kalaiadamtauman analysisofperceptronbasedactivelearning AT monteleoniclaire analysisofperceptronbasedactivelearning |