Almost all monotone Boolean functions are polynomially learnable using membership queries

摘要

We consider exact learning or identification of monotone Boolean functions by only using membership queries. It is shown that almost all monotone Boolean functions are polynomially identifiable in the input number of variables as well as the output being the sum of the sizes of the CNF and DNF representations.