Learning Boolean halfspaces with small weights from membership queries

DOI10.1007/978-3-319-11662-4_8zbMATH Open1353.68148arXiv1405.1535OpenAlexW1899968485MaRDI QIDQ2938726FDOQ2938726

Authors: Hasan Abasi, Ali Z. Abdi, Nader H. Bshouty 

Publication date: 14 January 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of proper learning a Boolean Halfspace with integer weights $0,1,ldots,t$ from membership queries only. The best known algorithm for this problem is an adaptive algorithm that asks $n^{O(t^5)}$ membership queries where the best lower bound for the number of membership queries is $n^t$ [Learning Threshold Functions with Small Weights Using Membership Queries. COLT 1999] In this paper we close this gap and give an adaptive proper learning algorithm with two rounds that asks $n^{O(t)}$ membership queries. We also give a non-adaptive proper learning algorithm that asks $n^{O(t^3)}$ membership queries.

Full work available at URL: https://arxiv.org/abs/1405.1535

Recommendations

• Learning Boolean halfspaces with small weights from membership queries
• PAC learning intersections of halfspaces with membership queries
• Learning intersections and thresholds of halfspaces
• scientific article; zbMATH DE number 1301786
• Learning of bounded-weight Boolean functions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational learning theory (68Q32)

Cited In (2)

• Exact learning from an honest teacher that answers membership queries
• Low-weight halfspaces for sparse boolean vectors

This page was built for publication: Learning Boolean halfspaces with small weights from membership queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938726)