Many selection processes such as finding patients qualifying for a medical
trial or retrieval pipelines in search engines consist of multiple stages,
where an initial screening stage focuses the resources on shortlisting the most
promising candidates. In this paper, we investigate what guarantees a screening
classifier can provide, independently of whether it is constructed manually or
trained. We find that current solutions do not enjoy distribution-free
theoretical guarantees -- we show that, in general, even for a perfectly
calibrated classifier, there always exist specific pools of candidates for
which its shortlist is suboptimal. Then, we develop a distribution-free
screening algorithm -- called Calibrated Subset Selection (CSS) -- that, given
any classifier and some amount of calibration data, finds near-optimal
shortlists of candidates that contain a desired number of qualified candidates
in expectation. Moreover, we show that a variant of CSS that calibrates a given
classifier multiple times across specific groups can create shortlists with
provable diversity guarantees. Experiments on US Census survey data validate
our theoretical results and show that the shortlists provided by our algorithm
are superior to those provided by several competitive baselines.

本文考察了筛选分类器能否提供独立于手动或训练方式构建的理论保证。我们发现目前的解决方案没有分布无关的理论保证，开发了一种分布无关的筛选算法 -- Calibrated Subset Selection（CSS），可以在任何分类器和某些校准数据的情况下找到包含所需合格候选人数量的最佳候选人短列表。实验验证了我们算法提供的清单优于几种竞争基线。

通过校准子集选择改善筛选流程

Improving Screening Processes via Calibrated Subset Selection

In submodular $k$-secretary problem, the goal is to select $k$ items in a
randomly ordered input so as to maximize the expected value of a given monotone
submodular function on the set of selected items. In this paper, we introduce a
relaxation of this problem, which we refer to as submodular $k$-secretary
problem with shortlists. In the proposed problem setting, the algorithm is
allowed to choose more than $k$ items as part of a shortlist. Then, after
seeing the entire input, the algorithm can choose a subset of size $k$ from the
bigger set of items in the shortlist. We are interested in understanding to
what extent this relaxation can improve the achievable competitive ratio for
the submodular $k$-secretary problem. In particular, using an $O(k)$ shortlist,
can an online algorithm achieve a competitive ratio close to the best
achievable online approximation factor for this problem? We answer this
question affirmatively by giving a polynomial time algorithm that achieves a
$1-1/e-\epsilon -O(k^{-1})$ competitive ratio for any constant $\epsilon > 0$,
using a shortlist of size $\eta_\epsilon(k) = O(k)$. Also, for the special case
of m-submodular functions, we demonstrate an algorithm that achieves a
$1-\epsilon$ competitive ratio for any constant $\epsilon > 0$, using an $O(1)$
shortlist. Finally, we show that our algorithm can be implemented in the
streaming setting using a memory buffer of size $\eta_\epsilon(k) = O(k)$ to
achieve a $1 - 1/e - \epsilon-O(k^{-1})$ approximation for submodular function
maximization in the random order streaming model. This substantially improves
upon the previously best known approximation factor of $1/2 + 8 \times
10^{-14}$ [Norouzi-Fard et al. 2018] that used a memory buffer of size $O(k
\log k)$.

本文提出了一种称为 submodular k-secretary problem with shortlists 的问题设置，旨在改善 submodular k-secretary 问题的可达竞争比率，而使用大小为 O (k) 的 shortlist，我们证明了该算法可以保证任意常数 ε>0 的竞争比率为 1-1/e-ε-O (k^-1)。我们还证明了，在 m-submodular 函数的特殊情况下，使用 O (1) 的 shortlist，我们的算法可以保证 ε>0 的竞争比率为 1-ε。最后，我们还证明了我们的算法可以在流处理模型中实现，并且可以通过使用大小为 O（k）的内存缓冲区来保证子模函数最大化的 1-1/e-ε-O (k^-1) 逼近，这大大提高了以前已知的逼近因子。

带有短列表的次模秘书问题

Submodular Secretary Problem with Shortlists

In this paper, we study shortlists as an interface component for recommender
systems with the dual goal of supporting the user's decision process, as well
as improving implicit feedback elicitation for increased recommendation
quality. A shortlist is a temporary list of candidates that the user is
currently considering, e.g., a list of a few movies the user is currently
considering for viewing. From a cognitive perspective, shortlists serve as
digital short-term memory where users can off-load the items under
consideration -- thereby decreasing their cognitive load. From a machine
learning perspective, adding items to the shortlist generates a new implicit
feedback signal as a by-product of exploration and decision making which can
improve recommendation quality. Shortlisting therefore provides additional data
for training recommendation systems without the increases in cognitive load
that requesting explicit feedback would incur.
We perform an user study with a movie recommendation setup to compare
interfaces that offer shortlist support with those that do not. From the user
studies we conclude: (i) users make better decisions with a shortlist; (ii)
users prefer an interface with shortlist support; and (iii) the additional
implicit feedback from sessions with a shortlist improves the quality of
recommendations by nearly a factor of two.

本文研究了使用 shortlists 作为推荐系统的接口组件，以支持用户的决策过程，从而改善隐式反馈获取，提高推荐质量，并进行了电影推荐设置下的用户研究测试和分析，结果表明，使用带有 shortlists 的界面能够使用户做出更好的决策和提高推荐系统的精度。