# Classification Under Partial Reject Options

Måns Karlsson111Department of Mathematics, Stockholm University, 106 91
Stockholm, Sweden. Email<EMAIL_ADDRESS>Ola Hössjer222Department of
Mathematics, Stockholm University, 106 91 Stockholm, Sweden. Email:
<EMAIL_ADDRESS>
We study set-valued classification for a Bayesian model where data originates
from one of a finite number $N$ of possible hypotheses. Thus we consider the
scenario where the size of the classified set of categories ranges from 0 to
$N$. Empty sets corresponds to an outlier, size 1 represents a firm decision
that singles out one hypotheses, size $N$ corresponds to a rejection to
classify, whereas sizes $2\ldots,N-1$ represent a partial rejection, where
some hypotheses are excluded from further analysis. We introduce a general
framework of reward functions with a set-valued argument and derive the
corresponding optimal Bayes classifiers, for a homogeneous block of hypotheses
and for when hypotheses are partitioned into blocks, where ambiguity within
and between blocks are of different severity. We illustrate classification
using an ornithological dataset, with taxa partitioned into blocks and
parameters estimated using MCMC. The associated reward function’s tuning
parameters are chosen through cross-validation.

Keywords: Blockwise cross-validation, Bayesian classification, conformal
prediction, classes of hypotheses, indifference zones, Markov Chain Monte
Carlo, reward functions with set-valued inputs, set-valued classifiers.

##  1 Introduction

Classification of observations among a finite number $N$ of hypotheses or
categories is a well studied problem in statistics, and also a central concept
of modern machine learning (Bishop, 2006; Hastie et al., 2009). With a
Bayesian approach the maximum aposteriori classifier maximizes the probability
of a correct classification (Berger, 2013; Bishop, 2006). For some problems,
when there is much ambiguity about the category that fits data the best, it is
possible to add a reject option, where no classification is made (Chow, 1970;
Ripley, 2007; Freund et al., 2004; Herbei and Wegkamp, 2006), and if such a
reject option is followed by additional data collection, this leads to
Bayesian sequential analysis (Arrow et al., 1949). These types of classifiers
were generalized in Karlsson and Hössjer (2021), and formulated in the context
of reward functions with a set-valued argument. Each such reward function
leads to a set-valued classifier, where the size of the classified set of
categories is 0 if the classifier rejects all hypotheses, 1 for a firm
decision that singles out one category, between 1 and $N$ for a partial reject
option, where ambiguity remains between some but not all categories, and $N$
for a rejection to classify, i.e when none of the categories are singled out.

In this paper we analyze reward functions with a set-valued argument in more
detail, and in particular we derive the associated optimal Bayes classifiers
that maximize expected rewards. We start by considering reward functions for a
homogeneous collection of categories of the same type, and find explicit
formulas for the Bayes classifier in terms of the ordered aposteriori
probabilities of all hypotheses and a penalty term for the size of the
classified set. It is shown that conformal prediction (Vovk et al., 2005;
Shafer and Vovk, 2008) with posterior probabilities as nonconformity measure
is a special case of our approach. Then we consider scenarios where the
categories are divided into a number of blocks, such that categories
(typically) are more similar within than between blocks. The associated Bayes
classifiers involve the ordered aposteriori probabilities within each block
and penalty terms $a$ and $b$ for adding classified categories from the
correct and wrong blocks respectively. In particular, we demonstrate that
classification with indifference zones (Bechhofer, 1954; Goldsman, 1986) can
be represented as an instance of set-valued classification with two blocks of
categories.

Our framework of set-valued classification, with the set of categories
partitioned into blocks, is applied to an ornithological data set. Each
observation in data consists of three observed traits for a bird and which
taxon the bird belongs to. Based on these data we want to train a classifier
of future birds to taxon. The taxa are partitioned into blocks with regard to
cross-taxon similarities. The parameters of the underlying statistical model
are estimated through a Markov Chain Monte Carlo procedure, and the tuning
parameters of the set-valued reward function are estimated through cross
validation.

The article is organized as follows: In Section 2 we introduce the statistical
model with $N$ hypotheses, and define the optimal (Bayes) set-valued class-
ifier. Then we introduce a large class of reward functions for models with one
block of categories (Section 3) and several blocks of categories (Section 4)
respectively, and give explicit expressions for the corresponding Bayes
classifiers. The ornithological dataset is analyzed in Section 5 and a
discussion in Section 6 concludes the paper.

##  2 Statistical model and optimal classifiers

Consider a random variable $Z\in{\cal Z}$, whose distribution follows one of
$N$ possible hypotheses (or categories)

$H_{i}:Z\sim f_{i},\quad i=1,\ldots,N,$ (1)

where $f_{i}$ is the density or probability function of $Z$ under $H_{i}$. We
will assume a Bayesian framework, and thus the true but unknown hypothesis
$I\in{\cal N}=\\{1,\ldots,N\\}$ is a random variable. It is given a
categorical prior distribution with parameter vector $\pi_{i}=P(I=i)$, for
$i=1,\ldots,N$ and the corresponding parameter vector of the categorical
posterior distribution of an observed value $z$ of $Z$ is

$p_{i}=p_{i}(z)=\mathbb{P}(I=i|Z=z)=\frac{\pi_{i}f_{i}(z)}{\sum_{j=1}^{N}\pi_{j}f_{j}(z)}.$
(2)

Our objective is to classify $z$. To this end, a classifier
$\hat{I}=\hat{I}(z)\subset{\cal N}$ with partial reject options is defined as
a subset of categories. When $\hat{I}=\\{i\\}$, a firm decision of category
$i$ is made, whereas $\hat{I}={\cal N}$ corresponds to a reject option, where
no decision is made about which categories that conform with $z$ the most.
Note that it is the action “to classify” that is rejected, when $\hat{I}={\cal
N}$. The intermediate case $2\leq|\hat{I}|=m\leq N-1$ corresponds to a partial
reject option, where the classifier excludes $N-m$ hypotheses but rejects
discrimination among the remaining $m=m(z)$ categories. Another possibility,
$\hat{I}=\emptyset$, corresponds to a scenario where none of the $N$
categories fit the observed data $z$ well, i.e. we exclude all hypotheses.
This can be regarded as a safeguard against outliers or otherwise faulty data
(Ripley, 2007; Karlsson and Hössjer, 2021).

Let

$p_{(1)}\leq\ldots\leq p_{(N)}$ (3)

refer to the ordered posterior category probabilities. The well-known Maximum
Aposteriori (MAP) classifier (Berger, 2013)

$\hat{I}=\hat{I}(z)=\\{(N)\\}$ (4)

always makes a firm decision, so that

$\mathbb{P}(|\hat{I}|=1)=1.$ (5)

It also maximizes the probability $\mathbb{P}(\hat{I}=\\{i\\})$ of a correct
classification, but has a higher probability of misclassification than correct
classification, when $p_{(N)}<1/2$. The MAP classifier can be formulated as
$\hat{I}$ being the classifier that maximizes the expected value

$\bar{V}=\mathbb{E}[R(\hat{I},I)]$ (6)

of the reward function

$R({\cal I},i)=\left\\{\begin{array}[]{ll}1,&{\cal I}=\\{i\\},\\\ 0,&{\cal
I}\neq\\{i\\}\end{array}\right.$ (7)

assigned to a classified subset ${\cal I}\subset{\cal N}$ of categories when
the true category is $i$. Since $\hat{I}=\hat{I}(Z)$, the expectation in (6)
is with respect to $Z$ and $I$. Let the value function

$V(z;{\cal I})=\mathbb{E}\left[R({\cal I},I)\mid Z=z\right]$

refer to the conditional expected reward given $Z=z$. It is clear the optimal
Bayes classifier, that maximizes the expected reward, or equivalently
maximizes the expected value function $\bar{V}=\mathbb{E}[V(Z;\hat{I}(Z))]$ is
obtained as

$\displaystyle\hat{I}(z)$ $\displaystyle=\operatorname*{arg\,max}_{{\cal
I}\subset{\cal N}}V(z;{\cal I})$
$\displaystyle=\operatorname*{arg\,max}_{{\cal I}\subset{\cal
N}}\mathbb{E}\left[R({\cal I},I)\mid Z=z\right]$
$\displaystyle=\operatorname*{arg\,max}_{{\cal I}\subset{\cal
N}}\sum_{i=1}^{N}R({\cal I},i)p_{i}(z)$ (8)

for each $z\in{\cal Z}$. Since the reward function (7) only takes non-zero
values for singelton choices of ${\cal I}\subset{\cal N}$, we only need to
consider ${\cal I}=\\{i\\}$ for $i=1,\ldots,N$, in order to find $\hat{I}$.
For each choice ${\cal I}=\\{i\\}$, $V(z;\\{i\\})=p_{i}$. Thus we choose
$i=(N)$, since $p_{(N)}$ for each fixed $z$ is the largest value $V(z,{\cal
I})$ can return. This shows that the MAP classifier (4) is the optimal
classifier under (7).

In this paper we will consider optimal classifiers (8) for reward functions
other than (7); those that allow not only for single classified categories,
but also for outliers and (partial) reject options.

##  3 Partial rejection, one block of categories

When ${\cal N}$ represents one homogeneous block of categories, the following
class of reward functions is natural to use:

######  Definition 1.

Given a set of categories ${\cal N}=\\{1,\ldots,N\\}$, with $i\in{\cal N}$ the
true category of an observation and ${\cal I}\subset{\cal N}$ the classified
subset of categories, a reward function

$R({\cal I},i)=R(\tau({\cal I}),\tau(i))$ (9)

invariant w.r.t. permutations $\tau:{\cal N}\to{\cal N}$ of the labels is
called an _invariant reward function_.

It is easily seen that

$R({\cal I},i)=1(i\in{\cal I})-g(|{\cal I}|)$ (10)

is an invariant reward function. The first term of (10) corresponds to a
reward of 1 for a classified set ${\cal I}$ that includes the true category
$i$, whereas the second term $g(|{\cal I}|)\geq 0$ penalizes based on the size
$|{\cal I}|$ of the classified set. Of particular interest are the following
classifiers:

######  Definition 2.

A classifier containing the $m\in\\{0,\ldots,N\\}$ categories with the largest
posterior probabilities, where

$\hat{I}_{m}=\begin{cases}\\{(N+1-m),\ldots,(N)\\},&\quad m\geq 1,\\\
\emptyset,&\quad m=0,\end{cases}$ (11)

is called an _$m$ most probable classifier_, abbreviated as an $m$-MP
classifier.

The MAP classifier is thus a special case of the more general class of $m$-MP
classifiers, and obviously the 1-MP classifier is the MAP classifier, whereas
the $0$-MP classifier corresponds to the empty set, since we then choose none
of the categories. We will now link invariant reward functions of type (10) to
$m$-MP classifiers:

######  Proposition 1.

The optimal classifier for an invariant reward function of type (10), is an
$m$-MP classifier $\hat{I}(z)=\hat{I}_{m(z)}$ with

$m(z)=\operatorname*{arg\,max}_{0\leq m\leq N}\left[v(m;z)-g(m)\right].$ (12)

where $v(0;z)=0$ and

$v(m;z)=\sum_{j=1}^{m}p_{(N+1-j)},\quad m=1,\ldots,N.$ (13)

###### Proof.

Recall that the optimal classifier $\hat{I}(z)$ maximizes, for each $z\in{\cal
Z}$, the value function $V(z;{\cal I})$ among all nonempty subsets ${\cal I}$
of ${\cal N}$. For the reward function of equation (10) we have that

$\displaystyle V(z;{\cal I})=\mathbb{E}\left[R({\cal I},I)\mid Z=z\right]$
$\displaystyle=\sum_{i=1}^{N}\left(1(i\in{\cal I})-g(|{\cal
I}|)\right)p_{i}(z)$ $\displaystyle=\sum_{i=1}^{N}1(i\in{\cal
I})p_{i}(z)-\sum_{i=1}^{N}g(|{\cal I}|)p_{i}(z)$
$\displaystyle=\sum_{i\in{\cal I}}p_{i}-g(|{\cal I}|)$
$\displaystyle\leq\sum_{j=1}^{|{\cal I}|}p_{(N+1-j)}-g(|{\cal I}|)$
$\displaystyle=v(|{\cal I}|;z)-g(|{\cal I}|).$ (14)

Note that the inequality occurs since we go from considering a subset ${\cal
I}\subseteq{\cal N}$ of categories to considering another subset with equally
many but the most probable categories. Consequently, among all ${\cal
I}\subset{\cal N}$ of size $|{\cal I}|=m$, the value function $V(z;{\cal I})$
is maximized by $\hat{I}_{m}$ in (11), for some $m\in\\{0,\ldots,N\\}$. Among
these subsets, the optimal classifier is $\hat{I}=\hat{I}_{m(z)}$, where
$m(z)$ is the value of $|{\cal I}|$ that maximizes the right hand side of
(14). Since this value of $m(z)$ is identical to the one in (12), this
finishes the proof. ∎

Example 1 (Classification with reject options.) Ripley (2007) introduced a
reward function with a reject option. In our notation it corresponds to

$R({\cal I},i)=\left\\{\begin{array}[]{ll}1(i=j),&{\cal I}=\\{j\\},\\\
r,&{\cal I}={\cal N},\\\ 0,&|{\cal
I}|\in\\{0,2,3,\ldots,N-1\\},\end{array}\right.$ (15)

with a reward of $1/N<r<1$ assigned to the reject option. The special case of
(15) for $N=2$ categories was treated by Chow (1970); Herbei and Wegkamp
(2006). Note that (15) is equivalent to a reward function (10) with penalty
term

$g(m)=\left\\{\begin{array}[]{ll}0,&m=1,\\\ 1,&m=2,\ldots,N-1,\\\
1-r,&m=N.\end{array}\right.$ (16)

The corresponding classifier

$\hat{I}=\left\\{\begin{array}[]{ll}(N),&p_{(N)}>r,\\\ {\cal N},&p_{(N)}\leq
r\end{array}\right.$ (17)

is of interest for Bayesian sequential analysis (Arrow et al., 1949; Berger,
2013) and sequential clinical trials (Carlin et al., 1998), where the reject
option $\hat{I}={\cal N}$ corresponds to delaying the decision and collecting
more data before the seqential procedure is stopped and a specific category is
chosen. $\Box$

The next result is a corollary of Proposition 1, and it treats an important
class of reward functions with a convex penalty function:

######  Corollary 1.

Consider a classifier $\hat{I}(z)$ based on a reward function (10), for which
the penalty term $g(m)$ is a convex function of $m$, with $g(0)=0$. Then (12)
simplifies to $\hat{I}(z)=I_{m(z)}$, with

$m(z)=\max\\{m^{\prime}(z),m^{\prime\prime}(z)\\},$ (18)

where

$\begin{array}[]{rcl}m^{\prime}(z)&=&0,\\\ m^{\prime\prime}(z)&=&\max\\{1\leq
m\leq N;\,p_{(N+1-m)}\geq g(m)-g(m-1)\\},\end{array}$ (19)

and $\max\emptyset=-\infty$ in the definition of $m^{\prime\prime}(z)$.

######  Remark 1.

Note that in the second line of (19), the inequality constitutes an inclusion
criterion that a category needs to fulfill to be included in the classifier.
As can be seen from the left and right hand sides of the inequality, the
category with the largest posterior probability not yet included, will be
included if its posterior probability is larger than the added penalty
$g(m)-g(m-1)$ associated with enlarging the size of the classifier from $m-1$
to $m$.

###### Proof.

In order to prove (19), we first deduce from (3) that $v(m;z)$ is a concave
function of $m$ (indeed, the differences $v(m+1;z)-v(m,z)$ are decreasing as
$m$ increases and thus $v(m;z)$ is concave). Consequently, if $g(m)$ is a
convex function of $m$ it follows that $v(m;z)-g(m)$ is a concave function of
$m$, and it is therefore maximized by

$m(z)=\max\left\\{0,\max_{1\leq m\leq N}\left\\{\,v(m;z)-g(m)\geq
v(m-1;z)-g(m-1)\right\\}\right\\},$ (20)

where $\max\emptyset=-\infty$ in the inner maximization. By the definition of
$v(m;z)$ in (13), equation (20) is equivalent to the expression for $m(z)$
given in equation (19). ∎

Example 2 (Proportion-based reward functions.) In order to illustrate
Corollary 1 we introduce the following class of reward functions with a
penalty germ $g(m)=c\max(0,m-1)$ that only includes one cost parameter $c$:

######  Definition 3.

An invariant reward function of the form

$R({\cal I},i)=1(i\in{\cal I})-c\max(0,|{\cal I}|-1),$ (21)

with $c\geq 0$, is called a _proportion-based reward function_.

Note that a proportion-based reward function has a penalty term that is almost
linear in $|{\cal I}|$. It is only the maximum operator that prevents us from
refering to (21) as a reward function with a linear penalty term (abbreviated
as a linear reward function). We may interpret $c$ as a cost per extra
classified category on top of the first one. For proportion-based reward
functions, Corollary 1 simplifies as follows:

######  Corollary 2.

A proportion-based reward function (21) gives rise to an $m$-MP classifier
(11) with $m(z)$ as in (18) and

$\begin{array}[]{rcl}m^{\prime}(z)&=&1,\\\ m^{\prime\prime}(z)&=&\max\\{2\leq
m\leq N;\,p_{(N+1-m)}\geq c\\}.\end{array}$ (22)

###### Proof.

Since a proportion-based reward function (21) has penalty term
$g(m)=c\max(0,m-1)$, it follows that

$g(m)-g(m-1)=\left\\{\begin{array}[]{ll}0,&m=1,\\\
c,&m=2,\ldots,N.\end{array}\right.$ (23)

Inserting (23) into (19), equation (22) follows. ∎

Note that the MAP classifier (4) is obtained for $c>p_{(N)}$. For this reason
Karlsson and Hössjer (2021) restricted the cost term of (21) to a range $0\leq
c\leq p_{(N)}$ and reparametrized it as

$c=\rho p_{(N)},$ (24)

with $0\leq\rho\leq 1$. The $m$-MP classifier (11), with $m=m(z)$ as in (18)
and (22), then takes the form

$\hat{I}=\\{i;\,p_{i}\geq\rho p_{(N)}\\}.$ (25)

$\Box$

Example 3 (Conformal prediction) Conformal prediction (Vovk et al., 2005;
Shafer and Vovk, 2008) is a general method for creating a prediction region
$\Gamma^{\delta}=\Gamma^{\delta}(z)$ for an observation $z$ with a confidence
level $(1-\delta)$%, where $\delta\in(0,1)$ is chosen freely, typically close
to 0. For the case of categorical prediction, the conformal algorithm (Shafer
and Vovk, 2008, Section 4.3) uses as input the new observation $z$ that we
want to classify, a labeled training data set $B$, the number $\delta$, and a
nonconformity measure $A$. Then for each possible label $i\in{\cal N}$ of $z$
a decision is made as to whether $i$ should be included in the prediction
region $\Gamma^{\delta}$ or not.

It turns out that conformal prediction is as a special case of the
classification theory presented this section, when posterior probabilities are
used as nonconformity measure. We choose the penalty term $g(|{\cal
I}|)=c|{\cal I}|$ in (10) and find that
$\Gamma^{\delta}=\hat{I}(z)=\hat{I}_{m(z)}$, where

$\displaystyle m(z)$ $\displaystyle=\max\left\\{0,\max\left\\{1\leq m\leq
N;p_{(N+1-m)}\geq c\right\\}\right\\}$ $\displaystyle=\left\\{i;1\leq i\leq
N,p_{i}\geq c\right\\},$ (26)

We can use theory from Shafer and Vovk (2008) to specify how $c=c(\delta)$ in
(26) relates to $\delta$. To this end, let $z$ be the observation we want to
classify. For each possible label (or category) $i\in{\cal N}$ of $z$,
provisionally set $(z,i)$ as a future observation that is part of training
data (although in practice $z$ is rather a future observation that we want to
classify). The batch of previous examples $B$ corresponds to a very large
training data set (which is called ${\cal D}={\cal D}_{1}\cup\ldots\cup{\cal
D}_{N}$ in Section 5.2), with $n_{i}\to\infty$ observations from each category
$i$, which in the limit makes it possible to know the distributions
$f_{1},\ldots,f_{N}$ of data under the various hypotheses. If
$n_{i}/\sum_{j=1}^{N}n_{j}\to\pi_{i}$ when $n_{i}\to\infty$ for
$i=1,\ldots,N$, the asymptotic batch corresponds to a mixture

$f\sim\sum_{i=1}^{N}\pi_{i}f_{i}$ (27)

of the distributions of the $N$ categories. We then use the posterior
probabilities $\pi_{i}$ to define the nonconformity measure

$A[B,(z,i)]=p_{i}(z).$ (28)

Let $F_{i}$ refer to the distribution function of $p_{i}(Z)$ when $Z\sim
f_{i}$, and let

$F=\sum_{i=1}^{N}\pi_{i}F_{i}$ (29)

be the corresponding mixture distribution function. The conformal algorithm
then corresponds to choosing a classifier (26) with

$c=F^{-1}(\delta),$ (30)

where, as mentioned, $1-\delta$ is the confidence level of the prediction
region.

As a last remark, if the penalty parameter is changed from $c$ to
$\rho=c/p_{(N)}$ (cf. Example 2), we notice that (26) is equivalent to (25)
for any value of $\rho\geq 0$. $\Box$

##  4 Several blocks of categories

This section will cover an extension of the classical classification problem,
where observations belong to a category and categories belong to
supercategories, or blocks, as we will call them. Thus we partition the $N$
categories into $K$ blocks of sizes $N_{1},\ldots,N_{K}$, with
$\sum_{k=1}^{K}N_{k}=N$. Without loss of generality, the labels $i$ are
defined so that each block

${\cal N}_{k}=\left\\{\sum_{l=1}^{k-1}N_{l}+1\leq
i\leq\sum_{l=1}^{k}N_{l}\right\\}$ (31)

consists of adjacent categories. The different scenarios when it is worse to
misclassify within a block than between blocks, and vice versa, will be a
subject of study later on in the paper. In order to define classifiers that
take this into account, we introduce a new type of reward functions.

######  Definition 4.

For a set of $N$ categories, partitioned into blocks ${\cal N}_{k}$,
$k=1,\ldots,K$ with $N_{k}$ categories in each block, _block invariant reward
functions_ satisfy (9) only for block preserving permuations $\tau({\cal
N}_{k})={\cal N}_{k}$, $k=1,\ldots,K$.

A class of block invariant reward functions is

$R({\cal I},i)=1(i\in{\cal I})-g_{k(i)}(|{\cal I}_{k(i)}|,|{\cal I}|-|{\cal
I}_{k(i)}|),$ (32)

where

${\cal I}_{k}={\cal I}\cap{\cal N}_{k}$ (33)

contains the categories of the classified set ${\cal I}$ that belong to block
$k$, whereas $k(i)$ is the block to which $i$ belongs, i.e. $i\in{\cal
N}_{k(i)}$. Moreover, $g_{k}$ is a penalty term for misclassification, when
the true category $i$ belongs to ${\cal N}_{k}$. This term is a function of
the number of categories $|{\cal I}_{k(i)}|$ in the classified set ${\cal I}$
that belong to the correct block as well as the number of classified
categories $|{\cal I}|-|{\cal I}_{k(i)}|$ that belong to any of the wrong
blocks. In order to define the classifiers of interest we order the posterior
probabilities $p_{i}$, $i\in{\cal N}_{k}$ within each block as

$p_{(k1)}\leq\ldots\leq p_{(kN_{k})}.$

######  Definition 5.

For an integer vector

$\mbox{\boldmath$m$}=(m_{1},\ldots,m_{K})\in\bigotimes_{k=1}^{K}\\{0,\ldots,N_{k}\\}$
(34)

let

$\hat{I}_{\mbox{\scriptsize\boldmath$m$}}=\left\\{(ki);\,1\leq k\leq
K,N_{k}+1-m_{k}\leq i\leq N_{k}\right\\}$ (35)

be a classifier that includes the $m_{k}$ categories with the largest
posterior probabilites from block $k$. We call this a _composite classifier_.

A composite classifier is a subset of ${\cal N}$ of size

$m=\sum_{k=1}^{K}m_{k}.$ (36)

In particular, the two extreme scenarios with no categories classified or a
rejection to classify, correspond to $\hat{I}_{(0,\ldots,0)}=\emptyset$ and
$\hat{I}_{(N_{1},\ldots,N_{K})}={\cal N}$ respectively. Moreover, (36) reduces
to an $m_{k}$-MP classifier (11) for a particular block $k$ if $m$ has only
one non-zero element $m_{k}$ (cf. Example 4). The following result links
composite classifiers to block invariant reward functions of type (32):

######  Proposition 2.

The optimal classifier, for a reward function (32), is a composite classifier
$\hat{I}(z)=\hat{I}_{\mbox{\scriptsize\boldmath$m$}(z)}$ in (35), with

$\mbox{\boldmath$m$}(z)=\operatorname*{arg\,max}_{\mbox{\scriptsize\boldmath$m$}=(m_{1},\ldots,m_{K})}\sum_{k=1}^{K}\left[v_{k}(m_{k};z)-P_{k}g_{k}(m_{k},m-m_{k})\right],$
(37)

where

$\displaystyle P_{k}=P_{k}(z)$ $\displaystyle=\sum_{i\in{\cal N}_{k}}p_{i},$
$\displaystyle m$ $\displaystyle=\sum_{k=1}^{K}m_{k},$ (38) $\displaystyle
v_{k}(m_{k};z)$ $\displaystyle=\sum_{j=1}^{m_{k}}p_{(k,N_{k}+1-j)}$

and $v_{k}(0;z)=0$ for any $k$.

###### Proof.

The proof mimics that of Proposition 1. We start by finding the value function
$V(z;{\cal I})$ in (8) for the block invariant reward function (32). It is
given by

$\displaystyle V(z;{\cal I})$ $\displaystyle=\sum_{k=1}^{K}\sum_{i\in{\cal
I}_{k}}p_{i}-\sum_{k=1}^{K}P_{k}g_{k}(|{\cal I}_{k}|,|{\cal I}|-|{\cal
I}_{k}|)$ $\displaystyle\leq\sum_{k=1}^{K}\left[\sum_{j=1}^{|{\cal
I}_{k}|}p_{(k,N_{k}+1-j)}-P_{k}g_{k}(|{\cal I}_{k}|,|{\cal I}|-|{\cal
I}_{k}|)\right]$ $\displaystyle=\sum_{k=1}^{K}\left[v_{k}(|{\cal
I}_{k}|;z)-P_{k}g_{k}(|{\cal I}_{k}|,|{\cal I}|-|{\cal I}_{k}|)\right].$ (39)

From this it follows that $V(z;{\cal I})$ is maximized, among all ${\cal I}$
with $|{\cal I}_{k}|=m_{k}$ for $k=1,\ldots,K$, by
$\hat{I}_{(m_{1},\ldots,m_{K})}$ in (35). The optimal classifier is therefore
$\hat{I}=\hat{I}_{\mbox{\scriptsize\boldmath$m$}(z)}$, where
$\mbox{\boldmath$m$}(z)=(m_{1}(z),\ldots,m_{K}(z))$ is the value of $(|{\cal
I}_{1}|,\ldots,|{\cal I}_{K}|)$ that maximizes the right hand side of (39).
Hence $\mbox{\boldmath$m$}(z)$ is given by (37). ∎

Example 4 (Composite proportion-based reward functions.) We will consider a
class of reward functions that are special cases (32). These reward functions
involve two cost parameters $a$ and $b$:

######  Definition 6.

A block invariant reward function of the form

$R({\cal I},i)=1(i\in{\cal I})-a\max\left(|{\cal
I}_{k(i)}|-1,0\right)-b\left(|{\cal I}|-|{\cal I}_{k(i)}|\right),$ (40)

where $0\leq a\leq b$ are fixed constants, is called a _composite proportion-
based reward function_.

It follows from Propositon 2 that composite proportion-based reward function
have very explicit optimal classifiers:

######  Corollary 3.

A composite proportion-based reward function (40), gives rise to an optimal
classifier that is a composite classifier
$\hat{I}(z)=\hat{I}_{\mbox{\scriptsize\boldmath$m$}(z)}$ in (35) with

$\displaystyle m_{k}(z)$ $\displaystyle=\operatorname*{arg\,max}_{0\leq
m_{k}\leq
N_{k}}\left[v_{k}(m_{k},z)-aP_{k}\max(m_{k}-1,0)-b(1-P_{k})m_{k}\right]$
$\displaystyle=\max\\{m_{k}^{\prime}(z),m_{k}^{\prime\prime}(z)\\},$ (41)

for $k=1,\ldots,K$, where

$\begin{array}[]{rcl}m_{k}^{\prime}(z)&=&1\left(p_{(kN_{k})}\geq(1-P_{k})b\right),\\\
m_{k}^{\prime\prime}(z)&=&\max\\{2\leq m_{k}\leq
N_{k};\,p_{(k,N_{k}+1-m_{k})}\geq P_{k}a+(1-P_{k})b\\},\end{array}$ (42)

and with $\max\emptyset=-\infty$ used in the definition of
$m_{k}^{\prime\prime}(z)$.

###### Proof.

In view of Proposition 2, it suffices to prove that for a composite
proportion-based reward function (40), the optimal classifier is of type
$\hat{I}(z)=\hat{I}_{\mbox{\scriptsize\boldmath$m$}(z)}$, where
$\mbox{\boldmath$m$}(z)=(m_{1}(z),\ldots,n_{K}(z))$ is given by (41). To this
end, we first notice, from the right hand side of (39), that the value
function of a classified set $\hat{I}_{\mbox{\scriptsize\boldmath$m$}}$ is

$\displaystyle V(z;\hat{I}_{\mbox{\scriptsize\boldmath$m$}})$
$\displaystyle=\sum_{k=1}^{K}\left[v_{k}(m_{k};z)-P_{k}\left(a\max\\{m_{k}-1,0\\}+b\sum_{l;l\neq
k}m_{l}\right)\right]$
$\displaystyle=\sum_{k=1}^{K}\left[v_{k}(m_{k};z)-\left(P_{k}a\max\\{m_{k}-1,0\\}+(1-P_{k})bm_{k}\right)\right].$
(43)

Since $V(z;\hat{I}_{\mbox{\scriptsize\boldmath$m$}})$ splits into a sum of $K$
terms that are functions of $m_{1},\ldots,m_{K}$ respectively, it follows that
$V(z;\hat{I}_{\mbox{\scriptsize\boldmath$m$}})$ is maximized, as a function of
$m$, by maximizing each term separately with respect to $m_{k}$. The maximum
for term $k$, on the right hand side of (43), is attained for

$m_{k}(z)=\operatorname*{arg\,max}_{0\leq m_{k}\leq
N_{k}}\left[v_{k}(m_{k};z)-\left(P_{k}a\max\\{m_{k}-1,0\\}+(1-P_{k})bm_{k}\right)\right],$
(44)

in accordance with the first identity of (41). The second identity of (41)
follows from the fact that the function being maximized in (44) is concave in
$m_{k}$. ∎

To give some more intuition to the choice of $a$ and $b$ for the reward
function (40), we will look at the penalty term

$g_{k(i)}({\cal I})=a\max(|{\cal I}_{k(i)}|-1,0)+b(|{\cal I}|-|{\cal
I}_{k(i)}|)$

and the optimal classifier
$\hat{I}(z)=\hat{I}_{\mbox{\scriptsize\boldmath$m$}(z)}$ defined in equations
(41)-(42) of Corollary 3. Note that a cost of $a$ is incurred per extra
category from the correct block in the classified set $\hat{I}$, whereas a
cost of $b$ is added for each category in the classified set originating from
the wrong block. These costs are chosen, and can be interpreted as threshold
values for including categories in the classifier, especially when looking at
(42). From the first row of this equation we notice that a low value on $b$
means that we are more prone to include the most probable category from each
block, whereas the second row implies that with a low value of $a$ we are more
prone to include several categories from the same block. However, since $b$
occurs in the second row of (42) as well, a small $a$ might not have any
effect if $b$ is large. On the other hand, combining a small $b$ with a large
$a$, we get a classifier that is composed of categories from many blocks, but
few categories from each block. Such a classifier might not include the
correct category, but will to a large extent include some category from the
correct block, and might be suitable when we want to safeguard in particular
against erraneous superclassification. Finally, if we want to ensure that
$\hat{I}\neq\emptyset$ in composite classification, we have to choose

$b\leq\max\left(\frac{p_{(1N_{1})}}{1-P_{1}},\ldots,\frac{p_{(KN_{K})}}{1-P_{K}}\right).$
(45)

Let us end Example 4 by considering two special cases of the proportion-based
reward function (40). The first one occurs when $a=b=c$, and it corresponds to
a reward function

$R({\cal I},i)=1(i\in{\cal I})-c\left[|{\cal I}|-1(|{\cal
I}_{k(i)}|>0)\right]$ (46)

that differs slightly from (21) in that all categories in the classified set
${\cal I}$ are penalized by $c$ when none of them belong to the correct block
$k(i)$, that is, when ${\cal I}_{k(i)}=\emptyset$.

The second special case of (40) occurs when it is known that observation $z$
belongs to block $k$, i.e. $P_{k}(z)=1$. The classifier
$\hat{I}_{\mbox{\scriptsize\boldmath$m$}(z)}$ in (35), with
$\mbox{\boldmath$m$}(z)=(m_{1}(z),\ldots,m_{K}(z))$ as in (41), then
simplifies to

$\begin{array}[]{rcl}m_{k}(z)&=&\max\left\\{1,\max\\{2\leq m_{k}\leq
N_{k};\,p_{(k,N_{k}+1-m_{k})}\geq a\\}\right\\},\\\ m_{l}(z)&=&0,\,\,l\neq
k.\end{array}$

This corresponds to an $m$-MP classifier (11), with $m=m(z)$ as in (18) and
(22), when classification is restricted to categories within class $k$, and a
penalty $c=a$ is incurred per extra classified category. $\Box$

Example 5 (Indifference zones.) Assume that we want to know which of $N$
normally distributed populations with unit variances and expected values
$\theta_{1},\ldots,\theta_{N}$ has the largest expected value $\theta_{(N)}$.
Let

$Z=(Z_{ij};\,1\leq i\leq N,1\leq j\leq n_{i})$

be a sample of independent random variables, with $Z_{ij}\sim
N(\theta_{i},1)$. Letting $\phi$ be the density function of a standard normal
distribution, this gives a likelihood

$f(z;\theta)=\prod_{i=1}^{N}\prod_{j=1}^{n_{i}}\phi(z_{ij}-\theta_{i})$

with a parameter vector $\theta=(\theta_{1},\ldots,\theta_{N})$ that is
assumed to have a prior density $P(\theta)$. Divide the parameter space
$\Theta={\mathbb{R}}^{N}$ into a disjoint union

$\Theta=\Theta_{1}\cup\ldots\cup\Theta_{N+1}$ (47)

of $N+1$ regions, where

$\begin{array}[]{rcl}\Theta_{i}&=&\\{\theta;\,\theta_{i}=\theta_{(N)}\geq\theta_{(N-1)}+\epsilon\\},\quad
i=1,\ldots,N,\\\
\Theta_{N+1}&=&\Theta\setminus(\Theta_{1}\cup\ldots\cup\Theta_{N})\end{array}$
(48)

and $\epsilon>0$ is a small number. Whereas $\Theta_{1},\ldots,\Theta_{N}$
correspond to all hypo-theses where some parameter $\theta_{i}$ is largest by
a margin of at least $\epsilon$, $\Theta_{N+1}$ is the indifference zone,
where none of the populations has an expected value that is at least
$\epsilon$ units larger than all the others (Bechhofer, 1954, Goldsman, 1986).

It is possible to put this model into the framework of Section 2, with

$\begin{array}[]{rcl}\pi_{i}&=&\int_{\Theta_{i}}P(\theta)d\theta,\\\
f_{i}(z)&=&\int_{\Theta_{i}}f(z;\theta)P(\theta)d\theta/\int_{\Theta_{i}}P(\theta)d\theta,\end{array}$
(49)

for $i=1,\ldots,N+1$, and an extra category $N+1$ is added that represents the
indifference zone. We will consider reward functions

$R({\cal I},i)=\left\\{\begin{array}[]{ll}1({\cal
I}=\\{i\\}),&i=1,\ldots,N,\\\ r1({\cal
I}=\emptyset),&i=N+1,\end{array}\right.$ (50)

where $r>0$ is the reward of not selecting any population as having the
largest mean, when the parameter vector belongs to the indifference zone.
Formally, this corresponds to a block invariant reward function with the two
blocks

$\begin{array}[]{rcl}{\cal N}_{1}&=&\\{1,\ldots,N\\},\\\ {\cal
N}_{2}&=&\\{N+1\\}\end{array}$ (51)

of categories, although misclassification in this example is more serious
within than between blocks. However, the reward function (50), with blocks as
in (51), does not belong to the class of reward functions in (32). It is
therefore not possible to make use of Propositon 2, but it can still be seen
that the optimal classifier is

$\hat{I}=\left\\{\begin{array}[]{ll}(1N);&p_{(1N)}\geq rp_{N+1},\\\
\emptyset;&p_{(1N)}<rp_{N+1}.\end{array}\right.$

In Section 6 we briefly discuss an extended class of reward functions that
includes (50). $\Box$

##  5 Illustration for an ornithological data set

In this section taxon identification will be used as a case study. In
particular, we will look at four bird species that are morphologically
similar, but share three measurable traits. In Karlsson and Hössjer (2021), we
treat the underlying fitting problem in detail, with covariates,
heteroscedasticity, missing values and imperfect observations, examplified on
data on the same four bird species. Since this paper has a stronger emphasis
on developing a theory of classification, we use a subset of data from
Karlsson and Hössjer (2021) for the purpose of illustration. This data set
includes complete observations only from a certain stratum of the population,
eliminating the need for covariates. To a large extent, our data is the same
as in Malmhagen et al. (2013), where the same classification problem is
treated with mostly descriptive statistics.

###  5.1 The data set

species | $n_{i}$
---|---
Reed warbler | 409
Blyth’s reed warbler | 41
Paddyfield warbler | 18
Marsh warbler | 414
Table 1: The number of observations of each species.

The four species considered are _Reed warbler_ , _Marsh warbler_ , _Blyth’s
reed warbler_ and _Paddyfield warbler_ , and the three shared traits are _wing
length_ , _notch length_ and _notch position_. For details on the measurements
of the traits, see e.g. Svensson (1992); Malmhagen et al. (2013) and Karlsson
and Hössjer (2021). In total we have 882 complete observations of juvenile
birds, with the number $n_{i}$ of birds of each species given in Table 1. This
gives rise to a training data set

${\cal D}_{i}=\\{z_{ij};\,j=1,\ldots,n_{i}\\}$

for each species $i=1,\ldots,4$.

The species were partitioned as follows: _Reed warbler_ and _Marsh Warbler_
constitute the block “common breeders”, _Blyth’s reed warbler_ constitutes the
block “rare breeder” and _Paddyfield warbler_ constitutes the block “rare vag-
rant”. We acknowledge that the grouping is quite arbitrary and that the block
names are inaccurate in most places of the world, but here it will mainly
illustrate classification with a partitioned label space.

###  5.2 Model

We assume that the parameters associated with each category are independent.
If $\theta_{i}\in\Theta_{i}$ is the parameter vector associated with category
$i$, with a prior distribution $P(\theta_{i})$, and if $f({\cal
D}_{i};\theta_{i})$ refers to the likelihood of training data for taxon $i$,
the posterior distribution of $\theta_{i}$ is

$P(\theta_{i}|{\cal D}_{i})=\frac{P(\theta_{i})f({\cal
D}_{i}|\theta_{i})}{P({\cal D}_{i})}.$ (52)

Let $z$ be an observed new data point that we wish to classify, based on
training data. If $f(z;\theta_{i})$ is the likelihood of the test data point
for taxon $i$, we integrate over the posterior distribution (52) in order to
obtain the corresponding likelihood

$f_{i}(z)=\int_{\Theta_{i}}f(z;\theta_{i})P(\theta_{i}|{\cal
D}_{i})d\theta_{i}$ (53)

of $z$ for the hypothesis $H_{i}$ that corresponds to this taxon. Then we
insert (53) into (2) in order to obtain the posterior probabilities $p_{i}(z)$
of all categories. In our example we assume that
$z_{ij}\sim\text{MVN}\left(\mu_{i},\Sigma_{i}\right)$ has a multivariate
normal distribution $f(\cdot;\theta_{i})$, with
$\theta_{i}=(\mu_{i},\Sigma_{i})$. We estimate (53) using Monte Carlo
simulation, i.e. we simulate $L$ realizations of
$\theta_{il}=\left(\mu_{il},\Sigma_{il}\right)$ from $P(\theta_{i}\mid{\cal
D}_{i})$ for each $i$, compute

$\hat{f}_{i}(z)=\frac{1}{L}\sum_{l=1}^{L}f(z;\theta_{il})$ (54)

and then plugg (54) into (2). For a more detailed model setup, see Section 3.1
and Appendix A of Karlsson and Hössjer (2021). All implementation was done in
R (R Core Team, 2021), using the package mvtnorm (Genz et al., 2021).

###  5.3 Classifiers based on composite proportion-based reward functions

We will derive composite classifiers from the composite proportion-based
reward function (40). This reward function involves the two constants $a\geq
0$ and $b>0$, and the corresponding classifier of $z$ is denoted
$\hat{I}_{(a,b)}(z)$. We will regard $0\leq\varepsilon=a/b$ as a fixed
parameter that quantifies how much more severe it is to misclassify a category
outside a block than inside it, with severity inversly proportional to
$\varepsilon$. If $0\leq\varepsilon<1$, it is more severe to misclassify
between blocks than within, whereas the opposite is true when $\varepsilon>1$.
The parameter $b$ will be chosen through leave-one-out cross validation. To
this end, let $\tilde{R}({\cal I},i)$ be a binary-valued reward function (to
be chosen below) without any penalty term, and let

$R_{ab}^{\mbox{\scriptsize
cv}}(\tilde{R})=\sum_{i=1}^{N}\frac{w_{i}}{n_{i}}\sum_{j=1}^{n_{i}}\tilde{R}(\hat{I}_{(a,b)}(z_{ij}),i)$
(55)

refer to the fraction of observations $z_{ij}$ in the training data set ${\cal
D}={\cal D}_{1}\cup\ldots\cup{\cal D}_{N}$ that return a reward in the cross-
validation procedure. That is, $R_{ab}^{\mbox{\scriptsize cv}}(\tilde{R})$
equals the fraction of observations $z_{ij}$ with
$\tilde{R}(\hat{I}_{(a,b)}(z_{ij}),i)=1$, where $\hat{I}_{(a,b)}(z_{ij})$ is
the classifier of $z_{ij}$ based on the rest of the data. It is further
assumed that $w_{i}$ are non-negative weights that sum to $1$, such as
$w_{i}=1/N$ or $w_{i}=n_{i}/\sum_{j=1}^{N}n_{j}$.

The choice of $b$ will depend on which reward function $\tilde{R}$ that is
used in (55). Some possible choices of the binary-valued reward function are
given in Table 2. For two of them ($\tilde{R}_{3}$ and $\tilde{R}_{4}$) the
reward $\tilde{R}({\cal I},i)$ is a non-decreasing function of ${\cal I}$, and
therefore the non-reward rate $1-R_{\varepsilon b,b}^{\mbox{\scriptsize cv}}$,
obtained from the cross validation procedure (55), is a non-decreasing
function of $b$. We will therefore choose $b$ as the largest cost parameter
for which the non-reward rate is at most $\delta>0$, i.e.

$b_{\varepsilon\delta}=\max\\{b\geq 0;\,1-R_{\varepsilon
b,b}^{\mbox{\scriptsize cv}}\leq\delta\\}.$ (56)

In particular, it can be shown that when the reward function $\tilde{R}_{3}$
is used in (56), this generalizes the conformal algorithm (Shafer and Vovk,
2008, Section 4.3) from the case of one block ($K=1$) to several blocks
($K>1$), although we use cross-validation from training data rather than
prediction of a new observations, as in Shafer and Vovk (2008).

For the other two reward functions $\tilde{R}_{1}$ or $\tilde{R}_{2}$ of Table
2, it is no longer the case that estimated non-reward rate $1-R_{\varepsilon
b,b}^{\mbox{\scriptsize cv}}$ in (55) is monotonic in $b$. For these two
choices of $\tilde{R}$ we rather choose the cost parameter

$b_{\varepsilon}=\arg\min_{b\geq 0}(1-R_{\varepsilon b,b}^{\mbox{\scriptsize
cv}})$ (57)

in order to minimize the estimated non-reward rate.

Binary reward function | Reward critera
---|---
$\tilde{R}_{1}({\cal I},i)=1({\cal I}=\\{i\\})$ | Correct (point) classification.
$\tilde{R}_{2}({\cal I},i)=1(i\in{\cal I}\land{\cal I}\subseteq{\cal N}_{k(i)})$ |  Correct category is in the classifier, and no category from an incorrect block is in the classifier. The analogy of $\tilde{R}_{1}$ for block prediction.
$\tilde{R}_{3}({\cal I},i)=1(i\in{\cal I})$ | Correct category in classifier.
$\tilde{R}_{4}({\cal I},i)=1({\cal I}\cap{\cal N}_{k(i)}\neq\emptyset)$ |  Some category from the correct block in the classifier. The analogy of $\tilde{R}_{3}$ for block prediction.
Table 2: The four binary reward functions used in the case study. Since
$\tilde{R}_{1}({\cal I},i)\leq\tilde{R}_{2}({\cal I},i)\leq\tilde{R}_{3}({\cal
I},i)\leq\tilde{R}_{4}({\cal I},i)$, it follows that $\tilde{R}_{1}$ is the
least generous reward function and $\tilde{R}_{4}$ the most generous one. Note
that $R_{\varepsilon b,b}^{\mbox{\scriptsize cv}}(\tilde{R}_{3})$ and
$R_{\varepsilon b,b}^{\mbox{\scriptsize cv}}(\tilde{R}_{4})$ are both
decreasing functions of $b$, so that (56) makes sense for choosing $b$ for any
of these two choices of $\tilde{R}$, whereas (57) is more approriate for
choosing $b$ for the other two reward functions.

We will look at three different prior distributions, namely a uniform prior
($\pi^{(\text{flat})}$), a prior proportional to the number of observations
$n_{i}$ from each category in training data ($\pi^{(\text{prop})}$), and a
prior proportional to the number of registered birds of each species at the
Falsterbo Bird observatory throughout its operational history
($\pi^{(\text{real})}$). The purpose of $\pi^{(\text{flat})}$ is to represent
a situation of no prior knowledge on how likely any of the categories is to
occur. The prior $\pi^{(\text{real})}$ is supposed to examplify a real world
situation of having some commonly occuring species and some very rare ones,
whereas $\pi^{(\text{prop})}$ is a middle ground between these two extremes
that fits the data set ${\cal D}$ very well. As weights we choose

$\displaystyle w^{(\text{bird})}_{i}$
$\displaystyle=n_{i}/\sum_{j=1}^{4}n_{j},$ $\displaystyle
w^{(\text{spec})}_{i}$ $\displaystyle=1/4,$ $\displaystyle
w^{(\text{rare})}_{i}$
$\displaystyle=1/\sum_{j=1}^{4}\pi_{i}^{(\text{real})}/{\pi_{j}^{(\text{real})}},$
(58)

for $i=1,2,3,4$. We weight each observation equally with $w^{(\text{bird})}$,
each species equally with $w^{(\text{spec})}$, whereas the species are
weighted higher the less expected they are with $w^{(\text{rare})}$. Since the
number of observations are not balanced across species, $w^{(\text{bird})}$
will weight species higher the more common they are, i.e. the more
observations we have of them. Using $w^{(\text{spec})}$, birds will be
weighted unequally due to the same imbalance (the less birds of a given
species there are, the higher weights are assigned to these birds). Finally,
as mentioned above, $w^{(\text{rare})}$ weights less frequently observed
species more heavyly; the rationale being that we value observations of rarely
occuring species, as data on these are scarce.

###  5.4 Results

We will analyze the estimated reward rate (55) for the four choices of
$\tilde{R}$ that are listed in Table 2. In Tables 3 and 4 we present the
automatic choice of the cost parameter $b$ (cf. (56) and (57)) for two ratios
$\varepsilon=1/2$ and $\varepsilon=2$ of $a$ and $b$, and for all nine
combinations priors and weights. As can be seen from Table 4, the same optimal
$b$-values are found for $\tilde{R}_{1}$ and $\tilde{R}_{2}$, with the same
non-reward rates. This is mostly due to the small block sizes, meaning that it
sometimes is equivalent to pick the correct species, as to pick the correct
block.

In Figures 1(c) and 2(c) we plot the value of estimated non-reward rate
$1-R_{\varepsilon b,b}^{\mbox{\scriptsize cv}}$ for a grid of $b$-values, for
$\varepsilon=1/2$ and $\varepsilon=2$ respectively. Note the monotone decrease
of $\tilde{R}_{3}$ and $\tilde{R}_{4}$ as $b$ decreases. Also notice the
minimums of $\tilde{R}_{1}$ and $\tilde{R}_{2}$ in the graphs.

Finally we refer to Appendix A for further visualisations of $\tilde{R}_{1}$
and $\tilde{R}_{2}$, evaluated over a lattice of $a$ and $b$-values. It can
seen that for $\tilde{R}_{2}$ the optimal non-reward rate is achived by
choosing $a=0$. This is straightforward to explain, as $\tilde{R}_{2}$ does
not punish the inclusion of several categories from the correct block. For
this reason the classifier $\hat{I}_{(a,b)}$ with minimal non-reward rate
includes as many categories as possible from each block with at least one
classified member, corresponding to $a=0$. Notice also that there are large
regions of values of $a$ and $b$ that attain the minimum non-reward rate.

$\varepsilon$ | Prior | $\tilde{R}$ | $b_{\varepsilon,0.05}$
---|---|---|---
$w^{(\text{bird})}$ | $w^{(\text{spec})}$ | $w^{(\text{rare})}$
$1/2$ | $\pi^{(\text{flat})}$ | $\tilde{R}_{3}$ | $\geq 20.00$ | 2.29 | 2.11
$\tilde{R}_{4}$ | $\geq 20.00$ | 3.05 | 2.11
$\pi^{(\text{prop})}$ | $\tilde{R}_{3}$ | $\geq 20.00$ | 5.23 | 4.81
$\tilde{R}_{4}$ | $\geq 20.00$ | 6.96 | 4.81
$\pi^{(\text{real})}$ | $\tilde{R}_{3}$ | 1.07 | 0.43 | 0.18
$\tilde{R}_{4}$ | $\geq 20.00$ | 0.52 | 0.18
$2$ | $\pi^{(\text{flat})}$ | $\tilde{R}_{3}$ | $\geq 20.00$ | 2.29 | 2.11
$\tilde{R}_{4}$ | $\geq 20.00$ | 3.05 | 2.11
$\pi^{(\text{prop})}$ | $\tilde{R}_{3}$ | $\geq 20.00$ | 5.23 | 4.81
$\tilde{R}_{4}$ | $\geq 20.00$ | 6.96 | 4.81
$\pi^{(\text{real})}$ | $\tilde{R}_{3}$ | 1.07 | 0.21 | 0.18
$\tilde{R}_{4}$ | $\geq 20.00$ | 0.52 | 0.18
Table 3: The table specifies the estimated values of the cost parameter $b$, using (56) with $\delta=0.05$. These estimates of $b$ are computed for each combination of $\varepsilon$, prior $\pi_{i}$, and weights $w_{i}$. We evaluated (55) for $0.01\leq b\leq 20$ with a resolution of 0.01. $\varepsilon$ | Prior | $\tilde{R}$ | $w^{(\text{bird})}$ | $w^{(\text{spec})}$ | $w^{(\text{rare})}$
---|---|---|---|---|---
$b_{\varepsilon}$ |  non-reward rate | $b_{\varepsilon}$ |  non-reward rate | $b_{\varepsilon}$ |  non-reward rate
$1/2$ | $\pi^{(\text{flat})}$ | $\tilde{R}_{1}$ | 1.24 | 1.59% | 17.16 | 9.12% | 1.16 | 4.06 %
$\tilde{R}_{2}$ | 1.24 | 1.59% | 17.16 | 9.12% | 1.16 | 4.06%
$\pi^{(\text{prop})}$ | $\tilde{R}_{1}$ | 2.63 | 1.59% | 2.24 | 4.06% | 2.63 | 4.06%
$\tilde{R}_{2}$ | 2.63 | 1.59% | 2.24 | 4.06% | 2.63 | 4.06%
$\pi^{(\text{real})}$ | $\tilde{R}_{1}$ | 10.28 | 6.69% | 10.28 | 19.41% | 10.28 | 49.62%
$\tilde{R}_{2}$ | 10.28 | 6.69% | 10.28 | 19.41% | 10.28 | 49.62%
$2$ | $\pi^{(\text{flat})}$ | $\tilde{R}_{1}$ | 1.24 | 1.59% | 17.16 | 9.12% | 1.16 | 4.06%
$\tilde{R}_{2}$ | 1.24 | 1.59% | 17.16 | 9.12% | 1.16 | 4.06%
$\pi^{(\text{prop})}$ | $\tilde{R}_{1}$ | 2.63 | 1.59% | 2.24 | 4.06% | 2.63 | 4.06%
$\tilde{R}_{2}$ | 2.63 | 1.59% | 2.24 | 4.06% | 2.63 | 4.06%
$\pi^{(\text{real})}$ | $\tilde{R}_{1}$ | 10.28 | 6.69% | 10.28 | 19.41% | 10.28 | 49.62%
$\tilde{R}_{2}$ | 10.28 | 6.69% | 10.28 | 19.41% | 10.28 | 49.62%
Table 4: The table specifies the estimated values of the cost parameter $b$,
using (57). These estimates of $b$ are computed for each combination of
$\varepsilon$, prior $\pi_{i}$, and weights $w_{i}$. They were found using the
optimise-function in R. Figure 1: This figure represents the case
$\varepsilon=1/2$. The prior is specified in the title of each graph, whereas
the weights are explained in the subcaptions. Each color of the functions in
the graphs correspond to one of the four reward functions
$\tilde{R}_{1},\tilde{R}_{2},\tilde{R}_{3},\tilde{R}_{4}$, given by the
legends above each subfigure. For all priors and weights we observe that
$\tilde{R}_{3}$ and $\tilde{R}_{4}$ decrease monotonically as $b$ decreases,
whereas $\tilde{R}_{1}$ and $\tilde{R}_{2}$ have a global minimum.

(a) Using $w^{(\text{bird})}$ we observe similar curves for
$\pi^{(\text{flat})}$ and $\pi^{(\text{prop})}$, whereas $\pi^{(\text{real})}$
gives overall higher non-reward rates.

(b) Using $w^{(\text{spec})}$, the curves for $\tilde{R}_{1}$ and
$\tilde{R}_{2}$ look similar for $\pi^{(\text{flat})}$ and
$\pi^{(\text{prop})}$, wheras the large drop in $\tilde{R}_{3}$ and
$\tilde{R}_{4}$ occurs either for large values of $b$ ($\pi^{(\text{flat})}$)
or for small values of $b$ ($\pi^{(\text{prop})}$). Again, the non-reward
rates are overall higher using $\pi^{(\text{real})}$.

(c) The scale along the vertical axis (for the non-reward rate) is different
in these subplots compared to (a) and (b). Using $w^{(\text{rare})}$, with a
very uneven weighting of species, the curves for $\tilde{R}_{1}$ and
$\tilde{R}_{2}$, as well as for $\tilde{R}_{3}$ and $\tilde{R}_{4}$, take
values very close to each other. Thus it seems like these curves overlap, when
in reality they do not. This is just a consequence of the extreme amount of
up-weighting of rare species, which are both in singelton blocks.

Figure 2: This figure represents the case $\varepsilon=2$. The prior is
specified in the title of each graph, whereas the weights are explained in the
subcaptions. Each color of the functions in the graphs correspond to one of
the four reward functions
$\tilde{R}_{1},\tilde{R}_{2},\tilde{R}_{3},\tilde{R}_{4}$, given by the
legends above each subfigure. For all priors and weights we observe that
$\tilde{R}_{3}$ and $\tilde{R}_{4}$ decrease monotonically as $b$ decreases,
whereas $\tilde{R}_{1}$ and $\tilde{R}_{2}$ have a global minimum.

(a) Using $w^{(\text{bird})}$ we observe similar curves for
$\pi^{(\text{flat})}$ and $\pi^{(\text{prop})}$, whereas $\pi^{(\text{real})}$
gives overall higher non-reward rates.

(b) Using $w^{(\text{spec})}$, the curves for $\tilde{R}_{1}$ and
$\tilde{R}_{2}$ look similar for $\pi^{(\text{flat})}$ and
$\pi^{(\text{prop})}$, wheras the large drop in $\tilde{R}_{3}$ and
$\tilde{R}_{4}$ occurs either for large values of $b$ ($\pi^{(\text{flat})}$)
or for small values of $b$ ($\pi^{(\text{prop})}$). Again, the non-reward
rates are overall higher using $\pi^{(\text{real})}$.

(c) The scale along the vertical axis (for the non-reward rate) is different
in these subplots compared to (a) and (b). Using $w^{(\text{rare})}$, with a
very uneven weighting of species, the curves for $\tilde{R}_{1}$ and
$\tilde{R}_{2}$, as well as for $\tilde{R}_{3}$ and $\tilde{R}_{4}$, take
values very close to each other. Thus it seems like these curves overlap, when
in reality they do not. This is just a consequence of the extreme amount of
up-weighting of rare species, which are both in singelton blocks.

##  6 Discussion

In this article we introduce a general framework of set-valued classification
of data that originates from one of a finite number of possible hypotheses. We
introduce reward functions with a set-valued input argument, and derive the
optimal (Bayes) classifier by maximizing the expected reward. Explicit
formulas for the Bayes classifier are derived for a large class of reward
functions. This includes scenarios where hypotheses either consitute one
homogeneous block, or consist of several blocks of hypotheses, such that
ambiguity within blocks is (typically) less serious than ambiguity between
them. Our procedure is illustrated with an ornithological data set, where taxa
(hypotheses) are divided into blocks.

As mentioned in Ripley (2007), a possible reason for including reject options
is to obtain classifiers that are more reliable but also less expensive to
use. In our case study of Section 5, for instance, a possible option is to
consult an expert who would be able to identify the bird species
morphologically, without using the measured traits. Although expertise does
not come cheap, this could still be an alternative when the expected cost of
algorithmic classification exceeds the cost of consulting an expert. The
latter cost might be independent or a function of the number of hypotheses she
needs to consider. In the former case, the reject option of Ripley (2007)
would suffice, and in the latter case a partial rejection, as proposed in this
paper, could be beneficial.

A number of generalizations of our work is possible. Firstly, suppose the new
observation $z$ that we want to classify, by means of the optimal classifier
$\hat{I}=\hat{I}(z)$ in (8), involves a covariate vector $x$ and a reponse
variable $Y$. Following Karlsson and Hössjer (2021), the most straightforward
approach is to include covariates into the observation $z=(x,Y)$ that is to be
classified. The covariate information will then be included in the category
distributions $f_{i}$ and posterior probabilities $p_{i}$ of all categories
$i=1,\ldots,N$, as well as in the resulting $m$-MP and composite classifiers.
However, if we also want the ambiguity of the classifier to depend on
covariate information, it is possible to let the cost parameters of the reward
function $R$ depend on $x$ as well. For instance, the conformal prediction
algorithm of Example 3 involves choosing the cost
$c(\delta)=F^{-1}(\delta)=Q(\delta)$ of including more lables in the
classifier, as a quantile $Q(\delta)$ of the distribution $F$ of posterior
probabilities (cf. (30)). In this context it is possible to use quantile
regression (Koenker, 2005; Bottai et al., 2010) and choose the cost parameter
$c(\delta;x)=Q(\delta|x)=g^{-1}[x^{\top}\beta(\delta)]$ as a conditional
quantile function. This is a regression model where the parameter vector
$\beta(\delta)$ is a function of the quantile $\delta$, whereas $g$ is a link
function. This approach might be particularly helpful for models with
heteroscedasticity.

Secondly, it is possible to consider reward functions with other penalty
terms. Instead of penalizing the number of classified categories within the
correct and wrong blocks respectively, as in (32), one penalizes the number of
wrongly classified categories within the correct and wrong blocks. This
corresponds to a reward function

$R({\cal I},i)=1(i\in{\cal I})-g_{k(i)}(|{\cal I}_{k(i),(-i)}|,|{\cal
I}|-|{\cal I}_{k(i)}|,|{\cal I}|),$ (59)

where ${\cal I}_{k(i),(-i)}={\cal I}_{k(i)}\setminus\\{i\\}$ is the number of
wrong categories of ${\cal I}$ that belong to block $k(i)$ when category $i$
is true. For instance, the reward function (50) for indifference zones
(Example 5) can be formulated in accordance with (59). In order to see this
let $m_{1}$ and $m_{2}$ refer to the number of wrongly classified categories
of blocks 1 and 2, whereas $m$ is the size of the classified set (hence
$m-(m_{1}+m_{2})$ equals 1 or 0 depending on whether $i\in{\cal I}$ or not).
Then (50) corresponds to having penalty terms

$\begin{array}[]{rcl}g_{1}(m_{1},m_{2},m)&=&1(m=m_{1}+m_{2}+1\mbox{ and
}(m_{1},m_{2})\neq(0,0)),\\\ g_{2}(0,m_{1},m)&=&1(m=m_{1}+1)-r1(m=m_{1}\mbox{
and }m_{2}=0),\end{array}$

when the true category belongs to block 1 and 2 respectively.

Thirdly, suppose an observation $z$ belongs to several categories ${\cal
J}\subset{\cal N}$, such as when ${\cal J}$ represents the properties
associated with $z$. It is natural in this context to have a reward $R({\cal
I},{\cal J})$ for a classified set ${\cal I}\subset{\cal N}$ of categories.
The MAP classifier (7), for instance, corresponds a reward function $R({\cal
I},{\cal J})=1({\cal I}={\cal J})$. If we allow for some misclassified
categories and all categories belong to one homogeneous block, a natural
extension of (10) is a function $R({\cal I},{\cal J})=1({\cal J}\subset{\cal
I})-g(|{\cal I}|)$ where the first term gives a unit reward if all true
categories are included in the classifier, whereas the second term $g(|{\cal
I}|)$ penalizes the size $|{\cal I}|$ of the classified set.

## Acknowledgements

The authors would like to thank Vilhelm Niklasson at Stockholm University for
suggesting the topic of conformal prediction, and the Falsterbo Bird
Observatory for providing the data set.

##  Appendix A Optimising $\tilde{R}_{1}$ and $\tilde{R}_{2}$

In Figure 3 the non-reward rate $1-R_{ab}^{\mbox{\scriptsize cv}}(\tilde{R})$
(cf. (55)) is plotted as a function of the two cost parameters $a$ and $b$ of
the classifier $\hat{I}_{(a,b)}$ for the two reward functions $\tilde{R}_{1}$
and $\tilde{R}_{2}$ of Table 2. The objective function is not smooth and thus
it can be hard to optimize. However, we obtained good results with Nelder-Mead
optimization (Nelder and Mead, 1965), as implemented in the optim-function in
R, with a starting value of $(a,b)$ that corresponds to a small non-reward
rate.

Figure 3: The figure contains filled contour plots of the estimated non-reward
rate $1-R_{ab}^{\mbox{\scriptsize cv}}(\tilde{R})$ (cf. (55)), as a function
of the two cost parameters $a$ and $b$ of the classifier $\hat{I}_{(a,b)}$.
These estimated non-reward rates make use of weights
$w_{i}^{(\mbox{\scriptsize bird})}$ (cf. (58)), the reward function
$\tilde{R}_{1}$ (top row) and $\tilde{R}_{2}$ (bottom row). The columns, from
left to right, correspond to the priors $\pi^{(\text{flat})}$ ,
$\pi^{(\text{prop})}$ and $\pi^{(\text{real})}$ (cf. Section 5.3). The levels
of the contour plots are crudely drawn, but it can still seen that
$\tilde{R}_{1}$ attains a low value for a large set of $(a,b)$, whereas
$\tilde{R}_{2}$ attains its lowest values over a small region where $a$ is
close to 0.

## References

  * Arrow et al. (1949) Arrow, K. J., D. Blackwell, and M. A. Girshick (1949).  Bayes and minimax solutions of sequential decision problems.  Econometrica, Journal of the Econometric Society, 213–244.
  * Bechhofer (1954) Bechhofer, R. E. (1954).  A single-sample multiple decision procedure for ranking means of normal populations with known variances.  The Annals of Mathematical Statistics, 16–39.
  * Berger (2013) Berger, J. O. (2013).  Statistical decision theory and Bayesian analysis.  Springer Science & Business Media.
  * Bishop (2006) Bishop, C. M. (2006).  Pattern Recognition and Machine Learning.  Springer.
  * Bottai et al. (2010) Bottai, M., B. Cai, and R. E. McKeown (2010).  Logistic quantile regression for bounded outcomes.  Statistical Medicine (29), 309–317.
  * Carlin et al. (1998) Carlin, B. P., J. B. Kadane, and A. E. Gelfand (1998).  Approaches for optimal sequential decision analysis in clinical trials.  Biometrics, 964–975.
  * Chow (1970) Chow, C. (1970).  On optimum recognition error and reject tradeoff.  IEEE Transactions on information theory 16(1), 41–46.
  * Freund et al. (2004) Freund, Y., Y. Mansour, and R. E. Schapire (2004).  Generalization bounds for averaged classifiers.  The annals of statistics 32(4), 1698–1722.
  * Genz et al. (2021) Genz, A., F. Bretz, T. Miwa, X. Mi, F. Leisch, F. Scheipl, and T. Hothorn (2021).  mvtnorm: Multivariate Normal and t Distributions.  R package version 1.1-2.
  * Goldsman (1986) Goldsman, D. (1986).  Tutorial on indifference-zone normal means ranking and selection procedures.  In Proceedings of the 18th conference on Winter simulation, pp. 370–375.
  * Hastie et al. (2009) Hastie, T., R. Tibshirani, J. Friedman, et al. (2009).  The elements of statistical learning (Second ed.).  Number 10. Springer series in statistics New York.
  * Herbei and Wegkamp (2006) Herbei, R. and M. H. Wegkamp (2006).  Classification with reject option.  The Canadian Journal of Statistics/La Revue Canadienne de Statistique, 709–721.
  * Karlsson and Hössjer (2021) Karlsson, M. and O. Hössjer (2021).  Identification of taxon through classification with partial reject options.
  * Koenker (2005) Koenker (2005).  Quantile Regression (Econometric Society monographs; no. 38).  Cambridge university press.
  * Malmhagen et al. (2013) Malmhagen, B., M. Karlsson, and S. Menzie (2013).  Using wing morphology to separate four species of Acrocephalus warblers in Scandinavia.  Ringing & Migration 28(July), 63–68.
  * Nelder and Mead (1965) Nelder, J. A. and R. Mead (1965).  A simplex method for function minimization.  The computer journal 7(4), 308–313.
  * R Core Team (2021) R Core Team (2021).  R: A Language and Environment for Statistical Computing.  Vienna, Austria: R Foundation for Statistical Computing.
  * Ripley (2007) Ripley, B. D. (2007).  Pattern recognition and neural networks.  Cambridge university press.
  * Shafer and Vovk (2008) Shafer, G. and V. Vovk (2008).  A tutorial on conformal prediction.  Journal of Machine Learning Research 9(3).
  * Svensson (1992) Svensson, L. (1992).  Identification guide to European passerines.  L. Svensson.
  * Vovk et al. (2005) Vovk, V., A. Gammerman, and G. Shafer (2005).  Algorithmic learning in a random world.  Springer Science & Business Media.