The application of the inclusion-exclusion principle in learning Monotone Boolean functions
Christopher Gaffney · 2008
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 inclusion-exclusion 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 inclusion-exclusion method is an improvement whenever the size of the boundary of the “unknown vector set” is small.