Maximum Selection and Ranking under Noisy Comparisons
Authors: Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We compare the performance of our algorithms with that of others over simulated data. Similar to (Yue & Joachims, 2011), we consider the stochastic model where p(i, j) = 0.6 8i < j. Note that this model satisfies both SST and STI. We find 0.05-maximum with error probability δ = 0.1. Observe that i = 1 is the only 0.05-maximum. We compare the sample complexity of KNOCKOUT with that of BTMPAC (Yue & Joachims, 2011), Mallows MPI (Busa-Fekete et al., 2014a), and AR (Heckel et al., 2016). |
| Researcher Affiliation | Collaboration | 1University of California, San Diego 2Google Research. |
| Pseudocode | Yes | Algorithm 1 COMPRARE Input: element i, element j, bias , confidence δ. Initialize: ˆpi = 1 2, m = 1 2 2 log 2 δ , r = 0, wi = 0. 1. while (| ˆpi 1 2| ˆc and r m) (a) Compare i and j. if i wins wi = wi + 1. (b) r = r + 1, ˆpi = wi r . 2. ˆc = 1 2r log 4r2 δ . If wi r < 1 2 Output: j. else Output: i. |
| Open Source Code | No | The paper does not provide an explicit statement about the release of open-source code for the methodology described, nor does it include a link to a code repository. |
| Open Datasets | No | The paper conducts experiments on 'simulated data' and describes the stochastic models used (e.g., 'p(i, j) = 0.6' or 'Mallows model'), but it does not refer to any publicly available dataset with a link, DOI, or formal citation. |
| Dataset Splits | No | The paper conducts simulations on various stochastic models, but it does not specify any training, validation, or test dataset splits, as it's not a typical machine learning task with pre-partitioned datasets. |
| Hardware Specification | No | The paper does not mention any specific hardware used for running the simulations or experiments. |
| Software Dependencies | No | The paper does not provide details about specific software dependencies or their version numbers used for implementation or experimentation. |
| Experiment Setup | Yes | Similar to (Yue & Joachims, 2011), we consider the stochastic model where p(i, j) = 0.6 8i < j. Note that this model satisfies both SST and STI. We find 0.05-maximum with error probability δ = 0.1. ... As in (Busa-Fekete et al., 2014a), we consider n = 10 elements and various values for φ: 0.03, 0.1, 0.3, 0.5, 0.7, 0.8, 0.9, 0.95 and 0.99. |