.style= for tree= base=bottom, child anchor=north, align=center, s sep+=1cm,
straight edge/.style= edge path=[edge,thick,-Latex] (!u.parent anchor) –
(.child anchor); , if n children=0 tier=word, draw, thick, rectangle draw,
diamond, thick, aspect=2, if n=1edge path=[edge,thick,-Latex] (!u.parent
anchor) -— (.child anchor) node[pos=.2, above] Y; edge
path=[edge,thick,-Latex] (!u.parent anchor) -— (.child anchor) node[pos=.2,
above] N;

Predictive Inference with Weak Supervision

Maxime Cauchois1 Suyash Gupta1 Alnur Ali1 John Duchi1,2

Stanford University, Departments of 1Statistics and 2Electrical Engineering

January 2022

###### Abstract

The expense of acquiring labels in large-scale statistical machine learning
makes partially and weakly-labeled data attractive, though it is not always
apparent how to leverage such data for model fitting or validation. We present
a methodology to bridge the gap between partial supervision and validation,
developing a conformal prediction framework to provide valid predictive
confidence sets—sets that cover a true label with a prescribed probability,
independent of the underlying distribution—using weakly labeled data. To do
so, we introduce a (necessary) new notion of coverage and predictive validity,
then develop several application scenarios, providing efficient algorithms for
classification and several large-scale structured prediction problems. We
corroborate the hypothesis that the new coverage definition allows for tighter
and more informative (but valid) confidence sets through several experiments.

##  1 Introduction

Consider the typical supervised learning pipeline that we teach students
learning statistical machine learning: we collect data in $(X,Y)$ pairs, where
$Y$ is a label or target to be predicted; we pick a model and loss measuring
the fidelity of the model to observed data; we choose the model minimizing the
loss and validate it on held-out data. This picture obscures what is becoming
one of the major challenges in this endeavor: that of actually collecting
high-quality labeled data [44, 13, 38]. Hand labeling large-scale training
sets is often impractically expensive. Consider, as simple motivation, a
ranking problem: a prediction is an ordered list of a set of items, yet
available feedback is likely to be incomplete and partial, such as a top
element (for example, in web search a user clicks on a single preferred link,
or in a grocery, an individual buys one kind of milk but provides no feedback
on the other brands present). Developing methods to leverage such partial and
weak feedback is therefore becoming a major focus, and researchers have
developed methods to transform weak and noisy labels into a dataset with
strong, “gold-standard” labels [38, 56].

In this paper, we adopt this weakly labeled setting, but instead of
considering model fitting and the construction of strong labels, we focus on
validation, model confidence, and predictive inference, moving beyond point
predictions and single labels. Our goal is to develop methods to rigorously
quantify the confidence a practitioner should have in a model given only weak
labels. First consider the standard supervised learning scenario for data
$(X,Y)\in\mathcal{X}\times\mathcal{Y}$: here, given a desired confidence level
$\alpha$, the goal, rather than to provide point estimates $\widehat{Y}$ of
$Y$ given $X$, is to give a confidence set mapping $\widehat{C}_{n}$ based on
$(X_{i},Y_{i})_{i=1}^{n}$ that guarantees the distribution-free coverage

$\mathbb{P}\left[Y_{n+1}\in\widehat{C}_{n}(X_{n+1})\right]\geq 1-\alpha,$ (1)

where $(X_{n+1},Y_{n+1})$ is a new observation following the same distribution
as the first $n$ points. Conformal inference provides precisely these
guarantees [53, 30, 31, 32, 3].

There are many scenarios, however, where it is natural to transition away from
this strongly supervised setting with fully labeled examples. Above we note
ranking: individuals are very unlikely to provide full feedback [1, 14, 34].
In multi-label image classification [5, 15], a labeler may identify a few
items in a given scene but not all, leading to partial labeled feedback. A
major challenge in industrial machine learning deployment is to monitor models
once they are in production, where it may be challenging to collect high-
quality labels, but weak supervision—in the form of clicks on a recommended
website, or agreeing to a suggested text message completion—is relatively easy
and cheap to collect. In all of these, developing valid confidence sets and
measures for our predictions is of growing importance, as we wish for models
to be trustable, usable, verifiable.

With this as motivation, we consider supervised learning problems where,
instead of directly observing the ground truth labels $\\{Y_{i}\\}_{i=1}^{n}$,
we observe only noisy partial labeling. We make this formal in two equivalent
ways. In the first, for each instance $i\in[n]$, there exists a (random)
function $\varphi_{i}:\mathcal{Y}\to\mathcal{Y}^{\textup{weak}}$, that belongs
to a set $\Phi\subset\\{\mathcal{Y}\to\mathcal{Y}^{\textup{weak}}\\}$ of
partially supervising functions, such that we only observe
$Y^{\textup{weak}}_{i}=\varphi_{i}(Y_{i})$. Equivalently, the pair
$(Y^{\textup{weak}}_{i},\varphi_{i})$ specifies a weak set
$W_{i}\subset\mathcal{Y}$ that contains $Y_{i}$:

$\displaystyle
W_{i}\coloneqq\left\\{y\in\mathcal{Y}\mid\varphi_{i}(y)=Y^{\textup{weak}}_{i}\right\\}\subset\mathcal{Y},$
(2)

so that we observe a set $W_{i}$ consistent with $Y_{i}$. Instead of observing
strong labels $(X_{i},Y_{i})\stackrel{{\scriptstyle\rm iid}}{{\sim}}P$, we
thus observe only $(X_{i},\varphi_{i},Y^{\textup{weak}}_{i})_{i=1}^{n}$. We
consider two fundamental questions in this weakly-labeled setting: (i) for
what is it even possible to provide (distribution-free) coverage (e.g., true
labels $Y$, weak labels $W$, or something else), and (ii) what methods can
guarantee coverage?

While a first goal would be to produce a confidence mapping using
$(X_{i},Y^{\textup{weak}}_{i},\varphi_{i})_{i=1}^{n}$ guaranteeing the
coverage (1), as we prove in Section 2.1, this is impossible without further
distribution assumptions and would in general produce uninformative confidence
sets. We therefore relax our coverage desiderata, instead seeking a confidence
set $\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$ that covers the
weak counterpart $Y^{\textup{weak}}_{n+1}=\varphi_{n+1}(Y_{n+1})$ of the true
label in the sense that

$\displaystyle\mathbb{P}\left[\widehat{C}_{n}(X_{n+1})\cap
W_{n+1}\neq\emptyset\right]=\mathbb{P}\left[\exists
y\in\widehat{C}_{n}(X_{n+1})~{}\mbox{s.t.}~{}\varphi_{n+1}(y)=Y^{\textup{weak}}_{n+1}\right]\geq
1-\alpha.$ (3)

One could certainly use standard conformal inference approaches [53, 30, 3] to
obtain this, but naive application would yield predictions in the space
$\mathcal{Y}^{\textup{weak}}$ of weak labels—we wish to return usable labels
and configurations in the actual target space $\mathcal{Y}$ of interest. The
condition (3) is weaker than the initial coverage (1), and any confidence set
satisfying the former will also satisfy the latter, though it allows smaller
confidence set sizes. A major challenge is that the function $\varphi_{n+1}$
representing an individual’s weak supervision is _a priori_ unknown (e.g., we
do not know precisely what items a labeler will label in an image ahead of
time). Indeed, if we observe $\varphi_{n+1}$ prior to our prediction, a simple
and optimal way to achieve coverage (3) follows. First, construct a valid
confidence set mapping
$\widehat{C}_{n,\textup{weak}}:\mathcal{X}\rightrightarrows\mathcal{Y}^{\textup{weak}}$
for $Y^{\textup{weak}}_{n+1}$ using classical conformal methodology [53, 30,
3], which as in (1) would guarantee
$\mathbb{P}(Y^{\textup{weak}}_{n+1}\in\widehat{C}_{n,\textup{weak}}(X_{n+1}))\geq
1-\alpha$, Then define $\widehat{C}_{n}(x)\subset\mathcal{Y}$ to include a
single $y\in\mathcal{Y}$ for each
$y^{\textup{weak}}\in\widehat{C}_{n,\textup{weak}}(x)$ such that
$\varphi_{n+1}(y)=y^{\textup{weak}}$. Such an approach is unfortunately
impossible: we do not know ahead of time if an individual cares only about the
top item of her ranking or requires a ranking accurate up to the $10$th item.

Given the subtleties of coverage (3), we dedicate Section 2 to question (i)
above: what types of coverage are even possible. We devote Sections 3 and 4 to
question (ii): the development of methodologies that can guarantee the
coverage (3). In the former (Sec. 3), we provide a general recipe, while in
Section 4 we provide more tailored methods for large output spaces, such as
those in structured prediction. To provide some initial insights into the
methods and potential applications, we provide experiments on several real-
world domains in Section 5.

###  1.1 Related Work

An extensive line of work addresses prediction with partially labeled data.
The major focus is on strong label recovery under weak supervision, including
in multiclass [11, 35] and multilabel [55] tasks as well as structured
prediction problems, such as ranking [24, 28], segmentation [48, 36], and
natural language processing [17, 33]. More recent work tackles constructing
strongly labeled datasets from disparate weak supervision tasks [38, 56],
while the papers [10, 50, 6] provide generic theoretical conditions allowing
strong label recovery. Yet this literature focuses primarily on point
prediction problems, where a model only returns a single label with the
(putative) highest likelihood, in contrast to our confidence-based approach,
which provides calibrated uncertainty estimates and guarantees valid
confidence sets with virtually no distributional assumptions.

Our work also connects to the substantial literature on conformal inference,
where the goal is to provide valid predictive confidence sets (1). Vovk et al.
[53] introduce the main techniques—that examples are exchangeable, and so
essentially can provide $p$-values for significance of one-another—and suggest
the simple and generic split-conformal algorithm for building valid confidence
sets. Essentially all conformalized confidence sets offer the coverage
guarantee (1), so it is of interest to improve various aspects of the mappings
$\widehat{C}_{n}$. For example, works focus on improving the precision of
these methods and optimizing average confidence set size [32, 43, 23, 40, 2,
3], or on bridging the gap with other forms of coverage, like classwise [43]
or conditional [41, 3, 8, 42] coverage.

Along these lines, Bates et al. [4] generalize conformal inference to offer
error control with respect to loss functions beyond the 0-1 loss (coverage or
non-coverage) central to the guarantee (1), taking structured prediction
problems as motivation—as we do. Bates et al. [4] focus on settings where the
loss function naturally reflects the structure of the label space
$\mathcal{Y}$, such as hierarchical classification problems where one wishes
to label an example $X$ at a resolution (level of the tree) appropriate to the
confidence with which it can be labeled. We view our approaches as
complementary to theirs: their approaches make sense for scenarios with fully
labeled data in which a particular loss function is natural, for example in
tree-structured hierarchical classification, where a prediction can be made at
a given level in the tree. Conversely, approaches are sensible when one
receives weakly supervised data and wishes to make a single good prediction;
think of a grocery store deciding which of a large collection of shaving
creams to stock, a ranking problem with the where one wishes to make sure that
each individual’s desired shaving cream is stocked (in this context, this is
the guarantee (3)). In that respect, our approach relates to the expanded
admission problem [18], which allows for multiple labels to be “admissible”,
except that we do not observe to strongly supervised labels in our setting.
Consequently, we motivate our distinct coverage guarantees from a set of
impossibility results we present in the next section. Additionally, we pay
special attention (see Sec. 4) to developing practical algorithms that scale
to large label spaces, an important consideration with real-world weak
supervision.

##### Notation

Throughout this paper, $[n]$ stands for the set $\\{1,2,\dots,n\\}$. We use
$C:\mathcal{X}\rightrightarrows\mathcal{Y}$ to denote a set valued mapping
$C:\mathcal{X}\to 2^{\mathcal{Y}}\coloneqq\\{W\mid W\subset\mathcal{Y}\\}$.
$P$ is either the probability distribution generating the data
$(X,Y,\varphi)\in\mathcal{X}\times\mathcal{Y}\times\Phi$, or equivalently
$(X,Y,W)\in\mathcal{X}\times\mathcal{Y}\times 2^{\mathcal{Y}}$, as both
notations are equivalent for our purpose, and $U\sim\mathsf{Uni}[0,1]$ defines
a uniform random variable on $[0,1]$. $\mathfrak{S}(U,V)$ is the set of
bijections between two sets $U$ and $V$, using the shorthand
$\mathfrak{S}_{K}\coloneqq\mathfrak{S}([K],[K])$; $(i,j)$ is the transposition
of elements $i$ and $j\in[K]$, and for $k\in\mathbb{N}$,
$\Delta_{k}\coloneqq\\{p\in\mathbb{R}_{+}^{k}\mid p^{T}\mathbf{1}=1\\}$ is the
space of probability distributions on $[k]$.

##  2 Conformal inference with weakly supervised data

The starting point of this paper is to delineate realistic goals in weak-
conformal inference by determining what is actually possible—as we show, a
form of weak coverage—and what is unachievable. To that end, we demonstrate
that strong coverage (1), while desirable, is impossible without further
distributional assumptions. We thus relax our goals, presenting a general weak
conformal scheme (Section 2.2) that relies on weakly supervised data.

###  2.1 The strong coverage dilemma with partially supervised data

Consider a fully supervised classification setting with feature space
$\mathcal{X}$ and output space $\mathcal{Y}$, and let $P_{\textup{strong}}$ be
a joint distribution on $\mathcal{X}\times\mathcal{Y}$ representing strong, as
opposed to weak, supervision. In this fully supervised setting, we observe
samples $(X_{i},Y_{i})\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P_{\textup{strong}}$, in contrast to observing the weak label set
$W\subset\mathcal{Y}$ satisfying only $Y\in W$. We first require definitions
of consistency and validity.

######  Definition 2.1.

A probability distribution $P$ on
$(X,Y,W)\in\mathcal{X}\times\mathcal{Y}\times 2^{\mathcal{Y}}$ is _consistent_
if $P(Y\in W)=1$. For any consistent distribution $P$, $P_{\textup{weak}}$ and
$P_{\textup{strong}}$ denote the marginal distributions of $(X,W)$ and
$(X,Y)$, respectively, when $(X,Y,W)\sim P$.

######  Definition 2.2.

Let $\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$ be a
(potentially randomized) procedure depending only on the weakly supervised
sample $(X_{i},W_{i})_{i=1}^{n}\in\mathcal{X}\times 2^{\mathcal{Y}}$. Then
$\widehat{C}_{n}$ provides _$(1-\alpha)$ -strong distribution free coverage_
if for all consistent distributions $P$ on $\mathcal{X}\times\mathcal{Y}\times
2^{\mathcal{Y}}$ and
$(X_{i},Y_{i},W_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\rm iid}}{{\sim}}P$, we
have Eq. (1), i.e.

$\displaystyle\mathbb{P}\left[Y_{n+1}\in\widehat{C}_{n}(X_{n+1})\right]\geq
1-\alpha,$

and that $\widehat{C}_{n}$ provides _$(1-\alpha)$ -weak distribution free
coverage_ if it satisfies Eq. (3), i.e.

$\displaystyle\mathbb{P}\left[W_{n+1}\cap\widehat{C}_{n}(X_{n+1})\neq\emptyset\right]\geq
1-\alpha.$

With these definitions, we can provide the (negative) result that, on average
over the data set, any procedure satisfying strong distribution free coverage
(1) must include every individual label $y\in W_{n+1}$ with probability at
least $1-\alpha$. To formalize this, for a confidence set mapping
$\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$ constructed with
$(X_{i},W_{i})_{i=1}^{n}$, define the function

$\displaystyle
p_{n}(x,y)\coloneqq\mathbb{P}\left(y\in\widehat{C}_{n}(x)\right),$

which is the probability, taken over the weakly supervised sample
$(X_{i},W_{i})_{i=1}^{n}$, that $\widehat{C}_{n}(x)$ contains the potential
label $y$. We prove the following theorem in Appendix A.1.1.

######  Theorem 1.

Suppose that $\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$
provides $(1-\alpha)$-strong distribution free coverage. Then for all
consistent distributions $P$ on $\mathcal{X}\times\mathcal{Y}\times
2^{\mathcal{Y}}$,

$\displaystyle\mathbb{E}_{\\{(X_{i},W_{i})\\}_{i=1}^{n+1}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P_{\textup{weak}}}\left[\inf_{y\in
W_{n+1}}p_{n}(X_{n+1},y)\right]\geq 1-\alpha.$

Theorem 1 essentially states that $\widehat{C}_{n}$ simultaneously includes
each element $y\in W_{n+1}$ with probability at least $1-\alpha$. The theorem
is generally not improvable, as $W_{n+1}$ need not be a subset of
$\widehat{C}_{n}(X_{n+1})$. Indeed, think of the trivial procedure
$\widehat{C}_{n}$ that includes every label $y\in\mathcal{Y}$ independently
with probability $1-\alpha$: it obviously satisfies strong distribution-free
coverage but has no connection with $W_{n+1}$. As an additional immediate
corollary, if the sets $W$ contain at least a fixed number of labels, then so
does $\widehat{C}_{n}(X_{n+1})$.

######  Corollary 2.1.

Suppose that $\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$
provides $(1-\alpha)$-strong distribution free coverage, and that $P(|W|\geq
L)=1$ for some $L\geq 1$. Then

$\displaystyle\mathbb{E}_{\\{(X_{i},W_{i})\\}_{i=1}^{n+1}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P_{\textup{weak}}}\left[\big{|}\widehat{C}_{n}(X_{n+1})\big{|}\right]\geq
L(1-\alpha).$

Proof By Theorem 1,

$\displaystyle\mathbb{E}\left[\big{|}\widehat{C}_{n}(X_{n+1})\big{|}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{y\in\mathcal{Y}}p_{n}(X_{n+1},y)\right]\geq\mathbb{E}\left[|W_{n+1}|\inf_{y\in
W_{n+1}}p_{n}(X_{n+1},y)\right]\geq L(1-\alpha)$

as claimed. ∎

An alternative perspective is to consider large-sample limits; often, the
procedure $\widehat{C}_{n}$ converges to some population confidence set
mapping $C:\mathcal{X}\rightrightarrows\mathcal{Y}$ as $n\to\infty$, in that

$\mathbb{E}\left[\big{|}\widehat{C}_{n}(X)\triangle C(X)\big{|}\right]\to 0$
(4)

as $n\to\infty$, where the expectation is over both the construction of
$\widehat{C}_{n}$ and $X$ independent of
$(X_{i},W_{i})\stackrel{{\scriptstyle\rm iid}}{{\sim}}P_{\textup{weak}}$.
Typically, the limiting $C$ is a (nearly) deterministic function111 In some
cases, we use randomization over a single label to guarantee that
$\mathbb{P}(Y\in C(X))=1-\alpha$ of $x$; for example, the standard
construction [e.g. 53, 30, 3] takes $C(x)=\\{y\in\mathcal{Y}\mid
s(x,y)\leq\tau\\}$ for some scoring function
$s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ and threshold $\tau$, which is
deterministic. In this case, we can show that we nearly have $W\subset C(X)$,
so $C(X)$ must be large whenever $W$ is. To formalize, let

$\textup{Det}_{C}(x)\coloneqq\left\\{y\in\mathcal{Y}\mid\mathbb{P}(y\in
C(x))\in\\{0,1\\}\right\\}$

be the labels that are deterministically in _or_ out of $C(x)$ (where the
probability is over any randomization in the mapping $C$) so that
$\textup{Det}_{C}(x)=\mathcal{Y}$ whenever $C$ is deterministic. Then can show
that $W\subset C(X)$ with probability at least $1-\alpha$:

######  Corollary 2.2.

Suppose that $\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$
provides $(1-\alpha)$-strong distribution free coverage and satisfies the
limit (4). Then

$\displaystyle\mathbb{P}(W\cap\textup{Det}_{C}(X)\subset C(X))\geq 1-\alpha.$

See Appendix A.1.2 for a proof.

Theorem 1 and its corollaries suggest that any procedure achieving strong
(distribution-free) coverage necessarily produces inefficient (large)
confidence sets when one uses only weakly supervised data. Even in cases where
there is implicitly a single correct label, such as the structured prediction
problems Cabannes et al. [6] consider, where the weak labels $w$ that a single
$x$ supports (those for which $\mathbb{P}(W=w\mid X=x)>0$) have a single label
$y$ in their intersection $\cap_{w:\mathbb{P}(w\mid x)>0}\\{w\\}=\\{y\\}$,
never disallow large weak sets $W$. We thus must take a different tack,
targeting new coverage desiderata.

##### An aside: regression.

Although we primarily focus on classification (where $\mathcal{Y}$ is finite),
our development applies equally to regression or other problems with
continuous or infinite response sets, e.g., $\mathcal{Y}=\mathbb{R}$, as
nothing in Theorems 1 or 2 requires $\mathcal{Y}$ to be any particular space.
We leverage this in our experiments (Sec. 5) in the sequel to give numerical
examples, touching on the $\mathbb{R}$-valued case here to demonstrate the
analogues of our theoretical results.

As an example, weak sets $W$ in the continuous case may be intervals, arising,
for example, from measurements with limited resolution. We adapt Corollary 2.1
to regression by replacing counting measure with the Lebesgue measure Leb,
where the response set $\mathcal{Y}=\mathbb{R}$ and the weak sets
$W\subset\mathbb{R}$. Assuming that the weak sets all have a minimal volume,
any valid confidence set mapping necessarily is large (on average) as well:

######  Corollary 2.3.

Suppose that
$\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}=\mathbb{R}$ provides
$(1-\alpha)$-strong distribution free coverage, and let $L>0$. If
$P(\textup{Leb}(W_{i})\geq L)=1$, for $i=1,\ldots,n+1$, then

$\displaystyle\mathbb{E}\Big{[}\textup{Leb}\big{(}\widehat{C}_{n}(X_{n+1})\big{)}\Big{]}\geq
L(1-\alpha).$

An analogy to Corollary 2.2 follows nearly immediately from Corollary 2.3,
just as Corollary 2.2 follows Corollary 2.1. That is, if there exists a
deterministic set-valued mapping $C:\mathcal{X}\rightrightarrows\mathcal{Y}$
for which $\mathbb{E}[\textup{Leb}(\widehat{C}_{n}(X)\triangle C(X))]\to 0$,
then $\mathbb{P}(W\subset\widehat{C}_{n}(X_{n+1}))\geq 1-\alpha$.

###  2.2 A general weak-conformal scheme via scoring functions

The theoretical limitations we identify motivate the weak coverage (3) we
target instead of the strong converage (1). Following our discussion above,
the new coverage definition stems from two desiderata: if the problem is
actually low-noise and there already exists a highly predictive model we can
leverage to build our confidence sets—roughly, that conditional on $x$, a
single label $y$ belongs to the weak sets $W$ with high probability and a
model exists that can predict this $y$—then while we should return this
singleton even if we cannot guarantee strong coverage. In the alternative
perspective that we care only about the value $\varphi(Y)$—recall the weak set
(2)—providing any $y$ satisfying $\varphi(y)=Y^{\textup{weak}}$ should suffice
for prediction. We turn now to provide our general weak conformalization
scheme.

Our starting point is via the typical output of a machine-learned model, a
scoring function $s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ that ranks
potential labels (or responses) $y$ for an input example $x\in\mathcal{X}$. We
treat $s(x,y)$ is a non-conformity score, meaning the model predicts that
values of $y$ for which $s(x,y)$ is small are more likely. Standard examples
of such scoring functions include $s(x,y)\coloneqq-|y-\widehat{\mu}(x)|$ in
regression, where $\widehat{\mu}:\mathcal{X}\to\mathbb{R}$ predicts $y\mid x$;
or $s(x,y)\coloneqq-\log p_{y}(x)$ in multiclass classification, where
$p_{y}(x)$ models the conditional probability of $y\mid x$. Throughout this
section, we adopt a split-conformal perspective [53, 3], assuming the
practitioner provides a scoring function independent of the sample
$(X_{i},\varphi_{i},Y^{\textup{weak}}_{i})_{i=1}^{n}$ (the sample would
typically be a _validation set_), and we show how to transform any such
scoring function into a valid (weakly-covering) confidence mapping.

Algorithm 1 starts from a simple observation, assuming that the scoring
function $s$ is relatively good. Given a query function $\varphi$ and weak
label $Y^{\textup{weak}}$—equivalently, the weak set
$W=\\{y\mid\varphi(y)=Y^{\textup{weak}}\\}$—the most likely label should
typically be the $y$ satisfying $\varphi(y)=Y^{\textup{weak}}$ minimizing
$s(x,y)$.

Algorithm 1 Partially supervised conformalization

Input: sample $\\{(X_{i},Y^{\textup{weak}}_{i},\varphi_{i})\\}_{i=1}^{n}$;
score function $s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ independent of
the sample; desired coverage $1-\alpha\in(0,1)$

For each $i\in[n]$, compute  $\displaystyle
S_{i}\coloneqq\min_{y:~{}\varphi_{i}(y)=Y^{\textup{weak}}_{i}}s(X_{i},y).$ (5)

Set $\widehat{t}_{n}\coloneqq(1+n^{-1})(1-\alpha)\text{-quantile
of}~{}\\{S_{i}\\}_{i=1}^{n}$.

Return: predictive set mapping
$\widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y}$ defined by
$\widehat{C}_{n}(x)\coloneqq\left\\{y\in\mathcal{Y}\mid
s(x,y)\leq\widehat{t}_{n}\right\\}.$

Note that a completely equivalent scheme to the scores (5) with label mappings
$\varphi$ and weak labels $Y^{\textup{weak}}_{i}$ uses weak sets $W_{i}$,
where we replace the scores (5) with

$S_{i}\coloneqq\min_{y\in W_{i}}s(X_{i},y).$

In either case, Algorithm 1 achieves valid coverage weak (3):

######  Theorem 2.

Let $(X_{i},Y_{i},\varphi_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P$ and $Y^{\textup{weak}}_{i}=\varphi_{i}(Y_{i})$ for
$i\in[n+1]$. Then Algorithm 1 returns a confidence set mapping satisfying

$\displaystyle\mathbb{P}\left[\text{There exists
}y\in\widehat{C}_{n}(X_{n+1})~{}s.t~{}\varphi_{n+1}(y)=\varphi_{n+1}(Y_{n+1})=Y^{\textup{weak}}_{n+1}\right]\geq
1-\alpha.$

Proof Let
$S_{i}\coloneqq\min_{\varphi_{i}(y)=Y^{\textup{weak}}_{i}}s(X_{i},y)$ for each
$i\in[n+1]$. By definition of $\widehat{C}_{n}$, we have

$\displaystyle\left\\{y\in\widehat{C}_{n}(X_{n+1})\mid\varphi_{n+1}(y)=Y^{\textup{weak}}_{n+1}\right\\}=\left\\{y\in\mathcal{Y}\mid\varphi_{n+1}(y)=Y^{\textup{weak}}_{n+1}\text{
and }s(X_{n+1},y)\leq\widehat{t}_{n}\right\\},$

which is nonempty if and only if

$\displaystyle
S_{n+1}\coloneqq\min_{\varphi_{n+1}(y)=Y^{\textup{weak}}_{n+1}}s(X_{n+1},y)\leq\widehat{t}_{n}.$

As $\\{S_{i}\\}_{i=1}^{n+1}$ are i.i.d., this occurs with probability at least
$1-\alpha$ [e.g. 47, Lemma 1]. ∎

##  3 Constructing effective conformal prediction sets

Algorithm 1 provides a generic method for conformalization in the presence of
partially supervised data, and it makes no assumptions on the input score
function $s$. Though the coverage guarantee (3) holds regardless, we can
delineate a few additional desiderata that the predictive sets and score
functions $s$ should satisfy to make them more practically useful, which is
our focus in this section:

  * •

The score function $s$ must allow the practitioner to efficiently carry out
the computation of the partial infimum scores (5).

  * •

The lower level sets $\widehat{C}_{n}(x)=\\{y\in\mathcal{Y}\mid
s(x,y)\leq\widehat{t}_{n}\\}$ should be efficiently representable.

  * •

The confidence sets $\widehat{C}_{n}(x)$ should be small, as smaller
confidence sets (for a fixed confidence level $\alpha$) carry more
information.

Deferring our discussion of computational efficiency to Section 4, in this
section we only focus on the last desideratum, implicitly assuming computation
is tractable (e.g., if $\mathcal{Y}$ is small). We first (Sec. 3.1) develop
conditions sufficient for optimally-sized confidence sets to even exist—a few
subtleties arise—before giving greedy algorithms for confidence set-size
minimization, describing their properties, and providing a few optimality
guarantees in Sections 3.2 and 3.3.

###  3.1 Size-optimal scoring mechanism

As in standard approaches to conformal inference [30, 31, 3], we aim to
construct a confidence set mapping $\widehat{C}_{n}$ with minimal average size
over $X\sim P_{X}$. Our starting point is simply to define size-optimality,
where to achieve exact coverage and size guarantees, we allow randomization of
our confidence sets via an independent variable $U\sim\mathsf{Uni}[0,1]$.

######  Definition 3.1.

A randomized confidence set mapping
$C_{1-\alpha}:\mathcal{X}\times[0,1]\rightrightarrows\mathcal{Y}$ is
_marginally size-optimal_ at level $\alpha$ if it solves

$\begin{split}\mathop{\rm
minimize}_{C:\mathcal{X}\times[0,1]\rightrightarrows\mathcal{Y}}&~{}\mathbb{E}_{X,U\sim\mathsf{Uni}[0,1]}\left[|C(X,U)|\right]\\\
\mathop{\rm subject\;to}&~{}\mathbb{P}(W\cap C(X,U)\neq\emptyset)\geq
1-\alpha.\end{split}$ (Marg)

It is _conditionally size-optimal_ at level $\alpha$ if for almost every
$x\in\mathcal{X}$, $C(x,\cdot)$ solves

$\displaystyle\mathop{\rm
minimize}_{C:[0,1]\rightrightarrows\mathcal{Y}}~{}\left\\{\mathbb{E}_{U\sim\mathsf{Uni}[0,1]}\left[|C(U)|\right]~{}\mbox{s.t.}~{}~{}\mathbb{P}(W\cap
C(U)\neq\emptyset\mid X=x)\geq 1-\alpha\right\\}.$ (Cond)

Even with full knowledge of the distribution $P$, techniques for finding
marginally size-optimal confidence sets (Marg) are not immediately apparent;
as a consequence, we focus on the conditional case first. Even in this case,
it is in general non-trivial to obtain smallest confidence sets. Yet as we
follow the standard practice [3, 30, 53] in conformal prediction of defining
confidence sets via the scores $s$ (recall Alg. 1) as $C_{t}(x)=\\{y\mid
s(x,y)\leq t\\}$, our confidence sets have the natural nesting property that
$C_{t}(x)\subset C_{t^{\prime}}(x)$ whenever $t<t^{\prime}$. Abstracting away
the particular form of $C$ to enable a purely set-based focus, we thus
consider nested confidence sets, where we show that optimality guarantees are
possible.

######  Definition 3.2.

A collection of mappings
$\\{C_{\eta}:\mathcal{X}\times[0,1]\rightrightarrows\mathcal{Y}\\}_{\eta\in(0,1)}$
is _nested_ if

$P(C_{\eta_{1}}(X,U)\subset C_{\eta_{2}}(X,U))=1~{}\text{for
all}~{}0<\eta_{1}<\eta_{2}<1.$

There is an immediate equivalence between score-based conformalization schemes
and nested collections of confidence mappings [cf. 21]: we simply define

$\displaystyle s^{\textup{nest}}(x,y,u)\coloneqq\inf\left\\{\eta\in(0,1)\mid
y\in C_{\eta}(x,u)\right\\}.$ (6)

The next lemma formalizes this equivalence (see Appendix A.2.1 for a proof).

######  Lemma 3.1.

Assume the confidence set mappings $\\{C_{\eta}\\}_{\eta\in(0,1)}$ are nested
and $s^{\textup{nest}}(x,y,U)$ has continuous distribution for
$U\sim\mathsf{Uni}[0,1]$. Then

$\displaystyle C_{\eta}(x,U)=\left\\{y\in\mathcal{Y}\mid
s^{\textup{nest}}(x,y,U)\leq\eta\right\\}~{}~{}\mbox{with~{}}U\mbox{-probability}~{}1.$

That is, obtaining weak coverage for nested confidence mappings is equivalent
to obtaining weak coverage using the scoring function $s^{\textup{nest}}$,
which Alg. 1 provides, that is, equivalent to choosing the smallest
$\eta\in(0,1)$ such that $\mathbb{P}(W\cap C_{\eta}(X,U)\neq\emptyset)\geq
1-\alpha$. A second useful distributional property of the nested scores (6) is
that, assuming the confidence sets $C_{\eta}$ are conditionally valid, we can
provide strong distributional results on $s^{\textup{nest}}$. To make this
precise, we say that $C_{\eta}$ is _conditionally valid for the weak labels
$W$_ if for each $\eta\in(0,1)$ and with $\mathbb{P}$-probability $1$ over
$X$,

$\mathbb{P}\left(C_{\eta}(x,U)\cap W\neq\emptyset\mid X=x\right)=\eta.$ (7)

We then have the following uniformity property as an immediate consequence of
Lemma 3.1:

######  Lemma 3.2.

In addition to the conditions of Lemma 3.1, assume that $C_{\eta}$ is
conditionally valid (7) for the weak label $W$. Then the minimum score (5) is
independent of $X$ and satisfies

$\displaystyle\inf_{y\in W}s^{\textup{nest}}(x,y,U)\sim\mathsf{Uni}[0,1].$

Proof With $U$-probability 1, $\inf_{y\in W}s^{\textup{nest}}(x,y,U)\leq\eta$
if and only if $C_{\eta}(x,U)\cap W\neq\emptyset$, and so
$\mathbb{P}(\inf_{y\in W}s^{\textup{nest}}(x,y,U)\leq\eta\mid
X=x)=\mathbb{P}(W\cap C_{\eta}(x,U)\neq\emptyset\mid X=x)=\eta$. ∎

To illustrate this lemma, suppose that there exist nested conditionally size-
optimal mappings $\\{C^{\textup{cond}}_{\eta}\\}_{\eta\in(0,1)}$ solving
problem (Cond): in that case, they satisfy the conditions for application of
Lemma 3.2 so that the induced scores $S_{i}$ are uniform; Alg. 1 will thus
compute $\widehat{t}_{n}=(1-\alpha)+O_{P}(n^{-1/2})$ as $\widehat{t}_{n}$ is
the $(1-\alpha)$ quantile of $S_{i}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\mathsf{Uni}[0,1]$. So—in the case that we have (near)
conditional coverage—Alg. 1 maintains it. Notably, given a score function $s$,
not necessarily the nested score (6), but strong in the sense that it models
$(X,Y)$ well enough that for each $\alpha$, we can choose $t$ so that
$\mathbb{P}(s(x,Y)\leq t\mid X=x)=\alpha$, then the confidence sets Algorithm
1 returns are indeed nested, and Lemma 3.2 applies to the induced nested score
$s^{\textup{nest}}$. Unfornately, optimal nested sets need not always exist
(see Example 2 below), but we can provide natural conditions on the
distribution of $W\mid X=x$ sufficient to allow such nested coverage, which we
do in the next subsection.

####  3.1.1 From conditionally to marginally valid confidence sets

Our initial criterion (Marg) is purely marginal: we wish to compute a
marginally size-optimal confidence set. Conveniently, conditionally size-
optimal mappings can yield marginally size-optimal problems. In particular,
assume that the mappings $\\{C^{\textup{cond}}_{\eta}\\}_{\eta\in(0,1)}$ are
conditionally size-optimal (Cond) and satisfy $\mathbb{P}(W\cap
C^{\textup{cond}}(x,U)\neq\emptyset\mid X=x)\geq\eta$. The following
proposition shows how to transform these into marginally size-optimal
confidence sets.

######  Proposition 1.

Let the mappings $\\{C^{\textup{cond}}_{\eta}\\}$ be conditionally size-
optimal (Cond) as above, and define the average
$\textup{size}(x,\eta)\coloneqq\mathbb{E}_{U}[|C^{\textup{cond}}_{\eta}(x,U)|]$.
Let $s_{\textup{marg}}$ be any minimizer of

$\displaystyle\mathbb{E}\left[\textup{size}(X,s(X))\right]~{}~{}\mbox{s.t.
}~{}~{}\mathbb{E}[s(X)]\geq 1-\alpha$

over $s:\mathcal{X}\to[0,1]$. Then a solution to the initial marginal problem
(Marg) is

$\displaystyle C^{\textup{marg}}_{1-\alpha}(x,u)\coloneqq
C^{\textup{cond}}_{s_{\textup{marg}}(x)}(x,u).$

More directly, any conditionally size-optimal sets—which are at least easier
to _characterize_ as they need only randomize over
$U\sim\mathsf{Uni}[0,1]$—yield marginally size-optimal confidence sets in a
relatively straightforward way: one chooses the probability of miscoverage,
$s(x)$, minimizing the expected confidence set size.

Proof That $C^{\text{Marg}}_{1-\alpha}$ provides valid $1-\alpha$ coverage is
nearly immediate: by conditional size optimality, we have $\mathbb{P}(W\cap
C^{\text{marg}}_{1-\alpha}(X,U)\neq\emptyset)=\mathbb{E}[t_{\textup{marg}}(X)]\geq
1-\alpha$.

Let $C$ be any confidence set mapping such that $\mathbb{P}(W\cap
C(X,U)\neq\emptyset)\geq 1-\alpha$, and define
$s_{C}(x)\coloneqq\mathbb{P}(W\cap C(x,U)\neq\emptyset\mid X=x)\in[0,1]$,
which satisfies $\mathbb{E}[s_{C}(X)]\geq 1-\alpha$. By assumption on
$C^{\textup{cond}}$, for each fixed $x\in\mathcal{X}$, the set
$C^{\textup{cond}}_{s_{C}(x)}(x,U)$ is size-optimal (Cond) at level
$s_{C}(x)$, so that for $P_{X}$-almost every $x\in\mathcal{X}$, we have

$\displaystyle\textup{size}(x,s_{C}(x))=\mathbb{E}_{U\sim\mathsf{Uni}[0,1]}\left[|C^{\textup{cond}}_{s_{C}(x)}(x,U))|\right]\leq\mathbb{E}_{U\sim\mathsf{Uni}[0,1]}\left[|C(x,U)|\right].$

Integrating both sides of the inequality over $X\sim P_{X}$, and using the
assumed optimality condition on $s_{\textup{marg}}$, we obtain

$\displaystyle\mathbb{E}\left[\textup{size}(X,s_{\textup{marg}}(X))\right]\leq\mathbb{E}\left[\textup{size}(X,s_{C}(X))\right]\leq\mathbb{E}_{X,U}\left[|C(X,U))|\right].$

The left-hand size is the average size of $C^{\textup{margin}}_{1-\alpha}$. ∎

###  3.2 Greedy algorithms for confidence set-size minimization

Given the distribution—or a model of the distribution—of the weak set $W$
conditional on $x$, we propose a natural greedy algorithm to construct a
confidence set satisfying the weak coverage constraint: at each step,
Algorithm 2 adds the label that increases coverage the most until the
confidence set achieves a desired level. As we show presently, there are
natural families of distributions where this greedy algorithm is optimal;
however, there are failure modes, of which we also provide an example. In
Section 3.3, we relate this greedy construction to submodular optimization to
provide general guarantees of confidence set size and coverage.

Algorithm 2 Greedy weakly supervised scoring mechanism

Input: model for the distribution of $W$ given $X=x$; coverage rate
$\eta\in(0,1)$

for each $j\in[K]$ define recursively  $y_{j}(x)\coloneqq\mathop{\rm
argmax}_{y\in\mathcal{Y}}\,P\\!\left(y\in
W,\,\bigcap_{i=1}^{j-1}\\{y_{i}(x)\not\in W\\}\mid X=x\right).$

for each $j\in[K]$ define $C^{\textup{gr},{j}}(x)\coloneqq\\{y_{i}(x)\mid
i\leq j\\}$ and set $\displaystyle j(x,\eta)\coloneqq\min\left\\{j\in[K]\mid
P\left(W\cap C^{\textup{gr},{j}}(x)\neq\emptyset\mid
X=x\right)\geq\eta\right\\}.$

set $\displaystyle
t_{\eta}(x)\coloneqq\dfrac{\eta-P(C^{\textup{gr},{j(\eta,x)-1}}(x,U)\cap
W\neq\emptyset\mid X=x)}{P(C^{\textup{gr},{j(x,\eta)}}(x,U)\cap
W\neq\emptyset\mid X=x)-P(C^{\textup{gr},{j(x,\eta)-1}}(x,U)\cap
W\neq\emptyset\mid X=x)}.$

return function
$C^{\textup{gr}}_{\eta}:\mathcal{X}\times[0,1]\rightrightarrows\mathcal{Y}$
defined by  $\displaystyle
C^{\textup{gr}}_{\eta}(x,u)\coloneqq\begin{cases}C^{\textup{gr},{j(x,\eta)}}(x)&\mbox{if
}u<t_{\eta}(x),\\\
C^{\textup{gr},{j(x,\eta)-1}}(x)&\mbox{otherwise.}\end{cases}$

Alg. 2 returns a nested sequence
$\\{C^{\textup{gr}}_{\eta}(x,U)\\}_{\eta\in(0,1)}$, where
$U\sim\mathsf{Uni}[0,1]$ randomizes to achieve an appropriate level. While the
sequence need not necessarily solve problem (Cond) (see Example 2 to come),
there are natural sufficient conditions for Algorithm 2 to return a size-
optimal set, of which we present two. As the first particular case, consider
that conditional on $x$, labels $y\in\mathcal{Y}$ belong to $W$ independently:

######  Definition 3.3.

A probability distribution $P$ on $W\in 2^{\mathcal{Y}}$ has _label-
independent structure_ if $\\{1\\!\left\\{y\in
W\right\\}\\}_{y\in\mathcal{Y}}$ are independent random variables when $W\sim
P$.

We might expect $W$ to exhibit label independence when all labels
$y\in\mathcal{Y}$ satisfy $\pi(y\mid x)\ll 1$, with the exception of a single
label $y^{\star}(x)$, for which $\pi(y^{\star}(x)\mid x)\approx 1$, as will
often be the case in low-noise classification settings.

Another scenario occurs when the label space exhibits a hierarchical tree
structure, as one may expect in image classification [12] or structured
prediction tasks [6]. When the weak sets $W$ obey the same structure the
distribution—they are subtrees of the global tree—we say the labels have a
tree structure (see Figure 1):

######  Definition 3.4.

A probability distribution $P$ on $W\in 2^{\mathcal{Y}}$ has a _tree
structure_ if for all $w_{1},w_{2}\subset\mathcal{Y}$,

$\displaystyle
P(W=w_{1})>0~{}\text{and}~{}P(W=w_{2})>0~{}\text{imply}~{}w_{1}\cap
w_{2}\in\\{w_{1},w_{2},\emptyset\\}.$ (8)

[$\mathcal{Y}^{\star}$ [$W_{0}$ [$W_{1}$ [$y_{1}$] [$y_{3}$] ] [$W_{2}$ [$y_{2}$] [$y_{5}$] ] ] [$y_{4}$] ] |  Figure 1:  A tree-structured (8) distribution for $W$ given $X=x$, with $\mathcal{Y}^{\star}=\\{1,2,3,4\\}$. The possible configurations for $W$ are the singletons $\\{y_{1}\\},\\{y_{2}\\},\\{y_{3}\\},\\{y_{4}\\}$, the two pairs $W_{1}=\\{y_{1},y_{3}\\}$ and $W_{2}=\\{y_{2},y_{5}\\}$, $W_{0}=\\{y_{1},y_{2},y_{3},y_{5}\\}$, and $\mathcal{Y}^{\star}$ itself.
---|---

Both definitions (independent labels and hierarchically-structured weak
labels) are sufficient to guarantee size-optimality for the greedy confidence
sets Algorithm 2 constructs. The next Proposition, whose proof we provide in
Appendix A.2.2, makes this formal.

######  Proposition 2.

Suppose the probability law $\mathcal{L}(W\mid X=x)$ has either label-
independent structure (Def. 3.3) or a tree structure (Def. 3.4). Then for all
$\eta\in(0,1)$, $C^{\textup{gr}}_{\eta}$ is conditionally size-optimal, and
therefore is a minimizer in equation (Cond).

In general, even with perfect knowledge of the distribution of $W\mid X=x$,
the nested greedy confidence sets $C^{\textup{gr}}_{\eta}$ need not be size-
optimal, as there may be weak sets appearing with high probability while their
constituents do not, so that the conditionally size-optimal sets
$\\{C^{\textup{cond}}_{\eta}\\}_{\eta\in[0,1]}$ are not nested. The next
example illustrates one such failure mode:

Example 1: Let the distribution of $W$ be

$\displaystyle W=\begin{cases}\left\\{1,2\right\\}&\mbox{w.p. }0.3\\\
\left\\{1,3\right\\}&\mbox{w.p. }0.25\\\ \left\\{2\right\\}&\mbox{w.p. }0.2\\\
\left\\{3\right\\}&\mbox{w.p. }0.15\\\ \left\\{1\right\\}&\mbox{w.p. }0.1.\\\
\end{cases}$

Then for $\eta=0.9$, it is immediate that
$C^{\textup{cond}}_{\eta}(x,u)=\\{2,3\\}$, but
$C^{\textup{gr}}_{\eta}(x,u)=\\{1,2,3\\}\text{ or }\\{1,2\\}$ depending on
whether $u<1/3$. In addition,
$C^{\textup{cond}}_{eta^{\prime}}(x,u)=\\{1,3\\}$ when $\eta^{\prime}=0.85$,
showing that in this case, the confidence set mappings
$C^{\textup{cond}}_{\eta}$ need not be nested. $\Diamond$

###  3.3 A general upper bound for the greedy approach

As we saw in the previous section, reasonable conditions on label
distributions guarantee that the greedy mappings
$\\{C^{\textup{gr}}_{\eta}\\}_{\eta\in(0,1)}$ solve problem (Cond), while
pathologies (as in Example 2) exist. In this section, we show that even in
general cases, the sizes of the confidence sets $C^{\textup{gr}}$ and
$C^{\textup{cond}}$ cannot be too far apart. We motivate our approach by
noting the similarity between problem (Cond) and the minimum set cover problem
familiar in submodular optimization [52, 20], which we recall. Let
$f:2^{\mathcal{Y}}\to[0,1]$ be a monotone submodular coverage function,
meaning that for each $A\subset B\subset\mathcal{Y}$ and
$y\in\mathcal{Y}\setminus B$, $f$ satisfies $f(A)\leq f(B)$,
$f(A\cup\\{y\\})-f(A)\geq f(B\cup\\{y\\})-f(B)$, $f(\mathcal{Y})=1$, and
$f(\emptyset)=0$. A solution to the minimum set cover problem is

$\displaystyle C^{\star}_{\eta}\in\mathop{\rm
argmin}_{C\subset\mathcal{Y}}~{}\left\\{|C|~{}\textrm{s.t.}~{}f(C)\geq\eta\right\\}.$
(9)

A classical result combinatorial optimization of Wolsey [54] bounds the size
of the set that a natural greedy algorithm for problem (9) returns. To state
the result, we introduce a bit of notation. For any set $C\subset\mathcal{Y}$
and $y\in\mathcal{Y}$, we define

$\displaystyle\Delta(C,y)\coloneqq f(C\cup\\{y\\})-f(C),$

increase in coverage from adding $y$ to $C$. At each step $j\in[K]$, the
greedy algorithm chooses

$\displaystyle y_{j}\coloneqq\mathop{\rm
argmax}_{y\in\mathcal{Y}}\Delta(\\{y_{1}\dots,y_{j-1}\\},y),$

and stops at the first step $j(\eta)\leq K$ such that
$f(\\{y_{1},\ldots,y_{j(\eta)}\\})\geq\eta$. For the greedy set
$C^{\textup{gr},{j}}\coloneqq\\{y_{1},\dots,y_{j}\\}$, define the constant

$\displaystyle K_{f,\eta}\coloneqq\min\Bigg{\\{}$
$\displaystyle\frac{\eta}{\eta-f(C^{\textup{gr},{j(\eta)-1}})},$
$\displaystyle\max_{\begin{subarray}{c}y\in\mathcal{Y},\,j\leq j(\eta)\\\
\Delta(C^{\textup{gr},{j}},y)>0\end{subarray}}\Bigg{(}\frac{\Delta(\emptyset,y)}{\Delta(C^{\textup{gr},{j}},y)}\Bigg{)},\frac{\max_{y\in\mathcal{Y}}\Delta(\emptyset,y)}{\max_{y\in\mathcal{Y}\setminus
C^{\textup{gr},{j(\eta)-1}}}\Delta(C^{\textup{gr},{j(\eta)-1}},y)}\Bigg{\\}}.$

We then have the following result.

######  Lemma 3.3 (Wolsey [54], Theorem 1).

Let $f:2^{\mathcal{Y}}\to[0,1]$ be a monotone submodular coverage function.
Then

$\displaystyle|C^{\textup{gr},{j(\eta)}}|\leq\Big{(}1+\log
K_{f,\eta}\Big{)}\cdot|C^{\star}_{\eta}|$

Given the apparent similarity between the problems (9) and (Cond), we would
like to leverage Lemma 3.3 to establish a similar guarantee for Alg. 2. To
apply Lemma 3.3 to Alg. 2, we provide the natural analogous quantities,
leveraging the notation in the algorithm and working conditional on $X=x$.
Define $f_{x}(C)\coloneqq P(W\cap C\neq\emptyset\mid X=x)$, which is
immediately a submodular coverage function, and for each $x$ we have increment
function $\Delta_{x}(C,y)=P(W\cap C=\emptyset,y\in W\mid X=x)$. Because the
greedy sets $C^{\textup{gr}}_{\eta}(x,u)$ may be randomized but always satisfy
$C^{\textup{gr}}_{\eta}(x,1)\subset C^{\textup{gr}}_{\eta}(x,0)$, we provide a
slight alternative to the constant $K_{f,\eta}$, defining

$\displaystyle K_{P,\eta,x}\coloneqq\min\Bigg{\\{}$
$\displaystyle\frac{\eta}{\eta-P(W\cap
C^{\textup{gr}}_{\eta}(x,1)\neq\emptyset\mid X=x)},$ (10)
$\displaystyle\max_{\begin{subarray}{c}y\in\mathcal{Y},\,j\leq j(x,\eta)\\\
\Delta_{x}(C^{\textup{gr},{j}}(x),y)>0\end{subarray}}\left(\frac{\Delta_{x}(\emptyset,y)}{\Delta_{x}(C^{\textup{gr},{j}}(x),y)}\right),\frac{\max_{y\in\mathcal{Y}}\Delta(\emptyset,y)}{\max_{y\in\mathcal{Y}}\Delta(C^{\textup{gr}}_{\eta}(x,1),y)}\Bigg{\\}}.$

Invoking Lemma 3.3 and simplifying gives the following result, which bounds
the size of the greedy set by a logarithmic quantity times the size of the
best (deterministic) covering set.

######  Corollary 3.1.

Let
$C^{\textup{gr}}_{\eta}:\mathcal{X}\times[0,1]\rightrightarrows\mathcal{Y}$ be
the confidence set mapping Algorithm 2 outputs. Then for all $x\in\mathcal{X}$
and $u\in[0,1]$,

$\displaystyle|C^{\textup{gr}}_{\eta}(x,u)|\leq|C^{\textup{gr}}_{\eta}(x,0)|$
$\displaystyle\leq\Big{(}1+\log
K_{P,\eta,x}\Big{)}\cdot\min_{C\subset\mathcal{Y}}\left\\{|C|~{}\mbox{s.t.}~{}P(W\cap
C\neq\emptyset\mid x)\geq\eta\right\\}.$

We can roughly interpret the three terms inside the minimum in (10) as
follows. The first term is large when the greedy algorithm nearly attains the
required coverage on the iteration just before terminating, and therefore
measures (in a sense) how “wasteful” the algorithm is. The second term is
large when choosing a label earlier would have improved the coverage more, and
so expresses a kind of regret. The third term measures how often the labels
$y\in\mathcal{Y}$ co-occur in $W$. Though the bound is a functional of the
discrete derivative $\Delta_{x}(C,y)$ and small when the “local” information
in $\Delta_{x}(C,y)$ gives good indicators of globally optimal sets $C$, it
can be hard to compute explicitly; we therefore evaluate the size of the sets
that Alg. 2 generates for a few experimental examples in Section 5.

##  4 Efficient conformalization for large output spaces

While Section 3 provides a generic treatment on for producing scoring
functions and associated confidence sets of minimal size, in typical practice,
a (pre-trained) model provides a predictive scoring function, which may not be
directly associated to a probability metric, and we wish to leverage such
models. This is of particular interest when the label space $\mathcal{Y}$ is
large, as in structured prediction problems [45, 6], where computational
efficiency becomes a main challenge. In this section, we thus first introduce
a general method for computing and representing confidence set mappings of the
form $\\{y\mid s(x,y)\leq\hat{t}_{n}\\}$, and then describe how to efficiently
carry out Alg. 1 in ranking and matching problems.

###  4.1 Conformal confidence sets with sequential partitioning

We seek to efficiently compute and represent the confidence set
$\widehat{C}_{n}(x)$ for any instance $x\in\mathcal{X}$, typically for a task
where the label space contains more configurations than are efficiently
enumerable ($K!$ for matching and ranking problems over $K$ items). At the
same time, recalling that $\widehat{t}_{n}$ denotes the threshold Algorithm 1,
if our confidence sets are to be informative they should include relatively
few configurations $y\in\mathcal{Y}$ satisfying $s(x,y)\leq\widehat{t}_{n}$.
To the end of computing the set $\widehat{C}_{n}(x)=\\{y\mid
s(x,y)\leq\widehat{t}_{n}\\}$ in Alg. 1, we focus on methods for computing a
given number $M$ of configurations with the smallest score $s(x,y)$. This is
essentially without loss of generality: while we may not know the appropriate
$M=M_{x}=|\widehat{C}_{n}(x)|$ to guarantee coverage, if for each
$M\in\mathbb{N}$ we can find the $M$ best configurations in time polynomial in
$M$, then by sequentially doubling $M$ until we obtain an element
$y\in\mathcal{Y}$ such that $s(x,y)>\widehat{t}_{n}$, we achieve time
polynomial in $M_{x}$. Algorithm 3 builds on this intuition to return a valid
confidence set.

We remark briefly that an alternative approach is to conformalize directly on
the size $M$ of the confidence set: suppose we learn a function
$\widehat{M}:\mathcal{X}\to\mathbb{N}$ predictive of the rank (according to
$\\{s(x,y)\\}_{y\in\mathcal{Y}}$) of the first “compatible” configuration, i.e
predictive of

$\displaystyle M_{i}\coloneqq\text{rank of the first
configuration}~{}y\in\mathcal{Y}~{}\text{such
that}~{}\varphi_{i}(y)=Y_{i}^{\textup{weak}}.$

In that case, if we let
$\widehat{Q}_{n}\coloneqq\left(1+n^{-1}\right)\left(1-\alpha\right)\text{-quantile
of}~{}\\{M_{i}-\widehat{M}(X_{i})\\}_{i=1}^{n},$ we would only need to return

$\displaystyle\widehat{C}_{n}(x)\coloneqq\left\\{\widehat{M}(x)+\widehat{Q}_{n}~{}\text{best
configurations}~{}y\in\mathcal{Y}~{}\text{ordered by}~{}s(x,y)\right\\}.$

This approach makes prediction more efficient (as we know in advance the
number of configurations to compute), but the computational effort of the
conformalization step (5) increases, as we must compute the rank of the best
constrained configuration for each instance.

####  4.1.1 Returning $M$ best configurations with sequential partitioning

PartitionUpdate$\mathcal{Y}_{1}^{3}$$\mathcal{Y}_{2}^{3}$$\mathcal{Y}_{3}^{3}$$\mathcal{Y}_{2}^{4}$$\mathcal{Y}_{1}^{4}$$\mathcal{Y}_{4}^{4}$$\mathcal{Y}_{3}^{4}$$y_{1}$$y_{2}$$y_{2,2}^{3}$$y_{1,2}^{3}$$y_{3,2}^{3}$$y_{3}$$y_{1}$$y_{1,2}^{3}$$y_{3,2}^{3}$$y_{3}$$y_{2}$$y_{2,2}^{3}=y_{4}$$y_{1}$$y_{1,2}^{4}$$y_{3,2}^{4}$$y_{3}$$y_{2}$$y_{4}$$y_{4,2}^{4}$$y_{2,2}^{4}$
Figure 2: Alg. 3 scheme for sequential partitioning: first, partition the
subset containing the $m+1$-th best configuration, $y_{2,2}^{3}$ in this case,
then compute both second-best configurations in the newly formed subsets of
the partition—here $\mathcal{Y}_{2}^{4}$ and $\mathcal{Y}_{4}^{4}$.

Let us now fix $M\geq 1$, and focus on retrieving the $M$ configurations with
the lowest scores. Algorithm 3 provides a general recipe using dynamic
programming, and it is efficient as long as we can efficiently compute certain
partitions of the label space. We require the following definition.

######  Definition 4.1.

A function
$\textsc{Partition}:2^{\mathcal{Y}}\times\mathcal{Y}\times\mathcal{Y}\to
2^{\mathcal{Y}}\times 2^{\mathcal{Y}}$ is _valid for a score function_ $s$ if,
for every subset $\tilde{\mathcal{Y}}\subset\mathcal{Y}$ and pair of
configurations $y_{1},y_{2}\in\tilde{\mathcal{Y}}$ satisfying

$\displaystyle y_{1}\in\mathop{\rm
argmin}_{y\in\tilde{\mathcal{Y}}}s(x,y)~{}~{}\mbox{and}~{}~{}y_{2}\in\mathop{\rm
argmin}_{y\in\tilde{\mathcal{Y}}\setminus\\{y_{1}\\}}s(x,y),$

Partition$(\tilde{\mathcal{Y}},y_{1},y_{2})$ returns a partition
$(\tilde{\mathcal{Y}}_{1},\tilde{\mathcal{Y}}_{2})$ of $\tilde{\mathcal{Y}}$
such that $y_{1}\in\tilde{\mathcal{Y}}_{1}$ and
$y_{2}\in\tilde{\mathcal{Y}}_{2}$.

We thus leverage two conditions: a valid Partition for our score function $s$
and, for each pair of subsets
$\mathcal{Y}_{1},\mathcal{Y}_{2}\subset\mathcal{Y}$ that it produces, we must
be able to (efficiently) compute the second-best configurations in
$\mathcal{Y}_{1}$ and $\mathcal{Y}_{2}$, i.e.,

$\displaystyle y_{1,2}\in\mathop{\rm
argmin}_{y\in\mathcal{Y}_{1}\setminus\\{y_{1}\\}}s(x,y)~{}~{}\text{and}~{}~{}y_{2,2}\in\mathop{\rm
argmin}_{y\in\mathcal{Y}_{2}\setminus\\{y_{2}\\}}s(x,y).$

Figure 2 encapsulates the main idea Alg. 3: at each step $m\in[M]$, we
maintain a partition $\\{\mathcal{Y}_{j}^{m}\\}_{j=1}^{m}$ of $\mathcal{Y}$
such that if $y_{j}^{m}\in\mathop{\rm
argmin}_{y\in\mathcal{Y}_{j}^{m}}s(x,y),$ then for all $j\in[m]$, we have

$\displaystyle y_{j}^{m}\in\mathop{\rm
argmin}_{y\in\mathcal{Y}\setminus\\{y_{1}^{m},\dots,y_{j-1}^{m}\\}}s(x,y),$

i.e., $y_{j}^{m}$ is the $j$-th best configuration in $\mathcal{Y}$. Now, for
each $j\in[m]$, let the configuration $y_{j,2}^{m}\in\mathop{\rm
argmin}_{y\in\mathcal{Y}_{j}^{m}\setminus\\{y_{j}^{m}\\}}s(x,y)$ be the
second-best configuration in $\mathcal{Y}_{j}^{m}$. The key is then to observe
that if we set

$\displaystyle\text{ind}(m)\coloneqq\mathop{\rm
argmin}_{j\in[m]}s(x,y_{j,2}^{m}),$

then $y_{\text{ind}(m),2}^{m}$ is the $(m+1)$st best configuration in
$\mathcal{Y}$. The Partition function then divides
$\mathcal{Y}_{\text{ind}(m)}^{m}$ into two sets
$\mathcal{Y}_{\text{ind}(m)}^{m+1}$ and $\mathcal{Y}_{m+1}^{m+1}$ such that
$y_{\text{ind}(m)}^{m}\in\mathcal{Y}_{\text{ind}(m)}^{m+1}$ and
$y_{\text{ind}(m),2}^{m}\in\mathcal{Y}_{m+1}^{m+1}$. Under the assumption that
Partition is valid (Def. 4.1) for the score $s$, the following lemma
guarantees the validity of Algorithm 3.

Algorithm 3 Sequential partitioning

0: score function $s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$; valid (Def.
4.1) Partition: $2^{\mathcal{Y}}\times\mathcal{Y}\times\mathcal{Y}\to
2^{\mathcal{Y}}\times 2^{\mathcal{Y}}$; instance $x\in\mathcal{X}$

initialize: Compute $y_{1}^{1}\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}}s(x,y)$ and $y_{1,2}^{1}\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}\setminus\\{y_{1}^{1}\\}}s(x,y)$.

Set $\mathcal{Y}^{m}_{1}\coloneqq\mathcal{Y}$ {Initialize the partition}

for $m=1,2,\ldots,M-1$ do

$\text{ind}(m)\coloneqq\mathop{\rm argmin}_{j\in[m]}s(x,y_{j,2}^{m})$ {Find
the $m+1$-th best configuration}

$y_{m+1}^{m+1}\coloneqq y_{\text{ind}(m),2}^{m}$

for $j\in[m]\setminus\\{\text{ind}(m)\\}$ do

$(\mathcal{Y}^{m+1}_{j},y_{j}^{m+1},y_{j,2}^{m+1})\coloneqq(\mathcal{Y}^{m}_{j},y_{j}^{m},y_{j,2}^{m})$
{All subsets $\\{\mathcal{Y}^{m}_{j}\\}_{j\neq\text{ind}(m)}$ remain
identical}

end for

$\mathcal{Y}^{m+1}_{\text{ind}(m)},\mathcal{Y}^{m+1}_{m+1}\coloneqq\textsc{Partition}(\mathcal{Y}^{m}_{\text{ind}(m)},y_{\text{ind}(m)}^{m},y_{m+1}^{m+1})$
{Update the partition for $\mathcal{Y}^{m}_{\text{ind}(m)}$}

$y_{\text{ind}(m)}^{m+1}\coloneqq y_{\text{ind}(m)}^{m}$ and
$y_{\text{ind}(m),2}^{m+1}\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}^{m+1}_{\text{ind}(m)}\setminus\\{y_{\text{ind}(m)}^{m+1}\\}}s(x,y)$

$y_{m+1,2}^{m+1}\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}^{m+1}_{m+1}\setminus\\{y_{m+1}^{m+1}\\}}s(x,y)$
{Compute second-best configurations}

end for

return $\\{y_{m}^{M}\\}_{m=1}^{M}$

######  Lemma 4.1.

Assume the Partition function is valid for the score function $s$. Then
Algorithm 3 returns a set of configurations $\\{y_{j}\\}_{j=1}^{M}$ such that
for each $j\in[M]$,

$\displaystyle y_{j}\in\mathop{\rm
argmin}_{y\in\mathcal{Y}\setminus\\{y_{1},\dots,y_{j-1}\\}}s(x,y).$

Proof This follows by an induction over $m\geq 1$, which guarantees that at
every step $m\geq 1$, $\\{\mathcal{Y}_{j}^{m}\\}$ is a partition of
$\mathcal{Y}$ such that $y_{j}^{m}=\mathop{\rm
argmin}_{y\in\mathcal{Y}_{j}^{m}}$ and

$\displaystyle s(x,y_{1}^{m})\leq s(x,y_{2}^{m})\dots\leq
s(x,y_{m}^{m})\leq\min_{y\in\mathcal{Y}\setminus\\{y_{j}^{m}\\}}s(x,y).$

The property transitions from $m$ to $m+1$ as the Partition function is valid,
and we choose $y_{m+1}^{m+1}$ as the best second-best configuration, hence it
is the $(m+1)$st best configuration. ∎

The existence of an efficient valid Partition function is instance-dependent
and typically requires a specific choice of scoring function; we provide
concrete implementations for two types of structured prediction problems.

###  4.2 Two structured prediction examples

While Algorithm 3 is generic, we now show that efficient partitioning and
minimization functions exist in two structured prediction instances, so that
we may efficiently carry out both Algs. 1 and 3 in the instance.

####  4.2.1 Perfect matching scores and weak supervision

A matching task consists of trying to optimally pair elements of a bipartite
graph given a feature vector $x\in\mathcal{X}$ (for example, one may wish to
identify paired amino acids in protein folding [46]). We assume there exists a
bipartite graph $G$ with disjoint sets $U$ and $V$ of $K\geq 1$ nodes; each
label $Y$ is then a perfect matching between $U$ and $V$, i.e., a bijection
$Y\in\mathcal{Y}=\mathfrak{S}(U,V)$. General supervised approaches for perfect
matching problems, such as structured Support Vector Machines [49] or
Adversarial Bipartite Matching [16], generally learn pairwise score functions
$\varphi_{u,v}:\mathcal{X}\to\mathbb{R}$ for all $(u,v)\in U\times V$, which
measure the cost of adding the edge $e\coloneqq(u,v)$ for a feature vector
$x\in\mathcal{X}$, and then output a prediction

$\displaystyle y^{\star}(x)\coloneqq\left\\{\mathop{\rm
argmin}_{y\in\mathfrak{S}(U,V)}\sum_{u\in U}\varphi_{u,y(u)}(x)=\sum_{u\in
U,v\in V}1\\!\left\\{v=y(u)\right\\}\varphi_{u,v}(x)\right\\},$

an instance of minimum cost perfect matching solvable in time
$\mathcal{O}(K^{3})$ with the Hungarian algorithm.

To efficiently adapt this approach in the context of Alg. 1, we assume we have
trained a set of pairwise score functions $\\{\varphi_{u,v}\mid(u,v)\in
U\times V\\}$, (e.g. using supervised training data) and wish to conformalize
with partially supervised data, using the following score function

$\displaystyle s^{\text{Matching}}(x,y)\coloneqq\sum_{u\in U,v\in
V}1\\!\left\\{v=y(u)\right\\}\varphi_{u,v}(x,y).$ (11)

In a matching problem, weak supervision can arise under the form of a partial
matching between subsets $U_{i}\subset U$ and $V_{i}\subset V$ of the nodes,
which we write $Y_{i}^{\textup{weak}}\in\mathfrak{S}(U_{i},V_{i})$: each $u\in
U_{i}$ has a matching element $Y_{i}^{\textup{weak}}(u)=Y_{i}(u)\in V_{i}$.
Computing the minimum partial scores (5) in Alg. 1 is then computationally
efficient, as it reduces to yet another minimum cost perfect matching problem:

$\displaystyle S_{i}\coloneqq\sum_{u\in
U_{i}}\varphi_{u,Y_{i}^{\textup{weak}}(u)}(x)+\min_{\tilde{y}\in\mathfrak{S}(U\setminus
U_{i},V\setminus V_{i})}\Biggr{\\{}\sum_{\begin{subarray}{c}u\in U\setminus
U_{i}\\\ v\in V\setminus
V_{i}\end{subarray}}1\\!\left\\{v=\tilde{y}(u)\right\\}\varphi_{u,v}(x)\Biggr{\\}}.$

In the matching case, Alg. 3 is equivalent to finding the $M$-best minimal
weight perfect matching in a bipartite graph, which Chegireddy and Hamacher
[9] efficiently solve. In the context of Alg. 3, their approach iteratively
chooses an edge $e_{m}\in y_{\text{ind}(m)}^{m}\setminus
y_{\text{ind}(m),2}^{m}$, then partitions the set of matchings
$\mathcal{M}\in\mathcal{Y}_{\text{ind}(m)}^{m}$ depending on whether
$e_{m}\in\mathcal{M}$ or not. The computation of each second-best
configuration then amounts to solving at most $K$ different perfect matching
problems, resulting in an overall $\mathcal{O}(MK^{4})$ cost of the procedure.

####  4.2.2 Ranking problems and partial labeling mechanisms

Our second structured prediction example addresses partially supervised
ranking tasks. The goal here is to predict a preference ranking
$y\in\mathcal{Y}=\mathfrak{S}_{K}$ of $K$ different items, documents, for a
certain user or query $x\in\mathcal{X}$, where $y(i)$ denotes the item of rank
$i$. Typically, one achieves this by learning relevance functions
$r_{k}:\mathcal{X}\to\mathbb{R}$, which evaluate each item $1\leq k\leq K$
individually before aggregating into a single ranking prediction [19, 14, 37,
7]. We assume here that we have access to such relevance functions.

In ranking tasks, there are two reasonable ways in which practitioners may
acquire partial supervision or user feedback. The first mechanism [6] assumes
they only receive a subset of all $\binom{K}{2}$ pairwise comparisons
$\left(1\\!\left\\{y^{-1}(i)<y^{-1}(j)\right\\}\right)_{1\leq i<j\leq K}$ as a
partial label, which is especially relevant in cases where the practitioner
solicits feedback from users by asking them to compare a small number of
items. Unfortunately, carrying out the computation (5) in Alg. 1 is an NP-hard
problem, namely the minimal cost feedback arc set problem [1, 51], for which
only an approximate solution is available (by solving an integer linear
program).

Another form of feedback, on which we focus in the rest of the section and
that allows to run both Algs. 1 and 3 efficiently, instead assumes that users
only provide a fraction of their preferred ranking and reveal
$\left(y(i)\right)_{i=1}^{K^{\text{partial}}}$ for some
$K^{\text{partial}}\leq K$. In order to construct score functions suitable to
the application of Alg. 3, we first introduce ranking-consistent score
functions.

######  Definition 4.2.

A scoring function $s^{\textup{rank}}$ is _ranking-consistent_ with a set of
relevance functions $\\{r_{k}:\mathcal{X}\to\mathbb{R}\\}_{k\in[K]}$ if a for
all $1\leq i<j\leq K$ and $y\in\mathfrak{S}_{K}$,

$\displaystyle s^{\textup{rank}}(x,(i,j)\circ y))\leq
s^{\textup{rank}}(x,y)~{}\text{if}~{}r_{y(i)}(x)\leq r_{y(j)}(x),$ (12)

where $(i,j)\circ y$ denotes transposition of $i$ and $j$ in the permutation
$y$.

Such a scoring mechanism should always favor a ranking that gives a higher
rank to $y(j)$ than $y(i)$ if $r_{y(i)}(x)\leq r_{y(j)}(x)$, i.e., if $y(j)$
has a greater relevance than $y(i)$. It ensures in particular that the
$(m+1)$st best ranking is always a “neighbor” of one of $m$ best; this is an
immediate property of the score function, as it can always increase by
swapping two elements $i$ and $j$ that are mis-ordered.

An example of ranking-consistent scoring function is the disagreement-based
scoring function [26, 25, 14]

$\displaystyle
s^{\textup{rank}}(x,y)\coloneqq\sum_{i<j}\psi\left(r_{y(i)}(x),r_{y(j)}(x)\right),$
(13)

where $\psi:\mathbb{R}^{2}\to\mathbb{R}\geq 0$ is a function satisfying
$\psi(a,b)=0$ when $a\geq b$ and $\psi(a,b)>0$ when $a<b$, non-increasing in
the first argument and non-decreasing in the second. Unless we specify
otherwise we use $\psi(a,b)=\left[{b-a}\right]_{+}$ in our experiments.

Finding the configuration $y$ that minimizes the partial score (5) of a
ranking-consistent score function is straightforward: it suffices to rank all
the elements in $[K]\setminus\left\\{y(i)\right\\}_{i=1}^{K^{\text{partial}}}$
according to their relevance scores $(r_{j}(x))_{j=1}^{K}$, and then append
them to the first $K^{\text{partial}}$ elements. More interestingly, this
property allows efficiently retrieving the $M\geq 1$ best configurations with
Alg. 3. Throughout the loop, we make sure that any set of permutations
$\mathcal{Y}_{j}^{m}$ is a subset of permutations consistent with a finite
number of partial rankings (pairwise comparisons), and that its best and
second-best configurations $y_{j}^{m}$ and $y_{j,2}^{m}$ only differ by a
neighboring transposition of the form $(i+1,i)$, satisfying

$\displaystyle y_{j,2}^{m}\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}_{j}^{m}}\\{s(x,y)\mid\exists
i\in[K],~{}y=(i+1,i)\circ y_{j}^{m}\\}.$ (14)

If we can guarantee this loop invariant, then there always exists
$i_{j,m}\in[K]$ such that $y_{j,2}^{m}=(i_{j,m}+1,i_{j,m})\circ y_{j}^{m}$,
and we only need to define the partition function on a smaller subset of
$2^{\mathcal{Y}}\times\mathcal{Y}\times\mathcal{Y}$: for any subset of
permutations $\tilde{\mathcal{Y}}\subset\mathcal{Y}$,
$\tilde{y}\in\tilde{\mathcal{Y}}$ and $i\in[K]$ such that
$(i+1,i)\circ\tilde{y}\in\tilde{\mathcal{Y}}$, we let

$\displaystyle\begin{split}&\textsc{Partition}_{\text{Ranking}}(\tilde{\mathcal{Y}},\tilde{y},(i+1,i)\circ\tilde{y})\coloneqq\\\
&~{}~{}~{}\tilde{\mathcal{Y}}\cap\big{\\{}y\in\mathcal{Y}\mid
y^{-1}(\tilde{y}(i))<y^{-1}(\tilde{y}(i+1))\big{\\}},\tilde{\mathcal{Y}}\cap\big{\\{}y\in\mathcal{Y}\mid
y^{-1}(\tilde{y}(i))<y^{-1}(\tilde{y}(i+1))\big{\\}},\end{split}$ (15)

splitting $\tilde{\mathcal{Y}}$ according to whether $\tilde{y}(i)$ has a
higher rank than $\tilde{y}(i+1)$.

The next lemma, whose proof is in Appendix A.3.1, states that this partition
rule indeed guarantees that, at every step $m$ of the loop in Algorithm 3, the
second-best configuration in $\mathcal{Y}_{j}^{m}$ satisfies the invariant
(14).

######  Lemma 4.2.

Assume the score function is ranking-consistent (12) for a set of relevance
functions $\\{r_{k}\\}_{k=1}^{K}$. Then Algorithm 3 with the
$\textsc{Partition}_{\text{Ranking}}$ function (15) produces a sequence of
partitions with second-best configurations satisfying equation (14).

That is, Algorithm 3 is correct.

##  5 Experiments

In this section, we test our weakly supervised methods experimentally, in
different classification and regression problems, on both synthetic and real
datasets, with an emphasis on their computational efficiency and
informativeness. The primary goal of this paper is not to provide end-to-end
models with only partially supervised data, but rather to introduce a new form
of coverage validity and show how to achieve it with partially labeled data.
In contrast to the split-conformal method [53], which requires fully
supervised instances for both training and validating, we only need these to
train a model and form a scoring function suitable for the application of Alg.
1. In some cases, standard models already exist, such as in image
classification [22].

To provide a meaningful comparison with existing conformal methods and test
for predictive set size efficiency, we use fully labeled real datasets, and
introduce different plausible forms of weak supervision on our calibration and
test sets before applying Algorithm 1 to construct confidence sets. Our method
displays similar behavior across all datasets and forms of partial
information. To provide a baseline, we also run a standard fully supervised
conformal scheme (FSC) using the strong labels $Y_{i}$ and true scores
$s(X_{i},Y_{i})$, which runs similarly as Alg. 1, but with threshold

$\displaystyle\widehat{t}^{\text{full}}_{n}\coloneqq(1+n^{-1})(1-\alpha)\text{-quantile
of }\\{s(X_{i},Y_{i})\\}_{i=1}^{n}.$ (16)

We can then estimate the gain in efficiency—in the form of decreased
confidence set sizes—that stems from the weakening of strong coverage (1) to
weak coverage (3).

###  5.1 A toy classification example

\begin{overpic}[scale={0.55}]{figures/weak-multiclass-simulation-summary.pdf}
\put(-1.0,10.0){ \leavevmode\hbox to11.98pt{\vbox
to171.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{170.71654pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(15.0,0.0){
\leavevmode\hbox to114.41pt{\vbox
to11.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{11.3811pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(15.0,0.0){
\small$\sigma^{-1}$ } \put(38.0,0.0){ \small$\sigma^{-1}$ } \put(70.0,0.0){
\leavevmode\hbox to114.41pt{\vbox
to9.14pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{113.81102pt}{8.53583pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(75.0,0.0){
\small$\sigma^{-1}$ } \put(49.0,13.0){ \leavevmode\hbox to11.98pt{\vbox
to142.86pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{142.26378pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(50.0,22.0){\rotatebox{90.0}{
\small$\mathbb{E}\left[\big{|}\hat{C}(X)\big{|}\right]$}}
\par\par\put(6.0,47.5){ \leavevmode\hbox to85.96pt{\vbox
to9.14pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(30.0,47.5){
\leavevmode\hbox to85.96pt{\vbox to9.14pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(10.0,47.5){
\small$\mathbb{P}(Y\in\widehat{C}(X))$ } \put(31.0,47.5){
\small$\mathbb{P}(W\cap\widehat{C}(X)\neq\emptyset)$ } \par\end{overpic}
Figure 3: Results for the simulated multiclass data (17), over
$N_{\text{trials}}=20$ trials. The left plot shows respectively the strong (1)
and weak (3) coverage for the greedy weakly supervised (GWS), the weakly
supervised conformal (WSC) and the fully supervised conformal (FSC) confidence
sets. The right plot displays the average confidence set size for these
methods.

We first perform an experiment with a toy multiclass data set containing
$K=10$ different classes and $d=2$ dimensional features. We consider a
partially supervised problem on
$\mathcal{X}\times\mathcal{Y}=\mathbb{R}^{d}\times[K]$ for which we wish to
output valid confidence sets. We use the following model: each potential
response $y\in[K]$ has a noisy score depending on the feature vector
$X\in\mathbb{R}^{d}$ though a vector $\theta_{y}^{\star}\in\mathbb{R}^{d}$,

$\displaystyle\\{S^{\text{oracle}}_{y}\\}_{y\in[K]}\mid
X=x\sim\mathsf{N}(\\{x^{T}\theta_{y}^{\star}\\}_{y\in[K]},\sigma^{2}I_{K})$
(17)

Ideally, we would recover the strong label $Y\coloneqq\mathop{\rm
argmin}_{y\in\mathcal{Y}}S^{\text{oracle}}_{y}$, but our weakly supervised
methods do not observe $Y$ directly: instead, for a random instance-dependent
threshold $T$, we only have access to the weak set

$\displaystyle W\coloneqq\\{y\in\mathcal{Y}\mid S^{\text{oracle}}_{y}\leq
T\\}.$

As motivation, consider a supervised learning task in which, out of all
potential responses, there is always only one ground truth, but there are
other labels that are “good enough” (i.e. have a low enough score) to answer a
certain query. In this setting, a confidence set is weakly valid (3) as long
as it contains at least one label $y$ such that $S^{\text{oracle}}_{y}\leq T$,
whereas it is strongly valid (1) if it contains $Y$.

We vary the signal-to-noise ratio $\sigma^{-1}\in\\{10^{-2},\dots,10^{2}\\}$:
when it is too small, no model (even an oracle one) can be highly predictive,
and a standard conformal method should provide large uninformative confidence
sets, whereas we expect our new definition of coverage to yield smaller sets,
as any label in $W$ (i.e. with a low enough score) provides valid coverage.

In this experiment, we compare three different methods. The “Greedy weakly
supervised” (GWS) method only uses partially labeled data both when training
and conformalizating. It first trains $K$ separate logistic regressions with
$\\{X_{i}\\}$ as features and each $\\{1\\!\left\\{y\in W_{i}\right\\}\\}$ for
all $y\in\mathcal{Y}$ as potential response, providing a model for $P(y\in
W\mid X=x)$, and models the distribution of $W$ given $X=x$ as label-
independent (see Definition 3.3). It then computes a nested sequence of
confidence sets thanks to Alg. 2, which we then feed to the conformalization
Algorithm 1 using the nested scoring mechanism (6).

The second and third methods, the “Weakly supervised conformal” (WSC) and the
“Full supervised conformal” (FSC) methods respectively, use fully supervised
data for training: we first train a standard logistic regression model
$p_{\theta}(y\mid x)\propto\exp(\theta_{y}^{T}x)$ on $\\{(X_{i},Y_{i})\\}$,
and then construct a scoring function using the Generalized Inverse Quantile
(GIQ) procedure that Romano et al. [42] introduce. In the conformalization
step, the WSC method runs Algorithm 2 with partially labeled calibration data,
while the FSC method uses strongly labeled data to compute the threshold
$\widehat{t}_{n}^{\text{full}}$ in (16). The threshold $\widehat{t}_{n}$ in
Alg. 2 is always smaller than $\widehat{t}_{n}^{\text{full}}$, so the FSC
method returns larger confidence sets than the WSC method. We expect that as
the signal to noise ratio decreases, the gap between the GWS and WSC
confidence sets and the FSC confidence sets increases.

The precise experimental set-up is as follows: we simulate $n=10^{4}$ data
points, splitting them into training ($30\%$), calibration ($20\%$) and test
($50\%$) sets. We draw each $\theta_{y}$ uniform on $\mathbb{S}^{d-1}$,
$\\{X_{i}\\}_{i=1}^{n}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\mathsf{N}(0,I_{d})$, choosing weak threshold
$T\sim\mathsf{Uni}[\min_{y\in\mathcal{Y}}\\{S^{\text{Oracle}}_{y}\\},\max_{y\in\mathcal{Y}}\\{S^{\text{Oracle}}_{y}\\}]$.
We repeat the entire process $N_{\text{trials}}=20$ times to account for
uncertainty, presenting our results in Figure 3.

As we expect, using an alternative weaker version of coverage (3) allows us to
significantly decrease the size of the confidence set (by up to a factor of
3), especially when the signal-to-noise ratio is small, as one must include
more classes in the confidence set to maintain strong coverage. Indeed, we can
see that the strong coverage (1) for the GWS and WSC procedures fall well
below $1-\alpha=95\%$ in this case, since they only strive for weak $1-\alpha$
coverage, which they consistently achieve. Since the GWS method aims to
construct minimal confidence sets, we expect that it produces smaller
confidence sets than the WSC method, which simply leverages an existing
strongly supervised model; we consistently observe this across different
values of $\sigma$.

###  5.2 Document ordering for query answering

We now present the results of two experiments using Alg. 1 in a ranking
problem. The first one is a simulation of a standard ranking task, while the
second focuses on ranking documents’ relevance to specific queries in the
Microsoft LETOR dataset [37].

####  5.2.1 Ranking simulation study

\begin{overpic}[scale={0.55}]{figures/weak-ranking-simulation-size.pdf}
\put(-1.0,10.0){ \leavevmode\hbox to11.98pt{\vbox
to171.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{170.71654pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(0.0,6.0){\rotatebox{90.0}{ \small$\mathbb{P}(K_{i}^{\text{partial}}=t)$}
} \put(15.0,25.0){ \leavevmode\hbox to114.41pt{\vbox
to11.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{11.3811pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(14.0,25.5){
\small$\sigma^{-1}$ } \put(37.0,25.5){ \small$\sigma^{-1}$ }
\par\put(25.0,0.0){ \leavevmode\hbox to114.41pt{\vbox
to10.56pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{9.95847pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(22.0,0.0){
\small Size $t$ } \par\put(70.0,0.0){ \leavevmode\hbox to114.41pt{\vbox
to10.56pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{9.95847pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(75.0,0.0){
\small Size $t$ } \put(49.5,13.0){ \leavevmode\hbox to11.98pt{\vbox
to142.86pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{142.26378pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(49.5,20.0){\rotatebox{90.0}{ \small$\mathbb{P}\left(|\widehat{C}(X)|\leq
t)\right)$}} \par\put(6.0,47.5){ \leavevmode\hbox to85.96pt{\vbox
to9.14pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(30.0,47.5){
\leavevmode\hbox to85.96pt{\vbox to9.14pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{8.53583pt}\pgfsys@lineto{85.35828pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(10.0,47.5){
\small$\mathbb{P}(Y\in\widehat{C}(X))$ } \put(31.0,47.5){
\small$\mathbb{P}(W\cap\widehat{C}(X)\neq\emptyset)$ } \par\put(5.0,50.0){ \bf
A} \put(5.0,25.0){ \bf B} \put(52.0,50.0){ \bf C} \par\put(56.0,49.0){
\leavevmode\hbox to17.67pt{\vbox
to11.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{11.3811pt}\pgfsys@lineto{17.07166pt}{11.3811pt}\pgfsys@lineto{17.07166pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{17.07166pt}{11.3811pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(56.3,49.0){
\small$\sigma^{-1}$ } \end{overpic} Figure 4: Results for the ranking
simulation study (18) over $N_{\text{trials}}=20$ trials. A: Strong (1) and
Weak (3) coverage for the weakly supervised conformal (WSC) and the fully
supervised conformal (FSC) confidence sets. B: Density histogram of the
variable $K^{\text{partial}}$ (18) governing the weak distribution in this
example. C: Distribution of the confidence set size $|\widehat{C}(X)|$ for
different signal-to-noise ratios $\sigma^{-1}$.

In a first simulation study, we aim to predict a ranking of labels $y\in[K]$
based on a feature vector $X\in\mathbb{R}^{d}$. Think here of a supervised
problem where we want to rank users’ preferences for a set of items. Each user
has an unknown relevance score $S^{\text{Oracle}}_{y}\in\mathbb{R}$ for each
item $y\in[K]$, which induces a ground truth ranking over the labels:

$\displaystyle
Y\coloneqq\text{argsort}\\{S^{\text{Oracle}}_{y}\\}_{y\in[K]}\in\mathfrak{S}_{K}.$

The problem is to recover this noisy ranking and produce valid confidence sets
in $\mathfrak{S}_{K}$, but our weakly supervised methods do not observe the
full ranking when conformalizing: they can only observe the ranking up to the
$K_{\text{partial}}\leq K$-th element, leading to the weak set

$\displaystyle W=\\{y\in\mathfrak{S}_{K}\mid~{}\forall
j\in[K_{\text{partial}}],y(j)=Y(j)\\}.$ (18)

In our experiment, we simulate $n=10^{4}$ i.i.d. different users, using the
same (30,20,50) train/validation/test split as in Section 5.1. With $K=7$ and
$d=2$, we draw the user feature vector $X_{i}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\mathsf{N}(0,I_{d})$, and then conditionally on $X_{i}$, we
produce normal item-wise relevance scores
$\\{S^{\text{Oracle}}_{iy}\\}_{i\in[n],y\in[K]}$ following the distribution
(17). We finally simulate partial supervision by drawing the number of
observed elements in the ranking $K_{i}^{\text{partial}}$ as
$\min(K,1+A_{i})$, where $A_{i}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\text{Poi}(.5)$. The lower left panel of Figure 4 shows the
overall distribution of this quantity: most users only reveal the first 1 to 3
items in their optimal ranking.

We then produce strongly and weakly valid confidence sets at the
$1-\alpha\coloneqq 90\%$ level. We use the same scoring model for both the
fully supervised conformal (FSC) and weakly supervised conformal (WSC)
procedures: we learn linear individual relevance score functions
$\\{r_{y}\\}_{y\in[K]}$ (with fully supervised training data) via the ListNet
procedure [7], which we briefly describe here. Given a set of relevance scores
$\\{r_{y}\\}_{y\in\mathcal{Y}}\in\mathbb{R}^{K}$, ListNet models the
probability of a ranking $\pi\in\mathfrak{S}_{K}$ as

$\displaystyle
P_{r}(\pi)\coloneqq\prod_{y=1}^{K}\frac{\exp(r_{\pi(y)})}{\sum_{l=y}^{k}\exp(r_{\pi(l)})},$
(19)

which gives each item $y\in\mathcal{Y}$ a top-1 probability (of ranking first)
equal to

$\displaystyle P^{1}_{r}(y)\coloneqq
P_{r}(\pi(1)=y)=\frac{\exp(r_{y})}{\sum_{l=1}^{k}\exp(r_{l})}.$

Given a training data set containing pairs
$(X,R)\in\mathcal{X}\times\mathbb{R}^{K}$ of features/relevance scores, we
learn score mappings by minimizing the log-loss of the top-1 distribution over
a set $\mathcal{F}$ of functions

$\displaystyle\\{\hat{r}_{y}\\}_{y\in[K]}\coloneqq\mathop{\rm
argmin}_{\tilde{r}\in\mathcal{F}^{\mathcal{Y}}}\left\\{\sum_{(X,R)\in\text{
training
data}}\sum_{k=1}^{K}-P^{1}_{R}(k)\log\left(P^{1}_{\tilde{r}(X)}(k)\right)\right\\}.$

In our experiment, we only observe the ranking (or even a fraction of), not
the true per-item relevance scores, hence, following common practice [7], we
use $R_{y}=K-~{}\text{the rank of the item}=K-Y^{-1}(y)$ as a proxy for our
observed item-wise relevance scores when training our model.

In our experimental set up, each relevance score function
$r_{y}:\mathcal{X}\to\mathbb{R}$ ideally estimates the true conditional mean
of the oracle scores, $x\mapsto x^{T}\theta_{y}^{\star}$. Given these
individual scores, we use the scoring mechanism (13) with
$\psi(x,y)\coloneqq(y-x)_{+}$ and conformalize using the strategy we describe
in Section 4.2.2.

The difference between the WSC and FSC methods is the conformalization step on
calibration data: WSC runs Alg. 1 with partially supervised data to compute
the score threshold $\widehat{t}_{n}$ while FSC uses strongly supervised data
to return the more conservative threshold $\widehat{t}_{n}^{\text{full}}$ in
(16).

Our results fit our initial expectations, in line with our first experiments:
the size of the confidence set, as Figure 4C shows, benefits from the weaker
definition of coverage: for any value of the signal to noise ratio
$\sigma^{-1}>0$, the WSC method produces much smaller and more informative
confidence sets than the FSC method, as it only needs to include a ranking
with the correct first $K_{\text{partial}}$ elements to provide valid
coverage. ,At the cost of the strong coverage falling below $1-\alpha$ (see
Fig. 4A), and with little information (only the first $K_{\text{partial}}<K$
labels), the WSC method constructs predictive sets that are much smaller and
yet still valid (in a weak sense).

####  5.2.2 Ranking experiment with Microsoft LETOR dataset

\begin{overpic}[scale={0.55}]{figures/weak-ranking-letor-size.pdf}
\put(-1.0,45.0){ \leavevmode\hbox to11.98pt{\vbox
to171.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{170.71654pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(15.0,0.0){
\leavevmode\hbox to114.41pt{\vbox
to11.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{11.3811pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(14.0,0.0){
\small$c$ } \put(37.0,0.0){ \small$c$ } \par\par\put(70.0,0.0){
\leavevmode\hbox to114.41pt{\vbox
to10.56pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{9.95847pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(75.0,0.0){
\small Size $t$ } \put(49.5,42.0){ \leavevmode\hbox to11.98pt{\vbox
to142.86pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{142.26378pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{142.26378pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(49.5,42.0){\rotatebox{90.0}{
\small$\mathbb{P}\left(|\widehat{C}(X)|\wedge M\leq t)\right)$}}
\par\put(6.0,97.5){ \leavevmode\hbox to71.73pt{\vbox
to9.14pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{71.1319pt}{8.53583pt}\pgfsys@lineto{71.1319pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{71.1319pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(30.0,97.5){
\leavevmode\hbox to71.73pt{\vbox to9.14pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.53583pt}\pgfsys@lineto{71.1319pt}{8.53583pt}\pgfsys@lineto{71.1319pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{71.1319pt}{8.53583pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(10.0,97.5){
\small$\mathbb{P}(Y\in\widehat{C}(X))$ } \put(31.0,97.5){
\small$\mathbb{P}(W\cap\widehat{C}(X)\neq\emptyset)$ } \par\put(47.0,88.0){
\leavevmode\hbox to6.29pt{\vbox to29.05pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(47.5,95.0){\rotatebox{270.0}{ \small$K=2$} } \par\put(47.0,72.0){
\leavevmode\hbox to6.29pt{\vbox to29.05pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(47.5,79.0){\rotatebox{270.0}{ \small$K=4$} } \par\put(47.0,56.0){
\leavevmode\hbox to6.29pt{\vbox to29.05pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(47.5,63.0){\rotatebox{270.0}{ \small$K=6$} } \par\put(47.0,40.0){
\leavevmode\hbox to6.29pt{\vbox to29.05pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(47.5,47.0){\rotatebox{270.0}{ \small$K=8$} } \par\put(47.0,24.0){
\leavevmode\hbox to6.29pt{\vbox to29.05pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(47.5,31.0){\rotatebox{270.0}{ \small$K=10$} } \par\put(47.0,8.0){
\leavevmode\hbox to6.29pt{\vbox to29.05pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{28.45276pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(47.5,15.0){\rotatebox{270.0}{ \small$K=15$} } \par\par\put(97.0,88.0){
\leavevmode\hbox to6.29pt{\vbox to51.81pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{51.21497pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(97.5,95.0){\rotatebox{270.0}{ \small$K=2$} } \par\put(97.0,72.0){
\leavevmode\hbox to6.29pt{\vbox to51.81pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{51.21497pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(97.5,79.0){\rotatebox{270.0}{ \small$K=4$} } \par\put(97.0,56.0){
\leavevmode\hbox to6.29pt{\vbox to51.81pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{51.21497pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(97.5,63.0){\rotatebox{270.0}{ \small$K=6$} } \par\put(97.0,40.0){
\leavevmode\hbox to6.29pt{\vbox to51.81pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{51.21497pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(97.5,47.0){\rotatebox{270.0}{ \small$K=8$} } \par\put(97.0,24.0){
\leavevmode\hbox to6.29pt{\vbox to51.81pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{51.21497pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(97.5,31.0){\rotatebox{270.0}{ \small$K=10$} } \par\put(97.0,8.0){
\leavevmode\hbox to6.29pt{\vbox to51.81pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@stroke{0.85}{0.85}{0.85}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@rgb@fill{0.85}{0.85}{0.85}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{51.21497pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.69055pt}{51.21497pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }
\put(97.5,15.0){\rotatebox{270.0}{ \small$K=15$} } \par\put(5.0,100.0){ \bf A}
\put(52.0,100.0){ \bf B} \end{overpic} Figure 5: Results for LETOR ranking
dataset [37] over $N_{\text{trials}}=20$ trials. Each plot represents a
different value of $K\in\\{2,4,8,10,15\\}$, the number of documents to rank,
and we compare different scoring functions by varying the value of
$c\in\\{0,2,5,8\\}$ in equation (21). A: Strong (1) and Weak (3) coverage for
the weakly supervised conformal (WSC) and the fully supervised conformal (FSC)
confidence sets. B: Distribution of the confidence set size $|\widehat{C}(X)|$
for different numbers $K$ of suggested documents. We display here the
distribution of $\min(|\widehat{C}(X)|,M)$ for $M=100$.

We now tackle a slightly different type of ranking problem: we wish to rank a
set of potential documents by order of relevance to a specific user query:
documents more relevant to the query should occupy a higher position in the
final ranking. A search engine is a good example of such problem: a user makes
a search query, and the task is to sort Web pages that best answer that query
among a (potentially large) set of potential pages.

##### Learning to rank with Microsoft LETOR dataset [37]

To study that problem, we design an experiment with Microsoft LETOR data set.
For each potential query/document pair $(x,d)$, the dataset aggregates several
quantities of interest to determine whether $d$ is relevant to $x$ into a
$d=46$-dimensional feature vector $\phi(x,d)\in\mathbb{R}^{d}$. For a query
$x$ with a set of potentially relevant documents
$D(x)\coloneqq\\{d_{j}\\}_{j=1}^{|D(x)|}$, our data set additionally contains
a ranking $\Pi(x)\in\mathfrak{S}_{|D(x)|}$ that orders these documents
according to their relevance. Our goal is to retrieve that ranking using the
feature vectors $\\{\phi(x,d_{j})\\}_{j=1}^{D(x)}$.

##### A semi-synthetic weakly supervision set-up

Here is how we construct weakly supervised calibration and test data sets. For
each split (calibration/test), we first sample $n=2000$ queries from the
entire set of queries in LETOR validation and test datasets. For every query
$X_{i}$, we select $K\in\\{2,4,6,8,10,20\\}$ documents by first sorting
$D(X_{i})$ into $K$ equally sized subsets by relevance, so subset $\ell\in[K]$
contains the documents with rank $\Pi(x)_{y}$ for every
$y\in\\{\frac{(\ell-1)|D(X_{i})|}{K}+1,\dots,\frac{\ell|D(X_{i})|}{K}\\}$, and
then drawing one document from each box uniformly at random.

This procedure ensures that there exists a significant relevance gap between
any two potential documents in the query, and that the number of documents to
rank is sufficient to allow reasonably-sized confidence sets. $\Pi(X_{i})$
additionally induces a sub-ranking $Y_{i}\in\mathfrak{S}_{K}$ on these
documents, which we treat as a strong label. Similarly to our approach in
Section 5.2.1, we introduce partial labels by assuming that our weakly
supervised method can only access the first $K_{i}^{\text{partial}}$ elements
of $Y_{i}$, where $K_{i}^{\text{partial}}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}1+\text{Poi}(.5)$: this simulates the plausible setting where a
user has given feedback on the most relevant documents to the query, but
certainly not to all of them. We repeat the entire simulation procedure
$N_{\text{trials}}=20$ times.

##### Building a ranking scoring function (13)

We next describe how we use fully supervised training data to construct the
scoring function that we feed Alg. 1 with. We first learn a linear
query/document relevance function

$\displaystyle r_{\theta}(x,d)\coloneqq\theta^{T}\phi(x,d)$ (20)

using the ListNet procedure (19) on LETOR (fully supervised) train data

$\displaystyle\left(x_{i},(d_{i,j})_{j=1}^{D(x_{i})},y_{i}\in\mathfrak{S}_{D(x_{i})}\right)_{i=1}^{n_{\text{train}}},$

containing 55700 different query/document pairs.

We then use a specific implementation of the score function
$s^{\text{Ranking}}$ as in Eqn (13): if we rank $K$ documents
$\\{d_{k}\\}_{k\in[K]}$ for a query $x$, we rescale our relevance scores to
the interval $[0,1]$,

$\displaystyle\\{r_{k}(x)\\}_{k\in[K]}\coloneqq\biggr{\\{}\dfrac{r_{\theta}(x,d_{k})-\min_{j\in[K]}r_{\theta}(x,d_{j})}{\max_{j\in[K]}r_{\theta}(x,d_{j})-\min_{j\in[K]}r_{\theta}(x,d_{j})}\biggr{\\}}_{k\in[K]},$

and then, for a choice of $c\in\\{0,2,5,8\\}$, apply the scoring mechanism
(13) with these relevance scores and pairwise comparison function

$\displaystyle\psi_{c}(r_{1},r_{2})\coloneqq\exp(-cr_{1})\left(r_{2}-r_{1}\right)_{+}.$
(21)

In this example, we guarantee weak coverage if the true ranking $Y_{i}$ on the
first $K_{i}^{\text{partial}}$ elements coincides with either one of the
predictive rankings. To keep the predictive set size small, we thus wish to
ensure that it doesn’t contain two rankings with the same first
$K_{i}^{\text{partial}}$ elements (as they would be redundant): this is why we
introduce the exponential term $\exp(-cr_{1})$, which makes sure that when
ranking all configurations by their score, highly ranked configurations have
different first elements (rather than different last elements). To estimate
the distribution of $|\widehat{C}(X)|$, we then compute the $M=100$ best
rankings for each query using Alg 3, and then replace the size of the
confidence set by $\min(M,|\widehat{C}(X)|))$, effectively truncating it to
$M$.

##### Experimental results

We present our results in Figure 5. The confidence sets display the behavior
we expect: when the number $K$ of items to classify is small, the fully
supervised conformal (FSC) and weakly supervised conformal (WSC) methods are
similar, since partial labels are often equal to strong labels. Since the
overall number of configurations is small, both methods are also able to
maintain fairly small confidence sets. On the other hand, when $K$ grows, the
weak supervision method quickly departs from the full supervision one, and is
able to produce confidence sets that are much smaller: when $K\geq 8$, the FSC
method is unable to produce confidence sets with fewer than $100$
configurations, as the number of configurations is large, and the problem is
inherently noisy, especially for comparing documents with a fairly small
relevance. The WSC (partially) overcomes that difficulty with its restrained
notion of coverage, and is able to maintain a majority of confidence sets with
size smaller than $M$, at least until $K=15$. Of course, this method pays a
price in terms of strong coverage, as for large $K$, the confidence set almost
never contains the actual ground true ranking. That said, it may not a real
issue as we are more interested in detecting which documents are actually
relevant, and hence should have a higher rank, rather than correctly ordering
documents with very little relevance to the query at the bottom of the list.

In addition, as we predicted, higher values of $c$ in the pairwise comparison
function (21) produce much smaller confidence sets by favoring more diverse
rankings at the top of the list.

###  5.3 Pedestrian tracking with partial matching information

\begin{overpic}[scale={0.55}]{figures/weak-matching-mot15.pdf}
\put(-1.0,10.0){ \leavevmode\hbox to11.98pt{\vbox
to171.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{170.71654pt}\pgfsys@lineto{11.3811pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{11.3811pt}{170.71654pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(15.0,0.0){
\leavevmode\hbox to114.41pt{\vbox
to11.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{11.3811pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{11.3811pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} } \put(15.0,0.0){
\small Train/Validation split } \put(70.0,0.0){ \leavevmode\hbox
to114.41pt{\vbox to10.56pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }{{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{9.95847pt}\pgfsys@lineto{113.81102pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{113.81102pt}{9.95847pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope