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.

本文描述了串行和并行组合模型的多个对象，这些对象具有部分共享。 对象由部分子部件组成，并用对象部件的分层字典来表示。 我们描述了这些模型的推理和学习算法。 我们分析了这种模型的计算时间复杂度（对于串行计算机）和节点数（例如，“神经元”）（对于并行计算机）。 特别地，我们计算了由于部分共享而获得的复杂度收益及其取决于字典如何随分层级别与比例变化。 我们研究了三种不同的字典比例行为对算法的影响，并得出结论，表明在某些行为区间内，使用共享部分使算法能够在指数级别的对象中实现线性时间推理。 在其他行为区间中，与串行计算机相比，部分共享的优势不大，但可以在并行计算机上实现线性处理。

组合模型中表示和推理的复杂度与部分共享