Name
Abstract | ||
|---|---|---|
A Boolean function is called k -convex if for any pair x,y of its true points 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 question 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 algorithms 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 extensions 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 doubly exponential. On the other hand, we also show that for large k the class of k -convex Boolean functions is PAC-learnable. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0304-3975(98)00337-5 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Boolean function,Orthogonal disjunctive normal forms,convex Boolean function,Hamming distance,false point,convex Boolean extension,data set,convex extension,Partially-defined Boolean functions,true point,polynomial algorithm,Polynomial algorithms,Computational learning theory,Classification,logical analysis,Logical Analysis | Journal | 244 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 7 |
PageRank | References | Authors |
0.92 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oya Ekin | 1 | 69 | 5.34 |
| Peter L. Hammer | 2 | 1996 | 288.93 |
| A. Kogan | 3 | 142 | 12.92 |