Convexity and logical analysis of data

A Boolean function is called k-convex if for any pair x,y of its true point s at Hamming distance at most k, every point "between" x and y is also true . Given a set of true points and a set of false points, the central questio n of Logical Analysis of Data is the study of those Boolean functions whose values agree with those of the given points. In this paper we examine data sets which admit k-convex Boolean extensions. We provide polynomial algori thms for finding a k-convex extension, if any, and for finding the maximum k for which a k-convex extension exists. We study the problem of uniqueness , and provide a polynomial algorithm for checking whether all k-convex exte nsions agree in a point outside the given data set. We estimate the number of k-convex Boolean functions, and show that for small k this number is dou bly exponential. On the other hand, we also show that for large k the class of k-convex Boolean functions is PAC-learnable. (C) 2000 Elsevier Science B.V. All rights reserved.