Title: On the inherent competition between valid and spurious inductive inferences in Boolean data,
Abstract: Inductive inference is the process of extracting general rules from specific
observations. This problem also arises in the analysis of biological networks,
such as genetic regulatory networks, where the interactions are complex and the
observations are incomplete. A typical task in these problems is to extract
general interaction rules as combinations of Boolean covariates, that explain a
measured response variable. The inductive inference process can be considered
as an incompletely specified Boolean function synthesis problem. This
incompleteness of the problem will also generate spurious inferences, which are
a serious threat to valid inductive inference rules. Using random Boolean data
as a null model, here we attempt to measure the competition between valid and
spurious inductive inference rules from a given data set. We formulate two
greedy search algorithms, which synthesize a given Boolean response variable in
a sparse disjunct normal form, and respectively a sparse generalized algebraic
normal form of the variables from the observation data, and we evaluate
numerically their performance.