Boolean analysis of incomplete examples

Abstract

As a form of knowledge acquisition from data, we consider the problem of deciding whether there exists an extension of a partially defined Boolean function with missing data $(\tilde T,\tilde F)$, where $\tilde T$ (resp., $\tilde F$) is a set of positive (resp., negative) examples. Here, “*” denotes a missing bit in the data, and it is assumed that $\tilde T \subseteq$ {0,1,*}ⁿ and $\tilde F \subseteq$ {0,1,*}ⁿ hold. A Boolean function f: {0,1}ⁿ → {0,1} is an extension of $(\tilde T,\tilde F)$ if it is true (resp., false) for the Boolean vectors corresponding to positive (resp., negative) examples; more precisely, we define three types of extensions called consistent, robust and most robust, depending upon how to deal with missing bits. We then provide polynomial time algorithms or prove their NP-hardness for the problems under various restrictions.

This research was partially supported by ONR (Grants N00014-92-J-1375 and N00014-92-J-4083), and the Scientific Grants in Aid by the Ministry of Education, Science and Culture of Japan. The visit of the first author to Kyoto University was made possible by Grant 06044112 of the Ministry of Education, Science and Culture of Japan. The third author is supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists.