期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2020
卷号：20
期号：8
页码：164-168
出版社：International Journal of Computer Science and Network Security
摘要：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.
关键词：Constraints; Learning; Acquisition; Decision Making
