Learning boolean halfspaces with small weights from membership queries

详细信息    查看全文

• 作者：Hasan Abasi^a ; ^{hassan@cs.technion.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Ali Z. Abdi^b ; ^{aliabdi16@hotmail.com" class="auth_mail" title="E-mail the corresponding author} ; Nader H. Bshouty^a ; ^{bshouty@cs.technion.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Membership query ; Proper learning ; Boolean halfspaces ; Automata ; Adaptive algorithm
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：18 October 2016
• 年：2016
• 卷：650
• 期：Complete
• 页码：45-56
• 全文大小：382 K

文摘

We consider the problem of proper learning of a boolean halfspace with integer weights {0,1,…,t}$\{0,1,\dots ,t\}$, from membership queries only. The best known algorithm for this problem is an adaptive algorithm that asks n^O(t5)$n^{O(t^5)}$ membership queries, while the best lower bound for the number of membership queries is n^Ω(t)$n^{\mathrm{\Omega }(t)}$[1].

In this paper we close this gap and give an adaptive proper learning algorithm with two rounds, and asking n^O(t)$n^{O(t)}$ membership queries. We also give a non-adaptive proper learning algorithm that asks n^O(t3)$n^{O(t^3)}$ membership queries.