Authors: Hasan Abasi, Ali Z. Abdi, and
Nader H. Bshouty
Source: Algorithmic Learning Theory, 25th International Conference, ALT 2014,
Bled, Slovenia, October 8  10, 2014, Proccedings,
Lecture Notes in Artificial Intelligence 8776, pp. 96–110, Springer, 2014.
Abstract.
We consider the problem of proper learning a Boolean Halfspace with
integer weights {0,1,…,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} (see [AAB99]).
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 nonadaptive proper learning algorithm that asks
n^{O(t 3)} membership queries.
[AAB99]:
Abboud, E., Agha, N., Bshouty, N.H., Radwan, N., Saleh, F.:
Learning Threshold Functions with Small Weights Using Membership Queries.
In: COLT 1999. pp. 318322 (1999)
©Copyright Springer 2014
