A Caltech Library Service

How to Query an Oracle? Efficient Strategies to Label Data

Lahouti, Farshad and Kostina, Victoria and Hassibi, Babak (2022) How to Query an Oracle? Efficient Strategies to Label Data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44 (11). pp. 7597-7609. ISSN 0162-8828. doi:10.1109/tpami.2021.3118644.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We consider the basic problem of querying an expert oracle for labeling a dataset in machine learning. This is typically an expensive and time consuming process and therefore, we seek ways to do so efficiently. The conventional approach involves comparing each sample with (the representative of) each class to find a match. In a setting with N equally likely classes, this involves N/2 pairwise comparisons (queries per sample) on average. We consider a k-ary query scheme with k ≥ 2 samples in a query that identifies (dis)similar items in the set while effectively exploiting the associated transitive relations. We present a randomized batch algorithm that operates on a round-by-round basis to label the samples and achieves a query rate of O(N/k²). In addition, we present an adaptive greedy query scheme, which achieves an average rate of ≈0.2N queries per sample with triplet queries. For the proposed algorithms, we investigate the query rate performance analytically and with simulations. Empirical studies suggest that each triplet query takes an expert at most 50% more time compared with a pairwise query, indicating the effectiveness of the proposed k-ary query schemes. We generalize the analyses to nonuniform class distributions when possible.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemDiscussion paper
Lahouti, Farshad0000-0002-8729-873X
Kostina, Victoria0000-0002-2406-7440
Hassibi, Babak0000-0002-1375-5838
Additional Information:The authors would like to thank O. Shokrollahi and the participants who helped with the experiments reported in Section 6.
Issue or Number:11
Record Number:CaltechAUTHORS:20221031-572094900.1
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117647
Deposited By: Research Services Depository
Deposited On:07 Nov 2022 21:24
Last Modified:07 Nov 2022 21:24

Repository Staff Only: item control page