טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAbasi Hassan
SubjectExact Learning of Monotone Functions from Membership
Queries
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty


Abstract

In this thesis, we study many problems of learning monotone classes using membership queries model. In membership queries the learner is allowed to choose any input, and receives its output. We study mainly three classes: Hyper-graphs, Graphs and Boolean Half-space classes. In Hyper-graphs (graph) H=(V, E), the membership query is called hyperedge-detecting query QH(S) in a way that given S sub-set  V, QH(S) is answered true if and only if S contains at least one edge of H.  We study the Hyper-graph class where the number of edges is s, each of which is of size at most r. We first present new lower bounds for this problem and then present deterministic and randomized adaptive algorithms with hyperedge-detecting query complexity that is almost optimal. All the adaptive algorithms that we present run in time linear in hyperedge-detecting query complexity and the number of vertices. Then, we study the Non-adaptive learning of Hyper-graphs, and we give the first polynomial time non-adaptive learning algorithm for learning a Hyper-graph that asks an almost optimal number of queries. In addition, we study the problem where alpha-fraction of hypergraph-detecting queries return incorrect answers, and we give a polynomial time non-adaptive learning algorithm for a hyper-graph problem with at most alpha-fraction incorrect queries. In addition, we study the graph class and give many results in both adaptive and non-adaptive models. Graph class G=(V, E) where the number of vertices and edges is n=|V| and m=|E| respectively. The information-theoretic lower bound gives mlogn for the number of queries. Angluin and Chen algorithm runs in 4 rounds and detects O(mlogn) queries, and in another hard case where the number of edges m is unknown, their algorithm runs in 5 rounds and asks O(mlogn   m1/2log2n) queries. We present a 3-round algorithm that asks in O(mlogn) queries and an O(1)-round algorithms that asks O(mlogn 1/2log[k] nlog n) queries for any constant k, where log[k]n=log?log n (k times). Finally, we study Half-space classes. 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 nO(t^5) membership queries where the best lower bound for the number of membership queries is nt. One of our main results is closing 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.