Features in Concert: Discriminative Feature Selection meets Unsupervised Clustering

Marius Leordeanu, Alexandra Radu, Rahul SukthankararXiv 2014 · arXiv

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$):

  1. Sum to 1: $\sum w_i = 1$
  2. 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.

Figure 2. Optimization and sensitivity analysis: a) Sensitivity to k. Performance improves as features are added, is stable around the peak k = 60 and falls k > 100 as useful features are exhausted. b) Features ordered by weight for k = 50 confirming that our method selects nearly equal weights up to the chosen k. c) Our method converges to a solution in 10–20 iterations. d) Runtime of interior point method divided by ours, both in Matlab and with 100 max iterations. All results are averages over 100 random experiments.

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.
Figure 1. Context in the mind: What classes can trigger the idea of a “train”? Many classes have similar appearance but are semanti- cally unrelated; others are semantically close but visually dissimi- lar. We argue that consistently co-firing classifiers, either based on spatial and temporal context or similar appearance, can be power- ful in collaboration and robust to outliers, overfitting and missing features. Here, we show the classifiers that are consistently se- lected by our method, from very limited training data, as providing valuable input to the class “train”.

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

Abstract

Feature selection is an essential problem in computer vision, important for category learning and recognition. Along with the rapid development of a wide variety of visual features and classifiers, there is a growing need for efficient feature selection and combination methods, to construct powerful classifiers for more complex and higher-level recognition tasks. We propose an algorithm that efficiently discovers sparse, compact representations of input features or classifiers, from a vast sea of candidates, with important optimality properties, low computational cost and excellent accuracy in practice. Different from boosting, we start with a discriminant linear classification formulation that encourages sparse solutions. Then we obtain an equivalent unsupervised clustering problem that jointly discovers ensembles of diverse features. They are independently valuable but even more powerful when united in a cluster of classifiers. We evaluate our method on the task of large-scale recognition in video and show that it significantly outperforms classical selection approaches, such as AdaBoost and greedy forward-backward selection, and powerful classifiers such as SVMs, in speed of training and performance, especially in the case of limited training data.
BibTeX
@misc{leordeanu2014features,
  author = {Marius Leordeanu and Alexandra Radu and Rahul Sukthankar},
  title = {{Features in Concert: Discriminative Feature Selection meets Unsupervised Clustering}},
  year = {2014},
  eprint = {1411.7714},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.7714},
}
Figure