In the world of computer vision, we are often drowning in features. From low-level edges to high-level deep learning outputs, the challenge isn't just finding a good feature, but finding the right ensemble of features that work together harmoniously.
The paper "Features in Concert: Discriminative Feature Selection meets Unsupervised Clustering" presents a clever mathematical bridge between two traditionally separate worlds: supervised classification and unsupervised clustering. By doing so, it offers a highly efficient way to pick a "concert" of diverse, powerful features that excel even when training data is scarce.
TL;DR
The authors reformulate feature selection as a convex quadratic program that is mathematically equivalent to unsupervised clustering. This approach efficiently discovers sparse ensembles of diverse classifiers that outperform standard methods like SVMs and AdaBoost, particularly in "small data" regimes and large-scale video recognition.
What Problem Does This Paper Address?
Feature selection—the task of picking the most relevant subset of features from a massive pool—is notoriously difficult. Mathematically, it's NP-hard, meaning finding the absolute best combination is computationally prohibitive.
Existing methods have drawbacks:
- Boosting (e.g., AdaBoost): Works well with "weak" features but struggles to combine "strong" ones (like pre-trained CNNs) because the first few features selected tend to dominate the weights.
- SVMs: Powerful, but prone to overfitting when training samples are few and the feature space is huge.
- Greedy Search: Often gets stuck in local optima and doesn't explicitly account for feature diversity.
The authors sought a method that could handle a "vast sea" of candidate features, encourage diversity (to avoid redundancy), and remain computationally efficient.
Methods
The core innovation lies in the Problem Formulation. The authors start with a standard linear discriminant objective (minimizing sum of squares error) but add two critical constraints to the feature weights ($w$):
- Sum to 1: $\sum w_i = 1$
- Upper Bound: $0 \leq w_i \leq 1/k$
The $1/k$ constraint is the "secret sauce." It prevents any single feature from dominating and forces the model to select at least $k$ features.
When you expand the math, the objective function splits into two parts:
- A Linear Term: This encourages picking features that are individually strongly correlated with the ground truth.
- A Quadratic Term: This acts as a penalty for features that "co-fire" (are highly correlated with each other).
This structure is exactly what you see in unsupervised clustering problems. Minimizing this objective effectively "clusters" together features that are individually strong but mutually independent. To solve this efficiently, they use the Integer Projected Fixed Point (IPFP) algorithm, which converges in just 10–20 iterations.
Datasets
The authors evaluated their method on the YouTube-Objects dataset, a challenging large-scale video benchmark featuring 10 categories (aeroplane, car, dog, etc.) in wild, unconstrained settings.
To build their "feature pool," they used three types of inputs:
- Type I (CIFAR): HOG+SVM classifiers trained on clusters of CIFAR-10 images.
- Type II (YouTube-Parts): Linear SVMs trained on specific sub-regions (e.g., top-left, center) of video frames.
- Type III (ImageNet): Soft outputs from pre-trained Caffe CNNs, applied to various image sub-windows.
Key Insights and Ideas
- Sparsity is a Feature, Not a Bug: Proposition 1 in the paper proves that at the optimum, weights are typically either $0$ or exactly $1/k$. This means the algorithm isn't just weighting features; it's performing hard feature selection by averaging the top $k$ performers.
- The "Concert" Effect: By penalizing redundancy, the model picks features that cover different "aspects" of a class. For example, to recognize a "train," it might pick a feature for "tracks," one for "metal textures," and one for "linear perspective."
- Semantic vs. Visual Logic: Interestingly, the model often picks "unrelated" classes as features. As shown in Figure 1, to identify a "train," the model consistently selects classifiers for "library," "greenhouse," and "steel arch bridge." While semantically different, these share visual structures (parallel lines, glass/metal grids) or context that are highly discriminative for trains.
Key Results
- Superior Generalization: The gap between training and test accuracy was significantly smaller for this method than for SVMs, indicating it is much less prone to overfitting (see Figure 5).
- Efficiency in Training: The training time is quadratic in the number of features but constant relative to the number of training samples. In practice, it was 10–100x faster than standard convex optimization solvers (Figure 2d).
- Small Data Performance: The method showed remarkable robustness when trained on as few as 1 to 5 frames per video shot, significantly outperforming AdaBoost and FoBa (Figure 6).
- Accuracy: On YouTube-Objects, using the full pool of ~6000 features, the method achieved ~71% accuracy, nearly doubling the performance compared to using smaller, less diverse feature sets (Table 2).
Limitations and Future Work
- The $k$ Parameter: The model requires choosing $k$ (the number of features to average). While Figure 2a shows a relatively stable peak, it still requires tuning.
- Independence Assumption: The theoretical convergence to zero error (Proposition 2) assumes features are independent given the class, which isn't always true in practice.
- Future Directions: The authors suggest this could be a building block for hierarchical recognition systems, where each layer is an ensemble of the layer below, potentially mimicking the recursive nature of deep neural networks but with the added benefit of explicit feature selection.
Summary updated