Crowdsourcing Feature Discovery via Adaptively Chosen Comparisons
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Preventing False Discovery in Interactive Data Analysis is Hard
We show that, under a standard hardness assumption, there is no computationally efficient algorithm that given $n$ samples from an unknown distribution can give valid answers to $n^{3+o(1)}$ adaptively chosen statistical…
validInteractive Fingerprinting Codes and the Hardness of Preventing False Discovery
We show an essentially tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given $n$ samples from an unknown distribution. A statistical que…
validImplicitly Abusive Comparisons -- A New Dataset and Linguistic Analysis
We examine the task of detecting implicitly abusive comparisons (e.g. {``}Your hair looks like you have been electrocuted{''}). Implicitly abusive comparisons are abusive comparisons in which abusive words (e.g. {``}dumb…
Active Ranking using Pairwise Comparisons
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of $n$ objects can be identified by standard sorting methods using $n log_2…
Generalization for Adaptively-chosen Estimators via Stable Median
Datasets are often reused to perform multiple statistical analyses in an adaptive way, in which each analysis may depend on the outcomes of previous analyses on the same dataset. Standard statistical guarantees do not ac…