High scale video mining with forests of fuzzy decision trees

Marcin Detyniecki, Ph.D., Christophe Marsala, Marcin DetynieckiCstst 2008 · DOI

TL;DR

This paper introduces a novel video mining method using Forests of Fuzzy Decision Trees (FFDT) for high-scale applications like automatic video indexing. By leveraging fuzzy logic, their approach offers improved robustness and accuracy compared to traditional decision trees, particularly for complex and imbalanced datasets.

What Problem Does This Paper Address?

The ever-increasing volume of video content presents a significant challenge for manual indexing and content retrieval. Automatically identifying high-level semantic concepts (e.g., "people," "maps," "military personnel") within videos is crucial for efficient access and analysis. Traditional machine learning methods, especially decision trees, often struggle with the inherent imprecision and vastness of video data, leading to issues with robustness and thresholding. This paper aims to address these limitations by proposing a more sophisticated approach that can handle large-scale video mining effectively.

Methods

The core of the proposed method lies in the use of Forests of Fuzzy Decision Trees (FFDT). Here's a breakdown of their approach:

  • Video Pre-processing: Videos are first segmented into temporal shots, and representative frames are extracted. For each frame, a set of descriptors is computed. These include:
  • Visual Information Descriptors: These are derived from spatial segmentation of frames into overlapping regions (top, bottom, left, right, center). Histograms in the HSV color space are computed for each region.
  • Temporal Information Descriptors: These capture the temporal position and duration of shots and frames within the video.
  • Class Descriptors: These are obtained through manual indexing of training videos, assigning high-level features to specific frames.
  • Fuzzy Decision Trees (FDT): Unlike traditional decision trees that use crisp thresholds, FDTs employ fuzzy set theory. This allows them to handle imprecise data and smooth out the effects of noisy or uncertain information. They build fuzzy partitions on numerical descriptor values.
  • Forests of Fuzzy Decision Trees (FFDT): Recognizing that a single FDT might not be sufficient for complex, high-dimensional data, the authors propose using a "forest" of FDTs. Each FDT in the forest is trained on a balanced random sample of the training data. For a given feature, multiple FDTs are trained, each potentially capturing different aspects of the data.
  • Classification: To classify a frame, each FDT in the forest provides a degree of membership (between 0 and 1) indicating the likelihood of the feature being present. These individual degrees are then aggregated (e.g., through simple or weighted voting) to produce a final classification score for the frame.
  • Shot Ranking: The frame-level scores are aggregated for each shot (typically using a "max" operation) to obtain a global score for the shot. Shots are then ranked based on these scores.

Datasets

  • Waveform Dataset: This is a well-known machine learning dataset used for initial experiments to study the influence of the forest size and aggregation operators on error rates. It consists of 5000 instances with 3 symbolic classes and 21 real-valued attributes.
  • TRECVID 2007 Challenge Dataset: This real-world dataset was used to evaluate the performance of their video mining tool. It comprises 109 videos (each around 30 minutes long) and 18142 reference shots, with a focus on high-level feature extraction.

Key Insights and Ideas

  • Fuzzy Logic for Robustness: The paper strongly advocates for the use of fuzzy set theory in decision trees. It demonstrates that fuzzy approaches (Zadeh and Lukasiewicz t-norms) consistently yield lower error rates than classical, crisp decision trees on both the Waveform dataset and in the TRECVID challenge.
  • Forests Outperform Single Trees: For complex, high-scale problems like video mining, a single FDT is insufficient. Combining multiple FDTs into a forest significantly improves performance by better covering the entire input space.
  • Forest Size Matters: The experiments show a clear trend: increasing the number of FDTs in the forest generally leads to a decrease in error rate, up to a certain point. This highlights the importance of the forest's ensemble size.
  • Classification vs. Ranking: The FFDT approach is more effective at classifying whether a shot contains a feature than at precisely ranking all shots based on their relevance. This is an important distinction for applications where identifying the presence of a feature is the primary goal.

Key Results

  • Waveform Dataset: The fuzzy versions of FFDT consistently outperformed the "Classic" FDT, with error rates around 0.15 for the classic approach and lower for fuzzy methods, regardless of forest size.
  • TRECVID 2007 Challenge:
    • FFDTs achieved good results for certain features, ranking among the top approaches for concepts like "animal," "computer TV screen," and "maps."
    • The "F35_Zadeh" FFDT (35 trees) generally performed better than "F25_Zadeh" (25 trees), reinforcing the benefit of a larger forest.
  • The fuzzy approach consistently outperformed the "Classic" FFDT in the TRECVID evaluation metrics (Inferred Average Precision and number of hits at different ranking levels).
  • Runtime: The experiments, including constructing 500 FDTs and classifying a test set with multiple operators, took approximately 7350 seconds on a multi-processor computer, indicating a manageable computational cost for high-scale applications.

Limitations and Future Work

  • Descriptor Dependency: The performance of FFDT is highly dependent on the chosen descriptors. For complex features, more sophisticated descriptors are needed.
  • Ranking Limitations: FFDTs are primarily classification tools and struggle with precise ranking.
  • Forest Size Optimization: While larger forests generally improve results, the optimal size needs further study.
  • Future Work: The authors suggest exploring other types of descriptors to encode video shots to improve results for a wider range of high-level features. They also aim to further investigate the impact of forest size and potentially explore different aggregation strategies.

Summary updated

BibTeX
@inproceedings{phd2008high,
  author = {Marcin Detyniecki, Ph.D. and Christophe Marsala and Marcin Detyniecki},
  title = {{High scale video mining with forests of fuzzy decision trees}},
  booktitle = {Cstst},
  year = {2008},
  doi = {10.1145/1456223.1456308},
}
Figure