# Improving Classification Performance With Human Feedback:
Label a few, we label the rest

Eden Chung, Liang Zhang, Katherine Jijo, Thomas Clifford, Natan Vidra

###### Abstract

In the realm of artificial intelligence, where a vast majority of data is
unstructured, obtaining substantial amounts of labeled data to train
supervised machine learning models poses a significant challenge. To address
this, we delve into few-shot and active learning, where are goal is to improve
AI models with human feedback on a few labeled examples. This paper focuses on
understanding how a continuous feedback loop can refine models, thereby
enhancing their accuracy, recall, and precision through incremental human
input. By employing Large Language Models (LLMs) such as GPT-3.5, BERT, and
SetFit, we aim to analyze the efficacy of using a limited number of labeled
examples to substantially improve model accuracy. We benchmark this approach
on the Financial Phrasebank, Banking, Craigslist, Trec, Amazon Reviews
datasets to prove that with just a few labeled examples, we are able to
surpass the accuracy of zero shot large language models to provide enhanced
text classification performance. We demonstrate that rather than needing to
manually label millions of rows of data, we just need to label a few and the
model can effectively predict the rest.

##  1 Introduction

In the world of AI, a significant challenge is handling massive amounts of
data. Only 15 percent of this data is structured, while the rest, a surprising
85 percent, is unstructured. For AI/ML models to work effectively, they
usually need large sets of data that are labeled, but getting such data is
challenging.

Traditional AI methods rely heavily on millions of rows to train models. This
means pairing inputs (like pictures or text) with the correct labels. The big
question is: How can we gather this massive amount of labeled data
efficiently? Right now, businesses have to choose between leaving their data
unlabeled (which is risky) or manually (AI Assisted) labeling it. While AI
tools like Labelbox, Heartex, Datasaur and Prodigy can help with labeling,
they aren’t perfect. Training data often necessitates the expertise of
subject-matter professionals, such as doctors, legal analysts, and financial
analysts, for labeling. This manual data labeling is tedious, time-consuming,
and costly, but particularly, when business requirements change, requiring
manual labeling over and over again is not sustainable. Furthermore, manual
labeling does not even ensure the correctness of the data; in fact, it can
oftentimes be incorrect, which is one of the limitations of relying solely on
manual labeling. Even state-of-the-art data sets, such as MNIST and ImageNet
can have incorrectly labeled data 111Curtis Northcutt and Anish Athalye and
Jonas Mueller. Label Errors in ML Test Sets. https://labelerrors.com, Accessed
on 2023-12-23.. On the other hand, AI models such as GPT3 and Claude, although
surely very helpful, can still hallucinate and return false data. Therefore,
an approach that integrates human expertise with AI can accelerate labeling
processes while ensuring accuracy, as well as minimizing errors, especially
for diverse data types from different industries.

One such approach that combines human power with AI is programmatic labeling
222Programmatic labeling. https://snorkel.ai/programmatic-labeling/, Accessed
on 2023-12-23. . Instead of manually labeling each data point one by one, in
programmatic labeling, the user inputs labeling functions, capturing the
reasoning behind the labeling, which can then be generalized to larger amounts
of unlabeled data through AI. This has been a great step forward, allowing for
scalability and adaptability. However, there are several limitations to
programmatic labeling. Since creating labels is generalizing data, the model
may struggle with ambiguous cases or nuanced cases, and labeling functions may
not be able to capture these subtle patterns that a human might be able to. In
addition, as mentioned before, humans can make errors in labeling, and if
these errors occur in the labeling functions, these errors will propagate
throughout the dataset, instead of being limited to just one incorrect data
point. Finally, as manual labeling is, programmatic labeling is still
relatively resource-intensive.

Novel NLP research in Large Language Models and few shot learning has changed
the way that data labeling is done. GPT-3, introduced in “Language Models Are
Few Shot Learners” 333Tom B. Brown and Benjamin Mann and Nick Ryder and
Melanie Subbiah, et al. Language Models are Few-Shot Learners, 2020.
arXiv:2005.14165., 2020, demonstrated the abilities for LLMs to learn with
minimal data. LaMDA 444Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam
Shazeer, Apoorv Kulshreshtha, et al. LaMDA: Language Models for Dialog
Applications, 2022. arXiv:2201.08239. and PaLM 555Aakanksha Chowdhery, Sharan
Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra et al. PaLM: Scaling
Language Modeling with Pathways, 2022. arXiv:2204.02311. , significantly
contributed to the enhancement of language models. In 2021, “Want To Reduce
Labeling Cost? GPT-3 Can Help” was published 666Shuohang Wang and Yang Liu and
Yichong Xu and Chenguang Zhu and Michael Zeng. Want To Reduce Labeling Cost?
GPT-3 Can Help, 2021. arXiv:2108.13487. The paper highlighted that employing
labels produced by GPT-3 is notably more economical, both in terms of
computational resources and potentially time, compared to acquiring labels
from human experts. Furthermore, even with these cost benefits, models trained
using GPT-3.5-generated labels demonstrated comparable performance to those
trained on human-provided labels.

From this research, combining AI and human power called “few-shot learning”
became the practical. Instead of labeling millions of data points, we can work
with just a few thousand. This approach lets AI learn from a small amount of
labeled data and then make educated guesses for the rest. Large language
models such as GLaM 777Nan Du, Yanping Huang, Andrew M. Dai, Simon Tong, et
al. GLaM: Efficient Scaling of Language Models with Mixture-of-Experts, 2022.
arXiv:2112.06905., Flamingo 888Jean-Baptiste Alayrac, Jeff Donahue, Pauline
Luc, Antoine Miech, et al. Flamingo: a Visual Language Model for Few-Shot
Learning, 2022. arXiv:2204.14198., and the “Alexa Teacher Model” 999Jack
FitzGerald, Shankar Ananthakrishnan, Konstantine Arkoudas, Davide Bernardi, et
al. Alexa Teacher Model: Pretraining and Distilling Multi-Billion-Parameter
Encoders for Natural Language Understanding Systems. In Proceedings of the
28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’22),
August 2022. http://dx.doi.org/10.1145/3534678.3539173, DOI:
10.1145/3534678.3539173., all demonstrate the expanding capabilities of AI
models in learning efficiently from limited data. These models have set new
benchmarks in the field, showcasing the power of few-shot learning in diverse
applications, from language understanding to visual recognition and beyond.

In 2022, Hugging Face announced SetFit, an efficient framework for few-shot
fine-tuning of Sentence Transformers, which allows high accuracy with little
labeled data 101010Lewis Tunstall and Nils Reimers and Unso Eun Seo Jo and
Luke Bates and Daniel Korat and Moshe Wasserblat and Oren Pereg. Efficient
Few-Shot Learning Without Prompts, 2022. arXiv:2209.11055.. Few-shot learning
is a technique that allows a model to utilize just a minimal number of
examples to guide the model. By incorporating feedback from industry experts
and integrating few-shot learning techniques, we can significantly improve the
overall accuracy of the model with a small amount of labeled data provided by
the industry expert. By combining state-of-the-art transformers with few-shot
learning techniques, the system learns in real time, assisting data annotators
with the labeling process.

##  2 Background

LLM’s have evolved vastly over time, with this mainly being due to the
architecture behind the models. Several main architectural methods have been
used; we will discuss Recurrent Neural Networks (RNN) and Transformers.

###  2.1 Recurrent Neural Networks (RNN)

Recurrent Neural Networks (RNN), the earlier architecture behind LLMs, was a
concept thought up of in 1986, but the architecture for the model was finally
built only in 1997. RNN has evolved over time to 3 distinct phases: Overloaded
Single Memory (Vanilla RNN), Multiple Gate Memories (LSTM), and Encoder-
Decoder architecture 111111Chen Yanhui. A Battle Against Amnesia: A Brief
History and Introduction of Recurrent Neural Networks.
https://towardsdatascience.com/a-battle-against-amnesia-a-brief-history-and-
introduction-of-recurrent-neural-networks-50496aae6740, Accessed on
2023-12-17..

###  2.2 Transformers

With technology constantly changing and deep learning models improving over
time, RNN began to be replaced with a new architectural model – transformers.
First introduced in 2016, they have since revolutionized the field of LLMs and
NLP. Beginning with BERT in 2018, models have continued to evolve with GPT in
2020 and LaMDA in 2021 121212Ashish Vaswani and Noam Shazeer and Niki Parmar
and Jakob Uszkoreit and Llion Jones and Aidan N. Gomez and Lukasz Kaiser and
Illia Polosukhin. Attention Is All You Need, 2023. arXiv:1706.03762., proving
that LLMs keep getting better and better, and it is clear that these models
will only get more impressive with time.

Transformers are now the core architecture behind many NLP models such as Chat
GPT and Bard. Instead of having to consider words sequentially, as RNN models
do, they can instead analyze words simultaneously. As a result, transformers
are very good at adapting, so many LLMs exist today with many different use
cases.

Figure 1: Transformer architecture 131313Liz McQuillan. Deep Learning 101:
What Is a Transformer and Why Should I Care?
https://www.saltdatalabs.com/blog/deep-learning-101/what-is-a-transformer-and-
why-should-i-care, Accessed on 2023-12-17

##  3 Process and Work

In order to attempt to improve the accuracy of ML models, a human feedback
approach is introduced, enhancing text classification accuracy. Similar to
providing students with clear examples for better understanding, the strategy
involves fine-tuning models through human feedback or providing more labeled
examples.

In order to evaluate whether or not few-shot learning is really effective or
not, in this study, a continual test and evaluation loop is used. The process
consists of continually testing a datasets accuracy, precision, and recall but
varying the number of labeled data points inputted. Starting with 10 data
labeled data points given, after each iteration, human feedback is applied. 10
incorrect answers are chosen and then fed into the model, giving it the
correct answer instead, and this cycle repeats. So, on each iteration, the
number of labeled data points increases by 10.

###  3.1 Data Sets

In our machine learning research, we utilized six distinct datasets for
various analyses. The Amazon reviews dataset consisted of a training set with
6,001 rows and a testing set of 2,001 rows, encompassing labels such as
Excellent’, Very Good’, Neutral’, Good’, and Bad’. The banking dataset, on the
other hand, had a training data of 200 rows and a testing set of 2,000 rows,
with 77 distinct labels like cash received’, fiat currency support’, and pin
blocked’. The Craigslist dataset was structured with 201 rows in its training
set and 1,001 rows in its testing set, covering categories like phone,
furniture, housing, electronics, and car, with labels categorized into ABBR,
ENTY, DESC, HUM, LOC, and NUM. The financial phrasebank dataset had 4,850 rows
of data with categories positive, negative and neutral. Lastly, the Trec
dataset offered both a coarse label set of 6 labels and a fine label set of 50
detailed labels such as expression abbreviated, animals, organ of body, color,
invention, book, and other creative pieces. This Trec is consistent with 5,452
rows in training and 500 rows in testing.

Figure 2: Sample of the Trec Data Set Figure 3: Sample of the Finance
Phrasebank Set

##  4 Approach

In text classification, key metrics play a pivotal role. The probability
metric indicates the confidence level of a model’s predictions, while the
entropy metric measures the significance or unpredictability of a prediction
within the dataset. Higher entropy suggests that the predicted label has an
impact on the overall classification or decision-making process. To initiate
our process, we utilize zero-shot models like Claude, GPT, BERT, and SETFIT to
derive initial predictions from the provided data. For clarity on our
predictions for a spam versus non-spam dataset, before doing anything we have
to examine the zero-shot model predictions.

Table 1: Zero shot model predictions Text Body | Predicted | Probability | Entropy
---|---|---|---
Important notice: Your package has been delivered. | not spam | 0.65 | 0.88
Dear customer, Your account balance is low. | not spam | 0.58 | 0.82
Hi, How are you doing? Let’s catch up soon. | not spam | 0.58 | 0.75
Urgent notice: Last chance to update your personal information. | spam | 0.92 | 0.51
Hi there, You have won a free vacation! Claim now! | spam | 0.95 | 0.42
Congratulations! You’ve won a million dollars! | spam | 0.97 | 0.36

The first step in active learning from human feedback is to generate a
prioritized list of edge cases. These edge cases highlight instances where the
model’s predictions demonstrate uncertainty or reduced confidence. Once this
list is established, human evaluators can review and assign the appropriate
labels. In Table 2, we can see that the actual label is not spam. By iterating
through this process, the model is once again organized based on entropy and
probability values. Upon this second evaluation, you’ll notice a decrease in
entropy and an increase in probability scores, highlighting the model’s
enhanced confidence and refined predictions.

Table 2: Spam Classification Results Text | Actual Label | Predicted | Probability | Entropy
---|---|---|---|---
Important notice: Your package has been delivered. | not spam | not spam | 1.0 | 0
Urgent notice: Last chance to update your personal information. |  | not spam | 0.88 | 0.28
Dear customer, Your account balance is low. |  | spam | 0.70 | 0.76
Hi, How are you doing? Let’s catch up soon. |  | not spam | 0.65 | 0.68
Congratulations! You’ve won a million dollars! |  | spam | 0.92 | 0.22
Hi there, You have won a free vacation! Claim now! |  | spam | 0.80 | 0.25

We iterate on this process again. The model once again is sorted by entropy,
we provide the row / edge case with the highest potential for impact.

Table 3: Iterated Model Predictions - First Iteration Text | Actual Label | Predicted | Probability | Entropy
---|---|---|---|---
Important notice: Your package has been delivered. | not spam | not spam | 1.0 | 0
Dear customer, Your account balance is low. |  | spam | 0.70 | 0.76
Hi, How are you doing? Let’s catch up soon. |  | not spam | 0.65 | 0.68
Urgent notice: Last chance to update your personal information. |  | not spam | 0.88 | 0.28
Hi there, You have won a free vacation! Claim now! |  | spam | 0.80 | 0.25
Congratulations! You’ve won a million dollars! |  | spam | 0.92 | 0.22

Here, we see the sentence Dear customer, Your account balance is low. which
has the highest entropy of the non-labeled data points. We label this row as
spam, largely due to the fact that the sentence is referring to account
balance. Notice how this row of text data, with the corresponding label, is
added to the annotation history once we confirm the annotation. After this
second label, the models predictions, uncertainty and entropy is adjusted once
more.

Table 4: Iterated Model Predictions - Second Iteration Text | Actual Label | Predicted | Probability | Entropy
---|---|---|---|---
Important notice: Your package has been delivered. | not spam | not spam | 1.0 | 0
Dear customer, Your account balance is low. | spam | spam | 1.0 | 0
Hi, How are you doing? Let’s catch up soon. |  | not spam | 0.80 | 0.62
Urgent notice: Last chance to update your personal information. |  | spam | 0.86 | 0.18
Hi there, You have won a free vacation! Claim now! |  | spam | 0.75 | 0.20
Congratulations! You’ve won a million dollars! |  | spam | 0.88 | 0.18

Notice how over time, the entropy is decreasing as the model is becoming more
stable as more human labels are added. After a few labels, the entropy is able
to stabilize, and no more labels are needed (the labels impact the accuracy
less than is worth the effort).

##  5 Evaluating Method

We primarily employed the BERT, SEFIT, and GPT-3.5 Turbo models for our
evaluation. Initially, we tasked these models with predicting outcomes on the
testing set. This approach helped us identify areas where the models exhibited
weakness or lower confidence. For any incorrect predictions made by the
models, we adjusted the labels for 10 rows to reflect the correct
classifications. We then fine-tuned the models based on this corrected data,
simulating human feedback, and measured accuracy, precision, and recall on the
testing set after feedback. Subsequently, we incorporated these 10 rows into
the training set and excluded them from the testing set. We repeated this
process iteratively while measuring their accuracy, precision, and recall. We
continued this iterative approach up to 150 labels.

##  6 Results

After fine-tuning the models with human feedback and additional labeled
examples, we observed a consistent improvement in accuracy across different
datasets. Notably, our experiments revealed that incorporating targeted
training in areas where the model is weak played a pivotal role. This
iterative approach allowed the model to gradually enhance its proficiency in
handling specific domains. To see the raw results and code in more detail,
please access it here.

Figure 4: Amazon Dataset Figure 5: Amazon Dataset Plot Figure 6: Banking
Dataset Figure 7: Banking Dataset Plot Figure 8: Craigslist Dataset Figure 9:
Craigslist Dataset Plot Figure 10: Financial Phrasebank Dataset Figure 11:
Financial Phrasebank Dataset Plot Figure 12: Trec Coarse Label Dataset Figure
13: Trec Coarse Dataset Plot Figure 14: Trec Fine Label Dataset Figure 15:
Trec Fine Label Dataset Plot

##  7 Conclusion

Our investigation into few-shot learning and active learning methodologies is
promising in enhancing language models with minimal labeled data. We were able
to produce notable improvements in model accuracy, recall, and precision
across diverse domain-specific datasets by utilizing a continuous feedback
loop and integrating human expertise. The ability to leverage a minimal number
of labels to refine a model will be extremely beneficial to businesses.
Companies will be able to maintain model performance levels while minimizing
the resources typically required for manual labeling processes. While our
research demonstrated the potential of few-shot learning with human feedback,
there are some limitations. Our study is focused on a limited number of models
such as GPT, BERT, and SetFit. To gain a more comprehensive understanding of
the applicability of few-shot learning across various model structures, we can
expand the work to train a diverse array of models. We could test newer model
architectures like T5, Transformer-XL, or different BERT and GPT 4 variations.
Experimenting with additional models can provide deeper insights into the
effectiveness of these approaches.

##  8 Next Steps

To address these limitations, follow-up research could include training the
models on datasets with complex taxonomies and intricate label hierarchies. By
employing datasets from domains such as medical, legal, or financial fields
with complex taxonomies, we will challenge the model’s ability to generalize.
By looking at classification problems on millions of rows of data with
hundreds to thousands of categories and subcategories, the accuracy of these
models will be of significant importance for ROI in specific domains. This
will establish the foundation for using complex, industry-specific data to
train more accurate classification models, bridging the gap between model
performance and real-world application.

##  9 References

  1. 1.

What are Large Language Models (LLM)? https://aws.amazon.com/what-is/large-
language-model/, Accessed on 2023-12-17.

  2. 2.

Chen Yanhui. A Battle Against Amnesia: A Brief History and Introduction of
Recurrent Neural Networks. https://towardsdatascience.com/a-battle-against-
amnesia-a-brief-history-and-introduction-of-recurrent-neural-
networks-50496aae6740, Accessed on 2023-12-17.

  3. 3.

Kiel Dang. Language Model History — Before and After Transformer: The AI
Revolution. https://medium.com/@kirudang/language-model-history-before-and-
after-transformer-the-ai-revolution-bedc7948a130, Accessed on 2023-12-17.

  4. 4.

Sanchit Goel. Evolution of Transformers — Part 1.
https://sanchman21.medium.com/evolution-of-transformers-part-1-faac3f19d780,
Accessed on 2023-12-17.

  5. 5.

Liz McQuillan. Deep Learning 101: What Is a Transformer and Why Should I Care?
https://www.saltdatalabs.com/blog/deep-learning-101/what-is-a-transformer-and-
why-should-i-care, Accessed on 2023-12-17.

  6. 6.

Ashish Vaswani and Noam Shazeer and Niki Parmar and Jakob Uszkoreit and Llion
Jones and Aidan N. Gomez and Lukasz Kaiser and Illia Polosukhin. Attention Is
All You Need, 2023. arXiv:1706.03762.

  7. 7.

Shuohang Wang and Yang Liu and Yichong Xu and Chenguang Zhu and Michael Zeng.
Want To Reduce Labeling Cost? GPT-3 Can Help, 2021. arXiv:2108.13487.

  8. 8.

Lewis Tunstall and Nils Reimers and Unso Eun Seo Jo and Luke Bates and Daniel
Korat and Moshe Wasserblat and Oren Pereg. Efficient Few-Shot Learning Without
Prompts, 2022. arXiv:2209.11055.

  9. 9.

Curtis Northcutt and Anish Athalye and Jonas Mueller. Label Errors in ML Test
Sets. https://labelerrors.com, Accessed on 2023-12-23.

  10. 10.

Programmatic labeling. https://snorkel.ai/programmatic-labeling/, Accessed on
2023-12-23.

  11. 11.

Tom B. Brown and Benjamin Mann and Nick Ryder and Melanie Subbiah, et al.
Language Models are Few-Shot Learners, 2020. arXiv:2005.14165.

  12. 12.

Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv
Kulshreshtha, et al. LaMDA: Language Models for Dialog Applications, 2022.
arXiv:2201.08239.

  13. 13.

Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra
et al. PaLM: Scaling Language Modeling with Pathways, 2022. arXiv:2204.02311.

  14. 14.

Nan Du, Yanping Huang, Andrew M. Dai, Simon Tong, et al. GLaM: Efficient
Scaling of Language Models with Mixture-of-Experts, 2022. arXiv:2112.06905.

  15. 15.

Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, et al.
Flamingo: a Visual Language Model for Few-Shot Learning, 2022.
arXiv:2204.14198.

  16. 16.

Jack FitzGerald, Shankar Ananthakrishnan, Konstantine Arkoudas, Davide
Bernardi, et al. Alexa Teacher Model: Pretraining and Distilling Multi-
Billion-Parameter Encoders for Natural Language Understanding Systems. In
Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data
Mining (KDD ’22), August 2022. http://dx.doi.org/10.1145/3534678.3539173, DOI:
10.1145/3534678.3539173.

##  10 Appendix A: Dataset Descriptions

  1. 1.

Amazon Dataset

     * •

Description: Amazon product reviews

     * •

Source: Aymeric Roucher on HuggingFace

     * •

Size: 6000 rows

     * •

URL:
https://huggingface.co/datasets/A-Roucher/amazon_product_reviews_datafiniti

  2. 2.

Finance Phrasebank Dataset

     * •

Description: Finance phrases from news along with a rating out of 5 of whether
they are negative, neutral, or positive

     * •

Source: HuggingFace

     * •

Size: 4850 rows

     * •

URL: https://huggingface.co/datasets/financial_phrasebank

  3. 3.

TREC Dataset

     * •

Description: Text Retrieval Conference (TREC) with coarse labels and fine
labels

     * •

Source: HuggingFace

     * •

Size: 5450 rows

     * •

URL: https://huggingface.co/datasets/trec


# Conformalized Ordinal Classification with Marginal and Conditional Coverage

Subhrasish Chakraborty  Department of Mathematical Sciences
New Jersey Institute of Technology  Chhavi Tyagi  Department of Mathematical
Sciences
New Jersey Institute of Technology  Haiyan Qiao  School of Computer Science &
Engineering
California State University San Bernardino  Wenge Guo Author e-mail addresses:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Mathematical Sciences
New Jersey Institute of Technology

###### Abstract

Conformal prediction is a general distribution-free approach for constructing
prediction sets combined with any machine learning algorithm that achieve
valid marginal or conditional coverage in finite samples. Ordinal
classification is common in real applications where the target variable has
natural ordering among the class labels. In this paper, we discuss
constructing distribution-free prediction sets for such ordinal classification
problems by leveraging the ideas of conformal prediction and multiple testing
with FWER control. Newer conformal prediction methods are developed for
constructing contiguous and non-contiguous prediction sets based on marginal
and conditional (class-specific) conformal $p$-values, respectively.
Theoretically, we prove that the proposed methods respectively achieve
satisfactory levels of marginal and class-specific conditional coverages.
Through simulation study and real data analysis, these proposed methods show
promising performance compared to the existing conformal method.

KEY WORDS: Conformal prediction, ordinal classification, multiple testing,
FWER control, marginal coverage, class-specific conditional coverage

##  1 Introduction

Ordinal classification, also known as ordinal regression or ordinal
prediction, is a machine learning task that involves predicting a target
variable with ordered categories (McCullagh, 1980; Agresti, 2010). In ordinal
classification, the target variable has a natural ordering or hierarchy among
its categories, but the intervals between the categories may not be evenly
spaced or defined. Unlike regular classification, where the classes are
nominal and unordered, ordinal classification takes into account the ordering
relationship between the classes. This makes it suitable for situations where
the outcome variable has multiple levels of severity, satisfaction ratings, or
rankings. Here are a few examples of ordinal classification: customer
satisfaction levels, movie ratings, disease severity levels, and education
levels (Agresti, 2010).

In ordinal classification, the goal is to learn a model that can accurately
predict the ordinal variable’s value given a set of input features. The model
needs to understand the ordering of the classes and make predictions that
respect this order. In the literature, some conventional classification
algorithms have been adapted or modified to address ordinal classification,
for example, ordinal logistic regression, SVM, decision trees, random forest,
and neural networks (Harrell, 2015; da Costa et al., 2010; Kramer et al.,
2001; Janitza et al., 2016; Cheng et al., 2008). Some alternative methods are
also specifically developed for ordinal classification problems by fully
exploiting the ordinal structure of the response variables (Frank and Hall,
2001; Cardoso and da Costa, 2007; Gutiérrez et al., 2015). However, these
existing methods can only provide point prediction, which is not adequate in
some high stakes areas such as medical diagnosis and automatic driving.
Uncertainty quantification (UQ) techniques aim to go beyond point predictions
and provide additional information about the reliability of these predictions.
There are various techniques for UQ in machine learning, including Bayesian
methods, calibration, and conformal prediction (Hüllermeier and Waegeman,
2021).

Conformal prediction is a unique distribution-free UQ technique that provides
a prediction set rather than a point prediction for the true response with
guaranteed coverage (Vovk et al., 1999, 2005; Shafer and Vovk, 2008;
Angelopoulos and Bates, 2021; Fontana et al., 2023). It can be used as a
wrapper with any black-box algorithm. In this paper, we use the conformal
prediction technique to construct prediction sets for ordinal classification
problems. By combining the ideas of conformal prediction and multiple testing,
two new conformal prediction methods are introduced for constructing
contiguous and non-contiguous prediction sets. Firstly, the problem of ordinal
classification is reformulated as a problem of multiple testing; Secondly, for
each constructed hypothesis, the marginal and conditional conformal $p$-values
are respectively calculated; Thirdly, based on these marginal (conditional)
conformal $p$-values, three multiple testing procedures are developed for
controlling marginal (conditional) familywise error rate (FWER); Finally,
based on the testing outcomes of these procedures, the prediction sets are
constructed and proved having guaranteed marginal (conditional) coverage.

There are almost no works of applying conformal prediction to address ordinal
classification in the literature. To our knowledge, Lu et al. (2022) is the
only existing work, in which, a new (split) conformal prediction method is
developed for constructing adaptive contiguous prediction region. This method
is proved to have guaranteed marginal coverage, however, it cannot guarantee
to have more desired conditional coverage. Moreover, it does not work well for
high dimensional data. Compared to the method introduced in Lu et al. (2022),
our proposed methods generally show via theoretical and numerical studies
performing better in the settings of higher dimensions and in terms of class-
specific conditional coverage; especially for the conditional conformal
$p$-values based methods, they are proved to have guaranteed conditional
coverage.

The rest of this paper is structured as follows. In Section 2, we briefly
introduce split-conformal prediction and review related works, followed by
Section 3 which presents the development of our proposed conformal methods
using the idea of multiple testing. Section 4 provides numerical studies to
evaluate the performance of the proposed methods compared to the existing
method. Some discussions are presented in Section 5 and all proofs

##  2 Preliminaries

In this section, we briefly describe the conformal prediction framework and
review the related literature.

###  2.1 Conformal Prediction

Conformal prediction is a general approach to construct prediction sets
combined with a pre-trained classifier. The main advantage of this approach is
that it is distribution-free and can work with any black-box algorithm.
Conformal prediction is broadly of two types – full conformal prediction and
split-conformal prediction. The full conformal prediction uses all the
observations to train the black-box algorithms (Vovk et al., 2005). In
contrast, split-conformal prediction (Papadopoulos et al., 2002) involves
splitting the training data into proper training data to train the black-box
algorithm and calibration data to calculate the threshold for forming
prediction sets. Our proposed methods are based on the split-conformal method.
Consider a multi-class classification problem with feature space $\mathcal{X}$
and labels $\mathcal{Y}=\\{1,2,\cdots,K\\}$. Given the training observations
$(X_{i},Y_{i})_{i=1}^{2n}$ and a test input $X_{2n+1}$, the goal is to find a
prediction set $C(X_{2n+1}):\mathcal{X}\mapsto 2^{\mathcal{Y}}$ that contains
the unknown response $Y_{2n+1}$ with enough statistical coverage.

The split-conformal procedure suggests to split $2n$ observations to $n$
training observations, i.e., $(X_{i},Y_{i})_{i=1}^{n}$, which are used to
train $\hat{f}$, a black-box classifier such that
$\hat{f}:\mathcal{X}\mapsto\mathcal{Y}$ and the remaining $n$ observations
$(X_{i},Y_{i})_{i=n+1}^{2n}$ for calibration. The central part of this
technique involves calculating the conformity scores for each observation,
which measures how much the test observation conforms with the calibration
observations. There can be several choices of conformity scores for multi-
class classification problem, including posterior class probability,
cumulative probability, and regularized cumulative probability (Sadinle et
al., 2019; Romano et al., 2020; Angelopoulos et al., 2020). Given the score
function $s:\mathcal{X}\times\mathcal{Y}\mapsto\mathbb{R}$, the conformity
score for the $i^{th}$ calibration observation is defined as
$s_{i}=s(X_{i},Y_{i}),\hskip 5.69046pti=n+1,\cdots,2n$.

For a test input $X_{2n+1},$ we compute the conformity score for each class
label. Therefore, for a class label $y\in\mathcal{Y}$ the conformity score
corresponding to $(X_{2n+1},y)$ is $s_{2n+1}=s(X_{2n+1},y)$. By using the
conformity scores obtained for the calibration observations and the test input
coupled with a given label $y$, we can calculate the conformal $p$-value to
test whether the unknown true label $Y_{2n+1}$ corresponding to the test input
$X_{2n+1}$ is $y$ or not. The (marginal) conformal $p$-value is defined as,

$p(X_{2n+1},y)=\frac{\sum\limits_{i=n+1}^{2n}\mathbb{I}\left(s_{2n+1}\leq
s_{i}\right)+1}{n+1}.$ (1)

The final step involves constructing the prediction set
$C(X_{2n+1})=\\{y:p(X_{2n+1},y)\geq\alpha\\}$, which satisfies

$\mathbb{P}(Y_{2n+1}\in C(X_{2n+1}))\geq 1-\alpha,$ (2)

when the calibration and test observations $(X_{i},Y_{i})_{i=n+1}^{2n+1}$ are
exchangeably distributed, where $\alpha\in(0,1)$ is a pre-specified mis-
coverage level. Equation (2) is called marginal validity of the prediction set
$C(X_{2n+1})$. It guarantees that the true label $Y_{2n+1}$ is contained in
the prediction set with $100(1-\alpha)\%$ confidence. Vovk (2012) introduced
another type of conformal $p$-value which is called as the conditional
conformal $p$-value. Let $\mathcal{D}_{cal}=\\{n+1,\ldots,2n\\}$ denote the
indices of the calibration observations $(X_{i},Y_{i})_{i=n+1}^{2n}$. For a
test input $X_{2n+1}$ and any class $y=1,\dots,K$, the (class-specific)
conditional conformal $p$-value given $Y_{2n+1}=y$ is defined as

$p(X_{2n+1}|y)=\frac{\sum_{i\in\mathcal{I}_{y}}\mathbb{I}\\{s_{i}\leq
s_{2n+1}\\}+1}{n_{y}+1},$ (3)

where $\mathcal{I}_{y}=\\{i\in\mathcal{D}_{cal}:Y_{i}=y\\}$,
$n_{y}=|\mathcal{I}_{y}|$ is the size of $\mathcal{I}_{y}$, and
$s_{i}=s(X_{i},y)$ for $i=n+1,\ldots,2n+1$.

In general, the concept of conditional coverage such as object conditional
validity and class-specific conditional validity are more relevant to
practical applications (Vovk, 2012; Lei, 2014; Barber et al., 2021). If it is
satisfied, the more desired results are often guaranteed. Specifically, in
classification problems, class-specific conditional validity provides
conditional coverage for each given class, which is defined as

$\mathbb{P}(Y_{2n+1}\in C(X_{2n+1})|Y_{2n+1}=y)\geq 1-\alpha$ (4)

for any $y=1,\dots,K$. Proposition 1 and 2 below ensure that the marginal and
conditional conformal $p$-values are valid, which result in desired marginal
and (class-specific) conditional coverage.

To simplify the notation, we let $Z_{i}=(X_{i},Y_{i})$ for $i=1,\ldots,2n+1$
and denote the conformity scores of the calibration data,
$\\{Z_{i}\\}_{i=n+1}^{2n}$, as $s_{i}$’s, and the conformity score of the test
data, $Z_{2n+1}=(X_{2n+1},Y_{2n+1})$, as $s_{2n+1}$, where $Y_{2n+1}$ is
unknown. These notations are used in all propositions and theorems presented
in this paper.

######  Proposition 1.

Suppose that $\\{Z_{i}\\}_{i=1}^{2n+1}$ where $Z_{i}=(X_{i},Y_{i})$ are
exchangeable random variables, then the marginal conformal $p$-values defined
below as,

$p(Z_{2n+1})=\frac{\sum_{i=n+1}^{2n}\mathbb{I}(s_{i}\leq s_{2n+1})+1}{n+1}$
(5)

is valid in the sense that for any $t\in[0,1],$ we have

$\mathbb{P}(p(Z_{2n+1})\leq t)\leq t.$

Moreover, if the conformity scores $\\{s_{i}\\}_{i=n+1}^{2n+1}$ are distinct
surely, we have $p(Z_{2n+1})\sim U\Bigl{\\{}\frac{1}{n+1},\cdots,1\Bigl{\\}}$.

######  Proposition 2.

Suppose that $\\{Z_{i}\\}_{i=1}^{2n+1}$ where $Z_{i}=(X_{i},Y_{i})$ are
exchangeable random variables, then for any $y\in\mathcal{Y}$, given
$\mathcal{I}_{y}\subseteq\mathcal{D}_{cal}$ and $Y_{2n+1}=y$, the
corresponding conditional conformal $p$-value as defined in equation (3), is
conditionally valid in the sense that for any $t\in[0,1]$,

$\mathbb{P}\left(p(X_{2n+1}|y)\leq
t~{}\big{|}~{}\mathcal{I}_{y},Y_{2n+1}=y\right)\leq t.$

Moreover, if $\\{s_{i}\\}_{i\in\mathcal{I}_{y}\cup\\{2n+1\\}}$ are distinct
surely, we have that conditional on $\mathcal{I}_{y}$ and $Y_{2n+1}=y$,

$p(X_{2n+1}|y)\sim U\Bigl{\\{}\frac{1}{n_{y}+1},\cdots,1\Bigl{\\}}.$

###  2.2 Related work

The framework of Conformal prediction was introduced by Vladimir Vovk and his
collaborators Vovk et al. (1999, 2005) and has found many applications in
classification problems. Shafer and Vovk (2008) and Angelopoulos and Bates
(2021) provided a tutorial introduction and brief literature review on this
field. Several conformal methods have been developed to address binary
classification (Lei, 2014) and multi-class classification problems
(Hechtlinger et al., 2018; Sadinle et al., 2019; Romano et al., 2020;
Angelopoulos et al., 2020; Tyagi and Guo, 2023). Coverage guarantees of all
these methods are established under the assumption of exchangeability. Very
recently, some new conformal prediction methods have been developed in the
settings of non-exchangeability (Tibshirani et al., 2019; Cauchois et al.,
2021; Gibbs and Candes, 2021).

Although various conformal prediction methods have been developed for
conventional classification problems, however, to our knowledge, Lu et al.
(2022) is the only reference that is specifically devoted to address ordinal
classification problems using conformal prediction methods, in which an
adaptive conformal method is developed for constructing contiguous prediction
sets for ordinal response and is applied to AI disease rating in medical
imaging. In addition, Xu et al. (2023) is the closely related reference in
which newer methods are developed for two types of loss functions specially
designed for ordinal classification in the more general framework of conformal
risk control.

##  3 Method

In this section, we introduce several new conformal prediction methods for
ordinal classification problems, in which there is a natural ordering among
the classes labels. For simplicity, we assume a descending order of priority
from class $1$ to $K$ in the response space $\mathcal{Y}=\\{1,2,\cdots,K\\}$.

###  3.1 Problem Formulation

We formulate the ordinal classification problem as a multiple testing problem.
Specifically, by using the One-vs-All (OVA) strategy (Rifkin and Klautau,
2004), for each class label, we construct a hypothesis to test whether or not
a given test input $X_{2n+1}$ belongs to the particular class. The
construction of the hypothesis is described as follows,

$\centering H_{i}:Y_{2n+1}=i\hskip 11.38109pt\textnormal{ vs }\hskip
11.38109ptH^{\prime}_{i}:Y_{2n+1}\neq i,\@add@centering$ (6)

for $i=1,\cdots,K.$ It is easy to see that all these hypotheses are random and
there is only one true null. To test each individual hypothesis $H_{i}$, we
use the corresponding marginal conformal $p$-value $p(X_{2n+1},i)$; to test
$H_{1},\ldots,H_{K}$ simultaneously, we consider the following three
$p$-value-based testing procedures:

  * •

Procedure 1 : Test $H_{1},H_{2},\cdots,H_{K}$ sequentially. The test is
performed as follows.

    * –

If $p(X_{2n+1},1)\leq\alpha$, reject $H_{1}$, move to test $H_{2}$ else stop
testing;

    * –

For $i=2,\cdots,K-1$, if $p(X_{2n+1},i)\leq\alpha$, reject $H_{i}$, move to
test $H_{i+1}$ else stop testing;

    * –

If $p(X_{2n+1},K)\leq\alpha$, reject $H_{K}$ else stop testing.

  * •

Procedure 2 : Test $H_{K},H_{K-1},\cdots,H_{1}$ sequentially. The test is
performed as follows.

    * –

If $p(X_{2n+1},K)\leq\alpha$, reject $H_{K}$, move to test $H_{K-1}$ else stop
testing;

    * –

For $i=K-1,\cdots,2$, if $p(X_{2n+1},i)\leq\alpha$, reject $H_{i}$, move to
test $H_{i-1}$ else stop testing;

    * –

If $p(X_{2n+1},1)\leq\alpha$, reject $H_{1}$ else stop testing.

  * •

Procedure 3 : Single-step procedure with common critical value $\alpha$. This
procedure rejects any hypothesis $H_{i}$ if and only if
$p(X_{2n+1},i)\leq\alpha$.

Procedure 1 and 2 are two pre-ordered testing procedures for which Procedure 1
follows the same testing order as that of the $K$ classes whereas Procedure 2
uses the reverse order of these classes (Dmitrienko et al., 2009). Procedure 3
is actually a conventional Bonferroni procedure for a single true null. Since
there is only one true null among the $K$ tested hypotheses, by Proposition 1,
we have that all these three (marginal) conformal $p$-value based procedures
strongly control family-wise error rate (FWER) at a pre-specified level
$\alpha$ (Dmitrienko et al., 2009). For each Procedure $i,i=1,2,3$ defined
above, the index set $A_{i}$ of the accepted hypotheses is described as
follows,

  1. 1.

$A_{1}=\\{y_{min},y_{min}+1,\cdots,K\\}$, where
$y_{min}=\min\\{y\in\mathcal{Y}:p(X_{2n+1},y)>\alpha\\}$;

  2. 2.

$A_{2}=\\{1,2,\cdots,y_{max}\\}$, where
$y_{max}=\max\\{y\in\mathcal{Y}:p(X_{2n+1},y)>\alpha\\}$;

  3. 3.

$A_{3}=\\{y:p(X_{2n+1},y)>\alpha\\}$.

###  3.2 Ordinal Prediction Interval

Based on the the acceptance sets $A_{1}$ and $A_{2}$ of Procedure 1 and 2
given as above, we can obtain a new acceptance region $A_{12}=A_{1}\cap
A_{2}=\\{y_{min},\ldots,y_{max}\\}$, which is used to define the prediction
region $C(X_{2n+1})$ for the unknown response $Y_{2n+1}$. Specifically, the
prediction region $C(X_{2n+1})$ consists of the class labels for which the
corresponding hypotheses are both accepted by Procedure 1 and 2, resulting in
a contiguous set of labels $\\{y_{min},\ldots,y_{max}\\}$. This prediction
region is referred to as a prediction interval in this context. The procedure
for constructing the prediction interval $C(X_{2n+1})$ is summarized in
Algorithm 1 and illustrated in Figure 1.

Input: training set $\mathcal{D}_{train}=(X_{i},Y_{i})_{i=1}^{n}$, calibration
set $\mathcal{D}_{cal}=(X_{i},Y_{i})_{i=n+1}^{2n}$, test input $X_{2n+1}$,
black-box algorithm $\mathcal{A}$, conformity score function $s$, mis-coverage
level $\alpha.$

Output: Prediction interval, $C(X_{2n+1}).$

Train a classifier $\mathcal{A}$ on $\mathcal{D}_{train}$;

for  _$(X_{i},Y_{i})\in\mathcal{D}_{cal}$_ do

Compute conformity score $s_{i}=s(X_{i},Y_{i})$;

end for

For each $y\in\mathcal{Y}$, compute conformity score $s_{2n+1}=s(X_{2n+1},y)$
and corresponding conformal $p$-value $p(X_{2n+1},y)$ using equation (1);

$y_{min}=\min\\{y\in\mathcal{Y}:p(X_{2n+1},y)>\alpha\\}$ ;

$y_{max}=\max\\{y\in\mathcal{Y}:p(X_{2n+1},y)>\alpha\\}$ ;

Prediction interval, $C(X_{2n+1})=\\{y_{min},\ldots,y_{max}\\}$.}

Algorithm 1 Ordinal Prediction Interval Figure 1: Graphical representation of
Ordinal Prediction Interval (OPI) with $K$ nulls where $p(i)$ represents the
conformal $p$-values.

###  3.3 Ordinal Prediction Set

Our second method for constructing ordinal prediction regions is based on
Procedure 3. In this method, the prediction region $C(X_{2n+1})$ is defined
simply using the acceptance region $A_{3}$ of Procedure 3, that is,
$C(X_{2n+1})=\\{y\in\mathcal{Y}:p(X_{2n+1},y)>\alpha\\}$. Specifically, the
prediction region consists of any class labels for which the corresponding
hypotheses are not rejected by Procedure 3, resulting in a non-contiguous set
of labels. This prediction region is referred to as a prediction set in this
context. The procedure for constructing the prediction set is detailed in
Algorithm 2 below.

Input: training set $\mathcal{D}_{train}=(X_{i},Y_{i})_{i=1}^{n}$, calibration
set $\mathcal{D}_{cal}=(X_{i},Y_{i})_{i=n+1}^{2n}$, test observation
$X_{2n+1}$, black-box algorithm $\mathcal{A}$, conformity score function $s$,
mis-coverage level $\alpha.$

Output: Prediction set, $C(X_{2n+1}).$

Train a classifier $\mathcal{A}$ on $\mathcal{D}_{train}$;

for  _$(X_{i},Y_{i})\in\mathcal{D}_{cal}$_ do

Compute conformity score $s_{i}=s(X_{i},Y_{i})$;

end for

For each $y\in\mathcal{Y}$, compute conformity score $s_{2n+1}=s(X_{2n+1},y)$
and corresponding conformal $p$-value $p(X_{2n+1},y)$ using equation (1);

Prediction Set, $C(X_{2n+1})=\\{y:p(X_{2n+1},y)>\alpha\\}$.

Algorithm 2 Ordinal Prediction Set

In the following, we present two results regarding the FWER control of
Procedure 1-3 and (marginal) coverage guarantees of Algorithm 1-2 introduced
as above.

######  Proposition 3.

Suppose that $(X_{i},Y_{i})_{i=n+1}^{2n+1}$ are exchangeable random variables,
then Procedure 1-3 based on marginal conformal $p$-values, all strongly
control the FWER at level $\alpha$, i.e., $FWER\leq\alpha$. Specifically, if
the conformity scores $\\{s_{i}\\}_{i=n+1}^{2n+1}$ are distinct surely, then
for Procedure 3, we also have, $FWER\geq\alpha-\frac{1}{n+1}.$

######  Theorem 1.

Suppose that $(X_{i},Y_{i})_{i=n+1}^{2n+1}$ are exchangeable random variables,
then the prediction region $C(X_{2n+1})$ determined by Algorithm 1 and 2 both
satisfy

$\mathbb{P}(Y_{2n+1}\in C(X_{2n+1}))\geq 1-\alpha.$

Specifically, for $C(X_{2n+1})$ determined by Algorithm 2, if the conformity
scores $\\{s_{i}\\}_{i=n+1}^{2n+1}$ are distinct surely, we have

$\mathbb{P}(Y_{2n+1}\in C(X_{2n+1}))\leq 1-\alpha+\frac{1}{n+1}.$

###  3.4 Class-specific conditional coverage

To achieve more desired class-specific conditional coverage for our
constructed prediction intervals and prediction sets, in Procedure 1-3 we use
(class-specific) conditional conformal $p$-values $p(X_{2n+1}|y)$ as described
in equation (3), instead of the marginal conformal $p$-values $p(X_{2n+1},y)$
for simultaneously testing $H_{1},\ldots,H_{K}$ formulated in equation (6). It
is shown in Proposition 4 below that all these three modified procedures
strongly control the conditional familywise error rate (FWER) at level
$\alpha$, i.e., $\text{FWER}_{y}=\mathbb{P}(V>0|Y_{2n+1}=y)\leq\alpha$, for
any $y\in\mathcal{Y}$, where $V$ is the number of type 1 errors. This result
in turn leads to that the prediction regions $C(X_{n+1}|y)$ constructed by
Algorithm 1 and 2 based on $p(X_{2n+1}|y)$ satisfy more desired (class-
specific) conditional coverage, as stated in Theorem 2.

######  Proposition 4.

Under the same exchangeability assumption as in Proposition 2, Procedure 1-3
based on conditional conformal $p$-values $p(X_{2n+1}|y)$ all strongly control
the conditional FWER at level $\alpha$, i.e., for any $y\in\mathcal{Y}$,

$FWER_{y}=\mathbb{P}\\{\textnormal{reject}~{}H_{y}|Y_{2n+1}=y\\}\leq\alpha.$

Specifically, if the conformity scores
$\\{s_{i}\\}_{i\in\mathcal{I}_{y}\cup\\{2n+1\\}}$ are distinct surely, then
for Procedure 3 based on $p(X_{2n+1}|y)$, we have that for any
$y\in\mathcal{Y}$ and $\mathcal{I}_{y}\subseteq\mathcal{D}_{cal}$.

$\mathbb{P}(\textnormal{reject}~{}H_{y}|Y_{2n+1}=y,\mathcal{I}_{y})\geq\alpha-\frac{1}{n_{y}+1}.$

######  Theorem 2.

Under the same exchangeability assumption as in Theorem 1, the prediction
region $C(X_{2n+1}|y)$ determined by Algorithm 1 or 2 based on conditional
conformal $p$-values $p(X_{2n+1}|y)$ satisfies

$\mathbb{P}\left(Y_{2n+1}\in C(X_{2n+1}|y)~{}\big{|}Y_{2n+1}=y\right)~{}\geq
1-\alpha$

for any $y\in\mathcal{Y}$. Specifically, for the prediction set $C(X_{n+1}|y)$
determined by Algorithm 2 based on $p(X_{2n+1}|y)$, if the conformity scores
$\\{s_{i}\\}_{i\in\mathcal{I}_{y}\cup\\{2n+1\\}}$ are distinct surely, we have

$\mathbb{P}\left(Y_{2n+1}\in
C(X_{2n+1}|y)~{}\big{|}Y_{n+1}=y,\mathcal{I}_{y}\right)\leq
1-\alpha+\frac{1}{n_{y}+1}$

for any $y\in\mathcal{Y}$ and $\mathcal{I}_{y}\subseteq\mathcal{D}_{cal}$.

##  4 Numerical Study

In this section, we evaluate the performance of our four proposed methods,
Ordinal Prediction Interval (OPI) in Algorithm 1 based on marginal conformal
$p$-values (marginal OPI), the OPI based on conditional conformal $p$-values
(conditional OPI), Ordinal Prediction Set (OPS) in Algorithm 2 based on
marginal conformal $p$-values (marginal OPS), and the OPS based on conditional
conformal $p$-values (conditional OPS), in comparison with the existing
counterpart developed in Lu et al. (2022), Ordinal Adaptive Prediction Set
(OAPS), on simulated data and one real dataset. The comparison is based on the
marginal coverage, average set size, and class-specific conditional coverage
of the prediction regions for a pre-specified level $\alpha$. The empirical
metric we use to measure the class-specific conditional coverage (CCV) of the
above methods is defined as

$CCV=\max\limits_{y\in\\{1,2,\cdots,K\\}}\\{(1-\alpha)-P_{y},0\\},$

where $P_{y}$ is the estimate of $\mathbb{P}(Y\in C(X_{2n+1}|y)~{}|Y=y)$ and
$C(X_{2n+1}|y)$ is the prediction region obtained from Algorithm 1 or 2 using
conditional conformal $p$-values for any $y\in\mathcal{Y}$. Intuitively, the
metric measures the maximum of the deviance of the conditional coverage for
each of the classes from the desired level of conditional coverage $1-\alpha$.

In the whole numerical investigations including simulation studies and real
data analysis, we use the logistic regression algorithm as the black-box
algorithm for our experiments and compute the conformity scores as estimated
posterior probabilities of classes.

###  4.1 Simulations

We present the simulation study to evaluate the performance of our proposed
methods along with the existing method. We consider two simulation settings
below, a Gaussian mixture model and a sparse model.

  1. 1.

Gaussian mixture.
$(X|Y=k)\sim\pi_{1}N_{d}(\mu_{k},\Sigma)+\pi_{2}N_{d}(\mu_{k+1},\Sigma)$ for
$k=1,2,3$ and $(X|Y=4)\sim\pi_{1}N(\mu_{4};\Sigma)+\pi_{2}N(\mu_{1};\Sigma)$
with $\pi_{1}=0.2,\pi_{2}=0.8$.

In the above setting, we set $d=2$, $\mu_{1}=(-1,0)$, $\mu_{2}=(-1,-1)$,
$\mu_{3}=(0,-1)$, $\mu_{4}=(1,-1)$, and $\Sigma$ as the equal correlation
matrix with correlation $=0.1$.

2\. Sparse model. The sparse model is generated with different dimensions of
feature vector with $d=5,10,20,50,\text{ or }100$. The features are generated
with $X_{i}\sim N(0,1)$ with $Cov(X_{i},X_{j})=0.5$ for $i\neq j.$ The class
labels are generated using the sigmoid function $f(x)$ and the the following
decision rule,

$Y_{i}=k\hskip 11.38109ptif\hskip 11.38109pt\frac{k-1}{4}\leq
f(x_{i})<\frac{k}{4},\hskip 5.69054ptwhere\hskip 5.69054ptk=1,2,3,4,$

where $f(x)={1}/{(1+e^{-\beta^{{}^{\prime}}x})}$ with
$\beta=(\beta_{1},\cdots,\beta_{d})^{\prime}$ and
$x=(x_{1},\ldots,x_{d})^{\prime}$. The value of $\beta$ is set as
$(\beta_{1},\ldots,\beta_{5})=(1,1,1,-\sqrt{2},1)$, and $\beta_{i}=0$ for any
$5<i\leq d$.

The sample size for these two simulation settings is 2,000, out of which 500
samples have been used to train the classifier, 525 observations for
calibration, and 975 for validation. The simulations are repeated 500 times,
and the results are averaged to obtain the final performance metrics.

Figure 2: Performance comparison of four proposed methods OPS and OPI using
marginal and conditional conformal $p$-values with the existing Ordinal APS
under simulation setting 1 in terms of marginal coverage (left), average set
size (middle) and class-specific conditional coverage (right) of the
prediction sets.

Figure 2 displays the performance of our proposed methods along with the
existing method under simulation setting 1. It can be seen from the left panel
of Figure 2 that all these five methods empirically achieve the desired level
of marginal coverage. The middle panel of Figure 2 compares the set sizes of
the prediction regions corresponding to these five methods. It can be seen
from the figure that the marginal OPS and the conditional OPS use shorter set
sizes to attain the proper marginal coverage than the existing OAPS whereas
the OAPS has shorter set sizes than the marginal OPI and the conditional OPI.
Finally, while the marginal coverage is guaranteed by all the methods, the
right panel of Figure 2 shows their differences in class-specific conditional
coverage; the existing OAPS exhibits the largest value of CCV compared to the
proposed methods and among the four proposed methods, the conditional OPI and
conditional OPS exhibit lower values of CCV than the marginal OPI and marginal
OPS.

Figure 3: Performance comparison of four proposed methods with existing
Ordinal APS under simulation setting 2 with different dimensions of inputs and
fixed mis-coverage level $\alpha=0.1$ in terms of marginal coverage (left),
average set size (middle) and CCV (right) of the prediction sets.

Figure 3 shows the performance of our proposed methods along with the existing
method under simulation setting 2 with different dimensions of inputs. It can
be seen from the left panel of this figure that all these methods empirically
achieve desired marginal coverage for lower dimensions, however, the existing
OAPS massively undercovers for higher dimensions and thus loses the control of
mis-coverage rate. From the middle and right panels of Figure 3, we can also
see that the conditional OPI and conditional OPS achieve lower values of CCV
than the existing OAPS, although the OAPS has the lower set sizes than our
proposed methods for various dimensions of input.

###  4.2 Application to real data

We also evaluate the performance of our proposed methods on a real dataset,
Traffic accident data, which is publicly available on the website of Leeds
City Council. The real data consists of 1,908 traffic accidents that occurred
in the year 2019. The objective is to predict the severity of the casualties,
which are classified into three categories – mild, serious, and fatal based on
the features available. In the numerical experiment, 500 observations are used
to train the logistic regression model, $35\%$ of the remaining observations
are used for calibration, and $65\%$ for validation. Figure 4 shows that all
these methods empirically achieve desired marginal coverage for different
levels of mis-coverage, however, the proposed marginal OPI and marginal OPS,
and existing OAPS have lower set sizes than the conditional OPI and
conditional OPS. It is also evident from Figure 4 that the proposed
conditional OPS and conditional OPI both attain desired class-specific
conditional coverage unlike the existing method, OAPS, which seems to largely
deviate from the desired level of conditional coverage.

Figure 4: Performance comparison of four proposed methods OPS and OPI using
marginal and conditional conformal $p$-values with the existing Ordinal APS in
terms of marginal coverage (left), average set size (middle) and CCV (right)
of the prediction regions for Traffic Accident Data.

##  5 Concluding Remarks

In this paper, we discussed the ordinal classification problem in the
framework of conformal prediction and introduced two types of conformal
methods, OPI and OPS, for constructing distribution-free contiguous prediction
regions and non-contiguous prediction sets, respectively. These methods are
developed by leveraging the idea of multiple testing with the FWER control and
are specifically designed based on marginal conformal $p$-values and (class-
specific) conditional conformal $p$-values, respectively. Theoretically, it
was proved that the proposed methods based on marginal and conditional
$p$-values respectively achieve satisfactory levels of marginal and class-
specific conditional coverages. Through some numerical investigations
including simulations and real data analysis, our proposed methods show
promising results for the settings of higher dimensions and for class-specific
conditional coverage.

This paper discussed constructing valid prediction set for single test input.
It would be interesting to discuss how to construct (simultaneous) prediction
sets for multiple test inputs with some overall error control such as false
discovery rate (FDR) control. Another interesting extension might be to relax
the conventional distributional assumption we used for classification
problems, for which the training data and the test data follow from the same
distribution. It will be interesting to see whether the proposed methods can
be extended to the settings of distribution shift where the training and test
data sets have different distributions.

## References

  * Agresti (2010) Alan Agresti.  _Analysis of ordinal categorical data_.  John Wiley & Sons, 2010.
  * Angelopoulos and Bates (2021) A.N. Angelopoulos and S. Bates.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification.  _arXiv preprint arXiv:2107.07511_ , 2021.
  * Angelopoulos et al. (2020) Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I. Jordan.  Uncertainty sets for image classifiers using conformal prediction.  _arXiv preprint arXiv:2009.14193_ , 2020.
  * Barber et al. (2021) Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani.  The limits of distribution-free conditional predictive inference.  _Information and Inference: A Journal of the IMA_ , 10(2):455–482, 2021.
  * Cardoso and da Costa (2007) Jaime Cardoso and Joaquim Pinto da Costa.  Learning to classify ordinal data: The data replication method.  _Journal of Machine Learning Research_ , 8:1393–1429, 2007.
  * Cauchois et al. (2021) Maxime Cauchois, Suyash Gupta, and John C Duchi.  Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction.  _The Journal of Machine Learning Research_ , 22(1):3681–3722, 2021.
  * Cheng et al. (2008) Jianlin Cheng, Zheng Wang, and Gianluca Pollastri.  A neural network approach to ordinal regression.  In _2008 IEEE International Joint Conference on Neural Networks_ , pages 1279–1284. IEEE, 2008.
  * da Costa et al. (2010) Joaquim F Pinto da Costa, Ricardo Sousa, and Jaime S Cardoso.  An all-at-once unimodal svm approach for ordinal classification.  In _2010 Ninth International Conference on Machine Learning and Applications_ , pages 59–64. IEEE, 2010.
  * Dmitrienko et al. (2009) Alex Dmitrienko, Ajit C Tamhane, and Frank Bretz.  _Multiple testing problems in pharmaceutical statistics_.  CRC press, 2009.
  * Fontana et al. (2023) Matteo Fontana, Gianluca Zeni, and Simone Vantini.  Conformal prediction: a unified review of theory and new challenges.  _Bernoulli_ , 29(1):1–23, 2023.
  * Frank and Hall (2001) Eibe Frank and Mark Hall.  A simple approach to ordinal classification.  In _12th European Conference on Machine Learning, Proceedings 12_ , pages 145–156. Springer, 2001.
  * Gibbs and Candes (2021) Isaac Gibbs and Emmanuel Candes.  Adaptive conformal inference under distribution shift.  _Advances in Neural Information Processing Systems_ , 34:1660–1672, 2021.
  * Gutiérrez et al. (2015) Pedro Antonio Gutiérrez, Maria Perez-Ortiz, Javier Sanchez-Monedero, Francisco Fernandez-Navarro, and Cesar Hervas-Martinez.  Ordinal regression methods: survey and experimental study.  _IEEE Transactions on Knowledge and Data Engineering_ , 28(1):127–146, 2015.
  * Harrell (2015) Frank E Harrell.  Ordinal logistic regression.  In _Regression modeling strategies: with applications to linear models, logistic and ordinal regression, and survival analysis_ , pages 311–325. Springer, 2015.
  * Hechtlinger et al. (2018) Yotam Hechtlinger, Barnabás Póczos, and Larry Wasserman.  Cautious deep learning.  _arXiv preprint arXiv:1805.09460_ , 2018.
  * Hüllermeier and Waegeman (2021) Eyke Hüllermeier and Willem Waegeman.  Aleatoric and epistemic uncertainty in machine learning: an introduction to concepts and methods.  _Machine Learning_ , 110:457–506, 2021.
  * Janitza et al. (2016) Silke Janitza, Gerhard Tutz, and Anne-Laure Boulesteix.  Random forest for ordinal responses: prediction and variable selection.  _Computational Statistics & Data Analysis_, 96:57–73, 2016.
  * Kramer et al. (2001) Stefan Kramer, Gerhard Widmer, Bernhard Pfahringer, and Michael De Groeve.  Prediction of ordinal classes using regression trees.  _Fundamenta Informaticae_ , 47(1-2):1–13, 2001.
  * Lei (2014) J. Lei.  Classification with confidence.  _Biometrika_ , 101(4):755–769, 2014.
  * Lu et al. (2022) C. Lu, A.N. Angelopoulos, and S. Pomerantz.  Improving trustworthiness of ai disease rating in medical imaging with ordinal conformal prediction sets.  _arXiv preprint arXiv:2207.02238_ , 2022.
  * McCullagh (1980) Peter McCullagh.  Regression models for ordinal data.  _Journal of the Royal Statistical Society B_ , 42:109–142, 1980.
  * Papadopoulos et al. (2002) Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman.  Inductive confidence machines for regression.  In _13th European Conference on Machine Learning, Proceedings 13_ , pages 345–356. Springer, 2002.
  * Rifkin and Klautau (2004) Ryan Rifkin and Aldebaro Klautau.  In defense of one-vs-all classification.  _The Journal of Machine Learning Research_ , 5:101–141, 2004.
  * Romano et al. (2020) Y. Romano, M. Sesia, and E. Candès.  Classification with valid and adaptive coverage.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 3581–3591, 2020.
  * Sadinle et al. (2019) M. Sadinle, J. Lei, and L. Wasserman.  Least ambiguous set-valued classifiers with bounded error levels.  _Journal of American Statistical Association_ , 114:223–234, 2019.
  * Shafer and Vovk (2008) G. Shafer and V. Vovk.  A tutorial on conformal prediction.  _Journal of Machine Learning Research_ , 9:371–421, 2008.
  * Tibshirani et al. (2019) Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas.  Conformal prediction under covariate shift.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Tyagi and Guo (2023) Chhavi Tyagi and Wenge Guo.  Multi-label classification under uncertainty: a tree-based conformal prediction approach.  In _Conformal and Probabilistic Prediction with Applications_ , pages 488–512. PMLR, 2023.
  * Vovk et al. (2005) V. Vovk, A. Gammerman, and G. Shafer.  _Algorithmic learning in a random world_.  Springer, 2005.
  * Vovk (2012) Vladimir Vovk.  Conditional validity of inductive conformal predictors.  In _Asian Conference on Machine Learning_ , pages 475–490. PMLR, 2012.
  * Vovk et al. (1999) Vladimir Vovk, Alex Gammerman, and Craig Saunders.  Machine-learning applications of algorithmic randomness.  In _Sixteenth International Conference on Machine Learning_ , pages 444–453, 1999.
  * Xu et al. (2023) Yunpeng Xu, Wenge Guo, and Zhi Wei.  Conformal risk control for ordinal classification.  In _Uncertainty in Artificial Intelligence_ , pages 2346–2355. PMLR, 2023.

##  Appendix A Proofs

###  A.1 Proof of Proposition 1

###### Proof.

Suppose, for any given values of conformity scores, $v_{1},\cdots,v_{n+1},$
they can be rearranged as $\tilde{v}_{1}<\cdots<\tilde{v}_{k}$ with
repetitions $n_{i}$ of $\tilde{v}_{i}$ such that $\sum_{i=1}^{k}n_{i}=n+1$.
Let $E_{v}$ denote the event of
$\\{s_{n+1},\cdots,s_{2n+1}\\}=\\{v_{1},\cdots,v_{n+1}\\}$. Then, under
$E_{v}$, for $i=1,\cdots,k$, we have

$\mathbb{P}(s_{2n+1}=\tilde{v}_{i}|E_{v})=\frac{n_{i}}{n+1},$

due to the exchangeability of $s_{i}$’s,

We also note that under $E_{v}$ and $s_{2n+1}=\tilde{v}_{i}$ we have from
equation (5),

$p(Z_{2n+1})=\frac{\sum_{l=1}^{i}n_{l}}{n+1}.$ (7)

Then, for any $t\in[0,1]$ and $i=1,\cdots,k$, we have

$\mathbb{P}(p(Z_{2n+1})\leq
t|E_{v},s_{2n+1}=\tilde{v}_{i})=\begin{cases}0&\text{if
}t<\frac{\sum_{l=1}^{i}n_{l}}{n+1},\\\ 1&\text{o.w.}\end{cases}$ (8)

Thus, for any $i=1,\cdots,k$ and $\frac{\sum_{l=1}^{i-1}n_{l}}{n+1}\leq
t<\frac{\sum_{l=1}^{i}n_{l}}{n+1}$, we have

$\displaystyle\qquad\mathbb{P}(p(Z_{2n+1})\leq t|E_{v})$
$\displaystyle=\sum_{l=1}^{k}\mathbb{P}(p(Z_{2n+1})\leq
t|E_{v},s_{2n+1}=\tilde{v}_{l})\cdot\mathbb{P}(s_{2n+1}=\tilde{v}_{l}|E_{v})$
$\displaystyle=\frac{\sum_{l=1}^{i-1}n_{l}}{n+1}\leq t.$

By taking the expectation on the above inequality, it follows that the
conformal $p$-value $p(Z_{2n+1})$ is marginally valid.

Specifically, if conformity scores $\\{s_{i}\\}_{i=n+1}^{2n+1}$ are distinct
surely, then $k=n+1$ and $n_{i}=1$ for $i=1,\ldots,n+1$. Thus,

$\mathbb{P}\left(p(Z_{2n+1})\leq t|E_{v}\right)=\frac{i-1}{n+1},\textnormal{
if }\frac{i-1}{n+1}\leq t<\frac{i}{n+1},$

that is,

$p(Z_{2n+1})|E_{v}\sim U\Bigl{\\{}\frac{1}{n+1},\cdots,1\Bigl{\\}}.$

This completes the proof. ∎

###  A.2 Proof of Proposition 2

###### Proof.

For any given $y\in\mathcal{Y}$, the corresponding (class-specific)
conditional conformal $p$-value is given by

$p(X_{2n+1}|y)=\frac{1}{n_{y}+1}\left[\sum_{i\in\mathcal{I}_{y}}\mathbb{I}\\{s_{i}\leq
s_{2n+1}\\}+1\right],$ (9)

where $\mathcal{I}_{y}=\\{i:(X_{i},Y_{i})\in\mathcal{D}_{cal},Y_{i}=y\\}$,
$n_{y}=|\mathcal{I}_{y}|$, $s_{i}=s(X_{i},y)$ for $i\in\mathcal{I}_{y}$, and
$s_{2n+1}=s(X_{2n+1},y)$. Given $I_{y}$ and $Y_{2n+1}=y$,
$(X_{i})_{i\in\mathcal{I}_{y}}\cup\\{X_{2n+1}\\}$ are exchangeably
distributed, which is due to the assumption that $(X_{i},Y_{i})_{i=1}^{2n+1}$
are exchangeably distributed. Using the similar arguments as in the proof of
Proposition 1, for any given values of $v_{1},\cdots,v_{n_{y}+1}$, suppose
that they can be arranged as $\tilde{v}_{1}<\cdots<\tilde{v}_{l}$ with
repetitions $m_{i}$ of $\tilde{v}_{i}$ such that
$\sum_{i=1}^{l}m_{i}=n_{y}+1$.

Let $E_{v}$ denote the event
$\\{s_{i}\\}_{i\in\mathcal{I}_{y}}\cup\\{s_{2n+1}\\}=\\{v_{1},\cdots,v_{n_{y}+1}\\}$.
Then, given $E_{v},I_{y}$, and $Y_{2n+1}=y$, we have

$\mathbb{P}(s_{2n+1}=\tilde{v}_{i}|E_{v},I_{y},Y_{2n+1}=y)=\frac{m_{i}}{n_{y}+1}$

for $i=1,\cdots,l$ and $y=1,\cdots,K$, due to exchangeability of $s_{i}$,
$i\in I_{y}\cup\\{2n+1\\}$ given $I_{y}$, which in turn is due to
exchangeability of $(X_{i},Y_{i})_{i=1}^{2n+1}$. Note that given $E_{v}$,
$I_{y}$, $Y_{2n+1}=y$, and $s_{2n+1}=\tilde{v}_{i}$, we have from equation
(9),

$p(X_{2n+1}|y)=\frac{\sum_{j=1}^{i}m_{j}}{n_{y}+1}.$

Thus, for any $t\in[0,1]$ and $i=1,\cdots,l$,

$\mathbb{P}\left(p(X_{2n+1}|y)\leq
t\big{|}E_{v},I_{y},Y_{2n+1}=y,s_{2n+1}=\tilde{v}_{i}\right)=\begin{cases}0&\text{if
}t<\frac{\sum_{j=1}^{i}m_{j}}{n_{y}+1},\\\ 1&\text{o.w.}\end{cases}$ (10)

Then, for any given $i=1,\cdots,l$ and
$\frac{\sum_{j=1}^{i}m_{j}}{n_{y}+1}\leq
t<\frac{\sum_{j=1}^{i+1}m_{j}}{n_{y}+1}$, we have

$\displaystyle\qquad\mathbb{P}\left(p(X_{2n+1}|y)\leq
t\big{|}E_{v},I_{y},Y_{2n+1}=y\right)$
$\displaystyle=\sum_{j=1}^{l}\mathbb{P}\left(p(X_{2n+1}|y)\leq
t\big{|}E_{v},I_{y},Y_{2n+1}=y,s_{2n+1}=\tilde{v}_{i}\right)\cdot\mathbb{P}\left(s_{2n+1}=\tilde{v}_{i}\big{|}E_{v},I_{y},Y_{2n+1}=y\right)$
$\displaystyle=\frac{\sum_{j=1}^{i}m_{j}}{n_{y}+1}\leq t.$

By taking expectation, it follows that $p(X_{2n+1}|y)$ is conditionally valid
given $Y_{2n+1}=y$. ∎

###  A.3 Proof of Proposition 3

###### Proof.

Consider Procedure 1-3 based on marginal conformal $p$-values. Note that among
the tested hypotheses $H_{1},\ldots,H_{K}$, there is exactly one hypothesis
$H_{Y_{2n+1}}$ to be true. Thus, the FWER of Procedure 1-3 are all equal to

$\mathbb{P}(\text{reject
}H_{Y_{2n+1}})\leq\mathbb{P}\left(p(X_{2n+1},Y_{2n+1})\leq\alpha\right)\leq\alpha,$

where the last inequality follows by Proposition 1.

Specifically, for Procedure 3, if the conformity scores
$\\{s_{i}\\}_{i=n+1}^{2n+1}$ are distinct surely, by Proposition 1, we have

$\displaystyle\qquad\text{FWER}=\mathbb{P}(\text{reject
}H_{Y_{2n+1}})=\mathbb{P}\Bigl{\\{}p(X_{2n+1},Y_{2n+1})\leq\alpha\Bigl{\\}}~{}\geq\alpha-\frac{1}{n+1},$

the desired result. ∎

###  A.4 Proof of Theorem 1

###### Proof.

Note that the prediction set derived from Algorithm 1 is given by
$C(X_{2n+1})=A_{1}\cap A_{2}.$ Thus, by Proposition 1,

$\mathbb{P}(Y_{2n+1}\in
C(X_{2n+1}))\geq\mathbb{P}(p(X_{2n+1}),Y_{2n+1})>\alpha)\geq 1-\alpha.$

Similarly, for Algorithm 2, its prediction set is given by
$C(X_{2n+1})=\\{y\in\mathcal{Y}:p(X_{2n+1},y)>\alpha\\}.$ By Proposition 1, it
is easy to check that

$\displaystyle\mathbb{P}(Y_{2n+1}\in
C(X_{2n+1}))=\mathbb{P}(p(X_{2n+1},Y_{2n+1})>\alpha)\geq 1-\alpha.$

Specifically, if the conformity scores $\\{s_{i}\\}_{i=1}^{2n+1}$ are distinct
surely, for Algorithm 2, we have

$\mathbb{P}(Y_{2n+1}\in
C(X_{2n+1}))=1-\mathbb{P}(p(X_{2n+1},Y_{2n+1})\leq\alpha)\leq
1-\alpha+\frac{1}{n+1}.$

This completes the proof. ∎

###  A.5 Proof of Proposition 4

###### Proof.

Consider Procedure 1-3 based on conditional conformal $p$-values. For any
$y=1,\cdots,K$, given $Y_{2n+1}=y$, the conditional FWER of Procedure 1-3 are
all equal to

$\mathbb{P}(\text{reject
}H_{y}|Y_{2n+1}=y)\leq\mathbb{P}(p(X_{2n+1}|y)\leq\alpha|Y_{2n+1}=y)\leq\alpha,$

where the inequalities follow the definitions of Procedure 1-3 and Proposition
2.

Specifically, for Procedure 3, if the conformity scores
$\\{s_{i}\\}_{i\in\mathcal{I}_{y}\cup\\{2n+1\\}}$ are distinct surely, then by
Proposition 2, the FWER conditional on $I_{y}$ and $Y_{2n+1}=y$ is equal to

$\displaystyle\mathbb{P}\Bigl{\\{}\text{reject}~{}H_{y}~{}\big{|}I_{y},Y_{2n+1}=y\Bigl{\\}}=\mathbb{P}(p(X_{2n+1}|y)\leq\alpha|I_{y},Y_{2n+1}=y)\geq\alpha-\frac{1}{n_{y}+1}.$

This completes the proof. ∎

###  A.6 Proof of Theorem 2

###### Proof.

By using Proposition 4 and the similar arguments as in the proof of Theorem 1,
the prediction sets $C(X_{2n+1}|y)$ derived from Algorithm 1 and 2 based on
the conditional conformal $p$-values $p(X_{2n+1}|y)$ all satisfy,

$\mathbb{P}\Bigl{\\{}Y_{2n+1}\in
C(X_{2n+1}|y)~{}\big{|}I_{y},Y_{2n+1}=y\Bigl{\\}}~{}\geq 1-\alpha$

for any $y=1,\ldots,K$. Specifically, if the conformity scores
$\\{s_{i}\\}_{i\in\mathcal{I}_{y}\cup\\{2n+1\\}}$ are distinct surely, for
Algorithm 2, we have

$\displaystyle\mathbb{P}\Bigl{\\{}Y_{2n+1}\in
C(X_{2n+1}|y)~{}\big{|}I_{y},Y_{2n+1}=y\Bigl{\\}}$
$\displaystyle=\mathbb{P}\Bigl{\\{}p(X_{2n+1}|y)>\alpha~{}\big{|}I_{y},Y_{2n+1}=y\Bigl{\\}}$
$\displaystyle\leq 1-\alpha+\frac{1}{n_{y}+1},$

the desired result. ∎