Learning in Compositional Hierarchies: Inducing the Structure of Objects from Data

Joachim UtansNeurIPS 1993

Published in the early 1990s, this foundational paper represents a significant effort to transition away from hand-coded computer vision models. Instead, it proposes a system capable of "discovering" the internal, hierarchical structure of objects entirely on its own from raw data.

The Challenge of Structural Induction

In the early days of model-based object recognition, researchers understood that representing objects as hierarchies was incredibly powerful. For example, modeling a "Human" as being made of "Arms," which are in turn made of "Lower Arms" and "Hands," allows a system to better handle rotation, scale, and visual distortion. However, these hierarchical structures were almost exclusively designed by hand.

Hierarchical decomposition of a human figure into parts like arms and lower arms.

The core challenge addressed by Joachim Utans in this work is structural induction: How can a machine observe multiple examples of an object and autonomously deduce that certain parts belong together in a sub-group? This task is notoriously difficult because intermediate sub-groups (like a "sub-cluster" of dots or a specific limb segment) are "hidden"—they are not explicitly labeled in the training data.

Methodology: Objects as Bayesian Belief Networks

To solve this, the author treats the object hierarchy as a Compositional Hierarchy modeled via a Bayesian Belief Network. The algorithm relies on several key technical components to induce structure:

  • Conditional Independence: The foundational assumption is that if two parts (e.g., two fingers) are grouped under a single parent node (a hand), their spatial positions should become independent once the position of the parent hand is known.
  • Star-Decomposability: To determine if parts should be grouped together, the algorithm utilizes a mathematical condition known as star-decomposability (Pearl, 1988). For three variables to share a common hidden parent, their pairwise correlation coefficients must satisfy a specific "triangle inequality."
  • Soft Grouping & EM Algorithm: Rather than making immediate, rigid "yes/no" decisions about grouping parts, the algorithm employs "soft" grouping variables. It uses an Expectation-Maximization (EM) approach to iteratively guess the structure, estimate parameters (like the mean and variance of positions), and then refine the structure based on those statistical estimates.
  • Objective Function: The system optimizes a cost function that actively penalizes grouping parts under a common parent if they fail to satisfy the statistical requirements of independence.

Datasets and Key Insights

The paper evaluates the algorithm using a synthetic "dot cluster" dataset. This dataset features a three-level hierarchy where a global cluster contains three sub-clusters, each containing three individual dots (9 dots total). Data was generated by taking a prototype and adding independent Gaussian noise to the coordinates at each hierarchical level. This toy problem allowed the author to rigorously verify if the algorithm could recover a known "ground truth" structure from noisy observations.

Several profound insights emerged from this approach:

  • Structure from Correlation: The geometric structure of an object is inherently encoded in the statistical correlation of its parts. If two parts consistently move together across different samples, they likely share a common structural "cause."
  • Decoupling via Context: By assigning parts to a local sub-structure, the model effectively "decouples" them from the rest of the object. This makes the model highly robust to local deformations; for instance, an arm moving does not change the local relationship between the fingers and the hand.
  • Avoiding Overfitting: Hierarchical grouping naturally combats overfitting. While a dataset might contain few examples of a specific "whole object" in a certain pose, there are many more examples of its constituent "parts" and "sub-structures" available to the model as it aggregates data up the tree.

Results and Future Directions

In the dot-cluster simulations, the algorithm successfully recovered the original three-level hierarchy that generated the data, correctly identifying which dots belonged to which sub-clusters. However, the author noted a mathematical ambiguity: while the structure was recovered, the exact coordinate values of the hidden intermediate nodes couldn't be uniquely identified, as shifting a parent's position can be perfectly offset by shifting its children.

Hierarchical decomposition of a handwritten digit '9' into distinct strokes.

The paper concludes by outlining limitations and avenues for future work. The current model is unsupervised—it learns to represent an object well, but not necessarily the features that best distinguish one object from another. Furthermore, the initial model assumes all parts are present in every image, requiring future extensions to handle occlusions. Finally, while the concept was proven on simple coordinates, scaling to complex real-world data—like the hierarchical strokes of handwritten digits or facial features—requires further research into parameterizing complex shapes.

Summary updated

BibTeX
@inproceedings{utans1993learning,
  author = {Joachim Utans},
  title = {{Learning in Compositional Hierarchies: Inducing the Structure of Objects from Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
}
Figure