  This paper describes serial and parallel compositional models of multiple
objects with part sharing. Objects are built by part-subpart compositions and
expressed in terms of a hierarchical dictionary of object parts. These parts
are represented on lattices of decreasing sizes which yield an executive
summary description. We describe inference and learning algorithms for these
models. We analyze the complexity of this model in terms of computation time
(for serial computers) and numbers of nodes (e.g., "neurons") for parallel
computers. In particular, we compute the complexity gains by part sharing and
its dependence on how the dictionary scales with the level of the hierarchy. We
explore three regimes of scaling behavior where the dictionary size (i)
increases exponentially with the level, (ii) is determined by an unsupervised
compositional learning algorithm applied to real data, (iii) decreases
exponentially with scale. This analysis shows that in some regimes the use of
shared parts enables algorithms which can perform inference in time linear in
the number of levels for an exponential number of objects. In other regimes
part sharing has little advantage for serial computers but can give linear
processing on parallel computers.
