  We introduce the hierarchical compositional network (HCN), a directed
generative model able to discover and disentangle, without supervision, the
building blocks of a set of binary images. The building blocks are binary
features defined hierarchically as a composition of some of the features in the
layer immediately below, arranged in a particular manner. At a high level, HCN
is similar to a sigmoid belief network with pooling. Inference and learning in
HCN are very challenging and existing variational approximations do not work
satisfactorily. A main contribution of this work is to show that both can be
addressed using max-product message passing (MPMP) with a particular schedule
(no EM required). Also, using MPMP as an inference engine for HCN makes new
tasks simple: adding supervision information, classifying images, or performing
inpainting all correspond to clamping some variables of the model to their
known values and running MPMP on the rest. When used for classification, fast
inference with HCN has exactly the same functional form as a convolutional
neural network (CNN) with linear activations and binary weights. However, HCN's
features are qualitatively very different.
