Kernels on Structured Objects Through Nested Histograms

Marco Cuturi, Kenji FukumizuNeurIPS 2006 · OpenReview

Overview

This paper introduces a novel framework for comparing structured objects, such as images or text, by representing them as a hierarchy of nested histograms. By efficiently averaging kernels across all possible resolutions—from global summaries to fine-grained local details—the authors create a flexible similarity measure that outperforms standard "bag-of-components" approaches without massive computational overhead.

The Problem with Standard Histograms

In machine learning, kernel methods (like Support Vector Machines) are powerful tools for classification, but they typically require data to be in a vector format. To handle "structured" data—such as an image made of pixels or a document made of words—researchers often use the bag-of-components paradigm. This involves turning the object into a flat histogram, such as a color histogram for an image.

Transition from flat bag-of-components to a nested hierarchy

The primary issue with standard histograms is that they discard structural and contextual information. For instance, a color histogram of a sunset looks identical whether the orange pixels are concentrated at the top (the sky) or scattered randomly throughout the image. While some researchers attempt to fix this by using very fine-grained local histograms (e.g., dividing an image into a $16 \times 16$ grid), these can become too specific and fail to recognize broader similarities. The challenge lies in finding the optimal resolution that balances global context with local detail.

Proposed Method: Nested Histograms

The authors propose a middle ground: instead of selecting a single resolution, the model leverages all of them.

  1. Hierarchical Representation: Objects are represented as a family of nested histograms. For an image, this hierarchy might start with the whole image (Level 0), divide into quadrants (Level 1), then into smaller sub-quadrants (Level 2), and so forth.
Examples of different image partitions and grid resolutions
  1. Resolution-Specific Kernels: For any given way to partition the object, the authors define a kernel that multiplies the similarities of the corresponding histogram pieces.
  2. The Averaging Trick: Because there are exponentially many ways to partition a hierarchy, calculating a simple average is computationally infeasible. To solve this, the authors use a branching process prior to weight different partitions.
  3. Efficient Factorization: The core mathematical contribution of the paper is a proof showing that this weighted average over all possible partitions can be factorized. This allows the final kernel value to be computed in linear time relative to the number of nodes in the hierarchy.

Key Insights

  • Bayesian Averaging of Resolutions: Instead of performing traditional model selection to find the "best" grid size, the kernel performs a Bayesian averaging. It automatically detects which resolutions provide the best match between two objects.
  • Context via Conditioning: This framework extends beyond images. In text processing, a "nested histogram" could represent words found after specific grammatical categories or prefixes, capturing linguistic structure that a simple bag-of-words misses.
  • Computational Elegance: By utilizing the branching process prior, the authors transform a combinatorial nightmare into a simple recursive calculation. If a standard histogram kernel can be computed, this hierarchical version can be added with minimal extra cost.

Experimental Results

The authors evaluated their approach on an image retrieval task using a subset of the Corel Stock database (1,200 images across 12 classes). Images were reduced to a 512-color RGB space, and centered grids of $4 \times 4$, $8 \times 8$, and $16 \times 16$ patches were used to build the nested histograms.

Focusing on the misclassification rate using different base kernels (like Hellinger or $\chi^2$ distance), the experiments showed:

  • Superiority of the Mixture: The "averaged" kernel consistently outperformed both the coarsest (global only) and finest (local only) perspectives.
  • Concrete Improvements: Using the Hellinger $H_1$ distance, the global histogram alone yielded an 18.4% error rate, and the finest patches alone yielded 17.3%. The proposed mixture reduced the error to ~14.5%.
  • Robustness: Performance remained stable across a wide range of hyperparameters, indicating the method is not overly sensitive to tuning.

Limitations and Future Work

While robust, the method requires users to choose the base kernel and the branching probability ($\epsilon$). The authors suggest cross-validation but note that more principled, semi-supervised ways to estimate these parameters are an area for future work. Additionally, the framework requires the base kernel to be positive definite on all bounded measures, excluding some popular information-diffusion kernels. Finally, the quality of the results inherently depends on defining a sensible hierarchy (like a spatial grid for images), making its utility less clear for data without an obvious hierarchical structure.

Ultimately, this hierarchical approach serves as an effective "template procedure" that can be easily integrated into existing histogram-based kernel methods, offering a significant accuracy boost for a negligible increase in compute time.

Summary updated

Abstract

We propose a family of kernels for structured objects which is based on the bag-ofcomponents paradigm. However, rather than decomposing each complex object into the single histogram of its components, we use for each object a family of nested histograms, where each histogram in this hierarchy describes the object seen from an increasingly granular perspective. We use this hierarchy of histograms to define elementary kernels which can detect coarse and fine similarities between the objects. We compute through an efficient averaging trick a mixture of such specific kernels, to propose a final kernel value which weights efficiently local and global matches. We propose experimental results on an image retrieval experiment which show that this mixture is an effective template procedure to be used with kernels on histograms.
BibTeX
@inproceedings{cuturi2006kernels,
  author = {Marco Cuturi and Kenji Fukumizu},
  title = {{Kernels on Structured Objects Through Nested Histograms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=HyZXWvbd-r},
}
Figure