|
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 nO(t 5) membership queries where the
best lower bound
for the number of membership queries is nt (see [AAB99]).
In this paper we close this gap and give an adaptive proper learning algorithm with
two rounds that asks nO(t)
membership queries. We also give a non-adaptive proper learning algorithm that asks
nO(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. 318-322 (1999)
©Copyright Springer 2014
|