# Feedback Capacity Formulas of AGN Channels Driven by Nonstationary
Autoregressive Moving Average Noise

Stelios Louka, Christos Kourtellaris and Charalambos D. Charalambous
Department of Electrical and Computer Engineering
University of Cyprus, 75 Kallipoleos Avenue, P.O. Box 20537, Nicosia, 1678,
Cyprus,
<EMAIL_ADDRESS>
###### Abstract

In this paper we derive closed-form formulas of feedback capacity and
nonfeedback achievable rates, for Additive Gaussian Noise (AGN) channels
driven by nonstationary autoregressive moving average (ARMA) noise (with
unstable one poles and zeros), based on time-invariant feedback codes and
channel input distributions. From the analysis and simulations follows the
surprising observations, (i) the use of time-invariant channel input
distributions gives rise to multiple regimes of capacity that depend on the
parameters of the ARMA noise, which may or may not use feedback, (ii) the more
unstable the pole (resp. zero) of the ARMA noise the higher (resp. lower) the
feedback capacity, (iii) certain conditions, known as detectability and
stabilizability are necessary and sufficient to ensure the feedback capacity
formulas and nonfeedback achievable rates are independent of the initial state
of the ARMA noise. Another surprizing observation is that Kim’s [1]
characterization of feedback capacity which is developed for stable ARMA
noise, if applied to the unstable ARMA noise, gives a lower value of feedback
capacity compared to our feedback capacity formula.

##  I Introduction

The AGN channel is defined by

$\displaystyle Y_{t}=X_{t}+V_{t},\hskip 7.22743ptt=1,\ldots,n,\hskip
7.22743pt\frac{1}{n}{\bf
E}\Big{\\{}\sum_{t=1}^{n}(X_{t})^{2}\Big{\\}}\leq\kappa$ (I.1)

where $\kappa\in[0,\infty)$ is the total power of the transmitter,
$X^{n}=\\{X_{1},X_{2},\ldots,X_{n}\\}$, $Y^{n}=\\{Y_{1},Y_{2},\ldots,Y_{n}\\}$
and $V^{n}=\\{V_{1},\ldots,V_{n}\\}$, are the sequences of channel input,
channel output, and Gaussian noise random variables (RVs), respectively.
The feedback and nonfeedback capacity of the AGN channel, when the noise
$V^{n}$ is stable, stationary, or asymptotically stationary, can be considered
to have been explained sufficiently in information theory [2, 3]. The most
general is the Cover and Pombra formulation and coding theorems [3, Theorem
1], for the set of uniformly distributed messages $W:\Omega\rightarrow{\cal
M}^{(n)}\stackrel{{\scriptstyle\triangle}}{{=}}\left\\{1,2,\ldots,\lceil
M_{n}\rceil\right\\}$, codewords of block length $n$,
$X_{1}=e_{1}(W),\ldots,X_{n}=e_{n}(W,X^{n-1},Y^{n-1})$, decoder functions,
$y^{n}\longmapsto d_{n}(y^{n})\in{\cal M}^{(n)}$, with average error
probability

$\displaystyle{\bf P}_{error}^{(n)}=\frac{1}{\lceil
M_{n}\rceil}\sum_{w=1}^{\lceil M_{n}\rceil}{\bf P}\Big{(}d_{n}(Y^{n})\neq
W\Big{|}W=w\Big{)}.$ (I.2)

The objective of this paper is twofold.

1) To show that feedback and nonfeedback capacity formulas and achievable
rates, may behave very different, depending on the definitions of achievable
rates, in particular, whether conditions are imposed to ensure these rates are
insensitive to initial states or distributions of the channel, i.e., of
$V^{n}$.

2) To show, the surprizing result that, the consideration of an unstable noise
$V^{n}$ alters the mathematical formulas of feedback and nonfeedback capacity
formulas and achievable rates, and that noises with unstable poles give
significant gains of achievable rates, at no extra expense of power.

To keep the analysis simple, we consider the unstable and stable,
autoregressive moving average, unit memory noise, denoted by
ARMA$(a,c),a\in(-\infty,\infty),c\in(-\infty,\infty),c\neq a$, as defined
below. Versions of stable or marginally stable,
ARMA$(a,c),a\in[-1,1],c\in[-1,1]$ noise are considered since the early 1970’s,
in [4, 5, 6, 7, 8, 9, 1], where the reader may find bounds on achievable rates
of feedback and nonfeedback codes, under various assumptions and formulations.

$\displaystyle\mbox{ARMA$(a,c)$:}\hskip
7.22743ptV_{t}=cV_{t-1}+W_{t}-aW_{t-1},\hskip 7.22743ptt=1,\ldots,n,$ (I.3)
$\displaystyle W_{t}\in N(0,K_{W}),\>K_{W}>0,\>t=1,\ldots,n,\>\mbox{ mutually
indep},$ (I.4) $\displaystyle\\{W_{1},\ldots,W_{n}\\}\;\mbox{indep. of initial
state $S\stackrel{{\scriptstyle\triangle}}{{=}}(V_{0},W_{0})$},$ (I.5)
$\displaystyle V_{0}\in N(0,K_{V_{0}}),\hskip 7.22743ptW_{0}\in
N(0,K_{V_{0}}),\hskip 7.22743ptK_{V_{0}}\geq 0,\hskip 7.22743ptK_{W_{0}}\geq
0,$ (I.6) $\displaystyle a\in(-\infty,\infty),\hskip
7.22743ptc\in(-\infty,\infty),\hskip 7.22743ptc\neq a,$ (I.7)

where the notation, $Z\in N(0,K_{Z})$ means $Z$ is a Gaussian RV, with zero
mean, and variance $K_{Z}$. The $ARMA(a,c)$ noise is equivalently expressed in
state form, with state $S_{t}$ as,

$\displaystyle
S_{t}\stackrel{{\scriptstyle\triangle}}{{=}}\frac{cV_{t-1}-aW_{t-1}}{c-a},\hskip
7.22743ptt=1,\dots,n,$ (I.8) $\displaystyle S_{t+1}=cS_{t}+W_{t},\hskip
7.22743ptS_{1}=s,\hskip 7.22743ptt=1,\dots,n,$ (I.9) $\displaystyle
V_{t}=(c-a)S_{t}+W_{t},\hskip 7.22743ptt=1,\dots,n$ (I.10)

From the $ARMA(a,c)$ noise, follow the two special cases,

$\displaystyle\mbox{Autoregressive: }AR(c)\big{|}_{a=0}:\hskip
7.22743ptV_{t}=cV_{t-1}+W_{t}$ (I.11) $\displaystyle\mbox{Moving Average:
}MA(a)\big{|}_{c=0}:\hskip 7.22743ptV_{t}=W_{t}-aW_{t-1}$ (I.12)

###  I-A Literature Review

Due to the relevance to our investigation, of prior formulas found in [4, 5,
6, 7, 3, 8, 9, 1], we briefly discuss some of these below, with emphasis on
the formulations and assumptions.

3) Formulation and Bounds with Initial State [5, 6, 7]. Wolfowitz [6] and
Butman [7], derived a lower bound on feedback capacity of the AGN channel,
driven by the noise, AR$(c),c\in[-1,1]$, using the linear feedback coding
scheme, $X_{t}=g_{t}\Big{(}\Theta-{\bf
E}\big{\\{}\Theta\Big{|}Y^{t-1},v_{0}\big{\\}}\Big{)},t=2,\ldots,n,X_{1}=g_{1}\Theta$,
where $g_{t}$ are nonrandom real numbers, and
$\Theta:\Omega\rightarrow{\mathbb{R}}$ is Gaussian, $\Theta\in N(0,1)$, i.e.,
under the assumption the initial state $V_{0}=v_{0}$ is known to the encoder
and decoder. The lower bound is

$\displaystyle C^{LB}=\frac{1}{2}\log\chi^{2},\hskip 7.22743pt\mbox{where
$\chi$ is the positive root of}$ (I.13)
$\displaystyle\chi^{4}-\chi^{2}-\frac{\kappa}{K_{W}}\Big{(}\chi+|c|\Big{)}^{2}=0,\;|c|\leq
1,\;K_{W}>0.$ (I.14)

Butman [7] conjectured that $C^{LB}$ is the feedback capacity.
[7] includes a comparison to the Tienan and Schalkwijk upper bound [5], also
derived under the same assumptions.

Figure I.1: Comparison of $C_{FB}=C^{YKT}=C^{LB}$, i.e., Butman’s (I.13),
Kim’s feedback capacity [1, Theorem 6.1, $C_{FB}$], and our feedback capacity
and achievable nonfeedback rate for unstable and stable AR$(c)$ noise

4) Formulation, Characterizations and Closed-Form Formulas with and without
Initial State [3, 9, 1].
4.1) Cover and Pombra [3] characterized the feedback (and nonfeedback)
capacity of the AGN channel, driven by a nonstationary Gaussian noise $V^{n}$,
[3, Theorem 1], for codes that do not assume knowledge of the initial state of
the noise. The feedback capacity is
$C\stackrel{{\scriptstyle\triangle}}{{=}}\lim_{n\longrightarrow\infty}\frac{1}{n}C_{n}$
(provided the limit exists), where $C_{n}$ is the $n$-finite block length or
transmission feedback information ($n-$FTFI) capacity,

$\displaystyle
C_{n}\stackrel{{\scriptstyle\triangle}}{{=}}\sup_{\frac{1}{n}{\bf
E}\big{\\{}\sum_{t=1}^{n}(X_{t})^{2}\big{\\}}\leq\kappa}H(Y^{n})-H(V^{n})$
(I.15) $\displaystyle
X_{n}=\sum_{j=1}^{n-1}\Gamma_{n,j}V_{j}+\overline{Z}_{n},\hskip
7.22743ptn=1,2,\ldots,\hskip 7.22743ptX_{1}=\overline{Z}_{1},$ (I.16)

and the supremum is over nonrandom $\Gamma_{n,j},j=1,\ldots,n-1$ and jointly
correlated, Gaussian RVs $\\{\overline{Z}_{1},\ldots,\overline{Z}_{n}\\}$,
independent of $V^{n}$; $H(X)$ is the differential entropy of RV $X$.

4.2) Yang, Kavcic and Tatikonda [9] analyzed the feedback capacity of the AGN
channel driven a noise $V^{n}$, with state $S^{n}$, under the following
assumption.

Assumption (YKT) [9, page 933, I)-III)]: given the initial state of the noise
$S_{1}=s$, which is known to the encoder and the decoder, the channel input
$X^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\\{X_{1},\ldots,X_{n}\\}$
uniquely defines the state variables $S^{n}$ and vice-versa.

[9, Theorem 7], computed the feedback rate of the AGN channel driven by
ARMA$(a,c),a\in(-1,1),c\in(-1,1)$ noise, using the definition,

$\displaystyle
C^{YKT}\stackrel{{\scriptstyle\triangle}}{{=}}\sup_{(\Lambda,K_{Z}):\lim_{n\longrightarrow\infty}\frac{1}{n}{\bf
E}\big{\\{}\sum_{t=1}^{n}\big{(}X_{t}\big{)}^{2}\big{|}S_{1}=s\big{\\}}\leq\kappa}\lim_{n\longrightarrow\infty}\Big{\\{}$
$\displaystyle\hskip
56.9055pt\frac{1}{n}\sum_{t=1}^{n}H(Y_{t}|Y^{t-1},s)-H(V^{n}|s)\Big{\\}},$
(I.17) $\displaystyle X_{n}=\Lambda\Big{(}S_{n}-{\bf
E}\Big{\\{}S_{n}\Big{|}Y^{n-1},S_{1}=s\Big{\\}}\Big{)}+Z_{n},\;n=2,\ldots,$
(I.18) $\displaystyle X_{1}=Z_{1},\hskip 7.22743ptZ_{n}\in
N(0,K_{Z}),\;K_{Z}\geq 0,\hskip 7.22743ptn=1,2,\ldots$ (I.19)

where the RVs, $\\{Z_{1},Z_{2},\ldots,Z_{n}\\}$ are mutually independent. The
limiting problem in the steady state, is solved, and a formula of $C^{YKT}$ is
obtained. For the AR$(c),c\in(-1,1)$ noise,
$C^{YKT}=\frac{1}{2}\log|\Lambda^{*}|^{2}$, where $\Lambda^{*}$ satisfies
Butman’s equation (I.14), i.e., $C^{YKT}=C^{LB}$ of Butman (see [9, Corollary
7.1]).

######  Remark I.1.

In both [9, Theorem 7, Corollary 7.1], $C^{YKT}$, are achieved by
$\Lambda=\Lambda^{*}$ and $K_{Z}=K_{Z}^{*}=0$.

4.3) Kim [1] re-visited the AGN channel driven by a stable noise, and derived
characterizations of feedback capacity, in frequency domain [1, Theorem 4.1],
with zero power spectral density of the innovations part of the channel input
$X_{n},n=1,2,\ldots$, and in time-domain [1, Theorem 6.1], with zero variance
of the innovations part, $Z_{n}$ of the input $X_{n},n=1,2,\ldots$, (I.18),
(I.19). Kim [1, page 78, first paragraph], stated that [1, Theorem 6.1,
$C_{FB}$]) characterizes the feedback capacity (i.e., $C_{FB}$) as conjectured
in [9, Theorem 6 and Conjecture 1], in a simpler form (without the innovations
process of the input).
In [1, Page 76], the AGN channel with ARMA$(a,c),a\in(=[-1,1],c\in[-1,1]$
noise is considered, with initial state $(V_{0}=0,W_{0}=0)$, and the feedback
capacity $C_{FB}$ is computed based on the limiting expression (I.17), with
input $X_{n}$, replaced by

$\displaystyle X_{1}=Z_{1},\hskip 14.45377pt\mbox{$Z_{n}$ is zero mean,
variance $K_{Z}>0$}$ (I.20) $\displaystyle X_{n}=\Lambda\Big{(}S_{n}-{\bf
E}\Big{\\{}S_{n}\Big{|}Y^{n-1}\Big{\\}}\Big{)},\hskip 14.45377ptn=2,\ldots$
(I.21)

For the AR$(c),c\in(-1,1)$ noise, the optimal $\Lambda=\Lambda^{*}$ satisfies
Butman’s equation (I.14), and $C_{FB}=\frac{1}{2}\log|\Lambda^{*}|^{2}$, i.e.,
identical to Butman’s lower bound.

###  I-B Main Problem of the Paper: Brief Discussion of Results and
Comparisons

As we briefly demonstrate via simulations of our feedback capacity
expressions, which we derived in Section II, that even for stable
ARMA$(a,c),a\in(-1,1),c\in(-1,1)$ noise, we arrive at completely different
formulas, compared to those in [9, 1]. We show these differences are
attributed to our feedback capacity problem definition, stated as Problem I.1.
In particular, the limiting expression of feedback rate, (I.22), is
independent of the initial state of the noise, i.e.,
$C^{\infty}(\kappa,s)=C^{\infty}(\kappa),\forall s$, when compared to (I.17).

######  Problem I.1.

Consider the AGN channel driven by the $ARMA(a,c)$ noise, with
$c\in(-\infty,\infty)$, $a\in(-\infty,\infty)$, and with initial state
$S_{1}=s$, known to the encoder and the decoder. Define the feedback rate

$\displaystyle C^{\infty}(\kappa,s)\stackrel{{\scriptstyle\triangle}}{{=}}$
$\displaystyle\sup_{\lim_{n\longrightarrow\infty}\frac{1}{n}{\bf
E}\big{\\{}\sum_{t=1}^{n}\big{(}X_{t}\big{)}^{2}\big{|}s\big{\\}}\leq\kappa}\lim_{n\longrightarrow\infty}\Big{\\{}\frac{1}{n}\sum_{t=1}^{n}H(Y_{t}|Y^{t-1},s)$
$\displaystyle-H(V^{n}|s)\Big{\\}}$ (I.22)

where the supremum is taken over all jointly Gaussian channel input process
$X_{n},n=1,2,\ldots$, generated by time-invariant feedback strategies, and
induce distributions ${\bf P}_{X_{t}|X^{t-1},Y^{t-1},S_{1}},t=1,2,\ldots$,
such that the joint process $(X_{n},Y_{n}),n=1,2,\ldots,$ is jointly Gaussian,
for $S_{1}=s$.
We address the following questions.
(a) What are necessary and/or sufficient conditions for,
(i) asymptotic stationarity of the process $(X^{n},Y^{n}),n=1,2,\ldots$ or the
marginal process $X^{n}$, that achieve $C^{\infty}(\kappa,s)$, and
(ii) $C^{\infty}(\kappa,s)=C^{\infty}(\kappa)\;\forall s$, i.e., independent
of initial data?
(b) What are the closed form formulas of feedback capacity
$C^{\infty}(\kappa,s)=C^{\infty}(\kappa)\;\forall s$?

Problem I.1.(a).(i),(ii), captures the requirement that $C^{\infty}(\kappa,s)$
is well-defined, for unstable
$ARMA(a,c),c\in(-\infty,\infty),a\in(-\infty,\infty)$ noise (as well as
stable, $c\in(-1,1),a\in(-1,1)$), and
$C^{\infty}(\kappa,s)=C^{\infty}(\kappa),\forall s$.
In the rest of the paper, we show there are multiple regimes of
$C^{\infty}(\kappa)$, which depend on the parameters $(a,c,\kappa)$. At some
regimes, feedback does not increase the capacity. This is attributed to the
use of time-invariant channel input strategies. For these regimes we derive
achievable nonfeedback rates $C^{\infty,nfb}_{LB}(\kappa)$, based on a simple
IID channel input $X_{n}=Z_{n},Z_{n}\in N(0,\kappa),n=1,2,\ldots$.
Fig. I.1, compares our feedback capacity and achievable nonfeedback rate to
Butman’s lower bound and Kim’s feedback capacity [1, Theorem 6.1, $C_{FB}$],
for the AR$(c)$, stable and unstable noise. For unstable noise, even an IID
channel input outperforms the feedback rate $C_{FB}=C^{YKT}=C^{LB}$.
The verification of our objectives described in Section I, under 1) and 2),
are demonstrated in Figures I.2, I.3.

Figure I.2: Feedback capacity $C^{\infty}(\kappa)$ for $\kappa\in{\cal
K}^{\infty}(a,c,K_{W})$ based on (II.49) and lower bound on nofeedback
capacity $C_{LB}^{\infty,nfb}(\kappa)$ for $\kappa\in(0,\infty)$ based on
(II.54), of the AGN channel driven by stable/unstable ARMA$(a,c)$ noise, for
various values of $a=0.2$, $c\in(-\infty,\infty)$ and $K_{W}=1$. Figure I.3:
Lower bound achievable rate for no-feedback $C_{LB}^{\infty,nfb}(\kappa)$ for
$\kappa\in(0,\infty)$ based on (II.54), of the AGN channel driven by stable
ARMA$(a,c)$ noise, for various values of $|a|\leq 1$, $c=0.5$ and $K_{W}=1$.

Figure I.2, shows that feedback capacity $C^{\infty}(\kappa)$ over the
appropriate region, is an increasing function of the parameter $c$, i.e., the
higher unstable pole, the higher the value of $C^{\infty}(\kappa)$. On the
other hand, the higher the value of $a$, i.e., of the zero, the lower the
value $C^{\infty}(\kappa)$.
Figure I.3 shows that the lower bound on nofeedback capacity
$C^{\infty,nfb}_{LB}(\kappa)$ is achievable for all $\kappa\in(0,\infty)$, for
stable and unstable $ARMA(a,c)$ noise, and it is very closed to the feedback
capacity $C^{\infty}(\kappa)$.

##  II Characterization of Feedback Capacity

We consider a the set of uniformly distributed messages
$W:\Omega\rightarrow{\cal
M}^{(n)}\stackrel{{\scriptstyle\triangle}}{{=}}\left\\{1,2,\ldots,\lceil
M_{n}\rceil\right\\}$, codewords
$X_{1}=e_{1}(W,S_{1}),\ldots,X_{n}=e_{n}(W,S_{1},X^{n-1},Y^{n-1})$, decoder
functions $(s,y^{n})\longmapsto d_{n}(s,y^{n})\in{\cal M}^{(n)}$, and average
error probability (I.2), which is also conditioned on $S_{1}=s$.

###  II-A $n-$FTFI Capacity of Time-Invariant Channel Input Strategies

Since our code depends on the initial state of ARMA$(a,c)$ noise, $S_{1}=s$,
then the entropies in (I.15), (I.16), are conditional on $S_{1}=s$, and
$C_{n}^{fb}$ is denoted by $C_{n}(\kappa,s)$, and $X_{n}$ depends on
$S_{1}=s$. Theorem II.1 is easily derived from the Cover and Pombra
characterization (see [10]) or [9].

######  Theorem II.1.

Characterization of $n-$FTFI Capacity
Consider the AGN Channel driven by ARMA$(a,c)$ noise, and a feedback code with
knowledge of the noise initial state $S_{1}=s$, and let
$\widehat{S}_{t}\stackrel{{\scriptstyle\triangle}}{{=}}{\bf
E}\big{\\{}S_{t}|Y^{t-1},S_{1}=s\big{\\}}$,
$K_{t}\stackrel{{\scriptstyle\triangle}}{{=}}{\bf
E}\big{\\{}\big{(}S_{t}-\widehat{S}_{t}\big{)}^{2}|S_{1}=s\big{\\}},K_{1}=0,t=2,\ldots,n.$
The analog of (I.15) and (I.16) are given as follows.

$\displaystyle
X_{t}=\Lambda_{t}\Big{(}{S}_{t}-\widehat{S}_{t}\Big{)}+Z_{t},\hskip
7.22743ptt=1,\dots,n,\hskip 7.22743ptX_{1}=Z_{1},$ (II.23) $\displaystyle
Z_{t}\in N(0,K_{Z_{t}}),\;\mbox{a Gaussian sequence,}\;t=1,\ldots,n,$ (II.24)
$\displaystyle Z_{t}\hskip 7.22743pt\mbox{independent of}\hskip
7.22743pt(V^{t-1},X^{t-1},Y^{t-1},{S}_{1}),$ (II.25) $\displaystyle
V_{t}=(c-a)S_{t}+W_{t},\hskip 7.22743ptS_{1}=s,\hskip 7.22743ptt=1,\ldots,n,$
(II.26) $\displaystyle
Y_{t}=X_{t}+V_{t}={\Lambda}_{t}\Big{(}{S}_{t}-\widehat{S}_{t}\Big{)}+Z_{t}+V_{t}$
(II.27) $\displaystyle\hskip
7.22743pt={\Lambda}_{t}\Big{(}{S}_{t}-\widehat{S}_{t}\Big{)}+\Big{(}c-a\Big{)}S_{t}+W_{t}+Z_{t},$
(II.28) $\displaystyle Y_{1}=Z_{1}+\Big{(}c-a\Big{)}S_{1}+W_{1},\hskip
7.22743ptS_{1}=s,$ (II.29) $\displaystyle S_{t+1}=cS_{t}+W_{t}\hskip
7.22743ptS_{1}=s,\hskip 7.22743ptt=2,\dots,n,$ (II.30)
$\displaystyle\frac{1}{n}{\bf
E}\Big{\\{}\sum_{t=1}^{n}\big{(}X_{t}\big{)}^{2}\Big{|}S_{1}=s\Big{\\}}=\frac{1}{n}\sum_{t=1}^{n}\Big{\\{}\big{(}\Lambda_{t}\big{)}^{2}K_{t}+K_{Z_{t}}\Big{\\}},$
(II.31)
$\displaystyle(\Lambda_{t},K_{Z_{t}})\in(-\infty,\infty)\times[0,\infty)\hskip
7.22743pt\mbox{scalar, non-random,}$ (II.32)

Further, $H(Y^{n}|s)-H(V^{n}|s)$, $(\widehat{S}_{t},K_{t}),t=1,\ldots,n$ are
determined by the generalizedl time-varying Kalman-filter.
Kalman-filter recursion:

$\displaystyle\widehat{S}_{t+1}=c\widehat{S}_{t}+M_{t}(K_{t},\Lambda_{t},K_{Z_{t}})I_{t},\hskip
7.22743pt\widehat{S}_{1}=s,$ (II.33) $\displaystyle
I_{t}\stackrel{{\scriptstyle\triangle}}{{=}}Y_{t}-{\bf
E}_{s}\Big{\\{}Y_{t}\Big{|}Y^{t-1}\Big{\\}}=Y_{t}-\Big{(}c-a\Big{)}\widehat{S}_{t},$
$\displaystyle I_{1}=Z_{1}+W_{1},\hskip 7.22743ptt=1,\ldots,n,$ (II.34)
$\displaystyle\hskip
7.22743pt=\Big{(}\Lambda_{t}+c-a\Big{)}\Big{(}S_{t}-\widehat{S}_{t}\Big{)}+Z_{t}+W_{t},$
(II.35) $\displaystyle
M_{t}(K_{t},\Lambda_{t},K_{Z_{t}})\stackrel{{\scriptstyle\triangle}}{{=}}\Big{(}K_{W_{t}}+cK_{t}\Big{(}\Lambda_{t}+c-a\Big{)}\Big{)}\cdot$
$\displaystyle\hskip
14.45377pt\Big{(}K_{Z_{t}}+K_{W_{t}}+\Big{(}\Lambda_{t}+c-a\Big{)}^{2}K_{t}\Big{)}^{-1}$
(II.36)

Error recursion,
$E_{t}\stackrel{{\scriptstyle\triangle}}{{=}}S_{t}-\widehat{S}_{t}$ :

$\displaystyle
E_{t+1}=F_{t}(K_{t},{\Lambda}_{t},K_{Z_{t}})E_{t}-M_{t}(K_{t},{\Lambda}_{t},K_{Z_{t}})\Big{(}Z_{t}+W_{t}\Big{)}+W_{t},$
$\displaystyle E_{1}=S_{1}-\widehat{S_{1}}=0,\ \ t=2,\ldots,n.$ (II.37)
$\displaystyle
F_{t}(K_{t},{\Lambda}_{t},K_{Z_{t}})\stackrel{{\scriptstyle\triangle}}{{=}}c-M_{t}(K_{t},{\Lambda}_{t},K_{Z_{t}})\Big{(}{\Lambda}_{t}+c-a\Big{)}$
(II.38)

Entropy of channel output Process:

$\displaystyle H(Y^{n}|s)=\sum_{t=1}^{n}H(I_{t}),\hskip 7.22743ptI_{t}\hskip
7.22743pt\mbox{indep. innovation process.}$ (II.39)

Generalized time-varying difference Riccati equation (DRE):

$\displaystyle K_{t+1}=$ $\displaystyle
c^{2}K_{t}+K_{W}-\frac{\Big{(}K_{W}+cK_{t}\big{(}\Lambda_{t}+c-a\big{)}\Big{)}^{2}}{\Big{(}K_{Z_{t}}+K_{W}+\big{(}\Lambda_{t}+c-a\big{)}^{2}K_{t}\Big{)}},$
(II.40) $\displaystyle K_{t}\geq 0,\hskip 7.22743ptK_{1}=0,\hskip
7.22743ptt=2,\dots,n$

The characterization of the $n-$FTFI capacity $C_{n}(\kappa,s)$ is

$\displaystyle C_{n}$
$\displaystyle(\kappa,s)=\sup_{\big{(}\Lambda_{t},K_{Z_{t}}\big{)},t=1,\ldots,n:\hskip
7.22743pt\frac{1}{n}\sum_{t=1}^{n}\big{\\{}\big{(}\Lambda_{t}\big{)}^{2}K_{t}+K_{Z_{t}}\big{\\}}\leq\kappa}\Big{\\{}$
$\displaystyle\frac{1}{2}\sum_{t=1}^{n}\log\Big{(}\frac{\big{(}\Lambda_{t}+c-a\big{)}^{2}K_{t}+K_{Z_{t}}+K_{W}}{K_{W}}\Big{)}\Big{\\}}.$
(II.41)

###### Proof.

See [10]. ∎

Unlike the Cover and Pombra problem (I.15) and (I.16), problem (II.41) is
sequential, hence easier to address.

###  II-B Feedback Capacity of Time-Invariant Channel Input Strategies

To address Problem I.1, we restrict the channel input strategies to time-
invariant, $\Lambda_{t}=\Lambda^{\infty},K_{Z_{t}}=K_{Z}^{\infty},\forall t$,
with corresponding
$X_{t}=X_{t}^{o},Y_{t}=Y_{t}^{o},I_{t}=I_{t}^{o},E_{t}=E_{t}^{o},K_{t}=K_{t}^{o}\equiv
K_{t}^{o}(\Lambda^{\infty},K_{Z}^{\infty})$. Then we have the following.
Generalized time-Invariant DRE:

$\displaystyle K_{t+1}^{o}=$ $\displaystyle
c^{2}K_{t}^{o}+K_{W}-\frac{\Big{(}K_{W}+cK_{t}^{o}\big{(}\Lambda^{\infty}+c-a\big{)}\Big{)}^{2}}{\Big{(}K_{Z}^{\infty}+K_{W}+\big{(}\Lambda^{\infty}+c-a\big{)}^{2}K_{t}^{o}\Big{)}},$
$\displaystyle K^{o}_{t}\geq 0,\hskip 7.22743ptK^{o}_{1}=0,\hskip
7.22743ptt=2,\dots,n.$ (II.42)

We define feedback capacity $C^{\infty}(\kappa,s)$, as in [9, 1]),

$\displaystyle C^{\infty}(\kappa,$ $\displaystyle
s)=\sup_{\stackrel{{\scriptstyle\Lambda^{\infty}\in(-\infty,\infty),K_{Z}^{\infty}\in[0,\infty):}}{{\lim_{n\longrightarrow\infty}\frac{1}{n}\sum_{t=1}^{n}\big{\\{}\big{(}\Lambda^{\infty}\big{)}^{2}K_{t}^{o}+K_{Z}^{\infty}\big{\\}}\leq\kappa}}}\lim_{n\longrightarrow\infty}\frac{1}{2n}\bigg{\\{}$
$\displaystyle\sum_{t=1}^{n}\log\Big{(}\frac{\big{(}\Lambda^{\infty}+c-a\big{)}^{2}K_{t}^{o}+K_{Z}^{\infty}+K_{W}}{K_{W}}\Big{)}\bigg{\\}}.$
(II.43)

To address Problem I.1.(a), we require conditions for convergence of DRE
(II.42) to algebraic Riccati equation (ARE),

$\displaystyle K^{\infty}=c^{2}K^{\infty}+K_{W}$
$\displaystyle-\frac{\Big{(}K_{W}+cK\Big{(}\Lambda^{\infty}+c-a\Big{)}\Big{)}^{2}}{\Big{(}K_{Z}^{\infty}+K_{W}+\Big{(}\Lambda^{\infty}+c-a\Big{)}^{2}K^{\infty}\Big{)}},\hskip
14.45377ptK^{\infty}\geq 0.$ (II.44)

Such conditions require concepts of detectability and stabilizability of DREs
[11], as done in [10], using the definitions,

$\displaystyle
A\stackrel{{\scriptstyle\triangle}}{{=}}c,\;\;C\stackrel{{\scriptstyle\triangle}}{{=}}{\Lambda}^{\infty}+c-a,\;\;A^{*}\stackrel{{\scriptstyle\triangle}}{{=}}c-K_{W}R^{-1}C,\;\;B^{*,\frac{1}{2}}\stackrel{{\scriptstyle\triangle}}{{=}}K_{W}^{\frac{1}{2}}B^{\frac{1}{2}},$
$\displaystyle
R\stackrel{{\scriptstyle\triangle}}{{=}}K_{Z}^{\infty}+K_{W},\;\;B\stackrel{{\scriptstyle\triangle}}{{=}}1-K_{W}\big{(}K_{Z}^{\infty}+K_{W}\big{)}^{-1}.$
(II.45)

The next notions are directly related to the asymptotic stability of the error
recursion (II.37).

######  Definition II.1.

[11][12] Asymptotic stability.
A solution $K^{\infty}\geq 0$ to the generalized ARE (II.44), assuming it
exists, is called stabilizing if
$|F(K^{\infty},\Lambda^{\infty},K_{Z}^{\infty})|<1$. In this case, we say
$F(K^{\infty},\Lambda^{\infty},K_{Z}^{\infty})$ is asymptotically stable.

######  Definition II.2.

[11][12]
(a) The pair $\big{\\{}A,C\big{\\}}$ is called detectable if there exists a
$G\in{\mathbb{R}}$ such that $|A-GC|<1$ (stable).
(b) The pair $\big{\\{}A^{*},B^{*,\frac{1}{2}}\big{\\}}$ is called unit circle
controllable if there exists a $G\in{\mathbb{R}}$ such that
$|A^{*}-B^{*,\frac{1}{2}}G|\neq 1$.
(c) The pair $\big{\\{}A^{*},B^{*,\frac{1}{2}}\big{\\}}$ is called
stabilizable if there exists a $G\in{\mathbb{R}}$ such that
$|A^{*}-B^{*,\frac{1}{2}}G|<1$.

In the next theorem we collect known results on the convergence of DREs to
AREs.

######  Theorem II.2.

[11] and [13]
Let $\\{K_{t}^{o},t=1,2,\ldots,n\\}$ denote a sequence that satisfies the DRE
(II.42) with an arbitrary initial condition.
Then the following hold.
(1) Consider the DRE (II.42) with zero initial condition, i.e., $K_{1}^{o}=0$,
and assume, the pair $\big{\\{}A,C\big{\\}}$ is detectable, and the pair
$\big{\\{}A^{*},B^{*,\frac{1}{2}}\big{\\}}$ is unit circle controllable.
The sequence $\\{K_{t}^{o}:t=1,2,\ldots,n\\}$ that satisfies (II.42), with
$K_{1}^{o}=0$, converges, $\lim_{n\longrightarrow\infty}K_{n}^{o}=K^{\infty}$,
where $K^{\infty}$ satisfies the ARE (II.44), if and only if the pair
$\big{\\{}A^{*},B^{*,\frac{1}{2}}\big{\\}}$ is stabilizable.
(2) Assume, the pairs, $\big{\\{}A,C\big{\\}}$ is detectable, and
$\big{\\{}A^{*},B^{*,\frac{1}{2}}\big{\\}}$ is unit circle controllable. Then
there exists a unique stabilizing solution $K^{\infty}\geq 0$ to ARE (II.42),
i.e., such that, $|F(K^{\infty},\Lambda^{\infty},K_{Z}^{\infty})|<1$, if and
only if $\\{A^{*},B^{*,\frac{1}{2}}\\}$ is stabilizable.
(3) If $\\{A,C\\}$ is detectable and $\\{A^{*},B^{*,\frac{1}{2}}\\}$ is
stabilizable, then any solution $K_{t}^{o},t=1,2,\ldots,n$ to the DRE (II.42)
with arbitrary initial condition, $K_{1}^{o}$ is such that
$\lim_{n\longrightarrow\infty}K_{n}^{o}=K^{\infty}$, where $K^{\infty}\geq 0$
is the unique solution of the generalized ARE (II.44) with
$|F(K^{\infty},\Lambda^{\infty},K_{Z}^{\infty})|<1$, i.e., it is stabilizing.

######  Remark II.1.

At this point we should emphasize that to address Problem I.1, we need to
impose detectability and stabilizability. This is fundamentally different from
[9, Theorem 7, Corollary 7.1] and [1, Theorem 6.1 and Lemma 6.1] (as explain
under literature review), where the stabilizability condition is not part of
the optimization problems of [9, 1], i.e., (I.17)-(I.19). Because of this, our
answers are different from[9, 1].

###  II-C Closed-Form Formulas of Feedback Capacity of AGN Channels Driven by
Nonstationary Noise

Using Theorem II.2, we address Problem I.1 as stated in Theorem below.

######  Theorem II.3.

Consider the Problem I.1. Define the set

$\displaystyle{\cal P}^{\infty}\stackrel{{\scriptstyle\triangle}}{{=}}$
$\displaystyle\Big{\\{}(\Lambda^{\infty},K_{Z}^{\infty})\in(-\infty,\infty)\times[0,\infty):$
(i) the pair $\\{A,C\\}$ is detectable, $\displaystyle\mbox{(ii) the pair
$\\{A^{*},B^{*,\frac{1}{2}}\\}$}\;\mbox{is stabilizable}\Big{\\}}.$ (II.46)

Then,

$\displaystyle
C^{\infty}(\kappa)\stackrel{{\scriptstyle\triangle}}{{=}}\frac{1}{2}\log\Big{(}\frac{\big{(}\Lambda^{\infty}+c-a\big{)}^{2}K^{\infty}+K_{Z}^{\infty}+K_{W}}{K_{W}}\Big{)}$
(II.47) $\displaystyle{\cal
P}^{\infty}(\kappa)\stackrel{{\scriptstyle\triangle}}{{=}}\Big{\\{}(\Lambda^{\infty},K_{Z}^{\infty})\in{\cal
P}^{\infty}:K_{Z}^{\infty}\geq 0,\
\big{(}\Lambda^{\infty}\big{)}^{2}K^{\infty}+K_{Z}^{\infty}\leq\kappa\Big{\\}}$

provided there exists $\kappa>0$ such that ${\cal P}^{\infty}(\kappa)$ is non-
empty. The maximum element $(\Lambda^{\infty},K_{Z}^{\infty})\in{\cal
P}^{\infty}(\kappa)$, is such that,
(i) if $|c|<1$, then $(S_{t},V_{t},X_{t},Y_{t}),t=1,\ldots$ are asymptotic
stationary, and (ii) $(X_{t},I_{t}),t=1,\ldots$ are asymptotic stationary,
$\forall c\in(-\infty,\infty),a\in(-\infty,\infty)$.

###### Proof.

By Theorem II.2 the limits in (II.43) converge to a unique number and
$C^{\infty}(\kappa,s)$ is independent of $s$. ∎

Theorem II.4 is obtained by solving the optimization problem of Theorem II.3.

######  Theorem II.4.

Consider the optimization problem of Theorem II.3. Feedback increases capacity
for the following regions.
$\mbox{A)
}c\in\big{(}1,\sqrt{2}\big{)}\cup\big{(}\sqrt{2},\infty\big{)},a\in\left[\frac{-c}{c^{2}-2},\frac{1}{c}\right]\\\
\mbox{B)
}c\in\big{(}-\infty,-\sqrt{2}\big{)}\cup\big{(}-\sqrt{2},-1\big{)},a\in\big{(}-\infty,\frac{1}{c}\big{]}\cup\big{[}\frac{-c}{c^{2}-2},\infty\big{)}$
provided the power $\kappa$ satisfies
$\kappa>\kappa_{min}\stackrel{{\scriptstyle\triangle}}{{=}}\frac{K_{W}\big{(}1-ac\big{)}\big{(}2ac-
ac^{3}-c^{2}+\sqrt{c^{3}\big{(}a^{2}c^{3}-6ac^{2}+4a+4c^{3}-3c\big{)}}\big{)}}{2c^{2}\big{(}c^{2}-1\big{)}^{2}}$
and the value of feedback capacity $C^{\infty}(\kappa)$ is

$\displaystyle
C^{\infty}(\kappa)=\frac{1}{2}\log\Big{(}\frac{\big{(}\Lambda^{\infty,*}+c-a\big{)}^{2}K^{\infty,*}+K_{Z}^{\infty,*}+K_{W}}{K_{W}}\Big{)}$
(II.48) $\displaystyle\hskip
25.6073pt=\frac{1}{2}\log\Big{(}\frac{cK_{W}(c-2a+a^{2}c)+c^{2}\kappa(c^{2}-1)}{K_{W}(c^{2}-1)}\Big{)},$
(II.49) $\displaystyle K^{\infty,*}=\frac{g}{c(c^{2}-1)(a-c)^{2}},$ (II.50)
$\displaystyle\Lambda^{\infty,*}=\frac{K_{W}(a-c)^{2}(1-ac)}{g},$ (II.51)
$\displaystyle
K_{Z}^{\infty,*}=\frac{c\kappa(c^{2}-1)g-K_{W}^{2}(a-c)^{2}(1-ac)^{2}}{c(c^{2}-1)g}.$
(II.52) $\displaystyle g=K_{W}(2a-c+a^{2}c^{3}-2a^{2}c)+c\kappa(c^{2}-1)^{2}$
(II.53)

###### Proof.

The solution is obtained by a method similar to [14]. ∎

The discussion, conclusions and Figures of Section I-B, related to feedback
capacity, are based on Theorem II.4.
For the complements of Regimes A and B of Theorem II.4, or
$\kappa\leq\kappa_{min}$, there does not exist feedback strategy. However, we
can show that we can always pick $\Lambda^{\infty}=0$ and ensure a nonfeedback
achievable rate.

###  II-D Nonfeedback Achievable Rates of IID Channel Input Processes

Letting $\Lambda^{\infty}=0$, in (II.43), the channel input reduces to an
independent innovation process $X^{o}_{t}=Z^{o}_{t},\;t=1,\dots,n$, and hence
the code does not use feedback. For such an input the detectability and
stabilizibility conditions are always satisfied, and we obtain a nonfeedback
achievable rare, as stated in the next theorem.

######  Theorem II.5.

Consider (II.43), with $\Lambda^{\infty}=0$. and An achievable lower bound on
nonfeedback capacity is,

$\displaystyle
C_{LB}^{\infty,nfb}(\kappa)\stackrel{{\scriptstyle\triangle}}{{=}}\frac{1}{2}\log\Big{(}\frac{(c-a)^{2}K^{\infty}+\kappa+K_{W}}{K_{W}}\Big{)},\hskip
7.22743pt\forall\kappa\in(0,\infty)$ (II.54)

where $K^{\infty}$ is the unique and stabilizable solution of (II.44), with
$K_{Z}^{\infty}=\kappa,\Lambda^{\infty}=0$, given by

$\displaystyle
K^{\infty}=\frac{-h+\sqrt{h^{2}+4(c-a)^{2}K_{W}\kappa}}{2(c-a)^{2}}\geq 0$
$\displaystyle h=\kappa\big{(}1-c^{2})+K_{W}(1-a^{2}).$

###### Proof.

This is straightforward to show. ∎

##  III Acknowledgements

This work was supported in parts by the European Regional Development Fund and
the Republic of Cyprus through the Research Promotion Foundation Projects
EXCELLENCE/1216/0365 and EXCELLENCE/1216/0296.

##  IV Conclusion

In this paper, we characterized and derived closed form expressions of
feedback capacity and achievable lower bounds on nonfeedback rates, for AGN
channels driven by ARMA$(a,c),a\in(-\infty,\infty),c\in(-\infty,\infty),c\neq
a$ noise, when channel input strategies or distributions are time-invariant.
Simulations showed that the more unstable the noise the higher the feedback
capacity, and the achievable lower bounds on nonfeedback rates.

## References

  * [1] Y.-H. Kim, “Feedback capacity of stationary Gaussian channels,” _IEEE Transactions on Information Theory_ , vol. 56, no. 1, pp. 57–85, 2010.
  * [2] R. T. Gallager, _Information Theory and Reliable Communication_. John Wiley & Sons, Inc., New York, 1968.
  * [3] T. Cover and S. Pombra, “Gaussian feedback capacity,” _IEEE Transactions on Information Theory_ , vol. 35, no. 1, pp. 37–43, Jan. 1989.
  * [4] S. Butman, “A general formulation of linear feedback communications systems with solutions,” _IEEE Transactions on Information Theory_ , 1969.
  * [5] J. Tienan and J. P. M. Schalkwijk, “An upper bound to the capacity of bandlimited Gaussian autoregressive channel with noiseless feedback,” _IEEE Transactions on Information Theory_ , vol. IT-14, May 1974.
  * [6] J. Wolfowitz, “Signalling over a gaussian channel with feedback and autoregressive noise,” _Journal of Applied Probability_ , vol. 12, no. 4, pp. 713–723, 1975.
  * [7] S. Butman, “Linear feedback rate bounds for regressive channels,” _IEEE Transactions on Information Theory_ , 1976.
  * [8] L. Ozarow, “Upper bounds on the capacity of Gaussian channel with feedback,” _IEEE Transactions on Information Theory_ , vol. 36, no. 1, pp. 156–161, January 1984.
  * [9] S. Yang, A. Kavcic, and S. Tatikonda, “On feedback capacity of power-constrained Gaussian noise channels with memory,” _Information Theory, IEEE Transactions on_ , vol. 53, no. 3, pp. 929–954, March 2007.
  * [10] C. D. Charalambous, C. Kourtellaris, and S. Louka, “New formulas of feedback capacity for agn channels with memory: A time-domain sufficient statistic approach,” _arXiv preprint arXiv:2010.06226_ , 2020.
  * [11] T. Kailath, A. Sayed, and B. Hassibi, _Linear Estimation_. Prentice Hall, 2000.
  * [12] P. E. Caines, _Linear Stochastic Systems_ , ser. Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., New York, 1988.
  * [13] C. Kourtellaris, C. D. Charalambous, and S. Loyka, “New formulas of ergodic feedback capacity of agn channels driven by stable and unstable autoregressive noise,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 2073–2078.
  * [14] C. D. Charalambous, C. K. Kourtellaris, and S. Loyka, “Time-invariant feedback strategies do not increase capacity of AGN channels driven by stable and certain unstable autoregressive noise,” _CoRR_ , vol. abs/1907.10991, 2019\. [Online]. Available: http://arxiv.org/abs/1907.10991


# On the Utility of Prediction Sets in Human-AI Teams

Varun Babbar1 Umang Bhatt 1,2 Adrian Weller1,2 1University of Cambridge, 2The
Alan Turing Institute
{vb395, usb20<EMAIL_ADDRESS>
###### Abstract

Research on human-AI teams usually provides experts with a single label, which
ignores the uncertainty in a model’s recommendation. Conformal prediction (CP)
is a well established line of research that focuses on building a
theoretically grounded, calibrated prediction set, which may contain multiple
labels. We explore how such prediction sets impact expert decision-making in
human-AI teams. Our evaluation on human subjects finds that set valued
predictions positively impact experts. However, we notice that the predictive
sets provided by CP can be very large, which leads to unhelpful AI assistants.
To mitigate this, we introduce D-CP, a method to perform CP on some examples
and defer to experts. We prove that D-CP can reduce the prediction set size of
non-deferred examples. We show how D-CP performs in quantitative and in human
subject experiments ($n=120$). Our results suggest that CP prediction sets
improve human-AI team performance over showing the top-1 prediction alone, and
that experts find D-CP prediction sets are more useful than CP prediction
sets.

##  1 Introduction

Human-AI collaboration is of increasing importance. Several works have shown
the benefits of human-AI collaboration in boosting accuracy, fairness, and
compatibility Madras et al. (2018); Bansal et al. (2019); Mozannar and Sontag
(2020). One form of collaboration in the medical domain is the effect of AI
explanations on team performance Lundberg et al. (2018), where team
performance improves if model explanations are provided. Another form of
human-AI collaboration develops techniques for models to defer to an expert.
Prior literature exploring both these forms of collaboration has mainly
considered models which output singular predictions. However, this does not
allow experts to gauge and interpret the predictive uncertainty of the model,
which can prevent deployment in high risk settings. A solution to this is for
the model to display set valued predictions. We define a set valued model
prediction $\Gamma$ as a mapping from the input space $\mathcal{X}$ to the
power set of the label space $\mathcal{Y}$, i.e.
$\Gamma:\mathcal{X}\rightarrow 2^{\mathcal{Y}}$. One way to construct a set
valued predictor is through a technique called Conformal Prediction (CP) Vovk
et al. (2005). CP generates a prediction set that may contain multiple labels,
but contains the true label with a user defined error probability. The goal of
CP is to construct predictive sets that are sufficiently small but have high
probability of containing the true label.

One problem often associated with CP sets is that they can be quite large,
which can limit their usefulness in time and cost sensitive domains such as
medical diagnostics, where it is crucial to narrow down the list of possible
diagnoses. Previous work such as Bellotti (2021) and Stutz et al. (2022) have
devised surrogate loss functions for minimizing set sizes whilst maintaining
coverage guarantees. Angelopoulos et al. (2020) regularize the low scores of
unlikely classes to provide small, stable sets. However, CP literature in
general has given little consideration given to a) how useful such predictive
sets are in human-AI teams and b) how human expertise could be leveraged to
get smaller predictive sets Sadinle et al. (2016); Romano et al. (2020);
Angelopoulos and Bates (2021). Recently, Straitouri et al. (2022) explored
improving expert predictions using CP, with a focus on finding the optimal
error tolerance parameter $\alpha$ that benefits the expert. In this
concurrent work, we fix $\alpha$ and use deferral as a mechanism to provide
sets that are smaller and hence more useful to an expert.

Figure 1: An AI assistant working alongside an expert can output one of three
things: the most likely label, a set valued prediction with a predetermined
error probability, or a deferral token indicating that the example should be
labelled by the expert. The precise nature of the AI’s prediction should be
dependent on acquired knowledge of the expert’s capabilities. Generally
speaking, because the size of the predictive set is a reflection of the
model’s confidence, deferring examples on which an expert is more confident
than the model would prevent an expert from using large, incoherent prediction
sets.

Our contributions are the following:

  * •

Through human subject experiments on CIFAR-100, we first show that CP sets
result in higher levels of reported trust and utility as compared to Top-1
predictions.

  * •

We empirically demonstrate one limiting aspect of CP sets: they can be very
large for some examples. In order to mitigate this, we propose combining set
valued classification and learning to defer. Through a toy example, we show
the utility of learning to defer for the predictive set size of non-deferred
examples.

  * •

We then introduce D-CP, a general practical scheme that learns to defer on
some examples and perform conformal prediction on others. We prove that, under
mild conditions, the set size associated with non-deferred examples will be
smaller than that of the original dataset.

  * •

Through further human subject experiments on the CIFAR-100 dataset, we
discover two benefits of D-CP: smaller predictive sets and improved team
performance. We find that D-CP leads to higher reported utility and expert
accuracy compared to showing only CP sets.

##  2 Related Work

###  2.1 Conformal Prediction

There is growing interest in conformal prediction Vovk et al. (2005) as a
method of rigorous uncertainty quantification. Given a test example $X_{test}$
and its (hidden) true label $Y_{test}$, this method allows the user to
construct sets $\Gamma(X_{test})$ that control for the binary risk, i.e. the
error probability $\alpha=P(Y_{test}\notin\Gamma(X_{test}))$. This is done by
performing a statistical test for each label in order to decide whether the
label should be present in the set. In particular, we define a conformity
score $\tau(X_{test},y):\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{R}$
that determines how different example $(X_{test},y)$ is from already observed
data $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$. This is a design choice and several
papers explore different choices of conformity functions Sadinle et al.
(2016); Angelopoulos et al. (2020); Romano et al. (2020). To include label $y$
in a predictive set, we require that the conformity score $\tau(X_{test},y)$
is at least $\alpha$-common with respect to conformity scores on previously
observed data, i.e.
$\textrm{Quantile}(\tau(X_{test},y),\\{\tau(X_{i},Y_{i})\\})\geq\alpha$.

This is equivalent to learning a threshold conformity score for including
labels in a set. Defining the threshold as
$\tau_{cal}=\textrm{Quantile}(\alpha,\\{\tau(X_{i},Y_{i})\\})$, we require
$\tau(X_{test},y)\geq\tau_{cal}$ to include the label $y$ in the predictive
set for $X_{test}$. The conformal set is therefore defined as:
$\Gamma(X_{test},\tau_{cal})=\\{y:\tau(X_{test},y)\geq\tau_{cal}\\}$. In this
paper, we employ a computationally efficient scheme called Inductive Conformal
Prediction (ICP) Papadopoulos (2008). This requires an additional calibration
dataset $\mathcal{D}_{cal}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ drawn from the same
distribution as training and validation sets. After training a classifier on a
training dataset, we can use this calibration dataset to choose the $\alpha$
Quantile threshold $\tau_{cal}$.

None of the works that have previously studied CP Sadinle et al. (2016);
Angelopoulos et al. (2020); Romano et al. (2020); Stutz et al. (2022) involved
experts in the loop or even considered the utility of prediction sets
generated in the context of human-AI teams.

###  2.2 Learning to Defer

Many works have studied the idea of learning a model that adapts to an
underlying expert. One approach is to learn a rejector and a classifier,
wherein, given a cost of deferring $c$, one learns a binary classifier that
rejects whenever it is less than $1-c$ confident Bartlett and Wegkamp (2008);
Cortes et al. (2016). For multi-class problems, Mozannar and Sontag (2020)
learn a model that predicts the true label whenever the expert is wrong and
defers otherwise. Similarly, Okati et al. (2021) develop a method for exact
triage under multiple expert annotations and prove its optimality under
conditions where there is expert disagreement. Wilder et al. (2021), on the
other hand, develop a decision theoretic approach, training $3$ probabilistic
models representing the AI, expert, and joint human-AI to maximize utility.
However, all these approaches only examine settings where the AI makes point
predictions whereas we aim to defer some examples and provide principled,
calibrated prediction sets on others.

##  3 Are Prediction Sets better for Human-AI teams than Top-1 Predictions?

Our first study focuses on establishing the value of set valued predictions.
For our experiments, we focus on one particular CP scheme called Regularised
Adaptive Prediction Sets (RAPS) Angelopoulos et al. (2020). We recruit $30$
participants on Prolific, paying them at a rate of £$10$ per hour prorated,
and divide them into $2$ equal groups. The first group is shown $18$ images
from the CIFAR-100 dataset alongside the model’s most probable prediction
(Top-1). The second group is shown the same images but alongside a RAPS
prediction set with error rate $\alpha=0.1$. To understand the effect of set
valued predictions on examples of varying difficulty, we divide the CIFAR-100
test dataset into $3$ difficulty quantiles, where difficulty is defined as the
entropy of the model predictive distribution. We select $6$ images from each
difficulty quantile. For each quantile, we show $2$ images whose Top-1
prediction is incorrect but whose RAPS set contains the true label. This is
consistent with the accuracy of the model ($\approx 65\%$) and lets us
determine the effect of set valued predictions on examples on which the model
is almost correct. Given these model predictions for each image, we ask
participants in both groups to predict the correct class, rate their
confidence in their predictions, and rate how useful they found the model
predictions on that example. At the end of the survey, we ask participants to
rate their overall trust in the model’s predictions. All ratings are on a
scale from $1-10$. We employ preliminary attention checks by first asking them
to classify $3$ easy examples, rejecting any participants who classify these
examples incorrectly. We evaluate the statistical significance of our results
using a two sample t-test.

Metric | Top-1 | RAPS |  $p$ value | Effect Size
---|---|---|---|---
Accuracy | 0.76 $\pm$ 0.05 | 0.76 $\pm$ 0.05 | 0.999 | 0.000
Reported Utility | 5.43 $\pm$ 0.69 | 6.94 $\pm$ 0.69 | 0.003 | 1.160
Reported Confidence | 7.21 $\pm$ 0.55 | 7.88 $\pm$ 0.29 | 0.082 | 0.674
| Reported Trust in Model
---
5.87 $\pm$ 0.81 | 8.00 $\pm$ 0.69 |  $<$ 0.001 | 1.487

Table 1: Top-1 vs RAPS: All Examples

Metric | Top-1 | RAPS |  $p$ value | Effect Size
---|---|---|---|---
Accuracy | 0.90 $\pm$ 0.05 | 0.87 $\pm$ 0.07 | 0.486 | 0.273
Reported Utility | 6.067 $\pm$ 0.94 | 6.35 $\pm$ 1.00 | 0.438 | 0.195
Reported Confidence | 7.88 $\pm$ 0.65 | 8.82 $\pm$ 0.31 | 0.013 | 1.019

Table 2: Top-1 vs RAPS: Lowest Difficulty Quantile

Metric | Top-1 | RAPS |  $p$ value | Effect Size
---|---|---|---|---
Accuracy | 0.64 $\pm$ 0.07 | 0.66 $\pm$ 0.10 | 0.828 | 0.068
Reported Utility | 5.30 $\pm$ 0.75 | 7.28 $\pm$ 0.69 | 0.001 | 1.432
Reported Confidence | 6.64 $\pm$ 0.64 | 6.96 $\pm$ 0.78 | 0.4888 | 0.280

Table 3: Top-1 vs RAPS: Highest Difficulty Quantile

From Table 1, we see that Top-1 predictions result in statistically
significant lower levels of trust ($p<0.001$) and perceived utility
($p=0.003$) compared to RAPS. However, both schemes result in similar accuracy
and confidence in predictions. We also see that users find Top-1 and RAPS
predictions equally useful for easy examples (Table 2). This makes sense
because in such cases, the predictive set will be small and therefore
comparable to a Top-1 prediction. However, users are more confident about
their answers when they observe RAPS predictions. On the other hand, RAPS sets
are perceived to be much more useful on hard examples, where Top-1 predictions
will often be wrong.
Takeaway: While there is seen to be no significant difference in team accuracy
when shown either Top-1 or set-valued predictions, displaying set-valued
predictions in human-AI teams results in higher reported utility of
predictions as well as higher reported overall trust in the model.

##  4 Proposed Approach

###  4.1 The Problem with CP Sets

In our experiments above, we showed users examples where the set sizes on
CIFAR-100 are small enough to be considered useful. However, this may not
always be the case, especially on tasks with large label spaces. For instance,
a standard WideResNet model trained on CIFAR-100 ($\approx 65\%$ accuracy)
with APS conformal prediction yields prediction sets with greater than $15$
labels for $20\%$ of examples. One option to mitigate this issue is to defer
examples with the largest CP set sizes to an expert. However, this provides no
guarantee that the expert will be able to classify them with sufficient
accuracy. Furthermore, we also lose the finite sample coverage guarantees
provided by contemporary CP methods, i.e. we cannot ascertain that
$P(Y_{test}\notin\Gamma(X_{test}))\leq\alpha$.

###  4.2 Our Scheme

Our scheme, described in Algorithm 1, is centered around two components: a
deferral policy $\pi(x):\mathcal{X}\rightarrow\\{0,1\\}$ and a CP method. The
deferral policy is based on our knowledge of the expert’s strengths either
acquired during training or a-priori. For example, if an expert is better at
identifying brain tumors than our model, our policy should learn to defer
those examples with high probability. Using this black box policy, we first
prune our calibration dataset, removing all examples where our deferral policy
recommends deferral. One could use any scheme in Mozannar and Sontag (2020);
Okati et al. (2021); Wilder et al. (2021) to learn a deferral policy. While
Algorithm 1 specifies a deferral policy as an input, for some deferral methods
(such as Mozannar and Sontag (2020)), the policy is trained alongside the
model. In others, such as Okati et al. (2021), the policy is applied post-hoc.
In this paper, we consider the former deferral policy: the D-CP algorithm for
this is outlined in Algorithm $2$ in the Supplementary Material. After
training a model and a suitable deferral policy, we perform conformal
calibration on this pruned dataset of non-deferred examples. In this
procedure, for any predictive set $\Gamma(X_{test},\tau_{cal})$ for an example
$X_{test}$ we can guarantee that:

$1-\alpha\leq P(Y\in\Gamma(X_{test},\tau_{cal})|\pi(X_{test})=0)$ (1)

where $1$ represents the action of deferral. From Angelopoulos et al. (2020),
when the conformity scores are known to be almost surely distinct and
continuous, we can also guarantee:

$P(Y\in\Gamma(X_{test},\tau_{cal})|\pi(X_{test})=0)\leq
1-\alpha+\frac{1}{n+1}$ (2)

where $n$ is the size of the non-deferred calibration dataset. Because the
deferral policy $\pi$ probabilistically decides which unseen examples to
defer, all non-deferred examples can be thought of as being generated from a
data generating distribution $X\sim p(X|\pi(X)=0)$. Any new test example
$X_{test}$ that is not deferred is therefore independently drawn from this
distribution. Thus, $\\{X_{i}\\}_{i=1}^{n}\cup\\{X_{test}\\}\sim
p(X_{1},..X_{test}|\pi(X_{1}),..\pi(X_{test})=0)$ are exchangeable, thereby
satisfying the coverage guarantee in Equation 1.

Figure 2: D-CP: Test Phase given a deferral policy $\pi(X)$ Figure 3: D-CP:
Training and Calibration Phase Algorithm 1 General D-CP

Input: Classifier $m_{\theta}(x)\in\mathcal{R}^{|\mathcal{Y}|}$, Deferral
Policy $\pi(x)\in\\{0,1\\}$, Training Set $\mathcal{D}$, Expert
$h(x)\in\mathcal{Y}$, Calibration Set $\mathcal{D}_{\textrm{cal}}$, Validation
Set $\mathcal{D}_{\textrm{val}}$, Test Example $x_{test}$, Conformity Score
Function $\tau(X,y)$, Loss function $l(m_{\theta}(x),y,h(x))$
Parameter: Number of Epochs $N$, Learning Rate $\gamma$, Error Tolerance
$\alpha$

1:for $i\in\\{1,...N\\}$ do

2: for Batch $\mathcal{B}\in\mathcal{D}$ do

3:
$\theta=\theta-\gamma\mathbb{E}_{(x,y)\in\mathcal{B}}[\nabla_{\theta}l(m_{\theta}(x),y,h(x))]$

4: end for

5:end for

6:$\mathcal{D}^{\prime}_{\textrm{cal}}=\\{(X,Y)|\pi(X)=0,(X,Y)\in\mathcal{D}_{\textrm{cal}}\\}$

7:$\tau_{cal}=\textrm{Quantile}(\alpha,\\{\tau(X_{i},Y_{i})|(X_{i},Y_{i})\in\mathcal{D}^{\prime}_{\textrm{cal}}\\})$

8:if $\pi(X_{test})=0$ then

9: return $\Gamma(X_{test},\tau_{cal})=\\{y|\tau(X_{test},y)\geq\tau_{cal}\\}$

10:else if $\pi(X_{test})=1$ then

11: Defer to Expert $h(X_{test})$

12:end if

To show the utility of our scheme, a good deferral policy would guarantee that
resulting predictive sets on non-deferred examples will contain fewer
incorrect labels than before. We prove this formally in Theorem $1$ in the
Supplementary Material. While this technically applies to conformity scores
$\tau(x,y)$ that are monotonic with respect to softmax probabilities (such as
LAC), our subsequent experiments with other CP methods such as RAPS and APS
suggest that our scheme generalises well across other classes of conformity
score functions.

##  5 Toy Example

One way to combine conformal prediction and deferral is to only perform CP on
“easy” examples and defer the “hard” examples. An “easy” example would be one
which the model is confident on and a “hard” example is the converse. This can
lead to smaller sets. To demonstrate the intuition, we generate equiprobable
synthetic data using a Mixture of Gaussians (MoG) model. Each datapoint is
generated from one of $4$ Gaussians - $\mathcal{N}(1,1)$, $\mathcal{N}(1,-1)$,
$\mathcal{N}(-1,1)$, and $\mathcal{N}(-1,-1)$ \- and we wish to infer class
memberships. We first train a multilayer perceptron (MLP) on $1000$ training
samples (not shown) to infer the decision boundaries. Then, using a held out
calibration set, we perform CP with error tolerance $\alpha=5\%$ using the
Least Ambiguous Classifiers (LAC) method Sadinle et al. (2016). In this
method, we use the model softmax probabilities $p(y|x)=\tau(x,y)$ as
conformity scores. Figure 5 (top) shows a 1-D scatter plot of conformity
scores assigned to ground truth labels in the toy dataset.

Figure 4 shows the resulting test datapoints colored according to their true
classes with model decision boundaries overlaid. We see that points closer to
the decision boundary have larger predictive set sizes, reflecting their
inherent uncertainty. If we defer points with conformity scores in the bottom
$15^{th}$ percentile (naive decision policy) as in Figure 5, the $\alpha$
threshold conformity score will increase. From Figure 5 (Right), for non-
deferred examples, this increases the threshold for including labels in the
set, resulting in more confident sets for the same error control. However,
this naive deferral method, whilst ensuring small set sizes on the remaining
examples, does not take into account the expertise of the expert involved.
Furthermore, we assumed access to ground truth labels for test examples, which
is not practical. We can engage the expert in a better manner and approximate
the idea of the toy example by learning a deferral policy which incorporates
estimates of expert ability as well as machine difficulty. This scheme makes
an implicit assumption that the expert is a) either better than the model on
average or b) not necessarily better than the model on average, but is
proficient in classifying certain subgroups of examples. In these situations,
our deferral policy is more likely to defer examples that a model is less
confident on. Given these assumptions about an expert, Theorem $1$ ensures
lower predictive set sizes.

Figure 4: (Left): Toy dataset from Figure 1 comprising of datapoints belonging
to one of $4$ classes along with overlaid model decision boundaries. The size
of the datapoints indicates their predictive set sizes. (Right) We defer the
$\beta=0.15$ proportion of examples with the lowest ground truth conformity
scores. Doing so increases the value of the $5^{th}$ percentile conformity
score of the remaining examples in Figure 1, causing CP set sizes of examples
to be smaller. Note that we have not changed the model in this process.

Figure 5: (Left): 1-D scatter plot of all ground truth conformity scores
$\tau=p(Y_{i}|X_{i})$ on a toy calibration dataset in Figure 2. We assume an
oracle deferral policy that defers $\beta=15\%$ of examples with the lowest
$\tau$. Both values of $\tau_{cal}$ maintain $95\%$ coverage on their
respective datasets. (Right): Class probabilities for the test green starred
example. For the predictive set, we include all scores which are greater than
the threshold $\tau_{cal}$. Thus, the predictive set $\\{1,2,3\\}$ gives
$95\%$ coverage for the original dataset. On the non-deferred dataset, the set
$\\{1\\}$ gives $95\%$ coverage.

##  6 Experiments with D-CP

To validate our approach, we perform experiments with synthetic expert labels
on the CIFAR-100 dataset and real expert labels on the CIFAR-10H Peterson et
al. (2019) dataset111Our code is hosted at https://github.com/cambridge-
mlg/d-cp.. Because the CIFAR-10H dataset contains expert labels only on the
CIFAR-10H validation set, we employ the approach in Mozannar and Sontag (2020)
and train a binary classifier to predict examples where the expert is correct.
We then provide synthetic expert labels $\mathcal{I}_{h(x)=y}$ or
$\mathcal{I}_{h(x)\neq y}$ for examples the training set according to whether
the expert errs on them. Note that, in line with the assumption made in this
paper, the experts chosen in this setting are, on average, better than the
model trained. We consider $2$ scenarios:

  * •

We have access to a single expert’s annotations. For CIFAR-100, we generate a
synthetic expert with $70\%$ accuracy. To motivate this choice, we ran a
control study where we asked $20$ participants to classify $15$ randomly
chosen CIFAR-100 examples. We found participants had average accuracy of
$69\%$ with a standard error of $\approx 2.5\%$. For the CIFAR-10H dataset, we
randomly sample a label from the predictive distribution provided.

  * •

We have access to multiple expert annotations. This is an ensemble of the
above experts, and the predicted class is chosen through majority voting for
both datasets. For the CIFAR-100, we generate predictions from $5$ experts.

|  |  |  | Predictive Set Size of Non-Deferred Examples
---|---|---|---|---
Deferral Rate $b$ |  Classifier Accuracy |  System Accuracy (Single Expert) |  System Accuracy (Multiple Experts) | RAPS | APS | LAC
0 | 65.18 $\pm$ 0.30 | 65.18 $\pm$ 0.30 | 65.18 $\pm$ 0.30 | 3.75 $\pm$ 0.06 | 4.61 $\pm$ 0.08 | 3.26 $\pm$ 0.03
0.05 | 68.39 $\pm$ 0.31 | 68.04 $\pm$ 0.32 | 68.91 $\pm$ 0.33 | 3.22 $\pm$ 0.05 | 4.16 $\pm$ 0.06 | 2.48 $\pm$ 0.03
0.10 | 69.92 $\pm$ 0.24 | 69.95 $\pm$ 0.31 | 71.53 $\pm$ 0.35 | 2.81 $\pm$ 0.05 | 4.05 $\pm$ 0.06 | 2.13 $\pm$ 0.04
0.20 | 72.98 $\pm$ 0.30 | 72.25 $\pm$ 0.30 | 78.99 $\pm$ 0.40 | 2.36 $\pm$ 0.07 | 2.93 $\pm$ 0.10 | 2.07 $\pm$ 0.03

|  |  |  | Predictive Set Size of Non-Deferred Examples
---|---|---|---|---
Deferral Rate $b$ |  Classifier Accuracy |  System Accuracy (Single Expert) |  System Accuracy (Multiple Experts) | RAPS | APS | LAC
0 | 82.02 $\pm$ 0.55 | 82.02 $\pm$ 0.55 | 82.02 $\pm$ 0.55 | 1.91 $\pm$ 0.03 | 2.83 $\pm$ 0.05 | 2.47 $\pm$ 0.12
0.05 | 84.41 $\pm$ 0.69 | 84.31 $\pm$ 0.65 | 84.64 $\pm$ 0.30 | 1.87 $\pm$ 0.08 | 2.76 $\pm$ 0.10 | 2.25 $\pm$ 0.08
0.10 | 86.12 $\pm$ 0.67 | 86.53 $\pm$ 0.68 | 88.12 $\pm$ 0.61 | 1.73 $\pm$ 0.08 | 2.56 $\pm$ 0.07 | 1.90 $\pm$ 0.15
0.20 | 88.97 $\pm$ 0.50 | 89.43 $\pm$ 0.64 | 91.46 $\pm$ 0.32 | 1.49 $\pm$ 0.06 | 2.13 $\pm$ 0.11 | 1.51 $\pm$ 0.09

Table 4: D-CP Predictive Set Size, System Accuracy, and Classifier Accuracy on
the CIFAR-100 (top) and CIFAR-10H (bottom) datasets for the deferral scheme in
Mozannar and Sontag (2020) and the 3 CP schemes ($\alpha=0.1$, 5 Trials,
$95\%$ CI). Even in the low deferral rate regime, we not only obtain smaller
set sizes across all CP schemes tested, but also benefit from increased human-
AI system accuracy. While having multiple experts does not further improve the
predictive set size for this deferral policy, we benefit from further improved
system accuracy.

Our deferral policy is based on the loss function in Mozannar and Sontag
(2020). We train a WideResNet Zagoruyko and Komodakis (2016) classifier
$m_{\theta}(x):\mathcal{X}\rightarrow\mathcal{Y}\cup\perp$ on CIFAR-10H and
CIFAR-100 for $5$ and $10$ epochs respectively using the learning rate
schedule in Mozannar and Sontag (2020). $\perp$ represents the action of
deferral to an expert $h(x)$. We modify the loss function used in this work as
below:

$\displaystyle\mathcal{L}_{\textrm{CE}}(h,x,y,m_{\theta})$
$\displaystyle=-(\mathcal{I}_{h(x)\neq y}+\alpha\mathcal{I}_{h(x)=y})\log
m_{\theta}(x)_{y}$ $\displaystyle-\beta\mathcal{I}_{h(x)=y}\log
m_{\theta}(x)_{\perp}$

where we set $\alpha=1$ and vary the $\beta\in[0,1]$ penalty term to control
the deferral rate. The policy $\pi(x)$ is therefore:

$\pi(x)=\begin{cases}1&\textrm{argmax}_{y\in\mathcal{Y}\cup\perp}m_{\theta}(x)_{y}=|\mathcal{Y}\cup\perp|\\\
0&\textrm{otherwise}\end{cases}$

To compute conformity scores, we renormalize the softmax probabilities for
examples where $\pi(x)=0$ using Bayes’ rule:

$\displaystyle p(y|x,\pi(x)=0,\theta)$
$\displaystyle=\frac{p(y\neq|\mathcal{Y}\cup\perp||x,y,\theta)p(y|x,\theta)}{p(y\neq|\mathcal{Y}\cup\perp||x,\theta)}$
$\displaystyle=\frac{p(y|x,\theta)}{p(y\neq|\mathcal{Y}\cup\perp||x,\theta)}$

Figure 6: D-RAPS vs RAPS on some examples in the CIFAR-10H dataset
($\alpha=0.05$, $b=0.2$). Deferring on examples where experts are more
confident than the model provides smaller sets on examples where the model is
more confident than the expert. Thus, we leverage the strengths of both the
model and the expert. Figure 7: Cumulative CP and D-CP Set Size Distribution
of Non-Deferred Examples in the CIFAR-100 dataset ($\alpha=0.05$, deferral
rate $b=0.2$, Single Expert).

In our experiments, we did not notice any statistically significant difference
in accuracy of non-deferred examples or predictive set sizes when employing
multiple experts as opposed to a singular expert, at least in the deferral
rate regimes tested. Because we are performing experiments in the low deferral
rate regime, it is likely that the deferral scheme defers similar examples to
both expert types - examples the model is sure the expert(s) will get right.
Thus, in Table 4, the classifier accuracy and predictive set sizes are
representative for both singular and multiple experts. However, we benefit
from increased system accuracy by using ensemble voting across multiple
experts. In addition, per Table 4 and Figure 7, our scheme ensures smaller set
sizes across all conformal methods and deferral rates tested. Increasing the
deferral rate reduces the predictive set size. In Figure 6, the model and
expert have a mutually beneficial relationship: the model provides smaller
predictive sets on examples the expert is more uncertain on and defers
examples it is less certain of than an expert.

Takeaway: D-CP provides smaller predictive set sizes on non-deferred examples
for the same level of coverage. For the policy in Mozannar and Sontag (2020),
while the number of experts does not make a difference in the resulting
predictive set size of non-deferred examples, having more experts predict
through majority voting improves the system accuracy.

##  7 Evaluation on Experts

Our second human subject experiment focuses on establishing the value of
smaller set predictions and learning to defer - the 2 promises of D-CP. We
choose another set of $15$ examples from the CIFAR-100 test set for which we
generate RAPS prediction sets with error rate $\alpha=0.1$ and D-RAPS
prediction sets with deferral rate $0.2$ and error rate $\alpha=0.1$. We
select $12$ non-deferred examples at random wherein the D-RAPS predictive set
is smaller than the RAPS predictive set, but the ground truth labels are
contained in both sets. Lastly, we choose the remaining $3$ deferred examples
where the model is underconfident, i.e. the ground truth label is not in the
RAPS set. This aims to establish the value of deferral in situations where the
model may provide misleading predictions. We ask participants the same
questions as in Section $3$ and follow a similar recruitment procedure as in
Section 3 ($60$ participants total, $2$ groups, reward of £$10$ per hour
prorated).

Metric | D-RAPS | RAPS |  $p$ value | Effect Size
---|---|---|---|---
Accuracy | 0.76 $\pm$ 0.08 | 0.67 $\pm$ 0.05 | 0.002 | 0.832
Reported Utility | 7.93 $\pm$ 0.39 | 6.32 $\pm$ 0.60 |  $<$ 0.001 | 1.138
Reported Confidence | 7.31 $\pm$ 0.29 | 7.28 $\pm$ 0.29 | 0.862 | 0.046
| Reported Trust in Model
---
8.00 $\pm$ 0.45 | 6.87 $\pm$ 0.61 | 0.006 | 0.754

Table 5: D-RAPS vs RAPS: All Examples

Metric | D-RAPS | RAPS |  $p$ value | Effect Size
---|---|---|---|---
Accuracy | 0.88 $\pm$ 0.05 | 0.81 $\pm$ 0.04 | 0.058 | 0.508
Reported Utility | 7.93 $\pm$ 0.39 | 6.19 $\pm$ 0.62 |  $<$ 0.001 | 1.211
Reported Confidence | 7.78 $\pm$ 0.33 | 7.31 $\pm$ 0.34 | 0.059 | 0.507

Table 6: D-RAPS vs RAPS: Non-Deferred Examples

Tables $5$ and $6$ suggest that there is a statistically significant increase
in expert accuracy when the D-CP scheme is employed, with borderline
significance on non-deferred examples. Even though participants did not
perform as well on deferred examples in general, we noticed that their
accuracy was still higher than when they were shown CP sets, which contained
misleading labels. Equally interestingly, on examples where both RAPS and
D-RAPS sets contain the ground truth label (i.e. the non-deferred examples),
the perceived utility of D-CP sets is higher ($p<0.001$). As D-RAPS sets are
smaller, this shows that, for the same confidence level, smaller set sizes are
more useful to experts and therefore a preferred choice for human-AI teams.
Table $5$ also shows a statistically significant difference in reported trust
in the model between D-RAPS and RAPS. These are important considerations for
real world human-AI teams. We provide further results in the Supplementary
Material which show that participants display a bias towards towards incorrect
predictions shown in larger CP sets, warranting caution when deploying models
with large CP sets in human-AI teams.
Takeaway: There are statistically significant improvements increases in
reported utility, trust, and accuracy in the model when the D-CP scheme is
employed.

##  8 Conclusion

In this paper, we explored the importance of set valued predictions for human-
AI teams. We first showed experts find CP predictive sets more useful than
Top-1 predictions. However, CP set sizes can be very large for some examples,
especially in large label spaces. Thus, we motivate the need for combining the
ideas of learning to defer and set valued predictions. We introduce D-CP, a
general practical scheme that defers some examples and performs CP on others.
Empirical and theoretical evidence shows that the scheme provides smaller set
sizes on non-deferred examples for any CP method compared to performing CP on
all examples. The scheme allows the model and expert to have a mutually
beneficial relationship by leveraging the expert and the model’s respective
strengths. Our human subject experiments show that, compared to CP, experts
find the smaller D-CP predictive sets more useful, the model more trustworthy,
and are more accurate. We hope that this informs a) future research on
improved deferral policies that consider the predictive uncertainty of the
model and b) larger scale human evaluations that uncover specific, desirable
properties of a predictive set.

## Acknowledgements

The authors thank the anonymous reviewers for their thorough feedback. UB
acknowledges support from DeepMind and the Leverhulme Trust via the Leverhulme
Centre for the Future of Intelligence (CFI), and from the Mozilla Foundation.
AW acknowledges support from a Turing AI Fellowship under grant EP/V025279/1,
The Alan Turing Institute, and the Leverhulme Trust via CFI.

## References

  * Angelopoulos and Bates [2021] Anastasios N Angelopoulos and Stephen Bates.  A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification.  arXiv preprint arXiv:2107.07511, 2021.
  * Angelopoulos et al. [2020] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik.  Uncertainty Sets for Image Classifiers Using Conformal Prediction.  In International Conference on Learning Representations, 2020.
  * Bansal et al. [2019] Gagan Bansal, Besmira Nushi, Ece Kamar, Daniel S Weld, Walter S Lasecki, and Eric Horvitz.  Updates in Human-AI Teams: Understanding and Addressing the Performance/Compatibility Tradeoff.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2429–2437, 2019.
  * Bartlett and Wegkamp [2008] Peter L Bartlett and Marten H Wegkamp.  Classification with a reject option using a hinge loss.  Journal of Machine Learning Research, 9(8), 2008.
  * Bellotti [2021] Anthony Bellotti.  Optimized conformal classification using gradient descent approximation.  CoRR, abs/2105.11255, 2021.
  * Bondi et al. [2022] Elizabeth Bondi, Raphael Koster, Hannah Sheahan, Martin Chadwick, Yoram Bachrach, Taylan Cemgil, Ulrich Paquet, and Krishnamurthy Dvijotham.  Role of Human-AI Interaction in Selective Prediction.  Proceedings of the AAAI Conference on Artificial Intelligence, 2022\.
  * Cortes et al. [2016] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri.  Learning with Rejection.  In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 67–82, Cham, 2016. Springer International Publishing.
  * Lei et al. [2016] Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman.  Distribution-Free Predictive Inference For Regression.  Journal of the American Statistical Association, 113:1094–1111, 4 2016.
  * Lundberg et al. [2018] Scott M. Lundberg, Bala Nair, Monica S. Vavilala, Mayumi Horibe, Michael J. Eisses, Trevor Adams, David E. Liston, Daniel King-Wai Low, Shu-Fang Newman, Jerry Kim, and Su-In Lee.  Explainable Machine-Learning Predictions for the Prevention of Hypoxaemia During Surgery.  Nature Biomedical Engineering, 2(10):749–760, October 2018.
  * Madras et al. [2018] David Madras, Toniann Pitassi, and Richard Zemel.  Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6150–6160, 2018.
  * Mozannar and Sontag [2020] Hussein Mozannar and David Sontag.  Consistent Estimators for Learning to Defer to an Expert.  In International Conference on Machine Learning, pages 7076–7087. PMLR, 2020.
  * Okati et al. [2021] Nastaran Okati, Abir De, and Manuel Gomez-Rodriguez.  Differentiable Learning Under Triage.  In Advances in Neural Information Processing Systems, 2021.
  * Papadopoulos [2008] Harris Papadopoulos.  Inductive Conformal Prediction: Theory and Application to Neural Networks.  In Paula Fritzsche, editor, Tools in Artificial Intelligence, chapter 18. IntechOpen, Rijeka, 2008.
  * Peterson et al. [2019] Joshua Peterson, Ruairidh Battleday, Thomas Griffiths, and Olga Russakovsky.  Human Uncertainty Makes Classification More Robust.  In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 9616–9625, 2019.
  * Romano et al. [2020] Yaniv Romano, Matteo Sesia, and Emmanuel Candes.  Classification with Valid and Adaptive Coverage.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 3581–3591. Curran Associates, Inc., 2020.
  * Sadinle et al. [2016] Mauricio Sadinle, Jing Lei, and Larry Wasserman.  Least Ambiguous Set-Valued Classifiers with Bounded Error Levels.  Journal of the American Statistical Association, 114:223–234, 9 2016.
  * Straitouri et al. [2022] Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Gomez Rodriguez.  Provably improving expert predictions with conformal prediction.  CoRR, abs/2201.12006, 2022.
  * Stutz et al. [2022] David Stutz, Krishnamurthy Dj Dvijotham, Ali Taylan Cemgil, and Arnaud Doucet.  Learning optimal conformal classifiers.  In ICLR, 2022.
  * Tibshirani et al. [2019] Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candes, and Aaditya Ramdas.  Conformal Prediction Under Covariate Shift.  Advances in Neural Information Processing Systems, 32, 4 2019.
  * Vovk et al. [2005] Vladimir Vovk, Alex Gammerman, and Glenn Shafer.  Algorithmic Learning in a Random World.  Springer, 01 2005.
  * Wilder et al. [2021] Bryan Wilder, Eric Horvitz, and Ece Kamar.  Learning to Complement Humans.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20, 2021.
  * Zagoruyko and Komodakis [2016] Sergey Zagoruyko and Nikos Komodakis.  Wide Residual Networks.  In Edwin R. Hancock Richard C. Wilson and William A. P. Smith, editors, Proceedings of the British Machine Vision Conference (BMVC), pages 87.1–87.12. BMVA Press, September 2016.

##  Appendix A Proofs

######  Theorem 1.

Consider a deferral policy $\pi(x):\mathcal{X}\rightarrow\\{0,1\\}$ and a
classification model $m_{\theta}(x):\mathcal{X}\rightarrow\mathcal{Y}$ acting
on a dataset $\mathcal{D}=\\{(X_{1},Y_{1}),...(X_{n},Y_{n})\\}$. Define some
conformity measure $\tau(x,y)$ such that if $p(\hat{y}|\hat{x})\geq p(y|x)$
then $\tau(\hat{x},\hat{y})\geq\tau(x,y)$ for any softmax probabilities
$p(\hat{y}|\hat{x}),p(y|x)$, labels $\hat{y},y\in\mathcal{Y}$, and inputs
$\hat{x},x\in\mathcal{X}$. If the expected loss on non-deferred examples is
lower than the original loss, i.e.
$\mathbb{E}_{(x,y)|\pi(x)=0}[\mathcal{L}(y,m_{\theta}(x))]\leq\mathbb{E}_{(x,y)}[\mathcal{L}(y,m_{\theta}(x))]$,
then the average conformal predictive set of non-deferred examples will
contain fewer incorrect labels on average.

###### Proof.

Because the expected loss on non-deferred examples is lower, we know that:

$\mathbb{E}_{(x,y)|\pi(x)=0}[p(Y=y|x)]\geq\mathbb{E}_{(x,y)}[p(Y=y|x)]$ (3)

From our definition of the conformity measure $\tau(x,y)$ above:

$\mathbb{E}_{(x,y)|\pi(x)=0}[\tau(Y=y,x)]\geq\mathbb{E}_{(x,y)}[\tau(Y=y,x)]$
(4)

for any ground truth label $y$ associated with an example $x$. Therefore,

$\displaystyle\mathbb{E}_{(x,y)|\pi(x)=0}[\sum_{\begin{subarray}{c}i=1\\\
i\neq
y\end{subarray}}^{K}p(Y=i|x)]\leq\mathbb{E}_{(x,y)}[\sum_{\begin{subarray}{c}i=1\\\
i\neq y\end{subarray}}^{K}p(Y=i|x)]$
$\displaystyle\Rightarrow\mathbb{E}_{(x,y)|\pi(x)=0}[\sum_{\begin{subarray}{c}i=1\\\
i\neq
y\end{subarray}}^{K}\tau(Y=i,x)]\leq\mathbb{E}_{(x,y)}[\sum_{\begin{subarray}{c}i=1\\\
i\neq y\end{subarray}}^{K}\tau(Y=i,x)]$

Because
$\mathbb{E}_{(x,y)|\pi(x)=0}[\tau(Y=y,x)]\geq\mathbb{E}_{(x,y)}[\tau(Y=y,x)]$,
$\tau^{\prime}_{\alpha}=\textrm{Quantile}(\alpha,\\{\tau(Y=y,x)|(x,y)\in\mathcal{D},\pi(x)=0\\})\geq\tau_{\alpha}=\textrm{Quantile}(\alpha,\\{\tau(Y=y,x)|(x,y)\in\mathcal{D}\\})$
for any user defined error tolerance $\alpha\in[0,1]$. Thus:

$\mathbb{E}_{(x,y)|\pi(x)=0}\left[\sum_{\begin{subarray}{c}i=1\\\ i\neq
y\end{subarray}}^{K}\mathbb{I}_{\tau(Y=i,x)\geq\tau^{\prime}_{\alpha}}\right]\leq\mathbb{E}_{(x,y)|\pi(x)=0}\left[\sum_{\begin{subarray}{c}i=1\\\
i\neq y\end{subarray}}^{K}\mathbb{I}_{\tau(Y=i,x)\geq\tau_{\alpha}}\right]$
$\leq\mathbb{E}_{(x,y)}\left[\sum_{\begin{subarray}{c}i=1\\\ i\neq
y\end{subarray}}^{K}\mathbb{I}_{\tau(Y=i,x)\geq\tau_{\alpha}}\right]$

This implies:

$\displaystyle\mathbb{E}_{(x,y)|\pi(x)=0}[|\\{\hat{y}|\tau(x,\hat{y})\geq\tau^{\prime}_{\alpha},\hat{y}\neq
y\\}|]\leq$
$\displaystyle\mathbb{E}_{(x,y)}[|\\{\hat{y}|\tau(x,\hat{y})\geq\tau_{\alpha},\hat{y}\neq
y\\}|]$

∎

##  Appendix B Coverage Guarantees and Statistical Efficiency of D-CP

For an Inductive Conformal Predictior (ICP), the coverage is defined as:

$C=\frac{1}{n_{val}}\sum_{i=1}^{n_{val}}\mathcal{I}_{Y_{i}\in\Gamma(X_{i},\tau_{cal})|\\{(X_{i},Y_{i})\\}_{i=1}^{n}}$
(5)

for a validation dataset of size $n_{val}$ and a calibration dataset of size
$n$. While conformal prediction provides theoretical guarantees of the form in
Equations $1$ and $2$, due to the finite number of samples and variations in
test and training data distributions, ICP does not result in exact coverage in
practice. Tibshirani et al. [2019] and Lei et al. [2016] report that the
coverage of conformal intervals is highly concentrated around $1-\alpha$.
Because D-CP ensures that samples in the calibration and validation sets
remain exchangeable, we get similar coverage distributions for D-CP as we
would for any CP method. This is illustrated in Figure 8.

Figure 8: (top) Coverage Distribution on Non-Deferred Test Examples for
Different D-CP Schemes: Deferral Rate $\beta\approx 0.2$.
(bottom) Coverage Distribution on All Test Examples for Different CP Schemes.
For both D-CP and CP, $\alpha=0.05$, Dataset = CIFAR-10H, Number of Trials =
$200$, $n=8000$, $n_{val}=8000$

However, due to the reduced number of finite samples, we would expect a slight
increase in the variance of the coverage of the estimator. This is evident in
Figure 8. Angelopoulos and Bates [2021] show that the standard deviation of
the obtained coverage in Equation 5 can be expressed as:

$\textrm{Std}(C)=\sqrt{\frac{(n+1-l)(n+n_{val}+1)l}{n_{val}(n+1)^{2}(n+2)}}=\mathcal{O}\bigg{(}\frac{1}{\sqrt{\min(n,n_{val})}}\bigg{)}$
(6)

where $n$ and $n_{val}$ is the size of the calibration and test dataset
respectively and $l=\lfloor(n+1)\alpha\rfloor$. Given a deferral rate of
$\beta$, the effective sizes of $n$ and $n_{cal}$ reduce by a factor of
$1-\beta$ for D-CP, increasing the standard deviation of the average coverage
by a factor of $\frac{1}{\sqrt{1-\beta}}$. The benefits of smaller predictive
sets and human-AI complementarity therefore come at the price of a reduction
of statistical efficiency. However, this is not a problem in practice as long
as the model doesn’t defer a large proportion of examples to an expert.
Angelopoulos and Bates [2021] claim that a calibration size of $1000$ will be
sufficient for most applications employing CP methods. For D-CP, given a model
with, say a reasonable $20\%$ deferral rate, the calibration dataset need only
be around $25\%$ larger than before to provide empirical coverage with the
same variance as conventional CP methods.

##  Appendix C D-CP Algorithm for Experiments in Section 7

Below, we present one instance of the D-CP algorithm that was used for
experiments in this paper. Note that while the exact algorithm depends on the
deferral policy being trained (e.g. using approaches in Okati et al. [2021] or
Wilder et al. [2021]), the main workflow followed is illustrated in Section
$4$ in the paper.

Algorithm 2 D-CP using the deferral policy in Mozannar and Sontag [2020]

Input: Classifier $m_{\theta}(x):\mathcal{X}\rightarrow\mathcal{Y}\cup\perp$,
Training Set $\mathcal{D}$, Expert $h(x)\in\mathcal{Y}$ , Calibration Set
$\mathcal{D}_{\textrm{cal}}$, Validation Set $\mathcal{D}_{\textrm{val}}$,
Error Tolerance $\alpha$, Number of Epochs $N$, Learning Rate $\gamma$, Test
Example $x_{\textrm{test}}$

1:for $i\in\\{1,...N\\}$ do

2: for Batch $\mathcal{B}\in\mathcal{D}$ do

3:
$\theta=\theta-\gamma\mathbb{E}_{(x,y)\in\mathcal{B}}[\nabla_{\theta}l(m_{\theta}(x),y,h(x))]$

4:$\triangleright$ Loss function in Mozannar and Sontag [2020]

5: end for

6:end for

7:$D^{\prime}_{\textrm{cal}}=\varnothing$

8:for $(x,y)\in\mathcal{D}_{\textrm{cal}}$ do

9: if $\textrm{argmax}m_{\theta}(x)\neq|\mathcal{Y}|+1$ then

10: $m^{\prime}_{\theta}=\textrm{softmax}(m_{\theta})$ $\triangleright$
Deferral Policy

11:
$m^{\prime}_{\theta}=\frac{m^{\prime}_{\theta}[1:|\mathcal{Y}|]}{1-m^{\prime}_{\theta}[|\mathcal{Y}|+1]}$
$\triangleright$ Bayes’ Rule

12:
$D^{\prime}_{\textrm{cal}}=D^{\prime}_{\textrm{cal}}\cup(x,y,m^{\prime}_{\theta}(x))$

13: end if

14:end for

15:$\tau_{cal}$ = $\alpha$ threshold conformity score learnt from conformal
calibration on $\mathcal{D}^{\prime}_{cal}$

16:if $\textrm{argmax}m_{\theta}(x_{test})\neq|\mathcal{Y}|+1$ then

17: Output predictive set:

18:$\Gamma(x_{test})=\\{y|y\in\mathcal{Y},\tau(x_{test},y)\geq\tau_{cal}\\}$

19:else

20: Defer to expert $h(x_{test})$

21:end if

##  Appendix D Additional Results from Human Subject Experiments

###  D.1 Bias of Experts Towards Incorrect Model Predictions

Bondi et al. [2022] established for binary classifiers that model predictions
influence expert decisions and that displaying incorrect predictions can cause
experts to err in judgement when compared to purely deferring predictions. We
report similar findings for set valued predictions in this paper. To this end,
we define the bias towards incorrect predictions as the proportion of examples
where an incorrect prediction made by an expert is found in the predictive set
output by the model averaged across all subjects. That is, given experts $h$,
examples $x$, the associated label $y(x)$, and the CP set $\Gamma(x)$:

$\text{Bias}=\mathbb{E}_{h,x}\big{[}\mathcal{I}_{h(x)\in\Gamma(x)}\mathcal{I}_{h(x)\neq
y(x)}\big{]}$ (7)

Metric | D-RAPS |  | RAPS
---
Non-Deferred Examples
| RAPS
---
Deferred Examples
Bias | 0.063 $\pm$ 0.035 | 0.189 $\pm$ 0.046 | 0.933 $\pm$ 0.069

Table 7: D-RAPS vs RAPS: Bias towards incorrect or misleading labels

Comparing just the non-deferred examples (where both D-RAPS and RAPS sets
contain the true label) we see that experts are much more biased towards
incorrect predictions in RAPS sets than in D-RAPS sets. This is a consequence
of RAPS sets containing more incorrect labels, which presents more scope for
ambiguity. Another interesting observation is that on examples deferred by
D-RAPS (whose RAPS sets contain only incorrect labels), expert are much more
reliant on RAPS predictions. These findings warrant caution when deploying
models with only CP wrappers in human-AI teams, as large, incoherent sets in
critical settings can result in costly mistakes when expert bias their
decisions heavily on model predictions.

###  D.2 Further Analysis of RAPS vs D-RAPS

Metric | RAPS | D-RAPS | N | p-value | Effect Size | $\mathbf{N_{min}}$
---|---|---|---|---|---|---
Accuracy (All) | 0.67 | 0.76 | 30 | 0.003 | 0.87 | 22
Accuracy (Easy) | 0.87 | 0.83 | 30 | 0.310 | 0.27 | 218
Accuracy (Difficult) | 0.55 | 0.67 | 30 |  $<$ 0.001 | 1.04 | 16

Table 8: RAPS vs D-RAPS Accuracy on All Examples. $N_{min}$ is the minimum
sample size for each group needed for $p\leq 0.05$ with power $1-\beta=0.8$
and $N$ is the experimental sample size of each group.

Table 8 shows a power analysis on the results of the D-RAPS vs RAPS
experiments. We divide the $15$ images chosen into $3$ difficulty groups -
where difficulty is defined as the entropy of the model predictive
distribution - and evaluate the statistical significance of the accuracy on
the easiest and most difficult groups. It is seen that the accuracy increases
the most on examples the model found difficult, which are by definition the
most likely to be deferred. On the other hand, there is no increase in
accuracy of easy examples.

###  D.3 Human Subject Experiment Questions

In order to aid reproducibility, we also show excerpts from the survey
questionnaire for the RAPS vs Top-1 and D-RAPS vs RAPS experiments.

  * •

Figures $9$ and $10$ are questions posed to participants across all
experiments

  * •

Figures $11$ and $12$ are questions posed to participants in the RAPS vs
D-RAPS experiment.

  * •

Figures $13$ and $14$ are questions posed to participants in the RAPS vs Top-1
experiment.

Figure 9: After each non-deferred example, we asked users these questions
Figure 10: Additionally, at the end of the survey, we asked users to rate
their trust in the model on a scale from $1-10$

Figure 11: We first show an example of an image where both RAPS and D-RAPS
sets contain the true label, but the D-RAPS set is smaller than the RAPS set.
The true label for this image is: Cockroach. $15$ participants are shown the
RAPS set (left image) and $15$ different participants are shown the D-RAPS set
(right image)

Figure 12: We also have images where the RAPS set provides incorrect and
potentially misleading labels (such as ’willow tree’) but where a D-RAPS set
defers. The true label for this image is: Forest

Figure 13: While evaluating Top-1 predictions (left) in comparison to RAPS
(right), we choose some examples where Top-1 predictions are wrong but where
the true label is contained in the RAPS set. We have $2$ such images for each
difficulty quantile for a total of $6$ images. In this image, the true label
is: Pear.

Figure 14: For the remaining $9$ images, the Top-1 predictions are correct and
the RAPS sets contain the true label. Here, for example, the true label is:
Train.