Learning Boolean halfspaces with small weights from membership queries

DOI10.1007/978-3-319-11662-4_8MaRDI QIDQ2938726zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(3)

• Exact learning from an honest teacher that answers membership queries
• Learning Boolean halfspaces with small weights from 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)