Accelerated Experimental Design for Pairwise Comparisons
Accelerated Experimental Design for Pairwise Comparisons
复制标题
DOI：
10.1137/1.9781611975673.49
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Yuan Guo;Jennifer G. Dy;Deniz Erdoğmuş;Jayashree Kalpathy-Cramer;S. Ostmo;J. Campbell;M. Chiang
中科院分区：
文献类型：
--
作者：
Yuan Guo;Jennifer G. Dy;Deniz Erdoğmuş;Jayashree Kalpathy-Cramer;S. Ostmo;J. Campbell;M. Chiang
成对比较标签比类标签更具信息性和可变性，但生成它们提出了一个挑战：它们的数字在数据集大小中二次增长。我们研究了自然的实验设计目标，即D-Ovipimality，可用于确定要生成的$ K $成对比较。已知该目标在实践中表现良好，并且是子模型，从而使选择可以通过贪婪算法近似。 na \“ ive贪婪实现具有$ o（n^2d^2k）$复杂性，其中$ n $是数据集大小，$ d $是特征空间维度，而$ k $是生成的比较数量。我们证明，通过利用数据集的固有几何形状（即它由成对比较组成），可以将贪婪算法的复杂性降低到$ o（n^2（k+d）+n（dk+d^2）+d^2k）。$我们也将相同的加速度应用于所谓的懒惰贪婪算法。 $ 10^8 $比较的数据集的执行时间;终止。
Pairwise comparison labels are more informative and less variable than class labels, but generating them poses a challenge: their number grows quadratically in the dataset size. We study a natural experimental design objective, namely, D-optimality, that can be used to identify which $K$ pairwise comparisons to generate. This objective is known to perform well in practice, and is submodular, making the selection approximable via the greedy algorithm. A na\"ive greedy implementation has $O(N^2d^2K)$ complexity, where $N$ is the dataset size, $d$ is the feature space dimension, and $K$ is the number of generated comparisons. We show that, by exploiting the inherent geometry of the dataset--namely, that it consists of pairwise comparisons--the greedy algorithm's complexity can be reduced to $O(N^2(K+d)+N(dK+d^2) +d^2K).$ We apply the same acceleration also to the so-called lazy greedy algorithm. When combined, the above improvements lead to an execution time of less than 1 hour for a dataset with $10^8$ comparisons; the na\"ive greedy algorithm on the same dataset would require more than 10 days to terminate.