Complexity of Representation and Inference in Compositional Models with Part Sharing
This work addresses efficiency challenges in hierarchical object recognition for computer vision and AI, though it is incremental in analyzing specific scaling behaviors.
The paper analyzes the computational complexity of inference in compositional models with part sharing, showing that in certain scaling regimes, shared parts enable linear-time inference for an exponential number of objects, while in others, benefits are limited to parallel processing.
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.