Abstract
We introduce an unsupervised approach to efficiently discover the underlying features in a data set via crowdsourcing. Our queries ask crowd members to articulate a feature common to two out of three displayed examples. In addition we also ask the crowd to provide binary labels to the remaining examples based on the discovered features. The triples are chosen adaptively based on the labels of the previously discovered features on the data set. In two natural models of features, hierarchical and independent, we show that a simple adaptive algorithm, using "two-out-of-three" similarity queries, recovers all features with less labor than any nonadaptive algorithm. Experimental results validate the theoretical findings.
The Challenge of Feature Discovery
When analyzing complex datasets—such as medical imaging or sign language—researchers often rely on crowdsourced "tagging" to categorize data. However, standard tagging is frequently inefficient. If workers are shown items in isolation, they tend to provide obvious, redundant labels (e.g., "person," "indoors") that fail to distinguish between items in a meaningful way.
The core challenge is feature discovery: identifying the specific attributes that partition a dataset into useful categories. Traditional non-adaptive methods often miss "fine-grained" nuances because they don't force workers to look beyond the most salient, surface-level characteristics.
The Adaptive Triple Algorithm
To solve this, researchers from Microsoft and UC San Diego developed the Adaptive Triple Algorithm. This method moves away from single-item tagging to "two-out-of-three" (2/3) queries. A worker is presented with three examples $(x, y, z)$ and asked: Name a feature common to two of these, but not the third.
The power of this approach lies in its adaptivity. Once a feature is identified (e.g., "wearing a hat"), the system asks the crowd to label the entire dataset for that feature. The algorithm then intelligently selects future triples that are not yet "resolved" by known features. If the system already knows about gender, it will avoid showing a triple of two men and one woman. Instead, it might show three men, forcing the worker to find a more subtle distinction, such as "bearded" or "smiling."
Theoretical Models
The paper analyzes the algorithm's performance under two primary models:
- Hierarchical: Features are structured in a tree. As shown in the figure above, the algorithm aims to discover the "most general" features first before drilling down into sub-categories.
- Independent: Features occur randomly and may overlap (e.g., "wearing glasses" and "smiling").
Mathematically, in a hierarchical tree with $M$ features, the adaptive algorithm can discover all features in exactly $M$ queries. In contrast, a random, non-adaptive approach would require $\Omega(M^3)$ queries—representing a massive reduction in human labor.
Experimental Validation
The researchers tested their approach on three datasets: American Sign Language (ASL) videos, human faces, and a diverse mix of product images.
The results were definitive. After just 35 queries:
- Adaptive Triples discovered 24-25 distinct, interesting features.
- Random Triples found only 12-18 features.
- Standard Tagging performed worst, yielding only 9-13 features, as workers repeatedly tagged the same obvious attributes.
Conclusion and Future Directions
By leveraging the psychological tendency of humans to better identify shared positive traits rather than shared absences (as noted in Tversky’s theory of similarity), and by using an adaptive selection process, this method significantly improves the efficiency of unsupervised feature discovery. Future work may focus on managing natural language redundancy (e.g., "male" vs. "man") and scaling the labeling process for massive datasets.
Summary updated