Convexity and logical analysis of data.(English)Zbl 0945.68082

Summary: 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.

MSC:

 68Q32 Computational learning theory
Full Text:

References:

 [1] Anthony, M.; Biggs, N., Computational learning theory, (1992), Cambridge University Press Cambridge · Zbl 0755.68115 [2] Ball, M.O.; Nemhauser, G.L., Matroids and a reliability analysis problem, Math. oper. res., 4, 132-143, (1979) · Zbl 0407.90034 [3] A. Beimel, F. Bergadano, N.H. Bshouty, E. Kushilevitz, S. Varricchio, On the applications of multiplicity automata in learning, in: Proc. 37th Annual IEEE Symp. on Foundations of Computer Science (FOCS’1996), pp. 349-358. [4] A. Blake, Canonical expressions in Boolean algebra, Ph.D. Thesis, University of Chicago, August 1937. · Zbl 0018.38601 [5] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M.K., Learnability and the vapnik – chervonenkis dimension, J. assoc. comput. machinery, 36, 4, 929-965, (1989) · Zbl 0697.68079 [6] E. Boros, P.L. Hammer, T. Ibaraki, A. Kogan, E. Mayoraz, I. Muchnik, An implementation of logical analysis of data, IEEE Transactions on Knowledge and Data Engineering, accepted for publication. [7] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-509, (1952) · Zbl 0048.11804 [8] Colbourn, C.J., The combinatorics of network reliability, (1987), Oxford University Press New York [9] Crama, Y.; Hammer, P.L.; Ibaraki, T., Cause-effect relationships and partially defined Boolean functions, Ann. oper. res., 16, 299-326, (1988) · Zbl 0709.03533 [10] Ehrenfeucht, A.; Haussler, D.; Kearns, M.; Valiant, L., A general lower bound on the number of examples needed for learning, Inform. comput., 82, 3, 247-261, (1989) · Zbl 0679.68158 [11] O. Ekin, P.L. Hammer, A. Kogan, On connected Boolean functions, Discrete Appl. Math., accepted for publication. · Zbl 0937.06014 [12] Hammer, P.L.; Rudeanu, S., Boolean methods in operations research, (1968), Springer Berlin · Zbl 0155.28001 [13] Kearns, M.J.; Vazirani, U.V., An introduction to computational learning theory, (1994), MIT Press Cambridge, MA [14] Quine, W., A way to simplify truth functions, Amer. math. monthly, 62, 627-631, (1955) · Zbl 0068.24209 [15] Ramamurthy, K.G., Coherent structures and simple games, (1990), Kluwer Academic Publishers Dordrecht · Zbl 0738.90093
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.