Abstract
In this work, we analyze the generalization error for learning a constrained problem, also known as a constraint acquisition problem. We consider the problem of learning constraints over finite and discrete domains (of variables) analyze the generalization error of the well-known version space learning algorithm. We show that a consistent learner would errs at most m(m-1)/2 times for a discrete network with variables having m domain values. Furthermore, we empirically demonstrate the feasibility of building version space learner which outputs a consistent hypothesis of small size even in large constraint networks. This holds true even if the examples were noisy/inconsistent with the given hypothesis.