We consider the problem of proper learning a Boolean Half-space 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. In this paper we close this gap and give an adaptive proper learning algorithm with two rounds that asks n~(O(t5)) membership queries. We also give a non-adaptive proper learning algorithm that asks n~(O(t~3)) membership queries.
展开▼
