Computing minimal sets of descriptive conditions for binary data

Suppose we are given a set of binary attributes. Each attribute is described by a finite set of objects to which the attribute applies. We consider the following problem. Is it possible to find a small set of conditions, or factors, associated to the attributes in such a way that an attribute applies to an object if and only if the object satisfies all conditions associated to the attribute? In this sense, we look for minimal sets of descriptive conditions for a set of binary attributes. We show that this problem can equivalently be expressed by so-called triangular decompositions of binary matrices. Small sets of descriptive conditions correspond to decompositions with small inner dimension. The conditions, or factors, used in these decompositions correspond to I-beam-shaped patterns in binary matrices. We utilize results on triangular decompositions and provide an efficient approximation algorithm for computing optimal decompositions. We present an example demonstrating usefulness of discovering descriptive conditions and evaluate performance of the algorithm.