On the inherent competition between valid and spurious inductive inferences in Boolean data
This addresses the challenge of reliable rule extraction in complex systems like genetic networks, but it is incremental as it builds on existing methods for Boolean function synthesis.
The paper tackles the problem of distinguishing valid from spurious inductive inference rules in Boolean data, particularly in biological networks, by formulating greedy algorithms to synthesize Boolean functions and numerically evaluating their performance.
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.