Convexity and logical analysis of data

Citation
O. Ekin et al., Convexity and logical analysis of data, THEOR COMP, 244(1-2), 2000, pp. 95-116
Citations number
15
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
244
Issue
1-2
Year of publication
2000
Pages
95 - 116
Database
ISI
SICI code
0304-3975(20000806)244:1-2<95:CALAOD>2.0.ZU;2-U
Abstract
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.