UPMC-LIP6 at TrecVid'08: Balanced and Unbalanced Forests of Fuzzy Decision Trees for High-Level Feature Detection

Marcin Detyniecki, Ph.D., Christophe Marsala, Marcin DetynieckiTrecvid 2008

Introduction

Automated video indexing relies heavily on High-Level Feature Extraction (HLFE)—the ability of a system to identify semantic concepts like "mountain," "explosion," or "person speaking" within video keyframes. A significant hurdle in this domain is the data imbalance problem: in massive datasets like TRECVID, negative examples (frames without the feature) vastly outnumber positive ones. Researchers from UPMC-LIP6 investigated whether ensemble learning, specifically Forests of Fuzzy Decision Trees (FFDT), could effectively navigate this lopsided search space.

Methodology: Fuzzy Forests and Spatial Context

The UPMC-LIP6 team developed a pipeline that prioritizes local context and robust classification boundaries.

Spatial Segmentation and Descriptors

Rather than analyzing a keyframe as a single entity, the system segments each image into overlapping regions. This approach allows the model to capture features that might be localized, such as a logo in a corner or a face in the center.

Spatial segmentation of a keyframe into overlapping regions (A, B, C, and D) to capture localized visual features.

For each region, HSV histograms are computed. The precision of these histograms (bin count) is varied based on the region's perceived importance, providing a more granular description of the central areas compared to the periphery.

Forests of Fuzzy Decision Trees (FFDT)

The core classifier is a Forest of Fuzzy Decision Trees. Unlike standard decision trees that use rigid thresholds, fuzzy trees employ "soft" boundaries, making them more resilient to the continuous and often noisy numerical values inherent in image data. By building an ensemble (a "forest") of these trees, the system achieves higher stability and accuracy than a single complex tree.

Experimental Results: The Power of Unbalanced Sampling

The pivotal experiment compared two training strategies:

  1. Balanced Sampling: Equalizing the number of positive and negative examples in the training set.
  2. Unbalanced Sampling: Maintaining a distribution that more closely reflects the real-world scarcity of positive examples.

Contrary to some traditional machine learning intuitions, the unbalanced sampling strategy yielded superior results.

Inferred Average Precision across 20 features, comparing balanced and unbalanced forest configurations.

As shown in the performance data, the unbalanced forests (such as Run #2 with 200 trees) achieved a mean Inferred Average Precision (IAP) of 0.0231, outperforming the balanced counterpart (Run #3) at 0.0193. The authors suggest that unbalanced training forces individual trees to become "specialists," learning to be highly conservative and only predicting a feature when evidence is overwhelming. This significantly reduces false positives, which is critical for high-precision search tasks.

Conclusion and Future Work

The UPMC-LIP6 study demonstrates that Forests of Fuzzy Decision Trees are a viable tool for HLFE, particularly when trained on unbalanced data to mimic real-world distributions. While the current system uses relatively simple color descriptors, the framework is designed to be extensible. Future work will focus on integrating more sophisticated visual descriptors and optimizing the imbalance ratio for specific semantic features to further improve mean IAP.

Summary updated

BibTeX
@inproceedings{phd2008upmc,
  author = {Marcin Detyniecki, Ph.D. and Christophe Marsala and Marcin Detyniecki},
  title = {{UPMC-LIP6 at TrecVid'08: Balanced and Unbalanced Forests of Fuzzy Decision Trees for High-Level Feature Detection}},
  booktitle = {Trecvid},
  year = {2008},
}
Figure