Measuring similarity is a cornerstone of machine learning, but traditional methods often fall short when dealing with complex, unstructured data. Standard global measures, such as Correlation or Mutual Information, usually require signals to be perfectly aligned. Conversely, "bag of features" methods—which count the occurrences of local patterns—ignore the spatial or temporal structure of the signal entirely.
Consider comparing two images of a dancer in different poses. A pixel-wise comparison will fail because the images aren't aligned. A "bag of features" approach might correctly identify that both images contain "arm-like" and "leg-like" patches, but it would also score a scrambled image of those same patches just as highly.
To bridge this gap, researchers have introduced a novel similarity measure based on a simple intuition: one signal is "similar" to another if it can be easily reconstructed using a few large, contiguous chunks from the reference. By focusing on the size of shared regions rather than just pixel-wise alignment or feature distributions, this approach creates a powerful, general-purpose framework for tasks ranging from defect detection in images to action recognition in video and speaker identification in audio.
The Core Concept: Similarity by Composition
The core idea is to determine if a query signal ($Q$) is similar to a reference signal ($ref$) by attempting to "compose" $Q$ using pieces of $ref$. The algorithm relies on three primary scoring mechanisms:
- Local Evidence Score (LES): The algorithm searches for a region in the query that exists in the reference. It calculates a log-likelihood ratio to determine how much more likely it is that this region was "borrowed" from the reference versus being generated by a random process. Crucially, the larger the contiguous chunk found, the higher the score.
- Point Evidence Score (PES): For every single point in the signal, the algorithm identifies the most informative chunk that contains that point.
- Global Evidence Score (GES): To obtain a single similarity metric for the entire signal, the algorithm accumulates these local scores. Because calculating the perfect global score is computationally intractable (due to the vast number of ways to segment an image), the authors provide mathematically sound upper and lower bounds that are efficient to compute.
To find these chunks efficiently, the researchers employ a "Star Model." They break regions into small, overlapping patches and use a graphical model to allow for small local distortions (like a slight bend in an arm) while maintaining the overall geometric arrangement of the patches.
Key Insights
- Size is the Signal: The most profound insight of this work is that the size of the shared contiguous region provides the statistical evidence for similarity. Anyone can compose an image using 1x1 pixel chunks, but being able to use a 50x50 chunk is a strong indicator of a meaningful relationship.
- Inference of New Configurations: This method can recognize a pose it has never seen before. If the reference has a person with an arm up and another with a leg out, the algorithm can "compose" a new pose (arm up AND leg out) and recognize it as similar because the large constituent parts exist in the reference.
- Geometric over Linear: Unlike PCA or Wavelets, which decompose signals into a linear combination of basis functions, this is a geometric, data-driven decomposition.
Applications and Results
The authors demonstrate the versatility of their approach across several distinct domains, showcasing impressive results.
Intra-Signal Saliency and Defect Detection
By trying to compose a signal using other parts of itself, the algorithm can find "saliency." If a part of an image cannot be composed using the rest of the image, it stands out as an irregularity. The algorithm successfully identified tiny defects in fruit (like grapefruits) and fabric by recognizing that those specific regions could only be composed of very small, fragmented pieces of the "healthy" reference data.
Video Action Recognition
The method was tested on the Weizmann Action Database, which contains 81 video sequences of nine people performing actions like running, walking, and jumping. The approach achieved 97.5% accuracy (79/81 sequences). When tested on more complex scenes with multiple people and occlusions, the accuracy actually improved to 98%.
Audio Speaker Recognition
The framework is not limited to visual data. On a database of 31 speakers repeating a five-word sentence recorded over a phone line, the global similarity measure (GES) correctly identified the speaker in 97% of cases (90/93), even with very short (2-3 second) speech signals.
Limitations and Future Work
While highly effective, the approach has a few limitations. First, computational complexity remains a challenge; while the bounds make the algorithm usable, the full marginalization over all possible segmentations is intensive. Second, the current implementation primarily handles shifts. While the framework can theoretically accommodate scaling and rotation, these transformations add significant computational overhead. Finally, the method relies on parameter tuning, such as patch sizes and distortion thresholds, which may need to be adjusted for different types of signals (e.g., high-frequency audio versus smooth images).
Despite these challenges, "Similarity by Composition" offers a highly intuitive and robust alternative to traditional signal matching, paving the way for more flexible and structurally aware machine learning models.
Summary updated