The Application of the Inclusion-Exclusion Principle in Learning Monotonic Boolean Functions
Thomas Quint, Christopher Gaffney · SSRN Electronic Journal · 2012
In this paper, we consider the inference problem for monotone Boolean structure functions (for example, Torvik and Triantaphyllou, 2002 and 2005; or Judson et al., 2005). We follow Judson’s algorithm (in Judson, 1999; or Judson et al., 2005), except with two possible changes. First, when choosing a vector to test, we consider simply evaluating the “value” of a given number of random vectors (instead of using Judson’s “neighbor” algorithm to find test vectors). Second, we consider a new way of calculating the value of a vector, which makes use of the inclusionexclusion principle from combinatorics. Via testing on some 10-component systems, we find that the “random” approach is better than the “neighbor” approach, and that the inclusionexclusion method is an improvement whenever the size of the boundary of the “unknown vector set” is small.