Transductive conformal inference with adaptive scores

Ulysse Gazin[Université Paris Cité and Sorbonne Université, CNRS, Laboratoire de Probabilités, Statistique et Modélisation. Email<EMAIL_ADDRESS>Gilles Blanchard[Université Paris Saclay, Institut Mathématique d'Orsay. Email<EMAIL_ADDRESS>Etienne Roquain[Sorbonne Université and Université Paris Cité, CNRS, Laboratoire de Probabilités, Statistique et Modélisation. Email<EMAIL_ADDRESS>
Conformal inference is a fundamental and versatile tool that provides distribution-free guarantees for many machine learning tasks. We consider the transductive setting, where decisions are made on a test sample of $m$ new points, giving rise to
$m$ conformal $p$-values. While classical results only concern their marginal distribution, we show that their joint distribution
follows   a Pólya urn model,
and establish
a concentration inequality for their empirical distribution function. The results hold for arbitrary exchangeable scores, including adaptive ones that can use the covariates of the test+calibration samples at training stage for increased accuracy. We demonstrate the usefulness of these  theoretical
results through uniform, in-probability guarantees for two machine learning tasks of current interest: interval prediction for transductive transfer learning and novelty detection based on two-class classification.

Keywords: Conformal inference, Multiple testing, False Discovery Rate,  Uniform error control

§ INTRODUCTION

Conformal inference is a general framework aiming at providing sharp uncertainty quantification guarantees
for the output of machine learning algorithms used as “black boxes”.
A central tool of that field is the construction of a “(non)-conformity score” $S_i$ for each sample point.
The score functions can be learnt on a training set using various machine learning
methods depending on the task at hand.
The scores observed
on a data sample called “calibration sample” $\dcal$ serve as references for the scores of a “test sample” $\dtest$ (which may or may not be observed, depending on the setting). The central property of these scores is that they are an exchangeable family of random variables.

§.§ Motivating tasks

To be more concrete, we start with two specific settings serving both as motivation and
as application.

(PI) Prediction intervals: we observe $\mathcal{D}_{{\tiny \mbox{cal}}}=(X_1,Y_1), \dots, (X_n,Y_n)$ a sample of i.i.d. variables with unknown distribution $P$, where $X_i\in \R^d$ is a regression covariate and $Y_i\in \R$ is the outcome. Given a new independent datum $(X_{n+1},Y_{n+1})$ generated from $P$, the task is to build a
prediction interval for $Y_{n+1}$ given $X_{n+1}$ and $\mathcal{D}_{{\tiny \mbox{cal}}}$.
More generally, in the transductive conformal setting [25], the task is
repeated $m\geq 1$ times:
given $m$ new data points $\mathcal{D}_{{\tiny \mbox{test}}}=(X_{n+1},Y_{n+1}), \dots, (X_{n+m},Y_{n+m})$ i.i.d from $P$, build $m$
prediction intervals for $Y_{n+1},\dots,Y_{n+m}$ given $X_{n+1},\dots,X_{n+m}$ and $\mathcal{D}_{{\tiny \mbox{cal}}}$.

(ND) Novelty detection: we observe  $\mathcal{D}_{{\tiny \mbox{cal}}}=(X_1,\dots,X_n)$, a sample of nominal data points in $\R^d$, drawn i.i.d. from an unknown (null) distribution $P_0$, and a
test sample $\mathcal{D}_{{\tiny \mbox{test}}}=(X_{n+1},\dots,X_{n+m})$ of independent points in $\R^d$, each of which is distributed as $P_0$ or not.  The task is to  decide if each $X_{n+i}$ is distributed as the training sample (i.e., from $P_0$) or is a “novelty”.

Task (PI) with adaptive scores in a non-parametric regression setting with domain shift between train and calibration+test samples
proof-of-concept model, see Section <ref>).  Our contribution is both to propose adaptive scores and predictions relying on transfer learning (this figure), and uniform bounds on the false coverage proportion, see Figure <ref>.

For both inference tasks, the usual pipeline is based on the construction of non-conformity real-valued scores $S_1,\dots,S_{n+m}$ for each member of $\mathcal{D}_{{\tiny \mbox{cal}}}\cup\mathcal{D}_{{\tiny \mbox{test}}}$, which requires an additional independent training sample $\mathcal{D}_{{\tiny \mbox{train}}}$ (in the so-called “split conformal” approach):

(PI) the scores are (for instance) the regression residuals $S_i=|Y_i-\mu(X_i;\mathcal{D}_{{\tiny \mbox{train}}})|$, $1\leq i\leq n+m$, where the function $\mu(x;\mathcal{D}_{{\tiny \mbox{train}}})$ is a point prediction of $Y_i$ given $X_i=x$, learnt from the sample $\mathcal{D}_{{\tiny \mbox{train}}}$.

(ND) the scores are of the form $S_i=g(X_i;\mathcal{D}_{{\tiny \mbox{train}}})$, $1\leq i\leq n+m$, where the score function $g(\cdot;\mathcal{D}_{{\tiny \mbox{train}}})$ is learnt using the sample $\mathcal{D}_{{\tiny \mbox{train}}}$; $g(x)$ is meant to be large if $x$ is fairly different from the members of $\mathcal{D}_{{\tiny \mbox{train}}}$ (so that it is “not likely” to have been generated from $P_0$).

In both cases,
inference is based on the so-called split conformal $p$-values [26]:

\begin{equation}\label{equemppvalues}
p_i=(n+1)^{-1}\paren[3]{1+\sum_{j=1}^n \ind{S_j\geq S_{n+i}}},\:\: i\in \range{m}.
\end{equation}

In other words, $(n+1)p_i$ is equal to the rank of $S_{n+i}$ in the set of values $\{S_1,\dots, S_n,S_{n+i}\}$,
and a small $p$-value $p_i$ indicates that the test score $S_{n+i}$ is abnormally high within the set of reference scores.
The link
to the two above
tasks is as follows: for (PI), the prediction interval $\bm{\mathcal{C}}(\alpha)$ for $Y_{n+i}$ with coverage probability $(1-\alpha)$ is obtained by inverting the inequality $p_i>\alpha$ w.r.t. $Y_{n+i}$, see (<ref>) below. For (ND), the members of the test sample declared as novelties are those with a $p$-value $p_i\leq t$ for some
threshold $t$.

Studying the behavior of the conformal $p$-value family is thus a cornerstone of
conformal inference. Still, classical results only concern the marginal distribution of the $p$-values while the joint distribution remains largely unexplored in full generality.

§.§ Contributions and overview of the paper

In Section <ref>, we present new results for the joint distribution of the conformal $p$-values  (<ref>) for general exchangeable scores (for any sample sizes $n$ and $m$). First, in Section <ref>, we show that the dependence structure involved only depends on $n$ and $m$, and
follows a Pólya urn model; this entails both explicit formula and useful characterizations. Second,
we deduce a new finite sample DKW-type concentration inequality [16] for the empirical distribution function (ecdf) of the conformal $p$-values.
We emphasize the following favorable features of our results for application of the conformal methodology:

(i) The weak assumption of exchangeable (rather than i.i.d.) scores allows to handle adaptive score training:  the score functions can depend on the training sample, and on the calibration+test sample (in a way that maintains exchangeability).

(ii) Simultaneous and uniform inference: since $m$ decisions are taken simultaneously (transductive setting), the joint error distribution
should be taken into account for global risk assessment. We provide error bounds with high probability and  uniform
validity over a family of possible decisions (allowing for user or data-driven choice).

These findings are then applied in detail to (PI)  in Section <ref> and (ND) in Section <ref>.
For (ND), we consider adaptive scores proposed by [14] leveraging two-class classification.
For (PI), we consider a setting of domain shift between training and calibration+test, and introduce a novel approach (to our knowledge)
of transductive transfer for PI, leveraging transfer learning algorithms.
In both cases, use of adaptive scores significantly improves inference quality (see Figure <ref> for our approach to transductive transfer PI). We give sharp bounds in probability for
the  false coverage proportion (FCP) (for PI) and the false discovery proportion (FDP) (for ND), with a possibly data-driven choice of the prediction intervals for (PI) and of the size of rejection threshold for (ND).
This is in contrast  to previous results only providing in-expectation guarantees of FCP/FDP.
Our work hence brings more fine-grained reliability, which can be crucial when the practitioner faces sensible data.

§.§ Relation to previous work

For fundamentals on conformal prediction, see [26, 1].
We only consider the split conformal approach, also named inductive conformal approach in the seminal work of [17].
The split conformal approach uses a separate training set but  is considered the
most practically amenable approach for big data (in contrast to the “full conformal” approach which can be sharper but computationally intractable).

The most important consequence of score exchangeability is that the marginal distribution of a conformal $p$-value is a discrete uniform under the joint (calibration and test) data distribution.
There has been  significant recent interest for the conditional distribution of a marginal $p$-value,
conditional to the calibration sample, under the stronger assumption of i.i.d. scores. The corresponding results take the form
of bounds on $\P(p_1\leq t \:|\: \dcal)$ holding with high probability over $\dcal$ (24, 6, 20, 3,
where in the two latter references the results are in addition uniformly valid in $t$).
However, the i.i.d. scores assumption prevents handling adaptive scores (point (i) above), for which only exchangeability is guaranteed; moreover, these works are restricted to a single predictor, and do   not address point (ii) either.
Simultaneous inference for the (PI) task has been  proposed by [25] (see also 21 for an earlier occurrence for one $p$-value with multiple new examples), referred to as transductive conformal inference, and which includes a Bonferroni-type correction.
Closest to our work, [15]  analyzes the false coverage proportion (FCP) of the usual prediction interval family $\bm{\mathcal{C}}(\alpha)$ repeated over $m$ test points:
the exact distribution of the FCP
under data exchangeability is provided, and related to a Pòlya urn model with two colors.
We show the more general result that the full joint distribution of $(p_1,\dots,p_m)$ follows a Pòlya urn model with $(n+1)$ colors, which entails the result of [15] as a corollary (see Appendix <ref>). This brings substantial innovations: our bounds on FCP are uniform in $\alpha$, and we provide both
the exact joint distribution and an explicit non-asymptotic approximation via a DKW-type concentration bound.

The (ND) setting is alternatively referred to as Conformal Anomaly Detection (see Chapter 4 of 1).
We specifically consider here the (transductive) setting of [3] where the test sample contains novelties, and the corresponding $p$-values for `novelty' entries are not discrete uniform  but expected to be stochastically smaller.
Due to strong connections to multiple testing,  ideas and procedures stemming from that area can be adapted to address (ND), specifically by controlling the false discovery rate (FDR, the expectation of the FDP), such as as the Benjamini-Hochberg (BH) procedure
Use of adaptive scores and corresponding FDR control has been investigated by [14].
Our contribution with respect to that work comes from getting uniform and in-probability bounds for the FDP
(rather than only in expectation, for the FDR).

§ MAIN RESULTS

§.§ Setting

We denote integer ranges using $\range{i}=\{1,\dots,i\}$, $\range{i,j}=\{i,\dots,j\}$.
Let $(S_i)_{i \in \range{n+m}}$ be real random variables corresponding to non-conformity scores, for which $(S_j)_{j \in \range{n}}$ are the “reference” scores and $(S_{n+i})_{i \in \range{m}}$ are the “test” scores.
We assume

\begin{equation}\label{as:exchangeable}\tag{Exch}
\mbox{The score vector $(S_i)_{i\in \range{n+m}}$ is exchangeable.}
\end{equation}

Under (<ref>), the $p$-values (<ref>) have super-uniform marginals (see, e.g., 18).
In addition, the marginal distributions are all equal and uniformly distributed on $\{\ell/(n+1),\ell\in\range{n+1}\}$ under the additional mild assumption:

\begin{equation}\label{as:noties}\tag{NoTies}
\mbox{The score vector $(S_i)_{i\in \range{n+m}}$ has no ties a.s.}
\end{equation}

While the marginal distribution is well identified, the joint distribution of the $p$-values is not well studied yet. In particular, we will be interested in the
empirical distribution function of the $p$-value family, defined as

\begin{equation}\label{equ-ecdfpvalues}
\wh{F}_m(t):=m^{-1}\sum_{i=1}^m \ind{p_i\leq t}, \:\:\: t\in [0,1].
\end{equation}

Note that the $p$-values are not i.i.d. under (<ref>), so that most classical concentration inequalities, such as DKW's inequality [16], or Bernstein's inequality, cannot be directly used. Instead, we should take into account the specific dependence structure underlying these $p$-values.

§.§ Key properties

We start with  a straightforward result, under the stronger assumption

\begin{equation}\label{as:iid}\tag{IID}
\mbox{The variables $S_i ,i\in \range{n+m}$, are i.i.d.}
\end{equation}

For this, introduce, for any fixed vector $U=(U_1,\dots,U_n)\in [0,1]^n$, the discrete distribution $P^U$ on the set $\set[1]{\frac{\ell}{n+1}, \ell \in \range{n+1}}$,  defined as

\begin{equation}\label{equPU}
P^U(\{\l/(n+1)\})=U_{(\l)}-U_{(\l-1)}, \:\:\:\l\in \range{n+1},
\end{equation}

where $0=U_{(0)}\leq U_{(1)}\leq \dots \leq U_{(n)}\leq U_{(n+1)}=1$  are the increasingly ordered values of $U=(U_1,\dots,U_n)$. In words, the $n$ values of $U$ divide the interval $[0,1]$ into $(n+1)$ distinct cells
(labeled $\frac{\ell}{n+1}, \ell\in \range{n+1}$), and $P^U$ is
the probability distribution of the label of the cell
a $\mathrm{Unif}[0,1]$ variable would fall into.

Note that $P^U$ has for c.d.f.

\begin{equation}\label{equFU}
F^U(x)=U_{(\lfloor (n+1)x\rfloor)}, \:\:\:x\in [0,1].
\end{equation}

Assume (<ref>) and (<ref>) and consider the $p$-values $(p_i,i\in \range{m})$ given by (<ref>). Then conditionally on  $\mathcal{D}_{{\tiny \mbox{cal}}}=(S_1,\dots,S_n)$, the $p$-values
are i.i.d. of common distribution given by

p_1 \:|\: \mathcal{D}_{{\tiny \mbox{cal}}} \sim P^U,

where  $U=(U_1,\dots,U_n)=\paren[1]{1-F(S_1),\dots,1-F(S_n)}$ are pseudo-scores
and $F$ is the common c.d.f. of the scores of $\mathcal{D}_{{\tiny \mbox{cal}}}$, that is, $F(s)=\P(S_1\leq s)$, $s\in \R$.
In addition the pseudo-score vector $U$ is i.i.d. $\mathrm{Unif}[0,1]$ distributed.

Proof sketch.
The conditional distribution
of $p_i$ only depends on score ordering which is unambiguous due to (<ref>),
and is thus invariant by monotone transformation of the scores by $(1-F)$.
Writing explicitly the cdf of $p_i$ from the uniformly distributed transformed scores yields (<ref>).
See Appendix <ref> for details.

In the literature, such a result is used  to control the conditional failure  probability $\P(p_1\leq \alpha \:|\: \mathcal{D}_{{\tiny \mbox{cal}}})$ around its expectation (which is ensured to be smaller than, and close to, $\alpha$) with concentration inequalities valid under an i.i.d. assumption [3, 20].

By integration over $U$, a direct consequence of Proposition <ref> is that, under (<ref>) and (<ref>), and unconditionally on $\mathcal{D}_{{\tiny \mbox{cal}}}$, the family of conformal $p$-values $(p_i,i\in \range{m})$ has the “universal” distribution
$P_{n,m}$ on $[0,1]^m$ defined as follows:

\begin{align}
P_{n,m} = \mathcal{D}\big(q_i,i\in \range{m}\big)
\label{equ:distribution}, \text{ where }\\
\begin{cases}
\hfill\big(q_1,\ldots,q_m |U\big) &\stackrel{\text{i.i.d.}}{\sim} P^U;\\
\text{ and } U=(U_1,\ldots,U_n) &\stackrel{\text{i.i.d.}}{\sim} \mathrm{Unif}([0,1]).
\end{cases} \label{equ:generation}
\end{align}

Our first result is to note that the latter holds beyond the i.i.d. assumption.

Assume (<ref>) and (<ref>), then the family of $p$-values $(p_i,i\in \range{m})$ given by (<ref>)
has joint distribution $P_{n,m}$, which is
defined by (<ref>)-(<ref>) and is independent of the specific score distribution.

Proof sketch. The joint distribution of the $p$-values only depends on the ranks of the $(n+m)$
scores. Since the scores have exchangeable distribution and (<ref>) holds, their ranks form a random permutation of $\range{n+m}$.
the same rank distribution (and consequently joint $p$-value distribution) is generated when the scores are i.i.d.
Applying Proposition <ref>, the $p$-value distribution can be represented as (<ref>)-(<ref>).
See also Appendix <ref>.

The next proposition is an alternative and useful characterization of the distribution $P_{n,m}$.

is the distribution of
the colors of $m$ successive draws in a standard Pólya urn model with $n+1$ colors labeled $\big\{\frac{\l}{n+1},
\l \in \range{n+1}\big\}$.

Proposition <ref> is proved in Appendix <ref>, where several explicit formulas for $P_{n,m}$ are also provided. We also show that this generalizes the previous work of [15].

Comparing Proposition <ref> and Proposition <ref>, we see that having i.i.d. scores is more favorable because guarantees are valid conditionally on $\mathcal{D}_{{\tiny \mbox{cal}}}$ (with an explicit expression for $U=U(\dcal)$). However, as we will see in Sections <ref> and <ref>, the class of exchangeable scores is much more flexible and includes adaptive scores, which can improve substantially inference sharpness in specific situations. For this reason, we work with the unconditional distribution as in Proposition <ref> in the sequel.

§.§ Consequences

We now provide a DKW-type envelope for
the empirical distribution function (<ref>) of conformal $p$-values.
Let us introduce the discretized identity function

\begin{align}
I_n(t) =\lfloor (n+1)t\rfloor/(n+1)=\E \wh{F}_m(t),\:\:\:t\in [0,1],\label{discretizedid}
\end{align}

and the following bound:

\begin{align}
B^{\mbox{\tiny DKW}}(\lambda,n,m)&:=
\bm{1}_{\set{\lambda <1}} \left[1+\frac{2\sqrt{2\pi}\lambda \tau_{n,m}}{(n+m)^{1/2}}\right]e^{-2\tau_{n,m} \lambda^2},
\label{BDKW}
\end{align}

where $\tau_{n,m}:=nm/(n+m)\in [(n\wedge m)/2, n\wedge m]$ is an
“effective sample size”.

Let us consider the process $\wh{F}_m$ defined by (<ref>), the discrete identity function $I_n(t)$ defined by (<ref>), and assume (<ref>) and (<ref>). Then we have  for all $\lambda>0$, $n,m\geq 1$,

\begin{align}
\P\Big(\sup_{t\in [0,1]}(\wh{F}_m(t) - I_n(t)) > \lambda\Big)&\leq B^{\mbox{\tiny DKW}}(\lambda,n,m).\label{boundDKWup}
\end{align}

In addition, $B^{\mbox{\tiny DKW}}(\lambda^{\mbox{\tiny DKW}}_{\delta,n,m},n,m)\leq \delta$ for

\begin{align}
&\lambda^{\mbox{\tiny DKW}}_{\delta,n,m}=\Psi^{(r)}(1);
\label{boundDKWupexplicit}\\
&\Psi(x)=1\wedge\bigg( \frac{\log(1/\delta)+\log\big(1+ \sqrt{2\pi}  \frac{2\tau_{n,m}x}{(n+m)^{1/2}}\big)}{2\tau_{n,m}} \bigg)^{1/2}, \notag
\end{align}

where $\Psi^{(r)}$ denotes the function $\Psi$ iterated $r$ times (for an arbitrary integer $r\geq 1$).

Proof sketch. Use the representation (<ref>), apply the DKW inequality separately
to $(U_1,\ldots,U_n)$ and to $(q_1,\ldots,q_m)$ conditional to $U$, and integrate over $U$.
See Appendix <ref> for details (a slightly more accurate bound is also proposed).

Since the distribution $P_{n,m}$ can be easily sampled from, $\lambda^{\mbox{\tiny DKW}}_{\delta,n,m}$ in (<ref>)
can be further improved by considering the sharper but implicit quantile

\begin{align*}
&\lambda^{\mbox{\tiny num-DKW}}(\delta,n,m)=\min\Big\{x\geq 0\::\: \pi_{n,m,x}\leq \delta\Big\}, \text{with}\\
P_{n,m}\bigg(\sup_{\l\in \range{n+1}}\Big(\wh{F}_m\Big(\frac{\ell}{n+1}\Big) - \frac{\ell}{n+1}\Big) > x\bigg).\nonumber
\end{align*}

In addition, numerical confidence envelopes for $\wh{F}_m$ with other shapes can be investigated.
For instance, for any set $\mathcal{K} \subset \range{m}$ of size $K$, we can calibrate thresholds $t_1,\dots,t_K>0$ such that

\begin{align}
&\P_{\bm{p}\sim P_{n,m}}(\forall k\in \mathcal{K},\:p_{(k+1)}> t_k)\nonumber\\
&= \P_{\bm{p}\sim P_{n,m}}(\forall k\in \mathcal{K},\: \wh{F}_m(t_k)\leq k/m)\geq 1-\delta.\label{exactcontrol}
\end{align}

A method is to start from a “template” one-parameter family $(t_k(\lambda))_{k\in \mathcal{K}}$ and then adjust $\lambda$ to obtain the desired control [7, 12]. This approach is developed in detail in Appendix <ref>.

§ APPLICATION TO PREDICTION INTERVALS

In this section, we apply our results to build simultaneous conformal prediction intervals, with an angle towards adaptive scores and transfer learning.

§.§ Setting

Let us consider a conformal prediction framework for a regression task, see, e.g., [11], with three independent samples of points $(X_i,Y_i)$, where $X_i\in \R^d$ is the covariable and $Y_i\in \R$ is the outcome:

* Training sample $\mathcal{D}_{{\tiny \mbox{train}}}$: observed and used to build predictors;

* Calibration sample $\mathcal{D}_{{\tiny \mbox{cal}}}=\{(X_i,Y_i),i\in \range{n} \}$;
observed and used to calibrate the size(s) of the prediction intervals;

* Test sample $\mathcal{D}_{{\tiny \mbox{test}}}=\{(X_{n+i},Y_{n+i}), i \in \range{m}\}$;
only the $X_i$'s are observed and the aim is to provide prediction intervals for the labels.

In addition, we consider the following
transfer learning setting: while the data points are i.i.d. within each sample and the distributions of $\mathcal{D}_{{\tiny \mbox{cal}}}$ and $\mathcal{D}_{{\tiny \mbox{test}}}$ are the same,  the distribution of $\mathcal{D}_{{\tiny \mbox{train}}}$ can be different. However, $\mathcal{D}_{{\tiny \mbox{train}}}$ can still help to build a good predictor by using a transfer learning toolbox, considered here as a black box
(see, e.g., 27 for a survey on transfer learning).
A typical situation of use is when the training labeled data $\mathcal{D}_{{\tiny \mbox{train}}}$ is abundant but
there is a domain shift for the test data, and we have a limited number of labeled data $\mathcal{D}_{{\tiny \mbox{cal}}}$ from the new domain.

§.§ Adaptive scores and procedures

Formally, the aim is to build $\bm{\mathcal{I}}=(\mathcal{I}_i)_{i\in \range{m}}$, a family of $m$ random intervals of $\R$ such that the amount of coverage errors $(\ind{Y_{n+i}\notin \PI_i})_{i\in \range{m}}$ is controlled.
The construction of a rule $\bm{\mathcal{I}}$ is based on non-conformity scores $S_i$, $1\leq i\leq n+m$,  corresponding to residuals between $Y_{i}$ and the prediction at point $X_{i}$:

\begin{equation}\label{equadaptscores}
S_i:=|Y_{i}-\hat{\mu}(X_{i};(\dtrain,\dxct))|, \:\: i\in \range{n+m},
\end{equation}

where the predictor $\hat{\mu}$
is learnt using $\dtrain$ and the calibration + test covariates $\dxct=(X_1,\ldots,X_{n+m})$.
More sophisticated scores than the residuals have been proposed in earlier literature [19], in particular allowing for
conditinal variance or quantile prediction and resulting prediction intervals of varying length. Our theory extends to those as well and we consider here (<ref>) for
We call the scores (<ref>) adaptive because they can use the unlabeled data $\dxct$, which is particularly suitable in the transfer learning framework where the covariates of $\mathcal{D}_{{\tiny \mbox{train}}}$ should be mapped to those of $\dxct$ to build a good predictor.
Classical scores can also be recovered via (<ref>)  if the predictor ignores $\dxct$.
The predictor $\wh{\mu}$ can be any “black box" (an unspecified transfer learning algorithm)
provided the following mild assumption is satisfied, ensuring score exchangeability:

\begin{equation}
\mbox{$\forall x\in \R^d$, $\hat{\mu}\big(x;(\mathcal{D}_{{\tiny \mbox{train}}}, \dxct)\big)$}
\mbox{ is invariant by permutation of } \dxct.
\label{as:permut}\tag{PermInv}
\end{equation}

Since $(X_i,Y_i)_{i \in \range{n+m}}$ are i.i.d. and thus exchangeable, one can  easily show that  (<ref>) holds for the adaptive scores (<ref>) when the predictor satisfies (<ref>).
Predictors based on transfer machine learning procedures typically satisfy (<ref>).
In addition, (<ref>) is a mild assumption: add a negligible noise to the scores is an appropriate tie breaking that makes  (<ref>) hold.

Given the scores (<ref>), we build the conformal $p$-values via (<ref>) and define the specific conformal procedure $\bm{\mathcal{C}}(\alpha)=(\mathcal{C}_i(\alpha))_{i\in \range{m}}$ obtained by inverting $\{p_i>\alpha\}$ with respect to $Y_{n+i}$, that is, $\{p_i>\alpha\}=\{Y_{n+i}\in \mathcal{C}_i(\alpha)\}$  almost surely with

\begin{equation}\label{equrules}
\mathcal{C}_i(\alpha):=\left[ \hat{\mu}(X_{n+i};
(\dtrain,\dxct)) \pm S_{(\lceil (n+1)(1-\alpha)\rceil)}\right],
\end{equation}

where $S_{(1)}\leq \dots \leq S_{(n)}\leq S_{(n+1)}:=+\infty$ denote the order statistics of the calibration scores $(S_1,\dots,S_n)$.
Observe that the radius of the interval $S_{(\lceil (n+1)(1-\alpha)\rceil)}$ can be equivalently described as the $(1-\alpha)$-quantile of the distribution $\sum_{i=1}^n \frac{1}{n+1}\delta_{S_i} + \frac{1}{n+1} \delta_{+\infty}$. Note also that $\bm{\mathcal{C}}(\alpha)=\R^m$ if $\alpha<1/(n+1)$, that is, if the desired coverage error is too small w.r.t. the size of the calibration sample.

§.§ Transductive error rates

By Proposition <ref>, the following marginal control holds for the conformal procedure $\bm{\mathcal{C}}(\alpha)$ (<ref>):

\begin{equation}\label{equ:marg}
\P(Y_{n+i}\notin \mathcal{C}_i(\alpha))\leq \alpha, \:\:i\in \range{m}.
\end{equation}

This is classical for non-adaptive scores and our result already brings an extension to adaptive scores in the transfer learning setting.

In addition, we take into account the prediction multiplicity by considering false coverage proportion (FCP) of some procedure $\bm{\mathcal{I}}=(\PI_i)_{i\in \range{m}}$, given by

\begin{align}
\FCP(\bm{\mathcal{I}})&:=m^{-1}\sum_{i=1}^m \ind{Y_{n+i}\notin \PI_i}.\label{error}
\end{align}

It is clear from (<ref>) that the procedure $\bm{\mathcal{C}}(\alpha)$ (<ref>) controls the false coverage rate, that is, $\FCR(\bm{\mathcal{C}}(\alpha))):=\E[\FCP(\bm{\mathcal{C}}(\alpha))]\leq \alpha$.
However,  the error $\FCP(\bm{\mathcal{C}}(\alpha))$ naturally fluctuates around its mean and the event $\{\FCP(\bm{\mathcal{C}}(\alpha))\leq \alpha\}$ is not guaranteed. Hence, we aim at the following control in probability of the FCP:

\begin{align}
\P[\FCP(\bm{\mathcal{C}}(\alpha))\leq \ol{\alpha}]&\geq 1-\delta\label{controlalphaFWER}.
\end{align}

Several scenarios can be considered: $\alpha$ is fixed and we want to find a suitable bound $\ol{\alpha} = \ol{\FCP}_{\alpha,\delta}$ for the
“traditional” conformal procedure $\bm{\mathcal{C}}(\alpha)$; or conversely, $\ol{\alpha}$ is fixed and we want to adjust the
parameter $\alpha = t_{\ol{\alpha},\delta}$ of the procedure to ensure the probabilistic control at target level $\ol{\alpha}$.
For $\ol{\alpha}=0$, this reduces to $\P[\forall i\in\range{m}, \:Y_{n+i}\in \PI_i]\geq 1-\delta$, i.e., no false coverage with high probability. By applying a union bound, the procedure $\bm{\mathcal{C}}(\delta/m)$
satisfies the latter control, as already proposed by [25]. However,  in this case the predicted intervals can be trivial, that is,  $\bm{\mathcal{C}}(\delta/m)=\R^m$, if the test sample is too large, namely, $m> \delta(n+1)$.
Moreover, in a more general scenario the practitioner may want to adjust the parameter $\alpha=\wh{\alpha}$ on their own
depending on the data, for example based on some personal tradeoff between the probabilistic control obtained and the length of the corresponding prediction intervals —
this is the common practice of a “post-hoc” choice (made after looking at the data).
This motivates us to aim at a uniform (in $\alpha$) bound, that is,
find a family of random variables $({\overline{\FCP}}_{\alpha,\delta})_{\alpha\in (0,1)}$ such that

\begin{align}
\prob{\forall \alpha\in (0,1),\:\: \FCP(\bm{\mathcal{C}}(\alpha))\leq {\overline{\FCP}}_{\alpha,\delta}}&\geq 1-\delta\:.\label{controlalphaFWERunif}
\end{align}

Establishing such bounds is investigated in the next section.
This gives a guarantee on the FCP in any of the above scenarios, in particular a post-hoc choice of the parameter $\wh{\alpha}$.

Plot of $\FCP(\bm{\mathcal{I}})$ (<ref>) (dashed) and bound ${\overline{\FCP}}^{\mbox{\tiny DKW}}_{\hat{\alpha}(L),\delta}$  (<ref>) (<ref>) (solid, $\delta=0.2$) in function of interval length $2L$ in  the same setting and procedures as in Figure <ref>.

As a concrete example, one may want to choose a data-dependent $\wh{\alpha}$ to ensure prediction intervals $\bm{\mathcal{C}}(\alpha)$ of radius at most $L$, namely,

\begin{equation}\label{equ:length}
\widehat{\alpha}(L)=(n+1)^{-1}\sum_{i=1}^n \ind{S_i\leq L}.
\end{equation}

Guarantee (<ref>) yields a $(1-\delta)$-confidence error bound  ${\overline{\FCP}}_{\widehat{\alpha}(L),\delta}$ for this choice.

§.§ Controlling the error rates

To establish (<ref>) and (<ref>), we use that from (<ref>), (<ref>) and (<ref>), $\FCP(\bm{\mathcal{C}}(t))=\wh{F}_m(t)$ and thus for all $t\in [0,1]$,

\begin{align*}
\{\FCP(\bm{\mathcal{C}}(t))\leq \ol{\alpha}\}&=\set[1]{\wh{F}_m(t) \leq \ol{\alpha}}\\
&=\set[1]{m\wh{F}_m(t) \leq \lfloor \ol{\alpha} m\rfloor}\\
&=\set[1]{p_{(\lfloor \ol{\alpha} m\rfloor+1)}>t},
\end{align*}

where $p_{(1)}\leq \dots\leq p_{(m)}$ denote the ordered conformal $p$-values.
We deduce the following result.

Let $n,m\geq 1$. Consider the setting of Section <ref>, the conformal procedure $\bm{\mathcal{C}}(\alpha)$ given by (<ref>) and $P_{n,m}$ given by (<ref>). Then the following holds:

(i) for any $\ol{\alpha}\in [0,1]$, $\delta\in (0,1)$,  $\bm{\mathcal{C}}(\alpha=t_{\ol{\alpha},\delta})$ satisfies (<ref>) provided that $t_{\ol{\alpha},\delta}$ is chosen s.t.

\begin{equation}\label{equalphabaredelta}
\P_{\bm{p}\sim P_{n,m}}( p_{(\lfloor \ol{\alpha} m\rfloor+1)}\leq t_{\ol{\alpha},\delta})\leq \delta.
\end{equation}

(ii) for any $\delta\in (0,1)$,  $\paren[1]{{\overline{\FCP}}_{\alpha,\delta}}_{\alpha\in (0,1)}$ satisfies  (<ref>)  provided that

\begin{equation}\label{equalphabaredeltabis}
\P_{\bm{p}\sim P_{n,m}}\paren[1]{\exists \alpha\in (0,1)\::\: \wh{F}_m(\alpha) > {\overline{\FCP}}_{\alpha,\delta} }\leq \delta.
\end{equation}

Applying Corollary <ref> (i), for conformal prediction with guaranteed FCP, we obtain an adjusted level parameter
which can be computed numerically
(an explicit formula can also be given for $\alpha=0$, see Appendix <ref>). Applying Corollary <ref> (ii), and thanks to (<ref>), the following family bound $({\overline{\FCP}}_{\alpha,\delta})_{\alpha\in (0,1)}$  is valid for (<ref>)

\begin{align}
{\overline{\FCP}}^{\mbox{\tiny DKW}}_{\alpha,\delta}&= \paren[1]{\alpha + \lambda^{\mbox{\tiny DKW}}_{\delta,n,m}}\ind{\alpha\geq 1/(n+1)},  \label{boundfalsepositiveDKW}
\end{align}

with $\lambda^{\mbox{\tiny DKW}}_{\delta,n,m}>0$ given by (<ref>).
Obviously, numerical bounds can also be developed according to Remark <ref>.

§.§ Numerical experiments

To illustrate the performance of the method, we consider the following proof-of-concept regression model: $(W_i,Y_i)$ i.i.d. with $Y_i \:|\: W_i \sim \mathcal{N}(\mu(W_i),\sigma^2)$  for some unknown function $\mu$ and parameter $\sigma>0$.
To accommodate the transfer learning setting, we assume that we observe $X_i=f_1(W_i)$ in $\dtrain$ and $X_i=f_2(W_i)$ in $\dcal \cup \dtest$ for some transformations $f_1$ and $f_2$.
Three conformal procedures[Python code for (PI) based on implementation of [8].] $\bm{\mathcal{I}}=\bm{\mathcal{C}}(\alpha)=(\mathcal{C}_i(\alpha))_{i\in \range{m}}$ are considered which differ only in the construction of the scores: first, $\bm{\mathcal{I}}^{\tiny \mbox{naive}}$ consists in using a predictor of the usual form $\hat{\mu}(\cdot,\mathcal{D}_{{\tiny \mbox{train}}})$ hence ignoring the distribution difference between $\dtrain$ and $\dcal \cup \dtest$ (no transfer) with a RBF kernel ridge regression;
the second procedure $\bm{\mathcal{I}}^{\tiny \mbox{split}}$ ignores completely $\dtrain$ and works by splitting $\dcal$ in two new samples of equal size to apply the usual approach with these new (reduced) samples (transfer not needed); the third approach $\bm{\mathcal{I}}^{\tiny \mbox{transfer}}$ is the proposed one, and uses the transfer predictor $\hat{\mu}(\cdot;(\dtrain,\dxct))$
based on optimal transport
proposed by [9].
While all methods provide the correct $(1-\alpha)$ marginal coverage, we see from Figure <ref> that $\bm{\mathcal{I}}^{\tiny \mbox{transfer}}$ is much more accurate, which shows the benefit of using transfer learning and adaptive scores. Here, $\left |\dtrain\right |=5000$,
$n=m=75 $, $\mu(x)=\cos(x)$,  $W_i\sim\mathcal{U}(0,5)$, $f_1(x)=x$, $f_2(x)=0.6x+x^{2}/25$ and $\sigma=0.1$.
Next, for each of the three methods, the FCP and corresponding bounds (<ref>) are displayed in Figure <ref>. This illustrates both that each bound is uniformly valid in $L$ and that transfer learning reduces the FCP (and thus also the FCP bounds).

§ APPLICATION TO NOVELTY DETECTION

§.§ Setting

In the novelty detection problem, we
observe the two following independent samples:

* a training null sample $\mathcal{D}_{{\tiny \mbox{null}}}$ of $n_0$ nominal data points in $\R^d$ which are i.i.d. with common distribution $P_0$;

* a test sample $\mathcal{D}_{{\tiny \mbox{test}}}=(X_i, i\in \range{m})$ of independent points in $\R^d$ either distributed as $P_0$ or not.

The aim is to decide if each $X_i$ is distributed as the training sample (that is, as $P_0$) or not.
This long standing problem in machine learning has been recently revisited with the aim of controlling the proportion of errors among the items declared as novelties [3]; let $\cH_0=\{i\in \range{m}\::\: X_i\sim P_0\}$ corresponding to the set of non-novelty in the test sample and consider the false discovery proportion

\begin{equation}\label{FDP}
\FDP(R)=\frac{|R\cap \cH_0|}{|R|\vee 1},
\end{equation}

for any (possibly random) subset $R\subset \range{m}$ corresponding to the $X_i$'s declared as novelties.
The advantage of considering $\FDP(R)$ for measuring the errors has been widely recognized in the multiple testing literature since the fundamental work of [4] and its popularity is nowadays increasing in large scale machine learning theory, see [3, 14, 10, 2], among others.
The main advantage of $\FDP(R)$ is that the number of errors  $|R\cap \cH_0|$ is rescaled by the number of declared novelties $|R|$, which makes it scale invariant with respect to the size $m$ of the test sample, so that novelty detection can still be possible in large scale setting.

§.§ Adaptive scores

Following [3, 14], we assume that scores are computed as follows:

* Split the null sample $\mathcal{D}_{{\tiny \mbox{null}}}$ into $\mathcal{D}_{{\tiny \mbox{train}}}$ and  $\mathcal{D}_{{\tiny \mbox{cal}}}=(X_i, i\in \range{n})$ for some chosen $n\in (1,n_0)$;

* Compute novelty scores $S_{i}=g(X_{i})$, $i\in \range{n+m}$,
for some score function $g:\R^d\to \R$ (discussed below);

* Compute conformal $p$-values as in (<ref>).

In the work of [3], the score function is built from $\mathcal{D}_{{\tiny \mbox{train}}}$ only, using a one-class classification method (classifier solely based on null examples), which makes the scores independent conditional to $\dtrain$. The follow-up work [14] considers a score function depending both on $\mathcal{D}_{{\tiny \mbox{train}}}$ and $\mathcal{D}_{{\tiny \mbox{cal}}}\cup \mathcal{D}_{{\tiny \mbox{test}}}$ (in a permutation-invariant way of the sample $\mathcal{D}_{{\tiny \mbox{cal}}}\cup \mathcal{D}_{{\tiny \mbox{test}}}$), which allows to use a two-class classification method including test examples. Doing so, the scores are adaptive to the form of the novelties present in the test sample, which
significantly improves novelty detection (in a nutshell: it is much easier to detect an object when we have some examples of it).
While the independence of the scores is lost, an appropriate exchangeability property is maintained so that we can apply our theory in that case, by assuming in addition (<ref>).

§.§ Methods and FDP bounds

Let us consider any thresholding novelty procedure

\begin{equation}\label{thresrule}
\mathcal{R}(t):=\{i\in \range{m}\::\:p_i\leq t\}, \:\: t\in (0,1).
\end{equation}

Then the following result holds true.

In the above novelty detection setting and under Assumption <ref>, the family of thresholding novelty procedures (<ref>) is such that, with probability at least $1-\delta$, we have for all  $ t\in (0,1)$,

\begin{equation}\label{ThresholdFDPboundDKW}
\FDP(\mathcal{R}(t))\leq  \frac{\hat{m}_0 I_n(t) + \hat{m}_0 \lambda^{\mbox{\tiny DKW}}_{\delta,n,\hat{m}_0}}{1\vee |\mathcal{R}(t)|}=:{\overline{\FDP}}^{\tiny \mbox{DKW}}_{t,\delta},
\end{equation}

where $\lambda^{\mbox{\tiny DKW}}_{\delta,n,\hat{m}_0}$ is given by (<ref>) and
$\hat{m}_0$ is any random variable such that

\begin{equation}\label{m0hat}
\hat{m}_0\geq \max\bigg\{r\::\: \inf_t\frac{\sum_{i=1}^m\ind{p_i> t} + r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r} }{1-I_{n}(t)}\geq r\bigg\},
\end{equation}

where $r$ is in the range $\range{m}$ and the maximum is equal to $m$ if the set is empty.

The proof is provided in Appendix <ref>.

Among thresholding procedures (<ref>), AdaDetect [14] is obtained by applying the Benjamini-Hochberg (BH) procedure [4] to the conformal $p$-values. It is proved to control the expectation of the FDP (that is, the false discovery rate, FDR) at level $\alpha$.
Applying Corollary <ref> provides in addition an FDP bound for AdaDetect, uniform in $\alpha$, see  Appendix <ref>.

Plot of $\FDP(\mathcal{R}(t))$ (<ref>)(<ref>) (dashed) and bound ${\overline{\FDP}}^{\mbox{\tiny DKW}}_{t,\delta}$  (<ref>)  (solid, $\delta=0.2$) in function of the threshold $t$ for $\mathcal{R}(t)$ (<ref>) with a score obtained either with a one-class classification (non-adaptive) or a two-class classification (adaptive).

§.§ Numerical experiments

We follow the numerical experiments on “Shuttle” datasets of [14][The Python code uses the implementation of the procedure AdaDetect of  [13].].
In Figure <ref>, we displayed the true FDP and the corresponding bound (<ref>) when computing $p$-values based on different scores: the non-adaptive scores of [3] obtained with  isolation forest one-class classifier; and the adaptive scores of [14] obtained with random forest two-class classifier. While the advantage of considering adaptive scores is clear (smaller FDP and bound)
, it illustrates that the bound is correct simultaneously on $t$.
Additional experiments are provided in Appendix <ref>.

§ CONCLUSION

The main takeaway from this work is the characterization of a “universal” joint distribution $P_{n,m}$ for conformal $p$-values
based on $n$ calibration points and  $m$ test points.
We derived as a consequence a non-asymptotic
concentration inequality for the $p$-value empirical distribution function; numerical procedures can also be of use for calibration in practice.
This entails uniform error bounds on the false coverage/false discovery proportion that hold with high probability, while standard results are only marginal or in expectation and not uniform in the decision. Since the results hold under the
score exchangeability assumption only, they are applicable to adaptive score procedures using the calibration and test sets for training.

§ ACKNOWLEDGEMENTS

We would like to thank Anna Ben-Hamou and Claire Boyer for constructive discussions and Ariane Marandon for her support with the code. The authors acknowledge the grants ANR-21-CE23-0035 (ASCAI) and ANR-19-CHIA-0021-01
(BISCOTTE) of the French National Research Agency ANR and the Emergence project MARS.

[1]
Balasubramanian, V., Ho, S.-S., and Vovk, V. (2014).
Conformal prediction for reliable machine learning: theory,
adaptations and applications.
Morgan Kaufmann books.

[2]
Bashari, M., Epstein, A., Romano, Y., and Sesia, M. (2023).
Derandomized novelty detection with FDR control via conformal
arXiv preprint 2302.07294.

[3]
Bates, S., Candès, E., Lei, L., Romano, Y., and Sesia, M. (2023).
Testing for outliers with conformal p-values.
Ann. Statist., 51(1):149–178.

[4]
Benjamini, Y. and Hochberg, Y. (1995).
Controlling the false discovery rate: a practical and powerful
approach to multiple testing.
J. Roy. Statist. Soc. Ser. B, 57(1):289–300.

[5]
Benjamini, Y. and Yekutieli, D. (2001).
The control of the false discovery rate in multiple testing under
Ann. Statist., 29(4):1165–1188.

[6]
Bian, M. and Barber, R. F. (2022).
Training-conditional coverage for distribution-free predictive
arXiv preprint arXiv:2205.03647.

[7]
Blanchard, G., Neuvial, P., and Roquain, E. (2020).
Post hoc confidence bounds on false positives using reference
Ann. Statist., 48(3):1281–1303.

[8]
Boyer, C. and Zaffran, M. (2023).
Tutorial on conformal prediction.

[9]
Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy, A. (2017).
Joint distribution optimal transportation for domain adaptation.
In Advances in neural information processing systems 30 (NIPS
2017), volume 30.

[10]
Jin, Y. and Candès, E. J. (2023).
Model-free selective inference under covariate shift via weighted
conformal p-values.
arXiv preprint arXiv:2307.09291.

[11]
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. (2018).
Distribution-free predictive inference for regression.
J. Amer. Stat. Assoc., 113(523):1094–1111.

[12]
Li, J., Maathuis, M. H., and Goeman, J. J. (2022).
Simultaneous false discovery proportion bounds via knockoffs and
closed testing.
arXiv preprint arXiv:2212.12822.

[13]
Marandon, A. (2022).
Machine learning meets FDR.

[14]
Marandon, A., Lei, L., Mary, D., and Roquain, E. (2022).
Machine learning meets false discovery rate.
arXiv preprint 2208.06685.

[15]
Marques F., P. C. (2023).
On the universal distribution of the coverage in split conformal
arXiv preprint 2303.02770.

[16]
Massart, P. (1990).
The tight constant in the Dvoretzky-Kiefer-Wolfowitz
Ann. Probab., 18(3):1269–1283.

[17]
Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. (2002).
Inductive confidence machines for regression.
In 13th European Conference on Machine Learning (ECML 2002),
pages 345–356. Springer.

[18]
Romano, J. P. and Wolf, M. (2005).
Exact and approximate stepdown methods for multiple hypothesis
J. Amer. Statist. Assoc., 100(469):94–108.

[19]
Romano, Y., Patterson, E., and Candes, E. (2019).
Conformalized quantile regression.
Advances in neural information processing systems, 32.

[20]
Sarkar, S. and Kuchibhotla, A. K. (2023).
Post-selection inference for conformal prediction: Trading off
coverage for precision.
arXiv preprint arXiv:2304.06158.

[21]
Saunders, C., Gammerman, A., and Vovk, V. (1999).
Transduction with confidence and credibility.
In 16th International Joint Conference on Artificial
Intelligence (IJCAI 1999), pages 722–726.

[22]
Simes, R. J. (1986).
An improved Bonferroni procedure for multiple tests of
Biometrika, 73(3):751–754.

[23]
Vanschoren, J., van Rijn, J. N., Bischl, B., and Torgo, L. (2013).
Openml: networked science in machine learning.
SIGKDD Explorations, 15(2):49–60.

[24]
Vovk, V. (2012).
Conditional validity of inductive conformal predictors.
In 4th Asian conference on machine learning (ACML 2012), pages
475–490. PMLR.

[25]
Vovk, V. (2013).
Transductive conformal predictors.
In Artificial Intelligence Applications and Innovations: 9th
IFIP WG 12.5 International Conference (AIAI 2013), pages 348–360. Springer.

[26]
Vovk, V., Gammerman, A., and Shafer, G. (2005).
Algorithmic learning in a random world.

[27]
Zhuang, F., Qi, Z., Duan, K., Xi, D., Zhu, Y., Zhu, H., Xiong, H., and He, Q.
A comprehensive survey on transfer learning.
Proceedings of the IEEE, 109(1):43–76.

§ EXACT FORMULAS FOR $P_{N,M}$

In this section, we provide new formulas for the distribution $P_{n,m}$ given by (<ref>).
First let for $\bm{j}=(j_1,\dots,j_m)\in \range{n+1}^m$,   $\bm{M}(\bm{j}):=(M_k(\bm{j}))_{k\in \range{n+1}}$ where  $M_k(\bm{j}):=|\{i\in \range{m}\::\: j_i=k\}|$ is the number of coordinates of $\bm{j}$ equal to $k$, for $k\in \range{n+1}$, and $\bm{M}(\bm{j})!:=\prod_{k=1}^{n+1} (M_k(\bm{j})!)$.

$P_{n,m}$ corresponds to the distribution of the colors of $m$ successive draws in a standard Pólya urn model with $n+1$ colors labeled as $\set[1]{\frac{\l}{n+1},\l\in \range{n+1}}$ (with an urn starting with $1$ ball of each color). That is,
for $\bm{p}\sim P_{n,m}$ in (<ref>), we have

(i) Sequential distribution: for all $i\in \range{0,m-1}$,
the distribution of $p_{i+1}$ conditionally on $p_1,\dots,p_{i}$ does not depend on $m$ and is given by

\begin{equation}
\mathcal{D}(p_{i+1}\:|\: p_1,\dots,p_{i}) = \sum_{j=1}^{n+1} \frac{1+\sum_{k=1}^{i}\ind{p_k=j/(n+1)}}{n+1+i}\delta_{j/(n+1)}\label{equMarkov}.
\end{equation}

(ii) Joint distribution: for all vectors $\bm{j}\in \range{n+1}^m$,

\begin{equation}
\P\paren{
\bm{p}=\frac{\bm{j}}{n+1}
} =
\bm{M}(\bm{j})!
\frac{n!}{(n+m)!}\label{equjoint},
\end{equation}

(iii) Histogram distribution: the histogram of $\bm{p}$ is uniformly distributed on the set of histograms of $m$-sample into $n+1$ bins, that is, for all $\bm{m}=(m_1,\dots,m_{n+1})\in \range{0,m}^{n+1}$ with $ m_1+\dots+m_{n+1}=m$,

\begin{equation}
\P\big(\bm{M}\paren[1]{(n+1)\bm{p}}=\bm{m}\big) = \binom{n+m}{m}^{-1}.
\label{equunifhisto}
\end{equation}

In particular, conditionally on $\bm{M}\paren[1]{(n+1)\bm{p}}$, the variable $\bm{p}$ is uniformly distributed on the set of possible trajectories, that is,
for all vectors $\bm{j}\in \range{n+1}^m$,

\begin{equation}
\P\paren{\bm{p}=\frac{\bm{j}}{n+1} \:\bigg|\: \bm{M}\paren[1]{(n+1)\bm{p}}=\bm{M}\paren[1]{\bm{j}}} = \frac{\bm{M}\paren[1]{\bm{j}}!}{m!}.
\label{equuniftraj}
\end{equation}

Theorem <ref> is proved in Section <ref> for completeness.
Theorem <ref> (i) gives the mechanism of the Pólya urn model: Namely, the urn first contains one ball of each of the $n+1$ colors, so $p_1$ has a uniform distributed on $\set[1]{\frac{\l}{n+1},\l\in \range{n+1}}$; then, given $p_1=\ell/(n+1)$, we have drawn a ball of color $\ell$ and we put back this ball in the urn with another one of the same color $\ell$, so $p_2$ is generated according to the distribution on $\set[1]{\frac{\l}{n+1},\l\in \range{n+1}}$ with equal chance ($=1/(n+2)$) of generating $k/(n+1)$, $k\neq \l$, and twice more chance ($=2/(n+2)$) of generating $\l/(n+1)$. Recursively, given $p_1,\dots,p_{i}$, the random variable $p_{i+1}$ is generated in $\set[1]{\frac{\l}{n+1},\l\in \range{n+1}}$ according to the sizes of the histogram of the sample $((n+1)p_1,\dots, (n+1)p_{i})$, see Figure <ref>.

Theorem <ref> (ii) provides the exact dependency structure between the $p$-values: for instance, $\bm{M}(\bm{j})!=1$ when the coordinates of $\bm{j}=(j_1,\dots,j_m)$ are all distinct, while $\bm{M}(\bm{j})!=m!$ when the coordinates of $\bm{j}=(j_1,\dots,j_m)$ are the same. This means that the distribution slightly favors the $\bm{j}$ with repeated entries. This shows that the conformal $p$-values are not i.i.d. but have a positive structure of dependency. This is in accordance with the specific positive dependence property (called PRDS) already shown by [3, 14].

Theorem <ref> (iii) shows an interesting non-concentration behavior of $P_{n,m}$ when $n$ is kept small: if the $p_i$'s were i.i.d. uniform on $\set[1]{\frac{\l}{n+1},\l\in \range{n+1}}$ then the histogram $\bm{M}((n+1)\bm{p})$ would follow a multinomial distribution  and the histogram would concentrate around the uniform histogram as $m$ tends to infinity. Rather, the $p_i$'s are here  only exchangeable, not i.i.d., and the histogram does not concentrate when $m$ tends to infinity while $n$ is small. As a case in point, for $n=1$, $M_1((n+1)\bm{p})$ is uniform on $\range{m}$, whatever $m$ is, see (<ref>).
Nevertheless, we will show in the next section that a concentration occurs when both $m$  and $n$ tend to infinity.

Note that $P^U$ in (<ref>) is the conditional distribution that one would get by applying the de Finetti theorem to the infinite exchangeable sequence $(p_i)_{i\geq 1}$ with  $(p_1,\dots,p_m)\sim P_{n,m}$ for all $m$.

Illustration of the sequential realization of $P_{n,m}$ as proved in Theorem <ref> (ii) for $n=5$ and $m=6$.

Relation to [15].
As a consequence of (<ref>), given any $I\subset \set{\frac{\ell}{n+1}, \ell\in \range{n+1}}$, we have

\begin{align*}
\P(p_{i+1}\in {I}\:|\: p_1,\dots,p_{i}) {= \frac{|I|+N_i(I)}
=\P\left(p_{i+1}\in {I} \:\Big|N_i(I)
\right),}
\end{align*}

where $N_i(I) = |\set{ k \in \range{i}: p_k \in I)}|$.
In words, it means that the Pólya urn model continues to hold if we group (or “re-paint”) the
initial $(n+1)$ colors into only two colors, determined by whether the original color label belongs to $I$ or not.

In particular, we recover the Pólya urn model put forward by [15]: letting $Z_i=\ind{p_i>\alpha}$, we have that
for all $i\in \range{0,m-1}$,
the distribution of $Z_{i+1}$ conditionally on $Z_1,\dots,Z_{i}$ does not depend on $m$ and is given by

\begin{equation}
\mathcal{D}(Z_{i+1}\:|\: Z_1,\dots,Z_{i}) =  \frac{\lfloor \alpha(n+1)\rfloor+\sum_{k=1}^{i}\ind{Z_k=j}}{n+1+i}\delta_{0} +\frac{\lceil (1-\alpha)(n+1)\rceil+\sum_{k=1}^{i}\ind{Z_k=j}}{n+1+i}\delta_{1} \label{equMarkov2}.
\end{equation}

Hence, the distribution of $(Z_1,\dots,Z_m)$ corresponds to the distribution of the colors of $m$ successive draws in a standard Pólya urn model with $2$ colors labeled as $\{0,1\}$ (with an urn starting with $\lfloor \alpha(n+1)\rfloor$ balls $0$ and $\lceil (1-\alpha)(n+1)\rceil$ balls $1$).

In particular, we recover Theorem 1 of [15].

In the setting of Theorem <ref>, we have for all $\alpha\in (0,1)$ and $k\in \range{m}$, by denoting $k_0=\lceil \alpha(n+1)\rceil$,

\begin{equation}\label{equMarques}
\P\paren{\wh{F}_m(\alpha) = \frac{k}{m}}={m \choose k}  \frac{(n-k_0+1)\dots (n-k_0 + m-k)\times k_0 \dots(k_0+k-1)}{(n+1)\dots (n+m) }.
\end{equation}

By Proposition <ref>, (<ref>) and the notation of (<ref>), we have

\begin{align*}
\P\paren{\wh{F}_m(\alpha) = \frac{k}{m} }&={m \choose k}\E\left[ (U_{(k_0)})^k (1-U_{(k_0)})^{m-k}\right]\\
&={m \choose k} \frac{n!}{(k_0-1)! (n-k_0)!} \int_0^1  u^{k+k_0-1} (1-u)^{m-k+n-k_0} du\\
&={m \choose k} \frac{n!}{(k_0-1)! (n-k_0)!} \frac{(k+k_0-1)!(m+n-k-k_0)!}{(m+n)!},
\end{align*}

by using that $U_{(k_0)}$ follows a beta distribution with parameter $(k_0,n+1-k_0)$  and by using the beta distribution with parameter $(k+k_0,m+n+1-k-k_0)$. This shows the result.

§ NUMERICAL BOUNDS AND TEMPLATES

The bound proposed in Theorem <ref> are explicit and elegant, but can be conservative in some cases and we develop here the numerical approach mentioned  in Remark <ref>.

We rely on showing (<ref>), which immediately implies a confidence envelope on $\wh{F}_m$ because

\begin{align*}
\set{\forall k\in \mathcal{K}\::\: \wh{F}_m(t_k)\leq \frac{k}{m} }&=\set{\forall k\in \mathcal{K}\::\: \wh{F}_m(t_k)< \frac{k+1}{m} }\\
&=\{\forall k\in \mathcal{K}\::\: p_{(k+1)} >t_k \}.
\end{align*}

To establish (<ref>), we use the notion of template introduced by [7], see also [12].
A template is a one-parameter family $t_k(\lambda)$, $\lambda\in [0,1]$, $k\in \mathcal{K}\subset \range{m}$, such that $t_k(0) = 0$ and $t_k(\cdot)$ is continuous increasing on $[0, 1]$.
From above, we have for all $\lambda$,

\begin{align*}
\{\forall k\in \mathcal{K}\::\: \wh{F}_m(t_k(\lambda))\leq k/m \}&=\{\forall k\in \mathcal{K}\::\: p_{(k+1)} >t_k(\lambda) \}\\
&=\Big\{\min_{k\in \mathcal{K}}\{t_k^{-1}(p_{(k+1)})\}>\lambda\Big\}.
\end{align*}

Hence, let us consider

\begin{equation}\label{equlambdacal}
\lambda(\delta,n,m) = \max\set{\lambda \in \Lambda\::\: \P_{\bm{p}\sim P_{n,m}}\paren[2]{\min_{k\in \mathcal{K}}\{t_k^{-1}(p_{(k)})\}>\lambda}\geq 1-\delta},
\end{equation}

where $\Lambda$ is the finite set $\{t_k^{-1}(\ell/(n+1)),  k\in \mathcal{K}, \ell\in \range{n+1}\}$.
Then by Proposition <ref> we have the following result.

Let us consider the process $\wh{F}_m$ defined by (<ref>), the distribution $P_{n,m}$ given by (<ref>), a template $t_k(\lambda)$, $\lambda\in [0,1]$, $k\in \mathcal{K}$ as above, and assume (<ref>) and (<ref>). Then we have for all $\delta\in (0,1)$, $n,m\geq 1$,

\begin{align}
\P\paren{\forall k\in \mathcal{K}\::\: \wh{F}_m\paren[2]{t_k\paren[1]{\lambda(\delta,n,m)}}\leq \frac{k}{m}}\geq 1-\delta,
\label{ineqlambdacal}
\end{align}

for $\lambda(\delta,n,m)$ given by (<ref>).

Here are two template choices:

* The linear template $t_k(\lambda)=k \lambda /m$, $\mathcal{K}=\range{m}$, which leads to the inequality

\P\paren{\exists t \in (0,1) \::\: \wh{F}_m( t)> \frac{\lceil tm/\lambda(\delta,n,m)\rceil}{ m}}\leq \delta,

which recovers the Simes inequality (<ref>) with an adjusted scaling parameter.

* The “beta template” [7], for which $t_k(\lambda)$ is the $\lambda$-quantile of the distribution $\mbox{Beta}(k,m+1-k)$ and thus
$\Lambda=\{F_{\tiny{\mbox{Beta}(k,m+1-k)}}(\ell/(n+1)),  k\in \mathcal{K}, \ell\in \range{n+1}\}$. For instance, it can be used with $\mathcal{K}=\{1+k\lceil \log(m)\rceil ,k\in \range{K}\}$.

§ PROOFS

§.§ Proof of Proposition <ref>

Assumption (<ref>) implies that marginal score distribution is atomless, so that $F$ is
continuous and $1-F(S_i)$ has $\mathrm{Unif}[0,1]$ distribution.
Therefore, $(U_1,\dots,U_{n+m})=(1-F(S_1),\dots,1- F(S_{n+m}))$ are i.i.d. $\sim \mathrm{Unif}[0,1]$. Recall

\[
p_i=(n+1)^{-1}\paren[3]{1+\sum_{j=1}^n \ind{S_j\geq S_{n+i}}},\:\: i\in \range{m},
\]

since $p_i$ is a function of $S_{n+i}$ and $\dcal$ only, it follows that conditionally on $\dcal$, the variables $p_1,\dots,p_m$ are independent
(and identically distributed).

Since $F$ is continuous, it holds $F^\dagger(F(S_i))=S_i$ almost surely, where $F^\dagger$ is the generalized inverse of $F$. Therefore
$\ind{S_j \geq S_{n+i}} = \ind{U_j \leq U_{n+i}}$ almost surely. Hence, $p_1$ is distributed as

(n+1)^{-1}\paren[3]{1+\sum_{j=1}^n \ind{U_j\leq U_{n+1}}} =(n+1)^{-1}\paren[3]{1+\sum_{j=1}^n \ind{U_{(j)}\leq U_{n+1}}},

where $U_{(1)}\leq \dots \leq U_{(n)}$ denotes the order statistics of $(U_1,\dots,U_n)$. Therefore, we have for all $x\in [0,1] $,

\begin{align*}
\P(p_1\leq x\:|\: \dcal)&=\P\paren[3]{1+\sum_{j=1}^n \ind{U_{(j)}\leq U_{n+1}} \leq x(n+1) \Big| \dcal }\\
\P\paren[3]{1+\sum_{j=1}^n \ind{U_{(j)}\leq U_{n+1}} \leq \lfloor x(n+1) \rfloor \Big| \dcal }\\
&= \P(U_{n+1}<U_{(\lfloor x(n+1) \rfloor)} | \dcal ) = U_{(\lfloor x(n+1) \rfloor)},
\end{align*}

which finishes the proof.

§.§ Proof of Proposition <ref>

If there are no tied scores, which by assumption (<ref>) happens with probability 1, the ranks $R_i$ of the ordered scores are
well-defined and
the vector $(p_1,\dots,p_{m})$ is only a function of the rank vector $(R_1,\dots,R_{n+m})$.
Namely, $R_i\leq  R_j$ if and only if $S_i\leq S_j$, and the conformal $p$-values (<ref>) can be written as

\begin{equation*}
p_i=(n+1)^{-1}\paren[3]{1+\sum_{j=1}^n \ind{R_j\geq  R_{n+i}}},\:\: i\in \range{m}.
\end{equation*}

Now, by (<ref>), the vector $(R_1,\dots,R_{n+m})$ is uniformly distributed on the permutations of $\range{n+m}$.
Any score distribution satisfying (<ref>) and (<ref>) therefore gives rise to the same rank distribution,
and thus the same joint $p$-value distribution. This joint distribution has been identified as (<ref>)-(<ref>)
from the result of Proposition <ref> in the particular case of i.i.d. scores. (Thus the i.i.d. assumption turns out to be unnecessary for what
concerns the joint, unconditional distribution of the $p$-values, but provides a convenient representation.)

§.§ Proof of Theorem <ref>

Proof of (ii)
By (<ref>),(<ref>) the permutation that orders the scores $(S_1,\dots,S_{n+m})$ that is $\sigma$ such that

S_{()}=(S_{\sigma(1)}> \dots >S_{\sigma(n+m)}),

is uniformly distributed in the set of permutations of $\range{n+m}$.
In addition, $\sigma$ is independent of the order statistics $S_{()}$ and we seek for identifying the distribution of $(p_1,\dots,p_m)$ conditionally on $S_{()}$. Next, using again (<ref>), we can assume without loss of generality that $j_1\leq \dots\leq j_m$ when computing the probability in (<ref>).
Now, due to the definition (<ref>), the event $\{(p_1,\dots,p_m)=(j_1/(n+1),\dots,j_m/(n+1)\}$ corresponds to a specific event on $\sigma$. Namely, by denoting $(a_1,\dots,a_\l)$ the vector of unique values of the set $\{j_1,\dots,j_m\}$ with $1\leq a_1<\dots<a_\l\leq n$, and $M_k=\sum_{i=1}^m \ind{j_i=a_k}$, $1\leq k\leq \ell$, the corresponding multiplicities, the above event corresponds to the situation

\begin{align*}
&\underbrace{S_{\sigma(1)}>\cdots>S_{\sigma( a_1-1)}}_{ a_1-1 \text{ null scores}}>\underbrace{S_{\sigma(a_1)}>\cdots>S_{\sigma(a_1+M_1-1)}}_{M_1\text{ test scores in $\{S_{n+1},\dots,S_{n+M_1}\}$}}>\\
&\underbrace{S_{\sigma( a_1+M_1)}>\cdots>S_{\sigma( a_2+M_1-1)}}_{\text{$ a_2- a_1$ null scores}}>\underbrace{S_{\sigma(a_2+M_1)}>\cdots>S_{\sigma_1(a_2+M_1+M_2-1)}}_{M_2\text{ test scores in $\{S_{n+M_1+1},\dots,S_{n+M_1+M_2}\}$}}>\cdots\\
&\underbrace{S_{\sigma( a_{\ell-1}+M_1+\cdots+M_{\ell-1})}>\cdots>S_{\sigma( a_\ell+M_1+\cdots+M_{\ell-1}-1)}}_{\text{$ a_\ell- a_{\ell-1}$  null scores}}>\underbrace{S_{\sigma(a_\ell+M_1+\cdots+M_{\ell-1})}>\cdots>S_{\sigma(a_\ell+m-1)}}_{M_\ell\text{ test scores in $\{S_{ n+M_1+\cdots+M_{\ell-1}+1},\dots,S_{n+m}\}$}}>\\
&\underbrace{S_{( a_\ell+m)}>\cdots>S_{(n+m)}}_{n- a_\ell+1\text{ null scores}}.
\end{align*}

This event can be formally described as follows:

\begin{align*}
\Big\{\forall k \in \range{\ell}\::\: &\sigma\paren[1]{\left\{a_\ell+M_1+\cdots+M_{k-1},\dots,a_\ell+M_1+\cdots+M_{k}-1\right\}} \\
& = \left\{n+M_1+\cdots+M_{k-1}+1,\dots,n+M_1+\cdots+M_{k}\right\}\Big\}.
\end{align*}

Since $\sigma$ is uniformly distributed in the set of permutations of $\range{n+m}$, the probability of this event (conditionally on $S_{()}$) is equal to
n! \big(\prod_{k=1}^\ell (M_k!)\big)/(n+m)!,
which yields  (<ref>).

Proof of (i)
By using (<ref>) of (ii), we have

\P(p_{i+1}=j_{i+1}/(n+1)\:|\: (p_1,\dots,p_i)=(j_1/(n+1),\dots,j_i/(n+1))) = \frac{ \bm{M}(j_1,\dots,j_{i+1})! \frac{n!}{(n+i+1)!}}{ \bm{M}(j_1,\dots,j_i)! \frac{n!}{(n+i)!}}.

Now, we have

\begin{align*}
\bm{M}(j_1,\dots,j_{i+1})!&=\prod_{j=1}^{n+1} \left[\left(\sum_{k=1}^{i+1} \ind{j_k=j}\right)!\right]=\prod_{j=1}^{n+1} \left[\left(\sum_{k=1}^{i} \ind{j_k=j}+\ind{j_{i+1}=j}\right)!\right]\\
&=\prod_{j=1}^{n+1} \left(\sum_{k=1}^{i} \ind{j_k=j}\right)! \left[1+\ind{j_{i+1}=j}\sum_{k=1}^{i} \ind{j_k=j}\right]\\
&=\bm{M}(j_1,\dots,j_{i})!\left[1+\ind{j_{i+1}=j}\sum_{k=1}^{i} \ind{j_k=j}\right].
\end{align*}

This proves (<ref>).

Proof of (iii)
For all $\bm{m}=(m_1,\dots,m_{n+1})\in \range{0,m}^{n+1}$ with $ m_1+\dots+m_{n+1}=m$,  we have

\begin{align*}
\P\big(\bm{M}((n+1)\bm{p})=\bm{m}\big) &=\sum_{\bm{j}\in \range{n+1}^m} \ind{\bm{M}(\bm{j})=\bm{m}} \P\big((n+1)\bm{p}=\bm{j}\big)\\
&=\bm{m}! \frac{n!}{(n+m)!}\sum_{\bm{j}\in \range{n+1}^m} \ind{\bm{M}(\bm{j})=\bm{m}}  \\
&=\bm{m}! \frac{n!}{(n+m)!} \frac{m!}{\bm{m}!}= \frac{n!m!}{(n+m)!},
\end{align*}

where we have used (ii) and the multinomial coefficient.

§.§ Proof of Theorem <ref>

First observe that the LHS of (<ref>) is $0$ if $\lambda\geq 1$ so that we can assume $\lambda<1$.

Let us  prove (<ref>) with the more complex bound

\begin{align}
B^{\mbox{\tiny DKWfull}}(\lambda,n,m)&:=
\frac{n}{n+m} e^{-2m \lambda^2} + \frac{m}{n+m} e^{-2n\lambda^2} +  C_{\lambda,n,m}\frac{2\sqrt{2\pi}\lambda nm}{(n+m)^{3/2}}  e^{-\frac{2nm}{n+m}\lambda^2},
\label{BDKWfull}
\end{align}

where $C_{\lambda,n,m}=\P(\mathcal{N}(\lambda \mu,\sigma^2)\in [0,\lambda])<1$, for $\sigma^2=(4(n+m))^{-1}$ and $\mu=n(n+m)^{-1}$.
Let us comment the expression (<ref>) of $B^{\mbox{\tiny DKWfull}}(\lambda,n,m)$. As we can see, the role of  $n$ and $m$ are symmetric (except in $C_{\lambda,n,m}$, that we can always further upper-bound by $1$), and the two first terms are a convex combination of the usual DKW bounds for $m$ and $n$ i.i.d. variables, respectively. The third term is a “crossed” term between $n$ and $m$, which becomes negligible if $n\gg m$ or $n\ll m$ but should be taken into account otherwise.

Below, we establish

\begin{align}
\P\paren[3]{\sup_{t\in [0,1]}\paren[1]{\wh{F}_m(t) - I_n(t)} > \lambda}&\leq B^{\mbox{\tiny DKWfull}}(\lambda,n,m);\label{boundDKWfullup}\\
\P\paren[3]{\sup_{t\in [0,1]}\paren[1]{-\wh{F}_m(t) + I_n(t)} > \lambda}&\leq B^{\mbox{\tiny DKWfull}}(\lambda,n,m);\label{boundDKWfulldown}\\
\P\paren{\norm[1]{\wh{F}_m - I_n}_\infty > \lambda}&\leq  2  B^{\mbox{\tiny DKW}}(\lambda,n,m).\label{boundDKWfulltwosided}
\end{align}

The result will be proved from (<ref>) because $B^{\mbox{\tiny DKWfull}}(\lambda,n,m)\leq B^{\mbox{\tiny DKW}}(\lambda,n,m)$ since $n\vee m\geq nm/(n+m)$ and $C_{\lambda,n,m}\leq 1$.

The proof relies on Proposition <ref> and the representation (<ref>). Let $U=(U_1,\dots,U_n)$ i.i.d. $\sim U(0,1)$,  and denote $F^U(x)=U_{(\lfloor (n+1)x\rfloor)}$, $x\in [0,1]$. Conditionally on $U$, draw $(q_i(U),i\in \range{m})$  i.i.d. of common c.d.f. $F^U$ and let

\wh{G}_m(t)=m^{-1}\sum_{i=1}^m \ind{q_i(U)\leq t}, \:\:\: t\in [0,1],

the empirical c.d.f. of $(q_i(U),i\in \range{m})$. By Proposition <ref>, we have that
$\wh{F}_m$ has the same distribution as $\wh{G}_m$ (unconditionally on $U$), so that for any fixed $n,m\geq 1$ and $\lambda>0$,

\begin{align}\label{equinterm}
\P\paren[3]{\sup_{t\in [0,1]}\paren[1]{\wh{F}_m(t) - I_n(t)} > \lambda}&=\e{\P\paren[3]{ \sup_{t\in [0,1]}\paren[1]{\wh{G}_m(t) - I_n(t)} > \lambda\:\Big|\: U}}.
\end{align}

We now prove the bound (<ref>) (the proof for (<ref>) is analogous).
Denote $Z=\sup_{t\in [0,1]}\paren[1]{F^U(t)-I_n(t)}\in [0,1]$.
We write by (<ref>) and the triangle inequality

\begin{align*}
\P\paren{\sup_{t\in [0,1]}\paren[1]{\wh{F}_m(t) - I_n(t)} > \lambda} &\leq \e{ \P\Big(\sup_{t\in [0,1]}(\wh{F}_m(t) - F^U(t)) + Z  > \lambda\:\Big|\: U\Big)}
\\
&\leq \e{ \P\Big(\sup_{t\in [0,1]}(\wh{F}_m(t) - F^U(t))  \geq  \big(\lambda- Z\big)_+\:\Big|\: U\Big)}\\
&\leq \e{ e^{- 2m  (\lambda- Z)^2_+}}.
\end{align*}

The last inequality above is the DKW inequality [16] applied to control the inner conditional probability, since
conditionally to $U$, $\wh{F}_m$ is the e.c.d.f. of $(q_i(U),\in \range{m})$, which are i.i.d. $\sim F^U$; and $Z$ conditional to $U$ is a constant.
Now the last bound can be rewritten as

\begin{align}
\int_0^{1} \P\paren{e^{- 2m  (\lambda- Z)^2_+}> v} dv
&= e^{-2m \lambda^2} +  \int_{e^{-2m \lambda^2}}^1\P\paren{(\lambda- Z)_+< \sqrt{\log(1/v)/(2m)}} dv \notag\\
&= e^{-2m \lambda^2} +  \int_{e^{-2m \lambda^2}}^1 \P\paren{\lambda- Z< \sqrt{\log(1/v)/(2m)}} dv \notag \\
&= e^{-2m \lambda^2} +  \int_{e^{-2m \lambda^2}}^1 \P\paren{Z> \paren[1]{\lambda-\sqrt{\log(1/v)/(2m)}}} dv. \label{eq:intermed}
\end{align}

To upper bound the integrand above, denote $\wh{H}_n$ the ecdf of $(U_1,\ldots,U_n)$; it holds for any $x \in [0,1]$:

\begin{align*}
\P\paren{Z>x}
& = \P\paren[3]{\sup_{t\in [0,1]}\left(U_{(\lfloor (n+1)t\rfloor)}-\lfloor (n+1)t\rfloor/(n+1) \right)> x}\\
&=\P\left(\exists k\in \range{n}\::\: U_{(k)} > x+k/(n+1)\right)\\
&=\P\paren[3]{\exists k\in \range{n}\::\: \sum_{i=1}^{n}\ind{U_i\leq x+k/(n+1)} \leq k-1}\\
&=\P\left(\exists k\in \range{n}\::\:  \wh{H}_n\paren[1]{x+k/(n+1)} -  [x+k/(n+1)] \leq (k-1)/n -  [x+k/(n+1)] \right).\\
&\leq P\left(\exists k\in \range{n}\::\:  \wh{H}_n\paren[1]{x+k/(n+1)} -  [x+k/(n+1)] \leq -  x \right)\\
& \leq e^{-2n x^2 },
\end{align*}

where we used $(k-1)/n\leq k/(n+1)$ in the first inequality,
and the left-tail DKW inequality for the last one. Plugging this into (<ref>) yields

\begin{align*}
\int_0^{1} \P(e^{- 2m  (\lambda- Z)^2_+}> v) dv
&\leq e^{-2m \lambda^2} +  \int_{e^{-2m \lambda^2}}^1 e^{-2 n (\lambda-\sqrt{\log(1/v)/(2m)})^2}dv.
\end{align*}

Now letting $u=\sqrt{\log(1/v)/(2m)}$ (hence $v=e^{-2m u^2}$, $dv=-4mu e^{-2m u^2}du$), we obtain

\begin{align*}
\P\paren[3]{\sup_{t\in [0,1]}\paren[1]{\wh{F}_m(t) - I_n(t)} > \lambda}&\leq e^{-2m \lambda^2} +4 m \int_0^\lambda ue^{-2 n (\lambda-u)^2} e^{-2m u^2}du.
\end{align*}

by denoting $\sigma^2=\paren[1]{4(n+m)}^{-1}$ and $\mu=n(n+m)^{-1}$, we get

\begin{align*}
e^{\frac{2nm}{n+m}\lambda^2} \int_0^\lambda ue^{-2 n (\lambda-u)^2} e^{-2m u^2}du
&= \int_0^\lambda ue^{-2(n+m)\left(u-\frac{n\lambda}{n+m}\right)^2 du}\\
&=\int_0^\lambda ue^{-\frac{1}{2\sigma^2}\left (u-\lambda\mu\right )^2}du\\
&=\int_0^\lambda (u-\lambda\mu)e^{-\frac{1}{2\sigma^2}\left (u-\lambda\mu\right )^2}du+\int_0^\lambda \lambda\mu e^{-\frac{1}{2\sigma^2}\left (u-\lambda\mu\right )^2}du\\
&= \sigma^2e^{-2\lambda^2\frac{n^2}{m+n}}-\sigma^2e^{-2\lambda^2\frac{m^2}{m+n}}+\lambda\mu
\sqrt{2\pi} \sigma C_{\lambda,n,m}.
\end{align*}

where $C_{\lambda,n,m}=\P\paren[1]{\mathcal{N}(\lambda \mu,\sigma^2)\in [0,\lambda]}$.

\begin{align*}
\int_0^\lambda ue^{-2 n (\lambda-u)^2} e^{-2m u^2}du
\sqrt{2\pi} \sigma C_{\lambda,n,m}\right)\\
&=\sigma^2e^{-2n\lambda^2}-\sigma^2 e^{-2m\lambda^2}+\lambda\mu
\sqrt{2\pi} \sigma C_{\lambda,n,m} e^{-\frac{2nm}{n+m}\lambda^2}.
\end{align*}

This leads to

\begin{align*}
&e^{-2m \lambda^2}+4 m \int_0^\lambda ue^{-2 n (\lambda-u)^2} e^{-2m u^2}du\\
&=\frac{n}{n+m} e^{-2m \lambda^2} + \frac{m}{n+m}e^{-2n\lambda^2} + \lambda\sqrt{2\pi} \frac{nm}{(n+m)^{3/2}} 2C_{\lambda,n,m}e^{-\frac{2nm}{n+m}\lambda^2},
\end{align*}

which finishes the proof of (<ref>).

Finally, let us prove $B^{\mbox{\tiny DKW}}(\lambda^{\mbox{\tiny DKW}}_{\delta,n,m},n,m)\leq \delta$ for $\lambda^{\mbox{\tiny DKW}}_{\delta,n,m}=\Psi^{(r)}(1)$ where $\Psi^{(r)}$ denotes the function $\Psi$ iterated $r$ times (for an arbitrary integer $r\geq 1$), where

\Psi(x)=1\wedge \wt{\Psi}(x); \;\;\; \wt{\Psi}(x) := \paren{ \frac{\log(1/\delta)+\log\big(1+ \sqrt{2\pi}  \frac{2\tau_{n,m}x}{(n+m)^{1/2}}\big)}{2\tau_{n,m}} }^{1/2}.

If $\Psi(1) = 1$, then $\Psi^{(r)}(1) = 1$ for all $r$ and the announced claim holds since
$B^{\mbox{\tiny DKW}}(1,n,m)=0$ by definition. We therefore assume $\Psi(1) <1$ from now on.
Since $\Psi$ is non-decreasing, by an immediate recursion we have $\Psi^{(r+1)}(1) \leq \Psi^{(r)}(1) <1 $,
for all integers $r$.

On the other hand, note that for any $x\in(0,1)$ satisfying $\Psi(x) \leq x <1$, it holds $\Psi(x) = \wt{\Psi}(x)$ and thus

\[
B^{\mbox{\tiny DKW}}(\Psi(x),n,m) = \brac{1+\frac{2\sqrt{2\pi}\Psi(x) \tau_{n,m}}{(n+m)^{1/2}}}
\brac{1+\frac{2\sqrt{2\pi}x \tau_{n,m}}{(n+m)^{1/2}}}^{-1} \delta \leq \delta.
\]

Since we established that $x=\Psi^{(r)}(1)$ satisfies $\Psi(x) \leq x$ for any integer $r$ the claim follows.

§ EXPLICIT CONTROL OF (<REF>) FOR $\ALPHA=0$

By applying (<ref>) with $k=0$, the control (<ref>) for $\alpha=0$ is satisfied by choosing

t_{0,\delta}=\max\set{k/(n+1)\::\:  \frac{(n-k+1)\dots (n-k + m)}{(n+1)\dots (n+m) } \geq 1-\delta, k\in \range{n+1}}.

§ PROOF OF COROLLARY <REF>

Let $m_0=|\cH_0|$. We establish the following more general result.

Let $\bar m_0$ achieving $\min_{r\in \range{m_0,m}} \Big(r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r}\Big)$.
With probability at least $1-\delta$, we have both

\begin{align}
& \forall t\in (0,1),\:\:\FDP(\mathcal{R}(t))\leq
\frac{\min_{r \in \range{\bar m_0,m}}\Big(  r I_n(t)+  r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r}\Big)}{1\vee |\mathcal{R}(t)|} \label{ThresholdFDPboundDKW2};\\
& \ol{m}_0\leq \max\set{r\in \range{m}\::\:\inf_t \paren{\frac{\sum_{i=1}^m\ind{p_i> t} + r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r} }{1-I_{n}(t)}}\geq r}\label{ThresholdFDPboundDKW3}.
\end{align}

Lemma <ref> implies Corollary <ref> because if $\hat{m}_0$ is as in (<ref>), with probability at least $1-\delta$, $\hat{m}_0\geq \ol{m}_0$ by (<ref>), and by (<ref>)

\forall t\in (0,1),\:\:\FDP(\mathcal{R}(t))\leq  \frac{\min_{r \in \range{\bar m_0,m}}\Big(  r I_n(t)+  r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r}\Big)}{1\vee |\mathcal{R}(t)|}\leq    \frac{\hat{m}_0 I_n(t)+  \hat{m}_0 \lambda^{\mbox{\tiny DKW}}_{\delta,n,\hat{m}_0}}{1\vee |\mathcal{R}(t)|}.

Now, let us prove Lemma <ref>.

First, in the work of [14], it is proved that $(S_{1}, \ldots, S_{n}, S_{n+i},i\in \cH_0)$ is exchangeable conditionally on $(S_{n+i},i\in \cH_1)$ (see Lemma 3.2 therein).
Hence, the vector $(S_{1}, \ldots, S_{n}, S_{n+i},i\in \cH_0)$, of size $n+m_0$, and the $p$-value vector $(p_i,i\in \cH_0)$, of size $m_0$, fall into the setting described in Section <ref> with calibration scores being $(S_{i})_{i\in \range{n}}$ and test scores being $(S_{n+i})_{i\in \cH_0}$. By Proposition <ref>, this means $(p_i,i\in \cH_0)\sim P_{n,m_0}$.

Second, for $\bar m_0$ defined as in the statement, let $\wh{F}_{\bar m_0}( t)=(\bar{m}_0)^{-1}\sum_{i=1}^{\bar m_0} \ind{q_i\leq t},$ $t\in [0,1]$, with $(q_1,\dots,q_{\bar m_0})\sim P_{n,\bar m_0}$ and $(q_i, i\in \range{m_0})=(p_i,i\in \cH_0)$ (this construction is possible because the restriction of $P_{n,\bar m_0}$ to the $m_0$ first coordinates is the distribution $P_{n, m_0}$ thanks to Theorem <ref> (i)) and
consider the event

\begin{equation}\label{eqOmega}
\Omega=\set{\sup_{t\in [0,1]}(\wh{F}_{\bar m_0}(t) - I_{n}(t)) \leq \lambda^{\mbox{\tiny DKW}}_{\delta,n,\bar m_0}}.
\end{equation}

By applying Theorem <ref> and the explicit bound (<ref>), we have  $\P(\Omega)\geq 1-\delta$.
Next, $|\mathcal{R}(t)\cap \cH_0|=m_0\wh{F}_{m_0}(t)\leq \bar m_0\wh{F}_{\bar m_0}(t) $, which is at most $\bar m_0 I_{n}(t) + \bar m_0 \lambda^{\mbox{\tiny DKW}}_{\delta,n,\bar m_0}$ on $\Omega$. This gives  (<ref>)

\frac{\bar  m_0 I_n(t)+  \bar  m_0 \lambda^{\mbox{\tiny DKW}}_{\delta,n,\bar  m_0}}{1\vee |\mathcal{R}(t)|} =
\frac{\bar  m_0 I_n(t)+  \min_{r \in \range{\bar m_0,m}}\Big(    r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r}\Big)}{1\vee |\mathcal{R}(t)|} = \frac{\min_{r \in \range{\bar m_0,m}}\Big(  r I_n(t)+  r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r}\Big)}{1\vee |\mathcal{R}(t)|} .

Let us now turn to prove (<ref>) on $\Omega$.
For this, let us observe that on this event, we have for all $t\in(0,1)$,

\begin{align*}
\sum_{i=1}^m\ind{p_i> t}\geq \sum_{i=1}^{\bar m_0}\ind{q_i> t} &= \bar m_0(1-\wh{F}_{\bar m_0}(t)) \\
&\geq \bar  m_0(1-I_{n}(t)) - \bar m_0  \lambda^{\mbox{\tiny DKW}}_{\delta,n,\bar m_0} \\
\end{align*}

Hence, $\bar m_0$ is an integer $r\in \range{m}$ such that $\inf_t \Big(\frac{\sum_{i=1}^m\ind{p_i> t} + r \lambda^{\mbox{\tiny DKW}}_{\delta,n,r} }{1-I_{n}(t)}\Big)\geq r$, which gives (<ref>).

§ THE SIMES INEQUALITY

As proved in [14], and since the joint distribution of the conformal $p$-values does not change from one context to another (Proposition <ref>), the conformal $p$-values are positively regressively dependent on each one of a subset (PRDS)  under (<ref>) and (<ref>), see [5] for a formal definition of the latter.

Same as Figure <ref> with in addition Simes bound ${\overline{\FDP}}^{\mbox{\tiny Simes}}_{t,\delta}$  (<ref>) (transparent dashed, $\delta=0.2$).

Hence, by [5], the Simes inequality [22] is valid, that is, for all $\lambda>0$, we have

\begin{align}\label{Simes}
\P\paren{\sup_{t\in (0,1]}(\wh{F}_m(t)/t) \geq \lambda}&\leq 1/\lambda.
\end{align}

This envelope can be applied in the two applications of the paper as follows:

(PI) Under the condition of Corollary <ref>, the bound

\begin{align}
{\overline{\FCP}}^{\mbox{\tiny Simes}}_{\alpha,\delta}&=  (\alpha/\delta) \ind{\alpha\geq 1/(n+1)}\label{boundfalsepositiveSimes}
\end{align}

is valid for (<ref>).

(ND) Under the condition of Corollary <ref> the following control is valid

\begin{equation}\label{AdaFDPboundSimesa}
\P\Big( \forall t\in (0,1),\FDP(\mathcal{R}(t))\leq {\overline{\FDP}}^{\tiny \mbox{Simes}}_{t,\delta}\Big)\geq 1-\delta,
\end{equation}

\begin{align}
\ol{\FDP}^{\mbox{\tiny Simes}}_{t,\delta} :=\frac{\hat{m}_0 t/\delta}{1\vee |\mathcal{R}(t)|}  ,\label{AdaFDPboundSimesb}
\end{align}

for any estimator

\begin{align}
\hat{m}_0\geq m\wedge \inf_{t\in (0,\delta)} \frac{\sum_{i=1}^m \ind{p_i>t}}{1-t/\delta}.
\label{m0chapSimes}
\end{align}

§ UNIFORM FDP BOUND FOR ADADETECT

AdaDetect [14] is obtained by applying the Benjamini-Hochberg (BH) procedure [4] to the conformal $p$-values, that is, $\AdaDetect_\alpha:=\mathcal{R}(\alpha\hat{k}_\alpha/m)$, where

\begin{equation}\label{equkchapeau}
\hat{k}_\alpha := \max\set{k\in \range{0,m}\::\: \sum_{i=1}^m \ind{p_i\leq \alpha k/m}\geq k}.
\end{equation}

It is proved there to control the false discovery rate (FDR), defined as the mean of the FDP:

\begin{equation}\label{fdrcontrol}
\FDR(\AdaDetect_\alpha):=\E[\FDP(\AdaDetect_\alpha)] \leq  \alpha m_0/m.
\end{equation}

Applying Corollary <ref>, we obtain on the top of the in-expectation guarantee (<ref>) the following uniform FDP bound for $\AdaDetect_\alpha$: with probability at least $1-\delta$, we have

\begin{align}
&\forall \alpha\in (0,1),\:\:\FDP(\AdaDetect_\alpha)\leq \ol{\FDP}^{\mbox{\tiny DKW}}_{\alpha,\delta}\nonumber\\
&\ol{\FDP}^{\mbox{\tiny DKW}}_{\alpha,\delta} :=\paren{ \alpha\frac{\hat{m}_0}{m} + \frac{\hat{m}_0 \lambda^{\mbox{\tiny DKW}}_{\delta,n,\hat{m}_0}}{\hat{k}_\alpha\vee 1}}\ind{\hat{k}_\alpha>0},\label{AdaFDPboundDKW}
\end{align}

where $\hat{k}_\alpha$ is the rejection number (<ref>) of $\AdaDetect_\alpha$ and $\hat{m}_0$ satisfies (<ref>).

In addition, we consider

\begin{align}
\ol{\FDP}^{\mbox{\tiny Simes}}_{\alpha,\delta} :=\frac{\hat{m}_0 \alpha}{m\delta }  \ind{\hat{k}_\alpha>0},\label{AdaFDPboundSimesb2}
\end{align}

for any estimator $\hat{m}_0$ given by (<ref>).

§ ADDITIONAL EXPERIMENTS

In this section, we provide experiments to illustrate the FDP confidence bounds for AdaDetect, as mentioned in Remark <ref> and Section <ref>.

The two procedures used are of the AdaDetect type (<ref>) but with two different score functions: the Random Forest classifier from [14] (adaptive score), and the one class classifier Isolation Forest as in 3 (non adaptive score).
The hyperparameters of these two machine learning algorithms are those given by [13].

The FDP and the corresponding bounds are computed for the two procedures. The true discovery proportion is defined by

\begin{equation}\label{eq:TDP}
\TDP({R})=\frac{|R\cap \cH_1|}{|\cH_1|\vee 1},
\end{equation}

where $\cH_1= \range{m} \setminus \cH_0$;
this criterion will be considered in addition to the FDP to evaluate the detection power of the procedures.

Following the numerical experiments of [14] and [3], we consider the three different real data from OpenML dataset [23] given in Table <ref>.

Summary of datasets.

Shuttle     Credit card      Mammography

Dimension $d$     9     30      6

Feature type     Real     Real      Real
$|\mathcal{D}_{{\tiny \mbox{train}}}|$     3000     2000      2000

$n$ calibration sample size     2000      1000     1000

$m_0$ (test) inlier number     1500     500     500

$m_1$ (test) novelty number     300     260    260

$m=m_0 +m_1$ total test sample size     1800     760     760

The results are displayed in Figure <ref> for comparison of adaptive versus non-adaptive scores for the different FDP confidence bounds
and the TDP. On Figure <ref>, we focus on the adaptive scores and corresponding FDP bounds only; we compare the effect (on the bounds)
of demanding a more conservative error guarantee ($\delta=0.05$ versus $\delta=0.2$), as well as the effect of estimating
$m_0$ via (<ref>) instead of just using the inequality (<ref>) with $\hat{m}_0 = m$.

The high-level conclusions are the following:

* using adaptive scores rather that non-adaptive ones results in a performance improvement (better true discovery proportion for the same
target FDR level)

* for small target FDR level $\alpha$, the Simes upper bounds $\ol{\FDP}^{\tiny \mbox{Simes}}_{\alpha,\delta}$ are sharper than the DKW bound,
elsewhere the new DKW bound is sharper than Simes.
Furthermore, the relevant region for the Simes bound having the advantage becomes all the more tenuous as the error guarantee for the bound becomes more stringent
(smaller $\delta$). The reason is that the Simes upper bound is linear in $\delta^{-1}$, while the DKW is only (square root) logarithmic.

* estimating the estimator $\hat{m}_0$ from (<ref>) yields sharper bounds on the FDP and is therefore advantageous.

90Credit Card

Left: $\FDP(\AdaDetect_\alpha)$ (<ref>)(<ref>) (dotted) and bounds ${\overline{\FDP}}^{\mbox{\tiny DKW}}_{\alpha,\delta}$ (<ref>)  (solid)  $\ol{\FDP}^{\mbox{\tiny Simes}}_{\alpha,\delta}$ (<ref>) (dashed) ($\delta=0.2$) in function of the nominal FDR-level $\alpha$. Right: corresponding $\TDP$ (<ref>).
In AdaDetect, the score is obtained either with a one-class classification (non-adaptive, blue) or a two-class classification (adaptive, red); higher is better.

Effect of $\delta$     Effect of $\hat{m}_0$

90Credit Card

Same curves as Figure <ref> (left), but only for two-class classification (adaptive, red). Left: for comparison,
the bounds ${\overline{\FDP}}$
were also plotted for a smaller $\delta=0.05$ value (blue). Right: for comparison, bounds ${\overline{\FDP}}$ also plotted without an estimator of $m_0$
(taking $m$ instead of $\hat{m}_0$).


# Designing with Data: A Case Study

Teresa Castle-Green
Stuart Reeves
Joel E. Fischer
Boriana Koleva  Mixed Reality Laboratory
University of NottinghamNottinghamUK first name.last<EMAIL_ADDRESS>
###### Abstract.

As the Internet of Things continues to take hold in the commercial world, the
teams designing these new technologies are constantly evolving and turning
their hand to uncharted territory. This is especially key within the field of
secondary service design as businesses attempt to utilize and find value in
the sensor data being produced by connected products. This paper discusses the
ways in which a commercial design team use smart thermostat data to prototype
an advice-giving chatbot. The team collaborate to produce a chat sequence
through careful ordering of data & reasoning about customer reactions. The
paper contributes important insights into design methods being used in
practice within the under researched areas of chatbot prototyping and
secondary service design.

IoT; energy; design; data work; chatbot; work practice; prototyping.

††copyright: none

##  1\. Introduction

The hyped ‘vision’ for the Internet of Things (IoT) sees large quantities of
sensor data being made available from a plethora of ubiquitous connected
devices. This data lends itself to the production of secondary services (Lee
et al., 2014), also referred to as value-added services (Theodoridis et al.,
2013), which provide auxiliary functionality to devices and services connected
to the IoT. The practical reality of designing these services, presents some
significant challenges for design teams, as they attempt to make sense of
human, social activity from heterogeneous data sets. This paper looks at how a
commercial Digital Research and Development (R&D) team use smart thermostat
(ST) data as a design resource to prototype an advice-giving chatbot.

Previous studies in this area have looked at how smart home data can be used,
interpreted and accounted for by household members (Tolmie et al., 2016) and
also how design can support the use of smart home data to provide advice and
insights to householders (Fischer et al., 2017). These studies highlight some
of the challenges that design teams face when reusing smart home data to
design secondary services. This raises the question of how commercial design
teams are adapting to these new challenges and incorporating IoT data into
their design work.

idth=]anc/meeting.png Sidebar 1: Design meeting in progress. The team are
creating a prototype chat sequence on the whiteboard.

###  1.1. Design brief

To provide information and advice, based on smart thermostat (ST) data, to
answer the question ’how can I save money?’, in an understandable and customer
friendly way.
Sidebar 2: The design brief discussed at the start of the meeting

Transcript 1: The team are discussing the potential of an additional step in
the chat sequence to provide context to the user before introducing the boiler
on-time data
1: PM: so by saying things like, your bill will be
2: impacted by the time your heating is on
3: each month, sorts of things like this.
4: Then you’re kind of getting the customer
5: into the mindset, and then we can say
6: your boiler was on this much.

Chatbot interaction design is also an emerging area of HCI research (Følstad
and Brandtzæg, 2017) where there is a distinct lack of design methods and
frameworks that can be utilized by practitioners. There are a number of papers
that discuss elements of chatbot design (Abdul-Kader and Woods, 2015; Nica et
al., 2018; Setiaji and Wibowo, 2016), however, the main focus of these is on
the system elements of the design in terms of the natural language processing
(NLP) and knowledge retrieval techniques. There is very little discussion
about the design of the responder element (Abdul-Kader and Woods, 2015) and no
mention of prototyping methods or processes to support commercial design
teams. Insight is needed into the design work involved in prototyping chat
sequences as a practical accomplishment.

This paper unpacks an R&D team design meeting, within a large energy company,
as they approach the challenge of adding value to smart home data through a
prototype chatbot.

##  2\. The Study

The case study reported in this paper forms part of wider work looking at the
challenges of design practitioners working with the IoT. The data gathering
aspects consisted of ethnographic fieldwork. As an experienced design
practitioner, the first author of this paper was embedded as a participant
observer throughout the work. The approach to the research data consisted of 3
phases; participation, familiarization with the research data and evaluation
of the team’s approach to adding value to data.

To avoid any confusion the following terms have been used: ‘Chat’ refers to
conversational sequences being designed within the chatbot. ‘Data’ refers to
the resources the team are working with. ‘Research data’ refers to data
observed and recorded as part of the research study.

The design meeting discussed in this paper was recorded as part of a larger
corpus of data collected during a 2 week sprint. The sprint involved the team
focusing on the creation of a prototype to test the technical feasibility of
using customer and IoT data to provide advice to customers through a chatbot
system.

It is important to note that the meeting occurred 5 days into the sprint so
the team had already familiarized themselves with the systems that they were
using and the available data.

There were 3 members of the team invited to the meeting by the Project Manager
(PM), which comprised of Liz, Hugo and Neil. Liz had been working on the front
end of the chatbot, creating the wording and structure for the chat. Hugo and
Neil had been focusing on the data streams and how they could utilize them to
provide information and advice. The PM took the lead throughout the meeting,
reiterating the design brief (see sidebar 2) at the start and using the
whiteboard to record and display elements of the chat sequence as the team
worked through it.

The meeting itself focused on the designing of one chat sequence, or

1: PM: So we can’t offer them the choice
2: of looking at how long their heating
3: is on, the temperature they’ve set.
4: H: So you, you can definitely do that, but
5: the thing is, average set point and
6: average outdoor temperature are two
7: entities that are used to uh.
8: PM: you’re saying that this is a product
9: of the other two things?
10: H: yes
11: L: ((nods))
12: H: I mean, the cause is how long your
13: heating is on. I mean, the consequence
14: of the average set point and the average
15: outdoor temperature is how long your 16: heating is on.
17: N: and then you answer to the question
18: why. Why is the data. What is the data.
19: PM: ok, so we have to do it differently.
20: ((rubs out button on whiteboard)) so the
21: only thing we can offer then. Well the
22: first thing we have to offer them, is
23: information about how long their boiler
24: has been running.

’journey’, as the team referred to it. The work was purely focused on the
conversational elements of the chatbot’s user interface (UI). The technical
aspects of the chatbot infrastructure had previously been decided upon and
were not part of the design work in this meeting. The prototype was an initial
iteration designed to get feedback on the UI elements of the project. As such,
the design task was to create a chat sequence in a fairly static way. Later
iterations were planned to include the NLP & machine learning elements.

##  3\. Findings

One of the key challenges faced by the team was how to make data meaningful so
that it added value for the customer. There were 5 data streams that the team
had the potential to use to provide insight to users within the chat sequence.
The ST provided boiler on-time (BO) and thermostat set point (SP). Based on
the design brief and the initial fixed steps of the journey, it was implied
that these core data streams would be included. These were key resources from
which the team could draw inferences about activity in the home. Another data
stream that was fairly central to this design task was weather data, or more
specifically outdoor temperature (OT). This was considered important by the
team and its inclusion was discussed on a number of occasions.

The final 2 potential data streams were Customer and Energy Performance
Certificate (EPC) data. These were not included in this journey as they were
referred to as having their ’own journeys’. Relationships between journeys was
mentioned as something to be reviewed in a future project phase.

###  3.1. Assessing relevance

The team assigned a sequential order to the data in relation to the design
brief. This was not mapped out in a formal manner but can be seen throughout
the discussions, with an example of this is shown in transcript 1 where BO was
introduced as having a large impact on a customers bill (lines 1-3). The
assumption here was that if the heating is on for less time then the customer
will save money, thus making it directly relevant to the initiating question,
’how can I save money?’. In transcript 2 this sequential order is further
cemented. The PM initially (lines 1-3) asks for clarification from Hugo about
his justification for blocking a previous suggestion of giving the customer
the option to choose which data they would like to look at. Hugo responds to
this (lines 4-7) by clarifying that it is possible from a practical
perspective. He then presents a justification which highlights why BO is the
most relevant to the initiation question (lines 12-16). The PM accepts this
justification (line 19) and adopts the view that BO has to be presented first
(line 22).

This relationship mapping that the team assigned between the data and the
initiation question ultimately provided the structure for the chat sequence.
This is in contrast to how interesting the members believe the data is. There
are many occasions where data is labelled as ’interesting’ or ’more
interesting’ than another data stream. Transcript 3 shows an argument that
states while BO is interesting, SP & OT are more interesting as they can
explain BO (lines 1-3).

1:PM: So boiler on-time is interesting but the
2: reasons for the boiler being on are more
3: interesting do you think? Do you agree?
4: H: Yeah yeah yeah
5:PM: Because that’s something you can do
6: something with or not. Even knowing
7: that my boiler was on for 172 hours
8: doesn’t really help me. It just states the
9: fact.
10: H: But you have to state it anyway
11:PM:Of course, no I agree that, but knowing
12: now. The bit I wanna know, ok fine,
13: but what do I do? that’s why I’m here,
14: I wanna save money so what do I do
15: to reduce this? ((taps the BO step on
16: the whiteboard))

The terms interesting and meaningful are used to refer to data outputs that
are insightful or actionable for the customer. This is a type of relevance in
itself that links to customer goals and motivations but one that supports the
sequential order of the chat journey rather than driving it. By assessing the
relevance in these ways the members are able to map the data from the
initiation question through to actionable insights in a step by step manner.

###  3.2. Adopting the customer perspective

One of the key elements of this design task, as specified in the design brief,
was that the chat needed to be understandable and customer friendly. By
defining the question that initiates the journey the team provide a reasonable
sense of the goals and motivations of their user. Designing the prototype in
this static manner enables the team to draw on scenarios & predict reactions
related to the customers’ goals. This direct approach can be seen throughout
the meeting to further assess the relevance, meaning and value of the chat
steps in the journey.

Scenarios are used to reason about how the customer will be utilizing the
information presented to them. They can be presented by any member to support
an argument. Transcript 4 demonstrates how the PM draws on a scenario to make
his doubts about the relevance of the OT data stream accountable to the team.
He introduces a scenario by first stating his belief that weather information
is only relevant in some circumstances (lines 1-3). A usage scenario is then
delivered in the first person perspective giving an example of when the
information would be meaningless to a user (lines 6-14). The inclusion of the
initiation question (line 8) is used to highlight the customer’s goal as he
moves between the design brief and the customer perspective to frame his
argument. As a result of this discussion the team decide to drop the OT data
from this journey.

Transcript 3 shows an example of another scenario being used to demonstrate
how the data meets the assumed goals and expectations of the user (lines
12-15). In this example the scenario is intertwined with other conversational
elements. The PM switches between conversation about the data and delivering a
scenario. The scenario is made accountable to the other members by the use of
the first person perspective, allowing the PM successfully switch his assumed
role from designer to user. In this case the purpose of the scenario is not
only tied to a specific step in the chat journey but is also used to refocus
the team on the design brief and the assumed customer goal, in a more general
way, relating to the design task of the journey as a whole.

In addition to the use of scenarios the team also rely on predictions of
customer reactions. These are much shorter than the scenarios and as such, are
drawn on more regularly throughout the task. Their purpose is similar, they
are used to justify or back up a decision or argument in relation to whether
or not it adds value or meaning to the customer. These predicted reactions can
be either positive or negative. Transcript 1 shows an example of a positive
predicted reaction being presented to support an argument for

1: PM:so there are some quite specific
2: conditions under which weather
3: information is relevant to that person’s
4: visit.
5: H: mmhmm
6: PM: because if I’ve just come on and I go
7: through Liz’s welcome thing and I see
8: how to save money as an option, and I
9: click on it, and it’s August, knowing
10: what the average weather or what the
11: average temperature was in the last 30
12: days against the rest of the UK, or last
13: 30 days against the previous 30 days
14: it’s kind of meaningless isn’t it.

adding a context step before introducing the BO data (lines 4-5). The
justification for the additional step is to set the frame of mind of the
visiting customer, by making the meaning of the data presented in the
following step explicit. In contrast, transcript 5, gives an example of a
negative predicted reaction as Hugo suggests presenting the BO data in hours
over a 30 day period may cause the customer to freak out (line 10).

##  4\. Discussion

The findings demonstrate how the team collaboratively work through the task of
creating a prototype chat sequence that adds value to ST data streams. The
constraints placed on the task, through the specific design brief and decision
to keep the prototype fairly static, frame the task in a way that maintained
focus on adding value to the data. The team can be seen to create a sequential
order to the data that is used to drive the step by step elements of the
design. This approach sees the systematic linking of the data to the design
brief as they draw on their knowledge of the data streams. The method of
creating a step by step mapping of the chat sequence provides some interesting
insights into chatbot design work. The sequence mapping seen in this case was
performed before any NLP & ML elements were included, thus giving potential
for user testing to be performed on the user UI elements in a somewhat
controlled manner.

The focus on the customer within the design brief appeared to encourage the
team to reason about how the customers would be using and reacting to the
information that was being presented to them. This ties into some of the
challenges discussed by (Tolmie et al., 2016; Fischer et al., 2017). Scenarios
and predicted reactions were drawn on to justify design ideas and support
decisions. At such an early stage of the project, before any user feedback had
been received by the team, they used their knowledge about their customers and
personal experience to draw on. This technique was central to the design task
in respect to how the team were progressing and reviewing their progress in
relation to adding value to the data.

##  5\. Conclusions and future work

Design using sensor data to add value through secondary services is a complex
task. This study demonstrates how the team find sequential order in the data
to drive the structure of the design forward. Value is added through a process
of reasoning about how the users will use and react to the information
presented to them. Insights are also provided in relation to the work of
prototyping of a chatbot UI designed to facilitate future user testing
opportunities.

Future work will look at the wider corpus of data across the whole 2 week
sprint, along with additional studies of practice in this area.

This paper opens up a view into complexities involved in design with IoT data
and highlights current methods of commercial chatbot design work. More work is
needed to enable HCI to provide support to practitioners in the under

1: H: I think it would be days
2: L: because if it is for the last 30 days
3: hours is going to be pretty big
4: PM:Yeah, well, but days is kind of a weird
5: thing to compare boiler on time in, I
6: think, hours. You schedule your heating
7: in hours rather than days. I don’t know
8: I think we just need to see how that-
9: H: we can display hours but I
10: feel the customer will freak out. Because
11: sometimes you know it’s uh-
12: L: massive

researched areas of Chatbot prototyping and secondary service design.

###### Acknowledgements.

This work is supported by the Engineering and Physical Sciences Research
Council [grant number EP/K025848/1].

## References

  * (1)
  * Abdul-Kader and Woods (2015) Sameera A Abdul-Kader and JC Woods. 2015.  Survey on chatbot design techniques in speech conversation systems.  _International Journal of Advanced Computer Science and Applications_ 6, 7 (2015).
  * Fischer et al. (2017) Joel E Fischer, Andy Crabtree, James A Colley, Tom Rodden, and Enrico Costanza. 2017.  Data work: How energy advisors and clients make IoT data accountable.  _Computer Supported Cooperative Work (CSCW)_ 26, 4-6 (2017), 597–626.
  * Følstad and Brandtzæg (2017) Asbjørn Følstad and Petter Bae Brandtzæg. 2017.  Chatbots and the new world of HCI.  _interactions_ 24, 4 (2017), 38–42.
  * Lee et al. (2014) Jay Lee, Hung-An Kao, and Shanhu Yang. 2014.  Service innovation and smart analytics for industry 4.0 and big data environment.  _Procedia Cirp_ 16 (2014), 3–8.
  * Nica et al. (2018) Iulia Nica, Oliver A Tazl, and Franz Wotawa. 2018\.  Chatbot-based Tourist Recommendations Using Model-based Reasoning. In _20 th International Configuration Workshop_. 25.
  * Setiaji and Wibowo (2016) Bayu Setiaji and Ferry Wahyu Wibowo. 2016.  Chatbot using a knowledge in database. In _7th International Conference on Intelligent Systems, Modelling and Simulation_.
  * Theodoridis et al. (2013) Evangelos Theodoridis, Georgios Mylonas, and Ioannis Chatzigiannakis. 2013.  Developing an iot smart city framework. In _Information, intelligence, systems and applications (iisa), 2013 fourth international conference on_. IEEE, 1–6.
  * Tolmie et al. (2016) Peter Tolmie, Andy Crabtree, Tom Rodden, James Colley, and Ewa Luger. 2016.  ”This has to be the cats”: Personal Data Legibility in Networked Sensing Systems. In _Proceedings of the 19th ACM Conference on Computer-Supported Cooperative Work & Social Computing_. ACM, 491–502.