{"id":327395,"date":"2016-11-27T12:12:47","date_gmt":"2016-11-27T20:12:47","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/?post_type=msr-research-item&p=327395"},"modified":"2018-10-16T21:26:59","modified_gmt":"2018-10-17T04:26:59","slug":"analysis-perceptron-based-active-learning","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/analysis-perceptron-based-active-learning\/","title":{"rendered":"Analysis of Perceptron-Based Active Learning"},"content":{"rendered":"

We start by showing that in an active learning setting, the Perceptron algorithm needs Ω<\/mi>(<\/mo>1<\/mn>ϵ<\/mi>2<\/mn><\/mrow><\/msup><\/mfrac>)<\/mo><\/math>\">\u03a9<\/span>(<\/span>1<\/span>\u03f5<\/span>2<\/span><\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span>labels to learn linear separators within generalization error \u03b5<\/em>. 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 \u03b5<\/em> after asking for just O<\/mi>~<\/mo><\/mover><\/mrow><\/mrow>(<\/mo>d<\/mi>l<\/mi>o<\/mi>g<\/mi>1<\/mn>ϵ<\/mi><\/mfrac>)<\/mo><\/math>\">O<\/span>~<\/span><\/span><\/span><\/span><\/span><\/span>(<\/span>d<\/span>l<\/span>o<\/span>g<\/span>1<\/span>\u03f5<\/span><\/span>)<\/span><\/span><\/span><\/span><\/span><\/span> 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

We start by showing that in an active learning setting, the Perceptron algorithm needs \u03a9(1\u03f52)labels to learn linear separators within generalization error \u03b5. 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 […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"Springer Berlin Heidelberg","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005","msr_editors":"","msr_how_published":"","msr_isbn":"978-3-540-26556-6 (Print) 978-3-540-31892-7 (Online)","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"249-263","msr_page_range_start":"249","msr_page_range_end":"263","msr_series":"","msr_volume":"3559","msr_copyright":"","msr_conference_name":"18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005","msr_doi":"10.1007\/11503415_17","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2005-06-27","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561,13556],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-327395","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-artificial-intelligence","msr-locale-en_us"],"msr_publishername":"Springer Berlin Heidelberg","msr_edition":"18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005","msr_affiliation":"","msr_published_date":"2005-06-27","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"249-263","msr_chapter":"","msr_isbn":"978-3-540-26556-6 (Print) 978-3-540-31892-7 (Online)","msr_journal":"","msr_volume":"3559","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"327398","msr_publicationurl":"","msr_doi":"10.1007\/11503415_17","msr_publication_uploader":[{"type":"file","title":"2005-analysis_of_perceptron-based_active_learning","viewUrl":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2016\/11\/2005-Analysis_of_Perceptron-based_Active_Learning.pdf","id":327398,"label_id":0},{"type":"doi","title":"10.1007\/11503415_17","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Sanjoy Dasgupta","user_id":0,"rest_url":false},{"type":"user_nicename","value":"adum","user_id":30834,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=adum"},{"type":"text","value":"Claire Monteleoni","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199563],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/327395","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/327395\/revisions"}],"predecessor-version":[{"id":535981,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/327395\/revisions\/535981"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=327395"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=327395"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=327395"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=327395"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=327395"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=327395"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=327395"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=327395"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=327395"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=327395"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=327395"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=327395"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=327395"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}